Hvad er en gratis liste?
En gratis liste er en datastruktur, der indeholder adresserne på computerhukommelsesplaceringer, der er tilgængelige til brug af et kørende program, når der bruges dynamisk hukommelsesallokering. Listen bliver nødvendig, når et program skal allokere plads fra et område med fri hukommelse kaldet heapen. Implementeringen af en gratis liste kan være en enkel linket liste eller kan være en mere kompleks datastruktur, såsom sorteringstræ. De fleste programmeringssprog på højt niveau håndterer automatisk gratis listen og fjerner behovet for manuel styring.
Når et program kræver plads til at gemme information under programudførelse, skal det anmode om en bestemt mængde hukommelse fra det underliggende operativsystem. Placeringen af hukommelsesblokke, der kan bruges, gemmes i det frie for at tildelingen skal være vellykket, skal mængden af den ønskede hukommelse være tilgængelig i en eller flere af disse blokke. Når en markør til en passende hukommelsesplacering returneres, det element på listen fjernes.
Når et program er udført ved hjælp af hukommelsen, kan det affordele det. Dette indebærer, at markøren overføres til hukommelsesblokken tilbage til den frie liste, hvor den bliver tilgængelig næste gang en tildeling er Det er muligt for hukommelsestildeling at mislykkes, fordi listen er tom, eller fordi der ikke er tilgængelige hukommelsesblokke, der er store nok til at imødekomme programmets anmodning.
Den enkleste form for hukommelsesstyring kaldes det første fit system Dette system opretholder en enkelt liste over ledige hukommelsesplaceringer. Når der sendes en anmodning om hukommelse, gennemføres listen og den første blok der er stor nok returneres. Hvis blokken er mere end dobbelt så stor som den ønskede størrelse, halveres den, og den ubrugte halvdel tilføjes tilbage til listen. Denne metode handler med enkel kodning for risikoen for at have fragmenterede hukommelsesområder, der måske aldrig returneres til listen.
En anden form for hukommelseshåndtering kaldes buddy allocation-systemet. I modsætning til det første fit-system holder bud-allokering flere gratis lister, der hver har åbne blokke i kun en bestemt størrelse. Når en tildelingsanmodning modtages, konsulteres listen, der indeholder blokke, der er lige store nok til at udfylde anmodningen, og en åben placering returneres. Hvis der ikke findes gratis blokke, der er mindre end det dobbelte af størrelsen anmodede er tilgængelige, en større blok er delt i to for at opfylde kravene.
Udtrykket "fri liste" kan henvise til enten en enkelt linket liste over hukommelsesadresser, eller det kan henvise til en meget mere kompleks type datastruktur. Forskellige typer sorteretræer, hvis de holdes enkle og afbalancerede, kan hjælpe med at øge hastigheden ved at finde åbne hukommelsesblokke på bekostning af at komplicere kildekoden. En tilknyttet liste kan være langsommere end et specialiseret sorteringstræ, men skaber programmeringskode, der er langt lettere at læse, debug og modificer.
Nogle programmeringssprog og operativsystemer bruger en speciel mekanisme kaldet affaldsopsamling.Dette er en proces, der kan hjælpe med at tage de forskellige poster på en gratis liste og konsolidere de frie rum, så de er sammenhængende. effekten af at forhindre fragmentering og tillade, at større blokke af hukommelse tildeles.