第9章 仮想メモリ

9章について
この章では、メモリマッピングの手法や、アドレス変換の流れ、アロケータの仕組みなど仮想メモリについて説明されていました。
あらゆるシステム設計において中心的存在である仮想メモリについて学ぶことができます。
以下まとめです。

仮想メモリの特徴

仮想メモリはアクティブな領域のみを主記憶に保持して、必要に応じてディスクとメモリ間のデータ転送を繰り返す。
また各プロセスに一様なアドレス空間を提供することでメモリ管理を簡単にする。
アドレス空間が他のプロセスによって破損するのを防いでくれるといった特徴もある。

物理アドレシング : 初期のPCで使用されていた手法。単純な構成。

仮想アドレシング : CPU は仮想アドレスを生成して主記憶をアクセスし、主記憶に送られる前に適切な物理アドレスへ変換する。

キャッシュの構成

SRAMキャッシュ : CPU と主記憶との間に位置する L1, L2, L3 キャッシュ。

DRAMキャッシュ : 主記憶内に下層ページを保持する VM システムのキャッシュ。SRAM と比べて 10倍は遅い。

SRAM に比べて DRAM キャッシュにおけるキャッシュ･ミスに時間がかかる理由はディスクかにアクセスする必要があるから。

ページ･テーブル

アドレス変換ハードウェアは、仮想アドレスを物理アドレスに変換するたびにページ･テーブルをリードする。
ページ･テーブルは、ページ･テーブル･エントリ(PTE)の配列のこと。

仮想アドレス空間内の各ページは、ページ･テーブル内で決まったオフセットに位置する一つの PTE を持つ。

ページ･ヒット : アドレス変換ハードウェアは、PTE の場所を特定しインデクスとして仮想アドレスを使用する。

ページ･フォールト : DRAM のキャッシュ･ミスのこと。

アドレス変換

仮想アドレス空間と物理アドレス空間との間のマッピングのこと。
仮想アドレスは、 仮想ページ･オフセットと仮想ページ番号から構成される。
変換を行うことで、プログラム内ではアドレスを連続的に使用できるようになる。

メモリ･マッピング

Lnux が仮想メモリ領域を初期化する場合、その領域をディスク上のオブジェクトに関連付けることで初期化を行う。

メモリ領域は、通常ファイルか匿名ファイルのどちらかにマップされる。

• 通常ファイル : マップされるファイルの領域はページ･サイズの大きさに分割され、仮想ページの内容は、分割された各ファイルの内容で初期化される。

• 匿名ファイル : 匿名ファイルはカーネルによって作られ、その内容はゼロで初期化されている。

どちらの場合も、一度仮想ページが初期化されればカーネルが保持しているスワップ･ファイルとの間でスワップ･イン、スワップアウトされる。

Linux の仮想メモリ･システム

Linux は仮想メモリを領域 (セグメント)の集まりとして構成する。
コード、データ、ヘッド、共有ライブラリ、ユーザ･スタックはすべて異なる領域にある。
またどの領域にも属さない仮想ページは存在しないので参照できない。

共有オブジェクト

仮想アドレス空間にマップされた共有オブジェクトに書き込みを行うと、同じ共有オブジェクトを仮想メモリにマップしている他のプロセスにもその書き込み結果が見える。
そのため複数の共有領域にマップされていても共有オブジェクトのコピーは一つしか物理メモリ上に保持する必要はない。

コピー･オン･ライト

プライベート･オブジェクトを仮想メモリにマップする場合に使う。
スタート時点では、プライベート･オブジェクトも共有オブジェクトとまったく同じようにマップされている。

例外が発生した場合、書き込み対象となったページを物理メモリ上に新しくコピーして、そのページを指すように変更する。

(例) fork で子プロセスを生成する場合
どちらかのプロセスに書き込みを行うまでは、子プロセスは、親プロセスのコピーそのもの。
書き込みを行ったときに新しいページが作られる。

動的メモリ･アロケータ

ブロック

