Xref: utzoo comp.sys.mips:241 comp.arch:12003
Path: utzoo!attcan!uunet!mcsun!hp4nl!philapd!ssp1!dolf
From: dolf@idca.tds.PHILIPS.nl (Dolf Grunbauer)
Newsgroups: comp.sys.mips,comp.arch
Subject: Re: Mips, Mach, test-and-set
Message-ID: <326@ssp1.idca.tds.philips.nl>
Date: 23 Oct 89 07:36:01 GMT
References: <2591@ganymede.inmos.co.uk> <6831@hubcap.clemson.edu>
Organization: Philips Telecommunication and Data Systems, The Netherlands
Lines: 40

In article <6831@hubcap.clemson.edu> mark@hubcap.clemson.edu (Mark Smotherman) writes:
->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 **

Although the above state scenario is true, I do hope that no operation system
behaves like this. I worked on an operating system which also had to deal with
this problem. Actually there are two deadlock possibilities: user and
operating system.
A deadlock in user mode (i.e. made by user processes) cannot be detected for
100% (as the above described situation might just be what the user wanted :-).
A deadlock in the operating system or kernel of course must
be detected. There are a few options to bypass this deadlock. One of them
(in fact: Unix) raises the priority of a ready-to-run process on every
schedule when this process does not get running, so eventually the low order
process becomes running. Another solution, which is implemented in for example
DRM System, is priority semaphores. When a process enters a critical section,
the process priority is changed to a fixed (possible very high) priority, to
garantee that it will be executing & leave this section, avoiding the above
described deadlock. When leaving the critical section, the process priority
is restored. If the process has to wait before entering this critical section
(as another process is already in it), the process may be put in a priority
based FIFO queue, i.e. the higher the original process prority, the sooner
it will be the one awoken by the process leaving this section, and within
one priority the processes are queued on FIFO basis.
-- 
Dolf Grunbauer          Tel: +31 55 432764  Internet dolf@idca.tds.philips.nl
Philips Telecommunication and Data Systems  UUCP ....!mcvax!philapd!dolf
Dept. SSP, P.O. Box 245, 7300 AE Apeldoorn, The Netherlands