IPC2

IPC and Synchronization, Part II

Reading

Intro

We saw in the previous section that concurrency in processes and threads, with shared access to resources, can lead to problems. Contention for access to resources can even create a race condition, undermining program correctness.

Early solutions to these problems involved either hardware (special machine instructions, disabling interrupts), software (alternation, lock variables, Peterson's approach), or some combination. They all suffered from one of these important problems: In the following sections, we review semaphores a programming construct that provides correct and efficient solutions to concurrency.

As noted previously, the examples apply equally to processes and threads. The only difference is that processes must share resources explicitly, whereas threads share resources by default. The code and constructs for managing concurrency are essentially the same.

Afterwards, we'll consider some "classical" problems in concurrency that illustrate important challenges.

Semaphores

Introduction

The alternative to busy waiting is to put a process into the blocked state instead, "waking it up" when the resource is available for it to use (or the I/O is available to consume, etc.). The concept of the semaphore was introduced in 1965 by Edsger Dijkstra, who contributed so much to Computer Science theory. Note: Although concurrency primitives are described here as being used by processes that share resources, the same discussion apples equally to threads that share resources, as always.

Operation. A semaphore is nothing more than a non-negative integer that is used to track access to a resource (or multiple identical instances of a resource), in coordination with (and enforced by) the OS. It operates as follows:

Terminology. There are different terms used for describing the function calls that operate on semaphores: They all mean the same thing. For clarity, we will use the terms semWait() and semSignal() in our notes and examples.

Summary of semaphore operations. Given a semaphore s:
Example of use. Using semaphores to implement a solution to the critical section problem is done as follows:
semaphore s = 1;  /* shared globally */

/* each process or thread has code like this*/
while (true) {  
  
  semWait(s);

  /* critical section */

  semSignal(s);

  /* remainder */

}
As noted above, it is critical that the operations semWait() and semSignal() execute atomically, however they are implemented. This is typically ensured by implementing semaphores in the OS kernel or by using assembly code that leverages instructions like XCHG or TSL, mentioned previously.

Semaphore Types

The type of semaphore we have described is sometimes called a counting semaphore, because the value can be thought of as a "count of the number of resource instances currently available." A positive number means resources available, zero means none available. (Sometimes as an implementation optimization, negative numbers are used to represent the number of processes or threads that are actually blocked waiting for the resource.)

The counting semaphore is a generalization of the binary semaphore, which works the same but has a value of only 0 or 1. A binary semaphore is essentially a lock on a single resource instance, like a critical section. It can be locked by one process, and unlocked by another process. However, it can be shown that any implementation using counting semaphores can also be implemented using just binary semaphores (although it would be more complicated and take more of them).

Producer-Consumer Using Semaphores

The "bounded buffer" producer-consumer problem is a classic problem in Computer Science, because it occurs so frequently in real applications.
A bounded buffer.
Rules. There are three important considerations:
Solution.

A correct solution is shown in the following code snippet. Full working example: Code.
const int buffer_size = /* size */;
semaphore s=1, n=0, e=buffer_size;
// s: semaphore to ensure mutually exclusive access to buffer
// e: number of empty buffer spaces
// n: number of items in buffer 

void producer()
{
  while (true) {
    produce();    /* Get an item from somewhere */
    semWait(e);   /* Wait for empty spaces to exist */
    semWait(s);   /* Wait for buffer access */
    append();     /* Place item in buffer */
    semSignal(s); /* Release buffer */
    semSignal(n); /* Increment number of full spaces */
  }
}

void consumer()
{
  while (true) {
    semWait(n);   /* Wait for full spaces to exist */
    semWait(s);   /* Wait for buffer access */
    take();       /* Remove item */
    semSignal(s); /* Release buffer */
    semSignal(e); /* Increment number of empty spaces */
    consume();    /* Place item elsewhere */
  }
}
So, problem solved, right? We have illustrated that semaphores can correctly provide mutual exclusion over a shared resource, without busy waiting. Great. Consider, though, if we had reversed the order of the two semWait() statements at the start of the producer code, as in:
semWait(s);    /* Wait for buffer access  */
semWait(e);    /* Wait for empty spaces to exist */
Suppose a producer thread is scheduled to run on a full buffer which is currently not being accessed. As a result, no other thread may access the buffer! Hence, no consumer threads can remove items from the buffer, so it will never be free. This results in a deadlock, a condition we will discuss in more detail later.

By exchanging the order of just two instructions, the code no longer works! Unfortunately, subtle errors of this kind are very easy to make and not always easy to detect. This helps illustrate the principal challenges of semaphores:

The Dining Philosophers

Originally proposed by Edsger Dijkstra in 1965, the Dining Philosophers problem is the classical example for illustrating concurrency primitives in action. The problem description is as follows:
Dining Philosophers Setup.
The straightforward solution, which doesn't work, is as follows:
semaphore fork[5] = {1};
void philosopher(int i)
{
    while (true) {
        think();
        semWait(fork[i]);           /* Left fork */
        semWait(fork[(i+1) % 5]);   /* Right fork */
        eat();              
        semSignal(fork[(i+1) % 5]); /* Right fork */
        semSignal(fork[i]);         /* Left fork */
    }
}
This approach seems correct. However, what happens if all philosophers, in parallel, pick up their left forks at the same time? Now they all will be waiting on a right fork, but will never get it! Deadlock!

There are small modifications we could make to reduce the odds of this deadlock happening. For example, after grabbing the left fork, we could have each philosopher first check if the right for is available and, if not, put his left fork back down and wait a while. This will probably help, but does not guarantee that the philosophers will endlessly repeat the same sequence of all grabbing a left fork at the same time.

Another modification to improve our chances would be to have each philosopher wait a random amount of time before trying again. This, too, would make things better, on average. However, it does not always guarantee mutual exclusion, because correct operation is dependent on randomness and on the relative speed of execution of each philosopher thread.

There are a number of correct solutions to the problem. An easy solution with semaphores is to limit the number of philosophers in the room at any time to four, as in adding a room attendant. As long as there are four or fewer philosophers at the table, there will always be enough available forks so that at least one philosopher will be able to eat. This solution, with semaphores, looks like this:
semaphore fork[5] = {1};
semaphore room = {4};
int i;
void philosopher(int i)
{
    while (true) {
        think();
        semWait(room);
        semWait(fork[i]);           /* Left fork */
        semWait(fork[(i+1) % 5]);   /* Right fork */
        eat();              
        semSignal(fork[(i+1) % 5]); /* Right fork */
        semSignal(fork[i]);         /* Left fork */
        semSignal(room);
    }
}


The Tanenbaum text also shows a solution (fig. 2-47) that lets philosophers atomically pick up either two forks, if both are available, or none at all. Below, we'll show a simpler version that uses a single mutex to ensure that only one philosopher can be attempting to pick up forks at a time. While doing so, if they fail to get both forks, they'll release the forks and try again. Unlike the "put a fork down and wait a while" solution, this solution is guaranteed to eventually make progress because one of the following must be true right after the mutex is acquired: (a) some philosopher is holding both forks, and will eventually finish eating and put down more forks, OR (b) all the forks are available, and so the philosopher that just acquired the mutex will succeed in grabbing both of the forks that it needs. Here's some rough code:

semaphore fork[5] = {1};
semaphore mutex = {1};

void philosopher(int i)
{
    int left  = i;
    int right = (i+1) % 5; 
  
    while (true) {
        think();
        while (true) {   // loop until acquire both forks
          bool success = false;
          semWait(mutex);
          if (fork[left] && fork[right]) {
              semWait(fork[left ]);
              semWait(fork[right]);
              success = true;
            }
          semSignal(mutex);
          if (success) break;
        }
            
        eat();
        
        semWait(mutex);        
        semSignal(fork[left ]);
        semSignal(fork[right]);
        semWait(mutex);
    }
}


Make sure you understand how the "room semaphore" solution differs from the "fork-grabbing mutex" solution, and why the latter needs a loop for acquiring forks.

Readers and Writers

Another "classical" concurrency problem, because it comes up so often in practice, is Readers and Writers. There may be multiple reader threads and writer threads performing operations on one shared object, such as a database or other large file. The Readers-Writers problem can be solved using semaphores, "monitors" (see Tanenbaum), or message passing. Also, the solution can be tuned for one of the following cases: The general rules are:

Reader Priority

In this example: The drawback of this implementation is that writer starvation is possible. As long as there are readers reading and more readers willing to read, they will have priority over any waiting writers. There is no guarantee that a writer thread will ever get to write.

Variables: Code: full example code for Reader Priority with semaphores: Code
int readcount;
semaphore x=1, wsem=1;

void reader()
{
    while (true) {
        semWait(x);
        readcount++;
        if (readcount == 1) 
            semWait(wsem);      /* first reader must ensure no writers */   
        semSignal(x);           /* Additional readers don't wait */

        readunit();

        semWait(x);
        readcount--;
        if (readcount == 0)     /* Only way writing will be enabled... */
            semSignal(wsem);    /* ...is after readcount gets to 0 */
        semSignal(x);
    }
}
void writer()
{
    while (true) {
        semWait(wsem);
        writeunit();
        semSignal(wsem);
}
Readers-Writers with semaphores. Reader priority.

Writer Priority

Now let's examine how the solution might look with writer priority, using semaphores. This solution is a bit more complicated, and requires additional semaphores: Code: full example code for Writer Priority with semaphores: Code
int readcount, writecount; 
semaphore x=1, y=1, z=1, wsem=1, rsem=1

void reader()
{
    while (true) {
        /* z queues additional readers...*/
        semWait(z);     
        /* but 1st reader queues on rsem */
        semWait(rsem);  
        semWait(x);
        readcount++;
        if (readcount == 1) 
            semWait(wsem);  
        semSignal(x);       
        semSignal(rsem);
        semSignal(z);

        readunit();

        semWait(x);
        readcount--;
        /* Writing will only be enabled... */
        if (readcount == 0)     
            /* ...after readcount gets to 0 */
            semSignal(wsem);    
        semSignal(x);
    }
}
Readers-Writers with semaphores. Writer priority.
int readcount, writecount; 
semaphore x=1, y=1, z=1, wsem=1, rsem=1

void writer()
{
    while (true) {
        semWait(y);
        writecount++;
        if (writecount == 1)
            semWait(rsem);          
        semSignal(y);   
        semWait(wsem);

        writeunit();

        semSignal(wsem);
        semWait(y);
        writecount--;
        /* Reading will only be enabled... */
        if (writecount == 0)    
            /* ...after writecount gets to 0 */
            semSignal(rsem);    
        semSignal(y);
    }
}





Readers-Writers with semaphores. Writer priority.

How is writer priority established? In essence, no new readers are allowed access to the data area once at least one writer has declared a desire to write.

Summary / Key Points