« セマフォとミューテックス(2) | トップページ | 私はペンが長い »

2018年8月16日 (木)

生産者・消費者問題

某質問サイトで次の問題に関する質問が有りました。なお、2016 年の質問です。 元記事

セマフォを使い、消費者生産者問題を解きなさい。

4つのプロセスがあり、1つは生産者で残りの3つは消費者である。生産者は1度の実行により1つのアイテムを生成し、それをバッファに置く。生産者はバッファが空の時のみ実行を開始できる。9回実行し、9個のアイテムを1つずつ生成する。バッファのサイズは最大9個とする。バッファが9個いっぱいになったときのみ、残りの3つの消費者はバッファから消費が可能となる。それぞれの消費者は1度の実行につき1つのアイテムを消費する。9つすべてのアイテムがなくなるまで消費し続ける。そして、空になった時また生産者は9個のアイテムを生成し始める。その生成中は消費者は消費することはできない。

生産者は全てのバッファが空になるまで生産を開始せず、消費者は全てのバッファが埋まるまで消費を開始しません。この制限が無ければ、普通にセマフォを使ったプログラムでOKです。しかし、この制限がチョット面白そうなので、この問題を考えてみることにします。

以下の解は、シグナルによって目覚めるプロセスは、待ち行列に入っている先頭の1つだけということを前提としています。(仮にそうでなくても、細工をして、この前提を満たすように出来るでしょう。)

生産者は次の通りです。

void producer(void)
{
    while (1){
        int i;
        sem_wait(&empty, my_id);    /* (1-1) */
        for (i = 0; i < 9; i++){
            put_buf();
        }
        sem_sig(&stock);        /* (1-2) */
        ・・・
    }
}

生産者は1人なので簡単です。 empty はバッファが空かどうかを示すセマフォで、初期値は1です。そのセマフォを使って、バッファが空になるのを待ち(1-1)、空になれば9個のアイテムをバッファに置きます。置き終わったら、セマフォ stock のシグナルを送ります(1-2)。 stock はバッファにアイテムが有るかどうかを示すセマフォで、初期値は0です。どちらのセマフォも2進セマフォです(ミューテックスではない)。

消費者は次の通りです。

void consumer(void)
{
    while (1){
        int n;
        sem_wait(&stock, my_id);        /* (2-1) */
        n = take_buf();        /* (2-2) */
        if (n == 0){
            sem_sig(&empty);        /* (2-3) */
        } else {
            sem_sig(&stock);         /* (2-4) */
        }
        ・・・
    }
}

消費者は1工夫します。バッファにアイテムが置かれた時のシグナル stock を待ち(2-1)、バッファからアイテムを取り出します(2-2)。この時、バッファの残数を返してもらいます。その残数が 0 ならばセマフォ empty のシグナルを送って(2-3)生産者に仕事を促します。残数が 0 でなければセマフォ stock のシグナルを送ります(2-4)。生産者の場合は、バッファが満杯になった時に stock のシグナルを送っていましたが、消費者の場合は、バッファが0でなければシグナルを送ります。

以上が上記問題に対する私の解です。面白そうだと思ったのは錯覚だったようです。「制限」の無い方が面白いかも知れません。

« セマフォとミューテックス(2) | トップページ | 私はペンが長い »

プログラミング」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/584699/67064086

この記事へのトラックバック一覧です: 生産者・消費者問題:

« セマフォとミューテックス(2) | トップページ | 私はペンが長い »