セマフォ

　セマフォはもっとも基本的な同期プリミティブであり、ダイクストラにより提唱された。
　セマフォの原義は「腕木信号機」である。プロセスやスレッドを列車に見立て、路線に入ることのできる列車が一つしかないことを腕木信号機が保証することに由来している。しかし、ここではセマフォの実体により近い「オハジキ」のアナロジーにより説明する。
　４人のコックが共同でカツカレーセットを作っている。４人の分担は、トンカツ、カレーソース、味噌汁、野菜サラダであり、二口のガスコンロを共用している。
　ガスコンロが二口しかないために、ガスコンロの前に小皿があり、その上にオハジキが二つ置いてある。ガスコンロを使いたいコックは小皿のオハジキを取ろうとする。無事にオハジキが取れたら、コンロを使うことができる約束だ。コンロを使いおわったら、オハジキを小皿に返す。一方、オハジキを取れなかったコックは、皿の前に張り付いて休眠状態に入る[*1]。休眠は、別のコックがオハジキを返してくれるまで続き、オハジキが取れるとコックは再び動き出す。

　上記の「オハジキを入れた小皿」がセマフォである。一般的に、オハジキを取る操作をＰ命令といい、オハジキを返す操作をＶ命令という。

　セマフォは、「同期プリミティブ」の要件を満たしている。オハジキを取ることのできたプログラムだけが先に進めることから、セマフォには「早押しスイッチ」の機能があることが分る。また、オハジキを取れなかったプログラムが休眠状態に入ることから、「実行条件の整わないプログラムを休眠させる」機能がある。
　セマフォ（及びそれを発明したダイクストラ）のすごいところは、上のようなシンプルな機構で同期プリミティブを実現して見せたところにある。しかし、これはセマフォの欠点でもある。早押しと休眠を一つの命令で実現したために、セマフォによるプログラミングはやや難しく、問題によってはパズルを解くような感じになってしまう。セマフォをうまく使うコツは、「早押し」と「休眠」の機能を二つのセマフォに分けることである。

　上記セマフォの欠点は、本質的には、Ｐ命令を実行しないとセマフォの状態が分からないことに由来している。オハジキのたとえで説明すると、オハジキを取ってみないとオハジキが余っていることが分らず、もしオハジキがなければ有無をも言わさず休眠状態になってしまう。これは不便だ。オハジキを取る前にオハジキの有無（実行権の有無）を確かめたい。しかし、たとえオハジキの個数を確かめられたとしても、ウカウカしていると他のコックがオハジキを取ってしまい、オハジキの個数が変わってしまうかもしれない。だからこそ、セマフォは取ろうとすると同時に個数を調べているのだ。
　セマフォと同じくらい有名な同期プリミティブにモニタがある。こちらはセマフォより複雑であるが、上記の欠点は解決されている。詳しくはモニタの項を参照のこと。

[*1]	このへんがわざとらしくて、少し苦しい。