Vad är en gratis lista?
En fri lista är en datastruktur som innehåller adresserna för datorminnesplatser som är tillgängliga för användning av ett löpande program när du använder dynamisk minnesallokering. Listan blir nödvändig när ett program måste tilldelautrymme 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 somett sortträd. De flesta datorprogrammeringsspråk på hög nivå hanterar automatiskt den fria listan och tar bort behovet av manuell hantering.
När ett program kräver utrymme för att lagra information under programutförande, detMåste begära en viss mängd minne från det underliggande operativsystemet. Platserna för minnesblock som kan användas lagras i gratislistan. För att tilldelningen ska lyckas, mängden begärda minnemåste vara tillgänglig i ett eller flera av dessa block. När en pekare till en lämplig minneslokation returneras, det elementet i listan tas bort.
När ett program har gjorts med minnet kan det avvisa det. Detta innebär att du skickar pekaren till minnetBlockera tillbaka till den fria listan, där den kommer att bli tillgänglig nästa gång en tilldelning försöks. Det är möjligt för minnesallokering att misslyckas eftersom listan är tom eller för att det inte finns några tillgängliga minnesblock som är tillräckligt stora för att uppfyllaprogrammets begäran.
Den enklaste formen av minneshantering kallas First Fit -systemet. Detta system har en enda lista över gratis minnesplatser. När en begäran om minne skickas,Listan är korsad och det första blocket som är tillräckligt stort returneras. Om blocket är mer än dubbelt så mycket som den begärda storleken, halveras den och den oanvända halvan läggs tillbaka till listan. Denna metod handlar enkel kodning för risken att ha fragmenterat minneOmråden som aldrig kan återlämnas till listan.
En annan form av minneshantering kallas Buddy Allocation System. Till skillnad från det första passningssystemet håller Buddy Allocation flera gratis listor, var och en som hållerÖppna block av endast en viss storlek. Detta innebär att när en tilldelningsbegäran tas emot, returneras listan som innehåller block som bara är tillräckligt stora för att fylla begäran och en öppen plats returneras. Om nejGratis block som är mindre än dubbelt så mycket som begärs är tillgängliga, ett större block delas upp i två för att uppfylla kraven.
Termen Free List kan hänvisa till antingen en enda länkad lista över minnesadresser,eller det kan hänvisa till en mycket mer komplex typ av datastruktur. Olika typer av sorteringsträd, om de hålls enkla och balanserade, kan bidra till att öka hastigheten för att hitta öppna minnesblock på bekostnad av kompliceringkällkoden. En länkad lista kan vara långsammare än ett specialiserat sortträd men skapar programmering kod som är mycket lättare att läsa, felsöka och ändra.
Vissa programmeringsspråk och operativsystem använder en speciell mekanism som kallas skräpsamling. Detta är en process som kan hjälpa till att ta de olika posterna på enGratis lista och konsolidera de fria utrymmena så att de är sammanhängande. Detta har effekten av att förhindra fragmentering och möjliggöra större minnesblock.