Operating-system-os-memory-allocation-qa2
OSメモリ割り当てに関するQ＆A＃2
- 質問：*次の割り当てアルゴリズムについて説明します。
- 最初の適合
- ベストフィット
- 最悪のフィット
- バディのシステム
- 次のフィット
回答：
最初の適合
ファーストフィットアプローチでは、プロセスに対応できる十分な大きさの最初の空きパーティションまたはホールを割り当てます。 最初の適切な空きパーティションが見つかったら終了します。
利点
可能な限り検索が少ないため、最速のアルゴリズム。
不利益
割り当て後に残った未使用のメモリ領域は、小さすぎると無駄になります。 したがって、より大きなメモリ要件の要求を達成することはできません。
ベストフィット
最適な方法は、要求プロセスの要件を満たす最小の空きパーティションを割り当てることです。 このアルゴリズムは、最初に空きパーティションのリスト全体を検索し、適切な最小の穴を考慮します。 次に、必要な実際のプロセスサイズに近い穴を見つけようとします。
利点
メモリ使用率は、最初に利用可能な最小の空きパーティションを検索するため、最初の適合よりもはるかに優れています。
不利益
それは遅く、小さな無駄な穴でメモリをいっぱいにする傾向さえあります。
最悪のフィット
最悪の場合のアプローチでは、利用可能な最大の空き部分を見つけて、残りの部分が十分に大きくなるようにします。 これはベストフィットの逆です。
利点
小さなギャップの生成率を減らします。
不利益
より大きなメモリを必要とするプロセスが後の段階で到着した場合、最大の穴がすでに分割され占有されているため、それを収容することはできません。
バディのシステム
バディシステムでは、フリーブロックのサイズは2の整数乗の形式です。 E.g. 2、4、8、16など メモリのサイズまで。 サイズ2kの空きブロックが要求されると、サイズ2kの空きブロックのリストから空きブロックが割り当てられます。 サイズ2kの空きブロックがない場合、次に大きいサイズのブロック2k + 1は、要求を満たすためにバディと呼ばれる2つの半分に分割されます。
例
合計メモリサイズを512KBとし、プロセスP1で70KBをスワップインする必要があるとします。 ホールリストは2の累乗のみであるため、128KBで十分です。 最初は128KBもありませんし、256KBのブロックもありません。 したがって、512KBブロックはそれぞれ256KBの2つのバディに分割され、1つはさらに2つの128KBブロックに分割され、そのうちの1つがプロセスに割り当てられます。 次のP2には35KBが必要です。 35KBを2の累乗に切り上げるには、64KBブロックが必要です。
したがって、128KBブロックが2つの64KBバディに分割される場合。 ここでも、プロセスP3（130KB）は256KB全体で調整されます。 このようなブロックが空いているときにこの方法で要求を満たした後、2つのブロック/バディを再結合して、2番目の半分のバディも空いているときに2倍の元のブロックを形成できます。
利点
バディシステムの方が高速です。 サイズ2kのブロックが解放されると、マージが可能かどうかを確認するために2kメモリサイズのホールが検索されますが、他のアルゴリズムではすべてのホールリストを検索する必要があります。
不利益
多くの場合、メモリ使用率の面で非効率になります。 すべてのリクエストは2のべき乗に切り上げられる必要があるため、35KBプロセスが64KBに割り当てられ、余分な29KBが無駄になり、内部フラグメンテーションが発生します。 バディの間に穴があり、外部の断片化を引き起こす場合があります。
次のフィット
次の適合は、最初の適合の修正バージョンです。 空きパーティションを見つけるための最初の適合として始まります。 次回呼び出されたとき、最初からではなく、中断したところから検索を開始します。
