However,synchronization can introduce?thread contention,which occurs when two or more threads try to access the same resource simultaneously?and?cause the Java runtime to execute one or more threads more slowly,or even suspend their execution.??are forms of thread contention. See the section??for more information.

This section covers the following topics:

• ?describes how errors are introduced when multiple threads access shared data.
• ?describes errors that result from inconsistent views of shared memory.
• ?describes a simple idiom that can effectively prevent thread interference and memory consistency errors.
• ?describes a more general synchronization idiom,and describes how synchronization is based on implicit locks.
• ?talks about the general idea of operations that can't be interfered with by other threads.

public void increment() {
    c++;
}

public void decrement() {
    c--;
}

public int value() {
    return c;
}

Counter?is designed so that each invocation of?increment?will add 1 to?c,and each invocation of?decrement?will subtract 1 from?c. However,if a?Counter?object is referenced from multiple threads,interference between threads may prevent this from happening as expected.

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.

It might not seem possible for operations on instances of?Counter?to interleave,since both operations on?c?are single,simple statements. However,even simple statements can translate to multiple steps by the virtual machine. We won't examine the specific steps the virtual machine takes — it is enough to know that the single expression?c++?can be decomposed into three steps:

1. Retrieve the current value of?c.
2. Increment the retrieved value by 1.
3. Store the incremented value back in?c.

The expression?c--?can be decomposed the same way,except that the second step decrements instead of increments.

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:

1. Thread A: Retrieve c.
2. Thread B: Retrieve c.
3. Thread A: Increment retrieved value; result is 1.
4. Thread B: Decrement retrieved value; result is -1.
5. Thread A: Store result in c; c is now 1.
6. Thread B: Store result in c; c is now -1.

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.

public void inc1() {
    synchronized(lock1) {
        c1++;
    }
}

public void inc2() {
    synchronized(lock2) {
        c2++;
    }
}

public static void main(String[] args) {
    final Friend alphonse =
        new Friend("Alphonse");
    final Friend gaston =
        new Friend("Gaston");
    new Thread(new Runnable() {
        public void run() { alphonse.bow(gaston); }
    }).start();
    new Thread(new Runnable() {
        public void run() { gaston.bow(alphonse); }
    }).start();
}

public synchronized String take() {
    // Wait until message is
    // available.
    while (empty) {
        try {
            wait();
        } catch (InterruptedException e) {}
    }
    // Toggle status.
    empty = true;
    // Notify producer that
    // status has changed.
    notifyAll();
    return message;
}

public synchronized void put(String message) {
    // Wait until message has
    // been retrieved.
    while (!empty) {
        try { 
            wait();
        } catch (InterruptedException e) {}
    }
    // Toggle status.
    empty = false;
    // Store message.
    this.message = message;
    // Notify consumer that status
    // has changed.
    notifyAll();
}

public Producer(Drop drop) {
    this.drop = drop;
}

public void run() {
    String importantInfo[] = {
        "Mares eat oats","A kid will eat ivy too"
    };
    Random random = new Random();

    for (int i = 0;
         i < importantInfo.length;
         i++) {
        drop.put(importantInfo[i]);
        try {
            Thread.sleep(random.nextInt(5000));
        } catch (InterruptedException e) {}
    }
    drop.put("DONE");
}

public Consumer(Drop drop) {
    this.drop = drop;
}

public void run() {
    Random random = new Random();
    for (String message = drop.take();
         ! message.equals("DONE");
         message = drop.take()) {
        System.out.format("MESSAGE RECEIVED: %s%n",message);
        try {
            Thread.sleep(random.nextInt(5000));
        } catch (InterruptedException e) {}
    }
}

// Values must be between 0 and 255.
private int red;
private int green;
private int blue;
private String name;

private void check(int red,int green,int blue) {
    if (red < 0 || red > 255
        || green < 0 || green > 255
        || blue < 0 || blue > 255) {
        throw new IllegalArgumentException();
    }
}

public SynchronizedRGB(int red,int blue,String name) {
    check(red,green,blue);
    this.red = red;
    this.green = green;
    this.blue = blue;
    this.name = name;
}

public void set(int red,blue);
    synchronized (this) {
        this.red = red;
        this.green = green;
        this.blue = blue;
        this.name = name;
    }
}

