HW4 answers
released: 10/20, 16: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.)

Answer:

Suppose Bob's balance is 100. There are two threads; each runs this function
to transfer 99. They both pass the if-check before going into the critical section.
If so, both functions will return True with an overdrawn balance (-98).

>   1.b. State the fix in one sentence.

Answer:

Moving "acquire" to the beginning of this function.

> 
> 
> 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.

Answer:

1. Alice calls transfer(0,1) and Bob calls transfer(1,0) in two threads at the same time.
2. Alice successfully acquires the mutex "mtx[0]".
3. Bob successfully acquires the mutex "mtx[1]". Deadlock.

>   2.b. Keeping the same data structures, rewrite transfer() to eliminate the possibility of deadlock
> 

bool transfer(int from, int to, int trans) {
    acquire(&mtx[0]);
    acquire(&mtx[1]);
    // others remain the same
}

[cheng:
  - this is ugly, and only works for this specific case of Alice and Bob.
  - if your solution acquires the lock in order, you should be fine.
]

> 
> 
> 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.
> 

Answer:

1. "A B C": High starts to run first, and then Medium and Low join. High has the
            highest priority it will run to complete, then Medium, then Low.

2. "A C B": this is not possible. Medium will always preempt Low (i.e., B will always printed before C).

3. "B A C": Low starts to run first and acquires the mutex, then High and Medium join.
            High cannot acquire the mutex, so it will wait. Because Medium has
            a higher priority than Low, it will preempt and run to complete.
            Then, Low will run to release the mutex; High will preempt and run to complete.
            Finally, Low will finish. This is priority inversion.

4. "C B A": this is not possible. Medium will always preempt Low (i.e., B will always printed before C).