Parallel Programming: Java Threads, Concurrency, and Synchronization - PDF

Mathematics 3980: Parallel Programming Dr. Andrew Mertz Mathematics and Computer Science Department Eastern Illinois University Syllabus and Web Site Programming Environments There are many types of programming environments: Multiprogramming: Multiple processes in a u...

Mathematics 3980: Parallel Programming Dr. Andrew Mertz Mathematics and Computer Science Department Eastern Illinois University Syllabus and Web Site Programming Environments There are many types of programming environments: Multiprogramming: Multiple processes in a uniprocessor system. Multiprocessing: Multiple processes within a multiprocessor system. Distributed Processing: Multiple processes across multiple systems. Programming Environments There are many types of programming environments: Multiprogramming: Multiple processes in a uniprocessor system. Multiprocessing: Multiple processes within a multiprocessor system. Distributed Processing: Multiple processes across multiple systems. Important to all of these is concurrency. Concurrency Concurrency is when tasks execute in overlapping time periods. Parallelism is when tasks execute at the same time. Parallelism can be simulated in software, but true parallelism requires hardware. Concurrency Contexts Multiple Applications: The original goal of multiprogramming was to dynamically share processing time and resources of multiple applications. Multithreaded Programming: Some application benefit by being programmed as a set of concurrent processes. Operating Systems: The same benefits that apply to multithreaded programming often apply to operating systems. Multithreaded Programming in Java Java has had built in support for multithreaded programming since its inception Java 5 added the concurrent API that added synchronizers like semaphores Java 7 added the fork/join framework which Java 8 enhanced Java 9 added Reactive Streams Multithreaded Programming in Java A multithreaded program contain two or more parts, called threads, that can run concurrently Each thread defines a separate path of execution Each thread has a priority that determines how behaves with respect to other threads When we do GPU programing we will see a very different thread model Java Thread States Thread is java can be in different states: It can be running It can be ready to run as soon as CPU time becomes available It can be suspended It can be resumed (picks up where it left off after being suspended) It can be blocked while waiting for a resource It can be terminated (can not be resumed) Creating Threads There are two ways to create threads in Java: Implement the Runnable interface Extend the Thread class Design Issues Concurrent programming has many design issues: Communication between processes Sharing/Competing for resources Synchronization Scheduling Control Problems Concurrent processes have many potential problems: Mutual exclusion Deadlock Starvation Coherence Mutual Exclusion and Synchronization Mutual exclusion becomes a problem when two process require a non-sharable resource. Such a resource is called a critical resource. A block of code that requires a critical resource is called a critical section. Given any critical resource, only one process should be allowed into the corresponding critical sections at a time. Note that this could lead to deadlock or starvation. Mutual Exclusion in Java Java provides language level support for mutual exclusion via the synchronized keyword. In Java each object possesses a monitor. A monitor can only have one thread in it at a time, but the same thread can be in several monitors at once. To enter a synchronized method a thread must be in the corresponding object’s monitor. If it is not it waits until the monitor is free. access synchronized returnType methodName(parameters) {...} Note that static methods can not synchronized. synchronized Code Blocks We can also create synchronized code blocks that use a given object’s monitor. We can create synchronized methods for the classes we make. However, we may want to use a class that was not designed for multithreaded access. Synchronized code blocks solve this problem. synchronized(myObject) {...} To enter this code block the current thread must be in the monitor for the object myObject. Deadlock When working with multiple threads great care must be taken to avoid an error known as deadlock. Deadlock occurs when two or more processes have a circular dependency on critical resources (e.g. object monitors or semaphores). Deadlock can be very difficult to debug and detect. Often occurs only rarely, when the threads time slice in just the right way. Can involve many threads and monitors in a convoluted chain of dependencies. Comments on Java Threads Many methods of the Thread class are deprecated and should not be used as they can cause system instability and/or deadlock. destroy() resume() stop() suspend() They are deprecated because they can leave threads in monitors. Cancellation Because the direct cancellation stop and destroy are deprecated we should create our own methods for indirect cancellation. Waiting Threads can sleep for a given amount of time with Thread.sleep(). However, sleeping is rarely a useful (or correct) way of coordinating threads. Incorrect Producer and Consumer Example Waiting A Thread can also wait() on an object. This causes the current thread to wait until another thread invokes the notify() or notifyAll() methods for this object. To call wait() the current thread must own the object’s monitor. Correct Producer and Consumer Example Using Java Collections Note many Java collections are not synchronized. Thus if multiple threads access a collection concurrently, and a threads is going to modify the collection structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the collection. This is best done at creation time, to prevent accidental unsynchronized access. For example: List list = Collections.synchronizedList(new ArrayList(...)); Using Java Collections You can also use the alternatives from the concurrent API such as: ArrayBlockingQueue ConcurrentHashMap ConcurrentLinkedDeque... These and more are in the package java.util.concurrent. volatile Modifier Variables can be modified by the keyword volatile. This tells the compiler that the variable can be changed unexpectedly by other parts of the program, such as in a multithreaded program. class MyThread extends Thread { private volatile boolean running = true; synchronized public void setRunning(boolean running){ this.running = running; } public void run(){ while(running){ System.out.println("Still Going"); } } } volatile Modifier If running was not declared to be volatile the compiler would be free to optimize the loop so that a local copy of running is used. Comments on CPU Threads Must think concurrently not serially. Careful use of threads can lead to very efficient programs. Too many threads can degrade performance. Most GUI based programs are inherently multithreaded. Threads that catch events should not be put under a heavy load or they can miss events. The importance of efficient multithreaded programming will only increase in the future. Julia Set Example Speedup Told Slatency = Tnew Jnew Sthroughput = Jold Note speedup is dimensionless. Speedup > 1 means the new method is faster, while a speedup of < 1 means it is slower. Perfectly Parallel A perfectly parallel (also called embarrassingly parallel) problem, is one where little or no effort is needed to separate the problem into a number of parallel tasks. More concretely they are problems where n threads executing concurrently could theoretically yield a speedup of n. Homework 01 Concurrent API Synchronizers Executors Concurrent Collections Fork/Join Framework Synchronizers Semaphore: A classic counting semaphore ReentrantLock: A reentrant mutex ReentrantReadWriteLock: Holds separate locks for read and write access CountDownLatch: Waits until a given number of events have occurred CyclicBarrier: Have a group of threads wait a given location Exchanger: Swap data between two threads Phaser: Synchronize threads through multiple phase of an operation Semaphore Constructors Java semaphores are similar to classic counting semaphores. Semaphore(int value) Semaphore(int value, boolean fair) value is the initial value of the semaphore. If fair is true then waiting threads will be woken in the order they requested access. How to Wait The acquire methods will decrement the value of the semaphore by one or by the given amount. If the value would be negative them the calling thread must wait. void acquire() throws InterruptedException void acquire(int amount) throws InterruptedException void acquireUninterruptibly() void acquireUninterruptibly(int amount) How to Signal The release methods will increment the value of the semaphore by one or by the given amount. If the value is now large enough for a waiting thread to decrement it will be woken. void release() void release(int amount) See the javadoc for the other semaphore methods. Note that the slide will only show the most important methods. Always check the javadoc Demos Race synchronize vs. semaphore Producer and Consumer Revisited CountDownLatch A CountDownLatch is a great tool to block a collection of threads that are to be released after a given number of events. CountDownLatch(int numberOfEvents) void await() throws InterruptedException void countDown() Use await() to block a thread until the events have occurred. Use countDown to indicate that an event has happened. Demo Work in stages CyclicBarrier Many problems require a collection of threads to wait a location until all threads in the collection have arrived. CyclicBarrier is designed to solve this problem. CyclicBarrier(int numberOfThreads) int await() throws InterruptedException, BrokenBarrierException Demo H2 O Mutex You can use a Semaphore with 1 permit as a mutex. However if you want to support reentrantcy it is easier to use a ReentrantLock. ReentrantLock() ReentrantLock(boolean fair) void lock() void unlock() However, unlike semaphores to unlock the thread must have have been the one to lock it. Thus, we could not have used a ReentrantLock for the mutex in the H2 O problem. Readers and Writers ReentrantReadWriteLocks can be used to improve concurrency in some uses of Collections. This is typically worthwhile only when the collections are expected to be large, accessed by more reader threads than writer threads, and entail operations with overhead that outweighs synchronization overhead. Readers and Writers class RWDictionary { private final Map m = new TreeMap(); private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(); private final Lock r = rwl.readLock(); private final Lock w = rwl.writeLock(); public Data get(String key) { r.lock(); try { return m.get(key); } finally { r.unlock(); } } public Data put(String key, Data value) { w.lock(); try { return m.put(key, value); } finally { w.unlock(); } }... Exchanger The Exchanger class allows two threads to swap data. It waits until two threads call its exchange() method then swaps the given data. Demos Producer and Consumer one more time Executor Executors give us an alternative to directly manging threads. The Executor interface declares the execute method which starts the given thread. void execute(Runnable thread) ExecutorService extends Executor adding methods to control the threads. For example: void shutdown() ExecutorService static ExecutorService newCachedThreadPool() static ExecutorService newFixedThreadPool(int num) static ExecutorService newScheduledThreadPool(int num) Run ThreadPoolDemo Callable Sometimes we want threads that return values. The Callable interface is used to represent such task. The Callable interface declares the call method T call() throws Exception You then implement your task as a call method that either return a result or throws some exception on failure. Callable, Future, and ExecutorService To run a Callable object you submit it to an ExecutorService. Future submit(Callable task) This returns a Future object that you can use to the result. To retrieve the result you use the get method of Future, which will block until the value is ready. T get() See Futures demo Data The concurrent API defines many collection classes that are easy to use and provide support for concurrent usage. The java.util.concurrent.atomic package defines objects that support atomic operations on Integers, Longs and other data types. Fork/Join Framework While Java threads are very versatile, they are have a lot of overhead and where not designed for high performance multiprocessing. Thus the need for Fork and Join Framework which allows a large number of tasks to be managed by small number of threads in a much more efficient way. ForkJoinTask ForkJoinPoolb RecursiveAction (returns a value) RecursiveTask Fork/Join threads are daemon threads and will end if main ends. Fork/Join Framework The Fork/Join framework is well suited to the divide and conquer strategy. if work is small enough do the work directly else split my work into pieces invoke the pieces and wait for the results The Fork/Join framework uses a work stealing algorithm for load balancing. Some features in Java are implemented using the fork/join framework. e.g. Arrays.parallelSort(), Parallel Streams and more. Fork/Join Demos