Design Pattern: managing a limited number of a resource

Question

I am in the process of designing a feature for a system where I strongly feel that there must be a pattern for this out there, that I should know about before diving into the code.

The scenario is this:

• I have a pool of resources of which I have a limited number.
• I have a variable number of consumers that use those resources; each consumer needs exactly one resource, and it may not use the same resource as any other consumer at a given time.
• The consumers are divided into a fixed number of groups, and the system needs to guarantee that there is a minimum of one resource for each group.
• The number of consumers in each group varies over time; they are allocated and deallocated as needed.

My current approach is to put the resources into two stacks at startup: one "emergency stack" and one "common stack". The emergency stack will contain the same number of resources as there are groups (so, one for each group). The rest of the available resources go into the common stack.

When a new consumer is about to be created, the system will request a resource. If there are resources available in the common stack, one will be popped from it and returned to the caller. If the common stack is empty, a resource may be popped from the emergency stack instead, but only if there are no consumers within the same group that already has an emergency resource.

Whenever a consumer within a group can be deallocated, the associated resource will be returned, and pushed onto one of the resource stacks. The code responsible for deallocating consumers will make sure to always return any emergency resources first, so that the emergency stack is filled, before returned resources are being pushed onto the common stack.

I feel that this is the sort of problem for which there ought to exist a design pattern that has been tested and proven to work well, so I call out to the community: do you know of such a pattern? If so, I kindly ask you to enlighten me.

Update

The solution is now implemented, using bits and pieces from various answers to this question. I published a blog post about it.

Answer 1

I don't know of any pattern, but I think you can simplify your approach:

If your resource pool does know which group has a resource, you don't need an extra emergency stack.

1. Provide all resources from the same stack.
2. If the number of available resources is less than the number of guaranteed resources plus the number of used guaranteed resources, don't return a resource if the requesting group already has a resource.

Other than that I think your approach is sound and concise, I don't believe there's a better way. (But I might be wrong, of course)

Answer 2

I'd probably have a single resource stack, an array/map keyed by group of counts, and a count of groups that have no resources.

To allocate...

if group-counts [group] == 0
  pop resource from stack
  increment group-counts [group]
  decrement reserved-count

elseif reserved-count < stack.size
  pop resource from stack
  increment group-counts [group]

else
  fail

The key point is that the stack is never allowed to get smaller than the number of groups that still have the right to demand an immediate resource.

One advantage to this approach is that you can make it a little more flexible if needed. Suppose one group has a special requirement, so it may need two resources at any point.

if group-counts [group] < group-reserved [group]
  pop resource from stack
  increment group-counts [group]
  decrement reserved-count

elseif reserved-count < stack.size
  pop resource from stack
  increment group-counts [group]

else
  fail

The reserved-count in this case starts as the sum of all group-reserved[] values.

The release logic for this case is...

push resource to stack
decrement group-counts [group]
if group-counts [group] < group-reserved [group]
  increment reserved-count

For the simple case, use "if group-counts [group] == 0".

Answer 3

You could also swap the logic around (it might result in cleaner code):

Assign each group a resource from the start. Keep the rest of the resources in a list of "free" resources. Any consumer that asks for a resource does so through a group resource allocator that either just gives out the default group resource or queries for a free resource. On returning the resources, first fill group resource hole, then start filling free resource list.

So you end up with a pool of free resources. One resource allocator per group with access to the free resource pool and a default resource. Consumers interact with the group allocator.

Answer 4

This does seem like a very odd version of a pool.

For example, if you have seven groups and seven resources in the default pool, seven in 'emergency' pool. If each group requests one resource the default pool is exhausted, and then if any one group requests two more resources starvation occurs, with only eight of the fourteen resources in use. Even if you change it to use the group-specific resource first, you still find situations of starvation with only 8/14 utilisation.

Why exactly does it matter that the second request for a resource should be the one to fail instead of the first ( another way of looking at the "there is a minimum of one resource for each group" requirement )?

Answer 5

That's interesting. At a high level the issue is you have 2 types of resource requests:a high priority request which is not allowed to fail, and a standard request which can fail.

One possible way to handle this is if your consumers can be suspended. If that is possible you can implement a two way communication between the consumer and manager.

A consumer can request a resource or release a resource

The manager can revoke a resource

When the manager receives a normal request it will deny it if it has no free resources. If it received a priority request it will force a revoke on some consumer (decided by some apropriate policy). This is similar to how a distributed lock system might work. This prevents starvation, but dramatically increases complexity and may not even be possible if a consumer simply must run to completion upon starting.

Failing this, I think Daren's answer is probably the most ideal, however, you still risk waste if you have no active consumers in a group and many active consumers in another group. That could be mitigated by good partitioning of the groups, though.