Transcript Monitor

Outline
 Monitors
o Monitors in Java
 Barrier synchronization
 The sleeping barber problem
 Readers and Writers
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
1
Monitors - higher-level synchronization
(Hoare, Hansen, 1974-5)
 Semaphores and event-counters are low-level and errorprone
 Monitors are a programming-language construct
 Mutual exclusion constructs generated by the compiler.
Internal data structures are invisible.
 Monitors combine 2 synchronization mechanisms:
o Only one process is active at any given time inside the monitor.
o Condition variables for signaling (wait / signal).
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
2
Monitors - Definition
A monitor is a program module for concurrent
programming
o Encapsulate shared storage and operations.
A monitor has entry procedures
o Entry procedures are called by processes (threads); the
monitor is passive.
o The monitor guarantees mutual exclusion for calls of
entry procedures:
Condition variables are defined in the monitor
o Condition Variables are used within entry procedures for
condition synchronization.
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
3
Monitors
Only one monitor procedure active at any given time
monitor example
integer i;
condition c;
entry procedure p1( );
.
.
.
end;
entry procedure p2( );
.
.
.
end;
end monitor;
Slide taken from a presentation by Gadi Taubenfeld from IDC
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
4
Monitors: Condition variables
 Monitors guarantee “automatic” mutual exclusion
 Conditional variables enable signaling.
 Condition variables support two operations: wait and signal
o Signaling has no effect if there are no waiting threads
 The monitor provides queuing for waiting procedures
 When one operation waits and another signals there are two ways to proceed:
o The signaled operation will execute first: signaling operation immediately
followed by block() or exit_monitor (Hoare semantics)
o The signaling operation is allowed to proceed (Java semantics)
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
5
Monitors: Wait/Signal
wait (c) The executing process leaves the monitor and waits in a set associated to
c, until it is released by a subsequent call signal(c); then the process accesses
the monitor again and continues.
signal (c): The executing process releases one arbitrary process that waits for c.
Which of the two processes immediately continues its execution in the monitor
depends on the variant of the signal semantics:
signal-and-exit semantics (Hoare’s semantics):
The process that executes signal terminates the entry procedure call and leaves the monitor. The released process
enters the monitor immediately -without a state change in between and without the mutex being released ever
(hand to hand transfer of the mutex from signaling process to waiting process).
signal-and-wait semantics:
The process that executes signal leaves the monitor and waits to re-enter the monitor. The released process enters
the monitor immediately - without a state change in between (hand to hand transfer of mutex).
signal-and-continue semantics (Java semantics):
The process that executes signal continues execution in the monitor. The released process has to wait until the
monitor is free. The state that held at the signal call may be changed meanwhile; the waiting condition has to
be checked again. (no hand to hand transfer of mutex.)
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
6
type monitor-name = monitor
variable declarations
procedure entry P1 (…);
begin … end;
procedure entry P2 (…);
begin … end;
.
.
.
procedure entry Pn (…);
begin … end;
begin
initialization code
end
Entry queue
Shared data
Queues associated
with x, y conditions
x
y
…
operations
Figure 6.20 Monitor with Condition Variable
Ben-Gurion University
Initialization
code
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
7
Bounded Buffer Producer/Consumer with Monitors
This code only works if a
signaled thread is the next to
enter the monitor (Hoare)
Slide taken from a presentation by Gadi Taubenfeld from IDC
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
8
Issues if non-Hoare semantics
1. The buffer is full, k producers (for some k>1) are waiting on the full condition variable. Now, N
consumers enter the monitor one after the other, but only the first sends a signal (since count==N-1)
holds for it. Therefore only a single producer is released and all others are not. The corresponding
problem can occur on the empty semaphore.
Slide taken from a presentation by Gadi Taubenfeld from IDC
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
9
Issues if non-Hoare semantics (cont'd)
2) The buffer is full, a single producer p1 sleeps on the full condition variable. A consumer executes
and makes p1 ready but then another producer, p2, enters the monitor and fills the buffer. Now p1
continues its execution and adds another item to an already full buffer.
Slide taken from a presentation by Gadi Taubenfeld from IDC
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
10
Monitors - some comments
 Condition variables do not accumulate signals for later use
 wait() must come before signal() in order to be signaled
 No race conditions, because monitors have mutual exclusion
 Complex to implement – but “difficult work” done by compiler
 Implementation issues:
