Review of Concurrency and Process and Thread Synchronization

In the last class, we discussed the problem associated with the situation in which two or more concurrent processes or threads were updating a common resourse, such as a global variable or a record in a database.

Key concepts

• asynchronous - we cannot make any assumptions about timing. While each thread or process will execute its instuctions in order, we cannot make any assumptions about where any other thread (process) will be in its execution.
• Race condition - a situation where two events happen at about the same time, but we cannot assume which one will happen first.
• Atomic operation - an operation which will not be interrupted, an operation which is guaranteed to run to completion.
• Critical section - a section of code in a thread or process which updates a shared resource.

/* Process One */              /* Process Two */
while (TRUE) {                 while (TRUE) {
    NonCriticalSection();          NonCriticalSection();
    CriticalSection();             CriticalSection();
}                              }

Here are the rules:

• Only one process can be in its critical section at a time. This requirement is known as mutual exclusion
• No process that wants to enter its critical section can be blocked indefinitely. In other words, the waiting time must be bounded; once a process requests entry into its critical section, only a bounded number of other processes may enter their critical section before this process is allowed to enter its critical section. The condition in which a process is indefinitely blocked is known as starvation.An extreme version of starvation is known as deadlock in which all processes are blocked.
• A process can terminate in its NonCriticalSection, but we do not allow a process to terminate while it is in its Critical Section.
• In the absence of contention (i.e. no other process is in or wants to enter its critical section) a single process wishing to enter its critical section will succeed, ideally with minimal overhead.

/* Process One */              /* Process Two */
while (TRUE) {                 while (TRUE) {
    NonCriticalSection();          NonCriticalSection();
    PreProtocol();                 PreProtocol();
    CriticalSection();             CriticalSection();
    PostProtocol();                PostProtocol();      
}                              }

/* Dekker's Algorithm */
bool Need1 = false, Need2 = false;
int turn = 1; /* the initial value of turn is arbitrary */
/* Process One */                     /* Process Two */
while (TRUE) {                           while (TRUE) {
    NonCriticalSection();                    NonCriticalSection(); 
    Need1 = true;                            Need2 = true          
    turn = 2;                                turn = 1;
    while (turn == 2 && Need2 == true)       while (turn == 1 && Need1 == true)
       {* do nothing */ }                        { /* do nothing */ }
    CriticalSection();                       CriticalSection();
    Need1 = false;                           Need2 = false;
}                                        }

Semaphores

Modern operating systems provide a set of operations to solve this problem without busywaiting. The earliest of these was a semaphore. A semaphore has two operations, down and up. When the down operation is called, the system checks the value of the semaphore. If it is greater than zero, the value is decremented by one and the process returns. if the value of the semaphore is zero, the process is blocked.

When the up operation is called, the value of the semaphore is incremented, and if one or more processes are waiting on the semaphore, they are signaled.

Both down and up have to be implemented as atomic operations, so they are in the kernel.

Here is pseudocode for the semaphore operation. All processes are identical, so only one is shown

Semaphore S=1;
while (true) {
    NonCriticalSection();
    Down(S);
    CriticalSection();
    Up(S);
}

Mutexes

A simple version of a semaphore with only two states is called a mutex which is short for mutual exclusion. A mutex is a simple lock primitive which can be used to guard a shared resource such as a critical section to ensure that only one process or thread at a time is using the resource. A mutex only has two states, locked and unlocked. Like a semaphore, a process which tries to access its critical section but finds that the mutex is locked is typically blocked so that it does not use CPU cycles. When the mutex is unlocked, the blocked process or thread is awakened and allowed to enter its critical section after the mutex is relocked.

mutex M;
while (true)
{
     NonCriticalSection();
     M.lock();
     CriticalSection();
     M.unlock();
}

Monitors

A monitor is a synchronization abstraction; it is like a class which enforces mutual exclusion; in particular it enforces the fact that only one process can be executing a particular procedure at a particular time. As with any abstract data type, other processes must rely on the defined interface, they cannot manipulate data inside the monitor directly.

One feature of monitors is a condition variable, a boolean variable with a queue attached. If a process (thread) wants to do something, it checks the condition variable, and if it is true (or false, depending on the condition), the process is blocked and is put on the queue.

Here is an example (from Nutt, Operating Systems, a modern perspective) A north-south two way road has a one-way tunnel. A southbound (or northbound) car which arrives at the tunnel can enter immediately if there are no cars in the tunnel going the opposite way. Traffic is controlled with a traffic light.

The monitor has three functions, northboundArrival() which is called when a northbound car is approaching the tunnel, southboundArrival(), which is called when a southbound car approaches the tunnel, and depart which is called when a car leaves the tunnel. All three of these are triggered by sensors in the road.

Note the use of the condition variable busy

