Aritalab:Lecture/Programming/Java/Parallel

Latest revision as of 11:43, 24 June 2013

[edit] Javaによる並列プログラミング

このページでは並列プログラムの基本概念を習得します。並列プログラミングの基本は

• スレッド
• 排他制御
• 同期制御

になります。個々の概念をサンプルプログラムを用いて解説します。

[edit] スレッド

コンピュター上のアプリケーション・プログラムは、OSからみると「プロセス」という単位で実行されています。個々のプロセスはメモリ空間やファイル入出力などを独自に備えています。（個々のアプリケーションプログラムは独立ですから、当たり前です。）並列プログラミングを行う場合、こうしたプロセスを複数作成して並列処理を実装することも可能ですが、複数プロセスを操作するにはOSのカーネルモードとユーザーモード（アプリケーション自身のモード」を行き来することになります。このオーバーヘッドは望ましくありません。そこで単一のプロセス内に（つまりメモリ空間やファイルデスクリプタを共有した形で）複数の実行単位を持たせたものを「スレッド」と呼びます。以前は軽量 (lightweight) プロセスとも呼ばれました。

[edit] スレッドの作成

まずは以下のプログラムを実行してみてください。このプログラムは２つのスレッドを作成し、それぞれ 0-50 ms 休みながら数字をカウントして終了します。実行するたびに出力結果が異なることを確認して下さい。また、メイン関数から呼ばれる test() の処理がスレッドよりも早く終了することも確認して下さい。

class Counter extends Thread {
  String indent;
  public Counter(int c) {
    StringBuffer sb = new StringBuffer();
    for(int i=0; i < c; i++) sb.append('\t');
    indent = sb.toString();
  }

  public void run() {
    System.out.println(indent+"ready");
    try {
    for (int i=0; i < 5; i++) {
      Thread.sleep((int)(Math.random()*50)); // sleep for 0-50 ms
      System.out.println(indent+"count: " + i);
    }
    } catch (Exception e) { e.printStackTrace(); } 
    System.out.println(indent+"done");
  }
}

public class ThreadTest {
  static void test() {
    Counter thread1 = new Counter(0);
    Counter thread2 = new Counter(1);
    System.out.println("START");
    thread1.start();
    thread2.start();
    System.out.println("FINISH");
  }

  public static void main(String[] args) {
    ThreadTest.test();
  }
}

実行例（毎回異なる）

START
FINISH
ready
	ready
	count: 0
	count: 1
	count: 2
count: 0
count: 1
	count: 3
count: 2
	count: 4
	done
count: 3
count: 4
done

Java におけるスレッドは二通りの作成法があります。

1. Thread クラスを継承する
2. Runnable インターフェースを継承する

最初のほうが簡単ですが、後者のほうが（自分でクラスのデザインをできるぶん）柔軟です。インターフェースとは、「これこれの機能を実装しなくてはならない」という制約のみを付加する概念です。クラスとして実際に継承する中身はありません。 Counter テストプログラムの場合、Runnable を用いて書くには以下のようにします。

class クラス名 extends 継承する親クラス

とする代わりに

class クラス名 implements 実装すべきインターフェース

と書きます。

class Counter implements Runnable {
 ...
 }

static void test() {
   Counter thread1 = new Counter(0);
   Counter thread2 = new Counter(1);
   System.out.println("START");
   new Thread(thread1).run();
   new Thread(thread2).run();
   System.out.println("FINISH");
 }

クラス定義の部分で implements Runnable と、Runnableインターフェースを継承しています。このとき、インターフェースの定義から run() というメソッドを必ず実装しなくてはなりません。敬称の時に extends Thread とThreadクラスを継承すると、デフォールトの run() メソッドとしてThread クラスの run() を継承しますが（もちろん上書きすることもできる）、implements Runnable の場合は必要なメソッドを自分で実装しなくてはなりません。この違いはC++と異なり Java は多重継承を許さない点に起因します。例えば Applet クラスでスレッドを使いたい場合、Thread と Applet と両方を継承できないので Runnable というインターフェースを継承するのです。

[edit] リソースの共有

[edit] 排他制御：ロックとクリティカルリージョン

以下の Java プログラムを実行してみてください。スレッドが２つあり、それぞれが 1 を足していますが結果も 1 になります。なぜでしょうか。

public class ThreadTest {
  Integer val = 0; //ここが int でなくIntegerの理由は後述
  void addValue(int x) {
    int tmp = val;
    try { Thread.sleep((int)(Math.random()*100)); } catch(Exception e) {}
    val = tmp + x; 
  }

  class Adder extends Thread {
    ThreadTest v; 
    Adder(ThreadTest x) { v = x; }
    public void run() { v.addValue(1); }
  }
  
