Computer Science 432 Operating Systems Williams College Fall 2006

Agenda

• Announcements
  • Friday:

      if (isMountainDay(tomorrow)) {
        go on official CS Dept. Hike -- the Hopper Trail
      }
      else {
        colloquium with Max Ross from Google, 2:30 PM, TCL 206
      }
    

  • Lab 3 due Tuesday. It shouldn't take long.
  • Lab 4 out.
• Lecture assignment recap
• Classical Problems of Synchronization
  • Dining Philosophers
  • Readers-Writers
  • Sleeping Barber

Lecture Assignment

Due at the start of class, Thursday, October 12.

Please turn in a hard copy (typeset or handwritten are OK). We will discuss this problem during class, so no late submissions are accepted.

from a large pot that can hold M servings of stewed missionary. When a savage wants to eat, he helps himself from the pot, unless it is empty. If the pot is empty, the savage wakes up the cook and then waits until the cook has refilled the pot. The behavior of the savages and cook is defined by the following processes:

Develop psuedocode (along the lines of the in-class Sleeping Barber solution) for the actions of the savages and the cook. Use semaphores for synchronization. The only operations permitted on the semaphores are initialization, wait, and signal. You may assume the semaphores are fair. Your solution should avoid deadlock and awaken the cook only when the pot is empty. You do not need to implement C code, just a list of shared variables and pseudocode describing the actions of the savages and the cook. (5 points)

The readings for next time are the rest of SG&G Chapter 6 (except 6.9).

Examples

• Dining Philosophers
  • Straightforward attempt
    • Shared data:

      semaphore chopstick[5];
      chopstick[0..4]=1;
      

    • Philosopher i:

      while (1) {
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
      
         /* eat */
      
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
      
         /* think */
      
      }
      

  • Solution that breaks the symmetry

    void philosopher() {
      think;
      if (odd(i)) {
        wait(chopstick[(i+1) % n]);
        wait(chopstick[i]);
      }
      else {
        wait(chopstick[i]);
        wait(chopstick[(i+1) % n]);
      }
      eat;
      if (odd(i)) {
        signal(chopstick[(i+1) % n]);
        signal(chopstick[i]);
      }
      else {
        signal(chopstick[i]);
        signal(chopstick[(i+1) % n]);
      }
    }
    

• Readers-Writers
  • Shared data:

    semaphore wrt, mutex;
    int readcount;
    wrt=1; mutex=1; readcount=0;
    

  • Writer process:

    while (1) {
      wait(wrt);
    
        /* perform writing */
    
      signal(wrt);
    }
    

  • Reader process:

    while (1) {
      wait(mutex);
      readcount++;
      if (readcount == 1) wait(wrt);
      signal(mutex);
    
        /* perform reading */
    
      wait(mutex);
      readcount--;
      if (readcount == 0) signal(wrt);
      signal(mutex);
    }
    

• Sleeping Barber
  • Shared Data

    constant CHAIRS = maximum number of chairs (including barber chair)
    semaphore mutex=1,next_cust=0,barber_ready=0;
    int cust_count=0;
    

  • Customer process

      while (1) {
        /* live your non barber-shop life until you decide you need
           a haircut */
        wait(mutex);
         if (cust_count>=CHAIRS) {
           signal(mutex);
           exit; /* leave the shop if full, try tomorrow */ 
         }
         cust_count++;  /* increment customer count */
         signal(mutex);
         signal(next_cust);  /* wake the barber if he's sleeping */   
         wait(barber_ready); /* wait in the waiting room */
    
           /* get haircut here */
    
         wait(mutex);
         cust_count--;  /* leave the shop, freeing a chair */
         signal(mutex);
      }
    

  • Barber process

      while (1) {
        wait(next_cust); /* sleep until a customer shows up */  
        signal(barber_ready);  /* tell the next customer you are ready */
    
        /* give the haircut here */
    
      }