Takashi's Notes

Monitors and blocking synchronization

7 min read

Monitors and blocking synchronization

Prev: Spin locks and contention Next: Linked lists: the role of locking

Exercises

Exercise 8.1. Reimplement the SimpleReadWriteLock class using Java synchronized, wait(), notify(), and notifyAll() constructs in place of explicit locks and conditions.

Hint: you must figure out how methods of the inner read and write lock classes can lock the outer SimpleReadWriteLock object.

Exercise 8.2. Design a nested readers-writers lock in which a thread must first grab the read lock in order to grab the write lock, and releasing the write lock does not release the read lock. In order for a reader to become a writer with exclusive write access, every other reader must either unlock the read lock or also attempt to lock the write lock. Show that your implementation is correct and has a reasonable fairness guarantee between readers and writers.

Exercise 8.3. Read-write locks are fundamentally asymmetric in that many readers can enter at once but only one writer can enter. Design a symmetric locking protocol for two types of threads: RED and BLUE. For correctness, never allow a RED and BLUE thread to enter simultaneously. For progress, allow for multiple RED threads or multiple BLUE threads to enter at once, and have a symmetric fairness mechanism for draining RED threads to allow waiting BLUE threads to enter, and vice versa. Show that your implementation is correct, and describe the exact fairness property it guarantees and why you chose to use it.

Exercise 8.4. The ReentrantReadWriteLock class provided by the java.util.concurrent.locks package does not allow a thread holding the lock in read mode to then access that lock in write mode. The thread will block. Justify this design decision by sketching what it would take to permit such lock upgrades.

Exercise 8.5. A savings account object holds a nonnegative balance, and provides deposit(k) and withdraw(k) methods, where deposit(k) adds to the balance, and withdraw(k) subtracts , if the balance is at least , and otherwise blocks until the balance becomes or greater.

  1. Implement this savings account using locks and conditions.
  2. Now suppose there are two kinds of withdrawals: ordinary and preferred. Devise an implementation that ensures that no ordinary withdrawal occurs if there is a preferred withdrawal waiting to occur.
  3. Now add a transfer() method that transfers a sum from one account to another:
void transfer(int k, Account reserve) {
  lock.lock();
  try {
    reserve.withdraw(k);
    deposit(k);
  } finally {
    lock.unlock();
  }
}

We are given a set of 10 accounts, whose balances are unknown. At 1:00pm, each of threads tries to transfer 1000 to each account. Is every transfer() method called at 1:00pm certain to return?

Exercise 8.6. In the shared-bathroom problem, there are two classes of threads, called MALE and FEMALE. There is a single Bathroom resource that must be used in the following way:

  1. Mutual exclusion: persons of opposite sex may not occupy the bathroom simultaneously.
  2. Weak starvation-freedom: assuming that eventually there will be both a male and a female who want to use the bathroom, then everyone who needs to use the bathroom eventually enters.

The protocol specifies the following four procedures: enterMale() delays the caller until a male can enter the bathroom, and leaveMale() is called when a male leaves the bathroom, while enterFemale() and leaveFemale() do the same for females. For example:

enterMale();
teeth.brush(toothpaste);
leaveMale();

Implement this class using locks and condition variables. Explain why your implementation satisfies mutual exclusion and weak starvation-freedom.

Exercise 8.7. The Rooms class manages a collection of rooms, indexed from 0 to , where is an argument to the constructor. Threads can enter or exit any room in that range. Each room can hold an arbitrary number of threads simultaneously, but only one room can be occupied at a time. For example, if there are two rooms, indexed 0 and 1, then any number of threads might enter room 0, but no thread can enter room 1 while room 0 is occupied.

Each room can be assigned an exit handler: calling setExitHandler(i, h) sets the exit handler for room i to handler h. The exit handler is called by the last thread to leave a room, but before any threads subsequently enter any room. This method is called once per room and while it is running, no threads are in any rooms.

public class Rooms {
  public interface Handler {
    void onEmpty();
  }
 
  public Rooms(int m) { ... }
  public void enter(int i) { ... }
  public boolean exit() { ... }
  public void setExitHandler(int i, Rooms.Handler h) { ... }
}

Implement the Rooms class. Make sure that:

  • If some thread is in room i, then no thread is in room j != i.
  • The last thread to leave a room calls the room’s exit handler, and no threads are in any room while that handler is running.
  • Your implementation is fair: any thread that tries to enter a room eventually succeeds. You may assume that every thread that enters a room eventually leaves.

Exercise 8.8. Consider an application with distinct sets of active and passive threads, where we want to block the passive threads until every active thread has given permission for the passive threads to proceed.

A CountDownLatch encapsulates a counter, initialized to the number of active threads. An active thread gives permission for the passive threads to run by calling countDown(), which decrements the counter. Each passive thread calls await(), which blocks the thread until the counter reaches zero.

Provide a CountDownLatch implementation. Do not worry about reusing the CountDownLatch object.

class Driver {
  void main() {
    CountDownLatch startSignal = new CountDownLatch(1);
    CountDownLatch doneSignal = new CountDownLatch(n);
    for (int i = 0; i < n; ++i)
      new Thread(new Worker(startSignal, doneSignal)).start();
    doSomethingElse();
    startSignal.countDown();
    doSomethingElse();
    doneSignal.await();
  }
 
  class Worker implements Runnable {
    private final CountDownLatch startSignal, doneSignal;
 
    Worker(CountDownLatch myStartSignal, CountDownLatch myDoneSignal) {
      startSignal = myStartSignal;
      doneSignal = myDoneSignal;
    }
 
    public void run() {
      startSignal.await();
      doWork();
      doneSignal.countDown();
    }
  }
}

Exercise 8.9. This exercise is a followup to Exercise 8.8. Provide a CountDownLatch implementation where the CountDownLatch object can be reused.

Exercise 8.10. The following shows a proposed implementation of a RateLimiter class, which runs jobs but limits the weight of the jobs started per minute using a quota, which is increased to LIMIT every minute by a separate thread. We want to guarantee that jobs will run promptly if there is enough quota. You may assume a fast processor and fair scheduler, so that the RateLimiter reaches a quiescent state, all jobs are sleeping in await() or running, if possible, before each call to increaseQuota().

  1. Describe the distributions of weight values, where , under which this implementation works or fails and explain why.
  2. Fix this implementation so it allows jobs to have any weight value from 0 to LIMIT, and describe how it may impact performance.
public class RateLimiter {
  static final int LIMIT = 100;
  public int quota = LIMIT;
  private Lock lock = new ReentrantLock();
  private Condition needQuota = lock.newCondition();
 
  public void increaseQuota() {
    synchronized(lock) {
      if (quota < LIMIT) {
        quota = LIMIT;
        needQuota.signal();
      }
    }
  }
 
  private void throttle(int weight) {
    synchronized(lock) {
      while (quota < weight) {
        needQuota.await();
      }
      quota -= weight;
      if (quota > 0) {
        needQuota.signal();
      }
    }
  }
 
  public void run(Runnable job, int weight) {
    throttle(weight);
    job.run();
  }
}

Prev: Spin locks and contention Next: Linked lists: the role of locking

Graph View

Backlinks