「記憶管理」の版間の差分

提供: UnixClassWiki
移動先: 案内検索
(局所参照性)
(局所参照性)
141行目: 141行目:
 
[[File:Memory_fig4.png|thumb|left|300px|キャッシュのモデル]]
 
[[File:Memory_fig4.png|thumb|left|300px|キャッシュのモデル]]
  
局所参照性とは「プログラムは同じ場所を繰り返しアクセスする性質を持ちやすい」というものです。常に成立するわけではありません。もしプログラムがランダムにメモリ空間全域をアクセスする性質を一般に持っていたならば、たぶん仮想記憶のようなシステムは無意味だったでしょう。なぜならば大量のページイン・ページアウトが発生しまうからです。このように大量のページイン・ページアウトが発生してしまう状態をスラッシングと呼びます。しかし殆んどのプログラムは局所参照性を持つので、使われていない部分を外部に移しても全体としてみた場合、リーズナブルなパフォーマンスが得られているのです。
+
局所参照性とは「プログラムは同じ場所を繰り返しアクセスする性質を持ちやすい」というものです。
 +
常に成立するわけではありません。
 +
もしプログラムがランダムにメモリ空間全域をアクセスする性質を一般に持っていたならば、
 +
たぶん仮想記憶のようなシステムは無意味だったでしょう。
 +
なぜならば大量のページイン・ページアウトが発生しまうからです。
 +
このように大量のページイン・ページアウトが発生してしまう状態をスラッシングと呼びます。
 +
しかし殆んどのプログラムは局所参照性を持つので、
 +
使われていない部分を外部に移しても全体としてみた場合、
 +
リーズナブルなパフォーマンスが得られています。
  
  
この考え方は仮想記憶に限らずCPUのキャッシュメモリなどでも使われています。最近のCPUはキャッシュが512KB、1MB、2MBとどんどん増えています。これはメモリからデータをフェッチしてきて、CPU内のキャッシュにおき、そこをアクセスします。当然、外にあるメモリよりCPU内のキャッシュの方がアクセス速度は格段に良いですから、それだけ速度が出るということになります。
+
この考え方は仮想記憶に限らずCPUのキャッシュメモリなどでも使われています。
 +
最近のCPUはキャッシュが512KB、1MB、2MB という具合にどんどん増えています。
 +
これはメモリからデータをフェッチしてきて、CPU内のキャッシュにおき、そこをアクセスすることで高速化を狙います。
 +
当然、外にあるメモリよりCPU内のキャッシュの方がアクセス速度は格段に良いですから、それだけ速度が出るということになります。
  
  
これを一般化してみると、「データを高速にアクセスできるほど装置は容量当たりのコストが高いので、容量とコストを勘案し多段に装置を組合せることによって、リーズナブルに高速で大容量のアクセスできる記憶装置を用意することができる」ということになります。メモリ、仮想記憶、ファイルシステムなど色々な場面でこの考え方が使われます。
+
これを一般化してみると、
 +
「データを高速にアクセスできるほど装置は容量当たりのコストが高いので、'''容量とコストを勘案し多段に装置を組合せることによって、リーズナブルに高速で大容量のアクセスできる記憶装置を用意'''することができる」
 +
ということがいえるでしょう。
 +
メモリ、仮想記憶、ファイルシステムなど色々な場面でこの考え方が現れます。
  
  
このアクセスが高速で小容量の装置と低速で大容量の装置との間でデータを移動させなければなりませんが、この時どのデータを選ぶかが問題になってきます。よく使われるデータは速い方へ、なかなか使われないデータは遅い方へ移すのが合理的です。ただし、「良く使われる」というのは過去の話ではなく将来の話だという所がポイントです。「良く使われるだろう」と判断するルールを決めなければなりません。このルールでよく使われるのがLRU (least recently used)です。LRUは直訳すると「最近、最も使われていないもの」ということで、簡単に言えば一番暇なものを入れ換えるという単純な話です。LinuxのページングもLRUのポリシーで行っています。
+
このアクセスが高速で小容量の装置と低速で大容量の装置との間でデータを移動させなければなりませんが、
 +
