アルゴリズムの振る舞いを図解する

【 アルゴリズムの振る舞いを図解する 】

今回のセッションでは、Producer-Consumer同期のアルゴリズムの振る舞いを図解してみようと思います。（アルゴリズムの記述をみて、その振る舞いがわかった方は、読みとばしてもらって構いません。）

ポイントは、ProducerのプロセスにもConsumerのプロセスにも登場するawait 命令です。正確にいうとawait の後ろの条件文が重要です。

await 条件文 命令は、条件文が真になるまで、次のブロックの実行をせずに待機し続けます。逆にいうと、条件文が偽になった時初めて、次のブロックを実行します。

Producerのawait 命令は、await Len(buf) < N という形をしています。Consumer のawait 命令は、await Len(buf) > 0　という形をしています。どちらの条件文にも、 使われているバッファーの長さを示す Len(buf) という式が含まれています。

このことは、ProducerのプロセスとConsumerのプロセスの同期に、この式の値が利用されていることを示しています。以下では、LB = Len(buf) と表すことにしましょう。

LB = N となるのは、どういう場合でしょうか？　それは N個の容量を持つバッファーが全て使われている場合です。この時、バッファーにはデータを受け入れる余裕がないので、データを入力 in からバッファー buf に送り込もうとするProducer は待機を続けます。

LB = 0 となるのは、どういう場合でしょうか？　それは バッファーが空の場合です。この時、バッファーには読みこむべきデータがないので、データをバッファー buf から読み込んで出力 out に送り込もうとする Consumer は待機を続けます。

結局、ProducerとConsumerの待機状態が解けて、それぞれのプロセスが本来の仕事をするのは、 0 < NB < N の場合だけであることがわかります。ProducerはNBの値を一つだけ増やし、ConsumerはNBの値を一つだけ減らします。

一つ注意したいことがあります。

以前に、「振る舞いは、状態の変化の系列だ」と述べたと思います。ただ、Produucer, Consumer プロセスが待機状態にある時、状態は変化しません。こうした状態を stuttering state (停滞状態)と言います。「停滞状態」も、状態は変化しませんが、システムの振る舞いを構成するその重要な一部になります。

-------------------------------------------

セッションの動画のURL https://youtu.be/GfvGENvC6MY?list=PLQIrJ0f9gMcOeqlB09PdBddfXLv2QjG-F

スライドのpdf https://drive.google.com/file/d/14q_Ugtd4j3gvgYTB34lw7FKDSwdWwLPd/view?usp=sharing

関連blog 「アルゴリズムの振る舞いを図解する」 https://maruyama097.blogspot.com/2022/07/blog-post_22.html

参考資料 Lamport, L. The Computer Science of Concurrency: The Early Yearshttps://cacm.acm.org/magazines/2015/6/187316-turing-lecture-the-computer-science-of-concurrency/fulltext#R9

セミナーのまとめページ

https://www.marulabo.net/docs/concurrent/

セミナー告知・申込ページ https://concurrent.peatix.com/view -------------------------------------------