第7回(11/13) マルチスレッド
  ・スレッド、共有と排他制御

■ 用語説明
【プロセス(process)】オペレーティングシステム(OS)は、複数のアプリケーションを同時に実行することができる。これを並列処理という。たとえば、WWW ブラウザなどでは１つのアプリケーションで複数のウインドウを開き処理をしている。プロセスとは、OS がアプリケーションのプログラムを管理するときの単位である。
【親プロセス・子プロセス】プロセスは、新しいプロセスを作ることができる。作り主のプロセスを親プロセス、作られたプロセスを子プロセスという。
【スレッド(thread)】一般に、スレッドとは、プロセスを更に細分化したものを指す。スレッドを管理の単位とするOSもある。

● Thread クラス
Ruby では、並列処理にスレッドオブジェクトを使う。

■ マルチスレッドのプログラム
  ┌───────────┐
  │プログラム            │    Ruby プログラムは先頭から順に実行する。
  │require 'thread'      │    親スレッドとして
  │1行目 s1              │      命令（ステートメント）s1、s2、s3、…、
  │2行目 s2              │    を実行している。
  │3行目 s3              │
  │  ：                  │（並列処理開始）
  │fork 文 {             │    fork 文に来ると、親スレッドが子スレッド
  │     fork に附属する  │    を作る。子スレッドは、fork に付随するプログ
  │     プログラム       │    ラム部分（{ }で囲まれた部分。ブロックという）、
  │     k行目   sk       │      sk、sk1、…
  │     k+1行目 sk1      │    を実行する。親スレッドはこのブロック内は実行しない。
  │       ：             │
  │       ：             │
  │}                     │    親スレッドは、子スレッドを作ると、
  │n行目    sn           │      sn、sn1、…
  │n+1行目  sn1          │    を実行する。子スレッドはこの部分は実行しない。
  │  ：                  │
  │  ：                  │（並列処理終了）
  │join 文               │    親スレッドの実行が、join 文に来ると、子スレッドの処理終了を待つ
  │m行目     sm          │    親スレッドのみになり、
  │m+1行目   sm1         │      sm、sm1、…
  │  ：                  │    を実行する。
  └───────────┘
                               並列処理期間
            ─────────━━━━━━━━━━────────> 時間
親スレッド  s1,s2,s3,…, fork, sn, sn1,sn2,…,    join,sm,sm1,… 
子スレッド                    sk,sk1,     sk2,…

※ 子スレッドが親スレッドより早くプログラムを実行し終えると、自然に並列処理が終了する。しかし、そのようなプログラムでは、動作の状態が曖昧になる。そこで、join 文により、それ以降が並列処理でないことを明確にする（また、親スレッドが終了すると、子スレッドは処理途中でも終了となる）。

● Thread クラスの使い方
   (1) require 'thread'   により、スレッドのクラスライブラリをロードする。
   (2) fork 文は、
       変数 = Thread::fork{
           子スレッドのプログラム
           :
       }
       と書く。変数は、子スレッドを表す。
       （スレッドがオブジェクトという意味をこめて、Thread::new{ - - } とすることもできる）
   (3) join 文は、
       子スレッドのインスタンス.join
       と書く。実際には、(2)で得た変数を使う。
⇒ list0701.rb
⇒ list0702.rb  （終了待ちをする場合。join 行をコメントアウトして違いを見比べよう）

□□□ 演習1 □□□
子スレッドを呼出す前に定義したサブルーチンは、子スレッドから使うことができる。次のとおり、プログラムを作れ。バブルソートサブルーチンを、プログラム前半で定義する。メインルーチンでは、子スレッドを5つ作り、その中で整数の配列をバブルソートさせる。子スレッドは、ソートを終えるとそれを表示する（p 配列変数）。親スレッドは、すべての子スレッドが終了するのを待ち、終了すると「end」と表示する。

# バブルソートのサブルーチン
def bubblesort!(list)
    j = list.size - 1
    while j > 0 do
        i = 0
        while i < j do
            if list[i] > list[i+1]
                tmp = list[i]
                list[i] = list[i+1]
                list[i+1] = tmp
            end
            i += 1
        end
        j -= 1
        sleep(0.7)    # 並列処理のちがいを明かにするため
    end
end

# メインルーチンの一部
- - -
t1 = Thread::fork{
    list = [5,3,1,2,4]
    bubblesort!(list)
    p list
}       
t2 = Thread::fork{
    list = [50,30,10,20,40,60]
    bubblesort!(list)
    p list
}
- - -
⇒ prac0701.rb

■ 共有と相互排除（Mutal Exhibition）
   ・危険な使い方
⇒ list0703.rb
   ・相互排除クラス Mutex と同期メソッド synchronize
⇒ list0704.rb

□□□ 演習2 □□□
list0703.rb と list0704.rb の実行結果を比較せよ。

□□□ 演習3 □□□
入力文字列の中に "001","010",または,"100" があれば "000"、"110","101",または,"011"があれば"111"、と書き換えたい。１つめのスレッドは"001"だけを担当し、２つめのスレッドは"010"を担当する、というようにして６つの書き換えスレッドを作れ。書き換えスレッドは、時間待ちのためsleep(0.5)を実行後、相互排除を行って書き換えよ。また、文字列全体を表示するスレッドを作れ。表示スレッドは、前状態と現状態に違いがある場合のみ表示せよ。

入力文字列が、"10100101011010" であるとき、変化の様子を表示せよ。

なお、プログラムの概要は list0705.rb のとおりである。

※ 全体文字列を変数 a であらわすとする。a="abaa" のとき、"aba"を"aaa"に書き換えるプログラムは、a.gsub!(/aba/,"aaa") となる。
⇒ prac0703.rb
※ 実行結果は様々である。何回も実行し直して違いを見比べよう。

■ 宿題 ■
演習3では、すべての書き換えを表示するものではなかった（たとえば、書き換えスレッド1と書き換えスレッド2の実行後に表示スレッドが実行されることがあり、スレッド1の結果が表示されていなかった）。そこで、表示終了フラグshowflagを導入する。書き換えスレッドは表示終了フラグが立っている(true)ときに書き換えを行うことができ、書き換えを行うと表示終了フラグを下げる(false)。表示スレッドは表示終了フラグが下がっているとき表示を行い表示終了フラグを立てる。

プログラムを作成し、コメントを手書きし、実行結果の一例を印刷し、提出せよ。
⇒ work0701.rb