この時どのデータを選ぶかが問題になってきます。
 +
よく使われるデータは速い方へ、なかなか使われないデータは遅い方へ移すのが合理的です。
 +
ただし、「良く使われる」というのは過去の話ではなく将来の話だという所がポイントです。
 +
「良く使われるだろう」と判断するルールを決めなければなりません。
 +
このルールでよく使われるのがLRU (least recently used)です。LRUは直訳すると「最近、最も使われていないもの」ということで、
 +
簡単に言えば一番暇なものを入れ換えるという単純な話です。LinuxのページングもLRUのポリシーで行っています。
  
 
== 動的なメモリ領域確保 ==
 
== 動的なメモリ領域確保 ==

2010年11月11日 (木) 14:36時点における版

実メモリ

まず混乱を避けるためにメモリというあまりにも普段使い慣れた言葉を明確にしましょう。この節で使うメモリという言葉は、秋葉原で売っている部品のメモリのことではなく、オペレーティングシステムが管理し参照できる主記憶や仮想記憶もすべて含めた記憶領域の意味です。ですから、ここでのメモリという言葉は概念的でもあり、また実際に存在するものでもある両方の性質を持ちます。ここではハードウェアのメモリにあたるものとして実メモリという言葉という言葉を使います。


メモリは重要なリソースである上に、しかも注意深く管理しなければならない ものであるのは、いまさら言うまでもありません。メモリ上に実行コードやデー タが展開されていて、それに対し正しいアクセス制御できなければシステムは 正常に動かなくなってしまいます。


ページ

シンプルなアクセスモデル


プロセスからアクセスできるメモリリソースを考えてみましょう。 単純なモデルにしてみると右図のようにCPUリソースからメモリリソースに対しアクセスし読み書きする形になります。


しかし、みなさんは今時の記憶管理はこのような単純なモデルではなく、物理的なメモリサイズよりも大きなメモリ空間を扱える仮想記憶があることは既に承知しているはずです。 仮想記憶はメモリ空間をページと呼ばれる一定サイズのフレーム(区分)にし、 そのページをハードディスクのような外部記憶装置と物理的なメモリである実メモリ間で書き出し、 読み込みを行うことによって、 実際の実メモリの容量よりも多くのメモリ空間を使えるようにしています。


この書き込みや読み込みをする単位をページといい、サイズは32ビットアーキテクチャーのCPUは4KBのページサイズで、64ビットアーキテクチャーのCPUは8KBのものがほとんどです。[1]

MMU

仮想記憶のモデル

プロセスに割り当てられているメモリリソースとしてのメモリのアドレスは仮想的なアドレス空間に割り当てられます。仮想アドレス空間での仮想アドレスは、実際の実メモリの物理的な意味でのアドレスとは一致しません。

仮想アドレス空間と実メモリアドレス空間のマッピングは、それを管理する MMU (Memory Management Unit) というハードウェアによってマップされています。 今時はMMU はCPUチップ上に組み込まれていますが、概念的にはCPUとは違うハードウェアです。 むかしはCPUの中に入っていなかったので、CPUとは別にMMUのチップ [2] を用意していました。 また広大なメモリ空間を必要としない組込み用途向けCPUにはMMUを持っていないものもあります。


プロセスは仮想アドレス空間にアクセスしています。 MMU がアドレス変換をして仮想アドレス空間より実メモリアドレス空間をマップしてくれています。 これによってプロセスが連続したメモリ空間を確保することができるようになります。


実メモリに入りきらないものを外部記憶装置に書き出し、必要になったら実メモリに読み込もうというのが仮想記憶です。 実メモリアドレス空間より仮想アドレス空間よりが大きい状態になっていれば、実メモリ上にない仮想アドレスを要求することが発生します。 例えば32ビットアーキテクチャーの場合(232 / 4GB ) は仮想記憶空間として1048576(220)のページを持つことになります。もし512MBの物理メモリしか搭載していないマシンは内部で131072ページしか持っていません。


