UNIX原典(1)

ベル研メンバーによる開発秘話本って事で、読み物として買ってみました。オリジナルはBell System Technical Journal 1984年8月号第2部UNIX特集号らしい。

技術書というよりは歴史書として買ったつもりだったんだけど、結構面白い。ライオン本だと「どう実装しているのか」は理解できても、「どうしてそう実装したのか」までは理解しきれない点も多々ありますが、この本読んでると、バグの話なんかも出てきて、意外なところで実装の意図が読み取れるかも？まだ読み始めたところなんで最初だけかもしれませんが。とりあえず面白いなぁ、という話があったので、それについて書いておきます。

file descriptorの実体については"Lions' Commentary (7) - closeとunlink -"で書いたとおりで、プロセスに直接ぶら下がっているのは実体ではなく参照です。プロセス内でユニークな番号が振られているので、プロセス固有のリソースのような気がするわけですが、実はシステム固有のリソースとして実装されている。forkの話もあるので、なんとなく「そうすべき」というのは直感としてあるのですが、いまいち必然性までは理解できていませんでした。

初期のUNIX@PDP-7ではShellがCP/MのCCPに近い実装になっており、ユーザ・プログラムではなくOSの一部として動いていました。その後、forkとexecが実装され、shellがユーザ・プログラムとして分離。今風のプロセス制御も導入されて、バックグラウンド実行なんかもできるようになりました。この頃はfile descriptorの実体がプロセスにあり、以下のようなコマンド（今風に書きなおしています）が正しく動作しなかったそうです。

$ (echo foo; echo bar) > log

期待される結果は

foo
bar

ですが、実際には

bar

になってしまう。ははぁ、確かにforkとexecの挙動を考えると、file descriptorがプロセスにぶら下がっていると、そういう事になりますね。このバグに気づき、file descriptorの実体はプロセスの外に追い出された、との事です。なるほど。
また、当初はchdirも外部コマンドとして実装されていたそうです。プロセス制御がなかった頃はカレントディレクトリはttyに括りつけで1つで良かったわけで、chdirはこの括りつけのカレントディレクトリを変更して親のShellに戻っていました。ところがプロセス制御の導入によりカレントディレクトリはプロセスごとに個別に持たせる必要が生じ、その結果として外部プロセスとしてのchdirを実装できなくなりました。最近のUNIXから入ってると、むしろ初歩的なトラブルって感じがしちゃいますが、当時はUNIXの生みの親たちですら理解に苦しんだバグのようです。コロンブスの卵的なところがあるのかな。

The Singularity System

ここのところ、まったく時間がなかったのですが、出張帰りの飛行機で時間があったので、Communications of the ACMに寄稿されていたSingularityの記事を読んでみました。

SingularityとはMicrosoft Researchによる研究段階のOperating Systemです。micro kernelを採用しており、コストの高いプロセス間通信を解決する方法としてSIPと呼ばれる機構と、高位言語による記述を採用している点が特徴かと思います。

大雑把な説明はWikipediaの解説が手っ取り早いでしょうか。

Singularityでは、OSを含めて高位言語で記述するのが基本です。kernel本体はSing#と呼ばれるC#の拡張言語で記述され、他にはC#、F#、Visual Basicあたりがサポートされています。

Wikipediaを見るとSIPはmicro kernelと各サーバ群との通信を最適化するための仕組みのようにも見えますが、記事によるともっと一般的なプロセス分離の仕組みのようです。

Singularityにおけるプロセス保護は多層で実現（multiple layers of protection）され、基本的な方式がSIP、二次的な方式が仮想メモリ空間による分離（近代的なOSが一般的に採用している方法）になります。

SIPによる分離では、同一メモリ空間内にページ単位で複数プロセスを貼り付け、仮想メモリ空間切り替えによるプロセス切り替えコストを除去する事が目的となっています。ページ保護は利用しているようなので、SIPで分離されたプロセス間の切り替えでは、ページのアクセス権限だけ書き換えるのかな？この辺は詳しく書かれていないので想像です。このへんの保護は言語レベルでのサポートや形式検証なども使えるみたいです。

