モダンオペレーティングシステム 第2版 -第4章- - 技術書で学んだことをひたすらアウトプットするページ

メモリ管理

メモリ管理が無い場合

スワッピングやページング、その他メモリ管理が無い状況では、プログラムの実行は1度に1つのみ可能。
新しいプログラムを実行するためには、その都度ディスクからメモリにコピーしてくる必要がある。

プログラムごとのメモリ割り当て

プログラムを複数実行するためにメモリをいくつかの領域に分け、必要とされるメモリ量に応じてプログラムにメモリを割り当てる。
メモリ割り当てとCPU使用率は互いに強く関係する。
複数のプログラムがメモリに割り当てられれば、プログラムがIO待ちの間に実行できるプログラムが多くなり、CPUを効率よく使用することができる。
しかし、複数のプログラムを同時に実行する（マルチプログラミングを行う）時には、以下の2つの問題を考えなくてはいけない。

再配置

プログラムを置くアドレスと、コンパイラが作成したコード内で指定されたアドレスの一致

保護

プログラムが使用しているメモリ領域に、別のプログラムが不必要にアクセスすることを防ぐ

メモリ管理

メモリの管理の仕方は、大きく分けて以下の2つ方法がある。

ビットマップ

数KBの範囲をメモリブロックとする。
使用/未使用の判断のためにそれぞれ1bit分用意し、全メモリ領域をビットマップで管理する。
連続した空き領域を見つける時に、時間がかかるのが欠点。

連結リスト

空きメモリと使用中のメモリをリスト化する。
リスト化により、メモリを割り当てる際のアルゴリズムに柔軟性がある。
メモリ割り当ての代表的な方法としては、以下の5つが挙げられる。

1. first fit
   必要なメモリ量を確保できる空き領域を見つけたら、即割り当てる。
2. next fit
   first fitで割り当てた次のノードからリスト走査を開始する。
   first fitよりも性能が落ちる。
3. best fit
   空いているリストの中で、必要なメモリ量を確保できる最も小さいサイズを選択する。
   性能はfirst fit/best fitよりも悪い。
   小さいホールができやすいために、逆にメモリ消費効率も悪い。
4. worst fit
   best fitの逆で、最も大きな空き領域に割り当てる。
5. quick fit
   頻繁に要求されるメモリサイズごとにリストを作成する。
   隣接領域を連続して割り当てる際に行われる可能性がある「マージ」に時間がかかる。

仮想メモリ

オーバレイ

プログラムを分割して分割した部分のプログラムの実行が終わると、別のプログラムを実行するためにディスクからプログラムをロードする一連の流れ。
プログラマに大きな負担がかかる。

仮想メモリ

ディスクへメモリの内容を退避すること（スワップアウト）、メモリの内容をディスクからメモリへ読み込むこと（スワップイン）をOSが行う。
プログラマはメモリの容量を意識せずプログラムを書き、実行ことができる。

ページ

仮想アドレス空間は、「ページ」と呼ばれる単位に分割される。
仮想メモリが物理メモリに対応する部分を「ページフレーム」という。
物理メモリに仮想ページが割り当ていることの判断は1bitのデータで行う。
プログラムが、仮想ページが物理メモリに割り当てられていないアドレスにアクセスした場合、「ページフォールト」が起こる。
ページフォールトが起こると、使われていないページをディスクへスワップアウトさせ、必要なデータをディスクからメモリへスワップインする。
ページ管理は「ページテーブル」で行われるが、ページ番号がページテーブルのindexとして使用されるので、ページサイズを2のべき乗にすれば、以下のような計算でページテーブルを高速に行うことができる。
( Page Size ) = 1 << ( Shift )
( Page Index ) = ( ( Memory Address ) & ( Page Size ) ) >> ( Shift )

マルチレベルページテーブル

割り当てられていない仮想メモリを含む、全てのページに対してページテーブルを用意すると、ページテーブルだけで多くのメモリを消費する。
そこで通常のOSの実装では、ページテーブルを複数段のテーブルに分ける「マルチレベルページテーブル」と呼ばれる方法を採用している。

