<> <> <> <> <> <> <<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.>> <> <<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 >> <<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.>> <> <<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.>> <> <<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.>> <> <<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.>> <<>> 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; <<... 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.>> emergencyLimit: Word _ emergencyLimit; <<... 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.>> metaLock: Processor _ NIL; <<... 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>> schedulerLock: Processor _ NIL; <<... 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.>> 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] = { <<... 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.>> <> <> <<-- CHH: PrincOps ProcessImpl.Fork waits until a process is available. Do we really want to change the semantics? March 12, 1987>> < maxStackRets THEN nRets ELSE 0)+(IF nArgs > maxStackArgs THEN nArgs ELSE 0) words. >> <> <<(the original argument storage belongs to the caller)>> <> { -- 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--] ~ { <> < maxStackRets THEN >> <<{ retRecord _ argPtr^;>> <> <<};>> <> <> <> << >> <> <> <> <> <> <> <<}>> <<>> <> <<>> <> <<>> NotYetImplemented[]; }; Join: PUBLIC PROC [secureProcess: SecureProcess, retPtr: WordSeq] = { <<... joins the specified process, which waits for the process to complete, then copies the return values to the address given by retPtr.>> <> <> <> <> <> <<>> { -- 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 { <<... 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.>> <> <> DisableInterrupts[]; CurrentProcess[].when _ when; MarkFrame[]; <> ProcessSwitch[nextState, nextProcess]; EnableInterrupts[]; -- SIM only. RDI: happens automatically. }; Wait: PUBLIC PROC [cond: Condition, lock: MonitorLock] = { <<... 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.>> <> 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] = { <<... 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.>> <> 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] = { <<... 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.>> best: Process = Dequeue[@cond.queue]; IF best # NIL THEN MakeReady[best]; <> }; Broadcast: PUBLIC PROC [cond: Condition] = { <<... 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.>> 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] = { <<... 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.>> 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] = { <<... 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?>> 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 = { <<... tests for a requested abort.>> <> self: Process = CurrentProcess[]; IF self.abortState = requested THEN { self.abortState _ none; ERROR ABORTED }; }; RequestAbort: PUBLIC PROC [process: Process] = { <<... requests the given process to abort itself.>> <> SELECT process.abortState FROM none => { process.abortState _ requested; MakeReady[process]; RaiseReschedule[]; }; inhibited => process.abortState _ delayed; ENDCASE; }; SetPriority: PUBLIC SAFE PROC [p: Priority] ~ TRUSTED { <<... 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.>> 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 <<[requestKind: RequestKind]>> ~ 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 = { <<... 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).>> <= 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).>> 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 = { <<... 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).>> 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 = { <<... 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.>> 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 = { <<... 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.>> 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] = { <<... for each process P in the page fault with startPage >> <> 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] = { <<... 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).>> <<>> 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] ~ { <<... place process on the ready queue, if it's currently waiting. Also remove process from the timeout queue if it is there.>> <> 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[]] = { <<... places the process on the queue in FIFO order. Priority processing is the responsibility of Dequeue.>> 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] = { <<... 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.>> 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-- { <<... 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.>> 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] = { <<... dequeues the current process from the given queue. This operation has no effect if the process was not in the 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] = { <<... 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.>> 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-- { <<... releases ownership of the queue. Assumes that the current process owns the queue.>> <> SimStoreNilInProcess[ptr~@q.busy]; -- SIM only. }; <> AcquireMetaLock: PROC = --INLINE-- { <<... 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.>> WHILE NOT CStoreProcessor[ptr: @metaLock] DO <> WHILE metaLock # NIL DO SimYield[]; -- SIM only ENDLOOP; ENDLOOP; }; ReleaseMetaLock: PROC = --INLINE-- { <<... 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.>> <> SimStoreNilInProcessor[ptr~@metaLock]; -- SIM only }; SaveProcessState: PROC [process: Process] = --INLINE-- { <<... 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.>> <> <> <<>> <> <> <> <> <<>> <> <> <> <> NULL }; RestoreProcess: PROC [process: Process] = --INLINE-- { <<... 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.>> <<>> <> <> <> <> <> }; <> DelicateNotify: PROC [cond: Condition] = --INLINE-- { <<... 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.>> 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 ~ { <<... 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.>> <> self: Processor ~ CurrentProcessor[]; needReschedule: BOOL _ FALSE; FOR pProcess: Priority DECREASING IN (lowestRunningPriority..highestReadyPriority] DO <<(FOR each schedulable ready process priority pProcess, decreasing, DO ...)>> tailProcess: Process ~ readyQueueArray[pProcess]; IF tailProcess = NIL THEN LOOP; FOR process: Process _ tailProcess.meta, process.meta DO <<(FOR each ready process at priority pProcess 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 = { <<... 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.>> <> <<>> 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-- { <<... 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.>> priority: Priority = process.priority; EnqueueMeta[@readyQueueArray[priority], process]; IF priority > highestReadyPriority THEN highestReadyPriority _ priority; process.state _ ready; }; EnqueuePageFault: PROC [process: Process] = --INLINE-- { <<... 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.>> EnqueueMeta[@pageFaultMetaQueue, process]; process.state _ waitingPage; }; EnqueueMeta: PROC [metaQueue: MetaQueue, process: Process] = --INLINE-- { <<... 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.>> 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-- { <<... 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.>> 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 -- { <<... atomically performs {IF (stored _ ptr^ = old) THEN ptr^ _ new}.>> <> 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 -- { <<... atomically performs {IF (stored _ ptr^ = old) THEN ptr^ _ new}.>> <> 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 -- { <<... atomically performs {IF (stored _ ptr^ = old) THEN ptr^ _ new}.>> <> 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 [] = { <<... inhibits interrupts (must be a procedure call for RDI)>> SimThisProcessor[].sim.interruptsEnabled _ FALSE; -- Change in RDI }; EnableInterrupts: PROC [] = { <<... enables interrupts (must be a procedure call for RDI)>> SimThisProcessor[].sim.interruptsEnabled _ TRUE; -- Change in RDI }; ReadAndClearDeviceRequests: ENTRY PROC [lock: SimLock _ simIOLock] RETURNS [rw: RequestWord] ~ { <<... 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.>> <> 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 -- { <<... Determines whether or not device requests are pending, but does not alter them. This must agree with ReadAndClearDeviceRequests.>> <> ENABLE UNWIND => NULL; FOR k: RequestKind IN RequestKind DO IF simIORequestWord[k] THEN RETURN [TRUE]; ENDLOOP; RETURN [FALSE]; }; RaiseReschedule: PROC = -- MACHINE CODE -- { <<... raises the Reschedule interrupt, which, if disabled, will occur when it becomes enabled again.>> <> 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 -- { <<... fetches a word from the given special EU register.>> NotYetImplemented[noOp]; }; EUStoreSpecial: PROC [which: EUstateIndex, x: Word] = -- MACHINE CODE -- { <<... stores a word into the given special EU register.>> NotYetImplemented[noOp]; }; SaveStack: PROC = --INLINE-- { <<... 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.>> NotYetImplemented[noOp]; }; MarkFrame: PROC = --INLINE-- -- MACHINE CODE -- { <<... 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.>> NotYetImplemented[noOp]; }; <> Init: PROC [indexPtr: LONG POINTER TO CARD] ~ { <<... 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. >> 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 { <> <<(Do you suppose this code will ever be exercised on a real system? - ajd)>> 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 <<[requestKind: RequestKind]>> <> ~ 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 [] ~ { <<... create all the process objects. On entry we assume interrupts are disabled and the metaLock is held.>> <> 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 [] ~ { <<... 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.>> <> <> 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-- { <<... get a process object from free process list. On entry we require that interrupts are disabled and the metalock is held.>> 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] ~ { <<... get a process object from free process list.>> <> 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-- { <<... insert p into the ring of Processor objects. On entry we require that interrupts are disabled and the metaLock is held.>> <> 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.