Hög (minne)

En heap ( eng.  heap ) inom datavetenskap och programmering  är namnet på en datastruktur som implementerar dynamiskt allokerat applikationsminne.

Högstorlek  - mängden minne som tilldelats av operativsystemet (OS) för att lagra högen (under högen).

Hur det fungerar

När en process startar allokerar operativsystemet minne för att rymma högen. I framtiden kan minnet för högen (under högen) allokeras dynamiskt.

Användarprogrammet, med hjälp av funktioner som , kan få pekare till minnesområden som hör till högen. Program använder högen för att vara värd för dynamiskt skapade datastrukturer. Programmet kan frigöra minne med funktioner som . malloc()free()

Högminne kan delas in i använt (tilldelat till ett program som använder eller liknande funktioner) och ledigt (ännu ej upptaget eller redan frigjort med eller liknande funktioner). malloc()free()

För att lagra information om vilken del av högen som är upptagen och vilken som är ledig, används vanligtvis ett extra minnesområde.

Innan programmet startar initieras högen, under vilken minnet som tilldelats för högen markeras som ledigt.

En funktion som denna gör ungefär så här: malloc()

• tittar igenom listan över använda/fria minnesområden som är tilldelade på högen, letar efter ett ledigt område av lämplig storlek;
• i händelse av brist på ledigt minne kan den begära ytterligare minne från operativsystemet;
• lägger till det hittade området till listan över ockuperade områden (eller markerar området som ockuperat);
• returnerar en pekare till början av minnesområdet;
• om det av en eller annan anledning inte var möjligt att allokera minne, rapporterar ett fel (till exempel returnerar ).malloc()NULL

En funktion som denna gör ungefär så här: free()

• tittar igenom listan över upptagna/fria minnesområden som tilldelats på högen, letar efter det angivna området;
• tar bort det hittade området från listan över upptagna minnesområden;
• lägger till det hittade området till listan över lediga områden (eller markerar området som ledigt).

Programmet kan vara säker på att mellan anrop till funktioner som och , kommer minnesområdet markerat som upptaget inte att omallokeras. Efter ett samtal eller liknande funktion kommer minnesområdet att frigöras och kan senare återanvändas eller ges till OS. Om du använder en pekare till ett frigjort minnesområde kommer programmet att krascha eller köras oförutsägbart. malloc()free()free()

Algoritmer och prestanda

Högen är ett sammanhängande minnesområde uppdelat i ockuperade och fria områden (block) av olika storlekar.

Information om lediga och upptagna områden på högen kan lagras i listor med olika format. Prestanda för funktioner som och beror direkt på det valda listformatet , eftersom dessa funktioner tillbringar större delen av sin tid med att söka i listan över lämpliga områden. malloc()free()

Använd ett systemanrop för att öka storleken på heapen och liknande funktioner (ringa en OS-funktion). I det här fallet sker en kontextväxling från användarutrymme till OS-kärnutrymme och vice versa. Att söka i listan över använda/fria högområden är snabbare än kontextbyte, så det är mer lönsamt att använda ett systemanrop en gång för att allokera ett stort minnesområde för högen, och sedan allokera mindre områden till programmet från det befintliga stora området medan upprätthålla en lista över använda/fria områden. malloc()

Antalet element som ingår i listan över ockuperade/fria högområden kan minskas genom att slå samman element som innehåller information om successiva områden. Detta kommer att minska listans genomgångstid.

Varje element i listan kan lagra adressen till ett minnesområde, dess storlek, information om nästa (för sökning framåt) och/eller föregående (för sökning bakåt).

Implementeringsexempel

Skapa flera listor för att lagra information om områden av samma eller liknande storlek. Listval baserat på områdesstorlek.

Se även

• dynamiskt minne
• NULL

• malloc()
• fri()