FeGC: An efficient garbage collection scheme for flash memory based storage systems

NAND flash memory is a promising storage media that provides low-power consumption, high density, high performance, and shock resistance. Due to these versatile features, NAND flash memory is anticipated to be used as storage in enterprise-scale systems as well as small embedded devices. However, unlike traditional hard disks, flash memory should perform garbage collection that consists of a series of erase operations. The erase operation is time-consuming and it usually degrades the performance of storage systems seriously. Moreover, the number of erase operations allowed to each flash memory block is limited. This paper presents a new garbage collection scheme for flash memory based storage systems that focuses on reducing garbage collection overhead, and improving the endurance of flash memory. The scheme also reduces the energy consumption of storage systems significantly. Trace-driven simulations show that the proposed scheme performs better than various existing garbage collection schemes in terms of the garbage collection time, the number of erase operations, the energy consumption, and the endurance of flash memory.     

A performance perspective on the Active Memory System

One major problem of using Java in real-time and embedded devices is the non-deterministic turnaround time of dynamic memory management systems (memory allocation and garbage collection). For the allocation, the non-determinism is often contributed by the time to perform searching, splitting, and coalescing. For the garbage collection, the turnaround time is usually determined by the size of the heap, the number of live objects, the number of object collected, and the amount of garbage collected. Even with the current state-of-the-art garbage collectors (generational and incremental schemes), they may or may not guarantee the worst-case latency. Moreover, such schemes often prolong overall garbage collection time.

In this paper, the performance analysis of the proposed Active Memory Module (AMM) for embedded systems is presented. Unlike the software counterparts, the AMM can perform a memory allocation in a predictable and bounded fashion (14 cycles). Moreover, it can also yield a bounded sweeping time regardless of the number of live objects or heap size. By utilizing the proposed system, the overall speedup can be as high as 23% compared to the garbage collection system of the JDK 1.2.2 running in classic mode.     

The active deallocation of objects in object-oriented systems

In object-oriented systems, it is oftern useful for objects to be allowed to carry out some action before they are deallocated. This can be done by defining a destroy method in the object's class, and arranging for the memory system to send a message invoking this method immediately before deallocating the object. This allows resources associated with the object to be returned to the system, limited cross-language garbage collection, and other, more complex, behaviour. During the execution of the destroy method it is possible for new references to objects to be created. Care must be taken that the garbage collection does not erroneously free such objects. Algorithms are presented to implement destroy methods in systems using reference counting and mark-scan garbage collection techniques. Properties that are desirable in such systems are also discussed.     

Lazy garbage collection of recovery state for fault-tolerantdistributed shared memory

In this paper, we address the problem of garbage collection in a single-failure fault-tolerant home-based lazy release consistency (HLRC) distributed shared-memory (DSM) system based on independent checkpointing and logging. Our solution uses laziness in garbage collection and exploits consistency constraints of the HLRC memory model for low overhead and scalability. We prove safe bounds on the state that must be retained in the system to guarantee correct recovery after a failure. We devise two algorithms for garbage collection of checkpoints and logs, checkpoint garbage collection (CGC), and lazy log trimming (LLT). The proposed approach targets large-scale distributed shared-memory computing on local-area clusters of computers. In such systems, using global synchronization or extra communication for garbage collection is inefficient or simply impractical due to system scale and temporary disconnections in communication. The challenge lies in controlling the size of the logs and the number of checkpoints without global synchronization while tolerating transient disruptions in communication. Our garbage collection scheme is completely distributed, does not force processes to synchronize, does not add extra messages to the base DSM protocol, and uses only the available DSM protocol information. Evaluation results for real applications show that it effectively bounds the number of past checkpoints to be retained and the size of the logs in stable storage     

Object resizing and reclamation through the use of hardware bit-maps

