XYZ CODE: Chapter 5 Building blocks

5.1 Synchronized collections

The synchronized collection classes include Vector, Hashtable, and the synchronized wrapper classes created by the Collections.synchronizedxxx factory methods. These classes achieve thread safety by encapsulating their state and synchronizing every public method so that only one thread at a time can access the collections state.

The synchronized collections are thread-safe, but you may sometimes need to use additional client-side locking to guard compound actions.

UnsafeVectorHelpers.java and SafeVectorHelpers.java

Just as encapsulating an object's state makes it easier to preserve its invariants, encapsulating its synchronization makes it easier to enforce its synchronization policy.

Collections' (including Synchronized versions) Iterators can throw ConcurrentModificationException if they are not guarded by the correct lock.

HiddenIterator.java

5.2 Concurrent collections

Replacing synchronized collections with concurrent collections can offer dramatic scalability improvements with little risk.

The java.util.concurrent package includes a number of additions to the Java Collections Framework. These are most easily categorized by the collection interfaces provided:

BlockingQueue defines a first-in-first-out data structure that blocks or times out when you attempt to add to a full queue, or retrieve from an empty queue.
ConcurrentMap is a subinterface of java.util.Map that defines useful atomic operations. These operations remove or replace a key-value pair only if the key is present, or add a key-value pair only if the key is absent. Making these operations atomic helps avoid synchronization. The standard general-purpose implementation of ConcurrentMap is ConcurrentHashMap, which is a concurrent analog of HashMap.
ConcurrentNavigableMap is a subinterface of ConcurrentMap that supports approximate matches. The standard general-purpose implementation of ConcurrentNavigableMap is ConcurrentSkipListMap, which is a concurrent analog of TreeMap.

All of these collections help avoid Memory Consistency Errors by defining a happens-before relationship between an operation that adds an object to the collection with subsequent operations that access or remove that object.

5.3 Blocking queues and the producer-consumer pattern

Bounded queues are a powerful resource management tool for building reliable applications: they make your program more robust to overload by throttling activities that threaten to produce more work than can be handled.

The following example shows how producer-consumer pattern and blocking queue can be used to create a desktop file crawler.

ProducerConsumer.java

5.4 Blocking and interruptible methods

TaskRunnable.java

5.5 synchronizers

CountDownLatch allows one or more threads to wait for a set of events to occur. The constructor takes a positive int as the parameter, representing the number of events to wait for. The countDown method decrements the counter, and the await method wait for the counter to reach zero. If the counter is nonzero, await blocks until the counter reaches zero.

The following is an example usage of CountDownLatch.

TestHarness.java

Actually we already used CountDownLatch in chapter 1 example

AtomicAction1.java

FutureTask is an implementation of Future, which acts like a latch. A computation represented by a FutureTask is implemented with a Callable. Future.get() returns the computation result of the Callable immediately if FutureTask completed, otherwise, Future.get() blocks until the FutureTask reaches completed state then returns the result or throws exception.

Preloader.java

Semaphore manages a set of virtual permits; the initial number of permits is passed to the Semaphore constructor. Threads call acquire() methods to acquire permits and call release() to release permits. If no permit is available, acquire() blocks until one is available.

BoundedHashSet.java

Barriers are similar to latches in that they block a group of threads until some event has occurred. The key difference is that with a barrier, all threads must come together at a barrier point at the same time in order to proceed. Latches are for waiting for events; barriers are for waiting for other threads.

CyclicBarrier allows a fixed number of threads to simultaneously proceed repeatedly at a barrier point and is useful in parallel iterative algorithms that break down a problem into a fixed number of independent subproblems. Threads call await when they reach the barrier point, and await blocks until all the threads have reached the barrier point. Once a barrier has been successfully passed, all threads are released and the barrier is reset for reuse.

In the following examples, we will try to demonstrate the usage of CyclicBarrier with Conway's Life game. Before we went to the topic, lets write a simple single threaded implementation to show the game rule.

GameOfLife.java no GUI version

GameOfLife use println to visualize, which is ugly, we can use the swing event dispatch thread to handle the gui and have SwingWorker thread to handle the game engine, we can also interact with user click on game board grid and start button with ActionListener like we did before. However, let's bear with the display (until next holiday season :) ), for now, let's focus on the performance improvement provided by CyclicBarrier.

CellularAutomata.java no GUI version

5.6 Building an efficient, scalable result cache

Nearly every server application uses some form of caching. Reusing the results of a previous computation can reduce latency and increase throughput, at the cost of additional memory usage.

We already have a test bench for the example of chapter 2, we can reuse the test bench for new cache implementations and compare the performance (with maybe too many TOTALTHREAD of 2000, which simulate 2000 concurrent web service request to the server, and maybe too few of 20 possible request values new StringBuilder().append(rand.nextInt(20));).

Initial cache attempt using HashMap and synchronization

Replacing HashMap with ConcurrentHashMap

Memoizing wrapper using FutureTask

Final implementation of Memoizer

Summary of Part I

It's the mutable state, stupid.

All concurrency issues boil down to coordinating access to mutable state. The less mutable state, the easier it is to ensure thread safety.

Make fields final unless they need to be mutable.

Immutable objects are automatically thread-safe.

Immutable objects simplify concurrent programming tremendous.y. They are simpler and safer, and can be shared freely without locking or defensive copying.

Encapsulation makes it practical to manage the complexity.

You could write a thread-safe program with all data stored in global variables, but why would you want to? Encapsulating data within objects makes it easier to preserve their invariants; encapsulating synchronization within objects makes it easier to comply with their synchronization policy.

Guard each mutable variable with a lock.
Guard all variables in an invariant with the same lock.
Hold locks for the duration of compound actions.
A program that accesses a mutable variable from multiple threads without synchronization is a broken program.
Don't reply on clever reasoning about why you don't need to synchronize.
Include thread safety in the design process -- or explicitly document that your class is not thread-safe.
Document your synchronization policy.