Communicating Sequential Processes (1978)
September 30, 2023Communicating Sequential Processes (CSP)は、あるプロセスの出力を別のプロセスの入力に渡し、入出力のあるプロセスを並行実行するプログラミングモデルである。 たとえば、GoのgoroutinesはCSPにもとづく軽量スレッドである。
HoareがCSPを提唱した78年にも、マルチプロセッサ間の排他制御や同期に、プロセッサ間で共有する変数を確認、更新する方法がとられていた。 変数を共有する方法は、セマフォやモニタ、 conditional critial regionをはじめとしていくつかあり、いつどれを選べばよいか共通の見解はなかった。 また、プロセッサ間で記憶領域を共有することで、クロスバースイッチのような並行処理のハードウェアが必要になり、オーバーヘッドや不具合の原因が生じる。
CSPは、排他制御や同期のアルゴリズムの採択基準やハードウェアの問題を解決する目的で提唱された。 プロセスは変数を共有せず、プロセスの入出力でデータを受け渡す。 データは、プロセスに入力される前にDijkstraのGuardコマンドに渡され、成功したときにのみ、プロセスが実行される。 プロセスは、入力されるまで遅延する。
雑記
論文でHoare自身が指摘した課題に、CSPで実装したプログラムの正しさを検証する形式的な証明がないことと、実行速度の速いCSPの実装を提案していないことがある。 後者の解決策としてCSP向けのハードウェアが提案されているが、CSPがハードウェアの不具合やオーバーヘッドを解決する方法として提案されているので、ハードウェアによる解決策も不具合やオーバーヘッドとして考慮しなければならない。