The memory intensive nature of object-oriented languages such as C++ and Java has created the need of a high-performance dynamic memory management. Object-oriented applications often generate higher memory intensity in the heap region. Thus, high-performance memory manager is needed to cope with such applications. As today's VLSI technology advances, it becomes more and more attractive to map software algorithms such as malloc(), free(), realloc(), and garbage collection into hardware.

This paper presents hardware designs of realloc function and sweeping function (for mark and sweep garbage collection) that fully utilize the advantages of combinational logic. In our scheme, the reallocation on the original block can be done in constant time. If the reallocation on the original block is not possible, the previously proposed malloc() and free() can be used to move the contents to a new location. For the sweeping function, the bit-sweeper can detect and sweep the garbage in constant time. Since the sweeping phase often consumes more time than the marking phase, the garbage collection time can be substantially improved. The hardware complexity of proposed scheme (i.e. X-Unit, RS-unit, ESG-unit, and bit-sweeper) is O(n), where n represents the size of bit-map.     

Reference count garbage collection

A garbage collection algorithm that permits a reference count storage reclamation scheme to collect circularly linked inaccessible structures is presented. The algorithm requires no additional information beyond that required by a reference count scheme. In particular, it does not require the garbage collector to be able to find pointers outside the heap. The algorithm is most useful for augmenting reference count storage reclamation systems and for implementing storage management systems on top of languages that do not provide their own. It is, however, considerably less efficient in space and time than conventional garbage collection systems.     

Simple generational garbage collection and fast allocation

Generational garbage collection algorithms achieve efficiency because newer records point to older records; the only way an older record can point to a newer record is by a store operation to a previously created record, and such operations are rare in many languages. A garbage collector that concentrates just on recently allocated records can take advantage of this fact. Such a garbage collector can be so efficient that the allocation of records costs more than their disposal. A scheme for quick record allocation attacks this bottleneck. Many garbage-collected environments do not know when to ask the operating system for more memory. A robust heuristic solves this problem. This paper presents a simple, efficient, low-overhead version of generational garbage collection with fast allocation, suitable for implementation in a Unix environment.     

A high performance NAND array file system based on multiple NAND flash memories

The existing NAND flash memory file systems have not taken into account multiple NAND flash memories for large-capacity storage. In addition, since large-capacity NAND flash memory is much more expensive than the same capacity hard disk drive, it is cost wise infeasible to build large-capacity flash drives. To resolve these problems, this paper suggests a new file system called NAFS for large-capacity storage with multiple small-capacity and low-cost NAND flash memories. It adopts a new cache policy, mount scheme, and garbage collection scheme in order to improve read and write performance, to reduce the mount time, and to improve the wear-leveling effectiveness. Our performance results show that NAFS is more suitable for large-capacity storage than conventional NAND file systems such as YAFFS2 and JFFS2 and a disk-based file system for Linux such as HDD-RAID5-EXT3 in terms of the read and write transfer rate using a double cache policy and the mount time using metadata stored on a separate partition. We also demonstrate that the wear-leveling effectiveness of NAFS can be improved by our adaptive garbage collection scheme.     

Schedulable garbage collection in CLI virtual execution system

Virtual software execution environment, known as Virtual Machine (VM), has been gaining popularity through Java Virtual Machine (JVM) and Common Language Infrastructure (CLI). Given their advantages in portability, productivity, and safety, etc., applying VM to real-time embedded systems can leverage production cost, fast time-to-market, and software integrity. However, this approach can only become practical once the VM operations and application tasks are made schedulable jointly. In this paper, we present a schedulable garbage collection algorithm applicable on real-time applications in CLI virtual machine environment. To facilitate the scheduling of real-time applications and garbage collection operations, we make the pause time due to garbage collection controllable, and the invocation of garbage collection predictable. To demonstrate the approach, a prototype for a schedulable garbage collection has been implemented in CLI execution environment. The garbage collection is carried out by a concurrent thread while meeting a targeted pause time and satisfying the memory requests of applications. A cost model of garbage collection is established based on measured WCET such that the execution time and overhead of garbage collection operations can be predicted. Finally, we illustrate a joint scheduling algorithm to meet the time and memory constraints of real-time systems.     

