Loading article…
コンピュータのストレージにおいて、断片化とは、コンピュータシステム内でデータが小さな断片に分散され、コンピュータメモリやハードドライブなどのストレージスペースが非効率的に使用される現象であり、容量やパフォーマンス、あるいはその両方が低下します。断片化の具体的な影響は、使用されているストレージ割り当てシステムと断片化の具体的な形態によって異なります。多くの場合、断片化によってストレージスペースが「無駄」になり、メモリ不足のためにプログラムの実行効率が低下する傾向があります。
メインメモリの断片化とは、コンピュータプログラムがコンピュータシステムからメモリブロックを要求すると、そのブロックがチャンク単位で割り当てられる現象です。コンピュータプログラムはチャンクの使用を終えると、それをシステムに解放し、後で別のプログラムまたは同じプログラムに再度割り当てられるようにします。チャンクのサイズと保持時間はプログラムによって異なります。コンピュータプログラムは、その実行期間中に、多くのメモリチャンクを要求し、解放することができます。
メモリの断片化は、プログラムがメモリブロックを要求し、そのプログラムに割り当てられたものの、プログラムがそれを解放（コミット解除）していない場合に発生する可能性があります。[ 1 ]これにより、理論的には「利用可能」な未使用のメモリが割り当て済みとしてマークされ、グローバルに利用可能なメモリの量が減少し、プログラムがメモリを要求してアクセスすることが難しくなります。
プログラム起動時は、空きメモリ領域は長く連続しています。しかし、時間経過や使用に伴い、長く連続していた領域は次第に小さな連続領域へと断片化されていきます。最終的には、プログラムが大きな連続メモリ領域を確保することが不可能になる場合もあります。
データや空き領域が複数の断片に分割されると、断片化が発生します。断片化は、速度やシンプルさの向上と引き換えに受け入れられることがよくあります。プロセッサなどの他のリソースでも同様の現象が発生します（下記参照）。
メモリの断片化には、内部断片化と外部断片化がある。内部断片化は、メモリ割り当てによって必要以上の領域が確保され、空き領域が無駄になる場合に発生する。外部断片化は、空きメモリが断片化され、より大きな新しいブロックの割り当てが妨げられる場合に発生する。
現代のオペレーティングシステムでは、プログラムは固定サイズのページを受け取り、それを自身の様々な部分に割り当てます（多くの場合、mallocなどのアロケータによって）。その結果、メモリ割り当てには2つの階層が存在し、それぞれが内部および外部の断片化を引き起こす可能性があります。1つはメモリ割り当て器（mallocなど）のレベル、もう1つはページレベルです。（古いオペレーティングシステムではページを使用しない場合もありますが、プログラムはOSへの過剰な呼び出しを避けるために、依然として2階層システムを使用する傾向があります。）
メモリ割り当てに関する規則により、コンピュータのメモリは必要以上に割り当てられることがあります。このような場合、余剰メモリは無駄になります。この場合、スラック領域と呼ばれる使用できないメモリは、割り当てられた領域内に含まれます。固定パーティションと呼ばれるこの構成では、メモリの使用効率が低下します。つまり、どんなに小さなプロセスでも、パーティション全体を占有してしまうのです。この無駄は内部断片化と呼ばれます。
アロケータレベルでの内部断片化は、一度発生すると修復が非常に困難です。通常、それを解消する最善の方法は設計変更です。例えば、動的メモリ割り当てでは、メモリプールによってオーバーヘッド領域をより多くのオブジェクトに分散させることで、内部断片化を大幅に削減できます。
ページレベルでの内部断片化（アロケータレベルでは外部断片化）は、割り当てられたブロックを移動することで解消できます。これには、割り当てられたブロックの移動を反映するようにポインタを編集する必要がありますが、ガベージコレクション機能のない言語では困難です。圧縮型ガベージコレクタは、仮想アドレス空間を圧縮する際にポインタの修正を実行します。[ 5 ]
外部断片化は、空きメモリが小さなブロックに分割され、その間に割り当て済みメモリが混在する場合に発生します。これは、プログラムが使用するメモリを効率的に配置できない特定のストレージ割り当てアルゴリズムの弱点です。結果として、空きストレージは存在するものの、アプリケーションの要求を満たすには個々に小さすぎる断片に分割されるため、実質的に使用できなくなります。「外部」という用語は、使用できないストレージが割り当て済み領域の外側にあることを指します。
例えば、プログラムが連続する3つのメモリブロックを割り当て、その後中央のブロックを解放する状況を考えてみましょう。メモリ割り当て器は、この解放されたメモリブロックを今後の割り当てに使用できます。しかし、割り当てようとしているメモリのサイズがこの解放されたブロックよりも大きい場合は、このブロックを使用することはできません。
ページレベルでの外部断片化は、アプリケーション自身の割り当て器またはガベージコレクタによって、ページを解放してOSに返却（コミット解除）することで回収できます。
ページレベルでの外部断片化は、物理アドレス空間内のページを移動し、ページテーブルを編集してそれに合わせて、オペレーティングシステムによって再利用することもできます。これはページマイグレーションと呼ばれます。仮想メモリのアドレスは変更されないため、アプリケーションはこのプロセスを認識しません。[ 6 ]
データ断片化とは、メモリ内のデータ群が互いに近接していない多数の断片に分割される現象です。ファイルシステムは、ブロックデバイスブロック呼ばれる小さな固定サイズの単位でデータを管理しブロックまたはクラスタと呼ばれる独自の単位に抽象化します。
ファイルシステムが作成されると、ファイルブロックを連続して格納するための空き領域が確保されます。これにより、ファイルの高速なシーケンシャル読み書きが可能になります。しかし、ファイルの追加、削除、サイズ変更が行われると、空き領域は外部的に断片化され、新しいデータを配置できる小さな空き領域しか残らなくなります。これが外部断片化です。ファイルシステムは、断片化を念頭に置いて設計されている点でメモリとは異なります。新しいファイルが書き込まれるとき、または既存のファイルが拡張されるとき、オペレーティングシステムは新しいデータを、利用可能な空き領域に収まるように、新しい非連続のクラスタグループ（エクステント）に配置します。新しいデータブロックは必然的に分散されるため、シーク時間と読み書きヘッドの回転遅延によってアクセスが遅くなり、追加の場所を管理するためのオーバーヘッドも発生します。これがファイルシステム断片化です。多くの小さな断片に分割されたファイルが削除されると、同様に小さな空き領域しか残らないため、影響はさらに大きくなります。
既知のサイズの新しいファイルを書き込むとき、そのファイルよりも大きい空き領域があれば、オペレーティングシステムは、それらの空き領域のいずれかにファイルを配置することで、データの断片化を回避できます。これらの空き領域のうち、どの領域にファイルを配置するかを選択するためのアルゴリズムはいくつかあり、それぞれがビンパッキング問題に対するヒューリスティックな近似解です。「ベストフィット」アルゴリズムは、十分な大きさの最小の空き領域を選択します。「ワーストフィット」アルゴリズムは、最大の空き領域を選択します。「ファーストフィット」アルゴリズムは、十分な大きさの最初の空き領域を選択します。「ネクストフィット」アルゴリズムは、各ファイルが書き込まれた場所を追跡します。「ネクストフィット」アルゴリズムは「ファーストフィット」よりも高速で、「ファーストフィット」は「ベストフィット」よりも高速で、「ベストフィット」は「ワーストフィット」と同じ速度です。[ 7 ]
圧縮によって外部断片化を解消できるのと同様に、（外部）データ断片化は、関連する断片を近接するようにデータストレージを再配置することによって解消できます。たとえば、デフラグツールの主な役割は、ディスク上のブロックを再配置して、各ファイルのブロックが連続するようにすることです。ほとんどのデフラグユーティリティは、空き領域の断片化を減らすか解消しようとします。自動メモリ管理を実行するユーティリティである一部の移動型ガベージコレクタは、キャッシュのパフォーマンスを向上させるために、関連するオブジェクトを近接して移動します（これは圧縮と呼ばれます）。
4種類のシステムは、（外部）データ断片化を一切経験せず、常にすべてのファイルを連続して保存します。これら4種類のシステムはすべて、少なくとも一時的なデータ断片化を許容するシステムと比較して、重大な欠点を持っています。
内部断片化は、ファイルシステム全体のファイル割り当てを悪化させるような全体的な影響がないため、ファイルシステム上で問題になることはほとんどありません。ただし、ストレージ領域のオーバーヘッドが発生し、影響を受ける多数の小さなファイルへのアクセスが遅くなります（ファイルセット全体が「断片化」されているとみなされます）。この問題に対処するため、ext4やbtrfsなどのファイルシステムには、これらのファイルにクラスタを割り当てることを避け、代わりにinode （ファイルレコード）に直接格納するインラインデータまたはインラインファイル機能があります。[ 8 ]
外部断片化と比較すると、オーバーヘッドと内部断片化は、メモリの無駄遣いやパフォーマンスの低下という点で損失が少ない。これは次のように定義される。
断片化率が0%とは、空きメモリがすべて単一の大きなブロックに収まっている状態を意味します。断片化率が90%というのは、例えば100MBの空きメモリがあるにもかかわらず、ストレージ用の最大の空きメモリブロックがわずか10MBしかない場合などです。
ファイルシステムでは、外部断片化は主記憶装置（RAM）に比べて問題になりにくい傾向があります。これは、プログラムは通常、RAMストレージ要求を連続したブロックで満たす必要があるのに対し、ファイルシステムは利用可能なブロック（断片）の任意の集合を使用して、論理的に連続しているように見えるファイルを組み立てられるようになっているためです。したがって、断片化が激しいファイルや多数の小さなファイルがボリューム全体から削除され、新しく解放された領域と同じサイズの新しいファイルが作成されると、新しいファイルは削除によって解放された同じ断片を再利用します。削除されたのが1つのファイルだった場合、新しいファイルは古いファイルと同じように断片化されますが、いずれにしても、すべての（断片化が激しい）空き領域を使用して新しいファイルを作成することに障害はありません。一方、RAMでは、使用されるストレージシステムは、小さな非連続の空きブロックからの要求を満たすために大きなブロックを組み立てられないことが多く、そのため要求を満たすことができず、プログラムはそのメモリを必要とする処理を進めることができません（要求を複数の小さな個別の要求として再発行できる場合を除く）。
断片化によって引き起こされる最も深刻な問題は、リソースの早期枯渇によりプロセスやシステムが障害を起こすことです。連続したブロックを格納する必要があるにもかかわらず格納できない場合、障害が発生します。断片化は、リソースが十分にある場合でも、連続した量でなければ、このような障害を引き起こします。たとえば、コンピュータに4 GiBのメモリがあり、2 GiBが空いている場合でも、メモリが1 MiB使用、1 MiB空きというように交互に断片化されている場合、合計2 GiBの空きがあっても、1 GiBの連続したメモリを要求することはできません。
これを回避するため、アロケータはエラーになる代わりに、デフラグメンテーション（またはメモリ圧縮サイクル）や、メジャーガベージコレクションサイクルなどのリソース解放処理をトリガーし、要求を満たせるように試みる場合があります。これにより処理は続行できますが、パフォーマンスに深刻な影響を与える可能性があります。
断片化は、さまざまな理由でパフォーマンスの低下を引き起こします。最も基本的な理由は、断片化によってリソースの割り当てとアクセスに必要な作業が増加することです。たとえば、ハードドライブやテープドライブでは、シーケンシャルなデータ読み取りは非常に高速ですが、別のアドレスへのシークは低速です。そのため、断片化されたファイルの読み書きには多数のシークが必要となり、デバイスの摩耗が大きくなるだけでなく、処理速度も大幅に低下します。さらに、リソースが断片化されていない場合、割り当て要求は空き領域の先頭から単一のブロックを返すだけで簡単に満たすことができます。しかし、リソースが断片化されている場合、要求を満たすには、十分な大きさの空きブロックを検索する必要があり、これには時間がかかる場合があります。あるいは、複数の小さなブロックで要求を満たす必要があり（可能な場合）、結果として割り当てが断片化され、複数の断片を管理するための追加のオーバーヘッドが発生します。
より微妙な問題は、キャッシュが個々のデータではなくブロックを保持しているため、断片化によってキャッシュが早期に枯渇し、スラッシングが発生する可能性があることです。たとえば、プログラムのワーキングセットが 256 KiB で、256 KiB のキャッシュ (L2 命令 + データ キャッシュ) を備えたコンピュータで実行されているとします。この場合、ワーキングセット全体がキャッシュに収まるため、少なくともキャッシュ ヒットの観点からは高速に実行されます。さらに、4 KiBページごとに 64 個のトランスレーション ルックアサイド バッファ(TLB) エントリがあるとします。各メモリ アクセスには仮想から物理への変換が必要ですが、ページがキャッシュ (ここでは TLB) にある場合は高速です。ワーキングセットが断片化されていない場合、正確に 64 ページに収まり (ページワーキングセットは 64 ページになります)、すべてのメモリ検索はキャッシュから提供できます。しかし、ワーキングセットが断片化している場合、64ページに収まらず、スラッシングによって実行速度が低下します。これは、動作中にTLBへのページの追加と削除が繰り返されるためです。したがって、システム設計におけるキャッシュサイズには、断片化を考慮した余裕を持たせる必要があります。
メモリ断片化は、システム管理者が直面する最も深刻な問題の一つです。時間の経過とともに、システムパフォーマンスの低下を招き、最終的には（アプリケーションが使用可能な）空きメモリの完全な喪失につながる可能性があります。
メモリ断片化は、カーネルプログラミングレベルの問題です。アプリケーションのリアルタイム処理中、断片化レベルは99%にも達することがあり、システムクラッシュやその他の不安定性を引き起こす可能性があります。このようなシステムクラッシュは、メモリ断片化レベルの深刻な上昇を予測することが不可能なため、回避が困難です。しかし、メモリ断片化が過剰になった場合、システムがすべてのプログラムの実行を継続できない可能性がありますが、適切に設計されたシステムであれば、システム自身が使用するメモリブロックの一部を移動させて空きメモリをより少ない大きなブロックに統合したり、最悪の場合は一部のプログラムを終了させてメモリを解放し、結果として得られた空きメモリの合計をデフラグすることで、深刻な断片化状態から回復できるはずです。これにより、少なくともシステム障害という意味での真のクラッシュは回避され、システムは一部のプログラムの実行を継続したり、プログラムデータを保存したりすることができます。
メモリ断片化はシステムソフトウェア設計における現象であり、ソフトウェアの種類によって断片化の影響を受けやすい度合いは異なります。また、メモリ断片化によってプロセスが強制終了したりシャットダウンされたりすることが決してないシステムを設計することも可能です。
メモリ割り当ての問題としてフラグメンテーションが最もよく知られていますが、プロセッサをはじめとする他のリソースでも同様の現象が発生します。 [ 9 ]例えば、プリエンプティブマルチタスクにタイムシェアリングを使用するシステムで、プロセスがブロックされているかどうかをチェックしない場合、タイムスライスの一部で実行された後、ブロックされて残りのタイムスライスで実行できなくなったプロセスは、結果として生じるタイムスライスの内部フラグメンテーションのために時間を浪費します。より根本的には、タイムシェアリング自体が、単一の途切れない実行ではなく、断片化されたタイムスライスでプロセスを実行するため、プロセスの外部フラグメンテーションを引き起こします。その結果、プロセス切り替えのコストと、同じキャッシュを使用する複数のプロセスによるキャッシュ圧力の増加により、パフォーマンスが低下する可能性があります。
並行システム、特に分散システムでは、一連のプロセスが相互に作用して進行する必要がある場合、プロセスが別々の時間にスケジュールされたり、別々のマシン上でスケジュールされたり（時間やマシンに分散されたり）すると、互いを待ったり、互いに通信したりするのに費やされる時間がパフォーマンスを著しく低下させる可能性があります。その代わりに、高性能なシステムでは、グループの同時スケジューリングが必要です。 [ 9 ]
フラッシュファイルシステムの中には、「デッドスペース」や「ダークスペース」を含む、いくつかの異なる種類の内部断片化が存在するものがある。[ 10 ]
{{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)