Fragmentace (výpočetní) - Fragmentation (computing)

Fragmentace systému souborů viz Fragmentace systému souborů .

V počítačovém úložišti je fragmentace jevem, kdy je úložný prostor, hlavní úložiště nebo sekundární úložiště využíván neefektivně, což snižuje kapacitu nebo výkon a často obojí. Přesné důsledky fragmentace závisí na konkrétním používaném systému přidělování úložiště a konkrétní formě fragmentace. V mnoha případech fragmentace vede k „plýtvání“ úložným prostorem a v takovém případě se termín týká také samotného zbytečného prostoru.

Typy fragmentace

Existují tři různé, ale související formy fragmentace: vnější fragmentace, vnitřní fragmentace a fragmentace dat, které mohou být přítomny izolovaně nebo ve spojení. Fragmentace je často přijímána výměnou za zlepšení rychlosti nebo jednoduchosti. Analogické jevy se vyskytují u jiných zdrojů, jako jsou procesory; viz. níže.

Základní princip

Když počítačový program požaduje bloky paměti z počítačového systému, bloky jsou přiděleny po částech. Když je počítačový program dokončen s kusem, může jej uvolnit zpět do systému a zpřístupnit jej tak, aby byl později znovu přidělen jinému nebo stejnému programu. Velikost a doba, po kterou kus drží program, se liší. Během své životnosti může počítačový program požadovat a uvolnit mnoho kusů paměti.

Po spuštění programu jsou oblasti volné paměti dlouhé a souvislé. Časem a používáním se dlouhé souvislé oblasti fragmentují na menší a menší souvislé oblasti. Nakonec může být pro program nemožné získat velké souvislé bloky paměti.

Typy

Vnitřní fragmentace

Stránkování paměti vytváří vnitřní fragmentaci, protože bude přidělen celý rámeček stránky bez ohledu na to, zda je potřeba tolik úložiště. Kvůli pravidlům upravujícím alokaci paměti je někdy přiděleno více paměti počítače, než je potřeba. Například paměť může být poskytována pouze programům v blocích (obvykle násobek 4 bajtů) a v důsledku toho, pokud program požaduje asi 29 bajtů, ve skutečnosti získá kus 32 bajtů. Když k tomu dojde, přebytečná paměť se promrhá. V tomto scénáři je nepoužitelná paměť obsažena v přidělené oblasti. Toto uspořádání, nazývané pevné oddíly, trpí neefektivním využitím paměti - jakýkoli proces, bez ohledu na to, jak malý, zabírá celý oddíl. Tento odpad se nazývá vnitřní fragmentace .

Na rozdíl od jiných typů fragmentace je vnitřní fragmentaci obtížné získat zpět; obvykle nejlepší způsob, jak jej odstranit, je změna designu. Například v dynamické přidělování paměti , paměťové bazény drasticky snížit vnitřní roztříštěnost šířením prostor nad hlavou přes větší počet objektů.

Externí fragmentace

Externí fragmentace vzniká, když je volná paměť rozdělena na malé bloky a je proložena přidělenou pamětí. Je slabinou určitých algoritmů přidělování úložiště, když nedokáží efektivně objednat paměť používanou programy. Výsledkem je, že ačkoli je k dispozici bezplatné úložiště, je prakticky nepoužitelné, protože je rozděleno na kusy, které jsou jednotlivě příliš malé na to, aby uspokojily požadavky aplikace. Termín „externí“ označuje skutečnost, že nepoužitelné úložiště je mimo přidělené oblasti.

Zvažte například situaci, kdy program alokuje tři souvislé bloky paměti a poté uvolní střední blok. Alokátor paměti může použít tento volný blok paměti pro budoucí přidělení. Tento blok však nelze použít, pokud má přidělená paměť větší velikost než tento volný blok.

K externí fragmentaci dochází také v souborových systémech, protože se vytváří mnoho souborů různých velikostí, mění se velikost a jsou odstraněny. Efekt je ještě horší, pokud je soubor, který je rozdělen na mnoho malých částí, odstraněn, protože to ponechává podobně malé oblasti volného místa.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 Komentáře
Začněte s veškerou pamětí dostupnou pro úložiště.
A B C Přidělené tři bloky A, B a C o velikosti 0x1000.
A C Uvolněný blok B. Všimněte si, že paměť, kterou použil B, nemůže být zahrnuta pro blok větší než velikost B.
A C Blok C se přesunul do prázdného slotu bloku B, což umožnilo využití zbývajícího prostoru pro větší blok o velikosti 0x4000.

