仮想記憶 - oraccha/omicron GitHub Wiki
Virtual Memory
1959 年 Atlas ではじめて実現され，1960 年代後半，Multics で本格的に採用される．その後，仮想記憶の制御方式は OS 研究の大きなテーマとなった．P.J. Denning 氏によるワーキングセット(1968年)などの理論的な研究などを通して，70 年代前半から半ばにはプログラムの局所参照特性の重要性が認識されはじめた．そこでプログラムの局所参照性を改善するために D.J. Hatfield 氏らによってプログラム再構成法が提案された．
アドレス変換において，物理アドレスをキャッシュするアーキテクチャと，仮想アドレスをキャッシュするアーキテクチャがある．最近のアーキテクチャは後者を採用するものも多く，TLB と仮想アドレスキャッシュの共存も可能である．
- プロセッサ、MMU、物理メモリのどこにキャッシュを配置するかの違い。
- 仮想キャッシュは複数のプロセスが同じアドレス空間を使うので、曖昧性を克服する工夫が必要になる。そのためにキャッシュフラッシュ命令、アドレス空間を識別するためのID(ASID)の利用が提供される。
- また、仮想キャッシュの問題点として、OSとユーザプロセスが同じ物理アドレスを別の仮想アドレスとしてキャッシュする可能性がある。これはシノニムとかエイリアスと呼ばれる。これに対してアンチエイリアス機構やカラーリングなどの手法が考えられている。
LinuxとBSD系Unixにおける仮想記憶機構の違いについて
-
[http://www.os-omicron.org/~takano/private/trans/kt_70_07_j.html 仮想記憶: Linux Vs. BSD] . KernelTraffic の記事の日本誤訳．
-
Clock page replacement algorithm について捕捉．
- Unix 初期の仮想記憶にはプロセススワッピング(プロセスごとにごっそり入れ替える方式．PDP-11 がそんなハードウェアだったから)しかなく，ページングが実装されたのは VAX 上で動く 3BSD から．最初に Ozalp Babaoglu 氏によってワーキングセット方式による実装が試みられたが，VAX には参照ビットがなく，その作業は困難であった．そこで BillJoy 氏の協力を得て，デマンドページングの実装にこぎつけたらしい．
- 4BSD(3BSDも?)で使われたページ置換アルゴリズムが(一針)時計アルゴリズムだった．時計アルゴリズムの実装にはページテーブルエントリに参照ビットが必要であるが，BSD のターゲットマシンである VAX には存在しなかった．そこで，ダーティ(更新)ビットを利用し，ソフトウェア的に参照ビットをエミュレートする形で実装された．この方法はページフォールを利用する分，オーバヘッドになった．
- 各エントリはページデーモンによって周期的に検査されるが，メモリが多くなるにつれ，走査時間が増え，非効率的になってきた．そこで 4.3BSD のときに改良策として生まれたのが二針時計アルゴリズムである．
- Linux はスワッピングを実装していないけど，アイドルプロセスであるプロセス0の名前は "swapper" になっている．ちなみに歴史的に Unix の PID は 0 が swapper，1 が init，2 がページデーモンになっているみたい．
-
[http://www.at.sakura.ne.jp/~liu1/diary/?2000122&to=200012221#200012221 今日のブックマーク] (2000-12-22) . 内藤隆一氏のページから．リンクありがとうございます．確かに上の記事だけじゃもの足りないなぁ．
-
[http://www.kerneltrap.org/node.php?id=72 FreeBSD: Comparing The VM With Linux] (KernelTrap 2002-03-08) . Dimitar Peikov 氏が投稿した単純な malloc テストの結果に関する議論．
BSD系Unix 仮想記憶サブシステムの動向
- [http://www.daemonnews.org/200001/freebsd_vm.html Design Elements of the FreeBSD VM System] (daemon news) . Matthew Dillon 氏による FreeBSD の VM サブシステム．
- [http://www.ccrc.wustl.edu/pub/chuck/tech/uvm/ The UVM Virtual Memory System] . NetBSD/OpenBSD に搭載されている新しい VM サブシステム． UVM 以前(Machベースの 4.4BSD 由来の方式?)はページキャッシュと VM が統合されていなかったので，UVM の U は Unified とか Universal かと思ったけど，FAQ によれば特に意味はないらしい．さらにバッファキャッシュと VM を統合させる UBC というプロジェクトも存在するらしい．
OS/omicronがらみの話．
V2/V3 は実記憶 OS だったが，保護のためのバウンダリレジスタを実装するために仮想マシンでは MMU 操作を行なっていた．これが結構遅かった．
- OS/omicron 概説を延匡さんの発表 & デモで行なったとき，当事アステックにいた竹岡さんと延匡さんの間で「なぜ仮想記憶をやらないのか．技術者としては仮想記憶の実装をわかっていて欲しい」「仮想記憶はいつでもできる．まずは実記憶から」というようなやりとりがあったらしい．
で，この頃のターゲットマシンは日立 2050 だった．2050 はJR(国鉄)の緑の窓口で端末として使われていたもので(OS はたぶん Unix だろう)，プロセッサとして 68030 を搭載していたのだが，MMU は Motorola の純正品ではなく日立オリジナルだった．この MMU，仮想アドレスキャッシュのアーキテクチャで，SCSI の DMA 転送でも仮想アドレスを指定するといったものだったらしい．インテリジェンスなんだけど，当然遅い．
ということでソフトとハードの遅さの二重苦に苦しめられたそうな．
Topics