def binarySearch(a, key):
    i, j = 0, len(a)
    while i + 1 < j:
        h = (i + j) // 2
        if a[h] <= key: i = h
        else: j = h
    return a[i] == key

class Point {
    int x, y;
    Point(int x0, int y0) {
        x = x0; y = y0;
    }
    void move(int dx, int dy) {
        x += dx; y += dy;
    }
}

%%writefile Counter.java
class Counter {
    int a = 0;
    boolean e = true;
    // e == even(a)
    synchronized void inc() {
        a += 1; e = !e;
    }
    synchronized boolean even() {
        return e;
    }
}

synchronized void inc() {
        a += 1; e = !e;
    }

%%writefile Counter.java
class Counter {
    int a = 0;
    boolean e = true;
    // e == even(a)
    synchronized void inc() {
        a += 1; e = !e;
    }
    synchronized boolean even() {
        return e;
    }
}

%%writefile Semaphore.java
class Semaphore {
    int val;
    Semaphore(int init) {
        val = init;
    }
    synchronized void P() throws InterruptedException {
        while (val == 0) wait();
        val -= 1;
    }
    synchronized void V() {
        val += 1;
        notify();
    }
}

%%writefile OnePlaceBuffer.java
class OnePlaceBuffer {
    private Object buf;
    synchronized void deposit(Object x) throws InterruptedException {
        while (buf != null) wait();
        buf = x; notifyAll();
    }
    public synchronized Object fetch() throws InterruptedException {
        while (buf == null) wait();
        Object x = buf; buf = null;
        notifyAll(); return x;
    }
}

%%writefile BoundedBuffer.java
class BoundedBuffer { // INCORRECT
    int[] buf;
    int in = 0, out = 0, size;
    Semaphore full, empty;
    /* buf != null && buf.length == size && 0 <= in < size && 0 <= out < size &&
       0 <= full.val <= size && full.val + empty.val   ` == size && in == (out + full.val) % size
    */ 
    BoundedBuffer(int size) {
        this.size = size; buf = new int[size];
        full = new Semaphore(0); empty = new Semaphore(size);
    }
    synchronized void deposit(int x) throws InterruptedException {
        empty.P(); System.out.println("depositing");
        buf[in] = x; in = (in + 1) % size;
        full.V();
    }
    synchronized int fetch() throws InterruptedException {
        full.P(); System.out.println("fetching");
        int x = buf[out]; out = (out + 1) % size;
        empty.V(); return x;
    }
}

%%writefile BoundedBuffer.java
BoundedBuffer b = new BoundedBuffer(1);

class Fetcher extends Thread {
    public void run() {
        try {System.out.println(b.fetch());
        } catch (Exception e) {}
    }
}

System.out.println("starting");
Thread f = new Fetcher(); f.start(); Thread.sleep(100); // milliseconds
b.deposit(3)

%%writefile BoundedBuffer.java
class BoundedBuffer <E> { // CORRECT
    E[] buf;
    int in = 0, out = 0, size;
    Semaphore full, empty;
    /* buf != null && buf.length == size && 0 <= in < size && 0 <= out < size &&
       0 <= full.val <= size && full.val + empty.val == size && in == (out + full.val) % size
    */
    BoundedBuffer(int size) {
        this.size = size; buf = (E[]) new Object[size];
        full = new Semaphore(0); empty = new Semaphore(size);
    }
    void deposit(E x) throws InterruptedException {
        empty.P();
        synchronized(this) {buf[in] = x; in = (in + 1) % size;}
        full.V();
    }
    E fetch() throws InterruptedException {
        E x; full.P();
        synchronized(this) {x = buf[out]; buf[out] = null; out = (out + 1) % size;}
        empty.V(); return x;
    }
}

%%writefile ReadersWriters.java
class ReadersWriters {
    // … data …
    private int nr = 0;	// number of readers
    private synchronized void startRead() {
        nr += 1;
    }
    private synchronized void endRead() {
        nr -= 1; if (nr == 0) notify(); // awaken waiting writers
    }
    void read() {
        startRead();
        // … read data … 
        endRead();
    }
    synchronized void write() throws InterruptedException {
        while (nr > 0) wait();
        // … write data …; 
        notify(); // awaken another waiting writer
    }
}

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

%%writefile barber.c

#include <pthread.h>
#include <stdio.h>
#include <stdbool.h>

/* barber shop monitor */

int barber = 0, chair = 0, exit = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;          /* monitor lock */
pthread_cond_t barberAvailable = PTHREAD_COND_INITIALIZER;  /* signalling condition: barber > 0 */
pthread_cond_t chairOccupied = PTHREAD_COND_INITIALIZER;    /* signalling condition: chair > 0 */
pthread_cond_t exitOpen = PTHREAD_COND_INITIALIZER;         /* signalling condition: exit > 0 */
pthread_cond_t customerLeft = PTHREAD_COND_INITIALIZER;     /* signalling condition: exit = 0 */