アクセス時はアドレス変換を行うためのキャッシュであるTLB (Translation Lookaside Buffer)にアドレスを問い合わせます。 MMUの中にTLBの機能が含まれているタイプ、あるいはCPUチップ上にMMUとは別にTLBを用意しているタイプなどがあります。 いずれにしてもTLBにアドレスが見つからなかった場合、つまり実メモリ上に該当ページを見つけられないとMMUはシグナルを発生させます。 これをページフォルトいいます。

ページング

ページフォルト

ページフォルト時のモデル

ページフォルト(Page Fault)の発生をうけてオペレーティングシステムは実メモリ上に必要な記憶領域を確保しようとします。 実メモリのサイズは限られているわけですから、 必要であれば実メモリのページ内容を外部記憶装置に書き出し、 空きを作りそこに新しいページをマッピングします。 再度、その外部に書き出されたページをアクセスすることが発生したら、 該当のページを外部記憶装置から実メモリ上に読み込んできます。 ページを読み込むのがページイン (page-in)、 ページを書き出すのはページアウト(page-out)といいます。

スワップ

仮想記憶で実メモリ上からハードディスクなどの補助記憶装置との間でメモリの内容を書き出したり、読み込んだりするメカニズムことをスワップ(交換)といいます。


厳密にいえば本来のスワップの定義はメモリが少なくなるとプロセスが使っているメモリをまるごと補助記憶装置に移動させる方法です。 ページングはページ単位ですからページングとスワップとは技術的には区別されます。 その意味でLinuxはページングだけやってスワップはしません。[3] 尚、 GNU/Linux 関連のドキュメントを読んでいると、 あまりスワップとページングの言葉の使い分けを明確に区別しているよう感じではなく、 仮想記憶でページング(paging)機能全体をざっくり指してスワップみたいな括りで呼んでいるような印象です。


調べてみよう
本来のスワップを持っているオペレーティングシステムには、どんなものがあるだろうか。

Linuxのスワップ

ですがLinuxはスワップという言葉を使っています。ここでは「ページをスワップ(交換)している」と解釈するしかないので、そういうことで話を進めます。


仮想記憶の機能があっても、もし実メモリが十分余裕があれば、わざわざスワップのための設定をする必要がありません。またプラクティカルには実メモリは、スワップ先である外部記憶装置よりも高価であり、そのスワップのオーバーヘッドを考えても利益があると考えた場合に有効です。またスワップする先が用意できなければ当然できません。たとえばCD-ROMからブートするKNOPPIXではデフォルトではスワップを使っていません。


先ほど説明したように記憶空間はページと呼ばれる単位で分割されています。主記憶と補助記憶とのやりとりはページ単位で行われ、ページイン、ページアウトを行います。


一般的にはハードディスク上にスワップ用のパーティションを取って、そこをスワップ先に指定します。多くの場合はインストール時にセットアップするようになっています。通常はパーティションをマウントするための情報を書く/etc/fstabにスワップパーティションの割り当ての記述が作られているはずです。


 /dev/hda3 none  swap  sw  0    0


スワップの状態は/proc/swapsを見るとわかります。下の例はサイズが1453872K (1.45GB)バイトである/dev/hda3パーティションがスワップに使われているという意味です。


% cat /proc/swaps
Filename       Type           Size    Used    Priority
/dev/hda3      partition      1453872 0       -1


スワップ先はディスクパーティションだけではなく、通常のファイルでもスワップ先にできます。適当なサイズのファイルを作り、そのファイルをmkswapコマンドで処理し、最後にswaponコマンドでスワップに追加すると簡単に新しいスワップ領域が出来ます。


swapon

たとえばswapf01という名前のスワップファイルを作ってシステムにスワップファイルとして登録する時は次のようにします。


# /bin/dd if=/dev/zero of=swapf01 bs=8192 count=256
# /sbin/mkswap swapf01 2048
# sync 
# swapon swapf0


まずswapf01を適当なサイズにして作成します。40KB以上、127MB以下ならいずれのサイズでも構いません。次に作ったファイルのサイズを1024で割った値をmkswapで指定するブロックサイズとします。mkswapが済んだならsyncしてからファイルをswaponします。ここではコマンドswaponを使っていますが、システムコールswapon()も用意されています。


