Multithreaded Programming (Apr 7)

Overview

Review exercise
Binary Semaphores
Counting Semaphores
Parallel ideas in sequential programming
Fork/Join Framework
Review Exercise
Program to add up all the numbers from 1 to N
Click here
There are two bugs to fix
Java 8
Java 8 introduced last month
Functional programming — functions are first-class objects
Implementation: a function is like an interface with one method
E.g. Runnable
-> notation and effectively final (example)
Semaphores
in package java.util.concurrent
constructor public Semaphore(int permits) creates a new semaphore with this many permits
public void .acquire() throws InterruptedException asks for permit. if none available, blocks until available or interrupted
public void .acquireUninterruptibly() similar but can't be interrupted
public void .release() returns a permit
Exercise: re-do SumParallel with a Semaphore limited to one permit
As usual, important to prepare for emergencies! After obtaining a permit, use try and call .release() in finally block
Counting Semaphores
To control concurrent access
Example applications: device, file system, network, etc
Exercise: FTPLimiter uses a counting semaphore
Synchonized Data Structures
Built-in synchonized queues: ArrayBlockingQueue, LinkedBlockingQueue, and PriorityBlockingQueue
Three implementations of the BlockingQueue interface
Synchronizing wrappers for other data structures:
synchronizedSet, synchronizedList, synchronizedMap
- Takes any structure and makes its methods synchronized
- But does not synchronize its iterators
- Example: synchronizedMap
Parallel Ideas in Sequential Programming
We can ask a Set for an Iterator through its items
Iterator is a light-weight data structure: not a copy of original, just a "pointer" to an internal item
But if we change data structure while being iterated, iterator may be corrupted
This is also true without parallelism!
ConcurrentModificationException: someone tried to continue using an iterator after underlying data structure was changed
Exercise: CME
Fork/Join
Paradigm for parallel programming without explicit locks
Divide-and-conquer
Methods that return values: RecursiveTask<V>
or RecursiveAction: recursive method w/side effect
both implement ForkJoinTask
ForkJoinPool.invoke(ForkJoinTask) to start
Inside a RecursiveAction:
- .compute: abstract method to perform this task
- Construct ≥2 ForkJoinTasks in .compute()
- Call .invoke on one: run it and wait for it to finish
- Call invokeAll(ForkJoinTask...) on all: run all and wait for all to finish
- What is the difference between these? Exercise
Additional methods for RecursiveTask<V>, which implements a method returning a value of type V: .fork() to start execution, .join() to get value, cancellation methods and more
Other Pitfalls
Recall dining philosophers: each philosopher needs to access more than one resource
Simpler case of two philosophers already has a problem depending on policies:
- Say each has the policy "lock the left, lock the right, unlock the right, unlock the left"
```
leftlock.lock();
rightlock.lock();
//... eat
rightlock.unlock();
leftlock.unlock();
```
- Problem! If they each obtain one lock before anything else, neither can access the second lock/chopstick, but does not put the first one down either
How to deal with arbitrary graph of processes each using 2 out of M locks? (E.g. financial transactions?) ≥ 2?