Fragmentering (computing) - Fragmentation (computing)

For filsystemfragmentering, se Filsystemfragmentering .

I computerlagring er fragmentering et fænomen, hvor lagerplads, hovedlager eller sekundær opbevaring bruges ineffektivt, hvilket reducerer kapacitet eller ydeevne og ofte begge dele. De nøjagtige konsekvenser af fragmentering afhænger af det specifikke system til lagertildeling i brug og den særlige fragmenteringsform. I mange tilfælde fører fragmentering til, at lagerplads bliver "spildt", og i så fald refererer udtrykket også til selve det spildte rum.

Typer af fragmentering

Der er tre forskellige, men beslægtede former for fragmentering: ekstern fragmentering, intern fragmentering og datafragmentering, som kan være til stede isoleret eller sammen. Fragmentering accepteres ofte til gengæld for forbedringer i hastighed eller enkelhed. Analoge fænomener forekommer for andre ressourcer såsom processorer; se nedenunder.

Grundlæggende princip

Når et computerprogram anmoder om hukommelsesblokke fra computersystemet, tildeles blokkene i klumper. Når computerprogrammet er færdigt med et stykke, kan det frigøre det tilbage til systemet, hvilket gør det tilgængeligt for senere at blive allokeret igen til et andet eller det samme program. Størrelsen og mængden af ​​tid, en del er i et program, varierer. I løbet af sin levetid kan et computerprogram anmode om og frigøre mange bidder af hukommelse.

Når et program startes, er ledige hukommelsesområder lange og sammenhængende. Over tid og med brug bliver de lange sammenhængende områder fragmenteret i mindre og mindre sammenhængende områder. Til sidst kan det blive umuligt for programmet at få store sammenhængende bidder af hukommelse.

Typer

Intern fragmentering

Hukommelsessøgning skaber intern fragmentering, fordi der vil blive tildelt en hel sideramme , uanset om der er brug for så meget lagerplads. På grund af reglerne for tildeling hukommelse , er mere computerens hukommelse til tider allokeret end der er behov for. For eksempel kan hukommelse kun leveres til programmer i bidder (normalt et multiplum på 4 bytes), og som et resultat, hvis et program anmoder om måske 29 bytes, vil det faktisk få en bid på 32 bytes. Når dette sker, går den overskydende hukommelse til spilde. I dette scenario er den ubrugelige hukommelse indeholdt i en tildelt region. Dette arrangement, der kaldes faste partitioner, lider under ineffektiv hukommelsesbrug - enhver proces, uanset hvor lille, fylder en hel partition. Dette affald kaldes intern fragmentering .

I modsætning til andre former for fragmentering er intern fragmentering vanskelig at genvinde; normalt er den bedste måde at fjerne det med en designændring. For eksempel i hukommelsen dynamisk allokering , memory pools drastisk nedskæring opsplitning ved at sprede rummet ovenover over et større antal objekter.

Ekstern fragmentering

Ekstern fragmentering opstår, når ledig hukommelse adskilles i små blokke og spækkes med tildelt hukommelse. Det er en svaghed ved visse lagertildelingsalgoritmer, når de ikke bestiller hukommelse, der bruges af programmer effektivt. Resultatet er, at selvom der er gratis opbevaring tilgængelig, er den faktisk ubrugelig, fordi den er opdelt i stykker, der er for små individuelt til at tilfredsstille applikationens krav. Udtrykket "eksternt" henviser til det faktum, at det ubrugelige lager er uden for de tildelte regioner.

Overvej f.eks. En situation, hvor et program tildeler tre kontinuerlige hukommelsesblokke og derefter frigør midterblokken. Hukommelsesallokatoren kan bruge denne gratis hukommelsesblok til fremtidige tildelinger. Den kan dog ikke bruge denne blok, hvis den hukommelse, der skal tildeles, er større end denne gratis blok.

Ekstern fragmentering forekommer også i filsystemer, da mange filer i forskellige størrelser oprettes, ændrer størrelse og slettes. Effekten er endnu værre, hvis en fil, der er opdelt i mange små stykker, slettes, fordi det efterlader tilsvarende små områder med ledige rum.

