8. コンピュータはどうやって複数のプロセスが干渉しあわないようにしているのか?

カーネルのスケジューラは、プロセスの時間的な割り振りを担当しています。 同時に、オペレーティングシステムは、プロセスを空間的にも割り振って、それらが 互いの作業メモリ領域に干渉しないようにしなければなりません。 すべてのプログラムが協調して動いてくれると仮定した場合でも、 そのどれかひとつにバグがあり、それによって他のプログラムのメモリ領域が 破壊されてしまうような事態は望ましくありません。この問題を解決するために、 オペレーティングシステムが行う対処方法は、メモリ管理 (memory management) と呼ばれて います。

コンピュータ内の個々のプロセスには、そのコードを実行したり、変数を 保存したり、処理の結果を格納したりする場所として、独自のメモリ領域が 必要です。こうしたメモリ領域は、(プロセスの命令が保持される)読み出し専用 領域である コードセグメント (code segment) と、(プロセスのすべての変数が保持される) 書き込み可能な領域である データセグメント (data segment) から構成されていると考えることができます。データセグメントは、文字どおり 個々のプロセスに固有の領域ですが、二つのプロセスが同一のコードを 実行している場合、Unix は、メモリの利用効率の観点から、そうした プロセスが、単一のコードセグメントを共有するよう調整を行います。

8.1. 仮想メモリ:簡易バージョン

メモリは値段が高いので、効率よく利用することが大切です。ときには、マシンで 実行中のすべてのプログラム全体をメモリに保持するだけの余裕がない場合が 生じます。特に、X サーバのような巨大なプログラムを実行しているような場合 には、メモリ不足が生じることがあります。この問題に対処するために、 Unix は、仮想メモリ (virtual memory) と呼ばれるテクニックを 使います。これは、プロセスのすべてのコードとデータをメモリ内に保持 しようとするものではありません。むしろ、比較的少量の ワーキングセット (working set) だけを保持するようにして、 残りのプロセス状態は、ハードディスク上の スワップスペース (swap space) という特別な領域に置いておきます。

注意して欲しいのは、前の段落で「ときには....生じます」と書いた部分は、過去に おいては、「ほとんどいつも生じていました」と言い換えることができるという点 です。以前は、実行中のプログラムのサイズと比べてメモリのサイズが 全然足りなかったので、スワッピングは頻繁に起こっていました。しかし、 メモリは今日ではかなり安価になっていて、ローエンドのマシンにすら、かなりの メモリが積まれるようになっています。64 MB 以上のメモリを積んだ現在の 個人用マシンの場合、X やよく利用するジョブが最初からコアにロードされた あとでも、そうしたプロセスをスワッピングなしで実行することが可能に なっています。

8.2. 仮想メモリ:詳細バージョン

前章では、実際にちょっと話を単純化しすぎてしまいました。確かに、プログラム はメモリを、巨大で平板なアドレス領域であり物理メモリよりも大きなもの である、と認識していて、その幻想を支えるものとしてディスクスワッピングが 利用されているというのは本当です。しかし、現実には、ハードウェアは異なる 五種類もの メモリを持っていて、プログラムが最高速度で実行されるようチューニングしなけれ ばならない場合は、この五種類のメモリ間での違いは、非常に重要な問題となるの です。マシン内で何が起こっているのかを本当に理解するためには、これら 全体がどういう仕組みで動いているのかを知らなければなりません。

五種類のメモリとは、次のようなものです:プロセッサのレジスタ、内部(もしくは、 オン・チップ)キャッシュ、外部(もしくは、オフ・チップ)キャッシュ、 メインメモリ、およびディスクです。これだけの種類のメモリが存在することの理由 は、単純です。スピードを上げるにはお金がかかるからです。上記五種類のメモリは、 アクセス時間の短い順番、コストの高い順番に並んでいます。レジスタメモリは、 最速かつ最も高価なものであり、一秒間に十億回くらいランダムアクセスが可能です が、ディスクは最も低速かつ安価であり、一秒間に百回くらいのアクセスしか できません。

