Windows 临界区公平性 [英] Windows critical sections fairness

问题描述

我有一个关于使用 EnterCriticalSection 和 LeaveCriticalSection 方法的 Windows 临界区公平性的问题.MSDN 文档规定:无法保证线程获得临界区所有权的顺序，但是，系统对所有线程都是公平的."问题出在我写的一个应用程序中，它阻塞了一些从不进入临界区的线程，即使经过很长时间；所以我用一个简单的 c 程序进行了一些测试，以验证这种行为，但是当你有很多线程并且里面有一些等待时间时，我注意到奇怪的结果.这是测试程序的代码:

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);
  }
}

这样做的结果是一些线程被阻塞了很多个周期，而另一些则经常进入临界区.我还注意到如果你改变更快的睡眠(10 毫秒)，一切可能会恢复公平，但我没有发现睡眠时间和公平之间有任何联系.但是，这个测试示例比我的真实应用程序代码要好得多，后者要复杂得多，并且实际上显示了某些线程的饥饿.为了确保饥饿的线程还活着并正常工作，我做了一个测试(在我的应用程序中)，我在临界区进入 5 次后杀死线程:结果是，最后，每个线程都进入，所以我确保所有这些都活着并在互斥锁上被阻止.我是否必须假设 Windows 对线程真的不公平?你知道这个问题的解决方案吗?

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?

Linux 中使用 pthreads 的相同代码，按预期工作(没有线程饥饿).

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

我找到了一个有效的解决方案，强制公平，使用 CONDITION_VARIABLE.可以从这篇文章(链接)推断出来，所需的修改.

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

推荐答案

我认为您应该回顾以下几点:

I think you should review a few things:

• 在 10000 个案例中的 9997 个中，您分支到 Sleep(500).几乎每次成功尝试获取临界区时，每个线程都会保持临界区长达 500 毫秒.

• 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.

线程在释放临界区后执行另一个Sleep(500).结果，单个线程通过保持临界区占用了几乎 50% (49.985%) 的可用时间 - 无论如何！

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!

假设您这样做是为了显示行为:启动其中 20 个线程可能会导致最后一个线程在处理器完全耗尽时访问单个逻辑处理器上的临界区的最短等待时间为 10 秒可用于此测试.

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.

如果你做测试需要多长时间/什么 CPU?什么Windows版本?您应该能够写下更多事实:活跃线程与线程 ID 的直方图可以说明很多关于公平性的信息.

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.

关键部分应在短时间内获得.在大多数情况下，可以更快地处理共享资源.临界区中的 Sleep 几乎肯定会指向设计缺陷.

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 临界区公平性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！