0x0000 0x1000 0x2000 0x3000 0x4000 0x5000 Kommentarer
Start med al tilgængelig hukommelse til opbevaring.
EN B C Tildelt tre blokke A, B og C i størrelse 0x1000.
EN C Frigivet blok B. Bemærk, at den hukommelse, som B brugte, ikke kan inkluderes for en blok, der er større end B's størrelse.
EN C Blok C flyttede ind i blok B's tomme slot, så den resterende plads kunne bruges til en større blok i størrelsen 0x4000.

Datafragmentering

Datafragmentering opstår, når en samling af data i hukommelsen opdeles i mange stykker, der ikke er tæt på hinanden. Det er typisk resultatet af forsøg på at indsætte et stort objekt i lageret, der allerede har lidt ekstern fragmentering. For eksempel administreres filer i et filsystem normalt i enheder kaldet blokke eller klynger . Når et filsystem oprettes, er der ledig plads til at gemme filblokke sammen sammenhængende . Dette giver mulighed for hurtig sekventiel fillæsning og skrivning. Men efterhånden som filer tilføjes, fjernes og ændres i størrelse, bliver ledig plads fragmenteret eksternt og efterlader kun små huller til placering af nye data. Når en ny fil skrives, eller når en eksisterende fil udvides, lægger operativsystemet de nye data i nye ikke-sammenhængende datablokke for at passe ind i de tilgængelige huller. De nye datablokke er nødvendigvis spredt, hvilket bremser adgangen på grund af søge tid og rotations latens for læse/skrive hovedet og pådrage sig ekstra omkostninger til at styre yderligere placeringer. Dette kaldes filsystemfragmentering .

Når du skriver en ny fil af en kendt størrelse, hvis der er tomme huller, der er større end den fil, kan operativsystemet undgå datafragmentering ved at sætte filen i et af disse huller. Der er en række forskellige algoritmer til at vælge, hvilket af de potentielle huller der skal placeres filen; hver af dem er en heuristisk omtrentlig løsning på emballageproblemet . "Best fit" -algoritmen vælger det mindste hul, der er stort nok. "Værst egnet" -algoritmen vælger det største hul. " First-fit algoritmen " vælger det første hul, der er stort nok. Algoritmen "næste tilpasning" holder styr på, hvor hver fil blev skrevet. "Next fit" -algoritmen er hurtigere end "first fit", som igen er hurtigere end "best fit", som er den samme hastighed som "worst fit".

Ligesom komprimering kan eliminere ekstern fragmentering, kan datafragmentering elimineres ved at omarrangere datalagring, så relaterede stykker er tæt på hinanden. For eksempel er et defragmenteringsværktøjs primære opgave at omarrangere blokke på disken, så blokkene i hver fil er sammenhængende. De fleste defragmenteringsværktøjer forsøger også at reducere eller eliminere fragmentering af ledigt rum. Nogle bevægelige affaldssamlere , hjælpeprogrammer, der udfører automatisk hukommelsesstyring, vil også flytte relaterede objekter tæt sammen (dette kaldes komprimering ) for at forbedre cacheydelsen.

Der er fire slags systemer, der aldrig oplever datafragmentering - de gemmer altid hver fil sammenhængende. Alle fire slags har betydelige ulemper sammenlignet med systemer, der tillader mindst en vis midlertidig datafragmentering:

  1. Du skal blot skrive hver fil sammenhængende . Hvis der ikke allerede er tilstrækkelig sammenhængende ledig plads til at gemme filen, undlader systemet straks at gemme filen - selv når der er mange små stykker ledig plads fra slettede filer, der giver mere end nok til at gemme filen.
  2. Hvis der ikke allerede er tilstrækkelig sammenhængende ledig plads til at gemme filen, skal du bruge en kopieringsopsamler til at konvertere mange små stykker ledig plads til et sammenhængende ledigt område, der er stort nok til at holde filen. Dette tager meget mere tid end at bryde filen op i fragmenter og sætte disse fragmenter i den ledige ledige plads.
  3. Skriv filen i en hvilken som helst gratis blok gennem lagring af blokke i fast størrelse . Hvis en programmør vælger en fast blokstørrelse for lille, gemmer systemet ikke umiddelbart nogle filer - filer større end blokstørrelsen - selv når der er mange gratis blokke, der giver mere end nok til at gemme filen. Hvis en programmør vælger en blokstørrelse for stor, spildes meget plads på intern fragmentering.
  4. Nogle systemer undgår helt dynamisk tildeling, forlagring (sammenhængende) plads til alle mulige filer, de skal bruge-for eksempel tildeler MultiFinder en del RAM til hver applikation, da den blev startet i henhold til, hvor meget RAM, programmets programmør hævdede det ville have brug for.

