Fragmentierung (Computer)

Für die Fragmentierung des Dateisystems siehe Dateisystemfragmentierung.

Im Computerspeicher, Zersplitterung ist ein Phänomen, in dem Speicherplatz, Hauptspeicher oder Zweitlager, wird ineffizient verwendet, reduziert Kapazität oder Leistung und oft beides. Die genauen Konsequenzen der Fragmentierung hängen vom spezifischen System der verwendeten Speicherallokation und der besonderen Form der Fragmentierung ab. In vielen Fällen führt die Fragmentierung dazu, dass der Speicherplatz "verschwendet" wird, und in diesem Fall bezieht sich der Begriff auch auf den verschwendeten Raum selbst.

Arten der Fragmentierung

Es gibt drei verschiedene, aber verwandte Fragmentierungsformen: externe Fragmentierung, interne Fragmentierung und Datenfragmentierung, die isoliert oder konjunktion vorhanden sein können. Die Fragmentierung wird häufig als Gegenleistung für Verbesserungen der Geschwindigkeit oder Einfachheit akzeptiert. Für andere Ressourcen wie Prozessoren treten analoge Phänomene auf. siehe unten.

Grundprinzip

Wenn ein Computerprogramm Speicherblöcke aus dem Computersystem anfordert, werden die Blöcke in Stücken zugewiesen. Wenn das Computerprogramm mit einem Stück fertig ist, kann es es wieder zum System freigeben, sodass es später erneut an ein anderes oder das gleiche Programm zugewiesen werden kann. Die Größe und die Zeit, die ein Stück von einem Programm gehalten wird, variiert. Während seiner Lebensdauer kann ein Computerprogramm viele Speicherbrocken anfordern und frei.

Wenn ein Programm gestartet wird, sind die kostenlosen Speicherbereiche lang und angrenzend. Im Laufe der Zeit und im Gebrauch werden die langen zusammenhängenden Regionen in immer kleinere und kleinere Bereiche fragmentiert. Schließlich kann es für das Programm unmöglich werden, große zusammenhängende Speicherbrocken zu erhalten.

Typen

Interne Fragmentierung

Speicherpaging erzeugt interne Fragmentierung, weil eine Ganze Seitenrahmen wird zugewiesen, ob so viel Speicher benötigt wird oder nicht.[1] Aufgrund der Regeln, die regieren Speicherzuweisung, mehr Computerspeicher ist manchmal zugewiesen als nötig. Beispielsweise kann der Speicher nur für Programme in Stücken (normalerweise ein Vielfaches von 4 Bytes) bereitgestellt werden. Wenn ein Programm möglicherweise 29 Bytes anfordert, erhält er tatsächlich einen Teil von 32 Bytes. In diesem Fall wird der überschüssige Speicher verschwendet. In diesem Szenario ist das unbrauchbare Gedächtnis in einer zugewiesenen Region enthalten. Diese Anordnung, die als feste Partitionen bezeichnet wird, leidet unter ineffizienten Speichergebrauch - jeder Prozess, egal wie klein, nimmt eine ganze Partition ein. Dieser Abfall wird genannt interne Fragmentierung.[2][3]

Im Gegensatz zu anderen Arten der Fragmentierung ist die interne Fragmentierung schwer zurückzugewinnen. Normalerweise ist der beste Weg, es zu entfernen, mit einer Designänderung. Zum Beispiel in Dynamische Speicherzuweisung, Speicherpools Schneiden Sie die interne Fragmentierung drastisch durch, indem Sie den Raumaufwand über eine größere Anzahl von Objekten verteilen.

Externe Fragmentierung

Eine externe Fragmentierung entsteht, wenn der freie Speicher in kleine Blöcke getrennt ist und durch zugewiesenes Speicher durchsetzt wird. Es handelt sich um eine Schwäche bestimmter Speicherallokationsalgorithmen, wenn sie den Speicher, der von Programmen effizient verwendet wird, nicht bestellt. Das Ergebnis ist, dass, obwohl freier Speicher verfügbar ist, aber effektiv unbrauchbar ist, da er in Stücke unterteilt ist, die zu klein sind, um die Anforderungen der Anwendung zu erfüllen. Der Begriff "externe" bezieht sich auf die Tatsache, dass sich der unbrauchbare Speicher außerhalb der zugewiesenen Regionen befindet.

