ビューティフルコード (プ会 2008.4)
久野靖∗

2008.4.16

1

はじめに手元にある「よいプログラム」本2□ 自分の指導教官 (木村□ 自分が学生だったころは「美しくコードを書く」ことを泉先生) が翻訳をしていたことも解説した本って読んで当り前だったと思うんだけど…

結構大きい• 「プログラム書法」「ソフトウェア作法」をはじめ、• これ以外にもこういう関係の本があれば買っていた気がするけど…

沢山…

• bit(共立の雑誌、廃刊になってしまった) にも色々な記事があったけど…

• 今は必ずしも広く知られていないらしい!?
• なんちゃってプログラム書き人口が急増したため!?
• それってまずいんじゃない!?

「プログラミングの心理学」□ 最近、そういうことを考えるきっかけが 2 つほど…

2.1

□ 話題 1:□ ワインバーグ, 木村, 角田, 久野, 白濱訳, プログラミ「ドリトル本」付録「よいプログラムとは」ングの心理学, 毎日コミュニケーションズ, 2005.

• 今回、兼宗さんがドリトル V2 の解説本 (?) を編纂。
• (ドリトル V2 の方がまだリリースできなくて止まっています。この話はあとで本人から)• 古典的名著だけれど今は手に入らないようだ (古本ならある)• その中に「いいプログラムの書き方」の章 (付録) をというリクエストが兼宗さんからあった (なるほど!)• 人間的側面全般を広く扱っている• プログラミングのプロセス、言語などについても載っている• そんなの先人が沢山書いてるでしょと思ったけど、実は知らない人が多いらしい→恐れ多いけど書いてみましょうか2.2□ 今回は→ (A)「昔の本にはこんなのがありました」(B)「こ「プログラム書法」□ カーニハン, プローガー, 木村訳, プログラム書法 第 2

んなことを書いたけどどうでしょう」という話

版, 共立, 1982.

□ 話題 2:「ビューティフルコード」(翻訳)(4 月 23 日発売!)(第 1 版は 1976)□ まさに「よいプログラムを書くための知恵」がぎっしり• 原 著: Oram, Wilson, eds., Beautiful Code:
Leading Programmers Explain How They Think,詰まっている。言語が古いが今でも十分読める。だからO’Reilly, 2007. (Amazon で原著を買うと 4796円。和訳は 3990 円)□ さまざまな「規則」が書かれている。いくつか挙げると…

• 昨年出てすぐ翻訳依頼→ 7 月から作業→ 2 月に脱稿

• 「わかりやすく書こう --- うますぎるプログラムはいけない。」(冒頭にある規則)

現在でも入手可能。

(大変でした)• 「プログラムを上から下へ読めるようにしよう」• 内容: 33 人の著者が「自分が考える美しいコード」についてのエッセイ。すべての章においてコードの一• 「同じ表現の繰り返しは共通関数への呼び出しに変えよう」

部を掲載 (原著の方針)• 今回は→「色々な人が挙げる『美しい』は様々ですね」という話• 「だめなプログラムを修正するのはやめて、全部書き直そう」• 「まずわかりやすい擬似言語で書いて、それから目的の言語に翻訳しよう」• 「速くする前に、まず正しくしよう」∗ 筑波大学大学院経営システム科学専攻

1

2.3

「プログラミング 250 の心得」

• 「実装の詳細を隠蔽しよう」「ユーザに内緒で何かをするな」(インタフェース)□ George Ledin Jr.

& Victor Ledin, 篠 原 訳, プ ロ
グラミング 250 の心得, 多賀出版, 1981.

• 「エラーの検出は低いレベルで、その処理は高いレベ
ルで」(インタフェース)□ これも規則とその説明の山だが、「書法」より実務指向な• 「打つ前に読め」「自分のコードを他人に説明してみよう」(デバッグ)のが面白い。聞いたこともない出版社で知合いの誰も持ってない。珍しい本。

• 「回帰テストを自動化しよう」「テストの網羅範囲を測定しよう」(テスト)• 「ユーザのニーズにプログラムを適合させよ」• 「より優れたアルゴリズムやデータ構造を利用しよう」• 「ユーザの作成した入力データを表示せよ」「関係ない部分を最適化するな」(性能)• 「ループを重視して、これを単位として取り扱え」• 「システム依存のコードは別個のファイルに」「システ• 「同じ重みを持つ命令の頭を揃えよ」←字下げをしろという意味

