 | This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(July 2017) (Learn how and when to remove this message) |
Incomputer science,garbage includesdata,objects, or other regions of thememory of a computer system (or other system resources), which will not be used in any future computation by the system, or by a program running on it. Because every computer system has a finite amount of memory, and most software produces garbage, it is frequently necessary todeallocate memory that is occupied by garbage and return it to theheap, or memory pool, for reuse.
Garbage is generally classified into two types:syntactic garbage, any object or data which is within a program's memory space but unreachable from the program'sroot set; andsemantic garbage, any object or data which is never accessed by a running program for any combination of program inputs. Objects and data which are not garbage are said to belive.
Casually stated, syntactic garbage is data thatcannot be reached, and semantic garbage is data thatwill not be reached. More precisely, syntactic garbage is data that is unreachable due to the reference graph (there is no path to it), which can be determined by many algorithms, as discussed intracing garbage collection, and only requires analyzing the data, not the code. Semantic garbage is data that will not be accessed, either because it is unreachable (hence also syntactic garbage), or is reachable but will not be accessed; determining the latter requires code analysis, and is in generalundecidable.
Syntactic garbage is a (usually strict) subset of semantic garbage, as it is entirely possible for an object to hold a reference to another object without ever using that object.
In the following simplestack implementation in Java, each element popped from the stack becomes semantic garbage once there are no outside references to it:[a]
publicclassStack{privateObject[]elements;privateintsize;publicStack(intcapacity){elements=newObject[capacity];}publicvoidpush(Objecte){elements[size++]=e;}publicObjectpop(){returnelements[--size];}}
This is becauseelements[] still contains a reference to the object, but the objectwill never be accessed again through this reference, becauseelements[] is private to the class and thepop method only returns references to elements it has not already popped. (After it decrementssize, this classwill never access that element again.) However, knowing this requires analysis of the code of the class, which is undecidable in general.
If a laterpush call re-grows the stack to the previous size, overwriting this last reference, then the object will become syntactic garbage, because itcan never be accessed again, and will be eligible for garbage collection.
An example of the automatic collection of syntactic garbage, byreference counting garbage collection, can be produced using thePython command-lineinterpreter:
>>>classFoo:..."""This is an empty testing class."""...pass...>>>bar=Foo()>>>bar<__main__.Foo object at 0x54f30>>>>delbar
In this session, an object is created, its location in the memory is displayed, and the only reference to the object is then destroyed—there is no way to ever use the object again from this point on, as there are no references to it. This becomes apparent when we try to access the original reference:
>>>barTraceback (most recent call last): File"<stdin>", line1, in?NameError:name 'bar' is not defined
As it is now impossible to refer to the object, the object has become useless; it is garbage. Since Python uses garbage collection, it automatically deallocates the memory that was used for the object so that it may be used again:
>>>classBar:..."""This is another testing class."""...pass...>>>baz=Bar()>>>baz<__main__.Bar object at 0x54f30>
TheBar instance now resides at the memory location0x54f30; at the same place as where our previous object, theFoo instance, was located. Since theFoo instance was destroyed, freeing up the memory used to contain it, the interpreter creates theBar object at the same memory location as before, making good use of the available resources.
Garbage consumes heap memory, and thus one wishes to collect it (to minimize memory use, allow faster memory allocation, and prevent out-of-memory errors by reducing heap fragmentation and memory use).
However, collecting garbage takes time and, if done manually, requires coding overhead. Further, collecting garbage destroys objects and thus can cause calls tofinalizers, executing potentially arbitrary code at an arbitrary point in the program's execution. Incorrect garbage collection (deallocating memory that is not garbage), primarily due to errors in manual garbage collection (rather than errors in garbage collectors), results inmemory safety violations (that often create security holes) due to use ofdangling pointers.
Syntactic garbage can be collected automatically, and garbage collectors have been extensively studied and developed. Semantic garbage cannot be automatically collected in general, and thus causesmemory leaks even in garbage-collected languages. Detecting and eliminating semantic garbage is typically done using a specialized debugging tool called aheap profiler, which allows one to see which objects are live and how they are reachable, enabling one to remove the unintended reference.
The problem of managing the deallocation of garbage is well-known in computer science. Several approaches are taken:
| Hardware | |
|---|---|
| Virtual memory | |
| Segmentation | |
| Allocator | |
| Manual means | |
| Garbage collection | |
| Safety | |
| Issues | |
| Other | |
