This paper examines a List Processing System from the software programmer's viewpoint and discusses design features which permit efficient time-sharing with other programs. The term time-sharing is intentionally used loosely to include both multiprogramming and multi-access, since the essential problem common to both is that of sharing storage. To the software programmer a List Processing System is essentially organisation of store utilization.
So as not to get bogged down with vague generalities, this paper will discuss some aspects of the implementation of Lisp 1.5 on Atlas 1. The special feature of Lisp, as far as store utilization is concerned, is that the system includes automatic garbage collection. That is, when all the available working space has been utilized, a special process is carried out to determine which of the working space cells are still active and which are now inactive. An active cell is, of course, one which holds information which is required either permanently or until some further processing has been completed. It is the author's opinion that a good garbage collection scheme is essential to efficient store sharing.
Before garbage collection techniques are described it is worthwhile examining the different types of information which have to be kept in store, and the different store structures which these require. The term linear is used to describe information which is kept in consecutive store locations.
If two bits in every word can be made available as flags to identify the type of information that the word holds, then types (2), (3) and (4) can conveniently be kept in one region. The central problem is then the organisation of the composite free-storage.
Old methods of free-storage organisation have used the concept of a list of available space. All the inactive cells are strung together in a list and when a new cell is required the first inactive cell is removed from the list. When cells cease to be active they are left dangling free, ready to be swept on to a new free list by the garbage collector after the previous list has been exhausted. Alternatively, in the absence of a garbage collector, the cell may be inserted in the list as soon as it becomes inactive. The pathology of such systems is that the active and inactive cells become thoroughly interspersed. Thus the job must always hold on to the entire free-storage region in order to keep all the active information.
A newer method is to keep all the useful information at one end of the free storage region with a boundary separating the active from the inactive part. As new cells are required the boundary encroaches on the inactive region. Automatic garbage collection is essential for this scheme in order to repartition the active cells from the inactive cells after the latter have been exhausted. With this scheme the push-down stack can be made to encroach on the inactive region from the opposite end of the active region. This has the advantage of allowing dynamic allocation for the stack. All jobs can commence with a small amount of store and need only expand if a garbage collection sweeps up too few inactive cells. If, after garbage collection, the amount of storage in the inactive region is far in excess of what is immediately required, then large blocks of it can be released for other programs in the time-sharing system. This is possible only because the inactive cells have been weeded out of the active region and vice versa. Hence the need for a good garbage collection scheme. Note that a weeding process is faster than concertina-ing.
The binary program plays a relatively static role in storage organisation. However, facilities must be available for expanding this region for newly compiled or assembled routines. A simple method, for a paged core, is to put the binary program in its own segment. Another method is to make the push-down stack and the binary program dynamically relocatable (i. e. the information in these two regions should be independent of its position in store). The binary program can then reside beyond the push-down stack, which can then be shunted down into the inactive region when the binary program is to be extended. This is preferable to making the free-storage region relocatable, since this is usually the largest of the regions.
With the use of the above techniques of store utilization organization a job can be made to occupy little more than the least possible storage space, because the boundaries between storage regions are dynamic. This is unlike early systems, where static maximum limits had to be set on the size of several storage regions before the start of a run. Furthermore, a user can be made fully aware of the amount of storage he has used so that he may compare different methods possible for his program.
