Principles of Java Multicore Programming

Techniques and Caveats

Created by Ray Imber

Use the arrow keys to navigate

Why Java?

• Java runs on many devices.

• The VM abstracts many details.

• Java has specific language concepts and structures for dealing with parallelism.

  • These structures have their own peculiariarities in behavior

  • Parallelism in an Object Oriented Language

Parallelism vs. Concurrency

• Concurrency: The composition of independently executing processes

• Concurrency is an algorithmic and software design concern; like memoziation, or recursion

• Parallelism: The simultaneous execution of (possibly related) computations

• Parallelism is an implementation concern; Threads, SIMD, cluster/network computing

Rob Pike on this topic

C.A.R Hoare CSP Paper

A Process vs. A Thread

• Process: Fork and Join style parallelism
  • A Child program is spawned
  • No Shared memory
  • limited communication options
  • Entire new memory space
  • OS must execute and manage entire new process
• Thread
  • Shared Memory
  • Extensive communication options
  • Share memory space with parent
  • OS has to manage much less (Just thread state)

Java 8 Lambda Expressions

• Functional Interface or Single Abstract Method interfaces
• The Old Syntax:
  • Create an anonymous inner class with just one method
  • Very cumbersome.
• New way:
  • Single expression
  • Converted into a class by the compiler

    () -> ;

Official Java Docs

Java Threads

• Java has a thread Object.

  • Represents the thread itself, not the executed logic.

• Thread Object executes Objects that implement the Runnable Interface

  • The Runnable object can subclass a class other than Thread.

  • This approach is more flexible

  • Applicable to the high-level thread management APIs covered later

The Runnable Interface

• The Runnable Interface has one method: public void run().

• This can be represented as a "Lambda Expression" in Java 8.

• run takes no arguments and returns nothing.

  • How is Thread communication achieved?

  • (We will discuss this in much greater detail soon)

A Simple Example

public class HelloRunnable implements Runnable {

    public void run() {
        System.out.println("Hello from a thread!");
    }

    public static void main(String args[]) {
        (new Thread(new HelloRunnable())).start();
    }

}

Java 8 Equivalent

public class HelloLambdaRunnable {

    public static void main(String args[]) {
        (new Thread(() -> System.out.println("Hello from a thread!");)).start();
    }

}

Sleep, Interrupt, and Join

Join me while I sleep and don't Interrupt :-P

Sleep

• Thread.sleep causes the current thread to suspend execution for a specified period.

• Two Versions of Sleep:

  • Millisecond Accuracy
  • Nanosecond Accuracy

• Sleep times are not guaranteed to be precise

  • Limited by the OS.

Interrupts

• Indication to a thread that it should stop what it is doing and do something else.

  • That usually means the thread just terminates, but it could do other things.

• Two ways of dealing with Interrupts

  • High Level: catch InterruptedException
  • Low Level: check the Thread.interrupted() flag

Example

Using Exceptions

for (int i = 0; i < importantInfo.length; i++)
{
    // Pause for 4 seconds
    try
    {
        Thread.sleep(4000);
    }
    catch (InterruptedException e)
    {
        // We've been interrupted: no more messages.
        return;
    }
    // Print a message
    System.out.println(importantInfo[i]);
}

Example

Using the Interrupt flag

for (int i = 0; i < inputs.length; i++)
{
    heavyProcessing(inputs[i]);
    if (Thread.interrupted())
    {
        // We've been interrupted: no more crunching.
        return;
    }
}

OR

Throw our own InterruptedException

for (int i = 0; i < inputs.length; i++)
{
    heavyProcessing(inputs[i]);
    if (Thread.interrupted())
    {
        throw new InterruptedException();
    }
}

Causing Interrupts Yourself

• You can interrupt a thread yourself using Thread.interrupt()
  • This sets the internal interrupt flag to true for a particular thread.
  • No guarantee that the thread will respect your interrupt request!

Join

• Thread.join() causes one thread to wait for another.

• Join throws interruptedExcpetions, just like sleep.

• You can pass an optional timeout to limit the amount of time the thread will wait.

Example

public static void main(String args[])
    throws InterruptedException {
        Thread t = new Thread(new WorkerObject());
        t.start();
        // Wait maximum of 1 second
        // for Thread
        // to finish.
        t.join(1000);

        if ( t.isAlive() ) {
            // Tired of waiting!
            t.interrupt();
            // Shouldn't be long now
            // -- wait indefinitely
            t.join();
        }
    }

Thread Pools

Let's go swimming

• In large-scale applications, it makes sense to separate thread management and creation from the rest of the application

• Known as executors in Java

What do Thread Pools do?

