メモリ管理、Buddyシステム

					2010年01月12日
情報科学類 オペレーティングシステム II

                                       筑波大学 システム情報工学研究科 
                                       コンピュータサイエンス専攻, 電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/literacy-2009/2010-01-12
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

■今日の大事な話

• メモリ管理とは(OS I復習)
• 仮想記憶とは(OS I復習)
• Linux のメモリ管理(ページ単位の管理)

■前回資料

◆exitシステム・コール

■メモリ管理

• ユーザ・プロセスに対して、アドレス空間を作る。
• ユーザ・プロセスに対して、物理メモリを割り当てる。 不要になったメモリを回収する。
• カーネル自身のメモリを管理する。

◆Unixにおけるメモリに関するシステム・コールとライブラリ

• execve(): メモリ中のプログラムを入れ替える。アドレス空間を作る。
• malloc(): ヒープからメモリを割り当てる。
• free(): malloc() で割り当てたメモリを解放する。
• mmap(): ファイルをメモリにマップする。
• brk(), sbrk(): ヒープメモリを増やす。
• mprotect(): メモリの保護モードを変更する。
• mlock(): メモリをページアウトされないようにする（pinning、ピン留め）
• munlock(): mlock() でピン留めした状態を解除する。

◆OSに求められる機能

• 1台のコンピュータで複数のプロセスを走らせる(multiprogramming)。
• プロセスは、それぞれ独立したアドレス空間を持つ。多重(仮想)アドレス空間(multiple (virtual) address spaces)
• 仮想記憶(virtual memory)を実現する。物理メモリよりも大きなメモリを利用可能にする。 ディスクを二次記憶として使って。
• 物理メモリを固定長のページ・フレーム(page frame)に分割する。
• プロセスの仮想アドレス空間は、ページ(page)の並びに分割する。
• ページの大きさとページ・フレームの大きさは、同じ。 ページ・サイズと呼ぶ。ページ・サイズは、2のべき乗の大きさ。4KB-64KB が多い。
• 任意のページは、任意のページ・フレームにマップできる。
• CPU は、プログラムを実行中に仮想アドレス(virtual address)を 出力して、機械語命令やデータをアクセスする。
• MMU (Memory Management Unit) は、仮想アドレスを物理アドレス(physical address) に変換する。
• MMU は、メモリ中に作られたページテーブル(page table)を見ながら 変換する。ページテーブルは、仮想アドレスと物理アドレスの対応表。
• しばらく使わないページの内容を、ディスクに退避する(page out)。
• ディスクから要求されているページの内容をメモリにコピーする（page in）
• ページアウトされているメモリをアクセスすると、ページフォールト(page fault) が発生する。 OSは、ページインの処理を行い、再開する。
• 仮想アドレスの大きさは、普通、32ビットのシステムなら、32ビット。 64ビットのシステムなら、64ビット。
• 物理アドレスの大きさは、搭載しているメモリのサイズによる。 32ビットのシステムでも、4GB 以上のメモリを搭載している時には、 64ビットの物理アドレスが使われることがある。 (物理的な配線は、64本より少ないことがある。)

◆ページ構造体

include/linux/mm_types.h
  40: struct page {
  41:         unsigned long flags;            /* Atomic flags, some possibly
  42:                                          * updated asynchronously */
  43:         atomic_t _count;                /* Usage count, see below. */
...
  54:         union {
  55:             struct {
...
  63:                 struct address_space *mapping;
  70:             };
...
  75:             struct page *first_page;    /* Compound tail pages */
  76:         };
...
  81:         struct list_head lru;
...
  95:         void *virtual;                  /* Kernel virtual address (NULL if
  96:                                            not kmapped, ie. highmem) */
...
 109: };

• count: ページの参照カウント。0 なら、そのページ・フレームは空いて いる( 他の目的で使ってよい)ことを意味する。 1以上なら、その数のプロセスでそのページを参照している。
• mappping: ページがファイルにあるメモリを保持している時、 アドレス空間構造体(struct address_space)と結びつけられる。 mappping フィールドは、そのページがメンバとなっているアドレス空間構造体を指す。 アドレス空間構造体が実現している「アドレス空間」とは、 inode等の「メモリ・オブジェクト」1個に属しているページの集まり。
• lru: Least Recently Used でメモリ管理を行うための双方向リスト。 active_list (使われているメモリのリスト)か inactive_list (使われていないメモリのリスト、他の目的に使ってもよいメモリのリスト)につながれる。
• virtual: そのページが属している「仮想アドレス」へのポインタ。

◆メモリ・ゾーン

よく使われるゾーンの種類。

ZONE_DMA

(古いデバイスでも) DMA でアクセス可能なページ・フレーム。 x86 では、0-16M。 ISA バスのデバイスで 0-16M しかアクセスできないものがあった。

ZONE_NORMAL

(古いデバイスの)DMA ではアクセスできないが、カーネルの仮想アドレス空間に常にマップされている。

ZONE_HIGMEM

普段はカーネルの仮想アドレス空間にマップされていない。 使うときにはマップして使い、使い終わったらアンマップする。

◆zone構造体

include/linux/mmzone.h

 274: struct zone {
...
 278:         unsigned long watermark[NR_WMARK];
...
 309:         struct free_area        free_area[MAX_ORDER];
...
 386:         wait_queue_head_t       * wait_table;
 387:         unsigned long           wait_table_hash_nr_entries;
 388:         unsigned long           wait_table_bits;
...
 414: } ____cacheline_internodealigned_in_smp;

 153: enum zone_watermarks {
 154:         WMARK_MIN,
 155:         WMARK_LOW,
 156:         WMARK_HIGH,
 157:         NR_WMARK
 158: };

  22: /* Free memory management - zoned buddy allocator.  */
  23: #ifndef CONFIG_FORCE_MAX_ZONEORDER
  24: #define MAX_ORDER 11
  25: #else
  26: #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
  27: #endif
  28: #define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

• watermark: メモリがこの水位(warter mark)を下回ると、カーネルは メモリ不足対策を発動する。
• free_area: 利用可能な領域を保持する。
• wait_table, wait_table_hash_nr_entries, wait_table_bits: メモリが 足りない時に、プロセスをスリープさせるために使う。スリープ中、カーネル は他のプロセスのメモリをページアウトするなどして空きメモリを作るように がんばる。スリープから解除されたら、もう一度メモリを確保することを試み る。

◆ページフレームの割当てと開放

include/linux/gfp.npr
 312: #define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

 308: #define alloc_pages(gfp_mask, order) \
 309:                 alloc_pages_node(numa_node_id(), gfp_mask, order)

 279: static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
 280:                                                 unsigned int order)
 281: {
 282:         /* Unknown node is current node */
 283:         if (nid < 0)
 284:                 nid = numa_node_id();
 285: 
 286:         return __alloc_pages(gfp_mask, order, node_zonelist(nid, gfp_mask));
 287: }

 272: static inline struct page *
 273: __alloc_pages(gfp_t gfp_mask, unsigned int order,
 274:                 struct zonelist *zonelist)
 275: {
 276:         return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
 277: }

 331: #define __free_page(page) __free_pages((page), 0)
 332: #define free_page(addr) free_pages((addr),0)