Next most important thread lesson – Synchronisation.

The term atomic is related to the atom, once considered the smallest possible unit of matter, unable to be broken into separate parts. When a routine is considered atomic, it cannot be interrupted during its execution. This can either be accomplished in hardware or simulated in software. In general, atomic instructions are provided in hardware that is used to implement atomic routines in software. In our case, we define an atomic routine as one that can’t be found in an intermediate state. Atomicity is very important to avoiding race conditions.

Thread Interference

Consider a simple class called Counter

class Counter {
    private int c = 0;

    public void increment() {
        c++;
    }

    public void decrement() {
        c--;
    }

    public int value() {
        return c;
    }

}

Counter is designed so that each invocation of increment will add 1 to c, and each invocation of decrement will subtract 1 from c. However, if a Counter object is referenced from multiple threads, interference between threads may prevent this from happening as expected.

Interference happens when two operations, running in different threads, but acting on the same data, interleave. This means that the two operations consist of multiple steps, and the sequences of steps overlap.

It might not seem possible for operations on instances of Counter to interleave, since both operations on c are single, simple statements. However, even simple statements can translate to multiple steps by the virtual machine. We won’t examine the specific steps the virtual machine takes — it is enough to know that the single expression c++ can be decomposed into three steps:

1. Retrieve the current value of c.
2. Increment the retrieved value by 1.
3. Store the incremented value back in c.

The expression c-- can be decomposed the same way, except that the second step decrements instead of increments.

Suppose Thread A invokes increment at about the same time Thread B invokes decrement. If the initial value of c is 0, their interleaved actions might follow this sequence:

1. Thread A: Retrieve c.
2. Thread B: Retrieve c.
3. Thread A: Increment retrieved value; result is 1.
4. Thread B: Decrement retrieved value; result is -1.
5. Thread A: Store result in c; c is now 1.
6. Thread B: Store result in c; c is now -1.

Thread A’s result is lost, overwritten by Thread B. This particular interleaving is only one possibility. Under different circumstances it might be Thread B’s result that gets lost, or there could be no error at all. Because they are unpredictable, thread interference bugs can be difficult to detect and fix.

Race Condition:

A race condition occurs when the order of execution of two or more threads may affect some variable or outcome in the program. It may turn out that all the different possible thread orderings have the same final effect on the application: the effect caused by the race condition may be insignificant, and may not even be relevant. For example, a character lost in the AsyncReadSocket may not affect the final outcome of the program. Alternately, the timing of the threading system may be such that the race condition never manifests itself, despite the fact that it exists in the code.

A race condition is a problem that is waiting to happen. Simple changes in the algorithm can cause race conditions to manifest themselves in problematic ways. And, since different virtual machines will have different orderings of thread execution, the developer should never let a race condition exist even if it is currently not causing a problem on the development system.

Memory Consistency Errors

Memory consistency errors occur when different threads have inconsistent views of what should be the same data. The causes of memory consistency errors are complex and beyond the scope of this tutorial. Fortunately, the programmer does not need a detailed understanding of these causes. All that is needed is a strategy for avoiding them.

The key to avoiding memory consistency errors is understanding the happens-before relationship. This relationship is simply a guarantee that memory writes by one specific statement are visible to another specific statement. To see this, consider the following example. Suppose a simple int field is defined and initialized:

int counter = 0;

The counter field is shared between two threads, A and B. Suppose thread A increments counter:

counter++;

Then, shortly afterwords, thread B prints out counter:

System.out.println(counter);

If the two statements had been executed in the same thread, it would be safe to assume that the value printed out would be “1″. But if the two statements are executed in separate threads, the value printed out might well be “0″, because there’s no guarantee that thread A’s change to counter will be visible to thread B — unless the programmer has established a happens-before relationship between these two statements.

There are several actions that create happens-before relationships. One of them is synchronization, as we will see in the following sections.

We’ve already seen two actions that create happens-before relationships.

