[algogeeks] Re: mutual exclusion algorithm problem

Wed, 14 Jun 2006 04:53:13 -0700

is the flag := true equvilanet to Test & Set instruction? That is, can we assume that setting/unsetting the flag is an atomic operation?

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.



--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to