• Creating new Threads is expensive in terms of memory and time for creation.

• Instead of creating a new Thread for each new job, ad-hoc.

• Create a pre-defined set of worker Threads at the begining of the program.
• These worker threads never terminate.
  • They wait for a job.
  • They Execute the job.
  • They are then recycled.

See Java Docs for more info

The Optimal Thread Pool Size

Little's Law

• Start with an arbitrary Pool Size.
• Measure rate at which work unit requests arrive and the average amount of time to service them.
• Calculate the average number of requests in the system.
• If L is less than the pool size, reduce the pool size.
• If L is greater than the pool size, determine if system can support a larger thread pool.

Executor Interface

• Executor: Launches a runnable. Simplest interface.
• ExecutorService: Subinterface of Executor. Adds features for managing the lifecycle of tasks and of the executor.
• ScheduledExecutorService: Subinterface of ExecutorService. Adds support for future and/or periodic execution of tasks.

Java Docs

Types of Executors

• Standard Thread Pool
• Fork/Join Pool

Fixed Thread Pool

• Cached Thread Pool

• Single Thread Pool

• ScheduledExecutorService

  • Executes a Runnable or Callable task after a specified delay or at an interval.

Fork/Join Pool

• Uses a work-stealing algorithm.
• Worker threads that run out of things to do can steal tasks from other threads that are blocked.
• Must subclass the computation with ForkJoinTask
• Typically Recursive

  if (my portion of the work is small enough)
  do the work directly
  else
  split my work into two pieces
  invoke the two pieces and wait for the results

Java Docs

Java Memory Models

It's all about sharing

Thread State

• A Thread State has three parts
  • Program Counter
  • (Thread) Local Variables
  • Shared Variables

Shared vs Local Variables

• Thread communication is achieved through Shared Variables.

• All memory in Java must be contained in Objects.

  • Must have a way to seperate Shared memory from Local memory.
  • We must use a model to conceptualize this separation.

Java Object Models

• Two Object Models for Thread Variables
  • One Thread / One Object
  • Multiple Threads / One Object

One Thread / One Object

Example

Thread thread[] = new Thread[maxThreads];
for( int i = 0 ; i < maxThreads ; i++ )
{
    thread[i] = new Thread(new Worker());
}

Multiple Threads / One Object

Example

Thread thread[] = new Thread[maxThreads];
Worker singleRunnable = new Worker();
for( int i = 0 ; i < maxThreads ; i++ )
{
    thread[i] = new Thread(singleRunnable);
}

Locks and Atomic Variables in Java

• Synchronized
• Volatile

Synchronized

Locking in Java

• Synchronized is implemented with a Monitor Lock

  • See Chapter 8 of the textbook (pg.177).

• Two Ways to use

  • Synchronized Methods
  • Synchronized Statements

Synchronized Methods

• Simplest way to use locks in Java.

• The entire method becomes a critical section.

• The lock is attached to this.

• Static Synchronized lock is attached to the class object.

Example

public class SynchronizedCounter
{
    private int c = 0;
    private static int s = 1;

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

    public synchronized int value() {
        return c;
    }

    public static synchronized int staticValue() {
        return s;
    }
}

Memory Model

Synchronized Statements

• More control than synchronized methods.

• Define a specific block of statements to be the critical section.

• More efficient than locking the whole method.

• Can control which lock you use.

Example

public class MsLunch
{
    private long c1 = 0;
    private long c2 = 0;
    private Object extLock = new Object();

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

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

Memory Model

Code Example

private static int x;

private void readAndWrite() {
    int temp;
    synchronized(this){
        // Update Shared Class Variable
        temp = x;// Read x
        temp=temp+1;// increment x
        x=temp;// write x
    }
}
...
public static void main(String args[]) {
    Thread thread[] = new Thread[maxThreads];// Create a thread array
    for( int i = 0 ;i < maxThreads ; i++ ) {
        thread[i] = new Thread(new BadSync());
    }
}

Dangers of Improper Locking

Final Note about Synchronized

• Recall that All Objects in Java implement the Monitor interface
• Synchronized uses this implicit monitor to work
• You can use the monitor directly in your code!
• All of the Monitor Methods are available to you
  • wait()
  • notify()
  • notifyAll()

Volatile

• Makes any variable atomic. This includes objects (but not necessarily properties of the object)!

  • a.k.a pointers
  • 64 bit variables : doubles and longs

• A write to a volatile variable establishes a happens-before relationship with subsequent reads of that same variable

• Side effects that lead up to the change of the variable are also completely visible.

Volatile Cons

• Volatile is awesome, why should we ever use Synchronized?

• Volatile only works for simple reads and writes.

