Wat is een gratis lijst?
Een vrije lijst is een gegevensstructuur die de adressen bevat van computergeheugenlocaties die beschikbaar zijn voor gebruik door een actief programma bij gebruik van dynamische geheugentoewijzing. De lijst wordt nodig wanneer een programma ruimte moet toewijzen uit een gebied met vrij geheugen dat de heap wordt genoemd. De implementatie van een vrije lijst kan een eenvoudige gekoppelde lijst zijn of een complexere gegevensstructuur, zoals een De meeste computerprogrammeertalen op hoog niveau verwerken automatisch de vrije lijst, waardoor handmatig beheer overbodig wordt.
Wanneer een programma ruimte nodig heeft om informatie op te slaan tijdens de uitvoering van het programma, moet het een specifieke hoeveelheid geheugen opvragen van het onderliggende besturingssysteem. De locaties van geheugenblokken die kunnen worden gebruikt, worden opgeslagen in de vrije lijst. Om de toewijzing te laten slagen, moet de hoeveelheid gevraagd geheugen beschikbaar zijn in een of meer van deze blokken. Wanneer een pointer naar een geschikte geheugenlocatie wordt geretourneerd, dat element van de lijst is verwijderd.
Nadat een programma klaar is met gebruik van het geheugen, kan het de toewijzing ongedaan maken. Dit houdt in dat de aanwijzer naar het geheugenblok wordt teruggeleid naar de vrije lijst, waar het beschikbaar komt de volgende keer dat een toewijzing Het is mogelijk dat geheugentoewijzing mislukt omdat de lijst leeg is of omdat er geen geheugenblokken beschikbaar zijn die groot genoeg zijn om aan het verzoek van het programma te voldoen.
De eenvoudigste vorm van geheugenbeheer wordt het first-fit-systeem genoemd. Dit systeem onderhoudt een enkele lijst met vrije geheugenlocaties. Wanneer een verzoek om geheugen wordt verzonden, wordt de lijst doorlopen en het eerste blok dat groot genoeg is, wordt geretourneerd. Als het blok meer dan twee keer de gevraagde grootte heeft, wordt het gehalveerd en wordt de ongebruikte helft weer aan de lijst toegevoegd. Deze methode ruilt eenvoudige codering voor het risico van gefragmenteerde geheugengebieden die misschien nooit meer in de lijst worden opgenomen.
Een andere vorm van geheugenbeheer wordt het buddy-allocatiesysteem genoemd. Anders dan het first-fit-systeem houdt buddy-allocatie verschillende vrije lijsten bij, die elk open blokken van slechts één bepaalde grootte bevatten. wanneer een toewijzingsverzoek wordt ontvangen, wordt de lijst geraadpleegd met blokken die net groot genoeg zijn om aan het verzoek te voldoen en wordt een open locatie geretourneerd. Als er geen vrije blokken zijn die kleiner zijn dan tweemaal gevraagd zijn beschikbaar, wordt een groter blok in tweeën gesplitst om aan de vereisten te voldoen.
De term 'vrije lijst' kan verwijzen naar een enkele gekoppelde lijst met geheugenadressen of kan verwijzen naar een veel complexer type gegevensstructuur. Verschillende soorten sorteerbomen, indien eenvoudig en evenwichtig gehouden, kan helpen de snelheid van het vinden van open geheugenblokken te verhogen ten koste van het compliceren van de broncode. Een gekoppelde lijst kan langzamer zijn dan een gespecialiseerde sorteerboom maar creëert programmeercode die veel gemakkelijker te lezen is, debuggen en wijzigen.
Sommige programmeertalen en besturingssystemen maken gebruik van een speciaal mechanisme genaamd garbage collection. Dit is een proces dat kan helpen om de verschillende items op een vrije lijst te nemen en de vrije ruimtes te consolideren zodat ze aaneengesloten zijn. het effect van het voorkomen van fragmentatie en waardoor grotere blokken geheugen kunnen worden toegewezen.