OS自作入門 -Advent35-

Step10 OSのメモリ管理

OSの役割

コンピュータの資源を管理し、複数のタスクに効率的に割り当てること

と言えるだろう。

KOZOSでは処理をタスクとして分割するためにスレッドという仕組みを用意した。スレッドの実行時間は CPU時間 という資源を割り当てていることになる。

コンピューターの3大要素

• CPU
• メモリ
• I/O

がある。上述の通りスレッドの役割は CPU時間を複数のタスクに配分すること である。

メモリ管理の必要性

別な資源であるメモリについて考える。

メモリは通番のアドレスに配置されている単なる記憶領域であると言える。ただ、スレッド間で共有するので衝突する可能性がある。そのため管理する必要があるのだが、たとえばリンカ・スクリプトを利用することによって有限のサイズのメモリ領域を必要に応じて割り当てることができる。

しかし、これでは静的な取り扱いになってしまい、必要なときに確保するとか、不要になったら開放するとか、開放された領域を使い回すとかができない。なのでこれを動的な取り扱いができるようにしていく。

• メモリの獲得動作 = allocate
• メモリの開放処理 = free

と呼ぶ。

メモリ管理の概要

• 可変サイズのメモリ管理
  c言語でいう malloc()で実装されているメモリ管理方法
  1kbyteの領域が必要なら

  p = malloc(1024);

• 固定サイズのメモリ管理
  16byteをL個、128byteをM個、1024byteをN個。
  といった感じでメモリを確保しておく

の二種類が必要である。

malloc()でのメモリ管理

どのように実装していくか。

可変サイズの領域を切り売りする方法

以下のように先に領域を確保してそのうちのいくつかを返すようにする方法。

char memory_area[128 * 1024]

これで128kbyteのメモリプールを作ることができる。

この中で確保されたメモリの先頭部分にヘッダと呼ばれる情報（領域のサイズ、獲得済み・開放済みなどの情報）を保持しておくようにする。こうすることによって、アドレスを渡せばメモリ内の情報のみを利用してメモリの開放や確保を行うことができるようになる。（ポインタだけ渡されてもmallocやfreeは内をしたらいいのかわからないため）

また、このヘッダ情報にnextポインタを持たせて、 獲得した領域 と 開放した領域 をリンクリストで管理できるようにすると、いくつmallocされたとしてもnextがNULLになるポインタまで追えば 開放された領域 を検索することが可能になる。もし 開放された領域 に必要なサイズを満たすものがなければ未使用領域から割り当てれば良い。

01 head1 size: 5, next: 11, used, <- used_pointer
02 used
03 used
04 used
05 used
06 used
07 head2 size: 3, next: 14, free  <- free_pointer
08 free
09 free
10 free
11 head3 size: 2, next: NULL, used
12 used
13 used
14 head4 size: 4, next: NULL, free
15 free
16 free
17 free
18 memory pool <- unused_pointer
19 memory pool
20 ....

こんな感じで、used_pointerからnextを辿ればhead3が示すところまでメモリが利用されていて、free_pointerから辿ればhead2とhead4がそれぞれ空いているのがわかり、unused_pointerを見れば未使用領域がわかるようになる。

（途中の抜き出しを考慮する必要があるため実際の実装にはprevポインタも持たせて逆に辿れるようにもする）

このような可変サイズのメモリ領域を ヒープ領域 と呼ぶ。

ちなみに獲得と開放の繰り返しにより発生する フラグメンテーション というものがあるが、とりあえず置いておく。

可変サイズでの管理の欠点

上記の方法でOSがメモリ管理をすることができるようになるが、実はあまり向いてないらしい。

理由はメモリの開放済み領域を検索する際に検索が必要になり、OS内部にこのような処理があるとOSの応答性が悪くなったり性能にバラツキが出てしまう。

固定サイズのメモリ管理

16byteをL個、128byteをM個、1024byteをN個というようにメモリプールを用意し、それぞれをリンクリストにして管理する。メモリ獲得時にはリンクリストの先頭の領域を割り当て、開放された領域はリンクリストに接続するようにしておけばいい。

欠点といえば、実際に必要なサイズよりも大きな領域が割り当てられるため効率が良くない。だが、検索等は必要なく、先頭にあるものを割り当てればいいので高速な処理を行うことができる。

メモリ管理の実装

動的なメモリの確保・開放のサービスを追加する。システムコールの追加となる。

変更するファイル

• memory.h, memory.c （新規）
• test10_1.c（新規）
• ld.scr（修正）
• syscall.h, syscall.c（修正）
• kozos.h, kozos.c（修正）
• main.c（修正）
• Makefile（修正）

メモリプールの追加

まずメモリプールとして利用するRAMの空き領域をld.scrで定義する。

  .freearea : {
    _freearea = . ;
  } > ram

を追加

メモリ管理ライブラリ

固定サイズのメモリ管理 を行うライブラリを実装する。memory.hに以下の三つの関数を用意する。

• kzmem_init()
  メモリ・プールの初期化
• kzmem_alloc()
  メモリ領域の確保
• kzmem_init()
  メモリ領域の開放

構造体の定義

memory.cに構造体の定義を行う。

• kzmem_block
  メモリ・ヘッダに相当。
  領域のサイズ情報とリンクリストで管理するためのnextポインタがある。
