Hvad er en gratis liste?
En gratis liste er en datastruktur, der indeholder adresserne på computerhukommelsespladser, der er tilgængelige til brug af et kørende program, når du bruger dynamisk hukommelsesallokering. Listen bliver nødvendig, når et program skal tildeleRum fra et område med fri hukommelse kaldet bunken. Implementeringen af en gratis liste kan være en simpel linket liste eller kan være en mere kompleks datastruktur, såsomet slags træ. De fleste højniveau computerprogrammeringssprog håndterer automatisk den gratis liste og fjerner behovet for manuel styring.
Når et program kræver plads til at gemme information under programudførelse, er detSkal anmode om en bestemt mængde hukommelse fra det underliggende operativsystem. De placeringer af hukommelsesblokke, der kan bruges, gemmes på den gratis liste. For at tildelingen skal være vellykketskal være tilgængelig i en eller flere af disse blokke. Når en markør til en passende hukommelses location returneres, det element på listen fjernes.
Efter at et program er udført ved hjælp af hukommelsen, kan det de-allokere det. Dette involverer at videregive markøren til hukommelsenBloker tilbage på den gratis liste, hvor den bliver tilgængelig næste gang en tildeling forsøges. Det er muligt for hukommelsesallokering at mislykkes, fordi listen er tom, eller fordi der ikke er nogen tilgængelige hukommelsesblokke, der er store nok til at opfyldeProgrammets anmodning.
Den enkleste form for hukommelsesstyring kaldes det første fit -system. Dette system opretholder en enkelt liste over gratis hukommelsessteder. Når en anmodning om hukommelse sendes, sendesListen krydses, og den første blok, der er stor nok, returneres. Hvis blokken er mere end det dobbelte af den ønskede størrelse, er den halveret, og den ubrugte halvdel tilføjes tilbage til listen. Denne metode handler enkel kodning for risikoen for at have fragmenteret hukommelseOmråder, der måske aldrig returneres til listen.
En anden form for hukommelsesstyring kaldes Buddy -allokeringssystemet. I modsætning til det første FIT -system, holder Buddy -allokering flere gratis lister, hver enkelt holderÅbne blokke på kun en bestemt størrelse. Dette betyder, at når der modtages en tildelingsanmodning, er listen, der indeholder blokke, der er lige store nok til at udfylde anmodningen, konsulteres, og en åben placering returneres. Hvis NOGratis blokke, der er mindre end det dobbelte af den ønskede størrelse, er tilgængelige, en større blok er opdelt i to for at opfylde kravene.
Udtrykket gratis liste kan henvise til enten en enkelt linket liste over hukommelsesadresser,Eller det kan henvise til en meget mere kompleks type datastruktur. Forskellige typer af sorteringstræer, hvis de holdes enkle og afbalancerede, kan hjælpe med at øge hastigheden ved at finde åbne hukommelsesblokke på bekostning af at komplicerekildekoden. En tilknyttet liste kan være langsommere end et specialiseret sorteringstræ, men opretter programming -kode, der er langt lettere at læse, debug og ændre.
Nogle programmeringssprog og operativsystemer gør brug af en speciel mekanisme kaldet Garbage Collection. Dette er en proces, der kan hjælpe med at tage de forskellige poster på enGratis liste og konsolider de gratis rum, så de er sammenhængende. Dette har den virkning at forhindre fragmentering og give mulighed for, at større hukommelsesblokke tildeles.