Seriously thoughtful Dekker's Algorithm help.

[Catire]

My wonderful university decided last friday that instead of two weeks of finals we only needed one ( WTF? ) so now i'm swamped with tests, presentations, programs( double linked lists ) and a few papers.


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

[vivaldirules]

"It allows two threads to share a single-use resource without conflict, using only shared memory for communication."

See, if Geoff posts about chocolate in the "what are you doing now?" thread and also in the "posting milestones" thread but using only inferred communicative references to chocolate, then the sum total of chocolate available for consumption is not diminished (unless Am or Patricia or Zelda are here, in which case you better grab what you can get while you can get it). Oh, wait. "Seriously Thoughtful". Sorry. I've no clue. Sorry.

[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.

[Catire]

Thanks nate,

Right now i'm trying to finish a C program first and i'll take a crack at the paper tomorrow morning. I hope to finish it by noon if work doesn't get in the way.

[lene1949]

Clear as mud...

[GeoffC]

Clear as dark melted chocolate, but not as tasty ....

[Xenophon]

@Nate -- great description of Dekker's Alg. And I heartily agree that the instructor is badly in need of a solid whack upside the head with one or more thick textbooks!

An aspect of Dekker's algorithm that is implicit in your write-up—but that you did not call out explicitly—is that it enforces strict turn-taking! That is, if I arrive at the critical section when it's not my turn yet I wait as long as it takes for the other guy to take his turn before I proceed. This behavior is quite different from that of the locks found in languages like Java.

Xenophon

[Catire]

Not the prettiest or longest thing i've ever written but here's what I could come up with so far.

I still need to add a few things and pretty it up but the final "paper" will look mostly like that.


He only asked for a short paper with a simple explanation of Dekker's algorithm and I think I did that.

[GeoffC]

Oh gosh - now I need a language translator .... not to worry, someone more knowledgeable will comment ... good luck

[TGS]

Oh, you meant that Dekker's algorithm!

[Nate the great]

Originally Posted by Catire

Not the prettiest or longest thing i've ever written but here's what I could come up with so far.

I still need to add a few things and pretty it up but the final "paper" will look mostly like that.


He only asked for a short paper with a simple explanation of Dekker's algorithm and I think I did that.

I just now saw this. I'm working on something right now, but I'll get to it tonight.

[Billjr13]

SO... How did the paper turn out? Was the instructor happy? (even though he dosen't sound like he did any instructing on Dekker's algorithm)

[happy_terd]

How did it go?

[Catire]

It went fine, I got a 15 out of 20.

I got swamped with other stuff and didn't get the time to do it properly so i just turned in a somewhat prettier version of the document I posted.