Here is the code for the monitor

monitor tunnel {
    int northbound = 0, southbound = 0;
    traffic-signal northbound_signal = RED.
                   southbound_signal = RED;
    condition busy;
public:
    northboundArrival() {
        if (southbound > 0) busy.wait;
        northbound++;
        northbound_signal = GREEN;
        southbound_signal = RED;
    };
    southboundArrival() {
        if (northbound > 0) busy.wait;
        southbound++;
        southbound_signal = GREEN;
        northbound_signal = RED;
    };
    depart(Direction exit) {
        if (exit == north) {
            northbound--;
            if (northbound == 0)
                while(busy.queue) busy.signal;
        }
        else if (exit == south) {
             southbound--;
             if (southbound == 0) 
                 while(busy.queue) busy.signal;
        }
   };
}

No system has a primitive called a monitor; monitors are merely abstractions. Monitors can always be implemented using semaphores.

Posix Thread Synchronization

The Posix thread mechanism (pthreads) provides a simple mutex facility as defined in the previous module. The pthread library defines an opaque data type pthread_mutex_t. An instance of a pthread_mutex_t should be defined globally and initialized when it is declared with the macro PTHREAD_MUTEX_INITIALIZER. There are three system calls which perform operations on a mutex, each of which takes a pointer to a pthread_mutex_t as an argument.

int pthread_mutex_lock(pthread_mutex_t *mutex);

This function checks to see if the mutex is locked. If it is not, it locks the mutex and returns, thus allowing the calling thread to continue. If the mutex is locked, the thread blocks until the mutex becomes unlocked. At this time the mutex is set to the locked state again but the function returns, allowing the thread to continue. This should be called before a thread enters its critical section.

int pthread_mutex_trylock(pthread_mutex_t *mutex);

This is similar to the above function but it always returns immediately. The return value is zero if the mutex had previously been unlocked and the thread has successfully locked the mutex. If the mutex is locked, the function returns a non-zero value.

int pthread_mutex_unlock(pthread_mutex_t *mutex);

This unlocks a locked mutex. This should be called by a thread after it leaves its critical section.

/* pthreadmutex.c - a demo of pthread mutual exclusion */
#include <pthread.h>
#include <stdlib.h> /* for random() */
#include <stdio.h> /* for printf() */
#include <unistd.h> /* for sleep() */

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; /* declare the mutex globally */

void CriticalSection(int num)
{
  printf("Thread %d is in its critical section\n", num);
  sleep(random() % 4);  /* sleep for zero to four seconds */
  printf("Thread %d is leaving its critical section\n", num);
}

void NonCriticalSection(int num)
{
  printf("Thread %d is in its noncritical section\n", num);
  sleep(random() % 4);   /* sleep for zero to four seconds */
  printf("Thread %d is leaving its noncritical section\n", num);
}

void* ThreadController(void *arg)
{
  int *num = (int *)malloc(sizeof(int));
  int i;
  *num = *(int *)arg;
  for (i=0;i < 4;i++) {
    NonCriticalSection(*num);
    pthread_mutex_lock(&mutex);
    CriticalSection(*num);
    pthread_mutex_unlock(&mutex);
  }
  pthread_exit(num);
  return num; /* we never get here */
}

int main()
{
  int i;
  int retval;
  int *arg;
  pthread_t threadid[5];

  for (i=0;i < 5;i++) {  /* create five threads */
    arg = (int *)malloc(sizeof(int));
    *arg = i+1;
    retval = pthread_create(&threadid[i],NULL, ThreadController,arg);
    if (retval != 0) {
      fprintf(stderr,"ERROR creating thread");
    }
    
  } 
  for (i=0;i<5;i++) {
    arg = (int *) malloc(sizeof(int));
    retval = pthread_join(threadid[i],(void **)&arg);
    if (retval == 0)
      printf("Thread %d finished with value %d\n",
	     i, *arg);
    else
      fprintf(stderr,"ERROR on join");
  }
  return 0;
}

Semaphores in Unix

The pthread mutex works well for threads, but synchronization of multiple independent processes as created by fork is more complicated. Semaphores were not a part of the original Unix Operating Systems. They were added later, and the code is pretty ugly. This is a part of the Interprocess Communication (IPC) facility which includes mechanisms for shared memory and message passing in addition to semaphores.

The problem that IPC facilities have to solve is that two or more independent processes have to share a common structure, but it should not be available to just any old process. To obtain access to an IPC facility, the process has to know the key. The key is of type key_t but it is really just an integer. One process creates and initializes the semaphore, and other processes can then access it if they know the key.

The code for using IPC Semaphores is complicated, and, frankly, a little bizarre, and so we will not discuss it further. The interested student can read the Unix man pages for semget, semctl and semop.

