Fragmentare (calcul) - Fragmentation (computing)

Pentru fragmentarea sistemului de fișiere, consultați Fragmentarea sistemului de fișiere .

În stocarea pe computer , fragmentarea este un fenomen în care spațiul de stocare, stocarea principală sau stocarea secundară , este utilizat ineficient, reducând capacitatea sau performanța și adesea ambele. Consecințele exacte ale fragmentării depind de sistemul specific de alocare a stocării în uz și de forma particulară de fragmentare. În multe cazuri, fragmentarea duce la „risipirea” spațiului de stocare și, în acest caz, termenul se referă și la spațiul irosit în sine.

Tipuri de fragmentare

Există trei forme de fragmentare diferite, dar conexe: fragmentarea externă, fragmentarea internă și fragmentarea datelor, care pot fi prezente izolat sau conjuncțional. Fragmentarea este adesea acceptată în schimbul îmbunătățirii vitezei sau simplității. Fenomene analoge apar pentru alte resurse, cum ar fi procesoarele; Vezi mai jos.

Principiu de bază

Atunci când un program de computer solicită blocuri de memorie de la sistemul de computer, blocurile sunt alocate în bucăți. Când programul de computer este terminat cu o bucată, îl poate elibera înapoi în sistem, făcându-l disponibil pentru a fi alocat ulterior din nou altui sau aceluiași program. Mărimea și cantitatea de timp în care o bucată este ținută de un program variază. În timpul duratei sale de viață, un program de computer poate solicita și elibera multe bucăți de memorie.

Când este pornit un program, zonele libere de memorie sunt lungi și contigue. De-a lungul timpului și cu utilizarea, regiunile adiacente lungi devin fragmentate în zone adiacente din ce în ce mai mici. În cele din urmă, poate deveni imposibil ca programul să obțină bucăți mari de memorie adiacente.

Tipuri

Fragmentarea internă

Paginarea în memorie creează fragmentarea internă, deoarece va fi alocat un întreg cadru de pagină, indiferent dacă este sau nu atât de mult spațiu de stocare. Datorită regulilor care guvernează alocarea memoriei , uneori este alocată mai multă memorie de calculator decât este necesară. De exemplu, memoria poate fi furnizată doar programelor în bucăți (de obicei un multiplu de 4 octeți) și, ca rezultat, dacă un program solicită poate 29 de octeți, de fapt va obține o bucată de 32 de octeți. Când se întâmplă acest lucru, excesul de memorie se pierde. În acest scenariu, memoria inutilizabilă este conținută într-o regiune alocată. Acest aranjament, denumit partiții fixe, suferă de o utilizare ineficientă a memoriei - orice proces, oricât de mic ar fi, ocupă o întreagă partiție. Aceste deșeuri se numesc fragmentare internă .

Spre deosebire de alte tipuri de fragmentare, fragmentarea internă este dificil de recuperat; de obicei, cel mai bun mod de a-l elimina este cu o schimbare de design. De exemplu, în alocarea dinamică a memoriei , grupurile de memorie reduc drastic fragmentarea internă prin răspândirea spațiului peste un număr mai mare de obiecte.

Fragmentarea externă

Fragmentarea externă apare atunci când memoria liberă este separată în blocuri mici și este intercalată de memoria alocată. Este o slăbiciune a anumitor algoritmi de alocare a stocării, atunci când aceștia nu reușesc să comande eficient memoria utilizată de programe. Rezultatul este că, deși stocarea gratuită este disponibilă, este efectiv inutilizabilă, deoarece este împărțită în bucăți care sunt prea mici individual pentru a satisface cerințele aplicației. Termenul „extern” se referă la faptul că stocarea inutilizabilă se află în afara regiunilor alocate.

De exemplu, luați în considerare o situație în care un program alocă trei blocuri continue de memorie și apoi eliberează blocul din mijloc. Alocatorul de memorie poate utiliza acest bloc gratuit de memorie pentru alocări viitoare. Cu toate acestea, nu poate utiliza acest bloc dacă memoria de alocat are o dimensiune mai mare decât acest bloc liber.

Fragmentarea externă are loc, de asemenea, în sistemele de fișiere, deoarece multe fișiere de dimensiuni diferite sunt create, modifică dimensiunea și sunt șterse. Efectul este chiar mai rău dacă un fișier care este împărțit în multe bucăți mici este șters, deoarece acesta lasă regiuni similare de spații libere.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 Comentarii
Începeți cu toată memoria disponibilă pentru stocare.
A B C Alocate trei blocuri A, B și C, de dimensiunea 0x1000.
A C Blocul eliberat B. Observați că memoria utilizată de B nu poate fi inclusă pentru un bloc mai mare decât dimensiunea lui B.
A C Blocul C s-a mutat în slotul gol al blocului B, permițând spațiului rămas să fie utilizat pentru un bloc mai mare de dimensiunea 0x4000.

