









                              CHAPTER 1





                    THE SYNCHRONISATION PROBLEM.


















































1.0.- INTRODUCTION.



   The purpose of this chapter is to analize the intricacies  arising
in  the  design  and implementation of freely available Inter-process
Communication (IPC) mechanisms.   Section 1.1 presents  a  survey  of
syncronisation  approaches.    The  implementation  problems  of  the
synchronising primitives chosen as the  building  block  of  the  IPC
mechanisms  are  studied  in section 1.2.   Deadly embrace situations
arising with the misuse of well defined syncronisation primitives are
considered  briefly  in  section  1.3.   Section  1.4  comprises  the
analysis of the conglomeration  of  protection  problems  highlighted
throughout sections 1.2 and 1.3.

   It  is appropiate to begin with at least an informal definition of
the terminology employed.

   A process is the abstract entity which executes  the  instructions
of  a sequential program.   Strictly speaking, an independent process
proceeds in the execution of a program with complete disregard of the
activities  of  other  processes.    A  process  cannot be said to be
independent when its activities include interactions  with  those  of
other processes.   In this case, the 'co-operating' processes must be
synchronised with one another.   This chapter is concerned  with  the
syncronisation  of  co-operating  processes, briefly processes, whose
only communication media is the common store.

   The terms deadlock and deadly embrace will be used extensively.  A
deadly  embrace  situation  exists  when  one  or  more processes are
waiting for the occurrence of an event  which  cannot  possibly  take
place.    This  very  general  definition  is  useful to characterise
deadlock situations  encountered  in  the  design  of  syncronisation
primitives  as  well  as  those  arising with the misuse of correctly
defined and implemented primitives.

   Finally, it is important to note that the term 'critical  section'
is  employed  in  a  wider  context  than  that  initially defined by
Dijkstra [Di65].   We use  the  words  to  denote  any  conditionally
re-entrant program section.   More precisely, a critical section is a
program section whose execution  by  a  given  process  is  logically
dependent on certain events caused by other processes.




















1.1.- OVERVIEW OF SYNCRONISATION PRIMITIVES.



   The 'far from trivial' solution to the problem of synchronising  a
set  of  'mainly  independent'  processes  was discovered by Dijkstra
[Di65].  The main difficulty of Dijkstra's solution lies in the basic
assumption:  the  only indivisible operations are the reading from or
storing into a word of the common store.   The constraints obeyed  by
Dijkstra's   solution   guarantee   the  absence  of  deadly  embrace
situations.    That  is  to  say,  they  cannot   all   be   blocked.
Nevertheless,  his  conditions  do not preclude an individual process
from monopolising the execution of the critical section [Kn66].    It
would  be  deceptive  not  to  mention that the solution is perfectly
sound for the application intended in Dijkstra's article  and  indeed
for  a wide variety of applications.   An interesting analysis of the
difficulties encountered in the  construction  of  the  algorithm  is
given in [Di68].

   Later  solutions  impose  more severe constraints on the number of
processes which can gain control of the critical  section  before  an
individual process contending for access is allowed to enter.   Let n
be the number of co-operating processes.    The  algorithm  given  by
Knuth  guarantees  that a process wait at most 2**(n-1) turns [Kn66].
A further modification by de Bruijn provides access within  n*(n-1)/2
turns  and  the  algorithm  given  by  Eisenberg and Mc Guire ensures
access within n-1 turns [Br67,Ei72].

   The solutions cited  are  mainly  of  historical  and  theoretical
interest.   As  pointed  out  by  Knuth,  the  availability  of  more
elaborate indivisible operations  in  hardware  improve  greatly  the
efficiency and compactness of those algorithms [Kn66].

   It   is  important  to  underline  that  the  solutions  mentioned
demonstrate  the  possibility  of  synchronising  processes   without
encountering  deadlock  situations.   The overall absence of deadlock
depends on the correct use of the primitive operations.

   The first feasible syncronisation primitives are the P(s) and V(s)
operations  suggested  by  Dijkstra  [Di68].    The argument s of the
operations is called a semaphore: A non-negative  integer  which  can
only  be  accessed  by  P  and  V.   The initial value of a semaphore
depends on its intended use; when employed for mutual exclusion it is
initialised to 1.   We will refer to a semaphore as being 'busy' when
its instantaneous value is sero.   Equivalently, a semaphore is  busy
when  when  the  execution  of  a  P operation on the semaphore would
result in the suspension of the executing process; otherwise  we  say
that  the semaphore is 'free'.   The operations can be defined in IMP
as [St74]:
   P(s) = [ if s < 1 then . . . ; s = s-1 ]
   and
   V(s) = [s=s+1].
   where the square brackets indicate indivisibility.  The suspensive
