[Nate the great]

Originally Posted by Catire

Anyways one of my teachers decided to have us turn in a paper that explains Dekker's algorithm, and i think i'm burned out because I cant understand the damn thing, let alone explain it step by step.

Can anyone maybe point me to a website that explains how that thing works?? the library at school was no help

First, that teacher is either incompetent or a sadist. Dekker's Algorithm is an example of mutual exclusion, which is a topic that should be covered in an upper level class on concurrent processing. It should not have been thrown at you at the last minute.

First go read the Wiki article. Then I'll try to explain Dekker's. I don't know where you are in your studies, so I hope I can help.

Mutual exclusion problem: You have 2 objects that want to use the same piece of code, but only one can use it at a time (or bad things happen). When one object is using the piece of code, it needs to exclude the other from using the code.

Dekker's Algorithm is a 3 flag solution to the classic 2 thread mutual exclusion problem.

Start conditions:

 flag[0] := false
 flag[1] := false
 turn := 0   // or 1

Both boolean flags are set to false. False means "I don't want to use the critical section".

Turn is set to either 0 or 1. At this point it doesn't matter which value. If it's set to 0 p(0) enters the critical section before p(1), and if it's set to 1 p(1) enters the critical section before p(0).

     flag[0] := true // means = I want to use the piece of code
     while flag[1] = true { // means = enter while loop if other object wants to use the piece of code too
         if turn ≠ 0 {            // means =  if it's not my turn, 
             flag[0] := false   //set my flag to false and 
             while turn ≠ 0 {  // wait in this while loop until the other object says it's my turn
             }
             flag[0] := true    // other object let me out of while loop, so I want to use the critical code now
         }
     }
 
    // critical section
    ...
    turn := 1                       // let the other object know that it can go next
    flag[0] := false

// I don't want to use the critical section anymore

P.S. There are 3 situations that might happen.

1, one of the objects approaches the critical section, and the critical section is not in use, and it is this object's turn: the object uses the critical section

2, one of the objects approaches the critical section, and the critical section is not in use, and it is not this object's turn: the object waits in the while loop until the other object uses the critical section, leaves the section, and tells this object that it can use the critical section

3, one of the objects approaches the critical section, and the critical section is in use: the object waits in the while loop until the other object leaves the critical section, and tells this object that it can use the critical section

P.P.S. This is not a simple concept to explain. Honestly, it should be covered in an hour long lecture by someone with a PhD. Doing it in text is really difficult.

P.P.P.S. When you have the paper written, post it here. My Spanish should be up to the task of making sure you described the algorithm correctly.

P.P.P.P.S. Please, on my behalf, hit your instructor very hard with your textbook. He deserves it.