Software solutions
Constructing a solution
Strict alternation
Not a valid solution.
Dependence on the relative speed of execution of the intervening processes.
The process with less accesses imposes its rhythm to the others.
A process outside the critical section can prevent another from entering there.
If it is not its turn, a process has to wait, until its predecessor enters and give it access on leaving.
1st step
Not a valid solution.
Mutual exclusion is not guaranteed.
Assume the following sequence of execution:
P0 enters enter_critical_section and tests is_in[1] as being false.
P1 enters enter_critical_section and tests is_in[0] as being false.
P1 changes is_in[1] to true and enters its critical section.
P0changes is_in[0] to true and enters its critical section.
Thus, both processes enter their critical sections.
It seems that the failure is a result of testing first the other’s control variable and then change its own variable.
2nd step
Not a valid solution.
Mutual exclusion is guaranteed, but deadlock can occur.
Assume that:
P0 enters enter_critical_section and sets want_enter[0] to true.
P1 enters enter_critical_section and sets want_enter[1] to true.
P1 tests want_enter[0] and, because it is true, keeps waiting to enter its critical section.
P0 tests want_enter[1] and, because it is true, keeps waiting to enter its critical section.
Thus, both processes enter deadlock.
To solve the deadlock at least one of the processes have to go back.
3rd step
An almost valid solution.
The Ethernet protocol uses a similar approach to control access to the communication medium.
But, still not completely valid.
Even if unlikely, deadlock and starvation can still be present.
The solution needs to be deterministic, not random.
Dekker algorithm (1965)
The algorithm uses an alternation mechanism (on the priority) to solve the conflict.
Mutual exclusion in the access to the critical section is guaranteed.
Deadlock and starvation are not present.
No assumptions are done about the relative speed of the intervening processes.
However, it can not be generalized to more than 2 processes, satisfying all the requirements.
Dijkstra algorithm (1966)
Works, but can suffer from starvation.
Peterson algorithm (1981)
The Peterson algorithm uses the order of arrival to solve conflicts.
Each process has to write the other’s ID in a shared variable (last).
The subsequent reading allows to determine which was the last one.
It is a valid solution.
Guarantees mutual exclusion.
Avoids deadlock and starvation.
Makes no assumption about the relative speed of intervening processes.
Generalized Peterson algorithm (1981)
Can be generalized to more than two processes.
The general solution is similar to a waiting queue.
Last updated
