Transcript Monitors

Monitors and Higher Level Concurrency

Introduction to Monitors
Monitors are another mechanism for handling critical code sections.

Semaphore Disadvantages

Shared variable are global to all processes, easily accessed accidentally
without protection.

Concurrency code is scattered throughout the program
Mutual exclusion must always be coded.


Advantages of the Monitor Construct




Permanent, shared variables are hidden from processes (program writers).
Access to the monitor is via monitor procedures.
Only one process at a time can execute in the monitor, so mutual exclusion
is automatic. (Though several processes may be waiting in the monitor.)
Condition variables provide synchronisation.
1
Monitors

Real-World Analogy
Monitor is like a vending machine. A set of operations is listed on the
outside of the vending machine. A process can enter the vending machine
by pressing the button for an operation. Once inside the vending machine
the process executes the code for the procedure, stopping to wait on
condition variables when it encounters them. A running process can wake
up stopped processes by signalling on their condition variables. A process
leaves the vending machine when it reaches the end of the procedure. The
procedure can return results.
Process(P1)
MONITOR
Process(P2) (executing in the monitor)
Process(P3)
2
Monitors

Condition Variables


A condition variable, c, is an object which is defined inside a monitor. At
any one time during execution the condition variable has its own queue of
delayed (blocked) processes.
 wait(c)
 When a process executes wait(c) it is added to c's queue of
blocked processes
 signal(c)
 When a processes executes signal(c) this causes the front process
to be removed from c's queue of blocked processes and to be
added to a list of ready processes. The signaller continues
execution.
(Note: if c has an empty queue then signal(c) has no effect!)
P8 currently executing in the monitor
issues wait(C2). Then it will be placed to
wait on the associated C2 condition
queue. Another process will now get
access to the monitor
C1
P1
P8
(Executing)
C2
P3
P7
P9
3
Monitors

Condition Variables Versus Semaphores
Monitor
Semaphore
1. signal(c)
V(s)
< s = s + 1>
signal has no effect if
queue is empty
Signaller retains control.
(Can't be timed out
while in monitor.)
s is incremented by 1
2. wait(c)
P(s)
Always delays
If s > 0 then calling
process continues.
Signaller may be
interrupted by a ready
process.
4
Monitors
Bounded Buffer Monitor
Monitor BBuffer {
Front
Datatype buf[1:n];
int front = 1, rear = 1, count = 0;
Consumer
cond not_full;
Condition Variables
cond not_empty;
Rear
Producer
procedure deposit(Datatype item) {
while (count==n) wait(not_full);  Wait until there is space in the
buffer to deposit an item
buf[rear] = item;
rear = (rear mod n) + 1;
count = count + 1;
signal(not_empty); Signal that an item is now available
}
5
Monitors
procedure fetch(Datatype out) {
while(count == 0)wait(not_empty);  Wait until there is an item available
out = buf[front];
front := (front mod n ) + 1;
count := count - 1;
signal(not_full); Signal the buffer is no longer full
}
} //
end BBuffer
Monitor (Buffer)
fetch(…)
Consumer
deposit(…)
Producer
BBuffer List;
Producer  List.deposit(item);
Consumer  List.fetch(item);
6
Monitors

General Form of Monitor
A monitor consists of declarations, initialisation code and procedures.
monitor Mname {
declaration of permanent variables and initialisation code

procedure op1 (formal s1) {
instructions in body of op1
} // end op1
....
....
procedure opN(formal sn) {
instructions in body of opn
} //end opN
} // end Mname
7
Monitors

Usage of Monitor
Process calls monitor procedure by adding the Monitor name to the
procedure name:
 Mname.opi ( arguments );
 BBuffer.deposit(1000);

Additional Operations on Condition Variables
 empty(c)
 Returns true if the delay queue on the condition variable is empty,
otherwise false.
 wait(c, rank) ( or wait(c) – just wait on a non priority queue )
 organises process waiting on c in order of rank
 minrank(c)
 minimum rank in c's delay queue
 signal_all(c) ( or signal(c) – just signals the process at head of queue )
 wake all processes waiting on c
8
Monitors

Shortest Job Next - SJN