  void test() {
    Adder a1 = new Adder(this);
    Adder a2 = new Adder(this);
    a1.start();
    a2.start();
    try { a1.join(); a2.join(); } catch(Exception e) {}
    System.out.println(val);
  }

  public static void main(String[] args) {
    ThreadTest v = new ThreadTest();
    v.test();
  }
}

この不整合は、addValue メソッドが 2 つのスレッドに同時に呼ばれることが原因です。それぞれのスレッドが変数 val のコピーを持つために結果が 2 になりません。この解決は簡単で、addValue メソッドを synchronized 指定します。同一クラスの synchronized メソッドは複数のスレッドが同時実行できません。このような制限をロック (lock) と呼びます。Javaではメソッドだけでなくメソッド内の特定ブロックのみを synchronized 指定することも可能です。以下のようにすると、どちらも同じく 2 を返すようになります。このようにスレッド間で共有するリソースが使われる部分をクリティカルリージョン (critical region) と呼びます。

メソッド内のブロックを指定する時はロックするクラスを指定（以下の場合は val ）する必要があります。このため、このプログラムは val を Integer にしていたのでした。

void addValue(int x) {
    synchronized (val) {
    int tmp = val;
    try { Thread.sleep((int)(Math.random()*100)); }
    catch(Exception e) {}
    val = tmp + x;
    }
  }

synchronized void addValue(int x) {
    int tmp = val;
    try { Thread.sleep((int)(Math.random()*100)); }
    catch(Exception e) {}
    val = tmp + x;
  }

[edit] 基本データ型のロック

Javaではすべてのクラスがロックを獲得できますが、int, boolean などの基本データ型はロック機能を持ちません。Integer や Boolean 等のラッパークラスを使えば良いのですが volatile 指定することでロックらしき機能を実現することができます。volatile 指定されたフィールドは直ちにメモリ上および全てのスレッドに反映されます。よって複数スレッドが異なるコピーを持ち合う競合を起こしません。

[edit] スレッド間のやり取り

複数のスレッド間でリソースをやり取りするにはどうすればよいでしょうか。汎用の解決策はなく、事例別にプログラムを組まねばなりません。ここでは２つのスレッドでタスクを処理する例を考えましょう。タスクの置き場所を共有し、そこに Creator メソッドがタスクを置きます。また Processor メソッドがタスクを処理します。Creator メソッドがタスクを 1 個置く毎に Processor メソッドの処理を待つようにするには、置き場所へ常に 1 スレッドがアクセスするように制限するだけでなく、Creator がタスクを一つ置いたら Processor の処理を待たねばなりません。これには wait(), notifyAll() メソッドを利用します。

class Task {
  int val = 0;
  Task(int x) { val = x; }
  public String toString() { return new Integer(val).toString(); }
}

class TaskList {
  Task current;
  boolean ongoing = false;
  boolean done = false;

  synchronized void createTask(Task t) {
    while (ongoing) {
      try { wait(); } catch (Exception e) {}
    }
    ongoing = true;
    current = t;
    System.out.println("Set " + t);
    notifyAll();
  }

  synchronized void processTask(int i) {
    while (!ongoing) {
      try { wait(); } catch (Exception e) {}
    }
    current.val *= i;
    ongoing = false;
    notifyAll();
    System.out.println("\tDone " + current);
  }
}

class Creator extends Thread {
  private TaskList L;
  private int[] list = { -1, -2, -3, -4 };

  public Creator(TaskList l) { L = l; }

  public void run() {
    for (int i : list) {
      try {
        Task t = new Task(i);
        L.createTask(t);
        Thread.sleep((int)(Math.random()*50));
      } catch (Exception e) {}
    }
    L.done = true;
  }
}

class Processor extends Thread {
  private TaskList L;

  public Processor(TaskList l) { L = l; }

  public void run() {
    while (!L.done) {
      try {
        Thread.sleep((int)(Math.random()*50));
        L.processTask(-1);
      } catch (Exception e) {}
    }
  }
}

public class ThreadTest {
  static void test() {
    TaskList L = new TaskList();
    Creator p1 = new Creator(L);
    Processor p2 = new Processor(L);
    p1.start();
    p2.start();
  }

  public static void main(String[] args) {
    ThreadTest.test();
  }
}

上記のプログラムを実行するとどうなるでしょうか。考えてみて下さい。Creator メソッドは 4 つのタスクを for ループで作成しますが Processor メソッドが処理するまでは wait() によって待たされます。Processor スレッドはタスクを処理するたびに notifyAll() で通知をおこない、そのたびに Processor メソッドが新たなタスクを登録する仕組みになっています。

[edit] Concurrentパッケージ

このページをみて下さい。