どのファイルはハードディスクのパーティションであっても構いません。複数のハードディスクを同時に利用している時、スワップファイルを各々のハードディスク上に設定しスワップのプライオリティを同じ値にすることで、スワップディスクへの読み込み/書き込みなどディスクI/Oが分散させることができます。これはraid0のような効果となり高速化することになります。プライオリティを指定して、例えば高速なハードディスク、あるいはスワップファイルアクセス時にディスクスラッシングを避けるために作業しているハードディスクとは物理的に別のハードディスクをアクセスするようにするなどといったことも可能です。

局所参照性

キャッシュのモデル

局所参照性とは「プログラムは同じ場所を繰り返しアクセスする性質を持ちやすい」というものです。 常に成立するわけではありません。 もしプログラムがランダムにメモリ空間全域をアクセスする性質を一般に持っていたならば、 たぶん仮想記憶のようなシステムは無意味だったでしょう。 なぜならば大量のページイン・ページアウトが発生しまうからです。 このように大量のページイン・ページアウトが発生してしまう状態をスラッシングと呼びます。 しかし殆んどのプログラムは局所参照性を持つので、 使われていない部分を外部に移しても全体としてみた場合、 リーズナブルなパフォーマンスが得られています。


この考え方は仮想記憶に限らずCPUのキャッシュメモリなどでも使われています。 最近のCPUはキャッシュが512KB、1MB、2MB という具合にどんどん増えています。 これはメモリからデータをフェッチしてきて、CPU内のキャッシュにおき、そこをアクセスすることで高速化を狙います。 当然、外にあるメモリよりCPU内のキャッシュの方がアクセス速度は格段に良いですから、それだけ速度が出るということになります。


これを一般化してみると、 「データを高速にアクセスできるほど装置は容量当たりのコストが高いので、容量とコストを勘案し多段に装置を組合せることによって、リーズナブルに高速で大容量のアクセスできる記憶装置を用意することができる」 ということがいえるでしょう。 メモリ、仮想記憶、ファイルシステムなど色々な場面でこの考え方が現れます。


このアクセスが高速で小容量の装置と低速で大容量の装置との間でデータを移動させなければなりませんが、 この時どのデータを選ぶかが問題になってきます。 よく使われるデータは速い方へ、なかなか使われないデータは遅い方へ移すのが合理的です。 ただし、「良く使われる」というのは過去の話ではなく将来の話だという所がポイントです。 「良く使われるだろう」と判断するルールを決めなければなりません。 このルールでよく使われるのがLRU (least recently used)です。LRUは直訳すると「最近、最も使われていないもの」ということで、 簡単に言えば一番暇なものを入れ換えるという単純な話です。LinuxのページングもLRUのポリシーで行っています。

動的なメモリ領域確保

プロセス実行時に動的にメモリを確保するのにはプログラム中でmalloc(3)[4] を呼び出します。次のプログラムはプロセスが動的に512MBのメモリを割り当てるプログラムです。ここで使っているmalloc(3)やfree(3)の説明はオンラインマニュアルを参考してもらうとして、まずはプロセスが動的にメモリを確保するとどうなるかやってみましょう。


プログラム: malloctest.c
#include <stdlib.h>
main()
{
  char *p;
  size_t  areasize=1024*1024*512;
  if ((p=(char *)malloc(areasize)) == NULL) {
     perror("malloc");
  }
  sleep(10);
  free(p);
}
実行例: 
$ cc malloctest.c 
$ ./a.out &
$ ps axu | grep a.out
hironobu 29813  0.0  0.0 525528 284 pts/8    S    17:32   0:00 ./a.out
---この並びは下の様になっています---
USER      PID  %CPU  %MEM   VSZ RSS TTY      STAT START   TIME COMMAND


このプログラムは512MBメモリ領域をmalloc(3)を使いアロケーションしています。実行時の状況をpsで見てみると、VSZが525528、RSSが284となっています。VSZはVirtual memory Sizeのことで仮想記憶もふくめて全部のメモリサイズです。RSSはReal Set Sizeのことで、実メモリ(物理的なメモリ)で専有しているメモリサイズです。つまり、このプログラムは約523.5MBもの記憶領域を取っているにもかかわらず、実際の実メモリ上では284KBしか取られていません。