一般的にプロセス単位で仮想メモリ空間を切り替えるメリットは、メモリ保護だけでなくメモリ管理にもあります。プロセスにつきヒープとスタックという二種類の可変長作業域が必要となります。一般的にはヒープは下位アドレスからプラス方向に、スタックは上位アドレスからマイナス方向に伸びていくことで実現していますが、同じアドレス空間に複数のプロセスを配置するとなると、ヒープを拡張しようとしたら、別のプロセス空間が邪魔で・・・なんて状況が起き得ます。

680x0時代のMac OSでは、MMUが使えなかったため、ハンドルとコンパクションという考え方で対応してきました。メモリはハンドルで管理し、必要なときだけロックをかけてハンドルからポインタに変換します。使い終わったメモリはすぐにアンロックすることで、ポインタは無効になります。このお約束を守ることで、連続したメモリ領域がなくなった時、コンパクションによってロックされていないメモリを移動し、メモリ再配置による最適化を行うことができるようになります。

Singularityでこの辺りをどう対処しているのかは読み取れませんでした。Garbage Collectionによるメモリ管理をOS含めて導入しており、runtimeによるポインタチェックも行っているようなので、その気になればコンパクションもできるのかもしれません。今時のメモリサイズであれば、コンパクションがなくて実用上問題にならないのかなぁ。

あるいは、記事の例を見ると、そうは言ってもSIPによる分離は共有ライブラリやコンポーネント、Plug-insなどのレベルでメモリ保護を実現するための機構として利用しているようにも見え、実際には仮想メモリ空間による分離もかなり積極的に使っているのかもしれません。

SIPを導入するためには、Javaのような実行時のポインタチェック、配列領域チェックなどが必要になります。この記事の結論では、これらのruntimeのコストは5%程度の効率低下に留まり、仮想メモリ分離をやめたことによるパフォーマンスゲインが38%もあるため、総じて安い、という事のようです。

SIPを使うとプログラムはリロケータブルにする必要があるので、元々共有ライブラリで実装されていたような物は差がないんでしょうが、プロセス分離に適用しちゃうとローダがリロケートするコストが馬鹿にならないような気はしました。

SIP間通信の仕組みとしては、強く型付けされたパイプを使っているようです。実データは同一メモリ空間内のExchange Heapと呼ばれるところに格納され、ゼロコピーでデータ交換しているように読めます。このあたりが効いて、low latency、high bandwidthなプロセス間通信が実現できる、という事のようです。また、通信には"contract"と呼ばれる仕組みが使われており、この辺も突っ込んで調べてみると面白そう。通信データを入出力としてステートマシンを記述して制御しているようなので、形式検証を使ってプロトコルチェックとかできるのかも。

最後の方では、kernelにGarbage Collectionを適用する事の是非について触れられています。kernel objectの多くはlifetimeが非常に長く、プロセスの開始から終了まで張り付いています。この種のobjectを大量にGCで管理したところで、メモリ回収のwalkingにかかるコストが大きくなるだけで、あまり旨みがないのでは、といった議論があるようです。

という事で、最近は懐古趣味ばかりでしたが、めずらしく先端研究についても調べてみました。

オリゲー・フェスタ68

通称オリフェスに参加してきました。
自分のサークル名義じゃないけど、久々のイベント参加。

イモプロ名義で以下の物を展示してました。

• MegaZ-80K（最初の写真では画面左端より外側ｗ）

AVRをふんだんに使って再現したMZ-80K互換機。MEGA644でZ80エミュレーション。UARTベースで共有バスを張って、その上でI/O通してました。今回は足がいっぱいあったので、SRAMとはアドレス15bit、データ8bitを外部ラッチ無しで直に繋いでます。配線は圧倒的に楽ができた（笑。

画像表示はMEGA328が専任。ひたすらUARTモジュールを駆使してNTSC信号を作りまくるお仕事。I/Oからのアクセスにすぐに応答する余裕がないため、間にFIFOとしてのTINY2313がいます。
I/OバスとしてはシリアルでTINY2313がデータを掴み、HSYNCを待ってパラレルでMEGA328に流し込む感じです。