• kzmem_pool
  メモリ・プールの情報格納用。
  固定である領域のサイズと実際に利用するサイズの差が大きいと利用効率が悪くなる。
  このため数種類のブロック・サイズのメモリプールを用意する必要がある。

メモリ・プールの初期化

memory.cに実装を行う。

kzmem_init_pool()でメモリ・プールの初期化を行う。ポインタのポインタが出てくるのだが詳細が書籍に載っていたので良く読んでおこう。

なおメモリブロック（メモリヘッダ + データ領域）がそれぞれ16byte, 32byte, 64byteなのでヘッダ部分を引くと利用できる データ領域がそれぞれ8byte, 24byte, 56byteとなるので注意を。

メモリ領域の獲得

memory.cに実装を行う。

kzmem_allocを実装。必要とされるサイズを格納できるメモリプールを検索し、開放済み領域のリンクリストの先頭から領域を確保するようにしている。確保したら該当のメモリブロックはリンクリストから外しデータ領域の先頭アドレスを返す。

最大64byteだがこれを超えるサイズが要求されたらkz_sysdown()でシステム停止となる。

メモリ領域の開放

memory.cに実装を行う。

kzmem_freeを実装。開放するデータ領域の先頭アドレスが引数として渡される。アドレスを一つ遡りメモリヘッダを見つけてブロック・サイズを取得し、該当のメモリ・プールのリンクリストの先頭に接続する。

システム・コールの追加

メモリ管理はOSの役割であり、システムコールとして実装するのが適切である。

syscall.h、syscall.c、kozos.h、kozos.cに修正を行う。

syscall.hにはシステムコール番号（KZ_SYSCALL_TYPE_KMALLOC, KZ_SYSCALL_TYPE_KMFREE）の追加、引数と戻り値の受け渡しのための構造体にパラメータ領域を追加。

syscall.cに

• void *kz_kmalloc(int size);
• int kz_kmfree(void *p);

の二種類を追加する。

kozos.hには今回実装したkz_kmallocとkz_kmfreeのプロトタイプ宣言を行なっている。また今回のサンプルプログラムのためのtest10_1_main()のプロトタイプ宣言も合わせて行う。

kozos.cでは、kz_kmalloc()とkz_kmfree()の処理の実態として、thread_kmalloc()とthread_kmfree()を追加。処理としてはmemory.cに定義した関数を呼んでいるだけ。

kz_start()のメモリ・プールの初期化関数であるkzmem_init()を呼ぶ処理を追加。

サンプル・プログラム

test10_1.cに実装を行う。

4〜56のサイズでメモリの獲得。獲得したメモリに対してメモリフィル（aやbなどの特定パターンで埋める）。出力。開放。を行う。

main.cにも変更を加えて、test10_1_mainがスレッドで起動するように修正。

Makefileにコンパイル対象を加えて終わり。

プログラムの実行

kzload> run
starting from entry point: ffc020
kozos boot succeed!
test10_1 started.
00ffd258 aaa
00ffd268 bbb
00ffd268 aaaaaaa
00ffd258 bbbbbbb
00ffd2d8 aaaaaaaaaaa
00ffd2f8 bbbbbbbbbbb
00ffd2f8 aaaaaaaaaaaaaaa
00ffd2d8 bbbbbbbbbbbbbbb
00ffd2d8 aaaaaaaaaaaaaaaaaaa
00ffd2f8 bbbbbbbbbbbbbbbbbbb
00ffd2f8 aaaaaaaaaaaaaaaaaaaaaaa
00ffd2d8 bbbbbbbbbbbbbbbbbbbbbbb
00ffd3d8 aaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd418 bbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd418 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd3d8 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd3d8 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd418 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd418 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd3d8 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd3d8 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd418 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd418 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd3d8 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd3d8 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd418 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
00ffd418 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
00ffd3d8 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
test10_1 exit.
test10_1 EXIT.

できた。

00ffd258 aaa
00ffd268 bbb
00ffd268 aaaaaaa
00ffd258 bbbbbbb
...

先頭の16進数が獲得した領域のアドレス。3文字とか7文字になっているのは末尾にヌル・ターミネータ（'\0'）を入れているから。アドレスが交互に取得されている（ 00ffd258 => 00ffd268 => 00ffd268 => 00ffd258）のは獲得した順に開放し、後に開放された領域がリンクリストの先頭にくるためである。

readelfをした結果はreadelf-result2.txtに置いておく。

freeareaは00ffd250からメモリプールが開始されているので、ヘッダのサイズは8byteであるため、00ffd250に8byteを加算すると00ffd258となるので一番最初の16進数が示すアドレスと一致している。他の表示も同様に、確保した（allocした）byteに対して最小のメモリプールから領域が取得され、それぞれリンクリストの出し入れにしたがって順番に利用されているのがわかる。

メモリ管理も奥が深い。JVMとかは動的なメモリ確保の仕組みを作っていたりとかするのだからこの辺りの知識は必須だろう。しかし、ポインタ周りがなんというか技巧的に見えて何やっているのかを想像しながら書くってのが読みづらい。まぁそれも味か。今日はこの辺りで。あとはstep11とstep12を残すのみとなった。