Narrow Results

Replication-based incremental garbage collection is one of the more appealing concurrent garbage collection algorithms known today. It allows continuous operation of the application (the mutator) with very short pauses for garbage collection. There is a growing need for such garbage collectors suitable for a multithreaded environments such as the Java Virtual Machine. Furthermore, it is desirable to construct collectors that also work on multiprocessor computers.

We begin by pointing out an important, yet subtle point, which arises when implementing the replication-based garbage collector for a multithreaded environment. We first show that a simple and natural implementation of the algorithm may lead to an incorrect behavior of multithreaded applications. We then show that another simple and natural implementation eliminates the problem completely. Thus, the contribution of this part is in stressing this warning to future implementors.

Next, we address the effects of the memory coherence model on this algorithm. We show that even when the algorithm is properly implemented with respect to our first observation, a problem might still arise when a multiprocessor system is used. Adopting a naive solution to this problem results in very frequent (and expensive) synchronization. We offer a slight modification to the algorithm which eliminates the problem and requires little synchronization.

It is an important problem to determine the tenuring collection time or major collection time to meet the pause time goal for a generational garbage collector. From such a viewpoint, this paper proposes two stochastic models based on the working schemes of a generational garbage collector: Garbage collections occur at a nonhomogeneous Poisson process. Minor collections are made when the garbage collector begins to work, tenuring collection is made at a planned time T or at the first collection time when surviving objects have exceeded K for the first model. Major collection is made at time T or at the Nth collection for the second model. Using the techniques of cumulative processes and reliability theory, expected cost rates are obtained, and optimal policies of tenuring and major collection times which minimize them are discussed analytically and computed numerically.

In the computer science community, garbage collection is a dynamic storage management technology to ensure the reliability of computer systems. In this paper, we consider two garbage collection policies to meet the goal of time consumption for a generational garbage collector when increase in objects might be unclear at discrete times for the high frequency of computer processes. That is, (a) tenuring collection is triggered at the $n$th minor collection preventively or at a threshold amount $K$ of surviving objects correctively, and (b) major collection is made at discrete times $JT$ for a given $T$ or at the $N$th collection including minor and tenuring collections. Using the damage process and renewal theory, the expected cost rates are obtained, and their optimal policies for tenuring and major collection are discussed analytically and computed numerically.