Computer Science 432 Operating Systems Williams College Fall 2006

Agenda

• Announcements
  • The Mac labs will be down for maintenence Friday 2-4 PM. Hopefully this will not affect many of you.
  • CS Colloquium this week: more students talk about their work experiences from the summer. Snacks before the talk in the lounge upstairs, talks start at 2:35 Friday here in TCL 206.
• Cooperating Processes
  • Bounded buffer problem
  • Race conditions
  • The critical section problem
    • Requirements: mutual exclusion, progress, bounded waiting
    • 2-process algorithms
    • n-process algorithms

Lecture Assignment

Due at the start of class, Tuesday, October 3.

SG&G 6.1

Please turn in a hard copy (typeset or handwritten are OK). We will discuss Dekker's algorithm and how it solves the critical-section problem during class, so no late submissions are accepted.

The readings for next time are SG&G Sections 6.4-6.6.

Examples

• Modification of a singly-linked list

  struct node { 
    ...
    struct node *next;
  }
  
  struct node *head, *tail;
  
  void insert(val) {
    struct node *newnode;
  
    newnode = getnode();
    newnode->next = NULL;
    if (head == NULL){
       head = tail = newnode;
     } else {     //  <==== THE  WRONG PLACE 
       tail->next = newnode;
       tail = newnode;
     }
  }
  
  void remove() {  
    // ... code to remove value ...
    head = head->next;
    if (head == NULL) tail = NULL;
    return (value);
  }
  

  If the process executing insert is interrupted at "the wrong place" and then another process calls remove until the list is empty, when the insert process resumes, it will be operating on invalid assumptions and the list will be corrupted.
• Critical Section Algorithm 1
  • Shared data

    int turn=0;
    

  • Process P_i (define j=1-i, the other process)

    while (1) {
      while (turn!=i); /* busy wait */
    
        /* critical section */
    
      turn=j;
    
        /* non-critical section */
    
    }
    

• Critical Section Algorithm 2
  • Shared data

    boolean flag[2];
    flag[0]=false;
    flag[1]=false;
    

  • Process P_i

    while (1) {
      flag[i]=true;
      while (flag[j]);
    
        /* critical section */
    
      flag[i]=false;
    
        /* non-critical section */
    
    }
    

  flag[i] set to true means that P_i is requsting access to the critical section.
• Critical Section Algorithm 3 Known as Peterson's Algorithm.
  • Shared data

    int turn=0;
    boolean flag[2];
    flag[0]=false;
    flag[1]=false;
    

  • Process P_i

    while (1) {
      flag[i]=true;
      turn=j;
      while (flag[j] && turn==j);
    
        /* critical section */
    
      flag[i]=false;
    
        /* non-critical section */
    
    }
    

  So, we first indicate interest. Then we set turn=j;, effectively saying "no, you first" to the other process. Even if both processes are interested and both get to the while loop at the "same" time, only one can proceed. Whoever set turn first gets to go first.
• Peterson's Algorithm in Bounded Buffer: prodcons-pthreads/prodcons-pthreads-counter-cs.c
• Bakery Algorithm
  • [Seinfeld episode: The Dinner Party]
  Notation used below: an ordered pair (number, pid) fully identifies a process' number. We define a lexicographic order of these:
  • (a,b) < (c,d) is a < c or if a = c and b < d
  The algorithm:
  • Shared data, initialized to 0's and false

    boolean choosing[n];
    int number[n];
    

  • Process P_i

    while (1) {
      choosing[i]=true;
      number[i]=max(number[0],number[i],...,number[n-1])+1;
      choosing[i]=false;
      for (j=0; j<n; j++) {
        while (choosing[j]);
        while ((number[j]!=0) &&
               ((number[j],j) < (number[i],i)));
      }
    
        /* critical section */
    
      number[i]=0;
    
        /* non-critical section */
    
    }