ページテーブルの各エントリ

• ページフレーム番号
• 存在/不在bit
• 保護bit（アクセス権）
• 修正bit（dirty bit）
  スワップアウト時にwrite backするかしないかの判断に用いる。
• 参照bit
  スワップアウトするページを判断する時に用いる。
• キャッシング不可bit
  メモリマップドI/Oとして、ハードウェアデバイスがメモリアドレスの一部として割り当てている時にセットされる。
  キャッシュがオンになっていると、ハードウェアがデータを更新したにも関わらず、古いデータを取ってくる可能性がある。

TLB

ページテーブルは大きなメモリ領域を必要とするため、毎回メモリアクセスを行うと性能が劣化する。
ページテーブルを保存する専用のハードウェア「TLB（連想メモリ）」を載せ、頻繁にアクセスされるページを高速で取得できるようにする。
昔はハードウェアがTLBの管理を行っていたが、最近ではOSで管理をすることが多い。
目的のページテーブルがTLBに無ければ（TLBミス）、TLBフォールトを発生させてOSがその通知を受け取り、専用の処理を行う。

逆引きページテーブル

マルチレベルページテーブルを用いても、マシンの64bit化が進むと、ページテーブルの巨大化に対処する必要が出てくる。
そこで、ページフレーム1つにつき1つのページテーブルエントリとする方式とする、「逆引きページテーブル」が考えだされた。
逆引きページテーブルエントリには、以下の要素が含まれている。

• 割り当てられているプロセス
• 仮想ページ

逆引きページテーブルから実際の仮想メモリアドレスを導く方法は以下の通りである。
1.と2.の検索に時間がかかるので、実際はTLBを用いて高速化を行う。

1. 仮想アドレスをキーとして、ページフレームを値とするハッシュテーブルから目的のページフレームを探す
2. ページフレームを探す際に、エントリ内要素と自分自身のプロセスの一致を確認する
3. 仮想メモリを取得する

ページ置き換えアルゴリズム

ページ置き換えアルゴリズムは5種類あるが、最も良いとされるアルゴリズムは、LRUをもとにしたエージングと、ワーキングセットをもとにしたWS Clockである。

1. 最適ページ置き換えアルゴリズム
   [概要]
   最も近い将来使われるであろうページは、ページアウトしない。
   [問題点]
   将来使われるページを得ることは難しく、アルゴリズムの実現はできない。
2. NRUアルゴリズム
   [概要]
   読み出し/書き込み時にアクセスbitを1にする、書き込み時には修正bitを1にする。bitが1のものが多いほど、ページアウトの優先度を高くする。理解と実装が容易。
   [問題点]
   やや粗い。（性能的にはあまり期待できない。）
3. FIFOによるページ置き換えアルゴリズム
   [概要]
   スワップインされた時刻が最も古いページからページアウトする。
   [問題点]
   現在も使用しているページを追い出すことがある。
4. セカンドチャンス置き換えアルゴリズム
   [概要]
   NRUアルゴリズムで紹介したアクセスbitが、1であったらbitを0にしてFIFOの一番後ろに付け加える。0であったらページアウトさせる。3.の改良版
5. クロックページ置き換えアルゴリズム
   [概要]
   4.のFIFOをリングバッファにすることで、リスト内のノード間移動がなくなり、アルゴリズムとして性能が向上する。
6. LRUページ置き換えアルゴリズム
   [概要]
   最も長い間使われていなかったページをページアウトさせる。
   [問題点]
   スワップアウト時の追い出すページの検索と、使用中の印を書き込む処理のコストが高く、アルゴリズムの実現には専用のハードウェアが必要である。
7. LRUのソフトウェアによるシミュレーション
   [概要]
   6.をソフトウェアで実現。（NFUアルゴリズム）アクセスbitが1の時、ページごとにカウンタを増分させ、ページフォールト時に最小のカウンタ値をもつページをページアウトさせる。
   [問題点]
   各カウンタを初期化しないと、昔にカウントアップされたものがスワップアウトされることがなくなってしまうため、6.に比べて粗い。（対処法 : エージング）
