Fragmentering (databehandling) - Fragmentation (computing)

For fragmentering av filsystem, se Filsystemfragmentering .

I datalagring er fragmentering et fenomen der lagringsplass, hovedlagring eller sekundær lagring , brukes ineffektivt, reduserer kapasitet eller ytelse og ofte begge deler. De eksakte konsekvensene av fragmentering avhenger av det spesifikke systemet for lagertildeling i bruk og den spesielle fragmenteringsformen. I mange tilfeller fører fragmentering til at lagringsplass blir "bortkastet", og i så fall refererer begrepet også til selve bortkastet plass.

Typer fragmentering

Det er tre forskjellige, men beslektede former for fragmentering: ekstern fragmentering, intern fragmentering og datafragmentering, som kan være tilstede isolert eller sammen. Fragmentering blir ofte akseptert i bytte mot forbedringer i hastighet eller enkelhet. Analoge fenomener forekommer for andre ressurser som prosessorer; se nedenfor.

Grunnleggende prinsipp

Når et dataprogram ber om blokker med minne fra datasystemet, tildeles blokkene i biter. Når dataprogrammet er ferdig med en del, kan det frigjøre det tilbake til systemet, noe som gjør det tilgjengelig for senere å bli tildelt igjen til et annet eller samme program. Størrelsen og hvor lang tid en del blir holdt av et program varierer. I løpet av levetiden kan et dataprogram be om og frigjøre mange biter av minne.

Når et program startes, er ledige minneområder lange og sammenhengende. Over tid og med bruk blir de lange sammenhengende områdene fragmentert i mindre og mindre sammenhengende områder. Etter hvert kan det bli umulig for programmet å skaffe store sammenhengende biter av minne.

Typer

Intern fragmentering

Minnesøk skaper intern fragmentering fordi en hel sideramme vil bli tildelt uansett om det er nødvendig med så mye lagringsplass. På grunn av reglene om fordeling av minne , er mer datamaskinens minne noen ganger tildelt enn nødvendig. For eksempel kan minne bare gis til programmer i biter (vanligvis et multiplum på 4 byte), og som et resultat hvis et program ber om kanskje 29 byte, vil det faktisk få en del på 32 byte. Når dette skjer, går overflødig minne bort. I dette scenariet er det ubrukelige minnet inneholdt i en tildelt region. Dette arrangementet, kalt faste partisjoner, lider av ineffektiv minnebruk - enhver prosess, uansett hvor liten, opptar en hel partisjon. Dette avfallet kalles intern fragmentering .

I motsetning til andre typer fragmentering er intern fragmentering vanskelig å gjenvinne; vanligvis er den beste måten å fjerne det med en designendring. For eksempel, i dynamisk minnetildeling , hukommelses bassenger drastisk kutte internkontroll fragmentering ved å spre plass indirekte over et større antall objekter.

Ekstern fragmentering

Ekstern fragmentering oppstår når ledig minne skilles i små blokker og blir spiss av tildelt minne. Det er en svakhet ved visse algoritmer for lagertildeling, når de ikke bestiller minne effektivt brukt av programmer. Resultatet er at selv om gratis lagring er tilgjengelig, er den faktisk ubrukelig fordi den er delt inn i stykker som er for små individuelt til å tilfredsstille kravene til applikasjonen. Begrepet "eksternt" refererer til det faktum at ubrukelig lagring er utenfor de tildelte regionene.

Vurder for eksempel en situasjon der et program tildeler tre sammenhengende blokker med minne og deretter frigjør den midtre blokken. Minnetildelingen kan bruke denne ledige minneblokken til fremtidige tildelinger. Den kan imidlertid ikke bruke denne blokken hvis minnet som skal tildeles er større enn denne ledige blokken.

Ekstern fragmentering forekommer også i filsystemer ettersom mange filer i forskjellige størrelser opprettes, endres i størrelse og slettes. Effekten er enda verre hvis en fil som er delt inn i mange små biter slettes, fordi dette etterlater like små områder med ledige mellomrom.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 Kommentarer
Start med alt minne som er tilgjengelig for lagring.
EN B C Tildelt tre blokker A, B og C, i størrelse 0x1000.
EN C Frigjort blokk B. Legg merke til at minnet som B brukte ikke kan inkluderes for en blokk større enn Bs størrelse.
EN C Blokk C flyttet inn i blokk Bs tomme spor, slik at den gjenværende plassen kan brukes til en større blokk med størrelse 0x4000.

