« 自前のセマフォは案外たいへん(おまけ) | トップページ | セマフォとミューテックス(2) »

2018年7月19日 (木)

セマフォとミューテックス(1)

Wikipedia でセマフォの解説を読んで、どうにも納得出来ない個所が有ります。「重要な観点」という節で「要求したことのない資源を解放する」のは間違った使い方であると言っているのに、その後の節「例:生産者・消費者問題」は次のようになっています(表記は適宜変更しています)。

produce:
    emptyCount.wait();
    useQueue.wait();
    putItemIntoQueue(item);
    useQueue.signal();
    fullCount.signal();        // (0-1)

consume:
    fullCount.wait();
    useQueue.wait();
    item = getItemFromQueue();
    useQueue.signal();
    emptyCount.signal();    // (0-2)

producefullCount.signal() を実行していますが、それ以前に fullCount.wait() しているわけではありません(0-1)。つまり、要求したことのない資源を解放しているのです。 consumeemptyCount.signal() も同様です(0-2)。私は何か勘違いしているのでしょうか?

とにかく、上記の生産者・消費者問題のコードのように、セマフォは、 wait()signal() の対が同一プロセスで実行される必要は有りません。これがミューテックスとの大きな違いです(ということを今回、知ることが出来ました)。 wait()signal() を異なるプロセスで実行して良いとなると、その行為を「獲得・解放」と呼ぶのは適切ではないでしょう。代わりに「減少・増加」が良いと思います。これは、セマフォは「数」であるという見方に基づいた表現です。後で sem_down()sem_up() という関数を導入する予定です。

さて、「自前セマフォは案外たいへん」で示したコードは、(おまけ)でも書いたように、あのままではセマフォでもミューテックスでもないと判ったわけなので、改造案を示したいと思います。

まず、ミューテックスへの改造です。 mtx_unlock() のパラメータに実行者のプロセス ID を追加します(1-1)。その ID が que->id[que->first] に等しくなければエラーで返ります(1-2)。ミューテックスでは、 que->first はミューテックスの所有者を指しています。また、ミューテックスでは、それを獲得しているプロセスは1つだけなので、 (1-2) のチェックを掻い潜ってそれ以降に到達できるのは正当な権利を持ったプロセス1つだけです。したがって、シグナルを送る(1-4)前にスピンロックを解除(1-3)しても問題有りません。これでミューテックスの改造はOKです(たぶん)。

int mtx_unlock(queue_t *que, process_id id){        /* (1-1) */
    ・・・
    spinlock(&(que->lock));
    if (que->id[que->first] != id){        /* (1-2) */
        spinunlock(&(que->lock));
        return -1;
    }

    que->id[que->first] = 0;
    if (++(que->first) == que->size)
        que->first = 0;
    id_next = que->id[que->first];
    spinunlock(&(que->lock));            /* (1-3) */

    ・・・
    _os_send(id_next, que->signal);     /* (1-4) */
    ・・・
}
- 以下続く-

« 自前のセマフォは案外たいへん(おまけ) | トップページ | セマフォとミューテックス(2) »

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

コメント

コメントを書く

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

トラックバック

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

この記事へのトラックバック一覧です: セマフォとミューテックス(1):

« 自前のセマフォは案外たいへん(おまけ) | トップページ | セマフォとミューテックス(2) »