Fragmentarea datelor

Fragmentarea datelor are loc atunci când o colecție de date din memorie este împărțită în multe bucăți care nu sunt apropiate. Este de obicei rezultatul încercării de a introduce un obiect mare în stocare care a suferit deja o fragmentare externă. De exemplu, fișierele dintr-un sistem de fișiere sunt de obicei gestionate în unități numite blocuri sau clustere . Atunci când se creează un sistem de fișiere, există spațiu liber pentru a stoca blocuri de fișiere împreună contigue . Acest lucru permite citirea și scrierea secvențială rapidă a fișierelor. Cu toate acestea, pe măsură ce fișierele sunt adăugate, eliminate și modificate în dimensiune, spațiul liber devine fragmentat extern, lăsând doar mici găuri în care să plasați date noi. Când este scris un fișier nou sau când un fișier existent este extins, sistemul de operare pune noile date în blocuri de date necontigue pentru a se încadra în găurile disponibile. Noile blocuri de date sunt neapărat împrăștiate, încetinind accesul datorită timpului de căutare și a latenței de rotație a capului de citire / scriere și implicând cheltuieli suplimentare pentru a gestiona locații suplimentare. Aceasta se numește fragmentarea sistemului de fișiere .

Când scrieți un fișier nou de o dimensiune cunoscută, dacă există găuri goale care sunt mai mari decât acel fișier, sistemul de operare poate evita fragmentarea datelor punând fișierul în oricare dintre aceste găuri. Există o varietate de algoritmi pentru a selecta care dintre acele găuri potențiale să pună fișierul; fiecare dintre ele este o soluție euristică aproximativă la problema ambalării coșului . Algoritmul „cea mai potrivită” alege cea mai mică gaură suficient de mare. Algoritmul de „cea mai rea potrivire” alege cea mai mare gaură. „ Primul algoritm de potrivire ” alege prima gaură suficient de mare. Algoritmul „următoare potrivire” ține evidența locului în care a fost scris fiecare fișier. Algoritmul „următoare potrivire” este mai rapid decât „prima potrivire”, care este la rândul său mai rapid decât „cea mai bună potrivire”, care este aceeași viteză ca „cea mai proastă potrivire”.

Așa cum compactarea poate elimina fragmentarea externă, fragmentarea datelor poate fi eliminată prin rearanjarea stocării datelor, astfel încât piesele conexe să fie apropiate. De exemplu, sarcina principală a unui instrument de defragmentare este de a rearanja blocurile de pe disc astfel încât blocurile fiecărui fișier să fie contigue. Majoritatea utilităților de defragmentare încearcă, de asemenea, să reducă sau să elimine fragmentarea spațiului liber. Unele colectoare de gunoi în mișcare , utilitare care efectuează gestionarea automată a memoriei, vor muta, de asemenea, obiectele conexe aproape împreună (aceasta se numește compactare ) pentru a îmbunătăți performanța cache-ului.

Există patru tipuri de sisteme care nu experimentează niciodată fragmentarea datelor - ele stochează întotdeauna fiecare fișier în mod contigu. Toate cele patru tipuri au dezavantaje semnificative în comparație cu sistemele care permit cel puțin o fragmentare temporară a datelor:

  1. Pur și simplu scrieți fiecare fișier în mod contigu . Dacă nu există deja suficient spațiu contiguu liber pentru a păstra fișierul, sistemul nu reușește imediat să stocheze fișierul - chiar și atunci când există multe bucăți mici de spațiu liber din fișierele șterse care se adună la mai mult decât suficient pentru a stoca fișierul.
  2. Dacă nu există deja suficient spațiu contiguu liber pentru a păstra fișierul, utilizați un colector de copiere pentru a converti mai mulți bucăți de spațiu liber într-o regiune liberă contiguă suficient de mare pentru a păstra fișierul. Acest lucru necesită mult mai mult timp decât divizarea fișierului în fragmente și plasarea fragmentelor respective în spațiul liber disponibil.
  3. Scrieți fișierul în orice bloc gratuit, prin stocarea blocurilor de dimensiuni fixe . Dacă un programator alege o dimensiune fixă ​​a blocului prea mică, sistemul nu reușește imediat să stocheze unele fișiere - fișiere mai mari decât dimensiunea blocului - chiar și atunci când există multe blocuri gratuite care adună mai mult decât suficient pentru a stoca fișierul. Dacă un programator alege o dimensiune de bloc prea mare, se pierde mult spațiu pe fragmentarea internă.
  4. Unele sisteme evită în întregime alocarea dinamică, pre-stocând spațiul (contigu) pentru toate fișierele posibile de care vor avea nevoie - de exemplu, MultiFinder pre-alocă o bucată de RAM fiecărei aplicații, deoarece a fost pornită în funcție de cât de mult RAM a solicitat programatorul acelei aplicații o sa ai nevoie.

