Register Guidelines E-Books Search Today's Posts Mark Forums Read

 MobileRead Forums Seriously thoughtful Dekker's Algorithm help.

 03-03-2010, 08:30 PM #1 Catire Lord of the Universe     Posts: 670 Karma: 737849 Join Date: Jan 2008 Location: Maturin , Venezuela Device: Sony Reader PRS-505 / PSP Dekker's Algorithm help. 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
 03-03-2010, 08:55 PM #2 vivaldirules When's Doughnut Day?     Posts: 10,054 Karma: 13675475 Join Date: Jul 2007 Location: Houston, TX, US Device: Sony PRS-505, iPad "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.
03-03-2010, 09:58 PM   #3
Nate the great
Sir Penguin of Edinburgh

Posts: 11,824
Karma: 14499999
Join Date: Apr 2007
Location: DC Metro area
Device: Shake a stick plus 1
Quote:
 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:
Code:
``` 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).
Code:
```     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.

 03-04-2010, 12:24 AM #4 Catire Lord of the Universe     Posts: 670 Karma: 737849 Join Date: Jan 2008 Location: Maturin , Venezuela Device: Sony Reader PRS-505 / PSP 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.
 03-04-2010, 02:18 AM #5 lene1949 Wizard     Posts: 1,954 Karma: 213930 Join Date: Oct 2009 Location: Middelfart, Denmark Device: Kindle paper white Clear as mud...
 03-04-2010, 11:32 AM #6 GeoffC Chocolate Grasshopper ...     Posts: 27,574 Karma: 20816144 Join Date: Mar 2008 Location: Scotland Device: Muse HD , Cybook Gen3 , Pocketbook 302 (Black) , Nexus 10: wife has PW Clear as dark melted chocolate, but not as tasty ....
 03-04-2010, 01:32 PM #7 Xenophon curmudgeon     Posts: 1,473 Karma: 5665922 Join Date: Jun 2006 Location: Redwood City, CA USA Device: Kobo Aura HD, (ex)nook, (ex)PRS-700, (ex)PRS-500 @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
03-05-2010, 01:20 PM   #8
Catire
Lord of the Universe

Posts: 670
Karma: 737849
Join Date: Jan 2008
Location: Maturin , Venezuela
Device: Sony Reader PRS-505 / PSP
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.
Attached Files
 dekker.doc (36.0 KB, 224 views)

 03-06-2010, 08:33 AM #9 GeoffC Chocolate Grasshopper ...     Posts: 27,574 Karma: 20816144 Join Date: Mar 2008 Location: Scotland Device: Muse HD , Cybook Gen3 , Pocketbook 302 (Black) , Nexus 10: wife has PW Oh gosh - now I need a language translator .... not to worry, someone more knowledgeable will comment ... good luck
 03-06-2010, 04:12 PM #10 TGS Country Member     Posts: 9,059 Karma: 7676767 Join Date: Feb 2010 Location: Denmark Device: Liseuse: Irex DR800. PRS 505 in the house, and the missus has an iPad. Oh, you meant that Dekker's algorithm!
03-06-2010, 04:14 PM   #11
Nate the great
Sir Penguin of Edinburgh

Posts: 11,824
Karma: 14499999
Join Date: Apr 2007
Location: DC Metro area
Device: Shake a stick plus 1
Quote:
 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.

 03-11-2010, 04:19 AM #12 Billjr13 Addict     Posts: 357 Karma: 550002 Join Date: Jan 2009 Location: Colorado Device: Sony PRS 700 & 650 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)
 03-18-2010, 07:56 PM #13 happy_terd Banned   Posts: 13,045 Karma: 10105011 Join Date: Jan 2010 Location: Finally made it to Walmart. Device: PRS 420 How did it go?
 03-19-2010, 10:03 AM #14 Catire Lord of the Universe     Posts: 670 Karma: 737849 Join Date: Jan 2008 Location: Maturin , Venezuela Device: Sony Reader PRS-505 / PSP 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.