Transcript Concurrency-Bloch

Effective Java:
Concurrency
Last Updated: Spring 2010
Agenda

Material From Joshua Bloch


Cover Items 66-73


Effective Java: Programming Language Guide
“Concurrency” Chapter
Bottom Line:

Primitive Java concurrency is complex
Concurrency in Java
Some Background
(from Java Concurrency in Practice, B.
Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Holmes, and D. Lea)


Thread: lightweight processes; execute simultaneously
and asynchronously with each other; share same
memory address space of owning process, all thread
within a process have access to the same variables and
allocate objects from the same heap
Thread Safety



Managing the state: with respect to shared and mutable state.
Shared: accessed by multiple threads.
Mutable: value could change during lifecycle.
Concurrency in Java
Some Background
(from Java Concurrency in Practice, B.
Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Holmes, and D. Lea)

Thread Safety???:



Correctness – invariants; postconditions
“A class is thread-safe if it behaves correctly when accessed
from multiple threads, regardless of the scheduling or
interleaving of the execution of the threads by the runtime
environment, and with no additoinal synchronization or other
coordination on the part of the calling code.”
“Thread-safe encapsulate any needed synchronization so that
clients need not provide their own.”
Concurrency in Java
Java Concurrency Problems:
Examples



Race conditions – threads try to update
the same data structure at the same time
Deadlock – two threads need variables A
and B to perform a calculation; one thread
locks A and the other thread locks B;
Starvation – a thread is unable to obtain
CPU time due a higher priority threads
Concurrency in Java
Thread Interference
class Counter {
private int c = 0;
public void increment() {
c++;
}
public void decrement() {
c--;
}
public int value() {
return c;
}
}

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.
Concurrency in Java
Thread Interference
(concluded)

c++ can be decomposed into three steps




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:







Retrieve the current value of c
Increment the retrieved value by 1
Store the incremented value back in c
Thread
Thread
Thread
Thread
Thread
Thread
A: Retrieve c.
B: Retrieve c.
A: Increment retrieved value; result is 1.
B: Decrement retrieved value; result is -1.
A: Store result in c; c is now 1.
B: Store result in c; c is now -1.
N.B., 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.
Concurrency in Java
Memory Consistency Errors Java Memory Model
(from Java Concurrency in Practice,
B. Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Holmes, and D. Lea)

Partial ordering on Java program actions (happensbefore)






Read/write
Lock/unlock
Start/join threads
If action X happens-before Y, then X’s results are visible
to Y.
Within a thread the order is the program order.
Between threads, if synchronized or volatile is not used,
there are no visibility guarantees (i.e., there is no
guarantee that thread A will see them in the order that
thread be executes them).
Concurrency in Java
Item 66: Synchronize Access
to Shared Mutable Data


Method synchronization yields atomic
transitions:

public synchronized boolean doStuff() {…}

Fairly well understood…
Method synchronization also ensures that
other threads “see” earlier threads


Not synchronizing on shared “atomic” data
produces wildly counterintuitive results
Not well understood
Concurrency in Java
Java Synchronization




Communication between Java Threads
Java synchronization is implemented using
monitors
Each object in Java is associated with a monitor,
which a thread can lock and unlock
Only one thread at a time may hold a lock on a
monitor. Any other threads attempting to lock
that monitor are blocked until they can obtain a
lock on that monitor.
Concurrency in Java
Basic tools of Java Thread
Synchronization


Synchronized keyword – an unlock happens-before
every subsequent lock on the same monitor
Volatile keyword – a write to a volatile variable happensbefore subsequent reads of that variable; compiler and
runtime are notified that the variable should not be
reordered with memory operations; variables are not
cached in registers or in caches where they are hidden
from other processors, so a read of volatile variable
always returns the most recent write by any thread (from Java
Concurrency in Practice, B. Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Holmes, and D. Lea)

