4章並行プログラミング特有のバグと問題点

　本章では並行プログラミング時に発生する特有のバグや問題点について解説する。まずはじめに、デッドロック、ライブロック、飢餓といった、同期処理における基本的な問題を解説し、その後、再帰ロック、擬似覚醒といったより発展的な同期処理に関する問題について説明する。並行プログラミングではシグナルの扱いも問題となり、それについての説明も行う。実用的なシステムソフトウェアを実装する上では、シグナルの理解も重要である。最後に、CPUのアウトオブオーダ実行の説明と並行プログラミング時の問題点および、メモリバリアによる解決方法について説明する。

4.1　デッドロック

　並行プログラミング特有のバグを示す例として、食事する哲学者問題（dining philosophers problem）が知られている。食事する哲学者問題では、円卓の周りに哲学者が座っており、哲学者の前には食事が、哲学者の間には箸が1本ずつ置かれていると想定する。このとき、哲学者は両端の箸を取り上げ、箸を2本取り上げた際に食事を行うが（箸は2本ないと食事できないという制約があるとする）、哲学者のアルゴリズムによってはお互いにリソース（箸）の空きを待ち合うことになり、処理が進まなくなってしまう。

　次の図は、食事する哲学者問題を図で表したものとなる。ここでは、4人の哲学者がテーブルを囲んでおり、哲学者は両端の箸を取って食事し、しばらく食事した後箸を置くという動作を繰り返す。

図4-1　食事する哲学者問題