UNIX原典(3) - ラスト

続けてUNIX移植話に関連したトピックを3件ほど取り上げてみます。他にも性能やスケジューラの話なんかも面白かったのですが、UNIX原典の読書記録としては今回の記事を最後にしようと思います。

Fair Share Schedulerについてはこの資料が一番詳しいかな、って感じだったのですが、他のスケジューラとか勉強した時に、また比較で考えてみようと思います。

マルチプロセッサUNIXオペレーティング・システム
「UNIXカーネルの設計」の著者、M.J.Bachによるマルチプロセッサ環境への移植話。ここではMP（multiprocessor）、AP（Associated Processor）を取り上げていて、前者がいわゆる今時のSMP、CMPの話。後者はI/OはマスターCPUに括りつけて、他のCPUはユーザランドの実行だけを行うような単純な方式によるマルチプロセッサ化の話になります。この方式ではカーネル自体、特に排他制御などは不要で、スレーブCPU上でユーザがシステムコールを発行した際、マスターCPUにコンテキストを移し、システムコールは常にマスターCPU上で実行するようにするだけで対応できます。よって、この論文では主にMP上に移植する際の問題について書かれています。

Lions本などでも書かれているように、UNIXではatomicな処理が必要となるリスト探索などは、一時的に割り込みレベルを上げて、リスト探索中に割り込みによる中断と他の文脈からのコードの実行を禁止し、探索が終了したら割り込みレベルを通常に戻す、といった処理（spl6やspl0）をしています。ところがマルチプロセッサでは割り込みレベルを上げたところで、他方のCPUが競合するコードを実行する事は可能なわけで、意味をなしていません。よってMP版UNIXでは、これらの問題に対処するためにセマフォ(*1)が導入されました。

また、sleepとwakeupについてもセマフォの取得と開放（psemaとvsema）に置き換えられました。

セマフォを使う際に問題となるデッドロックについても説明されています。これは一般的なデッドロック回避方法「依存ループを作らない」の言い換えでもありますが、資源に順序付けを行い、ロックは順序付けにしたがって行う、という単純なルールに従うだけでデッドロックは回避できます。

排他制御を行う際には、細かな粒度でロックをかけることが性能の上で重要になってきます。連結リストをハッシュに置き換えてロックの粒度を小さくする方法が紹介されているが、一番競合が起きやすいバッファプールのフローリストについては、うまい分割方法が知られていない、と書かれていました。今時の最新事情でどうなっているのか、知っている人がいたら教えてください（笑）。


IBMシステム/370のUNIXシステムの実現
こちらはIBMのメインフレームへ移植したお話。この移植は370のハードへ移植した、というよりは370上で動くTSS/370をターゲットとして移植したようです。mach上で動くように移植されたLinux、MkLinuxに近いもの、と読みました。理由としては370の仕様がハードごとに細かく異なり、個別の移植が困難だったことが挙げられるようです。360系は長期に渡る使用に耐えた拡張性のあるアーキテクチャ、という事になっていますが、メインフレームの文化を考えると、ファームレベルではワークアラウンドやRASの処理がごった返し、相当なカオスなのでは、と想像されます。

この版のUNIXで特徴的なのはページングの実装方法です。1つの物理ページに対して、リファレンスカウントを用意して、複数の仮想ページに割りつけられるようになっています。当時のforkは、親のメモリを丸々コピーして子プロセスを生成する非常にコストの高い処理でした。そのためBSDではfork後すぐにexecを呼ぶプロセスのために、メモリをコピーしないvforkを用意しましたが、これは、親子でメモリを共有する危険な実装で、vfork後にexecせずにメモリ操作をした場合の動作は保証されていませんでした。この版のUNIXの実装では、fork時にはページのコピーをするのではなく、ページテーブルのコピーと物理ページ側の参照カウントをインクリメントするだけで済んでいます。また子プロセスで書き込みが発生した場合には親と共有している物理メモリの参照をデクリメントし、新しいページにメモリをコピーし、子供のページテーブルに登録するという、いわゆるcopy-on-writeを実装していたようです(*2)。

ディスクブロックサイズも、System III以前が512B、System Vや4.1BSDが1024Bだったのに対して、370版では4096Bと大きかったようです。


UNIX移植の経験
Intel 8086、AT&T 3B20S、3B5、UNIVAC 1100シリーズへの移植について書かれています。今までの2章に比べると目新しい話題はないのですが、AT&T UNIXが8086へ移植されていたとは、ちょっと驚きです。

ただ、この8086 UNIX、単純なソフトの移植というわけではなく、それ専用にPDP-11/70風のオフチップMMUを開発し、それを載せたシステムへの移植だったようです。

またエンディアンの違いの話も出ていたりしますが、今の人から見ればPDP-11のエンディアンが変態(*3)すぎるだけなわけですが。


(*1): 本の中ではDijkstraのセマフォ、と書かれている。いまやあまりにも当たり前の道具として使われているため、発明者について言及されることもなくなってしまいました。
(*2): 勉強不足のため、いわゆるcopy-on-writeの原点がこの実装なのかどうか、知りません。ご存じの方はぜひコメントを。
(*3): PDP-11のエンディアンはリトルエンディアンでもビッグエンディアンでもなく、ミドルエンディアン。リトルもビッグもそれぞれの言い分は理解できるのですが、ミドルだけは意味不明。アドホックにしか思えないのですが。。。これも意義をしっている方がいましたら、ぜひコメントを。