8. ワーキングセットページ置き換えアルゴリズム
   [概要]
   プロセスが使用中のページセットを「ワーキングセット」と言い、「デマンドページング」によりプロセスが要求したページを取得することで、ワーキングセットに収まらなくなると、ページフォールトが多数おきてしまう。（スラッシング）このアルゴリズムでは、ワーキングセットに含まれないページ（アクセスbitが0かつ、最後に使用された時間が現在の時間より一定時間以上離れているもの）を追い出す。
   [問題点]
   実現にコストがかかる。
9. WS Clockページ置き換えアルゴリズム
   [概要]
   5.と8.を組み合わせたアルゴリズムで、効率が良い。

Beladyの異常振る舞い

ページ数が増加した時、ページフォールト数も増加することを「Beladyの異常振る舞い」という。

スタックアルゴリズム

新しいページが割り当てられると、ページ番号の配列に割り当てたページ番号が無ければ、配列の一番先頭にページ番号を置く。
配列に既にある場合は、配列の一番先頭に移動する。
スタックアルゴリズムに置いて、配列の先頭から目的の特定のページ番号までの距離の列（「距離列」という）を用いることで、ページフレーム数とページフォールトが起きた回数の関係を得ることができる。

プロセスへのメモリを割り当て

1. 局所的方法

プロセスごとに固定量のページを割り当てる。

1. 大局的方法

全メモリ空間でプロセスごとに割り当て数を管理する。
「PFFアルゴリズム」と呼ばれる方法を用いて、ページフォールト数が多すぎる場合はプロセスに割り当てるページ数を増やし、少なすぎる場合はプロセスに割り当てるページ数を減らす。
ただし、全てのプロセスの要求するメモリを確保できる訳ではないので、特定のプロセスを犠牲にする必要がある。

1. その他割り当て方法

• 常に古いページがないか確認するデーモンを走らせ、古いページをpoolに置いておき、必要になったらpoolから取得することでページ取得時の性能向上をはかる。
• 高速なメッセージ通信でよく使われるプロセス間でのメモリ共有では、カーネル内でのメモリコピー処理が無いため、高いスループットを出すことができる。

ページサイズの決め方

ページサイズが大きいと「内部フラグメンテーション」が起こり、メモリの未使用領域が増えて非効率である。
メモリサイズが小さいと連続していないページをスワップアウトさせる場合に、ディスクのシーク時間がかかる。また、ページテーブルのサイズも増大する。

ページ用途別に割り当て方法を分ける

ページを割り当てる時、プログラムテキストとデータを別々に割り当てることも可能である。
例えば、UNIXでfork()システムコールを発行した後、親と子のプログラムテキストとデータを共有させ、メモリを節約することができる。
もし子プロセスから書き込み要求があった時には、ページをコピーすればよい。（コピーオンライトという）

OSがページングに関与するケース

1. プロセス生成
   ページテーブルの割り当て
2. プロセス実行
   スケジュール時にTLBフラッシュ
3. ページフォールト
   要求されたページを新たなページフレームに入れる
4. プロセス終了
   ページ・ページテーブル・スワップアウトされたものを捨てる

例：3.のページフォールト時には、OSは以下のことを行う。（実際には1命令が複数のページにまたがっていたり、CPUによってプログラムカウンタなどの振る舞いが異なるため、上記の処理を実現することは難しい。）

1. プログラムカウンタをスタック上に保存
2. 汎用レジスタの保存
3. 必要な仮想アドレスのアクセス正当性の確認
4. 3.で見つけたページがdirtyならディスクへWrite Backを行い、書き込みの間に別プロセスに実行権を与える
5. 必要なページの読み込みを行い、読み込みの間に別プロセスに実行権を与える
6. ページテーブルの更新
7. 1.2.で保存しておいたレジスタなどを保存
8. プロセスをスケジュールし、実行権が与えられたらプログラム実行再開