Betrachten Sie beispielsweise eine Situation, in der ein Programm drei kontinuierliche Speicherblöcke zuteilt und dann den mittleren Block befreit. Der Speicherallocator kann diesen freien Speicherblock für zukünftige Zuweisungen verwenden. Es kann diesen Block jedoch nicht verwenden, wenn der zugewiesene Speicher größer ist als dieser freie Block.

Eine externe Fragmentierung tritt auch in Dateisystemen auf, da viele Dateien verschiedener Größen erstellt werden, die Größe ändern und gelöscht werden. Der Effekt ist noch schlimmer, wenn eine Datei, die in viele kleine Stücke unterteilt ist, gelöscht wird, da dies ähnlich kleine Regionen freier Räume verlässt.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 Kommentare
Beginnen Sie mit dem gesamten Speicher für Speicher.
EIN B C Zugewandte drei Blöcke A, B und C von Größe 0x1000.
EIN C Befreit Block B. Beachten Sie, dass der von B verwendete Speicher für einen Block nicht mehr als die Größe von B enthalten ist.
EIN C Block C bewegte sich in den leeren Schlitz von Block B, sodass der verbleibende Raum für einen größeren Block der Größe 0x4000 verwendet werden kann.

Datenfragmentierung

Datenfragmentierung tritt auf, wenn eine Sammlung von Daten im Speicher in viele Stücke unterteilt ist, die nicht nahe beieinander liegen. Es ist in der Regel das Ergebnis des Versuchs, ein großes Objekt in die Speicherung einzufügen, die bereits eine externe Fragmentierung erlitten hat. Zum Beispiel Dateien in a Dateisystem werden normalerweise in Einheiten bezeichnet, die genannt werden Blöcke oder Cluster. Wenn ein Dateisystem erstellt wird, gibt es freien Speicherplatz, um Dateiblöcke gemeinsam zu speichern zusammenhängend. Dies ermöglicht eine schnelle sequentielle Datei liest und schriftlich. Wenn die Dateien jedoch hinzugefügt, entfernt und verändert werden, wird der freie Speicherplatz extern fragmentiert, so dass nur kleine Löcher für neue Daten platziert werden können. Wenn eine neue Datei geschrieben wird oder wenn eine vorhandene Datei erweitert wird, stellt das Betriebssystem die neuen Daten in neue nicht verknüpfte Datenblöcke ein, die in die verfügbaren Löcher passen. Die neuen Datenblöcke sind notwendigerweise verstreut und verlangsamt den Zugriff auf durchzuführen Zeit suchen und Rotationslatenz des Lese-/Schreibkopfes und zusätzlichen Aufwand, um zusätzliche Standorte zu verwalten. Das nennt man Dateisystemfragmentierung.

Beim Schreiben einer neuen Datei mit einer bekannten Größe kann das Betriebssystem die Datenfragmentierung vermeiden, indem die Datei in eines dieser Löcher eingesetzt wird. Es gibt eine Vielzahl von Algorithmen, um auszuwählen, welche dieser potenziellen Löcher die Datei einstellen; Jeder von ihnen ist a Heuristik ungefähre Lösung für die Packungsproblem. Der Algorithmus "Best Fit" wählt das kleinste Loch, das groß genug ist. Der Algorithmus "Worst Fit" wählt das größte Loch. Das "Erstanpassungsalgorithmus"Wählt das erste Loch, das groß genug ist. Der Algorithmus" Next Fit "verfolgt, wo jede Datei geschrieben wurde. Der Algorithmus" Nächster Anpassung "ist schneller als" Erstverpackt ", was wiederum schneller als" Beste Passform "ist, als" Beste Passform "ist, ist schneller als" Beste Passform ". Das ist die gleiche Geschwindigkeit wie "schlechteste Passform".[4]

