もちゅるの日常

特に決まっていないざっくばらんなブログ

メモリ確保のアルゴリズム一覧

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


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


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


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


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

引用元:http://www.ylw.mmtr.or.jp/~trustno1/legos/legos_4.html#4