dimanche 25 octobre 2015

Avoiding starvation with a C++ notify_all()

My barrier synchronisation scenario is this:

a. Threads take a step forward in synchronisation - i.e. they complete one unit of task and then wait for all the other threads to do the same, then when they do, they can move forward again.

b. I have a large number of threads (around 256) waiting on a condition variable. When the condition is met a notify_all() will be sent.

c. (Part where starvation risk arises): Immediately before the notify_all() is called, a runnable variable is set to true and a counter - completed - is set to zero. When a thread completes its task unit, it calls a function which first sets runnable to false, then increments the completed variable - the condition is met when completed equals the threshold (namely the number of threads that need to complete a task unit), where upon runnable is set to true.

I.e., we wait like this:

cond.wait(lck, runnable == true);

And have this:

unique_lock<mutex> lck(runMut);
runnable = true;
cond.notify_all();

My concern is that any woken thread could complete its task and then call into the wait() function before a thread further down the chain has been woken. When this "lower" thread tests runnable, it will find it set to false and so go back to sleep.

Is there a design pattern or some other way I can get round this?

Aucun commentaire:

Enregistrer un commentaire