> For the complete documentation index, see [llms.txt](https://prof.aheil.de/os/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://prof.aheil.de/os/fortgeschrittene-speichervewaltung/exkurs-free-list.md).

# Exkurs: Free List

* Bisher galt die Annahme, das alle Adressräume gleich sind
* Somit muss man »eigentlich nur« die nächste freie Lücke finden und »auffüllen«
* Segmentierung führt nun jedoch zur Fragmentierung (engl. external fragmentation)
* Innerhalb eines Adressraus spricht man ebenfalls von Fragmentierung (engl. internal fragmentation)

Beispiel: Heap

<br>

<figure><img src="/files/UCIi6kGgDroj0pXUPkhD" alt=""><figcaption></figcaption></figure>

* Eine Datenstruktur zur Verwaltung freier Speicherbereiche ist die sog. Free List
* Basiert auf einer verketteten Liste (engl. linked list)

<figure><img src="/files/IySRQkEBs9tuLdCxUHqu" alt=""><figcaption></figcaption></figure>

## Free List Beispiele![](/files/rNDh5CpaPwiOcRLlVZRM)

* Anfragen für größer 10 Bytes schlagen fehl (liefert NULL)
* Exakt 10 Bytes kann durch einen der beiden Blöcke bedient werden
* Aber was passiert, wenn nur 1 Byte angefordert wird?

<figure><img src="/files/4bXh7Ebt762YEf4wUAFy" alt=""><figcaption></figcaption></figure>

* Einer der freien Blöcke wird verkleinert…<br>

<figure><img src="/files/6FKbTmaEkSxWiqYvJQy0" alt=""><figcaption></figcaption></figure>

* Zurück zur Ausgangssituation mit drei Blöcken…
* Was passiert wenn der mittlere Block freigegeben wird?
* Es entstehen drei Blöcke… keine Gute Idee…<br>

<figure><img src="/files/qDQ8VLDpfyQprXXxAbU0" alt=""><figcaption></figcaption></figure>

* Daher fasst die zuständige Bibliothek den freien Speicher vor dem Allokieren so gut wie möglich zusammen<br>

<figure><img src="/files/qQkxBZ9WG5dIOgjEzzN0" alt=""><figcaption></figcaption></figure>