So wie die Verdichtung die externe Fragmentierung beseitigen kann, kann die Datenfragmentierung durch Neubeschaffung der Datenspeicherung beseitigt werden, sodass verwandte Teile nahe beieinander liegen. Zum Beispiel die Hauptaufgabe von a Defragmentierung Das Tool besteht darin, Blöcke auf der Festplatte neu zu ordnen, damit die Blöcke jeder Datei zusammenhängend sind. Die meisten Defragmentierversorger versuchen auch, die Fragmentierung des freien Raums zu reduzieren oder zu beseitigen. Einige bewegen sich Müllsammler, Dienstprogramme, die eine automatische Speicherverwaltung ausführen, verschieben auch verwandte Objekte nahe beieinander (dies heißt Kompakte) Um die Cache -Leistung zu verbessern.

Es gibt vier Arten von Systemen, bei denen es niemals Datenfragmentierung erlebt - sie speichern immer alle Dateien zusammenhängig. Alle vier Arten haben erhebliche Nachteile im Vergleich zu Systemen, die zumindest einige temporäre Datenfragmentierung ermöglichen:

  1. Schreiben Sie einfach jede Datei zusammenhängend. Wenn es nicht noch nicht genügend freien Speicherplatz gibt, um die Datei zu halten, kann das System die Datei sofort nicht speichern - auch wenn es viele kleine Teile freier Speicherplatz aus gelöschten Dateien gibt, die mehr als genug addieren, um die Datei zu speichern.
  2. Wenn es nicht noch nicht genügend freiem freien Speicherplatz gibt, um die Datei zu halten, verwenden Sie a Kopieren des Sammlers Um viele kleine Teile freier Speicherplatz in eine zusammenhängende freie Region umzuwandeln, die groß genug ist, um die Datei zu halten. Dies dauert viel mehr Zeit, als die Datei in Fragmente zu zerlegen und diese Fragmente in den verfügbaren freien Speicherplatz zu bringen.
  3. Schreiben Sie die Datei in einen jeden freien Block durch Speicher mit fester Größe Blöcke. Wenn ein Programmierer eine feste Blockgröße zu klein wählt, kann das System einige Dateien sofort nicht speichern - Dateien größer als die Blockgröße -, auch wenn es viele kostenlose Blöcke gibt, die mehr als genug addieren, um die Datei zu speichern. Wenn ein Programmierer eine zu große Blockgröße auswählt, wird bei interner Fragmentierung viel Platz verschwendet.
  4. Einige Systeme vermeiden die dynamische Allokation vollständig, vor dem Speicherplatz (zusammenhängender) Speicherplatz für alle möglichen Dateien, die sie benötigen-zum Beispiel, Multifinder Alkohol wirkt einen Teil des RAM für jede Anwendung vor, da er gemäß den Angaben der Anwendung behauptete, dass sie behauptete.

Überblick

Im Vergleich zur externen Fragmentierung erklären Overhead- und interne Fragmentierung nur geringe Verluste hinsichtlich des Verschwendung von Speicher und einer verringerten Leistung. Es ist definiert als:

Die Fragmentierung von 0% bedeutet, dass der gesamte freie Speicher in einem einzigen großen Block befindet. Die Fragmentierung beträgt 90% (zum Beispiel), wenn ein freier Speicher von 100 MB vorhanden ist, der größte freie Speicherblock für die Speicherung nur 10 MB beträgt.

Die externe Fragmentierung ist in tendenziell geringeren Problemen in Dateisystemen als in Primärspeicher (RAM -Speichersystemen), da Programme normalerweise erforderlich sind, um mit zusammenhängenden Blöcken erfüllt zu werden. Dateisysteme sind jedoch in der Regel so konzipiert, dass sie in der Lage sind, eine Sammlung zu verwenden von verfügbaren Blöcken (Fragmenten), um eine Datei zusammenzustellen, die logischerweise zusammenhängend erscheint. Wenn eine hoch fragmentierte Datei oder viele kleine Dateien aus einem vollen Volumen gelöscht werden und dann eine neue Datei mit Größe gleich dem neu befreiten Speicherplatz erstellt wird, wird die neue Datei einfach die gleichen Fragmente wiederverwendet, die durch die Löschung befreit wurden. Wenn das, was gelöscht wurde, eine Datei war, ist die neue Datei genauso fragmentiert wie diese alte Datei, aber auf jeden Fall gibt es keine Barriere für die Verwendung aller (hoch fragmentierten) freien Speicherplatz, um die neue Datei zu erstellen. Im RAM hingegen können die verwendeten Speichersysteme häufig keinen großen Block zusammenstellen, um eine Anfrage von kleinen, nicht zusammenhängenden freien Blöcken zu erfüllen, und so kann die Anfrage nicht erfüllt werden und das Programm kann nicht fortfahren, um das zu tun, wofür dieser Speicher benötigt wird (es sei denn Es kann die Anforderung als eine Anzahl kleinerer separater Anforderungen neu ausgeben).