points in the then part of the if statement indicate that the process
remains  suspended,  without  concluding  the  operation,  until  the
condition  becomes  true.    Moreover,  if  more  than one process is
suspended on the same semaphore, one and only one will  complete  the





operation and proceed to the next instruction; the rest remain in the
suspended state.

   The semaphore concept has proven extremely useful for studying the
properties of co-operating processes.  Clearly, the implementation of
the semaphore concept poses serious difficulties.   The suspension of
processes is not a problem to be treated lightly.   Furthermore,  the
implementation  of  the P primitive requires that a suspended process
be allowed to detect a change in the value of the semaphore!.

   One modification of the P operation consists in  substituting  the
suspension  of  the executing process for a cycling test on the value
of the semaphore.  This 'test and set' synchronising primitive can be
defined as:
   TS(s) = label: [ if s < 1 then -> label ; s = s-1 ]

   The TS and V primitives have the same macroscopic effect as the  P
and   V.    It  can  be  said  that  the  TS  operation  is  a  crude
implementation of the P  primitive.    A  serious  drawback  of  this
primitive  prompted Dijkstra to discard it as an adequate solution to
the mutual exclusion problem [Di68].   The process which executes the
TS  instruction  is  wasting  valuable  processor time.   Also, it is
probably stealing memory  cycles  from  other  processors  which  are
performing useful work.   However, the simplicity of the operation is
an advantage  which  makes  it  a  valuable  building  block  in  the
construction  of  more  elaborate  syncronisation  primitives.   In a
uniprocessor environment the TS instruction is obviously useless.   A
process  which  finds  a semaphore in the busy state must immediately
yield control of the CPU since that is the only possibility  for  the
semaphore to be freed by another process.

   A  more  faithful implementation of the semaphore concept requires
the support of process suspension.  In addition, the V operation must
be  suitably  modified  to  include  the  notification  to a possibly
suspended process to proceed.   Consequently, the semaphore  variable
must  be  extended to contain the identity of the processes which are
blocked, waiting for a V operation to be performed on the semaphore.

   An interesting technique for the implementation of semaphores with
associated  queues  is  given  in  [La68].   Lampson defines a set of
operations which  allow  the  communication  of  processes  with  the
process scheduler.   They include waking and activating a process and
other functions peculiar to  the  particular  scheduling  philosophy.
For  syncronisation  purposes he suggests the use of a TS instruction
together with a new instruction called PROtect.   The effect  of  the
PRO  instruction is to make the executing process uninterruptible for
a fixed number of  memory  cycles  and  also  to  prevent  any  other
processor from executing a PRO instruction until the current delay is
exhausted.   Access to a  critical  section  using  the  PRO  and  TS
instructions  can  be  described  along  the following lines.   After
executing the PRO instruction, a process uses  the  TS  to  test  the
state  of the semaphore.   If it finds the semaphore busy it proceeds
to execute the  steps  required  to  log  its  identity  in  a  queue
associated  with  the  semaphore.    When  a  process  concludes  the
execution of a critical section, it uses the PRO and TS  instructions
in  a  similar fashion in order to determine if a reactivation signal
must be sent to a blocked process.   The delay of the PRO instruction





guarantees that no other process manipulates the queue.

   This scheme has several drawbacks: a) The PRO instruction requires
that the processors communicate with one another.   Although this may
be easy to implement,  it  violates  the  assumption  that  processes
communicate  only  via the common memory.   Also, the PRO instruction
delays all processors attempting to perform a PRO, regardless of  the
logical  independency  of the indivisible sequences protected in each
case. c) Lampson suggests  that  the  PRO  instruction  need  not  be
privileged  since  it  only introduces a small uninterruptible delay.
However, the abuse of the instruction by 'clever' users attempting to
speed  up  the  execution  of  their  programs  could be the cause of
serious degradation in system performance.

   Syncronisation by means of  'conditional  critical  sections'  was
suggested by Brinch Hansen [Br72].  This approach can be described as
follows.   Let v be a 'lock' variable which can only  be  used  in  a
statement of the form:
   with v do cr ;
   The  with  statement  guarantees that at most one process executes
statement cr at a given time.   The conditional critical region cr is
specified by the construct:
       when b do
   begin
     .
     .
     .

   end ;
   Where  b  is a boolean expression.   If the outcome of b is false,
the process' identity is inserted in an event queue  associated  with
the  critical  region  and hence with variable v.   The process which
modifies the value of one of the operands of b must perform a:
   signal(v)
   operation.   The effect of this  is  to  re-activate  all  of  the
processes  held  up  in the event queue.   The re-activated processes
must begin execution at the with statement.

   Conditional critical regions are intended to  facilitate  compiler
