Vorige                       Inhoud                      Volgende
_________________________________________________________________

SASL                    860409          (c) 1986 by ORD-GROUP  49


Het  voornaamste  werk  van de interpreter bestaat er dus  in  om
telkens maar combinatoren in te vullen in een grote samenhangende
meestal  cyclische  graaf.  Verder moet dit  natuurlijk  zo  snel
mogelijk gaan.

De graaf bestaat in het geheugen uit een aantal cellen met onder-
linge pointers.  In extra bits is gecodeerd wat voor type pointer
of cel het is.

Garbage collection
Het beschikbare geheugen wordt opgedeeld in 3 gebieden. Van onder
naar boven zijn dat de celruimte waar alle cellen staan, de vrije
ruimte  en  de stack.  De celruimte groeit naar boven toe  en  de
stack  naar  beneden.  Bij het roeren in de graaf moet de  inter-
preter soms nieuwe cellen aanmaken terwijl sommige cellen achter-
blijven zonder dat een pointer deze aanwijst. Als de bovenste cel
in  het  geheugen in de buurt van de stack komt  moet  er  worden
opgeruimd.  Alle  loze  cellen worden weggehaald en alle  nuttige
cellen  naar onder toe aangeschoven.  Hierdoor ontstaat weer  een
grote ruimte tussen de stack en de bovenste cel en beiden  kunnen
weer groeien. Dit opruimen noemen we garbage collection.

Het  grote  probleem  bij garbage collection is  dat  de  garbage
collector  niet te veel geheugen gebruiken mag want hij wordt pas
aangeroepen als er een tekort aan geheugen is.  Dat betekent  dat
de garbagecollector een van tevoren gestelde (lage) bovengrens op
het geheugengebruik moet hebben.

De  garbage collector zoekt alle pointers op die van buiten in de
graaf  wijzen.  De cellen waar die pointers naar toe wijzen  zijn
in  gebruik  en worden dus gemerkt.  Cellen bevatten pointers  en
alle  cellen  die worden aangewezen door een pointer die  in  een
gemerkte  cel staat zijn ook in gebruik en moeten dus ook  worden
gemerkt. Dit gaat door todat alle bereikbare cellen zijn gemerkt.
De  ongemerkte  cellen zijn onbereikbaar en  dus  nutteloos.  Het
grote  probleem  is nu hoe je alle cellen kunt merken  zonder  te
veel geheugen te gebruiken.  Het merkproces is inherent recursief
en  de garbage collector moet ergens bijhouden welke pointers hij
nog allemaal moet volgen.

De oplossing is als volgt:  De garbage collector heeft een op- en
een  neerpointer.  Als de neerpointer niet naar een cel wijst dan
gaat de garbagecollector terug omhoog langs de oppointer.  Als de
neerpointer  wel naar een cel wijst dan wordt deze  gemerkt.  Als
deze cel een linkerpointer bevat dan wordt op de plaats waar deze
linkerpointer staat de oppointer neergezet, de oppointer wordt de
neerpointer met het merkteken 'links', en de neerpointer wordt de
linkerpointer van de cel.  Het hele proces herhaalt zich dan. Als
de  garbagecollector terug omhoog wil kan het aan  het  merkteken
van  de  oppointer zien op welke plaats in de cel de  vorige  op-
pointer  staat.  Het hele proces wordt herhaald voor de  rechter-
pointer waarna de garbage collector terug omhoog kan gaan.

In  feite  komt  dit erop neer dat je de stack  van  de  garbage
collector in de graaf bijhoudti.p.v. op de CPU stack.

_________________________________________________________________

Vorige                       Inhoud                      Volgende