10. 並行プログラミング¶

10.1. 並行と並列¶

逐次(sequential)

時間的に決められた順にしたがって実行すること。

並行(concurrent)

複数の実行単位相互の実行順序が決められていないこと。論理的並行とも言う。

並列(parallel)

複数のハードウェアによる実行が、時間的に重なりあって行われること。物理的並行とも言う。

並行は、必ずしも並列を意味しない。1個のCPUで並行実行するとは、複数の実行単位を切り替えながら実行するということ。

Preemptive

いつでも切り替わる可能性があるということ。実際にはタイマー割り込みや入出力イベントなどで切り替わる。

Non-preemptive

勝手には切り替わらない。切り替え用の命令を実行すると切り替わる。コルーチン(8.6 章)など。

10.2. 同期¶

スレッド(thread)

プログラム中の実行の軌跡、あるいは、実行を制御する単位（CPUのレジスタやスタックの内容を含む）。一つのスレッドはプログラムを逐次的に実行していく。同じプログラムを複数のスレッドが並行に実行することがある。

同期(synchronization)

プログラム中のある特定の点で、並行に実行されているスレッドの実行順序に制約を課すこと。

協調的同期(cooperation synchronization)

単に同期とも言う。他のスレッドの実行完了を待つ場合や、データの受け渡しを行なう場合。

競争的同期(competetion synchronization)

排他制御(mutual exclusion)とも言う。同時に一つのスレッドしかアクセスできない資源について、複数のスレッドが同時にアクセスしないように制御を行なう場合。

きわどい領域(critical section)

プログラム上で排他制御が必要な部分。危険領域とか臨界領域という場合もある。

競合の例

共有変数へのアクセスで排他制御を行なわないと何が起こるか？

変数 x の最初の値は 1 で、 x の値を 1 増やすプログラムがある。スレッド A と B がこのプログラムを並行に実行すると、次のような順序で実行される可能性がある。

A が x の値 1 を読み出す。
B が x の値 1 を読み出す。
A が 1 増やした値 2 を x に書き込む。
B が 1 増やした値 2 を x に書き込む。

共有資源に対して、他のスレッドがアクセスできないようにすることを、普通は「ロックをかける」と言う。すでにロックをかけられた資源にアクセスするためには、ロックが外れるまで待たなければならない。

デッドロック(deadlock)

すべてのスレッドが待ち状態となり、先に進めない。

餓死(starvation)

あるスレッドが共有資源にアクセスできない状態が永久に続く。

食事する哲学者

デッドロックが起きる可能性がある

loop
  左のフォークを取り上げる;
  右のフォークを取り上げる;
  食べる;
  両方のフォークを戻す;
  思考に沈む;
end

食事する哲学者改良版

餓死が起きる可能性がある

loop
  左のフォークを取り上げる;
  if 右のフォークが使われている
  then
    左のフォークを戻す;
  else
    右のフォークを取り上げる;
    食べる;
    両方のフォークを戻す;
    思考に沈む;
  end
end

課題18

食事する哲学者が輪にならずに一列に並んで座れば（フォークは哲学者の間と両端にあるとする）、デッドロックは起きないことを説明せよ。

【解答例】

10.3. セマフォ¶

セマフォ(semaphore)は、整数値のカウンタと、スレッドキューを組み合わせた抽象データ型。P 命令と V 命令の二つの操作が可能。

P 命令

カウンタが 0 より大きければ、カウンタを 1 減らす。カウンタが0 以下ならば、現在のスレッドをキューに入れ、他のスレッドの実行に切り替える。

V 命令

スレッドキューが空ならば、カウンタを 1 増やす。空でなければ、スレッドキューからスレッドを一つ取りだし、そのスレッドの実行に切り替える。

言語仕様に含まれていなくても、OS の機能を利用して、ライブラリの形で実現可能。誤りのないプログラムを書くことが難しく、すぐにデッドロックなどを引き起こす。

セマフォで生産者/消費者問題(協調的同期のみ)

wait がP命令、 release がV命令に相当する。

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) を実行すると、消費者の実行が再開する。

セマフォで生産者/消費者問題(排他制御もやる)

共有バッファへのアクセスはきわどい領域なので、排他制御が必要である。

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 ならばロックされていることを表わす。

10.4. モニタ¶

モニタ(monitor)とは、排他制御を言語の構文として構造化したもの。

モニタ内部では、同時に一つのスレッドしか実行を許されない。したがって、必ず排他制御が行なわれる。
モニタ内部でスレッドが寝ることができる。すると、次のスレッドがモニタ内に進入可能になる。
モニタ内部で寝ているスレッドを起こすことができる。起こされたスレッドは、起こしたスレッドがモニタから出た後に実行を再開する。

セマフォに比べて、排他制御でミスをする可能性はかなり低い。しかし、協調的同期を行なうプログラムは依然として難しい。

モニタで生産者/消費者問題

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;

課題19

Javaの構文要素で次の概念に対応するのはどれか？

モニタ
モニタの中で寝る
モニタの中で寝ているスレッドを起こす

【解答例】

10.5. チャネル¶

共有メモリを排他制御しながら使うのはバグが発生しやすいので、共有メモリを使わず、通信で同期を行おうという考えもある。理論的にはプロセス代数や Communicating Concurrent Processes (CSP) が基礎になっている。CSPは仕様記述言語として使われているが、それに基づいたプログラミング言語もいくつか作られている。

10.5.1. Occam¶

CSPの概念をプログラミング言語として使えるようにしたもの。Transputerという並列コンピュータのために開発された。

通信はチャネル(channel)を通して行う。チャネルは一対一、片方向で同期的（書き手と読み手が同時に通信を行わなければならない）な通信路である。

Occam Manual3

10.5.2. Go¶

Googleが開発している。2009年に発表され、2012年3月にVersion 1がリリースされた。

並行実行の単位はゴルーチン(goroutine)と呼ぶ。関数呼び出しの前に go を付けると、その関数がゴルーチンとして実行される。ゴルーチン間はチャネルで通信できる。

とほほのGo言語入門 - とほほのWWW入門

10. 並行プログラミング¶

10.1. 並行と並列¶

10.2. 同期¶

10.3. セマフォ¶

10.4. モニタ¶

10.5. チャネル¶

10.5.1. Occam¶

10.5.2. Go¶

目次

前のトピックへ

次のトピックへ

このページ