フラグメンテーション(コンピューティング)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータストレージでは断片化は、ストレージスペース、メインストレージまたはセカンダリストレージが非効率的に使用され、容量またはパフォーマンス、そして多くの場合その両方が低下する現象です。断片化の正確な結果は、使用中のストレージ割り当ての特定のシステムと断片化の特定の形式によって異なります。多くの場合、断片化によりストレージスペースが「無駄」になります。その場合、この用語は無駄なスペース自体も指します。

断片化の種類

断片化には、3つの異なる、しかし関連する形式があります。外部断片化、内部断片化、およびデータ断片化であり、これらは単独で、または組み合わせて存在する可能性があります。断片化は、速度や単純さの向上と引き換えに受け入れられることがよくあります。同様の現象は、プロセッサなどの他のリソースでも発生します。下記参照。

基本原則

コンピュータプログラムがコンピュータシステムにメモリのブロックを要求すると、ブロックはチャンクで割り当てられます。コンピュータプログラムがチャンクで終了すると、システムに解放され、後で別のプログラムまたは同じプログラムに再度割り当てることができます。チャンクがプログラムによって保持されるサイズと時間は異なります。その存続期間中、コンピュータプログラムはメモリの多くのチャンクを要求して解放することができます。

プログラムが開始されると、空きメモリ領域は長く連続しています。時間の経過とともに、使用に伴い、長い連続領域はますます小さな連続領域に断片化されます。最終的には、プログラムが連続した大きなメモリチャンクを取得できなくなる可能性があります。

タイプ

内部フラグメンテーション

メモリページングは​​、その量のストレージが必要かどうかに関係なくページフレーム全体が割り当てられるため、内部フラグメンテーションを作成します。[1]メモリ割り当てを 管理する規則により、より多くのコンピュータメモリが割り当てられることがあります必要以上に。たとえば、メモリはチャンク(通常は4バイトの倍数)でのみプログラムに提供でき、その結果、プログラムがおそらく29バイトを要求した場合、実際には32バイトのチャンクを取得します。これが発生すると、余分なメモリが無駄になります。このシナリオでは、使用できないメモリは割り当てられた領域内に含まれています。固定パーティションと呼ばれるこの配置は、メモリの使用効率が悪いという問題があります。どのようなプロセスでも、パーティション全体を占有します。この無駄は内部断片化と呼ばれます。[2] [3]

他のタイプの断片化とは異なり、内部断片化は再利用が困難です。通常、それを削除する最良の方法は、設計を変更することです。たとえば、動的メモリ割り当てでは、メモリプールは、スペースオーバーヘッドをより多くのオブジェクトに分散させることにより、内部の断片化を大幅に削減します。

外部フラグメンテーション

外部フラグメンテーションは、空きメモリが小さなブロックに分割され、割り当てられたメモリによって散在している場合に発生します。プログラムが使用するメモリを効率的に順序付けできない場合、これは特定のストレージ割り当てアルゴリズムの弱点です。その結果、無料のストレージは利用できますが、アプリケーションの要求を満たすには個別に小さすぎる部分に分割されているため、事実上使用できません。「外部」という用語は、使用できないストレージが割り当てられた領域の外にあるという事実を指します。

たとえば、プログラムが3つの連続したメモリブロックを割り当ててから、中央のブロックを解放する状況を考えてみます。メモリアロケータは、この空きメモリブロックを将来の割り当てに使用できます。ただし、割り当てられるメモリのサイズがこの空きブロックよりも大きい場合は、このブロックを使用できません。

さまざまなサイズの多くのファイルが作成され、サイズが変更され、削除されるため、ファイルシステムでも外部フラグメンテーションが発生します。多くの小さな断片に分割されたファイルを削除すると、同様に小さな空き領域が残るため、効果はさらに悪化します。

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 コメントコメント
ストレージに使用可能なすべてのメモリから始めます。
A B C サイズ0x1000の3つのブロックA、B、およびCを割り当てました。
A C ブロックBを解放しました。Bが使用したメモリは、Bのサイズより大きいブロックには含めることができないことに注意してください。
A C ブロックCはブロックBの空のスロットに移動し、残りのスペースをサイズ0x4000のより大きなブロックに使用できるようにしました。

