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

An Introduction to the occam Language

10.5.2. Go¶

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

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

実践Go言語

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

10.1. 並行と並列¶

10.2. 同期¶

10.3. セマフォ¶

10.4. モニタ¶

10.5. チャネル¶

10.5.1. Occam¶

10.5.2. Go¶

目次

前のトピックへ

次のトピックへ

このページ