写真はMac上のGtkで書いてたプロトタイプに、シリアルで画面表示モジュールにデータを流し込むコードを追加し、エミュレーションで書いた画面と実際のビデオ出力を比較しているところ。











あとはサウンドもTINY2313が担当。こっちは割り込みでレジスタをパタパタさせて鳴らしております。

で、最後はなぜかファミコンコントローラ。色々とツッコミもありましたが（笑。キーボードどうしようかな、PS/2にしようかな、USBにしようかな・・・と考えていたらPS/2の端子が部品箱にない事に気づきました。USBならいっぱいあるけど、ホストは作ったことはないし・・・。という事で、手っ取り早く済ませよう、とファミコンを投入。やっぱりTINY2313を使っていて、キーボードに対するI/Oアクセスが来たらコントローラのステータスを読み出し、適当にスキャンコードにマップして応答を返しています。

• CP/Mega88（左端、iBook）

再びCP/Mega88。こっちもインベーダー動かしたりして展示してました。
ライセンスはどうなってるの？って人もいましたが、今は開放されてます。

• USB-PSG/SID（中央、MacBook）

USB接続のPSG音源とCommodore64のSID音源。Linux用のドライバしか書いてないので、デモはUbuntu上で行いました。fMSXのPSGアクセス部に手を入れてドライバのI/Oを叩くようにしています。Ys-IIのサウンドモードを動かしていました。
同じような事をやってます、って話をしてくれた人が何人かいましたが、Windowsでやってる人はドライバ部分で苦労してるみたいです。Linuxはその辺がお手軽だったので、独自クラスで適当なbulk転送のプロトコル決めて、ちゃちゃっと処理しちゃってます。
/sys/bus/usb/drivers/usb_psg/ 以下にデバイスファイルが出来て、そこ経由でレジスタ読み書きしたり、レジスタダンプ表示させたり。
USB部分はPIC18F2550ですね。今回唯一のPIC成分。PICだとUSBフレームワークがついててファーム開発もらくらく・・・というわけではなく、実は自分、商用コンパイラ使うのが許せなかったので、sdcc向けにスクラッチでUSBのファームを書きました。当時は自前でUSB周りを叩いたファームって見かけなかったけど、今だとどうなんだろう。シリアルからデバッグメッセージ吐きながら開発してましたが、うかつにメッセージ吐くとUSBのプロトコル側でタイムアウトが発生してしまうので、結構大変だった記憶があります。

Kerne/VM探検隊

Kernel/VM探検隊#4に参加してきました。
今回も色々と刺激的なお話が聞けました。
技術的にも、年齢層的にも、けっこう幅広いのが良いです。

yojiroさんのUSBデバイス解析の話は面白かった。
「俺の電線に流れる電気信号を観測して何が悪い」って、なるほど。
電子工作のデバッグでプロトコルアナライザ使ったら敗北感がありますが、
ソフト開発では漢のツールですね。

kobaさんのqemu+chrootの話もgood。
クロス環境作成にはいつも苦労するので。
こういう発想はなかったな。。。
linuxの/proc/sys/fs/binfmt_miscも今回はじめて知った。
そういえば、UNIXの「#!」の習慣はどこから始まったんだろう。
Ancient UNIXではこの習慣はなかった。
実行ファイルでなければシェルがそのまま実行してますよね。

ucqさんはバイナリエディタでプログラミング。
Plan 9を例にしてたけど、やっぱり一番簡単なのはX680x0の.r形式だな。
ヘッダ一切なしで、relocatableな実行列の塊。
自分は開発環境が入ってなかった部室のマシンで、しかたなく
TYPEコマンドでリセットコマンドを作った記憶がある。。。

shudoさん参加してたのか。
しかも発表側。
末尾再帰で最適化かかってるんじゃない？的なコメントもあったけど、
その時はスタックは呼び出し元と整合するように補正してからジャンプ
ってなるはずだし、やはり元作者のケアレスミスでは。

