$A MARK=1
$A PAGENO=12


$A LEFT=0; LINE=69; PAGE=57
$A TOP=4; BOTTOM=9
$A NLS=2
$A TAB=1,7,13,19,25
$A TAB=4,7,10,13,16,19
$B5
$L1 CM
CHAPTER 1
$B5
$L1 CM
THE SYNCHRONISATION PROBLEM.
$N
$L1 C
1.0.- INTRODUCTION.
$P3
@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.
$P
@IT IS APPROPIATE TO BEGIN WITH AT LEAST AN INFORMAL DEFINITION OF
THE TERMINOLOGY EMPLOYED.
$P
@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.
$P
@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.
$P
@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.
$N
$L1 C
1.1.- OVERVIEW OF SYNCRONISATION PRIMITIVES.
$P3
@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].
$P
@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].
$P
@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].
$P
@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.
$P
@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]:
$A INDENT=1
@P(S) = [ %IF S < 1 %THEN $. $. $.  ; S = S-1 ]
$B0
AND
$B0
@V(S) = [S=S+1].
$A INDENT=0
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.
$P
@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!.
$P
@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:
$A INDENT=1
@T@S(S) = LABEL: [ %IF S < 1 %THEN -> LABEL ; S = S-1 ]
$A INDENT=0
$P
@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.
$P
@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.
$P
@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 @P@R@OTECT. @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.
$P
@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.
$P
@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:
$A INDENT=1
%WITH V %DO CR ;
$A INDENT=0
@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:
$A INDENT=1
$C+4 %WHEN B %DO
$B0
%BEGIN
$B0
$A NLS=1
$C+2 $.
$B0
$C+2 $.
$B0
$C+2 $.
$B
%END ;
$A INDENT=0
$A NLS=2
$B0
@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:
$A INDENT=1
%SIGNAL(V)
$A INDENT=0
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.
$P
@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.
$P
@HABERMAN'S SIGNAL(S)/WAIT(S) PRIMITIVES ARE VERY SIMILAR IN
CONCEPT TO @DIJKSTRA'S @P AND @V [@HA72].
$P
@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.
$P
@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.
$P
@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].
$P
@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].
$P
@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.
$N
$L1 C
1.2.- INTER USER PROCESS COMMUNICATIONS.
$P2
@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.
$P
@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.
$P
@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].
$P
@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.
$P
@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.
$P
@THE IMPLEMENTATION OF THE OUTLINED ACTIONS MUST CONFORM TO THE
FOLLOWING CONSTRAINTS:
$A INDENT=2
$C-3 I) @MODIFICATION AND EXAMINATION OF THE QUEUE'S CONTENTS MUST BE
MUTUALLY EXCLUSIVE.
$B0
$C-4 II) @THE QUEUEING OPERATION MUST BE SIMULTANEOUS WITH THE
SEMAPHORE
TEST.
$B0
$C-5 III) @TRANSMISSION OF THE WAKE UP SIGNAL AND RE-ACTIVATION OF
THE
RECEIVING PROCESS MUST BE SIMULTANEOUS WITH THE RE-SETTING OF
THE SEMAPHORE.
$B
$C-4 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.
$A INDENT=0
$P
@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.
$P
@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.
$P
@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!.
$P
@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.
$P
@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.
$P
@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:
$A TEMPA=TAB; TAB=4,12,15,18,21,24,27
$A INDENT=2
$T1 @P(S) = $T2 ${ %IF S < 1 %THEN %START
$A INDENT=3
QUEUE UP(QS,ME)
$B0
BLOCK-PROCESS(ME)
$B0
$A INDENT=2
%FINISH %ELSE S = S-1 $}
$B2
$T1 @V(S) = $T2 ${ %IF NON EMPTY(QS) %THEN %START
$A INDENT=3
ID = DEQUEUE(QS)
$B0
WAKE-UP-PROCESS(ID)
$A INDENT=2
%FINISH %ELSE S = S+1 $}
$A INDENT=0; TAB=TEMPA
$B1
@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.
$P
@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.
$P
@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.
$P
@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].
$P
@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:
$V3
$A INDENT=1
{ = LABEL: [ %IF .CYS < 1 %THEN -> LABEL ; .CYS = .CYS-1 ]
$B0
} = [ .CYS = .CYS+1 ]
$A INDENT=0
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.
$P
@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.
$P
@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.
$P
@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.
$P
@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:
$A INDENT=2
$C-3 .I) @THE TEST AND MODIFICATION OF THE SEMAPHORE PROPER MUST BE
PERFORMED SIMULTANEOUSLY.
$B0
$C-4 .II) @MODIFICATION OR EXAMINATION OF THE SEMAPHORE INFORMATION
STORED
IN THE QUEUE MUST BE MUTUALLY EXCLUSIVE.
$A INDENT=0
$P
@THE SYNCHRONISATION PRIMITIVES ARE:
$B
$A TAB=6,9,12,15,18,21
$A INDENT=2; NLS=1
$V25
$C-7 @P(S) = $C+3 [ S = S-1 ; %IF S < 0 %THEN -> L1 ]
$B
$C-4 CRITICAL SECTION:
$B
$C+5 $.
$B0
$C+5 $.
$B0
$C+5 $.
$B
L1: [ %IF .CYS < 1 %THEN -> L1 ; .CYS = .CYS-1 ]
$B
$A INDENT=3; NLS=2
QUEUE UP(QS,ME)
$B0
[ .NUMQPR = .NUMQPR+1 ]
$B0
$B0