validation of access to critical sections.   The main drawback of the
approach lies in  its  form  of  'busy  waiting'  [Co72,Br73].    The
repeated   re-evaluation  of  the  boolean  expression  by  processes
contending for access may introduce intolerable  degradation  due  to
memory  contention.    In  systems  with processor multiplexing it is
rather costly to schedule processes only to discover that  they  must
be blocked once again.

   Haberman's   signal(s)/wait(s)  primitives  are  very  similar  in
concept to Dijkstra's P and V [Ha72].

   Communication primitives can be  supported  at  a  suitably  inner
layer of the system.   This allows the different processes defined in
higher  layers  to  employ  the  primitives  for  the   purposes   of
syncronisation  and  mutual exclusion required in their interactions.
This  philosophy  has  been  used  in  the  construction  of  several
operating  systems.    Salient  examples  are:  THE,  BOSS2 and VENUS
[Di68b, La75,Li72].   The semaphore approach offers great flexibility





in the definition of IPC policies.   Furtheremore, it  is  ideal  for
exploiting  the  potential  parallelism  of  the  various  processes.
Unfortunately, the very flexibility must be very  carefully  employed
to  avoid  embarrassing deadlock situations.   Proving the absence of
deadly embrace  in  such  systems  is  accomplished  by  a  stuctured
approach in the constuction of the co-operating processes.  This is a
complicated and challenging intellectual undertaking.

   A rather  different  apprroach  to  IPC  consists  in  defining  a
communications  manager  or monitor.   Interactions between processes
take the form of requests to the  monitor  to  perform  the  required
action:  usually,  the  passing  of  or  waiting for the arrival of a
message to or from another process.   The monitor can record all  the
information  needed  to define the status of the processes engaged in
communication actions.   Moreover, it can  verify  every  request  to
determine  its  propriety.   The absence of deadly embrace situations
can  be  guaranteed  by  correct  definition  of  the   communication
protocols  since  the  monitor  can  ensure  that  they be faithfully
obeyed.

   This discipline has been employed in a number of operating systems
[Wh73,Re75,Ga72,Le68,Sp69,Br70].    Its main virtue is the simplicity
afforded by handling all the communication activities in  a  uniform,
predefined  fashion.    With  the exception of TSS these systems were
designed to run on uniprocessor  hardware  [Le68].    Therefore,  the
inherent  limitation  of  serviceing  one  request at a time need not
hinder system performance.   Communication managers are essential  in
distributed  networks  where processes do not have access to a common
information storage media [Co73,He73,Cr72,Th72].

   Various  more  sophisticated  syncronisation  schemes  have   been
suggested.    They  are  intended  to  facilitate the construction of
co-operating processes by introducing constructs which are easier  to
use  than  the  bare  primitive  operations.   By  and  large,  their
implementation  is  formally  described  in   terms   of   Dijkstra's
primitives; some by means of relatively complex procedures.  Examples
of the former case are given in  [Ho74,Ca74,Va73].    In  the  latter
case,  indivisibility  of  procedure  execution  is usually left as a
problem to be solved by the operating system [Be74,Sp69].

   Users and their processes are not normally allowed  direct  access
to  IPC  primitives.    Indeed,  only  the  MULTICS  IPC design makes
provisions for user processes  to  communicate  explicitly  with  one
another.  That is to say, via interactions other than those which are
implicit in input/output functions and the sharing of  files  [Sp69].
The only exception known to the author is described in [Li72].  Venus
is an experimental  system  designed  for  the  explicit  purpose  of
supporting  the  construction  of co-operating processes.   Users are
allowed to define semaphore variables and perform modified  P  and  V
operations  on them.   No attempt is made to prevent or detect deadly
embrace situations.   Crucial system resources are made available  to
users  via well defined system procedures.   Thus, system deadlock is
prevented.    In  general,  protection  is  limited  in  VENUS.    In
particular,  user processes cannot protect their segments from access
by other processes.







1.2.- INTER USER PROCESS COMMUNICATIONS.


   Our  objective  is  to  design  Inter  User  Process Communication
mechanisms: Malleable IPC facilities allowing the support of  Virtual
Multiprocessors  for user processes.   The flexibility and efficiency
of  the  mechanisms  must  enable  users  to  exploit  the   parallel
processing capabilities of multiprocessor hardware.

   At  this  point,  it is important to establish the characteristics
and limitations of the host computer system.  The first assumption is
the  availability  of m>1 general purpose processors.   The adjective
'general purpose' denotes that each of the m  CPU'S  can,  and  will,
execute the instruction sequences of user programs.   The number n of
processes which can co-exist in the system is,  in  general,  greater
than  m.    Hence,  processor multiplexing has to be supported by the
system.   Finally, the  processors  can  only  communicate  with  one
another by virtue of their capacity to modify and examine information
contained in commonly accessible storage media.

   Complete flexibility with maximum efficiency in the  communication
