Windows critical sections fairness

Question

I've a question about the fairness of the critical sections on Windows, using EnterCriticalSection and LeaveCriticalSection methods. The MSDN documentation specifies: "There is no guarantee about the order in which threads will obtain ownership of the critical section, however, the system will be fair to all threads." The problem comes with an application I wrote, which blocks some threads that never enter critical section, even after a long time; so I perfomed some tests with a simple c program, to verify this behaviour, but I noticed strange results when you have many threads an some wait times inside. This is the code of the test program:

CRITICAL_SECTION CriticalSection;

DWORD WINAPI ThreadFunc(void* data) {
  int me;
  int i,c = 0;;
  me = *(int *) data;
  printf(" %d started\n",me);
  for (i=0; i < 10000; i++) {
     EnterCriticalSection(&CriticalSection);
     printf(" %d Trying to connect (%d)\n",me,c);
     if(i!=3 && i!=4 && i!=5)
         Sleep(500);
     else
         Sleep(10);
    LeaveCriticalSection(&CriticalSection);
     c++;
     Sleep(500);
  }
  return 0;
}

int main() {
  int i;
  int a[20];
  HANDLE thread[20];

  InitializeCriticalSection(&CriticalSection);
  for (i=0; i<20; i++) {
        a[i] = i;
        thread[i] = CreateThread(NULL, 0, ThreadFunc, (LPVOID) &a[i], 0, NULL);
  }
}

The results of this is that some threads are blocked for many many cycles, and some others enter critical section very often. I also noticed if you change the faster Sleep (the 10 ms one), everything might returns to be fair, but I didn't find any link between sleep times and fairness. However, this test example works much better than my real application code, which is much more complicated, and shows actually starvation for some threads. To be sure that starved threads are alive and working, I made a test (in my application) in which I kill threads after entering 5 times in critical section: the result is that, at the end, every thread enters, so I'm sure all of them are alive and blocked on the mutex. Do I have to assume that Windows is really NOT fair with threads? Do you know any solution for this problem?

EDIT: The same code in linux with pthreads, works as expected (no thread starves).

EDIT2: I found a working solution, forcing fairness, using a CONDITION_VARIABLE. It can be inferred from this post (link), with the required modifications.

The MSDN article says nothing about fairness. Appropriately, there is none since Vista and Server 2003 SP1. Fairness causes lock convoys, backgrounder [is here](http://joeduffyblog.com/2006/12/14/anticonvoy-locks-in-windows-server-2003-sp1-and-windows-vista/). — Hans Passant, May 07 '14 at 12:08
Semaphores, Critical Sections, and Mutexes are not always the best choice for synchronization. For highly contested resources you have to be very very careful about what you use, sometimes letting a single thread manage that resource is desirable because you need not block any other thread on that resource. A classic example would be a UI. — Mgetz, May 07 '14 at 12:31
@HansPassant: I read the article, thanks, so I have to assume to not use the CriticalSection data structure, because it is not fair. I quoted this link: [link](http://msdn.microsoft.com/en-us/library/windows/desktop/ms683472%28v=vs.85%29.aspx), and it does say what I wrote. — Mat, May 07 '14 at 12:47

score 0 · Answer 1 · answered May 07 '14 at 11:33

You're going to encounter starvation issues here anyway since the critical section is held for so long.
I think MSDN is probably suggesting that the scheduler is fair about waking up threads but since there is no lock acquisition order then it may not actually be 'fair' in the way that you expect. Have you tried using a mutex instead of a critical section? Also, have you tried adjusting the spin count?

If you can avoid locking the critical section for extended periods of time then that is probably a better way to deal with this.

For example, you could restructure your code to have a single thread that deals with your long running operation and the other threads queue requests to that thread, blocking on a completion event. You only need to lock the critical section for short periods of time when managing the queue. Of course if these operations must also be mutually exclusive to other operations then you would need to be careful with that. If all of this stuff can't operate concurrently then you may as well serialize that via the queue too.

Alternatively, perhaps take a look at using boost asio. You could use a threadpool and strands to prevent multiple async handlers from running concurrently where synchronization would otherwise be an issue.

I didnt' try a mutex yet, because I assumed it handles fairness as than as the critical section does (but maybe I'm wrong). I know I can use some workarounds by restructuring my code, I just wanted to understand if it would be possible to avoid it. I'll give a try with mutexes (the spin count is not involved in this, and however did not help, as expected). — Mat, May 07 '14 at 12:09

Arno · Answer 2 · 2014-05-07T12:29:05.033

I think you should review a few things:

in 9997 of 10000 cases you branch to Sleep(500). Each thread holds the citical section for as much as 500 ms on almost every successful attempt to acquire the critical section.
The threads do another Sleep(500) after releasing the critical section. As a result a single thread occupies almost 50 % (49.985 %) of the availble time by holding the critical section - no matter what!
Behind the scenes: Joe Duffy: The wait lists for mutually exclusive locks are kept in FIFO order, and the OS always wakes the thread at the front of such wait queues.

Assuming you did that on purpose to show the behavior: Starting 20 of those threads may result in a minimum wait time of 10 seconds for the last thread to get access to the critical section on a single logical processor when the processor is completely available for this test.

For how long dif you do the test / What CPU? And what Windows version? You should be able to write down some more facts: A histogram of thread active vs. thread id could tell a lot about fairness.

Critical sections shall be acquired for short periods of time. In most cases shared resources can be dealt with much quicker. A Sleep inside a critical section almost certainly points to a design flaw.

Hint: Reduce the time spent inside the critical section or investigate Semaphore Objects.

Windows critical sections fairness

2 Answers2

Linked