DIRECTORY DragOps, PrincOps USING [zEXCH], -- SIM only PrincOpsUtils USING [PsbHandleToIndex, ReadPSB], -- SIM only Process USING [Detach, priorityBackground, SetPriority, Yield], -- SIM only SimProcess; SimProcessImpl: MONITOR LOCKS lock USING lock: SimProcess.SimLock -- will be PROGRAM in RDI -- IMPORTS PrincOpsUtils, Process, SimProcess -- in RDI: IMPORTS Process; note in SIM Process is the Dorado version EXPORTS SimProcess -- in RDI: exports Process = BEGIN OPEN C7Process: Process, SimProcess; -- in RDI: OPEN Process WordPtr: TYPE = LONG POINTER TO Word; WordSeq: TYPE = LONG POINTER TO WordSeqRep; WordSeqRep: TYPE = RECORD [SEQUENCE COMPUTED CARDINAL OF Word]; StackRegister: TYPE = MACHINE DEPENDENT {min (0), max (127)}; SimBackground: PROC ~ { C7Process.SetPriority[C7Process.priorityBackground] }; SimYield: PROC ~ { C7Process.Yield[] }; processorMap: REF ProcessorMap _ NEW [ProcessorMap _ ALL[NIL]]; ProcessorMap: TYPE ~ ARRAY [0..1024) OF Processor; SimThisProcessor: PROC RETURNS [p: Processor] ~ { processorIndex: CARDINAL _ PrincOpsUtils.PsbHandleToIndex[PrincOpsUtils.ReadPSB[]]; IF processorIndex >= 1024 THEN ERROR; p _ processorMap[processorIndex]; IF p = NIL THEN ERROR; }; SimSetThisProcessor: PROC [p: Processor] ~ { processorIndex: CARDINAL _ PrincOpsUtils.PsbHandleToIndex[PrincOpsUtils.ReadPSB[]]; IF processorIndex >= 1024 THEN ERROR; processorMap[processorIndex] _ p; }; SimCallAndSuspend: ENTRY PROC [lock: SimLock, process: Process, proc: PROC, caller: ATOM] ~ { ENABLE UNWIND => NULL; IF proc # NIL THEN TRUSTED { C7Process.Detach[ FORK SimDoCall[process, proc, caller] ] }; WHILE NOT process.sim.awakened DO WAIT process.sim.awakenEvent ENDLOOP; process.sim.awakened _ FALSE; SimSetThisProcessor[process.sim.processor]; -- SIM: processor may have changed }; SimDoCall: PROC [process: Process, proc: PROC, caller: ATOM] ~ { SimBackground[]; -- because we just forked SimSetThisProcessor[process.sim.processor]; -- because we just forked proc[]; process _ CurrentProcess[]; -- process assigned to this processor may have changed SimRestartSuspension[process.sim.lock, process]; SimSetThisProcessor[NIL]; -- this C7 process is about to go away ... }; SimRestartSuspension: ENTRY PROC [lock: SimLock, process: Process] ~ { ENABLE UNWIND => NULL; process.sim.processor _ SimThisProcessor[]; -- Should this happen here or in SetCurrentProcess? process.sim.awakened _ TRUE; NOTIFY process.sim.awakenEvent; }; NYIAction: TYPE ~ { noOp, error }; NYI: SIGNAL ~ CODE; NotYetImplemented: PROC [action: NYIAction _ error] ~ { SELECT action FROM noOp => NULL; error => NYI[]; ENDCASE => ERROR; }; CurrentProcess: PROC RETURNS [Process] ~ { RETURN [SimThisProcessor[].sim.process]; }; SetCurrentProcess: PROC [p: Process] ~ { processor: Processor ~ SimThisProcessor[]; processor.sim.process _ p; p.sim.processor _ processor; -- SIM only. }; CurrentProcessor: PROC RETURNS [current: Processor] ~ { current _ SimThisProcessor[]; IF current.sim.processor # current THEN ERROR; -- SIM sanity check }; SetCurrentProcessor: PROC [p: Processor] ~ { current: Processor _ SimThisProcessor[]; IF p # current THEN ERROR; current.sim.processor _ p; -- SIM only. }; runawayLimit: Word _ runawayLimit; emergencyLimit: Word _ emergencyLimit; metaLock: Processor _ NIL; schedulerLock: Processor _ NIL; readyQueueArray: ARRAY Priority OF MetaQueueRep _ ALL[emptyMetaQueueRep]; pageFaultMetaQueue: MetaQueueRep _ emptyMetaQueueRep; pageFaultCond: Condition; pageFaultCondRep: ConditionRep; timeoutMetaQueue: MetaQueueRep _ emptyMetaQueueRep; tailProcessor: Processor _ NIL; tailFreeProcess: Process _ NIL; panicStopLock: Process _ NIL; spinTries: NAT _ 10; lowestRunningPriority: Priority _ Priority.FIRST; highestReadyPriority: Priority _ Priority.FIRST; deferredWakeups: BOOL _ FALSE; Fork: PUBLIC PROC [proc: PROC ANY RETURNS ANY, argPtr: WordSeq, nArgs: INT, nRets: INT] RETURNS [new: SecureProcess] = { { -- The following SIM code works if there are no args or results ... p: Process; simProc: PROC _ LOOPHOLE [proc]; DisableInterrupts[]; AcquireMetaLock[]; p _ NewProcessInner[]; new _ SecureProcessFromProcess[p]; p.priority _ CurrentProcess[].priority; C7Process.Detach[ FORK SimForkee[p, simProc] ]; EnqueueReady[p]; ReleaseMetaLock[]; EnableInterrupts[]; -- SIM only. Automatic in RDI. SimCheckForRescheduleTrap[]; -- SIM only. }; }; SimForkee: PROC [process: Process, proc: PROC] ~ { SimBackground[]; -- SIM only, because we just forked SimCallAndSuspend[process.sim.lock, process, NIL, $SimForkee]; -- just suspend until we're switched to proc[]; MonitorEntry[@process.lock]; DO SELECT process.joinState FROM none, exiting => { process.joinState _ exiting; Wait[@process.joinCondition, @process.lock] }; detached, joined => { EXIT }; joining => { process.joinState _ exiting; Notify[@process.joinCondition]; Wait[@process.joinCondition, @process.lock] }; ENDCASE => ERROR; ENDLOOP; process.joinState _ none; -- not really necessary (will be done by CleanProcess) MonitorExit[@process.lock]; RDIDirectedYield[free, NIL, 0]; -- RDI: replace by DirectedYield. { self: Process _ CurrentProcess[]; SimRestartSuspension[self.sim.lock, self]; }; }; Forkee: PROC [proc: PROC ANY RETURNS ANY, argPtr: WordSeq, nArgs: INT, nRets: INT] RETURNS [--doesn't--] ~ { NotYetImplemented[]; }; Join: PUBLIC PROC [secureProcess: SecureProcess, retPtr: WordSeq] = { { -- SIM only, no args or results process: Process ~ ProcessFromSecureProcess[secureProcess]; MonitorEntry[@process.lock]; DO SELECT process.joinState FROM none, joining => { process.joinState _ joining; Wait[@process.joinCondition, @process.lock] }; exiting => { process.joinState _ joined; Notify[@process.joinCondition]; EXIT }; detached, joined => { ERROR InvalidProcess[secureProcess]; }; ENDCASE => ERROR; ENDLOOP; MonitorExit[@process.lock]; }; }; Detach: PUBLIC SAFE PROC [secureProcess: SecureProcess] ~ TRUSTED { process: Process ~ ProcessFromSecureProcess[secureProcess]; MonitorEntry[@process.lock]; SELECT process.joinState FROM none => { process.joinState _ detached }; exiting => { process.joinState _ detached; Notify[@process.joinCondition] }; joining, detached, joined => { ERROR InvalidProcess[secureProcess] }; ENDCASE => ERROR; MonitorExit[@process.lock]; }; DirectedYield: PUBLIC PROC [nextState: ProcessState, nextProcess: Process, when: Ticks] = TRUSTED { DoDirectedYield: PROC ~ { RDIDirectedYield[nextState, nextProcess, when] }; SimCallAndSuspend[CurrentProcess[].sim.lock, CurrentProcess[], DoDirectedYield, $DirectedYield]; SimCheckForRescheduleTrap[]; }; RDIDirectedYield: PUBLIC PROC [nextState: ProcessState, nextProcess: Process, when: Ticks] = TRUSTED { DisableInterrupts[]; CurrentProcess[].when _ when; MarkFrame[]; ProcessSwitch[nextState, nextProcess]; EnableInterrupts[]; -- SIM only. RDI: happens automatically. }; Wait: PUBLIC PROC [cond: Condition, lock: MonitorLock] = { Enqueue[@cond.queue]; IF lock # NIL THEN MonitorExit[lock]; IF (CurrentProcess[].abortState # requested) OR (NOT cond.flags.abortEnable) THEN { DirectedYield[waitingCV, NIL, cond.timeout]; }; DequeueSelf[@cond.queue]; IF lock # NIL THEN MonitorEntry[lock]; IF CurrentProcess[].abortState = requested AND cond.flags.abortEnable THEN TestAbort[]; }; WaitInterrupt: PUBLIC PROC [cond: Condition] = { IF NOT cond.flags.condRequest THEN { Enqueue[@cond.queue]; IF NOT cond.flags.condRequest THEN { DirectedYield[waitingICV, NIL, cond.timeout]; }; DequeueSelf[@cond.queue]; }; cond.flags _ defaultCondFlags; }; Notify: PUBLIC PROC [cond: Condition] = { best: Process = Dequeue[@cond.queue]; IF best # NIL THEN MakeReady[best]; }; Broadcast: PUBLIC PROC [cond: Condition] = { tail: Process _ cond.queue.chain; IF tail # NIL THEN { AcquireQueue[@cond.queue]; IF (tail _ cond.queue.chain) # NIL THEN { cond.queue.chain _ NIL; DO this: Process ~ tail.next; next: Process ~ this.next; tail.next _ next; this.queue _ NIL; this.next _ NIL; MakeReady[this]; IF this = tail THEN EXIT; -- we just removed the last one ENDLOOP; }; ReleaseQueue[@cond.queue]; }; }; MonitorEntry: PUBLIC PROC [lock: MonitorLock] = { self: Process = CurrentProcess[]; DO IF CStoreProcess[ptr: @lock.owner] THEN RETURN; Enqueue[@lock.queue]; { owner: Process = lock.owner; IF owner # NIL THEN { THROUGH [0..spinTries) WHILE owner.state = running DO SimYield[]; -- SIM only ENDLOOP; IF lock.owner # NIL THEN DirectedYield[waitingML, lock.owner, 0]; }; DequeueSelf[@lock.queue]; }; ENDLOOP; }; MonitorExit: PUBLIC PROC [lock: MonitorLock] = { IF lock.owner = CurrentProcess[] THEN { lock.owner _ NIL; IF lock.queue.chain # NIL THEN { next: Process = Dequeue[@lock.queue]; IF next # NIL THEN MakeReady[next]; }; IF deferredWakeups THEN { RaiseReschedule[]; }; }; }; TestAbort: PUBLIC PROC = { self: Process = CurrentProcess[]; IF self.abortState = requested THEN { self.abortState _ none; ERROR ABORTED }; }; RequestAbort: PUBLIC PROC [process: Process] = { SELECT process.abortState FROM none => { process.abortState _ requested; MakeReady[process]; RaiseReschedule[]; }; inhibited => process.abortState _ delayed; ENDCASE; }; SetPriority: PUBLIC SAFE PROC [p: Priority] ~ TRUSTED { self: Process ~ CurrentProcess[]; oldPriority: Priority; doYield: BOOL; DisableInterrupts[]; AcquireMetaLock[]; oldPriority _ self.priority; self.priority _ p; SELECT TRUE FROM p <= lowestRunningPriority => { lowestRunningPriority _ p }; oldPriority = lowestRunningPriority => { lowest: Priority _ tailProcessor.running.priority; FOR proc: Processor _ tailProcessor.next, proc.next WHILE proc # tailProcessor DO lowest _ MIN[lowest, proc.running.priority]; ENDLOOP; lowestRunningPriority _ lowest }; ENDCASE => NULL; doYield _ (p < highestReadyPriority); ReleaseMetaLock[]; IF doYield THEN { EnableInterrupts[]; -- SIM only? DirectedYield[ready, NIL, 0] } ELSE { EnableInterrupts[]; -- SIM only. Automatic in RDI. }; }; intHandlers: ARRAY RequestKind OF IntHandler _ ALL [StrayIntHandler]; StrayIntHandler: IntHandler ~ TRUSTED { ERROR }; RegisterIntHandler: PUBLIC SAFE PROC [requestKind: RequestKind, intHandler: IntHandler] RETURNS [old: IntHandler] ~ TRUSTED { IF intHandler = NIL THEN intHandler _ StrayIntHandler; DisableInterrupts[]; AcquireMetaLock[]; old _ intHandlers[requestKind]; intHandlers[requestKind] _ intHandler; ReleaseMetaLock[]; EnableInterrupts[]; -- SIM only. Automatic in RDI. SimCheckForRescheduleTrap[]; -- SIM only. }; SimCheckForRescheduleTrap: PROC ~ { IF NOT CurrentProcessor[].sim.interruptsEnabled THEN RETURN; WHILE CurrentProcessor[].sim.rescheduleRequested DO CurrentProcessor[].sim.rescheduleRequested _ FALSE; DisableInterrupts[]; -- so RescheduleTrap will be called with interrupts disabled SimCallAndSuspend[CurrentProcess[].sim.lock, CurrentProcess[], RescheduleTrap, $SimCheckForRescheduleTrap]; IF NOT CurrentProcessor[].sim.interruptsEnabled THEN ERROR; -- ???? ENDLOOP; }; RescheduleTrap: PROC = { entryPriority: Priority _ CurrentProcess[].priority; DO IF entryPriority.ORD <= lowestRunningPriority.ORD AND schedulerLock = NIL THEN IF CStoreProcessor[ptr: @schedulerLock] THEN { currentReq: RequestWord _ ReadAndClearDeviceRequests[]; IF currentReq # nullRequestWord THEN { MarkFrame[]; SaveProcessState[CurrentProcess[]]; }; AcquireMetaLock[]; IF currentReq # nullRequestWord THEN { FOR reqx: RequestKind IN RequestKind DO IF currentReq[reqx] THEN { (intHandlers[reqx])[reqx]; currentReq[reqx] _ FALSE; IF currentReq = nullRequestWord THEN EXIT; }; ENDLOOP; }; IF highestReadyPriority.ORD > lowestRunningPriority.ORD THEN { AssignProcessors[]; }; SimStoreNilInProcessor[ptr~@schedulerLock]; -- RDI: do the store in line ReleaseMetaLock[]; }; DO SELECT CurrentProcessor[].orders FROM noChange => EXIT; stopped => NULL; switchToGiven => { nextProcess: Process _ CurrentProcessor[].switchTo; CurrentProcessor[].orders _ noChange; MarkFrame[]; ProcessSwitch[ready, nextProcess]; << IF (nextProcess # NIL AND nextProcess.state = ready) OR CurrentProcess[].priority <= highestReadyPriority THEN { MarkFrame[]; ProcessSwitch[ready, nextProcess]; }; >> }; panicStop => { MarkFrame[]; SaveProcessState[CurrentProcess[]]; CurrentProcessor[].orders _ stopped; }; restart => { RestoreProcess[CurrentProcess[]]; CurrentProcessor[].orders _ noChange; }; ENDCASE => ERROR; ENDLOOP; IF schedulerLock # NIL THEN EXIT; IF NOT DeviceRequestsPending[] THEN EXIT; entryPriority _ Priority.FIRST; -- ???? was IF entryPriority.ORD > lowestRunningPriority.ORD THEN entryPriority _ entryPriority.PRED; ???? ENDLOOP; EnableInterrupts[]; -- SIM only. Automatic in RDI. }; ShuffleReadyQueues: PUBLIC PROC = { DisableInterrupts[]; AcquireMetaLock[]; FOR processor: Processor _ tailProcessor.next, processor.next DO SELECT processor.orders FROM noChange => { processor.switchTo _ NIL; processor.orders _ switchToGiven; }; ENDCASE; IF processor = tailProcessor THEN EXIT; ENDLOOP; RaiseReschedule[]; ReleaseMetaLock[]; EnableInterrupts[]; -- SIM only. Automatic in RDI. SimCheckForRescheduleTrap[]; -- SIM only. }; CausePanicStop: PUBLIC PROC = { self: Process = CurrentProcess[]; DO DisableInterrupts[]; IF CStoreProcess[ptr~@panicStopLock] THEN EXIT; EnableInterrupts[]; SimCheckForRescheduleTrap[]; -- SIM only. WHILE panicStopLock # NIL DO SimYield[]; -- SIM only. SimCheckForRescheduleTrap[]; -- SIM only. ENDLOOP; ENDLOOP; MarkFrame[]; SaveProcessState[self]; DO current: Processor _ CurrentProcessor[]; done: BOOL _ TRUE; AcquireMetaLock[]; FOR processor: Processor _ current.next, processor.next WHILE processor # current DO SELECT processor.orders FROM noChange => { processor.switchTo _ NIL; processor.orders _ panicStop; done _ FALSE; }; stopped => {}; ENDCASE => done _ FALSE; ENDLOOP; IF done THEN EXIT; ReleaseMetaLock[]; RaiseReschedule[]; ENDLOOP; }; ReleasePanicStop: PUBLIC PROC = { self: Processor ~ CurrentProcessor[]; FOR processor: Processor _ self.next, processor.next WHILE processor # self DO SELECT processor.orders FROM stopped => processor.orders _ restart; ENDCASE => ERROR; ENDLOOP; SimStoreNilInProcess[ptr~@panicStopLock]; -- RDI: panicStopLock _ NIL; ReleaseMetaLock[]; }; SatisfyPageFault: PUBLIC PROC [startPage, endPage: INT] = { DisableInterrupts[]; AcquireMetaLock[]; { tail: Process _ pageFaultMetaQueue; p: Process _ tail; WHILE p # NIL DO next: Process _ p.meta; SELECT p.state FROM waitingPage => IF WordToInt[p.page] IN [startPage..endPage] THEN { DequeueMeta[@pageFaultMetaQueue, p]; EnqueueReady[p]; IF p.priority > lowestRunningPriority THEN deferredWakeups _ TRUE; }; ENDCASE; p _ next; IF p = tail THEN EXIT; ENDLOOP; }; ReleaseMetaLock[]; EnableInterrupts[]; SimCheckForRescheduleTrap[]; -- SIM only. IF deferredWakeups THEN RaiseReschedule[]; }; ProcessSwitch: PROC [nextState: ProcessState, nextProcess: Process] = { self: Process ~ CurrentProcess[]; selfPriority: Priority ~ self.priority; SaveProcessState[self]; AcquireMetaLock[]; SELECT nextState FROM waitingML => { IF self.next = NIL THEN GO TO bailOut; self.state _ nextState; }; waitingCV, waitingICV => { IF self.next = NIL THEN GO TO bailOut; IF self.when # noTimeout THEN EnqueueMeta[@timeoutMetaQueue, self]; self.state _ nextState; }; waitingPage => { EnqueuePageFault[self]; -- self.state _ waitingPage; DelicateNotify[pageFaultCond]; }; ready => { IF (nextProcess # NIL) AND (nextProcess.state = waitingPage) THEN { self.page _ nextProcess.page; EnqueuePageFault[self]; -- self.state _ waitingPage; } ELSE { EnqueueReady[self]; -- self.state _ ready; }; }; free => { CleanProcess[self]; -- self.state _ free; }; ENDCASE => ERROR; IF nextProcess = NIL OR nextProcess.state # ready THEN { nextProcess _ NIL; -- Part of sanity check, below ???? - ajd FOR priority: Priority DECREASING IN [Priority.FIRST .. highestReadyPriority] DO tail: Process = readyQueueArray[priority]; IF tail # NIL THEN { nextProcess _ tail.meta; EXIT }; ENDLOOP; IF nextProcess = NIL THEN ERROR; -- Sanity check ???? - ajd }; DequeueMeta[@readyQueueArray[nextProcess.priority], nextProcess]; DO pri: Priority _ highestReadyPriority; IF pri = Priority.FIRST OR readyQueueArray[pri] # NIL THEN EXIT; highestReadyPriority _ pri.PRED; ENDLOOP; nextProcess.state _ running; SetCurrentProcess[nextProcess]; -- RDI: this loads an aux register. Is this the place for it? CurrentProcessor[].running _ nextProcess; IF selfPriority = lowestRunningPriority THEN { new: Priority _ tailProcessor.running.priority; FOR each: Processor _ tailProcessor.next, each.next WHILE each # tailProcessor DO IF new > each.running.priority THEN new _ each.running.priority; ENDLOOP; lowestRunningPriority _ new; }; ReleaseMetaLock[]; IF nextProcess # self THEN RestoreProcess[nextProcess]; EXITS bailOut => ReleaseMetaLock[]; }; MakeReady: PROC [process: Process] ~ { DisableInterrupts[]; AcquireMetaLock[]; SELECT process.state FROM waitingCV, waitingML, waitingICV => { priority: Priority ~ process.priority; DequeueMeta[@timeoutMetaQueue, process]; EnqueueReady[process]; IF priority > lowestRunningPriority THEN deferredWakeups _ TRUE; }; ENDCASE; ReleaseMetaLock[]; EnableInterrupts[]; -- SIM only. Automatic in RDI. }; Enqueue: PROC [q: Queue, p: Process _ CurrentProcess[]] = { AcquireQueue[q]; { tail: Process = q.chain; IF tail = NIL THEN p.next _ p ELSE {p.next _ tail.next; tail.next _ p}; q.chain _ p; p.queue _ q; }; ReleaseQueue[q]; }; Dequeue: PROC [q: Queue] RETURNS [best: Process _ NIL] = { lag: Process _ q.chain; IF q.chain # NIL THEN { AcquireQueue[q]; best _ DequeueInner[q]; ReleaseQueue[q]; }; }; DequeueInner: PROC [q: Queue] RETURNS [best: Process _ NIL] = --INLINE-- { lag: Process _ q.chain; IF lag # NIL THEN { tail: Process = lag; best _ lag.next; IF lag = best THEN q.chain _ NIL ELSE { head: Process _ best; -- loop invariant: lag.next = best this: Process _ head; DO next: Process _ this.next; IF next = head THEN EXIT; -- we have wrapped IF next.priority > best.priority THEN {lag _ this; best _ next}; this _ next; ENDLOOP; IF tail = best THEN q.chain _ lag; lag.next _ best.next; }; best.queue _ NIL; best.next _ NIL; -- the last change, due to test in ProcessSwitch }; }; DequeueSelf: PROC [q: Queue] = { IF CurrentProcess[].next # NIL THEN { lag: Process _ q.chain; IF lag # NIL THEN { AcquireQueue[q]; IF (lag _ q.chain) # NIL THEN { tail: Process = lag; DO p: Process = lag.next; IF p = CurrentProcess[] THEN { IF p = lag THEN q.chain _ NIL ELSE { IF p = tail THEN q.chain _ lag; lag.next _ p.next; }; CurrentProcess[].queue _ NIL; p.next _ NIL; -- the last change, due to test in ProcessSwitch EXIT; }; lag _ p; IF lag = tail THEN EXIT; ENDLOOP; }; ReleaseQueue[q]; }; }; }; AcquireQueue: PROC [q: Queue] = { WHILE NOT CStoreProcess[ptr: @q.busy] DO owner: Process _ q.busy; IF owner = NIL THEN LOOP; IF owner.state # running THEN DirectedYield[ready, owner, 0]; SimYield[]; -- SIM only! ENDLOOP; }; ReleaseQueue: PROC [q: Queue] = --INLINE-- { SimStoreNilInProcess[ptr~@q.busy]; -- SIM only. }; AcquireMetaLock: PROC = --INLINE-- { WHILE NOT CStoreProcessor[ptr: @metaLock] DO WHILE metaLock # NIL DO SimYield[]; -- SIM only ENDLOOP; ENDLOOP; }; ReleaseMetaLock: PROC = --INLINE-- { SimStoreNilInProcessor[ptr~@metaLock]; -- SIM only }; SaveProcessState: PROC [process: Process] = --INLINE-- { NULL }; RestoreProcess: PROC [process: Process] = --INLINE-- { }; DelicateNotify: PROC [cond: Condition] = --INLINE-- { cond.flags.condRequest _ TRUE; IF CStoreProcess[ptr: @cond.queue.busy] THEN { best: Process _ DequeueInner[@cond.queue]; IF best # NIL THEN { SELECT best.state FROM waitingICV => { DequeueMeta[@timeoutMetaQueue, best]; EnqueueReady[best]; IF best.priority > lowestRunningPriority THEN deferredWakeups _ TRUE; }; running, ready => NULL; ENDCASE => ERROR; -- ???? I'm not sure of this at all ???? - ajd }; ReleaseQueue[@cond.queue]; }; }; AssignProcessors: PROC ~ { self: Processor ~ CurrentProcessor[]; needReschedule: BOOL _ FALSE; FOR pProcess: Priority DECREASING IN (lowestRunningPriority..highestReadyPriority] DO tailProcess: Process ~ readyQueueArray[pProcess]; IF tailProcess = NIL THEN LOOP; FOR process: Process _ tailProcess.meta, process.meta DO BEGIN processor: Processor _ self; best: Processor _ NIL; priToBeat: Priority _ pProcess; DO SELECT processor.orders FROM noChange => { thisPri: Priority ~ processor.running.priority; IF thisPri < priToBeat THEN { best _ processor; priToBeat _ thisPri }; }; switchToGiven => { IF processor.switchTo = process THEN GOTO AlreadyAssigned; -- hint only }; ENDCASE => NULL; IF (processor _ processor.next) = self THEN EXIT; ENDLOOP; IF best = NIL THEN GOTO NoMoreProcessors; best.switchTo _ process; best.orders _ switchToGiven; IF best # self THEN needReschedule _ TRUE; EXITS AlreadyAssigned => NULL; END; IF process = tailProcess THEN EXIT; ENDLOOP; REPEAT NoMoreProcessors => NULL; ENDLOOP; IF needReschedule THEN RaiseReschedule[]; }; << AssignProcessors: PROC = { needReschedule: BOOL _ FALSE; current: Processor = CurrentProcessor[]; firstAvail: Processor _ current; deferredWakeups _ FALSE; FOR priority: Priority DECREASING IN (lowestRunningPriority..highestReadyPriority] DO tail: Process = readyQueueArray[priority]; IF tail # NIL THEN { FOR process: Process _ tail.meta, process.meta DO best: Processor _ NIL; -- ???? Why "_ NIL"? Isn't this dead? ???? - ajd bestPriority: Priority _ process.priority; { DO best _ firstAvail; IF best.orders = noChange THEN { np: Priority = best.running.priority; IF np < bestPriority THEN {bestPriority _ np; EXIT}; }; firstAvail _ best.next; IF firstAvail = current THEN GO TO done; IF best.switchTo = process AND best.orders = switchToGiven THEN GO TO alreadyAssigned; ENDLOOP; IF bestPriority # lowestRunningPriority THEN FOR p: Processor _ best.next, p.next WHILE p # current DO SELECT p.orders FROM switchToGiven => IF p.switchTo = process THEN GO TO alreadyAssigned; noChange => { np: Priority = p.running.priority; IF np < bestPriority THEN { best _ p; bestPriority _ np; IF np = lowestRunningPriority THEN EXIT; }; }; ENDCASE; ENDLOOP; best.switchTo _ process; best.orders _ switchToGiven; IF best # current THEN needReschedule _ TRUE; IF best = firstAvail THEN { firstAvail _ best.next; IF firstAvail = current THEN GO TO done; }; EXITS alreadyAssigned => { }; }; IF process = tail THEN EXIT; ENDLOOP; EXITS done => EXIT; }; ENDLOOP; IF needReschedule THEN RaiseReschedule[]; }; >> EnqueueReady: PROC [process: Process] = --INLINE-- { priority: Priority = process.priority; EnqueueMeta[@readyQueueArray[priority], process]; IF priority > highestReadyPriority THEN highestReadyPriority _ priority; process.state _ ready; }; EnqueuePageFault: PROC [process: Process] = --INLINE-- { EnqueueMeta[@pageFaultMetaQueue, process]; process.state _ waitingPage; }; EnqueueMeta: PROC [metaQueue: MetaQueue, process: Process] = --INLINE-- { IF process.meta = NIL THEN { tail: Process = metaQueue^; IF tail = NIL THEN process.meta _ process ELSE { process.meta _ tail.meta; tail.meta _ process }; metaQueue^ _ process; }; }; DequeueMeta: PROC [metaQueue: MetaQueue, process: Process] = --INLINE-- { IF process.meta # NIL THEN { tail: Process = metaQueue^; IF tail # NIL THEN { lag: Process _ tail; DO p: Process = lag.meta; IF p = process THEN { IF lag = p THEN metaQueue^ _ NIL ELSE { IF p = tail THEN metaQueue^ _ lag; lag.meta _ p.meta; }; p.meta _ NIL; EXIT; }; lag _ p; IF lag = tail THEN EXIT; ENDLOOP; }; }; }; simCStoreLock: SimLock _ NEW [SimLockRep _ []]; -- SIM only CStoreProcess: PROC [ptr: ProcessPtr, old: Process _ NIL, new: Process _ CurrentProcess[]] RETURNS [stored: BOOL] = -- MACHINE CODE -- { DoIt: ENTRY PROC [lock: SimLock] ~ { ENABLE UNWIND => NULL; IF (stored _ (ptr^ = old)) THEN ptr^ _ new }; DoIt[simCStoreLock]; }; SimStoreNilInProcess: ENTRY PROC [lock: SimLock _ simCStoreLock, ptr: ProcessPtr] ~ { ptr^ _ NIL; }; CStoreProcessor: PROC [ptr: ProcessorPtr, old: Processor _ NIL, new: Processor _ CurrentProcessor[]] RETURNS [stored: BOOL] = -- MACHINE CODE -- { DoIt: ENTRY PROC [lock: SimLock] ~ { ENABLE UNWIND => NULL; IF (stored _ (ptr^ = old)) THEN ptr^ _ new }; DoIt[simCStoreLock]; }; SimStoreNilInProcessor: ENTRY PROC [lock: SimLock _ simCStoreLock, ptr: ProcessorPtr] ~ { ptr^ _ NIL; }; CStoreCard: PROC [ptr: LONG POINTER TO CARD, old: CARD _ 0, new: CARD] RETURNS [stored: BOOL] = -- MACHINE CODE -- { DoIt: ENTRY PROC [lock: SimLock] ~ { ENABLE UNWIND => NULL; IF (stored _ (ptr^ = old)) THEN ptr^ _ new }; DoIt[simCStoreLock]; }; SimStoreInCard: ENTRY PROC [lock: SimLock _ simCStoreLock, ptr: LONG POINTER TO CARD, new: CARD] ~ { ptr^ _ new; }; simIOLock: SimLock _ NEW [SimLockRep _ []]; -- SIM only simIORequestWord: RequestWord _ nullRequestWord; -- SIM only DisableInterrupts: PROC [] = { SimThisProcessor[].sim.interruptsEnabled _ FALSE; -- Change in RDI }; EnableInterrupts: PROC [] = { SimThisProcessor[].sim.interruptsEnabled _ TRUE; -- Change in RDI }; ReadAndClearDeviceRequests: ENTRY PROC [lock: SimLock _ simIOLock] RETURNS [rw: RequestWord] ~ { ENABLE UNWIND => NULL; rw _ simIORequestWord; FOR k: RequestKind IN RequestKind DO IF rw[k] THEN simIORequestWord[k] _ FALSE; ENDLOOP; }; DeviceRequestsPending: ENTRY PROC [lock: SimLock _ simIOLock] RETURNS [BOOL] = -- MACHINE CODE -- { ENABLE UNWIND => NULL; FOR k: RequestKind IN RequestKind DO IF simIORequestWord[k] THEN RETURN [TRUE]; ENDLOOP; RETURN [FALSE]; }; RaiseReschedule: PROC = -- MACHINE CODE -- { deferredWakeups _ FALSE; -- ???? I'm not completely sure about this ???? - ajd SimRaiseReschedule[]; -- Wrong for RDI. }; SimRaiseReschedule: PROC ~ { FOR i: CARDINAL IN [0..maxProcessors) DO processors[i].sim.rescheduleRequested _ TRUE; ENDLOOP; }; WordToInt: PROC [x: Word] RETURNS [INT] = MACHINE CODE { PrincOps.zEXCH }; EUFetchSpecial: PROC [which: EUstateIndex] RETURNS [w: Word _ wordZero] = -- MACHINE CODE -- { NotYetImplemented[noOp]; }; EUStoreSpecial: PROC [which: EUstateIndex, x: Word] = -- MACHINE CODE -- { NotYetImplemented[noOp]; }; SaveStack: PROC = --INLINE-- { NotYetImplemented[noOp]; }; MarkFrame: PROC = --INLINE-- -- MACHINE CODE -- { NotYetImplemented[noOp]; }; Init: PROC [indexPtr: LONG POINTER TO CARD] ~ { processor: Processor; process: Process; index: CARD ~ indexPtr^; IF index = 0 THEN { CreateNachos[]; CreateProcesses[]; CreateProcessors[]; pageFaultCond _ @pageFaultCondRep; InitializeCondition[pageFaultCond, noTimeout]; }; SimStoreInCard[ptr~indexPtr, new~index+1]; -- RDI: indexPtr^ _ index+1; processor _ ProcessorFromIndex[index]; SetCurrentProcessor[processor]; AcquireMetaLock[]; process _ NewProcessInner[]; process.state _ running; process.priority _ lowestRunningPriority _ Priority.FIRST; SetCurrentProcess[process]; processor.running _ process; InsertProcessor[processor]; IF panicStopLock # NIL THEN { MarkFrame[]; SaveProcessState[process]; CurrentProcessor[].orders _ stopped; RaiseReschedule[]; -- ensure that this processor will follow its own orders immediately. }; ReleaseMetaLock[]; EnableInterrupts[]; SimCheckForRescheduleTrap[]; -- SIM only. IF index = 0 THEN { SetPriority[normal]; SystemStartup[] }; SetPriority[Priority.FIRST]; DO SimCheckForRescheduleTrap[]; -- SIM only. SimYield[]; -- SIM only. ENDLOOP; }; SystemStartup: PROC ~ { sP: SecureProcess; SetPriority[excited]; sP _ Fork[TimeSliceServer, NIL, 0, 0]; SetPriority[normal]; Detach[sP]; sP _ Fork[CountA, NIL, 0, 0]; Detach[sP]; sP _ Fork[CountB, NIL, 0, 0]; Detach[sP]; }; tickConditionRep: ConditionRep; ticksPerSlice: CARD _ 2; TimeSliceServer: PROC ~ { tickCondition: Condition ~ @tickConditionRep; InitializeCondition[tickCondition, 0]; [] _ RegisterIntHandler[0, HandleTick]; DO THROUGH [0 .. ticksPerSlice) DO WaitInterrupt[tickCondition]; ENDLOOP; ShuffleReadyQueues[]; ENDLOOP; }; HandleTick: IntHandler ~ TRUSTED { IF requestKind # 0 THEN ERROR; -- SIM: Sanity check ???? DelicateNotify[@tickConditionRep]; }; Tick: PROC ~ { EntryTick[] }; EntryTick: ENTRY PROC [lock: SimLock _ simIOLock] ~ { simIORequestWord[0] _ TRUE; SimRaiseReschedule[] }; counterA: CARD _ 0; counterB: CARD _ 0; CountOrders: TYPE ~ { init, go, quit }; countOrders: CountOrders _ init; CountA: PROC ~ { target: CARD _ 1; WHILE countOrders = init DO SimYield[]; SimCheckForRescheduleTrap[]; ENDLOOP; WHILE countOrders = go DO WHILE counterB < target DO SimYield[]; SimCheckForRescheduleTrap[]; ENDLOOP; target _ target.SUCC; counterA _ counterA.SUCC; ENDLOOP; }; CountB: PROC ~ { target: CARD _ 1; WHILE countOrders = init DO SimYield[]; SimCheckForRescheduleTrap[]; ENDLOOP; WHILE countOrders = go DO WHILE counterA < target DO SimYield[]; SimCheckForRescheduleTrap[]; ENDLOOP; target _ target.SUCC; counterB _ counterB.SUCC; ENDLOOP; }; CreateNachos: PROC ~ { NotYetImplemented[noOp] }; maxProcesses: CARDINAL = 40; processes: ARRAY [0..maxProcesses) OF ProcessRep; InvalidProcess: PUBLIC ERROR [secureProcess: SecureProcess] ~ CODE; ValidateProcess: PUBLIC SAFE PROC [sP: SecureProcess] ~ TRUSTED { i: CARD ~ sP.index; IF (i >= maxProcesses) OR (processes[i].secure.key # sP.key) THEN ERROR InvalidProcess[sP]; }; ProcessFromSecureProcess: PROC [sP: SecureProcess] RETURNS [p: Process] ~ --INLINE-- { i: CARD ~ sP.index; IF (i >= maxProcesses) OR ( (p _ @processes[i]).secure.key # sP.key) THEN ERROR InvalidProcess[sP]; }; SecureProcessFromProcess: PROC [p: Process] RETURNS [SecureProcess] ~ --INLINE-- { RETURN [p.secure] }; CreateProcesses: PROC [] ~ { FOR i: CARDINAL IN [0..maxProcesses) DO p: Process ~ @processes[i]; p.sim _ NEW [ SimProcessRep _ [lock~NEW[SimLockRep _ []], awakened~FALSE, processor~NIL] ]; -- SIM only. p.secure _ [key~0, index~i]; CleanProcess[p, FALSE]; ENDLOOP; }; CleanProcess: PROC [p: Process, check: BOOL _ TRUE] RETURNS [] ~ { p.secure.key _ p.secure.key + 1; p.queue _ NIL; p.next _ NIL; p.when _ noTimeout; p.page _ wordZero; p.priority _ Priority.FIRST; p.state _ free; InitializeMonitorLock[@p.lock]; p.abortState _ none; p.joinState _ none; InitializeCondition[@p.joinCondition, noTimeout]; { -- SIM only p.sim.awakened _ FALSE; p.sim.processor _ NIL; }; IF tailFreeProcess = NIL THEN p.meta _ tailFreeProcess _ p ELSE { p.meta _ tailFreeProcess.meta; tailFreeProcess.meta _ p }; }; NewProcessInner: PROC RETURNS [p: Process] ~ --INLINE-- { IF tailFreeProcess = NIL THEN ERROR; -- too horrible to contemplate p _ tailFreeProcess.meta; IF tailFreeProcess = p THEN tailFreeProcess _ NIL ELSE tailFreeProcess.meta _ p.meta; p.meta _ NIL; -- for sanity when debugging }; NewProcess: PROC RETURNS [p: Process] ~ { DisableInterrupts[]; AcquireMetaLock[]; p _ NewProcessInner[]; ReleaseMetaLock[]; EnableInterrupts[]; -- SIM only. Automatic in RDI. SimCheckForRescheduleTrap[]; -- SIM only. }; maxProcessors: CARDINAL ~ 5; numProcessors: [0..maxProcessors) _ 0; processors: ARRAY [0..maxProcessors) OF ProcessorRep; ProcessorFromIndex: PROC [i: CARDINAL] RETURNS [Processor] ~ --INLINE-- { RETURN [@processors[i]] }; CreateProcessors: PROC [] ~ { FOR i: CARDINAL IN [0 .. maxProcessors) DO p: Processor ~ ProcessorFromIndex[i]; p.sim _ NEW [SimProcessorRep _ [lock~NEW[SimLockRep _ []], interruptsEnabled~FALSE, rescheduleRequested~FALSE, process~NIL, processor~NIL]]; -- SIM only. p.next _ NIL; p.orders _ noChange; p.switchTo _ NIL; p.running _ NIL; ENDLOOP; }; InsertProcessor: PROC [p: Processor] ~ --INLINE-- { numProcessors _ numProcessors.SUCC; IF tailProcessor = NIL THEN p.next _ tailProcessor _ p ELSE { p.next _ tailProcessor.next; tailProcessor.next _ p }; }; numIn: CARD _ 0; -- number of processors that have entered critical section. numOut: CARD _ 0; -- number of processors that have left critical section. SimRunInit: PROC ~ { index: CARD; SimBackground[]; -- SIM only. DO index _ numOut; IF CStoreCard[ptr~@numIn, old~index, new~index+1] THEN EXIT; SimYield[]; -- SIM only. ENDLOOP; SimSetThisProcessor[ProcessorFromIndex[index]]; -- SIM only. Init[@numOut]; }; SimInit: PROC [nProc: NAT] ~ { IF nProc > maxProcessors THEN ERROR; THROUGH [0..nProc) DO C7Process.Detach[ FORK SimRunInit[] ]; ENDLOOP; }; END. Differences Between PrincOps and DragOps Note: this section requires knowledge of the PrincOps architecture. I freely admit that my knowledge of said architecture is spotty at best. This section is also incomplete. Multiple processors With current PrincOps machines atomicity is acheived through a combination of locks, inhibition of interrupts, priority levels, and non-interruptibility of non-faulting microcode routines. In the DragOps arhcitecture, only locks (based on memory bus arbitration) and inhibition of interrupts for a single processor (based on IFU inhibition of the Reschedule interrupt) can be used as sources of atomicity. This complicates life, you betcha. Memory vs. time For PrincOps, memory was assumed to be expensive, and cycles were assumed to be expendable if it saved memory. For example, a process block costs only 8 bytes when no state vector is used, and only costs 36 additional bytes when a state vector is used (the unusual case). The DragOps, memory is assumed to be relatively cheap, and cycles should only be spent to avoid gross memory costs. For example, a process block costs at least 40 bytes in the normal case, and there is no exceptional case. The ready queue For PrincOps, the head of the ready queue is the currently running process. For DragOps, running processes are not on the ready queue at all. Instead, running processes are located through the current ring of processors. The DragOps ready queue is special in that it is actually an array of metaqueues, one for each priority level. This bounds the search for the best ready process to a time proportional to the number of priority levels (small), yet also allows us to place processes on the ready queue in unit time. Queues and meta queues For PrincOps, all queues are circular queues of processes linked through a particular word in the PSB (Process State Block). Condition variables, monitor locks, and even the ready queue are all queues where the queue pointer points at the tail of the processor queue. For DragOps, there are Queues and MetaQueues. Although both are circular queues, and both point at the tail, the link words are different. A DragOps process can be queued at the same time on both a queue and a metaqueue. DragOps queues are used by "normal" Mesa monitors and condition variables. MetaQueues are used for more specialized reasons, like the ready queue (waiting for processor), the pageFault queue (waiting for a page to be brought into memory), and the timeout queue (waiting for some time to expire). Queues need not be pinned, while MetaQueues must be pinned. The scheduler is permitted to move processes between MetaQueues, but is not permitted to touch queues. All of this is done in the name of simplicity, you betcha. Monitor locks & condition variables For PrincOps, monitor locks and condition variables are managed by microcode that has carefully been constructed to not take interrupts at awkward times. For DragOps, managing monitor lock and condition queues is too complex to be performed in a single instruction, so each monitor lock and condition has a spin lock that must be acquired before the queue can be examined or modified. A potential problem with this scheme is that a higher-priority process may attempt to acquire the spin lock while a lower-priority process possess the lock. Therefore, each spin lock has the address of the owning process, so a process that fails to acquire the lock can yiled control directly to the owning process. Although this is technically a violation of preemptive scheduling, it is necessary to prevent livelock (where no progress can be made because of the higher-priority process spinning). State vectors For PrincOps, the eval stack and other cleanup information is contained in a state vector. Minimal stack restrictions on monitor entry and condition wait ensure that the eval stack is empty when such processes go to sleep, which tends to keep the number of state vectors low. For DragOps, there are no state vectors. When a process is about to go to sleep, it saves the frames in the IFU and EU stacks to memory, saves the appropriate EU registers to the process block, and puts itself on the appropriate metaqueue (if any). The only problem is ensuring that there are sufficient nachos to accomodate the stack of the process. The current thinking is to have an emergency-level process put every other process to sleep when frames are about to run out. When that has been done, a world-swap debug can take place. An improvement on this scheme can be made if there is an error generated for a particular process when it has used "too many" frames. Since this is typically due to a process executing unbounded recursion, we can tolerate at least a few runaways without having to world-swap. In both cases, we have to have some mechanism for keeping track of how many frames are in use by a given process, and how many are left in the global pool of frames. Details are yet to be specified. Costs For PrincOps, a process switch is on the order of 5 procedure call times. A procedure call (and return) is on the order of 5 microseconds (on the Dorado). For DragOps, a process switch is on the order of 100 procedure call times (very rough estimate). Partly, this is because procedure calls are about 10 times faster, and partly this is because there is more per process state to save and restore. Timeout For PrincOps, a timeout occurs when the clock ticks and some PSB that is awaiting timeout has its wait count go to 0. All PSBs have to be touched at every tick, although this is done via microcode. For DragOps, at each tick every process in timeoutMetaQueue has its when field decremented. If that field reaches 0, the process is placed in the ready queue. It then becomes the responsibility of the process to remove itself from the appropriate condition variable. This makes page faults (if any) due to touching the condition variable occur in the "right" process. Only PSBs waiting for timeout have to be touched at every tick. Aborts For PrincOps (as implemented for Cedar), aborts are enabled/inhibited on a per condition variable basis, and aborts are tested only by CVs & ICVs with aborts enabled and by explicit tests. For DragOps, aborts are enabled/inhibited on a per process basis and on a CV basis. Abort requests are tested when waiting for CVs, ICVs, and MLs, as well as the normal explcit tests. Is it worth having the enable/disable on a per-process basis? (it costs rather little) Things to do This section is a list of things that still need some design work. Fork / join These need to be coded in greater detail. Page faults How will the fault handler work and place things to sleep waiting for page fault? For an EU page fault, the offending memory address is in the MAR register in the EU. For an IFU page fault the offending PC is for the start of the instruction, so the memory address to page in may be the next page (since this fits well with page clustering anyway, we may want to always page in the following page on an IFU page fault whenever the following page is also valid). Soft and hard emergency limits on frames These need support in the scheduler, as well as in stack save/restore. Reaching the soft limit (per process) should raise an error. This is just an attempt to restrain runaway processes. Reaching the hard limit will cause system shutdown and a call to the world-swap debugger. This probably will only happen if a significant number of runaways occur. Timeout mechanism In current Cedar relatively few condition variables have timeouts (the default is not to have timeouts). The current design for the timeout queue is based on the assumption that this situation will continue on Dragon. The current design has O(n) insertion and deletion of entries from the queue, O(n) updating for every tick, and O(1) testing, where n is the number of processes waiting for timeout. A heapsort-style priority queue has O(n log n) insertion and deletion, and O(1) testing, but it also has more complicated code, and needs an auxilliary pinned data structure (1 word / process). The current simple design will be used until it becomes a bottleneck. Should the timeout "process" just be part of the scheduler? How will elapsed time be determined, and to what accuracy? Just for the record, there are three clocks of current interest to Cedar: 1: Time of day clock. This need not have resolution of better than a second, and it need not be locally stable, but it should have very good long-term accuracy. 2: Timeout clock. This need not have great accuracy, but it must generate interrupts, and it should have resolution of 10-100 milliseconds. More resolution is OK provided that timeout interrupts don't occur more often than every 10 milliseconds. 3: Elapsed time clock. This need not have great long-term accuracy, but it should have very good short-term accuracy, have roughly microsecond resolution, and it must be quite cheap to read. This clock can easily synthesize the Timeout clock. Stack trace SafeStorage needs a way to trace out the process stacks atomically. That is, all possible references in the process stacks must be discovered without any reference containing processes making headway. Dump frames are already pinned, and the panicStop mechanism can be used to stop all processes except for the current process (we may also want to have an stopRC command that would stop all processes that had not declared themselves to be non-RC). We can allocate frame extensions out of a special pool of memory that allows scanning. Possibly we should also make this pool pinned? Reschedule & page fault Setting L at procedure essentially transfers registers from the called frame to the calling frame, as far as stack save and restore are concerned. It will only work properly if both the calling frame and the called frame are in the EU (and IFU) registers. If the various compilers (and assembly language coders) guarantee that no calls are made before setting L, then there are only two sources of having the calling frame migrated into memory - reschedule & page fault. For these traps, if the youngest frame below the trap is P, and the next youngest is Q, and Q has zero registers, then both P and Q have to be restored before returning from the trap. ÎSimProcessImpl.mesa Copyright c 1984, 1985, 1986, 1987 by Xerox Corporation. All rights reserved. Russ Atkinson (RRA) October 9, 1986 4:57:12 am PDT Carl Hauser, April 1, 1987 10:26:21 am PST Demers, May 3, 1987 12:30:51 pm PDT About the Dorado Simulation Environment: 1. See the comments in SimProcess 2. The most significant differences between the SIM and RDI versions are in initialization, DirectedYield and RescheduleInterrupt. 3. There are (intended to be) lots of comments about how things will change between SIM and RDI. Search for SIM and RDI in the comments. About processes: 1. All processes execute in a single address space, although we will want to extend our model to multiple address spaces some day (Dragon has address space switching support). 2. Processes are (relatively) lightweight. Most of the process switch time is devoted to saving and restoring registers. We estimate 100-300 msecs per process switch, depending on the amount of state. 3. Processes are dynamically assigned to processors by the scheduler, so that processes can be considered virtual processors. We think of the scheduler as executing in the cracks between processes. 4. The scheduler attempts to run higher priority processes in preference to lower priority processes. However, there is no guarantee that a higher priority process will preempt a lower priority process, even for single processor systems. About locks: 1. Primitive spin locks (PSLs) are the most primitive locks. PSLs are built out of CStore, are only acquired with reschedule off, and must be pinned. A single processor system should never wait for PSLs, obviously. In a multi-processor system PSLs must never be held long, or they become a bottleneck. The most important (and currently only) PSL is the metaLock, which controls access to the global process state information (especially the meta queues). 2. General spin locks (GSLs) use CStore and directed Yield. If CStore cannot acquire the lock, then the process attempting to acquire the lock donates its cycles to the process holding the lock using directed Yield. If the process holding the lock cannot be run, directed Yield acts like undirected Yield. GSLs can be non-pinned. 3. General queues (GQs) use a GSL to serialize ownership of the queue, and a circular queue of processes to hold the processes that are waiting. See Enqueue and Dequeue for details. 4. Monitor locks (MLs) are built from a GQ and an ownership word, which is used to denote the process owning the lock. See MonitorEntry and MonitorExit for details. 5. Condition variables (CVs) do not assume that a monitor is held, although one is always present. CVs also support timeouts. CVs are built from a GQ and a timeout word that holds the initial value of the timeout period. A flags word contains a bit that can enable aborts to affect the CV. 6. Interrupt condition variables (ICVs) are the mechanism for turning device signals and interrupts into ICV notifications. ICVs do not assume that a monitor is held, since none is ever present. ICVs also support timeouts. ICVs are built from a CV and a request bit for interrupt requests so we do not lose them while not waiting for the ICV. ICVs must be pinned, to allow the scheduler to remove requests from them. Remarks: 1. Note that anybody who calls MarkFrame[] had better be sure he's on the IFU stack (and hasn't been replaced by the bogus frame). Otherwise ProcessSwitch is going to get totally screwed up  its correctness depends on the caller of MarkFrame not being saved. This is probably okay, as MarkFrame is called with interrupts disabled, and nothing called after it can page fault. 2. Maybe somebody had better know how many processors there are. Consider the possibility that somebody causes a panic stop before all the processors have installed themselves. Arrgh! I've put a patch in there to fix this case. I believe it's only necessary if we want to allow somebody to bring the system to a panic stop and then release the metaLock for awhile, but I think that's desirable. To Do: 1. Check to see whether SaveProcessState and RestoreProcess need process arguments. I (ajd) believe they don't. 2. Similarly, check to see whether EnqueueReady, EnqueuePageFault, ... need process arguments. I (ajd) suspect they don't. Types Basic A StackRegister is an index into the EU stack registers. Global State SIM-specific Priority reduction, ... (because so much code spins). The processor on which a Cedar7.0 simulator process is currently running SIM only. SIM only. Simulation of process suspension and process switch. Not very faithful, but ... SIM only. SIM only. SIM only. Operations with missing implementation details. Aux registers This aux register holds the current process block address. Outside of regions holding the metaLock it must be consistent with CurrentProcessor. RDI: Must change to fetch a processor register. Must change to set a processor register in RDI. This aux register holds the current processor block address. Must change to return a processor register in RDI. Set the aux register that holds the current processor block address. This is called only during initialization. (????) Must change to set a processor register in RDI. Global frame variables ... arbitrary limit on stack depth to guard against runaway processes. This limit could also be kept on a per-process basis at the cost of extra space. It is left as an unspecified constant. ... arbitrary limit on remaining stack frames to ensure that enough is left to save the state information for all running processes. It is left as an unspecified constant. ... the spin lock for meta queues. NIL means not busy. Any process that desires to examine or modify any meta queue must acquire this lock and spin until it is free. The possessor of this lock must have traps disabled, and must not page fault ... the lock for the scheduler. NIL means not busy. The possessor of this lock must have interrupts disabled, and must not page fault. The possessor of this lock has the sole responsibility to handle interrupts and to reschedule other processors. Possessing this lock does not permit using a meta queue without acquiring the metaLock as well. All ready processes are queued in this array of metaqueues. All processes waiting page faults are queued in this metaqueue. All processes waiting to handle page faults are queued on this interrupt condition. All processes waiting timeouts are queued in this metaqueue. Processors are arranged in a ring. This variable refers to the tail of the ring. This variable is protected by the metaLock. Free processes are arranged in a ring. This variable refers to the tail of the ring. This variable is protected by the metaLock. Possessing this lock gives the current processor the exclusive right to bring all processors to a panic stop. This is the number of times to spin-test in MonitorEntry when the monitor lock is held by another running processor. The "correct" value will be determined by experimentation. This is the priority of the lowest priority running process. It is used in the scheduler to accelerate testing for handling of reschedule interrupts. This value should only be used as a hint unless one is in possession of the metaLock. This is the priority of the highest priority process on the ready queue. It is used as an accelerator for various cases. TRUE if there have been calls to MakeReady since the last call to the scheduler or RaiseReschedule AND the priority of the process that was made ready is likely to be worth running immediately. This is a statistical hack to reduce the number of wakeups of processes that have been Notified before the monitor lock has been released. It may be worth keeping this flag on a finer basis than globally, or having some other hack entirely. External procedures ... forks a new process, which will initially call the given procedure using the given arguments. The number of words of arguments and returns is also necessary. In the calling process: F1: allocate a new process. Return NIL if we can't do this. (Error??) -- CHH: PrincOps ProcessImpl.Fork waits until a process is available. Do we really want to change the semantics? March 12, 1987 F2: newFX _ Allocate a FX of (IF nRets > maxStackRets THEN nRets ELSE 0)+(IF nArgs > maxStackArgs THEN nArgs ELSE 0) words. F3: copy the arguments from argPtr^ for nArgs words to newFX (the original argument storage belongs to the caller) F4: setup the process block & make it ready to run Forkee, having set things up so that Forkee's arguments will be correct. Forkee[proc, newFX, nArgs, nRets] RDI: allocate storage, copy args to a safe place, etc. RDI: make the process a schedulable entity that will run Forkee when it's scheduled. SIM: Note at this point SimCurrentProcessor[] is NIL! This is okay, since we're about to suspend ourselves. When we get switched back to, the current processor will be filled in. RDI: get arguments from somewhere RDI: put results somewhere RDI: Free the results SIM: don't create a suspension here ... this process won't get switched back to! SIM: now wake up the suspension we've just switched to ... retRecord: WordSeq; FF0: IF nRets > maxStackRets THEN { retRecord _ argPtr^; argPtr^ _ argPtr + nArgs; }; FF1: Depending on nArgs, either push argPtr or push nArgs from argPtr^; FF2: Push appropriate descriptor information for proc FF3: Call proc using an inline SFCI instruction; it eventually will return or not as it sees fit. JJ1: proc's RETURN record may either be in the FX pointed to by argPtr at offset nArgs or on the stack. JJ2: wait for JOIN or DETACH by another process. JJ3: IF JOINed THEN { Copy return values in stack or FX to a Nacho; Give the Nacho to the other process } JJ4: FrameAllocator.Free[argPtr]; JJ5: place the process in the free list (state _ free), free any remaining resources (possibly a FX) and quietly disappear ... joins the specified process, which waits for the process to complete, then copies the return values to the address given by retPtr. In the calling process: J1: wait for process to be in the done state (wait on condition?) J2: copy the return values to retPtr^ J3: place the process in the free list (state _ free) J4: return to the caller get the results ???? Possibly this should be a different error ???? ???? Possibly this should be a different error ???? SIM only ... this is a veneer around RDIDirectedYield, below. This is where the process will resume when it's rescheduled. ... yields the processor to the nextProcess, placing the current process in nextState. If nextProcess = NIL or is not ready, then the executing processor is yielded to the "best" ready process, placing the current process in nextState.. DirectedYield inhibits critical traps, and performs a ProcessSwitch. The when word is used for passing through timeout information. SIM: This routine must be called only when critical traps are enabled. RDI: change name to DirectedYield! This Indicates that the current frame should not be saved. ... waits for the condition variable cond to be the target of a Notify, Broadcast, or timeout. If lock # NIL, then lock must be released during the possible pause, and lock must be re-acquired after the Wait has finished. Place self on the condition variable; we do this before giving up the monitor to avoid missing a Notify, which would be wrong; we cannot get a Notify between now and releasing the monitor lock, since one must possess the monitor lock in order to do a Notify. Release the monitor lock. After this the condition can be Notified by another process. ???? How test abort ???? Go to sleep, choosing the "best" process to run next. If we get a Notify after exiting the monitor and before going to sleep, the Notify will remove this process from the condition, yet will NOT place this process on the ready queue (because its state is not yet waitingCV). Remove self from the condition queue, if still on it. DequeueSelf has no effect if the current process is not on a queue, so a race with some other process trying to dequeue this process is benign. Reacquire the monitor lock. Final test for abort request while we were waiting on the CV. ???? How test abort ???? ... waits for cond to be the target of an interrupt request, or timeout. Unlike Wait, there are no monitor locks involved, and we have to proceed immediately if interrupts have occurred since the last WaitInterrupt. For now, we prohibit aborts on interrupt condition variables; comments suggest how aborts could be implemented if we wanted them. We are now on the queue. A DelicateNotify is guaranteed either (i) to remove somebody from the queue, or (ii) to fail to acquire the queue. In case (i), if this process is the one removed from the queue, and it happens before the DirectedYield below, then the DirectedYield will return immediately. Otherwise, things happen normally. (See the comments in Wait.) In case (ii), the queue is held by some process in WaitInterrupt, which is guaranteed to examine cond.flags.condRequest shortly. In no case will an interrupt be lost. ABORTS: IF we've been aborted THEN skip the DirectedYield ... ABORT: IF we should abort THEN raise ABORTED; Also, make sure to change the code below to preserve the value of cond.flags.abortEnable. Clear cond.flags.condRequest. This is correct even if it's been set since we've examined it, since the current process (doing WaitInterrupt) is about to wake up. ... notifies the "best" process waiting on cond that the condition has occurred. The protecting monitor lock is presumed to be held, but is not needed for this primitive. There really was a process waiting on the CV. Although a process may be made ready, the process switch is not immediately required. The process switch may occur when the protecting monitor lock is released. ... notifies all processes waiting on cond that the condition has occurred. To eliminate race problems, all of the waiting processes are made ready while holding onto the queue. The protecting monitor lock is presumed to be held, but is not needed for this primitive. Remove all of the processes from the circular queue and make them ready. Although processes may be made ready, the process switch is not immediately required. The process switch may occur when the protecting monitor lock is released. ... is performed at the entry to any monitored procedure to lock up the monitor for exclusive access. This operation is performed frequently, so it should be fast in the case where the monitor is not already owned. Try for conditional store of current PSB index with 0 wait chain. If we succeed, then we are in, and can return. Place self on the monitor queue. If the monitor is still held, then go to sleep, yielding to best process, only to wake up when the monitor queue is OK. Otherwise, some process released the monitor while we were trying to Enqueue, so we should get off the monitor queue and try again. ... frees up the monitor lock. If there is a process waiting the monitor, dequeue the process from the monitor queue and place it in the ready queue. The current coding does nothing if we do not own the lock. Should we die instead of doing nothing? Give up ownership of the lock. Make ready the next process waiting for the monitor. There is a slight possibility that some other process will jump in ahead of this one while the monitor is free, but fairness is not guaranteed. deferredWakeups = TRUE indicates that we deferred a desirable wakeup while processing a Broadcast or Notify for some monitor. Statistically speaking, it was probably for this monitor. So we raise reschedule here to get the best processes running. ... tests for a requested abort. ???? CHH says this is bogus. ???? ... requests the given process to abort itself. ???? CHH says this is bogus. ???? ... changes the priority of the current process. We need to recompute lowestRunningPriority; also, if our new priority is lower than that of some ready process we need to initiate a process switch. Recompute lowestRunningPriority ... ???? All that's really necessary here is { MarkFrame[]; ProcessSwitch[ready, NIL] }, but that won't work in the simulation environment! ???? RDI: the above IF becomes simply IF doYield THEN DirectedYield[ready, NIL, 0]; ???? Reschedule Interrupt [requestKind: RequestKind] SIM version. Obviously we need to do something better here for RDI. SIM only. SIM: call this only from user-level code  when there's no suspension in the process block  because it sill put one there. On a real Dragon the current processor can change whenever interrupts are enabled! This code would be bogus on a real machine, but, after all, it's here to simulate a real machine's interrupt mechanism ... This is where the current process resumes when it's rescheduled. ... is called whenever the reschedule interrupt is enabled and either the reschedule line is asserted OR reschedule traps become enabled and there is a deferred reschedule pending. In either case, we start up with critical traps inhibited, and a special return (hand-coded in the RescheduleTrap vector) enables critical traps on exit. On entry, volatile EU state has been pushed in such a way that when the process is switched to later the volatile EU state will be restored correctly (again, hand-coded in the RescheduleTrap vector). RescheduleTrap is primarily called in response to two causes: device interrupts and explicit condition variable wakeups. Device interrupts are turned into condition variable wakeups in this routine, so the appearance outside of this routine is that we only have condition variable wakeups. Statistically we only get to enter RescheduleTrap if there is a ready process with priority >= lowestRunningPriority, and we try to give the scheduler to a processor with priority = lowestRunningPriority. The major exception to this is time-slicing, which should be kept to a modest rate (the current system uses about 10 per second). First, try to grab ownership of the scheduler (if at lowest priority) This processor is one of the best to try the scheduler, and the scheduler is free. At this point we have acquired the scheduler. sample & clear request word (currently protected by the schedulerLock) Make maximum possible room on IFU stack for device interrupt handler. This is expensive enough to be worth doing before grabbing the metaLock. don't allow changes to the ready queue by other processors Service requests in the currentReq word by tweaking the appropriate interrupt condition queues. This loop is not the fastest way to do this, but it is not worth improving unless we find out that it is taking a lot of time. There are ready processes that are better than at least some processor, so go do the bulk reassignment. Release locks. (in the given order). ???? what does the order have to do with anything? I would believe this if the test of schedulerLock = NIL below were done while holding the metaLock, but it isn't ???? - ajd Normal exit, just follow orders. If no orders to follow, then exit the inner loop. We're panic stopped, spin in this loop until ordered to restart. Switch to a particular process or to switch to the "best" available process. First (!) remember the switchTo field, and then reset orders to indicate they've been followed. Follow the orders ... Indicates that only frames older than the current frame are to be saved. It is possible that a switch is necessary. Otherwise keep running the current process. ???? How likely is this test to fail? I claim very unlikely. In any event, it's only an accelerator. I'd like to remove it. - ajd ???? Indicates that only frames older than the current frame are to be saved. Come to a panic stop. Save the state so it can be examined/modified. Indicates that only frames older than the current frame are to be saved. Restart after panic stop. Restore the state in case some piece of it was modified while we were stopped. Test for residual unserviced interrupts If some process already has the scheduler lock then we need not persist. If no device requests, then there is no point in going back for another try at the scheduler. By this point we have given a lowestRunningPriority processor the first chance to get in and process the interrupt. However, lowestRunningPriority must be treated as a hint, not as the truth. So if there are still device requests pending and no one has the scheduler, we go back to try to service those requests using the current processor. We lower entryPriority to try to force an entry into the scheduler. Special external procedures ... is called by the timeslicer service. It advances all processes waiting in the ready queues by one, and directs all undirected processes to switch to the best available process(es). Just order each processor to switch to the best available process. Force a switch to the best available process Last, raise the reschedule interrupt to make all processors choose the best available. Even the executing processor will eventually respond. ... causes all processors except the current one to come to a screeching halt with properly saved state. When we want to perform stack tracing, delicate debugging, or prepare for world-swap debugging, we use this routine to shut down the world. On entry, interrupts should be disabled but the metaLock should not be held. We return with interrupts disabled and the metaLock and panicStopLock held. Interrupts do get enabled during this routine, though, so a process switch might occur. Acquire panicStopLock, disable interrupts. Inhibit interrupts while we try to acquire the panicStopLock. If panicStopLock is acquired, exit with interrupts disabled. Allow interrupts to occur while we are waiting. This allows the current processor to panic stop if it is requested to do so. Spin (without using CStore) until panicStopLock is free. ???? I don't understand the need for the MarkFrame, SaveProcessState pair. Of course it can't hurt, but ... is it just so the caller doesn't have to worry about stack overflow? - ajd ???? Indicates that only frames older than the current frame are to be saved. We save the process state to make sure that the calling process is stable, and to make sure that we have enough stack registers to complete processing. We must have interrupts disabled to call this routine, but we don't need the metaLock. At this point all of the processors except the current processor have entered the stopped state, and are waiting for different orders to be given. We return to the caller with interrupts off and the metaLock and panicStopLock held. ... allows the stopped processors to resume with normal processing. Call this procedure to release all processes from their stopped state. We assume that the metaLock is held and interrupts are off, that the current process holds the panicStopLock, and that all processors but this one are stopped (i.e., the current process has successfully caused a panic stop). On exit, the current process has released the metaLock and the panicStopLock. At this point all of the stopped processors have been ordered to restart. It's not necessary to wait for them to follow the orders. They are guaranteed to do so eventually. Release the panicStopLock and the metaLock and return. The order of releasing the locks is important. Init[] tests to see if anyone holds the panicStopLock, while holding the metaLock; so here we must ensure that we can't release the panicStopLock unless we hold the metaLock. ... for each process P in the page fault with startPage < P.page < endPage, make the process ready. ???? Why can't we use a trailing pointer and remove processes from pageFaultMetaQueue directly here, instead of calling DequeueMeta (which has to search the queue) ???? After all, we hold the metaLock! ???? - ajd place the process on the ready queue (also maintains highestReadyPriority) The new process might be worth waking, but we don't do it here. We just remember that it was desirable. Internal procedures ... saves the state of the current process. If the process is not waiting, then it is placed on the ready queue. If nextProcess # NIL then it is the next process to run. Otherwise, the "best" ready process is chosen. During this sequence, we assume that critical traps are disabled. Note that if nextProcess # NIL, we must switch to it if it is ready, even if the current process is "better" (see comments in AcquireQueue to see why we require this). This is expensive enough to do outside of the region that holds the metaLock. From now on, don't allow changes to the ready queue by other processors. Check to see if this process is trying to go to sleep on a monitor lock that has already been exited, which could happen if the MonitorExit occurred after this process got on the queue, but before the Yield. We have carefully arranged for this to be OK with Dequeue and friends. Check to see if this process has already been removed from the condition queue, which could happen if the Notify occurred after this process got on the queue, but before the Yield. We have carefully arranged for this to be OK with Dequeue and friends. A page fault has occured. Put the offending process to sleep on the page fault metaQueue, then notify the page fault handling process. This is a directed yield to a process that is page faulting, so we should also wait for that page to be ready. It does us no good to proceed until that process is ready. Release the process structure here. This process will never be switched to again. We can't touch the process structure hereafter. We assume all resources (other than the Process structure itself) have already been released. This is an undirected yield OR a directed yield to a process that is not ready for some peculiar (possibly transient) reason. Just choose the best process to run. There are as many idle processes as processors, and the idle processes are always ready to run, so there will always be a process ready to run. At this point nextProcess # NIL, and we're committed to switching to it. Note: this is currently the ONLY place that a process is removed from a ready queue! Recompute the highestReadyPriority. Make nextProcess run on this processor. Recompute the lowestRunningPriority. Note that if we are the same process no state needs to be restored, since nothing should have changed except volatile EU state, which is restored later. We get here when we have NOT found a better process to run. Therefore there is no change necessary, and things get done more quickly. ... place process on the ready queue, if it's currently waiting. Also remove process from the timeout queue if it is there. SIM only: on entry, we require that interrupts NOT be disabled. Remove process from timeout queue if present ... Place the process on the ready queue (also maintains highestReadyPriority) ... Remember if the new process might be worth waking ... ... places the process on the queue in FIFO order. Priority processing is the responsibility of Dequeue. ... performs dequeue by process priority. We perform a linear search of every process in the queue to find the best. The best process in the queue is the first one we find with the maximum priority. Performing the priority testing in Dequeue is more expensive for the case where there are several things on the queue, but it allows us to change process priorities without altering the queue. If the process we find has also timed out, we have to handle the case elsewhere, but it is OK for Dequeue to dequeue such a process. Dequeue does not remove such a process from the timeout queue. ... is the inside part of Dequeue. While we still dequeue by process priority, we assume that we have already grabbed ownership of the queue. This allows us to have common code for this case and the more delicate notification required by interrupt requests & page faults. only process in queue, so clear the chain new candidate for the best process don't queue chain point to deleted process ... dequeues the current process from the given queue. This operation has no effect if the process was not in the queue. last one in queue, so show no chain don't let deleted one be the queue head ... grabs ownership of the given queue. Performs Yield[ready, owner] until queue is owned. This directed Yield is necessary to overcome nasty interactions between spin locks and preemptive scheduling. Try to donate our cycles to the owner of the queue. Note that if the owner is running on another processor that there is not need to Yield, since the queue should be given up quite soon. ... releases ownership of the queue. Assumes that the current process owns the queue. RDI: change this to an inline that just sets q.busy _ NIL. Internal procedures (interrupts disabled, must not hold metaLock) ... grabs ownership of all of the meta queues. On entry, we require that critical traps are disabled, of course. On exit, we hold the meta lock. spin using local cache only to reduce bus contention ... releases ownership of the meta lock. On entry, we require that critical traps are disabled and that the metaLock is held. On exit, the metaLock is not held, although critical traps are still disabled. RDI: change this to an INLINE that directly sets metaLock _ NIL. ... saves frames and process info from the current processor for the given process. On entry, we require that critical traps are disabled. On exit, there are no frames in the IFU stack (so a return will provoke a stack underflow). Note that this procedure must be an INLINE to keep from putting another frame on the stack. save stack frames SaveStack[]; (RDI only) save EU regs (RDI: fix this) FOR which: EUstateIndex IN EUstateIndex DO process.euState[which] _ EUFetchSpecial[which]; ENDLOOP; check for local stack overflow (RDI: fix this) IF WordToInt[process.euState[framesLeft]] <= 0 THEN cause a stack overflow fault for the caller NotYetImplemented[]; ... restores the given process to a running state. Also changes the result of CurrentProcess. On entry, we require that critical traps are disabled, and process.state = running. Note that this procedure must be an INLINE to keep from putting another frame on the stack. restore EU regs (RDI: fix this) FOR which: EUstateIndex IN EUstateIndex DO EUStoreSpecial[which, process.euState[which]]; ENDLOOP; ???? WHO should set the current process aux reg ???? I claim it should not be done here. In fact, I claim RestoreProcess doesn't need an argument; it always restores from CurrentProcess[]. - ajd Internal procedures (interrupts disabled, must hold metaLock) ... does an ICV notification, with the understanding that interrupts are disabled and the metaLock is held, so we just can't yield the processor. The condition must be resident, of course. We got the queue, so we can make the best process in it ready. If we did not get the queue, then the owner of it (who's running WaitInterrupt) will examine the flags pretty soon and see the notification. The following is like MakeReady ... see the comments in Wait and WaitInterrupt. remove from timeout queue if present place the process on the ready queue (also maintains highestReadyPriority) The new process might be worth waking, but we don't do it here. We just remember that it was desirable. ... set processor orders based on whether some ready process is "better" than any running process. We run through the ready processes in highest-to-lowest order. At the end of the reassignment, if we had to change the orders of any processor other than our own then we raise reschedule to get the other processors to follow their orders. The search for the best processor is arranged so that in the (most likely) case  we're running on the lowest priority processor and there's only a single ready process that needs to be assigned  the process will be assigned to the current processor, and it won't be necessary to raise reschedule. On entry we require that interrupts are disabled and the metaLock is held. (FOR each schedulable ready process priority pProcess, decreasing, DO ...) (FOR each ready process at priority pProcess DO ...) Ensure there's a processor assigned to process ... Set best _ lowest priority assignable processor, favoring self ... If there are no more assignable processors, we're done ... Set orders for best to switch to this process, and remember to pull reschedule if necessary ... ... sets processor orders based on whether the a ready process is "better" than any running processes; we run through the ready processes in highest to lowest order. At the end of the reassignment, if we had to change the orders of any processor other than our own then we raise reschedule to get the other processors to do their switching. On entry we require that interrupts are disabled and the metaLock is held. The cost of algorithm in this procedure has an upper bound of O(N*MIN[N,MAX[K,R]), where N is the number of processors, K is highestReadyPriority-lowestRunningPriority, and R is the number of ready processes with priority IN (lowestRunningPriority..highestReadyPriority]. In practice, the algorithm has somewhat better average behavior, since in most cases there will have been only one process made ready by a single device interrupt, an idle processor will answer the interrupt first, and immediately assign the new process to itself with no further reschedule activity. In this (anticipated) normal case the cost is O(K)+O(1). This algorithm could be made faster in the high cost cases by keeping the processors sorted by priority, but that would increase costs in ProcessSwitch so it might not be a net perfomance gain. At this point we are about to reassign all of the processors that need it, so nothing is really deferred. The first scan is for some available processor that could run the requested process. If none is found, then we exit all loops. If the first available processor found is not already at the minimum possible priority then it is worth scanning for another processor with a lower priority. We have found the best choice for the given process. If we are gave orders to another processor, then we rememebr the fact. The best processor was the first one we found. Therefore we advance firstAvail to the next processor (unless that happens to be the current processor, in which case we are completely done scanning). In this case the process was already assigned to a processor. So we want to choose another processor (starting at firstAvail) and another process. This should be rare. ... places the given process on the ready queue using the meta link. On entry, we require that critical traps are disabled and that the metaLock is held. On exit, process.state = ready. ... places the given process on the page fault queue using the meta link. On entry, we require that critical traps are disabled and that the metaLock is held. On exit, process.state = waitingPage. ... places the given process on the given meta queue using the meta link. On entry, we require that critical traps are disabled and that the metaLock is held. ... removes the given process from the given meta queue (timeout, ready, pageFault). On entry, we require that critical traps must be disabled and that the metaLock is held. The process state is not changed except for the meta link. remove from meta queue if it is there last one in queue, so show no chain don't let deleted one be the queue head Low-level primitives Conditional Store ... atomically performs {IF (stored _ ptr^ = old) THEN ptr^ _ new}. SIM: all CStores are atomic wrt one another, and wrt setting lock to nil, below. SIM only. In RDI just do the assignment inline. ... atomically performs {IF (stored _ ptr^ = old) THEN ptr^ _ new}. SIM: all CStores are atomic wrt one another, and wrt setting lock to nil, below. SIM only. In RDI just do the assignment inline. ... atomically performs {IF (stored _ ptr^ = old) THEN ptr^ _ new}. SIM: all CStores are atomic wrt one another, and wrt setting value to nil, below. SIM only. In RDI just do the assignment inline. Interrupts and I/O ... inhibits interrupts (must be a procedure call for RDI) ... enables interrupts (must be a procedure call for RDI) ... atomically reads and clears the device requests. This is done by reading the appropriate EU I/O location (Interrupt Request Word) then clearing the bits read. RDI: this should be MACHINE CODE to read EU I/O location, and not ENTRY. ... Determines whether or not device requests are pending, but does not alter them. This must agree with ReadAndClearDeviceRequests. RDI: this should be MACHINE CODE to read EU I/O location, and not ENTRY. ... raises the Reschedule interrupt, which, if disabled, will occur when it becomes enabled again. How to do this in RDI? SIM only. This is a crock: it ought to be done atomically. On a Dorado we must swap (16-bit) words. This is wrong for RDI, where the body should just be RETURN [LOOPHOLE[x]] ???? Should be in Basics or something like that ???? - ajd ... fetches a word from the given special EU register. ... stores a word into the given special EU register. ... saves the stack (updates the current value of the hook EU register), returning the number of frames saved. The stack is saved up to (and including) the eldest marked frame. Also updates the framesLeft EU register. For excruciating details, see GenStack.mesa. ... marks the youngest frame on the IFU stack as being the last one to save. The eldest frame marked is actually the last one saved by SaveStack. This procedure probably needs to be called when interrupts are disabled. Initialization ... called by each processor when it starts, with interrupts disabled and with enough room on the EU stack that a stack overflow is guaranteed not to occur. The value of indexPtr^ is the index of this processor's ProcessorRep structure in processors, below. Other processors will spin on indexPtr^ until it increases by 1. Thus, only one processor can enter at a time. This is important only for Processor 0, which creates the Nachos, Process and Processor objects. Every other processor just acquires the metaLock to allocate itself Processor and Process objects for the scheduler to manipulate; it then releases the metaLock and idles until the scheduler comes up with something better for it to do. Create the Nachos, Process and Processor objects, etc. Now it's okay to let other processors in ... Set up my processor object (so I can acquire the metaLock). Allocate myself a Process object, initialize so the scheduler can manipulate me. Somebody else has already brought the system to a panic stop, or is about to do so. In either case, this process should come to a panic stop ... (Do you suppose this code will ever be exercised on a real system? - ajd) Idle RDI: here we should test that the clock really did interrupt and reset it. [requestKind: RequestKind] SIM only - this is copied from the body of ShuffleReadyQueues. Nacho Storage Process Storage Mostly just dummied-up for simulation purposes. RDI: Does this have to change? ... create all the process objects. On entry we assume interrupts are disabled and the metaLock is held. RDI: Does this have to change? Possibly we should not initialize the secure key fields of the ProcessReps here. Arguably they should be initialized to random values rather than 0. ... put a Process object on the free list, restoring its fields to a "clean" state. On entry we require that interrupts are disabled and the metalock is held. ???? What do we do if check is TRUE ???? RDI: remove initialization of sim fields; do something about euState? RDI: do something about the EUState here? Probably not necessary. - ajd ... get a process object from free process list. On entry we require that interrupts are disabled and the metalock is held. ... get a process object from free process list. SIM: On entry we require that interrupts are enabled. Processor Storage Initialize the ProcessorRep structures. ... insert p into the ring of Processor objects. On entry we require that interrupts are disabled and the metaLock is held. Called only during initialization. SIM Initialization Something like this gets hand-coded for initialization, and is run by each processor. RDI: if index is 0 then start ProcessImpl. Ê6ç˜headšœ™Jšœ ÏmœC™NIcode™2L™*L™#—šœ(™(Iitem1šœ!™!Mšœ‚™‚Mšœ‰™‰—šœ™M™¯MšœÏgœ:™ÊM™ÆMšœpÏiœi™î—šœ ™ MšœÏbœÎŸœ]™ÊMšœ œ·™ÌMšœ œ¥™¶Mšœ  œ•™¥Mšœ œŽ™¤Mšœ œ„™¤—šœ™MšœôŸœ‚™ùMšœŽ™Ž—šœ™Mšœp™pMšœ{™{M™—šÏk ˜ L˜Lšœ ¡œ Ïc ˜#Lšœ¡œ¢ ˜™gLšœ˜—L˜—L˜Lšœ&™&Lš ©œ™¯Lšœ,¢˜HLšœ˜Lšœ˜——L˜Lšœ!™!š¡˜š¡œ¡˜%šœ ¡œ˜L™1—šœ ¡œ˜L™@—šœ˜™L™_Lšœ4˜4Lšœ%˜%—™˜ L™H—Lšœ"˜"—šœs˜sL™WLš ‰™‰˜ L™H—Lšœ"˜"L˜——L˜—šœ˜šœ™™.šœ ˜ L™H—Lšœ#˜#—Lšœ$˜$—Lšœ˜—šœ ˜ ™™NLšœ!˜!—Lšœ%˜%—Lšœ˜—Lš¡œ¡œ˜—Lš¡œ˜L˜—šœ(™(™HLš¡œ¡œ¡œ¡œ˜!—™]Lš¡œ¡œ¡œ¡œ˜)—šœ›™›Lšœ¡œ¢Ðbc ¦ ¦ ¦ ¦§ §˜Š——Lš¡œ˜—Lšœ¢˜3L˜——™š£œ¡œ¡œ˜#Lšœ¹™¹Lšœ˜Lšœ˜NšœB™Bš¡œ;¡˜@š¡œ¡˜šœ ˜ šœ,™,Lšœ¡œ˜Lšœ!˜!—Lšœ˜—Lš¡œ˜—Lš¡œ¡œ¡œ˜'Lš¡œ˜—N™L˜Lšœ˜Lšœ¢˜3Lšœ¢ ˜)L˜L˜—š£œ¡œ¡œ˜Lšœé™éLšœ!˜!L˜™*š¡˜šœ=™=Lšœ˜—šœ<™˜^Lšœ)˜)—L˜šœ$™$š¡œ&¡œ˜.Lšœ/˜/š¡œ1¡œ¡˜QLš¡œ¡œ˜@Lš¡œ˜—Lšœ˜Lšœ˜L˜——Lšœ˜L˜š¡œ¡œ˜7L™˜—L˜š¡˜šœ˜Lšœ†™†——L˜L˜—š£ œ¡œ˜&Lšœ|™|L™?Lšœ˜Lšœ˜š¡œ¡˜˜%Lšœ&˜&šœ0™0Lšœ(˜(—šœN™NLšœ˜—šœ5™5Lš¡œ"¡œ¡œ˜@—L˜—Lš¡œ˜—Lšœ˜Lšœ¢˜3Lšœ˜L˜—š£œ¡œ.˜;Lšœ'¡œ>™iLšœ˜šœ˜Lšœ˜š¡œ¡˜ Lš¡œ ˜Lš¡œ%˜)—Lšœ ˜ L˜ L˜—Lšœ˜L˜L˜—š£œ¡œ ¡œ¡œ˜:LšœÐ™ÐLšœ˜š¡œ ¡œ¡œ˜Lšœ˜Lšœ˜Lšœ˜L˜—L˜L˜—š £ œ¡œ ¡œ¡œ¡ œ˜JLšœ‘™‘Lšœ˜š¡œ¡œ¡œ˜Lšœ˜Lšœ˜š¡œ ˜ š¡œ ¡˜Lšœ)™)—š¡œ˜Lšœ¢"˜9Lšœ˜š¡˜L˜Lš¡œ ¡œ¡œ¢˜-š¡œ¡œ˜@Lšœ"™"—L˜ Lš¡œ˜—š¡œ ¡œ˜"Lšœ*™*—Lšœ˜L˜——Lšœ ¡œ˜Lšœ ¡œ¢0˜BL˜—L˜L˜—š£ œ¡œ˜ Lšœy™yš¡œ¡œ¡œ˜%Lšœ˜š¡œ¡œ¡œ˜Lšœ˜š¡œ¡œ¡œ˜Lšœ˜š¡˜Lšœ˜š¡œ¡œ˜š¡œ˜ š¡œ ¡˜Lšœ#™#—š¡œ˜š¡œ ¡œ˜Lšœ'™'—Lšœ˜L˜——Lšœ¡œ˜Lšœ ¡œ¢0˜?Lš¡œ˜L˜—L˜Lš¡œ ¡œ¡œ˜Lš¡œ˜—L˜—Lšœ˜L˜—L˜—L˜L˜—š£ œ¡œ˜!LšœÊ™Êš¡œ¡œ¡˜(Lšœ˜Lš¡œ ¡œ¡œ¡œ˜š¡œ¡œ ˜=Lšœ»™»—Lšœ ¢ ˜Lš¡œ˜—L˜L˜—š£ œ¡œ¡ œ˜,LšœV™VLš¡œ3¡œ™:Lšœ#¢ ˜/L˜L˜——™Aš£œ¡œ¡ œ˜$Lšœ’™’š¡œ¡œ!¡˜,Lšœ4™4š¡œ ¡œ¡˜Lšœ ¢ ˜Lš¡œ˜—Lš¡œ˜—L˜L˜—š£œ¡œ¢ œ˜$LšœÎ™ÎLš¡œ¡œ¡œ™@Lšœ'¢ ˜2L˜L˜—š£œ¡œ¡ œ˜8LšœÅ™ÅL˜Lšœ™Lšœ™L™Lšœ™š¡œ¡œ¡™*Lšœ/™/Lš¡œ™L™—Lšœ.™.š¡œ-¡™3Lšœ+™+Lšœ™—Lš¡œ˜L˜—š£œ¡œ¢ œ˜6Lšœ™L™Lšœ™š¡œ¡œ¡™*Lšœ.™.Lš¡œ™—Lšœ *œ<£œJ™ÃL˜——šœ=™=š£œ¡œ¡ œ˜5Lšœ½™½Lšœ¡œ˜š¡œ&¡œ˜.LšœÌ™ÌLšœ*˜*š¡œ¡œ¡œ˜L™Pš¡œ ¡˜˜šœ$™$Lšœ%˜%—šœK™KLšœ˜—šœh™hLš¡œ'¡œ¡œ˜E—L˜—Lšœ¡œ˜Lš¡œ¡œ¢§%¢˜@—L˜—Lšœ˜L˜—Lšœ˜L˜—š£œ¡œ˜Lšœÿ™ÿLšœJ™JL˜%Lšœ¡œ¡œ˜š¡œ¡ œ¡œ/¡˜UL™JL˜1Lš¡œ¡œ¡œ¡œ˜š¡œ2¢¡˜8L™4™2š¡˜Lšœ˜Lšœ¡œ˜Lšœ˜™Bš¡˜š¡œ¡˜˜ Lšœ/˜/Lš¡œ¡œ,˜GL˜—˜Lš¡œ¡œ¡œ¢ ˜GL˜—Lš¡œ¡œ˜—Lš¡œ%¡œ¡œ˜1Lš¡œ˜——™:Lš¡œ¡œ¡œ¡œ˜)—™_Lšœ˜Lšœ˜Lš¡œ ¡œ¡œ˜*—š¡˜Lšœ¡œ˜—Lš¡œ˜——Lš¡œ¡œ¡œ˜#Lš¡œ˜—š¡˜Lšœ¡œ˜—Lš¡œ˜—Lš¡œ¡œ˜)Lšœ˜—L˜L˜š£œ¡œ˜šœ¢™¢Ošœº™ºO™—Lšœ¡œ¡œ˜Lšœ(˜(Lšœ ˜ šœ¡œ˜Lšœi™i—š¡œ¡ œ¡œ/¡˜UL˜*š¡œ¡œ¡œ˜š¡œ,¡˜1Lšœ¡œ¢§(¢˜GLšœ*˜*˜š¡˜L™Lšœ˜š¡œ¡œ˜ Lšœ%˜%Lš¡œ¡œ¡œ˜4L˜—Lšœ˜Lš¡œ¡œ¡œ¡œ˜(Lš ¡œ¡œ¡œ¡œ¡œ˜VLš¡œ˜—š¡œ&¡˜,Lšœ™š¡œ"¡œ ¡˜9š¡œ ¡˜Lš œ¡œ¡œ¡œ¡œ˜Dšœ ˜ Lšœ"˜"š¡œ¡œ˜Lšœ ˜ Lšœ˜Lš¡œ¡œ¡œ˜(Lšœ˜—L˜—Lš¡œ˜—Lš¡œ˜——Lšœ4™4Lšœ˜Lšœ˜š¡œ¡œ¡œ˜-L™F—š¡œ¡œ˜LšœÇ™ÇLšœ˜Lš¡œ¡œ¡œ¡œ˜(Lšœ˜—š¡œ˜Lšœ©™©Lšœ˜—L˜—Lš¡œ¡œ¡œ˜Lš¡œ˜—Lš¡œ ¡œ˜L˜—Lš¡œ˜—Lš¡œ¡œ˜)Lšœ˜—˜L˜—š£ œ¡œ¡ œ˜4Lšœ»™»Lšœ&˜&Lšœ1˜1Lš¡œ!¡œ!˜HLšœ˜L˜L˜—š£œ¡œ¡ œ˜8LšœÆ™ÆLšœ*˜*Lšœ˜L˜L˜—š£ œ¡œ,¡ œ˜ILšœŸ™Ÿš¡œ¡œ¡œ˜Lšœ˜š¡œ¡˜ Lš¡œ˜Lš¡œ3˜7—Lšœ˜Lšœ˜—L˜L˜—š£ œ¡œ,¡ œ˜ILšœê™êš¡œ¡œ¡œ˜Lšœ%™%Lšœ˜š¡œ¡œ¡œ˜L˜š¡˜L˜š¡œ ¡œ˜š¡œ˜ š¡œ ¡˜Lšœ#™#—š¡œ˜š¡œ ¡œ˜"Lšœ'™'—Lšœ˜Lšœ˜——Lšœ ¡œ˜ Lš¡œ˜L˜—L˜Lš¡œ ¡œ¡œ˜Lš¡œ˜—L˜—L˜—L˜——™™Lšœ¡œ¢ ˜;L˜š £ œ¡œ"¡œ#¡œ ¡œ¢œ˜ˆLšœ¡œ¡œ ™CL™Pš£œ¡œ¡œ˜$Lš¡œ¡œ¡œ˜Lš¡œ¡œ˜-—L˜L˜L˜—š£œ¡ œ5˜UL™0Lšœ¡œ˜ L˜L˜—š £œ¡œ&¡œ'¡œ ¡œ¢œ˜’Lšœ¡œ¡œ ™CL™Pš£œ¡œ¡œ˜$Lš¡œ¡œ¡œ˜Lš¡œ¡œ˜-—L˜L˜L˜—š£œ¡ œ7˜YL™0Lšœ¡œ˜ L˜L˜—š£ œ¡œ¡œ¡œ¡œ¡œ¡œ ¡œ¡œ ¡œ¢œ˜tLšœ¡œ¡œ ™CL™Qš£œ¡œ¡œ˜$Lš¡œ¡œ¡œ˜Lš¡œ¡œ˜-—L˜L˜L˜—š£œ¡œ¡œ&¡œ¡œ¡œ¡œ¡œ˜dL™0Lšœ ˜ L˜L˜——™Lšœ¡œ¢ ˜7Lšœ1¢ ˜Lšœ¡œ˜ Lš¡œ¡œ¡œ¢§˜8Lšœ"˜"L˜L˜—Lš£œ¡œ˜š£ œ¡œ¡œ ˜5Lšœ¡œ˜L˜L˜—Lšœ ¡œ˜Lšœ ¡œ˜Lšœ ¡œ˜'J˜ L˜š£œ¡œ˜Lšœ¡œ˜š¡œ¡˜Lšœ ˜ L˜Lš¡œ˜—š¡œ¡˜š¡œ¡˜Lšœ ˜ L˜Lš¡œ˜—Lšœ¡œ˜Lšœ¡œ˜Lš¡œ˜—L˜L˜—š£œ¡œ˜Lšœ¡œ˜š¡œ¡˜Lšœ ˜ L˜Lš¡œ˜—š¡œ¡˜š¡œ¡˜Lšœ ˜ L˜Lš¡œ˜—Lšœ¡œ˜Lšœ¡œ˜Lš¡œ˜—L˜——™ š£ œ¡œ˜L˜——™L™/L™Lšœ¡œ˜Lšœ ¡œ¡œ ˜1L˜Lš£œ¡œ¡œ"¡œ˜CL˜š £œ¡œ¡œ¡œ¡œ˜ALšœ™Lšœ¡œ ˜š¡œ¡œ"˜