Fragmentace dat

K fragmentaci dat dochází, když je kolekce dat v paměti rozdělena na mnoho částí, které nejsou blízko sebe. Obvykle je to výsledek pokusu o vložení velkého objektu do úložiště, které již utrpělo externí fragmentaci. Například soubory v systému souborů jsou obvykle spravovány v jednotkách nazývaných bloky nebo klastry . Když je vytvořen souborový systém, je zde volné místo pro souvislé ukládání bloků souborů dohromady . To umožňuje rychlé sekvenční čtení a zápis souborů. Jak se však soubory přidávají, odebírají a mění velikost, volné místo se externě fragmentuje a zůstávají jen malé otvory, do kterých lze umístit nová data. Při zápisu nového souboru nebo při rozšíření existujícího souboru vloží operační systém nová data do nových nesousedících datových bloků, aby se vešly do dostupných děr. Nové datové bloky jsou nutně roztroušeny, zpomalují přístup kvůli době hledání a latenci otáčení čtecí/zapisovací hlavy a vznikají další režijní náklady na správu dalších umístění. Toto se nazývá fragmentace systému souborů .

Pokud při psaní nového souboru známé velikosti existují prázdné otvory, které jsou větší než tento soubor, může se operační systém vyhnout fragmentaci dat vložením souboru do kterékoli z těchto děr. Existuje celá řada algoritmů pro výběr, které z těchto potenciálních děr soubor umístit; každý z nich je heuristickým přibližným řešením problému s balením . Algoritmus „nejvhodnější“ vybere nejmenší díru, která je dostatečně velká. Algoritmus „nejhoršího uložení“ vybere největší díru. „ Algoritmus prvního přizpůsobení “ vybere první díru, která je dostatečně velká. Algoritmus „next fit“ sleduje, kde byl každý soubor zapsán. Algoritmus „dalšího přizpůsobení“ je rychlejší než „první přizpůsobení“, což je zase rychlejší než „nejlepší přizpůsobení“, což je stejná rychlost jako „nejhorší přizpůsobení“.

Stejně jako zhutňování může eliminovat externí fragmentaci, fragmentaci dat lze eliminovat přeskupením úložiště dat tak, aby související kusy byly blízko sebe. Například primární úlohou nástroje pro defragmentaci je přeskupit bloky na disku tak, aby bloky každého souboru byly souvislé. Většina nástrojů pro defragmentaci se také pokouší snížit nebo odstranit fragmentaci volného místa. Některé pohyblivé garbage collectory , nástroje, které provádějí automatickou správu paměti, budou také přesouvat související objekty blízko sebe (tomu se říká zhutňování ), aby se zlepšil výkon mezipaměti.

Existují čtyři druhy systémů, u nichž nikdy nedochází k fragmentaci dat - vždy ukládají každý soubor souvisle. Všechny čtyři druhy mají značné nevýhody ve srovnání se systémy, které umožňují alespoň dočasnou fragmentaci dat:

  1. Jednoduše napište každý soubor souvisle . Pokud již není dostatek souvislého volného místa pro uložení souboru, systém okamžitě soubor neuloží - i když je mnoho malých bitů volného místa z odstraněných souborů, které se k uložení souboru přidávají více než dost.
  2. Pokud již není dostatek souvislého volného místa pro uložení souboru, použijte kopírovací kolektor k převodu mnoha malých bitů volného místa do jedné souvislé volné oblasti dostatečně velké na uložení souboru. Trvá to mnohem více času, než rozdělit soubor na fragmenty a umístit je do dostupného volného místa.
  3. Zapište soubor do libovolného volného bloku prostřednictvím úložiště bloků pevné velikosti . Pokud programátor vybere příliš malou velikost pevného bloku, systém okamžitě neukládá některé soubory - soubory větší než velikost bloku - i když je k dispozici mnoho volných bloků, kterých je k uložení souboru více než dost. Pokud programátor vybere příliš velkou velikost bloku, mnoho místa se promrhá vnitřní fragmentací.
  4. Některé systémy se zcela vyhýbají dynamické alokaci, před ukládáním (souvislého) prostoru pro všechny možné soubory, které budou potřebovat-například MultiFinder předem alokuje část paměti RAM každé aplikaci, jak byla spuštěna, podle toho, kolik RAM si programátor dané aplikace nárokoval by potřeboval.

