Operating Systems - Process Synchronization

Author Avatar
Nathaniel May 07, 2015

The Critical Section Problem

Requirements

  1. Mutual exclusion: if process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
  2. Progress: if no process is executing in the critical section, then one process will be eventually selected.
  3. Bounded Waiting: a process can eventually get the chance to enter critical section.

Solution Template

while(1){
    /*entry section*/
    ...
    /*critical section*/
    ...
    /*exit section*/
    ...
    /*remainder section*/
}

Failed Algorithm #1

Initialization

/*shared between two processes*/
int turn = 0;

Implementation for Process Pi

while(1){
    while(turn != i);
    /*critical section*/
    ...
    turn = j;
    /*remainder section*/
}

“Progress” Violation Example

P0P1
while(turn != 0);—-
—-while(turn != 1);
/*critical section*/—-
turn = 1;—-
—-/*critical section*/
—-turn = 0;
—-while(turn != 1);
looping forever

Failed Algirithm #2

Initialization

/*shared between two processes*/
bool flag[2];
flag[0] = flag[1] = false;

Implementation for Process Pi

while(1){
    flag[i] = true;
    while(flag[j]);
    /*critical section*/
    ...
    flag[i] = false;
    /*remainder section*/
}

“Progress” Violation Example

P0P1
flag[0] = true;—-
—-flag[1] = true;
—-while(flag[0]);
looping
while(flag[1]);
looping forever		—-

Solution without OS Support

Initialization

/*shared between two processes*/
int turn = 0;
bool flag[2];
flag[0] = flag[1] = false;

Implementation for Process Pi

while(1){
    flag[i] = true;
    turn = j;
    while(flag[j] && (turn == j));
    /*critical section*/
    ...
    flag[i] = false;
    /*remainder section*/
}

Solution with Synchronization Hardware

Atomic Hardware Instruction testAndSet()

/*atomically set a boolean to be true, and return the original value*/
boolean testAndSet (bool *target) {
    /*no context switch from here*/
    bool rv = *target;
    *target = true;
    return rv;
    /*allow context switch from here*/
}

Initialization

/*shared between two processes*/
boolean lock = false;

Implementation for Process Pi

while(1){
    while(testAndSet(&lock));
    /*critical section*/
    ...
    lock = false;
    /*remainder section*/
}

Semaphore

Traditional Implementation - Busy Waiting

class Sempahore{
private:
    int value;
public:
    void wait();
    void signal();
}

/*atomic*/
void Semaphore::wait(){
    while(value <= 0);
    value--;
}

/*atomic*/
void Semaphore::signal(){
    value++;
}

Modern Implementation - Blocking

class Sempahore{
private:
    int value;
    Queue<Process> q;
public:
    void wait();
    void signal();
}

/*atomic*/
void Semaphore::wait(){
    value--;
    if(value < 0){
        block(); //system call to block the current process
    }
}

/*atomic*/
void Semaphore::signal(){
    value++;
    if(value <= 0){
        wakeup(q.dequeue()); //system call to wake up a process
    }
}

Solution with Semaphore

Initialization

/*shared between two processes*/
Semaphore *mutex = new Semaphore(1);

Implementation for Process Pi

while(1){
    mutex->wait();
    /*critical section*/
    ...
    mutex->signal();
    /*remainder section*/
}

Solutions of Classic Synchronization Problems using Semaphores

Bounded Buffer (aka. Producer/Consumer)

Requirements

  1. Two proceses, the producer and the consumer, share a same buffer with finite capacity.
  2. The producer generates a piece of data, add it to the buffer, and start again.
  3. At the same time, the consumer removes data from the buffer one piece at a time.
  4. The producer won’t try to add data into the buffer if it’s full.
  5. The consumer won’t try to remove data from an empty buffer.

Initialization

#DEFINE CAPACITY 10;
Buffer* buffer = new Buffer(CAPACITY);
Semaphore* empty = new Semaphore(CAPACITY);
Semaphore* full = new Semaphore(0);
Semaphore* mutex = new Semaphore(1);

Producer Process

while(1){
    Item* item = produce();
    empty->wait();
    mutex->wait();
    buffer->add(item);
    mutex->signal();
    full->signal();
}

Consumer Process

while(1){
    full->wait();
    mutex->wait();
    consume(buffer->remove());
    mutex->signal();
    empty->signal();
}

