Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Concurrent Programming: Two Techniques to Avoid Shared State

DZone 's Guide to

Concurrent Programming: Two Techniques to Avoid Shared State

The best solution for concurrent programming is to avoid shared state.

· Java Zone ·
Free Resource

The more I learn about multi-threaded programming, the harder it gets. Coordinating multiple threads and modifying the same data is complicated. The java.util.concurrent.ConcurrentHashMap, for example, needs, with 4264 lines of code, two times more lines of code than its single-threaded counterpart, the java.uti.HashMap, with 1617 lines of code.

So, I think the best solution for concurrent programming is to avoid shared state.

The first technique to avoid shared state is to copy the data before each modification. This technique relies on the fact that updating a single variable is easy. Only when we need to update multiple variables things get complicated.

Copy Before Modification

The following shows this technique using java.util.concurrent.locks.ReentrantLock for writing and a volatile field for reading:

final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;  
public E get(int index) {
     return (E) array[index];
}   
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
       Object[] elements = array;
       E oldValue = (E) elements[index];
       if (oldValue != element) {
          int len = elements.length;
          Object[] newElements = Arrays.copyOf(elements, len);
          newElements[index] = element;
          array = newElements;
      } else {
          // Not quite a no-op; ensures volatile write semantics
      array = elements;
       }
          return oldValue;
    } finally {
    lock.unlock();
    }
}


The example is based on the class java.util.concurrent.CopyOnWriteArrayList.

Reading consists of reading the volatile variable array and then the ith array element, line 4. Writing consists of locking the ReentrantLock, line 7. Then, if the current element and the new array element are no longer the same, creating a local copy of the array, line 14, modifying the local copy, line 15, and finally setting the array variable to the newly created array, line 16. Why do we need a volatile variable instead of a normal variable? This is further explained in this blog post.

The technique implies to copy the data each time we want to modify the data structure. Using so-called persistent data structures, we can avoid copying the complete data structures. Persistent data structures keep the old state together with the modification. This post by the Bifurcan Project compares different libraries that implement persistent data structures.

Copying before modifying works best for workloads consisting of multiple reads and few writes. The second technique works best for the opposite type of workloads, multiple writes, and only a few reads:

Asynchronous Modification Using a Single Thread

The idea of this technique is to use a single thread, which owns the state and a messaging queue to let other threads modify the state through this thread. The following example shows how to implement this technique using the ExecutorService:

ExecutorService executor = Executors.newFixedThreadPool(1);
executor.execute( () -> modifyState() );
executor.execute( () -> modifyState() );
executor.shutdown();
executor.awaitTermination(10, TimeUnit.MINUTES);


To implement this technique with a single threaded ExecutorService, we first need to create one, line 1. Then, we can modify the state asynchronously using the execute method, line 3 and 4. When we are done, we need to stop the ExecutorService, line 4, and wait until the service is terminated, line 5.

Martin Thompson recommends this technique in this blog post for highly contended data structures. The single event processing thread of UI libraries, like Swing or SWT, is another example usage of this technique. And the idea behind the Akka framework to use messaging between actors instead of shared state is similar to this technique.

What Is Next?

The two techniques presented here are described in further detail in the book Java Concurrency in Practice by Brian Goetz et al. This book is the best resource to learn concurrent programming.

To start with avoiding shared state, we need to know which parts of our application uses a shared state. I added a report in vmlens, a tool I developed to test multi-threaded Java, which shows which method uses shared state. This report is described here.

And if you are interested in writing concurrent collections, like the mentioned ConcurrentHashMap, read the book The Art of Multi-Processor Programming by Maurice Herlihy and Nir Shavit. This book explains how commonly used data structures can be implemented for multi-threaded access.

Topics:
java ,concurrent programming ,modification ,asynchronous ,asynchronous modification ,threads ,single threads ,copy ,shared state ,concurrent

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}