Přehled

Ve srovnání s externí fragmentací představují režijní a interní fragmentace malou ztrátu, pokud jde o plýtvání pamětí a snížení výkonu. Je definován jako:

Fragmentace 0% znamená, že veškerá volná paměť je v jednom velkém bloku; fragmentace je 90% (například), když je k dispozici 100 MB volné paměti, ale největší volný blok paměti pro ukládání je pouhých 10 MB.

Externí fragmentace bývá v souborových systémech menším problémem než v úložných systémech s primární pamětí (RAM), protože programy obvykle vyžadují, aby jejich požadavky na paměť RAM byly splněny souvislými bloky, ale souborové systémy jsou obvykle navrženy tak, aby mohly používat jakoukoli kolekci dostupných bloků (fragmentů) k sestavení souboru, který logicky vypadá souvisle. Pokud je tedy z celého svazku odstraněn vysoce fragmentovaný soubor nebo mnoho malých souborů a poté je vytvořen nový soubor s velikostí rovnou nově uvolněnému prostoru, nový soubor jednoduše znovu použije stejné fragmenty, které byly uvolněny odstraněním. Pokud byl odstraněn jeden soubor, nový soubor bude stejně fragmentovaný jako starý soubor, ale v každém případě nebude existovat žádná překážka pro využití veškerého (vysoce fragmentovaného) volného místa k vytvoření nového souboru. V RAM naopak používané úložné systémy často nedokážou sestavit velký blok tak, aby splňoval požadavek z malých nesousedících volných bloků, a tak požadavek nelze splnit a program nemůže pokračovat v tom, co pro danou paměť potřebuje (pokud může požadavek znovu vystavit jako několik menších samostatných požadavků).

Problémy

Selhání úložiště

Nejzávažnější problém způsobený fragmentací způsobuje selhání procesu nebo systému v důsledku předčasného vyčerpání zdrojů: pokud musí být souvislý blok uložen a nelze jej uložit, dojde k selhání. Fragmentace způsobí, že k tomu dojde, i když je zdroje dostatek, ale ne souvislé množství. Pokud má počítač například 4 GiB paměti a 2 GiB jsou volné, ale paměť je fragmentována ve střídavé sekvenci 1 použitá MiB, 1 MiB volná, pak požadavek na 1 souvislou GiB paměti nelze splnit, přestože 2 Součet GiB je zdarma.

Aby se tomu zabránilo, může alokátor namísto selhání spustit defragmentaci (nebo cyklus zhutňování paměti) nebo jiné rekultivace prostředků, jako je hlavní cyklus shromažďování odpadků, v naději, že bude poté schopen požadavek uspokojit. To umožňuje, aby proces pokračoval, ale může mít vážný dopad na výkon.

Snížení výkonu

Fragmentace způsobuje snížení výkonu z několika důvodů. V zásadě fragmentace zvyšuje práci potřebnou k přidělení a přístupu ke zdroji. Například na pevném disku nebo páskové jednotce jsou sekvenční čtení dat velmi rychlá, ale hledání na jinou adresu je pomalé, takže čtení nebo zápis fragmentovaného souboru vyžaduje četné hledání a je tedy mnohem pomalejší, navíc způsobuje větší opotřebení zařízení. Dále, pokud není zdroj fragmentován, mohou být žádosti o přidělení jednoduše uspokojeny vrácením jednoho bloku od začátku volné oblasti. Je však fragmentovaný, požadavek vyžaduje buď hledání dostatečně velkého volného bloku, což může trvat dlouho, nebo splnění požadavku několika menšími bloky (je -li to možné), což má za následek fragmentaci této alokace, která vyžaduje další nad hlavou zvládnout několik kusů.

