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

Go Back   MobileRead Forums > Miscellaneous > Lounge

Notices

Reply
 
Thread Tools Search this Thread
Old 03-03-2010, 08:30 PM   #1
Catire
Lord of the Universe
Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.
 
Catire's Avatar
 
Posts: 652
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
Catire is offline   Reply With Quote
Old 03-03-2010, 08:55 PM   #2
vivaldirules
When's Doughnut Day?
vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.vivaldirules ought to be getting tired of karma fortunes by now.
 
vivaldirules's Avatar
 
Posts: 10,047
Karma: 13675425
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.
vivaldirules is offline   Reply With Quote
Old 03-03-2010, 09:58 PM   #3
Nate the great
Sir Penguin of Edinburgh
Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.
 
Nate the great's Avatar
 
Posts: 10,524
Karma: 3569525
Join Date: Apr 2007
Location: DC Metro area
Device: Shake a stick plus 1
Quote:
Originally Posted by Catire View Post
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.

P.P.P.P.S. Please, on my behalf, hit your instructor very hard with your textbook. He deserves it.
Nate the great is online now   Reply With Quote
Old 03-04-2010, 12:24 AM   #4
Catire
Lord of the Universe
Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.
 
Catire's Avatar
 
Posts: 652
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.
Catire is offline   Reply With Quote
Old 03-04-2010, 02:18 AM   #5
lene1949
Wizard
lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.lene1949 ought to be getting tired of karma fortunes by now.
 
lene1949's Avatar
 
Posts: 1,957
Karma: 213930
Join Date: Oct 2009
Location: Ipswich, Queensland, Australia
Device: Kindle 2, Sony PRS 650, Ipod Touch
Clear as mud...
lene1949 is offline   Reply With Quote
Old 03-04-2010, 11:32 AM   #6
GeoffC
Chocolate Grasshopper ...
GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.
 
GeoffC's Avatar
 
Posts: 26,947
Karma: 16968764
Join Date: Mar 2008
Location: Scotland
Device: Cybook Gen3 , Pocketbook 302 (Black) , Nexus 10: wife has PW
Clear as dark melted chocolate, but not as tasty ....
GeoffC is offline   Reply With Quote
Old 03-04-2010, 01:32 PM   #7
Xenophon
curmudgeon
Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.Xenophon ought to be getting tired of karma fortunes by now.
 
Xenophon's Avatar
 
Posts: 1,453
Karma: 5657812
Join Date: Jun 2006
Location: Pittsburgh, PA USA
Device: Kobo Aura (soon), (soon-to-be-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
Xenophon is offline   Reply With Quote
Old 03-05-2010, 01:20 PM   #8
Catire
Lord of the Universe
Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.
 
Catire's Avatar
 
Posts: 652
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
File Type: doc dekker.doc (36.0 KB, 174 views)
Catire is offline   Reply With Quote
Old 03-06-2010, 08:33 AM   #9
GeoffC
Chocolate Grasshopper ...
GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.GeoffC ought to be getting tired of karma fortunes by now.
 
GeoffC's Avatar
 
Posts: 26,947
Karma: 16968764
Join Date: Mar 2008
Location: Scotland
Device: 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
GeoffC is offline   Reply With Quote
Old 03-06-2010, 04:12 PM   #10
TGS
Country Member
TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.TGS ought to be getting tired of karma fortunes by now.
 
TGS's Avatar
 
Posts: 9,045
Karma: 7673161
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!
TGS is offline   Reply With Quote
Old 03-06-2010, 04:14 PM   #11
Nate the great
Sir Penguin of Edinburgh
Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.Nate the great ought to be getting tired of karma fortunes by now.
 
Nate the great's Avatar
 
Posts: 10,524
Karma: 3569525
Join Date: Apr 2007
Location: DC Metro area
Device: Shake a stick plus 1
Quote:
Originally Posted by Catire View Post
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.
Nate the great is online now   Reply With Quote
Old 03-11-2010, 04:19 AM   #12
Billjr13
Addict
Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.Billjr13 ought to be getting tired of karma fortunes by now.
 
Billjr13's Avatar
 
Posts: 360
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)
Billjr13 is offline   Reply With Quote
Old 03-18-2010, 07:56 PM   #13
happy_terd
Banned
happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.happy_terd ought to be getting tired of karma fortunes by now.
 
Posts: 13,048
Karma: 10105011
Join Date: Jan 2010
Location: Finally made it to Walmart.
Device: PRS 420
How did it go?
happy_terd is offline   Reply With Quote
Old 03-19-2010, 10:03 AM   #14
Catire
Lord of the Universe
Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.Catire ought to be getting tired of karma fortunes by now.
 
Catire's Avatar
 
Posts: 652
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.
Catire is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Google PageRank Checksum Algorithm doctorow Lounge 295 08-03-2011 11:11 AM
An algorithm to render PDF in small devices caritas PDF 111 05-18-2010 10:50 AM


All times are GMT -4. The time now is 08:02 AM.


MobileRead.com is a privately owned, operated and funded community.