Datafragmentering

Datafragmentering oppstår når en samling av data i minnet brytes opp i mange biter som ikke er tett sammen. Det er vanligvis et resultat av et forsøk på å sette inn et stort objekt i lagring som allerede har lidd ekstern fragmentering. For eksempel administreres filer i et filsystem vanligvis i enheter som kalles blokker eller klynger . Når et filsystem opprettes, er det ledig plass til å lagre filblokker sammen sammenhengende . Dette gir mulighet for hurtig sekvensiell lesing og skriving av filer. Etterhvert som filer legges til, fjernes og endres i størrelse, blir ledig plass fragmentert eksternt og etterlater bare små hull for å plassere nye data. Når en ny fil skrives, eller når en eksisterende fil utvides, legger operativsystemet de nye dataene i nye ikke-sammenhengende datablokker for å passe inn i de tilgjengelige hullene. De nye datablokkene er nødvendigvis spredt, noe som reduserer tilgangen på grunn av søketid og rotasjonsforsinkelse for lese/skrivehodet, og det påløper ytterligere overhead for å administrere flere steder. Dette kalles filsystemfragmentering .

Når du skriver en ny fil med en kjent størrelse, hvis det er noen tomme hull som er større enn den filen, kan operativsystemet unngå datafragmentering ved å sette filen inn i et av disse hullene. Det finnes en rekke algoritmer for å velge hvilke av de potensielle hullene for å legge filen; hver av dem er en heuristisk omtrentlig løsning på emballasjeproblemet . "Best fit" -algoritmen velger det minste hullet som er stort nok. "Verst passform" algoritmen velger det største hullet. " First-fit algoritmen " velger det første hullet som er stort nok. "Next fit" -algoritmen holder oversikt over hvor hver fil ble skrevet. "Next fit" -algoritmen er raskere enn "first fit", som igjen er raskere enn "best fit", som er samme hastighet som "worst fit".

På samme måte som komprimering kan eliminere ekstern fragmentering, kan datafragmentering elimineres ved å omorganisere datalagring slik at relaterte stykker ligger tett sammen. For eksempel er hovedoppgaven til et defragmenteringsverktøy å omorganisere blokker på disken slik at blokkene i hver fil er sammenhengende. De fleste defragmenterende verktøy prøver også å redusere eller eliminere fragmentering av ledig plass. Noen flyttbare søppeloppsamlere , verktøy som utfører automatisk minnestyring, vil også flytte relaterte objekter nær hverandre (dette kalles komprimering ) for å forbedre hurtigbufferytelsen.

Det er fire typer systemer som aldri opplever datafragmentering - de lagrer alltid hver fil sammenhengende. Alle fire typene har betydelige ulemper sammenlignet med systemer som tillater minst noen midlertidig datafragmentering:

  1. Bare skriv hver fil sammenhengende . Hvis det ikke allerede er nok sammenhengende ledig plass til å lagre filen, klarer ikke systemet å lagre filen umiddelbart - selv om det er mange små biter ledig plass fra slettede filer som gir mer enn nok til å lagre filen.
  2. Hvis det ikke allerede er nok sammenhengende ledig plass til å holde filen, bruker du en kopieringssamler til å konvertere mange små biter ledig plass til en sammenhengende ledig region som er stor nok til å holde filen. Dette tar mye mer tid enn å dele filen opp i fragmenter og sette disse fragmentene i ledig ledig plass.
  3. Skriv filen inn i en hvilken som helst gratis blokk, gjennom lagring av blokker i fast størrelse . Hvis en programmerer velger en fast blokkstørrelse for liten, klarer systemet ikke umiddelbart å lagre noen filer - filer større enn blokkstørrelsen - selv om det er mange ledige blokker som gir mer enn nok til å lagre filen. Hvis en programmerer velger en blokkstørrelse for stor, blir mye plass bortkastet på intern fragmentering.
  4. Noen systemer unngår dynamisk allokering helt, forhåndslagring (sammenhengende) plass til alle mulige filer de trenger-for eksempel forhåndstildeler MultiFinder en del RAM til hver applikasjon da den ble startet i henhold til hvor mye RAM programmets programmerer hevdet det ville trenge.

