=                                                                   =















                              CHAPTER 1











                    THE SYNCHRONISATION PROBLEM.





































1






=                                                                   =





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



2






=                                                                   =





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.



































3






=                                                                   =





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



4






=                                                                   =





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



5






=                                                                   =





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.



6






=                                                                   =





   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



7






=                                                                   =





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



8






=                                                                   =





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



9






=                                                                   =





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



10






=                                                                   =





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.

















11






=                                                                   =





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.



12






=                                                                   =





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.



13






=                                                                   =





   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.



14






=                                                                   =





   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



15






=                                                                   =





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)



16






=                                                                   =





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



17






=                                                                   =





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



18






=                                                                   =





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



19






=                                                                   =





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:















20






=                                                                   =





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





21






=                                                                   =





   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.





22






=                                                                   =





   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



23






=                                                                   =





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.

















24






=                                                                   =





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



25






=                                                                   =





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.



26






=                                                                   =





   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



27






=                                                                   =





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.



















28






=                                                                   =





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



29






=                                                                   =





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.





































30






