Processes synchronization

Here I am writing about synchronization of processes in UNIX.

Before discussing about the four types of sync problems we will define some terms used in solving these kind of problems:

• deadlock – situation when 2 processes are waiting for each other, none of them will finish
• starvation – situation when a process access to resources is blocked, meaning that the process will never finish
• CS – critical section (every process has a critical section)
• mutual exclusion (letting only one process to run in it’s CS)
• semaphore – a structure of two types :

1. binary semaphore (for ex: mutex, the semaphore used for mutual exclusion of CS)
2. general semaphore (this is not a binary semaphore, it’s used for counting the allocated resources)

typedef struct {

      int val;
      struct thread listThreads;
}semaphore;

• wait function for the semaphore:

//S is a semaphore struct
wait(S){
S.val --;
 if (S.val < 0){
  add thread to listThread
  suspend();
 }
}

• signal function for the semaphore

signal(S){
     S.val ++;
     if (S.val == 1){
       remove thread from listThread
       resume(T); //T is a thread
     }
}

The four types of sync problems are :

1. Product – Consumer Scenario
2. CREW (Writers and Readers)
3. Dining Philosophers (Edsger Dijkstra)
4. Sleeping barber problem (Edsger Dijkstra)

1. Product – Consumer

Scenario: A process (Producer) adds some data to a buffer from where another process (Consumer) will retrieve the data.

There are 2 kind of situations:

• with unlimited buffer
• with limited buffer

a) Product – Consumer with unlimited buffer

the objects used are:

•  a binary semaphore : mutex (used for the mutual exclusion, allows only one process to run in CS)
•  an integer n : counting the elements in the buffer
•  a binary semaphore delay (used to show if the buffer is empty or not)

the structure of a product looks like this:

produce_element();
wait(mutex);
//between wait and signal is the CS
add_element_to_buffer();
n+=1;
if n == 1 then signal(delay); //marking that buffer is full
signal(mutex);

the structure of a consumer looks like this:

wait(mutex);
remove_element_from_buffer();
n-=1;
n_local = n;
signal(mutex);
if n_local == 0 then wait (delay); //marking that buffer is empty

b) limited buffer

for the limited buffer we add another semaphore delayProduct and change the code above for the producer to look like the one for the consumer

2. Writers and readers

Scenario: managing a database for a plane ticketing service: writers and readers that want to access the database will be competing against each other

There are 2 situations:

• when a reader is not stopped from reading a resource if the writer didn’t get the permission to write yet
• once a writer is set, it will write as soon as possible

a) for the first situation, the reader get’s higher priority in comparison with a writer when there’s a multitude of readers reading

( ! ) the writers may starve

b) for this situation, the writer get’s higher priority in comparison with a reader when there’s a multitude of writers writing

Solution for the first version:

The OS may use a mutex semaphore and a wrt semaphore ( for mutual exclusion regarding writers) :

for the writer:

wait(wrt);
write_element();
signal(wrt);

for the reader:

wait(mutex);

readCount += 1;
if readCount == 1 then wait(wrt);

signal(mutex);

read_element();

wait(mutex);
readCount -= 1;
if readCount == 0 then signal(wrt);
signal(mutex);

3. Dinning philosophers 

Scenario: There are 5 chinese philosophers sitting at a table. The philosophers are eating and thinking all day long. There are 5 plates of rice and 5 sticks (only 5).

Each philosopher can pick up only one stick at a time.

Solution: Thinking of chopsticks as being semaphores: we declare  a general semaphore  chopstick[5];

The structure of a philosopher:

wait(chopstick[i]);
wait(chopstick[i+1] mod 5);
eat();
signal(chopstick[i]);
signal(chopstick[i+1] mod 5);

4. Sleeping barber

Scenario: There is a barber shop which has only a limited number of chairs. The barber is sleeping until somebody wants a haircut. The client may take a sit and wait to be shaved if there are free seats or may walk away unshaved.

Solution: Using a mutex binary semaphore, a barber binary semaphore, a customer general semaphore and an integer for counting the free seats: freeSeatsCount;

INIT: mutex = 1; customer = barber = 0; freeSeatsCount = n (n being the number of chairs)

for the barber:

wait(customers);
wait(mutex);
freeSeatsCount++;
signal(barber);
signal(mutex);
shave();

and for the customer:

wait(mutex);
if freeSeatsCount > 0 then
{
    freeSeatsCount --;
    signal(customers);
    signal(mutex);
    wait(barber);
    is_shaved();
}
else signal(mutex);