過去・現在・未来

【 すみっこぐらし 】 稚内でも暑い日が始まりました。 今年初めてエアコンのスイッチを入れたのですが、うんともすんとも反応しません。 故障発覚から二日後の昨日の朝、ダイキンさんが、エアコン修理に来てくれました。 というか、コンセントをチェックしていたのですが、 　「あれ、これ電気きてないですね。」 電気がなければエアコン動かないですね。ただ、本体故障以外の電源工事や設置工事の問題は、別業者の責任区分になるとのこと。確かに、電気が来てなくて動かないエアコンは故障とは言えないし、修理のしようもないですからね。 どうすればいいの？　たらい回しになるのを一瞬心配したのですが、ダイキンさん、設置業者のケーズ電気さんに直接連絡をとって、事情を説明しくれました。 夕方、今度は、ケーズ電気の人が来てくれて配電盤をチェック。 　「あれ、これ、ここまで電気きてないですね。」 3年前、エアコンを買い替えた時、少し大型のにしたのですが、その時エアコン用に200Vの電源を用意してもらいました。100Vの方はちゃんと電気が来ているんですが、200Vの方の電気が来ていないとのこと。 屋内の配電工事はケーズさんの責任区分だけど、200Vの配電は北電さんの責任区分だといいます。デジャヴュです。 ただ、いいデジャヴュもあるんですね。今度も、ケーズさんが直接北電さんに連絡をとってくれ、夜の9時近くになって、今度は北電さんが来てくれました。 　「やはり、200V きてないですね。」 そんな。去年の夏はちゃんと動いていたのに。 ただ、さすがプロですね。思い当たることがあるようで、暗い戸外に出ていきました。家のブレーカーも落として欲しいというので、僕らも電気のない暗い室内で待機です。 10分もしないで戻ってきて、 　「ブレーカー入れて、エアコン試してもらえますか？」 なんと、エアコン復活しました。よかった。 北電さん、 　「こちらの施工不良です。」 と、いさぎよく、非を認めました。えらい。 ダイキン、ケーズ、北電の伝言ゲームは、一日で首尾よく終了です。 でも不思議です。どうして、それまで問題なかった戸外の配電にトラブルが起きたのか。 一つだけ思い当たることがあります。家の近くの電柱が、冬の間に除雪車にぶつかって傾いていたので、先週、大規模な修理工事をしていました。あるいは、その工事に關係あるのかもしれません。

【 次章へ。その前に ... 】 今回から、「生産者消費者同期」の話題に入ろうと思います。 「生産者消費者同期」問題というのは、データを生み出すデバイス（生産者）とデータを受け取るデバイス（消費者）との間をどう同期させるのがいいのかという問題です。 コンピュータが誕生したその最初期から、ハードウェア的な「バッファー」は使われてきました。バッファーのコントロールは、典型的な「生産者消費者同期」問題です。    その前に、というか、その最初に、ダイクストラの  semaphore を取り上げようと思います。というのも、この問題を初めて並列プログラミングの問題として捉え、semaphoreを利用してこの問題を定式化したのは、ダイクストラだったからです。 semaphoreの性質をまとめておきましょう。 　● semaphore というのは、全てのプロセスから共通にアクセスできる、0 または 正の整数値を取る変数のことです。 　● semaphore には、値を +1だけ増やす操作と、値を -1だけ減らす操作が用意されています。 　● semaphoreに対する操作は、アトミックに行われます。（他のプロセスが操作途中に介在することを許さない） これだけですが、semaphoreの導入は、並列アルゴリズムの記述に、大きな威力を発揮します。 今回のセッションでは、以前見たダイクストラの 「排他制御アルゴリズム」と、これから見ていく「生産者消費者同期アルゴリズム」が、semaphore を使うとどう記述できるかを紹介したいと思います。　 ------------------------------------------- セッションの動画のURL https://youtu.be/KFOxAummbBg?list=PLQIrJ0f9gMcOeqlB09PdBddfXLv2QjG-F スライドのpdf https://drive.google.com/file/d/13xbaDAWvH0ETk-KZFHEYzVViM32TJYjz/view?usp=sharing 関連blog 「次章へ。その前に ...」 https://maruyama097.blogspot.com/2022/07/blog-post_15.html 参考資料 Dijkstra, E.W. Cooperat

