home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / coders / collector / collector.dok < prev    next >
Text File  |  1995-03-02  |  10KB  |  245 lines
  1.                                  Collector 1.0
  2.  
  3.              Verwaltung und Garbage-Collection elementarer Objekte
  4.  
  5.                      Copyright © 1993-1994 by Lars Düning
  6.                             Alle Rechte vorbehalten.
  7.                      Nichtkommerzielle Nutzung gestattet.
  8.  
  9.  
  10.  Einführung
  11.  ----------
  12.  
  13. Oberon besitzt bekanntermaßen eine NÜtzlichkeit genannt "Garbagecollector",
  14. die das Handling mit frei allokierten Strukturen stark vereinfacht und
  15. sicherer macht. Leider ist in Oberon der GC in seiner NÜtzlichkeit doch
  16. eingeschränkt, denn
  17.  - er kennt keine 'Weak Pointer' (Zeiger, die zu schwach sind, ein Element
  18.    am Leben zu erhalten)
  19.  - Strukturen werden ohne Notifikation deallokiert (kein Destruktor-
  20.    Mechanismus)
  21.  - man kann ihn nicht abschalten.
  22. In Amiga-Oberon kommt zudem der zeitliche Overhead für den inkrementellen
  23. Garbagecollector hinzu.
  24.  
  25. 'Collector' ist nun ein "higher level" Ansatz eines GC, der zwar manuell
  26. bedient werden muß, aber dafür Wissen des Programmierers über das Programm
  27. ausnutzen kann. Er bietet zudem implizit 'Weak Pointer' und Destruktor-
  28. methoden für die Objekte. Er arbeitet inkrementell, da so die Arbeitslast
  29. gleichmäßiger auf die gesamte Programmlaufzeit verteilt wird.
  30.  
  31. 'Collector' existiert in zwei Varianten: einmal 'Collector' selber, der
  32. intern mit doppelt-verketteten Listen arbeitet, und 'CollectorS', der
  33. mit nur einfach-verketteten Listen operiert. Das Interface zu beiden
  34. ist (fast) völlig identisch.
  35.  
  36. 'Collector' benötigt neben etwas mehr Speicher mehr Aufwand während der
  37. Verwendung der Objekte, kann dafür aber die eigentliche Collection
  38. zielstrebiger durchführen.
  39. 'CollectorS' dagegen benÖtigt weniger Speicher und Verwendungsoverhead,
  40. benötigt aber mehr Zeit für eine Collection.
  41.  
  42.  
  43.  Paketumfang
  44.  -----------
  45.  
  46. Das komplette 'Collector'-Archiv enthält folgende Dateien:
  47.  
  48.   Collector.mod  : der Quellcode von Collector
  49.   CollectorS.mod : der QuellCode vom CollectorS
  50.   Collector.txt  : das 'Definitionsmodul' von Collector(S)
  51.   Mark.inline    : Inlinetext von CollectorS.Mark()
  52.   Check.inline   : Inlinetext von CollectorS.Check()
  53.   CollTest.mod   : ein simples Test- und Beispielprogramm
  54.   CHANGELOG      : was sich wann warum änderte
  55.   Collector.dok  : diese Dokumentation (Deutsch)
  56.   Collector.doc  : diese Dokumentation (Englisch)
  57.  
  58. Die Dateien sollten, müssen aber nicht unbedingt mit Icons versehen sein.
  59.  
  60. Entwickelt und getestet wurde 'Collector' unter Amiga-Oberon 3.11.
  61.  
  62.  
  63.  Installation
  64.  ------------
  65.  
  66. Zur Installation mÜssen beide Module schlicht compiliert und die erzeugten
  67. Dateien in die passenden Directories kopiert werden.
  68. Beide Module können mit und ohne Garbagecollection compiliert werden.
  69.  
  70.  
  71.   Benutzung
  72.   ---------
  73.  
  74. Zur Benutzung von Collector müssen die zu verwaltenden Datenstrukturen
  75. drei Rahmenbedingungen erfüllen:
  76.  - alle Strukturen müssen von Collector[S].Element abgeleitet werden
  77.  - die lebenden Daten müssen sich zur Laufzeit der Collectionroutine
  78.    vollständig aus der "rootset" Teilmenge erreichen lassen.
  79.  - es dürfen idR keine lokalen Zeiger auf Elemente über den Aufruf der
  80.    GC-Routine hinweg verwendet werden.
  81.  
  82. Die vom Collector verwalteten Elementen teilen sich in die 'normalen'
  83. und die 'Root'elemente. Rootelemente sind die Basiselemente des
  84. Datengeflechts: sie sind per definition lebendig, und dienen als Anker
  85. für die normalen Elemente. Alle Elemente, die sich von den Rootelementen
  86. aus erreichen lassen, gelten ebenfalls als lebend, die anderen werden
  87. vom Collector erkannt und deallokiert.
  88.  
  89. Um eine eigene Datenstruktur vom Collector verwalten zu lassen, muß sie
  90. von Collector[S].Element abgeleitet werden, und dem Collector mit
  91. .RegisterType() mitgeteilt werden. .RegisterType() erhält als primären
  92. Parameter eine Funktion, die bei Aufruf eine frisch allokierte
  93. Datenstruktur zurückliefert, sowie die Angabe, ob es sich um eine Root-
  94. datenstruktur handelt, und wie lang die Freeliste werden darf.
  95. Resultat von RegisterType() ist eine Typnummer, die verwendet werden
  96. muß, um vom Collector neue Instanzen dieser Datenstruktur mittels
  97. .New() anzufordern.
  98.  
  99. Es ist möglich, eine Datenstruktur sowohl normal als auch als Root zu
  100. verwenden, muß sie dafür aber zweimal beim Collector registrieren.
  101. Ob eine reale Datenstruktur dann Root oder nicht ist, läßt sich am
  102. Flag 'Collector.Root' im importierten Feld '.ecFlags' feststellen.
  103.  
  104. An ein Element sind zwei Funktionen gebunden, die vom Collector aufgerufen
  105. werden:
  106.  
  107.   mark()
  108.  
  109.     Diese Funktion wird aufgerufen, wenn der Collector ein Element als
  110.     lebendig erkannt hat, damit dieses Element die von ihm aus
  111.     erreichbaren Elemente mit Collector(S).Mark() markiert.
  112.  
  113.  
  114.   free()
  115.  
  116.     Der Collector hat dieses Element als 'nicht lebendig' erkannt und
  117.     möchte es deallokieren. Das Element hat die Möglichkeit, Aufräum-
  118.     arbeiten zu erledigen, oder eine Deallokation zu verweigern.
  119.     Der Resultatwert bestimmt die Aktion des Collectors:
  120.       .keep   : das Element bleibt weiter lebendig.
  121.       .enlist : das Element wird freigegeben, aber in seiner Freelist
  122.                 gehalten.
  123.       .dispose: das Element wird freigegeben.
  124.  
  125. Zu beachten ist, daß .free() auch für nicht-referenzierte Rootelemente
  126. aufgerufen wird - diese haben so die Gelegenheit, sich nach langer
  127. Nichtbenutzung selbst aus dem Speicher zu entfernen.
  128.  
  129. Zurückgegebene Elemente werden in der Regel nicht sofort deallokiert,
  130. sondern zunächst in einer Freelist zwischengespeichert, so daß nachfolgende
  131. Anforderungen von Elementen selben Typs schneller erledigt werden können.
  132.  
  133. Die maximale Anzahl von Elementen in einer Freelist wird bei der
  134. Registrierung eines Typs festgelegt - zwischenzeitlich lassen sich Elemente
  135. eines gewissen Alters (gemessen in GC-Läufen) mit ShortenLists() aus
  136. den Freelists freigeben.
  137.  
  138. Die inkrementelle Arbeitsweise des GC (sofern man sie ausnutzt) hat zur
  139. Folge, daß die typgebundene Funktion .mark() nicht zur vollständigen
  140. Markierung aller lebenden Elemente ausreicht - sobald neu allokierte
  141. Elemente an bereits bearbeitete Elemente zugewiesen werden.
  142. Daher muß generell bei jeder neuen Referenzierung eines Elementes
  143. der Collector mit Check() informiert werden.
  144.  
  145. Die eigentliche Garbagecollection wird durch den Aufruf der Funktion GC()
  146. ausgeführt. Parameter ist die Anzahl der geplanten Aufrufe, die zur
  147. Vervollständigung der GC nötig sein sollen. Gibt man hier '1' als Wert an,
  148. wird eine vollständige GC erzwungen (bzw. die soweit angefangene GC
  149. vervollständigt).
  150.  
  151.  
  152. Verwendet man CollectorS, beschränkt sich die 'Markierung' eines Elementes
  153. lediglich auf das Setzen eines Flags in der Elementstruktur, so daß
  154. die entsprechenden Routinen besser 'inline' programmiert werden (passende
  155. Templates sind in den Files 'Check.inline' and 'Mark.inline').
  156.  
  157.  
  158.  Algorithmus
  159.  -----------
  160.  
  161. Der Garbagecollector ist eine Variante von Dijkstra's Incremental Update
  162. Collector, implementiert nach einer Beschreibung in "Uniprocessor
  163. Garbage Collection Techniques".
  164.  
  165. Die existierenden Elemente werden mit einer von drei Farben gekennzeichnet:
  166.  
  167.   schwarz: die lebenden, in diesem GC-Lauf bereits vom GC bearbeiteten
  168.            Elemente.
  169.   grau   : die lebenden, noch nicht bearbeiteten Elemente.
  170.   weiß   : die potentiell toten, noch nicht bearbeiteten Elemente.
  171.  
  172. Der Collector arbeitet sich durch die Liste der grauen Elemente.
  173. Bei jedem grauen Element werden die von diesem aus erreichbaren Elemente
  174. ebenfalls grau markiert, das bearbeitete Element dann schwarz gefärbt.
  175. Ausgehend von den Root-Elementen, die statisch 'grau' markiert werden,
  176. werden so nach und nach alle lebenden Elemente erst grau, dann schwarz
  177. markiert. Ist kein graues Element mehr vorhanden, ist der aktuelle GC-Lauf
  178. vollständig, und die jetzt weißen Elemente sind als 'tot' deallokierbar.
  179.  
  180. Während des GC-Laufs allokierte neue Elemente werden zunächst weiß gefärbt,
  181. so daß nur kurzzeitig lebende Elemente möglichst schnell wieder freigegeben
  182. werden können.
  183.  
  184. Änderungen in den Beziehungen zwischen den Elementen während des GC-Laufs
  185. werden durch eine 'Write Barrier' abgefangen: wird ein Elementzeiger einem
  186. bereits geschwärztem Element zugewiesen, wird das referenzierte Element
  187. ebenfalls grau gefärbt.
  188.  
  189.  
  190. Die in Collector verwendete Implementation trennt Rootelemente scharf von
  191. normalen Elementen, um den Fall von nicht direkt referenzierten Rootelementen
  192. erkennen zu können. Dazu wird neben den zusätzlichen Listen für die
  193. Rootelemente eine weitere Schattierung 'dunkel' verwendet, die die vom
  194. GC bereits bearbeiteten, aber nicht direkt referenzierten Rootelemente
  195. kennzeichnet.
  196.  
  197. Ansonsten werden die Elemente in Ringlisten verwaltet, wobei jeder Farbe
  198. ein Ring entspricht (in CollectorS enthält die 'weisse' Liste auch die
  199. grauen Elemente). In Collector werden diese Listen durch doppelte Verkettung
  200. realisiert, in CollectorS nur durch einfache Verkettung.
  201. Als Folge bedeutet für Collector jede Umfärbung eines Elementes, daß das
  202. Element seinen Ring wechselt, während in CollectorS lediglich ein Flag
  203. gesetzt werden muß. Dafür muß Collector für eine vollständige GC jedes
  204. Element nur einmal abarbeiten, während CollectorS mehrere Durchläufe durch
  205. die 'weiße' Liste benötigt, um nachträglich grau markierte Elemente zu
  206. finden.
  207.  
  208.  
  209.  Disclaimer
  210.  ----------
  211.  
  212. Es funktioniert auf meinem Rechner - alles andere ist ausserhalb meines
  213. Einflußbereiches.
  214.  
  215. Das Modul samt Ideen, Algorithmen und Dateien ist Freeware: gedacht zum
  216. Nutzen vieler, aber nicht damit es jemand dazu benutzt, auf meine
  217. Kosten Geld und/oder Ruhm zu ernten. Wenn es dennoch jemand tut, gibt's
  218. Ärger.
  219.  
  220. Die nichtkommerzielle Verwendung, Vertrieb, Vervielfältigung und
  221. Weiterentwicklung von Programm und Dokumentation ist gestattet, solange
  222. der Wesensgehalt ungeändert bleibt, jede Änderung rekonstrierbar
  223. dokumentiert wird, und das Paket stets alle Dateien enthält.
  224.  
  225. Der Vetrieb in kommerziellen Softwaresammlungen ist gestattet, wenn
  226. innerhalb der Sammlung das Paket lediglich 'eines unter vielen' ist.
  227.  
  228.  
  229.  Mitwirkende
  230.  -----------
  231.  
  232. Lars Düning; Am Wendenwehr 25; D-38114 Braunschweig; Germany
  233.   duening@ibr.cs.tu-bs.de
  234.  
  235.  
  236.  Literaturtip
  237.  ------------
  238.  
  239. Paul R. Wilson: Uniprocessor Garbage Collection Techniques
  240.   1992 International Workshop on Memory Management
  241.   Springer-Verlag, Lecture Notes
  242.  
  243. "The concept is simply staggering. Pointless, but staggering."
  244.   (The Doctor)
  245.