Homework 2 - Chapter 2 Questions 3, 4, and 7

  1. Explain the difference between busy waiting and blocking
  2. Busy waiting is when a process runs continually checking whether a flag has been set (or a lock freed). Blocking involves the process not running until it is woken up to let it know that the resource is available.

     

  3. Does the busy waiting solution using the turn variable work when two processes are running on two CPUs sharing a common memory?

It enforces mutual exclusion (i.e. it doesn't allow both processes in their critical sections at the same time), but it violates the "no process not in its critical section can cause another process to block" constraint.

  1. Figure 2-10 has a fatal race condition: if either process decides to go to sleep and is de scheduled just before it calls sleep, a wakeup can be lost. There is a 2nd race condition as well. What is it?

If the count = count + 1 and count = count - 1 get interleaved, count may have an incorrect value. This

can result in trying to take something from an empty queue or put something on a full queue.

Assume count starts out as N-1, a consumer reduces it to N-2. Before the test of count == N-1, a producer runs making it N-1 again. Now, the consumer tests count == N-1 and gets preempted before it calls wakeup. The producer runs again, and now count = N. The producer continues and goes to sleep. The consumer wakes the producer which puts the item into the already full buffer.