Probleme

Speicherausfall

Das schwerwiegendste Problem, das durch Fragmentierung verursacht wird, ist, dass ein Prozess oder ein System aufgrund der vorzeitigen Erschöpfung der Ressourcen ausfällt: Wenn ein zusammenhängender Block gespeichert werden muss und nicht gespeichert werden kann, tritt ein Fehler auf. Fragmentierung führt dazu zusammenhängend Menge. Wenn beispielsweise ein Computer 4 Gib Speicher hat und 2 Gib frei sind, der Speicher in einer alternierenden Sequenz von 1 MIB, 1 MIB -frei, fragmentiert ist, kann eine Anforderung für 1 zusammenhängendes Speicher nicht erfüllt werden, obwohl 2 2 Gib insgesamt sind frei.

Um dies zu vermeiden, kann der Allocator, anstatt eine Defragmentierung (oder Speicherverfassungszyklus) oder eine andere Ressourcengewinnung, wie z. Dies ermöglicht den Prozess, sich weiterzuentwickeln, kann jedoch die Leistung stark beeinflussen.

Leistungsverschlechterung

Die Fragmentierung verursacht die Leistungsverschlechterung aus mehreren Gründen. Im Grunde genommen erhöht die Fragmentierung die Arbeit, die erforderlich ist, um eine Ressource zuzuweisen und zugänglich zu machen. Zum Beispiel sind auf einer Festplatte oder eines Bandlaufwerks die sequentiellen Datenlesungen sehr schnell, aber die Suche nach einer anderen Adresse ist langsam, so das Gerät. Wenn eine Ressource nicht fragmentiert ist, können Allokationsanforderungen einfach durch die Rückgabe eines einzelnen Blocks vom Beginn des freien Bereichs erfüllt werden. Es ist jedoch fragmentiert, die Anfrage erfordert, entweder nach einem ausreichend ausreichend freien Block zu suchen, was möglicherweise lange dauern kann, oder die Anforderung durch mehrere kleinere Blöcke (falls dies möglich ist), was dazu führt, dass diese Allokation fragmentiert wird und zusätzliche erfordert Overhead, um die verschiedenen Teile zu verwalten.

Ein subtileres Problem ist, dass die Fragmentierung einen Cache vorzeitig erschöpfen kann, der verursacht wird Prügel, aufgrund von Caches, die Blöcke halten, nicht individuelle Daten. Nehmen wir zum Beispiel an, ein Programm hat a Workingset von 256 kib und wird auf einem Computer mit einem 256 KIB -Cache (z. B. L2 -Befehl+Datencache) ausgeführt, sodass der gesamte Arbeitssatz in Cache passt und somit schnell in Bezug auf Cache -Treffer ausgeführt wird. Nehmen wir weiter an, dass es 64 hat Übersetzungs -Lookaside -Puffer (TLB) Einträge, jeweils für einen 4 kib Seite: Jeder Speicherzugriff erfordert eine virtuelle Übersetzung, die schnell ist, wenn sich die Seite im Cache befindet (hier TLB). Wenn das Arbeitssatz unfragmentiert ist, passt es auf genau 64 Seiten (die Seite Der Arbeitssatz beträgt 64 Seiten) und alle Speicher -Lookups können aus dem Cache bedient werden. Wenn der Arbeitssatz jedoch fragmentiert ist, passt er nicht in 64 Seiten und die Ausführung verlangsamt sich aufgrund von Verschlucken: Seiten werden während des Betriebs wiederholt hinzugefügt und aus dem TLB entfernt. Daher muss die Cache -Größen im Systemdesign die Marge enthalten, um die Fragmentierung zu berücksichtigen.

Gedächtnisfragmentierung ist eines der schwerwiegendsten Probleme für System Manager. Im Laufe der Zeit führt dies zu einer Verschlechterung der Systemleistung. Schließlich kann die Speicherfragmentierung zu einem vollständigen Verlust des (anwendungsnutzbaren) freien Speichers führen.

