2009年11月25日水曜日

Lions' Commentary (7) - closeとunlink -

I/Oバッファから、i-node関連の処理、あるいはファイルデスクリプタの実体操作、ファイル処理などの関数に取りかかってきました。パイプ用の処理が分岐で書かれているのがちょっと気になります。キャラクタでバイスやブロックデバイスはそれぞれの特殊処理はドライバ側あるいはその上位層で処理しているのですが、パイプだけは各処理の中で直接分岐して書かれています。この頃アドホックにインプリされた物が後継版で整理されていくのでしょうか。。。名前付きパイプなんて出てくる頃には綺麗に書き直されている気がしますね。System IIIで実装済みなのは知ってるので、どんな実装か確認しようと思えばできるのですが、ちょっと後回しかな。しかし、正確に発明されたタイミングはどの時点だろう?

あと、UNIXでは伝統的な挙動、ファイルは消しても誰かがオープンしている間は実体が消えない、というやつ。自分は大学の先輩(mick'n)から教えてもらった気がする。これもcloseのsystem callを追いかけていると見つかります。fork時に実体の参照カウントはインクリメントされるので、close時に参照カウンタが1の時のみファイルデスクリプタの実体を閉じます。んで、この時にi-nodeのlink数を調べて0以下だったらtruncateしてi-nodeを解放する、つまり実体を削除する、という処理になっていました。

Lionsを読むと、このあたりの実装はテンポラリファイルの運用を簡便にするための物のようですね。プロセス生存中はpidがシステムでユニークである事をOSが保証しているので、そのpidを交えた名前はプロセス内で衝突しない限りはシステムでユニーク。で、プロセス内では生成直後にunlinkしちゃえば、他からは触れないし、上書きされる心配もない。で、使い終わったら明示的にcloseすれば削除されるし、segvで落ちちゃった場合なんかでもOSがプロセスの解放処理をする際に全ファイルをcloseしてくれるので自然に実体も削除されるという。simple is bestな実にUNIXらしい考え方です。

2009年11月20日金曜日

Lions' Commentary (6) - I/Oバッファ -

書籍のAmazonへのリンクの出し方がわかったので入れてみました。

Lionsのほうはドライバの構造から入って参考にRKのドライバ周りを一通り読みました。
複数のドライブを1つの大容量ドライブに見せる仕掛けとか入ってました。

Bach本ではバッファキャッシュの話が最初にあって、読んでいて「あぁ、文明の光・・・」って感じでした。6版の場合、複雑に作ってもむしろ性能が落ちるような規模のシステムなので、リソース管理は非常にシンプル。一方でこちらはいきなり複数の双方向リンクでバッファを管理するような話で、いっきに近代化された印象を受けます。

が・・・Lions本で先に進むとdmr/bio.c つまり バッファ周りのソース。ここがまさにバッファキャッシュになっていて、Bach本とほぼ同じ構造で管理してました。違うのはハッシュを使ってるかどうかってところくらい。高々15エントリなんですが、LRUで置き換える事を考えるとやっぱり真面目にリストで管理するしかないですかね。

という感じで、わりと相補的に読めます、この2冊。
実際、Bach本で読んでスルーしてた循環リスト構造、Lions本でincore()を読んでいて、なんでこのループで正しく処理できるんだ・・・みたいにハマってしまって、再びBach本を見てみたら図解で細かく説明されていたという。。。


2009年11月15日日曜日

The Unix I/O System

Lions' Commentary 15章末尾に参考文献としてあげられているにも関わらず、ネット上で探すのに苦戦。Dennis Ritchieの文献として論文検索してもTime-Sharing〜のほうしか出てこない。

で、灯台下暗しというか、2238 Clubの参考文献にコピーが置いてあったのでメモとしてここに書いておきます。Lions' Commentaryで検索すると結構上に来るので。

地味にお世話になりっぱなしですね、2238 Club。

Go

Google発の新言語、というトピックには興味がなかったんだけど、なにやら別の面で気になる存在に。

という事で、ベル研からGoogleへ移籍したUNIXチームの面々が開発者なんですね。どうりで変なキャラがマスコットなわけだ。6版読んでる関係からPlan 9周辺もそれなりに調べてまして「間違えて“Inferno Programming with Limbo”を二冊買っちまったー」とか、こんなコレクターアイテム重複させてどうすんだろ・・・と思ってた矢先でした。
(VM絡みも別件で調べてて、Disもちょっとしたマイブームなんですw)

新言語習得という意味では、今はOCamlで苦戦してるので、すぐに手を出すつもりはないんですが・・・とりあえず処理系だけでもインストール、という事で非gcc版をインストールしてみました。

GNUなconfigureの作法に従わないあたり、らしいな〜と思いましたが(笑)。Plan9portとかInfernoと似たようなbuild方法ですね。ターゲットでDisもサポートしないかな〜。Infernoの裾野が広ければひと月もまてば誰かがportするんだろうけど。。。

次にGoogleが戦略的に出してくるとしたらVMですかね。個人プレイ中心ってイメージなので、企業としてのポートレートみたいなのがあるのか知りませんが。まぁ、悩みどころですね、うん。。。

2009年11月10日火曜日

Lions' Commentary (5) - スワップ処理、シグナルほか -

前回から読み進めた結果のまとめ。

まず、プリエンプションについては前回読み解いた通りの模様。
ただし端末から操作してるプロセスに関してはttyからの入出力で絶えず割り込みによるタスクスイッチが発生するので1秒という持ち時間は気にならない。
実際、この1秒のタスクスイッチを実験で観測しようとするとかなり難しい。システムコールも割り込みもなしにプロセスの状況を計測する手段がない。例えば、前回みたいな空ループのプロセスと、ひたすら“hello”と出力し続けるプロセスを同時に実行しても、どちらも違和感無く同時に実行されているように見えてしまう。これはhello側の実行を律速しているのがtty出力待ちであって、一文字書いてはタスクスイッチを行い、tty出力が終わると再びタスクスイッチでhelloに実行が戻る、といった処理が行われるため。一応、これについてはUNIX 7版上で実際に試してみました。

また(Lionsの順番通り)スワップアウトの処理を理解した上でスケジューラを読み直してみると、スワップアウト後は3秒経たないとスワップインさせない仕様や、スワップイン後にアクティブなプロセスが残っている状況では2秒経たないとスワップアウトさせない、といった仕様が目につく。これは4秒ごとの神の雷や、1秒ごとのプリエンプションとの相性を考えると妥当な数字のようだ。一度スワップすると3秒は戻ってこない、というのは凄いけど。。。アプリケーションのサイズの物理メモリの搭載サイズの差が小さかった状況を考えると、当然の実装かもしれない。

あと、順序的にはclockの話とスワップの話の間になりますが、システムコール入口やsignalの処理についても読み終わりました。
システムコールについてはプロセスの起動、終了やsignal関係、つまりはプロセス処理関連を読み終えました。ちょっと前の日記で疑問として書いた件ですが、execによるとやはり命令空間分離やデータ領域分離は実行ファイルの持つマジックナンバーが違うようです。またexitとwaitの関係とか。exitすると終了コードをswap空間に残して親がwaitで回収するのを待ちます。親が死ぬとinitの子供になるとか、ゾンビプロセスについての説明で出てくるような話も当時から存在した模様(swap空間に残す、というのが独特かもしれませんが)。
signalはSIGKILのみ上書きはできないけど、最後に呼ばれた1つしか覚えていない、という実装になってますが、これはそういうものなのかな。。。signalは取りこぼさないと思ってたんだけど、保証はしてないのかな。
まだ確証が得られるまで読み込んでないけど、signalが設定されたら即座に対象プロセスを起こしてハンドラを起動させているように見える。。。けど、たぶんスワップアウトしていたらスワップインを起動して再びスケジューラを起こすので、別プロセスから多重でsignalを設定される事はありそう。。。 まぁ、またそのうち見直すとします。

あとは特殊なsignalとしてptraceの処理。ptrace自体使った事がなかったので、こんな機能があったのかと勉強になりました。子プロセスのメモリ空間なら触る事ができるんですね、UNIXは。子供側からも許可を出す必要があるみたいだけど、これはforkしてから許可を出してexecすれば済む話のはず。
この辺はC言語からの引数とsystem call時の引数の順番が違っていて、読んでいて少しはまりました。7版でmanを見たらアセンブラからの呼び出し例が書いてあってようやく誤解に気づく罠。

Lions本とは関係ないけどBach本も入手。こっちはファイルシステムから解説に入るんですね。単独で読めるのでしばらくはトイレに常駐させときます。ぱっと見た感じではSystem Vになっても6版の構造はかなりひきずってるみたいですね。u区域とか重要な関数の名前なんかはそのままなので疑似コードからソースが想像しやすそう。
6版のソースは逆に残すところファイルシステムとドライバ関連のみ。どっちを読んでも、しばらくはファイルシステムべったりです。こっちは昼休みとか使ってコメント埋め込みつつMercurialでログをとってます。

今回は長文でした。

2009年11月5日木曜日

Lions' Commentary (4) -プリエンプション-

setpri()の疑問はclock周りまで読み進めれば理解できるかな、と思ってたんだけど。。。どうもclock.cで実装されているはずのプリエンプションが理解できない。というか、やってないように見える。

タスクスイッチするにはrunrunが非0にならなければいけないわけだけど、runrunを非0に設定するのはslp.cのsetpri()とsetrun()、あとはclock.cの中だけ。だけど、clock.cの中の処理といえば、タイマーの再設定、コールバック関数の呼び出し、CPU時間の累積くらい。それ以外は1秒に1回プロセス全体の優先度補正をしてるのと、4秒に1回、神の雷?で全プロセスを起こしてるだけ。優先度補正ではsetpri()を呼び出すし、神の雷でもrunrun++してるんだけど、これだと1秒に1回しかプリエンプションが起きない。そんなはずないよなぁ・・・(7版と見比べたけど神の雷が毎秒にかわってるくらいで本質的には差はなかった)。

実際以下のbusy loopのコードを走らせてみたけど 、普通に別端末でshellが滞りなく動いてるし。ひょっとしてI/Oで割り込みがかかるから? busy loopのコードどうしなら1秒単位でタスクスイッチする? う〜ん・・・まさか。
.globl _main
.text
_main:
jbr _main
.globl
.data
という事で、Lions' Commentaryでは11章まできましたが、まだまだプロセス制御でわからない事は多いです。風邪が治ってきたのでまた進捗は芳しくなくなるかもだし(笑。

あと、clock.cでタイマ割り込みハンドラを処理するあたり、callout配列の操作が末尾に暗黙の空エントリを期待してる。timeout()を見ると配列の大きさは気にせずに追加しちゃってるし。この辺りはまったく安全性を考慮されていないアドホックな実装になってますね。Lions'本によれば実際にはttrstrtからしか使われてないらしいので、まぁそういう事なんでしょうね。

2009年11月3日火曜日

Lions' Commentary (3) - setpriの真相はいかに -

setpri(2156)にはちょっとした問題がある。

関数のコメントには以下のように書かれている。

2150 /*
2151  * Set user priority.
2152  * The rescheduling flag (runrun)
2153  * is set if the priority is higher
2154  * than the currently running process.
2155  */
つまり、優先度を再計算して、現在実行中のプロセスより優先度が高くなっていたら再スケジューリングのためにrunrunを++する、と書かれている。ところが実際のコードは
2156 setpri(up)
2157 {
2158         register *pp, p;
2159 
2160         pp = up;
2161         p = (pp->p_cpu & 0377)/16;
2162         p =+ PUSER + pp->p_nice;
2163         if(p > 127)
2164                 p = 127;
2165         if(p > curpri)
2166                 runrun++;
2167         pp->p_pri = p;
2168 }
 であり、再計算した優先度が、実行中のプロセスの優先度より低ければ(if (p > curpri))再スケジューリング(runrun++)となっている。

で、Lions本によれば「自力でバグでない事を確認せよ(ヒント:呼び出し時の引数)」との事。さっそくgrepした感じではsetpriはプリエンプションの時に呼ばれているように見える。つまり、走行中のプロセスが持ち時間を使い切ってタイマーによって割り込まれた際に、CPU使用時間を計上してからsetpriを呼んでいる。優先度を下げる方向で再計算させているのであり、curpriは走行中のプロセスが選択された時の優先度。 下げてるんだからここでは常に「p > curpri」が成立するのは自明であり、再スケジューリングが走るのはしかるべきである。つまりコメント側が間違っている、という理解。バグではないという事で納得した・・・と思ったんですが。。。

例の2238 Clubにはバグという記述がありました。確かにベル研の資料には以下のように書かれている模様。
30)
    Bug fix in "setpri()": p>curpri should be p<curpri.
