Generational Garbage Collection

Why It needed?

      1.    Most objects die young.

      2.    Over 90% garbage collected in a GC is newly created post the previous GC cycle.

Mark and compact all the objects in a JVM is inefficient. As more and more objects are allocated, the list of objects grows and grows leading to longer and longer garbage collection time. However, empirical analysis of applications has shown that most objects are short lived.

Generational garbage collection is tracing garbage collection that makes use of the generational hypothesis. Objects are gathered together in generations. New objects are allocated in the youngest or nursery generation, and promoted to older generations if they survive. Objects in older generations are condemned less frequently, saving CPU time.

JVM Generations

YoungGen : It is place where lived for short period and divided in two parts:

à Eden Space(heap) : When object created using new keyword memory allocated on this space.

àSurvivor Space(heap) : The pool containing objects that have survived the garbage collection of the Eden space.

Tenured Generation(heap) : This memory pool contains objects which survived after multiple garbage collection means object which survived after garbage collection from Survivor space.

   à OldGen : This pool is basically contain tenured and virtual (reserved) space and will be holding those objects which survived after garbage collection from YoungGen space.

Permanent Generation : This memory pool contain permanent class metadata and descriptors information so PermGen space always reserved for classes and those that is tied to the classes for example static members.

Java8 Update: PermGen is replaced with Metaspace which is very similar.
Main difference is that Metaspace re-sizes dynamically i.e., It can expand at runtime.
Java Metaspace space: unbounded (default).

Code Cache (Virtual or reserved) : If you are using HotSpot Java VM this includes code cache area that containing memory which will be used for compilation and storage of native code.

The information gathered from the object allocation behavior can be used to enhance the performance of the JVM. Therefore, the heap is broken up into smaller parts or generations.

Young Generation is where all new objects are allocated and aged. When the young generation fills up, this causes a minor garbage collection. A young generation full of dead objects is collected very quickly. Some surviving objects are aged and eventually move to the old generation.

Stop the World Event - All minor garbage collections are "Stop the World" events. This means that all application threads are stopped until the operation completes. Minor garbage collections are always Stop the World events.

Old Generation is used to store long surviving objects. A threshold is set for young generation object, if object survived more meet the threshold then object gets moved to the old generation. This event is called a major garbage collection.

Major garbage collection are also Stop the World events. Often a major collection is much slower because it involves all live objects.

Major garbage collections should be minimized. The length of the Stop the World event for a major garbage collection is affected by the kind of garbage collector that is used for the old generation space.

The Permanent generation contains metadata required by the JVM to describe the classes and methods used in the application. The permanent generation is populated by the JVM at runtime based on classes in use by the application. In addition, Java SE library classes and methods may be stored here.

Classes may get collected (unloaded) if the JVM finds they are no longer needed and space may be needed for other classes. The permanent generation is included in a full garbage collection.

Object in different generations

First, any new objects are allocated to the Eden space. Both survivor spaces start out empty.

    

When the Eden space fills up, a minor garbage collection is triggered.

Referenced objects are moved to the first survivor space. Unreferenced objects are deleted when the Eden space is cleared.

At the next minor GC, the same thing happens for the Eden space. Unreferenced objects are deleted and referenced objects are moved to a survivor space.

At the next minor GC, the same process repeats. However this time the survivor spaces switch. Referenced objects are moved to S0. Surviving objects are aged. Eden and S1 are cleared.

This slide demonstrates promotion. After a minor GC, when aged objects reach a certain age threshold (8 in this example) they are promoted from young generation to old generation.

As minor GCs continue to occur objects will continue to be promoted to the old generation space.

               

So that pretty much covers the entire process with the young generation. Eventually, a major GC will be performed on the old generation which cleans up and compacts that space.

  

Garbage Collection

Garbage collection is the process of looking at heap memory, identifying which objects are in use and which are not, and deleting the unused objects.

An in use object, or a referenced object (program still maintains a pointer to that object).

An unused object, or unreferenced object (no longer referenced by any part of program). So the memory used by an unreferenced object can be reclaimed.

Step 1: Marking

This is where the garbage collector identifies which pieces of memory are in use and which are not.

                     

All objects are scanned in the marking phase to make this determination. This can be a very time consuming process if all objects in a system must be scanned.

Step 2: Normal Deletion