補足
もしmallocが失敗した場合、malloc: xxxxというメッセージが出ます。その場合でも小さい数字にはなりますがVSZやRSSの値は出ているはずです。


実メモリ上にあるのは、現在使おうとしているメモリです。アクセスがまったく発生すらしていないページは、まだページインされていない状態と同じです。この初期状態の時はまだ何も存在していないので、ページアウトしたものをページインする動作にはなりません。ここの部分だけに着目すると、アクセス時には、そのまま実メモリに作られる形になります。


プログラム中のsleepのある行を除いて、コンパイルし実行すると見かけ上512MB以上ものメモリを消費するプログラムがであっても、一瞬でプログラムが終ります。なぜならば、512MBのメモリ空間にアクセスしていないので、見かけ上このサイズのメモリが取れていてもまだ存在していないからです。アクセスが発生した始めて実メモリ上に必要な領域が生成されます。このように大量のメモリを見かけ上確保しても、それを使わない限り仮想のままで終ります。


次の ps コマンドを実行してみましょう。するとRSSでソートされて、USER / COMMAND / RSS / VSZの順で表示されます。

$ ps -Ao user,args,rss,vsize --sort rss
USER     COMMAND           RSS   VSZ
root     [keventd]           0     0
root     [ksoftirqd_CPU0]    0     0
...
hironobu emacs20 -geometr 9076 11112
canna    /usr/sbin/cannas 17540 19152


keventdやksoftirqd_CPU0などRSSとVSZが両方0のものはカーネルレベルで動いているスレッドです。ここではユーザレベルのプロセスであるemacs20と/usr/sbin/cannaserverのメモリの使い方に着目しましょう。emacs20はRSSは9076KBで、仮想記憶も含めたサイズは11112KBです。多くの場合、十分に実メモリに余裕があっても、プロ セス中で生成された記憶空間がすべて実メモリの上に載っているわけではありません。必要のあるもののみ実メモリ上にページインされます。CD-ROMから立ち上げるため仮想記憶のスワップ先がないKNOPPIXでも同じです。RSSもVSZも2つとも表示されて両者に差があります。


使われていない分、実メモリが空くわけですから、その分を動的にデバイスなどへのキャッシュなどに割り当ています。そのキャッシュが大きければ大きいほど、全体のパフォーマンスはよくなります。実メモリが必要になればキャッシュに使っていた実メモリをプロセスに回します。これはLinuxだけの話ではなく、今日多くのオペレーティングシステムではこのように全体のパフォーマンスを上げるためにメモリを効率よく使うというメカニズムが取り込まれています。


調べてみよう
vmstatで観察してみましょう。vmstatは仮想記憶のステータス観察するためのツールです。1秒毎に表示するオプションで動作させながら、先程のプログラムを改造し徐々に記憶を取るようなプログラムにして動かし、観察してみましょう。
% vmstat  1 <- 1秒毎に表示
 procs                  memory    swap        io    system         cpu
 r b w  swpd  free  buff cache  si  so   bi   bo   in   cs  us  sy  id
 0 0 0   624  3324 14868 61228   0   0    1    1    3    9   0   0   0
......
 4 0 0 28724  1120   412  2196 476 536  119  160  444  668  93   7   0
 2 1 0 29964  1140   368  2128 316 124   79  310  485  817  37   9  54
...

mmap

mmap(2)はファイルをメモリのように使うためのシステムコールです。mmapを使うことによってファイルとメモリの境目はなくなります。次のプログラムを見てください。これはファイルをオープンした後、ファイルの中身を文字型配列としてアクセスしています。readを使って読み込みをしているわけではありません。


プログラムmmap.c
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
main()
{
  int fd;
  struct stat st;
  char *p;
  int i;
  fd=open("dat",O_RDWR);
  fstat(fd, &st);
  p=mmap(0,st.st_size,(PROT_READ|PROT_WRITE),MAP_PRIVATE,fd,0);
  for(i=0; i < st.st_size -1 ; i++) {
    printf("[%c]",p[i]);
  }
  close(fd);
}
実行
$ echo  'abcdefg' > dat
$ cc mmap.c
$ ./a.out
[a][b][c][d][e][f][g]$ 