o How to interpret nested monitors?
o How to define wait, priority scheduling, timeouts, aborts?
o How to handle exception conditions?
o How to interact with process creation and destruction?
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
11
Implementing Monitors with Semaphores – take 1
semaphore mutex=1; /*control access to monitor*/
semaphore c /*represents condition variable c */
void enter_monitor() {
down(mutex); /*only one-at-a-time*/
}
void leave() {
up(mutex); /*allow other processes in*/
}
void leave_with_signal(semaphore c) { /* leave with signaling c*/
up(c);
/*release the condition variable, mutex not released */
}
void wait(semaphore c) { /* block on a condition c */
up(mutex); /*allow other processes*/
down (c); /*block on the condition variable*/
}
Any problem with this code? May deadlock.
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
12
Implementing Monitors with Semaphores – take 1
semaphore mutex=1;
semaphore c
/*control access to monitor*/
/*represents condition variable c */
void enter_monitor() {
down(mutex);
/*only one-at-a-time*/
}
void leave() {
up(mutex);
/*allow other processes in*/
}
void leave_with_signal(semaphore c) { /* leave with signaling c*/
up(c); /*release the condition variable, mutex not released */
}
void wait(semaphore c) { /* block on a condition c */
up(mutex); /*allow other processes*/
down (c); /*block on the condition variable*/
}
Signal as last call in
a procedure – unblocks
a process that did wait
and leave the monitor
without freeing mutex.
When wait resumes
from down(c) it does not
need to acquire mutex
because mutex was not
freed by signal(c)
Hand to hand passing of mutex – but if “missed signal”
(signal when no one waiting) – mutex is no freed 
deadlock.
Solution is that signal must distinguish between
signal->wait transitions and signal->exit transitions.
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
13
Implementing Monitors with Semaphores - Correct
Semaphore mutex = 1;
Cond c;
void enter_monitor() {
down(mutex);
}
void leave() {
up(mutex);
}
void leave_with_signal(cond c) {
if (c.count == 0)
up(mutex);
else {
c.count--;
up(c.s);
}
}
void wait(cond c)
{
c.count++;
up(mutex);
down(c.s);
}
Ben-Gurion University
/* control access to monitor */
/* c = {count;semaphore} */
/* only one-at-a-time
*/
/* allow other processes in */
/* cond c is a struct
*/
/* no waiting, just leave.. */
/*
/*
/*
/*
block on a condition
*/
count waiting processes */
allow other processes */
block on the condition */
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
14
Outline
 Monitors
o Monitors in Java
 Barrier synchronization
 The sleeping barber problem
 Readers and writers
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
15
Monitors in Java (before Java 5)
 Java directly adapted the Monitor model with some changes.
 Procedures designated as synchronized are like entry procedures.
o All Java Object instances include an implicit mutex lock.
 No explicit condition variables
o Only a single implicit condition variable on “this”
o Signaling operations:
 Wait()
 Notify()
 NotifyAll()
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
16
Monitors in Java Util Concurrent
Explicit lock interface:
o Use when synchronized blocks don’t apply
 Time−outs, back−offs
 Assuring interruptibility
 Hand−over−hand locking
 Need multiple condition variables.
