自作コンパイラの部屋 > 用語集 > 同期プリミティブ

同期プリミティブ

 同期プリミティブは並行プログラミングにおける基本ツールであり、次の二つの働きがある。

  1. 共有資源の取り合いを管理して、順番に使用できるようにする
  2. 実行条件が整わないプログラムを一時的に眠らせ、条件が整い次第、実行再開させる

 1.はクリティカルセクションをうまく処理する上で重要である。これはクイズの「早押しボタン」のアナロジーで説明することができる。
 テレビのクイズ番組では、何人かの解答者の中で最も早くボタンを押した人が一人だけ解答権を得るというタイプが多い。ボタンを押すまで、言い換えれば、問題の説明を聞いて答えを考えるところまでは並行動作だが、解答するところは一人ずつ、すなわち逐次動作となる。
 上記から分かるように、「早押しボタン」は同期プリミティブとしてとらえ得る。並行処理の用語で説明すると「セマフォ」と実質的に同じものである。また、クリティカルセクションは解答権を奪い合う部分である。

 次に2.について説明するには、デートのアナロジーを用いることにしよう。
 太郎君と花子さんがデートの待ち合わせをすることになった。待ち合わせ場所に太郎君が来てみると、花子さんはまだ来ていない。そこで太郎君は待ち合わせ場所で待つことにした。待ち方としては以下の四つの方法がある。

a) まだか、まだかとひたすら待つ。
b) 目覚し時計をセットして一定時間眠る。起きてもまだ花子さんがきていなかったら、同じことを繰り返す。
c) 起きる時間は決めないでとにかく眠る。花子さんが来たら、花子さんに起こしてもらう。
d) 太郎君の待てる限界の時間を目覚し時計にセットして眠る。花子さんが来たら起こしてもらう。目覚しで起きてもまだ花子さんが来ていない場合は(怒って)帰る。

 a)はポーリングという方法であり、プログラム的にいうと、ひたすら花子さんの到着チェックをしながら、花子さんが来るまでループするという方法だ。この方法の欠点は明らかに効率が悪いことである。なにもすることがなくてもループし続けるので、CPUパワーを無駄使いすることになる。

 b)はポーリングの変形だが、一定時間眠りながら待つことにより、CPUの無駄使いを避けたものである。一般に、並行処理に対応したOS(マルチタスクOS)には、一定時間プログラムを眠らせ、CPU能力を他のプログラムに振り向ける機能がある。この機能を利用するわけだ。

 この案はa)よりはましだが、眠る時間を決めるのが難しい。あまり頻繁に起きると、結果としてa)案と同じことになり、CPUの無駄使いとなる。あまり長く眠り過ぎると、花子さんが到着してから太郎君が起きるまでのタイムラグが問題となる。頻繁にデートをする場合には特にそうで、全体として処理時間が低下することになる。

 従って、相手に起こしてもらうのが好ましいことになる。これだとCPUの無駄使いもないし、タイムラグも生じない。同期プリミティブの「待ち合わせ」あるいは「同期」と呼ばれる機能がこれに該当する。言うまでもなく、「同期プリミティブ」の語源ともなっている。

 c)は同期プリミティブの基本型であり、d)はタイムアウトを考慮したものである。花子さんの気が変わって来なかった場合とか、途中で事故にあった(プログラムの異常やバグなど)場合、c)だと太郎君が眠りっぱなし(デッドロック)になってしまう。d)はこのケースに対処したものである。

 同期プリミティブの代表例としては、前述のセマフォの他、モニタ、ランデブー、メッセージなどがある。ランデブーはAda(エイダ)言語[*1]で採用されたものである。また、セマフォとモニタは特に基本的な同期プリミティブなので、別稿にして説明する。


[*1]
Adaは米国国防省が定めた統一言語の名称である。軍事目的用、たとえばミサイルの姿勢制御などができるように、リアルタイム処理、マルチタスクの機能が言語レベルでサポートされており、またミッションクリティカルな処理を記述するための例外処理、強固な型システムなどを特徴とする。Adaのオーナーは米国だが、仕様を作ったのはフランスのチームである。ランデブーなんて名称のセンスはいかにもフランス人らしい。

目次