Mutual exclusion (Dijkstra's algorithm)

[Greg Woodhouse]

since the topic has come up, one thing that'a been bugging me is
Dijkstra's mutual exclusion algorithm:

//process i
status[i] := competing
do
{
while (turn <> i)
{
status[i] := out;
if status[turn] = out then turn := i
}
status[i] := cs
} while (status[other] = cs);
//critical section
status[i] := out;

In the above turn is a shared read/write variable, every process can
read values of the status[] array, but only process i can write to
status[i]. In addition, operations need to be instantaneous (as far as
I can tell).

Can this be implemented in software?

===
Gregory Woodhouse <gregory....@sbcglobal.net>

"Mathematics is the science of patterns."
--Lynn Arthur Steen, 1988

[Darren Coolidge]

This may be off topic but check out how erlang solves concurrency.

http://www.defmacro.org/ramblings/concurrency.html

[kdt...@gmail.com]

I'll bite.

I can't understand this pseudocode. Is i and input variable or a
process thread? Are the status[i] values of 'competing','out','cs'
just simple flag states, line an enum? When you say that only process
i can write to status[i] is this a needed restriction, a coding
consequence, or something else?

And more basically, what is the purpose of the code?
Thanks

(And as you know I have no background in computer science, so go easy
on me :-) )

Kevin

[Gregory Woodhouse]

On Sep 13, 2006, at 6:46 PM, kdt...@gmail.com wrote:

I'll bite.

I can't understand this pseudocode.  Is i and input variable or a

process thread?  Are the status[i] values of 'competing','out','cs'

just simple flag states, line an enum?  When you say that only process

i can write to status[i] is this a needed restriction, a coding

consequence, or something else?

And more basically, what is the purpose of the code?

Thanks

(And as you know I have no background in computer science, so go easy

on me :-)   )

Kevin

I hope this is a bit better. There are n processes running on the same machine, and the goal is to ensure that no two of them can be in what is called their "critical region" at the same time. The algorithm is of historical interest because it is n process distributed algorithm (dating to 1965, I think) and is a generalization of a two process solution first published by Dekker. It makes some fairly restrictive assumptions: both the variable turn and the array status[] are shared by all processes, any process may write to turn at any time and any process may read turn[j] at any time, but it may process i may only write to it if j = i. Updates are immediate. 

//process i

status[i] := competing //process i is competing for access to the critical region

do  

{

  while (turn <> i)

  {

    status[i] := out //process i has lost (for now)

    if (status[turn] = out) then turn := i

  }

  status[i] := cs

} while (status[j] = cs for any j <> i);

//process i enters its critical section

write ("process ", i , " is entering its critical section!");

write ("process", i, " is about to leave its critical section!");

status[i] := out //process i is now in its remainder region

  

Gregory Woodhouse

gregory....@sbcglobal.net

I hear and I forget.

I see and I remember.

I do and I understand.

--Attributed to Confucius, 500 BCE

[Kevin Toppenberg]

On 9/13/06, Gregory Woodhouse <gregory....@sbcglobal.net> wrote:
>
> I hope this is a bit better.

OK, now I get it...

There are n processes running on the same
> machine, and the goal is to ensure that no two of them can be in what is
> called their "critical region" at the same time. The algorithm is of
> historical interest because it is n process distributed algorithm (dating to
> 1965, I think) and is a generalization of a two process solution first
> published by Dekker. It makes some fairly restrictive assumptions: both the
> variable turn and the array status[] are shared by all processes, any
> process may write to turn at any time and any process may read turn[j] at
> any time, but it may process i may only write to it if j = i. Updates are
> immediate.
>
> //process i
> status[i] := competing //process i is competing for access to the critical
> region
> do
> {
> while (turn <> i)
> {
> status[i] := out //process i has lost (for now)
> if (status[turn] = out) then turn := i
> }
> status[i] := cs
> } while (status[j] = cs for any j <> i);
> //process i enters its critical section
> write ("process ", i , " is entering its critical section!");
> write ("process", i, " is about to leave its critical section!");
> status[i] := out //process i is now in its remainder region
>

