Search

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $$\mathcal {C}$$ of GC algorithms. Apart from the Random GC algorithm, class $$\mathcal {C}$$ includes two novel GC algorithms: the $$d$$ - Choices GC algorithm, that selects $$d$$ blocks uniformly at random and erases the block containing the least number of valid pages among the $$d$$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $$N=50{,}000$$ blocks). We further show that the $$d$$ - Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $$d$$ values, e.g., $$d = 10$$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $$b$$ per block is large (e.g., for $$b \ge 64$$ ). [ABSTRACT FROM AUTHOR]

NAND flash memory is a popular storage device for consumer electronics and it is exploited to be swap space for extending the limited main memory of consumer electronics. Due to the out-of-place update scheme provided by NAND flash memory to solve its erase-before-write hardware constraint, garbage collection should be performed to reclaim garbage in terms of invalid pages and obtain free space in terms of free blocks. The garbage collection, which consists of a series of copy operations and erase operations, is energy-consuming. In order to reduce the energy consumption, a swap-aware garbage collection algorithm for NAND flash-based consumer electronics is proposed in this paper. The proposed algorithm focuses on reducing the garbage collection overhead and improving the endurance of NAND flash memory. Experimental results show that the proposed algorithm is superior to the existing garbage collection algorithms in terms of the number of copy operations, the number of erase operations, the degree of wear-leveling, and energy consumption. [ABSTRACT FROM AUTHOR]

As multi-tasking has become the common feature of modern smart devices, providing QoS (quality of service) guarantees for heterogeneous applications becomes challenging. For example, if a real-time application like a movie player is executed simultaneously with other applications, jitters may be experienced due to resource contention among the concurrent processes. This paper presents a novel I/O mechanism to provide jitter-free multimedia playing in smart devices. To this end, the I/O paths of smart devices were explored and two sources of unpredictable latency were discovered. The first one is the garbage collection overhead of flash memory and the second one is the non-preemptive scheduling used in the software platform of smart devices. This paper resolves these problems by adopting non-volatile memory as the storage of real-time applications, and then performing non-blocking I/O for them. This mechanism completely prevents all possible run-time delays due to the interferences of other processes, providing QoS-guaranteed services for real-time applications. Tracedriven simulations show that the proposed scheme reduces the deadline miss ratio of a movie player by 40% on average. [ABSTRACT FROM AUTHOR]

Abstract: Semispace garbage collectors relocate all the live objects in one step, which is simple and leads to good performance. Compared with mark-compact collectors, however, they need to reserve extra heap space for copying live objects. As much as half of the heap could be reserved as it is possible that all the allocated objects survive. In reality, however, most programs exhibit a high infant mortality, and therefore reserving half the heap is wasteful. We have observed that the memory usage of many ordinary programs is relatively stable over the course of their execution. This provides an opportunity for online predictions to dynamically adjust and optimize the reserved space. Consequently, we propose a skew-space garbage collector that reserves space dynamically. This collector is implemented using the MMTk framework of the Jikes RVM and gives encouraging results against related garbage collection algorithms for the DaCapo and SPECjvm98 benchmarks. [Copyright &y& Elsevier]

Abstract: Reference counting strategy is a natural choice for real-time garbage collection, but the cycle collection phase which is required to ensure the correctness for reference counting algorithms can introduce heavy scanning overheads. This degrades the efficiency and inflates the pause time required for garbage collection. In this paper, we present two schemes to improve the efficiency of reference counting algorithms. First, in order to make better use of the semantics of a given program, we introduce a novel classification model to predict the behavior of objects precisely. Second, in order to reduce the scanning overheads, we propose an enhancement for cyclic reference counting algorithms by utilizing strongly-typed reference features of the Java language. We implement our proposed algorithm in Jikes RVM and measure the performance over various Java benchmarks. Our results show that the number of scanned objects can be reduced by an average of 37.9% during cycle collection phase. [Copyright &y& Elsevier]