Gedächtnisfragmentierung ist a Kernel Programmierung Level Problem. Während Echtzeit-Computing Von Anwendungen können Fragmentierungsniveaus bis zu 99%erreichen und zu Systemabstürzen oder anderen Instabilitäten führen. Diese Art von Systemabsturz kann schwer zu vermeiden sein, da es unmöglich ist, den kritischen Anstieg der Speicherfragmentierung zu antizipieren. Obwohl es möglicherweise nicht möglich ist, dass ein System bei übermäßiger Speicherfragmentierung weiter ausführt Um die Konsolidierung des freien Speichers in weniger, größere Blöcke oder im schlimmsten Fall zu ermöglichen, indem einige Programme beendet werden, um ihren Speicher zu befreien und dann die resultierende Summe des freien Speichers zu defremant. Dies wird zumindest einen echten Absturz im Sinne des Systemausfalls vermeiden und es dem System ermöglichen, einige Programme weiter auszuführen, Programmdaten zu sparen usw. Es ist auch wichtig zu beachten, dass Fragmentierung ein Phänomen des Systemdesigns von Systemsoftware ist. Eine unterschiedliche Software ist anfällig für Fragmentierung in unterschiedlichem Maße, und es ist möglich, ein System zu entwerfen, das durch Speicherfragmentierung niemals gezwungen wird, Prozesse zu schließen oder abzutöten.

Analoge Phänomene

Während die Fragmentierung als Problem bei der Speicherzuweisung bekannt ist, treten analoge Phänomene für andere auf Ressourcen, insbesondere Prozessoren.[5] Zum Beispiel in einem System, das verwendet Zeitteilung zum Präventiver Multitasking, aber das prüft nicht, ob ein Prozess blockiert ist, ein Prozess, der für einen Teil seiner ausgeführt wird Zeitscheibe aber dann blockiert und kann für den Rest seiner Zeitscheibe keine Zeit wegen der daraus resultierenden Zeitverschwendung intern Fragmentierung von Zeitscheiben. Grundsätzlich verursacht die Zeit zum Teilen selbst extern Fragmentierung von Prozessen aufgrund des Ausführens in fragmentierten Zeitscheiben und nicht in einem einzigen ungebrochenen Lauf. Die daraus resultierenden Kosten von Prozessumschaltung und erhöhter Cache -Druck aus mehreren Prozessen unter Verwendung derselben Caches kann zu einer abgebauten Leistung führen.

Im Gleichzeitige Systeme, im Speziellen verteilte SystemeWenn eine Gruppe von Prozessen interagieren muss, um Fortschritte zu erzielen, wenn die Prozesse zu separaten Zeiten oder auf separaten Maschinen (über die Zeit oder Maschinen fragmentiert) geplant sind, kann die Zeit, die aufeinander wartet oder miteinander kommuniziert, die Leistung stark abbauen . Stattdessen erfordern Performantensysteme Coseduling aus der Gruppe.[5]

Etwas Flash -Dateisysteme haben verschiedene Arten von innerer Fragmentierung, die "toten Raum" und "dunkler Raum" beinhalten.[6]

Siehe auch

Verweise

  1. ^ Null, Linda; Lobur, Julia (2006). Das Wesentliche der Computerorganisation und Architektur. Jones und Bartlett Publishers. p. 315. ISBN 9780763737696. Abgerufen 15. Juli, 2021.
  2. ^ "Partitionierung, Partitionsgrößen und Antriebsschreiben". Die PC -Handbuch. 17. April 2001. Abgerufen 2012-01-20.
  3. ^ "Switches: Sektorkopie".Symantec.2001-01-14. Abgerufen 2012-01-20.
  4. ^ D. Samanta."Klassische Datenstrukturen" 2004. p. 76
  5. ^ a b OUSTERHOUT, J. K. (1982). "Planungstechniken für gleichzeitige Systeme" (PDF). Verfahren der dritten internationalen Konferenz über verteilte Computersysteme. S. 22–30.
  6. ^ .Adrian Hunter."Eine kurze Einführung in das Design von Ubifs".2008.etc p.8.

Quellen