Hva er en gratis liste?
En gratis liste er en datastruktur som inneholder adressene til datamaskinminnets lokasjoner som er tilgjengelige for bruk av et løpende program når du bruker dynamisk minnetildeling. Listen blir nødvendig når et program må tildelePlass fra et område med fritt minne kalt heapen. Implementeringen av en gratis liste kan være en enkel koblet liste eller kan være en mer kompleks datastruktur som for eksempelet sorterMå be om en spesifikk mengde minne fra det underliggende operativsystemet. Plasseringene av minneblokker som kan brukes, lagres i gratislisten. For at tildelingen skal være vellykket, mengden etterforespurt minnemå være tilgjengelig i en eller flere av disse blokkene. Når en peker til et passende minnelocation returneres, det elementet på listen fjernes.
Etter at et program er gjort ved hjelp av minnet, kan det fordele det. Dette innebærer å overføre pekeren til minnetBlokker tilbake i gratislisten, der den vil bli tilgjengelig neste gang en tildeling blir forsøkt. Det er mulig for minnetildeling å mislykkes fordi listen er tom eller fordi det ikke er noen tilgjengelige minneblokker som er store nok til å oppfylleProgrammets forespørsel.
Den enkleste formen for minnestyring kalles det første passformsystemet. Dette systemet opprettholder en enkelt liste over gratis minneplasser. Når en forespørsel om minne sendes,Listen er krysset og den første blokken som er stor nok blir returnert. Hvis blokken er mer enn det dobbelte av den forespurte størrelsen, blir den halvert, og den ubrukte halvparten blir lagt tilbake til listen. Denne metoden handler enkel koding for risikoen for å ha fragmentert minneOmråder som kanskje aldri blir returnert til listen.
En annen form for minnestyring kalles kompisfordelingssystemet. I motsetning til det første passformsystemet, holder kompisfordelingen flere gratis lister, hver og en holderÅpne blokker av bare en bestemt størrelse. Dette betyr at når en tildeling av tildelinger blir mottatt, blir listen som har blokker som er bare store nok til å fylle forespørselen, og et åpent sted returneres. Hvis ingenGratis blokker som er mindre enn det dobbelte av størrelsen som etterspørres er tilgjengelige, en større blokk er delt i to for å oppfylle kravene.
Begrepet gratis liste kan referere til enten en enkelt koblet liste over minneadresser,eller det kan referere til en mye mer kompleks type datastruktur. Ulike typer slags trær, hvis de holdes enkle og balanserte, kan bidra til å øke hastigheten på å finne åpne minneblokker på bekostning av å kompliserekildekoden. En koblet liste kan være tregere enn et spesialisert sorter, men oppretter programmering kode som er langt lettere å lese, feilsøke og endre.
Noen programmeringsspråk og operativsystemer bruker en spesiell mekanisme som kalles søppelinnsamling. Dette er en prosess som kan bidra til å ta de forskjellige oppføringene på enGratis liste og konsolidere de frie områdene slik at de er sammenhengende. Dette har effekten av å forhindre fragmentering og gjøre det mulig for større minneblokker.