A new external reference management and distributed unification for KL1

This paper describes a new external reference management scheme for KL1, a committed choice logic programming language based on GHC. The significance of the new scheme is that it realizes incremental inter-processor garbage collection. Previous distributed implementations of committed choice languages had not seriously addressed inter-processor garbage collection. Incremental inter-precessor garbage collection is realized by the Weighted Export Counting (WEC). It is a first attempt to use the weighted reference counting technique in logic programming language implementation, and is also new in that it has introduced export and import tables for making independent local garbage collection possible and reducing the number of inter-processor read requests. The problems with exhaustion of reference counts and indirect exportation are discussed. Since the binding order rule adopted in our previous implementation for avoiding creation of reference loops is insufficient in the presence of indirect exportation, a new binding order rule is introduced. We prove that avoidance of reference loops is guaranteed and also prove that the unification procedure always terminates for non-circular structures.     

Scheduling of hard real-time garbage collection

Automatic memory management or garbage collection greatly simplifies development of large systems. However, garbage collection is usually not used in real-time systems due to the unpredictable temporal behavior of current implementations of a garbage collector. In this paper we propose a real-time garbage collector that can be scheduled like a normal real-time thread with a deadline monotonic assigned priority. We provide an upper bound for the collector period so that the application threads will never run out of memory. Furthermore, we show that the restricted execution model of the Safety Critical Java standard simplifies root scanning and reduces copying of static data. Our proposal has been implemented and evaluated in the context of the Java processor JOP.     

A customisable memory management framework for C++

Automatic garbage collection relieves programmers from the burden of managing memory themselves and several techniques have been developed that make garbage collection feasible in many situations, including real time applications or within traditional programming languages. However, optimal performance cannot always be achieved by a uniform general purpose solution. Sometimes an algorithm exhibits a predictable pattern of memory usage that could be better handled specifically, delaying as much as possible the intervention of the general purpose collector. This leads to the requirement for algorithm specific customisation of the collector strategies. We present a dynamic memory management framework which can be customised to the needs of an algorithm, while preserving the convenience of automatic collection in the normal case. The Customisable Memory Manager (CMM) organises memory in multiple heaps. Each heap is an instance of C++ class which abstracts and encapsulates a particular storage discipline. The default heap for collectable objects uses the technique of mostly copying garbage collection, providing good performance and memory compaction. Customisation of the collector is achieved exploiting object orientation by defining specialised versions of the collector methods for each heap class. The object-oriented interface to the collector enables coexistence and coordination among the various collectors as well as integration with traditional code unaware of garbage collection. The CMM is implemented in C++ without any special support in the language or the compiler. The techniques used in the CMM are general enough to be applicable also to other languages. The performance of the CMM is analysed and compared to other conservative collectors for C/C++ in various configurations. © 1998 John Wiley & Sons, Ltd.     

Android存储系统中NAND闪存性能的改进

针对Android存储系统在闪存管理上存在较差的磨损均衡效果和较高的垃圾回收额外开销的缺陷,引入冷热数据分离策略,将文件按照不同热度写入对应热度的物理存储单元,同时改进垃圾回收策略,以达到良好的磨损均衡效果并减少垃圾回收额外开销。基于Android平台的实验结果表明,改进后的策略在有效减少NAND闪存垃圾回收额外开销的同时,还能有效改善其磨损均衡效果。     

Lazy garbage collection of recovery state for fault-tolerantdistributed shared memory

