Nat (Padmanabhan Natarajan) wrote: > is the flag := true equvilanet to Test & Set instruction? That is, can we > assume that setting/unsetting the flag is an atomic operation?
since it is a single command, I assume that, yes, it is atomic. Thanks ! > > On 6/14/06, Dan Ulman <[EMAIL PROTECTED]> wrote: > > > > > > Hi ! Can you please help me with the following ? > > > > Let A be an arbitrary deadlock-free mutual exclusion algorithm in which > > the > > number of steps in the exit code of A depends on the activity of the > > other > > processes (e.g., it has a loop with a wait statement). > > > > In the following, A is modifed, so that the new algorithm satisfies the > > requirement > > that the exit code be of constant number of steps. > > The modified algorithm uses one additional shared bit, called flag, is > > used. > > > > This is the modified mutual exclusion algorithm: > > > > 1 entry code of original A; > > 2 while flag do skip od; > > 3 flag := true; > > 4 exit code of original A; /* Whose step complexity may depend on other > > processes */ > > 5 critical section; > > 6 flag := false; > > > > Does the modifed algorithm satisfy deadlock-freedom and/or mutual > > exclusion (for any A)? Prove your answers. > > > > thanks !! > > Dan. > > > > > > > > > > > ------=_Part_9201_28782189.1150285992293 > Content-Type: text/html; charset=ISO-8859-1 > X-Google-AttachSize: 1385 > > is the flag := true equvilanet to Test & Set instruction? That is, can we > assume that setting/unsetting the flag is an atomic > operation?<br><br><div><span class="gmail_quote">On 6/14/06, <b > class="gmail_sendername">Dan Ulman > </b> <<a href="mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED]</a>> > wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid > rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><br>Hi ! > Can you please help me with the following ? > <br><br>Let A be an arbitrary deadlock-free mutual exclusion algorithm in > which<br>the<br>number of steps in the exit code of A depends on the activity > of the<br>other<br>processes (e.g., it has a loop with a wait statement). > <br><br>In the following, A is modifed, so that the new algorithm satisfies > the<br>requirement<br>that the exit code be of constant number of > steps.<br>The modified algorithm uses one additional shared bit, called flag, > is > <br>used.<br><br>This is the modified mutual exclusion algorithm:<br><br>1 > entry code of original A;<br>2 while flag do skip od;<br>3 flag := true;<br>4 > exit code of original A; /* Whose step complexity may depend on other > <br> processes */<br>5 critical section;<br>6 flag := false;<br><br>Does the > modifed algorithm satisfy deadlock-freedom and/or mutual<br>exclusion (for > any A)? Prove your answers.<br><br>thanks !!<br>Dan.<br><br><br> > ------=_Part_9201_28782189.1150285992293-- --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---