Win32 Synchronization System Calls

Unlike Unix, where process synchronization seems to have been added as an afterthought, synchronization of both threads and processes is an inherent feature of the Windows operating systems, and Win32 provide a very rich set of synchronization APIs.

If all that you want to do is to increment, decrement or set a value for a variable which is shared between processes or threads, WIN32 provides the follow functions.

LONG InterlockedIncrement(LPLONG lpAddent);

LONG InterlockedDecrement(LPLONG lpAddend);

LONG InterlockedExchange(LPLONG target, LONG Value);

WIN32 allows independent processes to create and use a mutex in the usual fashion. A mutex has a handle and a name, which is a string. To create a new mutex, use this function

HANDLE CreateMutex(
    LPSECURITY_ATTRIBUTES lpMutexAttributes,
    BOOL bInitialOwner,
    LPCTSTR lpname
);

Two or more processes can call CreateMutex to create the same named mutex. The first process actually creates the mutex and subsequent processes open a handle to the existing mutex.

The equivalent of the mutex lock facility is the API

DWORD WaitForSingleObject(HANDLE hHandle, DWORD dwMilliseconds);

The function which is equivalent to pthread_mutex_unlock is

BOOL ReleaseMutex(HANDLE hMutex);

/* winmutex.c a program using WIN32 mutexes */
#include 
#include 

void CriticalSection(int num)
{
	printf("Thread %d is in its critical section\n",num);
	Sleep((rand()%4) * 1000); 
	printf("Thread %d is leaving its critical section\n",num);
}

void NonCriticalSection(int num)
{
	printf("Thread %d is in its noncritical section\n",num);
	Sleep((rand()%4) * 1000);
	printf("Thread %d is leaving its noncritical section\n",num);
}

DWORD WINAPI ThreadController(LPVOID lpParameter)
{
	int *num = (int *)malloc(sizeof(int));
	int i;
	HANDLE hMutex;

	*num = *(int *)lpParameter;
	hMutex = CreateMutex(NULL,FALSE,"Hello");
	if (hMutex==INVALID_HANDLE_VALUE) {
		printf("Error,could not create the mutex\n");
		return 0;
	}
	for (i=0;i < 4;i++) {
		NonCriticalSection(*num);
        WaitForSingleObject(hMutex,INFINITE);
		CriticalSection(*num);
		ReleaseMutex(hMutex);
	}
	return 0;
}

int main()
{
	int i;
	int *arg;
	HANDLE TheHandles[5];
	DWORD ThreadId;
	for (i=0;i<5;i++) {
		arg = (int *)malloc(sizeof(int));
		*arg = i;
	    TheHandles[i] = CreateThread(NULL,0,ThreadController,arg,0,&ThreadId);
		if (TheHandles[i] == INVALID_HANDLE_VALUE) {
			printf("Error creating the thread %d\n",i);
		}
	}

	for (i=0;i<5;i++)
		WaitForSingleObject(TheHandles[i],INFINITE);
	return 0;
}

Classic Synchronization Problems

There are a number of classic problems that appear in almost all texts on operating systems to illustrate some of the issues associated with synchronization.

The Producer - Consumer (aka Bounded Buffer) Problem

In this situation, there are two classes of processes (or threads). One class produces data of some sort, and the other consumes the data. All processes are running concurrently and asynchronously. When a producer produces some data, it puts it in a buffer. There is a finite number of buffers, and if all of the buffers are full, then the producer is blocked until a buffer becomes available.

The consumers get their data from the buffers. When a consumer is ready to consume more data, it checks to see if there is any unconsumed data in the buffers, and if there is, it consumes the data, thus emptying the buffer. If there is no data waiting to be consumed, the consumers sleep until there is data available.

Typically the data are stored in a circular buffer of size N, i.e. it has N slots for data. We will treat the buffer as a first in first out queue with the two operations Enqueue to insert an item into the buffer and Dequeue to remove an item from the buffer.

The problem is to introduce synchronization to assure that producers do not try to add data to a full buffer or that more than one consumer does not try to consume the same data.

The obvious solution is wrong; it has a fatal race condition.

int count = 0;  /* number of items in the buffer */
void Producer()                      void Consumer()
{                                    {
    data_t item;                         data_t item;
    while (TRUE) {                       while (TRUE) {
       item = ProduceItem();                 if (count == 0) sleep();
       if (count == N) sleep();              item = Dequeue();
       Enqueue(item);                        count--;
       count++;                              if (count == N-1) wakeup(Producer);
       if (count == 1) wakeup(Consumer);     ConsumeItem(item);
   }                                     }
}                                     }

