CSAPP 第9章 仮想メモリ
bayamasa仮想メモリは仮想的なアドレス空間をCPU側で用意してあげる事によって、物理アドレスの容量よりも効率よくデータを格納したり、取り出したりすることができる仕組みである。
bayamasaMMU メモリ管理ユニット
CPUは物理アドレスの使用可能アドレスなどを知らなくてもよい。
CPU側は常に仮想アドレス(VA)に対して、通信を行う。
ここからMMUと呼ばれるメモリ管理ユニットが仮想アドレス→物理アドレスに変換する。
そうすることでメモリ自体も仮想アドレスのことを考えることなくデータを物理アドレスとして扱う事が出る。
bayamasa仮想メモリ(記憶)とは
主記憶と二次記憶のメモリ階層を「巨大な主記憶」として使えるように透過性をもたせたもの
つまりDRAMとDiskを一つの記憶領域としてCPU側に認識させることで、特別な操作をせずともCPU側はデータにアクセスすることができる。
bayamasaDRAMはキャッシュ階層的にディスクのデータをキャッシュする。
アクセス速度の比較として、CPU→SRAMのアクセス速度を1とすると、以下のような速度
SRAM : 1倍
DRAM : 10倍遅い
Disk : 100000倍遅い
DRAM→Diskに対しての通信はなるべく少ないほうがよい。
よってキャッシュミスを最小限にする、フルアソシアティブを採用。
置換アルゴリズムもより洗練されたものを使用している。
書き込み形式もライトスルーではなく、ライトバックを用いている。
bayamasaSSDだとまた別
bayamasaページテーブル
キャッシュと同様に、どこに該当のデータがあるか検索するためのテーブル。
もし該当しない場合はDiskからDRAMにデータを移す作業などが必要となる。
PTE(ページテーブルエントリ)はバリッドビットを持ち、これは値がDRAMにキャッシュされているかどうかを判定するためのビットとなる。
バリッドビットがfalseの場合は、値が存在しない/Disk側に値が存在するということになる。
bayamasaページテーブルはDRAM上に存在する
bayamasaページフォールト
CPUが参照したいデータをPTEに見に行くとき、もしそのページがDRAMではなくDiskに存在するとする。
その場合、カーネルはページフォールトを発生させ、例外ハンドラを呼び出す。
この処理でDRAMを参照して、もしDRAMがいっぱいの場合はどこかのアドレスとCPUが参照したいデータを交換する処理を行う。
これによっと交換が成立した際には、フォールト処理を完了して元の処理に戻り正常にプログラムを動かす事ができる。
bayamasaSRAMでのスワッピング(キャッシュミスによるデータの交換)はDRAMではページングと呼ぶ。
bayamasaページテーブルはプロセス毎に存在し、同じ基本フォーマットを持つ。
例えば、ページテーブルは必ず0x400000から始まる。
これによりリンカが実行可能ファイルを作成する際に、ページテーブルテーブルの構成を毎回確認することなく、実行ファイルを作成できるという利点がある。
bayamasaなるべく他のデバイスへのアクセスはセキュアでなくてはいけない。
PTEはプロセス毎に作成されたテーブル内の情報として、パーミッションビットを付与する。
これはいくつかの権限をビットで持つ。
各アドレスに対してそれぞれの権限を持つ、supervisor(kernel modeのみ有効か), read, write。
操作がこれらに該当しない場合、MMUはsegvを送信する
bayamasaTLB
トランスレーション・ルックアサイド・バッファ
CPUが仮想アドレスを生成するときは、毎回MMUがPTEを参照しないといけない。
これによりメモリへのアクセスが処理のオーバーヘッドになってしまう。
TLBと呼ばれるPTEのキャッシュを用いてそれを防ぐ。
TLBはMMU内の物理プロセッサであり、高速に動作する。
bayamasaコピーオンライト
書き込み付加のパーミッションを持っている、プライベート・オブジェクトを他のプロセスから書き込みを行うときに最初から物理メモリの他の部分にコピーするのではなく、書き込み命令のタイミングでコピーをすることで命令を省略できる
bayamasa動的メモリの確保において、カーネルは各々のプロセスについて変数brk(break)を管理する。
bayamasaガーベジコレクション
ヒープ領域において、使われなくなったブロックを自動的にfreeするプログラム。
bayamasamalloc
C言語でメモリをアロケーションするための関数
アライメントはコンパイルのオプションによって定められる。
mallocが返すアドレスは32bitなら8の倍数となり、64bitなら16の倍数となる。
bayamasamallocは問題に遭遇すると、NULLを返してerrnoを設定する。
bayamasamallocの抱える課題はスループットと使用効率である。
スループットはmallocの速度
使用効率とはmallocが使える領域がどれだけあるかということ
どちらかを犠牲すればどちらかが立つため、バランス感覚をどこにするかが大事になってくる
bayamasa断片化(フラグメンテーション)
ヒープ利用率が悪化する。
内部断片化
mallocで確保した領域よりも、使用している領域の方が少ないときに現れる。
例えばmalloc(5)として確保した領域に対して、3文字の文字列を割り当てた場合、1文字ないし2文字分の余りが存在する。
これをし続けることによりヒープ効率が悪化して、ヒープが逼迫してしまう。
外部断片化
例えばmalloc(4)としたときに、ヒープ領域にまだ4ワード残っているにも関わらず、そのメモリ領域が隣接していないので、使用できない時に外部断片化が起こっているという。
bayamasamallocするメモリには、ステータスビットが存在し
ステータスとしてfree済みかどうかなどを持っている。
これでヒープ領域における割当済みかそうでないか、などを管理している。
bayamasasbrk
引数にintptr_tをとり、カーネルのbrkにincrを足すことでヒープの伸び縮みを
行う事ができる。
bayamasamallocにおける配置方針
mallocは指定されたサイズに応じて適切はフリーブロックをヒープ領域から探す。
そのアルゴリズムは複数存在する
- ファーストフィット
要するに頭から全探索 - ネクストフィット
前回の検索が終わった部分から始める - ベストフィット
よしなにやる
bayamasafreeの融合
一度mallocした値をfreeすることで、ブロックヘッダが残ったままになる。
これによりfreeしたブロックは断片的になり、再利用が難しくなる場合がある。
これに対応したのが、融合である。
隣接するfree済みのブロックを融合してフリーブロックのサイズを拡張する
方法
- 即時融合
メモリ解放時に隣接部分に対してフリーブロックが存在するのであれば、融合する - 遅延融合
フリーブロックが必要になったタイミングで融合する
bayamasa境界タグ
融合の際のアルゴリズムとして、ヘッダを用いた方法がある。
ヘッダにそのメモリがfree済みかどうかが記載されているので、ヘッダをみることで次の値を融合できるかどうかを知ることができる。
しかしそれだと融合できるか判断できるメモリが対象のメモリの後のメモリのみになってしまう。
なぜなら前のメモリのヘッダがどのヒープの位置にあるかは対象メモリからは判断できないからである。
そのため境界タグというフッターに対してもfree済みかどうかの情報を付与することで、対象のメモリから前のメモリに対しても検索を行う
bayamasaGC
マークフェーズ
スイープフェーズ
GCはゴミを集めるときに、まずゴミを認識する必要がある。
まず、ゴミ＝使っていない割当ブロックをどうやって探すかというと、ノードから到達可能かという部分で探していく。
現在使用しているデータをルートノードとして、その中で使用しているポインタを入れ子式にたどっていき、最終まで到達させることで使用している割当プログラムを検知する。
もし、割当済みブロックで到達不可能なものがあった場合、それはゴミ(現在のプログラムで使用していない割り当て済みブロック)であると認識するのでfreeを行う。
- マークフェーズ
先程のノード探索によって割り当て済みかつ使用済みのブロックに対して、マークを付ける。 - スイープフェーズ
マークがついていないブロックに対してfreeを行う
bayamasaC言語はメモリに対して型情報つけない。
これにより、ノード探索においてあるメモリに存在する値がメモリなのか、単なるintなどの数値なのかが判断できない。
これによってもしintの値がたまたまheap領域に存在するポインタの値と同一だった場合、ノード探索でそのポインタの値を見に行ってしまい、ゴミなのにマークしてしまうという危険性がある
そのため、C言語はより保守的なマーク・アンド・スイープのプログラムを記述する必要がある