メモリ管理

今の CPU ではメモリ管理ユニット(Memory Management Unit)でメモリが管理されていることが多い。

昔は物理メモリがそのままアドレスに割り当てられていて、そのまま使うことができた。

現代では論理メモリ空間に物理メモリをページ単位で割り当てるようになっている。これはページングと呼ばれる。

これにより

物理メモリが少なくても、実際には使っていない物理メモリの内容をストレージに追い出して、再利用することで、論理メモリとして大量に使うことができるようになった。これはスワップと呼ばれる。

プロセス空間として論理メモリ空間を分離することで、別プロセスのメモリ空間を破壊するようなことがなくなった。

ファイル自体を論理メモリにマッピングすることで、実際にアクセスする範囲を自動ロード、セーブできるようになった。これはファイルマッピングと呼ばれる。これはプロセス間で共有することもできる。

特定のプロセス間のみで同じ物理メモリを(場合によっては異なるアドレスで)共有することができるようになった。これは共有メモリと呼ばれる。

また、ページ毎に読み込み/書き込み/実行の制約をすることができるようになった。

読み込み専用のデータ領域に書き込むような不正な事がなくなる。

データ領域を実行するような不正な事がなくなる。

プログラム領域を書き換えるような不正な事がなくなる。(元々自己書き換え型のプログラムの場合には注意が必要)

OS はこの論理メモリと物理メモリの管理をする必要がある。

マルチプロセッサではバスの競合が発生する。1つのバスには同時に1つのデータしか載せられない。

これを解決するために、NUMA と呼ばれる構成が発明された。

NUMA ではCPUのコアごとに分割された物理メモリとバスが割り当てられる。

分割された別の物理メモリに対してはリモートアクセスとしてCPU間で通信する。このためこれは通常のメモリアクセスに比べると遅くなる。

メモリは実際にその場で存在しないと困るもの(すぐさまアクセスされることが約束されているもの)と、遅い外部記憶装置を補うためのキャッシュとして使用される。

アプリケーション内部で使うキャッシュは宣言しない限り区別できない。

どう管理するか?

NUMA 構成かどうかを確認して、物理メモリマップを用意する。

NUMA の場合、リモートアクセスが発生しにくいように設計する。

プロセスごとに論理メモリページのツリーを用意する。

なぜツリーか?

64bit(16EB)ものメモリ空間を最終的には4KB単位で管理するように設計されているため。(AMD64)

それでも余りに大きすぎるため、実際にはせいぜい256TB(48bit)くらいまでの領域が使われる。

少なくとも、すべてのプロセスから参照されなくなった物理メモリページは回収する必要がある。

複数のプロセスから同じ物理ページが参照された方がいい場合がある。

あるプロセスが物理メモリページを書き換えようとした場合には、その時に別の物理メモリページにコピーして、そのコピーの方を書き換えさせるようにする。(Copy-on-write)

長期間参照されない物理メモリページは外部記憶装置に吐き出して物理メモリページを回収して再利用した方がよい。(いわゆるスワップ)

メモリはどう使われるのか?

あらかじめ必要なサイズが分かっているケースと分からないケースとがある。

集中して使われる所とほとんど使われない所とがある。

高速化が必要なところとそうでない所とがある。

捨てても構わないところとそうでない所とがある。

使うサイズが小さなサイズと巨大サイズとがある。

以下を分けて管理したい

必要性

絶対に必要なメモリ

余っていれば欲しいけど、必須ではないメモリ。(キャッシュなどのため)

速度

早ければ早いほどよい

遅くても構わないがメモリアクセスの形を取りたい

サイズ

サイズ拡張の必要性

期待する最大サイズ

スレッド間での共有

プロセス間での共有

ファイルマップ

書き込みの必要性

メモリの多重管理問題をなんとかしたい

メモリはあちこちで管理されている。

OS

言語ライブラリ

アプリケーション

メモリの管理はなぜ難しいのか?