mechanisms  can  only be accomplished by giving user processes direct
access  to  the  primitive  (hardware)  syncronisation  instructions.
Barring   the   hardware   implementation   of   relatively   complex
syncronisation operations,  the  cost  of  this  pseudo  solution  is
prohibitive.    It  would  enable  users to misuse the syncronisation
instructions to the point  of  rendering  the  system  useless.    An
intermediary  has  to  be  placed  between the process performing the
syncronisation operation and the  hardware  synchronising  primitive.
The  flexibility  constraint  is satisfied if the intermediary leaves
the effect of the primitive unaltered.   In spite of  the  occasional
arguments about the power of the P and V operations on semaphores, we
have chosen to implement Dijktra's primitives as  the  basis  of  the
IUPC mechanisms [Pa71,Pa75,Va73].

   It   will   become   clear  in  the  following  section  that  the
implementation of the full semaphore concept places the P and V  near
the  frontier  of non-primitive syncronisation operations.   Yet, the
concept of process suspension  implicit  in  the  P  primitive  makes
semaphores  a  comprehensive concept which is ideal in an environment
with processor multiplexing.   It is hoped  that  the  above  remarks
suffice  as  a justification for our choice in lieu of more primitive
or more elaborate alternatives.

   From efficiency  considerations  it  follows  that  suspension  of
processes   executing   P  operations  must  be  catered  for.    The
multiplexing of processors among processes requires that a  suspended
process  yield  control  of  the  CPU.   Clearly, suspended processes
cannot detect a change in the value of the semaphore when  a  certain
process  executes  a  V operation on it.   Therefore, before yielding
control of the CPU, the process must log  its  identity  in  a  queue
associated  with  the  semaphore.   A process executing a V operation
must  examine  the  contents  of  the  semaphore  queue,   direct   a
re-activation  signal to one of the blocked processes if the queue is
non-empty and re-set the value of  the  semaphore  to  allow  another
process  to enter the critical section.   In the following discussion
we assume the existence of a hardwired  indivisible  operation  which





tests and modifies the value of a single memory cell.

   The implementation of the outlined actions  must  conform  to  the
following constraints:
   i) Modification and examination of the queue's  contents  must  be
      mutually exclusive.
  ii) The queueing operation must be simultaneous with the  semaphore
      test.
 iii) Transmission of the wake up signal  and  re-activation  of  the
      receiving  process  must be simultaneous with the re-setting of
      the semaphore.

  iv) If condition iii) is violated, the re-activated process must be
      forced  to  re-initiate  the  P operation and re-setting of the
      semaphore value must precede the transmission of  the  wake  up
      signal.

   The  first  requirement  is  necessary for two reasons: To prevent
corruption of the information in the queue by more than  one  process
attempting  to  write  on  it  and  to  prevent  the  executor of a V
operation from finding inconsistent information in the queue.

   The second  constraint  allows  a  process  executing  a  P(s)  to
conclude  the  queueing  operation  if  the semaphore was in the busy
state before another process  is  able  to  perform  a  V  operation.
Otherwise,  the  following  sequence of events can occur.   Process A
tests semaphore s; before starting the queueing operation, process  B
executes  V(s).    The  empty  queue  indicates  to  B the absence of
suspended processes.   B re-sets the semaphore and A proceeds to  add
its  identity  on  the  queue.    This is a deadly embrace situation.
Process A may have to wait forever for another process to perform a V
operation on semaphore s.

   The  analysis of the third constraint requires a detailed analysis
of the inter-process signalling mechanism.  In Dijkstra's postulates,
the  re-activation  of  a  suspended process is simultaneous with the
execution of a V operation.    This  implies  that  the  re-activated
process  concludes the P operation which implies obtaining control of
the semaphore liberated by the V.   In  systems  requiring  processor
multiplexing, the actions needed to re-activate a process introduce a
delay.   The nefarious implication of the delay is  that  it  can  no
longer be assumed that the recipient of the activation signal will be
the process which succeeds in  its  claim  of  the  semaphore.    The
problem is easily exemplified in the following case.   Assume process
B is blocked by semaphore s which was set  by  process  A.    When  A
concludes execution of the critical section it examines the semaphore
queue, sends a wake up signal to A and increments  the  value  of  s.
The  delay  in  the  re-activation  of  process B is now in progress.
Process C arrives to execute the critical section.   The P  operation
finds  s>0, decrements it and allows C to enter the critical section.
Some time later A decrements s and proceeds to execute  the  critical
section. (Note that Dijkstra's definition of the P primitive does not
require the activated process to re-test the semaphore).   There  are
now two processes executing the critical section!.

   Either  of the constraints given in points iii) and iv) solves the
problem.  Conditions iv) constitute a very simple case of conditional





