有限バッファ問題

セマフォを使うと簡単に解決することができる代表的な問題である 有限バッファ問題(bounded buffer problem)を紹介しよう． この問題は 2 値ではなく， N 個の値を持つセマフォを考える．通常，セマフォはこちらを指す．

バッファとは，以下のように「ある値」を要素に持つ箱の集まりである． 元々の意味は，緩衝装置の意味で，コンピュータでの装置 (デバイス,device) 間での通信においてデータの流れを調節する場合に用 いられる．

図 8: 有限バッファ問題

有限バッファには，入力ポインタ(input pointer)と， 出力ポインタ(output pointer) があり， 各々データをバッファに入れる位置と，バッファから出す 位置を示す．また，各ポインタにはセマフォを付随させる(2 個のセマフォを 生成)． これらのセマフォは 2 値セマフォと違い整数値を保持するものとする．各々，

1. N - (現在格納されている要素数)
2. 現在格納されている要素数

を示す．

1. は，「入力ポインタ」に付随しているセマフォで， 「バッファが一杯でないか」をチェックする役目を持つ． 2. は，「出力ポインタ」に付随しているセマフォで， 「バッファが空でないか」をチェックする． ここで，どちらのセマフォも各ポインタが役目を果たせずに，待ち状態になる かをチェックしていることに注意しよう．

では，例題として以下のプログラムを見てみよう．

public class BBuffer {
  int values[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
  int inputp=0; int outputp=0;
  Semaphore isem; Semaphore osem;
  BBuffer() {
    isem = new Semaphore(10);
    osem = new Semaphore(0);
  }
  public void input(int i) {
    isem.Wait();
    values[inputp]=i;
    inputp=(++inputp)%10;
    osem.Signal();
  }
  public int output() {
    osem.Wait();
    int r=values[outputp];
    outputp=(++outputp)%10;
    isem.Signal();
    return r;
  }
  public static void main(String args[])
  {
    BBuffer bbuffer=new BBuffer();
    Producer p = new Producer(bbuffer);
    Consumer c = new Consumer(bbuffer);
    p.start(); c.start();
  }
}
class Producer extends Thread {
  BBuffer bbuffer;
  Producer(BBuffer bbuffer) {
    this.bbuffer=bbuffer;
  }
  public void run() {
    for(int i=0; i<100; i++) {
      System.out.println("input="+i);
      bbuffer.input(i);
    }
  }
}
class Consumer extends Thread {
  BBuffer bbuffer;
  Consumer(BBuffer bbuffer) {
    this.bbuffer=bbuffer;
  }
  public void run() {
    for(int i=0; i<100; i++) {
      System.out.println("output="+
        bbuffer.output());
    }
  }
}

クラス BBuffer のインスタンスにより有限バッファを表現している． バッファに値を入力する場合は input メソッドを使い， バッファから値を出力する場合は output メソッドを使う． 各々バッファへ入力するオブジェクトとして クラス Producer のインスタンスを定義し， バッファから出力するオブジェクトとしてクラス Consumer のインスタンスを定義する． 両オブジェクトはスレッドとして起動される． バッファは有限の大きさ (ここでは 10) しか持っていないので バッファの最後にポインタが来たら，最初にポインタを進める操作も必要であ る．そのため，

inputp=(++inputp)%10;

のように，

ポインタを進めた後にバッファの大きさの剰余をと るようにしている． バッファの要素は -1 で初期化され「要素なし」を意味する． 同期をちゃんと処理すれば，要素が入っているかどうかを気にせずにポインタ の操作のみでうまく処理される．

このプログラムを実行すると以下のようになる．

input=0
input=1
input=2
output=0
output=1
output=2
input=3
input=4
input=5
input=6
input=7
input=8
input=9
output=3
output=4
output=5
output=6
input=10
input=11
input=12
input=13
. . .

最初，クラス Producer のインスタンスにより input メソッドが呼出 され，3 つの値 (1と2，3) が入力される．その後， クラス Consumer のインスタンスに処理が移り，入力された値が取り出 されていることがわかる．再び クラス Consumer のインスタンスに処 理が移りバッファに値が入力されている．

結果として，0 から 99 の値がバッファへ入力され， 更にバッファから取り出されていることが確認できるが， その間も有限の個数しか持たない (10 個) バッファをうまく利用して待ち合 わせ処理が行われている．