Dekker’s Algorithm for the Critical Section Problem
The mutual exclusion problem has different solutions. Dekker was a Dutch mathematician who introduced a software-based solution for the mutual exclusion problem. This algorithm is commonly called Dekker’s algorithm. The Deckker’s algorithm was developed for an algorithm for mutual exclusion between two processes.
Implementation of Dekker’s Algorithm
Boolean flag[ 2]
Flag[0] = false;
flag[1] = false;
Int turn = 1;
Int PID = 0; this value is set for process P1,set this to 1and for process P2.
INT PID = 1 – PID ;
In this algorithm, the position of each process is indicated with the variables tern and flag. We can also check which process is in the critical section or not. The variable PID indicates which process is in the critical section. Similarly, we can say here that the PID2 variable represents that which process is not in its critical section.
In the above algorithm, we can see that the value of PID is set as 0 for the first process and we can and say that the first process is in its critical section.
The value of PID is set as 1 for another process that is not in its critical section.
So the value of variable PID and value of variable PID 2 are enough to tell us that a process in its critical section or not.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
main() { // to denote which thread will enter next int Luckythread = 1; boolean Entry_thread1 = false; boolean Entry_thread2 = false; ThreadsActivation(); } Thread1() { do { Entry_thread1 = true; // entry section // wait until thread2 entry // critical section of the process while (Entry_thread2 == true) { // if 2nd thread is more favored if (favaouredthread == 2) { // allow and provide access to other thread Entry_thread1 = false; // wait until this thread is favored while (Luckythread == 2); Entry_thread1 = true; } } // critical section // favor the 2nd thread Luckythread = 2; // exit section // indicate thread1 has finished // critical section of the process Entry_thread1 = false; // remainder section of the process } while (finished == false) } Thread2() { do { Entry_thread2 = true; // entry section // wait until thread1 entry // critical section of the process while (Entry_thread1 == true) { // if 1st thread is more favored if (favaouredthread == 1) { // allow and provide access to other thread Entry_thread2 = false; // wait until this thread is favored while (Luckythread == 1) ; Entry_thread2 = true; } } // critical section // favour the 1st thread Luckythread = 1; // exit section // indicate thread2 has finished // critical section of the process Entry_thread2 = false; // remainder section of the process } while (finished == false) } |
Advantages of Dekker’s algorithm
- Dekker’s algorithm helps in process synchronization.
- Dekker’s algorithm is the first correct solution to the critical section problem that can be proved.
- Dekker’s algorithm is the ideal solution for the mutual exclusion problem, especially in concurrent programming.
