Windows APIのクリティカルセクションはFIFO動作しない

Windows API提供の排他制御プリミティブCRITICAL_SECTIONでは、ロック競合スレッド間のケジューリングにおいてFIFO順序が保証されない。*1

下記コードで「処理(1)が2スレッド上で交互に実行される」ことを期待した場合、Windows XP以前では予想通りの実行結果 “A:1→B:1→A:1→...” をおよそ期待できるが*2、Windows Vista以降では期待通りに実行されない*3。古い動作仕様ではCRITICAL_SECTIONオブジェクトに対して「ロック獲得要求を行ったスレッドがFIFOキューに保持」されており、このFIFOキューに従って次にロック獲得するスレッドが決定する。新しい動作仕様ではこのFIFO順序保証を行わないことで実行効率を向上させている。

#include <windows.h>

CRITICAL_SECTION csObj;
InitializeCriticalSection(&csObj);

// 2スレッドA,Bで並列実行
void thread_func()
{
  for (;;) {
    EnterCriticalSection(&csObj);
    // 処理(1) : 直列実行領域
    LeaveCriticalSection(&csObj);
    // 処理(2) : 並列実行領域
  }
}

処理実行時間やメモリ空間効率といった理由により、排他制御プリミティブでは不公平(unfair)スケジューリングが一般的であり、このようなプリミティブの単純使用では前述仕様を正しく実装できない。公平(fair)スケジューリングが保証された排他制御プリミティブを用いるか、セマフォや条件変数を用いた同期制御機構を別途実装する必要がある。
注意：そもそも、このような排他制御プリミティブのみによる同期機構では、“任意の” スレッドスケジューリング下で “必ず” 交互に実行されることを保証できない。

MSDNより該当箇所を引用（下線部は強調）。

Starting with Windows Server 2003 with Service Pack 1 (SP1), threads waiting on a critical section do not acquire the critical section on a first-come, first-serve basis. This change increases performance significantly for most code. However, some applications depend on first-in, first-out (FIFO) ordering and may perform poorly or not at all on current versions of Windows (for example, applications that have been using critical sections as a rate-limiter). To ensure that your code continues to work correctly, you may need to add an additional level of synchronization.
Windows Server 2003 and Windows XP: Threads that are waiting on a critical section are added to a wait queue; they are woken and generally acquire the critical section in the order in which they were added to the queue. However, if threads are added to this queue at a fast enough rate, performance can be degraded because of the time it takes to awaken each waiting thread.

http://msdn.microsoft.com/en-us/library/windows/desktop/ms682530.aspx

*1:この動作はWindows Server 2003／Windows XP以前とは異なる。Windows Server 2003 SP1で仕様変更が行われ、Windows Server 2008以降／Windows Vista以降でもFIFO順序保証は無い。本記事では説明のためWindows Server OSは除外する。

*2:厳密にはWindows XPであっても「大抵の状況で」期待通り動作するに過ぎない。仮に処理時間が(1):(2)＝100:1であったとしても、OSスレッドスケジューラ動作によっては期待通りの動作を保証するものではない。期待通り動作しない例：A:ロック獲得成功→B:ロック獲得要求→A:1→A:ロック解放→A:2→A:ロック獲得成功（2回目）。

*3:新しい動作仕様では「FIFO順序が保証されない」ため、Windows Vistaでも期待通り動作するケースもありえる。