さて、前回までは排他制御の原則と実現戦略について学習のまとめ記事を書きました。

今回は、第17回「より高級な排他制御機構」をまとめていきたいと思います。

計算機システム概論第１７回「計算資源（CPU）の管理：より高級な排他制御機構」 - YouTube

モチベーション。
より高級な排他制御機構
Dijkstra のセマフォー
プロセスの状態遷移
- プロセスの状態遷移とP命令とV命令
Producer-Consumer 問題をセマフォーで解く
Producer
- P(EMPTY);
- P(Lock);
- V(Lock);
- V(FULL);
Consumer
まとめ

モチベーション。

Goの並行処理を理解したくて、まずはプロセスとスレッドを概念的に理解しようと思い見始めたこの講義ですが、最近ではすっかり生活の一部です。

育児をしながらだとPCの前に座ってコードを書くことも、また物理本をゆっくりと読むという時間もなかなかとれません。昼寝のタイミングでまとまった時間が取れることもありますが、家事やらで潰れることも多いです

がしかし、講義であれば、育児のスキマや家事しながらでもいけます。最近は寝かしつけのときに片耳だけイヤホンをハメて音声だけで聞いたりしてます。許せ息子。

もちろん一回聞いただけでは理解できないので、繰り返し聞いているのですが、そこも良いです。簡単に理解できてしまう内容であれば、すぐに飽きてしまいますが、自分にとっては適度な難易度なので、繰り返し聞いて理解を深める感覚もまたよいです。

なにより講義の内容が腹落ち感がすごいです。本質的には、なんなのか？ということに対して、明快に解説しておるので、楽しく聞くことができます

ということで、第17回「より高級な排他制御機構」興奮して進めてまいりましょう。

より高級な排他制御機構

講義では２つの排他制御機構について紹介しています。

Dijkstra のセマフォー
Brinch Hansen, Hoare のモニタ

今回は、セマフォーについてのみまとめてみました。

Dijkstra のセマフォー

まずは、用語について整理していきましょう。

セマフォ

セマフォは、

使用可能な資源の数 S と、使用可能な資源が無い (S == 0) の時の待ち行列を組みにしたデータ構造。

です。

後から詳しいことは理解しておくとして、一旦はイメージを載せておきます。

ちなみに、聞きなれない単語セマフォですが、鉄道などで列車が進行可能かどうかを示す信号機のことらしいです。

P命令

セマフォーは、P命令とV命令という２つの命令によって排他制御を行います。まずは、P命令から。

P命令は、資源の確保命令です。

コードにすると

P(S){
if (S == 0) then
     {プロセスを資源 S の待ち行列に入れる}
else
     { S = S - 1;}
}

となります。

S = 0 なら、プロセスを待ち行列にいれます。使用できる共有資源がない場合は、待つしかないからですね。

そして、S > 0 の場合、つまり共有可能な資源が存在する場合には、セマフォを１つ減らします。

日常生活に置き換えてみても、わかりやすいですね。

たとえば、混雑している駐車場などでは、満車の場合には道路に待機列を作りますよね。で、空きがある場合には、1台駐車されたらその分、駐車可能な台数が減るわけなので、空き台数を1つ減らしますね。

日常のいろんなところで、似たようなことが発見できそうです。

ちなみに、P命令は、オランダ語のpasserenから来ています。

passerenは、通る、合格するみたいな意味があるようですが、要は英語のpassと同じじゃないかなと。

P命令は、共有資源を要求したプロセスに対してパスする、PASS命令と覚えておくと忘れなそうですね。

V命令

続いては、V命令。

V命令は、資源の返却命令です。

コードにすると、

V(S){
if (S 待ちプロセスが存在)
    {一つのプロセスを選び Wakeup 処理}
else
   { S = S + 1; }
}

S > 0 で待ち行列がある場合、プロセスを１つ起動します。待ち行列がない場合には、Sを1つ増やします。

V命令のVですが、オランダ語のverhoog=起こすという言葉に由来しているそうです。

プロセスの状態遷移

ここで講義には出てこないのですが、P命令とV命令の理解がより深まると思ったので、プロセスの状態遷移についてざっとまとめたいと思います。

図にすると以下のようになります。

図の通り、プロセスは、３つの状態を遷移します。

プロセスの状態遷移とP命令とV命令

さて、ここでプロセスの状態遷移を確認したのは、P命令とV命令と関係しているからです。

まず、P命令ですが、P命令は共有資源がない場合には待ち行列にいれるわけですが、これは↑の図だと、wait命令を発行していることになります。

次に、V命令ですが、V命令は待ち行列で待っているプロセスを起こすわけなので、signal命令です。

繋がってきましたね。あばれる君的に言えば、プロセスについて少しずつですが理解が深まっていくのを感じざるを得ませんね。

Producer-Consumer 問題をセマフォーで解く

では、最後に Producer-Consumer 問題をセマフォーで解くを見ていきましょう。

講義では、「セマフォを使うことで、非常にエレガントに解ける」と解説していましたので、興奮してきますね。

Producer

まずは、Producerから

process Producer {
    while (TRUE) {
        { data 作成; }
        P(EMPTY);
        P(Lock);
        index = index + 1;
        BUF[index] = data;
        V(Lock);
        V(FULL);
    }
}

それぞれ、ステップを追って何をしているかを確認していきましょう。

講義スライドより引用

イメージしやすくするために、図も再度掲載します。

P(EMPTY);

まずは、EMPTYに対してP命令を発行しています。EMPTYは、空きバッファ数で初期値はMAXです。

生産者が、dataを格納できる最大値は、MAXの値です。

そのため、プログラム開始時にProducerは、Bufferに空きがあるかどうかを確認し、空きがあればこれから使用するので、一つ減らすという感じですね。

P(Lock);

続いては、Lockに対してP命令を発行し、バッファへのアクセス権を取得しにいきます。

このとき、他のプロセスがバッファのアクセス権を持っている場合には、待ち行列に入ります。

アクセス権が獲得できた場合には、バッファにデータを書き込んでindexを1つあげるという危険領域を処理します。

V(Lock);

危険領域を処理した後は、Lockを解放すればよいので、V命令を発行しLockを解放します。

もし、Lockを取得したいプロセスが待ちにいた場合には、そのプロセスを起動、signal命令を発行し、待っていたプロセスにアクセス権を譲ります。

待っているプロセスがいなかったら、+1してあげて、次にP命令を発行したプロセスが取得できるようにします。

V(FULL);

最後に、V(FULL)ですが、FULLセマフォを増やして、新しいdataがバッファに追加されたことを示します。

Consumer

では、続いてConsumerについて見ていきましょう。

process Consumer {
    while (TRUE) {
        P(FULL);
        P(Lock);
        data = BUF[index];
        index = index - 1;
        V(Lock);
        V(EMPTY);
        { data の処理; }
    }
}