Jump to content

Talk:Peterson's algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by SineBot (talk | contribs) at 07:41, 21 November 2009 (Signing comment by BurningSteel - "Redoing this incorrect section on "Peterson's Solution": new section"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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 (talkcontribs) 07:40, 21 November 2009 (UTC)[reply]