4 メモリマネジメント

   ここでは、legOSにおけるメモリマネージャの動作について調べてみる。
  legOSは組み込み型汎用8bitマイコンで動作し、 取り扱うメモリ空間も32Kbytesと小さく (アドレッシング空間は16bitなので65K)、 Pentiumなどの高機能なプロセッサのようにハードウェアーでサポートされた セグメント機構による保護機能やページング機構による仮想メモリ、 大容量ストレージのキャッシングなどの繁雑な処理と そのマネジメントアルゴリズムの実装の必要がないので メモリマネージャの機能はいたってシンプルである。 legOSでサポートすべきメモリマネージメント機能は 主にマルチタスキングでのタスク生成や消滅に伴うメモリイメージの管理である。

   カーネルがマルチプログラミングをサポートすると、 プロセスの生成や消滅にともなって動的にメモリを割り当てたり 開放したりする必要がある。 メモリマネージャはどこにどれだけの空きがあり、 どこがどのプロセスに使用されているかを把握し、 必要な時には必要なだけのメモリをプロセスに与えたり、 必要がなくなったときには空き領域資源として管理し、 将来の割り当てに備えなくてはならない。

   さらに、PCのような大規模なメモリ空間の管理には管理用の特別の メモリ領域を確保して空きセグメントリスト、使用セグメントリストを 設けて、メモリ管理はこのリストを参照して行われる。 (ギガバイト級のメモリを端っこから見てたら日がくれちゃうでしょ！) しかし、legOSでは管理すべき空間がそもそも狭いので、 メモリ空間そのものをリストとして管理参照している。

   カーネルがメモリ割り当てを行う際まず始めに行うことは、 必要なだけの連続した空き領域が存在するかを調べることである。 カーネルはmm_startで示されるメモリマネジメント領域の最初のアドレス からスタック領域の下限までの全てのメモリ空間から適切な空き領域 を選び出さなくてはならないが、legOSではこのアルゴリズムに ファーストフィット法を採用している。 以下に代表的な探索アルゴリズムをならべて眺めてみる。

ファーストフィット
もっとも単純なアルゴリズムである。 探索リストの最初から順番に探索し、十分な空き領域を見つけると そこを分割してプロセスに与え、残りを空き領域として記録する。 ファーストフィットはできるだけ検索量を少なくする働きがあるため 高速なアルゴリズムである。

ネクストフィット
ファーストフィットと同様な働きをするが、該当する空き領域を 検出したときに、その位置を記憶しており、次回起動されたときには そこから検索を開始するので毎回最初から検索するわけではない。 しかし、Bays(1977)によるシミュレートでは ファーストフィットよりもネクストフィットのほうが やや性能が劣っていたらしい。

ベストフィット
ベストフィットはリスト全体を検索し、該当する空き領域のなかで 最も小さいものを採用する。あとで必要となるかもしれない大きな 空き領域を分割することをせず、もっともフィットしたサイズの 空き領域を採用する。つまり検索時間をよけいにかけてでも メモリの使用効率を向上させようという試みである。 しかし実際には使い物にならないとても小さな領域を増やす結果 につながって使用効率はファーストフィットに劣るらしい。

ワーストフィット
ベストフィットの問題を回避しようとした方法で、 最も大きな領域を採用する。これもシミュレーションでは ファーストフィットに負けてしまったらしい。

クイックフィット
空き領域探索リストをサイズ毎に分類した別々のリストで管理する。 例えば2Kの空きリストと8Kの空きリストといったようにサイズごとに 設ければ必要な空き領域の探索が非常に高速化できる。 でも、legOSで複雑なリストを作るなんて限られたメモリ空間 (simple-rover.srecのダウンロード後は空き領域は全部で 11.5KBしかない！)の浪費でしょう？

というわけで legOSの採用しているアルゴリズムは賢明な選択だったのであーる。

   NO_MEMORY_MANAGEMENTマクロを未定義でコンパイルされたカーネルは 初期化シーケンスにおいてmm_init()の呼び出しでメモリマネージャを 初期化する。 初期化の手続きは以下。

   メモリの動的な確保の手続きを調べることでlegOSのメモリマネージャの働きが 全て分かるといっても過言ではないので調べてみることにする。 mallocは引数として確保すべき領域サイズ(bytes)を表す16bit値 size をとる。