critical regions [Br72].   The order of events imposed in  constraint
iv)  prevents  the  deadlock  situation  which  can  be caused by the
re-activated process performing the P(s)  before  the  value  of  the
semaphore is re-set.  The implementation of the requirements given in
iii)  require  a  modification  of  the  V  operation.   Suppose  the
incrementation  of  the  semaphore is made dependent on the following
rules: If the semaphore queue is empty the value of the semaphore  is
incremented.    Otherwise,  a wake up signal is transmitted to one of
the processes in the queue and no alteration is made to the value  of
the semaphore.  This ensures the blocking of the processes attempting
to initiate a  P  operation  while  the  re-activation  delay  is  in
progress.

   In the first solution, a process may be re-activeted and scheduled
only to discover that  it  must  be  blocked  immediately  because  a
process  which  was  not in the queue already performed a P(s).   The
second solution increases the probability of processes being blocked.
However,   the  primitives  are  designed  to  be  employed  by  user
processes.  No assumptions can be made about the time required in the
execution of critical sections by user processes.  Since, in a sense,
the second solution merely increments the time taken in the execution
of  the  critical  section, it is is quite appropiate for our present
purposes.   In addition,  note  that  the  first  solution  does  not
preclude  the  possibility  of  an individual process arriving always
late at the execution of the  P  operation  and  thus  being  blocked
forever.    This  is the main motivation for our choice of the second
alternative.

   The P and V operations can now be defined formally in IMP.   Let s
be a semaphore variable and qs be a queue uniquely associated with s.
The  algorithms  for  the  implementation   of   the   syncronisation
primitives are:
   P(s) =  { if s < 1 then start
              queue up(qs,me)
              block-process(me)
           finish else s = s-1 }


   V(s) =  { if non empty(qs) then start
              id = dequeue(qs)
              wake-up-process(id)
           finish else s = s+1 }

Where me is a variable local to the executing process and it uniquely
identifies the process; id is local to the V operation; queue up  and
dequeue  are  routines which insert and remove, respectively, a value
into or from the queue and non empty  is  a  boolean  function  whose
value  is  true  iff  the queue is not empty.   The brackets indicate
indivisibility.    Finally,  block-process  and  wake-up-process  are
routines  which store the values 'blocked' and 'ready', respectively,
into a special location, the status mark, of the state  word  of  the
process  specified  in  the  parameter to the routine.   In addition,
block-process retires the processor from the executing process.

   It is important to emphasize  that  the  constraints  imposed  are
based  solely  on  deadlock  avoidance  and  preservation  of  mutual
exclusion and that they require indivisible execution from  beginning





to end in the particular implementation of the P  and  V  primitives.
This  remark  is intended to disuade the designer from the temptation
of improving the efficiency or convenience of the  implementation  by
relaxing  some  constraint  without  a  suitable  modification of the
algorithms given for the P and V  primitives.    Finally,  note  that
conditions   i),  ii),  and  iii)  or  i),  ii)  and  iv)  constitute
sufficient, not  necessary,  conditions  for  the  implementation  of
semaphores with process suspension.

   In  a  single  processor  system the indivisibility problem can be
overcome by performing all semaphore  operations  in  uninterruptible
mode.    Clearly,  the  situation  in a multiprocessor environment is
quite different.   Indivisibility must be maintained with respect  to
independently running processes.   A completely loop free solution to
the mutual exclusion problem is not possible.   In order to  avoid  a
cycle  while  the  semaphore  is  busy  it  is necessary to include a
queueing operation in the synchronising primitive.  Nevertheless, the
queueing  operation itself must be implemented as a critical section.
Thus, entry to a critical section must be  protected  by  a  critical
section.

   The  above  loose usage of the terms loop and cycle is intended to
include hardware imposed delays such as the PRO instruction  and  the
Pseudo Interrupt Device described in [He73].

   Indivisibility  can be implemented by means of a hardware test and
set istruction described in section 1.1.   A  sequence  of  logically
indivisible   actions  can  be  surrounded  by  the  TS  forcing  the
contending processes to cycle until one concludes  execution  of  the
indivisible  sequence.   Thus, any sequence of actions encircled by {
and } can be made logically indivisible by substituting:
   { = label: [ if CYS < 1 then -> label ; CYS = CYS-1 ]
   } = [ CYS = CYS+1 ]
   where   the   square   brackets   indicate   hardware  implemented
indivisibility and CYS is a 'cycling semaphore': An integer  variable
initialised   to   zero   which  is  associated  locally  with  every
indivisible sequence of operations; i. e. with every  instance  of  a
semaphore proper.   It is vitally important to note that the use of a
cycling semaphore as described above demands that  the  block-process
routine  in  the  previous  algorithm  be  combined  with  the re-set
(CYS=CYS+1) of the cycling semaphore.

   This mode of implementing indivisibility is as reasonable  as  any