• When a statement invokes Thread.start, every statement that has a happens-before relationship with that statement also has a happens-before relationship with every statement executed by the new thread. The effects of the code that led up to the creation of the new thread are visible to the new thread.

• When a thread terminates and causes a Thread.join in another thread to return, then all the statements executed by the terminated thread have a happens-before relationship with all the statements following the successful join. The effects of the code in the thread are now visible to the thread that performed the join.

The Solution: Synchronisation

The Java specification provides certain mechanisms that deal specifically with this problem. The Java programming language provides two basic synchronization idioms: synchronized methods and synchronized statements.

The Java language provides the synchronized keyword; in comparison with other threading systems, this keyword allows the programmer access to a resource that is very similar to a mutex lock. For our purposes, it simply prevents two or more threads from calling our deduct() method at the same time:

public class Account {
private float total;

public synchronized boolean deduct(float t) {
if (t <= total) {
total -= t;
return true;
}
return false;
}
}

By declaring the method as synchronized, if two users decide to access the method at the same time, the first user executes the deduct() method while the second user waits until the first user completes the deduct() method. Since only one user may execute the deduct() method at a time, the race condition is eliminated. The effects can be effectively said to have the following impact:

• First, it is not possible for two invocations of synchronized methods on the same object to interleave. When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods for the same object block (suspend execution) until the first thread is done with the object.

• Second, when a synchronized method exits, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method for the same object. This guarantees that changes to the state of the object are visible to all threads.

Note: that constructors cannot be synchronized — using the synchronized keyword with a constructor is a syntax error. Synchronizing constructors doesn’t make sense, because only the thread that creates an object should have access to it while it is being constructed.

Warning: When constructing an object that will be shared between threads, be very careful that a reference to the object does not “leak” prematurely. For example, suppose you want to maintain a List called instances containing every instance of class. You might be tempted to add the line

instances.add(this);

to your constructor. But then other threads can use instances to access the object before construction of the object is complete.

With Java, there is a lock created in every object in the system. When a method is declared synchronized, the executing thread must grab the lock assigned to the object before it can continue. Upon completion of the method, the mechanism automatically releases the lock. Under the covers, the concept of synchronization is simple: when a method is declared as synchronized, it must have a token, which we call a lock. Once the method has acquired this lock (we may also say the lock has been checked out or grabbed), it executes the method and releases (we may also say returns) the lock once the method is finished. No matter how the method returns—including via an exception—the lock is released. There is only one lock per object, so if two separate threads try to call synchronized methods of the same object, only one can execute the method immediately; the other thread has to wait until the first thread releases the lock before it can execute the method.

Synchronized methods enable a simple strategy for preventing thread interference and memory consistency errors: if an object is visible to more than one thread, all reads or writes to that object’s variables are done through synchronized methods. (An important exception: final fields, which cannot be modified after the object is constructed, can be safely read through non-synchronized methods, once the object is constructed) This strategy is effective, but can present problems with liveness, as we’ll see later in this lesson.

The JVM organizes the data of a running Java application into several runtime data areas: one or more Java stacks, a heap, and a method area.

Inside the Java virtual machine, each thread is awarded a Java stack, which contains data no other thread can access, including the local variables, parameters, and return values of each method the thread has invoked. The data on the stack is limited to primitive types and object references. In the JVM, it is not possible to place the image of an actual object on the stack. All objects reside on the heap.

There is only one heap inside the JVM, and all threads share it. The heap contains nothing but objects. There is no way to place a solitary primitive type or object reference on the heap — these things must be part of an object. Arrays reside on the heap, including arrays of primitive types, but in Java, arrays are objects too.

Besides the Java stack and the heap, the other place data may reside in the JVM is the method area, which contains all the class (or static) variables used by the program. The method area is similar to the stack in that it contains only primitive types and object references. Unlike the stack, however, the class variables in the method area are shared by all threads.

Intrinsic Locks and Synchronization