/* monitor invariant: 0 <= barber <= 1 && 0 <= chair <= 1 && 0 <= exit <= 1 */

void getHaircut(long cust) {
    pthread_mutex_lock(&mutex);                             /* monitor entry */
        printf("%d waiting for barber\n", cust);
        while (barber == 0) pthread_cond_wait(&barberAvailable, &mutex);
        barber -= 1;
        chair += 1; pthread_cond_signal(&chairOccupied);
        printf("%d waiting for exit door\n", cust);
        while (exit == 0) pthread_cond_wait(&exitOpen, &mutex);
        exit -= 1; pthread_cond_signal(&customerLeft);
    pthread_mutex_unlock(&mutex);                            /* monitor exit */
}
void getNextCustomer() {
    pthread_mutex_lock(&mutex);                              /* monitor entry */
        barber += 1 ; pthread_cond_signal(&barberAvailable);
        printf("waiting for customer to sit in chair\n");
        while (chair == 0) pthread_cond_wait(&chairOccupied, &mutex);
        chair -= 1;
    pthread_mutex_unlock(&mutex);                            /* monitor exit */
}
void finishedCut() {
    pthread_mutex_lock(&mutex);                              /* monitor entry */
        exit += 1; pthread_cond_signal(&exitOpen);
        printf("waiting for customer to leave\n");
        while (exit > 0) pthread_cond_wait(&customerLeft, &mutex);
    pthread_mutex_unlock(&mutex);                            /* monitor exit */
}

/* end barber shop monitor */

void *villagebarber() {
    while (true) {
        getNextCustomer();  /* wait for a customer to sit in the barber's chair */
        printf("cutting hair\n"); sleep(1);
        finishedCut();      /* allow the customer to leave; returns after the customer left */
    }
}
void *customer(void *t) {
    long cust = (long) t;
    while (true) {
        printf("%d lives happily\n", cust); sleep(2);
        getHaircut(cust);
    }
}
        
int main(int argc, char *argv[]) {
    int numcust = atoi(argv[1]);
    long i;
    pthread_t b, c[numcust];
    pthread_create(&b, NULL, &villagebarber, NULL);
    for (i = 0; i < numcust; i++) pthread_create(&c[i], NULL, &customer, (void *) i);
    pthread_join(b, NULL);
    for (i = 0; i < numcust; i++) pthread_join(c[i], NULL);
}

!cc -pthread barber.c
!./a.out 5

from threading import Lock


class Counter:
  def __init__(self):
    self.count, self.lock = 0, Lock()

  def once(self):
    self.lock.acquire()
    self.count += 1
    self.lock.release()


c = Counter()
for _ in range(10):
  c.once()
c.count

class Counter:
  def __init__(self):
    self.count, self.lock = 0, Lock()

  def once(self):
    with self.lock:
      self.count += 1


c = Counter()
for _ in range(10):
  c.once()
c.count

class CounterPlus(Counter):
  def twice(self):
    with self.lock:
      super().once()  # same as Counter.once(self)
      super().once()


c = CounterPlus()
for _ in range(10):
  c.twice()
c.count

from threading import Lock


class Counter:
  def __init__(self):
    self.count, self.lock = 0, Lock()

  def inc(self):
    self.count += 1

  def once(self):
    with self.lock:
      self.inc()


c = Counter()
for _ in range(10):
  c.once()
c.count

class CounterPlus(Counter):
  def twice(self):
    with self.lock:
      super().inc()
      super().inc()


c = CounterPlus()
for _ in range(10):
  c.twice()
c.count

from threading import RLock


class Counter:
  def __init__(self):
    self.count, self.lock = 0, RLock()

  def once(self):
    with self.lock:
      self.count += 1


class CounterPlus(Counter):
  def twice(self):
    with self.lock:
      super().once()
      super().once()


c = CounterPlus()
for _ in range(10):
  c.twice()
c.count

`swap(a, 0, 1):`	`a:`	`swap(a, 1, 2):`
	`[5, 6, 7, 8]`
`h = a[0]`
		`h = a[1]`
`a[0] = a[1]`
	`[6, 6, 7, 8]`
		`a[1] = a[2]`
	`[6, 7, 7, 8]`
`a[1] = h`
	`[6, 5, 7, 8]`
		`a[2] = h`
	`[6, 5, 6, 8]`

Monitors¶

Emil Sekerinski, McMaster University, Fall 2019¶

On Thread-Safety and Monitors¶

Condition Variables¶

Additional Operations on Condition Variables¶

Monitor Implementation of a Semaphore¶

Readers and Writers¶

The Sleeping Barber¶

Monitors in Java¶

Semaphores in Java¶

Bounded Buffer in Java¶

Readers and Writers in Java¶

Monitors in C with Pthreads¶

Recursive Locking¶

Implementation of Monitors with Semaphores¶

Discussion of Monitors¶