Xref: utzoo comp.sys.mips:237 comp.arch:11938
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!gem.mps.ohio-state.edu!tut.cis.ohio-state.edu!bloom-beacon!eru!luth!sunic!mcsun!ukc!inmos!roger
From: roger@wraxall.inmos.co.uk (Roger Shepherd)
Newsgroups: comp.sys.mips,comp.arch
Subject: Re: Mips, Mach, test-and-set
Message-ID: <2591@ganymede.inmos.co.uk>
Date: 19 Oct 89 08:42:35 GMT
References: <6565@pt.cs.cmu.edu>
Sender: news@inmos.co.uk
Reply-To: roger@inmos.co.uk (Roger Shepherd)
Organization: INMOS Limited, Bristol, UK.
Lines: 40

In article <6565@pt.cs.cmu.edu> af@spice.cs.cmu.edu (Alessandro Forin) writes:
>
>A number of posts in various newsgroups raised the issue of how to write
>parallel programs for MIPS-based machines, given the lack of any form of
>interlocked instruction in the instruction set.  This article describes how
>the problem was solved in the port of Mach to the MIPS M-500 and
>DECStation-3100 done at CMU.
> ...
>The second solution for the Pmax is currently based on a new algorithm
>(derived from Lamport's) that does not need hardware support, as the
>hardware provides none. 
> ...
>Since Lamport's algorithms were mentioned, it is worth noting that
>those described in the TOCS paper "A Fast Mutual-Exclusion Algorithm"
>are inappropriate for user-level programs on MIPS.  The first problem
>is that Lamport explicitly noted that the first (fast) algorithm was
>only intended for interrupt-level routines in the kernel, e.g. with no
>pre-emption.  Too many people fail to realize this, even if it is
>clearly stated in the paper.

The problem of how to write parallel programs without hardware support
for interlocking is well known and a solution was published by E. W.
Dijkstra in Communications of the ACM, Volume 8, Number 9, September
1965. The abstract reads 

	"A number of mainly independent sequential-cyclic processes
	 with restricted means of communication with each other can
 	 be made in such a way that at any moment one and only one
	 of them is engaged in the ``critical section'' of its cycle.''

I suspect there are serious efficiency problems in using his solutoin on
a modern cache-coherent multiprocessor. However, it continues to amaze
me that it is possible to implement critical regions using only read and
write operations even in the presence of pre-emption.
 

Roger Shepherd, INMOS Ltd   JANET:    roger@uk.co.inmos 
1000 Aztec West             UUCP:     ukc!inmos!roger or uunet!inmos-c!roger
Almondsbury                 INTERNET: roger@inmos.com
+44 454 616616              ROW:      roger@inmos.com OR roger@inmos.co.uk