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
Note:
Java runs on many devices. This is both an advantage and a disadvantage.
We are going to discuss the basic syntax and semantic rules for dealing with parallelism in Java.
We will discuss some of the more advanced details of Java parrallel semantics and the problems
that can occur.
## 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](http://blog.golang.org/concurrency-is-not-parallelism)
[C.A.R Hoare CSP Paper](http://www.cs.ucf.edu/courses/cop4020/sum2009/CSP-hoare.pdf)
## 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
```java
() -> ;
```
[Official Java Docs](https://docs.oracle.com/javase/8/docs/api/java/lang/FunctionalInterface.html)
## 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
```java
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
```java
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
```java
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
```java
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
```java
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
```java
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](http://docs.oracle.com/javase/tutorial/essential/concurrency/pools.html)
## 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](https://docs.oracle.com/javase/tutorial/essential/concurrency/exinter.html)
## 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](https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html)
## 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
```java
Thread thread[] = new Thread[maxThreads];
for( int i = 0 ; i < maxThreads ; i++ )
{
thread[i] = *new Thread(new Worker())*;
}
```
## Multiple Threads / One Object
## Example
```java
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
```java
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
```java
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++;
}
}
}
```
Note: extLock is just a generic object. All Objects in Java have a monitor lock built in. It's part of the language. ANY object can be used as a lock because of this property. Be careful when interleiving locks!
## Memory Model
## Code Example
```java
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.
Note: All threads flushing their cache, is obviously a huge performance hit! Use Volatile conservatively.
## 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
```java
class VolatileTest {
static *volatile* int i = 0, j = 0;
static void threadOne() { *i++; j++;* }
static void threadTwo() { System.out.println(*"i=" + i* + *" j=" + j*); }
}
```
Note: i will always increment before j, but thread 2 could read a value for i, sleep for a very long time, and then come back and read a MUCH larger value for j. This would not happen with Synchronized. Volatile is important for implementing complex non-blocking data-structures and algorithms, but it is not a replacement for locks / synchronized.
## 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!
Note: Atomic does not mean the cache will be synced properly. A write will be Atomic, but that does not guarantee that another thread will see that write immediately.
## 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
```Java
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](http://docs.oracle.com/javase/tutorial/essential/concurrency/collections.html)
## 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](http://docs.oracle.com/javase/tutorial/essential/concurrency/index.html)
* [Java Concurrency Package API](http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/package-summary.html)
* [Java Memory Model](http://www.cs.umd.edu/~pugh/java/memoryModel/)
* [Java Concurrency in Practice (Book)](http://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601)
* [Java Performance Tuning](http://www.javaperformancetuning.com/news/qotm051.shtml)
* [Java Specification on Final Fields](http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.5)
* [Comparison of String Class Alternatives](http://javarevisited.blogspot.com/2011/07/string-vs-stringbuffer-vs-stringbuilder.html)
* [Five things you didn't know about Java Multithreading](http://www.ibm.com/developerworks/library/j-5things15/)
* [Thread Pool Performance Tuning](http://www.infoq.com/articles/Java-Thread-Pool-Performance-Tuning)
* [Implementing a Monitor Lock in Java](http://baptiste-wicht.com/posts/2010/09/java-concurrency-part-5-monitors-locks-and-conditions.html)
* [Prisoner Problem Case Study](http://anttila.ca/michael/100prisoners/)
## Thank You