home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / coders / collector / collector.doc < prev    next >
Text File  |  1995-03-02  |  9KB  |  226 lines
  1.                                  Collector 1.0
  2.  
  3.             Management and Garbage Collection of elemental objects.
  4.  
  5.                      Copyright © 1993-1994 by Lars Düning
  6.                              All rights reserved.
  7.                    Permission granted for non-commercial use.
  8.  
  9.  
  10.  Introduction
  11.  ------------
  12.  
  13. Oberon possesses a feature called 'garbage collection' easening the handling
  14. of free allocated structures. Unfortunately the GC of Oberon has just a
  15. restrained usability because:
  16.  - it doesn't know 'weak pointers' (pointers being too weak to keep an
  17.    element alive)
  18.  - elements are deallocated without notification (no destructor mechanism)
  19.  - it can't be switched off.
  20. Additionally, the incremental garbage collector of Amiga-Oberon adds a
  21. significant overhead to the program.
  22.  
  23. 'Collector' is the attempt to implement a GC on a 'higher level'. Though it
  24. must be operated manually, it can exploit the programmers knowledge about
  25. the program. It also features implicitely 'weak pointers' and destructor
  26. methods. Operation is incremental to scatter the workload more even over
  27. the total run of the program.
  28.  
  29. 'Collector' comes in two flavours: for once 'Collector' itself, using
  30. double-linked lists internally, and then 'CollectorS' using single-linked
  31. lists. The interface to both is (almost) identical.
  32.  
  33. 'Collector' needs a bit more memory and is busier during the usage of
  34. the elements, but is able to do the actual collection more straightforward.
  35. 'CollectorS' needs less memory and usage cycles, but more time for the
  36. collection.
  37.  
  38.  
  39.  Contents
  40.  --------
  41.  
  42. The complete 'Collecter' archive contains these files:
  43.  
  44.   Collector.mod  : the source of Collector
  45.   CollectorS.mod : the source of CollectorS
  46.   Collector.txt  : the 'definition' of Collector(S)
  47.   Mark.inline    : inline source of CollectorS.Mark()
  48.   Check.inline   : inline source of CollectorS.Check()
  49.   CollTest.mod   : a simple test and demonstration program
  50.   CHANGELOG      : what was changed when how by whom
  51.   Collector.dok  : this documentation (german)
  52.   Collector.doc  : this documentation (english)
  53.  
  54. The files should, but needn't be equipped with icons.
  55.  
  56. 'Collector' was developed and tested using Amiga-Oberon 3.11.
  57.  
  58.  
  59.  Installation
  60.  ------------
  61.  
  62. Compile both modules and copy the created binaries into the approbiate
  63. directories.
  64. Both modules may be used with and without the compilers garbagecollection.
  65.  
  66.  
  67.  Usage
  68.  -----
  69.  
  70. To make usage of Collector, the to be managed data structures need to
  71. fullfill three requirements:
  72.  - all structures must be derived of Collector[S].Element.
  73.  - at the runtime of the collector routine all living data must be
  74.    reachable from the 'rootset' data set.
  75.  - in general. no local pointers and elements must be kept over the
  76.    call of the collector routine.
  77.  
  78. The elements managed by Collector are divided into the 'normal' and
  79. the 'root' elements. Root elements are the base of the data web: they
  80. are by definition alive, and server as anchors for the normal elements.
  81. All elements which may be reached starting from a root element are
  82. alive as well, the others are detected by Collector and deallocated.
  83.  
  84. To let an own data structure be managed by Collector, it must inherit
  85. Collector[S].Element, and be registrated with Collector by a call to
  86. .RegisterType(). .RegisterType() gets as most important parameter a
  87. function, which on call returns a freshly allocated element of the
  88. registered structure. Other parameters determine, if the registered
  89. structure is of root type, and how long the list of free elements
  90. may grow.
  91. Result is a type number, which has to be used to request new instances
  92. of the registered type using .New().
  93.  
  94. It is possible to use a data structure as normal as well as root, but
  95. it must be registered twice with the Collector.
  96. If a given structure is root or not is flagged by 'Collector.Root' in
  97. the imported field '.ecFlags'.
  98.  
  99. To each element two functions are bound, which are called by the collector:
  100.  
  101.   mark()
  102.  
  103.     This function is called when the collector acknowledged an element
  104.     as alive. The element now has to mark all from it reachable elements
  105.     using Collector[S].Mark(),
  106.  
  107.  
  108.   free()
  109.  
  110.     The collector decided that this element is dead and would like to
  111.     deallocate it. The element now has the opportunity to perform
  112.     cleanup operations, or to deny the deallocation.
  113.     The result value determines the further action of the collector:
  114.       .keep   : the element stays alive.
  115.       .enlist : the element is freed, but kept in the free list of its
  116.                 type.
  117.       .dispose: the element is deallocated.
  118.  
  119. Note that .free() is called for unreferenced root elements as well - this
  120. way these have the opportunity to commit suicide after long idling.
  121.  
  122. 'Freed' elements are normally not deallocated, but instead kept in a
  123. free list, so that later requests for elements of the same type are
  124. fulfilled quicker.
  125.  
  126. The maximal number of elements in a free list is set at the registration
  127. of the type - but it is possible to deallocate free elements of a certain
  128. age (counted in GC runs) by a call to .ShortenLists().
  129.  
  130. The incremental operation of the GC (if one uses it at all) has the effect
  131. that the type bound function .mark() is not sufficient to mark all
  132. living elements as soon as a new allocated element is assigned to an
  133. already marked element.
  134. Therefore all new references between two elements must be notified to
  135. the collector by calling .Check().
  136.  
  137. The actual garbage collection is done by a call to .GC(). Parameter is
  138. the planned number of calls for one complete collection. Using '1' as
  139. value, a complete collection is enforced (or at least the already begun
  140. collection completed).
  141.  
  142.  
  143. Is CollectorS used, the marking of an element is just the setting of a flag
  144. in the element structure, so that the associated routines are better
  145. programmed 'inline'. Suiting templates are given in the files 'Check.inline'
  146. and 'Mark.inline'.
  147.  
  148.  
  149.  Algorithm
  150.  ---------
  151.  
  152. The gargabe collector is a variant of Dijkstra's Incremental Update Collector,
  153. implement using a description in "Uniprocessor Garbage Collection Techniques".
  154.  
  155. All existing elements are colored with one of three colours:
  156.  
  157.   black: the living, during the GC run already processed elements.
  158.   grey : the living, yet unprocessed elements.
  159.   white: the unprocessed, potentially dead elements.
  160.  
  161. The collector walks through the list of grey elements. For each grey element
  162. all from it reachable elements are colored grey as well, then the element
  163. itself is colored black. Starting from the root elements, which are statically
  164. colored 'grey', all living elements are first colored grey, then black.
  165. If no grey element is left, the current GC run is complete, and all elements
  166. still colored white are dead and therefor deallocatable.
  167.  
  168. Elements allocated during a GC run are colored white, so that elements with
  169. a life span shorter than the GC run may be deallocated already at the end
  170. of the current run.
  171.  
  172. Changes in the relations between elements during a GC run are detected using
  173. a 'write barrier': if an element pointer is assigned to an already blackened
  174. element, the element pointed to is colored grey during the assignment.
  175.  
  176.  
  177. The implementation used in Collector distinguishes root elements from normal
  178. elements to be able to detect unreferenced rootelements. For this a new
  179. color 'dark' is used, marking the processed but unreferenced rootelements.
  180.  
  181. Besides that, all elements are managed in rings, with a separate ring for
  182. each color (in CollectorS the 'white' ring also contains the 'grey' elements).
  183. In Collector these rings are implemented using double linked lists, in
  184. CollectorS by using single linked lists.
  185. This means for Collector, that each recoloring of an element must be
  186. accompained by a transfer of that element into another ring, whereas
  187. CollectorS just has to set a flag. On the other hand this enables Collector
  188. to process each element just once for a complete collection, whereas
  189. CollectorS has to process the 'white' ring several times to detect elements
  190. which were colored grey late.
  191.  
  192.  
  193.  Disclaimer
  194.  ----------
  195.  
  196. It runs on my machine - everything else is beyond my sphere of influence.
  197.  
  198. The module including ideas, algorithms and files is freeware: meant for
  199. the benefit of many, but not for someone making profit (money or glory)
  200. on my expenses. Infringement is a call for trouble.
  201.  
  202. Permission granted for non-commercial use, distribution, replication and
  203. development, as long as the 'meaning' remains the same, every change is
  204. clearly documented, and all files are included in the package
  205.  
  206. Distribution as part of commercial software libraries is permitted, as long
  207. as the package is just 'one among many'.
  208.  
  209.  
  210.  Participants
  211.  ------------
  212.  
  213. Lars Düning; Am Wendenwehr 25; D-38114 Braunschweig; Germany
  214.   duening@ibr.cs.tu-bs.de
  215.  
  216.  
  217.  Literature
  218.  ----------
  219.  
  220. Paul R. Wilson: Uniprocessor Garbage Collection Techniques
  221.   1992 International Workshop on Memory Management
  222.   Springer-Verlag, Lecture Notes
  223.  
  224. "Das Konzept ist einfach erstaunlich. Sinnlos, aber erstaunlich."
  225.   (Der Doktor)
  226.