CS 372 Operating Systems

Homework 2: Synchronization

Due: 10am Monday February 21, 2005
McKinley: in class
Mok and Witchel: in Taylor Homework Box
  1. Synchronization.  Describe an advantage of using enabling/disabling interrupts to provide a critical section over using a locking instruction such as test&set and vice versa. Would your answer depend on whether the critical section is user-supplied application code or OS code?

  2. Synchronization. Making Water. You need two hydrogen atoms (H), and one oxygen (O) to make water. Write solutions that generate water as soon as the atoms are available.

    1. Solve the problem using semaphores.
    2. Solve the problem using monitors.

  3. Monitors. A long term scheduling problem. A machine comes with a fixed size of memory M. Each process, i, in the system takes up some initial amount of memory space, K less than M. The OS only lets new processes become active in the system if the system will still use less than M amount of memory. When a process terminates, it releases all its memory. While a process is running it can request that the OS give it additional memory (increase K by A, K+A less than M). The OS satisfies this request if it can, otherwise it makes the process release all of its memory until the OS can satisfy the request. Insure your solution does not result in deadlock.

    You need to write three methods: Start(int i, K), AddMemory(int i, A) and Terminate(int i). You can assume each process id i is unique. Use an array memory[i] to keep track of the current memory in use by process i. To keep your solution as simple as possible, do not allocate or bounds check it. You can also assume all requests satisfy the constraints above (i.e., your code should not check that the process always requests less than M amount of memory).

  4. Deadlock. What does a resource allocation graph show? What does a cycle in the the resource graph mean?

  5. Deadlock. Consider the following Java progam. Can it deadlock? If not, does it correctly transfer money? 
    public class BankAccounts{
   private int accounts;

   public class synchronized void Account () {
   private int total;
   private boolen busy;
   ...
   Account(...) {
      ...
   }
   public synchronized void transfer(
         Account withdraw, Account deposit, int amount) {
      withdraw.busy = true;
      deposit.busy = true;
      withdraw.transaction(--amount);
      deposit.transaction(amount);
      withdraw.busy = false;
      deposit.busy = false;
   }
   public synchronized void transaction(int amount) {
      while (busy) wait();
      if (amount > 0) total+= amount;
      else (total < -amount)
         throw new InsufficientFundException()
      else total -= amount;
  }
}