Synchronization is built around an internal entity known as the intrinsic lock or monitor lock. (The API specification often refers to this entity simply as a “monitor.”) Intrinsic locks play a role in both aspects of synchronization: enforcing exclusive access to an object’s state and establishing happens-before relationships that are essential to visibility.

Object and class locks

As described above, two memory areas in the Java virtual machine contain data shared by all threads. These are:

 

• The heap, which contains all objects
• The method area, which contains all class variables

If multiple threads need to use the same objects or class variables concurrently, their access to the data must be properly managed. Otherwise, the program will have unpredictable behavior.

Class locks are actually implemented as object locks. When the JVM loads a class file, it creates an instance of class java.lang.Class. When you lock a class, you are actually locking that class’s Class object. More on that later.

Every object has an intrinsic lock associated with it. By convention, a thread that needs exclusive and consistent access to an object’s fields has to acquire the object’s intrinsic lock before accessing them, and then release the intrinsic lock when it’s done with them. A thread is said to own the intrinsic lock between the time it has acquired the lock and released the lock. Note that threads need not obtain a lock to access instance or class variables. However, as long as a thread owns an intrinsic lock, no other thread can acquire the same lock. The other thread will block when it attempts to acquire the lock.

When a thread releases an intrinsic lock, a happens-before relationship is established between that action and any subsequent acquistion of the same lock.

JVM and Lock Management:

To coordinate shared data access among multiple threads, the Java virtual machine associates a lock with each object and class. A lock is like a privilege that only one thread can “possess” at any one time. If a thread wants to lock a particular object or class, it asks the JVM. At some point after the thread asks the JVM for a lock — maybe very soon, maybe later, possibly never — the JVM gives the lock to the thread. When the thread no longer needs the lock, it returns it to the JVM. If another thread has requested the same lock, the JVM passes the lock to that thread.

Definition: Mutex Lock

A mutex lock is also known as a mutually exclusive lock. This type of lock is provided by many threading systems as a means of synchronization. Basically, it is only possible for one thread to grab a mutex at a time: if two threads try to grab a mutex, only one succeeds. The other thread has to wait until the first thread releases the lock; it can then grab the lock and continue operation.

Monitors

The JVM uses locks in conjunction with monitors. A monitor is basically a guardian in that it watches over a sequence of code, making sure only one thread at a time executes the code.

Each monitor is associated with an object reference. When a thread arrives at the first instruction in a block of code that is under the watchful eye of a monitor, the thread must obtain a lock on the referenced object. The thread is not allowed to execute the code until it obtains the lock. Once it has obtained the lock, the thread enters the block of protected code.

When the thread leaves the block, no matter how it leaves the block, it releases the lock on the associated object.

Multiple locks or Reentrant Synchronization

Recall that a thread cannot acquire a lock owned by another thread. But a thread can acquire a lock that it already owns. Allowing a thread to acquire the same lock more than once enables reentrant synchronization. This describes a situation where synchronized code, directly or indirectly, invokes a method that also contains synchronized code, and both sets of code use the same lock. Without reentrant synchronization, synchronized code would have to take many additional precautions to avoid having a thread cause itself to block.

Which implies, that a single thread is allowed to lock the same object multiple times. For each object, the JVM maintains a count of the number of times the object has been locked. An unlocked object has a count of zero. When a thread acquires the lock for the first time, the count is incremented to one. Each time the thread acquires a lock on the same object, a count is incremented. Each time the thread releases the lock, the count is decremented. When the count reaches zero, the lock is released and made available to other threads.

Actual Implementation:

Two opcodes, monitorenter and monitorexit, are used for synchronization blocks within methods, as shown in the table below.

MONITORS

Opcode	Operand(s)	Description

When monitorenter is encountered by the Java virtual machine, it acquires the lock for the object referred to by objectref on the stack. If the thread already owns the lock for that object, a count is incremented. Each time monitorexit is executed for the thread on the object, the count is decremented. When the count reaches zero, the monitor is released.

