Agenda

• Announcements
  • CS Colloquium Friday, 2:30 PM, TCL 206: Brent Heeringa. Come on out.
  • Lab 4 due Thursday. You will see more examples today that will help you attack the "Dining Savages."
  • Lab 5 out.
• Classical Problems of Synchronization
  • Dining Philosophers
  • Readers-Writers
  • Sleeping Barber

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 */
    
      }