本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/learning-generational-garbage-collection/
Through a large number of programs, we can found that most of the newly created objects have a very short survival time.In other words, the objects have only a short life cycle. This finding has been used to help optimize garbage collection. Using this discovery, we can design a generation garbage collector. The garbage collector maintain multiple heap regions, each one heap objects stored in different ages. We only focus on two generations: a young generation of objects, and an older generation. After a certain amount of garbage collect, if the object is still alive, it will be promoted to the old generation. Generational collector is a better choice because in generational collection,object that are referenced from older memory regions are promoted to the next high region,the older memory regions be recycled less frequently ,it’s efficient. The partition of objects into different generations (time intervals) based on time of allocation, and giving them different GC policies depending on age. Based on the heuristic (often true in practice) that most objects are discarded shortly after being used–hence the GC is tuned to get rid of those first. The Java heap is split into two areas, a new (or nursery) area and an old (or tenured) area. Objects are created in the new area and, if they continue to be reachable for long enough, they are moved into the old area. Objects are moved when they have been reachable for enough garbage collections (known as the tenure age). The new area is split into two logical spaces: allocate and survivor. Objects are allocated into the Allocate Space. When that space is filled, a garbage collection process called scavenge is triggered. During a scavenge, reachable objects are copied either into the Survivor Space or into the Tenured Space if they have reached the tenured age. Objects in the new area that are not reachable remain untouched. When all the reachable objects have been copied, the spaces in the new area switch roles. The new survivor space is now entirely empty of reachable objects and is available for the next scavenge. When the Allocate Space is full, a garbage collection is triggered. Reachable objects are then traced and copied into the Survivor Space. Objects that have reached the tenure age (have already been copied inside the new area a number of times) are promoted into Tenured Space. As the name Generational Concurrent implies, the policy has a concurrent aspect to it. The Tenured Space is concurrently traced with a similar approach to the one used for –Xgcpolicy:optavgpause. With this approach, the pause time incurred from Tenured Space collections is reduced. I am intrested in garbage collection algorithms’ differences and their respective advantages and disadvantages and after some implementation and analysis I choosed lisp2 as the algorithm of old generation’s collection and I choosed Cheney as the algorithm of young generation’s collection. I learned several kinds of writer-barrier and read-barrier and I choose a linear hashing as my writer-barrier as smalltalk and modual-3.And I divide the young generation into two parts but not three parts ,they are from and to, just like the copy collection. Lisp2 has some good feature : Sliding unit to ensure their order; fitting for variable size of units. But lisp2 has to travel the heap three times. Choosing linear hashing as Write-barrier because linear hashing also has some beautiful features: searching and deleting units of the list faster; supporting dynamic expansion and contraction. Besides these design, we also found a tricky point that can be used to improve the performance of the system. When my garbage collector is running, if the old generation becomes full, the lisp2 will work to collect the space, but if after this collection there is also not enough space to allocate, our garbage collector will say ” Out of memory…”and the program will dead. But remember I choose Cheney as my collection algorithm for young so that there may be half of the young generation that are empty. So if I can give full use of these space, I can still allocate heap space to maintain our program’ runtime. So I can compact the whole heap and then make the whole heap as a new heap. And I can use mark-compact or reference counting as the algorithm for the whole heap. So a generational garbage collector would become a simple reference counting collector or mark compact collector. Two generations become one generation. But this is just an idea and I have tried to implement this idea. But the tight time and complex debugging make me abandon it finally. To avoid O(n log n) complexity, the LISP2 algorithm uses 3 different passes over the heap. In addition, heap objects must have a separate forwarding pointer slot that is not used outside of garbage collection. After standard marking, the algorithm proceeds in the following 3 passes: 1.Compute the forwarding location for live objects. (1)Keep track of a free and live pointer and initialize both to the start of heap. (2)If the live pointer points to a live object, update that object’s forwarding pointer to the current free pointer and increment the free pointer according to the object’s size. (3)Move the live pointer to the next object (4)End when the live pointer reaches the end of heap. 2.Update all pointers (1)For each live object, update its pointers according to the forwarding pointers of the objects they point to. 3.Move objects (1)For each live object, move its data to its forwarding location. This algorithm is O(n) on the size of the heap; it has a better complexity than the table-based approach, but the table-based approach’s n is the size of the used space only, not the entire heap space as in the lisp2 algorithm. However, the lisp2 algorithm is simpler to implement. Remembered sets which is based on linear hashing have a strong advantage despite the extra generational check and the hash table insertions, since they allow markedly less root processing than the other schemes. My remembered sets are implemented as circular hash tables using linear hashing. A remembered set is allocated as an array of 2^i+ k entries. To enteran item in the set,we hash the item to obtain i bits and index the table. If the indexed location is empty then the item is stored in that slot and we are done. If the location already contains the item then we are done also. Otherwise, the immediately succeeding k slots are examined to try to place the item (this is not done circularly; hence the 2^i+ k rather than simply 2^i). If an empty location still cannot be found then a circular search of the table is made to find an empty slot. The hash tables are kept relatively sparse by growing a table whenever an item cannot be placed in its natural hash slot or the k following slots, and 60% or more of the table’s slots are full. We fixed k=2 and the growth policy is to increment i (i.e., basically double the table size when a table is grown). Conclusion: There are several conclusions we draw from the results.Although the generational garbage collector can work , but there are a lot of aspects that allowed us to improve. If after the old generation’s collection, there are still not enough space to allocate, should we announce that our collector has down, or should we borrow some space from system memory. There exists a method that allow collector to borrow some space from system and we can use a method called recombination ,the collector can cut down the object’s body and put them in system’s memory, after the collector return to work, collector will take back these objects’ body and goon work. These are just several ideas of memory management , there are lots of beauty in dynamic memory management algorithm. We should suit one’s measures to local conditions .
