2. Mutual Exclusion

The general situation: N processes execute instruction sequence concurrently.

Mutual Exclusion

It is a Safety Property means Instructions from critical sections of 2 or more processes must never be interleaved.

Requirement:

1. No deadlocks.
2. No starvation
3. Efficiency

To guarantee the Mutual exclusion:
Here we use the Bakery Algorithm.

Semaphores

There are 3 conditions for the definition:

1. processes agree on a variable S operating as a flag to indicate synchronization condition
2. an atomic operation P on S: for pass
   P(s): [if S > 0, then S -= 1;]
3. an atomic operation V on S: for release
   V(s): [S := S + 1]

Then, the S is called the semaphores.

3 kinds of Semaphore types exist:

1. Binary Semaphore

Restricted to [0,1] or [False, True]
There are sufficient to create other type of semaphores

2. General Semaphore(counting Semaphores)
   Increment or decrement the Semaphore By one.

3. Quantity Semaphore
   Increment or decrement value for the semaphores