程序代写代做代考 compiler concurrency algorithm Java CO2017 — Week3L3 — Monitors

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