The Producer-Consumer Relationship

Race Conditions

Take a look at the following class:

Knowing all that you know about Java programming at this point, answer the following question: Can an instance of LongSetter (example 16.12) ever be used in a program where its set() method might return false?

Example 16.12: chap16.race.LongSetter.java

 1       package chap16.race; 2 3       public final class LongSetter { 4         private long x; 5 6         public boolean set(long xval) { 7           x = xval; 8           return (x == xval); 9         } 10     }

If your answer is yes, explain why. If your answer is no, explain why. Think carefully before going on.

I mean it. Don’t read farther until you’ve thought about this. (I know I can’t really make you stop here and think this through but it’s worth a try!)

Do you have an answer? You do? Good!

The truth is that it is very simple to devise a multi-threaded program that causes the set() method to return false. If only one thread at a time ever calls LongSetter’s set() method then all is fine, but if two or more threads call it at the same time, all bets are off. Example 16.13 is a program designed to “break” LongSetter. It creates four threads and starts them all hammering at the set() method of one LongSetter instance. As soon as the set method returns false, the program ends. Run it to see the results. Figure 16-4 shows the results of running example 16.13 on my computer.

Example 16.13: chap16.race.Breaker.java

 1     package chap16.race; 2 3     public class Breaker extends Thread { 4       private final static LongSetter longSetter = new LongSetter(); 5 6       private final long value; 7 8       public Breaker(long value) { 9         this.value = value; 10      } 11      public void run() { 12        long count = 0; 13        boolean success; 14     15        while (true) { 16          success = longSetter.set(value); 17          count++; 18          if (!success) { 19            System.out.println( 20              "Breaker " + value + " broke after " + count + " tries."); 21            System.exit(0); 22          } 23        } 24      } 25      public static void main(String[] arg) { 26        new Breaker(1).start(); 27        new Breaker(2).start(); 28        new Breaker(3).start(); 29        new Breaker(4).start(); 30      } 31     }

 Breaker 2 broke after 2554997 tries.

Figure 16-4: Results of Running Example 16.13

Use the following commands to compile and execute the example. From the directory containing the src folder:

      javac –d classes -sourcepath src src/chap16/race/Breaker.java      java –cp classes chap16.race.Breaker

Figure 16-4 shows the results of running this program.

So what happened here? The flip side of thread independence is, unfortunately, thread non-cooperation. Left to its own devices, a thread charges recklessly forward, executing statement after statement in sequential order, caring not in the least what other reckless threads may be doing at the very same moment. And so it eventually happens in the Breaker program that after one thread executes the assignment “x = val” but before it executes the comparison “return x == val”, another thread tramples over the value of x by executing the assignment “x = val” with a different value for val. The diagram in figure 16-5 depicts just one of several possible unfortunate scenarios. Here, Breaker(3) sets x to 3 immediately after Breaker(2) sets it to 2. When it comes to the comparison, last one wins, so Breaker(2)’s comparison fails.

Figure 16-5: Breaker.java Thread Interaction

The implications of this are devastating. In a multithreaded application without proper defensive coding, a thread has no guarantee that the results of executing one statement will persist even until the beginning of the next statement’s execution. Actually, things are even worse than that because many single statements compile to more than one byte-code and threads can insert themselves between the execution of any two byte-codes. In this simple case, it is easy to see how thread interference negatively affected the results. But in an application of even moderate complexity, foreseeing the many different ways in which competing threads might interfere with each other can be very difficult if not virtually impossible.

The Breaker example above creates what is known as a race condition. This is a condition where more than one thread accesses the same resource at the same time, resulting in errors and/or resource corruption. You can think of the threads as racing with each other. In the case of Breaker, the last thread to set the value of x “wins” the race, but in other programs and situations, the first thread might “win”. Sometimes there is no “winner”. In any case, whether or not any particular thread wins, the program itself loses.

The Mechanics of Synchronization