Static initialization – done by the class loader, so the
JVM guarantees thread safety
Concurrency in Java
Atomic Example
(from Java Concurrency in Practice, B. Goetz, T.
Peierls, J. Bloch, J. Bowbeer, D. Holmes, and D. Lea)
@NotThreadSafe
Public class UnsafeCountingFactorizer implements Servlet {
private long count;
public long getCount() { return count; }
public void service(ServletRequest req, ServletResponse resp) {
BigInteger I = extractFromRequest(req);
BigInteger[] factors = factor(i);
++count;
encodeIntoResponse(resp, factors);
Why is this unsafe?
Atomic – execute as a single, indivisible operation.
Concurrency in Java
Item 66: Unsafe Example
// Broken! How long do you expect this program to run?
public class StopThread {
private static boolean stopRequested;
public static void main (String[] args)
throws InterruptedException {
Thread backgroundThread = new Thread(new Runnable() {
public void run() { // May run forever! Liveness failure
int i=o; while (! stopRequested) i++; // See below
}});
backgroundThread.start();
TimeUnit.SECONDS.sleep(1);
stopRequested = true;
} }
// Hoisting transform:
// while (!loopTest) {i++;}  if (!loopTest) while(true) {i++;}
Concurrency in Java
// Also note anonymous class
Item 66: Fixing the Example
// As before, but with synchronized calls
public class StopThread {
private static boolean stopReq;
public static synchronized void setStop() {stopReq = true;}
public static synchronized void getStop() {return stopReq;}
public static void main (String[] args)
throws InterruptedException {
Thread backgroundThread = new Thread(new Runnable() {
public void run() {
// Now “sees” main thread
int i=o; while (! getStop() ) i++;
}});
backgroundThread.start();
TimeUnit.SECONDS.sleep(1);
setStop();
} }
// Note that both setStop() and getStop() are synchronized
Concurrency in Java
Item 66: A volatile Fix for
the Example
// A fix with volatile
public class StopThread {
// Pretty subtle stuff, using the volatile keyword
private static volatile boolean stopRequested;
public static void main (String[] args)
throws InterruptedException {
Thread backgroundThread = new Thread(new Runnable() {
public void run() {
int i=o; while (! stopRequested) i++;
}});
backgroundThread.start();
TimeUnit.SECONDS.sleep(1);
stopRequested = true;
}
}
Concurrency in Java
Item 66: volatile Does Not
Guarantee Mutual Exclusion
// Broken! Requires Synchronization!
private static volatile int nextSerialNumber = 0;
public static int generateSerialNumber() {
return nextSerialNumber++;
}

Problem is that the “++” operator is not atomic
// Even better! (See Item 47)
private static final AtomicLong nextSerial = new AtomicLong();
public static long generateSerialNumber() {
return nextSerial.getAndIncrement();
}
Concurrency in Java
Item 66: Advice on Sharing
Data Between Threads

Confine mutable data to a single Thread

May modify, then share (no further changes)



Called “Effectively Immutable”
Allows for “Safe Publication”
Mechanisms for safe publication





In static field at class initialization
volatile field
final field
field accessed with locking (ie synchronization)
Concurrency in Java
Store in concurrent collection (Item 69)
Item 67: Avoid Excessive
Synchronization
// Broken! Invokes alien method from sychronized block
public interface SetOb<E> { void added(ObservableSet<E> set, E el);}
public class ObservableSet<E> extends ForwardingSet<E> { // Bloch 16
public ObservableSet(Set<E> set) { super(set); }
private final List<SetOb<E>> obs = new ArrayList<SetOb<E>>();
public void addObserver (SetObs<E> ob ) {
synchronized (obs) { obs.add(ob); } }
public boolean removeObserver (SetOb<E> ob ) {
synchronized (obs) { return obs.remove(ob); } }
private void notifyElementAdded (E el) {
synchronized(obs) {for (SetOb<E> ob:obs) // Exceptions?
ob.added(this, el);}
@Override public boolean add(E el) { // from Set interface
boolean added = super.add(el);
if (added) notifyElementAdded (el);
return added;
Concurrency in Java
}}
More Item 67: What’s the
Problem?
public static void main (String[] args) {
ObservableSet<Integer> set = new ObservableSet<Integer>
(new HashSet<Integer>);
set.addObserver (new SetOb<Integer>() {
public void added (ObservableSet<Integer> s, Integer e) {
System.out.println(e);
if (e.equals(23)) s.removeObserver(this); // Oops! CME
// See Bloch for a variant that deadlocks instead of CME
}
});
for (int i=0; i < 100; i++)
set.add(i);
}
Concurrency in Java
More Item 67: Turning the
Alien Call into an Open Call
// Alien method moved outside of synchronized block – open call
private void notifyElementAdded(E el) {
List<SetOb<E>> snapshot = null;
synchronized (observers) {
snapshot = new ArrayList<SetOb<E>>(obs);
}
for (SetObserver<E> observer : snapshot)
observer.added(this, el) // No more CME
}}



Open Calls increase concurrency and prevent failures
Rule: Do as little work inside synch block as possible
When designing a new class:


Do NOT internally synchronize absent strong motivation
Concurrency in Java
Example: StringBuffer vs. StringBuilder
Item 67: Alternate Fix Using
CopyOnWriteArray
public interface SetOb<E> { void added(ObservableSet<E> set, E el);}
public class ObservableSet<E> extends ForwardingSet<E> { // Bloch 16
public ObservableSet(Set<E> set) { super(set); }
private final List<SetOb<E>> obs = new
CopyOnWriteArrayList<SetOb<E>>();
public void addObserver (SetObs<E> ob ) {
synchronized (obs) { obs.add(ob); } }
public boolean removeObserver (SetOb<E> ob ) {
synchronized (obs) { return obs.remove(ob); } }
private void notifyElementAdded (E el) {
{for (SetOb<E> ob:obs) // Iterate on copy – No Synch!
ob.added(this, el);}
@Override public boolean add(E el) { // from Set interface
boolean added = super.add(el);
if (added) notifyElementAdded (el);
return added;
Concurrency in Java
}}
Item 68: Prefer Executors and
Tasks to Threads

Old key abstraction: Thread



Unit of work and
Mechanism for execution
New key abstractions:

Task (Unit of work)


Mechanism for execution



Runnable and Callable
Executor Service
Start tasks, wait on particular tasks, etc.
See Bloch for references
Concurrency in Java
Item 69: Prefer Concurrency
Utilities to wait and notify


wait() and notify() are complex
Java concurrency facilities much better


Legacy code still requires understanding low level
primitives
Three mechanisms


Executor Framework (Item 68)
Concurrent collections



Internally synchronized versions of Collection classes
Extensions for blocking, Example: BlockingQueue
Synchronizers

Objects that allow Threads to wait for one another
Concurrency in Java
More Item 69: Timing Example
// Simple framework for timing concurrent execution
public static long time (Executor executor, int concurrency, final Runnable
action) throws InterrruptedExecution {
final CountDownLatch ready = new CountDownLatch(concurrency);
final CountDownLatch start = new CountDownLatch(1);
final CountDownLatch done = new CountDownLatch(concurrency);
for (int i=0; i< concurrency; i++) {
executor.execute (new Runnable() {
public void run() { ready.countDown(); // Tell Timer we’re ready
try { start.await(); action.run(); // Wait till peers are ready
} catch (...){ ...}
} finally { done.countDown(); }} // Tell Timer we’re done
});}
ready.await();
// Wait for all workers to be ready
long startNanos = System.nanoTime();
start.countDown();
// And they’re off!
done.await()
// Wait for all workers to finish
return System.nanoTime() – startNanos;
}
Concurrency in Java
Item 70: Document Thread
Safety

Levels of Thread safety

Immutable:



Unconditionally thread-safe




Some methods require external synchronization
Example: Collections.synchronized wrappers
Not thread-safe



Instances of class are mutable, but is internally synchronized
Example: ConcurrentHashMap
Conditionally thread-safe


Instances of class appear constant
Example: String
Client responsible for synchronization
Examples: Collection classes
Thread hostile: Not to be emulated!
Concurrency in Java
Item 71: Use Lazy
Initialization Judiciously

Under most circumstances, normal
initialization is preferred
// Normal initialization of an instance field
private final FieldType field = computeFieldValue();
// Lazy initialization of instance field – synchronized accessor
private FieldType field;
synchronized FieldType getField() {
if (field == null)
field = computeFieldValue();
return field;
}
Concurrency in Java
More Item 71: Double Check
Lazy Initialization
// Double-check idiom for lazy initialization of instance fields
private volatile FieldType field; // volatile key – see Item 66
FieldType getField() {
FieldType result = field;
if (result == null) { // check with no locking
synchronized (this) {
result = field;
if (result == null) // Second check with a lock
field = result = computeFieldValue();
}
}
return result;
}
Concurrency in Java
Item 72: Don’t Depend on the
Thread Scheduler


Any program that relies on the thread
scheduler is likely to be unportable
Threads should not busy-wait


Use concurrency facilities instead (Item 69)
Don’t “Fix” slow code with
Thread.yield calls


Restructure instead
Avoid Thread priorities
Concurrency in Java
Item 73: Avoid Thread Groups

Thread groups originally envisioned as a
mechanism for isolating Applets for
security purposes

Unfortunately, doesn’t really work
Concurrency in Java