9fans archive / 1997 / 04 / 77 /    prev next

From: miller@ham... miller@ham...
Subject: In defence of hardware engineers and out of order execution.
Date: Wed, 23 Apr 1997 14:42:55 BST

David Johnston <DJ@sym...> writes:

> Being a hardware type (with a CS background) I'm feeling a little under
> fire here.

There's no need for anyone to feel under fire.  I think there has been a
failure of imagination on the part of both hardware and software folks, as
to just how much trickery our counterparts are likely to get up to.

When I wrote that

> it's better to be conservative with
> locks than to trust hardware designers to do what we expect.

I didn't mean that hardware designers were unreliable:  it's our own
expectations (that processors will conform to a simple model of behaviour
which hasn't been formally specified) that we shouldn't trust.
But equally, anyone who thinks that only "some madman" would write the
equivalent of
	par {
		{ a = 1; x = b; }
		{ b = 1; y = a; }
	}
has unrealistic expectations about the way concurrent software is being
written. Consider for example Peterson's Algorithm for mutual exclusion
using only shared variables:

P0:				    P1:	
    wanted[0] = 1;			wanted[1] = 1;
    turn = 0;				turn = 1;
    while (turn==0 && wanted[1])	while (turn==1 && wanted[0])
	{}		  		    {}
    /* ... critical section */		/* ... critical section */
    wanted[0] = 0;			wanted[1] = 0;

This algorithm, academically respectable enough to be in standard
Operating Systems textbooks, will presumably fail on any multiprocessor
which allows reads to overtake queued writes (no need to point the
finger at the Pentium Pro in particular).

-- Richard Miller