oracchaさんの発表でsocketはshutdownかけると相手側のreadが0で返り、
それをEOFとして処理するアプリが多いという事を知った。
signalが来た時もsystem call中断してhandlerに処理を移すけど、
あの時は-1か。確かにman 2 readに書いてある。
BeOSのsshがEOF検出できずに固まる事があったけど、あれはshutdownが
きちんと動いていなかったからなのだな。。。と今更気づいた。


そうそう、今朝、目覚めてふと疑問に思いました。
ファイルシステムのジャーナルってどの層でやってるんだろう。
普通UNIX系のシステムだと、デバイスの上にブロックデバイス
ドライバがあって、その上にバッファキャッシュが載っていて、
さらにその上にファイルシステムが載ってるはず。
トランザクションって意味ではファイルシステムの最下層で
ジャーナル録りたい気がするけど、その下のバッファキャッシュが
LRUで動いているので、それでは不意の終了に耐えられない。
かといってディスク直上でジャーナル録ってたら、
◯△fsのジャーナル機能が云々〜って話にはならないはずだし。

エレキジャック・フォーラム

というわけで、発表させていただきました。

発表資料のほうは、カーネル/VM探検隊で見たsexy hookの
プレゼンに触発されて、Preziで作ってみました。

CP/Mega88 on Prezi

オンラインでの参照はこちらから。

デモをしようと思ってたんだけど、ディスプレイ出力端子が
USB端子とぶつかってしまい断念。
この日にあわせて新マシンを調達したのが裏目に出たか（うひ

そのうち基板作ったら一式公開〜とか考えてたんですが、
興味もってくれた人がいたので、近いうちに一度公開しようと思います。

思考の整理学 (1)

電車通勤をやめてからすっかり本を読まなくなりました。
積まれていた本の中から１冊だけ鞄に入れてたんですが、今日は少しだけ読む機会があったので、読んだところを少しだけメモ（続き読むが先になるかもだし）。

という事で、表題の通り、外山滋比古さんの思考の整理学。
整理学とかいうタイトルだけど、特に考える事に関して体系化した書物というわけではないですね。「思考」に関する様々な角度からのエッセイを、どちらかと言えばごちゃっとまとめた感じ？

「グライダー」：グライダーと飛行機。詰め込み型教育の産物、自力で前へ進む事のできない人たちをグライダーに例えて批評。「自分で翔べない人間はコンピューターに仕事をうばわれる。」1986にまとめられた本にしては刺激的な台詞で締めくくられているけど、2010年になった今日、状況はどんなもんだろう？　就職難と人材不足の共存状態は、予言が的中した結果とも思えるけど、実際には大企業はまだまだグライダー人間に支配されている気はするなぁ。
続く「不幸な逆説」で述べられている、教える事を渋る事による飛行機人間の育成、という考え方は面白い。伝統芸能などで見られる教えない文化。師の業を盗もうと努力するところから学ぶ姿勢、意欲、独創性などが生まれるのではないか、という仮説。

「朝飯前」：まさに自分が修論の時期に実践していた事。一日のうち頭が働くのは起きた直後の数時間。ここまでは大学の仲間うちでも周知の事実だった。なので、一日を12時間ずつにわければ、頭が働く時間も二倍になるだろう、と。3時間寝て9時間作業〜みたいな生活だったと思う。普通に仕事して、論文も書いて、さらにバンド活動・・・となると、こうでもして時間を稼ぐほかなかった。凄い勢いで時間が過ぎていくようで、カレンダーは半分しか進まないという不思議な感覚で、実際に生産性もかなり上がった気がしました。
自分がやってた事と同じ事を筆者がしていると知って嬉しくなり、それがblogに書き留めようと思ったきっかけでもあるわけですが。さらに筆者は、朝飯を抜けば、さらにこの朝飯前の時間を長くとれる・・・と、なんだか子供じみた事まで（笑。偉い先生がこういう事を実践している、というのは生々しく、結局は努力なんだ、と思うと、なんだか救われた気持ちになります。努力でどうにでもなる世界、つまるところそれが究極の平等社会なんですけどね。民主党政権しかり、どうも日本は変な方向に向かいつつあります。

