Start Concurrent: A Gentle Introduction to Concurrent Programming

In Java, the language feature which allows you to enforce mutual exclusion is the synchronized keyword. There are two ways to use this keyword: with a method or with an arbitrary block of code. In the method version, you add the synchronized modifier before the return type. Let’s imagine a class with a private String field called message which is set to be "Will Robinson!" by the constructor. Now, we define the following method.

If danger() is called five times from different threads, message will contain
"Danger, Danger, Danger, Danger, Danger, Will Robinson!" Without the synchronized keyword, danger() would suffer from a race condition similar to the one in RaceCondition. Some of the String concatenations might be overwritten by other calls to danger(). You would never have more than five copies of "Danger, " appended to the beginning of message, but you might have fewer.

Any time a thread enters a piece of code protected by the synchronized keyword, it implicitly acquires a lock which only a single thread can hold. If another thread tries to access the code, it’s forced to wait until the lock is released. This lock is re-entrant. Re-entrant means that, when a thread currently holds a lock and tries to get it again, it succeeds. This situation frequently occurs with synchronized methods which call other synchronized methods.

Consider method safety() which does the “opposite” of danger(), by removing occurrences of "Danger, " from the beginning of message.

Will the danger() and safety() methods play nicely together on the same object? In other words, will a thread be blocked from entering safety() if another thread is already in danger()? Yes! The locks in Java are connected to objects. When you use the synchronized keyword on a method, the object the method is being called on (whichever object this refers to inside the method) serves as the lock. Thus, only one thread can be inside of either of these methods on a given object. If you have 10 synchronized methods in an object, only one of them can execute at a time for that object.

Perhaps this level of control is too restrictive. You may have six methods which conflict with each other and four others which conflict with each other but not the first six. Using synchronized in each method declaration would unnecessarily limit the amount of concurrency your program could have.

Although it takes a little more work, using synchronized with a block of code allows more fine-grained control. The following version of danger() is equivalent to the earlier one.

Using synchronized on a block of code gives us more flexibility in two ways. First, we can choose exactly how much code we want to control, instead of the whole method. Second, we can choose which object we want to use for synchronization. For the block style, any arbitrary object can be used as a lock. Objects keep a list of threads which are waiting to get the lock and do all the other management needed to make the synchronized keyword work.

If you have two critical sections which are unrelated to each other, you can use the fine-grained control the block style provides. First, you’ll need some objects to use as locks, probably declared so that they can easily be shared, perhaps as static fields of a class.

Then, wherever you need control over concurrency, you use them as locks.

Since declaring a method with synchronized is equivalent to having its body enclosed in a block beginning with synchronized(this), what about static methods? Can they be synchronized? Yes, they can. Whenever a class is loaded, Java creates an object of type Class which corresponds to that class. This object is what synchronized static methods inside the class will use as a lock. For example, a synchronized static method inside of the Eggplant class will lock on the object Eggplant.class.

Protecting critical sections with the synchronized keyword is a powerful technique, and many other synchronization tools can be built using just this tool. However, efficiency demands a few more options.

Sometimes a thread is waiting for another thread to finish a task so that it can process the results. Imagine one thread collecting votes while another one’s waiting to count them. In this example, the counting thread must wait for all votes to be cast before it can begin counting. We could use a synchronized block and an indicator boolean called votingComplete to allow the collector thread to signal to the counting thread.

What’s the problem with this design? The counting thread is running through the while loop over and over waiting for votingComplete to become true. On a single processor, the counting thread would slow down the job of the collecting thread which is trying to process all the votes. On a multicore system, the counting thread is still wasting CPU cycles that some other thread could use. This phenomenon is known as busy waiting, for obvious reasons.

To combat this problem, Java provides the wait() method. When a thread’s executing synchronized code, it can call wait(). Instead of busy waiting, a thread which has called wait() will be removed from the list of running threads. It will wait in a dormant state until someone comes along and notifies the thread that its waiting is done. If you recall the thread state diagram from Chapter 13, there’s a Not Runnable state which threads enter by calling sleep(), calling wait(), or performing blocking I/O. Using wait(), we can rewrite the vote counting thread.

