Xref: utzoo comp.sys.mips:239 comp.arch:11952
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!ncrlnk!ncrcae!hubcap!mark
From: mark@hubcap.clemson.edu (Mark Smotherman)
Newsgroups: comp.sys.mips,comp.arch
Subject: Re: Mips, Mach, test-and-set
Message-ID: <6831@hubcap.clemson.edu>
Date: 20 Oct 89 04:29:48 GMT
References: <2591@ganymede.inmos.co.uk>
Organization: Clemson University, Clemson, SC
Lines: 52

From article <2591@ganymede.inmos.co.uk>, by roger@wraxall.inmos.co.uk (Roger Shepherd):
> In article <6565@pt.cs.cmu.edu> af@spice.cs.cmu.edu (Alessandro Forin) writes:
>>
>>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.  ... 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.
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Several elegant busy-waiting solutions to the mutual exclusion problem
(including Dekker's, Peterson's simpler version of 1981, and the unadorned
use of test and set) often rely on an unstated assumption of "fair"
scheduling.  That is, they assume that the process currently in its critical
section will not be indefinitely postponed by scheduling precedence or
priorities.

Unfortunately, consider the following scenario.  A low-priority process is
executing inside its critical section.  An interrupt, say I/O completion,
is serviced and unblocks a higher-priority process.  The interrupt handler
exits through the dispatcher, which selects the higher-priority process
based on a preemptive HPF policy.  The higher-priority process now executes
and tries to enter its critical section.  But how can it enter when the low-
priority process cannot be dispatched and thus allowed to leave its critical
section?  ** DEADLOCK **

This is why the IBM S/370 P.O. manual says to only use test and set when
running in supervisor state with interrupts off.  That is, use it only for
synchronization between OS modules in different CPUs.  Compare and swap is
the appropriate instruction to implement busy waiting synchronization between
user processes, but note that the shared resource must be either a word or
a doubleword.  (Of course, the IBM OS provides users with blocking primitives
such as WAIT and POST, etc.)

The potential for deadlock is also why Univac implemented test and set on later
versions of the 1108 to cause an interrupt whenever the instruction found the
bit (byte/word?) already set.  Thus the OS gets involved immediately and blocks
the second process attempting to enter.
-- 
Mark Smotherman, Comp. Sci. Dept., Clemson University, Clemson, SC 29634
INTERNET: mark@hubcap.clemson.edu    UUCP: gatech!hubcap!mark