データの断片化

データの断片化は、メモリ内のデータのコレクションが互いに接近していない多くの部分に分割されたときに発生します。これは通常、外部の断片化がすでに発生しているストレージに大きなオブジェクトを挿入しようとした結果です。たとえば、ファイルシステム内のファイルは通常、ブロックまたはクラスターと呼ばれる単位で管理されます。ファイルシステムを作成すると、ファイルブロックを連続して保存するための空き領域ができます。これにより、ファイルの迅速な読み取りと書き込みが可能になります。ただし、ファイルが追加、削除、およびサイズが変更されると、空き領域は外部的に断片化され、新しいデータを配置するための小さな穴だけが残ります。新しいファイルが書き込まれるとき、または既存のファイルが拡張されるとき、オペレーティングシステムは、使用可能な穴に収まるように、新しいデータを新しい非連続データブロックに配置します。新しいデータブロックは必然的に分散し、読み取り/書き込みヘッドのシーク時間回転待ち時間のためにアクセスが遅くなり、追加の場所を管理するために追加のオーバーヘッドが発生します。これは、ファイルシステムの断片化と呼ばれます。

既知のサイズの新しいファイルを書き込むときに、そのファイルよりも大きい空の穴がある場合、オペレーティングシステムは、ファイルをそれらの穴のいずれかに配置することにより、データの断片化を回避できます。これらの潜在的な穴のどれをファイルに配置するかを選択するためのさまざまなアルゴリズムがあります。それらのそれぞれは、ビンパッキング問題のヒューリスティックな近似解です。「最適」アルゴリズムは、十分な大きさの最小の穴を選択します。「最悪の適合」アルゴリズムは、最大の穴を選択します。ファーストフィットアルゴリズム」は、十分な大きさの最初の穴を選択します。「ネクストフィット」アルゴリズムは、各ファイルが書き込まれた場所を追跡します。「次の適合」アルゴリズムは「最初の適合」よりも高速であり、「最初の適合」は「最初の適合」よりも高速です。[4]

圧縮によって外部の断片化を排除できるのと同様に、関連する部分が互いに接近するようにデータストレージを再配置することで、データの断片化を排除できます。たとえば、最適化ツールの主な役割は、各ファイルのブロックが連続するようにディスク上のブロックを再配置することです。ほとんどの最適化ユーティリティは、空き領域の断片化を削減または排除しようとします。自動メモリ管理を実行するユーティリティである一部の移動ガベージコレクターは、関連するオブジェクトを互いに近づけて移動し(これは圧縮と呼ばれます)、キャッシュのパフォーマンスを向上させます。

データの断片化を経験しないシステムには4種類あり、常にすべてのファイルを連続して保存します。4種類すべてに、少なくとも一時的なデータの断片化を許可するシステムと比較して、重大な欠点があります。

  1. 各ファイルを連続して書き込むだけですファイルを保持するのに十分な連続した空き領域がまだない場合、システムはすぐにファイルの保存に失敗します。削除されたファイルからファイルを保存するのに十分な数の空き領域がある場合でも、システムはすぐにファイルの保存に失敗します。
  2. ファイルを保持するのに十分な連続した空き領域がまだない場合は、コピーコレクターを使用して、ファイルを保持するのに十分な大きさの1つの連続した空き領域に多くの小さな空き領域を変換します。これには、ファイルをフラグメントに分割し、それらのフラグメントを使用可能な空き領域に配置するよりもはるかに時間がかかります。
  3. 固定サイズのブロックストレージを介して、ファイルを任意の空きブロックに書き込みますプログラマーが小さすぎる固定ブロックサイズを選択すると、ファイルを保存するのに十分な数の空きブロックがある場合でも、システムはすぐに一部のファイル(ブロックサイズよりも大きいファイル)の保存に失敗します。プログラマーが大きすぎるブロックサイズを選択すると、内部の断片化に多くのスペースが浪費されます。
  4. 一部のシステムは、動的割り当てを完全に回避し、必要なすべての可能なファイル用の(連続した)スペースを事前に保存します。たとえば、MultiFinderは、アプリケーションのプログラマーが要求したRAMの量に応じて、起動時に各アプリケーションにRAMのチャンクを事前に割り当てます。必要になります。

