Vad är en gratis lista?
En gratis lista är en datastruktur som innehåller adresserna till datorminnesplatser som är tillgängliga för användning av ett löpande program när dynamisk minnesallokering används. Listan blir nödvändig när ett program måste tilldela utrymme från ett område med fritt minne som kallas högen. Implementeringen av en fri lista kan vara en enkel länkad lista eller kan vara en mer komplex datastruktur, t.ex. sortera träd. De flesta högklassiga datorprogrammeringsspråk hanterar automatiskt gratislistan och tar bort behovet av manuell hantering.
När ett program kräver utrymme för att lagra information under programkörning måste det begära en viss mängd minne från det underliggande operativsystemet. Platserna för minnesblock som kan användas lagras i det fria För att allokeringen ska lyckas måste mängden önskat minne vara tillgängligt i ett eller flera av dessa block. När en pekare till en lämplig minnesplats returneras, det elementet i listan tas bort.
När ett program har gjorts med minnet kan det avdela det. Detta innebär att pekaren flyttas till minnesblocket tillbaka till gratislistan, där den kommer att bli tillgänglig nästa gång en allokering är Det är möjligt att minnesallokering misslyckas eftersom listan är tom eller eftersom det inte finns några tillgängliga minnesblock som är tillräckligt stora för att uppfylla programmets begäran.
Den enklaste formen för minneshantering kallas det första passningssystemet. Detta system har en enda lista över lediga minnesplatser. När en begäran om minne skickas, listas genom och det första blocket som är tillräckligt stor returneras. Om blocket är mer än två gånger den begärda storleken, halveras den och den oanvända halvan läggs tillbaka till listan. Denna metod handlar enkel kodning för risken för att ha fragmenterade minnesområden som kanske aldrig återgår till listan.
En annan form av minneshantering kallas kompisallokeringssystemet. Till skillnad från det första passningssystemet håller kompisallokeringen flera gratislistor, var och en har öppna block av endast en viss storlek. när en tilldelningsbegäran tas emot konsulteras listan som innehåller block som är precis tillräckligt stora för att fylla begäran och en öppen plats returneras. Om inga fria block som är mindre än dubbelt så stora begärda finns tillgängliga, ett större block delas i två för att uppfylla kraven.
Termen "gratis lista" kan hänvisa till antingen en enda länkad lista med minnesadresser, eller den kan hänvisa till en mycket mer komplex typ av datastruktur. Olika typer av sorteringsträd, om de hålls enkla och balanserade, kan hjälpa till att öka hastigheten på att hitta öppna minnesblock på bekostnad av att komplicera källkoden. En länkad lista kan vara långsammare än ett specialiserat sorteringsträd men skapar programmeringskod som är mycket lättare att läsa, felsöka och ändra.
Vissa programmeringsspråk och operativsystem använder sig av en speciell mekanism som kallas soporavfall. Detta är en process som kan hjälpa dig att ta de olika posterna på en gratis lista och konsolidera de fria utrymmena så att de är sammanhängande. effekten av att förhindra fragmentering och möjliggöra att större minnesblock tilldelas.