[ .CYS = .CYS+1 ]
$B0
BLOCK-PROCESS(ME)
$B0
-> CRITICAL SECTION
$A INDENT=0
AND
$A INDENT=2; NLS=1
$C-7 @V(S) = $C+3 [ S = S+1 ; %IF S <= 0 %THEN -> L2 ]
$B
$C+5 $.
$B0
$C+5 $.
$B0
$C+5 $.
$A INDENT=3; NLS=2
$B
$C-4 L2: [%IF .NUMQPR<1 %THEN -> L2 ; .NUMQPR$=NUMQPR+1]
$B0
$C-4 L3: [ %IF .CYS < 1 %THEN -> L3 ; .CYS = .CYS-1 ]
$B0
ID = DEQUEUE(QS)
$B0
WAKE-UP-PROCESS(ID)
$B0
[ .CYS = .CYS+1 ]
$B0
-> INSTRUCTION FOLLOWING THE @V
$A INDENT=0
$P3
@THE ABOVE ALGORITHMS HAVE AN INTERESTING PROPERTY: @THEY ALLOW TO
PERFORM THE SEMAPHORE PROPER TEST INDEPENDENTLY OF THE QUEUEING
OPERATIONS.
$P
@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.
$P
@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.
$P
@THE SECOND PARTS OF THE @P AND @V PRIMITIVES ARE, RESPECTIVELY, THE
PRODUCER/CONSUMER ALGORITHMS PROPOSED BY @DIJKSTRA [@DI68].
$P
@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:
$B0
$T2 PROCESSOR NUMBER , ABSOLUTE ADDRESS
$B0
@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.
$P
@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].
$P
@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.
$N
$L1 C
1.3.- THE DEADLOCK PROBLEM.
$P3
@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.
$P
@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.
$P
@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.
$P
@THE SYSTEM MUST HAVE THE FOLLOWING CHARACTERISTICS:
$A INDENT=2
$B0
$C-3 A) @DEADLOCK IN COMMUNICATING USER PROCESSES AFFECT ONLY THE
PROCESSES INVOLVED IN THE COMMUNICATIONS.
$B0
$C-3 B) @THE EFFECT OF DEADLY EMBRACE SITUATIONS ON OVERALL SYSTEM
PERFORMANCE MUST BE WELL WITHIN AN ACCEPTABLE THRESHOLD.
$B0
$C-3 C) @SYSTEM DETECTION OF DEADLOCK SITUATIONS MUST BE POSSIBLE IN
ORDER TO PRODUCE DIAGNOSTIC MESSAGES AND TAKE CORRECTIVE
ACTION.
$A INDENT=0
$P
@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.
$P
@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].
$P
@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.
$P
@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.
$P
@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.
$P
@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.
$N
$L1 C
1.4.- PROTECTION.
$P2
@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.
$P
@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.
$P
@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
@S@V@C'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 @S@V@C'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.
$P
@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.
$E