Jump to content

Talk:Dekker's algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Should we delete the paragraph with the compiler optimization?

[edit]

An optimizing compiler would also try to keep the three variables within registers. The algorithm would never work in this case. Therefore, a real implementation needs a compiler directive to add the semantic of "this variable can potentially be accessed by another entity" (e.g. ISO-C reserves the keyword "volatile" for this purpose). And once the variables are declared as "volatile", the compiler is not allowed to remove writes to them. Please verify my arguments and correct the article accordingly. [ibbis@gmx.de]

I wanted to make exactly this remark. The volatile vars are interprocess synchro-singnals. They are used to prevent inconsistency. This is not the same as memory incoherency. --Javalenok 16:40, 15 June 2006 (UTC)[reply]
Don't delete the paragraph, part of it is ok. Rewrite it instead. —Preceding unsigned comment added by 90.80.39.42 (talk) 13:38, 12 June 2009 (UTC)[reply]

Necessary memory barriers

[edit]

Can someone please add the necessary semantics of operations (acquire/release/...) to guarantee in-order execution of that code on the presence of reorderings? I think "while f1" and "f0 := false" should have acquire/release semantics respectively, and everything else should be nsync, but I'm not an expert on the subject. —Preceding unsigned comment added by 90.80.39.42 (talk) 12:18, 4 February 2009 (UTC)[reply]

volatile is supposed to work with hardware memory mapped ports, which would require in order execution on all objects declared as volatile. The ordering of non-volatile types mixed in with volatile types would not be guaranteed, but the volatile operation ordering would be guaranteed. This combined with cache coherency should make Dekker's algorithm safe as long as both wants_to_enter and turn are both declared to be volatile. Rcgldr (talk) 21:05, 16 December 2016 (UTC)[reply]
"Volatile" means different things in different programming languages. In fact, its meaning has changed between different editions of the same programming language standard in some cases. 2600:4041:D5:D600:1534:7255:8DB3:CE51 (talk) 15:05, 21 June 2022 (UTC)[reply]

Please provide sources

[edit]

I would like to note that this article is completely (!) unsourced. It does not have one single reference. All Wikipedia content must be sourced and verifiable. If a source is not provided soon, I will take this to WP:AfD per WP:OR. Offliner (talk) 23:08, 7 April 2009 (UTC)[reply]

More than two threads of execution section

[edit]

I have removed this whole section, because the code is incorrect and uncited. If any thread i runs this code when turn!=i, it will immediately enter the busy wait loop because "while (do_not_enter || turn != i)" will always be true regardless of the status of do_not_enter. The thread will then be stuck in busy wait until thread i-1 enters the critical section and sets the turn to i, which could be never. This problem can be solved by removing the "|| turn != i" condition from the while loop, but threads can still get stuck indefinitely in the busy wait, for example if thread 2 tries to access the critical section while thread 0 is already doing so - thread 2 will be stuck busy waiting until turn==2, but thread 0 will set the turn to 1 upon exiting the critical section.

I think that any alternative code supporting more than two threads should come with some sort of citation showing correctness before it is added to the page. — Preceding unsigned comment added by Gorbachomp (talkcontribs) 05:01, 9 April 2015 (UTC)[reply]