Oversigt

Sammenlignet med ekstern fragmentering tegner overhead og intern fragmentering sig for lidt tab i form af spildt hukommelse og reduceret ydeevne. Det er defineret som:

Fragmentering på 0% betyder, at al den ledige hukommelse er i en enkelt stor blok; fragmentering er 90% (f.eks.), når der er 100 MB ledig hukommelse til stede, men den største ledige hukommelsesblok til opbevaring er kun 10 MB.

Ekstern fragmentering har en tendens til at være et mindre problem i filsystemer end i primære hukommelseslagre (RAM), fordi programmer normalt kræver, at deres RAM -lagringsanmodninger opfyldes med sammenhængende blokke, men filsystemer er typisk designet til at kunne bruge enhver samling af tilgængelige blokke (fragmenter) til at samle en fil, der logisk ser ud til at være sammenhængende. Derfor, hvis en meget fragmenteret fil eller mange små filer slettes fra en fuld mængde, og der derefter oprettes en ny fil med størrelse svarende til det nyligt frigjorte rum, vil den nye fil simpelthen genbruge de samme fragmenter, der blev frigivet ved sletningen. Hvis det, der blev slettet, var en fil, vil den nye fil være lige så fragmenteret, som den gamle fil var, men under alle omstændigheder vil der ikke være nogen barriere for at bruge al (stærkt fragmenteret) ledig plads til at oprette den nye fil. I RAM, på den anden side, kan de anvendte lagersystemer ofte ikke samle en stor blok for at imødekomme en anmodning fra små ikke -sammenhængende gratis blokke, og derfor kan anmodningen ikke opfyldes, og programmet kan ikke fortsætte med at gøre, hvad det havde brug for den hukommelse til (medmindre det kan genudstede anmodningen som et antal mindre separate anmodninger).

Problemer

Lagringsfejl

Det mest alvorlige problem forårsaget af fragmentering er at få en proces eller et system til at mislykkes på grund af for tidlig ressourceudmattelse: Hvis en sammenhængende blok skal lagres og ikke kan lagres, opstår der fejl. Fragmentering får dette til at ske, selvom der er nok af ressourcen, men ikke en sammenhængende mængde. For eksempel, hvis en computer har 4 GiB hukommelse og 2 GiB er ledig, men hukommelsen er fragmenteret i en skiftende sekvens af 1 brugt MiB, 1 MiB fri, så kan en anmodning om 1 sammenhængende GiB hukommelse ikke opfyldes, selvom 2 GiB -total er gratis.

For at undgå dette kan allokatoren i stedet for at mislykkes udløse en defragmentering (eller hukommelseskomprimeringscyklus) eller anden genvinding af ressourcer, f.eks. En større affaldsindsamlingscyklus, i håb om at den derefter vil kunne imødekomme anmodningen. Dette tillader processen at fortsætte, men kan påvirke ydeevnen alvorligt.

Forringelse af ydeevnen

Fragmentering forårsager ydelsesforringelse af flere årsager. Grundlæggende øger fragmentering det arbejde, der kræves for at tildele og få adgang til en ressource. For eksempel på en harddisk eller bånddrev er sekventielle datalæsninger meget hurtige, men søgning til en anden adresse er langsom, så læsning eller skrivning af en fragmenteret fil kræver mange søger og er derfor meget langsommere, udover at forårsage større slid på enheden. Yderligere, hvis en ressource ikke er fragmenteret, kan allokeringsanmodninger blot opfyldes ved at returnere en enkelt blok fra starten af ​​det frie område. Uanset hvordan den er fragmenteret, kræver anmodningen enten at søge efter en tilstrækkelig stor gratis blok, som kan tage lang tid, eller at opfylde anmodningen med flere mindre blokke (hvis dette er muligt), hvilket resulterer i, at denne allokering bliver fragmenteret og kræver yderligere overhead til at styre de flere stykker.

