Put memory 'garbage' collection to good use
Published: 06 Oct 2002 20:41 BST
Automatic memory management allows the developer to focus on application logic (e.g., payroll, solving math problems) instead of innate details, such as memory allocation. However, popular computing languages like C and C++ didn't have a standardised method for supporting automatic memory management until very recently. Popularity and standardisation occurred with the emergence of governed virtual machines that execute intermediate languages, such as the virtual machines used to run Java or the .Net languages.
A deceptively difficult, yet interesting problem to solve is in the area of automatic memory management. Half of the problem, the act of allocating memory to a program, is relatively trivial -- the hard part is discovering when a program is truly finished with a piece of memory. Memory that is no longer needed, garbage memory, is collected by a garbage (memory) collector. The goal is to free unused memory as soon as it becomes garbage, so it can be reused later in the program if needed.
Many different types of algorithms have surfaced to handle memory management. Yet, there still is no best solution for all cases. This article discusses some of most popular garbage collector (GC) algorithms used today in the Java and .Net virtual machines. Garbage collecting algorithms work either on the fly while objects are being referenced and dereferenced, or in snapshot mode as if periodically the memory picture of the application is frozen while the collection runs and finds the garbage.
Reference counting
Probably the most intuitive automatic memory management algorithm is reference counting. If you keep track of which objects the program is referencing, those objects must still be needed. Implementing the algorithm requires that each object has a data field that is updated as to how many other program objects reference (i.e., point to) it. Any references of the object pointing to itself are ignored. If that count ever goes to zero, the object in question is considered garbage. After all, if no one references an object, it is, in effect, orphaned in memory. In terms of memory and performance, this is the most efficient way to collect garbage memory.
Unfortunately, computer scientists face an impossible problem with this algorithm. If two objects or a large chain of objects point to each other, and that set of objects is orphaned from the system, there is no obvious way to see the cycle. Since all objects involved have a reference count of at least 1, they preserve their non garbage status.
Because of this problem, reference counting isn't often used in modern VMs with any fervor. In fact, Java only uses reference counting with distributed objects (i.e., remote method invocation), which is borrowed from Modula-3's Network Objects. Distributed memory management imposes new constraints on garbage collections. Things like slow object access and references that can disappear at the drop of a network must be dealt with. Even though reference counting can leave cyclical garbage object sets alive, for performance and practicality reasons, it is more suitable for garbage collecting than other algorithms.
Mark and sweep
Mark and sweep garbage collecting seems to always be the first try when developers of new systems implement garbage collection. It is theoretically easier to implement than other systems, but keep in mind that easy is relative. This algorithm was used in many Java VMs in early versions and is still used as a subalgorithm in advanced garbage collectors today.
Mark and sweep starts by traversing all pointers from some canonical system object. That object is key to the VM, as in: If that object were to not exist, the VM is going down (i.e., the program has finished execution). Each object encountered via the pointer traversal is marked as being visited. Recursively, all pointers from all encountered objects are then traversed. In effect, this operation traverses the entire pointer reference tree rooted at the system canonical object, marking all objects marked along the way.
Once this stage is complete, the algorithm looks at its complete list of known objects in existence. If any objects are found unmarked, they are considered to be disconnected from the system (garbage).
This algorithm is clean and simple but suffers from some nagging issues. First, it requires all program execution to halt while it performs a job. Changes to the reference tree, while it is in midtraversal, compromise the algorithm. This algorithm was responsible for the pauses in execution that Java was famous for in its early days. Also, repeated sweeps cause memory fragmentation, which makes the job harder on the allocator. Eventually, a memory defrag must be run to clear up the fragmentation, causing even more pauses in execution.
Previous
Did you find this article useful?
57 out of 82 people found this useful
Digg
Slashdot
Del.ici.ous
Stumble
Reddit