ファイルdatの中身は"abcdefg"となっています。datをオープンしfstatでファイルのステータス情報を取り出します。そのステータス情報の中のファイルサイズがst.st_sizeです。mmapを使って、ファイルdatの中身をメモリ空間として割り当てます。そのポインタがpです。ループ内でpの中身を表示させると、ファイルの内容と同じであることがわかります。


これはメモリの中にファイルを読み込んでいるわけではありません。ファイルをメモリにマップしたのです。スワップページからページインするのと良く似ていると気が着く人もいるでしょうが、基本的には同じ動作で、ファイルを読み出す過程はページインと同じ仕組みです。


これは今日のUNIX系オペレーティングシステムでの重要なメカニズムの一つです。たとえばLinuxではプログラムを実行する時、バイナリの実行ファイルや標準ライブラリを読み込む動作をするのではなくmmapでマップします。これでファイルシステムとは違う記憶領域であるはずのメモリ内に存在するのと、まったく同じ動作ができます。動作時に実行コードをページインします。

glibcでのmalloc実装は/dev/zeroをオープンし一定領域をmmapで確保し、その領域から必要な分を切り出してプログラム側に返却しています。つまりmallocを呼び出したプログラムは/dev/zeroの領域を使っています。/dev/zeroは物理的なデバイスの実体を持たないので、カーネルが与えたメモリ空間になります。mmapはこんな使い方もされているという一例です。


さて、この例題プログラムではマップする属性をMAP_PRIVATEとしているので、ファイルの内容を読み込みはしますが、メモリ領域に書き込んでも、それはファイルには書き込まれません。これをMAP_SHAREDとするとファイルと同期を取ることができます。このファイルを複数のプログラムからオープンすると共有メモリとして利用できます。


補足
内容をアップデートして同期するにはメモリに書き込み後、msync(2)やmunmap(2)を呼ぶことが必要です。


単一レベル記憶

ファイルもメモリも、さらにデバイスすらも単純な1つの記憶空間として扱おうというコンセプトが単一レベル記憶です。現在、オペレーティングシステムレベルでサポートしているのはIBM社のSystem iシリーズぐらいしかないので、インターネット上で説明を探すとIBM System iの機能=単一レベル記憶の定義みたいな説明しかありませんが、実は、その歴史は古く1960年代に作られたMultics上に既に実装されています。

UNIXは単一レベル記憶を前提としているデザインはありませんが、現在のUNIX系のオペレーティングシステムはmmapを実装することによってMulticsが持っていたファイルもメモリも、そしてデバイスも同様に扱うことができる利益を得ています。例としては今時のLinuxやその他UNIX系のオペレーティングシステムでは実行バイナリやライブラリを動かすとき、一々ファイルの中身を読み込む動作をせず、実行するバイナリデータを内部でマップしてしまいます。ですから古典的なUNIXで言われるような、「実行バイナリファイルをメモリに読み込み実行する」という表現は少なくとも現在のLinuxの実行時の表現としては適切ではないという状況になっています。あとデバイスの利用例としては、malloc()のいくつかの実装では内部で記憶領域を確保するとき/dev/zeroをmmapでオープンして使っています。mmapの機能の背景にある単一レベル記憶というキーワードは知っていて損はないでしょう。

脚注

  1. これらはCPUのアーキテクチャーに依存するので異なる場合があります。 たとえばPowerPCは64KBのページサイズも利用することが出来ます、 そのためパフォーマンスのために64KBのページサイズとして使う場合もあります。 64KB pages on Linux for Power systems - http://www.ibm.com/developerworks/wikis/display/hpccentral/64KB+pages+on+Linux+for+Power+systems
  2. MC68851: paged memory management unit user's manual (1986) [1]
  3. ちなみにソースコードmm/memory.cを見るとLinuxで仮想記憶が動き始めたのは1991年12月18日だそうです。mm/memory.c
  4. malloc(3)の3の意味はマニュアルの分類を示しています。

目次