Operating Systems - Process Synchronization

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.

### Failed Algorithm #1

#### “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

#### “Progress” Violation Example

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

## 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.

#### Requirements

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

### 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.

#### 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)

#### “Mutual Exclusion” Violation Example

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

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

#### “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)

#### Analysis

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