HW4
released: 10/13, 7:00
due: 10/19, 13:00

Answer the following questions.
Submit your answers to Canvas assignments. There is an entry for this homework.


1. Time-of-check-to-time-of-use (TOCTTOU) bugs

Alice and Bob each have an account in a bank. Bob wants to transfer money to Alice.
The implementation of function transferBob2Alice is not correct.

  // assume all the variables are initialized correctly
  int alice_balance, bob_balance;
  mutex_t m;

  bool
  transferBob2Alice(int trans) {
    if (bob_balance > trans) {
      acquire(&m);
      bob_balance = bob_balance - trans;
      alice_balance = alice_balance + trans;
      release(&m);
      return true;
    }
    return false;
  }

Questions:
  1.a. What's wrong? (Give a problematic interleaving.)
  1.b. State the fix in one sentence.


2. Deadlock

The bank decides to use fine-grained locking. Here is its implementation:

  // assume all the variables are initialized correctly
  int balance[2];    // 0 for alice, 1 for bob
  mutex_t mtx[2];   // 0 for alice, 1 for bob

  bool transfer(int from, int to, int trans) {
    acquire(&mtx[from]);
    acquire(&mtx[to]);

    bool result = false;
    if (balance[from] > trans) {
      balance[from] = balance[from] - trans;
      balance[to] = balance[to] + trans;
      result = true;
    }

    release(&mtx[to]);
    release(&mtx[from]);
    return result;
  }

Questions:
  2.a. Write down an interleaving that results in deadlock.
  2.b. Keeping the same data structures, rewrite transfer() to eliminate the possibility of deadlock

    bool transfer(int from, int to, int trans) {
      // your code here
    }


3. Priority Inversion

In this problem, the system has three tasks: one at high priority, one at
medium priority, and one at low priority. Assume that the intent is to schedule
according to strict priority (although we will see that this intent will hold).

Some assumptions:
  - The system runs one task a time (so assume a single CPU).
  - All three tasks are begun before the first task ends (any task can start first.)
  - If a task with higher priority is ready to run, it will preempt the running
    task (note that if a thread is waiting on a mutex that is owned by another
    thread, then the waiting thread is NOT ready to run!).
  - Preemption can happen inside the critical section (just as when you code
    using mutexes in application space).
  - If a thread cannot continue (for example because it is waiting for a mutex), it yields.

Here are the three tasks:
    mutex_t res;

    void highPriority() {
      ... // do something
      acquire(&res);
      ... // handle resource
      release(&res);
      printf("A ");
    }

    void mediumPriority() {
      ... // do something
      printf("B ");
    }

    void lowPriority() {
      acquire(&res);
      ... // handle resource
      release(&res);
      ... // do something
      printf("C ");
    }

Questions:
  3.a. Which of the following outputs are possible?

    A B C
    A C B
    B A C
    C B A

  3.b. Explain.