クリティカルセクションと相互排除

複数の実行主体が共有する状態を読み書きするコード領域をクリティカルセクションという。任意の時刻に高々 1 つの実行主体しかクリティカルセクションを実行していないことを保証する性質を相互排除（mutual exclusion）という。相互排除に加えて、(i) クリティカルセクションに入りたい主体が存在し、中に誰もいなければ有限時間内に誰かが入れる（進行性）、(ii) 入りたい主体が無限に待たされない（有限待ち）、が満たされるとき、その排他機構は正しいという。