Untitled

Programming Environments

• Multiprogramming involves multiple processes in a uniprocessor system.
• Multiprocessing involves multiple processes within a multiprocessor system.
• Distributed Processing involves multiple processes across multiple systems.
• Concurrency is important to all of the above programming enviroments.

Concurrency

• Concurrency is when tasks execute in overlapping time periods.
• Parallelism is when tasks execute at the same time.
• True parallelism requires hardware, while parallelism can be simulated in software.

Concurrency Contexts

• The original goal of multiprogramming was to dynamically share processing time and resources of multiple applications.
• Some applications benefit by being programmed as a set of concurrent processes.
• The 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.
• The concurrent API was added in Java 5, introducing synchronizers like semaphores.
• Java 7 introduced the fork/join framework which Java 8 enhanced.
• Java 9 added Reactive Streams.
• A multithreaded program contains 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 it behaves with respect to other threads.
• GPU programming will be a very different thread model.

Java Thread States

• Thread states include: running, ready to run, suspended, resumed, blocked, terminated.
• Running: currently executing.
• Ready to run: can run as soon as CPU time becomes available.
• Suspended: temporarily halted.
• Resumed: picks up where it left off after being suspended.
• Blocked: waiting for a resource.
• Terminated: cannot be resumed.

Creating Threads

• Two ways exist for creating threads in Java: Implement the Runnable interface and Extend the Thread class.

Design Issues

• Concurrent programming involves several design issues: Communication between processes, Sharing/Competing for resources, Synchronization, and Scheduling.

Control Problems

• Concurrent processes have several potential problems: Mutual exclusion, Deadlock, Starvation, and Coherence.

Mutual Exclusion and Synchronization

• Mutual exclusion becomes a problem when two processes require a non-sharable resource.
• A resource is a critical resource.
• A block of code that requires a critical resource is a critical section.
• Only one process should be allowed into the corresponding critical sections at a time for any critical resource.
• Deadlock or starvation can result of this design.

Mutual Exclusion in Java

• Java provides language level support for mutual exclusion with the synchronized keyword.
• Each object in Java possesses a monitor.
• Monitors can only have one thread inside at a single time; threads can be in several monitors at once, however.
• To enter a synchronized method, a thread must be in the corresponding object's monitor, waiting until it is free.
• Static methods cannot be synchronized.

Synchronized Code Blocks

• Synchronized code blocks use a given object's monitor.
• synchronized methods can be created for classes.
• Synchronized code blocks solve this problem if a class was not designed for multithreaded access.
• To enter this code block the current thread must be in the monitor for the object myObject.

Deadlock

• Great care must be taken to avoid deadlock when working with multiple threads.
• Deadlock occurs when two or more processes have a circular dependency on critical resources, like object monitors or semaphores.
• Debugging and detecting deadlock can be very difficult as it often occurs rarely.

Comments on Java Threads

• Deprecated methods of the Thread class should not be used due to potential system instability and/or deadlock risks.
• Deprecated Methods: destroy(), resume(), stop(), suspend().
• Leaving threads in monitors is why these methods are deprecated.

Cancellation

• Creating custom methods for indirect cancellation is recommended, because direct cancellation methods (stop and destroy) are deprecated.

Waiting

• Threads can sleep for a given amount of time with Thread.sleep().
• Using sleep is rarely a useful way to coordinate threads.
• A Thread can also wait() on an object.
• The current thread waits until another thread invokes the notify() or notifyAll() methods for this object.
• The current thread must own the object's monitor to call wait().

Using Java Collections

• Many Java collections are not synchronized.
• For multiple threads accessing a collection concurrently and modifying it structurally, synchronization is required externally.
• This is accomplished by synchronizing on the object that encapsulates the collection naturally.
• Prevention of unsynchronized access is best done at initial creation.
• Alternatives from the concurrent API can be used, 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 which tells the compiler that the variable can be unexpectedly changed by other parts of the code.

volatile Modifier

• Without declaring running as volatile, compilers could optimize the loop and use a local copy running.

Comments on CPU Threads

• Concurrency should be thought about instead of serial execution.
• Efficient programs can be created with careful use of threads can.
• Too many threads can degrade performance.
• Multithreading is inherent in GUI based programs.
• The importance of efficient multithreaded programming will only increase in the future.
• Threads catching events must not be put under a heavy load.