Readers/Writers

Requirements

  1. Multiple reader and writer processes.
  2. Readers can read concurrently.
  3. Writing is performed ASAP (i.e. writers have precedence over readers).

Initialization

Essay* essay = new Essay();
int readcount = 0;
Semaphore* resource = new Semaphore(1);
Semaphore* mutex = new Semaphore(1);

Writer Process

resource->wait();
essay->write();
resource->signal();

Reader Process

mutex->wait();
readcount++;
if(readcount == 1){
    resource->wait();
}
mutex->signal();
essay->read();
mutex->wait();
readcount--;
if(readcount == 0){
    resource->signal();
}
mutex->signal();

Dining Philosophers

Requirements

  1. Five silent philosophers sit at a round table with bowls of spaghetti.
  2. Forks are placed between each pair of adjacent philosophers.
  3. Each philosopher must alternately think and eat.
  4. A philosopher can only eat spaghetti when he has both left and right forks.
  5. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher.
  6. After he finishes eating, he needs to put down both forks so they become available to others.
  7. A philosopher can take the fork on his right or the one on his left as they become available, but cannot start eating before getting both of them.
  8. Eating is not limited by the remaining amounts of spaghetti or stomach space.

Initializaiton

#DEFINE CAPACITY 5;
Semaphore* forks[CAPACITY];
for(int i = 0; i < CAPACITY; i++){
    forks[i] = new Semaphore(1);
}

Process for Each Philosopher $i$

while(1){
    fork[i]->wait();
    fork[(i + 1) % CAPACITY]->wait();
    eat();
    fork[i]->signal();
    fork[(i + 1) % CAPACITY]->signal();
    think();
}

Notes

This solution can suffer from deadlock (e.g. all philosophers decide to eat at the same time and all pick up
their left chopstick first) and/or starvation. Some ways to avoid deadlock are:

  1. Don’t allow all philosophers to sit and eat/think at once.
  2. Pick up both chopsticks in a critical section
  3. Alternate choice of first chopstick

More Examples on Synchronization Algorithms

Example #1 - Failed Algorithm (from Tutorial 4 Question 2)

Initializaiton

int flag[2];
flag[0] = flag[1] = 0;

Algorithm for Pi

while(1){
    while(flag[j] == 1);
    flag[i] = 1;
    /*critical section*/
    ...
    flag[i] = 0;
    /*remainder section*/
}

“Mutual Exclusion” Violation Example

P0P1
while(flag[1] == 1)—-
—-while(flag[0] == 1)
flag[0] = 1—-
/*critical section*/
already in critical section		—-
—-flag[1] = 1
—-/*critical section*/
mutual exclusion violated

Example #2 - Failed Algorithm (from AY14-15 Sem 1 Final Exam)

Initialization

int turn = 0;
bool flag[2];
flag[0] = flag[1] = false;

Algorithm Setting for P0

while(1){
    flag[0] = true;
    turn = 1;
    while(flag[1] && turn == 1);
    /*critical section*/
    ...
    flag[0] = false;
    /*remander section*/
}

Algorithm Setting for P1

while(1){
    flag[1] = true;
    turn = 0;
    while(flag[0]);
    /*critical section*/
    ...
    flag[1] = false;
    /*remander section*/
}

“Progress” Violation Example

P0P1
flag[0] = true;—-
—-flag[1] = true
—-turn = 0;
turn = 1;—-
—-while(flag[0])
looping
while(flag[1] && turn == 1)
looping forever		—-

Example #3 - Working Algorithm (from AY13-14 Sem 2 Final Exam)

Atomic Instruction compareAndSwap()

/* if an integer equals to oldV,
 * atomically set it to newV,
 * and return the original value*/
int compareAndSwap(int* addr, int oldV, int newV){
    /*no context switch from here*/
    int original = *addr;
    if(oldV == original){
        *addr = newV;
    }
    return original;
    /*context switch allowed from here*/
}

Implementation for Process Pi

int mutex = 0;
while(1){
    while(compareAndSwap(&mutex, 0, 1) == 1);
    /*critical section*/
    ...
    mutex = 0;
    /*remainder section*/
}

Analysis

This is solution is similar to the testAndSet() introduced in the lecture notes. Consider false value as 0 and true value as 1.