程序代写代做代考 Java compiler C graph concurrency c# cache Monitors

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 extends BaseBoundedBuffer {
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