Semaphores for Solving Coordination Problems

Semaphores for Solving Coordination Problems
Involving Multiple Processes

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Review

Definition:
- A semaphore is a kernel-maintained non-negative integer that can be operated on by processes using system calls
Operations:
- Setting the value
- Increasing the value by 1
- Blocking until the value can be decreased by 1

Using Semaphores for Two-Party Rendezvous Problems

Recall:
- There are two parties, Andrea and Bill, each of whom performs two tasks in order, \((A1, A2)\) for Andrea and \((B1, B2)\) for Bill
- The protocol must ensure that \(A1\) happens before \(B2\) and \(B1\) happens before \(A2\)
Using Semaphores:
- Use one semaphore for the status of \(A1\) and one semaphore for the status of \(B1\)

Semaphores for Two-Party Rendezous

unixexamples/semaphores/rendezvous.c

        #include <fcntl.h>       // For O_CREAT
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int
main(void)
{
  sem_t *completed_a1, *completed_b1;

  // Call open() in the original process so that we don't have to
  // worry about coordinating the call to open() 
  completed_a1 = sem_open("/completed_a1", O_CREAT, O_RDWR, 0);
  completed_b1 = sem_open("/completed_b1", O_CREAT, O_RDWR, 0);
  
  pid_t  pid = fork();
  switch(pid)
    {
    case -1:
      exit(1);

    case 0:  // Child
      write(STDOUT_FILENO, "Task A1\n", 8);
      sem_post(completed_a1);    // Increment the semaphore
      sem_wait(completed_b1);    // Try to decrement the semaphore
      write(STDOUT_FILENO, "Task A2\n", 8);

      sem_close(completed_a1);
      sem_close(completed_b1);
      sem_unlink("/completed_a1");
      exit(0);

    default: // Parent
      write(STDOUT_FILENO, "Task B1\n", 8);
      sem_post(completed_b1);    // Increment the semaphore
      sem_wait(completed_a1);    // Try to decrement the semaphore
      write(STDOUT_FILENO, "Task B2\n", 8);

      sem_close(completed_a1);
      sem_close(completed_b1);
      sem_unlink("/completed_b1");
      write(STDOUT_FILENO, "\nCheck: ls -l /dev/shm/sem.* \n", 30);
      exit(0);
    }
}

A "Too Strict" Rendezous Protocol

unixexamples/semaphores/rendezvous_toostrict.c

        #include <fcntl.h>       // For O_CREAT
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int
main(void)
{
  sem_t *completed_a1, *completed_b1;

  // Call open() in the original process so that we don't have to
  // worry about coordinating the call to open() 
  completed_a1 = sem_open("/completed_a1", O_CREAT, O_RDWR, 0);
  completed_b1 = sem_open("/completed_b1", O_CREAT, O_RDWR, 0);
  
  pid_t  pid = fork();
  switch(pid)
    {
    case -1:
      exit(1);

    case 0:  // Child
      write(STDOUT_FILENO, "Task A1\n", 8);
      sem_wait(completed_b1);    // Try to decrement the semaphore
      sem_post(completed_a1);    // Increment the semaphore
      write(STDOUT_FILENO, "Task A2\n", 8);

      sem_close(completed_a1);
      sem_close(completed_b1);
      sem_unlink("/completed_a1");
      exit(0);

    default: // Parent
      write(STDOUT_FILENO, "Task B1\n", 8);
      sem_post(completed_b1);    // Increment the semaphore
      sem_wait(completed_a1);    // Try to decrement the semaphore
      write(STDOUT_FILENO, "Task B2\n", 8);

      sem_close(completed_a1);
      sem_close(completed_b1);
      sem_unlink("/completed_b1");
      write(STDOUT_FILENO, "\nCheck: ls -l /dev/shm/sem.* \n", 30);
      exit(0);
    }
}

Note: With this protocol B1 will always be completed before A1 (which is not required).

Producer-Consumer Problems