以下に、2000年初頭の典型的なデスクトップマシンにおける各種メモリのスピード の一覧表を記載します。スピードと容量は年々上昇し、価格は下がっていきますが、 メモリ間でのそれらの比例関係は非常に安定していると考えることができます。 メモリが階層構造を持つのは、そうした比例関係が一定であるからです。

最速のメモリだけを使ってすべてを構築することはできません。 あまりに高価なものになりすぎるからです。仮に高価でなかったとしても、 高速なメモリは揮発性です。つまり、電源を切ると、せっかくの成果が 失われてしまいます。したがって、コンピュータはハードディスクやその他の 非揮発性のストレージを内蔵して、電源を切った際にもデータを保持できる ようにしなければなりません。また、プロセッサの速度とディスクの速度との 間には、あまりに大きな違いがあります。その中間にある三つのレベルのメモリ 階層 (内部キャッシュ (internal cache)外部キャッシュ (external cache) およびメインメモリ) は、基本的に、両者のギャップを埋めるために存在しています。

Linux とその他の Unix には、仮想メモリと呼ばれる機能が備わっています。 仮想メモリとは、オペレーティングシステムが実際に搭載しているメインメモリ 以上のメモリを持っているかのように振舞うということを意味しています。 実際の物理メインメモリは、より大きな「仮想」メモリ空間の窓、もしくは キャッシュのように振る舞い、仮想メモリの大部分は実際にはスワップエリア と呼ばれるディスク上の領域に保持されます。ユーザプログラムからは見えない ところで、OS は、データブロックをメモリとディスクの間で移動させ、 この幻想を維持しています。その結果、仮想メモリは、実メモリよりも ずっと大きいが、それほど遅くはないメモリとして機能するわけです。

仮想メモリが物理メモリと比べてどの程度低速になるかというのは、 オペレーティングシステムのスワッピングアルゴリズムが、どれだけ プログラムによる仮想メモリの利用方法に適合したものになっている かということで決まります。幸なことに、一定の時間間隔で見ると、メモリの 読み出しと書き込みは間を置かずになされることが多いため、場所的に見た 場合でも、メモリの読み書きはメモリ空間内の特定の場所に集中するという 傾向があります。 この傾向は、ローカリティ (locality) 、もしくはより正式には リファレンスのローカリティ (locality of reference) と呼ばれています。 これは都合のいいことです。メモリへの参照 (reference) が仮想メモリ空間 内の様々な場所にランダムに行われるなら、通常は、新しい参照のたびごとに ディスクに対する読み出しや書き込みが行われなければならず、仮想メモリは ディスクと同じくらい低速になってしまうでしょう。しかし、プログラムと いうのは一定の場所で読み書きを行うという強い傾向 (locality) を 示すものなので、メモリへの参照がある場合でも、オペレーティングシステムは スワップを行うことが比較的すくなくて済みます。

これは、経験則なのですが、最大公約数的にみて最も効率のよいメモリ利用 パターンというのは非常にシンプルなものです。その方法は、LRU もしくは 最長時間未使用アルゴリズム ("least recently used" algorithm) と 呼ばれています。仮想メモリシステムは、必要に応じて、ディスクブロックを メモリの ワーキングセット (working set) として取り込みます。ワーキングセット 用の物理メモリが足りなくなったら、最長時間未使用のブロックをディスクに 書き出してしまいます。すべての Unix や、仮想メモリを使うその他の オペレーティングシステムの大部分は、この LRU にいくらかの変更を加えた アルゴリズムを使っています。

仮想メモリは、ディスクとプロセッサのスピードの違いを調整する第一の 連環となっています。これは、OS が明示的に管理しています。しかし、 物理メモリのスピードと、プロセッサがそのレジスタメモリにアクセスする スピードとの間には、まだ大きなギャップがあります。外部と内部のキャッシュ は、これを埋めるものであり、そのために上記で述べた仮想メモリとよく似た テクニックを使っています。