Oversikt

Sammenlignet med ekstern fragmentering står overhead og intern fragmentering for lite tap når det gjelder bortkastet minne og redusert ytelse. Det er definert som:

Fragmentering på 0% betyr at alt ledig minne er i en enkelt stor blokk; fragmentering er 90% (for eksempel) når 100 MB ledig minne er til stede, men den største ledige minneblokken for lagring er bare 10 MB.

Ekstern fragmentering har en tendens til å være et mindre problem i filsystemer enn i lagringssystemer for primærminne (RAM), fordi programmer vanligvis krever at RAM -lagringsforespørsler oppfylles med sammenhengende blokker, men filsystemer er vanligvis designet for å kunne bruke hvilken som helst samling av tilgjengelige blokker (fragmenter) for å sette sammen en fil som logisk virker sammenhengende. Derfor, hvis en svært fragmentert fil eller mange små filer slettes fra et fullt volum og deretter opprettes en ny fil med størrelse som er lik den nylig frigjorte plassen, vil den nye filen ganske enkelt gjenbruke de samme fragmentene som ble frigjort ved sletting. Hvis det som ble slettet var en fil, vil den nye filen være like fragmentert som den gamle filen var, men det vil uansett ikke være noen hindring for å bruke all (sterkt fragmentert) ledig plass til å lage den nye filen. I RAM, derimot, kan lagringssystemene som brukes ofte ikke sette sammen en stor blokk for å imøtekomme en forespørsel fra små ikke -sammenhengende gratisblokker, og derfor kan forespørselen ikke oppfylles, og programmet kan ikke fortsette å gjøre det den trengte minnet for (med mindre den kan utstede forespørselen på nytt som et antall mindre separate forespørsler).

Problemer

Lagringsfeil

Det alvorligste problemet forårsaket av fragmentering forårsaker at en prosess eller et system mislykkes på grunn av for tidlig oppbrudd av ressurser: Hvis en sammenhengende blokk må lagres og ikke kan lagres, oppstår det feil. Fragmentering får dette til å skje selv om det er nok av ressursen, men ikke en sammenhengende mengde. For eksempel, hvis en datamaskin har 4 GiB minne og 2 GiB er ledig, men minnet er fragmentert i en vekslende sekvens på 1 MiB brukt, 1 MiB ledig, kan en forespørsel om 1 sammenhengende GiB minne ikke oppfylles selv om 2 GiB totalt er gratis.

For å unngå dette kan allokatoren, i stedet for å mislykkes, utløse en defragmentering (eller minnekomprimeringssyklus) eller annen ressursgjenvinning, for eksempel en stor søppelsamlingssyklus, i håp om at den da vil kunne tilfredsstille forespørselen. Dette gjør at prosessen kan fortsette, men kan påvirke ytelsen alvorlig.

Forringelse av ytelsen

Fragmentering forårsaker ytelsesforringelse av flere årsaker. Stort sett øker fragmenteringen arbeidet som kreves for å tildele og få tilgang til en ressurs. For eksempel, på en harddisk eller båndstasjon, er sekvensielle datalesninger veldig raske, men det er tregt å søke til en annen adresse, så å lese eller skrive en fragmentert fil krever mange søk og er dermed mye tregere, i tillegg til å forårsake større slitasje på enheten. Videre, hvis en ressurs ikke er fragmentert, kan tildelingsforespørsler ganske enkelt oppfylles ved å returnere en enkelt blokk fra starten av gratisområdet. Uansett om den er fragmentert, krever forespørselen enten å lete etter en stor nok gratis blokk, som kan ta lang tid, eller oppfylle forespørselen med flere mindre blokker (hvis dette er mulig), noe som resulterer i at denne tildelingen blir fragmentert og krever ytterligere overhead for å administrere flere stykker.

