William Stallings discuss various step by step process in developing Dekker's algorithm in his Operating Systems book. In process, he reaches to following version of algorithm (which is incomplete as it results in livelock):

2    /*    PROCESS 0    */
3    . 
4    . 
5    flag[0] = true;
6    while (flag[1])
7    {
8       flag[0] = false;
9       /* delay */ ;            
10       flag[0] = true;
11    }
12    /* critical section*/; 
13    flag[0] = false;.
15    .
17    /*    PROCESS 1   */
18    . 
19    . 
20    flag[1] = true;
21    while (flag[0]) 
22    {
23       flag[1] = false;
24       /* do */ ; 
25       flag[1] = true;
26    }
27    /* critical section*/; 
28    flag[1] = false;.
30    .

I want to know whether above algorithm satisfies the "bounded waiting" requirement of critical section solution.

My current opinion is that, if process 0 fails on lines 6,7,8,11,12,13,14,15, that is all lines where flag[0] is already set to true, then process 1 will be blocked and hence will result in unbounded waiting. Am I correct?

Also is there easy way to find whether given/proposed algorithm for critical section problem solution satisfies "bounded waiting" requirement?


A reasonable definition of bounded waiting is:

After a process made a request to enter its critical section and before it is granted the permission to enter, there exists a bound on the number of turns that other processes are allowed to enter. [1]

In your case each process makes its request to enter by setting its flag (line 5 for Process 0, line 20 for Process 1. The granting of permission is the test of the other process' flag (flag[1] false on line 6 grants permission to Process 0, flag[0] false on line 21 grants permission to Process 1).

So the only way to test the bounded waiting requirement here is to consider the case that Process 0 has just tested flag[1] on line 6, and found it true, and ask, "how many times can Process 1 leave and reenter the critical section while Process 0 is stuck in the loop?" (Hint: consider the case where Process 0 has really bad luck, and Process 1 is able to leave and reenter the critical section during Process 0's delay on line 9).

[1] source: http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf

  • $\begingroup$ So crashing of process is out of context, right? Considering following execution sequence I concluded that it may lead unbounded waiting: (1) P0 finds flag[1] == true in L6 (2) P0 sets flag[0] = false in L8 (3) P1 finds flagp[0] == false in L21 (4) P1 completes one iteration and sets flag[1] = true in line 20 of next iteration. (5) P0 sets flag[0] = true in L10 (6) P0 finds flag[1] == true in L6 And this continues forever, preventing process 0 from entering its critical section forever. Am I right with this thinking? $\endgroup$
    – Maha
    Jul 2 '16 at 20:20
  • $\begingroup$ Right on both. Crashing is out of context, and your example is unbounded waiting for P0. $\endgroup$ Jul 3 '16 at 0:55
  • $\begingroup$ Also was trying to decide if it ensures progress requirement. Can you tell me if this is correct too: (1) P1 sets flag[1]=true in L20 (2) P1 finds flag[0]=false in L20 (3) P1 completes its critical section (4) P0 sets flag[0]=true in L5 (5) P0 finds flag[1]=true in L6 (6) P1 sets flag[1]=false in L28 (7) P0 finds flag[1]=false in L6 (8) P0 enter in critical section. At (5) P0 wanted to enter its critical section & no one is executing in critical section). P1 only was involved in making decision whether to allow P0 or not. Hence progress is ensured. $\endgroup$
    – Maha
    Jul 3 '16 at 6:50
  • $\begingroup$ It does not ensure bounded waiting right? The reason being the code can go into livelock and any set of processes which have tendencies to get into livelock or deadlock cannot ensure bounded waiting, right? $\endgroup$
    – anir
    Jan 28 '20 at 15:18

Dekker's algorithm operates in strict alternation format i.e. 2 processes will alternatively gain Critical section.

As the definition given above by Wandering Logic, there is only one process for which another process has to wait.For example if process P1 wants to enter critical section then at most it has to wait for only one process(i.e. P0) for gaining control of CS.

This shows that Dekker's algorithm ensures bounded waiting property.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.