$A MARK=1
$A PAGENO=144


$A LEFT=0; LINE=69; PAGE=57
$A TOP=4; BOTTOM=9
$A NLS=2
$A TAB=1,7,13,19,25
$B5
$L1   CM
CHAPTER 4
$B5
$L1 CM
PROTECTED INTER-PROCESS SYNCHRONISATION.
$N
$L1 C
4.0- INTRODUCTION.
$P3
@THE COMMUNICATION BETWEEN PROCESSES CAN TAKE PLACE VIA THE
INTERCHANGE OF MESSAGES DEPOSITED WITHIN SHARED OPERAND OBJECTS. @THE
SYNCHRONISATION ACTIVITIES REQUIRED TO EFFECT THE COMMUNICATIONS CAN
BE ACCOMPLISHED VIA OBJECTS OF THE SEMAPHORE TYPE. @THE COST OF
PROVIDING SYNCHRONISING PRIMITIVES COMES FROM THE NEED TO SUPPLY
FOOLPROOF MECHANISMS TO PROTECT THE SYNCHRONISATION DATA STRUCTURES
AND TO ENSURE THAT THE SYSTEM'S ABILITY TO DETECT DEADLY EMBRACE
SITUATIONS CANNOT BE OBSTRUCTED.
$P
@WE BEGIN THE PRESENT CHAPTER WITH A DISCUSSION OF THE
CHARACTERISATION OF PROCESSES AND THE DEFINITION OF OPERATORS NEEDED
TO SUPPORT THE INTERACTIONS BETWEEN THEM. @IN SECTION 4.2 WE EXPLORE
THE INTEGRATION OF THE SYNCHRONISING PRIMITIVES WITH PROCESS
SUSPENSION AND RE-ACTIVATION. @SPECIFICALLY, WE WILL FILL THE GAPS
LEFT BY THE LOOSE DEFINITION OF THE WAKE-UP-PROCESS AND
SUSPEND-PROCESS META INSTRUCTIONS EMPLOYED IN THE BODIES OF THE @P
AND
@V OPERATIONS DISCUSSED IN CHAPTER 1. @IN SECTION 4.3 WE IDENTIFY A
FURTHER PROBLEM WHICH MUST BE SOLVED BY THE PROTECTION MECHANISM: @A
PROCESS SHOULD NOT ENJOY THE UNRESTRICTED PRIVILEGE OF TRANSMITTING
CAPABILITIES TO OTHER PROCESSES.
$P
@A FEATURE WHICH WILL BE APPARENT THROUGHOUT THE DISCUSSIONS IS A
DESIRE TO DISTRIBUTE SYNCHRONISATION OPERATIONS IN SPACE. @IN OTHER
WORDS, WE WILL CONSTANTLY ATTEMPT TO AVOID SYNCHRONISING CONFLICTS
OCCASIONED BY IMPLEMENTATION DECISIONS.
$N
$L1 C
4.1.- THE PROCESS TYPE.
$P3
@THE @I-SEG AND @P-SEG OF AN OPERATOR, TOGETHER WITH THE PORTION OF
THE @S-SEG ASSIGNED BY THE .INVOKE MECHANISM AND THE SET OF PROCESSOR
REGISTERS DELIMIT THE INSTANTANEOUS ENVIRONMENT OF EXECUTION OF A
PROCESS. @MOREOVER, EVERY PROCESS IS BOUND TO ONE AND ONLY ONE
OPERATOR AT ANY GIVEN TIME. @IT FOLLOWS THAT THE CAPABILITIES FOR THE
TOTALITY OF OBJECTS WHICH A PROCESS WILL BE ABLE TO ACCESS DURING ITS
LIFE-TIME MUST BE PRESENT IN THE ENVIRONMENT OF EXECUTION OF THE
OPERATOR TO WHICH THE PROCESS IS BOUND INITIALLY.
$P
@THE ABOVE STATEMENT IS NOT STRICTLY TRUE SINCE IT IS POSSIBLE FOR
A PROCESS TO AUGMENT ITS ENVIRONMENT BY INVOKING OPERATORS WHICH
CREATE NEW OBJECTS OR BY OBTAINING CAPABILITIES FOR EXISTING OBJECTS
VIA INTERACTIONS WITH OTHER PROCESSES. @NEVERTHELESS, BOTH ACTIVITIES
REQUIRE CAPABILITIES WHICH ARE EXTANT IN THE INITIAL ENVIRONMENT OF
THE PROCESS. @IN THIS SENSE, THE INITIAL PROTECTION REGIME OF EVERY
PROCESS ALSO DELIMITS THE POTENTIAL INCREASE OF ITS ADDRESS SPACE.
$P
@WHEN A PROCESS INVOKES AN EXTENDED OPERATOR THE PROTECTION
MECHANISM SAVES THE STATE OF THE CURRENT OPERATOR'S ENVIRONMENT BY
MEANS OF STORING THE CAPABILITIES FOR THE @I-SEG AND @P-SEG, RETURN
ADDRESS ETC. WITHIN THE @S-SEG. @CONSEQUENTLY, THE STATE WORD OF THE
PROCESS IS COMPLETELY CHARACTERISED BY INFORMATION CONTAINED IN THE
REPRESENTATIONS OF OBJECTS WHOSE CAPABILITIES RESIDE WITHIN THE
PROCESS CAPABILITY STACK: THE @S-SEG. @OF COURSE, WE ASSUME THAT THE
PROCESSOR REGISTERS ARE AN EXTENSION OF THE PROCESS' @S-SEG. @THIS
ALLOWS THE DEFINITION OF A PROCESS AS AN OPERAND OBJECT OF TYPE
'PROCESS' WHOSE REPRESENTATION IS THE @S-SEG ASSOCIATED WITH THE
PROCESS IN QUESTION.
$P
@THE MANAGEMENT OF PROCESSES DEMANDS A COLLECTION OF MISCELLANEOUS
OBJECTS WHICH CONTAIN INFORMATION SUCH AS TIMERS, ACCOUNTING TABLES,
STATUS (RUNNING, BLOCKED, ETC.) AND SO ON. @THE CAPABILITIES
CORRESPONDING TO THESE VARIOUS OBJECTS ARE JOINED TO THE CAPABILITY
FOR THE @S-SEG TO CONSTRUCT THE REPRESENTATION OF AN OPERAND OBJECT
OF
TYPE 'PROCESS' AS SHOWN IN FIGURE 4.1-1. @THUS, AN OPERAND OF TYPE
PROCESS COMPRISES THE CONGLOMERATION OF INFORMATION NEEDED BY THE
SYSTEM TO ADMINISTER THE PROCESS IN ADDITION TO THE STATE WORD OF THE
PROCESS CHARACTERISED BY AN @S-SEG.
$V0
$P
@CONCEPTUALLY, EVERY PROCESS MANAGER, AN INDEPENDENT SYSTEM
PROCESS, POSSESSES THE CAPABILITY FOR THE PROCESS ON BEHALF OF WHOM
IT WILL PERFORM SOME SERVICE. @THUS, THE SERVICES FURNISHED BY THE
OPERATING SYSTEM ARE EXPRESSED IN A UNIFORM FASHION IN TERMS OF
OPERATIONS ON OBJECTS OF TYPE PROCESS. @THIS IMPLIES THAT, WHEN A
PROCESS MANAGER IS BOUND TO ONE OF THE OPERATORS OF TYPE PROCESS, IT
HAS THE POWER TO MANIPULATE THE @S-SEG. @CLEARLY, THIS EXCESSIVE
POWER
SHOULD BE DIMINISHED; THE SITUATION IS DANGEROUSLY SIMILAR TO THE
PRIVILIEGED/NORMAL EXECUTION MODES OF CONVENTIONAL MACHINES. @IN
PRACTICE, A PROCESS MANAGER IS PROVIDED ONLY WITH THE CAPABILITY FOR
THE COMPONENT OF THE REPRESENTATION OF THE PROCESS WHICH IS RELEVANT
TO THE SERVICE IT PROVIDES. @BY MEANS OF THIS SHORTCUT, THE POWER OF
SYSTEM PROCESSES IS CONFINED AND EFFICIENCY IS ENHANCED BY AVOIDING
THE OVERHEAD OF INVOKING AN EXTENDED OPERATOR OF TYPE PROCESS. @A
DIFFERENT APPROACH TO ACHIEVE THE SELECTIVE PROTECTION IS TO DEFINE
THE @S-SEG COMPONENT OF A PROCESS AS THE REPRESENTATION OF AN
EXTENDED
OBJECT, SAY .XS. @AMONGST THE OPERATORS OF TYPE PROCESS, ONLY THOSE
WHICH NEED TO MANIPULATE THE @S-SEG; E. G. OPERATORS CONCERNED WITH
PROCESS SWITCHING, POSSESS CAPABILITIES FOR THE OPERATORS OF TYPE .XS.
@CLEARLY, THE SECOND ATTITUDE INTRODUCES DISPROPORTIONATE OVERHEADS;
NONETHELESS, WE WILL PERSIST IS DESCRIBING OPERATIONS ON PROCESSES
WITH COMPLETE DISRAGARD OF EFFICIENCY CONSIDERATIONS.
$P
@AT LEAST FOUR OPERATORS OF TYPE PROCESS ARE NEEDED; THESE ARE:
CREATE-PROCESS, DESTROY-PROCESS, START-PROCESS AND RESUME-PROCESS.
$P
@CREATE-PROCESS IS IN CHARGE OF CREATING THE STRUCTURE DEPICTED IN
FIGURE 4.1-1. @THE INITIAL ENVIRONMENT OF THE NEW PROCESS CONSISTS OF
AN OPERAND OBJECT, A DICTIONARY, CONTAINING THE SET OF CAPABILITIES
WHICH THE NEW PROCESS IS ENTITLED TO ACCESS. @THE CAPABILITY FOR THE
DICTIONARY IS PASSED AS PARAMETER TO CREATE-PROCESS BY ITS CALLER.
@THE CAPABILITY FOR THE DICTIONARY WILL ALSO BE PASSED AS PARAMETER
TO
THE FIRST OPERATOR WHICH THE NEW PROCESS WILL INVOKE. @IN ADDITION,
CREATE-PROCESS SELECTS THE FIRST OPERATOR OF THE NEW PROCESS
ACCORDING TO THE CATEGORY OF THE LATTER. @FOR EXAMPLE, THE FIRST
OPERATOR OF A PROCESS CREATED ON BEHALF OF AN INTERACTIVE USER CAN BE
THE SYSTEM OPERATOR 'COMMAND INTERPRETER'. @THE DESTROY-PROCESS
OPERATOR IS THE INVERSE OF CREATE-PROCESS.
$P
@THE REMAINING OPERATORS ARE NECESSARY FOR PROCESSOR MULTIPLEXING.
@START-PROCESS INITIATES EXECUTION OF THE DESIGNATED PROCESS BY MEANS
OF FORCING IT TO .INVOKE ITS FIRST OPERATOR. @RESUME-PROCESS IS USED
TO ALLOCATE A PROCESSOR TO A PROCESS WHICH HAD BEEN STARTED, THEN
SUSPENDED AT EARLIER TIMES.
$P
@FIRSTLY, WE WILL DISCUSS TWO ISSUES WHICH ARE INTIMATELY RELATED:
THE OWNERSHIP AND CONTROL OF OPERAND OBJECTS OF TYPE PROCESS;
BRIEFLY, PROCESSES. @IN OTHER WORDS, WE ARE INTERESTED IN OBSERVING
THE IMPLICATIONS OF THE UTILISATION OF THE FOUR OPERATORS OF TYPE
PROCESS.
$P
@FOR MOST PRACTICAL PURPOSES, AN OBJECT'S OWNER CAN BE DEFINED AS
THE AGENT WHICH CAUSES THE CREATION OF THE OBJECT: THE PROCESS WHICH
INVOKES THE OPERATOR WHICH CREATES A NEW INSTANCE OF AN OBJECT AND
RETURNS TO ITS CALLER A CAPABILITY FOR THE NEW OBJECT. @ASSUMING THAT
THE OWNER OF AN OPERAND OBJECT OF A GIVEN TYPE POSSESSES A SUFFICIENT
SET OF CAPABILITIES FOR OPERATORS OF THAT TYPE, IT IS ABLE
SUBSEQUENTLY TO EXECUTE OPERATIONS ON THAT OBJECT. @IN THIS SENSE,
THE OWNER HAS CONTROL OVER THE OWNED OBJECT. @IN PARTICULAR, THE
OWNER OF AN OBJECT HAS THE RIGHT TO DISTRIBUTE COPIES OF ITS
CAPABILITY TO OTHER PROCESSES. @AS A CONSEQUENCE, AN OPERAND OBJECT
MAY BE THE SUBJECT OF THE CONCURRENT EXECUTION OF SEVERAL OPERATORS.
$P
@FIRST OF ALL WE IMPOSE ONE RESTRICTION ON OPERAND OBJECTS OF TYPE
PROCESS: @OPERATIONS ON A PARTICULAR INSTANCE OF AN OPERAND OF THE
PROCESS TYPE MUST BE MUTUALLY EXCLUSIVE. @THE RESTRICTION IS
NECESSARY TO EXCLUDE THE OTHERWISE POSSIBLE CIRCUMSTANCE IN WHICH A
PROCESS EXECUTES ON MORE THAN ONE PROCESSOR. @THE RESTRICTION IMPLIES
THAT A PROCESS CANNOT ACT AS THE SCHEDULER OF VARIOUS PROCESSORS.
@THE MECHANISMS TO ENFORCE THE RESTRICTION ARE DISCUSSED BELOW. @FOR
THE TIME BEING, LET US ASSUME THAT THE CAPABLILITY FOR A GIVEN
INSTANCE OF A PROCESS IS UNIQUE.
$P
@ALTHOUGH PROCESSES CAN BE DEFINED AS SYSTEM OBJECTS, THERE ARE
SEVERAL REASONS WHY THEY CANNOT BE HANDLED BY THE .INVOKE MECHANISM
WITHOUT BEING TREATED AS A SPECIAL CASE.
$P
@ONE OF THE PRIMARY EFFECTS OF .INVOKE IS THAT IT FORCES THE
EXECUTING OPERATOR TO REMAIN DORMANT UNTIL THE INVOKED OPERATOR
SIGNALS THE TERMINATION OF ITS ACTIVITIES BY MEANS OF A .RETURN. @THIS
IMPLIES THAT THE OWNER OF A PROCESS, WHICH REQUESTS ITS ACTIVATION BY
MEANS OF THE RUN-PROCESS OPERATOR MUST BE WILLING TO SUSPEND ITS
EXECUTION THROUGHOUT THE DURATION OF THE SUBORDINATE'S ACTIVITY. @THE
SECOND IMPLICATION IS THAT THE RUN-PROCESS OPERATOR MUST NEVER
EXECUTE A .RETURN. @THE REASON IS THAT THE EXECUTION OF A .RETURN
CARRIES WITH IT THE DESTRUCTION OF THE TEMPORARY MEMORY (THE @S-SEG
WINDOW) ALLOCATED TO THE OPERATOR BY THE .INVOKE MECHANISM. @RETURNING
FROM THE RUN-PROCESS OPERATOR WOULD THEN BE EQUIVALENT TO DESTROYING
THE CORRESPONDING PROCESS.
$P
@THE ANALOGOUS OPERATION TO THE .RETURN FUNCTION OF A NORMAL
OPERATOR IS FULFILLED BY THE RESUME-PROCESS OPERATOR. @ITS EFFECT IS
TO PRESERVE THE STATE OF THE EXECUTING PROCESS, SUSPEND IT, AND
RESUME EXECUTION OF THE PROCESS DESIGNATED BY THE OPERAND OF THE
OPERATOR.
$P
@WHEN THE SYSTEM IS IN STEADY STATE, I. E. WHEN THERE IS NO PROCESS
WHOSE INITIAL ACTIVATION IS PENDING, THE RESUME-PROCESS OPERATOR IS
THE ONLY MEANS BY WHICH A PROCESS CAN ACTIVATE A SUB-PROCESS OR
RESUME EXECUTION OF ('RETURN TO') THE PROCESS WHICH ACTIVATED IT.
@CLEARLY, OUR OPERATIONS DEFINE A CO-ROUTINE TYPE OF RELATIONSHIP
BETWEEN PROCESSES. @THE RESUME OPERATOR IS THE SOLE POSSESSOR OF THE
CAPABILITIES FOR THE STORE-@S-REG AND LOAD-@S-REG KERNEL OPERATORS;
THEY ENABLE THE FORMER TO SWITCH THE PROCESSORS BETWEEN PROCESSES.
$P
@THE PROCESS STRUCTURE DEPENDS ON THE SYSTEM'S POLICY REGARDING THE
DISTRIBUTION OF CAPABILITIES FOR OPERATORS OF TYPE PROCESS. @IN THE
TREE OF FIGURE 4.1-2, THE NODES AND BRANCHES REPRESENT, RESPECTIVELY,
PROCESSES AND THE CREATOR/CREATED RELATIONSHIPS BETWEEN THEM. @THE
BRANCHES WOULD ALSO REPRESENT CONTROLLER/CONTROLLED RELATIONSHIPS IF
THE CREATE-PROCESS OPERATOR RETURNED THE CAPABILITY FOR THE NEWLY
CREATED OBJECT TO ITS CALLER AND EVERY PROCESS WERE FORCED TO RETAIN
THE CAPABILITIES FOR THE PROCESSES IT CREATES, IN ADDITION TO BEING
PROVIDED WITH ALL THE OPERATORS ON PROCESSES.
$V0
$P
@ARBORESCENT PROCESS STRUCTURES ARISE NATURALLY IN THE CASE OF WHAT
@LAUER CALLS NESTED ADDRESS SPACE SYSTEMS OUTLINED IN SECTION 2.3
[@LA74,@NE72]. @A SIGNIFICANT ADVANTAGE SUCH CONTROL STRATEGIES IS
THAT
EVERY PROCESS IS IN COMPLETE CONTROL OF ITS SUBORDINATES. @EVERY
CONTINGENCY WHICH CANNOT BE HANDLED BY A GIVEN PROCESS IS RELEGATED
AUTOMATICALLY TO ITS SUPERIOR. @IN PARTICULAR, .IPC CAN BE EXPRESSED
IN A CONSISTENT AND ELEGANT FASHION VIA THE TRANSMISSION OF MESSAGES
THROUGH THE BRANCHES OF THE PROCESS TREE. @UNFORTUNATELY, THE
COMMUNICATION BETWEEN PROCESSES WHICH DO NOT HAVE THE SAME IMMEDIATE
PREDECESSOR CAN BE INEFFICIENT. @FOR OUR PRESENT PURPOSES, THE MAIN
DRAWBACK OF THIS KIND OF CONTROL STRATEGY RESIDES IN THE SEVERE
LIMITATIONS IMPOSED ON THE PARALLEL EXECUTION OF PROCESSES. @IN ORDER
TO ALLOW THE DESCENDANTS OF ONE PROCESS TO EXECUTE CONCURRENTLY IT
BECOMES NECESSARY TO IMPLEMENT THE LATTER AS AN INCARNATION OF A
SCHEDULER OF MULTIPLE PROCESSORS. @AS A CONSEQUENCE OF SUCH A
DECISION PROCESSES WOULD CEASE TO BE SEQUENTIAL TO BECOME SPECIES OF
INTERRUPT HANDLERS.
$P
@A MORE ATTRACTIVE APPROACH FOR MULTIPROCESSOR HARDWARE IS TO
DEFINE THE CREATE-PROCESS OPERATOR IN SUCH A WAY THAT THE CAPABILITY
FOR THE NEW PROCESS IS NOT RETURNED TO THE CALLER BUT TRANSMITTED TO
A DISTINGUISHED SYSTEM PROCESS: THE PROCESS SCHEDULER. @THE SCHEDULER
IS THE SOLE COMPONENT IN CHARGE OF ALLOCATING PROCESSORS TO PROCESSES
[@LA68,@BR73]. @THE CREATE PROCESS OPERATOR MAY STILL RETURN TO THE
INVOKING PROCESS A CAPABILITY FOR THE NEW PROCESS, PROVIDED THE
LATTER DOES NOT PERMIT RESUME-PROCESS ACCESS. @A COMPREHENSIBLE SET
OF OPERATORS ON PROCESSES CAN BE DESIGNED TO ENABLE PROCESSES TO
MONITOR THE BEHAVIOUR OF THEIR SUBORDINATES SUBJECT TO THE
RESTRICTIONS IMPOSED BY SYNCHRONISATION PROBLEMS AND ENFORCED BY THE
OPERATORS OF TYPE PROCESS.
$P
@CLEARLY, THIS SCHEME AFFORDS COMPLETE FLEXIBILITY IN THE SYSTEM'S
POLICY FOR THE DISTRIBUTION OF COMPUTING RESOURCES. @IN ADDITION, IT
MAKES IT POSSIBLE TO IMPLEMENT THE COMMUNICATION OF PROCESSES IN A
DIRECT FASHION; THAT IS, WITHOUT THE INTERVENTION OF A SEQUENCE OF
CONTROL LINKS DETERMINED BY THE RIGID PROCESS HIERARCHY. @A
CENTRALISED CONTROL STRATEGY IS CONGRUENT WITH THE ABSTRACTION OF
PROCESSESS AS LOGICAL ENTITIES ENGAGED IN THE INVOCATION OF OPERATORS
[@DI68]. @THUS, A PROCESS IS NO LONGER IN CHARGE OF DISTRIBUTING
PROCESSOR TIME AMONGST ITS DESCENDANTS; INSTEAD, IT IS ONLY CONCERNED
WITH THE LOGICAL RULES GOVERNING THEIR INTERACTIONS. @ON THE OTHER
HAND, WITH A CENTRALISED CONTROL STRATEGY IT BECOMES MORE DIFFICULT
TO FORMULATE THE NOTION OF DEPENDENCY BETWEEN PROCESSESS. @PERHAPS
THE MAIN CAUSE OF THE DIFFICULTY IS THAT A PROCESS IS NO LONGER IN
CONTROL OF ALL THE RESOURCES UTILISED BY ITS SUBORDINATES: COMPUTING
RESOURCES ESCAPE DIRECT CONTROL.
$P
@NEVERTHELESS, A PROCESS CAN CONSPIRE WITH THE CREATE-PROCESS
OPERATOR TO ESTABLISH THE PROCEDURES WHICH ITS SUBORDINATES MUST
FOLLOW UPON THE OCCURRENCE OF CERTAIN CONTINGENCIES; E. G. TIME
EXCEEDED, A KIND OF INITIALISATION OF THE SUBORDINATE'S INTERRUPT
VECTOR. @IN ADDITION, THE CREATING PROCESS MAY HAVE THE OPTION OF
RETAINING THE PRIVILEGE TO ACCESS ALL OF THE OBJECTS PASSED TO THE
SUB-PROCESS AND IMPOSE ARBITRARY RESTRICTIONS ON THE WAY IN WHICH
DEPENDANTS CAN CREATE NEW OBJECTS. @FOR EXAMPLE, A PROCESS MAY BE
FORCED TO DEPOSIT THE CAPABILITIES FOR NEW OBJECTS WITHIN A @C-SEG
ACCESSIBLE TO ITS PARENT.
$P
@IN ORDER TO DEFINE SYNCHRONISATION PRIMITIVES IT IS NECESSARY TO
INTRODUCE TWO MORE OPERATORS OF TYPE PROCESS: BLOCK-PROCESS AND
WAKE-UP-PROCESS. @THE FUNCTION OF THESE OPERATORS IS TO STORE AN
APPROPIATE VALUE INTO A STATUS MARK CONTAINED IN THE REPRESENTATION
OF OPERAND OBJECTS OF TYPE PROCESS. @THE STATUS MARK IS EXAMINED BY
THE PROCESS SCHEDULERS WHICH REFUSE TO ACTIVATE (RESUME-PROCESS) ANY
PROCESS WHOSE STATUS MARK CONTAINS THE VALUE STORED BY THE
BLOCK-PROCESS OPERATOR.
$V0
$P
@THE PROCESS STRUCTURE FOR A CENTRALISED CONTROL STATEGY CAN BE
DESCRIBED BY THE DIAGRAM OF FIGURE 4.1-3. @THE CONNECTED CIRCLES
INDICATE THE EXISTENCE OF A CONTROL LINE (RESUME-PROCESS) CONNECTING
EVERY MEMBER OF THE SET @S OF SCHEDULER PROCESSES TO EVERY MEMBER OF
THE TREE OF NORMAL PROCESSES. @THE TREE BRANCHES REPRESENT THE
CREATOR/CREATED RELATIONSHIPS BETWEEN NORMAL PROCESSES. @AN ARROW
FROM A SCHEDULER TO A NORMAL PROCESS MEANS THAT THE CORRESPONDING
SCHEDULER HAD EXECUTED:
$B0
$T2
.INVOKE (RESUME-PROCESS,@P)
$B0
AND THEREFORE IT IS WAITING FOR THE NORMAL PROCESS, .P, TO RESUME
EXECUTION OF THE FORMER. @THE ABSENCE OF A LINE ORIGINATING FROM A
SCHEDULER INDICATES THAT THE SCHEDULER IS EITHER IDLE OR ENGAGED IN
EXAMINING THE VARIOUS PROCESSES IN ORDER TO ELECT THE NEXT CANDIDATE
FOR ACTIVATION. @NOTE THE EXISTENCE OF A NUMBER OF SCHEDULER
PROCESSES EQUAL TO THE NUMBER OF PROCESSORS OF THE HOST HARDWARE
SYSTEM. @THIS ALLOWS THE DEFINITION OF PROCESS SCHEDULING AND CONTEXT
SWITCHING WITHOUT DEVIATING FROM THE FUNDAMENTAL RESTRICTION STATED
AT THE BEGINNING OF THIS SECTION: @NAMELY, A PROCESS IS EXECUTABLE BY
AT MOST ONE PROCESSOR. @ALSO, THE TECHNIQUE PERMITS THE PARALLEL
PROCESSING OF LOGICALLY INDEPENDENT TASKS OF THE PROCESS SCHEDULERS.
@FINALLY, IT FACILITATES THE INTEGRATION OF THE INTERACTIONS BETWEEN
PROCESS SCHEDULING AND THE SYNCHRONISING PRIMITIVES. @THIS LAST
ASPECT WILL BE DISCUSSED IN SECTION 4.2.
$P
@THE SCHEDULER PROCESSES SHARE A DATA STRUCTURE CONTAINING THE
CAPABILITIES FOR ALL THE OPERAND OBJECTS OF TYPE PROCESS WHICH MAY BE
ACTIVATED.
$P
@WE WILL NOW EXAMINE THE REPRESENTATION OF PROCESSES IN MORE DETAIL
IN ORDER TO GIVE A PRECISE DEFINITION OF THE ACTIONS OF OUR OPERATORS
OF TYPE PROCESS.
$V0
$P
@IN FIGURE 4.1-4 WE REPRODUCE THE STRUCTURE DEPICTED IN FIGURE
4.1-1 WITH A FEW LABLES ADDED. @THE COMPONENTS OF THE PROCESS ARE THE
CAPABILITIES CONTAINED IN THE @C-SEG NAMED .RP: THE REPRESENTATION OF
THE EXTENDED OPERAND @P OF TYPE 'PROCESS'. @THE VARIOUS COMPONENTS OF
THE REPRESENTATION OF AN OPERAND OBJECT OF TYPE PROCESS INCLUDE: @THE
@S-SEG OF THE PROCESS; AN @N-SEG CONTAINING THE STATUS MARK AND A
POINTER TO THE TOP OF THE @S-SEG AT THE TIME THE PROCESS WAS
DE-ACTIVATED; AN .ACTIVATOR SLOT TO CONTAIN THE CAPABILITY FOR THE
PROCESS WHICH IS RESPONSIBLE FOR THE ACTIVATION OF THIS PROCESS AND ,
FINALLY, A NUMBER OF 'ADDITIONAL CAPABILITIES' FOR OBJECTS WHICH
CONTAIN INFORMATION SUCH AS TIMERS, ACCOUNTING TABLES, PAGE TABLES,
ETC.
$P
@THE WAKE-UP-PROCESS OPERATOR SIMPLY STORES THE VALUE 'READY' IN
THE PROCESS' STATUS MARK. @THE BLOCK-PROCESS OPERATOR STORES THE
VALUE 'BLOCKED' IN THE STATUS MARK; DEPOSITS THE CURRENT VALUE OF THE
TOP OF @S-SEG REGISTER .(TOS) INTO ITS CORRESPONDING PLACE AND
EXTRACTS
THE CAPABILITY LABELED .ACTIVATOR. @THIS CAPABILITY IS RETURNED TO
THE
CALLER OF RESUME-PROCESS.
$P
@THE EXECUTION OF
$B0
$T2
.INVOKE (BLOCK-PROCESS,@E)
$B0
BY THE CURRENTLY EXECUTING PROCESS .E, MUST BE FOLLOWED IMMEDIATELY
BY
THE OPERATION:
$B0
$T2
.INVOKE (RESUME-PROCESS,@A@C@T@I@V@A@T@O@R)
$B0
WHERE .ACTIVATOR IS THE CAPABILITY FOR THE PROCESS WHICH CAUSED THE
ACTIVATION OF THE CURRENTLY EXECUTING PROCESS.
$V0
$P
@IN FIGURE 4.1-5 WE DRAW A SNAPSHOT OF THE CURRENTLY EXECUTING
PROCESS WHOSE CAPABILITY IS CALLED .E, IMMEDIATELY AFTER IT ENTERS
THE
RESUME-PROCESS OPERATOR. .RE AND .RP ARE, RESPECTIVELY, THE
CAPABILITIES FOR THE REPRESENTATIONS OF @E AND .P. @IN THIS CASE, @P
IS
THE .ACTIVATOR OF .E. @THERE ARE TWO CAPABILITIES WITHIN THE WINDOW
ALLOCATED TO THE RESUME-PROCESS OPERATOR INVOKED BY .E: .RP AND .E.
.RP
WAS PASSED BY THE .INVOKE MECHANISM AND @E , THE SELF REFERENCING
CAPABILITY FOR PROCESS .E, IS AN ADDITIONAL PARAMETER PASSED TO
RESUME
PROCESS BY ITS CALLER. @RESUME-PROCESS CAN NOW USE CAPABILITY .RP TO
STORE CAPABILITY @E INTO THE .ACTIVATOR SLOT OF @P'S REPRESENTATION,
AND
ALSO TO LOAD THE .TOS OF PROCESS @P AND THE CAPABILITY FOR @P'S
@S-SEG.
@AT THIS POINT, THE PROCESSOR IS STILL EXECUTING ON BEHALF OF @E AND
YET IT IS REFERENCING THE @S-SEG ASSOCIATED WITH PROCESS .P.
@CONSEQUENTLY, THE EXECUTION OF A .RETURN CAUSES THE PROTECTION
MECHANISM TO RESTORE THE EXECUTION ENVIRONMENT WHICH WAS SAVED
PREVIOUSLY AT THE TOP OF THE @S-SEG OF PROCESS .P. @THIS IS PRECISELY
THE ENVIRONMENT OF THE OPERATOR TO WHICH @P WAS BOUND AT AN EARLIER
TIME, WHEN IT EXECUTED THE
$B0
$T2
.INVOKE(RESUME-PROCESS,E)
$B0
WHICH CAUSED THE ACTIVATION OF PROCESS .E.
$P
@WE HAVE DESCRIBED PROCESS SWITCHING STRICTLY IN TERMS OF THE
.INVOKE AND .RETURN MACHANISMS. @THE ONLY 'PRIVILEGED' INSTRUCTION
REQUIRED IN THE ABOVE ACTIONS IS THE LOADING OF THE PROCESSOR'S
@S-REG. @THE INSTRUCTION IS PRIVILEGED IN THAT IT IS ONLY AVAILABLE
TO
THE RESUME-PROCESS OPERATOR. @IT IS WORTHWHILE TO NOTE THAT PROCESS
SUSPENSION IS EXPRESSED IN TERMS OF AN IMPERATIVE REQUEST ISSUED BY
AN EXECUTING PROCESS. @IN CONTRAST, PROCESS ACTIVATION IS A NORMAL,
PASSIVE RETURN TO THE OPERATOR WHICH REQUESTED THE ACTIVATION OF THE
EXECUTING PROCESS. @THE IMPLEMENTATION CORRESPONDS CLOSELY WITH THE
ABSTRACT CONCEPT OF AN OPERATOR WHICH RETURNS TO ITS CALLER AFTER A
CERTAIN DELAY OF A DURATION DETERMINED BY THE ACTIVITIES IT PERFORMS.
$P
@THE ACTIVATION OF A NORMAL PROCESS BY A SCHEDULER DIFFERS FROM THE
INVERSE ACTION ONLY IN THE WAY IN WHICH THE ACTIVE PROCESS (NORMAL OR
SCHEDULER) SELECTS THE OPERAND OF THE RESUME-PROCESS OPERATOR; IN THE
FORMER CASE, A FREE CHOICE BETWEEN A NUMBER OF CAPABILITY FOR OBJECTS
OF TYPE PROCESS IS AVAILABLE; A NORMAL PROCESS IS FORCED TO EXTRACT
THE CAPABILITY FOR THE OPERAND OF RESUME-PROCESS FROM A PRE-DEFINED
LOCATION OF ITS STATE WORD.
$N
$L1 C
4.2.- SCHEDULING OF COMMUNICATING PROCESSES.
$P3
@WE BEGIN THE PRESENT SECTION WITH THE DEFINITION OF THE SEMAPHORE
TYPE UPON WHICH PROCESS SYNCHRONISATION IS BASED.
$V0
$P
@THE STRUCTURE OF AN OPERAND OF TYPE SEMAPHORE IS DEPICTED IN
FIGURE 4.2.-1. @A SEMAPHORE IS LOGICALLY DIVIDED INTO TWO COMPONENTS:
@A SEMAPHORE PROPER AND A SEMAPHORE QUEUE. @THE SEMAPHORE PROPER, .S,
IS AN INTEGER CONTAINING THE VALUE WHICH DETERMINES WHETHER OR NOT A
PROCESS PERFORMING A @P OPERATION WILL BE ALLOWED TO PROCEED OR A
PROCESS PERFORMING A @V OPERATION IS REQUIRED TO WAKE UP ANOTHER
PROCESS. @THE SEMAPHORE QUEUE COMPONENT COMPRISES TWO CYCLING
SEMAPHORES: .CYS AND .NUMQPROC. @AS DISCUSSED IN SECTION 1.2, .CYS IS
USED TO ENFORCE EXCLUSIVE ACCESS TO THE SEMAPHORE QUEUE AND .NUPQPROC
ENSURES THE ORDERLY ARRIVAL OF PROCESSES AT THE SECOND PART OF THE
ALGORITHMS IMPLEMENTING THE @P AND @V OPERATIONS. @IN ADDITION, THERE
IS A SET OF QUEUE POINTERS AND THE LIST OF CAPABILITIES FOR THE
PROCESSES WAITING FOR THE LIBERATION OF THE SEMAPHORE. @THE TWO
PRINCIPAL OPERATORS OF TYPE SEMAPHORE ARE @P AND .V. @THE CREATION,
INITIALISATION AND DESTRUCTION OF SEMAPHORES IS DISCUSSED IN SECTION
4.3.
$P
@THE @I-SEG OF THE @P OPERATOR CONTAINS CAPABILITIES FOR THE
OPERATORS: BLOCK-PROCESS AND RESUME-PROCESS. @THE @V OPERATOR ONLY
NEEDS THE WAKE-UP-PROCESS EXTENDED OPERATOR. @THE STRUCTURE OF THE @P
AND @V EXTENDED OPERATORS IS SHOWN IN FIGURE 4.2-2. @THE @P-SEGS OF
THE
OPERATORS CONTAIN THE CODE WHICH IMPLEMENTS THE ALGORITHMS DERIVED IN
SECTION 1.2. @FIGURE 4.2-3 IS A COPY OF THE ALGORITHMS. @THE
STATEMENT
$V0
$B0
$T2 BLOCK-PROCESS (ME)
$B0
OF THE @P OPERATION HAS BEEN SUBSTITUTED FOR THE PAIR OF STATEMENTS:
$B0
$T2 .ACTIVATOR = BLOCK-PROCESS (ME)
$B0
$T2 RESUME-PROCESS ( .ACTIVATOR)
$B0
WHERE .ACTIVATOR IS A VARIABLE OF TYPE .CAPABILITY. @AS DISCUSSED IN
THE PREVIOUS SECTION, FOLLOWING THE EXECUTION OF THE FIRST STATEMENT,
.ACTIVATOR CONTAINS THE CAPABILITY FOR THE (SCHEDULER) PROCESS
RESPONSIBLE FOR THE ACTIVATION OF THE EXECUTING PROCESS.
$P
@IN THE FOLLOWING DISCUSSION THE NOTATION:
$B0
$T2 .SEM$_CYS , .SEM$_QUEUE ; ETC.
$B0
WILL BE USED TO REFER TO THE VARIOUS COMPONENTS OF A SEMAPHORE CALLED
.SEM. @SIMILARLY,
$B0
$T2 .PROCESS$_STATUS
$B0
DENOTES THE STATUS MARK OF A PROCESS NAMED .PROCESS. @WE REMARKED AT
THE END OF SECTION 1.2 THAT THE RELEASE OF THE CYCLING SEMAPHORE .CYS
MUST BE PERFORMED AFTER THE EXECUTION OF THE BLOCK-PROCESS OPERATION
OR, ALTERNATIVELY, A WAKE UP WAITING FLAG CAN BE USED IN CONJUNCTION
WITH THE STATUS MARK OF A PROCESS TO DETERMINE ITS STATUS. @WE WILL
DISCUSS IN DETAIL THE TWO OPTIONS AND OUR REASON FOR REJECTING THE
USE OF WAKE UP WAITING FLAGS. @IN ADDITION, THE PROBLEM OF ENSURING
THAT AT MOST ONE SCHEDULER SELECT A GIVEN PROCESS IS DISCUSSED.
$P
@THE CAPABILITIES FOR ALL THE PROCESS WHICH MAY BE SCHEDULED ARE
STORED IN A DATA STRUCTURE WHICH IS SHARED BY ALL THE SCHEDULERS.
@EVERY SCHEDULER EXECUTES A 'SELECT A PROCESS' ROUTINE WHICH SCANS
THROUGH THE DATA STRUCTURE TRYING TO FIND A 'READY' PROCESS. @THERE
ARE BASICALLY TWO WAYS TO PREVENT THE SELECTION OF A GIVEN PROCESS BY
MORE THAN ONE SCHEDULER. @THE FIRST IS THAT THE SCHEDULER REMOVE THE
CAPABILITY FOR THE PROCESS SELECTED FOR ACTIVATION FROM THE SHARED
DATA STRUCTURE AND KEEP IT WITHIN ITS PRIVATE STORAGE. @THIS
EFFECTIVELY PREVENTS ANY OTHER SCHEDULER FROM SEEING THE CAPABILITY
OF - AND HENCE ACTIVATING - A RUNNING PROCESS; THIS IS LOGICALLY
EQUIVALENT TO MOVING THE CAPABILITY FOR THE PROCESS TO BE ACTIVATED
FROM A READY QUEUE TO A RUNNING QUEUE AND EXCLUDING THE RUNNING QUEUE
FROM THE SEARCH FOR READY PROCESSES. @NOTE THAT THE USE OF READY AND
RUNNING QUEUES MAKES IT SUPERFLUOUS TO DEFINE A 'RUNNING' STATUS FOR
PROCESSES. @THE SECOND APPROACH IS TO LEAVE THE CAPABILITY FOR THE
RUNNING PROCESS WITHIN THE SHARED DATA STRUCTURE AND TO IMPLEMENT A
PROTOCOL WHICH ENSURES THAT AT MOST ONE SCHEDULER CAN SUCCEED IN
EFFECTING THE TRANSITION FROM 'READY' TO 'RUNNING' OF A PROCESS'
STATUS MARK. @IN ADDITION, SCHEDULERS MUST IGNORE ANY PROCESS BEARING
THE 'RUNNING' STATUS MARK.
$P
@IT MAY BE ADVANTAGEOUS TO DO AWAY WITH SEPARATE READY AND RUNNING
QUEUES AND ALLOW SCHEDULERS TO ENQUIRE UPON THE STATUS OF POSSIBLY
RUNNING PROCESSES. @SUPPOSE A NORMAL, RUNNING PROCESS, SAY .A, IS
DEPRIVED OF ITS PROCESSOR AS A RESULT OF AN EXTERNAL INTERRUPT. @THIS
CAUSES THE ACTIVATION OF THE SCHEDULER OF @A VIA THE FORCED EXECUTION
OF THE SEQUENCE:
$A INDENT=2
.ACTIVATOR = BLOCK-PROCESS (ME)
$B0
RESUME-PROCESS ( .ACTIVATOR)
$B0
$A INDENT=0
@THE SCHEDULER DENOTED BY .ACTIVATOR IS NOW IN CHARGE OF RESUMING
EXECUTION OF THE PROCESS, CALLED .I, IN CHARGE OF EXECUTING THE
INTERRUPT ROUTINE. @THE LOGICAL STATUS OF @A IMMEDIATELY BEFORE THE
ACTIVATION OF @I IS 'READY'. @THEREFORE, THE SCHEDULER CAN CHOOSE
BETWEEN TWO ALTERNATIVES. @ONE IS TO MARK @A AS 'READY' AND MOVE @A'S
CAPABILITY TO A READY QUEUE (OR SIMPLY LEAVE IT THERE IF IT WAS NOT
REMOVED TO BEGIN WITH). @THIS MAKES IT POSSIBLE FOR ANOTHER SCHEDULER
TO ACTIVATE @A WHILE THE OTHER PROCESSOR IS ENGAGED IN THE EXECUTION
OF THE INTERRUPT HANDLER. @THE SECOND ALTERNATIVE IS TO LEAVE @A IN
AN
IMPRECISE 'BLOCKED' STATUS. @IN THIS CASE @A CANNOT BE ACTIVATED
UNTIL
THE UNRELATED ACTIVITY OF @I HAS CONCLUDED. @NATURALLY, THE PRACTICAL
ADVANTAGE OF THE SECOND APPROACH DEPENDS ON THE 'SIZE' OF THE
INTERUPT ROUTINE, THE AVAILABILITY OF DIFFERENT SETS OF REGISTERS
ETC. @HOWEVER, TO DEFINE A 'RUNNING' STATUS FOR PROCESSES PROVIDES
THE GREATER FLEXIBILITY AND ALSO RELIEVES SCHEDULERS FROM THE TASK OF
MAINTAINING VARIOUS SCHEDULING QUEUES. @IN THE FOLLOWING, IT WILL BE
ASSUMED THAT RUNNING PROCESSES ARE VISIBLE TO SCHEDULERS.
$P
@IN ANY CASE, A SET OF INTERLOCKS MUST BE PROVIDED TO GUARANTEE THE
CONSISTENCY OF THE SHARED DATA STRUCTURES AND TO PREVENT TWO OR MORE
SCHEDULERS FROM FINDING AND ACTIVATING MORE THAN ONE READY PROCESS.
@THE SIMPLEST WAY TO ACHIEVE THIS MUTUAL EXCLUSION IS TO DEFINE A ONE
AT A TIME ACCESS TO THE SHARED DATA STRUCTURE. @THIS GIVES RISE TO
THE FOLLOWING SCHEDULING ALGORITHM.
$A INDENT=2
$A NLS=1
%CYCLING %SEMAPHORE MUTEX ;
$B
%BEGIN %PROCESS ;
$B0
%CAPABILITY .PROCESS
$A INDENT=3
%CYCLE
$A INDENT=4
.TS (MUTEX) ;
$B0
$C+2 .PROCESS = SELECT READY ( .PROCESS .LIST) ;
$B0
$C+2 .PROCESS$_STATUS = 'RUNNING' ;
$B0
.RE (MUTEX) ;
$B0
RESUME-PROCESS( .PROCESS) ;
$B0
$A INDENT=3
%REPEAT ;
$A INDENT=2
%END %PROCESS ;
$A INDENT=0
$A NLS=2
$B
@IN THE ABOVE PROGRAM, 'SELECT READY' IS A ROUTINE WHICH SEARCHES THE
SHARED .PROCESS .LIST FOR A PROCESS MARKED 'READY' AND RETURNS A COPY
OF ITS CAPABILITY TO THE CALLER; MUTEX IS USED TO ENFORCE EXCLUSIVE
ACCESS TO THE SHARED DATA STRUCTURE, .PROCESS .LIST, CONTAINING THE
CAPABILITIES FOR ALL SCHEDULABLE NORMAL (I. E. NON-SCHEDULER)
PROCESSES. @THE CAPABILITIES FOR THE SCHEDULERS ARE EXCLUDED FROM THE
.PROCESS .LIST; THEIR ACTIVATION AND SUSPENSION OCCURS SOLELY AS A
RESULT OF THE SUSPENSION AND ACTIVATION, RESPECTIVELY, OF NORMAL
PROCESSES. @THE USE OF THE TEST AND SET .(TS) AND RELEASE .(RE)
SYNCHRONISING PRIMITIVES INSTEAD OF @P AND @V REFLECTS THE NEED TO
STOP
THE RECURSIVE PROVISION OF SCHEDULER PROCESSES. @NOTE THAT THE STATUS
MARK OF THE PROCESS CHOSEN IS MODIFIED WITHIN THE CRITICAL SECTION;
THIS GUARANTEES THAT THE PROCESS WILL NOT BE SELECTED BY ANY OTHER
SCHEDULER.
$P
@IT IS NOT THE AFFAIR OF SCHEDULER PROCESSES TO KNOW OF THE
EXISTENCE OF SEMAPHORES; THEIR ONLY CONCERN IS TO LOCATE AND ACTIVATE
PROCESSES BEARING THE 'READY' STATUS MARK. @THE AVOIDANCE OF CONFLICT
IN THE 'READY' TO 'RUNNING' TRANSITION OF PROCESSES - A
RESPONSABILITY OF THE SCHEDULERS - IS ACCOMPLISHED BY MEANS OF THE
CRITICAL SECTION IN THE SCHEDULER ALGORITHM. @IN CONTRAST, FROM THE
SCHEDULER'S VIEWPOINT, 'BLOCKED' TO 'READY' TRANSITIONS ARE
NON-DETERMINISTIC: THEY OCCUR AS A RESULT OF SOME ACTIONS .(P AND @V
OPERATIONS) EXECUTED BY RUNNING PROCESSES. @NOTE THAT 'RUNNING' TO
'BLOCKED' TRANSITIONS ARE ALSO NON-DETERMINISTIC; NEVERTHELESS, THEY
ARE NOT IMPORTANT TO THE SCHEDULERS BECAUSE PROCESSES WITH 'BLOCKED'
OR 'RUNNING' STATUS ARE IGNORED. @THE CRUCIAL POINT IS THAT A PROCESS
MARKED 'READY' HAS TO BE IN SUCH A STATE THAT THE RESUME-PROCESS
OPERATOR CAN BE APPLIED TO ITS CAPABILITY. @TO SEE THE IMPORTANCE OF
THIS POINT WE WILL EXAMINE A PARTICULAR EXAMPLE.
$P
@THE SAMPLE SYSTEM CONSISTS OF THREE PROCESSORS, HENCE THREE
SCHEDULER PROCESSES NAMED .S1, .S2 AND .S3. @THERE ARE M>3 PROCESSES
IN
THE SYSTEM. @WE ARE CONCERNED WITH TWO OF THE M PROCESSES WHICH WILL
BE DENOTED BY @A AND .B. @FIGURE 4.2-4 SHOWS A DIAGRAM OF THE SYSTEM.
@THE .PROCESS .LIST IS ENCLOSED IN AN OVAL. @SCHEDULER (AND
PROCESSOR)
.S3 IS JUST BEGINNING TO EXAMINE THE STATUS OF @A TO DETERMINE IF IT
MAY BE ACTIVATED. @B IS EXECUTING ON PROCESSOR .S2 AND @A IS
EXECUTING
IN PROCESSOR .S1.
$V0
$P
@SUPPOSE @A IS CURRENTLY EXECUTING A @P OPERATION ON SEMAPHORE .SEM
WHOSE VALUE AT THE TIME @A STARTS THE @P OPERATION WAS ZERO; I. E., @A
IS IN THE PROCESS OF QUEUEING UP AND BLOCKING. @MORE PRECISELY,
ASSUME @A IS BEGINNING EXECUTION OF THE RESUME-PROCESS(@S1) INVOKED
BY
THE @P OPERATOR. @THUS, FIGURE 4.2-4 SHOWS THE TOP OF @A'S @S-SEG
CONTAINING CAPABILITY .RS1: THE REPRESENTATION OF .S1. @THE
IMPORTANCE
OF THE OTHER CAPABILITY, .NSEM, SHOWN IN THE @S-SEG OF @A IS
DISCUSSED
BELOW. @FINALLY, ASSUME @B IS CURRENTLY ATTEMPTING TO PERFORM A @V
OPERATION ON .SEM. @THE LAST ASSUMPTION MEANS THAT @B IS PHYSICALLY
HELD UP ON THE CYCLING SEMAPHORE WHICH PROTECTS THE QUEUE ASSOCIATED
WITH .SEM WHERE THE CAPABILITY FOR @A IS STORED.
$P
@PROCESS @A IS YET TO PERFORM TWO ACTIONS: ONE IS TO RELEASE THE
CYCLING SEMAPHORE .CYS; THE OTHER IS TO LOAD THE STATE OF .S1 (THE
CAPABILITY FOR THE @S-SEG OF .S1) INTO THE PROCESSOR'S REGISTERS (THE
@S-REG) AND ISSUE A .RETURN. @THE FIRST ACTION USES CAPABILITY .NSEM:
THE COMPONENT OF .SEM WHICH CONTAINS THE CYCLING SEMAPHORE .CYS. @THE
SECOND REQUIRES THE PRESENCE OF CAPABILITY .RS1, THE CAPABILITY FOR
THE REPRESENTATION OF THE SCHEDULER .S1, IN THE @S-SEG OF .A. @THE
LATTER ACTION CANNOT BE PERFORMED BEFORE THE FORMER FOR ONCE THE
PROCESSOR'S @S-REG IS LOADED WITH THE CAPABILITY FOR THE @S-SEG OF
.S1,
IT BECOMES IMPOSSIBLE TO ACCESS THE CAPABILITY FOR THE @S-SEG OF .A.
@THIS, IN TURN, IMPLIES THAT CAPABILITY .NSEM CANNOT BE REACHED AND
THE
CYCLING SEMAPHORE, .CYS, CANNOT BE RESET BY PROCESS .A. @ON THE OTHER
HAND, SUPPOSE THE RESET OF THE CYCLING SEMAPHORE IS EXECUTED FIRST
AND WILL BE FOLLOWED AFTER A RELATIVELY LONG DELAY BY THE EXECUTION
OF THE OTHER ACTION. @THIS ALLOWS PROCESS @B TO PROCEED TO REMOVE THE
CAPABILITY FOR @A FROM THE SEMAPHORE QUEUE AND EXECUTE
$B0
$T2 WAKE-UP-PROCESS .(A)
$B0
@THIS OPERATION DEPOSITS THE VALUE 'READY' IN @A$_STATUS. @AT THIS
INSTANT, .S3 IS EXAMINNING THE STATUS OF @A AND CONCLUDES THAT IT IS
SAFE TO EXECUTE
$B0
$T2 RESUME-PROCESS .(A)
$B0
@RECALL THAT THIS LAST OPERATOR LOADS THE CAPABILITY FOR THE @S-SEG
OF
@A INTO THE PROCESSOR'S (IN THIS CASE .S3) @S-REG AND ORIGINATES, VIA
A
.RETURN, A CHAIN OF MODIFICATIONS OF THE @S-SEG OF .A. @SPECIFICALLY,
CAPABILITY .RS1 WILL BE TAMPERED WITH. @NOW THE DELAY MENTIONED ABOVE
IS EXHAUSTED BUT @A CANNOT FIND .RS1 AND THEREFORE IT CANNOT ACTIVATE
SCHEDULER .S1. @THE CAUSE OF THE PROBLEM IS THAT @A WAS NOT IN THE
QUIESCENT STATE WHEN SCHEDULER .S3 DECIDED TO RESUME ITS EXECUTION.
@TWO PROCESSORS, .S1 AND .S3 WERE ALLOCATED MOMENTARILY TO THE SAME
PROCESS AND ONE OF THEM DESTROYED INFORMATION WHICH WAS VITAL FOR THE
SYSTEM'S WELL BEING.
$P
@ONE OF THE WAYS TO SOLVE THIS PROBLEM IS TO INVENT A NEW HARDWARE
OPERATION WHICH PERFORMS BOTH ACTIVITIES, THE RELEASE OF THE CYCLING
SEMAPHORE AND THE LOADING OF THE @S-REG. @THE INSTRUCTION MUST
EXTRACT
FROM THE MEMORY BOTH CAPABILITIES, .RS1 AND .NSEM, BEFORE PROCEEDING
TO
ACTIVATE THE ADDRESSING/PROTECTION ACTIVITIES OF THE TWO ACTIONS.
@ANOTHER PLAUSIBLE SOLUTION AND OUR REASON FOR REJECTING IT IS
DISCUSSED IN THE NEXT FEW PARAGRAPHS.
$P
@A NEW VARIABLE CALLED ( .WAKE .UP .WAITING) .FLAG IS USED IN
ADDITION
TO .STATUS IN ORDER TO DETERMINE THE STATUS OF A PROCESS [@LA68]. @THE
WAKE-UP-PROCESS OPERATOR IS MODIFIED TO STORE THE VALUE 'WAKE' IN
VARIABLE .FLAG INSTEAD OF CHANGING THE VALUE OF .STATUS. @ALSO, THE @P
OPERATOR MUST NO LONGER INVOKE THE BLOCK-PROCESS OPERATOR. @THIS
ACTION MUST BE DEFERRED UNTIL THE SCHEDULER OF THE PROCESS WHICH IS
BLOCKING HAS GAINED CONTROL OF THE PROCESSOR, IN ORDER TO ENSURE THAT
THE VALUE OF .STATUS IS NOT SET TO 'BLOCKED' UNTIL THE BLOCKED
PROCESS
IS IN THE QUIESCENT STATE. @A SCHEDULER CAN DETERMINE IF A PROCESS IS
READY FOR ACTIVATION FROM THE VALUE OF THE BOOLEAN EXPRESSION:
$B0
$T2 READY= ( .STATUS = 'BLOCKED' %AND .FLAG = 'WAKE' )
$B0
@THE MOST ATTRACTIVE PROPERTY OF THIS SCHEME IS THAT THE CYCLING
SEMAPHORE, .CYS, OF THE SYNCHRONISING PRIMITIVES CAN BE RELEASED AS
SOON AS THE OPERATIONS WHICH ALTER THE STATE OF THE SEMAPHORE QUEUE
HAVE BEEN CONCLUDED. @THIS APPLIES TO BOTH, THE @P AND @V OPERATORS.
@THE PRACTICAL GAIN IN TERMS OF EFFICIENCY CANNOT BE ESTIMATED
WITHOUT
KNOWLEDGE OF THE EXPECTED FREQUENCY OF COLLISIONS IN THE EXECUTION OF
SYNCHRONISATION OPERATIONS ON THE SAME SEMAPHORE. @THE NUMBER OF
OPERATIONS OF THE SCHEDULING ALGORITHM IS SLIGHTLY LESS IF THE FIRST
SOLUTION IS ADOPTED, WHEREAS THE SECOND APPROACH REDUCES THE
UNINTERRUPTIBLE EXECUTION TIME OF THE @P AND @V OPERATORS.
$P
@ADMITTEDLY, THE CHOICE BETWEEN THE TWO SOLUTIONS IS PRIMARILY A
MATTER OF TASTE. @HOWEVER, A STRONGER MOTIVATION FOR OUR CHOICE OF
THE FIRST SCHEME DERIVES FROM THE FACT THAT IT IS HIGHLY DESIRABLE TO
MINIMISE THE NUMBER OF VARIABLES WHOSE VALUES DETERMINE IMPORTANT
DECISIONS, PARTICULARLY WHEN THOSE VALUES VARY IN A NON-DETERMINISTIC
MANNER. @THE COMPLEXITY OF ANALYSING THE EFFECT OF A MINOR CHANGE IN
AN ALGORITHM GROWS DISPROPORTIONALLY WITH THE THE NUMBER OF VARIABLES
WHOSE VALUES CAN BE MODIFIED SURREPTITIOUSLY BY ACTIVE PROCESSES.
@MOREOVER, WHEN THE NUMBER OF VARIABLES WHICH MUST BE MODIFIED BY
MORE
THAN ONE PROCESS IS ONE, THE VARIABLE ITSELF MAY BE DEFINED AS A
SEMAPHORE AND A CRITICAL SECTION TO ENFORCE MUTUAL EXCLUSION BECOMES
REDUNDANT. @WE WILL MAKE USE OF THIS PROPERTY IN THE FINAL DESIGN OF
THE SCHEDULING ALGORITHM SUGGESTED AT THE END OF THE PRESENT SECTION.
$P
@A FURTHER COMPLICATION ARISES FROM THE ABSOLUTE NECESSITY OF
PROVIDING MECHANISMS TO SYNCHRONISE SCHEDULERS WITH NORMAL PROCESSES.
@THE NEED IS DUE TO THE FACT THAT .PROCESS .LIST IS A VARIABLE WHOSE
STATE HAS TO CHANGE AS A RESULT OF ACTIONS PERFORMED BY NORMAL
PROCESSES; E. G., CREATE-PROCESS AND DESTROY-PROCESS. @IN REALITY,
.PROCESS .LIST CONTAINS ONLY THE CAPABILITIES FOR PROCESSES IN THE
CURRENT MULTIPROGRAMMING SET. @THE CAPABILITIES FOR THE REST OF THE
PROCESSES ARE HELD BY A SEPARATE, NORMAL (ALBEIT SYSTEM) PROCESS IN
CHARGE OF THE 'MEDIUM TERM' MANAGEMENT OF PROCESSES. @THIS IS
EXAMINED BELOW IN MORE DETAIL. @THE COMPLICATION OF SYNCRONISING
SCHEDULERS WITH NORMAL PROCESSES IS THAT THE @P OPERATIONS EXECUTED
BY
SCHEDULER PROCESSES MUST BE DIFFERENT IN NATURE FROM THOSE PERFORMED
BY NORMAL PROCESSES. @THE SUSPENSION OF SCHEDULERS IS NOT SUPPORTED;
HENCE, WHEN A SCHEDULER PERFORMS A @P OPERATION ON A BUSY SEMAPHORE
IT
MUST BE DETAINED IN SOME FORM OF WAIT, BE IT BUSY OR HARDWARE
IMPLEMENTED. @AT THE SAME TIME, THERE MUST BE A GUARANTEE TO THE
EFFECT THAT THE SCHEDULER IS HELD UP ONLY TO PREVENT IMMEDIATE
CONFLICT WITH THE ACTIONS OF ANOTHER PROCESS OR BECAUSE IT GENUINELY
HAS NOTHING TO DO. @A DETAINED SCHEDULER MAY BE CAUSING A DELAY IN
THE PROGRESS OF A READY, NORMAL PROCESS. @IN CONTRAST, THERE IS NO
PROBLEM IN ALLOWING SCHEDULER PROCESSES TO EXECUTE @V OPERATIONS.
@THIS CAN BE VERY CONVENIENT FOR IT ENABLES THE SCHEDULERS TO CONTROL
THE FREQUENCY OF ACTIVATION OF NORMAL PROCESSES WHICH MAY CAUSE THE
ACTIVATION OF SCHEDULERS.
$P
@THERE ARE TWO WAYS TO SUPPORT THE SYNCHRONISATION OF NORMAL
PROCESSES WITH SCHEDULERS. @THE FIRST IS SIMPLY TO ALLOW CERTAIN
NORMAL PROCESSES TO EXECUTE .TS/RE OPERATIONS ON THOSE CYCLING
SEMAPHORES WHICH NEED TO BE CROSS REFERENCED BY SCHEDULER AND NORMAL
PROCESSES. @THIS IMPOSES ON THE DESIGNER THE NEED TO SELECT THE
COMMUNICATION PROTOCOLS IN SUCH A WAY THAT ON THE ONE HAND, A
PRIVILEGED NORMAL PROCESS IS NOT DELAYED ON A CYCLING SEMAPHORE
UNLESS ABSOLUTELY NECESSARY AND ON THE OTHER, PRIVILEGED NORMAL
PROCESSES DO NOT MONOPOLISE CRITICAL SECTIONS WHICH MAY DETAIN
SCHEDULER PROCESSES. @CLEARLY, THE CONSTRAINTS HAVE TO BE KEPT IN
MIND EVEN IF THE SCHEDULERS COULD ACCESS SEMAPHORES IN EQUAL TERMS
WITH NORMAL PROCESSES.
$P
@THE ALTERNATIVE IS TO GIVE SCHEDULERS THE RIGHT TO CHEAT WHEN THEY
EXECUTE @P OPERATIONS ON SEMAPHORES. @THE TECHNIQUE WILL BE EXPLAINED
MERELY TO SHOW THAT IT IS POSSIBLE, ALBEIT EXTREMELY CUMBERSOME, TO
SUPPORT THE SYNCHRONISATION OF SCHEDULERS WITH NORMAL PROCESSES USING
THE SYNCHRONISING PRIMITIVES WHICH CAUSE PROCESS SUSPENSION.
$P
@FIRST OF ALL WE INTRODUCE A PSEUDO-PROCESS. @A SCHEDULER WHICH
DECIDES TO ENTER A CRITICAL SECTION IN ORDER TO MANIPULATE A RESOURCE
SHARED BETWEEN SCHEDULERS AND NORMAL PROCESSES MUST FIRST IMPERSONATE
THE PSEUDO-PROCESS. @WHEN THE PSEUDO-PROCESS EXECUTES A @P OPERATION
IT DOES NOT INVOKE THE RESUME-PROCESS OPERATOR; INSTEAD, THE
SCHEDULER PROCEEDS TO PERFORM ANOTHER ACTIVITY. @NEVERTHELESS, THE
STATUS MARK OF THE PSEUDO-PROCESS IS SET TO 'BLOCKED' BY THE
BLOCK-PROCESS OPERATOR INVOKED FROM THE @P OPERATOR. @EVENTUALLY,
SOME
PROCESS WILL PERFORM THE @V OPERATION WHICH CAUSES THE 'BLOCKED' TO
'READY' TRANSITION OF THE PSEUDO-PROCESS' STATUS. @A READY
PSEUDO-PROCESS INDICATES TO THE SCHEDULERS THAT IT IS APPROPIATE TO
RESUME THE ACTIVITIES WHICH WERE ABANDONED SOME TIME EARLIER. @WHEN
THE PSEUDO-PROCESS CONCLUDES ITS JOB IT MODIFIES ITS OWN STATE IN
SUCH A WAY THAT THE SCHEDULER WHICH IS LAST RESPONSIBLE FOR THE
ACTIVATION OF THE PSEUDO-PROCESS CAN DISCOVER THAT THE LATTER MAY BE
DE-ACTIVATED. @IT WOULD BE NECESSARY TO INTRODUCE A FURTHER STATUS,
SAY 'DISABLED', FOR THE PSEUDO-PROCESS. @THIS WOULD MAKE IT POSSIBLE
FOR SCHEDULERS TO ACTIVATE THE PSEUDO-PROCESS AT THEIR OWN
CONVENIENCE. @IT IS IMPORTANT TO NOTE THAT THE IMPERSONATOR OF THE
PSEUDO-PROCESS IS RESPONSIBLE FOR REMEMBERING THE 'TEXTUAL INDEX'
[@DI71] WHICH IDENTIFIES THE POINT OF PROGRESS OF THE COMPUTATION
REALISED BY THE PSEUDO-PROCESS. @THIS ADDITIONAL BURDEN IS NECESSARY
BECAUSE THE NORMAL MECHANISMS USED TO RESUME EXECUTION OF NORMAL
PROCESSES ARE NOT EMPLOYED WHEN DEALING WITH THE PSEUDO-PROCESS.
@CONSEQUENTLY, THE STATE OF THE PSEUDO-PROCESS IS NOT SAVED AND
RESTORED AUTOMATICALLY. @MOREOVER, WHEN THE PSEUDO-PROCESS BLOCKS,
ITS STATE MUST BE STORED IN STORAGE MEDIA ACCESSIBLE TO ALL THE
SCHEDULERS; THIS MAKES IT POSSIBLE FOR AN ARBITRARY SCHEDULER TO
CONTINUE THE EXECUTION OF THE PSEUDO-PROCESS WHEN IT BECOMES READY.
@THE LAST SCHEDULER TO IMPERSONATE THE PSEUDO-PROCESS WILL BE IN
POSSESION OF THE INFORMATION GATHERED BY THE PSEUDO-PROCESS IN ITS
COMMUNICATION WITH NORMAL PROCESSES. THE INFORMATION CAN BE USED TO
EFFECT THE NECCESSARY CHANGES ON THE RESOURCE WHICH IS SHARED
EXCLUSIVELY BETWEEN THE SCHEDULERS.
$V0
$P
@WE END THIS SECTION WITH THE DESCRIPTION OF A SKELETON FOR THE
INTERFACE OF THE SCHEDULERS WITH THEIR SURROUNDING WORLD I. E. THE
NORMAL PROCESSES. @THE ABSTRACT PROGRAM FOR ONE OF THE SCHEDULERS
PROCESSES IS SHOWN IN PART A) OF FIGURE 4.2-5; PART B) SHOWS THE
STRUCTURE OF A DISTINGUISHED PROCESS CALLED THE PROCESS MANAGER.
.PROCESS .LIST STANDS, AS BEFORE, FOR A DATA STRUCTURE CONTAINING A
SET
OF CAPABILITIES FOR PROCESSES WHICH IS A SUB-SET OF THE SET OF
PROCESSES EXISTING IN THE SYSTEM. @THE OBJECTIVE OF THE PROCESS
MANAGER IS TO MAINTAIN A LARGE NUMBER OF READY PROCESSES IN THE
.PROCESS .LIST, SUBJECT TO THE CONSTRAINTS IMPOSED BY THE SCARCITY OF
RESOURCES. @THIS LEAVES TO THE SCHEDULERS THE SOLE RESPONSIBILITY OF
PROCESSOR MULTIPLEXING.
$P
@THE .PROCESS .LIST IS MANIPULATED ONLY WITHIN THE CRITICAL SECTIONS
BRACKETED BY THE ROUTINE CALLS: READER ENTRY/READER EXIT AND WRITER
ENTRY/WRITER EXIT. @AS THE NAME OF THE BRACKETS SUGGEST, THE
SCHEDULERS DO NOT ALTER THE STRUCTURE OF .PROCESS .LIST; THEY ARE
ONLY
READERS OF THE SHARED RESOURCE ALTHOUGH THE VALUES OF THE STATUS
MARKS WHICH ARE REACHABLE VIA CAPABILITIES CONTAINED IN .PROCESS .LIST
ARE CHANGED BY THE SCHEDULERS. @IN CONTRAST, THE PROCESS MANAGER
REMOVES AND INSERTS CAPABILITIES FROM .PROCESS .LIST DEPENDING ON
CONCLUSIONS WHICH IT DRAWS FROM ITS INTERACTIONS WITH OTHER
PROCESSES. @THEREFORE, ANY NUMBER OF SCHEDULERS MAY BE ENGAGED IN THE
EXECUTION OF THE SELECTION ALGORITHM PROVIDED THE PROCESS MANAGER IS
NOT EXECUTING
$B0
$T2
UPDATE ( .PROCESS .LIST )
$B0
@FURTHERMORE, THE PROCESS MANAGER OUGHT TO HAVE PRIORITY OVER THE
SCHEDULERS SINCE, PRESUMABLY, ITS ALTERATIONS OF THE .PROCESS .LIST
WILL INCREASE THE NUMBER OF READY PROCESSES AVAILABLE TO THE
SCHEDULERS. @THAT IS, THE PROCESS MANAGER WILL REMOVE FROM .PROCESS
.LIST BLOCKED PROCESSES WHICH ARE EXPECTED TO REMAIN IN SUCH A STATUS
FOR A LONG TIME AND INSERT PROCESSES WHICH ARE READY FOR ACTIVATION.
$V0
$P
@FIGURE 4.2-6 SHOWS A GROUP OF ALGORITHMS FOR ENTERING AND EXITING
THE CRITICAL SECTION WHICH FULFILL THE CONDITIONS MENTIONED ABOVE.
@THE ALGORITHMS ARE A REPRODUCTION OF THE SOLUTION TO THE SECOND
READERS AND WRITERS PROBLEM PRESENTED BY @COURTOIS ET. AL. @WE WILL
ENNUMERATE THE PROPERTIES OF THE ALGORITHMS RATHER THAN REPEAT THE
DISCUSSION GIVEN BY THEIR AUTHORS [@CO71].
$A INDENT=2
$C-3 1) @ANY NUMBER OF READERS (OUR SCHEDULERS) MAY BE EXECUTING THE
CRITICAL SECTION. @HOWEVER, THE PRESENCE OF A WRITER WITHIN THE
CRITICAL SECTION EXCLUDES THE PRESENCE OF (ONE OR MORE)
READERS.
$B0
$C-3 2) @ONCE A WRITER OBTAINS CONTROL OF THE CRITICAL SECTION (VIA
THE
_@P(R) IN THE 'WRITER ENTRY' ROUTINE), NO OTHER READER WILL BE
ABLE TO ENTER UNTIL THE WRITER HAS EXITED. @FURTHERMORE, ANY
WRITER WHICH ATTEMPTS TO ENTER THE CRITICAL SECTION BEFORE THE
FIRST WRITER HAS EXITED WILL BE GIVEN PRIORITY OVER READERS.
$B0
$C-3 3) @THERE CAN BE AT MOST ONE WRITER ENGAGED IN THE EXECUTION OF
THE
CRITICAL SECTION.
$A INDENT=0
$P0
@THE UNDERLINED SYNCHRONISING STATEMENTS .(%P AND .%V) INDICATE THAT
THEY ARE OPERATIONS ON CYCLING SEMAPHORES. @SEMAPHORES W AND R ARE
THE ONLY CYCLING SEMAPHORES ACCESSED BY NORMAL PROCESSES.
$P
@WE ASSUME THAT THE CAPABILITIES CONTAINED IN .PROCESS .LIST ARE
ARRANGED IN SOME ORDER AND THAT THE LAST ELEMENT OF THE LIST IS THE
CAPABILITY FOR A PROCESS CALLED .NULL. @THE PROCESS CALLED .DUMMY IS
USED ONLY FOR THE SAKE OF THE PROGRAM'S READABILITY. @THE INNER
CRITICAL SECTION, ENCLOSED BY THE _@P(THE STATUS) $.$.$. _@V(THE
STATUS)
STATEMENTS, SIMPLY PREVENTS THE SELECTION OF THE SAME PROCESS BY MORE
THAN ONE SCHEDULER. @THE SEARCH FOR THE READY PROCESS TERMINATES WHEN
.NULL IS RETURNED BY 'NEXT PROCESS'. @A SCHEDULER WHICH FINDS A READY
PROCESS EXITS THE READER'S CRITICAL SECTION BEFORE CAUSING THE
ACTIVATION OF THE READY PROCESS. @WHEN THE ACTIVATED PROCESS BLOCKS,
THE SCHEDULER WILL PROCEED TO ENTER THE READER'S CRITICAL SECTION IN
ORDER TO SELECT A READY PROCESS ONCE AGAIN.
$P
@IF THE SEARCH FOR A READY PROCESS FAILS .(PROCESS = .NULL), THE
SCHEDULER EXECUTES THE STATEMENT:
$B0
$T2 @V ( MANAGERSEM )
$B0
AFTER HAVING EXITED THE READER'S CRITICAL SECTION. @THE VALUE OF
'MANAGERSEM' CAN BE USED BY THE ANOTHER PROCESS, E. G. THE MANAGER,
TO ESTIMATE PROCESSOR UTILISATION. @IN PARTICULAR, NOTE THAT THE
PROCESS MANAGER COULD CHOOSE TO EXECUTE A @P(MANAGERSEM) IF IT FINDS
IT APPROPIATE TO SUSPEND ITS ACTIVITIES. @OTHER ACTIONS SUCH AS
ACKNOWLEDGING EXTERNAL INTERRUPTS OR ENTER 'WAIT STATE' COULD BE
ADDED TO THIS ALTERNATIVE.
$P
@ANY NUMBER OF SCHEDULERS MAY BE EXECUTING THE SELECTION ALGORITHM
IN PARALLEL. @IN VIEW OF THIS, IT IS IMPORTANT TO DESIGN THE 'NEXT
PROCESS' ROUTINE IN SUCH A WAY THAT THE VARIOUS SCHEDULERS ARE LIKELY
TO BE EXAMINING DIFFERENT PROCESSES. @HOWEVER, THE ADVANTAGE IS
NEUTRALISED BY THE NEED TO PERFORM THE STATUS TEST IN STRICTLY
SEQUENTIAL ORDER. @THE CRITICAL SECTION PROTECTED BY SEMAPHORE 'THE
STATUS' CAN BE MODIFIED IN ORDER TO REMOVE THIS HINDRANCE. @THE
MODIFIED SCHEDULING ALGORITHM IS PRESENTED AND DISCUSSED IN APPENDIX
1. @HERE WE SIMPLY OUTLINE THE PRINCIPLE OF THE VARIATION AND POINT
OUT ITS ADVANTAGE.
$P
@THE VARIATION CONSISTS IN TREATING THE STATUS MARK AS A SEMAPHORE
AND INTERPRETING ITS VALUES AS:
$B0
$T2
.PROCESS$_STATUS = 0 MEANS 'RUNNING'
$B0
$T2
.PROCESS$_STATUS = 1 MEANS 'READY'
$B0
@THE TRANSITION FROM 'READY' TO 'RUNNING' CAN THEN BE PERFORMED BY
MEANS OF A MODIFIED @P OPERATION ON THE STATUS. @THE SIMPLIFICATION
CAN BE SIGNIFICANT BECAUSE, IGNORING MEMORY CONTENTION, TWO OR MORE
SCHEDULERS (I. E. PROCESSORS) CAN SELECT TWO OR MORE READY PROCESSES
FOR ACTIVATION STRICTLY AT THE SAME TIME. @NOTE THAT VARIABLE .PROCESS
IS LOCAL TO THE SCHEDULER EXECUTING THE ALGORITHM. @THUS, THE
PROBABILITY OF CONTENTION DUE TO SYNCHRONISATION IS REDUCED. @THE
REDUCTION IS DUE TO THE SUBSTITUTION OF A SINGLE SEMAPHORE ('THE
STATUS') GLOBAL TO ALL SCHEDULERS FOR A SET OF SEMAPHORES (THE
PROCESSES' STATUS MARK) ASSOCIATED WITH THE SPECIFIC POINT WHERE IT
IS LOGICALLY NECESSARY TO AVOID CONFLICT.
$P
@IN THE PROGRAM FOR THE PROCESS MANAGER, THE FIRST PART COMPRISES
ALL THE INTERACTIONS WITH OTHER NORMAL PROCESSES WHICH ENABLE THE
MANAGER TO DEDUCE WHETHER PROCESSES MUST BE INSERTED INTO OR REMOVED
FROM .PROCESS .LIST. @CLEARLY, THE CAPABILITY FOR THE PROCESS MANAGER
MUST RESIDE PERMANENTLY IN .PROCESS .LIST. @OTHERWISE ITS ACTIVATION
BY
THE SCHEDULERS WOULD BE IMPOSSIBLE AND THE SYSTEM WOULD BE BROUGHT TO
A STANDSTILL WHEN THE PROCESSES IN THE .PROCESS .LIST TERMINATE THEIR
ACTIVITIES. @THIS ILLUSTRATES ANOTHER IMPORTANT POINT: @THE PROCESS
MANAGER SHOULD NEVER BLOCK, WAITING FOR THE OCCURRENCE OF AN EVENT
WHICH ORIGINATES FROM ANOTHER PROCESS, UNLESS IT IS KNOWN THAT THE
SAID EVENT WILL TAKE PLACE 'SOON ENOUGH'. @A CONCRETE EXAMPLE IS
PROCESS CREATION: AN ACTIVITY WHICH PRODUCES MESSAGES (CAPABILITIES
FOR NEW PROCESSES) TO BE CONSUMED BY THE MANAGER. @THE PROCESS
MANAGER SHOULD NOT WAIT UNTIL THE BUFFER CONTAINING SUCH MESSAGES IS
NON-EMPTY.
$N
$L1 C
4.3.- DEADLOCK DETECTION AND CREATION OF SEMAPHORES.
$P3
@SEMAPHORE CREATION IS REQUESTED THROUGH THE OPERATOR:
$B0
$T2 NEWSEM = CREATE-SEMAPHORE( I,N )
$B0
WHERE I AND N ARE INTEGERS WHICH SPECIFY, RESPECTIVELY, THE INITIAL
VALUE OF THE SEMAPHORE PROPER AND THE MAXIMUM SIZE OF THE SEMAPHORE
QUEUE; I. E., N MUST BE GREATER THAN OR EQUAL TO THE MAXIMUM NUMBER
OF PROCESSES WHICH WILL BE SUPPLIED WITH A CAPABILITY ALLOWING @P
ACCESS TO THE SEMAPHORE. @THE EFFECT OF THE OPERATOR IS TO CREATE AN
OBJECT OF THE FORM SHOWN IN FIGURE 4.2-1 AND RETURN THE FULLY
PRIVILEGED CAPABILITY TO THE CALLER. @IN ADDITION, IT SUPPLIES THE
INITIAL VALUES OF THE QUEUE POINTERS, AND THE 'LOCAL' CYCLING
SEMAPHORES .CYS AND .NUMQPROC. @CYS IS INITIALISED TO 1 AND .NUMQPOR
TO
ZERO.
$P
@THE NEW OBJECT CAN BE ACCESSED ONLY BY THE OPERATORS:
$A INDENT=2
$L4 I
.P$(SEM)
.V$(SEM)
.INITIALISE$(SEM,I)
.DESROY$(SEM)
$C-4
AND
$B0
.LOOK$(SEM)
$A INDENT=0
$P
@THE RIGHT TO EXECUTE EACH OF THE ABOVE OPERATIONS IS GUARDED BY A
BIT IN THE ACCESS RIGHTS FIELD OF THE CAPABILITY FOR .SEM. .INITIALISE
IS IN CHARGE OF FLUSHING THE SEMAPHORE QUEUE AND STORING THE VALUE I,
AN INTEGER, INTO THE SEMAPHORE PROPER. @THE REMAINING LOCATIONS OF
THE SEMAPHORE'S REPRESENTATION ARE TREATED AS IN THE CREATE-SEMAPHORE
OPERATOR. @IT IS IMPORTANT TO NOTE THAT .INITIALISE AND .DESTROY
CAUSE
THE DESTRUCTION OF EVERY PROCESS WHOSE CAPABILITY IS FOUND IN THE
SEMAPHORE QUEUE. @THE SOLE POSSESSOR OF THE CAPABILITY FOR THE LAST
OPERATOR IS THE SYSTEM PROCESS IN CHARGE OF DEADLOCK DETECTION. @THE
EFFECT OF THE .LOOK OPERATOR IS TO RETURN TO ITS CALLER ALL THE
INFORMATION ABOUT THE SEMAPHORE: @THE INSTANTANEOUS VALUE OF THE
SEMAPHORE PROPER AND THE CONTENTS OF THE SEMAPHORE QUEUE.
$P
@ANY PROCESS WHICH RECEIVES THE CAPABILITY FOR A SEMAPHORE CAN
PROCEED TO EXECUTE OPERATIONS ON THE OBJECT PROVIDED IT POSSESSES THE
CAPABILITIES FOR THE NECESSARY OPERATORS. @RECALL THAT THE RECEIVER
CAN BE A USER PROCESS, THEREFORE, IT IS IMPERATIVE TO ENSURE THAT THE
SYSTEM BE ABLE TO DETECT DEADLY EMBRACE SITUATIONS WHICH MAY ARISE
FROM MISUSE OF SEMAPHORES. @IT IS IMPORTANT TO NOTE THAT THE CREATOR
OF A PROCESS IN CONJUNCTION WITH THE CREATE-PROCESS OPERATOR
DETERMINE THE COMPLETE SET OF OBJECTS WHICH THE SUBORDINATE WILL BE
CAPABLE OF ACCESSING DURING ITS LIFE-TIME. @IN PARTICULAR, A PROCESS
CAN INTERACT WITH OTHER PROCESSES ONLY IF ITS CREATOR FURNISHES IT
WITH THE SET OF (CAPABILITIES FOR) SAMAPHORES AND OTHER OBJECTS
NEEDED TO COMMUNICATE. @CONSEQUENTLY, A PROCESS WHICH CREATES A
SEMAPHORE CAN DISTRIBUTE COPIES OF THE SEMAPHORE'S CAPABILITY EITHER
TO PROCESSES WITH WHICH IT HAS ALREADY A COMMUNICATIONS LINK OR BY
SPECIFYING IT AS PART OF THE INITIAL ENVIRONMENT OF A NEW
SUB-PROCESS. @IT FOLLOWS THAT A PROCESS CANNOT ESTABLISH
COMMUNICATION LINKS WITH OTHER PROCESSES WITHOUT CONSENT FROM ITS
PARENT.
$P
@LET US ASSUME THAT, IN ORDER TO DETECT DEADLOCKS, IT IS SUFFICIENT
TO KNOW, FOR EVERY PROCESS: THE LIST OF SEMAPHORES WHICH THE PROCESS
MAY ACCESS; THE STATUS OF THE PROCESS; THE STATE OF THE SEMAPHORES
(INCLUDING THE VALUE OF THE SEMAPHORE PROPER AND OF THE SEMAPHORE
QUEUE); AND, FINALLY, THE MODES OF ACCESS WHICH A PROCESS ENJOYS ON
EACH SEMAPHORE. @ALL THE RELEVANT DATA CAN BE SUPPLIED TO A SYSTEM
PROCESS, WHICH WE CALL THE DEADLOCK DETECTOR OR 'DEADLOCKER', SIMPLY
BY PASSING TO IT THE CAPABILITY FOR EVERY SEMAPHORE WHICH IS MADE
AVAILABLE TO A USER PROCESS IN ADDITION TO THE IDENTITY OF THE
PROCESS. @WE WILL SAY THAT A SEMAPHORE IS 'DECLARED' BY A PROCESS OR
ON BEHALF OF A PROCESS WHEN THE PAIR:
$B0
$T2 SEMAPHORE,PROCESS
$B0
IS PASSED TO THE DEADLOCKER. @IN OTHER WORDS, THE ACT OF PASSING THE
ABOVE PAIR OF CAPABILITIES TO THE DEADLOCKER IS EQUIVALENT TO THE
DECLARATION OF THE SEMAPHORE TO THE SYSTEM.
$P0
THE CRUCIAL ASPECT ABOUT THE DECLARATION OF SEMAPHORES IS THAT THE
SYSTEM MUST ENSURE THAT ONLY THOSE PROCESSES WHICH HAVE DECLARED A
GIVEN SEMAPHORE BE ABLE OF PERFORMING OPERATIONS ON IT. @IT IS
POSSIBLE TO RELAX THIS RESTRICTION IF THE DEADLOCKER IMPOSES HARSH
PENALTIES ON THE USE OF SEMAPHORES WHICH HAVE NOT BEEN DECLARED. @FOR
INSTANCE, THE APPEARANCE OF THE CAPABILITY FOR A PROCESS IN THE QUEUE
OF A SEMAPHORE WHICH THE PROCESS HAS NOT DECLARED CAN BE TREATED AS A
DEADLOCK SITUATION. @HOWEVER, A SERIOUS PROBLEM OF THIS SORT OF
ATTITUDE IS THAT A PROCESS CAN DELIBERATELY CAUSE GHOST DEADLOCKS.
@NOTE THAT A PROCESS WHICH FAILS TO DECLARE ITS INTENTION (OR
ABILITY)
TO EXECUTE @V OPERATIONS ON A GIVEN SEMAPHORE MAY LEAD THE DEADLOCKER
TO FIND A DEADLY EMBRACE SITUATION WHEN THE PRESENCE OF THE
DECLARATION MAY HAVE BEEN SUFFICIENT TO CONCLUDE THE ABSENCE OF
DEADLOCK. @THEREFORE, IT SEEMS LESS DANGEROUS TO PERMIT @V ACCESS TO
UNDECLARED SEMAPHORES. @HOWEVER, WE PREFER TO CONSIDER THE DEADLOCK
DETECTOR AS AN ALLY, RATHER THAN AN ENEMY OF USER PROCESSES. @HENCE,
WE WILL EXAMINE VARIOUS SCHEMES TO ENFORCE THE FAITHFUL DECLARATION
OF SEMAPHORES FOR THIS ENABLES THE SYSTEM TO DRAW MORE ACCURATE
CONCLUSIONS ABOUT THE PRESENCE OR ABSENCE OF DEADLY EMBRACE
SITUATIONS. @FIRSTLY, WE WILL ANALYSE HOW IT IS POSSIBLE FOR A
PROCESS TO OBTAIN A SEMAPHORE'S CAPABILITY IN ORDER TO DISTINGUISH
THE POINT IN TIME AT WHICH SEMAPHORES HAVE TO BE DECLARED.
$A INDENT=2
$C-3 1) @THE PROCESS CAN CREATE A SEMAPHORE BY MEANS OF INVOKING THE
CREATE-SEMAPHORE OPERATOR. @CLEARLY, THE NEW SEMAPHORE CANNOT
BE EMPLOYED IN ANY MEANINGFUL WAY BEFORE COPIES OF ITS
CAPABILITY ARE DISTRIBUTED TO OTHER PROCESSES.
$B0
$C-3 2) @THE PROCESS CAN RECEIVE THE CAPABILITY FOR A SEMAPHORE FROM
ANOTHER PROCESS. @THIS IMPLIES THAT THE RECEIVER HAS ALREADY A
COMMUNICATIONS LINK WITH THE SENDER. @NOTE THAT THE CAPABILITY
FOR A SEMAPHORE CAN BE DEPOSITED IN THE INITIAL ENVIRONMENT OF
A NEW PROCESS. @IN THIS SENSE, THE PARENT OF A PROCESS HAS AT
LEAST A MOMENTARY COMMUNICATIONS LINK WITH ITS SUBORDINATES.
$A INDENT=0
$P0
@WITH RESPECT TO 1) WE CAN SAY THAT SEMAPHORE CREATION CAN GENERATE
AT MOST THE SINGLE DECLARATION ON BEHALF OF THE CREATOR OF THE
SEMAPHORE; THEREAFTER, THE EARLIEST POSSIBLE TIME AT WHICH SEMAPHORES
CAN BE DECLARED IS DISTRIBUTION TIME.
$P
@A RELATIVELY SIMPLE WAY OF ENFORCING SEMAPHORE DECLARATION AT
DISTRIBUTION TIME CONSISTS IN DEFINING SEMAPHORE CREATION AS AN
EXCLUSIVE PREROGATIVE OF A UNIQUE SYSTEM PROCESS: THE SEMAPHORE
CREATOR. @THE SEMAPHORE CREATOR IS THE OWNER OF THE CAPABILITY FOR
THE CREATE-SEMAPHORE OPERATOR. @SEMAPHORE CREATION CAN BE REQUESTED
BY MEANS OF MESSAGES TO THE SEMAPHORE CREATOR OF THE FORM:
$B0
$T2 NEWSEM, .PROCESSES
$B0
@HERE .PROCESSES IS A LIST OF THE NAMES OF THE PROCESSES TO WHICH
COPIES OF THE CAPABILITY FOR THE SEMAPHORE ARE TO BE DISTRIBUTED.
@THE SEMAPHORE CREATOR IS IN CHARGE OF DECLARING EVERY THE NEW
SEMAPHORE ON BEHALF OF EACH OF THE RECIEVING PROCESSES. @THIS
REQUIRES COMUNICATION LINKS BETWEEN THE SEMAPHORE CREATOR AND EVERY
POSSIBLE (USER) PROCESS IN THE SYSTEM. @IN ADDITION, THE SEMAPHORE
CREATOR MUST HAVE THE MEANS TO PREVENT PROCESSES FROM DISTRIBUTING
COPIES OF THE CAPABILITY FOR A NEW, DECLARED SEMAPHORE TO OTHER
PROCESSES. @THEREFORE, IN FACT, THE SEMAPHORE CREATOR REQUIRES
CONTROL POWERS OVER (RATHER THAN SIMPLE COMMUNICATION CHANNELS WITH)
USER PROCESSES. @THE RIGHT TO TRANSMIT A SEMAPHORE TO A PROCESS CAN
BE CONTROLLED BY ESTABLISHING THAT THE NAMES IN THE .PROCESSES LIST
BE
CAPABILITIES; E. G., THE CAPABILITY FOR THE RECIEVING PROCESS.
@FINALLY, NOTE THAT IT IS ALSO IMPORTANT TO CONTROL (PERHAPS TO
PREVENT) THE ABILITY TO TRANSMIT MESSAGES CONTAINING PROCESS NAMES.
@MECHANISMS TO CONTROL THE INTER-PROCESS TRANSMISSION OF CAPABILITIES
FOR SEMAPHORES ARE DISCUSSED BELOW.
$P
@A MORE RESTRICTIVE IMPLEMENTATION IS TO INCLUDE ALL THE SEMAPHORES
WHICH A PROCESS MAY EVER ACCESS IN ITS INITIAL ENVIRONMENT. @IN
CONTRAST WITH THE PREVIOUS ALTERNATIVE, THIS REMOVES THE NEED TO
DEFINE A SYSTEM PROCESS WITH CONTROL POWERS OVER ALL USER PROCESSES.
@THE REASON IS THAT THE CREATE-PROCESS OPERATOR HAS IMPLICIT POWERS
OF
CONTROL OVER THE NEW PROCESS, YET THE POWER IS MOMENTARY. @THE
DRAWBACK OF THE SCHEME IS THAT IT BECOMES IMPOSSIBLE FOR PROCESSES TO
ACQUIRE OR CREATE NEW SEMAPHORES DYNAMICALLY. @IN PARTICULAR, A
PROCESS WHICH CREATES NEW PROCESSES MUST POSSESS A PRIORI ALL THE
SEMAPHORES WHICH IT INTENDS TO MAKE AVAILABLE TO THE NEW SUBORDINATE.
@HOWEVER, SINCE THE CALLER OF CREATE-PROCESS IS NOT ALLOWED TO PASS
CAPABILITIES FOR SEMAPHORES TO ANY OTHER PROCESS, IT BECOMES
NECESSARY TO GIVE THE CREATE-PROCESS OPERATOR CONTROL POWERS OVER ITS
CALLER. @THUS, THE CREATE-PROCESS OPERATOR WOULD HAVE TO ISSUE A
REQUEST TO A PRIVILEGED SYSTEM PROCESS WITH PRACTICALLY UNLIMITED
PRIVILEGES OVER THE REQUESTING PROCESS. @THIS IS ALMOST IDENTICAL TO
THE FIRST IMPLEMENTATION DESCRIBED ABOVE. @THE CREATE-PROCESS
OPERATOR IS THE ONLY OPERATOR WHICH CAN SEND MESSAGES TO THE
SEMAPHORE CREATOR PROCESS. @IN VIEW OF THIS, THE ACTIVITIES OF THE
CREATE-PROCESS OPERATOR COULD BE EXTENDED TO INCLUDE THE CREATION AND
DECLARATION OF NEW SEMAPHORES ON BEHALF OF THE CALLER AND ON BEHALF
OF THE NEWLY CREATED PROCESS. @IN SUMMARY, A PROCESS IS CAPABLE OF
ACQUIRING NEW SEMAPHORES ONLY AS A RESULT OF THE CREATION OF A
SUB-PROCESS. @THE PROBLEM IS THAT A GIVEN PROCESS CANNOT EMPOWER ITS
CHILDREN TO COMMUNICATE DIRECTLY.
$P
@WE DISCUSS THE DYNAMIC DECLARATION OF SEMAPHORES (I. E.
IMMEDIATELY PRIOR TO THE USAGE) BELOW, AFTER EXPLORING SEVERAL
SCHEMES TO PREVENT PROCESSES FROM DISTRIBUTING DECLARED SEMAPHORES TO
OTHER PROCESSES.
$P
@THE VARIOUS APPROACHES TO ACCOMPLISH THE DESIRED OBJECTIVE CAN BE
SUMMARISED IN THE FOLLOWING POINTS:
$A INDENT=2
$C-3 I) @FORBID THE TRANSMISSION OF MESSAGES CONTAINING CAPABILITIES
FOR
OBJECTS OF TYPE SEMAPHORE.
$B0
$C-4 II) @DEPOSIT THE CAPABILITIES FOR ALL SEMAPHORES WITHIN THE
PROCESS'
ADDRESS SPACE IN SUCH A WAY THAT THE PASSING OF THOSE
CAPABILITIES TO ANOTHER PROCESS IS PREVENTED.
$B0
$C-5 III) @INCLUDE A MARKER IN THE CAPABILITY FOR EVERY SEMAPHORE
DENOTING
THE IDENTITY OF THE UNIQUE PROCESS WHICH IS ENTITLED TO USE THE
OBJECT.
$A INDENT=0
$P0
@THE COST OF ENFORCING APPROACH I) IS INTOLERABLE. @THE SYSTEM
WOULD BE FORCED TO SCAN THE TEXT OF EVERY INTER-PROCESS MESSAGE IN
ORDER TO ENSURE THAT TE RESTRICTION IS OBEYED. @CLEARLY, THE APPROACH
PRECLUDES THE POSSIBILITY OF ALLOWING PROCESSES TO COMMUNICATE
WITHOUT CONSTANT SYSTEM INTERVENTION. @THE RESTRICTION COULD BE
STRENGTHENED TO FORBID THE TRANSMISSION OF CAPABILITIES FOR OBJECTS
OF ANY TYPE. @HOWEVER, IT IS DIFFICULT TO CONCEIVE A WAY TO ENFORCE
THE STRONGER CONSTRAINT SHORT OF BANNING THE SHARING OF CAPABILITY
SEGMENTS.
$P
@ALTERNATIVE II) SEEMS MORE REASONABLE, IF ONLY BECAUSE IT CAN
CERTAINLY BE IMPLEMENTED MORE EFFFICIENTLY.
$V0
$P
@THE FIRST WAY TO IMPLEMENT THIS CONSTRAINT IS TO ENCLOSE THE
USER'S ENVIRONMENT WITHIN THE ENVIRONMENT OF AN OPERATOR CONSTRUCTED
BY THE SYSTEM DESIGNER. @THE SITUATION IS DEPICTED IN FIGURE 4.3-1.
@THE USER PROGRAMS ARE EXECUTED IN THE PROTECTION REGIMES OF THE
OPERATORS CALLED: .USER1, .USER2,$.$.$. WHICH IN TURN ARE ENCLOSED
WITHIN
THE ENVIRONMENTS OF OPERATORS .FIRST1, .FIRST2, $.$.$.. @THUS,
OPERATOR
@F@I@R@S@TI CAN BE USED BY THE SYSTEM DESIGNER TO FORCE THE USER TO
COMPLY
WITH ARBITRARY SYSTEM POLICIES. @IN OUR APPLICATION, OPERATOR .FIRST
RETAINS THE CAPABILITIES FOR ALL THE SEMAPHORES AND THE USER PROGRAM
IS REQUIRED TO .RETURN TO ITS SURROUNDING ENVIRONMENT IN ORDER TO
PERFORM OPERATIONS ON SEMAPHORES.
$P
@OUR MAIN OBJECTION TO THE APPROACH IS THAT IT SIMPLY SHIFTS THE
CONCEPT OF PRIVILEGED/NON-PRIVILEGED PROCESSES TO
PROVILEGED/NON-PRIVILEGED OPERATORS. @NOTE THAT THE USER PROGRAMS DO
NOT ENJOY ANY MODE OF ACCESS TO THE OBJECTS WHOSE CAPABILITIES ARE
CONTAINED EXCLUSIVELY IN .FIRST'S ENVIRONMENT. @THE ARTIFICIAL .RETURN
FOR THE SOLE PURPOSE OF REQUESTING THE EXECUTION OF A CERTAIN
ACTIVITY IS ALMOST IDENTICAL TO THE .SVC OF CONVENTIONAL
ARCHITECTURES. @THE APPROACH CAN BE REJECTED FOR THE ABOVE REASONS
WITHOUT DELVING INTO THE DEFFICULTIES AND INEFFICIENCIES INTRODUCED
BY THE NEED TO RESTORE THE ENVIRONMENT OF THE USER OPERATOR WHICH
REQUESTS THE ACTIVITY.
$P
@A SECOND WAY TO IMPLEMENT SCHEME II) EMPLOYS THE USE-ACCESS MODE
OF CAPABILITY SEGMENTS. @AS DESCRIBED IN SECTION 3.5, THE USE ACCESS
BIT ENTITLES THE POSSESSOR OF THE CAPABILITY FOR A @C-SEG TO PRESENT
CAPABILITIES CONTAINED IN THE @C-SEG TO THE .INVOKE MECHANISM. @ANY
OTHER FORM OF ACCESS, E. G. READ, MUST BE AUTHORISED EXPLICITLY BY
THE CORRESPONDING ACCESS BIT. @HENCE, A USE-WRITE-ONLY @C-SEG CAN BE
UTILISED AS THE CONTAINER OF CAPABILITY FOR THE SEMAPHORES WHICH A
GIVEN PROCESS IS ALLOWED TO ACCESS. @THIS EFFECTIVELY PREVENTS A
PROCESS FROM EXTRACTING THE CAPABILITY FOR A SEMAPHORE FROM ITS PLACE
OF RESIDENCE FOR THE PURPOSE OF PASSING IT TO ANOTHER PROCESS.
@UNFORTUNATELY, THE ARGUMENT HAS TWO FLAWS. @FIRSTLY, THE PROCESS IS
NOT PREVENTED FROM PASSING THE CAPABILITY FOR THE USE-WRITE-ONLY
@C-SEG CONTAINING THE CAPABILITIES FOR THE COMPLETE COLLECTION OF
SEMAPHORES ACCESSIBLE TO THE PROCESS. @SECONDLY, A GIVEN
SUB-ENVIRONMENT OF THE PROCESS (I. E. AN OPERATOR INVOKED BY THE
PROCESS) IN QUESTION CAN HAVE ACCESS TO ALL OF NONE OF THE SEMAPHORES
AVAILABLE TO THE PROCESS. @WE NOW DELVE INTO THESE TWO PROBLEMS
LABELLED @PROBLEM 1 AND @PROBLEM 2.
$B
%@PROBLEM 1.
$P
@IT IS POSSIBLE TO CIRCUMVENT THE FIRST PROBLEM BY ASSOCIATING A
NON-READABLE @C-SEG WITH EVERY PROCESS. @THE CONTENTS OF THIS NEW
SEGMENT, WHICH WE CALL THE GLOBAL SEGMENT (@G-SEG), ARE ACCESSIBLE,
ALTHOUGH NOT READABLE, FROM EVERY OPERATOR INVOKED BY THE PROCESS.
@IN ADDITION, THE CAPABILITY FOR THE @G-SEG CANNOT BE MANIPULATED BY
ANY PROGRAM EXECUTED BY THE PROCESS.
$P
@THE OBVIOUS PLACE TO STORE THE CAPABILITY FOR THE @G-SEG IS YET
ANOTHER NON-PROGRAMMABLE PROCESSOR CAPABILITY REGISTER: @THE @G-REG.
@THE @G-REG CAN BE SIMULATED BY MEANS OF PERMITTING CERTAIN SYSTEM
OPERATORS TO ACCESS THE FIRST FEW SLOTS OF THE @S-SEG IN ADDITION TO
THE WINDOW ALLOCATED NORMALLY BY THE .INVOKE MECHANISM. @A SIMULATED
@G-REG IS LESS COSTLY BUT IT IMPLIES SOME FORM OF PRIVILEGED MODE.
@LET US EXAMINE WHAT IS ACCOMPLISHED BY ASSOCIATING A NON-READABLE
CAPABILITY SEGMENT WITH EVERY PROCESS.
$V0
$P
@FIRSTLY, ANY PROCESS CAN CREATE A SEMAPHORE DIRECTLY; THAT IS,
WITHOUT INTERVENTION FROM PRIVILEGED SYSTEM PROCESSES. @THE
CREATE-SEMAPHORE OPERATOR CREATES THE NEW OBJECT; DECLARES IT TO THE
SYSTEM AND PUTS THE NEW CAPABILITY IN THE @G-SEG OF THE CALLING
PROCESS. @THE OPERATOR RETURNS TO ITS CALLER THE ADDRESS (A NORMAL
VALUE) OF THE CAPABILITY FOR THE NEW SEMAPHORE. @FROM THE SYSTEM'S
VIEWPOINT IT IS NOW SAFE FOR THE USER TO EXECUTE SYNCHRONISING
PRIMITIVES ON THE SEMAPHORE. @THE CREATE-SEMAPHORE OPERATOR MUST ALSO
DISTRUBUTE THE NEW CAPABILITY BECAUSE THE CALLER WILL NEVER BE ABLE
TO PRODUCE A COPY OF THE CAPABILITY. @THE DIAGRAM OF FIGURE 4.3-2
SHOWS HOW PROCESS @A REQUESTS THE CREATION OF A NEW SEMAPHORE CALLED
.NEW AND ITS DISTRUBUTION TO PROCESS .B. @PROCESS @A IS BOUND TO THE
USER DEFINED OPERATOR .UA AND EXECUTES:
$B0
$T2 NEW = CREATE-SEMAPHORE(I,N,@L@I@N@K,@B)
$B0
@THE TWO NEW PARAMETERS, .LINK AND .B, ARE, RESPECTIVELY, A
COMMUNICATIONS LINK AND THE NAME OF THE TARGET PROCESS. .LINK IS AN
EXTENDED OPERAND OF TYPE, SAY 'SEM LINK'. @THE REPRESENTATION OF THE
OBJECT CONTAINS A SET OF SEMAPHORES AND MESSAGE BUFFERS WHICH ENABLE
THE PROCESSES TO COMMUNICATE. @THE CAPABILITY FOR THE NEW SEMAPHORE,
.NEW, IS CREATED AND PLACED IN THE LTH SLOT OF @A'S @G-SEG. @THE
RESULT
OF CREATE-SEMAPHORE IS THE VALUE L. @THE TRANSMISSION OF .NEW TO @B
IS
ACCOMPLISHED THROUGH OPERATOR 'SEND SEM' OF TYPE 'SEM LINK' WHICH IS
PRIVATE TO CREATE-SEMAPHORE. @AT THE OTHER END, @B CAN RETRIEVE THE
CAPABILITY FOR .NEW ONLY BY MEANS OF INVOKING OPERATOR 'RECEIVE SEM'
WHICH IS ALSO OF TYPE 'SEM LINK'. @THIS LAST OPERATOR IS IN CHARGE OF
RETRIEVING THE CAPABILITY FOR .NEW FROM THE REPRESENTATION OF .LINK,
VERIFYING THAT THE SEMAPHORE WAS INTENDED FOR @B AND DECLARING .NEW
ON
BEHALF OF PROCESS .B. @THEN IT PROCEEDS TO PUT .NEW INTO THE @G-SEG
OF
.B. @SOME OF THE ADVANTAGES OBTAINED ARE: A) @DISTRIBUTION TAKES
PLACE
WITHOUT THE AID OF PRIVILEGED PROCESSES. B) @PROCESSES @A AND @B WERE
FURNISHED WITH THE APPROPIATE OPERANDS AND OPERATORS OF TYPE 'SEM
LINK' BY THEIR RESPECTIVE PARENTS. @WITHOUT THESE, THE TRANSMISSION
WOULD NOT HAVE BEEN POSSIBLE. C) @IF @A WERE EMPOWERED TO TRANSMIT
THE
CAPABILITY FOR .LINK (I. E. IF .LINK WERE NOT STORED IN THE @G-SEG)
THEN
@A COULD ESTABLISH CHANNELS BETWEEN @B AND ANY PROCESS WITH WHICH .A,
BUT NOT .B, HAS ALREADY COMMUNICATIONS LINKS. @ON THE NEGATIVE SIDE:
D) .NEW IS ACCESSIBLE FROM EVERY ENVIRONMENT OF @A (OR .B) WHICH
POSSESSES CAPABILITIES FOR THE .P/V OPERATORS. E) @IN ADDITION TO (OR
BECAUSE OF) THE NON-SELECTIVE PROTECTION OF SEMAPHORES, A NUMBER OF
SYSTEM WIDE CONVENTIONS HAVE TO BE ADOPTED BY PROCESSES WITH REGARDS
TO THE USAGE OF @G-SEG'S. @DISADVANTAGE E) IS INTOLERABLE; E) IS
INCONVENIENT. @BOTH PROBLEMS ARE A FORMULATION OF @PROBLEM 2
DISCUSSED
BELOW.
$B
%@PROBLEM 2.
$P
@THE PROBLEM CAN BE AMELIORATED BY USING A COPY BIT IN EVERY
CAPABILITY IN ADDITION TO THE @G-SEG. @AS DISCUSSED IN SECTION 2.5,
EVERY CAPABILITY CONTAINS A COPY BIT INITIALISED TO 1 AT CREATION
TIME. @THE READ-CAPABILITY OPERATOR REFUSES TO SATISFY REQUESTS TO
READ CAPABILITIES IN WHICH THE COPY BIT IS 0. @IT IS WORTHWHILE TO
POINT OUT THAT NOTHING IS GAINED BY PREVENTING OPERATORS FROM
PRODUCING COPIES OF CAPABILITIES UNLESS THE @G-SEG IS ALSO AVAILABLE.
@IN ORDER TO SEE THIS, CONSIDER AN OPERATOR, .OP, WHOSE @I-SEG
CONTAINS
THE CAPABILITY FOR SEMAPHORE @S WHICH IS NON-COPYABLE. @ASSUME THAT @S
HAS BEEN DECLARED ON BEHALF @A AND THAT @A IS BOUND TO THE USER
OPERATOR, .U, WHICH HAS A CAPABILITY FOR .OP. @THE SITUATION IS
SCHEMATISED IN FIGURE 4.3-3.
$V0
$P
@IF @A IS PERMITTED TO TRANSMIT THE CAPABILITY FOR .OP TO OTHER
PROCESSES, THEN, CLEARLY, THOSE PROCESSES WOULD BE ABLE TO REQUEST .OP
TO PERFORM OPERATIONS ON .S. @TO PREVENT @A FROM DOING SO REQUIRES
THAT
THE CAPABILITY FOR .OP CONTAINED IN @U'S ENVIRONMENT BE ALSO
NON-COPYABLE. @FURTHERMORE, THE ARGUMENT NEEDS TO BE REPEATED FOR
EVERY USER DEFINED OPERATOR WHICH POSSESSES A CAPABILITY FOR @U OR A
CAPABILITY FOR ANY OPERATOR WHICH LEADS TO A CALL OF .U. @THE
ULTIMATE
SITUATION IS THE SAME AS OUR DESCRIPTION OF THE FIRST IMPLEMENTATION
OF SCHEME II). @THAT IS TO SAY, IF THERE IS A USER DEFINED PROTECTION
REGIME IN A PATH OF CALLS FROM THE INITIAL ENVIRONMENT OF A PROCESS
TO AN ENVIRONMENT CONTAINING THE CAPABILITY FOR A SEMAPHORE, THEN THE
CAPABILITY WHICH ENABLES THE USER ENVIRONMENT TO 'FOLLOW THE PATH'
HAS TO BE NON-COPYABLE. @CLEARLY, EVERY OPERATION WHICH MAY LEAD TO
THE USE OF A SEMAPHORE MUST ORIGINATE FROM THE INITIAL ENVIRONMENT OF
THE PROCESS.
$P
@THE COPY BIT IS EFFECTIVE IN CONJUNCTION WITH THE @G-SEG. @SUPPOSE
IN OUR ABOVE EXAMPLE THE CAPABILITY FOR .OP IS PLACED IN THE @G-SEG.
@NOW .OP IS ACCESSIBLE FROM EVERY PROTECTION REGIME ENTERED BY .A.
@HOWEVER, IN ORDER TO INVOKE .OP IT IS ALSO NECESSARY TO POSSESS A
CAPABILITY FOR AN OPERAND OF .OP'S TYPE. @THEREFORE, ACCESS TO .OP
CAN
BE CONTROLLED THROUGH THE ADMINISTRATION OF THE CAPABILITIES FOR
OPERANDS OF THE CORRESPONDING TYPE. @THIS OBSERVATION IS THE BASIS
FOR THE SCHEME DESCRIBED BELOW.
$P
@THE PRINCIPLE UNDERLYING ALTERNATIVE III) IS STRAIGHTFORWARD.
@SUPPOSE WE HAVE TWO KINDS OF SEMAPHORES: MARKED SEMAPHORES AND
UNMARKED SEMAPHORES. @THE CAPABILITY FOR A MARKED SEMAPHORE CARRIES A
FLAG WHICH SAYS SOMETHING LIKE 'USEABLE BY PROCESS .U'. @THE
SYNCHRONISING PRIMITIVES OR THE PROTECTION MECHANISM CAN USE THE MARK
TO VERIFY THE PROPRIETY OF OPERATIONS REQUESTED BY EVERY PROCESS.
@THE DECLARATION OF SEMAPHORES CAN BE ENFORCED BY PROVIDING AN
OPERATOR WHICH MARKS THE CAPABILITY FOR THE SEMAPHORE AFTER
TRANSMITTING THE PAIR OF CAPABILITIES:
$B0
$T2 PROCESS,SEMAPHORE
$B0
TO THE SYSTEM'S DEADLOCK DETECTOR. @THE DISCIPLINE ALLOWS
CAPABILITIES FOR SEMAPHORES TO WANDER AMID PROCESSES WITHOUT
RESTRICTION SIMPLY BECAUSE SUCH CAPABILITIES CANNOT BE EMPLOYED
SUCCESSFULLY UNTIL THEY ARE DECLARED.
$P
@THE SCHEME IS IDEAL FOR OUR PURPOSES; IT RELIEVES THE SYSTEM FROM
THE TASKS OF CREATION AND DISTRIBUTION OF COMMUNICATIONS LINKS
BETWEEN PROCESSES, YET IT ENSURES THAT SUCH LINKS CANNOT BE HIDDEN
FROM THE SYSTEM.
$P
@THE MARKER IN THE CAPABILITIES FOR SEMAPHORES MUST ALLOW THE
UNAMBIGUOUS DISTINCTION OF EVERY PROCESS TO WHICH THE SEMAPHORE'S
CAPABILITY IS TO BE DISTRIBUTED. @CONSEQUENTLY, THE MARKERS HAVE TO
BE CHOSEN FROM ONE OF THE UNIVERSALLY UNIQUE NAMES. @OTHERWISE THE
SYSTEM WOULD HAVE TO BE FACED WITH TREATING SEMAPHORES AS RESOURCES.
@A TRIVIAL IMPLEMENTATION CONSISTS OF EXTENDING THE REPRESENTATION OF
SEMAPHORES TO INCLUDE THE LIST OF PROCESS CAPABILITIES INDICATING THE
IDENTITIES OF THE PROCESSES WHICH HAVE DECLARED THE SEMAPHORE AND
HENCE HAVE THE RIGHT TO PERFORM OPERATIONS ON IT. @CLEARLY, THIS IS A
VERY UNSATISFACTORY IMPLEMENTATION. @THE TYPE EXTENSION MECHANISM
PERMITS ONE TO DEFINE THE DECLARATION OF SEMAPHORES WITHOUT DEVIATING
FROM THE BASIC PRECEPT OF LEAVING ALL ACTIONS CONCERNING THE
VALIDATION OF ACCESS TO OBJECTS IN THE HANDS OF THE PROTECTION
MECHANISM.
$P
@IN THE FOLLOWING, WE WILL DISCUSS ONLY THE @P OPERATOR, ALL
CONSIDERATIONS REGARDING THE @V OPERATOR ARE ANALOGOUS. @UNLESS
OTHERWISE STATED WE ASSUME THAT SYSTEM CREATED OPERATORS ARE NOT
WILLING TO RETURN TO THEIR CALLERS ANY CAPABILITY CONTAINED IN THEIR
PRIVATE ADDRESS SPACES.
$P
@THE SYSTEM PREVENTS THE USER PROCESS @A FROM ACCESSING THE
CAPABILITY FOR THE @P OPERATOR DIRECTLY SIMPLY BY ENCLOSING THE
LATTER
WITHIN THE @I-SEG OF THE EXTENDED @P OPERATOR, .XP, CREATED BY THE
SYSTEM. @OPERATOR .XP IS OF TYPE .XSEM (EXTENDED SEMAPHORE). @IN VIEW
OF THIS RESTRICTION, THE USER CAN BE ALLOWED TO ACCESS CAPABILITIES
FOR OBJECTS OF TYPE SEMAPHORE DIRECTLY. @IN PARTICULAR, PROCESS @A
ENJOYS ACCESS TO THE CREATE-SEMAPHORE SYSTEM OPERATOR AND THE LATTER
RETURNS THE CAPABILITIES FOR THE SEMAPHORES IT CONSTRUCTS TO THE
LATTER. @SUPPOSE @A OWNS THE CAPABILITY FOR SEMAPHORE .S. @IN ORDER
TO
PERFORM @P OPERATIONS ON .S, THE USER MUST OBTAIN @THE CAPABILITY FOR
AN
OPERAND OBJECT OF TYPE .XSEM. @THIS CAN BE DONE ONLY BY MEANS OF AN
OPERATION OF THE FORM:
$B0
$T2 .DCL = DECLARE-SEMAPHORE(@S)
$B0
@DECLARE-SEMAPHORE IS A SYSTEM CREATED OPERATOR WHICH CONSTRUCTS AN
EXTENDED OBJECT OF THE FORM SHOWN IN FIGURE 4.3-4 AND RETURNS THE
CAPABILITY FOR THE NEWLY CREATED OBJECT TO ITS CALLER. @IN ADDITION
TO CREATING THE EXTENDED OBJECT, DECLARE-SEMAPHORE TRANSMITS THE PAIR
$V0
$B0
$T2 PROCESS,@S
$B0
TO THE DEADLOCK DETECTOR. @CLEARLY, DECLARE-SEMAPHORE MUST POSSESS A
SET OF CAPABILITIES TO COMMUNICATE WITH THE DEADLOCKER AND ALSO
CAPABILITY 'PROCESS': @THE CAPABILITY FOR THE CALLING PROCESS. @NOTE
THAT THE CAPABILITY FOR THE CALLING PROCESS CANNOT BE STORED IN THE
@G-SEG, BECAUSE COPIES OF IT HAVE TO BE DISTRIBUTED TO THE DEADLOCK
DETECTOR. @ALSO, THE @P OPERATOR MUST DEPOSIT A COPY OF THE PROCESS'
CAPABILITY IN THE SEMAPHORE QUEUE WHENEVER THE PROCESS IS BLOCKED.
@THE .XSEM TYPE HAS TO BE PRIVATE TO PROCESS .A. @OTHERWISE THE
CAPABILITY FOR .DCL (THE DECLARED SEMAPHORE) COULD BE DISTRIBUTED TO
OTHER PROCESSES. @MOREOVER, PROCESS @A MUST BE PREVENTED FROM PASSING
THE CAPABILITY FOR .XP TO OTHER PROCESSES. @TO THIS END, THE
UNIVERSALLY UNIQUE TYPE .XSEM IS CREATED BY THE SYSTEM UPON THE
CREATION OF EVERY (USER) PROCESS AND THE CAPABILITY FOR EVERY
OPERATOR OF TYPE .XSEM IS STORED IN THE @G-SEG OF THE CORRESPONDING
PROCESS.
$P
@WE HAVE DESCRIBED SEMAPHORE DECLARATION STRICTLY IN TERMS OF THE
TYPE EXTENSION MECHANISM. @IN ADDITION, VALIDATION OF REQUESTS TO
ACCESS SEMAPHORES TAKES PLACE VIA THE NORMAL PROTECTION ACTIVITIES.
$P
@AN ANOMALLY OF THE SCHEME IS THAT THE TYPE OF USEABLE I. E.
DECLARED, SEMAPHORES HAS ONLY LOCAL SIGNIFICANCE. @THE IMPLICATION IS
THAT DECLARED SEMAPHORES ARE NON-SHARED OBJECTS; THIS CONTRADICTS THE
NOTION THAT SEMAPHORES ARE, BY DEFINITION, SHARED VARIABLES.
$N
$E