Et subtilere problem er at fragmentering kan utmatte en hurtigbuffer for tidlig og forårsake søppel på grunn av hurtigbuffere som holder blokker, ikke individuelle data. Anta for eksempel at et program har et arbeidssett på 256 KiB, og kjører på en datamaskin med en 256 KiB -cache (si L2 -instruksjon+datacache), så hele arbeidssettet passer i hurtigbufferen og kjøres dermed raskt, i det minste i vilkår for cache -treff. Anta videre at den har 64 oversettelseslookaside buffer (TLB) oppføringer, hver for en 4 KiB side : hver minnetilgang krever en virtuell til fysisk oversettelse, som er rask hvis siden er i cache (her TLB). Hvis arbeidssettet er ufragmentert, så vil det passe på nøyaktig 64 sider (den siden arbeids settet vil være 64 sider), og alle minne oppslag kan serveres fra cache. Imidlertid, hvis arbeidssettet er fragmentert, vil det ikke passe inn på 64 sider, og utførelsen vil avta på grunn av søppel: sider blir flere ganger lagt til og fjernet fra TLB under drift. Cache -størrelsen i systemdesign må derfor inneholde margin for å ta hensyn til fragmentering.

Minnefragmentering er et av de mest alvorlige problemene som systemansvarlige står overfor . Over tid fører det til forringelse av systemytelsen. Til slutt kan fragmentering av hukommelse føre til fullstendig tap av (applikasjonsbrukbart) ledig minne.

Minne fragmentering er en kjerne programmeringsnivå problem. Under sanntidsberegning av applikasjoner kan fragmenteringsnivåene nå opp til 99%, og kan føre til systemkrasj eller andre ustabilitet. Denne typen systemkrasj kan være vanskelig å unngå, siden det er umulig å forutse den kritiske økningen i nivåer av minnefragmentering. Selv om det kanskje ikke er mulig for et system å fortsette å kjøre alle programmene i tilfelle overdreven hukommelsesfragmentering, bør et godt designet system kunne komme seg etter den kritiske fragmenteringstilstanden ved å bevege seg i noen minneblokker som brukes av selve systemet for å muliggjøre konsolidering av ledig minne i færre, større blokker, eller i verste fall ved å avslutte noen programmer for å frigjøre minnet og deretter defragmentere den resulterende summen av ledig minne. Dette vil i det minste unngå et sant krasj i betydningen systemfeil og tillate systemet å fortsette å kjøre noen programmer, lagre programdata, etc. Det er også viktig å merke seg at fragmentering er et fenomen av systemprogramvaredesign; forskjellig programvare vil være utsatt for fragmentering i ulik grad, og det er mulig å designe et system som aldri vil bli tvunget til å slå av eller drepe prosesser som et resultat av minnefragmentering.

Analoge fenomener

Selv om fragmentering er best kjent som et problem i minnetildeling, forekommer analoge fenomener for andre ressurser , særlig prosessorer. For eksempel, i et system som bruker tidsdeling for forebyggende multitasking , men som ikke sjekker om en prosess er blokkert, en prosess som utføres for en del av sin tidsskive, men deretter blokkerer og ikke kan fortsette for resten av sin tidskive tid på grunn av den resulterende interne fragmenteringen av tidskiver. Mer grunnleggende forårsaker tidsdeling i seg selv ekstern fragmentering av prosesser på grunn av å kjøre dem i fragmenterte tidsskiver, snarere enn i en enkelt ubrutt kjøring. Den resulterende kostnaden for prosessbytte og økt buffertrykk fra flere prosesser som bruker de samme cachene, kan resultere i forringet ytelse.

I samtidige systemer , spesielt distribuerte systemer , når en gruppe prosesser må samhandle for å gå videre, hvis prosessene er planlagt på separate tidspunkter eller på separate maskiner (fragmentert på tvers av tid eller maskiner), tiden som brukes til å vente på hverandre eller kommunisere med hverandre kan forringe ytelsen alvorlig. I stedet krever performante systemer co -planlegging av gruppen.

Noen flash -filsystemer har flere forskjellige typer intern fragmentering som involverer "dødt rom" og "mørkt rom.".

Se også

Referanser

Kilder