アロケータはヒープをさまざまなサイズのブロックの集合として扱う。
ブロックは、割り当て済かフリーのいずれかである仮想メモリの連続したチャンク(塊)である。
フリー･ブロックは、アプリケーションによって明示的に割り当てされるまでは、フリーの状態のまま。

明示的なアロケータ : アプリケーションが割り当て済ブロックをすべて明示的にフリーにする必要がある。malloc で確保した領域を free で解放する。
暗黙のアロケータ : 使われなくなったブロックを自動的にフリーにする手続きは、ガーベジ･コレクションとよばれる。

malloc

malloc は、指定されたサイズバイトのメモリ･ブロックへのポインタを返す。
ブロックのアドレスは、32ビット･モードでは 8の倍数、64ビット･モードでは 16の倍数となる。

free

割り当てたヒープのブロックを解放する。
引数で与えられるポインタは、割り当てしたブロックの先頭を指していなければならない。

アロケータの目標

• 要求にかかる時間を高速にする: 割り当てと解放の要求を満たすのにかかる平均時間を最小にすることで、スループットを最大にできる。

• メモリの使用効率を最大にする : 割り当て可能な仮想メモリの量は、ディスク上のスワップ領域の総量に制限される。

ヒープ利用率を犠牲にしてスループットを最大にするのは、容易に行えるのでそのバランスを取るのが難しい。

断片化(フラグメンテーション)

ヒープ利用率の悪化の第一の原因は、断片化と呼ばれる現象で未使用のメモリが利用できなくなる。

内部断片化

割り当てされたブロックが、データを格納する場所よりも大きい場合に起きる。
(例) malloc(10)に対して、データを3バイト分しか格納しない場合、 7バイトが内部断片化する。

外部断片化

利用可能なメモリの総和は十分にあるのに、連続していないため要求を満たせない場合に起きる。

0:フリー･ブロック
1:割り当て済
*:ポインタの位置

0000000000000 # ヒープ領域
*
1110000000000 # p1 = malloc(3)
*  *
1112222200000 # p2 = malloc(5)
*  *    *
1112222233330 # p3 = malloc(4)
*       *
1110000033330 # free(p2)
*  *    *
1114400033330 # p4 = malloc(2)

上記の場合最終的にメモリの総和は 4 バイトあるが連続している領域が最大で 3 バイトなので、3 バイトまでしか割り当てられない。
外部断片化は、未来の要求パタンにも依存するため予測が難しい。

アロケータ

アロケータは、ブロックの境界を区別したり、割り当てされたブロックとフリー･ブロックを区別するための何らかのデータ構造を必要とする。

アロケータのデータ構造は、1 つのブロックは 1 ワードのヘッダ、ペイロード、パティングから構成される。

暗黙のフリー･リスト

ヒープの構成のこと。連続した割り当て済ブロックとフリー･ブロックの連なりとして構成できる。

利点 : 実装が単純であること。
欠点 : 割り当て済ブロックの特定にかかるコストがかかること。

明示的なフリー･リスト

双方向連結リストを使うと、ファースト･フィットの割り当て時間が｢ブロック総数に比例｣から｢フリー･ブロックの数に比例｣に減る。

ガーベジコレクション

動的なストレージのアロケータで、プログラムから必要とされなくなった割り当て済ブロックを自動的に解放する。

メモリを有向グラフと考え、ルート･ノードから到達不能なブロックは、｢ごみ｣として扱う。
到達可能なグラフに何かの表現を与え、定期的に到達不能なノードを解放して、それらをフリー･リストに戻すことで回収する。

メモリ･リーク

割り当てしたブロックを解放するのを忘れて、ヒープにごみを作ってしまうこと。
leak が頻繁に呼ばれると、ヒープがごみでいっぱいになり、最悪の場合、仮想アドレス空間をすべて消費してしまう。

感想

これまでの章に比べてかなり難しかったです。。
その分重要だとも思うので、練習問題などを用いて復習してみようと思います。
個人的には、コピーオンライトの仕組みが好きでした。