Semaphore Examples
Andrews Chapter 4

Protecting a critical region:

sem mutex =1;
process CS[i = 1 to n] {
  while (true) {
    P(mutex);
    critical region;
    V(mutex);
    noncritical region;
   }
}

Implementing a 2-process barrier:

• Neither process can pass the barrier until both have arrived.
• Must be able continuously reuse the barrier; therefore it must reinitialize after letting processes pass the barrier.
• This will require two semaphores: a signaling semaphore for each of arrival and departure.
• Each process x signals its arrival using a V(arrivex) and then waits on the other process' (y) semaphore with a P(arrivey);

sem arrive1 = 0, arrive2 = 0;
process Worker1 {
  ...
  V(arrive1);  /*signal arrival */
  P(arrive2);  /*await arrival of other process */
  ...
}
process Worker2 {
  ...
  V(arrive2);
  P(arrive1);
  ..
}

Implementing a simple producer/consumer problem:

• Use a single shared buffer
• Only one process (producer or consumer) can be reading or writing the buffer at one time
• Producers put things in the buffer with a deposit
• Consumers take things out of the buffer with a fetch
• Need two semaphores:
• empty will keep track of whether the buffer is empty
• full will keep track of whether the buffer is full

typeT buf;  /* a buffer of some type */
sem empty =1; /*initially buffer is empty */
sem full = 0;  /*initially buffer is not full */

process Producer [i = 1 to m] {
  while (true) {
    ...
    /*produce data, then depositi it in the buffer */
    P(empty);
buf = data;
    V(full);
  }
}
process Consumer [j=1 to n] {
  while (true) {
    P(full);
    result = buf;
    V(empty);
    ...
  }
}

Bounded Buffers: Resource Counting

• Several messages can be queued between a producer and an consumer. For example, in streaming pages from a web server to a client, you do not want the server to send the pages to the client too fast, or the data will become intermixed and thus scrambled.
• Instead of just a binary semaphore to keep track of whether the single buffer is full or empty, we need counting semaphores to keep track of how many buffers are full and how many are empty. Thus, if none of the buffers contain data, the "full" semaphore will be "0" and a P(full) will stop a consumer from trying to fetch message. Likewise, a P(empty) will stop a producer if there are not empty buffers.

typeT buf[n];  /*an array to hold the queue of messages*/
int front =0, rear =0-;
sem empty =n, full = 0; /*n -2 <= empty+full <= n*/

process Producer {
  while (true) {
    ...
    /*produce message data and deposit it in the buffer;*/
    P(empty);
buf[rear] = data; rear = (rear+1)%n;
    V(full);
  }
}

process Consumer {
  while (true) {
    /*fetch message result and consume it */
    P(full);
    result = buf[front]; front = (front + 1)%n;
   V(empty);
    ...
  }
}

Implementing Multiple Producers and Consumers

• Since multiple producers can access deposit at the same time and multiple consumers can access fetch at the same time, we must make them critical regions

typeT buf[n]  /* an array of data*/
int front =0, rear =0;
sem empty = n, full =0;
sem mutexD =1, mutexF =1; /* semaphores for mutual exclusion*/

process Producer [i= 1 to M] {
  while (true) {
    ...
    /* produce message and deposit it in the buffer */
    P(empty);
    P(mutexD);
buf[rear] = data; rear = (rear +1) %n;
    V(mutexD);
    V(full);
  }
}

process Consumer [i = 1 to N] {
  while (true) {
    ...
    /*fetch message and consumer it */
    P(full);
    P(mutexF);
    result = buf[front]; front = (front+1) % n;
    V(mutexF);
    V(empty);
    ...
  }
}