Your original question was whether this could be implemented in
software. My concern is that with multi-tasking, there could be a
case where process A tests and finds that the critical area is now
available, but before it has time to actually set the status to
reflect that it is going to enter, another process ("B") beats A to
the punch, confusing A.

In M, it seems like this could be accomplished with locks. I.e.
process A should repeatedly try to lock a segment of the message
array. If it succeeds, OK, proceed. If it fails, then try again.

Kevin

[Gregory Woodhouse]

On Sep 13, 2006, at 7:46 PM, Gregory Woodhouse wrote:

 hope this is a bit better. There are n processes running on the same machine, and the goal is to ensure that no two of them can be in what is called their "critical region" at the same time. The algorithm is of historical interest because it is n process distributed algorithm (dating to 1965, I think) and is a generalization of a two process solution first published by Dekker. It makes some fairly restrictive assumptions: both the variable turn and the array status[] are shared by all processes, any process may write to turn at any time and any process may read turn[j] at any time, but it may process i may only write to it if j = i. Updates are immediate. 

In fact, this is the crux of the problem. Any process can update turn, but there are other algorithms where each shared variable is writable by at most one process, and this is much easier to implement. There is no chance of a race condition in which two processes try to update the same variable before it can be read, but it is still conceivable that a process can sneak in a "read" and see the old value of a variable when another process thinks it's been updated. Instantaneous updates (a misnomer since there is no common clock) are the crux of the difficulty in actually implementing algorithms like this. If only one process can run at a time, and each update takes a single instruction (not necessarily a safe assumption), then you're okay. But what if there is more than one processor?

Gregory Woodhouse

gregory....@sbcglobal.net

"The art of asking the right questions in mathematics is more important than the art of solving them."

--Georg Cantor

[Gregory Woodhouse]

On Sep 13, 2006, at 8:02 PM, Kevin Toppenberg wrote:

In M, it seems like this could be accomplished with locks.  I.e.

process A should repeatedly try to lock a segment of the message

array.  If it succeeds, OK, proceed.  If it fails, then try again.

Kevin

I tried this in MUMPS some years ago, both with and without locks. Everything worked perfectly when using locks, but unsurprisingly, it failed miserably when the locks were removed. The obvious problem is that global writes involve a time delay, and that time delay causes the algorithm to fail. Why not use locks? Well, isn't that "cheating" when it's your goal to implement mutual exclusion? Could you implement mutual exclusion in MUMPS if there were no locks?

Gregory Woodhouse

gregory....@sbcglobal.net

"Those who are enamored of practice

without theory are like a pilot who goes

into a ship without rudder or compass."

--Leonardo da Vinci (1452-1519)

[Gregory Woodhouse]

On Sep 13, 2006, at 4:17 PM, Darren Coolidge wrote:

This may be off topic but check out how erlang solves concurrency.

http://www.defmacro.org/ramblings/concurrency.html

This is great! I'd love to have been a fly on the wall during those interviews.

I've never studied Erlang, but there's a nice section on message passing in "The Structure and Interpretation of Computer Programs". Better yet, I did a Google search on 

Dijkstra's algorithm, and one of the first things I turned up was a solution in Scheme.

Gregory Woodhouse

gregory....@sbcglobal.net

Metaphors be with you.

[K.S. Bhaskar]

Greg --

Without hardware locking, I believe this does guarantee that if a
process gets to //critical section, it does have exclusive access.
While there is no possibility for a deadlock, the algorithm does have a
potential livelock situation, described below.

Consider a starting condition of turn=1, processes 2 and 3 are
competing, so status[2] and status[3] are set to competing. Since turn
is 1, both processes 2 and 3 set status[2] and status[3] to out and then
come to the statement if status[turn] = out then turn := i.

They both see status[turn=1] to be out, and set turn to i. At random,
turn might be 2 or 3, but the value doesn't matter. Both set
status[i]=cs, so status[2] and status[3] will both get set to cs.

The interesting part comes in the evaluation of while (status[other] =
cs) - 2 may see status[3] as cs and 3 may see status[2] as cs.

Another weakness of this technique of course is that there must be space
allocated in status for the maximum number of processes. Of course,
status could be coded as a tree that grows dynamically, but it will keep
growing and trees are slower than arrays for performance.

Regards
-- Bhaskar

