Agenda

• Announcements
  • As I mentioned in the e-mail last week, Lab 3 is not due today. It is due on Thursday.
  • Bounded buffer pseudocode that we looked at in class last time is on the lecture 6 web page.
• Cooperating Processes
  • Bounded buffer problem
  • Race conditions
  • The critical section problem
    • Requirements: mutual exclusion, progress, bounded waiting
    • 2-process algorithms
    • n-process algorithms

Examples

• One-lane bridges in Williamstown:

  

• 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;
    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

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