A single resource is to be allocated to the waiting job with the shortest
execution time.
P(2) is executing inside the monitor
Monitor SJN {
boolean free = true;
cond turn;
3
P(2)
7
P(6)
11
17
P(3)
P(4)
procedure request(time_taken){ P6, P3 and P4 have called request() and are
waiting on the condition queue called turn
if (free) free=false;
else wait(turn, time_taken); Wait until signalled that resource is free
{take resource}
} // end request
procedure release() {
{release resource}
if (empty(turn)) free = true;
else signal(turn); Signal waiting process (at head of queue)
} // end release
} //end SJN
9
Monitors
 Monitor Invariant


A monitor invariant MI is a predicate which captures the essential
properties of a given monitor.
For purposes of formal reasoning about the monitor:
 MI should be true:
 Whenever a process enters the monitor, i.e. at the beginning of
each monitor procedure.
 Whenever a process leaves the monitor, i.e. at the end of a
monitor procedure.
 Whenever a process releases control of the monitor by executing
wait().
10
Monitors
 Readers and Writers




Readers may access a database concurrently or a single writer may access
it.
The monitor is used to control access to the database(DB).
Four procedures are used:
 request_read(), release_read(),
 request_write(), release_write()
MI: ( nr == 0  nw == 0 )  nw  1
 where nr = number of readers accessing the DB
 and nw = number of writers accessing the DB
11
Monitors
 RW Controller
monitor RWController {
int nr = 0, nw = 0;
cond oktoread, oktowrite;  Condition Variables
procedure request_read(){
while (nw > 0) wait(oktoread);
nr = nr + 1;
} // end request_read
procedure release_read(){
nr = nr - 1;
if (nr = 0) signal(oktowrite)
} // end release_read
Wait until a WRITER is no
longer active (if READER
is active then go ahead)
If this is the last READER
leaving then signal that it is
ok for a WRITER to
proceed
12
Monitors
procedure request_write(){
While there is a READER or
while (nr >0  nw >0)
WRITER active then wait until they
wait(oktowrite)
leave
nw = nw + 1;
} // end request_write
procedure release_write(){
nw = nw - 1;
signal(oktowrite);
signal_all(oktoread);
} // end release_write
Once a WRITER leaves then signal
that it is OK for a waiting READER or
WRITER to go ahead
} // end RWController
13
Monitors
 Synchronisation Techniques

Monitor Design
1. Define procedure names, parameters, calling order by processes.
2. Define permanent monitor variables, MI - the monitor invariant.
3. Outline procedure bodies, add initialisation code so that MI is initially
true.
4. Use await B to synchronise on a Boolean condition B.
while (not B) wait(cB);
 Define one condition variable for each different B in the system.
 5. Awaken delayed processes with signal(cB).
 Make sure that there are enough signals to waken all waiting
processes that should be woken.
14
Monitors
 The Sleeping Barber

This is a classic problem (whose strategy can also be used to solve the
problem of disk scheduling required to carry out multiple reads and writes).

The barber shop has one entrance and one exit. Customers (processes)
enter one by one.
If the barber is asleep in an empty shop:
then the customer sits in the big chair, wakes barber, and sleeps.
Otherwise (if the barber is busy)
Customer sits in a waiting chair, and sleeps.
When woken by barber the customer sits in the big chair and
sleeps again.
After the haircut the customer is woken by the barber, leaves by the exit
door, waking the barber as he leaves.

15
Monitors

Barber Shop Activity
Waiting
Customers
Sleeping
Barber
Customer
Arriving
• This Customer will now move to the
Big Chair and sit in it, awake the
Barber and go to sleep.
• When the hair cut is finished the
Barber will waken the sleeping
Customer and sit in his own chair
and sleep
• The Barber is woken by the
Customer closing the exit door.
• If there is a waiting Customer the
Barber wakens the waiting
Customer and goes back to sleep.
• The Customer sits in the Big Chair
and the cycle is repeated.
Customer
Leaving
Big Chair where
Customer sits to
get haircut
16
Monitors
 Barber


The barber sleeps in his hair until woken by a customer.
 He cuts the customer's hair. Then he opens the exit door and wakes up the
