home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 8 / FreshFishVol8-CD2.bin / bbs / dev / oberon-a-1.4ß.lha / Oberon-A / texts / TechNotes.Text < prev    next >
Text File  |  1994-05-12  |  53KB  |  1,360 lines
  1. Departement Informatik
  2. Institut für Computersysteme
  3. Eidgenössische Technische Hochschule
  4. Zürich
  5.  
  6. ----------------------------------------------------------------------------
  7.  
  8. Oberon Technical Notes
  9.  
  10. Cuno Pfister (ed.)
  11.  
  12. The purpose of the Oberon technical notes is to provide the implementor
  13. of an Oberon system with the experience gained during the implementation
  14. efforts undertaken at the Institut für Computersysteme at ETH.
  15. Furthermore they give an overview over work already done or under way.
  16. This report contains the first five technical notes.
  17.  
  18. Table of Contents
  19.  
  20. 1. Oberon Implementations page 28
  21.  
  22. 2. An Integrated Heap Allocator/Garbage Collector page 30
  23.  
  24. 3. Type Guards and Type Tests page 40
  25.  
  26. 4. A Symmetric Solution to the Load/Store Problem page 42
  27.  
  28. 5. Garbage Collection on Open Arrays page 48
  29.  
  30. ----------------------------------------------------------------------------
  31.  
  32. 1. Oberon Implementations
  33.  
  34. Cuno Pfister
  35.  
  36. The original Oberon implementation [1] has been realized by N. Wirth and
  37. J. Gutknecht for the Ceres workstation [2]. Several ports of the system
  38. to other machines have been completed since then. We will give a short
  39. description of each of those projects. Differences to the original
  40. implementations are described.
  41.  
  42. Ceres (National Semiconductor NS32x32)
  43.  
  44. The original implementation. Oberon is the basic operating system.
  45. Module Display is written in assembly language. The garbage collector is
  46. a mark-and-sweep garbage collector which runs only between commands,
  47. i.e. it does not need to handle pointers on the stack. An access to a
  48. freed module results in a trap on the Ceres-1 and Ceres-2, but goes
  49. undetected on the Ceres-3. The heap allocator/garbage collector is
  50. written in assembly language and linked together with the inner core
  51. modules.
  52.  
  53. Sun  SPARCstation (Sun SPARC)
  54.  
  55. This implementation [3] runs on top of SunOS as a Unix process. Oberon
  56. takes over the whole screen. The display operations are based on the SUN
  57. Pixrect routines. Oberon files are mapped to Unix files. A variant of
  58. the buddy system strategy is used for heap allocation. The garbage
  59. collector is a mark-and-sweep garbage collector which usually runs
  60. between commands, but when NEW fails due to a memory shortage, the
  61. garbage collector is started also. This collector also takes pointers on
  62. the stack into account. This is done by treating each memory location on
  63. the stack as a possible pointer value. To find out whether a memory word
  64. is a pointer, it is subjected to some plausibility tests, such as
  65. testing whether the value points to a possible block address in the heap
  66. and whether a possibly valid type tag is found there. If the
  67. plausibility tests succeed, the heap is traversed sequentially to find
  68. the corresponding block. If the block is found, the tested memory
  69. location is treated as a root for the garbage collector. Modules are
  70. never freed but merely removed from the module list, i.e. an access to a
  71. freed module cannot be detected and aborted. The loader and heap
  72. allocator/garbage collector are written in Modula-2 and linked as a Unix
  73. application.
  74.  
  75. Apple  Macintosh II (Motorola MC68020)
  76.  
  77. This implementation [4, 5] runs on top of the MacOS as a (MultiFinder
  78. friendly) application. Oberon runs in one Macintosh window. The display
  79. operations are largely based on the Apple QuickDraw routines. Oberon
  80. files are mapped to Macintosh files. An integrated allocator/collector
  81. is used (see technical note # 2). Modules are never freed but merely
  82. removed from the module list, i.e. an access to a freed module cannot be
  83. detected and aborted. The type descriptors contain information about
  84. procedure variables in records, such that a checked version of the
  85. System.Free command could be implemented in the future. The loader, heap
  86. allocator/garbage collector and some raster operations are written in
  87. assembly language and linked as a Macintosh application.
  88.  
  89. DEC  DECstation (MIPS R2000)
  90.  
  91. This implementation runs on top of Ultrix as a process. Oberon runs in
  92. an X-window. The display operations are based on X-windows. Oberon files
  93. are mapped to Ultrix files. An integrated allocator/collector is used
  94. (see technical note # 2). Modules are never freed but merely removed
  95. from the module list, i.e. an access to a freed module cannot be
  96. detected and aborted. The loader is written in C and linked as a Unix
  97. application.
  98.  
  99. IBM  S/6000 (IBM S/6000)
  100.  
  101. This project has recently been started.
  102.  
  103. IBM  PS/2 (Intel 80386)
  104.  
  105. This project has recently been started.
  106.  
  107. Others
  108.  
  109. Other Oberon compiler back-ends have been written by students, but the
  110. system was not ported. The compiler back-ends available produce code for
  111. the following processors:
  112.  
  113.   - a virtual stack machine (similar to P-Code or M-Code)
  114.   - Intel 8086
  115.   - Intel 80386
  116.   - INMOS T800 Transputer
  117.   - C language (Oberon subset to C translator, for bootstrapping a compiler)
  118.  
  119. References
  120.  
  121. 1. Wirth N, Gutknecht J (1989), The Oberon System, Software-Practice and
  122. Experience, 19 (9), 857-893
  123.  
  124. 2. Eberle H (1987), Development and Analysis of a Workstation Computer,
  125. Ph. D. thesis no. 8431, ETH Zürich
  126.  
  127. 3. Templ J (1990), SPARC-Oberon, User's Guide and Implementation, Report
  128. 133, ETH Zürich
  129.  
  130. 4. Franz M (1990), The Implementation of MacOberon, Report 141, ETH
  131. Zürich
  132.  
  133. 5. Franz M (1990), MacOberon Reference Manual, Report 142, ETH Zürich
  134.  
  135. ----------------------------------------------------------------------------
  136.  
  137. 2. An Integrated Heap Allocator/Garbage Collector
  138. Beat Heeb, Cuno Pfister
  139.  
  140. Abstract
  141.  
  142. Heap Allocation and Garbage Collection are fundamental services of an
  143. Oberon implementation. It is shown how a simple and efficient
  144. implementation of these services can be attained.
  145.  
  146. Introduction
  147.  
  148. Programs for personal computers become increasingly loaded with
  149. features, most of them rarely needed. The reason for that is, apart from
  150. the marketing pressure to advertise more features than the competition,
  151. the desire to provide all the features that anyone might ever need or
  152. want. The result is that programs become ever larger, more complex,
  153. buggier, more expensive and sometimes delivered years after their
  154. announcements. Even then they often fail to provide features useful for
  155. a particular task. A solution to this problem lies in the development of
  156. extensible programs. Extensibility here means that a program can provide
  157. the customer with only the features needed most of the time and with
  158. some means to extend it. If the customer needs some special service, he
  159. (or usually a third party) can implement this service himself, without
  160. having access to the original program's source code.
  161.  
  162. For example, imagine an extensible page layout program which supports
  163. text boxes, draw boxes and bitmap boxes as standard box types, and
  164. commands to operate upon them. A user may have special needs concerning
  165. the available commands, like e.g. a command which aligns the selected
  166. objects in a document in a special way. It should be possible for him to
  167. write such a command, which operates on the exported document data
  168. structure. This poses a subtle problem, though. The command implementor
  169. may generate references, i.e. pointers, to an exported data structure,
  170. and these references are not known to the basic layout program. This
  171. means in particular that when the layout program disposes of the storage
  172. used by a document, there may still be pointers around which reference
  173. this storage. Such pointers are called dangling pointers . Dangling
  174. pointers are one of the most frequent and most dangerous sources of
  175. program malfunctions. Their use often results in the destruction of data
  176. not belonging to the erroneous module, and the destruction may not be
  177. detected for a long time. Such an error is difficult to track down,
  178. consequently it is difficult to determine who is responsible for an
  179. accident caused by the error. So extensibility leads to a loss of
  180. control over references and thereby to an increased probability for
  181. dangling pointers. We will come back to that shortly.
  182.  
  183. The user of a program like the one described above should also be able
  184. to write an extension that supports special table boxes, for instance.
  185. Such an extension consists of a module which implements the data type
  186. Table, together with the particular behaviour