【 無理は承知で ... 】 このセッションでは、ランポートの「パン屋のアルゴリズム」の新しいバージョンを紹介します。 何が新しいかというと、彼はアルゴリズムを記述するのに「並列にプロセスを実行する」という命令を導入して、その命令を使って「パン屋のアルゴリズム」を書き換えました。 以前のアルゴリズムそのものにに不満があったというより、そのアルゴリズムの「正しさの証明」 -- Assertiion ベースの証明に不満があったようです。 アルゴリズムの新しい記述法の導入にともなって、「並列にプロセスを実行する」とはどういうことなのか、「プロセスの相互排除」とはどういうことなのかを、改めて考えることになりました。 彼が注目したのは、時間の問題です。プロセスAの実行時間とプロセスBの実行時間の、時間軸上での関係を考えます。 プロセスAの実行が完全に終わってからプロセスBの実行がはじまる、あるいは、その逆に、プロセスBの実行が完全に終わってからプロセスAの実行がはじまるなら、それは、プロセスAとプロセスBの「並列実行」とは言いません。 並列実行（コンカレントな）実行というのは、二つ以上のプロセスが同時あるいは時間的には重複して実行される状態をさします。 critical section にはたかだか一つのプロセスの侵入しか許さないという、プロセスの相互排除が目指している状態は、それとは、まったく逆のものです。 プロセスAの実行が完全に終わってからプロセスBの実行がはじまる、あるいは、プロセスBの実行が完全に終わってからプロセスAの実行がはじまること、それが、プロセスAとプロセスBの相互排除です。 時間の流れが、過去から未来に一方向に流れている様に見えるのですが、世の中には、同時に起きることはたくさんあります。継起するイベントと同時に起きるイベントの数を比較してみてもいいのですが、「同時性」という概念自体、きちんと定義されるわけではありません。 とまれ、同時に走る並行プロセスでプロセスの相互排除を実現しようとすることは、本来同時並行に生起するものを無理やり一列に並ばせるようなものです。もちろん、こうした原理的には困難に思える無理を承知で、可能なアルゴリズムを模索しているのです。 ------------------------------------------- セッションの

 【 「パン屋のアルゴリズム」を図解する 】 このセッションでは、ランポートのアルゴリズムが正しいことを、ランポートの論文に従って示そうと思います。できるだけ図を使おうと思います。 ランポートは、アルゴリズムについての「三つの主張」が正しいことを示すことで、「パン屋のアルゴリズム」の正しさを証明しようとします。 三つの主張で重要なのは、critical section に入れるのは一つのプロセッサーだけだという主張（主張 2）と、レジ待ちのプロセッサーは、いずれ、critical section に入るという主張（主張 3）の二つです。 前者（主張 2）は、排他制御の safety という性質で、後者（主張 3）は、排他制御の liveness という性質です。ただし、この論文では、ランポートは、こうした言葉を使っていません。 アルゴリズム自身が進化・発展するだけでなく。アルゴリズムの記述のスタイル、アルゴリズムの正しさの証明のスタイルも時代と共に変化していることに留意してください。 このセッションで見るアルゴリズムの正しさの証明は、チケット番号全体に対する読み書きが、アトミックに行われる必要はないことを示しています。このbakeryアルゴリズムは、その値がコンカレントに書き込まれたものでないとしても、その読み出しが正しい値を返すならば、正しいのである。書き込みと重なった読み出しがどんな値を返すかは問題ではないのです。 コンカレントな書き込みによって9から10に変わろうとしているある数の読み出しが、2496という値を返したとしても、このアルゴリズムは正しいのです。 bakeryアルゴリズムの、この驚くべき性質は、それがプロセスがチケット番号に相互排除的にアクセスすることを想定していない相互排除のアルゴリズムの実装であることを意味しています。それは、下位のレベルの相互排除を前提としない、相互排除アルゴリズムの最初の実装です。　 1973年当時は、そうしたことは不可能だと考えられていました。1990年になっても、専門家でさえ、それは不可能だと考えていたように見えます。 ------------------------------------------- セッションの動画のURL https://youtu.be/0YdFQGPkyHE?list=PLQIrJ0f9gM

