Agenda

• Announcements
  • CS Colloquium tomorrow, 2:30 PM, TCL 206: Gleb Naumovich from Polytechnic University, speaking on software obfuscation.
  • Lab 4 Out.
• Cooperating Processes
  • The critical section problem
    • algorithms depending on hardware support
  • Semaphores
    • abstract synchronization primitive
    • POSIX semaphores
    • pthreads mutexes
  • Classical Problems of Synchronization
    • Bounded Buffer again
    • Dining Philosophers

Examples

• Using an atomic Test-and-Set operation

  boolean TestAndSet(boolean *target) {
     boolean orig_val = *target;
     *target = TRUE;
     return orig_val;
  }
  

  • Simple mutual exclusion:
    • Shared data

      boolean lock = false;
      

    • Process P_i

      while (1) {
        while (TestAndSet(&lock));  /* busy wait */
      
          /* critical section */
      
        lock = false;
      
          /* non-critical section */
      }
      

  • Adding in bounded waiting:
    • Shared data

      boolean lock=false;
      boolean waiting[n];  /* all initialized to false */
      

    • Process P_i and its local data

      int j;
      boolean key;
      
      while (1) {
        waiting[i]=true;
        key=true;
        while (waiting[i] && key)
          key = TestAndSet(&lock);
        waiting[i]=false;
      
          /* critical section */
      
        j=(i+1)%n;
        while ((j!=i) && !waiting[j])
          j=(j+1)%n;
        if (j==i) lock=false;
        else waiting[j]=false;
      
          /* non-critical section */
      
      }
      

• Critical section using semaphores
  • Shared data

    semaphore mutex=1;
    

  • Process P_i

    while (1) {
      wait(mutex);
    
        /* critical section */
    
      signal(mutex);
    
       /* non-critical section */
    }
    

• prodcons-pthreads-counter-sem
• prodcons-pthreads-counter-mutex
• Bounded Buffer using semaphores
  • Shared data:

    semaphore fullslots, emptyslots, mutex;
    full=0; empty=n; mutex=1;
    

  • Producer process:

    while (1) {
      produce item;
      wait(emptyslots);
      wait(mutex);
      add item to buffer;
      signal(mutex);
      signal(fullslots);
    }
    

  • Consumer process:

    while (1) {
      wait(fullslots);
      wait(mutex);
      remove item from buffer;
      signal(mutex);
      signal(emptyslots);
      consume item;
    }
    

  mutex provides mutual exclusion for the modification of the buffer (not shown in detail). The others make sure that the consumer doesn't try to remove from an empty buffer (fullslots is > 0) or that the producer doesn't try to add to a full buffer (emptyslots is > 0).

• Dining Philosophers

  See examples on the next lecture's page.