Transcript What are “condition objects”?

8. Condition Objects
Prof. O. Nierstrasz
Selected material © 2005 Bowbeer,
Goetz, Holmes, Lea and Peierls
Condition Objects
Roadmap
>
Condition Objects
— Simple Condition Objects
— The “Nested Monitor Problem”
— Permits and Semaphores
>
JUC (java.util.concurrent)
© Oscar Nierstrasz
2
Condition Objects
Roadmap
>
Condition Objects
— Simple Condition Objects
— The “Nested Monitor Problem”
— Permits and Semaphores
>
JUC (java.util.concurrent)
© Oscar Nierstrasz
3
Condition Objects
Pattern: Condition Objects
Intent: Condition objects encapsulate the waits and
notifications used in guarded methods.
Applicability
> To simplify class design by off-loading waiting and
notification mechanics.
— Because of the limitations surrounding the use of condition
objects in Java, in some cases the use of condition objects will
increase rather than decrease design complexity!
>
…
© Oscar Nierstrasz
4
Condition Objects
Pattern: Condition Objects
Applicability
…
> As an efficiency manoeuvre.
— By isolating conditions, you can often avoid notifying waiting
threads that could not possibly proceed given a particular state
change.
As a means of encapsulating special scheduling policies
surrounding notifications, for example to impose fairness
or prioritization policies.
> In the particular cases where conditions take the form of
“permits” or “latches”.
>
© Oscar Nierstrasz
5
Condition Objects
Condition Objects
A client that awaits a condition blocks until another object
signals that the condition now may hold.
public interface Condition {
public void await (); // wait for some condition
public void signal (); // signal that condition
}
Counter
Cf. java.util.concurrent.locks.Condition
© Oscar Nierstrasz
6
Condition Objects
A Simple Condition Object
We can encapsulate guard conditions with this class:
public class SimpleConditionObject implements Condition
{
public synchronized void await () {
try { wait(); }
catch (InterruptedException ex) {}
}
public synchronized void signal () {
notifyAll ();
}
}
NB: Careless use can
lead to the “Nested
Monitor Problem”
© Oscar Nierstrasz
7
Condition Objects
Roadmap
>
Condition Objects
— Simple Condition Objects
— The “Nested Monitor Problem”
— Permits and Semaphores
>
JUC (java.util.concurrent)
© Oscar Nierstrasz
8
Condition Objects
The Nested Monitor problem
We want to avoid waking up the wrong threads by
separately notifying the conditions notMin and notMax:
public class BoundedCounterNestedMonitorBAD
extends BoundedCounterAbstract {
protected Condition notMin = new SimpleConditionObject();
protected Condition notMax = new SimpleConditionObject();
public synchronized long value() { return count; }
...
Counter
© Oscar Nierstrasz
9
Condition Objects
public synchronized void dec() {
while (count == MIN)
notMin.await();
// wait till count not MIN
if (count-- == MAX)
notMax.signal();
}
public synchronized void inc() { // can’t get in!
while (count == MAX)
notMax.await();
if (count++ == MIN)
notMin.signal();
// we never get here!
}
}
© Oscar Nierstrasz
10
Condition Objects
The Nested Monitor problem ...
Nested monitor lockouts occur whenever a blocked thread
holds the lock for an object containing the method that would
otherwise provide a notification to unblock the wait.
© Oscar Nierstrasz
11
Condition Objects
Nested Monitors in FSP
Nested Monitors typically arise when one synchronized object is
implemented using another.
Recall our one Slot buffer in FSP:
const N = 2
Slot = (put[v:0..N] -> get[v] -> Slot).
Suppose we try to implement a call/reply protocol using a private
instance of Slot:
ReplySlot
= ( put[v:0..N] -> my.put[v] -> ack -> ReplySlot
| get -> my.get[v:0..N] -> ret[v] -> ReplySlot ).
0
© Oscar Nierstrasz
1
12
Condition Objects
Nested Monitors in FSP ...
Our producer/consumer chain obeys the new protocol:
Producer = ( put[0] -> ack
-> put[1] -> ack
-> put[2] -> ack -> Producer ).
Consumer = ( get-> ret[x:0..N]->Consumer ).
||Chain = (Producer||ReplySlot||my:Slot||Consumer).
0
© Oscar Nierstrasz
1
13
Condition Objects
Nested Monitors in FSP ...
But now the chain may deadlock:
Progress violation for actions:
{{ack, get}, my.{get, put}[0..2], {put, ret}[0..2]}
Trace to terminal set of states:
get
Actions in terminal set:
{}
0
© Oscar Nierstrasz
1
14
Condition Objects
Solving the Nested Monitors problem
You must ensure that:
>
Waits do not occur while synchronization is held on the host
object.
— Leads to a guard loop that reverses the faulty synchronization
> Notifications are never missed.
— The entire guard wait loop should be enclosed within synchronized
blocks on the condition object.
>
Notifications do not deadlock.
— All notifications should be performed only upon release of all
synchronization (except for the notified condition object).
>
Helper and host state must be consistent.
— If the helper object maintains any state, it must always be consistent
with that of the host
— If it shares any state with the host, access must be synchronized.
© Oscar Nierstrasz
15
Condition Objects
Example solution
public class BoundedCounterCondition extends BoundedCounterAbstract {
boolean wasMax = false;
// record notification condition
synchronized(notMin) {
// synch on condition object
while (true) {
// new guard loop
synchronized(this) {
if (count > MIN) { // check and act
wasMax = (count == MAX);
count--; break;
}
}
notMin.await();
// release host synch before wait
}
}
if (wasMax) notMax.signal(); // release all syncs!
} ...
}
© Oscar Nierstrasz
16
p
Condition Objects
Roadmap
>
Condition Objects
— Simple Condition Objects
— The “Nested Monitor Problem”
— Permits and Semaphores
>
JUC (java.util.concurrent)
© Oscar Nierstrasz
17
Condition Objects
Pattern: Permits and Semaphores
Intent: Bundle synchronization in a condition object when
synchronization depends on the value of a counter.
Applicability
> When any given await may proceed only if there have been more
signals than awaits.
— I.e., when await decrements and signal increments the number of
available “permits”.
>
You need to guarantee the absence of missed signals.
— Unlike simple condition objects, semaphores work even if one thread
enters its await after another thread has signalled that it may proceed (!)
>
The host classes can arrange to invoke Condition methods
outside of synchronized code.
© Oscar Nierstrasz
18
Condition Objects
Permits and Semaphores — design steps
>
Define a class implementing Condition that maintains
a permit count, and immediately releases await if there
are already enough permits.
— e.g., BoundedCounter
© Oscar Nierstrasz
19
Condition Objects
Example
public class Permit implements Condition {
private int count;
Permit(int init) { count = init; }
public synchronized void await() {
while (count == 0) {
try { wait(); }
catch(InterruptedException ex) { };
}
count --;
}
public synchronized void signal() {
count ++;
notifyAll();
}
}
Counter
© Oscar Nierstrasz
20
Condition Objects
Design steps ...
> As with all kinds of condition objects, their clients must
avoid invoking await inside of synchronized code.
— You can use a before/after design of the form:
class Host {
Condition aCondition; ...
public method m1() {
aCondition.await();
// not synced
doM1();
// synced
for each Condition c enabled by m1()
c.signal();
// not synced
}
protected synchronized doM1() { ... }
}
© Oscar Nierstrasz
21
Condition Objects
Using permits
public class Building{
Permit permit;
Building(int n) {
permit = new Permit(n);
}
void enter(String person) { // NB: unsynchronized
permit.await();
System.out.println(person + " has entered the building");
}
void leave(String person) {
System.out.println(person + " has left the building");
permit.signal();
}
}
Counter
© Oscar Nierstrasz
22
Condition Objects
Using permits
public static void main(String[] args) {
Building building = new Building(3);
enterAndLeave(building, "bob");
enterAndLeave(building, "carol");
...
}
private static void enterAndLeave(final Building building,
final String person) {
new Thread() {
bob has entered the building
carol has entered the building
public void run() {
ted has entered the building
building.enter(person);
bob has left the building
alice has entered the building
pause();
ted has left the building
building.leave(person);
carol has left the building
elvis has entered the building
}
alice has left the building
}.start();
elvis has left the building
}
© Oscar Nierstrasz
23
Condition Objects
Variants
Permit Counters: (Counting Semaphores)
> Just keep track of the number of “permits”
> Can use notify instead of notifyAll if class is final
Fair Semaphores:
> Maintain FIFO queue of threads waiting on a SimpleCondition
Locks and Latches:
> Locks can be acquired and released in separate methods
> Keep track of thread holding the lock so locks can be reentrant!
> A latch is set to true by signal, and always stays true
© Oscar Nierstrasz
24
Condition Objects
Semaphores in Java
public class Semaphore {
// simple version
private int value;
public Semaphore (int initial) { value = initial; }
synchronized public void up() {
// AKA V
++value;
notify();
// wake up just one thread!
}
synchronized public void down() {
// AKA P
while (value== 0) {
try { wait(); }
catch(InterruptedException ex) { };
}
--value;
}
Cf. java.util.concurrent.Semaphore
}
Counter
© Oscar Nierstrasz
25
Condition Objects
Using Semaphores
public class BoundedCounterSem extends BoundedCounterAbstract { …
protected Semaphore mutex, full, empty;
BoundedCounterVSem() {
mutex = new Semaphore(1);
full = new Semaphore(0);
// number of items
empty = new Semaphore(MAX-MIN);
// number of slots
}
public long value() {
mutex.down();
// grab the resource
long val = count;
mutex.up();
// release it
return val;
}
public void inc() {
empty.down();
// grab a slot
mutex.down();
count ++;
mutex.up();
full.up();
// release an item
}
…
Counter
© Oscar Nierstrasz
26
Condition Objects
Using Semaphores ...
These would cause a nested monitor problem!
...
public void BADinc() {
mutex.down(); empty.down();
count ++;
full.up(); mutex.up();
}
public void BADdec() {
mutex.down(); full.down();
count --;
empty.up(); mutex.up();
}
// locks out BADdec!
// locks out BADinc!
}
© Oscar Nierstrasz
27
Condition Objects
Roadmap
>
Condition Objects
—
—
—
—
>
Simple Condition Objects
The “Nested Monitor Problem”
Permits and Semaphores
Using Semaphores
JUC (java.util.concurrent)
© Oscar Nierstrasz
28
Condition Objects
java.util.concurrent
Executors
—Executor
—ExecutorService
—ScheduledExecutorService
—Callable
—Future
—ScheduledFuture
—Delayed
—CompletionService
—ThreadPoolExecutor
—ScheduledThreadPoolExecutor
—AbstractExecutorService
—Executors
—FutureTask
—ExecutorCompletionService
Queues
—BlockingQueue
—ConcurrentLinkedQueue
—LinkedBlockingQueue
—ArrayBlockingQueue
—SynchronousQueue
—PriorityBlockingQueue
—DelayQueue
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
Concurrent Collections
—ConcurrentMap
—ConcurrentHashMap
—CopyOnWriteArray{List,Set}
Synchronizers
—CountDownLatch
—Semaphore
—Exchanger
—CyclicBarrier
Locks: java.util.concurrent.locks
—Lock
—Condition
—ReadWriteLock
—AbstractQueuedSynchronizer
—LockSupport
—ReentrantLock
—ReentrantReadWriteLock
Atomics: java.util.concurrent.atomic
—Atomic[Type]
—Atomic[Type]Array
—Atomic[Type]FieldUpdater
—Atomic{Markable,Stampable}Reference
29
Condition Objects
Key Functional Groups
>
Executors, Thread pools and Futures
— Execution frameworks for asynchronous tasking
>
Concurrent Collections:
— Queues, blocking queues, concurrent hash map, …
— Data structures designed for concurrent environments
>
Locks and Conditions
— More flexible synchronization control
— Read/write locks
>
Synchronizers: Semaphore, Latch, Barrier
— Ready made tools for thread coordination
>
Atomic variables
— The key to writing lock-free algorithms
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
30
Condition Objects
The Executor Framework
>
>
Framework for asynchronous task execution
Standardize asynchronous invocation
— Framework to execute Runnable and Callable tasks
–
–
>
Runnable: void run()
Callable<V>: V call() throws Exception
Separate submission from execution policy
— Use anExecutor.execute(aRunnable)
— Not new Thread(aRunnable).start()
>
>
Cancellation and shutdown support
Usually created via Executors factory class
— Configures flexible ThreadPoolExecutor
— Customize shutdown methods, before/after hooks, saturation policies,
queuing
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
31
Condition Objects
Executor
>
Decouple submission policy from task execution
public interface Executor {
void execute(Runnable command);
}
>
Code which submits a task doesn't have to know in what
thread the task will run
— Could run in the calling thread, in a thread pool, in a single
background thread (or even in another JVM!)
— Executor implementation determines execution policy
–
–
Execution policy controls resource utilization, overload
behavior, thread usage, logging, security, etc
Calling code need not know the execution policy
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
32
Condition Objects
ExecutorService
>
>
Adds lifecycle management
ExecutorService supports both graceful and immediate shutdown
public interface ExecutorService extends Executor {
void shutdown();
List<Runnable> shutdownNow();
boolean isShutdown();
boolean isTerminated();
boolean awaitTermination(long timeout, TimeUnit unit);
// ...
}
>Useful utility methods too
—<T> T invokeAny(Collection<Callable<T>> tasks)
–Executes the given tasks returning the result of one that completed
successfully (if any)
—Others involving Future objects
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
CP 9.33
Liveness and Asynchrony
FutureTask
public FutureTask<Integer> service (final int n) {
FutureTask<Integer> future =
new FutureTask<Integer> (
new Callable<Integer>() {
public Integer call() {
return new Integer(fibonacci(n));
}
});
new Thread(future).start(); // or use an Executor
return future;
}
Asynchrony
JUC provides a generic implementation
of Futures, parameterized by Callable
or Runnable services.
© Oscar Nierstrasz
34
Condition Objects
Creating Executors
Sample Executor implementations from Executors
> newSingleThreadExecutor
>
— A pool of one, working from an unbounded queue
>
newFixedThreadPool(int N)
— A fixed pool of N, working from an unbounded queue
>
newCachedThreadPool
— A variable size pool that grows as needed and shrinks when idle
>
newScheduledThreadPool
— Pool for executing tasks after a given delay, or periodically
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
CP 9.35
Condition Objects
Locks and Synchronizers
>
java.util.concurrent provides generally useful
implementations
— ReentrantLock, ReentrantReadWriteLock
— Semaphore, CountDownLatch, Barrier, Exchanger
— Should meet the needs of most users in most situations
–
>
Some customization possible in some cases by subclassing
Otherwise AbstractQueuedSynchronizer can be
used to build custom locks and synchronizers
— Within limitations: int state and FIFO queuing
>
Otherwise build from scratch
— Atomics
— Queues
— LockSupport for thread parking/unparking
© Oscar
NierstraszGoetz, Holmes, Lea and Peierls
2005 Bowbeer,
CP 9.36
Condition Objects
What you should know!
>
>
>
>
>
>
What are “condition objects”? How can they make your
life easier? Harder?
What is the “nested monitor problem”?
How can you avoid nested monitor problems?
What are “permits” and “latches”? When is it natural to
use them?
How does a semaphore differ from a simple condition
object?
Why (when) can semaphores use notify() instead of
notifyAll()?
© Oscar Nierstrasz
CP 9.37
Condition Objects
Can you answer these questions?
>
>
>
>
>
Why doesn’t SimpleConditionObject need any instance
variables?
What is the easiest way to avoid the nested monitor
problem?
What assumptions do nested monitors violate?
How can the obvious implementation of semaphores (in
Java) violate fairness?
How would you implement fair semaphores?
© Oscar Nierstrasz
CP 9.38
Condition Objects
License
http://creativecommons.org/licenses/by-sa/2.5/
Attribution-ShareAlike 2.5
You are free:
• to copy, distribute, display, and perform the work
• to make derivative works
• to make commercial use of the work
Under the following conditions:
Attribution. You must attribute the work in the manner specified by the author or licensor.
Share Alike. If you alter, transform, or build upon this work, you may distribute the resulting
work only under a license identical to this one.
• For any reuse or distribution, you must make clear to others the license terms of this work.
• Any of these conditions can be waived if you get permission from the copyright holder.
Your fair use and other rights are in no way affected by the above.
© Oscar Nierstrasz
39