# 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="https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2FbCrNNpJ3JJU9iWv5uuwJ%2Fos.11.heap.de.png?alt=media&#x26;token=393e2e7d-53c2-4114-a036-a0e122db6781" 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="https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2F8vSdLqblmyJyhgtpvyOx%2Fos.11.freelist.de.png?alt=media&#x26;token=0c69d9a9-c4a0-4dbc-8ffc-555d2927968e" alt=""><figcaption></figcaption></figure>

## Free List Beispiele![](https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2FHpnpVixA1TAu6SmaA3ZX%2Fos.11.freelist_example.de.png?alt=media\&token=cbf2a93b-1c36-442f-91d8-63528a2aa07a)

* 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="https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2FNTsZyhwMb0MCLgZVgWsJ%2Fos.11.freelist_example.de.png?alt=media&#x26;token=d538097a-22d1-41d8-a6d0-571a0c33abd6" alt=""><figcaption></figcaption></figure>

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

<figure><img src="https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2FlGDy0YuZbvpNE6g7xsMu%2Fos.11.freelist_example_2.de.png?alt=media&#x26;token=85025ba6-cdd3-4923-9d1d-e10549b21584" 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="https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2FiaDQDsSFdMRHIMvLvxgN%2Fos.11.freelist_example_3.de.png?alt=media&#x26;token=470856ad-40bc-41b2-83ef-a644cc250ff3" 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="https://468234129-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F26UMH8aq11ryvyyIwN0H%2Fuploads%2FNX3swg2lSiWGLEzCCRwk%2Fos.11.freelist_example_4.de.png?alt=media&#x26;token=184d22ee-88c0-48c7-b981-109f30c2817a" alt=""><figcaption></figcaption></figure>