We address the problem of garbage collection in a single-failure fault-tolerant home-based lazy release consistency (HLRC) distributed shared-memory (DSM) system based on independent checkpointing and logging. Our solution uses laziness in garbage collection and exploits consistency constraints of the HLRC memory model for low overhead and scalability. We prove safe bounds on the state that must be retained in the system to guarantee correct recovery after a failure. We devise two algorithms for garbage collection of checkpoints and logs, checkpoint garbage collection (CGC), and lazy log trimming (LLT). The proposed approach targets large-scale distributed shared-memory computing on local-area clusters of computers. The challenge lies in controlling the size of the logs and the number of checkpoints without global synchronization while tolerating transient disruptions in communication. Evaluation results for real applications show that it effectively bounds the number of past checkpoints to be retained and the size of the logs in stable storage     

A parallel asynchronous garbage collection algorithm fordistributed systems

The problem of distributed garbage collection is discussed. An algorithm for parallel distributed asynchronous garbage collection is presented. The liveness and safety properties of this method are demonstrated. The algorithm does not require a global clock, complex termination detection methods, or distributed synchronization techniques. A new color code is introduced to distinguish between local cells (black) and those that are exclusively accessible from the remote pointers (gray). The mutator operation is revised to handle a multiple mutator scheme on a given local memory. Simulation results show that the developed distributed and parallel algorithm performs much better than the sequential method as tested on a Balance 8000 computer     

Efficient Garbage Collection Schemes for Causal Message Logging with Independent Checkpointing

This paper presents three garbage collection schemes for causal message logging with independent checkpointing. The first scheme allows each process to autonomously remove useless log information in its volatile storage by piggybacking only some additional information without requiring any extra message and forced checkpoint. Additionally, it supports faster output commit than traditional schemes. The second scheme enables each process to remove a part of log information in the storage if more empty space is required. It reduces the number of processes participating in the garbage collection by using the size of the log information of each process. The third scheme is a hybrid scheme having the advantages of the two proposed schemes. Simulation results show that the third scheme significantly reduces the garbage collection overhead compared with the traditional schemes regardless of specific communication patterns of distributed applications.     

A parallel copying garbage collection scheme for shared-memory multiprocessors

Earlier work on parallel copying garbage collection is based on parallelization of sequential schemes with breadth-first traversing of live data. Recently it has been demonstrated that sequential copying schemes with depth-first traversing of live data are more flexible and more efficient than the corresponding ones with breadth-first traversal. A clear advantage of the former is that they work with no extra space overheads on non-contiguous memory blocks, which allows more flexible implementation. This paper shows how to parallelize an efficient depth-first copying scheme while retaining its high efficiency and flexibility. Research interests: His research interests include techniques for parallel and distributed implementation of functional, logic, concurrent constraints and object-oriented programming systems. He is also interested in performance analysis and garbage collection. His current interest is efficient techniques for distributed implementation of the concurrent programming language Oz.     

基于智能垃圾桶的垃圾分类动态收运路径优化问题研究

针对城市生活垃圾分类收运过程中存在的环境二次污染和垃圾产生量不确定性等问题,提出了一种基于智能垃圾桶的动态收运车辆路径优化方法。建立以最小化碳排放成本、燃油消耗成本、固定成本和车辆延迟到达惩罚成本为目标的动态车辆路径优化模型。采用滚动时域的方式将动态问题转换为一系列静态问题,并设计两阶段算法进行求解。首先采用粒子群算法对收运车辆路径进行规划,而后在每个时域末,综合考虑待清运垃圾桶的位置和垃圾量、垃圾收运车辆的位置和装载量以动态调整现有车辆路径。研究结果表明,相较于传统的静态收运方案,动态垃圾收运方案能够在降低车辆运输成本和碳排放成本的同时,显著降低由于清运不及时造成的环境二次污染的风险。     

浅析.NET的垃圾回收机制

.NET Framework中的垃圾回收(Garbage Collection)机制减少了一些应用程序中发生内存泄露和访问冲突的可能性,但GC的工作机制仍然存在问题。在程序开发中,总会发现对于GC的错误理解。文章针对此问题进行研究分析,简要说明内存垃圾的产生原因、垃圾回收机制的原理、垃圾回收的主要对象以及释放模式。