INF1070 - V?r 2005

Dynamisk allokering

Dynamisk allokering er ? ha et minneomr?de (kalt en haug eller ?heap? p? engelsk) hvor brukeren kan reservere et omr?de (kalt en blokk) med et kall p? malloc eller tilsvarende og siden frigj?res med et kall p? free eller tilsvarende.

Implementasjon

Det er flere m?ter ? implementere dynamisk allokering p?. Den enkleste er ? tenke seg haugen som en liste av blokker der hver blokk angir hvor stor den er og om den er i bruk.

Hver blokk best?r av to deler:

  1. Hodet er her p? 1 byte og angir hvor stor blokken er. (Etter hodet kommer 1 byte som aldri brukes for at datafeltet skal starte p? en partallsadresse.)

    Hvis vi alltid lar blokkene best? at et partall byte, trenger vi ikke det siste bit-et i lengdeangivelsen (siden det alltid vil v?re 0). Derfor kan vi bruke dette bit-et til ? angi om en blokk er ledig eller ikke: 0 er ledig mens 1 er opptatt.

  2. Datafeltet er der brukeren kan legge sine data. 

  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 7 |   |XXX|XXX|XXX|XXX| 4 |   |ooo|ooo| 5 |   |XXX|XXX| 1 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Haugen over best?r av fire blokker:
  1. En opptatt blokk p? 6 byte (hvorav 4 med data).
  2. En ledig blokk p? 4 byte (med plass til 2 byte med data).
  3. En opptatt blokk p? 4 byte (hvorav 2 med data).
  4. En jukseblokk med lengde 0 for ? angi slutten p? listen. (Den er markert som opptatt s? den aldri blir sl?tt sammen med blokken f?r.)
Hodet er skjult for brukeren; det brukes kun av allokeringsrutinene. For eksempel, da brukeren ba om 4 byte, ble det reservert en blokk p? 6 byte (inkludert 2 byte for hodet) som startet i indeks 0. Brukeren fikk imidlertid svar fra allokeringsrutinen om at hans eller hennes tilgjengelige adresseomr?de startet fra indeks 2.

Allokering

N?r brukeren ber om et visst antall byte, vil allokeringsrutinen (malloc eller tilsvarende) g? gjennom listen til den finner en ledig blokk som er stor nok. Hvis blokken er for stor, blir den delt i to. S? blir blokken markert som opptatt og brukeren f?r beskjed om hvor han eller hun kan legge sine data.

Deallokering

N?r en blokk kan frigj?res, blir den ganske enkelt markert som ledig. For ? unng? fragmertering i mange sm? blokker, blir blokken sl?tt sammen med den foreg?ende i listen om den ogs? er ledig, eller med den etterf?lgende om den er ledig. Noen ganger kan den bli sl?tt sammen med b?de den foreg?ende og den etterf?lgende.

Et eksempel

Initielt ser haugen slik ut: 
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 14|   |ooo|ooo|ooo|ooo|ooo|ooo|ooo|ooo|ooo|ooo|ooo|ooo| 1 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Det best?r av en ledig blokk p? 14 byte (hvorav 12 kan brukes til data) og jukseblokken p? 0 byte som avslutning.

Allokering av 2 byte

For ? etterkomme et ?nske om 2 byte, blir blokken p? 14 byte delt i to: en p? 10 byte og en p? 4 byte. 
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 10|   |ooo|ooo|ooo|ooo|ooo|ooo|ooo|ooo| 5 |   |XXX|XXX| 1 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Brukeren f?r beskjed om at han eller hun kan bruke fra indeks 12.

Allokering av 2 byte

S? allokeres 4 byte til og blokken med 10 byte m? deles igjen. 
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 6 |   |ooo|ooo|ooo|ooo| 5 |   |XXX|XXX| 5 |   |XXX|XXX| 1 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Brukeren f?r tildelt indeks 8 (og 9).

Allokering av 3 byte

Et ?nske om 3 byte gj?r det settes av 4 byte siden det alltid skal allokeres et partall byte. Den siste ledige blokken tas i bruk. 
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 7 |   |XXX|XXX|XXX|XXX| 5 |   |XXX|XXX| 5 |   |XXX|XXX| 1 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Indeksene 2–4 er n? tilgjengelig for brukeren.

Frigj?ring av blokken 6

S? kan blokk nr 2 med indeks 6 frigj?res – det som sett fra brukerens side har indeks 8. Det markeres som ledig, men kan ikke sl?s sammen med noen av naboene. 
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| 7 |   |XXX|XXX|XXX|XXX| 4 |   |ooo|ooo| 5 |   |XXX|XXX| 1 |   |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Et eksempel i C

Her er et C-program som implementerer dynamisk allokering ved to funksjoner mgrab og mdrop som bruker lister slik det er beskrevet. I tillegg skriver det ut en oversikt over hvorledes minneomr?det ser ut etter hver operasjon; resultatet ser slik ut.