- Forward


Semaphores for Solving Coordination Problems
Involving Multiple Processes


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review
Back Forward
  • 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
Back Forward
  • 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
Back Forward
unixexamples/semaphores/rendezvous.c
 
A "Too Strict" Rendezous Protocol
Back Forward
unixexamples/semaphores/rendezvous_toostrict.c
 

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

Producer-Consumer Problems
Back Forward
  • 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.)
Back Forward
Basic Behavior

Producers

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

Consumers

product = get_next(warehouse); use(product);
Producer-Consumer Problems (cont.)
Back Forward
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.)
Back Forward
  • 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
      Expand
Producer-Consumer Problems (cont.)
Back Forward
  • Another Question:
    • Are the producer and consumer protocols symmetric?
  • An Answer:
    • No
      Expand
Producer-Consumer Problems (cont.)
Back Forward
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.)
Back Forward
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
Back Forward
  • 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.)
Back Forward
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.)
Back Forward
  • 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
There's Always More to Learn
Back -