Ph.D Thesis

Ph.D StudentPaz Harel
SubjectEfficient Memory Management for Servers
DepartmentDepartment of Computer Science
Supervisors PROF. Erez Petrank
PROF. Hillel Kolodner


Modern symmetric multi-processor (SMP) servers with large heaps provide new challenges for the design of suitable garbage collectors. Garbage collectors designed for client machines usually work in the so called stop-the-world (STW) manner. A STW collector stops all program threads while executing. Naive collectors employ only one of the available CPUs on an SMP. Naive STW collectors may lead to inefficient running times on servers, long pause times and poor CPU utilization. These problems can be solved by either executing the collector in a separate thread (or process) concurrently with the program threads, or by parallelizing the execution of the collection.

We have designed and implemented several alternative collectors for server platforms. These collectors attempt to improve the garbage collection process in SMP platforms. In particular, we have focused on concurrent collectors and reference-counting collectors.

We started by designing a mark-and-sweep on-the-fly algorithm based on the sliding-views mechanism of Levanoni and Petrank. This algorithm can also be used to infrequently collect garbage cycles in the reference-counting sliding-views collector. Next, we introduced the age-oriented collector, which exploits the generational hypothesis best when used with reference counting, to obtain highly efficient collection. In our third project, we proposed a new on-the-fly cycle collection algorithm to accompany the reference-counting sliding-views collector. In the fourth, we have inserted prefetch instructions into the reference-counting collector in order to hide (or decrease) cache miss stalls, and hence reduce the overhead imposed by a reference-counting collector. Finally, we studied ways to identify and eliminate wasteful use of the memory management subsystem by employing three patterns, when possible.