Prezentare generală

În comparație cu fragmentarea externă, costurile generale și fragmentarea internă reprezintă o pierdere mică în ceea ce privește memoria irosită și performanța redusă. Este definit ca:

Fragmentarea de 0% înseamnă că toată memoria liberă se află într-un singur bloc mare; fragmentarea este de 90% (de exemplu) atunci când există 100 MB memorie liberă, dar cel mai mare bloc liber de memorie pentru stocare este de doar 10 MB.

Fragmentarea externă tinde să fie mai puțin o problemă în sistemele de fișiere decât în ​​sistemele de stocare cu memorie primară (RAM), deoarece programele necesită, de obicei, ca cererile lor de stocare RAM să fie îndeplinite cu blocuri adiacente, dar sistemele de fișiere sunt de obicei concepute pentru a putea utiliza orice colecție de blocuri disponibile (fragmente) pentru a asambla un fișier care pare logic contigu. Prin urmare, dacă un fișier foarte fragmentat sau multe fișiere mici sunt șterse dintr-un volum complet și apoi se creează un fișier nou cu dimensiunea egală cu spațiul nou eliberat, noul fișier va reutiliza pur și simplu aceleași fragmente care au fost eliberate prin ștergere. Dacă ceea ce a fost șters a fost un fișier, noul fișier va fi la fel de fragmentat ca acel fișier vechi, dar în orice caz nu va exista nicio barieră în utilizarea întregului spațiu liber (foarte fragmentat) pentru a crea noul fișier. Pe de altă parte, în memoria RAM, sistemele de stocare utilizate nu pot asambla adesea un bloc mare pentru a satisface o cerere de la blocuri libere necontigue mici, astfel încât cererea nu poate fi îndeplinită și programul nu poate continua să facă orice ar fi avut nevoie de memoria respectivă (cu excepția cazului în care poate retransmite cererea ca un număr de cereri separate mai mici).

Probleme

Eșec de stocare

Cea mai gravă problemă cauzată de fragmentare este cauzarea eșecului unui proces sau sistem, din cauza epuizării premature a resurselor: dacă un bloc adiacent trebuie stocat și nu poate fi stocat, apare eșecul. Fragmentarea face ca acest lucru să apară chiar dacă resursa este suficientă, dar nu o cantitate contiguă . De exemplu, dacă un computer are 4 GiB de memorie și 2 GiB sunt libere, dar memoria este fragmentată într-o secvență alternativă de 1 MiB utilizat, 1 MiB liber, atunci o cerere pentru 1 GiB contiguu de memorie nu poate fi satisfăcută, chiar dacă 2 Totalul GiB este gratuit.

Pentru a evita acest lucru, distribuitorul poate, în loc să eșueze, să declanșeze o defragmentare (sau un ciclu de compactare a memoriei) sau alte recuperări de resurse, cum ar fi un ciclu major de colectare a gunoiului, în speranța că va putea apoi să satisfacă cererea. Acest lucru permite procesului să continue, dar poate afecta grav performanța.

Degradarea performanței

Fragmentarea cauzează degradarea performanței din mai multe motive. Cel mai practic, fragmentarea crește munca necesară pentru alocarea și accesarea unei resurse. De exemplu, pe un hard disk sau pe o unitate de bandă, citirile secvențiale de date sunt foarte rapide, dar căutarea către o adresă diferită este lentă, astfel încât citirea sau scrierea unui fișier fragmentat necesită numeroase căutări și este astfel mult mai lentă, pe lângă faptul că provoacă o uzură mai mare a dispozitivul. Mai mult, dacă o resursă nu este fragmentată, cererile de alocare pot fi satisfăcute prin returnarea unui singur bloc de la începutul zonei libere. Cu toate acestea este fragmentată, solicitarea necesită fie căutarea unui bloc gratuit suficient de mare, care poate dura mult timp, fie îndeplinirea cererii de către mai multe blocuri mai mici (dacă acest lucru este posibil), ceea ce are ca rezultat fragmentarea acestei alocări și care necesită un supliment deasupra capului pentru a gestiona mai multe piese.