Participants:
- Producers create products and add them to a warehouse
- Consumers retrieve products from the warehouse and use them
Coordination:
- Access to the warehouse must be mutually exclusive
- Consumers must block when the warehouse is empty

Producer-Consumer Problems (cont.)

Basic Behavior

Producers

  product = produce();
  add(product, warehouse);

Consumers

  product = get_next(warehouse);
  use(product);

Producer-Consumer Problems (cont.)

Coordinated Behavior

Semaphores

  sem_t *key = sem_open("/key", O_CREAT, ORDWR, 1);

  sem_t *available = sem_open("/available", O_CREAT, ORDWR, 0);

Producers

  product = produce();

  sem_wait(key);       // Wait for the key to the warehouse
  add(product, warehouse);
  sem_post(key);       // Release the key to the warehouse

  sem_post(available); // Indicate that a product is available

Consumers

  sem_wait(available); // Wait until a product is available

  sem_wait(key);       // Wait until the key to the warehouse is available
  product = get_next(warehouse);
  sem_post(key);       // Release the key to the warehouse

  use(product);

Producer-Consumer Problems (cont.)

A Question:
- What happens if, in between a consumer's call to sem_wait(available) and sem_wait(key), another process gets access to the warehouse and there is only a single product in the warehouse?
An Answer:
- The other process can't be a consumer because all other consumers are blocking on available

Producer-Consumer Problems (cont.)

Another Question:
- Are the producer and consumer protocols symmetric?
An Answer:
- No

Producer-Consumer Problems (cont.)

Two Producer Protocols

The Better Producer Protocol

  product = produce();

  sem_wait(key);         // Wait until the key is available
  add(product, warehouse);
  sem_post(key);         // Release the key

  sem_post(available);   // Indicate that a product is available

The Worse Producer Protocol

  product = produce();

  sem_wait(key);         // Wait until the key is available
  add(product, warehouse);
  sem_post(available);   // Indicate that a product is available
  sem_post(key);         // Release the key

Note: This protocol is worse because a consumer may stop waiting on available product before it can get the key (i.e., be unblocked and then immediately blocked again).

Producer-Consumer Problems (cont.)

Two Consumer Protocols

The Correct Consumer Protocol

  sem_wait(available);   // Wait until a product is available

  sem_wait(key);         // Wait until the key is available
  product = get_next(warehouse);
  sem_post(key);         // Release the key

  use(product);

A Consumer Protocol that is not Deadlock-Free


  sem_wait(key);         // Wait until the key is available
  sem_wait(available);   // Wait until a product is available
  product = get_next(warehouse);
  sem_post(key);         // Release the key to the warehouse

  use(product);

A consumer can get the key when no product is available and, since the key is no longer available, no producer will be able to add one.

Reader-Writer Problems

Participants:
- Writers add to or modify a data structure/database/file
- Readers read from a data structure/database/file
Coordination Constraints:
- Writers must have exclusive access to the critical section

Readers-Writers Problems (cont.)

Coordinated Behavior

Semaphores and Shared Variables

  sem_t *updateable = sem_open("/updateable", O_CREAT, ORDWR, 1);
  sem_t *key = sem_open("/key", O_CREAT, ORDWR, 1);
  int    readers = 0;

Writers

  sem_wait(key);    // Wait for the key

  // Critical section for writers

  sem_post(key);    // Release the key

Readers

  sem_wait(updateable);   // Wait until reader info can be updated
  readers++;
  if (readers == 1) sem_wait(key); // First in gets the key
  sem_post(updateable);   // Allow other readers to update info

  // Critical section for readers

  sem_wait(updateable);  // Wait until the reader info can be updated
  readers--;
  if (readers == 0) sem_post(key); // Last out releases the key
  sem_post(updateable);  // Allow other readers to update info

Readers-Writers Problems (cont.)

An Interesting Pattern:
- The first-in locks and last-out unlocks pattern arises in many coordination protocols
Starvation:
- With this protocol a writer can starve while readers come and go if it arrives when there are readers in the critical section