| |
– 15 –
werden. In Bakers Algorithmus werden beim Anlegen eines Objekts zusätzlich maximal
k Zellen gescannt, um den Collecting-Prozess weiterzuführen und sicherzustellen, dass
der Mutator nicht verhungert (Starving). Sofern genügend Speic her für das neue Objekt
vorhanden ist, wird der Zeiger T um n verringert und anschließend zurückgegeben.
Die Read-Barrier setzt nur beim lesenden Zugriff auf Objekte (Read) ein, wobei Baker
eine feingranulare Barriere einsetzt, die jeweils nur ein Objekt kopieren kann. Die Bar-
riere verhindert zwar, dass der Mutator Zugang zu weißen Objekten (in Fromspace) hat,
erlaubt aber den Zugriff auf graue Objekte. Die Read-Barrier kann entweder durch zu-
sätzliche Befehle im kompilierten Code in Software oder durch spezielle Hardware-
Checks bzw. Mikrocoderoutinen implementiert werden. Auf konventionellen Maschi-
nen verursacht die Read-Barrier hohe Kosten, weil bei jedem Laden eines Zeigers ge-
prüft werden muss, ob der Zeiger noch im Fromspace ist und kopiert werden muss. Da-
gegen bieten Lisp-Maschinen eine spezielle Hardwareunterstützung zur Erkennung der
Zeiger in Fromspace, was die Prüfung der Zeiger deutlich schneller macht [Wi94]. Eine
Schranke für Realzeitanwendungen kann von Bakers Algorithmus nicht garantiert wer-
den, da beispielsweise bei der Allokation neuer Objekte das Root Set nach einem Aufruf
der flip()-Funktion kopiert wird und vorher nicht bestimmbar ist, wie viele Elemente
darin enthalten sind. Das Problem, dass die Kosten für den Kopiervorgang von
Fromspace nach Tospace von der Objektgröße abhängen und deshalb ebenfalls nicht
vorhersagbar sind, lässt sich mittels sogenannten Lazy Copying lösen, bei dem große
Objekte nicht sofort vollständig nach Tospace kopiert werden sondern dort zuerst nur
Platz für sie reserviert wird und ein rückwärtiger Zeiger auf die Fromspace-Adresse
verweist [Jo96]. Die ersten Implementierungen von Bakers Algorithmus war selbst auf
Lisp-Maschinen so ineffizient, dass Benutzer damit nicht vernünftig arbeiten konnten
[Ap88]. Das erklärt, dass in vielen Variationen von Bakers Algorithmus versucht wird,
die Unterbrechungen vorhersagbarer und die Read-Barrier kostengünstiger zu gestalten,
wie z.B. von Brooks [Bro84]. Ein weiterer Ansatzpunkt ist, die Allokation neuer Objek-
te weniger konservativ vorzunehmen. So versucht Dawson [Da92] beispielsweise, neue
Objekte so oft wie möglich weiß zu färben, anstatt alle direkt schwarz anzulegen.
3.2.3
Appel-Ellis-Li Collector
Auch der Appel-Ellis-Li Collector basiert auf Bakers Algorithmus, jedoch bringen ver-
schiedene Änderungen entscheidende Effizienzvorteile. Erstens ist der Algorithmus im
Gegensatz zu Bakers für konkurrentes Arbeiten von Mutator und Collector ausgelegt.
Zweitens nutzt der Algorithmus, der sowohl für Uniprozessor- als auch für Multiprozes-
sormaschinen mit geteiltem Speicher konzipiert ist, Hardwareunterstützung für virtue l-
len Speicher, um Referenzen auf Fromspace zu erkennen [Ap88]. Drittens wird eine
|  |
|
| |
|
|