O problemă mai subtilă este că fragmentarea poate epuiza prematur o memorie cache, provocând zdrobire , din cauza blocurilor care dețin blocuri, nu a datelor individuale. De exemplu, să presupunem că un program are un set de lucru de 256 KiB și rulează pe un computer cu o memorie cache de 256 KiB (să spunem instrucțiuni L2 + cache de date), astfel încât întregul set de lucru se potrivește în cache și astfel se execută rapid, cel puțin în termenii accesărilor în cache. Să presupunem în plus că are 64 de intrări de tampon de traducere (TLB), fiecare pentru o pagină de 4 KiB : fiecare acces la memorie necesită o traducere virtual-fizică, care este rapidă dacă pagina este în cache (aici TLB). Dacă setul de lucru nu este fragmentat, acesta se va potrivi exact pe 64 de pagini ( setul de lucru pentru pagini va fi de 64 de pagini) și toate căutările de memorie pot fi servite din cache. Cu toate acestea, dacă setul de lucru este fragmentat, atunci acesta nu se va încadra în 64 de pagini, iar execuția va încetini din cauza thrashing: paginile vor fi adăugate și eliminate în mod repetat din TLB în timpul funcționării. Astfel, dimensionarea cache-ului în proiectarea sistemului trebuie să includă marjă pentru a explica fragmentarea.

Fragmentarea memoriei este una dintre cele mai grave probleme cu care se confruntă managerii de sistem . În timp, aceasta duce la degradarea performanței sistemului. În cele din urmă, fragmentarea memoriei poate duce la pierderea completă a memoriei libere (utilizabile de aplicație).

Fragmentarea memoriei este o problemă la nivel de programare a nucleului . În timpul calculării în timp real a aplicațiilor, nivelurile de fragmentare pot ajunge până la 99% și pot duce la blocări ale sistemului sau la alte instabilități. Acest tip de blocare a sistemului poate fi dificil de evitat, deoarece este imposibil să anticipăm creșterea critică a nivelurilor de fragmentare a memoriei. Cu toate acestea, deși este posibil să nu fie posibil ca un sistem să ruleze în continuare toate programele în cazul fragmentării excesive a memoriei, un sistem bine conceput ar trebui să fie capabil să se recupereze din condiția critică de fragmentare prin deplasarea în unele blocuri de memorie utilizate de sistemul însuși pentru a permite consolidarea memoriei libere în mai puține blocuri mai mari sau, în cel mai rău caz, prin terminarea unor programe pentru a-și elibera memoria și apoi pentru a defragmenta suma totală rezultată a memoriei libere. Acest lucru va evita cel puțin un adevărat blocaj în sensul eșecului sistemului și va permite sistemului să ruleze în continuare unele programe, să salveze datele programului etc. Este, de asemenea, important să rețineți că fragmentarea este un fenomen al proiectării software-ului sistemului; diferite programe vor fi susceptibile de fragmentare la diferite grade și este posibil să se proiecteze un sistem care nu va fi niciodată forțat să închidă sau să omoare procesele ca urmare a fragmentării memoriei.

Fenomene analoge

În timp ce fragmentarea este cel mai bine cunoscută ca o problemă în alocarea memoriei, apar fenomene similare pentru alte resurse , în special pentru procesoare. De exemplu, într-un sistem care folosește partajarea timpului pentru multitasking preventiv , dar care nu verifică dacă un proces este blocat, un proces care se execută pentru o parte din segmentul său de timp, dar apoi îl blochează și nu poate continua pentru restul deșeurilor de felie de timp. timp din cauza fragmentării interne rezultate a feliilor de timp. Mai fundamental, schimbul de timp în sine provoacă fragmentarea externă a proceselor datorită rulării lor în felii de timp fragmentate, mai degrabă decât într-o singură rundă neîntreruptă. Costul rezultat al comutării procesului și presiunea crescută a memoriei cache de la mai multe procese care utilizează aceleași cache pot duce la performanțe degradate.

În sistemele concurente , în special sistemele distribuite , când un grup de procese trebuie să interacționeze pentru a progresa, dacă procesele sunt programate la momente separate sau pe mașini separate (fragmentate în timp sau mașini), timpul petrecut așteptându-se unul pe celălalt sau comunicând între ele pot degrada sever performanța. În schimb, sistemele performante necesită co-programarea grupului.

Unele sisteme de fișiere flash au mai multe tipuri diferite de fragmentare internă care implică „spațiu mort” și „spațiu întunecat”.

Vezi si

Referințe

Surse