how does garbage collector work? what algorithm does it use?

• CS 61B Lecture 38: Garbage Collection

http://www.youtube.com/watch?v=rp8PvFvSO_c

• Java Programming - Garbage Collection - Video 15

http://www.youtube.com/watch?v=xxhEMb3BYng

• Lesson3 Garbage Collection

http://www.youtube.com/watch?v=YxRFcI7h3AU

• Garbage Collection Algorithms

Historically, the heap was managed explicitly by the programming
by using allocate and release function calls in a library (such as malloc/free in C, and new/delete in
C++).  Explicit memory management has been a significant source of software bugs, and programmer
pain (for example, using memory after it has been freed, freeing it twice, or forgetting to free it at all).

With automatic memory management, a programmer can request space from
the heap (eg. by instantiating a new object with a statement like “new MyObject()” in C# and Java),
and the run-time system does the job of allocating the necessary memory and releasing it to be reused when it’s no longer needed.  Automatic memory management is easier to use and less errorprone than explicit memory management, but is also usually considered to be less efficient and less
flexible.

Automatic memory management is usually implemented by the runtime system using a family of
algorithms called “garbage collection”.  Lisp was the first widespread programming language to
adopt garbage collection in the early 60s

The basic problem of garbage collection is to identify the memory which is no-longer needed by the
application, and to make it available for other allocations

Mark-sweep
The earliest and most basic garbage collection algorithm is mark-sweep garbage collection
Mark-sweep is a “stop-theworld” collector, which means that at some point when the program requests memory and none is
available, the program is stopped and a full garbage collection is performed to free up space. In marksweep, each object has a “mark-bit” which is used during the collection process to track whether the
object has been visited.

Semi-space
Semi-space garbage collection is a copying algorithm, which means that reachable
objects are relocated from one address to another during a collection.
Available memory is divided into two equal-size regions called “from-space” and “to-space”.
When there is insufficient space in to-space to fulfill an allocation, a collection is performed.

Other variations
Compacting garbage collectors typically use an algorithm like mark-sweep, but also re-arrange the
objects to coalesce free-space to avoid fragmentation.

Generational garbage collectors are designed under the assumption that objects which are created
recently are more likely to be garbage than objects which have been alive for a long time

Incremental garbage collectors attempt to minimize the pause time incurred due to a collection, at the
expense of more overhead overall relative to stop-the-world collectors.  This typically involves doing
a little bit of the GC work at every allocation

Most high-performance modern industrial GCs (including the one in Microsoft’s Common Language
Runtime) are generational mark-sweep compacting collectors, with an optional concurrent mode for
low-latency applications.

http://www.cs.washington.edu/education/courses/csep521/07wi/prj/rick.pdf

• Summary on Garbage collection in Java

1) Java Heap is divided into three generation for sake of garbage collection. These are young generation, tenured or old generation and Perm area.
2) New objects are created into young generation and subsequently moved to old generation.
3) String pool is created in Perm area of Heap, garbage collection can occur in perm space but depends upon JVM to JVM.
4) Minor garbage collection is used to move object from Eden space to Survivor 1 and Survivor 2 space and Major collection is used to move object from young to tenured generation.
5) Whenever Major garbage collection occurs application threads stops during that period which will reduce application’s performance and throughput.
6) There are few performance improvement has been applied in garbage collection in java 6 and we usually use JRE 1.6.20 for running our application.
7) JVM command line options –Xmx and -Xms is used to setup starting and max size for Java Heap. Ideal ratio of this parameter is either 1:1 or 1:1.5 based upon my experience for example you can have either both –Xmx and –Xms as 1GB or –Xms 1.2 GB and 1.8 GB.
8) There is no manual way of doing garbage collection in Java

http://javarevisited.blogspot.com/2011/04/garbage-collection-in-java.html#ixzz29y2yGnJQ