customer.
 He sleeps until the customer has left, gets woken by the customer leaving,
then looks to see if there is a waiting customer.
 If there is a waiting customer the barber wakes up the customer and sleeps
again. The customer sits in the big chair, wakes the barber and then sleeps
again as above.
Solution
 The customers and barber are processes and the barbers shop is a monitor
in which the processes interact.
 To implement the interactions we can model the barbers shop as a monitor
with three procedures: haircut, get_cust, finished_cut.
 Customers call haircut; they return from this procedure after getting a
haircut.
17
Monitors


The barber repeatedly calls get_cust to wait for a customer to sit in the big
chair, then gives the customer a haircut, and finally calls finished_cut to
allow the customer to leave the shop.
Within the sleeping barber monitor, we need to synchronize the actions of the
barber and the customers.
 First the barber and a customer need to rendezvous (i.e. the barber has to
wait for a customer to arrive, and a customer has to wait for the barber to
be available.
 Second, the customer has to wait until the barber has finished giving him a
haircut, which is indicated by the barber opening the exit door.
 Finally before closing the exit door the barber has to wait until the
customer has left the shop.
18
Monitors
monitor Barber_Shop {
int barber = 0; int chair = 0; int open = 0;
cond bfree, chocc, doorop, cleft;
procedure haircut() { // called by customers
Customer waits until the Barber
while (barber == 0)wait bfree;
signal that he is free
barber = barber - 1;
chair = chair + 1;
Customer signal that he is sitting in the
signal(chocc);
Big Chair ready for haircut
{ .. Haircut ..}
Customer waits/sleeps in the Big Chair until
while(open==0)wait(doorop);
the Barber signals that he is finished by
open = open - 1;
opening the door for the Customer to leave
signal(cleft);
Customer signals to the Barber that he
has left – this allows the barber to move to
} // end haircut
the next Customer
19
Monitors
procedure get_cust() { // called by the barber
barber = barber + 1;
Barber signal to Customer that he is ready
signal(bfree);
while (chair==0)wait(chocc);
Barber waits until the Customer sits in
the Big Chair
chair = chair - 1;
} // end get_cust
procedure finished_cut() { // called by the barber
open = open + 1;
Barber indicates to the Customer that he is finished
signal(doorop);
by opening the door for the Customer to leave
while (open > 0) wait(cleft);
Barber waits for the Customer to leave
} // end finished_cut
} Barber_Shop
20

Interaction
21
Monitors

Note the following:
 The value of the variable barber is 1 when the barber is waiting for a
customer to sit in the barbers chair.
 The variable chair is 1 when the customer has sat in the chair, but the
barber has not yet become busy.
 The variable open is 1 when the exit door has been opened but the
customer has not yet left.
 In addition we need to implement the await statements using condition
variables
 bfree (signaled when barber>0 )
 chocc (signaled when chair>0)
 doopop (signaled when open>0)
 cleft (signaled when open=0)
22
Monitors - Java


Java can use the synchronized keyword to identify regions of code that are critical sections.
Example: A shared counter (synchronized blocks in bold):
public class SharedCounter {
private Object myLock = new Object();
private int count;
•
•
public SharedCounter() {
this.count = 0;
}
public void increment() {
synchronized (myLock) {
count++; }
}
public int get() {
synchronized (myLock) {
return count; }
}
} // end SharedCounter
Synchronized
Block
Each synchronized block specifies the
monitor to be locked.
Java uses a special form of syntax for
critical sections to ensure that if the
critical section throws an exception,
the lock is guaranteed to be released.
Otherwise, a monitor could be left in a
locked state, meaning that any future
attempt to acquire the lock will result
in deadlock.
Concurrent Threads can now use this “SharedCounter” by calling
the methods “increment()” and “get()” in the knowledge that no
data will be overwritten or corrupted. E.g.
SharedCounter sCounter = new SharedCounter;
Thread 1:
sCounter.increment();
Thread2:
System.out.println(“Count Value =“+sCounter.get() );
23
Monitors - Java

Java - Wait and Notify

wait allow threads to wait until a condition involving shared data becomes true
 notifyAll and notify indicates to other threads that shared data has changed (possibly enabling a
condition that other threads are waiting for)
Example - Adding a waitThreshold method (i.e. condition) to the SharedCounter class:

public void waitThreshold(int value) throws InterruptedException {
synchronized (myLock) {
•Note that we have declared the waitThreshold
while (count < value) {
method to throw InterruptedException.
myLock.wait();
•While a thread is waiting on a monitor, it may be
}
}
"interrupted" by another thread. If a thread is interrupted
}
in this way, its call to wait does not return normally, but

We also have to change the increment method:
instead throws InterruptedException.
public void increment() {
•This mechanism can be used to "cancel" potentially longsynchronized (myLock) {
}
}
count++; // shared data has changed so
running operations involving waiting on the state of
myLock.notifyAll(): // notify all waiting thread(s)
shared data. In practical terms, it means that every time
we call the wait method we must either
handle InterruptedException using try/catch, or
declare the method as throwing InterruptedException.
24
Monitors - Java
 Java-Synchronized Methods
Java allows entire methods to be marked as synchronized and then we have an implicit lock.
For example, in our SharedCounter class, we could omit the myLock object, and instead mark
the methods accessing shared data as synchronized.


public class DangerousCounter {
private int count;
public DangerousCounter() {
this.count = 0; }
public synchronized void increment() {
count++;
this.notifyAll();
}
public synchronized int get() {
return count;
}
•You'll notice that there are no longer any explicit synchronized blocks.
Instead, each method which is marked with the synchronized keyword
implicitly treats its body as if it were contained inside a synchronized block.
•The question is then "what monitor is locked and unlocked"? The answer is
that the object on which the synchronized method is called is locked and
unlocked. We can see this because the waitThreshold method makes the
call this.wait(); to wait on its condition, implying that "this" is the lock
associated with the condition.
•This is why synchronized methods are not such a good idea. They make the
mechanism used to synchronize access to the shared data, which is
a private implementation detail of the class, and expose it to the world. The
main danger is that there is nothing preventing users of the shared counter
object from performing synchronization that can result in unintended
consequences.
public synchronized void waitThreshold(int value) throws InterruptedException {
while (count < value) {
this.wait();
}
}
}
25
Java - High Level Concurrency Support


High-Level Java Concurrency Features
We can use the standard Java APIs to develop basic tasks, but higher-level building
blocks are needed for more advanced tasks.


This is especially true for massively concurrent applications that fully exploit today's
multiprocessor and multi-core systems.
High-level concurrency features were introduced in Java 5.0 in the
java.util.concurrent packages.





Lock objects support locking idioms that simplify many concurrent applications.
Executors define a high-level API for launching and managing threads. Executor
implementations provided by java.util.concurrent provide thread pool management
suitable for large-scale applications.
Concurrent collections make it easier to manage large collections of data, and can
greatly reduce the need for synchronization.
Atomic variables have features that minimize synchronization and help avoid memory
consistency errors.
ThreadLocalRandom (in JDK 7) provides efficient generation of pseudorandom
numbers from multiple threads.
26
Java Concurrency Issues

Java Model of Concurrency

All concurrency abstractions in Java are based on the shared mutable state
paradigm and prone to the vulnerabilities of race conditions,
blocking/contention and deadlocks.

Fork/Join will allow programmers to exploit finer-grained concurrency by
allowing independent task components to be parallelized through recursive
divide-and-conquer techniques.

The Fork/Join task can be mapped to a pool of worker threads that initiates
and manages their execution using advanced queuing and scheduling
techniques.

When multiple threads can potentially invade a piece of critical section
concurrently, the programming model becomes complicated.

Fork/Join points us towards functional decomposition, which becomes most
effective, when we can talk about side-effect-free subtasks that can execute in
its own thread of execution independent of its other counterparts.

We should note that not all problems are parallelizable via decomposition.

To ensure that all subtasks do not share any mutable state, while programming in an
imperative language, is a big ask.
27
Conclusion

Topics Addressed:

Introduction to Monitors

Condition Variables

General form of a Monitor

Monitor Invariant

Readers and Writers

Synchronization Techniques with examples

The Sleeping Barber

Java and Monitors

Java and Synchronization Issues
28