概要

外部の断片化と比較すると、オーバーヘッドと内部の断片化は、メモリの浪費とパフォーマンスの低下という点でほとんど損失をもたらしません。これは次のように定義されます。

0%の断片化は、すべての空きメモリが1つの大きなブロックにあることを意味します。たとえば、100 MBの空きメモリが存在する場合、断片化は90%ですが、ストレージ用のメモリの最大の空きブロックはわずか10MBです。

プログラムは通常、RAMストレージ要求を連続したブロックで処理する必要があるため、外部フラグメンテーションはプライマリメモリ(RAM)ストレージシステムよりもファイルシステムで問題が少ない傾向がありますが、ファイルシステムは通常、任意のコレクションを使用できるように設計されています論理的に連続しているように見えるファイルをアセンブルするための使用可能なブロック(フラグメント)の数。したがって、非常に断片化されたファイルまたは多数の小さなファイルがフルボリュームから削除され、次に新しく解放されたスペースと等しいサイズの新しいファイルが作成された場合、新しいファイルは、削除によって解放された同じ断片を単に再利用します。削除されたファイルが1つのファイルの場合、新しいファイルは古いファイルと同じように断片化されますが、いずれの場合も、すべての(高度に断片化された)空き領域を使用して新しいファイルを作成することに支障はありません。一方、RAMでは、

問題

ストレージ障害

断片化によって引き起こされる最も深刻な問題は、リソースの早期枯渇が原因でプロセスまたはシステムに障害が発生することです。連続するブロックを保存する必要があり、保存できない場合、障害が発生します。断片化により、リソースが十分にある場合でもこれが発生しますが、連続した量ではありません。たとえば、コンピュータに4 GiBのメモリがあり、2 GiBが空いているが、メモリが1 MiBの使用、1 MiBの空きの交互のシーケンスで断片化されている場合、2つの連続したGiBのメモリの要求は満たされません。 GiBの合計は無料です。

これを回避するために、アロケータは、失敗する代わりに、デフラグ(またはメモリ圧縮サイクル)または主要なガベージコレクションサイクルなどの他のリソース再利用をトリガーして、要求を満たすことができるようにすることができます。これによりプロセスを進めることができますが、パフォーマンスに深刻な影響を与える可能性があります。

パフォーマンスの低下

断片化は、いくつかの理由でパフォーマンスの低下を引き起こします。最も基本的に、フラグメンテーションは、リソースの割り当てとアクセスに必要な作業を増やします。たとえば、ハードドライブまたはテープドライブでは、シーケンシャルデータの読み取りは非常に高速ですが、別のアドレスへのシークは遅いため、断片化されたファイルの読み取りまたは書き込みには多数のシークが必要であり、摩耗が大きくなるだけでなく、はるかに遅くなります。デバイス。さらに、リソースが断片化されていない場合は、空き領域の先頭から1つのブロックを返すだけで、割り当て要求を満たすことができます。ただし、フラグメント化されている場合、リクエストには十分な大きさの空きブロックを検索する必要があります。これには時間がかかる場合があります。または、リクエストをいくつかの小さなブロックで実行する必要があります(可能な場合)。その結果、この割り当てがフラグメント化されます。

微妙な問題は、個々のデータではなくブロックを保持しているキャッシュが原因で、断片化によってキャッシュが早期に使い果たされ、スラッシングが発生する可能性があることです。たとえば、プログラムに256 KiBのワーキングセットがあり、256 KiBキャッシュ(たとえば、L2命令+データキャッシュ)を備えたコンピューターで実行されているとすると、ワーキングセット全体がキャッシュに収まり、少なくともキャッシュヒットの条件。さらに、64のトランスレーションルックアサイドバッファ(TLB)エントリがあり、それぞれが4 KiBページであるとします。各メモリアクセスには仮想から物理への変換が必要です。これは、ページがキャッシュ(ここではTLB)にある場合に高速です。ワーキングセットが断片化されていない場合、正確に64ページ(ページワーキングセットは64ページになります)、すべてのメモリルックアップはキャッシュから提供できます。ただし、ワーキングセットが断片化されていると、64ページに収まらず、スラッシングが原因で実行速度が低下します。操作中にページがTLBに繰り返し追加され、TLBから削除されます。したがって、システム設計のキャッシュサイズには、断片化を考慮したマージンを含める必要があります。

