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 being conducted 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 of Grenoble purchased an IBM 7044, a machine 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.
Still using the Lisp embedding in Algol, I noticed that a non-compacting garbage collector (GC) considerably degraded the efficiency of the virtual memory. That could 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].I remember having significantly increased the available virtual memory of that computer without considerably decreasing 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]—which was to be followed by many others in subsequent years.
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 the 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, along with Yves Bekker, I co-edited the proceedings of the first international conference in Memory Management [CY 92]