Thursday, August 4, 2011

Java Threads - How They Work

What is Thread: A thread is a single sequence of instructions being executed in a java virtual machine. The instructions in two different threads have no mutual ordering, they can execute independent of each other.

How to create a thread: In java, the only way to create a thread is by creating an object of class java.lang.Thread. In reality, we can either extend the Thread class and override the method run(), or we can implement java.lang.Runnable in a separate class and pass it to Thread's constructor. This article is meant for people who have some experience with Thread programming in java. If you do not know how to do thread programming in java, there is a very good tutorial in here.

Memory Model: Every thread has its own working memory. A thread keeps a copy of all the variables it uses in its working memory. There is a master memory called the main memory, which is accessible to all the threads. It is not necessary that the working memory of a thread and the main memory be in sync. The purpose of having a working memory is to enable the JVM to do some performance optimization. It does not matter where the local variables are stores, because they are only accessible to one thread.

Operations by Thread and Main Memory: The following operations are defined for a thread.
  1. use: thread gets the value of a variable in its working memory
  2. assign: thread puts the value of a variable in its working memory
  3. load: fetches the value of a variable from main memory into the same variable in the working copy after read operation by main memory
  4. store: syncs the value of a variable in working copy to the same variable in the main memory by a subsequent write operation by the main memory.

The main memory on the other hand can do the following.
  1. read: reads the value of a variable so that a thread can perform a load
  2. write: writes the value into a variable after a store by a thread.
Note that synchronizing a variable's value is a two step process, one taken by the thread, and the other taken by the main memory. It is guaranteed that the load operation is always preceded by a read and a store operation is always followed by a writes operation. There can be a delay between the read and the load or the store and the write. Though there may be some delay between the operation of the thread and the operation of the main memory (called the transit time), the operations on a single variable by main memory is guaranteed to maintain order. That is to say that if a load has been requested after a store on a variable, the corresponding read must happen after the write operation.

Rules on Variables: Operations on variables must follow the following rules.
  1. The use and assign operations are done based on program logic and in the same order as they appear in the program
  2. There must be a store operation between a load and an assign. This makes sure that the thread does not lose any update
  3. There must be an assign between a load and store. The thread is not allowed to make unnecessary sync
  4. Before a variable is used or stored first time in the thread, there must be a load or assign to that variable
  5. If a new variable is created, it must be either assigned or loaded before it is stored or used
  6. A load operation always has a corresponding read operation before it
  7. A store operation always has a corresponding write operation after it

Locks and Operations: Every object is associated with a lock, and so is every class. However, unlike variables, locks have only one copy in the main memory. It does not make sense for a lock to have a copy in the thread's working memory, and that does not happen either. At a time only one thread can get hold of an object's lock. When a thread has obtained the object's lock, it can perform any number of additional lock operations on the same object. The object's lock is released when an equal number of unlock happens on the object. Thus conceptually, the locking operations on an object are nested.

If multiple threads attempt to acquire the lock of the same object, only one of them gets it, and the other others must wait until the thread that started it have relinquished the lock.

In java, there is no syntax to directly lock or unlock an object. Locking and unlocking is achieved by the synchronized keyword. A code block can be synchronized on an object. A thread must get hold of a lock before it executes the code inside the block. The lock gets released after the code in the synchronized block finishes executing.

When a thread gets hold of a lock, it immediately loads all its variables, and the just before the lock is relinquished, all the variables in the working copy are synced in the main memory. This is not exactly true, but has the same effect as of the following rules.

  1. Before an unlock happens, all the variables that are assigned to are stored in the main memory.
  2. After a lock happens, any variable used must be first loaded from the main memory

Prescient Store Operations: Every assign operation might have a corresponding store operation. It is permissible for a thread to do the store before the assign operation, provided it does not change the effect. Which means, if such an out-of-order store happens, an assign must also happen. It is not allowable to first do the store and then throw an exception before the assign happens. This kind of a write is called prescient store operation.

Volatile Variable: A field variable can be declared volatile with the volatile keyword. A volatile variable has much stringent rules for synchronizing between the main memery and the thread's working memory. For a volatile variable, the use operation is tightly coupled with the load operation and the assign operation is tightly coupled with the store operation. These are as stated in the rules below.

  1. The use operation is only permitted if the previous operation in the thread is a load for the same variable. An load is only permitted if the next operation is an use of the same variable
  2. The assign is only permitted if the next operation is the store of the same variable. A store operation is permitted only if the previous operation is assign of the same variable

Effectively, volatile variable gives the impression that it is not even stored in the working memory, that it is always directly accessed from the main memory. The following two programs will give a visible difference.

Note that all programs below deliberately contain infinite loop. Press ctrl+c to exit any program.

In, the change done by the set thread is scarcely visible to the display thread. This is why "whoa" is printed only a very few times, if at all. On the other hand, in, the variable x is declared volatile causing the changes to it visible to all other threads. This causes a frequent printing of "whoa".

Nonatomic Operations in double and long Variables: Due to some hardware restrictions etc., a JVM is allowed to treat the basic assign or use operations on double and long to be non-atomic, ie. a combination of two operations of 32 bits a time. However, this is not allowed in case of volatile variables. The following programs show example. Note that you might have to run the program a few times before you see the result. The operations are allowed to be non-atomic, but not required to be so. Also if you have a 64 bit JVM, it might not work at all.

Sometimes you will see prints like the following


Where do those values come from? We have never assigned those values. They are result of the assignment of x being non-atomic. Sometimes only 32 bits are assigned leaving the other 32 bits unchanged, causing those values. In the second program, since the variable x is declared volatile, this never happens. Thus in that case, nothing is ever printed.

Wait-sets and Notifications: Along with a lock, an object also has a wait-set which is a set of threads. These are threads waiting on that object. Every object has a wait() method. It can be called from a thread that already has obtained the lock of that object. Otherwise, an IllegalMonitorStateException will be thrown. When this method is invoked by this thread, the lock is temporarily relinquished, the thread is barred from competing for processor time and the thread is added to the wait-set of the object. The thread remains this way until one of the following happens
  1. Any other thread, which has obtained the lock on that object calls the notify() method on the object and this thread is chosen by the JVM to get the notification.
  2. Any other thread, which has obtained the lock on that object calls the notifyAll() method on the object.
  3. The wait() method was called with a maximum wait period, and the time period has passed.

When the thread comes back from the wait-set of the object, it must first compete for the lock on the same object. When it gets the lock again, it gets back the state it has before it called the wait() method on the object. Reference: Java Virtual Machine Specification - Threads and Locks


Post a Comment