CO2017 — Week3L3 — Monitors
CO2017 — Week3L3 — Monitors
Dr Gilbert Laycock (gtl1)
2017–02–05
gtl1–R914 W3L3 — Monitors 2017–02–05 1 / 23
Recap and overview
Recap and Lecture Overview
Recap
Simple techniques: disable interrupts; Peterson’s algorithm, etc.
Hard to reason about; need to be re-implemented in each case.
Semaphore is simpler and more robust.
Overview of this lecture:
More detailed critique of semaphores.
Introduce monitor as improved concurrency primitive.
Apply monitor to the Producer and Consumer problem.
gtl1–R914 W3L3 — Monitors 2017–02–05 2 / 23
Semaphores
Recap: Semaphores
A Semaphore has a non-negative integer value and supports the
following two operations:
a wait operation Wait(): an atomic operation that waits for
semaphore to become positive, then decrements it.
a signal operation Signal(): an atomic operation that
increments the semaphore, waking up a waiting process, if any.
gtl1–R914 W3L3 — Monitors 2017–02–05 3 / 23
Semaphores Mutex and resource constraints
Using Semaphores
Mutual Exclusion
Binary semaphore, we set initial value to 1.
mutex.Wait(); critical-section; mutex.Signal();
Scheduling (resource) constraint
Use one semaphore for each constraint.
Recall Producer and Consumer problem: one semaphore to test if
buffer is empty, another to test if buffer is full.
gtl1–R914 W3L3 — Monitors 2017–02–05 4 / 23
Semaphores Bounded buffer recap
Recap: Semaphore solution to Bounded Buffer
Semaphore mx = 0;
Semaphore ready = 0; Semaphore spaces = 5;
Consumer:
ready.Wait(); mx.Wait();
value = b.take();
mx.Signal(); spaces.Signal();
Producer:
spaces.Wait(); mx.Wait();
b.place(i);
mx.Signal(); ready.Signal();
gtl1–R914 W3L3 — Monitors 2017–02–05 5 / 23
Semaphores Positive features of semaphores
Positive aspects of Semaphores
Powerful enough to program all kinds of synchronisation and
resource management requirements
Relatively easy to be implement efficiently
A general semaphore can be simulated by binary ones
gtl1–R914 W3L3 — Monitors 2017–02–05 6 / 23
Semaphores Negative features of semaphores
Negative aspects of Semaphores
It is a low level facility and still error-prone, especially when more
than one semaphore is in use at a time
Missing a Signal() may lead to deadlock
Missing a Wait() may lead to a violation of safety requirement,
such as mutual exclusion
Putting them in wrong order may be dangerous: just swapping
Wait()s can lead to deadlock
The use of monitors will overcome these problems
gtl1–R914 W3L3 — Monitors 2017–02–05 7 / 23
Monitors
Concepts Behind Monitor
Introduced by Hoare and Hansen (1972).
Shown by Hoare to be equivalent to Dijkstra’s semaphores.
Two parts to a monitor:
lock for enforcing mutual exclusion
condition variable(s) for controlling access to resources; AKA
guards
gtl1–R914 W3L3 — Monitors 2017–02–05 8 / 23
Monitors
Concept of Monitor
In Object-oriented terms, a monitor is a class with
Some attributes (data) (to be shared by processes)
Some synchronised methods used to access the data
Some variables for condition control (guards)
Monitor data can only be accessed via its methods
Entry to a monitor by one process excludes entry by any other
processes.
gtl1–R914 W3L3 — Monitors 2017–02–05 9 / 23
Monitors Mutual exclusion by Synchronisation
Synchronization
Java has a fundamental mechanism (based on monitors): make
methods synchronized
A class providing a shared resource can have one or more
methods accessing the data declared as synchronized
This ensures that at a given moment of time only one thread can
be executing a synchronized method
All the other mechanisms of controlled access to a shared
resources discussed so far can be simulated in Java using
synchronisation
gtl1–R914 W3L3 — Monitors 2017–02–05 10 / 23
Monitors Mutual exclusion by Synchronisation
Execution of a Synchronised Method
Java associates a lock with every object which
transparently inserts code to acquire the lock before executing a
synchronised method;
and code to release the lock when the method returns.
Concurrent threads are blocked until the lock is released
Only one thread at a time may hold the lock and thus may be executing
the synchronised method
Executing synchronised methods of different objects can be
concurrent
gtl1–R914 W3L3 — Monitors 2017–02–05 11 / 23
Monitors Mutual exclusion by Synchronisation
Example of simple mutual exclusion
public class MonitorBuffer {
public static final int BUFFSIZE = 5;
private int[] _b = new int[BUFFSIZE];
private int _count = 0;
private int _nextIn, _nextOut;
public MonitorBuffer() { _nextIn=0; _nextOut=0; }
public synchronized void place(int item)
throws InterruptedException {
_b[_nextIn] = item;
_nextIn = (_nextIn +1)%BUFFSIZE;
}
public synchronized int take()
throws InterruptedException {
int val = _b[_nextOut];
_nextOut = (_nextOut +1)%BUFFSIZE;
return val;
}
gtl1–R914 W3L3 — Monitors 2017–02–05 12 / 23
Monitors Condition variables
Condition Synchronisation
Sometimes we need further control to synchronise the order of threads
entering the critical section
Condition synchronisation is the property that one process wishing to
access shared data must be delayed until some condition holds
E.g. in the Producer-Consumer problem
Producer can place an item into the buffer only when it is not full
Consumer can take an item from the buffer only when it is not empty
regardless of whether any other thread is trying to use the buffer.
gtl1–R914 W3L3 — Monitors 2017–02–05 13 / 23
Monitors Condition Synchronisation in Java
Condition Synchronisation in Java
Java provides a thread wait queue for each monitor (actually per
object).
Objects in the class Object have methods
public final void notify(): wakes up a single thread that is
waiting on this object’s wait set.
public final void notifyAll(): wakes up all threads that are
waiting on this object’s wait set.
public final void wait()
throws InterruptedException: waits to be notified by
another thread. Implicitly releases lock.
gtl1–R914 W3L3 — Monitors 2017–02–05 14 / 23
Monitors Condition Synchronisation in Java
Basic pattern of Condition Synchronisation
The basic format for condition synchronisation is
when (safety condition) do critical action
or
while (not safety condition) block
do critical action
In Java, the format is
public synchronized void act()
throws InterruptedException {
while (!cond) wait();
…… // modify monitor data
notifyAll();
}
gtl1–R914 W3L3 — Monitors 2017–02–05 15 / 23
Producer/Consumer example revisited Bounded buffer as a monitor
Bounded Buffer as a Monitor
public class MonitorBuffer {
public static final int BUFFSIZE = 5;
private int[] _b = new int[BUFFSIZE];
private int _count = 0;
private int _nextIn, _nextOut;
public MonitorBuffer() { _nextIn=0; _nextOut=0; }
public synchronized void place(int item)
throws InterruptedException {
while (_count >= BUFFSIZE) wait();
_b[_nextIn] = item;
++_count;
_nextIn = (_nextIn +1)%BUFFSIZE;
notifyAll();
}
gtl1–R914 W3L3 — Monitors 2017–02–05 16 / 23
Producer/Consumer example revisited Bounded buffer as a monitor
Bounded Buffer as a Monitor (Cont’d)
public synchronized int take()
throws InterruptedException {
int value;
while (_count == 0) wait();
value = _b[_nextOut];
_nextOut = (_nextOut + 1)%BUFFSIZE;
-_count;
notifyAll();
return value;
}
public static void main(String[] args) {
MonitorBuffer buff=new MonitorBuffer();
Producer p = new Producer(buff);
Consumer c = new Consumer(buff);
p.start(); c.start();
}
}
gtl1–R914 W3L3 — Monitors 2017–02–05 17 / 23
Producer/Consumer example revisited Producer
The Producer Class
class Producer extends Thread {
MonitorBuffer _b;
public Producer(MonitorBuffer mb) { _b = mb; }
public void run() {
for (int i=1; i<=100; i++) {
try {
_b.place(i);
Thread.sleep(500);
} catch(InterruptedException e) { }
System.out.println("Producer puts "
+ i +" in the buffer.");
}
}
}
gtl1–R914 W3L3 — Monitors 2017–02–05 18 / 23
Producer/Consumer example revisited Consumer
The Consumer Class
class Consumer extends Thread {
MonitorBuffer _b;
public Consumer(MonitorBuffer mb) { _b = mb; }
public void run() {
int value;
for (int i=1; i<=100; i++) {
try {
value = _b.take();
Thread.sleep(1000);
} catch(InterruptedException e) { }
System.out.println("Consumer takes "
+ value + " out of the buffer.");
}
}
}
gtl1–R914 W3L3 — Monitors 2017–02–05 19 / 23
Producer/Consumer example revisited Analysis
Features of this Program
Encapsulates the critical code into the monitor
Releases the user’s responsibility for coding/ordering Wait() and
Signal() operations in the thread class
The responsibility for ensuring mutual exclusion is moved to the
language compiler
Is more efficient and robust than Semaphore
gtl1–R914 W3L3 — Monitors 2017–02–05 20 / 23
Implement semaphores using synchronized methods
Recall definition of Semaphore
A semaphore is an integer val that takes only non-negative values
(representing the quantity of a resource available)
Only two operations are permitted on a semaphore s:
Wait
If val > 0 then decrement val
else block the calling process
Signal
If there are processes blocked on s then unblock one
else increment val
gtl1–R914 W3L3 — Monitors 2017–02–05 21 / 23
Implement semaphores using synchronized methods
Java Code for the Semaphore Class
class Semaphore {
private int value;
public Semaphore (int init) { value = init; }
synchronized public void Wait()
throws InterruptedException {
while (value == 0) this.wait();
–value; }
synchronized public void Signal() {
if (value == 0) this.notifyAll();
++value; }
}
gtl1–R914 W3L3 — Monitors 2017–02–05 22 / 23
Summary
Summary
Semaphore concept has some limitations
Monitor is a better choice for condition synchronisation
A monitor has a set of data to be shared among threads and
synchronised methods to be used by threads
Illustrated the application of monitor for the Producer and Consumer
problem
gtl1–R914 W3L3 — Monitors 2017–02–05 23 / 23
Semaphores
Mutex and resource constraints
Bounded buffer recap
Positive features of semaphores
Negative features of semaphores
Monitors
Mutual exclusion by Synchronisation
Condition variables
Condition Synchronisation in Java
Producer/Consumer example revisited
Bounded buffer as a monitor
Producer
Consumer
Analysis
Implement semaphores using synchronized methods