Path: utzoo!attcan!uunet!lll-winken!vette!brooks
From: brooks@vette.llnl.gov (Eugene Brooks)
Newsgroups: comp.arch
Subject: Re: Synchronisation (was re: MIPS Architecture Question)
Keywords: synchronisation, read-modify-write
Message-ID: <16700@lll-winken.LLNL.GOV>
Date: 17 Jan 89 23:33:19 GMT
References: <5434@ux.cs.man.ac.uk> <4124@hubcap.UUCP>
Sender: usenet@lll-winken.LLNL.GOV
Reply-To: brooks@maddog.llnl.gov.UUCP (Eugene Brooks)
Organization: Lawrence Livermore National Laboratory
Lines: 30

In article <4124@hubcap.UUCP> mark@hubcap.UUCP (Mark Smotherman) writes:
>In article <5434@ux.cs.man.ac.uk>, rmd@r3.cs.man.ac.uk writes:
>> ... it is possible to
>> implement a TAS instruction with a sequence of simpler instructions!
>> ... with support for multi-processing.
>                       ^^^^^^^^^^^^^^^^
>	From the article, it appears that multi-tasking on a single CPU
>	is being discussed rather than multiprocessor support as was the
>	apparent intent of the original MIPS Arch. Ques. posting.

Although it is true that the article in question was not talking true
multiprocessor support, it is possible to establish protection of a
critical region with only read and write operations.  It takes 5 memory
operations, except when a collision occurs between processors in which
it takes a scan of an array having an element for each processor. The algorithm
can be quite competitive (in the absence of collisions) on systems where
the special "test and set" instructions run slower due to implementation
hardware choices.  The algorithm, due to Leslie Lamport, breaks even with
Sequent's Atomic Lock Memory used on their Balance series, but is slower than
the indivisible memory operations supported on their Symmetry series.  A
multiprocessor using the MIPS chip does not have much of a choice,
one can either use Lamport's algorithm or implement the equivalent of
Atomic Lock Memory.  If the Atomic Lock Memory is implemented with a slow
bus interface Lamport's algorithm may be faster.

A more important synchronization primitive, barrier synchronization, is
best done with an algorithm using read and write to shared memory and not
locked counters, in any event.  There are quite of few tricky synchronization
tricks which use read and write only, and some of them are the "best" way
to get the particular synchronization done.