Linuxのメモリ管理について

参考書籍: 詳解Linuxカーネル第3版

メモリ

物理メモリ
- 領域にはアドレスがある
仮想メモリ(OS管理)
- 物理メモリとは異なる管理方法で、異なるアドレスを持つ
RAMは4KB、8KBなどの大きさのページフレームに分割される
仮想アドレスと物理アドレスを紐付けるために、ページテーブルを導入する
RAMの用途
- バッファ、ディスクリプタなどカーネルデータに関するもの。カーネルからの要求を満たす
- メモリ領域、メモリマッピングに関するのもの。プロセスからの要求を満たす
- キャッシュとして利用する。ディスクなどバッファリングされるデバイスの性能改善のために利用する
MMU(memory management unit)
- 物理メモリアドレスと仮想メモリアドレスの変換をする
課題
- メモリ回収
  - 経験則にもとづくアルゴリズム
- メモリの断片化（memory fragmentation）
  - 理想的には、メモリの要求に失敗するのは空きページフレーム数が足りないときがよい
  - しかし、カーネルは物理的に連続したメモリ領域の使用を強制されることがある（どういう場合？）。全体としてはメモリ空き容量があるにもかかわらず、1つの連続した部分として利用できないため失敗する
プロセスのアドレス空間には、プロセスが参照可能なすべての仮想アドレスが含まれている
- TODO: プロセスごとに仮想アドレスをわりあてで合ってるか？
カーネルは、プロセスの仮想アドレス空間を memory region discriptor のリストとして保存している。
- プロセスがexec()系のシステムコール経由で何らかのプログラムの実行を開始すると、カーネルはそのプロセスに、以下の内容から形成される仮想アドレス空間を割り当てる:
  - プログラムの実行可能なコード
  - プログラムの初期値有りのデータ
  - プログラムの初期値無しのデータ
  - 最初のプログラムスタック
    - TODO: プログラムスタックとは何か？
  - 必要となる共有ライブラリの実行コードとデータ
  - ヒープ（プログラムにより動的に要求されるメモリ）
demand paging
- プロセスは自分のページを物理メモリには1つも持たない状態でプログラムの実行を開始することができる。以下のような処理となる:
  - プロセスが存在しないページにアクセスしようとすると、MMU(memory management unit)が例外を発生させる。例外ハンドラは、対象のメモリ領域を探し出し、空きページを割り当て、適切なデータでそのページを初期化する
  - 同様に、カーネルがmalloc()または、malloc()が内部的に呼び出すbrk()を使ってメモリを動的に要求する際、カーネルは物理的なメモリ領域の確保は行わずに、単にプロセスのヒープ領域の大きさを更新するのみとなる
    - TODO: 逆にカーネルが物理的なメモリ領域の確保を行うタイミングはどこか？
  - ページフレームがプロセスに割当てられるのは、仮想アドレスを参照しようとして例外が発生したときだけ
  - コピーオンライト（fork()したときに、親か子のどちらかがページに書き込む必要が生じるまで、ページの複製を可能な限り遅延させる。プロセス生成時に時間がかかってしまうことを防ぐため）も、仮想アドレス空間で利用されている。新しいプロセスが生成されると、カーネルは親プロセスのページフレームを子プロセスのアドレス空間に読み取り専用で割当てる。親または子プロセスがページの内容を変更しようとすると、例外が発生する。例外ハンドラは、例外を発生させたプロセスに新しいページフレームを割り当て、元のページの内容で初期化する。

Linux のメモリー管理(メモリ－が足りない？,メモリーリークの検出/防止)(Kodama’s tips page)

ディスクキャッシュ

ハードディスクドライブはRAMより非常に高速であり、ディスクアクセスがボトルネックになることが少なくない
空いている物理メモリをディスクのキャッシュとして利用することができる
- ディスクから読み込んだブロックに対応するディスクバッファをRAMに残しておくことにより、実際のディスクへの書き込みをできるだけ先延ばしにする
- プロセスがディスクアクセスを要求すると、カーネルはメモリのディスクキャッシュ上にデータがないか調べる。キャッシュにヒットすれば、カーネルはディスクを操作することなく高速にプロセスの要求に答えることができる
- sync()は、対応するディスクブロックとは内容が異なるすべてのバッファをディスクをに書き込むことで、強制的にメモリ上のディスクキャッシュとディスクとの同期をとる。データの同期は定期的に実行される。

