The synchronization problem

While multi-threaded program provide a huge performance advantage, this advantage comes with complications related to concurrent modification of shared memory. The following program creates several threads, each modifying the same object in the memory. Note how the modifications are inconsistent.

    class Data {
        long i=0;
        void increment() {
            i=i+1;
        }
    }

    /**Does incrementation given many times on given Data instance */
    class Incrementer implements Runnable {
        Data d;
        long c;
        Incrementer(Data d,long c) {
            this.d=d;
            this.c=c;
        }
        public void run() {
            while(c>0) {
                d.increment();
                c--;
            }
        }

        public static void main(String[] args) {
            Data d=new Data();
            long c=10000000;
            int numthreads=Integer.parseInt(args[0]);
            Incrementer[] incrementers=new Incrementer[numthreads];
            Thread[] threads=new Thread[incrementers.length];
            for(int j=0; j<incrementers.length;j++) {
                incrementers[j]=new Incrementer(d,c);
                threads[j]=new Thread(incrementers[j]);
            }
            for(int j=0; j<incrementers.length;j++) 
                threads[j].start();
            try {
                for(int j=0; j<incrementers.length;j++) {
                    threads[j].join();
                }
                System.console().format("Total increments %,d\n",c*numthreads);
                System.console().format("Data increments %,d\n",d.i);
                System.exit(0);
            } catch  (InterruptedException e) {
                System.out.println(e);
            }

        }
    }

When the program is run with 5 threads it produces an output as follows:

    $ java Incrementer 5
    Total increments 50,000,000
    Data increments 13,087,155

The source of synchronization problem

The synchronization problem exists because modifications to shared objects are not atomic operations. Consider the line in the above program's Data class,:

    i=i+1;

Execution of the above command is not atomic, but instead consists of three steps in the CPU:

  1. obtain current calue of i
  2. add 1 to the value
  3. put obtained sum in i

Now consider a situation where a thread enters step 1 above while another is executing step 2! They will start off with the same starting value of i, increment it, but at the end i will end up being incremented only with 1.

Critical section

Sections of the program which is problematic against such concurrent modifications are called critical sections. Multi-threaded programs must be guarded, somehow, against entering critical sections at the same time. In other words, the whole critical section must be turned into an atomic operation.

The Lock concept to protect critical sections

See Dijkstra's 1965 paper titled "Solution of a Problem in Concurrent Programming Control".

Applying locks

The ReentrantLock class in java.util.locks library implements what Dijktra describes. It is used as follows:

    import java.util.concurrent.locks.*;

    class Data {
        long i=0;
        Lock lock=new ReentrantLock();
        void increment() {
            lock.lock();
            i=i+1;
            lock.unlock();
        }
    }

    class Incrementer implements Runnable {
        Data d;
        long c;
        Incrementer(Data d,long c) {
            this.d=d;
            this.c=c;
        }
        public void run() {
            while(c>0) {
                d.increment();
                c--;
            }
        }

        public static void main(String[] args) {
            Data d=new Data();
            long c=10000000;
            int numthreads=Integer.parseInt(args[0]);
            Incrementer[] incrementers=new Incrementer[numthreads];
            Thread[] threads=new Thread[incrementers.length];
            for(int j=0; j<incrementers.length;j++) {
                incrementers[j]=new Incrementer(d,c);
                threads[j]=new Thread(incrementers[j]);
            }
            for(int j=0; j<incrementers.length;j++) 
                threads[j].start();
            try {
                for(int j=0; j<incrementers.length;j++) {
                    threads[j].join();
                }
                System.console().format("Total increments %,d\n",c*numthreads);
                System.console().format("Data increments %,d\n",d.i);
                System.exit(0);
            } catch  (InterruptedException e) {
                System.out.println(e);
            }

        }
    }

Java's synchronized code blocks

The Object class, hence every reference type value in Java, has an instance of ReentrantLock embedded in it. Java synchronized modifier makes use of that lock.

The above code can be written as:

    class Incrementer implements Runnable {
        Data d;
        long c;
        Incrementer(Data d,long c) {
            this.d=d;
            this.c=c;
        }
        public void run() {
            while(c>0) {
                synchronized (d) { //EQUIVALENT TO ACQUIRING THE HIDDEN LOCK OF d
                    d.increment();
                }                  //EQUIVALENT TO UNLOCKING THE HIDDEN LOCK OF d
                c--;
            }
        }

synchronized methods

synchronized modifier can be also used as a method modifier which then used this object's lock. Therefore, the below code is an equivalent use of object lock:

    class Data {
        long i=0;
        Lock lock=new ReentrantLock();
        synchronized void increment() {//EQUIVALENT TO ACQUIRING THE HIDDEN LOCK OF this
            i=i+1;
        }                               //EQUIVALENT TO UNLOCKING THE HIDDEN LOCK OF this
    }

NOTE: If the synchronized modifier is used in front of a static method, its object of synchronization is the class, not the instance!