HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Process Synchronization: Dekker's algorithm

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dekkeralgorithmsynchronizationprocess

Problem

This Screenshot is taken from William Stalling's Operating Systems book.
My doubt is that Bounded wait is not satisfied by this solution.

For example: P0 and P1 both want to enter critical section and set their flags to true.

flag[0] = true

flag[ 1] = true

Both p0 and p1 enter while loop, p0 wins the race process P1 sets its flag to false

now flag[ 1]= false

Process P0 goes into Critical Section, comes out, sets turn = 1 and flag[0]=false.

Now actual problem starts from here:

Process P1 comes out of infinite while loop and before i could set flag[ 1] to True from False, it gets preempted.

Now Process P0 can go any number of times in Critical section because Flag[ 1] is False.

Conclusion: Process P1 tried to get access to critical section but because of bad solution it did set its flag to False to give path to Po and now stuck for infinite time.

hence B.W is not satisfied!

Solution

When P1 runs again, it set its flag to True. Your scenario assumes P0 is executed continuously, while P1 never gets a chance to execute its code. This also happens in the simple case where there is only one process running, but obviously this does not contradict bounded waiting.

An implicit assumption when talking about protocols for mutual exclusion is that all of the processes involved will eventually run and execute their current command (otherwise it is meaningless to talk about properties such as bounded waiting or starvation freedom).

Context

StackExchange Computer Science Q#80273, answer score: 4

Revisions (0)

No revisions yet.