The solution is to have two counting semaphores, labeled full (the number of slots with data in them in the buffer) and empty (the number of empty slots in the buffer) and a mutex to make sure that only one process is accessing the buffer at a time. Recall that a semaphore has two operations, up, which increases its value and down, which decreases its value. These operations are performed atomically. If a semaphore has a value of zero, the down operation blocks until it has a non-zero value.

Here is a solution which works.

Semaphore empty = N;
Semaphore full = 0;
Mutex     M = Unlocked;

void Producer()                       void Consumer()
{                                     {
     data_t item;                          data_t item;
     while (TRUE) {                        while (TRUE) {
        item = ProduceItem();                 down(&full);
        down(&empty);                         lock(&M);
        lock(&M);                             item = Dequeue();
        Enqueue(item);                        unlock(&M);
        unlock(&M);                           up(&empty);
        up(&full);                            ConsumeItem(item);
     }                                     }
}                                     }

The consumer process is symmetrical.

The Readers and Writers Problem

Consider a file of data, such as an airline reservation system which keeps track of the reserved seats on a flight or set of flights. There are travel agents all around the country who can access this file, so there are potential issues of contention. There is no problem if many different agents want to read the file at the same time, but only one agent at a time should be able to write to the file.

Here are the rules that we want to enforce:

• Any number of readers can simultaneously read the file
• Only one writer at a time can write to the file
• If a writer is writing, no reader can read.
• No process will starve, any process that wants to read or write will eventually be allowed to read or write.

Here is the solution from the text, slightly rewritten. We have a global counter ReadCount which keeps track of the number of readers reading. We need two Mutex variables, RCMutex guards ReadCount and DBMutex guards the database.

int ReadCount = 0; /* number of readers reading */
Mutex RCMutex = unlocked, DBMutex = unlocked;

void Reader()
{
    while (true) {
       lock(&RCMutex);     
       ReadCount++;
       if (ReadCount == 1)
          lock(&DBMutex);
       unlock(&RCMutex);
       ReadDataBase();
       lock(&RCMutex);
       ReadCount--;
       if (ReadCount == 0)
          unlock(&DBMutex);
       unlock(&RCMutex);
       DoOtherStuff(); /* noncriticalsection */     
    }
}

void Writer() 
{
   DoOtherStuff();
   lock(&DBMutex);
   WriteDataBase();
   unlock(&DBMutex);
}  

An alternative solution is to give writers priority. If any process is waiting to write to the database, no reader is allowed to read. This solution is also unsatisfactory because it is possible for readers to starve. As long as new writers want to write, no reader ever gets to read.

To solve this problem, if no writer is waiting to write, any reader that wants to read is allowed to read. As soon as a writer wants to write, no new readers are allowed to read. As soon as all of the current readers are through reading, the writer is allowed to write. Once the writer is finished writing, all of the readers that have been blocked are allowed to read.

If multiple writers want to write, it is necessary to enforce alternation between readers and writers to prevent starvation. That is, after a writer has finished writing, all of the readers that have been blocked are allowed to read, but new readers that want to read are not permitted to read if there are writers waiting. Otherwise, the readers could starve.

The Dining Philosophers

Imagine five philosophers sitting at a round table. Philosophers only do two things, they think and they eat. There are five chopsticks on the table, initially located between every two philosophers. In other words, the left chopstick of Philospher One is the right chopstick of Philosopher Two. There is a large platter of food in the middle of the table, and when philosophers get hungry, they pick up their left and right chopsticks, and start to eat. If one of the chopsticks is in use by a neighbor, the philosopher has to wait.

Here is the code for philosopher i

Mutex chopstick[5]; /* global
Philosopher {
    while (true)
    {  
         think();
         lock(&chopstick[i]);
         lock(&chopstick[(i+1)%5]);
         eat();
         unlock(&chopstick[(i+1)%5]);
         unlock(&chopstick[(i)]);
    }
}  

Let's consider several solutions to the problem. First, we change the rules so that unless philosophers can obtain access to both chopsticks, they cannot pick up either one. This solution prevents deadlock, but it still allows an individual philosopher to starve. Suppose that Philospher Two is hungry, but Philosopher Three is eating, so Philosopher Two's left chopstick is not available. He waits for both to become available. Before Philosopher Three finishes eating, Philosopher One starts eating, using Philosopher Two's right chopstick. Now Philosopher Three stops eating and puts down her chopsticks, but Philosopher Two still can't start eating. Before Philosopher One finishes eating, Philosopher Three starts eating again. This can continue indefinitely, allowing Philosopher Two to starve.

One solution which does work is to assign a number to each chopstick, and have a rule that each philosopher has to pick up the lower numbered chopstick first. This means that philosophers one to four pick up their right chopstick, then their left chopstick, but philosopher five picks up his left chopstick before his right chopstick because he is using chopsticks 5 and 1.

Back to course home page