Research Assistants: G. Rodriguez-Rivera, P. A. Muckelbauer
Sponsor: SUN Microsystems
This project addresses the management of dynamically allocated memory in a system of concurrently executing processes potentially distributed across multiple computers. Each process allocates random amounts of memory at random intervals. The dynamically allocated memory may be shared among an arbitrary subset of processes. The algorithms being investigated place no constraints on the use and sharing of this memory, but still allow unused memory to be automatically reclaimed and re-added to the pool of free memory. In particular, we are doing research on systems which automatically "garbage collect" memory without each process explicitly indicating when it is done with a block of dynamically allocated memory.
Three constraints are placed on this problem. First, there should not be an appreciable impact on the interactive performance of the system. In other words, the system should not suffer from bursty behavior where processes are forced to pause while available memory is collected and/or compacted. Instead, algorithms that allow garbage collection to be executed concurrently with the processes are being investigated. The second constraint is that those algorithms should work locally, as well as in a distributed environment. This means that during garbage collection a block of dynamically allocated memory is not reclaimed if either a local or remote process is using it. Any solution for this problem should deal with issues such as lost, duplicated, out of order messages, disconnection, system crashes, and cycles. Those issues may cause the existence of garbage never collected, or the collection of memory blocks that are still in use. The third constraint is scalability. The algorithm should be able to work with a large number of machines without a significant degradation in its performance. Solutions that make use of time-stamped memory and timeouts are currently explored. The testbed for this project is the kernel of the Renaissance object-oriented operating system.