Monitors
CS511
1/47
Review
We’ve seen that semaphores are an efficient tool to solve synchronization problems
However, they have some drawbacks 1. They are low-level constructs
It is easy to forget an acquire or release 2. They are not related to the data
They can appear in any part of the code
2/47
Monitors
Combines ADTs and mutual exclusion Proposed by Tony Hoare:
Monitors: An Operating System Structuring Concept (Commu- nications of the ACM, 17(10), 549-557, 1974).
Adopted in many modern PLs Java
C#
Python Ruby
3/47
Main Ingredients
A set of operations encapsulated in modules
A unique lock that ensures mutual exclusion to all operations
in the monitor
Special variables called condition variables, that are used to program conditional synchronization
4/47
Counter Example
Construct a counter with two operations: inc()
dec()
No two threads should be able to simultaneously modify the value of the counter
Think of a solution using semaphores A solution using monitors
5/47
Counter using Semaphores
class Counter {
private int c = 0;
private Semaphore mutex = new
public void inc() { mutex.acquire(); c++; mutex.release();
1
2
3
4
5
6
7
8 9}
Semaphore (1);
10 11 12 13 14 15
public void dec() { mutex.acquire(); c–; mutex.release();
} }
6/47
Counter using Monitors
monitor Counter {
private int counter = 0;
public void inc() { counter ++;
1
2
3
4
5 6} 7
8
9 10 11 12
public void dec() { counter –;
} }
The monitor comes equipped with a lock or mutex that allows at most one thread to execute its operations
Note:
This is pseudocode (not Groovy nor Java)
7/47
Counter in Java
class Counter {
private int counter = 0;
public synchronized void inc() { counter ++;
1
2
3
4
5
6 7} 8
9 10 11 12 13
public synchronized void dec() { counter–;
} }
Each object has its own lock called intrinsic or monitor lock It also has its own wait-set (more on this later)
The class also has a lock but we don’t use it in this example
8/47
Condition Variables
Apart from the lock, there are condition variables associated to the monitor
They have
1. Three operations:
Cond.wait() Cond.signal() Cond.empty()
2. A queue of blocked processes.
9/47
Condition Variables
Cond.wait()
Always blocks the process and places it in the waiting queue of the variable Cond.
When it blocks, it releases the mutex on the monitor. Cond.signal()
Unblocks the first process in the waiting queue of the variable Cond and sets it to the READY state
If there are no processes in the waiting queue, it has no effect. Cond.empty()
Checks if waiting queue of Cond is empty or not
10/47
Example: Buffer of Size 1
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22
monitor Buffer {
private Object buffer = null; // shared buffer
private condition full; // wait until space available private condition empty; // wait until buffer available
public Object consume () { while (buffer == null)
full.wait(); Object aux = buffer; buffer = null; empty.signal(); return aux;
}
public void produce(Object o) { while (buffer != null)
empty.wait(); buffer = o; full.signal();
} }
11/47
Example: Buffer of Size 1 in Groovy
1 2 3 4 5 6 7 8 9
class Buffer {
Object buffer = null; // shared buffer
synchronized Object consume() { while (buffer == null)
wait(); // wait on object’s wait-set Object aux = buffer;
buffer = null;
signalAll(); // signal on object’s wait-set return aux;
}
synchronized void produce(Object o) {
10
11
12
13
14
15 wait(); // wait on object’s wait-set 16 buffer = o;
17 18 19
signalAll(); // signal on object’s wait-set }
}
while (buffer != null)
Every object has a wait-set on which methods wait, signal and signalAll operate
These methods must be called from synchronized methods or else an IllegalMonitorStateException is raised
12/47
Example: Buffer of Size 1 in Groovy (cont)
Buffer b =new Buffer();
20. times { // 20 producers int id=it
Thread.start {
b.produce(id);
Thread.start { // Consumer 1 println “consumer “+ b.consume();
}
Thread.start { // Consumer 2 println “consumer “+ b.consume();
}
return ;
1
2
3
4
5
6 7} 8}
9 10 11 12 13 14 15 16 17 18
13/47
Explaining Monitors Graphically
Operations
Implementation Condition Variables Monitor
c1
c2
14/47
Typical Behavior
c1
c2
15/47
Typical Behavior
c1
c2
15/47
Typical Behavior
c1
c2
15/47
Typical Behavior
c1
c2
15/47
Typical Behavior
c1
c2
15/47
Wait
Caller blocks (and moves to c1’s queue)
c1
c2
Blocks process currently executing and associates it to variable’s queue
Upon blocking frees the lock allowing the entry of other processes
16/47
Wait
c1
c2
Blocks process currently executing and associates it to variable’s queue
Upon blocking frees the lock allowing the entry of other processes
16/47
Wait
c1
c2
Blocks process currently executing and associates it to
variable’s queue
Upon blocking frees the lock allowing the entry of other processes
16/47
Signal
Executes c1.signal()
c1
c2
Signalling process continues to execute after notifying on c1? Processes waiting in c1’s queue start immediately running
inside the monitor?
What about the processes blocked on entry to the monitor?
17/47
Signal – States That a Process Can Be In
Waiting to enter the monitor
Executing within the monitor (only one)
Blocked on condition variables
Queue of processes just released from waiting on a condition variable
The Immediate Resumption Requirement
Queue of processes that have just completed a signal
operation
ff
f
condition 1
fff AA
condition 2 A ff A
HH
monitor
f
waiting
°° ff ° signaling
° f
M. Ben-Ari. Principles of Concurrent and Distributed Programming, Second edition ≠c M. Ben-Ari 2006 Slide 7.8 18 / 47
Notify
The Immediate Resumption Requirement
fff
condition 1
fff AA
condition 2 A ff A
HH
monitor
f
waiting
°° ff ° signaling
° f
Two strategies:
M. Ben-Ari. Principles of Concurrent and Distributed Programming, Second edition ≠c M. Ben-Ari 2006 Slide 7.8
Signal and Urgent Wait: E < S < W (classical monitors)
Signal and Continue: E = W < S (Java ⇐ We focus on this one)
where the letters denote the precedence of S: signalling processes
W : waiting processes
E: processes blocked on entry
19/47
Monitors
More Examples
Monitors in Java Visibility
Explicit Locks
20/47
Monitor that Defines a Semaphore
1 monitor Semaphore {
2 private condition nonZero;
3 private int permissions;
4
5 public Semaphore(int n) {
6 7} 8
9
this.permissions = n;
10 11 12 13 14 15 16 17 18 19 20
public void acquire () { while (permissions == 0)
nonZero.wait(); permissions --;
}
public void release () { permissions ++; nonZero.notifyAll();
} }
21/47
Notify and Continue
Must re-check the condition since may have gained entry long after it was notified
public void acquire () { while (permissions == 0)
nonZero.wait(); permissions --;
}
Another reason for re-checking the condition:
Spurious wakeups: “Implementations are permitted, although not encouraged, to perform ”spurious wake-ups”, that is, to remove threads from wait sets and thus enable resumption without explicit instructions to do so.”1
1JLS for Java 8 [1] (page 642)
22/47
Signal and Continue
1 monitor Semaphore {
2 private condition nonZero;
3 private int permissions;
4
5 public Semaphore(int n) {
6 7} 8
9
this.permissions = n;
10 11 12 13 14 15 16 17 18 19
public void acquire () { while (permissions == 0)
nonZero.wait(); permissions --;
}
public void release () { permissions ++; nonZero.signal();
} }
Is it fair?
What happens with a process that is waiting to acquire the
lock on the condition variable’s queue?
23/47
Buffer of Size n
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
monitor Buffer {
private private private
Object[] data = new Object[N]; intbegin=0,end=0; condition notFull , notEmpty;
public void put(Object o) { while (isFull())
notFull.wait(); data[begin] = o;
begin = (begin+1) % N;
notEmpty.notify() }
public Object take() { while (isEmpty())
notEmpty.wait();
Object result = data[end]; end = (end+1) % N notFull.notify();
return result;
}
private boolean isEmpty() { return begin == end; }
private boolean isFull() { return next(begin) == end; } }
24/47
Readers/Writers
8
9 10 11 12
public void
... }
}
monitor RW { ...
1
2
3
4
5 6} 7
public void
...
read ()
write ()
{
{
What is the problem with this setting?
25/47
Readers/Writers
10 11 12 13 14 15 16 17 18 19
OKtoRead.wait(); readers = readers
+ 1;
monitor RW {
int readers = 0;
int writers = 0;
condition OKtoRead , OKtoWrite;
public void StartRead () {
while (writers != 0 or not OKtoWrite.empty()) {
1
2
3
4
5
6
7
8 9}
}
public void EndRead {
readers = readers if (readers==0) {
- 1;
OKtoWrite.notify(); }
}
// continues
26/47
Readers/Writers
1 public void StartWrite () 2 while (writers != 0 or 3 OKtoWrite.wait(); 4}
{
readers != 0) {
5 writers = writers + 1; 6}
7
8
9 10 11 12 13
public void EndWrite () { writers = writers - 1; OKtoWrite.signal(); OKtoRead.signalAll();
} }
27/47
Assessment
Upholds the readers-writers invariant.
However, it gives priority to readers over writers:
new readers can enter the monitor without waiting as long as a
reader is active
waiting writers have to wait until the last reader calls endRead
and signals OKtoWrite
as long as readers keep arriving and queuing for entering the
monitor, the waiting writers will never execute
28/47
Dining Philosophers
monitor ForkMonitor {
int[] fork = {2,2,2,2,2}; condition[] OKtoEat; // 0-4
public void takeForks(integer i) { while (fork[i] != 2) {
OKtoEat[i].wait();
fork[i+1] = fork[i+1] -1;
fork[i-1] = fork[i-1] -1; }
public void releaseForks(integer i) { fork[i+1] = fork[i+1] +1; fork[i-1] = fork[i-1] +1;
if (fork[i+1] == 2) {
OKtoEat[i+1].signal(); }
if (fork[i-1] == 2) { OKtoEat[i-1].signal();
} }
}
forks[i] is number of forks available to philosopher i
1
2
3
4
5
6
7 8}
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
29/47
Monitors
More Examples
Monitors in Java Visibility
Explicit Locks
30/47
Visibility
Whether a thread can see the modifications of other threads
Visibility is subtle because the compiler may Reorder operations
Cache values in registers
synchronization, used for atomicity, helps with visibility too: All changes made in one synchronized method or block are
visible with respect to other synchronized methods and blocks employing the same lock.
31/47
Volatile Variables
1 int n=0;
2 Thread.start { // P 2
Thread.start { // Q int local;
local = n+6;
3
4
5
6
7
8 9}
int local1 , local2; 3 n = some expression; 4 computation not using n; 5 local1 = (n+5)*7; 6 local2 = n+5; 7 n = local1 * local2; 8
9}
The instruction in Q may be interleaved at any place during the execution of the instructions in P
32/47
Volatile Variables
An optimizing compiler could translate statements in thread P as:
1 tempReg1 = some expression 2 computation not using n
3 tempReg2 = tempReg1 + 5
4 local2 = tempReg2
5 local1 = tempReg2 * 7 6 n = local1 * local2
1 n = some expression;
2 computation not using n; 3 local1 = (n+5)*7;
4 local2 = n+5;
5 n = local1 * local2;
6 .
No assignment to n in the first statement. Original statements p3 and p4 are executed out of order
Without concurrency, the translated code would be correct
With concurrency and interleaving, the translated code may
no longer be correct
Specifying a variable as volatile instructs the compiler to load and store the value of the variable at each use, rather than to optimize away these loads and stores.
33/47
Example 12
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22
public class SharedVariable {
private static int sharedVariable = 0;
public static void main(String[] args) throws InterruptedExcept
new Thread(new Runnable() { @Override
public void run() {
try { Thread.sleep(100); }
catch (InterruptedException e) {
e.printStackTrace();
}
sharedVariable = 1; }}). start ();
for(int i=0;i<1000;i++) { for (;;) {
if(sharedVariable == 1) { break; } }
}
System.out.println("SharedVariable : " + sharedVariable); }
}
Try this code as is (loops due to compiler optimization), then add the qualified volatile to the declaration of sharedVariable and run
34/47
again
Example 2
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
public class NoVisibility { private static boolean ready; private static int number;
private static class ReaderThread extends Thread { public void run() {
while (!ready) Thread.yield();
System.out.println(number); }
}
public static void main(String[] args) { new ReaderThread (). start ();
number = 42;
ready = true;
} }
java.lang.Thread.yield() causes the currently executing thread object to temporarily pause and allow other threads to execute
What is the output?
35/47
Example 2
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
public class NoVisibility { private static boolean ready; private static int number;
private static class ReaderThread extends Thread { public void run() {
while (!ready) Thread.yield();
System.out.println(number); }
}
public static void main(String[] args) { new ReaderThread (). start ();
number = 42;
ready = true;
} }
java.lang.Thread.yield() causes the currently executing thread object to temporarily pause and allow other threads to execute
What is the output? Could loop forever or print 0!
35/47
Monitors
More Examples
Monitors in Java
Visibility
Explicit Locks
36/47
Explicit Locks
Apart from the intrinsic lock of an object, one can use explicit locks
This is convenient for modeling condition variables
We next present the Lock interface and the class ReentrantLock that implements it
37/47
Explicit Locks – An Example
We take a look at the producers/consumers example
We present two implementations: Using intrinsic locks
Using explicit locks
Source: Goetz’s Java Concurrency in Practice, Addison-Wesley, 2006
38/47
Bounded Buffers Revisited
1 public abstract class BaseBoundedBuffer
2 private final V[] buf;
3 private int tail;
4 private int head;
5 private int count;
6
7 protected BaseBoundedBuffer(int capacity) {
8
9} 10
this.buf = (V[]) new Object[capacity];
11 12 13 14 15 16 17 18
protected synchronized final void doPut(V v) { buf[tail] = v;
if (++tail == buf.length) tail = 0;
++count; }
// continued
39/47
Bounded Buffers Revisited
1
2
3
4
5
6
7
8 9}
10 11 12 13 14 15 16 17 18
public synchronized final boolean isFull() { return count == buf.length;
}
public synchronized final boolean isEmpty() { return count == 0;
} }
protected synchronized final V doTake() { V v = buf[head];
buf[head] = null;
if (++head == buf.length)
head = 0; –count;
return v;
40/47
Crude Blocking
1 public class BoundedBuffer
2 // CONDITION PREDICATE: not-full (!isFull())
3 // CONDITION PREDICATE: not-empty (!isEmpty())
4 public BoundedBuffer() {
5 6} 7
8
9
this (100);
10 11 12 13 14 15 16 17 18 19
}
// BLOCKS-UNTIL: not-full
public synchronized void put(V v) throws InterruptedException while (isFull())
wait(); doPut(v);
notifyAll (); }
// continues
public BoundedBuffer(int size) { super(size);
41/47
Crude Blocking
1
2
3
4
5
6
7 8} 9
10 11 12 13 14 15 16 17 18 19 20
// BLOCKS-UNTIL: not-full
// Alternate form of put() using conditional notification public synchronized void alternatePut(V v) throws InterruptedE
} }
// BLOCKS-UNTIL: not-empty
public synchronized V take() throws InterruptedException { while (isEmpty())
wait ();
V v = doTake ();
notifyAll (); return v;
while (isFull()) wait();
boolean wasEmpty = isEmpty (); doPut(v);
if (wasEmpty)
notifyAll ();
42/47
Lock Interface
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15
public interface Lock {
void lock(); // Acquires the lock.
void lockInterruptibly() throws InterruptedException;
}
boolean tryLock();
// Acquires the lock unless
// the current thread is interrupted. // Acquires the lock only if it is
// free at the time of invocation.
boolean tryLock(long time, TimeUnit unit)
throws InterruptedException; // Acquires the lock if it
// is free within the given waiting time
// and the current thread has not been interrupted. void unlock(); // Releases the lock.
Condition newCondition(); // Returns a new Condition instance
// that is bound to this Lock instance.
43/47
Using Locks
1
2
3
4
5
6 7}
Lock l = new ReentrantLock (); l.lock();
try {
// access the resource protected by this lock
} finally { l.unlock();
44/47
Using Condition Interface
1 public interface Condition {
2 void await(); // Causes the current thread to wait until
3 // it is signalled or interrupted.
4 boolean await(long time, TimeUnit unit);
5 long awaitNanos(long nanosTimeout);
6 void awaitUninterruptibly ();
7 boolean awaitUntil(Date deadline);
8
9 void signal(); // Wakes up one waiting thread.
10 void signalAll(); // Wakes up all waiting threads.
11 }
In condition objects we replace wait, notify and notifyAll by await, signal and signalAll
45/47
Using Condition Interface
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
public class ConditionBoundedBuffer
protected final Lock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition(); private final Condition notEmpty = lock.newCondition(); private static final int BUFFER_SIZE = 100;
private final T[] items = (T[]) new Object[BUFFER_SIZE]; private int tail, head, count;
// BLOCKS -UNTIL: notFull
public void put(T x) throws InterruptedException { lock.lock();
try
{
while (count == items.length)
notFull.await(); items[tail] = x;
if (++tail == items.length) tail = 0;
++count;
notEmpty.signal(); } finally {
lock.unlock(); }
}
// continues
46/47
Using Condition Interface
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
// BLOCKS -UNTIL: notEmpty
public T take() throws InterruptedException { lock.lock();
} }
try {
while (count == 0)
notEmpty.await();
T x = items[head]; items[head] = null;
if (++head == items.length)
head = 0; –count;
notFull.signal();
return x; } finally {
lock.unlock(); }
47/47