メモリアドレッシング

プログラマはメモリアドレスを参照することで、メモリの内容にアクセスする。80x86プロセッサの場合は、メモリアドレスには以下の3種類がある:
- 論理アドレス: マシン語命令において、オペランドや命令のアドレスを指定するときに使用するアドレス
- リニアアドレス: 仮想アドレス。32ビットの符号なし整数で表現する。16進数で表現し、0x00000000から0xffffffffまでの値をとる。
- 物理アドレス: メモリチップ内のメモリセルを指定する際に使用する。メモリセルの指定とは、プロセッサのアドレスピンを通じて、電気信号をメモリバスに送ることをいいます。物理アドレスは32ビットまたは36ビットの符号なし整数で表現します。
MMUは、セグメンテーション回路というハードウェアを使って、論理アドレスをリニアアドレスに変換します。その後、ページング回路を用いて、リニアアドレスを物理アドレスに変換します。
- 論理アドレス -> <セグメンテーション回路> -> リニアアドレス -> <ページング回路> -> 物理アドレス

CPUとメモリ

マルチプロセッサシステムは、通常、すべてのCPUが同じメモリを共有する。RAMチップへ別のCPUから同時にアクセスする可能性がある。しかし、RAMチップへの読み書き操作は逐次に行う必要があり、バス（）とすべてのRAMチップの間に調停回路(memory arbiter)を備えている
- memory arbiterは、CPUからRAMチップにアクセスしようとしたとき、他のCPUが使っていなければそのCPUに使用権を与え、他のCPUが使用中であれば、そのCPUを待たせる
単一プロセッサの場合はもDMA（Direct Memory Access）Controllerが存在するためmemory ariterを使う
- 昔は、RAMの読み書きをするにはCPUがバスマスタの役割を果たさなければいけなかった。I/Oデバイスとメモリ間のデータ転送にはCPUが介する必要があった。そのため、I/Oデバイスとメモリ間のデータ転送中はCPUは待たされた
- 最近は、DMAによって、上記の待ち問題は解消されている。PCIバスでは、周辺機器に必要な回路が備わっていれば、周辺機器自身がバスマスタとして動作できる。最近のPCにはDMA補助回路が備わっており、この回路によってRAMとI/Oデバイス間でデータを転送することができる。CPUが1度DMA回路を駆動すると、CPUとは独立してデータを転送する。データ転送が完了したら、割り込み要求を発行してCPUに知らせる。CPUとDMAの両方が同時に同じメモリ位置にアクセスする場合は、memory arbiterが衝突を解消する
  - DMAはディスクドライバなど、転送するデータが多い処理に利用される。DMAの準備には比較的時間がかかるため、小さなデータの転送にはCPUががデータ転送したほうが速い
- CPUはDMA命令を実行する

ページキャッシュ

ページキャッシュとは、Linuxカーネルが使う中心的なディスクキャッシュ
カーネルは、ディスクとの読み書き両方においてページキャッシュを参照する。書き込みの場合は、カーネルがページキャッシュに保存されたデータをディスクに対して遅延書き込みとして実行する
ただし、O_DIRECTフラグを指定してファイルをオープンすると、ディスクキャッシュは利用されない

dirty cacheのディスクへの書き込み

プロセスが何らかのデータを更新した場合は、必ず対応するページにPG_dirtyフラグを設定する
dirtyなページキャッシュのディスクへの書き込みを遅延させることで、システムの性能を著しく向上させることができる。書き込み頻度を減らせるし、書き込み操作を遅延させても読み取り操作ほど他の処理に悪影響を与えない（読み取りが遅延されるとプロセスが休止してしまうが、書き込みの遅延はプロセスを休止させることがない）
- TODO: プログラムの実行は、読み→何かの処理がほとんどで、書き→何かの処理が少ないから？
dirtyなページを長時間残しておくと問題がある（電源障害でRAMの内容を復旧できない、ページキャッシュを置くためのRAMの量が膨大になる）ため、カーネルは以下の条件が成り立つとdirtyなページをディスクへ書き戻す
- 「ページキャッシュの空きがほとんどない」、かつ「より多くのページが必要な場合」あるいは「dirtyなページの数が多すぎる場合」
- ページがdirtyになってから長期間たった場合
- プロセスが、ブロック型デバイスまたは特定のファイルのすべての保留中の変更を書き戻すように要求した場合。
  - sync(), fsync(), fdatasync()