メモリの断片化は、システム管理者が直面する最も深刻な問題の1つです。[要出典]時間の経過とともに、システムパフォーマンスの低下につながります。最終的に、メモリの断片化により、(アプリケーションで使用可能な)空きメモリが完全に失われる可能性があります。

メモリの断片化は、カーネル プログラミングレベルの問題です。アプリケーションのリアルタイムコンピューティングに、断片化レベルは99%に達する可能性があり、システムクラッシュやその他の不安定性につながる可能性があります。[要出典]このタイプのシステムクラッシュは、メモリの断片化のレベルの重大な上昇を予測することが不可能であるため、回避するのが難しい場合があります。ただし、過度のメモリフラグメンテーションが発生した場合、システムがすべてのプログラムを実行し続けることはできない場合がありますが、適切に設計されたシステムは、システム自体が使用する一部のメモリブロックを移動することにより、重大なフラグメンテーション状態から回復できる必要があります。空きメモリをより少ない、より大きなブロックに統合できるようにするため、または最悪の場合、一部のプログラムを終了してメモリを解放し、結果として得られる空きメモリの合計を最適化するため。これにより、少なくともシステム障害という意味での真のクラッシュを回避し、システムが一部のプログラムの実行を継続したり、プログラムデータを保存したりできるようになります。断片化はシステムソフトウェア設計の現象であることに注意することも重要です。さまざまなソフトウェアがさまざまな程度で断片化の影響を受けやすく、メモリの断片化の結果としてプロセスを強制的にシャットダウンしたり強制終了したりしないシステムを設計することができます。

類似の現象

断片化はメモリ割り当ての問題として最もよく知られていますが、他のリソース、特にプロセッサでも同様の現象が発生します。[5]たとえば、プリエンプティブマルチタスクにタイムシェアリングを使用しているが、プロセスがブロックされているかどうかをチェックしないシステムでは、タイムスライスの一部で実行された後、ブロックされて残りのプロセスを続行できないプロセスタイムスライスの内部断片化が発生するため、タイムスライスは時間を浪費します。より基本的には、タイムシェアリング自体が、単一の途切れのない実行ではなく、断片化されたタイムスライスでプロセスを実行するため、プロセスの外部断片化を引き起こします。結果として生じるコストプロセスの切り替えと、同じキャッシュを使用する複数のプロセスからのキャッシュプレッシャーの増加により、パフォーマンスが低下する可能性があります。

並行システム、特に分散システムでは、プロセスのグループが進行するために相互作用する必要がある場合、プロセスが別々の時間または別々のマシン(時間またはマシン間で断片化されている)でスケジュールされている場合、相互の待機または通信に費やされる時間相互に接続すると、パフォーマンスが大幅に低下する可能性があります。代わりに、パフォーマンスの高いシステムでは、グループの同時スケジューリングが必要です。[5]

一部のフラッシュファイルシステムには、「デッドスペース」と「ダークスペース」を含むいくつかの異なる種類の内部フラグメンテーションがあります。[6]

も参照してください

参照

  1. ^ ヌル、リンダ; Lobur、Julia(2006)。コンピュータの組織とアーキテクチャの要点ジョーンズとバートレットの出版社。p。315. ISBN 97807637376962021年7月15日取得
  2. ^ 「パーティション分割、パーティションサイズおよびドライブレタリング」PCガイド。2001年4月17日2012年1月20日取得
  3. ^ 「スイッチ:セクターコピー」ノートンライフロック。2001-01-14 2012年1月20日取得
  4. ^ D.サマンタ。 「古典的なデータ構造」 2004年。p。76
  5. ^ a b Ousterhout、JK(1982)。「並行システムのスケジューリング手法」(PDF)分散コンピューティングシステムに関する第3回国際会議の議事録pp。22–30。
  6. ^ エイドリアンハンター。 「UBIFSの設計の簡単な紹介」2008.etcp。8.8。

ソース