アマゾンでも誰かがレビューに書いてましたが、アイデアについてのエッセイでのべている事はジェームス W.ヤングの本に書かれている事と同じですね。学生の頃に読んで意識、実践してきたけど、アイデアが生まれるプロセスに関してこの本の解析はかなり正しい。色々な人が共感している事からも万人にとって真なんだと思う。うまくやれば凡人でも非凡のフリができる。。。はず。



＃そういえば、内閣府調査の一環で面接がありました。大学院教育はどうあるべきか、というテーマで議論したのですが、つまるところ調査の趣旨は「ゆとり教育は失策だった。その分、大学院教育でフォローして、なんとか社会で使える人間に仕上げる体制を作りたい。」という事だそうです。大学、大学院の進学率が伸びていますが、今まで12年で身になっていた事を16年、18年じっくりかけて教えているだけ。こういう状況にあって、自分の子供にどう学ぶ事を教えていくべきか、非常にむずかしい問題だと感じています。未だ脳の衰えを感じる事はありませんが、知識に関しては若ければ若いほど吸収が早く、使える技術になり易いのは事実でしょう。

ファミ・コンパーチブル（改）

あきばお〜で買い物ついでに。。。
600円弱とちょーお安かったのでw

背面についてる端子は写真の通り。
コンポジット端子なのでその辺のモニタに気楽にさせるわけですが、ちょっと配置が変（笑。付属のケーブルも赤／黄だったりして、なんじゃ？　って感じ。

答えから言うと、白と赤にはまったく同じ信号が配線されてます。日本ではステレオに繋ぐ時にもL（白）だけ繋げれば自動で左右に展開されるのが一般的ですが、大陸では違うのでしょうか。。。謎は深まります。

ちなみにACアダプタ端子が付いてますが、添付の紙っぺらによれば使用禁止。
・・・PSE通ってないから？　一応電池4本でも動くんですけど、電池は面倒です。
「まぁ、その辺のアダプタをさせば動くだろう・・・」
と甘い考えでその辺に転がってたアダプタをさしたら

ぷつんっ
「あっ」
・・・ぷ〜ん（異臭）・・・

やべー、やべー。
ってことでさっそく分解して調べてみたら極性が逆でした。

しかし、この電源作りが怖いです。。。
アナログ弱いんで理解が怪しいですが、トランジスタ（8550）１つで定電圧回路を作ってました。エミッタベース間に逆電圧をかけてツェナー効果で6Vを作っている模様。

ってなもんで、試しにセンターマイナスのアダプタを挿してみましたが、電圧が不安定なせいで画面がぶれまくり。

しかも、めちゃくちゃ熱くなるので要注意。。。

これじゃ使えないな、という事で例によってUSBから電源拾えるように（笑

写真の位置が空きスペース的にも固定するにもあつらえ向きでした。ここからUSB配給の電源を電池ケースの+/-に繋ぎ込めばOKです。

電圧が6Vから5Vになりますが、まぁ大丈夫でしょう。というか、むしろ5Vが本命な気はする。

で、多くの互換機と同じように拡張音源に対応してなかったので、ついでにその辺もプチ改造。カートリッジの45番ピンと46番ピンがショートしてるので、パターンカット。カートリッジから出力端子に繋がってるケーブルのA(udio)線をカットして、基板側を45番に、A(udio)線を46番に繋ぎ込めばOKなはず。

という事でためしにマダラを。

う〜ん・・・鳴るようにはなったけど、バランスがいまいちでした。FC音源側が極端に小さく鳴ります。

45番と46番の間にダイオードと抵抗挟むくらいで調整できないかな。。。
アナログ詳しい人いたら弟子入り希望（笑

という事で、ちょっと息抜きの寄り道でした。満足したのでこいつはステステ（ぇ

（注）この記事は無保証ですので、改造はAYORでお願いしますね。