Et subtilere problem er, at fragmentering for tidligt kan udmatte en cache og forårsage stød på grund af caches, der holder blokke, ikke individuelle data. Antag for eksempel, at et program har et arbejdssæt på 256 KiB og kører på en computer med en 256 KiB -cache (f.eks. L2 -instruktion+datacache), så hele arbejdssættet passer i cachen og udføres dermed hurtigt, i det mindste i vilkår for cache -hits. Antag endvidere, at den har 64 oversættelses lookaside buffer (TLB) poster, hver for en 4 KiB side : hver hukommelsesadgang kræver en virtuel til fysisk oversættelse, hvilket er hurtigt, hvis siden er i cache (her TLB). Hvis arbejdsmiljøet sæt er fragmenteret, så vil det passe på nøjagtig 64 sider (den side arbejdssæt vil være 64 sider), og alle hukommelse opslag kan serveres fra cachen. Men hvis arbejdssættet er fragmenteret, passer det ikke til 64 sider, og udførelsen vil bremse på grund af stød: sider tilføjes og fjernes gentagne gange fra TLB under drift. Cachestørrelse i systemdesign skal således indeholde margin for at tage højde for fragmentering.

Hukommelsesfragmentering er et af de mest alvorlige problemer, som systemansvarlige står over for . Over tid fører det til forringelse af systemets ydeevne. Til sidst kan hukommelsesfragmentering føre til fuldstændigt tab af (applikationsbrugelig) ledig hukommelse.

Hukommelse fragmentering er en kerne programmering niveau problem. Under realtidsberegning af applikationer kan fragmenteringsniveauer nå op på 99%og kan føre til systemnedbrud eller andre ustabilitet. Denne type systemnedbrud kan være vanskelig at undgå, da det er umuligt at forudse den kritiske stigning i niveauer af hukommelsesfragmentering. Selvom det muligvis ikke er muligt for et system at fortsætte med at køre alle programmer i tilfælde af overdreven hukommelsesfragmentering, bør et veldesignet system kunne genoprette den kritiske fragmenteringstilstand ved at bevæge sig i nogle hukommelsesblokke, der bruges af selve systemet for at muliggøre konsolidering af ledig hukommelse i færre, større blokke eller i værste fald ved at afslutte nogle programmer for at frigøre deres hukommelse og derefter defragmentere den resulterende sum af gratis hukommelse. Dette vil i det mindste undgå et sandt nedbrud i betydningen systemfejl og give systemet mulighed for at fortsætte med at køre nogle programmer, gemme programdata osv. Det er også vigtigt at bemærke, at fragmentering er et fænomen i systemsoftwaredesign; forskellig software vil være modtagelig for fragmentering i forskellige grader, og det er muligt at designe et system, der aldrig vil blive tvunget til at lukke ned eller dræbe processer som følge af hukommelsesfragmentering.

Analoge fænomener

Selvom fragmentering bedst er kendt som et problem i hukommelsesallokering, forekommer analoge fænomener for andre ressourcer , især processorer. For eksempel i et system, der bruger tidsdeling til forebyggende multitasking , men som ikke kontrollerer, om en proces er blokeret, en proces, der udføres for en del af sin tidsskive, men derefter blokerer og ikke kan fortsætte i resten af ​​sin tidsskive spilder tid på grund af den resulterende interne fragmentering af tidskiver. Mere grundlæggende forårsager tidsdeling i sig selv ekstern fragmentering af processer på grund af at køre dem i fragmenterede tidsskiver snarere end i et enkelt ubrudt løb. De resulterende omkostninger ved processkift og øget cachetryk fra flere processer, der bruger de samme caches, kan resultere i forringet ydeevne.

I samtidige systemer , især distribuerede systemer , når en gruppe processer skal interagere for at komme videre, hvis processerne er planlagt på separate tidspunkter eller på separate maskiner (fragmenteret på tværs af tid eller maskiner), den tid der bruges på at vente på hinanden eller kommunikere med hinanden kan forringe ydeevnen kraftigt. I stedet kræver performante systemer en tidsplanlægning af gruppen.

Nogle flashfilsystemer har flere forskellige former for intern fragmentering, der involverer "dødt rum" og "mørkt rum.".

Se også

Referencer

Kilder