Towards Transparent CPU Scheduling by Joseph T. Meehean
マルチプロセサのスケジューラを扱った博士論文をオンラインで読んだ。
https://research.cs.wisc.edu/adsl/Publications/meehean-thesis11.pdf
OSTEP の第十章の文献リストにあったことに興味を惹かれて、序章を読んだ。全体を読むにはいたっていないが、いつか読むだろうという気がする。皮算用になろうとここに掲げておく。
プロセサの速度が 2003 年にピークを迎えたあと、ハードウェアの関心はプロセサの数を増やすことに向かった。アプリケーションが並列化したのと同様に、 CPU スケジューラも並列化することになった。このときアプリケーションが依存するスケジューラの方針は、必ずしも明らかでないという。既存の文献はシングルプロセッサ時代の知識へと偏る傾向があって、ユーザーも開発者も研究者も、低レイヤのスケジューラにまつわる理解は一様に低い状態にあるのだそうだ。
論文は Linux のもつ 3 つのスケジューラ、 O(1) Scheduler と CFS (Completely Fair Scheduler) と BFS (Brain Fuck Scheduler) について、長所と短所のサマリを提出しているようだ。
大雑把に分類すると、 O(1) と CFS は分散キューを使ういっぽう、 BFS はグローバルキューを使う。
O(1) は Multi-Level Feedback Queue に似た優先度ベースのロジックで、キャッシュとの親和性を強く打ち出す。 CFS はその名のとおり公平性を尊重して、キャッシュの最適化は捨象してランダムにプロセサを割り当てる。 BFS は CFS よりもいっそう公平性を高めているが、キャッシュとの親和性はいちじるしく低い。
Multi-Level Feedback Queue
OSTEP の第8章で Multi-Level Feedback Queue の理念と動作原理について読んだ。
OS のスケジューリング問題へのアプローチとして1962年に考案されたアルゴリズムである。日本語だと「多段フィードバックキュー」が定訳らしいと wikipedia で知った。
ターンアラウンドタイムとレスポンスタイムというふたつのメトリクスを最適化の対象として意識する。それぞれの定義はこうなる。
- ターンアラウンドタイム: ジョブが到着してからジョブが完了するまでの時間
- レスポンスタイム: ジョブが到着してからジョブが最初にスケジュールされるまでの時間
Shortest Jobs First アルゴリズムは、ターンアラウンドタイムをよくするがレスポンスタイムを悪くする。 Round Robin アルゴリズムはその逆に、レスポンスタイムをよくするがターンアラウンドタイムを悪くする。
Multi-Level Feedback Queue とは、それぞれ異なる優先度をもった複数のキューのあいだをジョブに行き来させながら、ふたつのメトリクスを最適化するよううながすものである。任意のジョブがどのくらいの実行時間を持つかはわからないにせよ、ジョブを実行しながら最善の予測をおこなって最適化しようとするアルゴリズムである。
Multi-Level Feedback Queue の仕組みは次の五つのルールに還元される。
- 優先度の高いキューからジョブを実行する。
- 優先度の等しいキューのジョブは Round Robin で実行する。
- 新しいジョブは常に優先度のもっとも高いキューにおかれる。
- キューごとに定義された一定の割り当て時間を使い切ると、そのジョブは優先度のひとつ低いキューに移動する。
- 一定の時間ごとにすべてのジョブを優先度のもっとも高いキューに移動する。
一般に、 CPU を短く使うジョブは優先度が高く処理されて、素早く終わる。対して CPU を長く使うジョブは優先度の低いキューに到達して、優先度の高いジョブを邪魔しない。 I/O が絡むジョブは、優先度の高いキューにとどまる傾向がありながら、 4. のルールに従って公平に割り当てられる。
5. のルールがうまくできている。これは優先度の高いジョブが大量におかれたときに、優先度の低いジョブがいつまでも CPU を割り当ててもらえない (starvation) という問題を解いている。レスポンスタイムの公平性を守りながら、ターンアラウンドタイムの素早さも守っている。
仕組みとしてはこれに勝るものなしとおもわれるが、難しさはパラメータのチューニングという形でやってくる。すなわち...
- 優先度の異なるキューをいくつ用意するか
- キューごとの Round Robin のタイムスロットはどれくらいか
- キューごとの優先度を下げるまでの割り当て時間はどれくらいか
- すべてのジョブの優先度を最高にする頻度はどれくらいか
これらが一般化できない問題として残される。もっとも、それ以外の問題は一般化できるという意味でもある。
おもうに、特殊な事象を一般化するのはマクロな科学の産物で、パラメータをチューニングするのはミクロな工学の関心である。
すべてを巨視的に還元するでもなく、すべてを微視的に解消するでもない。工学と科学が重なりあった主題に触れて、おもしろくおもった。
『スター・ウォーズ 帝国の逆襲』
スター・ウォーズの第二作を観た。アーヴィン・カーシュナーが監督をしていて、ジョージ・ルーカスは製作にまわっている。
ルーク・スカイウォーカーは相変わらず英雄然としていない。むしろたいした負け犬で、しかもオビ＝ワンとヨーダの忠告に逆らって負けに突き進む姿はほとんどアナキン・スカイウォーカーと変わらない。ふたりの関係を考えるとそれは自然であるのだけれど、アナキンは転んでルークは転ばないというのがいくぶんご都合主義にみえもする。アナキンに肩入れしたくなる判官贔屓なのかもしれないが...。
もっとも、ルークの脆弱さはそれだけにとどまらない。冒頭からして注意力散漫から雪男につかまって、ハンともども極寒の惑星で一夜を明かす危機に招き入れるし、出会ったばかりのヨーダを取るに足らない妖怪とあしらって性急さを咎められたり、あまつさえフォースへの信念を欠いて修行を諦める素振りさえみせる。新三部作でアナキンがみせた才能と実力のきらめきに比べると、主役の格が落ちているようにもおもわれる。
たいして、ハン・ソロの存在感は変わらず光っていた。リーダーぶることは一切しようとしないけれど天性のリーダーの資質をもって冒険をひっぱる姿がいちいち格好いい。野性味を出してレイア姫にくちづけしたかとおもうと、チューバッカと一緒にミレニアム・ファルコンの修理に奔走する理系っぽさも持っている。そして最後には、カーボンフリーザーの餌食になるが、その直前でレイア姫の愛の告白を "I know." とキザに受け入れるやりかたも、一匹狼キャラが一貫している。
なんの希望も残さずに幕引きになるときに、勇壮なテーマ曲が流れてもあまりいい後味にはならない。だいたい、ルークがヴェイダーに大敗を喫したうえ、ソロを賞金稼ぎの手に落としているのである。これからそれを奪還しにいくと最後にぽろりと垣間みせたところで、空虚な気持ちは変わらないのに、レイア姫が嬉しそうに笑っているのはどうかしているとおもう。悲壮な結末は悲壮な演技で閉じてもよかったのではないか。そのあたりが、娯楽映画の第二作というスケールに収まっていて、いくぶん物足りなくもある。
『スター・ウォーズ 新たなる希望』
ジョージ・ルーカスによる SF サーガの第一作をみた。
子供の頃にテレビ放送を録画して繰り返し観ていたのは『ジェダイの帰還』とたまに『帝国の逆襲』だった。『新たなる希望』は案外みたことがなかったかもしれない。筋書きをよく知っているつもりでいて、懐かしく観返すような気分でいながら、実はディテールの記憶はほとんどなかった。
ルーク・スカイウォーカーはまだ未熟な段階にあるようで、主人公らしい存在感を終始発揮しているというのではなく、むしろ感情的な脆弱さを周囲に支えられながらなんとか自立しているという風だった。オビ＝ワンやハン・ソロは、彼を補佐する役割という以上の存在感を画面に与えていた。
とはいえ、終盤にデス・スター破壊作戦をめぐってルークたちが繰り広げるドッグファイトは、『トップガン マーヴェリック』を踏まえてみても充実していた。ライトセイバーでの殺陣がいくらか激しい動きに欠けているようなところを、戦闘機の攻防が補って奇想天外な SF に戦争もののリアリティを備わらせていた。
『フェイブルマンズ』
スティーブン・スピルバーグの新作を劇場に観に行った。脚本にトニー・クシュナーが参加している作品を観たのははじめてになる。
ある映画好きの少年が青年に成長するまでを描いている。これは監督による自伝にあたると宣伝されているのだけれど、観てみたところでどうみても虚構の作品であって、自伝であることがなににどう作用しているのかはまったくピンとこなかった。映画少年の個人的な物語が、すこし陳腐といってもいいやりかたで描かれている。もっとも、陳腐であることは不出来であることを意味しない。ティーンエイジャーとして誰もが思い悩むように、家族との関係のぎこちなさと学校での居心地の悪さ、かけがえのない友人との関係、働き始めることの苦しさと高揚感を等身大に描いている。
とはいえ、はじめて観にいった映画で鉄道と自動車が大クラッシュすることに執着をおぼえて、みずからそれをフィルムに捉えなおそうとする逸話は、あきらかに監督自身の特異な執着にオーバーラップする。いってしまえば主人公のサム・フェイブルマンと監督のスティーブン・スピルバーグをつなぐ糸はそれだけであるのだが、そうして自伝的な伝記映画であることを示唆してしまうことで、いくぶん尊大さも紛れ込んでいるようにおもう。ボリスおじさんがサム少年をつかまえて「おまえは芸術に奉仕する宿命を持っているのだ」といい、サム少年がそれに怯えてみせるシーンは、他の映画であれば特に引っかかりもなく観ることができただろうが、こと自伝を示唆してしまったことによって、うぬぼれていないようにみせようとするうぬぼれが生じていないか。いくぶんわざとらしい仕草にみえた。
父親が IBM に雇用されるというので、親友のベニーとアリゾナで別れてロサンゼルスに越してから先は、フェイブルマン一家から焦点がすこし離れて、サムを中心にしたハイスクールの人間関係が描かれる。スクールカーストの上位にいる男子学生からは反ユダヤ主義のおおいにこもったいじめを受けて、そのいっぽうではそれを痛ましくおもうようにしてすこし変わった女子学生とのロマンスも描かれる。
いじめっ子のローゲンが、サムの撮った映画をみて奇妙な感情の爆発をみせる筋書きは卓越していた。その映画はローゲンを、ギリシャの英雄さながら完璧な肉体と完璧な色気をまとった姿で映し出している。サムからしてみれば、自分をいじめた相手を偶像化しているようで、これは観客にもピンとこない仕草である。特にその制作過程での葛藤が示されることはないから、どうしてサムがそういう映画を作ったのかは、ローゲンがふたりきりの廊下でサムに激しく抗議するまで明らかでない。サムの答弁はいくらか凡庸だから注目する必要はないが、完璧な姿を映し出されたローゲンが、そのことに激怒するという心理こそおもしろい。なにか一般的な真実を描こうとしているのではなく、ただ彼個人の容易でない機微が表現されることによって、単なるいじめっ子の端役であったローゲンが一転して、魂をもった人間として再登場するということに、制作の不思議な采配を感じた。そのことがなにを意味していたのかはわからないが。
最後の最後に3分間だけ登場して、言葉少なだったかとおもうと一気に大声をあげて、金言めいているようでナンセンスのようでもある助言を叫ぶジョン・フォードがすぐれてよかった。いかにもアメリカの巨匠がいいそうなセリフに、デビッド・リンチが演技によってますます存在感を与えている。意味がないけど偉そうなことを端的にいわせるには最良の人選がリンチであった。登場することを予期しない配役であっただけに、いっそうたのしい気分で映画は終わった。
『隠し砦の三悪人』
黒澤明の『隠し砦の三悪人』を観た。1950年代の黒澤作品はこれが最後で、1960年の『悪い奴ほどよく眠る』の前作になる。
これは『スター・ウォーズ』を観る前に、見比べてたのしむことができるよう選んだ。はじめての鑑賞ではないけれど、おもしろく観た。キャラクターの造形ははっきりと立ちながら、文芸的な追求を目的としない軽やかさから、娯楽映画としてたのしく鑑賞した。
国立映画アーカイブの『脚本家 黒澤明』で、この映画の脚本が四人の共同執筆であることを知った。菊島隆三、小国英雄、橋本忍、そして黒澤が静岡の旅館にこもって、即興的な執筆と推敲のプロセスを踏んだということらしい。その草稿と、推敲プロセスを電子的に表現した展示が展覧会では公開されたようだ。
作品の外側での逸話をさておいても、この映画は独特なたたずまいをもっている。最初のカットは、ふたりの百姓が荒野をさまよう様子を、背中から撮る。そして彼らのユーモラスな罵り合いをみせる。どこか演劇的な立ち上がりである。
アクションにも充実している。六郎太が両手で刀を握ったまま手放しで馬を疾走させる躍動感のように派手なショットもあるし、ふたりの百姓が険しい岩山をぜいぜい言いながら登るところも、運動の過酷さがありありと出ている。終盤のターニングポイントとなる火祭りの描写は、激しく燃え上がる炎を中心にして大所帯が踊り狂って乱れる様子が収められていて、ダイナミックなことこのうえない。
田所兵衛は端役のようにしてあらわれて、最後にもういちど見どころを持つ。「ひとの命は火と燃やせ」「よし、燃やすか！」「裏切り御免！」というモノローグは、彼一人の心情のうつろいを言い当てていて、爽やかな後味を残す。
日本対メキシコ
前の晩の三時近くに寝ようとして、翌朝に WBC の準決勝があると気づいた。見逃しはすまいと、朝八時に目覚まし時計をセットして、春分の日に早起きして観戦した。
メキシコ先発のサンドバル投手は、初球のストライクがおおくてテンポよく、四球をほとんど出さなかった。チャンスはおおくなかった。日本の先発の佐々木投手も好投していたが、凡打性のヒットがふたつ続いたあとの、高くはいったフォークを本塁打にされて三点のビハインドを与えられた。
サンドバル投手が降りてからの日本代表は、チャンスメイクはするものの無得点のまま残塁を積み重ねていた。メキシコ代表が少ないチャンスを効率的に活かしたことと対比して、日本チームが劣勢であることは明らかなようにおもわれた。七回裏に吉田選手が同点ホームランを打ったところで一安心して、九段下に出かけたが、準備をして駅に向かうあいだにメキシコが勝ち越し点を取っていた。運を味方につけられずにいて、これはもうだめかもしれないなとみえていた。
高田馬場で西武新宿線から東西線に乗り換えるころから、ふたたびストリーミングでライブ観戦した。一点のビハインドで九回裏の攻撃だった。メキシコチームのクローザーに、カージナルスでリリーフを努めるガジェゴス投手。先頭の大谷選手が初球打ちで右中間をやぶって、一塁手前にヘルメットを捨てながら全力疾走をした。二塁ベース上で繰り返し両手を振ってダッグアウトを鼓舞していた。無死の走者。同点は引き寄せられたと感じた。続けて吉田選手は四球。サヨナラのピンチランナーに周東選手が送られて、最後には村上選手が三球目をセンターオーバーの二塁打にした。
サヨナラの瞬間は、九段下駅に迎えに来てくれた友人と落ち合って、静かな路地を歩いているときにおとずれた。打球が抜けた瞬間、やったあ！ と大声をもらしてしまった。一打で逆転サヨナラというシナリオにこれだけ興奮したことに、夏の甲子園で金足農業が近江高校に逆転スクイズを決めたときのことを思い出した。しかし今度はアマチュア大会ではなく、プロ選手による国際大会でそれが起こった。スケールのおおきな筋書きだとおもった。
松井がヤンキースに移籍した年にはじめてアメリカをおとずれた。リーグ優勝決定シリーズの直前で、ボストンとニューヨークのキャップを買ってもらって、それぞれの街でかぶらせてもらった記憶がある。その松井がスラッガーでなくクラッチヒッターとして記憶される選手になったことが、メジャーリーグの底知れなさを子供心に印象付けたようにおもう。そのメジャーリーグの選手たちに日本リーグの選手たちが渡り合って、印象深い試合をつくりあげた。そのことが、二十年をへだてて印象をうわ書いた。
