Resolving shared resource contention
To solve the problem of thread collision, virtually all multithreading schemes serialize access to shared resources. This means that only one thread at a time is allowed to access the shared resource. This is ordinarily accomplished by putting a locked clause around a piece of code so that only one thread at a time may pass through that piece of code. Because this locked clause produces mutual exclusion, a common name for such a mechanism is mutex.
Consider the bathroom in your house; multiple people (threads) may each want to have exclusive use of the bathroom (the shared resource). To access the bathroom, a person knocks on the door to see if it’s available. If so, they enter and lock the door. Any other thread that wants to use the bathroom is “blocked” from using it, so that thread waits at the door until the bathroom is available.
The analogy breaks down a bit when the bathroom is released and it comes time to give access to another thread. There isn’t actually a line of people and we don’t know for sure who gets the bathroom next, because the thread scheduler isn’t deterministic that way. Instead, it’s as if there is a group of blocked threads milling about in front of the bathroom, and when the thread that has locked the bathroom unlocks it and emerges, the one that happens to be nearest the door at the moment goes in. As noted earlier, suggestions can be made to the thread scheduler via yield( ) and setPriority( ), but these suggestions may not have much of an effect depending on your platform and JVM implementation.
Java has built-in support to prevent collisions over resources in the form of the synchronized keyword. This works much like the Semaphore class was supposed to: When a thread wishes to execute a piece of code guarded by the synchronized keyword, it checks to see if the semaphore is available, then acquires it, executes the code, and releases it. However, synchronized is built into the language, so it’s guaranteed to always work, unlike the Semaphore class.
The shared resource is typically just a piece of memory in the form of an object, but may also be a file, I/O port, or something like a printer. To control access to a shared resource, you first put it inside an object. Then any method that accesses that resource can be made synchronized. This means that if a thread is inside one of the synchronized methods, all other threads are blocked from entering any of the synchronized methods of the class until the first thread returns from its call.
Since you typically make the data elements of a class private and access that memory only through methods, you can prevent collisions by making methods synchronized. Here is how you declare synchronized methods:
synchronized void f() { /* ... */ }
synchronized void g(){ /* ... */ }
Each object contains a single lock (also referred to as a monitor) that is automatically part of the object (you don’t have to write any special code). When you call any synchronized method, that object is locked and no other synchronized method of that object can be called until the first one finishes and releases the lock. In the preceding example, if f( ) is called for an object, g( ) cannot be called for the same object until f( ) is completed and releases the lock. Thus, there is a single lock that is shared by all the synchronized methods of a particular object, and this lock prevents common memory from being written by more than one thread at a time.
One thread may acquire an object’s lock multiple times. This happens if one method calls a second method on the same object, which in turn calls another method on the same object, etc. The JVM keeps track of the number of times the object has been locked. If the object is unlocked, it has a count of zero. As a thread acquires the lock for the first time, the count goes to one. Each time the thread acquires a lock on the same object, the count is incremented. Naturally, multiple lock acquisition is only allowed for the thread that acquired the lock in the first place. Each time the thread leaves a synchronized method, the count is decremented, until the count goes to zero, releasing the lock entirely for use by other threads.
There’s also a single lock per class (as part of the Class object for the class), so that synchronized static methods can lock each other out from simultaneous access of static data on a class-wide basis.
Synchronizing the EvenGenerator
By adding synchronized to EvenGenerator.java, we can prevent the undesirable thread access:
//: c13:SynchronizedEvenGenerator.java
// Using "synchronized" to prevent thread collisions
public
class SynchronizedEvenGenerator implements Invariant {
private int i;
public synchronized void next() { i++; i++; }
public synchronized int getValue() { return i; }
// Not synchronized so it can run at
// any time and thus be a genuine test:
public InvariantState invariant() {
int val = getValue();
if(val % 2 == 0)
return new InvariantOK();
else
return new InvariantFailure(new Integer(val));
}
public static void main(String[] args) {
SynchronizedEvenGenerator gen =
new SynchronizedEvenGenerator();
new InvariantWatcher(gen, 4000); // 4-second timeout
while(true)
gen.next();
}
} ///:~
You’ll notice that both next( ) and getValue( ) are synchronized. If you synchronize only one of the methods, then the other is free to ignore the object lock and can be called with impunity. This is an important point: Every method that accesses a critical shared resource must be synchronized or it won’t work right. On the other hand, InvariantState is not synchronized because it is doing the testing, and we want it to be called at any time so that it produces a true test of the object.
Atomic operations
A common piece of lore often repeated in Java threading discussions is that “atomic operations do not need to be synchronized.” An atomic operation is one that cannot be interrupted by the thread scheduler; if the operation begins, then it will run to completion before the possibility of a context switch (switching execution to another thread).
The atomic operations commonly mentioned in this lore include simple assignment and returning a value when the variable in question is a primitive type that is not a long or a double. The latter types are excluded because they are larger than the rest of the types, and the JVM is thus not required to perform reads and assignments as single atomic operations (a JVM may choose to do so anyway, but there’s no guarantee). However, you do get atomicity if you use the volatile keyword with long or double.
If you were to blindly apply the idea of atomicity to SynchronizedEvenGenerator.java, you would notice that
public synchronized int getValue() { return i; }
fits the description. But try removing synchronized, and the test will fail, because even though return i is indeed an atomic operation, removing synchronized allows the value to be read while the object is in an unstable intermediate state. You must genuinely understand what you’re doing before you try to apply optimizations like this. There are no easily-applicable rules that work.
As a second example, consider something even simpler: a class that produces serial numbers.[70] Each time nextSerialNumber( ) is called, it must return a unique value to the caller:
//: c13:SerialNumberGenerator.java
public class SerialNumberGenerator {
private static volatile int serialNumber = 0;
public static int nextSerialNumber() {
return serialNumber++;
}
} ///:~
SerialNumberGenerator is about as simple a class as you can imagine, and if you’re coming from C++ or some other low-level background, you would expect the increment to be an atomic operation, because increment is usually implemented as a microprocessor instruction. However, in the JVM an increment is not atomic and involves both a read and a write, so there’s room for threading problems even in such a simple operation.
The serialNumber field is volatile because it is possible for each thread to have a local stack and maintain copies of some variables there. If you define a variable as volatile, it tells the compiler not to do any optimizations that would remove reads and writes that keep the field in exact synchronization with the local data in the threads.
To test this, we need a set that doesn’t run out of memory, in case it takes a long time to detect a problem. The CircularSet shown here reuses the memory used to store ints, with the assumption that by the time you wrap around, the possibility of a collision with the overwritten values is minimal. The add( ) and contains( ) methods are synchronized to prevent thread collisions:
//: c13:SerialNumberChecker.java
// Operations that may seem safe are not,
// when threads are present.
// Reuses storage so we don't run out of memory:
class CircularSet {
private int[] array;
private int len;
private int index = 0;
public CircularSet(int size) {
array = new int[size];
len = size;
// Initialize to a value not produced
// by the SerialNumberGenerator:
for(int i = 0; i < size; i++)
array[i] = -1;
}
public synchronized void add(int i) {
array[index] = i;
// Wrap index and write over old elements:
index = ++index % len;
}
public synchronized boolean contains(int val) {
for(int i = 0; i < len; i++)
if(array[i] == val) return true;
return false;
}
}
public class SerialNumberChecker {
private static CircularSet serials =
new CircularSet(1000);
static class SerialChecker extends Thread {
SerialChecker() { start(); }
public void run() {
while(true) {
int serial =
SerialNumberGenerator.nextSerialNumber();
if(serials.contains(serial)) {
System.out.println("Duplicate: " + serial);
System.exit(0);
}
serials.add(serial);
}
}
}
public static void main(String[] args) {
for(int i = 0; i < 10; i++)
new SerialChecker();
// Stop after 4 seconds:
new Timeout(4000, "No duplicates detected");
}
} ///:~
SerialNumberChecker contains a static CircularSet that contains all the serial numbers that have been extracted, and a nested Thread that gets serial numbers and ensures that they are unique. By creating multiple threads to contend over serial numbers, you’ll discover that the threads get a duplicate serial number reasonably soon (note that this program may not indicate a collision on your machine, but it has successfully detected collisions on a multiprocessor machine). To solve the problem, add the synchronized keyword to nextSerialNumber( ).
The atomic operations that are supposed to be safe are reading and assignment of primitives. However, as seen in EvenGenerator.java, it’s still easily possible to use an atomic operation that accesses your object while it’s in an unstable intermediate state, so you cannot make any assumptions. On top of this, the atomic operations are not guaranteed to work with long and double (although some JVM implementations do guarantee atomicity for long and double operations, you won’t be writing portable code if you depend on this).
It’s safest to use the following guidelines:
- If you need to synchronize one method in a class, synchronize all of them.
It’s often difficult to tell for sure if a method will be negatively
affected if you leave synchronization out.
- Be extremely careful when removing synchronization from methods. The typical
reason to do this is for performance, but in JDK 1.3 and 1.4 the overhead of
synchronized has been greatly reduced. In addition, you should only do
this after using a profiler to determine that synchronized is indeed the
bottleneck.
Fixing Semaphore
Now consider Semaphore.java. It would seem that we should be able to repair this by synchronizing the three class methods, like this:
//: c13:SynchronizedSemaphore.java
// Colliding over shared resources
public class SynchronizedSemaphore extends Semaphore {
private volatile int semaphore = 0;
public synchronized boolean available() {
return semaphore == 0;
}
public synchronized void acquire() { ++semaphore; }
public synchronized void release() { --semaphore; }
public InvariantState invariant() {
int val = semaphore;
if(val == 0 || val == 1)
return new InvariantOK();
else
return new InvariantFailure(new Integer(val));
}
public static void main(String[] args) throws Exception {
SynchronizedSemaphore sem =new SynchronizedSemaphore();
new SemaphoreTester(sem);
new SemaphoreTester(sem);
new InvariantWatcher(sem).join();
}
} ///:~
This looks rather odd at first—SynchronizedSemaphore is inherited from Semaphore, and yet all the overridden methods are synchronized, but the base-class versions aren’t. Java doesn’t allow you to change the method signature during overriding, and yet doesn’t complain about this. That’s because the synchronized keyword is not part of the method signature, so you can add it in and it doesn’t limit overriding.
The reason for inheriting from Semaphore is to reuse the SemaphoreTester class. When you run the program you’ll see that it still causes an InvariantFailure.
Why does this fail? By the time a thread detects that the Semaphore is available because available( ) returns true, it has released the lock on the object. Another thread can dash in and increment the semaphore value before the first thread does. The first thread still assumes the Semaphore object is available and so goes ahead and blindly enters the acquire( ) method, putting the object into an unstable state. This is just one more lesson about rule zero of concurrent programming: Never make any assumptions.
The only solution to this problem is to make the test for availability and the acquisition a single atomic operation—which is exactly what the synchronized keyword provides in conjunction with the lock on an object. That is, Java’s lock and synchronized keyword is a built-in semaphore mechanism, so you don’t need to create your own.