delay  imposed  by  hardware  on the contending processors.   In both
cases,  processors  are  prevented  from  performing   useful   work.
Furthermore,  both  cases  require  a mechanism to guarantee that the
delay be short. i. e. that  the  sequence  of  logically  indivisible
operations  be  executed  quickly.    Finally,  the cycling semaphore
approach  allows  to  discriminate  between   logically   independent
sequences,  that  is to say, only the processors competing for access
to  a  particular  indivisible  sequence   are   forced   to   cycle.
Unfortunately,  it  is impractical to envisage allocating the cycling
semaphore in one memory bank and the rest of the  data  structure  in
another.    Consequently, all the processors attempting to access the
same semaphore will be stealing memory cycles from the member of  the
group  whose  useful  work is a pre-requisite for the progress of the
other processors.   Where memory interleaving  is  available,  memory





contention is reduced by a factor of two.   A hardware  mechanism  to
avoid memory cycle stealing by waiting processors is proposed below.

   It is imperative to minimise useless cycling time by ensuring that
the logically indivisible sequence be performed rapidly.    Since  we
cannot  improve  on  processor  speed, uninterrupted execution of the
sequence is required.   This can be accomplished by  microprogramming
of   the   synchronising   primitives  or  performing  all  semaphore
operations via supervisor calls.   The  latter  alternative  must  be
rejected  on  the  basis  that  it  can  be  the  cause  of excessive
contention  in  operating  system   calls.     Microprogramming   the
operations  is  not enough to solve the protection problems discussed
in section 1.4.

   We now present algorithms for the implementation of the  P  and  V
operations  which  allow  the  execution of a significant part of the
synchronising primitives without the need to implement indivisibility
of a physically divisible sequence.

   The  semaphore  proper, s, is no longer a non-negative integer; it
can also adopt negative values.    In  addition,  a  further  cycling
semaphore  called NUMQPR is required; its utility is discussed below.
The initial value of NUMQPR is zero.   The following constraints  are
forced on the algorithms:
   I) The test and modification  of  the  semaphore  proper  must  be
      performed simultaneously.
  II) Modification or examination of the semaphore information stored
      in the queue must be mutually exclusive.

   The synchronisation primitives are:

 P(s) =   [ s = s-1 ; if s < 0 then -> l1 ]

    critical section:

             .
             .
             .

        l1: [ if CYS < 1 then -> l1 ; CYS = CYS-1 ]

           queue up(qs,me)
           [ NUMQPR = NUMQPR+1 ]
           [ CYS = CYS+1 ]
           block-process(me)
           -> critical section
           and
 V(s) =   [ s = s+1 ; if s <= 0 then -> l2 ]

             .
             .
             .

       l2: [if NUMQPR<1 then -> l2 ; NUMQPR=NUMQPR+1]
       l3: [ if CYS < 1 then -> l3 ; CYS = CYS-1 ]
           id = dequeue(qs)
           wake-up-process(id)





           [ CYS = CYS+1 ]
           -> instruction following the V



   The  above  algorithms have an interesting property: They allow to
perform the semaphore  proper  test  independently  of  the  queueing
operations.

   It  is  easier  to  visualise  the significance of the property by
looking at the -> label of  the  semaphore  proper  test  as  a  high
priority  interrupt to that label.   The (hardware implemented) first
instruction of the P(s) and V(s)  can  be  performed  in  user  mode.
Thereafter,  the  system  is  in charge of ensuring that the queueing
operations are performed in uniterruptible mode.  This is intended to
reduce  the  waiting  time  on the cycling semaphore CYS used only to
implement indivisibility in the queueing operations and  the  cycling
semaphore  NUMQPR which ensures that the processes enter the critical
section protected by CYS in the appropiate order.

   Because indivisibility is broken momentarily after the first  part
of  the  P  or  V  operation has been executed, it is not possible to
guarantee the order of arrival at the second part of the  algorithms.
NUMQPR ensures that the process which executes the second part of the
V will find an entry in the semaphore queue.  It is important to note
that  the  cycling  test  of  NUMQPR  need  not  delay  the executing
processor any more than the indispensable cycling  semaphore  CYS  in
this and the previous algorithm.  The reason is that the value of the
semaphore proper tells the process which performs the  V  that  there
has  to  be  a  process in the queue; if it is not there yet, it will
arrive as soon as the process which executed the corresponding  P  is
able to complete its high priority interrupt routine: the second part
of the V operation.

   The second parts of the P and V primitives are, respectively,  the
producer/consumer algorithms proposed by Dijkstra [Di68].

   Memory cycle steeling by cycling processors can be aliminated with
the use of the following  mechanism.    Consider  including  a  small
associative  memory  (AM)  of  n  entries,  n  being  the  number  of
processors, in the memory access unit.   An associative memory  entry
is of the form:
        processor number , absolute address