Normal deletion removes unreferenced objects leaving referenced objects and pointers to free space.

         

The memory allocator holds references to blocks of free space where new object can be allocated.

Step 2a: Deletion with Compacting

To make new memory allocation easier and faster, we can compact (by moving referenced object together) the remaining referenced objects along with deletion of unreferenced objects.

Instance (non-static) variable cannot be called from static method

Compiler error: "non-static variable cannot be referenced from a static context".

Static variable in Java belongs to Class and its value remains same for all instances.

public class Test {

       int var = 0;

       public static void main(String args[] ) {

              ++var; // Cannot make a static reference to the non-static field count

       }

}

Initialization:

Static variable: class is loaded into JVM.

Instance variable: They get created when instance of an object is created either by using new() operator or using reflection like Class.newInstance() and has different value for each instances.

So if you try to access a non-static variable without any instance compiler will complain because those variables are not yet created and they don't have any existence until an instance is created and they are associated with any instance. So this may be the reason which makes sense to disallow non static or instance variable inside static context is non-existence of instance.

Since code in static context can be run even without creating any instance of class, it does not make sense asking value for a specific instance which is not yet created.

Daemon threads

Daemon threads in Java are like a service providers for other threads or objects running in the same process as the daemon thread.

Example of daemon thread is the garbage collection.

Daemon threads are used for background supporting tasks and are only needed while normal threads are executing. If normal threads are not running and remaining threads are daemon threads then the interpreter exits.

A daemon thread is a thread that does not prevent the JVM from exiting when the program finishes but the thread is still running.

setDaemon(true/false): This method is used to specify that a thread is daemon thread.

public boolean isDaemon(): This method is used to determine the thread is daemon thread or not.

class WorkerThread extends Thread {

     public WorkerThread() {

         setDaemon(true);

         /**When false (user thread) the Worker thread continues to run.

          * When true (daemon thread) the Worker thread terminates

          * when the main thread terminates.

          **/

     }

     public void run() {

         int count=0 ;

         while (true) {

            System.out.println("Hello from Worker "+count++) ;

            try {

                  sleep(5000);

            } catch (InterruptedException e) {}

         }

     }

}

public class DaemonTest {

     public static void main(String[] args) {

            new WorkerThread().start();

            try {

                   Thread.sleep(7500);

            } catch (InterruptedException e) {

                   System.out.println("Interrupted Exception");

            }

            System.out.println("Main Thread ending") ;

      }

}

Output:

Hello from Worker 0

Hello from Worker 1

Main Thread ending

Points to remember:

Default nature of a thread is non daemon because Thread inherits its daemon nature from the Thread which creates it i.e. parent Thread and since main thread (Thread class) is a non-daemon thread.

A thread will remain non-daemon until explicitly made daemon by calling setDaemon(true).

Thread should setDaemon before start it otherwise It will throw IllegalThreadStateException if corresponding Thread is already started and

running.

Difference between Daemon and Non Daemon:

JVM doesn’t wait for any daemon thread to finish before existing.

Daemon Threads are treated differently than User Thread when JVM terminates, finally blocks are not called, Stacks are not unwounded and JVM just exits.

Longest Repeating Subsequence

Find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., any i’th character in the two subsequences shouldn’t have the same index in the original string.

Examples:

inputStr = "abc"

Output: 0

inputStr = "aab"

Output: 1

aab

 aab

inputStr = "aabb"

Output: 2

a a b b

  a a b b

if(inputChars[i-1]==inputChars[j-1] && i!=j) {

         dp[i][j] = dp[i-1][j-1]+1;

} else {

         dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

}

package geeks.dp;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class LongestRepeatingSubsequence {

       public static void main(String[] args) throws IOException {

                 BufferedReader buffReader = new BufferedReader(

                                             new InputStreamReader(System.in));

                 char[] inputChars = buffReader.readLine().toCharArray();

                 int length = inputChars.length;

                

                 int[][] dp = new int[length+1][length+1];

                 for (int i = 1; i <= length; i++) {

                          for (int j = 1; j <= length; j++) {

                                   if(inputChars[i-1]==inputChars[j-1] && i!=j) {

                                       dp[i][j] = dp[i-1][j-1]+1;

                                   } else {

                                       dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);

                                   }

                          }

                 }

                 System.out.println(dp[length][length]);

         }

}