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:
- No deadlocks.
- No starvation
- Efficiency
To guarantee the Mutual exclusion:
Here we use the Bakery Algorithm.
Semaphores
There are 3 conditions for the definition:
- processes agree on a variable S operating as a flag to indicate synchronization condition
- an atomic operation P on S: for pass
P(s): [if S > 0, then S -= 1;] - 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:
- Binary Semaphore
Restricted to [0,1] or [False, True]
There are sufficient to create other type of semaphores
General Semaphore(counting Semaphores)
Increment or decrement the Semaphore By one.Quantity Semaphore
Increment or decrement value for the semaphores