Speedup

• Speedup is dimensionless.
• Formulas for speedup include:
  • S(latency) = T(old) / T(new)
  • S(throughput) = J(new) / J(old)
• Speedup > 1 means the new method is faster, while a speedup of < 1 means it is slower.

Perfectly Parallel

• A perfectly parallel problem requires little to no effort separating the problem into a number of parallel tasks, and is also called "embarrassingly parallel".
• n threads executing concurrently could theoretically yield a speedup of n in more concrete terms.

Concurrent API

• Concurrent API areas include: Synchronizers, Executors, Concurrent Collections and Fork/Join Framework.

Synchronizers

• Types of Synchronizers include: Semaphore, ReentrantLock, ReentrantReadWriteLock, CountDownLatch, CyclicBarrier, Exchanger, Phaser.
• Semaphore is a clasic counting semaphore.
• ReentrantLock is a reentrant mutex.
• ReentrantReadWriteLock holds separate locks for read and write access.
• CountDownLatch waits until a given number of events have occurred.
• CyclicBarrier has a group of threads wait a given location.
• Exchanger swaps data between two threads.
• Phaser synchronizes threads through multiple phases of an operation.

Semaphore Constructors

• Java semaphores are similar to classic counting semaphores.
• Two types include: Semaphore(int value) and Semaphore(int value, boolean fair).
• "value" is the initial value of the semaphore.
• If fair is true, 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.
• The calling thread will wait if the value would be negative.
• Methods include: void acquire() throws InterruptedException, void acquire(int amount) throws InterruptedException, void acquireUninterruptibly(), and void acquireUninterruptibly(int amount).

How to Signal

• The release methods increment the value of the semaphore by one or by the given amount.
• A waiting thread will awaken if the value is now large enough to decrement.
• Methods: void release() and void release(int amount).

CountDownLatch

• A CountDownLatch is a great tool to block a collection of threads that are to be released following a given number of events.
• Code: 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.

CyclicBarrier

• Many problems need a collection of threads that are to wait a location until all threads in the collection have arrived.
• CyclicBarrier is designed to solve this problem.
• Code: CyclicBarrier(int numberOfThreads), int await() throws InterruptedException, BrokenBarrierException

Mutex

• You can use a Semaphore with 1 permit as a mutex.
• ReentrantLock is easier for supporting reentrancy.
• Code: ReentrantLock(), ReentrantLock(boolean fair), void lock(), void unlock()
• Unlike semaphores, the thread must be the one to lock it to unlock it.

Readers and Writers

• ReentrantReadWriteLocks are useful for improving concurrency in Collections.
• This matters when: Collections are large, Collections are accessed more by reader threads than writer threads, entail operations with overhead that outweighs synchronization overhead.

Exchanger

• The Exchanger class is used for allowing two threads to swap data.
• It waits until two threads call its exchange() method.

Executor

• Executors provide an alternative to directly manging threads.
• The Executor interface declares the execute method which starts the given thread with: void execute(Runnable thread).
• ExecutorService extends Executor adding methods to control the threads such as: void shutdown().

ExecutorService

• There are methods for creating different types of thread pools:
  • static ExecutorService newCachedThreadPool().
  • static ExecutorService newFixedThreadPool(int num).
  • static ExecutorService newScheduledThreadPool(int num).

Callable

• Some threads need to return values.
• The Callable interface is used to represent such task.
• The Callable<T> 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<T> submit(Callable<T> 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()

Data

• The concurrent API defines many collection classes that are easy to use and support concurrent usage.
• The java.util.concurrent.atomic package defines objects with atomic operations.

Fork/Join Framework

• Java threads are versatile yet have a lot of overhead and aren't designed for high performance.
• The Fork and Join Framework are needed because they enable a large number of tasks to be managed by small number of threads.
• Types: ForkJoinTask, ForkJoinPoolb, RecursiveAction, RecursiveTask.
• Fork/Join threads are daemon threads and will end if main ends.

Fork/Join Framework

• This framework is well suited to the "divide and conquer" strategy.
• if work is small enough, do the work directly.
• Split the current work into pieces and invoke them to get results if the work is too large.
• The Fork/Join framework uses a "work stealing" algorithm for load balancing.
• Some Java features use the framework such as: Arrays.parallelSort() and Parallel Streams.