Scope of a lock:

The scope of a lock is defined as the period of time between when the lock is grabbed and released. In our examples so far, we have used only synchronized methods; this means that the scope of these locks is the period of time it takes to execute these methods. This is referred to as method scope.

Synchronized Statements

To create a synchronized statement, you use the synchronized keyword with an expression that evaluates to an object reference. Unlike synchronized methods, synchronized statements must specify the object that provides the intrinsic lock:

public void addName(String name) {
    synchronized(this) {
        lastName = name;
        nameCount++;
    }
    nameList.add(name);
}

In the case above, the statements contained within the synchronized block will not be executed until a lock is acquired on the current object (this). If instead of a this reference, the expression yielded a reference to another object, the lock associated with that object would be acquired before the thread continued.

In this example, the addName method needs to synchronize changes to lastName and nameCount, but also needs to avoid synchronizing invocations of other objects’ methods. (Invoking other objects’ methods from synchronized code can create liveness problems) .Without synchronized statements, there would have to be a separate, unsynchronized method for the sole purpose of invoking nameList.add.

Synchronized statements are also useful for improving concurrency with fine-grained synchronization. Suppose, for example, class MsLunch has two instance fields, c1 and c2, that are never used together. All updates of these fields must be synchronized, but there’s no reason to prevent an update of c1 from being interleaved with an update of c2 — and doing so reduces concurrency by creating unnecessary blocking. Instead of using synchronized methods or otherwise using the lock associated with this, we create two objects solely to provide locks.

public class MsLunch {
    private long c1 = 0;
    private long c2 = 0;
    private Object lock1 = new Object();
    private Object lock2 = new Object();

    public void inc1() {
        synchronized(lock1) {
            c1++;
        }
    }

    public void inc2() {
        synchronized(lock2) {
            c2++;
        }
    }
}

Use this idiom with extreme care.You must be absolutely sure that it really is safe to interleave access of the affected fields.

Note: How does a synchronized method behave in conjunction with a nonsynchronized method?
Simply put, a synchronized method tries to grab the object lock, and a nonsynchronized method doesn’t. This means it is possible for many nonsynchronized methods to run in parallel with a synchronized method. Only one synchronized method runs at a time.

Note that a catch clause ensures the locked object will be unlocked even if an exception is thrown from within the synchronized block. No matter how the synchronized block is exited, the object lock acquired when the thread entered the block definitely will be released.

Synchronized methods

To synchronize an entire method, you just include the synchronized keyword as one of the method qualifiers, as in:

class HeatSync {

    private int[] intArray = new int[10];

    synchronized void reverseOrder() {
        int halfWay = intArray.length / 2;
        for (int i = 0; i < halfWay; ++i) {
            int upperIndex = intArray.length - 1 - i;
            int save = intArray[upperIndex];
            intArray[upperIndex] = intArray[i];
            intArray[i] = save;
        }
    }
}

The JVM does not use any special opcodes to invoke or return from synchronized methods. When the JVM resolves the symbolic reference to a method, it determines whether the method is synchronized. If it is, the JVM acquires a lock before invoking the method. For an instance method, the JVM acquires the lock associated with the object upon which the method is being invoked. For a class method, it acquires the lock associated with the class to which the method belongs. After a synchronized method completes, whether it completes by returning or by throwing an exception, the lock is released.
You might wonder what happens when a static synchronized method is invoked, since a static method is associated with a class, not an object. In this case, the thread acquires the intrinsic lock for the Class object associated with the class. Thus access to class’s static fields is controlled by a lock that’s distinct from the lock for any instance of the class.

Synchronized Method Versus Synchronized Block: Which to use?

It is actually possible to use only the synchronized block mechanism, even when we need to synchronize the whole method. Picking the whole method is the simplest technique, but , it is possible to have deadlock because the scope is too large. It may also be inefficient to hold a lock for the section of code where it is actually not needed.

