Critical Section OwnerShip

If a critical section lock is currently owned by a thread and other threads are trying to own this very lock, then all the threads other than the thread which owns the lock enter into a wait queue for the lock to be released.

When the initial owning thread releases the critical se开发者_Go百科ction lock then one of the threads in the waiting queue will be selected to run and given the critical section lock allowing the thread to run.

How is the next thread to run selected as it is not guaranteed that the thread that first came will be the owner of the thread.

If threads are not served in FIFO fashion then how is the next owner Thread selected from the wait queue?

The next thread to get the critical section is chosen non-deterministically. The only thing that you should be concerned about is whether the critical section is implemented fairly, i.e., that no thread waits infinitely long to get its turn. If you need to run threads in specific order, you have to implement this yourself.

The next thread is chosen in quasi FIFO order. However many system level variables may cause this to appear non deterministic:

From Concurrent Programming On Windows by Joe Duffy: (Chapter 5)

... When a fixed number of threads needs to be awakened, the OS uses a semi-fair algorithm to choose between them: as threads wait they are placed in a FIFO queue that the awakening logic consults when determining which thread to wake up. Threads that have been waiting for the longest time are thus preferred over threads that been waiting less time. Although the OS does use a strict FIFO data structure to manage wait lists; ... this ordering is regularly perturbed by other system code and is not reliable.

Posix threads do the FIFO queue.

What about Thread Scheduling Algorithm , the threads in waiting state get priority as per Thread Scheduling algorithm Plz correct if I am wrong.