******************** 並行プログラミング ******************** ============ 並行と並列 ============ 逐次(:index:`sequential`) 時間的に決められた順にしたがって実行すること。 並行(:index:`concurrent`) 複数の実行単位相互の実行順序が決められていないこと。論理的並行とも言う。 並列(:index:`parallel`) 複数のハードウェアによる実行が、時間的に重なりあって行われること。物理的並行とも言う。 並行は、必ずしも並列を意味しない。1個のCPUで並行実行するとは、複数の実行単位を切り替えながら実行するということ。 Preemptive いつでも切り替わる可能性があるということ。実際にはタイマー割り込みや入出力イベントなどで切り替わる。 Non-preemptive 勝手には切り替わらない。切り替え用の命令を実行すると切り替わる。コルーチン(:numref:`coroutine`)など。 ====== 同期 ====== スレッド(:index:`thread`) プログラム中の実行の軌跡、あるいは、実行を制御する単位（CPUのレジスタやスタックの内容を含む）。一つのスレッドはプログラムを逐次的に実行していく。同じプログラムを複数のスレッドが並行に実行することがある。 同期(:index:`synchronization`) プログラム中のある特定の点で、並行に実行されているスレッドの実行順序に制約を課すこと。 協調的同期(:index:`cooperation synchronization `) 単に同期とも言う。他のスレッドの実行完了を待つ場合や、データの受け渡しを行なう場合。 競争的同期(:index:`competetion synchronization `) 排他制御(:index:`mutual exclusion`)とも言う。同時に一つのスレッドしかアクセスできない資源について、複数のスレッドが同時にアクセスしないように制御を行なう場合。 きわどい領域(:index:`critical section`) プログラム上で排他制御が必要な部分。危険領域とか臨界領域という場合もある。 .. admonition:: 競合の例 共有変数へのアクセスで排他制御を行なわないと何が起こるか？ 変数 x の最初の値は 1 で、 x の値を 1 増やすプログラムがある。スレッド A と B がこのプログラムを並行に実行すると、次のような順序で実行される可能性がある。 1. A が x の値 1 を読み出す。 2. B が x の値 1 を読み出す。 3. A が 1 増やした値 2 を x に書き込む。 4. B が 1 増やした値 2 を x に書き込む。 共有資源に対して、他のスレッドがアクセスできないようにすることを、普通は「ロックをかける」と言う。すでにロックをかけられた資源にアクセスするためには、ロックが外れるまで待たなければならない。 デッドロック(:index:`deadlock`) すべてのスレッドが待ち状態となり、先に進めない。 餓死(:index:`starvation`) あるスレッドが共有資源にアクセスできない状態が永久に続く。 .. admonition:: 食事する哲学者 デッドロックが起きる可能性がある :: loop 左のフォークを取り上げる; 右のフォークを取り上げる; 食べる; 両方のフォークを戻す; 思考に沈む; end .. admonition:: 食事する哲学者改良版 餓死が起きる可能性がある :: loop 左のフォークを取り上げる; if 右のフォークが使われている then 左のフォークを戻す; else 右のフォークを取り上げる; 食べる; 両方のフォークを戻す; 思考に沈む; end end .. admonition:: 課題18 :class: exercise 食事する哲学者が輪にならずに一列に並んで座れば（フォークは哲学者の間と両端にあるとする）、デッドロックは起きないことを説明せよ。 :ref:`【解答例】 ` ========== セマフォ ========== セマフォ(:index:`semaphore`)は、整数値のカウンタと、スレッドキューを組み合わせた抽象データ型。P 命令と V 命令の二つの操作が可能。 P 命令 カウンタが 0 より大きければ、カウンタを 1 減らす。カウンタが0 以下ならば、現在のスレッドをキューに入れ、他のスレッドの実行に切り替える。 V 命令 スレッドキューが空ならば、カウンタを 1 増やす。空でなければ、スレッドキューからスレッドを一つ取りだし、そのスレッドの実行に切り替える。 言語仕様に含まれていなくても、OS の機能を利用して、ライブラリの形で実現可能。誤りのないプログラムを書くことが難しく、すぐにデッドロックなどを引き起こす。 .. admonition:: セマフォで生産者/消費者問題(協調的同期のみ) ``wait`` がP命令、 ``release`` がV命令に相当する。 .. code-block:: ada semaphore fullspots, -- 共有バッファに入っているデータの個数 emptyspots; -- 共有バッファで空いている場所の個数 fullspots.count := 0; -- 最初に入っているデータは0個 emptyspots.count := BUFLEN; -- 最初に空いている場所はBUFLEN個 task producer; loop -- データを生産する -- wait(emptyspots); -- 空きが無ければ待つ -- データを共有バッファに置く -- release(fullspots); -- データの個数を1増やす end loop end producer; task consumer; loop wait(fullspots); -- データが無ければ待つ -- データを共有バッファから取り出す -- release(emptyspots); -- 空きの個数を1増やす -- データを消費する -- end loop end consumer; * 既に入っているデータの個数をセマフォ ``fullspots`` で管理する。 * 通常は、生産者がデータを入れる時に ``release(fullspots)`` で1増やし、消費者がデータを取り出す時に ``wait(fullspots)`` で1減らす。 * バッファが空っぽの時（ ``fullspots`` の値が0の時）にさらに消費者がデータを取り出そうとすると、``wait(fullspots)`` のところで実行が停止する。次に生産者が ``release(fullspots)`` を実行すると、消費者の実行が再開する。 .. admonition:: セマフォで生産者/消費者問題(排他制御もやる) 共有バッファへのアクセスはきわどい領域なので、排他制御が必要である。 .. code-block:: ada semaphore exclusion, fullspots, emptyspots; exclusion.count := 1; fullspots.count := 0; emptyspots.count := BUFLEN; task producer; loop -- データを生産する -- wait(emptyspots); -- 空きが無ければ待つ wait(exclusion); -- ロックされていれば待つ -- データを共有バッファに置く -- release(exclusion); -- ロックをはずす release(fullspots); -- データの個数を1増やす end loop end producer; task consumer; loop wait(fullspots); -- データが無ければ待つ wait(exclusion); -- ロックされていれば待つ -- データを共有バッファから取り出す -- release(exclusion); -- ロックをはずす release(emptyspots); -- 空きの個数を1増やす -- データを消費する -- end loop end consumer; * セマフォ ``exclusion`` のカウンタが 1 ならばロックされていないことを、0 ならばロックされていることを表わす。 ======== モニタ ======== モニタ(monitor)とは、排他制御を言語の構文として構造化したもの。 * モニタ内部では、同時に一つのスレッドしか実行を許されない。したがって、必ず排他制御が行なわれる。 * モニタ内部でスレッドが寝ることができる。すると、次のスレッドがモニタ内に進入可能になる。 * モニタ内部で寝ているスレッドを起こすことができる。起こされたスレッドは、起こしたスレッドがモニタから出た後に実行を再開する。 セマフォに比べて、排他制御でミスをする可能性はかなり低い。しかし、協調的同期を行なうプログラムは依然として難しい。 .. admonition:: モニタで生産者/消費者問題 .. code-block:: modula2 type databuf = monitor const bufsize = 100; var buf : array [1..bufsize] of integer; next_in, next_out : 1..bufsize; filled : 0..bufsize; sender_q, receiver_q : queue; procedure entry deposit(item : integer); begin if filled = bufsize then delay(sender_q); buf[next_in] := item; next_in := (next_in mod bufsize) + 1; filled := filled + 1; continue(receiver_q) end ; procedure entry fetch(var item : integer) ; begin if filled = 0 then delay(receiver_q); item := buf[next_out]; next_out := (next_out mod bufsize) + 1; filled := filled - 1; continue(sender_q) end; begin filled := 0; next_in := 1; next_out := 1 end; type producer = process(buffer: databuf); var new_value : integer; begin cycle (* データを生産してnew_valueに入れる *) buffer.deposit(new_value); end end; type consumer = process(buffer: databuf); var stored_value : integer; begin cycle buffer.fetch(stored_value); (* stored_valueに入っているデータを消費する *) end end; .. admonition:: 課題19 :class: exercise Javaの構文要素で次の概念に対応するのはどれか？ * モニタ * モニタの中で寝る * モニタの中で寝ているスレッドを起こす :ref:`【解答例】 ` ========== チャネル ========== 共有メモリを排他制御しながら使うのはバグが発生しやすいので、共有メモリを使わず、通信で同期を行おうという考えもある。理論的にはプロセス代数や Communicating Concurrent Processes (CSP) が基礎になっている。CSPは仕様記述言語として使われているが、それに基づいたプログラミング言語もいくつか作られている。 Occam ----- CSPの概念をプログラミング言語として使えるようにしたもの。Transputerという並列コンピュータのために開発された。 通信はチャネル(channel)を通して行う。チャネルは一対一、片方向で同期的（書き手と読み手が同時に通信を行わなければならない）な通信路である。 * `An Introduction to the occam Language `_ Go -- Googleが開発している。2009年に発表され、2012年3月にVersion 1がリリースされた。 並行実行の単位はゴルーチン(goroutine)と呼ぶ。関数呼び出しの前に ``go`` を付けると、その関数がゴルーチンとして実行される。ゴルーチン間はチャネルで通信できる。 * `実践Go言語 `_