The Flash Translation Layer (FTL) in Solid-State Disks (SSDs) maps logical addresses to physical addresses for disk drive virtualization. In order to reduce garbage collection overhead, we propose full associative striped block-level mapping. In addition, an adaptive merge is proposed to avoid excessive data block reconstructions during garbage collection. With these mechanisms, the write latency is improved up to 78% in comparison with the previous multichannel hybrid FTLs in a sample PC trace. The performance improvements stem from 52% reduced garbage collection. [ABSTRACT FROM AUTHOR]

Hard real-time systems always choose not to use garbage collection in order to avoid its unpredictable executions. Much effort has been expended trying to build predictable garbage collectors which can provide both temporal and spatial guarantees. Unfortunately, most existing work leads to systems that cannot easily achieve a balance between temporal and spatial performances. Moreover, the scheduling of garbage collectors has not been integrated into modern real-time scheduling frameworks, which makes the benefits provided by the advancement of scheduling techniques very difficult to obtain. This paper argues that the existing design criteria for real-time garbage collectors do not reflect the unique requirements of flexible hard real-time systems. As a part of our design criteria, a new performance indicator is proposed to describe the capability of a real-time garbage collector to achieve a better balance between temporal and spatial performances. A hybrid garbage collection algorithm is designed accordingly which also uses dual priority scheduling algorithm to reclaim spare capacity while guaranteeing deadlines. [ABSTRACT FROM AUTHOR]

A real-time garbage collector has to fulfill two basic properties: ensure that programs with bounded allocation rates do not run out of memory and provide short blocking times. Even for incremental garbage collectors, two major sources of blocking exist, namely, root scanning and heap compaction. Finding root nodes of an object graph is an integral part of tracing garbage collectors and cannot be circumvented. Heap compaction is necessary to avoid probably unbounded heap fragmentation, which in turn would lead to unacceptably high memory consumption. In this article, we propose solutions to both issues. Thread stacks are local to a thread, and root scanning, therefore, only needs to be atomic with respect to the thread whose stack is scanned. This fact can be utilized by either blocking only the thread whose stack is scanned, or by delegating the responsibility for root scanning to the application threads. The latter solution eliminates blocking due to root scanning completely. The impact of this solution on the execution time of a garbage collector is shown for two different variants of such a root scanning algorithm. During heap compaction, objects are copied. Copying is usually performed atomically to avoid interference with application threads, which could render the state of an object inconsistent. Copying of large objects and especially large arrays introduces long blocking times that are unacceptable for real-time systems. In this article, an interruptible copy unit is presented that implements nonblocking object copy. The unit can be interrupted after a single word move. We evaluate a real-time garbage collector that uses the proposed techniques on a Java processor. With this garbage collector, it is possible to run high-priority hard real-time tasks at 10 kHz parallel to the garbage collection task on a 100 MHz system. [ABSTRACT FROM AUTHOR]

A coarse-grained log block allocation policy has been proved to be efficient in the newly emerging block-group-based NAND flash translation layers (FTL). However, these FTL schemes can result in a large garbage collection overhead in terms of valid page copy and erase operations, because they employ a least recently used (LRU) algorithm as their victim selection policy for garbage collection. In this paper, we propose a cost-oriented recycling policy (CORP) to remedy this problem, where the victim block-groups for garbage collection are selected based on the recycling operation overhead and the write access possibility of each logical block. Trace-driven simulations show that the proposed scheme greatly reduces the garbage collection overhead and promises a more efficient FTL solution. [ABSTRACT FROM AUTHOR]

We present two simple mark and sweep algorithms, A and B, for concurrent garbage collection by a single collector running concurrently with a number of mutators that concurrently modify shared data. Both algorithms are based on the ideas of Ben-Ari’s classical algorithm for on-the-fly garbage collection with one mutator. The algorithms require the mutators to estimate the set of objects they currently hold in private variables. They differ in the grain of atomicity of this estimate and in their mutator marking requirements. For algorithm A, the only synchronization needed is at the point where the list of newly collected garbage nodes is included in the free list to again become available to the mutators. Such synchronization of access to the free list seems unavoidable. For algorithm A, the estimate can be constructed concurrently with mutator actions. Algorithm B requires that the estimate is constructed atomically. Algorithms of this form have always been error-prone. We therefore provide assertional proofs of correctness, which moreover have been verified with the proof assistant PVS. [ABSTRACT FROM AUTHOR]