ページフレームの回収

カーネルは利用可能なメモリを最大限使う。メモリキャッシュもディスクキャッシュも、ページフレームをどんどん使うが、それを開放しない。キャッシュ機構は、いつプロセスがキャッシュしたデータを使うか、あるいは使わなくなるかわからないため、どの程度のキャッシュを開放すべきか決められない
PFRA(Page Frame Reclamation Algorithm)は、ユーザモードプロセスとカーネルのキャッシュの両方からページフレームをこっそり盗み（※ PFRAが特に通知なしでページフレームを取得することだと思われる）、バディ・システムの空きブロックのリストに追加する
PFRAはページを以下のように区別する:
- 回収不能
  - 回収不能、あるいは回収不要なページフレーム
- スワップ可能
  - ユーザモードアドレス空間にある無名ページ、tmpfsファイルシステムにマッピングしているページ。ページ内容をスワップ領域に保存して回収する
    - TODO: 無名ページ
    - TODO: tmpfsファイルシステム
- 同期可能
  - ユーザモードアドレス空間にマッピングしているページ、ページキャッシュ内のページでディスク上のファイルのデータを含むもの、ブロック型デバイスのバッファページ、ディスクキャッシュのページ
  - 必要なら、ページとディスクの状態を同期する（sync()?）
- 破棄可能
  - メモリキャッシュ内の使用していないページ
  - 何もしない
    - TODO: 回収はどのようにされるのか？
メモリが不足している場合、あるいは他のメモリ割り当て要求がきた場合に、try_to_free_pages()を呼ぶ
- try_to_free_pages()は、shrink_caches(), shrink_slab()を繰り返し呼んで少なくとも32個のページフレームを開放しようとする
  - shrink_caches(), shrink_slab()を実行するたびに優先度（最初は12，最低）をあげて実行し、最終的に0（最高の優先度）になった段階でページフレームが32個確保できなかった場合は、PFRAは最終手段としてどれか1つのプロセスを強制終了し、そのページフレームを開放する。この処理はout_of_memory()関数が実行する
    - メモリを使い切り、ページフレームの開放にも失敗し続けるとプロセスが落とされる

ページフレームの定期回収

メモリ割り当て要求は、割り込み処理や例外処理中に起こることもある。この場合、ページフレームを開放するまでcurrent processの実行を中断できない。また、メモリ割り当て要求が、クリティカル資源への排他的アクセスを行っているカーネル実行パスから行われることもある。この場合はI/Oデータ転送を行うことができない。これらのメモリ割り当て要求が発生すると、カーネルはメモリを開放できない
- TODO: クリティカル資源への排他的アクセスを行っているカーネル実行パスから行われることもある。この場合はI/Oデータ転送を行うことができない わからない
kswapd
- カーネルスレッド。定期的にshrink_zone(), shrink_slab()を呼び出し、LRUリスト（最長不使用順リスト。Last Recently Used List. アクティブリスト、非アクティブリストがあり、ページの回収は非アクティブリストから行われる）からページを回収する

スワップ処理

TODO: スワップ処理

OOMキラー

PFRAが一定の空きページフレームを保持しようとするにもかかわらず、メモリ負荷が高くなり、利用できるメモリを使い果たしてしまうとシステムは急停止することになる。このようなひどい自体に対処するため、PFRAはOOMキラー（Out Of Memory Killer）という機構を使う
out_of_memory()が呼ばれると、select_bad_process()を使って選びだしたプロセスを、oom_kill_process()を呼び出して終了させ、メモリを回収する
select_bad_process()は以下のような要求を満たすプロセスを選出する
- 仕事量が少ない。何日も動作し続けているプロセスを殺すのはよくない
- 低い優先度で稼働している
- ルート権限で稼働していない。ルート権限で動作しているプロセスを急に殺すと、ハードウェアが予期しない状態に陥る恐れがある
- swapperプロセス（プロセスID0），initプロセス（プロセスID1）、その他カーネルスレッドではない