2011年5月8日

相互排除問題,際どい部分,そして並行プログラミング

複数の実行中のプログラム(プロセス)が関わる処理では,必ず排他制御が問題になる. 複数のプロセスがあらかじめ許容された同時アクセス数を越えて共有資源を使おうとすれば, どのプロセスにアクセスを許し,どれに許さないかを,決めなくてはならない. これを mutual exclusion problem 日本語では相互排除問題という.

この相互排除問題について,最近岩波書店より 「相互排除問題」(以下「本書」とする) というそのものズバリの本が先月2011年4月に出版された. 著者は土居範久先生.日本におけるこの分野の第一人者である.

本書の参考文献リストを見ると,ほとんどの文献が 1990年以前に書かれている.しかし,内容はいささかも古いものではなく, 現在のマルチコア環境,あるいは分散ネットワーク環境において課題となっている 同期と相互排除に関する問題のほとんどを網羅している. 言い換えれば,現時点の課題の大多数は,20年前に解かれていると 言い切れるかもしれない. (もちろん,アルゴリズムの効率化や,実行環境の速度等に合わせた最適化は 現在も引き続き行われているが.)

本書では,アルゴリズムの説明にPascalに似た疑似コードを使っている. しかし,本書の本文中では逐次処理にとどまらず,HoareのCSPや分散プロセス, メッセージ通信など現在の並行処理や分散処理の基本となる概念が くまなく網羅されており,疑似コードも書籍を読み進めるに従って, 内容が拡張されていく仕組みになっている.そういう意味では,読んでいて楽しい. もっとも,例示されているそれぞれの疑似コードを咀嚼して理解するには, かなりのプログラミングの経験が必要だが.

本書のページ数は256と少ないものの,気軽に片手間で読める本ではない. 本書のテーマである「際どい部分」(critical section)や 「際どい資源」(critical resource)の扱いは, 一歩間違えれば,大変な事故を引き起こしかねないものだからだ. 別の言い方をすれば,この本を一通り理解できるようになったら, ソフトウェアエンジニアとしては一人前と言えるかもしれない. 日本語で並行処理を理解する上で,本書は必読といえるだろう.