物理メインメモリがディスクスワップ領域に対する一連の窓やキャッシュのように 振る舞っているように、外部キャッシュもメインメモリに対する窓のように 振る舞います。外部キャッシュは、高速 (100M よりも速い 秒間 250M アクセス)で、 容量の小さいメモリです。ハードウェア (特に、コンピュータのメモリコントローラ) は、LRU の方法を使って、メインメモリから取ってきた一連のデータをもとにして、 外部キャッシュ内のデータを管理します。歴史的な理由で、キャッシュ スワッピングの単位は、ページ (page) ではなくライン (line) と呼ばれています。

しかし、これで話が終わったわけではありません。内部キャッシュが、 外部キャッシュの一部をさらにキャッシュすることで、アクセス速度の底上げの 最終段階を担当しています。この内部キャッシュは、さらに高速で容量の小さいメモリ です。事実、これはプロセッサチップのすぐ側に置かれています。

読者がプログラムを本当に速くしたいと思うなら、こうした細かい事柄を知って おくことが有益です。プログラムは、ローカリティが強いほど高速になります。 キャッシュがより効果的に働くからです。それゆえ、プログラムを速くする一番簡単な 方法は、プログラムを小さくすることです。プログラムが多くのディスク I/O の ために動きが鈍くなったり、ネットワークイベントを待ったりしなくても すむ場合、それは、通常、システム内で許容されている最大のキャッシュ効果を ともなったスピードで実行されるはずだからです。

プログラム全体を小さくできない場合は、スピードに関係する部分をチューニング するようにして、強いローカリティを発揮するようにすれば報われるでしょう。 そうしたチューニングに関するテクニックの詳細は、この文書の範疇を越えます。 読者がそれらを必要とする頃には、コンパイラにかなり精通しているはずなので、 そうした方法はおのずと理解できるはずです。

8.3. メモリ管理ユニット (memory management unit)

充分な容量のコアがあり、スワッピングを避けられるときでも、メモリ管理 (memory management) と呼ばれるオペレーティング システムの一部は、重要な役割を果たしています。確認しておきたいのは、 プログラムは自分のデータセグメントしか変更できないということです。 すなわち、あるプログラムの中の不具合のあるコードや悪意を持って作られた コードが、他のプログラムのデータセグメントにデータを吐き出すことは 出来ない仕組みになっているということです。これを実現するために、 メモリ管理機構では、データセグメントとコードセグメントの一覧が書かれた テーブルを保持しています。 このテーブルは、プロセスが追加のメモリ領域を要求したり、それまで使っていた メモリ領域を開放する(通常、これはプロセス終了時に起こります)たびに、 更新されるようになっています。

オペレーティングシステムのメモリ管理機構は、このテーブルを使って、 MMU もしくは メモリ管理ユニット (memory management unit) と呼ばれる、下位層のハードウェアにある特別な箇所にコマンドを渡しています。 現代のプロセッサチップには、複数の MMU が内蔵されています。 MMU は、メモリ領域を保護するための特別な機能を持っているので、越境的な メモリ参照は拒否されるとともに、その際には特殊な割り込みが発生するように なっています。

今までに、"Segmentation fault" や "core dumpd" といったメッセージを見た ことがあるなら、まさに、そうした越境的なメモリ参照が起こったということを 意味します。実行中のプログラムが自分以外のセグメントにメモリアクセス しようとすると、致命的な割り込みが起きるのです。これは、プログラムに バグがあることを意味しています。MMU が残す core dump は、プログラマがそのバグを追跡するのを支援するための 診断情報なのです。

プロセスの相互干渉の防止は、プロセスがアクセスできるメモリ領域を分離する こと以外に、さらに別の観点からもなされています。読者は、上記以外にも、 ファイルへのアクセス制御が出来るようにして、バグのあるプログラムや悪意を 持ってつくられたプログラムがシステムの重要ファイルを破壊できないように したいと思うことでしょう。 Unix が、ファイルパーミッションという 仕組みを持っているのは、このためです。これについては、後ほど説明します。