Nun wir haben jetzt einen kleinen Eindruck bekommen, wie die Lochliste abgespeichert wird und wie da

der Bezug zur lineal überliegenden Adressraumkonzepten eines Betriebssystems letztendlich

aussieht. Jetzt wollen wir uns mal anschauen, wie man denn eigentlich so eine Lochliste verarbeitet,

nach welchen Strategien die Verarbeitung da eigentlich läuft. Also die Verfahrensweisen stehen

jetzt im Vordergrund. Nun zunächst gehen wir mal der Einfachheit halber wirklich nur davon aus,

es ist eine lineare Lochliste, eine dynamische Datenstruktur, eine einfach verkettete Liste.

Da stellt sich dann grundsätzlich erstmal die Frage, wenn man jetzt sozusagen in dieser

Liste nach Löchern sucht, welche Art von Loch möchte man denn haben. Denn es ist so,

dass wenn wir jetzt praktisch einen Speicherbereich einer gewünschten Größe haben,

dann suchen wir nach einem Loch dieser Größe, wo wir mindestens diese Anforderung erfüllen können.

Wir müssen auch davon ausgehen, dass die Löcher, die wir da halt haben, irgendwie alle größer sind,

als das, was gerade angefordert ist. Und es ist die Frage, wie wir denn damit umgehen.

Ob wir dann einfach das gesamte Loch jeweils, das am besten passende Loch in hoch der Form zurückgeben,

oder ob wir aus diesem Loch dann nur diese angeforderte Größe halt herausschneiden und wieder

einen Verschnitt erhalten, den man dann typischerweise wieder neu in so einer Liste einsortieren muss,

wenn die Elemente dieser Liste der Größe nach sortiert sind. Und diese grundsätzliche Sortierungsstrategie

der Größe nach steht jetzt hier mal auf dieser Folie im Vordergrund, wo wir sagen, die Lochliste

ist der Größe nach auf- oder absteigend sortiert. Und da haben wir dann schon zwei unterschiedliche

Techniken. Die eine Technik, best fit, versteht die Lochliste als aufsteigend sortierte Löcher.

Im Endeffekt, und dann versucht man, das kleinste passende Loch zu finden. Man kann davon ausgehen,

dass wenn praktisch in der Liste die Löcher größer werden, dass der Suchaufwand dadurch

minimiert werden soll. Im Endeffekt und zum Teil eben auch der Verschnitt dabei minimiert wird.

Man wird immer das kleinste passende Loch sozusagen finden. Und wenn man da noch was

rausschneiden muss, bleibt etwas kleineres übrig, was denn erneut einzusortieren wäre.

Dieser erneute Einsortierungsvorgang startet dann vorne wieder, wo die kleineren Löcher sind und

wird mit einer gewissen Wahrscheinlichkeit eben auch schnell die Stelle finden, wo denn dieser Rest,

dieses kleinere Restloch denn eigentlich platziert ist. Nun, wenn man aber so eine Liste halt nun hat

nach best fit organisiert und man lässt das System jeweils lang laufen. Dann wird man feststellen,

dass man mit diesem Verfahren typischerweise eher kleinere Löcher hinterlässt, die denn für

jeweils kommende Speicheranforderungen der Prozesse vielleicht ihm dennoch zu klein sind und man

demzufür in der Liste nach hinten gehen muss. Das heißt, der Suchaufwand steigt durchaus bei best fit.

durchaus bei Bestfit. Vorne eher kleinere Löcher hinterlassen. Wir müssen weiter nach hinten in

diese Liste rein und damit haben wir zeitmäßig gesehen einen höheren Aufwand, eine Wartezeit,

wenn man so will, bis man dann halt das passende Loch gefunden hat. Eine andere Rangehensweise ist

Worstfit. Da ist die Liste genau umgekehrt sortiert. Das heißt vorne sind die größeren

Löcher und nach hinten hin wird werden die Löcher dann halt immer kleiner absteigende

Lochgrößen. Man sucht das größte passende Loch im Endeffekt und kriegt natürlich da eine sehr

schnelle Zuteilungsentscheidung. Wenn man jetzt mal annehmen würde, dass diese Speicheranforderung

erfüllbar ist, man einfach das erste Loch dann vorne nimmt, ja, rausschneidet und dann den Rest

natürlich wieder einsortieren muss. Für den Einsortiervorgang möglicherweise man jetzt,

je nachdem wie groß oder klein der Verschnitt ist, man mehr oder weniger viel Zeit benötigt,

bis man denn praktisch in der Liste die entsprechende Position gefunden hat. Wenn

die Speicheranforderung, die wir stellen, einfach zu groß ist, das sieht man dann gleich an der

Größe des ersten Lochs in der Liste, da kann man also ganz schnell auch eine Aussage darüber

treffen, ob diese Anforderung überhaupt erfüllbar ist. Die Situation hier ist, dass wir vorne eher

immer größere Löcher hinterlassen. Wir haben große Löcher, wo wir von der Liste am Anfang damit

starten. Wir hinterlassen durchaus eher größere Löcher, aber es hängt natürlich sehr stark von

den Speicheranforderungen ab, bei mehr oder weniger konstantem Suchaufwand, weil wir nämlich sehr

schnell eben eine Aussage treffen können, ob überhaupt genügend Speicher für diese Anforderung

zur Verfügung steht. Nun aber wichtig ist, in beiden Fällen muss erneut einsortiert werden,