Computer Science 432 Operating Systems Williams College Fall 2006

Agenda

• Announcements
  • CPU Simulator due; new (short) lab out
• Lecture assignment recap: Dekker's Algorithm
• More on hardware support for process synchronization
  • bounded wait using atomic test-and-set
  • using atomic swap instruction
• Semaphores
  • abstract synchronization primitive
  • wait/signal semantics
  • using to solve the critical section problem
  • implementation idea
  • POSIX semaphores
  • pthreads mutexes
  • using as a general synchronization tool
• Classical problems of synchronization
  • back to the bounded buffer, now armed with semaphores
  • the Dining Philosophers
  • Readers-Writers

Lecture Assignment

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

Turn in short answers to these questions. Please turn in a hard copy (typeset or handwritten are OK). We will discuss these questions during class, so no late submissions are accepted.

SG&G 6.3, 6.4

You need not turn in answers to the next two questions, but we will discuss them briefly in class.

SG&G 6.5, 6.6

There are no new readings for next time. At this point, you should be up to Section 6.6 in SG&G.

Examples

• Mutual exclusion using test-and-set, with 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

Links

• http://www.semaphores.com