ム依存部分はインタフェースの裏に隠蔽しよう」(移植性)• 「ジョブ向きの正しい言語を使え」• 「ライブラリ関数を使え」「よいプログラムとは」を書く…

32.4

□ 前提:

「ソフトウェア作法」

ラム」についての) 話を読んでもらい→「なるほど」と思□ カーニハン, プローガー, 木村訳, ソフトウェア作法,共立, 1981.

い実践してもらう (ほんとか?)

この本は Ratfor というヘンな言語で例題• さまざまな言語とか技術的に難しい話とかはできない(教育プログラミング研で喋ったらいろいろ厳しい意が書かれているのに、とても人気があり、今でも大きな書店に行けば並んでいる (!!)

見とダメ出しをもらってしまって…)• この本は「日本で初めてコンピュータ原稿を使って制作された本」であり、それが「木村研の日本語処理シ• 言語はドリトル (ドリトルでよいプログラムの書き方って…?)

ステムの成果」。そのため、制作のお手伝いを久野ほか• →一般的な指針とお話 + 「書き方改良の具体例」

がずっとやっていた (磁気テープ抱えて漢字プリンタ• 構成: 目標→「プログラムの」指針→改良例→「作り方の」指針→評価規準→学び方 (カリキュラム構成)

出力に行ったり先生の赤入れに対応するカタカナファ
イル原稿のエディタ編集をしたり…)→まとめ• 内容は「書法」より上のレベルで、各種題材 (圧縮、文字列置換、整列、パターンマッチ、マクロ展開、文書「プログラムを作るときの目標」

整形、プリプロセサ) について設計してみせながら蘊

3.1

蓄を語る。

□ まず「何を目標とするべきか」を提示したいと思ったの• コードが全部掲載されていて、なぜこう書いてあるかという話も沢山書いてある。

2.5