Note that the while loop has moved inside the synchronized block. Doing so before might have kept our program from terminating: As long as the vote counting thread held the lock, the vote collecting thread would not be allowed to modify votingComplete. When a thread calls wait(), however, it gives up the corresponding lock it’s holding until it wakes up and runs again. Why use the while loop at all now? There’s no guarantee that the condition you’re waiting for is true. Many threads might be waiting on this particular lock. We use the while loop to check that votingComplete is true and wait again if it isn’t.

In order to notify a waiting thread, the other thread calls the notify() method. Like wait(), notify() must be called within a synchronized block or method. Here is corresponding code the vote collecting thread might use to notify the counting thread that voting is complete.

A call to notify() will wake up one thread waiting on the lock object. If there are many threads waiting, the method notifyAll() used above can be called to wake them all up. In practice, it’s usually safer to call notifyAll(). If a particular condition changes and a single waiting thread is notified, that thread might need to notify the next waiting thread when it’s done. If your code isn’t very carefully designed, some thread might end up waiting forever and never be notified if you only rely on notify().

Deadlock is the situation when two or more threads are both waiting for the others to complete, forever. Some combination of locks or other synchronization tools has forced a blocking dependence onto a group of threads which will never be resolved.

In the past, people have described four conditions which must exist for deadlock to happen.

Starvation is another problem which can occur with careless use of synchronization tools. Starvation is a general term which covers any situation in which some thread never gets access to the resources it needs. Deadlock can be viewed as a special case of starvation since none of the threads which are deadlocking makes progress.

The dining philosophers problem was framed around the idea of eating with humorous intent. If a philosopher is never able to acquire chopsticks, that philosopher will quite literally starve.

Starvation doesn’t necessarily mean deadlock, however. Examine the implementation in Example 14.2 for the bank account. That solution is correct in the sense that it preserves mutual exclusion. No combination of balance checks, deposits, or withdrawals will cause the balance to be incorrect. Money will neither be created nor destroyed. A closer inspection reveals that the solution is not entirely fair. If a single thread is checking the balance, no other thread can make a deposit or a withdrawal. Balance checking threads could be coming and going constantly, incrementing and decrementing the readers variable, but if readers never goes down to zero, threads waiting to make deposits and withdrawals will wait forever.

Another kind of starvation is livelock. In deadlock, two or more threads get stuck and wait forever, doing nothing. Livelock is similar except that the two threads keep executing code and waiting for some condition that never arrives. A classic example of livelock is two polite (but oddly predictable) people speaking with each other: Both happen to start talking at exactly the same moment and then stop to hear what the other has to say. After exactly one second, they both begin again and immediately stop. Lather, rinse, repeat.

When designing a parallel program, you might notice that synchronization tools are necessary to get a correct answer. Then, when you run this parallel version and compare it to the sequential version, it runs no faster or, worse, runs slower than the sequential version. Too much zeal with synchronization tools can produce a program which gives the right answer but doesn’t exploit any parallelism.

For example, we can take the run() method from the parallel implementation of matrix multiply given in Example 13.11 and use the synchronized keyword to lock on the matrix itself.

In this case, only a single thread would have access to the matrix at any given time, and all speedup would be lost.

For the parallel version of matrix multiply we gave earlier, no synchronization is needed. In the case of the producer/consumer problem, synchronization is necessary, and the only way to manage the buffer properly is to enforce sequential execution. Sometimes sequential execution can’t be avoided, but you should always know which pieces of code are truly executing in parallel and which aren’t if you hope to get the maximum amount of speedup. The synchronized keyword should be used whenever it’s needed, but no more.

In Chapter 13 we suggest that you rarely use thread priorities. Even good reasons to use priorities can be thwarted by priority inversion. In priority inversion, a lower priority thread holds a lock needed by a higher priority thread, potentially for a long time. Because the high priority thread cannot continue, the lower priority thread gets more CPU time, as if it were a high priority thread.

Worse, if there are some medium priority threads in the system, the low priority thread could hold the lock needed by the high priority thread for even longer because those medium priority threads reduce the amount of CPU time the low priority thread has to finish its task.