Using the synchronized block mechanism may also be a problem if too many locks are involved. As we shall see, it is possible to have a deadlock condition if we require too many locks to be grabbed. There is also an overhead in grabbing and releasing the lock, so it may be inefficient to free a lock just to grab it again a few lines of code later.

Synchronizing Static Methods

So far, we kept referring to “obtaining the object lock.” But what about static methods? When a synchronized static method is called, which object are we referring to? A static method does not have a concept of the this reference. It is not possible to obtain the object lock of an object that does not exist. So how does synchronization of static methods work?

To answer this question, we will introduce the concept of a class lock. Just as there is an object lock that can be obtained for each instance of a class (object), there is a lock that can be obtained for each class. We will refer to this as the class lock . In terms of implementation, there is no such thing as a class lock, but it is a useful concept to help us understand how this all works.

When a static synchronized method is called, the program obtains the class lock before calling the method. This mechanism is identical to the case in which the method is not static; it is just a different lock. The same rule applies: if a synchronized static method calls another synchronized static method of the same class, the system is smart enough to support the nesting of class locks.

But how is the class lock related to the object lock? Apart from the functional relationship between the two locks, they are not operationally related at all. These are two distinct locks. The class lock can be grabbed and released independently of the object lock. If a nonstatic synchronized method calls a static synchronized method, it acquires both locks. Achieving deadlock between these two locks is a little difficult (but not impossible) to accomplish since a static method cannot call a nonstatic method without an object reference.

If a synchronized static method has access to an object reference, can it call synchronized methods of that object or use the object to lock a synchronized block? Yes: in this case the program first acquires the class lock when it calls the synchronized static method and then acquires the object lock of the particular object:

public class MyStatic {
public synchronized static void staticMethod(MyStatic obj) {
// Class lock acquired
obj.nonStaticMethod();
synchronized (obj) {
// Class and object locks acquired
}
}
public synchronized void nonStaticMethod() {
// Object lock acquired
}
}

Can a nonstatic method grab the static lock without calling a synchronized static method? In other words, can a synchronized block apply to the class lock? For example, something like this:

public class ClassExample {
synchronized void process() {
synchronized (the class lock) {
// Code to access static variables of the class
}
}
}

The main reason for a nonstatic method to grab a class lock is to prevent a race condition for variables that apply to the class (i.e., static variables). This can be accomplished by calling a static synchronized method of the class. If for some reason this is not desired, we can also use the synchronized block mechanism on a common static object (using a static instance variable would probably be the best technique for storing such a common object). For example, we could use an object stored in a common location that can be accessed by all objects of a particular class type:

public class ClassExample {
private static Object lockObject = new Object();
synchronized void process() {
synchronized (lockObject) {
// Code to access static variables of the class
}
}
}

The Class Lock and the Class Object

In this example, we are using the object lock of the Class object as a common lock for the class. We are using this object because there is a one-to-one correspondence of class objects and classes in the system. We have also mentioned that when a synchronized static method is called, the system will grab the class lock.

It turns out that there is actually no such thing as a class lock. When a synchronized static method is called, the system grabs the object lock of the class object that represents the class. This means the class lock is the object lock of the corresponding class object. Using both static synchronized methods and synchronized blocks that use the class object lock can cause confusion.

Finally, if creating a new object is not desired, you may also obtain the class object (that is, the instance of the java.lang.Class class) that represents the class itself. Objects of this class are used to represent classes in the system. For our purposes, we are using this class because there is a one-to-one ratio of classes and objects of the Class class that represents the classes. This class object can be obtained as follows:

public class ClassExample {
synchronized void process() {
synchronized (Class.forName(“ClassExample”)) {
// Code to access static variables of the class
}
}
}

A call to the forName() method of the Class class returns this object. We can then use this class object as the locking object via the synchronized block mechanism.

---

Possibly related posts: (automatically generated)

• Matter is made of atoms!
• Ancient Computing Revolution