Multiple condition variables per lock
o Condition interface with lock.newCondition()
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
17
Producer-consumer in Java
class BoundedBuffer {
final Lock lock = new ReentrantLock();
final Condition notFull = lock.newCondition();
final Condition notEmpty = lock.newCondition();
final Object[] items = new Object[100];
int putptr, takeptr, count;
public void put(Object x) throws InterruptedException {
lock.lock();
try {
while (count == items.length) notFull.await();
items[putptr] = x;
if (++putptr == items.length) putptr = 0;
++count;
notEmpty.signal();
} finally {
lock.unlock();
}
}
public Object take() throws InterruptedException {
lock.lock();
try {
while (count == 0) notEmpty.await();
Object x = items[takeptr];
if (++takeptr == items.length) takeptr = 0;
--count;
notFull.signal();
return x;
} finally {
lock.unlock();
}
}
}
Ben-Gurion University
Java7 supports multiple condition variables
on a single lock using the Lock interface
and the newCondition() factory.
The java.util.concurrent.ArrayBlockingQueue class
provides this functionality (with generic types)
so there is no reason to implement this class.
condition.await() and signal()
require that the underlying lock
be acquired – else throw IllegalMonitorState.
Observe the pattern:
lock.lock();
try {…} finally { lock.unlock();}
to enforce mutex using an explicit lock
(instead of the implicit synchronized).
Explicit locks support testing for locking and timeout.
From http://www.docjar.com/docs/api/java/util/concurrent/locks/Condition.html
Written by Doug Lea with assistance from members of JCP JSR-166
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
18
Producer-consumer in Java
class Producer implements Runnable {
private BoundedBuffer bb;
public Producer(BoundedBuffer b) {bb = b;}
void run() {
while(true) {
Integer item = produceItem();
bb.insert(item);
}
}
protected Integer produceItem() { …}
}
class Consumer implements Runnable {
private BoundedBuffer bb;
public Consumer(BoundedBuffer b) {bb = b;}
void run() {
while(true) {
int item = bb.extract();
consume(item);
}
}
protected void consume(Integer item) { …}
}
Ben-Gurion University
class ProducerConsumer {
private Producer p;
private Consumer c;
private BoundedBuffer b;
public ProducerConsumer() {
b = new BoundedBuffer();
p = new Producer(b);
c = new Producer(b);
}
public static int main(String args[]){
(new Thread(p)).start();
(new Thread(c)).start();
}
}
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
19
Monitors in Java: comments
 notify() does not have to be the last statement
 wait() adds the calling Thread to the queue of waiting threads
 a Thread performing notify() is not blocked - just moves one waiting Thread to
state ready
 once the monitor is open, all queued ready Threads (including former waiting
ones) are contesting for entry (NO hand to hand passing of mutex).
 To ensure correctness, wait() operations must be part of a condition-checking
loop (because of the “hole” in the mutex between notify() and resume of
wait()).
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
20
Outline
 Monitors
o Monitors in Java
 Barrier synchronization
 The sleeping barber problem
 Readers and writers
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
21
Barriers
 Useful for computations that proceed in phases
 Use of a barrier:
(a) processes approaching a barrier
(b) all processes but one blocked at barrier
(c) last process arrives, all are let through
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
22
Using CyclicBarrier in Java
import
import
import
import
java.util.concurrent.BrokenBarrierException;
java.util.concurrent.CyclicBarrier;
java.util.logging.Level;
java.util.logging.Logger;
public class CyclicBarrierExample {
//Runnable task for each thread
private static class Task implements Runnable {
private CyclicBarrier barrier;
public Task(CyclicBarrier barrier) {
this.barrier = barrier;
}
}
public void run() {
try {
System.out.println(Thread.currentThread().getName() + " is waiting on barrier");
barrier.await();
System.out.println(Thread.currentThread().getName() + " has crossed the barrier");
} catch (InterruptedException ex) {
Logger.getLogger(CyclicBarrierExample.class.getName()).log(Level.SEVERE, null, ex);
} catch (BrokenBarrierException ex) {
Logger.getLogger(CyclicBarrierExample.class.getName()).log(Level.SEVERE, null, ex);
}
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
23
Using CyclicBarrier in Java
public static void main(String args[]) {
//create a CyclicBarrier with 3 parties, i.e., 3 Threads needs to call await()
final CyclicBarrier cb = new CyclicBarrier(3, new Runnable() {
public void run(){
//This task will be executed once all threads reach barrier
}
}
}
System.out.println("All parties are arrived at barrier, lets play");
});
new Thread(new Task(cb), "Thread 1").start();
new Thread(new Task(cb), "Thread 2") .start();
new Thread(new Task(cb), "Thread 3") .start();
Output:
Thread 1
Thread 3
Thread 2
All parties
Thread 3
Thread 1
Thread 2
is waiting on barrier
is waiting on barrier
is waiting on barrier
are arrived at barrier, lets play
has crossed the barrier
has crossed the barrier
has crossed the barrier
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
24
Typical Use of CyclicBarrier
Fork and Join
// Dispatch work to N workers
// Then merge the results.
class Solver {
final int N;
final float[][] data;
final CyclicBarrier barrier;
class Worker implements Runnable {
int myRow;
Worker(int row) { myRow = row; }
public void run() {
while (!done()) {
processRow(myRow);
try {
barrier.await();
} catch (InterruptedException ex) {
return;
} catch (BrokenBarrierException ex) {
return;
}
}
}
}
Ben-Gurion University
public Solver(float[][] matrix) {
data = matrix;
N = matrix.length;
barrier = new CyclicBarrier(N,
new Runnable() {
public void run() {
mergeRows(...);
}
});
for (int i = 0; i < N; ++i)
new Thread(new Worker(i)).start();
}
}
waitUntilDone();
Read more on the Fork-Join Framework
http://gee.cs.oswego.edu/dl/cpjslides/fj.pdf
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
25
Implementing CyclicBarrier
The fetch-and-increment instruction
Fetch-and-increment(w)
do atomically
prev:=w
w:=w+1
return prev
Called InterlockedIncrement in Windows
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
26
Why can’t we just do simple?
shared integer counter=0
Barrier()
Fetch-and-increment(counter)
await (counter == n)
We want to reset the barrier and re-use it (recycle) and
We want to execute a follow-up action only once.
Who should reset? Beware the race condition!
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
27
A simple barrier using fetch-and-inc
shared integer counter=0, bit go
local local-go, local-counter
Barrier()
local-go := go
local-counter := Fetch-and-increment(counter)
if (local-counter == n-1)
counter := 0
go := 1-go
else
await (local-go ≠ go)
This is a busy-wait solution – look at Java solution for lock-based
higher latency barrier:
http://www.docjar.com/html/api/java/util/concurrent/CyclicBarrier.java.html
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
28
Outline
 Monitors
o Monitors in Java
 Barrier synchronization
 The sleeping barber problem
 Readers and writers
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
29
CyclicBarrier Java Implementation (1/4)
public class CyclicBarrier {
/**
* Each use of the barrier is represented as a generation instance.
* The generation changes whenever the barrier is tripped, or
* is reset. There can be many generations associated with threads
* using the barrier - due to the non-deterministic way the lock
* may be allocated to waiting threads - but only one of these
* can be active at a time (the one to which <tt>count</tt> applies)
* and all the rest are either broken or tripped.
* There need not be an active generation if there has been a break
* but no subsequent reset.
*/
private static class Generation {
boolean broken = false;
}
/** The lock for guarding barrier entry */
private final ReentrantLock lock = new ReentrantLock();
/** Condition to wait on until tripped */
private final Condition trip = lock.newCondition();
/** The number of parties */
private final int parties;
/* The command to run when tripped */
private final Runnable barrierCommand;
/** The current generation */
private Generation generation = new Generation();
/**
* Number of parties still waiting. Counts down from parties to 0
* on each generation. It is reset to parties on each new
* generation or when broken.
*/
private int count;
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
30
CyclicBarrier Java Implementation (2/4)
/**
* Updates state on barrier trip and wakes up everyone.
* Called only while holding lock.
*/
private void nextGeneration() {
// signal completion of last generation
trip.signalAll();
// set up next generation
count = parties;
generation = new Generation();
}
/**
* Sets current barrier generation as broken and wakes up everyone.
* Called only while holding lock.
*/
private void breakBarrier() {
generation.broken = true;
count = parties;
trip.signalAll();
}
public CyclicBarrier(int parties, Runnable barrierAction) {
if (parties <= 0) throw new IllegalArgumentException();
this.parties = parties;
this.count = parties;
this.barrierCommand = barrierAction;
}
public int await() throws InterruptedException, BrokenBarrierException {
try {
return dowait(false, 0L);
} catch (TimeoutException toe) {
throw new Error(toe); // cannot happen;
}
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
31
CyclicBarrier Java Implementation (3/4)
/**
* Main barrier code, covering the various policies.
*/
private int dowait(boolean timed, long nanos)
throws InterruptedException, BrokenBarrierException,
TimeoutException {
final ReentrantLock lock = this.lock;
lock.lock();
try {
final Generation g = generation;
if (g.broken)
throw new BrokenBarrierException();
if (Thread.interrupted()) {
breakBarrier();
throw new InterruptedException();
}
int index = --count;
if (index == 0) { // tripped
boolean ranAction = false;
try {
final Runnable command = barrierCommand;
if (command != null)
command.run();
ranAction = true;
nextGeneration();
return 0;
} finally {
if (!ranAction)
breakBarrier();
}
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
32
CyclicBarrier Java Implementation (4/4)
// loop until tripped, broken, interrupted, or timed out
for (;;) {
try {
if (!timed)
trip.await();
else if (nanos > 0L)
nanos = trip.awaitNanos(nanos);
} catch (InterruptedException ie) {
if (g == generation && ! g.broken) {
breakBarrier();
throw ie;
} else {
// We're about to finish waiting even if we had not
// been interrupted, so this interrupt is deemed to
// "belong" to subsequent execution.
Thread.currentThread().interrupt();
}
}
if (g.broken)
throw new BrokenBarrierException();
if (g != generation)
return index;
if (timed && nanos <= 0L) {
breakBarrier();
throw new TimeoutException();
}
}
} finally {
lock.unlock();
}
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
33
CyclicBarrier Java Implementation: Notes
What makes the code complex?
- Interruptibility: what happens if any thread that is waiting on barrier
is interrupted?
- Exceptions: what happens if the thread that executes the followup
action throws an exception?
- Timeouts: how can we wait for the barrier for a limited amount of
time and give up after timeout?
That is – Barrier can exit for 4 different reasons:
(1) tripped (good), (2) broken, (3) interrupted or (4) timed out.
Introduce “broken barrier” case and “Generation” object:
- Can break barrier from the outside to “free” the blocked threads.
- Barrier is broken in case of interruption
- Threads of different generations can co-exist
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
34
The Sleeping Barber Problem
35
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
The sleeping barber problem (cont’d)
 Barber shop - one service provider; many customers
 A finite waiting queue
 One customer is served at a time
 Service provider, barber, sleeps when no customers are waiting
 Customer leaves if shop is full
 Customer sleeps while waiting in queue
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
36
The sleeping barber: implementation
#define CHAIRS
5
Semaphore customers = 0;
Semaphore barbers = 0;
int waiting = 0;
Semaphore mutex = 1;
//
//
//
//
number of waiting customers
number of available barbers: either 0 or 1
copy of customers for reading
mutex for accessing ‘waiting’
void barber() {
while (TRUE) {
down(customers);
// block if no customers
down(mutex);
// access to ‘waiting’
waiting = waiting - 1;
up(barbers);
// barber is in.
up(mutex);
// release ‘waiting’
// Synchronization complete:
// One barber faces one customer.
cut_hair();
}
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
37
The sleeping barber: implementation (cont’d)
void customer() {
down(mutex);
// access to `waiting’
if (waiting < CHAIRS) {
waiting = waiting + 1;
up(customers);
// wake up barber
up(mutex);
// release ‘waiting’
down(barbers);
// go to sleep if barbers=0
// Synchronization complete:
// one customer, one barber
get_haircut();
} else {
up(mutex);
}
// shop full - leave
}
Any problem with this code? Two customers on chair at once
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
38
The sleeping barber: correct synchronization
#define CHAIRS
5
Semaphore customers = 0;
Semaphore barbers = 0;
Semaphore mutex = 1;
Semaphore synch = 0;
int waiting = 0;
//
//
//
//
//
number of waiting customers
number of available barbers: 0 or 1
mutex for accessing ‘waiting’
synchronize the service operation
copy of customers for reading
void barber() {
while (TRUE) {
down(customers);
// block if no customers
down(mutex);
// access to ‘waiting’
waiting = waiting - 1;
up(barbers);
// barber is in..
up(mutex);
// release ‘waiting’
cut_hair();
down(synch)
//wait for customer to leave
}
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
39
The sleeping barber: correct synchronization (cont’d)
void customer() {
down(mutex);
if (waiting < CHAIRS) {
waiting = waiting + 1;
up(customers);
up(mutex);
down(barbers);
get_haircut();
up(sync);
// access to `waiting’
// wake up barber
// release ‘waiting’
// go to sleep if barbers=0
// synchronize service
// customer leaves chair
}
else {
up(mutex);
}
// shop full
.. leave
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
40
The sleeping barber in Java - Barber
public class Barber implements Runnable {
}
private Queue<Customer> customers;
private Shop shop;
public Barber(Shop shop) {
this.shop = shop;
customers = new LinkedBlockingQueue<Customer>(3);
}
public void addCustomerToQueue(Customer customer) {
customers.add(customer);
}
public void run() {
while (! customers.isEmpty()) {
Customer customer = customers.remove();
performHaircut(customer);
shop.releaseChair();
}
}
private void performHaircut(Customer customer) {
System.out.println("Customer " + customer.getId() +
" has got a haircut");
}
http://bluepi.in/blogs/2013/03/18/actors-in-action-sleeping-barber-problem-with-akka/
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
41
The sleeping barber in Java - Shop
public class Shop {
private Barber barber;
private Semaphore semaphore;
private AtomicInteger count = new AtomicInteger(0); // customers served
public Shop() {
semaphore = new Semaphore(3); // How many chairs in shop
}
public void init() {
barber = new Barber(this);
Executors.newSingleThreadScheduledExecutor()
.scheduleAtFixedRate(barber, 100, 1000, TimeUnit.MILLISECONDS);
}
public void acquireChair(Customer customer) throws InterruptedException {
boolean acquired = semaphore.tryAcquire(1, 100, TimeUnit.MILLISECONDS);
if (acquired) {
count.getAndIncrement();
barber.addCustomerToQueue(customer);
} else {
System.out.println("Turning customer " + customer.getId() + " away");
}
}
public void releaseChair() {
semaphore.release(1);
}
public int getSuccessfulHaircutCount() { return count.intValue(); }
}
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
42
The sleeping barber in Java - Notes
1.
Barber is an active object (Runnable) which works in the context of a Shop. Shop activates Barber
in an executor.
2.
Shop at the time of initialization passes itself as a callback to the Barber so that all the activities
performed by Barber can be recorded by the shop.
3.
Shop in the init method starts the barber in a periodic executor to periodically invoke run method.
This is instead of the “while (true)” loop of the naïve code (reduces contention on the
blockingQueue when many customers arrive at once).
4.
When a customer arrives, it tries to acquire a chair which is represented by a Semaphore(N), N is
the number of spots in the waiting room of the shop. No more than N customers can wait at any
given point. Note how we use the “tryAcquire” method of the semaphore with timeout instead of
testing explicitly for a counter as in the naïve code.
5.
Note usage of AtomicInteger to safely count served customers.
Questions:
1.
Complete code that simulates arrival of Customers.
2.
Why is init() needed in Shop? (Review “Escape reference” problem from SPL)
3.
Is the Barber queue used in a safe manner? (Any possible conflict between thread inserting new
Customers in addCustomerToQueue() and Barber taking them in run()?)
4.
Write a simpler version exploiting the BlockingQueue synchronization capabilities – compare
performance.
5.
How does the size of the waiting room impact overall performance?
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
43
Outline
 Monitors
o Monitors in Java
 Barrier synchronization
 The sleeping barber problem
 Readers and writers
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
44
The readers and writers problem
 Motivation: database access
 Two groups of processes: readers, writers
 Multiple readers may access database simultaneously
(no conflicts on read-only)
 A writing process needs exclusive database access
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
45
Readers and Writers: 1st algorithm
Int rc = 0
semaphore mutex = 1;
semaphore db = 1;
void reader() {
while (TRUE) {
down(mutex);
rc = rc + 1;
if (rc == 1)
down(db);
up(mutex);
read_data_base();
down(mutex);
rc = rc - 1;
if (rc == 0)
up(db);
up(mutex);
}
}
Ben-Gurion University
// # of reading processes
// controls access to rc
// controls database access
void writer() {
while(TRUE) {
down(db);
write_data_base()
up(db)
}
Who is more likely to run:
readers or writers?
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
46
Comments on 1st algorithm
 No reader is kept waiting, unless a writer has already
obtained the db semaphore
 Writer processes may starve - if readers keep coming in
and hold the semaphore db
 An alternative version of the readers-writers problem
requires that no writer is kept waiting once it is “ready” when a writer is waiting, no new reader can start reading
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
47
Readers and Writers: Writers priority
Int rc, wc = 0
// # of reading/writing processes
semaphore Rmutex, Wmutex = 1; // controls readers/writers access to rc/wc
semaphore Rdb, Wdb = 1; // controls readers/writers database access
void reader() {
while(TRUE) {
down(Rdb);
down(Rmutex);
rc = rc + 1;
if(rc == 1)
down(Wdb);
up(Rmutex);
up(Rdb)
read_data_base();
down(Rmutex);
rc = rc - 1;
if (rc == 0)
up(Wdb);
up(Rmutex); }
}
Ben-Gurion University
void writer() {
while(TRUE) {
down(Wmutex);
wc = wc + 1;
if (wc == 1)
down (Rdb);
up(Wmutex);
down(Wdb);
write_data_base();
up(Wdb);
down(Wmutex);
wc = wc-1;
if (wc == 0)
up(Rdb);
up(Wmutex); }}
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
48
Comments on 2nd algorithm
 When Readers are holding Wdb, the first Writer to arrive
decreases Rdb
 All Readers arriving later are blocked on Rdb
 All Writers arriving later are blocked on Wdb
 Only the last Writer to leave Wdb releases Rdb – Readers can
wait…
 If a writer and a few readers are waiting on Rdb, the writer may
still have to wait for these readers. If Rdb is unfair, the writer may
again starve.
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
49
Readers and Writers: improved writers priority
Int rc, wc = 0
// # of reading/writing processes
semaphore Rmutex, Wmutex, Mutex2 = 1;
semaphore Rdb, Wdb = 1;
void reader() {
while(TRUE) {
down(Mutex2)
down(Rdb);
down(Rmutex);
rc = rc + 1;
if (rc == 1)
down(Wdb);
up(Rmutex);
up(Rdb)
up(Mutex2)
read_data_base();
down(Rmutex);
rc = rc - 1;
if(rc == 0)
up(Wdb);
up(Rmutex); }
}
Ben-Gurion University
void writer() {
while(TRUE) {
down(Wmutex);
wc = wc + 1
if (wc == 1)
down (Rdb);
up(Wmutex);
down(Wdb);
write_data_base();
up(Wdb);
down(Wmutex);
wc = wc-1;
if (wc == 0)
up(Rdb);
up(Wmutex);
}
}
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
50
Improved writers priority
 After the first writer does down(Rdb), the first reader that enters
is blocked after doing down(Mutex2) and before doing up(Mutex2). Thus no
other readers can block on Rdb.
 This guarantees that the writer has to wait for at most a single reader.
Ben-Gurion University
Operating Systems, 2013, Meni Adler, Michael Elhadad, Amnon Meisels
51