Hva er en gratis liste?
En gratis liste er en datastruktur som inneholder adressene til datamaskinens plasseringer som er tilgjengelige for bruk av et kjørende program når du bruker dynamisk minnetildeling. Listen blir nødvendig når et program må tildele plass fra et område med fritt minne som kalles heapen. Implementeringen av en gratis liste kan være en enkel koblet liste eller kan være en mer kompleks datastruktur som en sorter tre. De fleste programmeringsspråk på høyt nivå håndterer automatisk gratislisten og fjerner behovet for manuell styring.
Når et program krever plass for å lagre informasjon under programutførelse, må det be om en bestemt mengde minne fra det underliggende operativsystemet. Plasseringene av minneblokker som kan brukes, er lagret i det frie for at tildelingen skal lykkes, må mengden av ønsket minne være tilgjengelig i en eller flere av disse blokkene. Når en peker til et passende minneplass returneres, det elementet i listen blir fjernet.
Etter at et program er gjort med minnet, kan det fordele det. Dette innebærer å føre pekeren til minneblokken tilbake til gratislisten, der den vil bli tilgjengelig neste gang en tildeling er Det er mulig for minnetildeling å mislykkes fordi listen er tom, eller fordi det ikke er tilgjengelige minneblokker store nok til å oppfylle programmets forespørsel.
Den enkleste formen for minnehåndtering kalles det første passingssystemet. Dette systemet opprettholder en enkelt liste over ledige minneplasser. Når en forespørsel om minne sendes, blir listen 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 halvdelen blir lagt tilbake til listen. Denne metoden handler enkelt koding for risikoen for å ha fragmenterte minneområder som kanskje aldri blir returnert til listen.
En annen form for minnestyring kalles kompisallokeringssystemet. I motsetning til det første passingssystemet holder kompisfordelingen flere gratis lister, hver og en har åpne blokker av bare en bestemt størrelse. når en tildelingsforespørsel mottas, blir listen over blokker som er like store nok til å fylle forespørselen, konsultert, og en åpen plassering returneres. Hvis ingen gratis blokker som er mindre enn dobbelt så stor som etterspurt er tilgjengelige, en større blokk er delt i to for å oppfylle kravene.
Begrepet "gratis liste" kan referere til enten en enkelt lenket liste over minneadresser, eller den kan referere til en mye mer sammensatt type datastruktur. Ulike typer sortertrær, hvis de holdes enkle og balanserte, kan bidra til å øke hastigheten på å finne åpne minneblokker på bekostning av å komplisere kildekoden. En lenket liste kan være tregere enn et spesialisert sorteringstre, men oppretter programmeringskoder som er langt lettere å lese, feilsøke og endre.
Noen programmeringsspråk og operativsystemer bruker en spesiell mekanisme kalt søppelinnsamling. Dette er en prosess som kan hjelpe deg med å ta de forskjellige oppføringene på en gratis liste og konsolidere de frie områdene slik at de er sammenhengende. effekten av å forhindre fragmentering og tillate større blokkering av minne.