高校の先生とかに初めてこういう (「よいプログで。具体的には次の 3 つ。
□ 「プログラムがコンピュータ上で動くこと」• 最初は「書法」にならって「分かりやすく」を書いていたのだけれど、それはプロの言うことで、最初はま「プログラミング作法」

ず「動く」から始めないとだめらしい…

□ カーニハン, パイク, 福崎訳, プログラミング作法, アスキー, 2000.

これは言語が C と C++と Java だから現□ 「プログラムが『正しい』(やってほしい) 動作をしてく役。普通に買える。

れること」□ 「書法」「作法」の集大成な感じで、第 1 章「スタイル」• これも言わずもがなだが、Ledin には書いてあった。

からはじまり「アルゴリズムとデータ構造」「設計と実装」

コンパイルエラーが取れて動いたらそれでいいと思っ「インタフェース」「デバッグ」「テスト」「性能」「移植性」ている人もいるから?

「記法」とうまくテーマが選ばれている□ 「プログラムが、人間が読めるように (分かりやすく) 書• 「グローバルにはわかりやすい名前を、ローカルにはかれていること」これが「書法」の冒頭なのでまず言い短い名前を」(書法)

たかったことだけれど、そういうわけで 3 番目になってしまった。

• 「多分岐の判定には else-if を使え」(書法)23.2「よいプログラムの指針」□ 添削前
カメ太=タートル!作る。
「カメ太!100 歩く 144 右回り」!5 繰り返す。
x=カメ太!図形を作る (黄色) 塗る -380 0 移動する。
「カメ太!100 歩く 144 右回り」!5 繰り返す。
y=カメ太!図形を作る (黄色) 塗る -300 60 移動する。
「カメ太!100 歩く 144 右回り」!5 繰り返す。
z=カメ太!図形を作る (黄色) 塗る -220 120 移動する。
カメ太!消える。
ボタン!『動く』作る -380 -180 位置。
ボタン:動作=「
時計=タイマー!作る 1 時間 0.1 間隔。
時計!「x!5 10 移動する。y!5 10 移動する。z!5 10移動する」実行。
時計! 3 時間 0.1 間隔。
時計!「x!10 -5 移動する。y!10 -5 移動する。z!10-5 移動する」実行。
時計! 2 時間 0.1 間隔。
時計!「z! 20 10 移動する」実行。時計!「y! 20 10移動する」実行。時計!「x! 20 10 移動する」実行。
」。

□ 前記 3 目標を達成するようなプログラムの書き方の指針を示し、理由を簡単に解説する• 「素直に分かりやすく書こう」• 「分かりやすい名前をつけよう」• 「むずかしいところはコメントをつけよう」• 「字下げや文字の配置にも気を配ろう」• 「構造を整理しよう」• 「ステップに分けて書こう」• 「同じことは 1 箇所にまとめよう」• 「無理でない範囲で短く簡潔に書こう」□ 多すぎても読んでもらえないので、そこそこの数になるように大切と思うことから選んだ□ ところが「素直に分かりやすく書こう」が理解してもらえない!

「どういのが素直じゃないのか」(悪い例) を質問されるが、悪い例とはトリッキーなので納得しても• どの段階で何をしているのかが分かりにくい。

らえない• 変数名が内容を表していない。

• 前の版: 「奇数か偶数か調べるのに x & 1 はやめて剰余で」• 何回も同じ動作を記述して星を作っている。

• 今 の 版:

• いい加減な位置で行替えしてあるので読みにくい。

• 何回も同じ動作を記述して複数の星を動かしている。

数 値 変 換 に「x-0」整 数 変 換 に「x|0」(JavaScript)• メソッドの範囲が字下げしていないので分かりにくい。

• どっちにせよいまいち…

□ 添削後□ 「無理でない範囲で短く簡潔に書こう」も最初は「短く// 星を 3 つ用意する
カメ太=タートル!作る。
「カメ太!100 歩く 144 右回り」!5 繰り返す。
星 1=カメ太!図形を作る (黄色) 塗る -380 0 移動する。
星 2=星 1!作る 80 60 移動する。
星 3=星 2!作る 80 60 移動する。

しようと頑張りすぎない」だった (それが我々の常識ですよね…)• ところが、短くするのはいいことだという注文がついた• 子供がコードを書くと、動いたものをコピペしてどんどん長く増やしてしまう→ループの代わりに展開され// 星を配列に入れて扱えるようにしておく
星列=配列!(星 1)(星 2)(星 3) 作る。
カメ太!消える。

たものが延々と続く• それをループで整理することは目指させて欲しいという意見でこのように。

3.3// ボタンを用意する
ボタン!『動く』作る -380 -180 位置。
ボタン:動作=「時計=タイマー!作る 1 時間 0.1 間隔。
// 星を 3 つ斜め上に動かす
時計!「星列!「|x|x!5 10 移動する」それぞれ実行」実行。
時計! 3 時間 0.1 間隔。
// 星を 3 つ斜め下に動かす
時計!「星列!「|x|x!10 -5 移動する」それぞれ実行」実行。

「例題: プログラムを添削する」□ 次のような感じで星を 3 つ動かすプログラム// 星を個別に動かす
時計!「星 3! 20 10 移動する」実行。
時計!「星 2! 20 10 移動する」実行。
時計!「星 1! 20 10 移動する」実行。
」。

• どの段階で何をしているのかが分かりにくい。→コメントをつけて、プログラムのそれぞれの場所が何をしているか説明するようにした。

3

• 変数名が内容を表していない。→ 3 つの星を表す変数

3.6

を「星 1」「星 2」「星 3」とした。

□ 我々が「一般の人でもこういうことを知っておいてくれ• 何回も同じ動作を記述して星を作っている。→最初の星を作ったら、あと 2 つの星はそれを「作る」でコピーたら我々はずっと楽なんだけど/日本はずっとよくなるんだけど」と思うことして作るようにした。

• 「決まった手順に沿った厳密な実行」• 何回も同じ動作を記述して複数の星を動かしている。
→ 3 つの星を「星列」という配列に入れておき、3 つ• 「高速だが融通の効かないコンピュータ」

を一緒に動かす時は配列の「それぞれ実行」を使うよ• 「考えることの大切さ」

うにした。

• 「人間は間違える」• いい加減な位置で行替えしてあるので読みにくい。→
行が長くて行替えするときは命令の切れ目などきりの• 「変数と値の書き換え」「制御構造 (繰り返し、枝分かれ)」「アルゴリズムの考え方」

いいところで行替えするようにしている。

• 「構造と設計の考え方」• メソッドの範囲が字下げしていないので分かりにく• 「『注文』を満たすことの大切さ」

い。→メソッドの内側は字下げして範囲が分かるよう• 「製品と実験用模型の違い」←難しいか?にした。

3.4「プログラミング学習で学んで欲しいこと」• 「プログラムの活躍している場所」「うまくプログラムを作るための指針」

3.7□ こちらは「プロセス」の指針ということで (こういうこと「プログラミングの学び方」□ 自分が「この順番で学ぶのがいいと思う」おすすめのカもたぶんあまり知られていないかも)リキュラム進行も書いてみた。

• 計画を立てよう ←「いきなり打ち始めるな!」• 「『決まった書き方』があることを学ぶ• 少しずつ動作を確認しながら作ろう ←一気に作って• 「決まった順序で実行されることを学ぶ」

破滅な人が多い• 「同じことをいく通りにも書けることを学ぶ」• 系統的にテストしよう ←言うのは簡単だけど…

• 「自分が考えたことを書き表すことを学ぶ」• 先に進む前に整理しよう ←リファクタリング?

• 「少しずつ確認しながら組み立てることを学ぶ」• 間違いが分からなくなったら ←切り分け、他人に説• 「計画を立てて組み合わせて行くことの重要性を学ぶ」

明、print デバグ• 「コンピュータとは結局何なのかを学ぶ」←おまけ

3.5「プログラムを評価する基準」

3.8□ 教育現場では「点数つけ」が不可欠だからというので入れまとめると…

□ 結局自分が言いたいことは「わかりやすく書け」だけれど…

たけど…普通のソフト開発ではないことなので苦労した□ それだけでは分かってもらえないから色々回り道したと• 「プログラムが『課題』の条件を守っていること」←

いうか…

注文ではなく課題がいいそうで。

• 「プログラムが『ちゃんと動く』こと」←エラーがあって動かなかったり途中で死んだりするものも提出され4てくるから…

「ビューティフルコード」翻訳□ この本の特徴 (冒頭で挙げた「美しいプログラム」本との• 「プログラムの性能」←課題の充足に＋αすること…
使いやすさ、みばえ、たのしさ、オリジナル性、工夫、違い) → 33 人の著者がバラバラに言いたいことを言って(速さ←速さを見やすさと引替えにしないこと)いる• 「プログラムの美しさ」←何が美しいかという定義は• 見事にバラバラで、意表を衝いて面白いものが沢山ある

困難なのでお茶を濁させていただいて…

• カーニハンの (1 章) とかは、ある意味予想通りだなーという感じ• ウォーレン Jr. の (10 章) とかは、Hacker’s Delight
中のネタの再利用

4• ベントレーの (3 章) は quicksort だが意表を衝いて• しかしこの章、もっと色々語ってくれるのかと思った「整列しないで計算量を測る」でコードを動かさないらあっという間に終わってしまう感じ…(「作法」「書ので確かに新しいけど…

法」に慣らされているから食い足りない)• 久野個人が面白いのはやっぱりプログラムを動かす話で、しかも読んだことがないようなもの (贅沢)(まあ4.2全部訳したわけだし…)□ 自分の好きな並列/並行の話…Haskell STM の売り込み□ 結局、各章は読む人によって面白いものもワケワカなも• 内容については略 (面白いけど、木戸さんもいるし…)のもバラバラだろうと思う• 章 の 題 名 に つ い て 。原 著 は「Beautiful• だからある意味、この本の面白いところはその「バラConcurrency」 。も と も と は「 並 行 は キ タ ナ イ けど、Haskell STM ならこんなに美しいよ」というつバラさ」• 手慣れた著者はさらっと書いて終わるが、著者によっては「これが大切なんだ!」とか力が入っている→そもりらしい→「並行性を美しく書く」が適切な訳?

• 自分としては「普通の並行性はキタナイ」はやめてほの力の入っているポイントが本当に章ごとにまったくしいし、宣伝ぽくない方がいいでしょ→奥さんの案を違うのが面白い→読んで頂くのが一番頂いた。「並列って楽しいよね」という意味になるの• とはいえ、せっかくの機会なので、いくつか久野個人が面白かった章について紹介させてください。

も嬉しい。

4.3
4.1

24 章「美しきかな、並列」

32 章「働くコード」□ まさに「よいコードの書き方」の話題なので…

30 章「世界につながる手段がボタンだけだったら」□ 掲載コードはめちゃくしゃしょぼい (言い訳も書いてある)□ しかし記述されているユーザインタフェースはすごく頑• この章もセイワルド (著者の 1 人) の「整った (プリ張っている。

ティ) コードの 7 か条」がネタとなっている (が、それほど有名でもないと思うので…)• 「ホーキング博士のためのインタフェース」→指 1 本• 「『本のよう』であること」「似たものは似て見えるよで編集や任意のコマンドの起動ができる (実際はホーうにすること」「字下げを克服すること」「コードをもキング博士は使い慣れたソフトから移行してないそう

つれさせないこと」「ごちゃごちゃにしないこと」「既だけど)存のスタイルにとけこむこと」• 階層メニュー。各メニューが一定時間間隔で循環ハイライト、ハイライトされたときにクリックすると選択• しかしちょっと異論もあったりする…訳者が訳注で喧嘩を売るというわけにはいかないのでここで。

できる (上に戻るには戻るという項目を選ぶ)• これで効率良くするため徹底して学習する (入力した単語とか文例とか全部 20 個保存しておいて LRU で更新)

□ 「本のようであること」→幅狭く書けということ (じゃあ縦に伸びるのはいいのか?)• そのために使う「1 行挿入すると最も古い行が捨てら×れる」プログラムが掲載されている (! あと 2 つ掲
if( bf->end == bf->Lines() && lf1->end == lf1->Lines() &&載されているが似たりよったり)
lf2->end == lf2->Lines() ) return( DD_EOF );○if( bf->end == bf->Lines() &&4.4 6 章「フレームワーク設計の挑戦」
lf1->end == lf1->Lines() &&lf2->end == lf2->Lines() )□ FITって知ってます? FITってこういうものだったのか、return( DD_EOF );という勉強になる。しかし FIT の話題ではない。

□ 自分では行を長くしてでも行数を減らす方なのでどうも…

• 普通のフレームワークは中身を隠蔽してユーザが実装に依存しないように気をつける→常識□ 賛同できることももちろんある。

• しかし FIT ではずっと「あけっぱなし」で「いくらで• 「入れ子を字下するのは当然だけど、それでコードがもいじっていい」→カルチャーショック!

読みやすくなるわけではない (字下げを深くしないのがベスト」• このようなカルチャーの選択肢があり得ることと、それを可能にしている要因が説明されている→なるほどね• 「カラフルな表示でなくても読めるコードであるべき〜(gdb とかが表示するときは色なんかついてないから)」5

4.5

33 章「『本』のためにプログラムを書く」

5.1

スレッド/ロック/優先度継承□ スレッドは同期/排他制御のため同期オブジェクト (ロッ□ 最後の章だし期待したのだけどなんか肩すかしというか…

ク) を獲得• 問題: 「3 点 (px,py)(qx,qy)(rx,ry) が一直線上にあるか否か?」

スレッド• 3 点のうち 2 点から直線の式 Y=AX+B を求め、残る 1点がこれを満たすか調べると… 直線が Y 軸に並行だ

owner

同期オブジェクト（ロック）取得と傾き A を求めるとき困るので…(以下延々とさまざまな案が出ては否定されて進んで行く)□ 取ろうとしたロックを他人が取っていると待つ必要がある→連鎖• あなたならどうしますか?
□ 自分ではこういう問題は (ICPC などで) やらされるので:• 「2 つの直線の傾きが等しい」(qy-py)(ry-py)------- == -----(qx-px)(rx-px)□ スレッドには優先度がある→高いものが先に実行→ロッ
クで待っている高優先度のスレッドが待たされてしまう• このままでは 0 割りになるから分母を掛けて(優先度逆転)(qy-py)*(rx-px) == (ry-py)*(qx-px)• こうすれば大丈夫、という訳注を書いて、最後の方ま8で読んで行ったら実はこれが「究極の解」として書か８なのに待たされるれているのであわてて削除した

×5○
優先度の高い方が実行• さらにこの著者 (ブライアン・ヘイズ) は大した意味もなくコードをすべて Lisp で書いていて、Lisp コー□ 待ちに入るスレッドの優先度がロックを持っているスレッ

ドの読み方をわざわざ説明している… その例題は再ドの優先度より高い場合、その高い優先度を「一時的に帰 GCD(もちろん他のコードには再帰なんて出てこな(ロックを持っている間)」伝播い)。どうなんでしょうね?

対象読者が易しめ?
85322 838

優先度を伝播

22 章「スプーン一杯の汚水で」

8□ 題名の由来は…

優先度を伝播

樽いっぱいの汚水にスプーン一杯のワインを注ぐと、樽いっぱいの汚水になる。
樽いっぱいのワインにスプーン一杯の汚水を注ぐと、樽いっぱいの汚水になる。
(ショーペンハウエルのエントロピーの法則)

5.2• そのココロは… ソフトは 1 箇所でもバグがあったら台○

2 85×
優先度の高い方が実行
35×○×
ロックを解放したらロック手渡し 優先度を戻す

連鎖の整合性管理□ 複数 CPU による本物の並列実行→優先度を上昇させよう無し (ソフトの種類によるけど、OS の同期プリミティとした瞬間にスレッドがロックを解放すると→間違ったブだと…)優先度に→厳密な整合性の管理が不可欠!

• Solaris 8 (Sun の商用 Unix) のリリース直前に発現したバグ→ OS がパニック (緊急停止) で止まる→必死

8で直したら→ OS がいきなりハングする→真っ青、と

2 8

83上昇させようとした
瞬間にロック解放8間違った優先度！

優先度を伝播いうお話• 自分には最高に面白かったがこれが楽しめる読者はど

8

れくらいいるのか… (今回は結構いそうなので取り上

2 8優先度を伝播げます)□ スレッド自体にロックを掛けて整合性を管理。ではブロッキングチェーン全体に渡ってロックを掛けるかというと…

6

• ユーザレベル優先度継承を (カーネルレベルと同じよ3286うにして) やろうとしたときに、優先度継承ロックをガードするカーネルレベルのロックを介したループができていて、それを検出してパニック□ それは駄目。スレッドロックは実際は「ロック構造へのポ□ 通常、カーネルはユーザレベルのデータ構造は「信用しインタ」であり、ロック構造はいくつかのものは共有されない」のだが、優先度継承処理については厳密に状態をている→ 2 つ目をロックしようとするとデッドロックに追跡する必要→ここに問題の根源• カーネル内の偽デッドロック→パニックで停止！！
32

8• ユーザレベルでの偽デッドロック→エラーで返る→エ
ラーコードを見ないアプリでは取れていないロックを6取れたと思って進行→データを壊してしまう• カーネル内ロックを使わないで済ませようと努力したがこれは無理そうだと分かる• なせこうなっているかというと、ロックを使う度にメモリ管理では遅くて駄目なので、ロック+キューの配• 問題の状態を検出して何とかするしかない…

列を用意し、ハッシュによりその配列のどのエントリを使うかを決定する (ハッシュが衝突した場合は同じ5.4エントリになる)

解決策□ ケース 1:

優先度継承を処理していって、自分に戻って来てしまったが、自分が持っているのが最初に処理を始□ 実際にはブロック連鎖の「巻き戻り」は右端 (先端側) でめたカーネルロック (変数 mp) である場合しか起こらないので「常に 2 つロックを取っている状態」
で進んで行けば左側 (根元側) のロックは解放してしまってよい

8u

kmp

• ぐるっと 1 周して優先度継承処理を終えたので、これで止めてよい。処理が終わったら自分が mp を解放するのでサイクルではなくなる。

• その 2 つのロックが同じな場合はチェックしてすぐ対□ ケース 2:

処可能

• さらに AB/BA デッドロックを防ぐため、取る時は「アドレスの若い順に」取る (このため、原著には書いてないが 3 つずつ押えて行く?)

8k5.3

優先度継承を処理していって、カーネルロックからユーザレベルロックに渡った場合

kuu

問題• カーネルからユーザに渡る (カーネルコードがユーザ□ 前記の点はカーネルの優先度継承。しかし今日ではユーコードを待つ) というのはユーザレベルロックの優先ザレベルでも複数スレッド間同期を行うため、ユーザレ度継承処理でしかあり得ない (これ以前には一切ありベルスレッド間でも優先度継承を行う必要→リリース予得なかった) 状況。これは現在誰か他の人が必死で優定の Solaris 8 に組み込む (1999.10) →バグが見つかり先度を調整しつつある過渡的な状況→しばらく待って検死ダンプを読んでいた (1999.12)
B

5

A

8

ユーザレベル優先度継承ロックをガードするカーネル内ロック

やり直せばなくなっているはず
Ａはロックを手渡されてこれから起きるところ

5.5

ユーザレベル優先度継承ロック

問題 B□ しかし、これを直して負荷テストを行うと…こんどはカーネルがいきなりハングするという症状が…

7

→ ユーザレベルロックのエントリが入るハッシュ表だけ• turnstile block() → mutex vector exit() →分離して低いアドレスに置く (これでアドレス順の獲得にturnstile block() という系列の中。

なり AB/BA デッドロクも防げる)• つまり、ユーザレベル優先度継承ロックの「獲得時」と「解放時」それぞれについて、カーネルロックの獲得

ユーザレベルロック専用と解放が必要だった (データ構造をガードするため)、その前者において…

wchanhwchanh• 優先度継承を処理する→カーネルロック解放のため、データ構造をすべて切り替える→ロックを解放して一般のハッシュ表• あまりにも特定問題向けの解決策ではないかという疑swtch()

念はあったが、これしかなかった。数年たってもここ• しかしその間にそのロックで待ちに入ったスレッドがあると、それを起こす必要があるため、そのスレッドからバグが出ず、これより良い解法も考案されていな
い→これこそ「ビューティフルコード」!!

ロックを獲得。加えて、継承した優先度を放棄するためカレントスレッドのロックも獲得。

• カレントスレッドのロックは既に待とうとしているユー

6

ザレベルロックをガードする (ハッシュ表中の) ロックまとめ□ 「ビューティフルコード」のまとめになっている。
cpu_t

cpu_t

user-level
lock guard

ハッシュ表中で同じものになってる→ハング• 22 章のような手に汗握る話は大好きだけど、しかしこれを楽しめるのには相当な経験が必要なんじゃないだ
ろうか…

スレッドをロック寝ようとする• まあこれだけ難しいのもあるというところが本書の幅広さなのかも。

起こす必要• ずっと易しい章とか、ソフトウェア工学ぽい章なんか

このロックで待つ人もあるので、これはこれでいいのかなと思う。

解放する• 皆様もぜひご一読を。

ハッシュ表wchanhwchanh□ 本日全体のまとめ• 「美しいコード」の話に何を求めるかは、人によって全然違っている。

• カーネルロックとユーザレベルロックのハッシュ値が• 「美しいコード」の話は楽しい。

同じだと、同じロックを 2 回取ろうとしてデッドロッ
ク (実際に起こったこと)• 同じでなかったとしても、アドレス順によって AB/BAデッドロックの可能性□ 基本的な問題は「ほぼ待ち状態に入った後でカーネルロックを解放する」という非常に困難な問題• 待ち状態に変更する前に優先度を戻せないか? ::それでは優先度逆転の穴が発生• turnstile block() → mutex vector exit() →turnstile block() という系列を検出できないか?
:: 複数スレッドによる AB/BA デッドロックに対応

注: この資料は 2008 年 4 月 16 日に開催された「プログラミング・情報教育研究会」の資料です。本資料に言及されている「ドリトル本」は 2007 年 9 月にイーテキストから「ドリトルで学ぶプログラミング-グラフィックス、音楽、ネットワーク、ロボット制御」として刊行されましたが、本資料で言及している「よいプログラムを書く」の部分は兼宗先生が大幅改訂して、ここで述べられているものとは別内容になっています。

できない• うーん…

5.6

解決策 B

注: 本資料の内容はコピー、抜粋、要約を含め、自由に利用されて構いません。ただし出典を明示してください。

□ 要するに、ユーザレベルロックのエントリと他のロックのエントリがたまたま同じハッシュ値になるからいけない8