むぅ・・・公式にバグと言ってるわけだから、やっぱりバグなのだろうか。。。
真実を知っている人がいたら、ぜひ答えを教えて下さい。

simhと7th UNIX

我が家ではsimh上でAncient UNIXを動かしています。
具体的にはPDP11版の7th Editionに2BSDをインストール。自前パッチとして
  • date 2000年問題対応
  • vi hjklカーソル移動対応
  • vi 大画面対応
あたりを施した状態なんですが、動作中にCPUを食い潰しにいくのが気になってました。大昔のUNIXなんて電力制御も糞もないので、idle時にbusy loopでもしてるんだろう、と思ってたんですが、スケジューリング周りのコードを理解すると、きちんとスケジューリング対象がいない時にはidle()からwait命令を発行してCPUが割り込み待ちで寝るように作ってあります。
という事は・・・と思ってsimh側を見てみたら、どうやら「set cpu idle」を設定してあげないといけないようでした。

という事で、うちの設定は(ストレージ周りの設定を除くと)
set cpu u18
set cpu idle
set tti 7b
set dz 7b lines=16
att dz -am 4096
こんな感じです。
コンソールはマルチプレクサ(dz)通してtelnetで入れるようにしてあります。
7bってのはvi使うときに必要な設定で、これがないとtermcap使った画面制御がうまくいきません(制御ビットがマスクされちゃう)。viのbuildに成功して最初に起動したときは相当はまりました。termcapの設定ミスかと思って色々追いかけましたが、まさかsimh側の設定に問題があったとはorz 最近の環境に慣れ親しんだ身としてはcatとedだけの探検というのはジャングルでの生活に匹敵しますね。

2009年11月2日月曜日

Lions' Commentary (2)

ちょっと忙しくなって進捗が停滞してました。
仕事のコードレビューとかいつも数万行単位で実施してて、その時間を6版のレビューにあてられたら、すぐなのになぁ・・・とか思ったりします。って前回も同じ事書いてたか(汗

という事で、風邪をひいて熱を出してしまい、せっかくだから病院で読み進めました。
Lions'本でいうところの7章プロセスのあたりを読みました。外なので訳本で読んでたんですが、P.322の表に誤字がありますね。t+16,t+144って書いてあるところ、d+16,d+144が正しい。オリジナルの資料を確認したらそっちは正しく書いてありました。

Kernel空間と違ってUser空間はブロック(64B)単位(MMUが扱える最小単位)に細かくMMUを張ってますね。ページ単位に慣れた現代人としてはちょっと気持ち悪いですが。suregの最後(1762)のアドレス補正はちょっと難しい。アドレス空間分離モードだと必ずx_caddrが設定される、という前提のコードという理解で良いのだろうか。。。

まだローダとか見てないんだけど、命令/データ分離の場合とそうでない場合で実行ファイルの互換性ってないのかな?

完全には消化しきれていない感じです。