Thread synchronizing: shared resources and actions with different resource number demand

I have the following task:

There is a pool of equivalent resources (e.g. input slots) and a set of actions to be performed with this pool.

Each action is executed in a separate thread.

Each action requires different number of input slots available.

I want to use something like semaphores for the following task:

All action threads are executed simultaneously

The action is performed when the required number of input slots are free to use

Slots are set free when the action is finished

I can't use regular semaphore because it's impossible to set semaphore negative initial value or decrement the value until it becomes negative

So I need "semaphore" with the function WaitMultiple(int N), which does smth like "wait until resource value reaches N"

Any suggestions how I can solve it? I prefer thread block/release, I can not afford active loops

Answers


I'm not sure that semaphores are useful here.

I think you can do this with a thread pool and some code in a CS/mutex protected section. Put the actions in a collection, (list/queue/stack, whatever is best for your dispatching algorithm), and initialize a slot-count. Then, and whenever slots are freed by completing actions, enter the CS and decide which action/s to execute given the current slot-count. Submit these actions to a thread pool, decrement the slot-count appropriately and exit the CS.

'Slot-count' could be a simple integer or a collection count of some complex class - doesn't really matter.

Whenever the free slot count increases, you have to make a decision about which action to dispatch onto the threadpool. You will need some sort of algorithm since it seems possible that a slot-release may make it possible to run more than one action - do you maybe run the action with the highest slot-requirement first?

I don't see any need for a separate dispatcher thread and certainly not any CPU loops! I fear that any solution based on thread/s trying to accumulate a slot target by waiting on some synchro object for available slots would be a deadlock risk - many threads could be stuck with partial slot counts and so prevent forward progress. Also, you would be unable to tweak the algorithm to, say, prevent actions with a high slot-requirement being starved.


You can implement your own fast semaphore with the possibility of a negative count. For example, have a class MySemaphore like this:

public class MySemaphore
{
    private int size; // number of occupied resources
    private readonly int capacity; // total capacity

    public MySemaphore(int size, int capacity)
    {
        this.size = size;
        this.capacity = capacity;
    }

    public void Lock(int count) // acquire "count" resources
    {
        lock(this)
        {
            while(capacity - size < count)
            {
                Monitor.Wait(this);
            }
            size += count;
        }
    }        

    public void Unlock(int count) // release "count" resources
    {
        lock(this)
        {
            size -= count;
            Monitor.PulseAll(this);
        }
    }
}

Need Your Help

Add NSMutableArray in TableView Which contains set of Views

iphone ios uitableview uiview nsmutablearray

Here is what I am trying to do, I have set View with one Image and 3 Label, each are identical.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.