Re: CSP, JMM and better processor architectures

[Denis A Nicole <dan@xxxxxxxxxxxxxxx>]

On Fri, 12 Oct 2001, P.H.Welch wrote:

> It was exactly this line of reasoning that led to the failure (race hazard
> leading to deadlock) of the original monitor algorithms for the JCSP
> ALT implementation.  I had to avoid a deadlock by removing a lock and
> thought I had "carefully reasoned" that it would be safe - I was wrong.
> The fixed algorithm, with the lock back in, avoided the deadlock by
> cutting out another shortcut into which I had been tempted.  The now
> verified code is much prettier than the incorrect clever one ...

For the simple-minded (like me), if a lock causes deadlock, then removing
it is unlikely to be right---after all, some race is clearly being
prevented...

I'm currently teaching the synchronisation bit of our second year OS
course. The way I teach it:

1. You need enough locks to prevent uncontrolled data sharing. This causes
death, eg in Therac 25.

You are now one step ahead. You may not sell any product, but you won't
have to explain your code to a coroner.

2. You might now get deadlock. Use a standard technique (eg breaking
symmetry or preventing resource filling) or work something out and test
your idea _by_model_checking_. 

You now have code that works. Marketing can probably sell it. Of course,
there's every probability that your carefully locked code runs _slower_
than a sequential solution. So,

3. Either
  a. Throw away your code and replace it with a sequential one. SPoC, for
  example, makes a good job of implementing conceptually parallel code
  efficiently in a single thread. I would be willing to bet that a single
  threaded JCSP would always be faster.

or

  b. Throw away your code and design a scalable parallel code. Your aim
  should be to run faster (not slower) as you add processors... 

Denis A Nicole                 WWW:   http://www.hpcc.ecs.soton.ac.uk/~dan
High Performance Computing     Email: dan@xxxxxxxxxxxxxxx
Department of Electronics      Phone: +44 23 8059 2703
       & Computer Science      Fax:   +44 23 8059 3903
University of Southampton
SO17  1BJ
United Kingdom