CAOS 02

We're now going to talk about a Process Synchronization tool known as Semaphores and how it relates to Deadlocks. The previous solutions require something known as the Busy Waiting, which means to continuously loop on a while() loop while the condition is not met. Even though it works, it is extremely processor-inefficient.
Another method is to allow the processes to share a common Semaphore struct. This Semaphore struct is defined as such:
typedef struct
{
int value;
struct process *L;
} semaphore;

In this case, each Semaphore has a value, typically representing the number of items in a List (representing a Queue) depending on its negative magnitude, and a list of processes.

The Semaphores can be modified only through two atomic operations: wait(semaphore S) and signal (semaphore S). These are the two functions:
void wait (semaphore S, process P)
{
S.value--;
if (S.value < 0)
{
S.L.add(P);
block(P);
}
}

void signal (semaphore S)
{
S.value++;
if (S.value <= 0)
{
P = S.L.remove();
wakeup(P);
}
}

Think of L as a stack and P is a process's PCB0. Think of "value" as whether there is Mutual Exclusion. When wait() is called and "value" is 1, the process can proceed after changing the value to 0. If a value is 0 or less, then the process will go into Waiting state through block(), add itself into the L stack associated with the Semaphore, and it will add its count into the value. This is called when a process wants to enter critical section (if you recall, it means that it's a Entry Section operation).

signal() simply allows a previously waiting program to be popped from the stack and be put into the Ready Queue. It is typically called after a process completes its Critical Section (it is a Exit Section operation).

The Achilles' Heel of Semaphores is also the existence of a condition that may cause indefinite waiting. Let us look at two processes, P0 and P1, which require two resources to complete an operation. These resources are represented by Semaphores S0 and S1.

The processes look like this:

P0          P1
wait(S0);   wait(S1);
wait(S1);   wait(S0);
signal(S0); signal(S1);
signal(S1); signal(S0);

In this case, P0 and P1 both execute wait(S0) and wait(S1) respectively, so the Semaphore's values would both change to 0. They both then execute wait(S1) and wait(S0). Because the Semaphores have a value of 0 at this point, both processes are blocked indefinitely.

If this sounds like a familiar problem, you may recall something like this in Algorithm 2 in the previous post. This is known as a Deadlock! A Deadlock is said to occur when every process in the set is waiting for an event that can only be caused by another process in the set. In this case, that process is the "signal" process. According to the textbook, the main cause of Deadlocks are "Resource Acquisition and Release" (though other events cause that too).

Starvation, or Indefinite Blocking, is when a process is never removed from the queue in which it is suspended. This can be caused when the programs are removed in a LIFO order.

We now deal with Semaphores which values can only be 0 or 1. This type of Semaphores are known as Binary Semaphores.

As you may recall in the previous Article, we spoke of a "fish" variable that was incremented or decremented by two processes. This is actually an Unbounded-Buffer Producer/Consumer problem, where P0 is the producer and P1 is the consumer. In the Producer/Consumer problem, a Producer produces data, such as a program producing characters to print, and a Consumer consumes data, such as a printer driver removing the characters and printing it. Unbounded-Buffer simply means that there exists no limits on how much data space is available for the Producer to produce.

We now look at the Bounded-Buffer problem, where there exists a cap on how much a producer can produce at one time. In this case, the producer must check to see if a buffer is empty. If it's empty, it will produce. If not, it will skip.

The same applies the other way round. The consumer checks to see if a buffer is full. If it's full, it will consume. If not, it will skip.

We can implement this by having three different Semaphores at work. An empty (init 1) semaphore, a full semaphore (init 0), and a mutex semaphore (init 1).

The Producer can then be implemented as such:
do
{
wait(empty);
wait(mutex);
//Write to buffer
criticalSection();
signal(mutex);
signal(full);
} while (1);

Similarly, the Consumer can be implemented as such:
do
{
wait(full);
wait(mutex);
//Read from buffer
criticalSection();
signal(mutex);
signal(empty);
} while (1);

We also look at another problem related to file reading and writing known as the Readers-Writers problem. If multiple readers read a file, there exists no adverse effects. However, if any reader or writer attempts to access a file while it's being written, it will have adverse consequences.

There are two basic ways to approach this problem. One is to give priority to readers (it may not be written while there is at least 1 reader), while one is to give priority to writers (writers are allowed to write as soon as possible).

The solution to the first process is as follows.

We have two semaphores, mutex (init 1) and wrt (init 1) and a readCount counter that counts the number of readers.

In this case, we have a simple Writer process:
do
{
wait(wrt);
criticalSection();
signal(wrt);
} while(1);

On the other hand, we have a complex Reader process:
do
{
//Mutual Exclusion for readCount variable
wait(mutex);
//Add itself to the number of readers
readCount++;
//If it is the first reader
if (readCount == 1)
{
//Restrict the writer from writing
wait(wrt);
}
signal(mutex);
read();
//Mutual Exclusion for readCount variable
wait(mutex);
//Subtract itself from the number of readers
readCount--;
//If it is the last reader
if (readCount==0)
{
//The writer may now write
signal(wrt);
}
signal(mutex);
} while (1);