In order to defend a multi-threaded program from the ravages of unruly threads, it is necessary to delve deep into the Java language into the mechanics of Object itself, the root of all Java classes. Associated with every Object is a unique lock more formally known as a monitor. Every Object is said to “contain” this lock although no lock “attribute” is actually defined. Rather, the concept of a lock is embedded into the JVM implementation and is a part of Object’s low-level architecture. As such, it obeys different rules than do Objects and primitives. Here are some of the rules and behaviors of locks as they relate to threads:

1. A lock can be “owned” by a thread.

2. A thread becomes the owner of a lock by explicitly acquiring it.

3. A thread gives up ownership of a lock by explicitly releasing it.

4. If a thread attempts to acquire a lock not currently owned by another thread, it becomes the lock’s owner.

5. If a thread attempts to acquire a lock that is owned by another thread, then it blocks (stops executing code) at least until the lock is released by the current owner.

6. A thread may simultaneously own locks on any number of different Objects.

Figure 16-6 illustrates the process of a thread acquiring and releasing the lock of an Object, A.

Figure 16-6: Acquiring and Releasing Locks

Although there are no actual method calls for acquiring or releasing a lock, there is a syntax for synchronizing a block of code on an object. A code block that is synchronized on an object can only be executed by a thread that owns that object’s lock. There are no restrictions on what a synchronized code block may do. Here is an example of a block of code synchronized on “object”:

        /* Before entering, the current thread must either acquire or own object's lock */        synchronized (object) { //The current thread now owns object's lock           /* Code placed here is synchronized on object's lock */        }// The current thread releases object's lock if it acquired it when entering

The synchronized statement requires a parameter of type Object. The synchronized code block is said to be synchronized “on” that object. When a thread that does not already own the object’s lock encounters a synchronized statement, it will attempt to acquire the lock. If the lock is not available, it will wait until the lock becomes available, at which point it will make another attempt to acquire the lock. When (if ever) it has successfully acquired the lock, it will enter and execute the synchronized block of code. When the thread finally exits the code block, the lock will be released. A thread that already owns the lock has no need to reacquire the lock when it encounters the synchronized block. It immediately enters and executes the code block. Nor will it release the lock upon exit. It will, of course, have to release the lock whenever it exits the block of code that initially caused it to acquire the lock.

Just as with any other code block, synchronized code blocks may be nested. This makes it possible for a thread to own more than one lock simultaneously. Due to this nested nature, a thread that owns more than one lock will always release its locks in the reverse order of the order in which they were acquired. Following is an example of a nested synchronized block of code.

        synchronized (objectA) {//The current thread now owns objectA's lock           synchronized (objectB) {//The current thread now owns objectB's lock also              /* Code placed here is synchronized on objectA's and objectB's lock */           }//The current thread releases objectB's lock if it acquired it when entering         }//The current thread releases objectA's lock if it acquired it when entering

Three Basic Rules of Synchronization

There are three basic rules for utilizing synchronization effectively. We will explore them in this section.

Synchronization Rule 1

Synchronization can be used to ensure cooperation between threads competing for common resources.

Let’s see in a diagram similar to figure 16-5 what might happen if we put the call to LongSetter.set() inside a code block that is synchronized on an Object, A. This would require all threads to own or acquire a lock on A before executing the two statements of LongSetter.set(). In figure 16-7, we’ll have Breaker(3) attempt to execute the method after Breaker(2) has begun. This is the same scenario as figure 16-5 depicted but this time, as figure 16-7 shows, Breaker(3) is forced to block because Breaker(2) owns the lock. Breaker(2) finishes the code block and releases the lock. Then Breaker(3) attempts to acquire the lock, succeeds and executes the code block. This illustrates how the use of synchronization can prevent race conditions from occurring.

Figure 16-7: Breaker(2) and Breaker(3) Both Succeed

Let’s test this approach with some code. SynchedBreaker (example 16.14) synchronizes on the LongSetter instance. Since it is a static field, all instances of SynchedBreaker will synchronize on the same object.

Example 16.14: chap16.race.SynchedBreaker.java

 1      package chap16.race; 2 3      public class SynchedBreaker extends Thread { 4        private final static LongSetter longSetter = new LongSetter(); 5 6        private final long value; 7 8        public SynchedBreaker(long value) { 9          this.value = value; 10       } 11       public void run() { 12         long count = 0; 13         boolean success; 14 15         while (true) { 16           synchronized (longSetter) { 17             success = longSetter.set(value); 18           } 19           count++; 20           if (!success) { 21             System.out.println( 22               "Breaker " + value + " broke after " + count + " tries."); 23             System.exit(0); 24           } 25         } 26       } 27       public static void main(String[] arg) { 28         new SynchedBreaker(1).start(); 29         new SynchedBreaker(2).start(); 30         new SynchedBreaker(3).start(); 31         new SynchedBreaker(4).start(); 32       } 33     }

Use the following commands to compile and execute the example. From the directory containing the src folder:

    javac –d classes -sourcepath src src/chap16/race/SynchedBreaker.java    java –cp classes chap16.race.SynchedBreaker

As you can see from running it, SynchedBreaker doesn’t break. When you are satisfied that it will never break, go ahead and terminate it.

Synchronization Rule 2

All threads competing for common resources must synchronize their access or none is safe.

In figures 16-8 and 16-9, we show what might happen if some but not all competing threads synchronize their access to shared resources. Here, Breaker(2) synchronizes its access but Breaker(3) does not. Consequently, Breaker(2)’s acquisition of A’s lock does nothing to prevent Breaker(3) from unsynchronized access. Nor does it protect Breaker(3) from Breaker(2)’s intrusion.

Figure 16-8: Breaker(2) Fails Because Not All Threads Synchronized

Figure 16-9: Breaker(3) Fails Because Not All Threads Synchronized

This rule is verified by MixedModeBreaker (example 16.15), where one thread synchronizes on the LongSetter instance before invoking the set() method and three threads don’t. Figure 16-10 shows the results of running example 16.15.

Example 16.15: chap16.race.MixedModeBreaker.java

 1      package chap16.race; 2 3      public class MixedModeBreaker extends Thread { 4        private final static LongSetter longSetter = new LongSetter(); 5 6        private final long value; 7        private boolean synch; 8 9        public MixedModeBreaker(long value, boolean synch) { 10         this.value = value; 11         this.synch = synch; 12       } 13       public void run() { 14         long count = 0; 15         boolean success; 16     17         while (true) { 18           if (synch) { 19             synchronized (longSetter) { 20               success = longSetter.set(value); 21             } 22           } else { 23             success = longSetter.set(value); 24           } 25           count++; 26           if (synch && !success) { 27             System.out.println( 28               "Breaker " + value + " broke after " + count + " tries."); 29             System.exit(0); 30           } 31         } 32       } 33       public static void main(String[] arg) { 34         new MixedModeBreaker(1, false).start(); 35         new MixedModeBreaker(2, false).start(); 36         new MixedModeBreaker(3, false).start(); 37         new MixedModeBreaker(4, true).start(); 38       } 39      }

 Breaker 4 broke after 2648189 tries.

Figure 16-10: Results of Running Example 16.15

Use the following command to compile and execute the example. From the directory containing the src folder:

    javac –d classes -sourcepath src src/chap16/race/MixedModeBreaker.java    java –cp classes chap16.race.MixedModeBreaker

Synchronization Rule 3

All threads competing for common resources must synchronize their access on the same lock or none is safe.

In Figure 16-11, Breaker(2) and Breaker(3) both have synchronized access to LongSetter.set() but they synchronize on different objects, Breaker(2) on A and Breaker(3) on B. Again, the use of synchronization here is ineffective. Breaker(2)’s acquisition of A’s lock has no effect on Breaker(3)’s ability to acquire B’s lock and visa versa.

Figure 16-11: Breaker(2) Fails Because Threads Synchronized on Different Locks

We verify rule 3 with PointlessSynchedBreaker (example 16.16) where each PointlessSynchedBreaker synchronizes on itself rather than on a common object. Figure 16-12 shows the results of running example 16.16.

Example 16.16: chap16.race.PointlessSynchedBreaker.java

 1      package chap16.race; 2 3      public class PointlessSynchedBreaker extends Thread { 4        private final static LongSetter longSetter = new LongSetter(); 5 6        private final long value; 7 8        public PointlessSynchedBreaker(long value) { 9          this.value = value; 10      } 11       public void run() { 12         long count = 0; 13         boolean success; 14     15         while (true) { 16           synchronized (this) { 17             success = longSetter.set(value); 18           } 19           count++; 20           if (!success) { 21             System.out.println( 22               "Breaker " + value + " broke after " + count + " tries."); 23             System.exit(0); 24           } 25         } 26       } 27       public static void main(String[] arg) { 28         new PointlessSynchedBreaker(1).start(); 29         new PointlessSynchedBreaker(2).start(); 30         new PointlessSynchedBreaker(3).start(); 31         new PointlessSynchedBreaker(4).start(); 32       } 33     }

 Breaker 1 broke after 37265504 tries.

Figure 16-12: Results of Running Example 16.16

Use the following commands to compile and execute the example. From the directory containing the src folder:

 javac –d classes -sourcepath src src/chap16/race/PointlessSynchedBreaker.java java –cp classes chap16.race.PointlessSynchedBreaker

Synchronizing Methods

What if we didn’t want or weren’t able to modify Breaker’s code in order to prevent race conditions with LongSetter? Is there something else we could do? Yes, we could modify LongSetter itself as in the following code for SynchedLongSetter.

Example 16.17: chap16.race.SynchedLongSetter

 1      package chap16.race; 2 3      public final class SynchedLongSetter { 4        private long x; 5 6        public boolean set(long xval) { 7          synchronized (this) { 8            x = xval; 9            return (x == xval); 10         } 11       } 12     }

From the point of view of execution, using Breaker with SynchedLongSetter is identical to using SynchedBreaker with LongSetter. In each approach, the assignment and comparison statements within the set() method are protected by requiring the current thread to own the LongSetter (or SynchedLongSetter) instance’s lock. In the first approach, SynchedBreaker assumes responsibility for synchronization; in the second, SynchedLongSetter assumes responsibility. The pattern of synchronizing an entire method on “this” is so common place that there is an alternate notation for it. The following two methods, for instance, are equivalent. Before allowing a thread to execute the method body, they both require it to own (or acquire) the lock of the Object instance whose method is being invoked. Methods declared in this shorthand way are called synchronized methods.

      public class Example {        public synchronized void doSomething() {          /* code block */        }      }

is shorthand for

      public class Example {         public void doSomething () {            synchronized (this) {               /* code block */            }         }      }

This alternate notation applies to static methods as well. The following two static methods are equivalent to each other. Before allowing a thread to execute the method body, they both require it to own (or acquire) the lock of the Class object associated with the class that defines the method.

      public class Example {         public synchronized static void doSomethingStatic () {            /* code block */        }      }

is shorthand for

      public class Example {         public static void doSomethingStatic () {            synchronized (Example.class) {               /* code block */            }         }      }

Please keep in mind that these are simply alternate notations. No matter how it may look, the word “synchronized” is not part of a method’s signature and it is not inherited by subclasses. In the following two classes, for example, Example.doSomething() is synchronized but Example2.doSomething() is not.

      public class Example {         public synchronized void doSomething () {             /* code block */         }      }      public Example2 extends Example {         public void doSomething () {            /* code block */         }      }

Quick Review

A race condition is a condition where more than one thread accesses the same resource at the same time, resulting in errors and/or resource corruption. Synchronization can be used to prevent race conditions by ensuring that a block of code is executed by only one thread at a time. Synchronization is only effective when all threads attempting to execute a block of code are synchronized on a common object. Synchronization is applied to a block of code. Synchronized methods have a slightly different syntax but they too are simply blocks of code that have been synchronized.