A processor requests a TS operation from the memory access unit.   If
the value contained in the addressed location  is  zero,  the  memory
access  unit  simply stores the corresponding pair in the associative
memory.  Conversely, when a release operation ( e. g. [CYS=CYS+1]) is
requested  by a processor, the unit consults the AM.   If a processor
is held up on that particular location, it is allowed to proceed  and
the  value  of the memory cell is not altered; otherwise the value is
incremented as usual.   When more than one processors are waiting for
the  same  address,  the  memory access unit may select one in a fifo
manner or according to a fixed  priority  related  to  the  processor
number.  In the former case, many synchronisation algorithms could be
simplified [Co71].  In the latter, programers are forced to treat the
TS  and  release  operations  as  if  selection took place at random.
However, it is important to note that programming errors could  cause





a processor to wait forever whereas, if selection  were  in  fact  at
random, the error might remain undetected.

   The  algorithms provide an important gain in efficiency when the P
operation finds the semaphore in the free state or the V discovers an
empty  queue.    In  those cases, the complete primitives are in fact
elementary operations requiring only two memory cycles.  The solution
is  only  valid  when  the 'size' of the critical section is unknown.
This is precisely the case we are dealing with.   Note that it is not
possible  to estimate the execution time of the critical section even
if it were implemented  as  a  supervisor  call  to  be  executed  in
uninterruptible  mode.    The  reason  is that, when the semaphore is
free, an external interrupt can occur immediately after completion of
the  first  instruction  in  the P operation.   The solution requires
three easy to implement hardware indivisible  operations  similar  to
those encountered in current architectures [Bl67,St67].

   A  final  remark.    In  contrast  with  the first algorithms, the
block-process(me) request of the P operation is performed outside the
critical  section protected by CYS.   Therefore, it is possible for a
wake-up-process signal directed to a given process  to  arrive  shile
the   process   is   still   active;  that  is,  before  it  executes
block-process(me).   The discrepancy  can  be  adjusted  by  using  a
wake-up  waiting switch in conjunction with a status mark in order to
determine  the  true  status  of  processes  [La68].    The  detailed
discussion  of  the  problem  is  postponed  until chapter 4, where a
detailed definition of the characterisation of processes and the form
of the scheduling algorithms will be available.


































1.3.- THE DEADLOCK PROBLEM.



   As a  by  product  of  mutual  exclusion,  indescriminate  use  of
syncronisation  primitives  can  easily  lead to deadlock situations.
Consequently, one of  the  most  important  aspects  of  the  use  of
syncronisation mechanisms is the deadlock problem.   A detailed study
of the problem, its causes, detection and prevention  is  beyond  the
scope of this work.  Literature on the subject is abundant.  Numerous
articles include the formal treatment of proving  or  disproving  the
correctness   of   programs   employing   syncronisation   primitives
[Gi72,Ll73,Ha72]; the structured  approach  to  the  construction  of
co-operating  processes  to  reduce  the  likelyhood  of encountering
deadly embrace situations [Di68a,Di72,Ho75,Ca74]  and  the  detection
and  prevention  of  deadlock  based  on  certain  assumptions on the
behaviour  of  processes  [Ha69,Co71,Ho72].   Several  of  the  cited
references  contain  extensive  bibliographies  on  the  topic.   The
intention of this section is to identify the  problems  arising  with
the  misuse of syncronisation primitives and to lay out the necessary
requirements to empower the system to remedy the ensuing situations.

   System deadlocks must be avoided by proving the absence of  deadly
embrace situations in those syncronisation activities in which system
processes are involved.  Essentially, this is accomplished in current
systems  by  showing  the correctness of the operating system process
structure  and  relying  on  the  correct  implementation  of  system
programs  [Di68b,La75,Li72,Re75].    In  addition,  system  processes
employ a variety of algorithms to determine the safeness of  granting
physical  resources  to  user  processes  [Ha69].    Short of proving
program correctness, the absence of  deadlock  in  user  defined  and
implemented  communication  and  syncronisation  protocols  cannot be
guaranteed  [Gi72,Ha72].    Unfortunately,  the  state  of  the   art
precludes proving the correctness of user programs.

   As  a  practical compromise, we propose to allow the occurrence of
deadlock in the interactions between user processes, detect them when
they take place and effect the necessary corrective actions.

   The system must have the following characteristics:
     a) Deadlock in communicating  user  processes  affect  only  the
        processes involved in the communications.
     b) The effect of deadly embrace  situations  on  overall  system
        performance must be well within an acceptable threshold.
     c) System detection of deadlock situations must be  possible  in
        order  to  produce  diagnostic  messages  and take corrective
        action.

   It follows from the above  requirements  that  physical  resources
must  be  controlled  by  well  defined  system  processes  and  that
syncronisation between system and  user  processes  must  take  place
through  well  defined protocols implemented by protected procedures.
Syncronisation  primitives  are  not  intended  to  give  users   the
authority  to manage physical resources.   Their purpose is to enable
user processes to co-operate in the handling of resources the use  of
which has been authorized by the system.  The first constraint can be
satisfied  by  a  careful  structuring  of  the   system   processes.