Jemnější problém spočívá v tom, že fragmentace může předčasně vyčerpat mezipaměť, což způsobí vyřazení kvůli mezipaměti, která obsahuje bloky, nikoli jednotlivá data. Předpokládejme například, že program má pracovní sadu 256 KiB a běží na počítači s 256 kB mezipaměti (řekněme instrukce L2+mezipaměť dat), takže celá pracovní sada se vejde do mezipaměti, a proto se rychle spustí, alespoň v podmínky přístupů do mezipaměti. Předpokládejme dále, že má 64 translation lookaside buffer (TLB) záznamů, každý po KiB 4 stránky : každý přístup do paměti vyžaduje virtuální na fyzický překlad, která je rychlá, pokud je stránka v mezipaměti (zde TLB). V případě, že pracovní sada je unfragmented, pak se vejde na přesně 64 stránky ( strana pracovní sada bude 64 stran), a všechny paměti je vyhledávání mohou být podávány z mezipaměti. Pokud je však pracovní sada roztříštěná, pak se nevejde na 64 stránek a provádění se zpomalí kvůli mlácení: stránky budou během provozu opakovaně přidávány a odebírány z TLB. Velikost mezipaměti v návrhu systému tedy musí zahrnovat rezervu, která zohlední fragmentaci.

Fragmentace paměti je jedním z nejzávažnějších problémů, se kterými se potýkají správci systému . Časem to vede ke snížení výkonu systému. Fragmentace paměti může nakonec vést k úplné ztrátě (použitelné) volné paměti.

Fragmentace paměti je problém na úrovni programování jádra . Během výpočtu aplikací v reálném čase mohou úrovně fragmentace dosáhnout až 99%a mohou vést k selhání systému nebo jiným nestabilitám. Tomuto typu selhání systému je obtížné se vyhnout, protože nelze předvídat kritický nárůst úrovní fragmentace paměti. Přestože v případě nadměrné fragmentace paměti nemusí být možné, aby systém pokračoval ve spouštění všech programů, dobře navržený systém by měl být schopen zotavit se z kritického stavu fragmentace přesunutím v některých blocích paměti používaných samotným systémem za účelem umožnění konsolidace volné paměti do menšího počtu větších bloků nebo v nejhorším případě ukončením některých programů k uvolnění paměti a následným defragmentací výsledného součtu volné paměti. Tím se alespoň vyhnete skutečnému selhání ve smyslu selhání systému a umožníte systému pokračovat v spouštění některých programů, ukládání programových dat atd. Je také důležité si uvědomit, že fragmentace je fenomén návrhu systémového softwaru; různý software bude náchylný k fragmentaci v různé míře a je možné navrhnout systém, který nebude nikdy nucen vypínat nebo zabíjet procesy v důsledku fragmentace paměti.

Analogické jevy

Zatímco fragmentace je nejlépe známá jako problém při přidělování paměti, u jiných zdrojů , zejména procesorů, dochází k analogickým jevům . Například v systému, který používá sdílení času pro preemptivní multitasking , ale který nekontroluje, zda je proces blokován, proces, který se spustí pro část svého časového úseku, ale pak zablokuje a nemůže pokračovat po zbytek svého časového úseku, ztrácí čas kvůli výsledné vnitřní fragmentaci časových řezů. Podstatnější je, že samotné sdílení času způsobuje vnější fragmentaci procesů v důsledku jejich spouštění ve fragmentovaných časových úsecích, nikoli v jediném nepřerušeném běhu. Výsledné náklady na přepínání procesů a zvýšený tlak v mezipaměti z více procesů využívajících stejné mezipaměti mohou mít za následek snížení výkonu.

V souběžných systémech , zejména v distribuovaných systémech , kdy skupina procesů musí interagovat, aby mohly pokročit, pokud jsou procesy naplánovány v různých časech nebo na různých počítačích (rozdělené na čas nebo stroje), doba strávená na sebe navzájem nebo při komunikaci navzájem mohou vážně snížit výkon. Výkonné systémy místo toho vyžadují střídání skupiny.

Některé systémy souborů Flash mají několik různých druhů vnitřní fragmentace zahrnující „mrtvý prostor“ a „temný prostor“.

Viz také

Reference

Prameny