public synchronized int getRGB() {
    return ((red << 16) | (green << 8) | blue);
}

public synchronized String getName() {
    return name;
}

public synchronized void invert() {
    red = 255 - red;
    green = 255 - green;
    blue = 255 - blue;
    name = "Inverse of " + name;
}

// Values must be between 0 and 255.
final private int red;
final private int green;
final private int blue;
final private String name;

private void check(int red,int blue) {
    if (red < 0 || red > 255
        || green < 0 || green > 255
        || blue < 0 || blue > 255) {
        throw new IllegalArgumentException();
    }
}

public ImmutableRGB(int red,blue);
    this.red = red;
    this.green = green;
    this.blue = blue;
    this.name = name;
}


public int getRGB() {
    return ((red << 16) | (green << 8) | blue);
}

public String getName() {
    return name;
}

public ImmutableRGB invert() {
    return new ImmutableRGB(255 - red,255 - green,255 - blue,"Inverse of " + name);
}

Lock?objects work very much like the implicit locks used by synchronized code. As with implicit locks,only one thread can own a?Lockobject at a time.?Lock?objects also support a?wait/notify?mechanism,through their associated?Condition?objects.

The biggest advantage of?Lock?objects over implicit locks is their ability to back out of an attempt to acquire a lock. The?tryLockmethod backs out if the lock is not available immediately or before a timeout expires (if specified). The?lockInterruptibly?method backs out if another thread sends an interrupt before the lock is acquired.

Let's use?Lock?objects to solve the deadlock problem we saw in?. Alphonse and Gaston have trained themselves to notice when a friend is about to bow. We model this improvement by requiring that our?Friend?objects must acquire locks for?both?participants before proceeding with the bow. Here is the source code for the improved model,?Safelock. To demonstrate the versatility of this idiom,we assume that Alphonse and Gaston are so infatuated with their newfound ability to bow safely that they can't stop bowing to each other:

    public Friend(String name) {
        this.name = name;
    }

    public String getName() {
        return this.name;
    }

    public boolean impendingBow(Friend bower) {
        Boolean myLock = false;
        Boolean yourLock = false;
        try {
            myLock = lock.tryLock();
            yourLock = bower.lock.tryLock();
        } finally {
            if (! (myLock && yourLock)) {
                if (myLock) {
                    lock.unlock();
                }
                if (yourLock) {
                    bower.lock.unlock();
                }
            }
        }
        return myLock && yourLock;
    }

    public void bow(Friend bower) {
        if (impendingBow(bower)) {
            try {
                System.out.format("%s: %s has"
                    + " bowed to me!%n",bower.getName());
                bower.bowBack(this);
            } finally {
                lock.unlock();
                bower.lock.unlock();
            }
        } else {
            System.out.format("%s: %s started"
                + " to bow to me,but saw that"
                + " I was already bowing to"
                + " him.%n",bower.getName());
        }
    }

    public void bowBack(Friend bower) {
        System.out.format("%s: %s has" +
            " bowed back to me!%n",bower.getName());
    }
}

static class BowLoop implements Runnable {
    private Friend bower;
    private Friend bowee;

    public BowLoop(Friend bower,Friend bowee) {
        this.bower = bower;
        this.bowee = bowee;
    }

    public void run() {
        Random random = new Random();
        for (;;) {
            try {
                Thread.sleep(random.nextInt(10));
            } catch (InterruptedException e) {}
            bowee.bow(bower);
        }
    }
}


public static void main(String[] args) {
    final Friend alphonse =
        new Friend("Alphonse");
    final Friend gaston =
        new Friend("Gaston");
    new Thread(new BowLoop(alphonse,gaston)).start();
    new Thread(new BowLoop(gaston,alphonse)).start();
}

As with any?ExecutorService?implementation,the fork/join framework distributes tasks to worker threads in a thread pool. The fork/join framework is distinct because it uses a?work-stealing?algorithm. Worker threads that run out of things to do can steal tasks from other threads that are still busy.

The center of the fork/join framework is the?ForkJoinPool?class,an extension of the?AbstractExecutorService?class.?ForkJoinPoolimplements the core work-stealing algorithm and can execute?ForkJoinTask?processes.

Basic Use

The first step for using the fork/join framework is to write code that performs a segment of the work. Your code should look similar to the following pseudocode:

Wrap this code in a?ForkJoinTask?subclass,typically using one of its more specialized types,either?RecursiveTask?(which can return a result) or?RecursiveAction.

After your?ForkJoinTask?subclass is ready,create the object that represents all the work to be done and pass it to the?invoke()?method of a?ForkJoinPool?instance.

Blurring for Clarity

To help you understand how the fork/join framework works,consider the following example. Suppose that you want to blur an image. The original?source?image is represented by an array of integers,where each integer contains the color values for a single pixel. The blurred?destination?image is also represented by an integer array with the same size as the source.

Performing the blur is accomplished by working through the source array one pixel at a time. Each pixel is averaged with its surrounding pixels (the red,and blue components are averaged),and the result is placed in the destination array. Since an image is a large array,this process can take a long time. You can take advantage of concurrent processing on multiprocessor systems by implementing the algorithm using the fork/join framework. Here is one possible implementation:

// Processing window size; should be odd.
private int mBlurWidth = 15;

public ForkBlur(int[] src,int start,int length,int[] dst) {
    mSource = src;
    mStart = start;
    mLength = length;
    mDestination = dst;
}

protected void computeDirectly() {
    int sidePixels = (mBlurWidth - 1) / 2;
    for (int index = mStart; index < mStart + mLength; index++) {
        // Calculate average.
        float rt = 0,gt = 0,bt = 0;
        for (int mi = -sidePixels; mi <= sidePixels; mi++) {
            int mindex = Math.min(Math.max(mi + index,0),mSource.length - 1);
            int pixel = mSource[mindex];
            rt += (float)((pixel &amp; 0x00ff0000) >> 16)
                  / mBlurWidth;
            gt += (float)((pixel &amp; 0x0000ff00) >>  8)
                  / mBlurWidth;
            bt += (float)((pixel &amp; 0x000000ff) >>  0)
                  / mBlurWidth;
        }

        // Reassemble destination pixel.
        int dpixel = (0xff000000     ) |
               (((int)rt) << 16) |
               (((int)gt) <<  8) |
               (((int)bt) <<  0);
        mDestination[index] = dpixel;
    }
}

Now you implement the abstract?compute()?method,which either performs the blur directly or splits it into two smaller tasks. A simple array length threshold helps determine whether the work is performed or split.

int split = mLength / 2;

invokeAll(new ForkBlur(mSource,mStart,split,mDestination),new ForkBlur(mSource,mStart + split,mLength - split,mDestination));

If the previous methods are in a subclass of the?RecursiveAction?class,then setting up the task to run in a?ForkJoinPool?is straightforward,and involves the following steps:

1. Create a task that represents all of the work to be done.

   // source image pixels are in src // destination image pixels are in dst ForkBlur fb = new ForkBlur(src,src.length,dst);

2. Create the?ForkJoinPool?that will run the task.

   ForkJoinPool pool = new ForkJoinPool();

3. Run the task.

   pool.invoke(fb);

For the full source code,including some extra code that creates the destination image file,see the?ForkBlur?example.

Standard Implementations

Besides using the fork/join framework to implement custom algorithms for tasks to be performed concurrently on a multiprocessor system (such as the?ForkBlur.java?example in the previous section),there are some generally useful features in Java SE which are already implemented using the fork/join framework. One such implementation,introduced in Java SE 8,is used by the?java.util.Arraysclass for its?parallelSort()?methods. These methods are similar to?sort(),but leverage concurrency via the fork/join framework. Parallel sorting of large arrays is faster than sequential sorting when run on multiprocessor systems. However,how exactly the fork/join framework is leveraged by these methods is outside the scope of the Java Tutorials. For this information,see the Java API documentation.

Another implementation of the fork/join framework is used by methods in the?java.util.streams?package,which is part of?scheduled for the Java SE 8 release. For more information,see the??section.

• 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??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.

public void increment() {
    c++;
}

public void decrement() {
    c--;
}

public int value() {
    return c;
}

public synchronized void increment() {
    c++;
}

public synchronized void decrement() {
    c--;
}

public synchronized int value() {
    return c;
}

public void increment() {
    c.incrementAndGet();
}

public void decrement() {
    c.decrementAndGet();
}

public int value() {
    return c.get();
}