  • No complex logic.

• Only applys to An Object's Reference not it's properties.

  • This applies to arrays and array elements as well.

• Volatile only guarantees order inside a single thread is preserved.

  • This is a special guarantee that can be difficult to reason about.
  • Happens Before does not guarantee total ordering!

Example

class VolatileTest {
    static volatile int i = 0, j = 0;

    static void threadOne() { i++; j++; }

    static void threadTwo() { System.out.println("i=" + i + " j=" + j); }

    }

Volatile Perfomance vs. Synchronized Performance

• Volatile and Synchronized force cpu caches to be flushed on a write.

  • Synchronized flushes all caches.
  • Volatile flushes only the cache block containing the written variable.

• Volatile can never have a higher overhead than synchronized.

  • Synchronized has to do locking and unlocking overhead.
  • Volatile does not have any lock overhead.

• Synchronized can have the same overhead if the compiler (JIT) is able to optimize it.

The Cost of a Volatile Cache Flush

Atomic Operations

• What operations are Atomic in Java?

• Reads and writes are atomic for reference variables and for most primitive variables

  • Except long and double.

• Reads and writes are atomic for all variables declared volatile

  • Including long and double.

• Memory consistency errors are still possible!

Atomic Primatives

• Library of special Atomic Classes provided by Oracle in the Standard Library
• Internally, the atomic classes use compare-and-swap (CAS)

AtomicInteger, AtomicBoolean, AtomicLong, and AtomicReference

• incrementAndGet()
• updateAndGet(lambdaExpression)
• accumulateAndGet(lambdaExpression)

LongAdder, LongAccumulator

• Just like the equivalent Atomic Class but
• Maintains a set of variables internally to reduce contention over threads
• Preferable when updates from multiple threads are more common than reads
• The drawback is higher memory consumption from the extra variables

Example

class FinalFieldExample {
    final int x;
    int y;
    static FinalFieldExample f;

    public FinalFieldExample() { x = 3; y = 4; } //constructor

    static void writer() { f = new FinalFieldExample(); }
    static void reader() {
        if (f != null) {
            int i = f.x; // guaranteed to see 3
            int j = f.y; // could see 0
        }
    }
}

Futures (Java 8)

• Callable interface: Lke the Runnable interface but
• Returns a value
• Callables can be submitted to executor services just like runnables
• Executor.submit() does not wait until the task completes
• The executor service cannot return the result of the callable directly
• Instead the executor returns a special result of type Future

Futures Continued

• Future can be used to retrieve the actual result at a later point in time
• Future.isDone() : check if the result is ready yet
• Future.get() : blocks the current thread and waits until the callable completes before returning the actual result

Batching Futures

• Executors support batch submitting of multiple callables at once via Executor.invokeAll()
• Accepts a collection of callables and returns a list of futures

Concurrent Collections

• Pre-built data-structures and algorithms provided by Oracle that are Thread Safe and Thread Optimized.

• These are NOT built into the language. They are libraries, provided for your convenience.

• Many of these libraries are implemenations based on the theories from this course.

See Java Docs for more info

Common Concurrent Collections

• BlockingQueue:
  • A FIFO data structure that blocks or times out on add to a full queue, or retrieve from an empty queue.
• ConcurrentHashMap:
  • A concurrent analog of HashMap.
  • Java 8 has greatly improved the implementation.
• ConcurrentSkipListMap:
  • A concurent analog of a Red-Black tree.
• ThreadLocalRandom:
  • A thread optimized random number generator.
  • Math.random() is thread safe, but performs badly.

Java Strings

• Java Strings are implemented with Final.

• Many security features of the Java programming language depend upon String objects being immutable.

• Any time a Java string is modified, a new String object is referenced, the raw data buffer is never changed.

• String Pool saves memory by attempting to re-use old Strings if possible.

Different String Alternatives

• String vs. StringBuilder vs. StringBuffer

• String : immutable

  • Memory inefficient but fast and very thread safe.

• String Buffer : mutable, but protected with locks.

  • Memory efficient but slow because of locks.

• String Builder : mutable, no protection.

  • Raw Char buffer like C++ String.
  • Memory efficient and fast, but not thread safe at all.

String Alternatives Comparision

References and Further Reading

• The Official Java Tutorials on Concurrency
• Java Concurrency Package API
• Java Memory Model
• Java Concurrency in Practice (Book)
• Java Performance Tuning
• Java Specification on Final Fields
• Comparison of String Class Alternatives
• Five things you didn't know about Java Multithreading
• Thread Pool Performance Tuning
• Implementing a Monitor Lock in Java
• Prisoner Problem Case Study

Thank You