[Gregory Woodhouse]

On Sep 14, 2006, at 2:51 PM, K.S. Bhaskar wrote:

Greg --

Without hardware locking, I believe this does guarantee that if a 

process gets to //critical section, it does have exclusive access. 

Let's walk through the protocol with two processes: 1 and 2, but drop the assumption that writes are instantaneous (i.e., we suppose that after some small random time epsilon, a process reading a value that had just been written will see the old value.) Assume turn is initially 1.  I may have made a mistake, but under these conditions, this seems a possibility:

1. process 2 sets status[2] to competing

2. process 2 sets turn to 1

3. process 2 sets status[1] to out

4. process[1] sets status 1 to competing

5. process 2 sees status[1] = out (the old value)

6. process 2 sets turn to 1

7. process 1 sees turn = 1 (faster this time!)

8. process 1 sees that status[2] <> cs

9. process 1 enters its critical section. We may either suppose it has not set status[1] to cs, or that this new value is not yet visible to process 2

10. process 2 sees status[1] <> cs

11. process 2 enters its critical section (oops!)

Now the tests I performed were some years ago under DSM. As far as I know, global updates may be immediately visible in GT.M (or Caché), but if they are not, I don't think Dijkstra's algorithm will work.

While there is no possibility for a deadlock, the algorithm does have a 

potential livelock situation, described below.

Absolutely! 

Consider a starting condition of turn=1, processes 2 and 3 are 

competing, so status[2] and status[3] are set to competing.  Since turn 

is 1, both processes 2 and 3 set status[2] and status[3] to out and then 

come to the statement if status[turn] = out then turn := i.

They both see status[turn=1] to be out, and set turn to i.  At random, 

turn might be 2 or 3, but the value doesn't matter.  Both set 

status[i]=cs, so status[2] and status[3] will both get set to cs.

The interesting part comes in the evaluation of while (status[other] = 

cs) - 2 may see status[3] as cs and 3 may see status[2] as cs.

Nice example.  Maybe this doesn't need to be said, but I wasn't recommending Dijkstra's algorithm as a practical technique. I suppose that in a threaded environment where variable updates take a single instruction, then it might work, but atomic update just doesn't sound like a safe assumption. I don't know how shared memory is implemented in Linux or OS X, but I would expect that some system level synchronization would be needed. (As an aside, when I introduced LOCKs to protect updates to the shared variables, which I implemented using the ^TMP global, Dijkstra's algorithm worked perfectly. I'm not saying that's surprising, quite the contrary, but even if LOCK wasn't used to protect the critical section itself, I did think it did dull the luster of the example a bit.

Another weakness of this technique of course is that there must be space 

allocated in status for the maximum number of processes.  Of course, 

status could be coded as a tree that grows dynamically, but it will keep 

growing and trees are slower than arrays for performance.

Right. There are various options here such as using a tournament; i.e., processes compete in pairs for a chance to enter the critical section, but the competition continues until only one process is left. Then there are algorithms using an entirely different approach: One I find rather appealing is the Bakery algorithm. The idea is that processes entering the "bakery" will take a ticket like those you see on those fancy ticket dispensing wheels you see in some stores and clinics. The trick is that once a process has entered the "waiting room" it needs to be able to "watch" for its number to come up. That's easier said then done, and is, in fact, the scenario that motivated my question about notifying processes.

Regards

-- Bhaskar

Greg Woodhouse wrote, on 09/13/2006 07:13 PM:

Gregory Woodhouse

gregory....@sbcglobal.net

"In the human mind, one-sidedness has always been the rule and many-sidedness the exception. Hence, even in revolutions of thought, one part of the truth usually sets while another rises."

--John Stuart Mill

[K.S. Bhaskar]

Gregory Woodhouse wrote, on 09/14/2006 11:14 PM:

[KSB] <...snip...>

> Now the tests I performed were some years ago under DSM. As far as I
> know, global updates may be immediately visible in GT.M (or Caché),
> but if they are not, I don't think Dijkstra's algorithm will work.

[KSB] Since GT.M has no daemon, but instead processes cooperate with one
another to manage the database, the write is instantaneously visible as
soon as the process making the update releases the critical section
where it sets shared memory control structures.