While pursuing my doctorate at the University of Grenoble, I developed a Lisp-embedding into Algol [CN 65] that was used to study many aspects of list structures and memory recovery. In the mid 1960s, I became aware of the work on virtual memory and paging done in England in the development of the Atlas computer. I was fascinated by the possibility of extending memory capacity in Lisp programs through the use of paging. (I was already familiar with the assembly language programming with the Burroughs 205 a computer that resorted to (hardwired) multiple copies of data to speed up drum access.)
At that time, the university in Grenoble purchased an IBM 7044, and that machine was available for trials of virtual memory simulation. I developed a paging system for the 7044 with the help of Alain Auroux, an expert system programmer for the IBM machine. The paging was operational within a few weeks and used in the context of the Lisp-embedding into Algol.
I remember having increased significantly the available virtual memory of that computer without decreasing considerably the access time. This was because memory usage was basically sequential, and adjacency of data played a key role in reducing access time of pages already present in fast memory. It was then that I published my first paper in the Communications of the ACM [Coh 67b]. That was to be followed by many others in subsequent years.
Still using the Lisp embedding in Algol, I noticed that a non-compacting garbage collector (GC) degraded considerably the efficiency of the virtual memory. That is able to be anticipated, since collection using a free-list scatters information throughout the entire virtual memory, decreasing data locality. A paper describing the efficiencies of virtual memory list processors with compacting and non-compacting GC appeared in 1967 [CT 67].
My involvement with GC continued for many years, and a survey on that topic became a classic reference for a long time [Coh 81]. Later, I combined my interest in analysis of algorithms to study the efficiency of sequential collectors, [CN 83] and later also studied the efficiency of parallel GC [CH 84].
Virtual memory was also used in a student's senior thesis (Arthur Benjamin) who later won an ACM prize for the best paper written by an undergraduate [Ben 72]. Benjamin implemented an editor for a small machine using concepts in paging, involving a relatively small memory coupled with a floppy disk! Those editors were the precursors of current editors running on PC's.
In 1992, I co-edited with Yves Bekker the proceedings of the first international conference in Memory Management [CY 92].
jc@cs.brandeis.edu
