Talk:Peterson's algorithm

Unclear wording

"Note that reordering of memory accesses can happen even on processors that don't reorder instructions (such as the PowerPC processor in the Xbox 360)." -- Is unclear on two levels, first, what is it that causes reordering if not the CPU (I suspect the author was thinking of the compiler)? Second, is PowerPC in the 360 an example of accesses being reordered despite the processor not reordering instructions, or is it an example of a processor that reorders instructions?

Code sample and description not synced

The description refers to a 'flag' variable, but there is no such variable in the code sample, only 'interested' and 'turn'. 108.198.115.103 (talk) 02:23, 18 December 2011 (UTC)

Test and Set

As far as I know, test and set instructions have nothing to do with dual port RAM. tst have to do with the processor architecture, the bus arbiter, but not with the memory. For the time being, I will remove the link to dual port ram. Glipari (talk) 22:05, 25 January 2008 (UTC)

External Links

This External Link leads to a trivialization of Peterson's Algorithm.

It uses the AND operator and does not reset the flags. After the first run, which is interleafed, it reverts to serial runs, which is a trivialization of Peterson's original algorithm (1981). Using Peterson's original OR operator and resetting the flags as he does, every run is interleafed. These results have been checked by my research student, Ali Nademi, who has tested these runs using SPIN. Ali notes also that the run using the AND with no flag reset has no assertion violations. Even so, the interleafing stops after the first run. Since serial ordering of processes has no concurrency problem, there are no conflicts. Batch processing in serial order removes any need for the mutual exclusion algorithm, which is why we say that the AND version of Peterson's algorithm is a trivialization of the original intent.

GWO, 08-2005: I changed it back to the AND operator including a flag reset, because it didn't work as it was... Interleaving also seams to be fine now.

Earlier this month I provided a link to a Java application of Peterson's Algorithm, including source code. However, it was removed by 66.65.123.238. I've restored it for the time being until a justified reason for removal is given, such as the above statements which concern a different link that has long since been removed. -Stimpy 01:46, 27 November 2006 (UTC)

Stub?

Shouldn't this article be a stub? The actual algorithm itself isn't discussed anywhere...

More information on Dutch page

I came here from the Dutch page. Which gives a full formal proof (albeit in dutch) of the algorithm, and cites an english book (which I can verify, as I have it too). Also, is it really necessary to have an entire piece of C-code? Nice and fancy, but a very simple scetch(sp?) of the problem, and the proper solution should do just fine.

Essential criteria

• The algorithm satisfies the three essential criteria of mutual exclusion: [...]
  • How come there are exactly three criteria, no more, no less? Does this follow from the theory of computation? Is there a proof that there are three? --Abdull (talk) 14:03, 14 August 2008 (UTC)
    • I have had a similar question and performed some research: Silberschatz claims you need three conditions to hold: mutual exclusion, progress and bounded waiting (Operating System Concepts, 7th Edition, section 6.2, page 194). Tanenbaum claims you "need four conditions to hold to have a good solution" (Modern Operating Systems, 3rd Edition, section 2.3.2, page 117). These four are mutual exclusion, progress, bounded waiting and fairness ("No assumptions can be made about speeds or the number of CPUs."). Tanenbaum probably included fairness, because he thinks that it is required for a good (i.e. efficient) solution. Update: Added my signature. --Robert Nitsch (talk) 07:22, 14 February 2012 (UTC)

Please provide sources

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

Wrong Wrong

Thanks to your Process I have failed a project. I thought Wikkipedia had correct information always. My professor says that Peterson's Progress condition is satisfied at a 100% and you claim it is not!

I looked stupid thanks to you —Preceding unsigned comment added by 74.9.88.75 (talk) 18:49, 16 October 2009 (UTC)

rotfl. That's why you should use reliable sources. Wikipedia is not reliable, by definition. You've learned something. --Lo'oris (talk) 11:13, 6 July 2010 (UTC)

Redoing this incorrect section on "Peterson's Solution"

Let's discuss the portion that makes this section incorrect.

"This criterion says that no process which is not in a critical section is allowed to block a process which wants to enter the critical section."

You are incorrect, since your definition for Progress is incomplete. In the book, Operating System Concepts: Seventh Edition by Silbershatz on Page 194, the definition for Progress is the following: "If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely." The remainder section is the portion after the a process exits from the critical section.

The following is another section where you were incorrect.

"There is no strict alternating between P0 and P1."

Again, in Silberschatz's Operating System Concepts: Seventh Edition, on Page 195, it states "Peterson's solution is restricted to two processes that alternate execution between their critical sections and remainder sections." Furthermore, although I have not read it anywhere, your example of a process wanting to immediately get into the Critical Section AGAIN would probably infringe upon the requirement for there to be Bounded Waiting, since if a process could constantly demand and get into the CS the other Process may never get in the Critical Section! —Preceding unsigned comment added by BurningSteel (talk • contribs) 07:40, 21 November 2009 (UTC)

Sorry but your correction is incorrect! If Process 1 does not want to enter the critical section it will not set its flag and process 0 will be able to enter and leave as many times as it wants in the absence of that flag. Thus it is correct that "There is no strict alternating between P0 and P1."

Wording on progress and alternance

Regarding the Progress section, I don't think alternance between processes is clerarly explained. Maybe it's the wording, but the text vaguely suggests that there is strict alternance between processes, and that is incorrect. Furthermore, the quotation from the book: "Peterson's solution is restricted to two processes that alternate execution between their critical sections and remainder sections", helps to mislead the reader in this text. I'm not saying that the book is incorrect, of course, but without context, the quotation does not provide enough information in the section.

I know I could not explain it much better, so I suggest someone with expertise in concurrency develops this section a bit more, because it is one of the most important details of the algorithm and it is not portrayed in a clear way. For the rest of the article, seems fine to me.

Maybe replacing "The algorithm" with "Pseudocode", and including an image with a flowchart that could describe the algorithm without any code or syntax would be quite suitable.

Thanks!

Edit: Would it be possible to translate the Dutch article to English? It seems to be the best version. It even includes Mathematical proof.

Abmirayo (talk) 14:12, 5 March 2010 (UTC)

more than two

While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.

ok, there's a reference to a book, fine. Still, this article should really go into more detail about that. --Lo'oris (talk) 11:14, 6 July 2010 (UTC)

TLA+/PlusCal

Leslie Lamport gives an example specification of this algorithm in PlusCal: should it be linked from here? --82.40.14.9 (talk) 05:20, 4 February 2022 (UTC)