【 これは、やさしいアルゴリズムだ！】 今回は、排他制御のアルゴリズムとして、ランポートの「bakery アルゴリズム」というのを紹介しようと思います。 「bakeryアルゴリズム」は、「パン屋のアルゴリズム」ということです。混雑している人気のパン屋をイメージしましょう。こんな感じです。 ● パン屋の店先には、番号付きの整理券を発行する機械がある。整理券の番号は一つづつ増えていく。 ● お客は、パン屋に入る前に、機械から整理券を受け取る。同時に一人しか整理券を受け取れない。 ● パン屋には、一つのレジしかない。一番小さな番号の整理券を持ったお客から、パンを買うことができる。 パン屋じゃなくても病院でも銀行でも、身の回りの日常で混雑整理の方法として、よくみる風景ですね。 最初に、先行したダイクストラらのアルゴリズムの特徴をおさらいしておきましょう。それは、次のような性質を持っていました。 ● どの時点でも、多くても一つのコンピュータしかcritical sectionに入ることができない。● どのコンピュータも、（途中でマシンが停止しなければ）最終的にはいずれcritical sectionに入ることができる。 ● どのコンピュータも、非critical sectionで停止しても構わない。また、それぞれのコンピュータの処理スピードは問わない。 ランポートのアルゴリズムでは、最後の実際にレジでパンを買うところが、critical sectionに入ることに相当します。ダイクストラらの排他制御アルゴリズムの特徴を、ランポートのbakery アルゴリズムが持つことは、直感的には明らかに思えます。 だって、 　レジでパンを買えるのは、一人だけ。 　整理券を持っていれば、いずれ、パンを買える。 　途中で店を抜けても、時間をかけてゆっくりパンを選んでも構わない。 ですからね。 その上、アルゴリズムはとてもわかりやすいですね。ソースにコメントを入れました。ダイクストラのアルゴリズムでギブアップした人も、ランポートのアルゴリズムのわかりやすさを体験ください。 ただ、アルゴリズムのわかりやすさだけが、ランポートのアルゴリズムのメリットではないのです。実は、ダイクストラらのアルゴリズムには（クヌース、ド・ブルイジンらの「改良版」でも共通に）、実践的には弱点がありました。 それは、N台の

【 あのころみんな若かった 】 ダイクストラは、読者に論文を最後まで読む前に、しばしたちどまって、自分自身で問題を考えてほしいと、問題への挑戦を呼びかけています。 「というのも、そうすることが、それぞれのコンピュータは、同時には一方向のメッセージを要求することしかできないという事実のトリッキーな帰結をしっかりと感じてもらう唯一の方法のように思えるからだ。」 「そして、それのみが、どの程度までこの問題が、トリビアルな問題からは遠い問題であることを、読者に理解させるだろう。」 なかなか挑発的です。ダイクストラは、このアルゴリズムの発見で高揚した気分になっているようにも思えます。今だったら、「論文に、こんなこと書かなくていいから」と指導教員からダメ出しされそうです。 ダイクストラのアルゴリズムというのは、10数行で記述されているとても短いものです。1日、1000行近いコードを生産するプログラマを、僕は何人か知っています。20行足らずのコードなんて、読むのも書くのも簡単だと思われるかもしれません。ただ、そうではありません。 事実、ダイクストラのアルゴリズムは、すぐに多くの人に正確に理解されたわけではないようです。ある日事件が起きます。ダイクストラの論文が掲載されたComm ACM誌の編集部宛に、Hymanという人が、コンピュータが2台の場合、ダイクストラのアルゴリズムをもっと簡単にできるという趣旨の手紙を出し、それが掲載されたのです。ただ、それは、間違ったものでした。 この手紙に最初に反応したのは、クヌースでした。（のちに、ド・ブルイジンも参戦します。） 「Hyman氏の「解法」なるものの反例を見つけるのは簡単である。（氏の12行のプログラムには、ALGOLの文法エラーが15個も含まれているのだが、たとえそれでも、何人かの読者は、彼のプログラムを理解できたかもしれないと、私は信じている。）」 キツイいいかたですね。でも、クヌースのダイクストラのアルゴリズムの理解は正確なものでした。その上、彼は、ダイクストラのアルゴリズムには、いくつか問題があることも指摘しています。さすがクヌース。　 Knuth, Additional Comments on a Problem in Concurrent Programming Control  https://dl.acm.org/do

【 chain rule と convex linear 】 先月もエントロピー論のセミナーをしていたのですが、そこでは、エントロピーの特徴づけでは、"Chain Rule" が一番基本的だという話をしました。 今月もエントロピー論のセミナーをしているのですが、そこは、カテゴリー論でエントロピーを特徴づけるというのがトピックスで、"Entropy as a Functor" という見方が、大事だという話をしています。 月が変わるごとに別の話をしているようで、申しわけないんですが、実は二つの話題はつながっています。 今回は、そのつながりを述べてみたいと思います。 エントロピーのFunctorがConvex Linearという性格を持つことは、エントロピーがChain Ruleで特徴づけられることと、とほぼ同じ意味を持っています。  といっても、残念ながら今回の話は、正面からこの二つが同じものだといっているわけではありません。Functor がconvex linear だというためには、chain rule を知ってないとうまくいかないよという話です。 YouTube : https://youtu.be/9q7OScwC2wM?list=PLQIrJ0f9gMcPcLv9Xw1F4OnNfO1d9lxxh スライドのpdfは、次のページからアクセスできます。 https://drive.google.com/file/d/1klb9qJvCYUxyZ7BsS6TvhLZvEAVuISWi/view?usp=sharing このシリーズのまとめページは、「エントロピー論とカテゴリー論」です。 https://www.marulabo.net/docs/info-entropy5-addendum/ セミナーへのお申し込みは、次からお願いします。 https://ent-cat.peatix.com/view お申し込みお待ちしています。