巨大サイズから小さなサイズまで要求されるサイズがバラバラ。

いつ確保、解放されるかが分からない。

領域確保と解放を繰り返すと空き領域がフラグメント化(fragment)する。(フラグメンテーション, fragmentation)

予備的に確保しても、使われないと空間効率が悪くなる。

全部解放されず、ごく一部解放されるというのを繰り返されるとスカスカになる。

複雑な管理をすると管理情報が大きくなりやすい。

メモリの利用効率が下がる。

管理自体のパフォーマンスが問題になる。

論理メモリの最後を常に確保し、古い領域を一切再利用しない、という単純ワンタイムな使い方をしたとしても、部分的に解放されないなら、その区域を管理する情報が次第に肥大化する。

マルチスレッド、マルチプロセスではメモリ管理の途中でタスクスイッチすると管理情報が壊れるのでロックか空間分離が必要。

メモリにアクセスする確率が高いのは確保した直後か解放する直前。結果的に解放するときにはキャッシュに載っている可能性が高い。再確保するときにこのキャッシュの効果が無視できない。

一般的には、メモリは処理の経過では以下のような使われ方をする。(処理の局所性がある。)

処理の開始時に大量に確保される。

処理の中間では確保と解放がほどほど行われる。

処理の終了時に大量に解放される。

メモリの解放と再確保では同じサイズのものが要求されることが多い。

解放されたメモリをどう管理するかが意外と難しい

フラグメンテーションを解消するために結合したいが、安易にすぐに結合すると再確保の時に同じサイズを要求された時に損をする。

マルチCPUでは、同じメモリアドレスでもキャッシュに載っていないことがある。

OSでは、スレッドはできる限り同じCPUに割り当てる必要がある。

空間効率と時間効率は大体の場合トレードオフになる。

早くしようとするとメモリが無駄になる。

メモリを有効に使おうとすると遅くなる。

使えそうなアイデア

ポインタそのものに情報を持たせる。

ポインタを意図的にアライメントすると、そこに情報を載せることができる。

AND でマスクするだけで管理情報へのポインタが得られる。

ポインタ自身にサイズ情報を載せることもできる。

サイズデータはある程度のサイズでアライメントすると下位ビットが常に0になってしまう。ここを流用する。

管理情報を減らす方法

無意味になってるビットを流用する。

32bitポインタの場合、下2bitは常に0になる。

計算できるものは管理情報に記録しない。

よく知られているメモリ管理

単純な空き領域管理

次の空き領域へのポインタ(リンクリスト)

領域の長さ

small bin

8バイトずつサイズを増やしたリストで管理する。

O(1)でサイズに合ったメモリを取得できる。

巨大サイズの取り扱いが問題。

large bin

small bin では長いリストの管理が必要になるが、ある程度大きなサイズになると、もっと大雑把なサイズが必要になる。次第に大きくなるように配置。

この場合でも巨大領域確保を繰り返すとリストの最後だけが使われてパフォーマンスが劣化する。

4KBページを 2^n 単位のサイズごとに分割して使う。

マルチスレッドで管理を競合させないために、それぞれのスレッドでアリーナ(Arena)として1MB単位でメモリを確保する。

Linuxではメモリ要求時に1MBアライメントできないので、まず2MB要求して、そこから1MB切り出して他を捨てる。

何が必要か?

使用可能な物理メモリページの一覧

プロセス管理

論理メモリページに対する、使用している物理メモリページのマップ

メモリページに対する読み込み/書き込み/実行の制約の管理

「仮想メモリ」(Virtual Memory)という文言について

実際にメモリが全部物理的にマップされている状態(昔々のコンピュータのメモリ管理)に対して、仮想的にメモリがマップされているという意味合いの言葉。

スワップするかどうかはまた別問題だが、多くの場合、実メモリ量より多く使えるようになるメリットがあるため、スワップを行うようにしているのが一般的。

メモ

Keyword: 仮想メモリ