セマフォ
ミューテックスは基本的にバイナリセマフォと等価であり、時には基本実装が同一ということもある。ただし、ミューテックスは2つの実行単位が同時に共用資源にアクセスするのを防止する構成物を表し、バイナリセマフォは単一の資源へのアクセスを制限する構成物を表す。
多くの場合、ミューテックスには「所有者」の概念がある。すなわちミューテックスをロックした実行単位だけがそれをアンロックすることができる。対照的にセマフォにはそのような制限がなく、上述の生産者/消費者問題の例でもそれを利用している。
したがって基本的には、ミューテックスは実行単位などの実行実体と結びついており、セマフォは資源と結びついている。
カウンティングセマフォの概念は、一度に複数個の資源を獲得・解放できるように拡張でき、UNIXでの実装もそのようになっている。その場合のVおよびP操作は次のように修正される。
リソーススタベーションを防ぐため、セマフォには実行単位のキュー(通常はFIFO)が1つ付属している。セマフォ値がゼロのときにP操作をすると、その実行単位はセマフォ付属のキューに追加される。別の実行単位がV操作でセマフォ値をインクリメントしたとき、キュー上に実行単位があれば、そのうちの1つをキューから外して実行再開させる。実行単位に優先度が設定されている場合、キュー上で優先度順に実行単位を並べるなどして、最も優先度の高い実行単位が最初に実行再開できるようにする。
実装においてインクリメント/デクリメントや比較の不可分性が保証されていない場合、インクリメントやデクリメントが行われなかったり、セマフォ値が不正になる危険性が生じる。不可分性を達成するには、リード・モディファイ・ライト(英語版)(読み取って、変更を加えて、書き込むという処理サイクル)を不可分に実行できる機械語命令を使用する。そのような機械語命令がない場合、デッカーのアルゴリズムなどのソフトウェアによる排他制御を使用する。シングルプロセッサのシステムでの不可分操作は、プリエンプションを一時的に禁止したり、割り込みをマスクしたりすることでも実現できる。マルチプロセッサシステムではそれだけでは不十分で、同じセマフォを共有する2つのプログラムが別々のプロセッサ上で同時に動作している場合に対処できない。そのためテスト・アンド・セット命令などを使用してセマフォ変数へのアクセスをロックする必要がある。
ある図書室に学習室が10部屋あり、それぞれの学習室は一度に1人の学生が使用するとする。争奪戦が始まらないよう、学生は受付カウンターで学習室の使用を申し込むことになっている。学習室を使用し終えたら、学生は受付所に立ち寄ってその学習室が空いたことを知らせなければならない。全ての学習室が埋まっている場合、学生は受付所で学習室が空くのを待つ。
受付カウンターの図書係はどの学習室が空いているかは把握しておらず、単に空いている部屋数のみを知っている。学生が申し込んできたとき、図書係は空き部屋数から1を引く。学生が学習室の利用を終えたとき、図書係は空き部屋数に1を加える。学習室の使用許可が与えられたとき、その部屋は必要なだけ使い続けることができる。学習室は事前に予約することはできない。
このシナリオでは、受付カウンターがセマフォ、学習室が資源、学生が実行単位に相当する。また、セマフォの初期値は10になっている。学生が学習室の使用を申し込んで許可されたとき、セマフォ値から1が引かれて9になる。次の学生のときには8、さらに次は7となる。1を引くとセマフォ値が負になるという状態で学生が申し込んだ場合、その学生は待たされる。複数人の学生が待っているとき、彼らは待ち行列を形成するか、いずれかの学生が学習室の使用を終えて受付カウンターにやってきたときに空いた部屋を割り当てる。割り当て方式には、ラウンドロビン・スケジューリング方式等がある(セマフォが正しく制御されるよう実装されていれば、割り当て方式は妥当なものであればよい)。