Similarly, the second condition can be  accomplished  by  a  suitable
design of resource management policies.

   Semaphores can be viewed as controllers of logical resources.  The
execution of a P(s) can be interpreted as a request by the  executing
process  to  obtain the resource controlled by s.   Similarly, a V(s)
can be considered as a means for a process to  release  the  resource
protected  by  the semaphore.   Deadlock detection can be achieved by
constructing directed graphs which model the status of  availablility
of  resources  in  the  system.   Certain  conditions  in  the  graph
determine that a deadlock situation has occurred [Co71,Ho72].

   Holt has introduced a distinction  in  types  of  resources  which
mimics the different usage of semaphores [Ho72].   Reusable resources
can be equated with critical sections and consummable resources  have
the  same  characteristics  as  events  or  messages.   The  apparent
drawback of Holt's algorithms for deadlock detection is that in order
to maintain the resource graph, the different types of resources must
be identified a priori.   The implication is  that  user's  processes
(which  are  executing  user  programs) must correctly declare to the
deadlock detecting mechanism their intended usage of the  semaphores.
Failure to do so can cripple the deadlock detecting algorithms in the
sense that it might find nonexisting  deadly  embrace  situations  or
miss existing ones.

   Deadlock  detection  has  to rely on a certain knowledge about the
behaviour of the co-operating processes.   This is easily depicted by
a simple example.   Assume a set of processes is blocked by semaphore
s.   It is impossible to know if the set of processes  is  deadlocked
without knowing whether or not another process, say C, is expected to
perform a V(s) at al later time.   Assume it is known that C  intends
to execute a V(s).  If , due to a programming error, C never performs
the  V  operation,  there  exists  a  deadlock  situation  which   is
undetectable as long as C is not permanently blocked.

   In  summary,  it  is  always  possible  to  misuse  syncronisation
primitives to the  point  of  creating  undetectable  deadly  embrace
situations.     Therefore,  the  third  constraint  cannot  be  fully
satisfied.   The system can only trust that users are  not  malicious
and hope that errors do not cause unidentifiable deadlocks.  Deadlock
detection becomes a valuable diagnostic tool for  user  owned  pseudo
co-operating processes: Processes which fail to co-operate due to non
intentional errors.   It is also useful from the  system's  viewpoint
since  it  allows  the  detection  of a variety of harmful situations
which deteriorate system performance.   In  addition,  ad  hoc  rules
based on blocked time must be imposed.

   Together  with  the  information  about  the intended usage of the
synchronising primitives, the construction of the resource  graph  is
based on the requests and releases of resources by processes.  In the
case of semaphores, the history of resource  usage  is  held  in  the
semaphore  queues.   Clearly,  the  information  is  crucial  to  the
deadlock detecting algorithms.









1.4.- PROTECTION.


   The  discussion  of  the present section is based on the following
obvious  fact:  The  incorruptibility  of  the  syncronisation   data
structures  is  an  indispensable  condition  for  the syncronisation
primitives  to  function  correctly.   This  observation  places  the
protection  requirements  for the purposes of deadlock detection in a
poor second place.

   Note that the syncronisation data structures must be  read  /write
accessible  to the processes engaged in the communication activities.
At the same time, the system must ensure that access be  confined  to
the execution of the P and V primitives.  Clearly, failure to enforce
the second constraint could allow a number of  disastrous  situations
such  as  corruption  of  semaphore  queues and misuse of the process
identifiers contained therein.    Also,  the  right  to  execute  the
block/wake  up  functions  must be restricted to the execution of the
syncronisation primitives and be, in a sense,  directly  availabe  to
user processes.

   An  important  aspect  which  has  not  yet  been discussed is the
interaction between the syncronisation primitives  with  the  process
scheduler.  That is to say, a precise definition of the block/wake up
functions implicit in the P and V operations.  Again, these functions
are conventionally implemented by system programs which are ivoked by
users through supervisor calls (SVC).   The desirability of  avoiding
SVC's  in the execution of syncronisation primitives has been pointed
out.   Although the  block/wake  up  functions  need  not  always  be
executed  as  part of the P and V operations, avoidance of SVC's only
in the case when the semaphore is free or the queue is empty is  only
a minute improvement over performing the complete P or V operation in
supervisor mode.   Allowing  user  processes  to  interact  with  the
process  scheduler  without supervisor intervention demands stringent
protection requirements.

   It is necessary to devise protection  mechanisms  which  permit  a
finer  grade  of  access  control  than that afforded by conventional
architectures.   The next two chapters are devoted to  the  study  of
capability  based protection mechanisms intended to create a suitable
framework for the support of IUPC mechanisms.
















