Midterm 2 Review

CS42

1. A binary semaphore is a semaphore whose integer value can range only between 0 and 1. Show how a busy-wait counting semaphore can be implemented using binary semaphores.

2. Consider the following code fragment using five semaphores and four processes:

   main() {
   
       semaphore A = 2, B = 2, C = 3, D = 3, E = 2;
   
       cobegin {
          P1: {
             P(B,D,E);
             /* compute one */
             P(A,C);
             /* compute two */
             V(A,B,C,D,E);
          }
          P2: {
             P(C,D,E);
             /* compute one */
             P(A,B);
             /* compute two */
             V(A,B,C,D,E);
          }
          P3: {
             P(A,C);
             /* compute one */
             P(B,D);
             /* compute two */
             V(A,B,C,D);
          }
          P4: {
             P(A,B);
             /* compute one */
             P(D,E);
             /* compute two */
             V(A,B,D,E);
          }
       }
   }
   

   The cobegin statement is used to fork child processes. Each labeled block becomes a child process of the parent. For a multisemaphore P() to proceed, all of the semaphore arguments must have values greater than zero.

   Each process has completed its compute one phase and is performing the second multisemaphore P operation. Prove that this system is currently deadlocked. If you could increase by one the number of units of any of the five resources, which increase (if any) would resolve the deadlock?

3. The Cigarette Smokers Problem --- Consider a system with three smoker processes and one agent process. Each smoker continuously makes a cigarette and smokes it. But to make a cigarette, three ingredients are needed: tobacco, paper, and matches. One of the processes has paper, another tobacco and the third has matches. The agent has an infinite supply of all three. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient can then make and smoke a cigarette, signalling the agent upon completion. The agent then puts out another two of the three ingredients and the cycle repeats. Write a program to synchronize the agent and the smokers.

4. A barbershop consists of a lounge with N chairs and two barber rooms, one for each of the barbers (Phil and Mel). Each barber room contains one barber chair. If a barber is not cutting a customer's hair, he goes to sleep in his chair. If a customer enters the barbershop and the lounge is full, then the customer leaves the shop. A customer may express a preference for Phil or Mel, but not necessarily. If the barber is busy, then the customer sits in one of the available free chairs. Customers are served in the order of their arrival, with the of those customers who are waiting for a particular barber (in this case the other barber may possibly serve customers who arrived after this customer). If a barber is asleep, the customer wakes the barber up. Write processes (functions) for the barbers and the customers, showing how the processes are coordinated

5. What is a deadlock? What are the four necessary conditions for a deadlock? Are these four conditions sufficient to cause a deadlock? How does starvation differ from deadlock?

6. Consider the following snapshot of a system with five running processes and four resource types:

   

   1. Draw the claim graph that corresponds to this system state.

   2. Is the system state safe?

   3. If a request from process P1 arrives for (0,4,2,0) can the request be granted immediately? Why or why not?

7. A disk has 200 cylinders numbered from 0 to 199. The head is currently at cylinder 150. The queue of disk requests contains requests for the following cylinders: 34, 89, 142, 23, 24, 188, 77, 101, 142, 130

   Determine the order in which the requests are serviced for each of the following disk scheduling disciplines:

   1. FCFS scheduling

   2. SSTF scheduling

   3. C-SCAN scheduling