排他制御
これまでに説明した方式を使い、次のような同期プリミティブが構築できる。
ロック スピンロック
ミューテックス - 単純な相互排除
セマフォ - k-相互排除
モニタ
メッセージパッシング
排他制御の多くの形式には副作用がある。例えば、古典的セマフォはデッドロックを引き起こしうる。あるプロセスがあるセマフォを獲得し、別のプロセスが別のセマフォを獲得した状態で、互いに相手の獲得したセマフォが解放されるのを待ち続けることが考えられる。よくある副作用としてリソーススタベーションがあり、その場合プロセスは処理を完遂するのに十分な資源を決して得られない。また、優先順位の逆転は低優先度のスレッドのせいで高優先度のスレッドが待たされる現象であり、レイテンシが長くなり、割り込みへの反応が悪くなる。
排他制御に関する研究の多くはそういった副作用を排除することを目的としており、例えばLock-freeとWait-freeアルゴリズムはブロッキングされずに処理が進行することを保証する。完璧な方法はまだ見つかっていない。