The memory management of distributed objects, when done manually, is an error-prone task. It leads to memory leaks and dangling references, causing applications to fail. Avoiding such errors requires automatic memory management, called distributed garbage collection (DGC). Current DGC solutions are either not safe, not complete or not portable to widely used platforms such as .NET. As a matter of fact, most solutions either run on specialised environments or require modifications of the underlying virtual machine (e.g. rotor, common language runtime (CLR)), hindering its immediate and widespread utilisation. This study describes the design, architecture, implementation and performance measurements of a DGC algorithm for .NET that: (i) is complete, that is, capable of reclaiming both acyclic and cyclic garbage, while (ii) being portable in the sense that it neither requires the underlying virtual machine to be modified, nor source or byte-code modification. The distributed garbage collector was implemented on top of two implementations of the common language infrastructure (.NET virtual machine specification): CLR and shared source CLI, commonly known as Rotor. The implementation requires no modification of the environment, it makes use of the provided aspect-oriented functionalities, and the performance results are encouraging. [ABSTRACT FROM AUTHOR]

Abstract   We consider garbage collection (GC) in dynamic real-time systems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mutator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness and superiority. [ABSTRACT FROM AUTHOR]

There is an important class of interactive multimedia applications that deals with stream data from distributed sources. Indexing the data temporally facilitates ordering individual streams as well as correlating items from different streams. The Stampede programming system organizes stream data into channels that are distributed and synchronized data structures that contain timestamped items. A Stampede program is a data flow graph of threads and channels. Stampede semantics for channels allow concurrent access from multiple threads for input and output. While a channel holds timestamped items, the semantics do not place any restriction on either the production or consumption order of these items. Furthermore, timestamps of items in a channel need not be contiguous. These flexibilities are required due to the dynamic and parallel structure of stream-oriented applications targeted by the Stampede system. Under such circumstances, a key issue is the ‘garbage collection’ (GC) of channel items. In this paper, we present and compare three different GC algorithms: 1) REF is a simple algorithm that keeps a reference count on individual items; 2) TGC is a distributed algorithm for computing a global low watermark for timestamp values of interest in the entire application; 3) DGC is another distributed algorithm that uses information about the dependencies between the producers and consumers of data streams to compute a low water mark local to each node of the data flow graph. DGC can simultaneously eliminate garbage from channels and unneeded computations from threads. In tests performed using an interactive application, DGC enjoys nearly 30 percent reduction in the application memory footprint compared to TGC and REF. DGC and REF are also shown to be more scalable compared to TGC. [ABSTRACT FROM AUTHOR]

This paper discusses implementations of distributed garbage collectors derived using a previously developed methodology which involves mappings of distributed termination detection algorithms (DTAs) to local garbage collection schemes. Implementations produced by such mappings preserve the safety and completeness properties of the original local collectors. Through our collector implementations we have come to understand that the derivation technique extends to distributed collection schemes with heterogeneous local collector behaviour. Our contribution, reported here, is the construction of an experimental platform, implementations of the Task Balancing DTA, an extension to the derivation methodology that minimises constraints on local collectors, together with three new mappings and their implementations. [ABSTRACT FROM AUTHOR]

We present a new approach to parallel copying garbage collection on symmetric multiprocessor (SMP) machines appropriate for Java and other object-oriented languages. Parallel, in this setting, means that the collector runs in several parallel threads. Our collector is based on a new idea called delayed allocation, which completely eliminates the fragmentation problem of previous parallel copying collectors while still keeping low synchronization, high efficiency, and simplicity of collection. In addition to this main idea, we also discuss several other ideas such as termination detection, balancing the distribution of work, and dealing with contention during work distribution. [ABSTRACT FROM AUTHOR]

Focuses on the importance of Java virtual machines in understanding the different garbage collection algorithms. Improvement of the Java program performance; Accounts on the workload distribution in a Java system; Phases of the mark-compact garbage collection.

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. [ABSTRACT FROM AUTHOR]

Describes a server-based algorithm for garbage collecting persistent object stores in a client-server environment. Architectural features of the persistent object stores; Selection of a garbage collection algorithm; Problems in implementing garbage collection.