〈os.java〉=/** A simple operating system without virtual storage and with pre-emptive scheduling. */ import java.util.Arrays import java.util.List import java.util.ArrayList class os implements OperatingSystem /** Cancel any outstanding countdown-timer interrupts. */ private void clearQuantum() setQuantum(0) 〈Handle a system-call interrupt〉 /** Treat the running process as if it made an exit system call. */ private void exitRunningProcess() storageBlocks.deallocate( runningProcess.startAddress(), programBlockCount[runningProcess.programIndex]) processQueue.remove(runningProcess) clearQuantum() if processQueue.processCount() ≡ 0 hw.store(Hardware.Address.haltRegister, 0) else runProcess(processQueue.readyProcess()) /** Handle an interrupt. it: The interrupt to handle. */ public void interrupt(Hardware.Interrupt it) switch it case countdown yieldRunningProcess() break 〈Handle disk interrupt〉 case illegalInstruction case invalidAddress exitRunningProcess() break case reboot diskInterruptHandler = new DiskIndexInterruptHandler(hw) diskInterruptHandler.startRequest() runProcess(processQueue.readyProcess()) break case systemCall doSystemCall(hw.fetch(0)) break default SystemSim.panic("Oh no! " + it + " unhandled!") /** Create an instance of this operating system. hw: The hardware on which this os will be running. */ public os(Hardware hw) this.hw = hw diskInterruptHandler = new UnexpectedDiskInterruptHandler(hw) processQueue = new ProcessQueue() /** Run a process loaded into primary store. process: The process to run. */ private void runProcess(ProcessDescriptor process) assert runningProcess ≠ process runningProcess = process process.restoreRegisters(hw) if processQueue.readyProcessCount() > 1 setQuantum(quantum) /** Set the delay until the next countdown-timer interrupt. quantum: The number of ticks until the next countdown-timer interrupt. If 0, cancel the next countdown-timer interrupt. */ private void setQuantum(int quantum) assert quantum > -1 hw.store(Hardware.Address.countdownRegister, quantum) /** Submit a request to load a program. pi: The index of the program to load. sa: The primary-store start address at which the program is to be loaded. requestor: A reference to the process making the request. */ private void submitProgramLoad(int pi, int sa, ProcessDescriptor requestor) diskRequestQueue.add( new ProgramLoadInterruptHandler(hw, pi, sa, requestor)) if diskRequestQueue.size() ≡ 1 diskInterruptHandler = diskRequestQueue.get(0) diskInterruptHandler.startRequest() /** Suspend the running process, and schedule the next process to run. */ private void suspendRunningProcess() runningProcess.saveRegisters(hw) processQueue.suspendReadyProcess() clearQuantum() runProcess(processQueue.readyProcess()) /** If there’s a process to yield to, suspend the running process and run the next process, and hang the formally running process back on the ready queue. */ private void yieldRunningProcess() if processQueue.readyProcessCount() > 1 final ProcessDescriptor pd = runningProcess // If there are exactly two ready processes, runProcess() (via // suspendRunningProcess()) will only see one, and not set the countdown // timer. Set it here. suspendRunningProcess() setQuantum(quantum) processQueue.resumeProcess(pd) 〈The disk-index interrupt handler〉 〈The program-load interrupt handler〉 〈The unexpected disk-interrupt handler〉 〈Operating system instance variables〉 /** A queue of pending disk requests. */ private final List<DiskInterruptHandler> diskRequestQueue = new ArrayList<DiskInterruptHandler>() /** A reference to the hardware on which this os runs. */ private final Hardware hw /** The ith program has programBlockCount[i] blocks. */ private int programBlockCount [] /** The ith program’s first block on the disk has index programFirstBlock[i]. */ private int programFirstBlock [] /** The processes ready to run. */ private final ProcessQueue processQueue /** The quantum size in ticks. */ private final int quantum = 10 /** The running process; if nil, the idle process is running (however, if the idle process is running, runningProcess may not be nil). */ private ProcessDescriptor runningProcess /** A reference to the user-space free-segment allocator. */ private StorageBlocks storageBlocks = new StorageBlocks()
Definesos,os.java(links are to index).
〈Handle a system-call interrupt〉= (←U)/** Handle a system-call interrupt sc: The system-call identifier. */ private void doSystemCall(int sc) switch sc 〈exec system-call switch case〉 〈exit system-call switch case〉 〈get-slot system-call switch case〉 〈put-slot system-call switch case〉 〈yield system-call switch case〉 〈default system-call switch case〉
DefinesdoSystemCall(links are to index).
There is a choice to be made when implementing the exec system call: if a new process is supposed to run a program already in user space, should the new process refer to the program already in store, or should it read in another copy of the program?
The documentation is unclear on this choice, apart
from the indication that the exec system call could fail because there are
no resources. However, that reference is ambiguous: there could be no
resources (primary store) because there are too many different programs being
run, or too many copies of the same program being run.
〈exec system-call switch case〉= (←U)case OperatingSystem.SystemCall.exec // Check for a legal program identifier. final int pno = hw.fetch(1) if (pno < 0) ∨ (pno ≥ programBlockCount.length) hw.store(0, Hardware.Status.badPid) return // Allocate some user space for the new program. final int startAddress = storageBlocks.allocate(programBlockCount[pno]) if startAddress < 0 hw.store(0, Hardware.Status.noResource) return // Start the program load and suspend the parent process making the exec // system call while the child process is loading. submitProgramLoad(pno, startAddress, runningProcess) suspendRunningProcess() break
〈exit system-call switch case〉= (←U)case OperatingSystem.SystemCall.exit exitRunningProcess() break
A get-slot system call succeeds if a value has been written to the calling process’s slot since the last get-slot call, or at all, and fails otherwise.
〈get-slot system-call switch case〉= (←U)case OperatingSystem.SystemCall.getSlot final ProcessDescriptor.SlotResult sr = runningProcess.readSlot() if sr.slotValueWriter < 0 hw.store(0, Hardware.Status.noResource) else hw.store(0, Hardware.Status.ok) hw.store(1, sr.slotValue) hw.store(2, sr.slotValueWriter) break
A put-slot system call succeeds if the receiving process’s slot is empty and fails otherwise.
〈put-slot system-call switch case〉= (←U)case OperatingSystem.SystemCall.putSlot final ProcessDescriptor receiver = processQueue.process(hw.fetch(1)) final int value = hw.fetch(2) if null ≡ receiver hw.store(0, Hardware.Status.badPid) else hw.store(0, receiver.writeSlot(runningProcess.processID, value) ? Hardware.Status.ok : Hardware.Status.noResource) break
Were it not for that cursed return code, the yield system call would be as simple as the exit system call.
〈yield system-call switch case〉= (←U)case OperatingSystem.SystemCall.yield hw.store(0, Hardware.Status.ok) yieldRunningProcess() break
The default system-call switch case raises a quandry. Either the system-call
code sc is illegal, or it’s a legal system-call code and unhandled. If
it’s legal, it’ll string convert to a recognizable system-call name.
〈default system-call switch case〉= (←U)default final String s = OperatingSystem.SystemCall.toString(sc) if s.charAt(0) ≡ '[' exitRunningProcess() else SystemSim.panic( "Oh no! " + s + " (= " + sc + ") is an unhandled system call!")
Each of the second and third reasons can be further divided into
- The disk-index block has been read.
- A block from the first program to run has been read.
- A block from a program specified in an exec system call run has been read.
- A program block that’s not the last block needed has been read.
- The last program block needed has been read.
In addition, thinking ahead, later programming assignments are going to add more reasons for causing disk interrupts.
Each of these reasons requires interrupt handling different from the interrupt handling required by the other reasons. Without careful management, keeping track of the differences could get messy fast.
Fortunately, object-oriented design gives us a technique for carefully managing the different ways of handling disk interrupts: define an abstract class that encapsulates the common activities needed by all disk-interrupt handlers, and lets each handler establish its own interrupt-handling requirements.
〈Disk-interrupt handler abstract class〉= (U→)abstract class DiskInterruptHandler /** The method called to handle an interrupt. */ abstract void handleInterrupt() 〈Disk-interrupt handler common methods〉 〈Disk-interrupt handler instance variables〉
DefinesDiskInterruptHandler(links are to index).
A particular disk-interrupt handler defines a child of
DiskInterruptHandler, filling in the handleInterrupt() method with the
code needed to handle the specific disk interrupt.
DiskInterruptHandler abstract class, the operating system can
define an instance variable to represent the action to be taken when the next
disk interrupt arrives.
〈Operating system instance variables〉= (←U)/** What to do when a disk interrupt comes in. */ private DiskInterruptHandler diskInterruptHandler
DefinesdiskInterruptHandler(links are to index).
When a disk interrupt arrives, the operating system calls handleInterrupt()
on the currently defined disk-interrupt handler to deal with it.
〈Handle disk interrupt〉= (←U)case disk diskInterruptHandler.handleInterrupt() break
As an example of defining a new disk-interrupt handler, consider the simplest possible interrupt handler: the one for handling unexpected interrupts. Because unexpected disk interrupts should never occur, the only thing an operating system can do when it receives one is panic.
〈The unexpected disk-interrupt handler〉= (←U)/** Handle an unexpected disk interrupt. */ private class UnexpectedDiskInterruptHandler extends DiskInterruptHandler UnexpectedDiskInterruptHandler(PrimaryStore ps) super(ps, 0, 0, 0) public void handleInterrupt() SystemSim.panic("Unexpected disk interrupt received.")
DefinesUnexpectedDiskInterruptHandler(links are to index).
〈The program-load interrupt handler〉= (←U)/** Handle a disk interrupt from a program load. */ private class ProgramLoadInterruptHandler extends DiskInterruptHandler /** Handle a disk interrupt from a request to load a program block. */ public void handleInterrupt() checkDiskStatus() if loadComplete() // The last progrm block just got read. Turn the program into a // process, and hang it on the ready queue. final ProcessDescriptor newProcess = new ProcessDescriptor( programIndex, startAddress, startAddress + Hardware.Disk.blockSize*programBlockCount[programIndex]) processQueue.add(newProcess) // If this load request came from a process via exec rather than the // initial program load, copy the requestor’s non-system registers to // the new process, and resume the suspended requestor, feeding it the // results of the exec system call. if requestingProcess ≠ null newProcess.copyRegisters(requestingProcess) newProcess.registerSet(1, requestingProcess.processID) processQueue.resumeProcess(requestingProcess) requestingProcess.registerSet(0, Hardware.Status.ok) requestingProcess.registerSet(1, newProcess.processID) // If there are three process on the ready queue, there was one // before the disk interrupt, and it was running with no // countdown timer. Re-enable the countdown timer. if processQueue.readyProcessCount() ≡ 3 setQuantum(quantum) // If the idle proces is running, replace it with a ready process. if processQueue.isIdleProcess(runningProcess) runProcess(processQueue.readyProcess()) // Remove this request from the head of the disk-request queue. If // there’s another request pending, start it. Otherwise, treat a disk // interrupt as unexpected. diskRequestQueue.remove(0) if !diskRequestQueue.isEmpty() diskInterruptHandler = diskRequestQueue.get(0) diskInterruptHandler.startRequest() else diskInterruptHandler = new UnexpectedDiskInterruptHandler(hw) else // Read in the program’s next block. diskBlockLoad() /** Create a new program-load interrupt handler. ps: A reference to the hardware. pi: The index of the program to load. sa: The starting (lowest, leftmost) primary-store address of the loaded program. requestor: The process making the load request. */ ProgramLoadInterruptHandler( PrimaryStore ps, int pi, int sa, ProcessDescriptor requestor) super(ps, programFirstBlock[pi], sa, programBlockCount[pi]) requestingProcess = requestor programIndex = pi /** The disk-index block index of the program being loaded. */ private final int programIndex /** A reference to the descriptor for the process requestion this program load. */ final ProcessDescriptor requestingProcess
DefinesProgramLoadInterruptHandler(links are to index).
The disk-index interrupt handler is essentially unchanged from the first assignment and will not be repeated here.
〈The disk-index interrupt handler〉= (←U)/** Handle the interrupt that comes back from the disk-read request for the disk-index block. */ private class DiskIndexInterruptHandler extends DiskInterruptHandler /** Create a handler to read the index block from the disk. ps: A reference to primary store. */ DiskIndexInterruptHandler(PrimaryStore ps) super(ps, 0, Hardware.Address.userBase, 1) /** Handle the interrupt marking the end of the index-block read. */ public void handleInterrupt() checkDiskStatus() // Copy the non-zero entries in the index block into an array of // size-in-block values for programs. programBlockCount = new int [Hardware.Disk.blockSize] for int i = 0; i < Hardware.Disk.blockSize; i++ final int r = primaryStore.fetch(Hardware.Address.userBase + i) if r < 0 SystemSim.panic("disk index has a negative block count.") if r ≥ Hardware.Disk.blockCount SystemSim.panic( "disk index has a block count greater than the disk size.\n" + "disk index " + i + " is " + r + ".") if r ≡ 0 programBlockCount = Arrays.copyOf(programBlockCount, i) break programBlockCount[i] = r // If there are no programs, quit. if programBlockCount.length ≡ 0 primaryStore.store(Hardware.Address.haltRegister, 0) // Compute the first-block indices for the programs on the disk. programFirstBlock = new int [programBlockCount.length] programFirstBlock[0] = 1 for int i = 0; i < programBlockCount.length - 1; i++ programFirstBlock[i + 1] = programFirstBlock[i] + programBlockCount[i] // Allocate space for the first process. final int startAddress = storageBlocks.allocate(programBlockCount[0]) if startAddress < 0 SystemSim.panic("Initial program is larger than user space.") // Issue a load request for the first program. submitProgramLoad(0, startAddress, null)
DefinesDiskIndexInterruptHandler(links are to index).
〈Disk-interrupt handler common methods〉= (←U)/** Check the status of the most recent disk command, dying if it’s not ok. */ protected void checkDiskStatus() final int r = primaryStore.fetch(Hardware.Address.diskStatusRegister) if Hardware.Status.ok ≠ r SystemSim.panic( "disk operation status is " + Hardware.Status.toString(r)) /** Read a disk block into primary store. */ protected void diskBlockLoad() assert blockCount > 0 primaryStore.store( Hardware.Address.diskBlockRegister, firstBlock + --blockCount) primaryStore.store( Hardware.Address.diskAddressRegister, startAddress + Hardware.Disk.blockSize*blockCount) primaryStore.store( Hardware.Address.diskCommandRegister, Hardware.Disk.readCommand) /** Create an instance of a disk interrupt handler. ps: A reference to primary storage. fbi: The index of the first block in the program. sa: The primary-store address at which the program will be loaded. bc: The program size in disk blocks. */ protected DiskInterruptHandler(PrimaryStore ps, int fbi, int sa, int bc) primaryStore = ps firstBlock = fbi startAddress = sa blockCount = bc /** Determine if this program load is done. Returns: True iff there are no more blocks to load. */ protected boolean loadComplete() return blockCount ≡ 0 /** Start the disk requests to read the program. */ protected void startRequest() diskBlockLoad()
〈DiskInterruptHandler.java〉=/** An abstract disk-interrupt handler. */ 〈Disk-interrupt handler abstract class〉
DefinesDiskInterruptHandler,DiskInterruptHandler.java(links are to index).
〈Disk-interrupt handler instance variables〉= (←U)/** The number of blocks read from the disk. */ private int blockCount /** The index of the program’s first block. */ private final int firstBlock /** A reference to the hardware’s primary store. */ protected final PrimaryStore primaryStore /** The primary-store address into which the first word of the disk block will be read. */ protected final int startAddress
〈ProcessDescriptor.java〉=/** Describe a process’s resources and state. */ class ProcessDescriptor /** Copy a process’s non-system registers to this descriptor. pd: A reference to the process descriptor holding the registers to copy. */ void copyRegisters(ProcessDescriptor pd) for int i = 0; i < 11; i++ registers[i] = pd.registers[i] /** Represent a process. pi: The disk-block index of the program associated with this process. start: The process’s lowest (leftmost) address. end: One past the process’s highest (rightmost) address. */ ProcessDescriptor(int pi, int start, int end) if start ≥ end SystemSim.panic( "Program segment has start (" + start + ") ≥ end (" + end + ").") registers[Hardware.Address.baseRegister] = start registers[Hardware.Address.topRegister] = end registers[Hardware.Address.PCRegister] = start programIndex = pi processID = nextProcessID++ slotValueWriter = -1 /** Return the value stored in a slot, or not. Returns: A pair containing the slot writer’s process id and the value written. If the process id is negative, the slot is empty and the value is undefined. */ SlotResult readSlot() final SlotResult sr = new SlotResult(slotValueWriter, slotValue) slotValueWriter = -1 return sr /** Store a value in this process’s saved register set. registerIndex: The index of the register into which the value will be stored. value: The value to store. */ void registerSet(int registerIndex, int value) registers[registerIndex] = value /** Move the process’s register set to the hardware registers. */ void restoreRegisters(PrimaryStore ps) for int i = 0; i < Hardware.Address.registerSetSize; i++ ps.store(i, registers[i]) /** Make a copy of the contents of the hardware’s registers. */ void saveRegisters(PrimaryStore ps) for int i = 0; i < Hardware.Address.registerSetSize; i++ registers[i] = ps.fetch(i) /** Get this process’s base (starting, lowest, leftmost) address. Returns: This process’s base address. */ int startAddress() return registers[Hardware.Address.baseRegister] /** Write a value into this process descriptor’s slot, assuming the slot doesn’t already contain a value. wid: The slot writer’s process id. sv: The value to write into the slot. Returns: True if the value was written into the slot, false if the value was not written into the slot because the slot’s already got a value. */ boolean writeSlot(int wid, int sv) if slotValueWriter < 0 slotValueWriter = wid slotValue = sv return true return false /** The result of calling readSlot(). */ static class SlotResult final int slotValue final int slotValueWriter SlotResult(int wid, int v) slotValue = v slotValueWriter = wid /** The next id to be assigned to a process. */ static private int nextProcessID = 1024 /** A place to save registers. */ private final int registers[] = new int [Hardware.Address.registerSetSize] /** This process’s id. */ final int processID /** The disk-block index of the program associated with this process. */ final int programIndex /** The value stored in the slot. If there’s no writer, the value stored here is undefined. */ private int slotValue /** The slot-value writer’s process id. If negative, there’s no writer and the slot value is undefined. */ private int slotValueWriter
DefinesProcessDescriptor,ProcessDescriptor.java(links are to index).
〈ProcessQueue.java〉=/** A straightforward round-robin process queue. */ import java.util.ArrayList import java.util.Set import java.util.HashSet class ProcessQueue /** Add a process to the queue tail. p: The a reference to the process to add. */ void add(ProcessDescriptor p) readyQueue.add(p) /** Determine if a process is the idle process. p: The process of interest. Returns: True iff the given process is the idle process. */ boolean isIdleProcess(ProcessDescriptor p) return p ≡ idleProcess /** Find a process given its id. pid: The id of the process of interest. Returns: A reference to the process having the given descriptor, or null if there’s no such process. */ ProcessDescriptor process(int pid) for ProcessDescriptor pd : readyQueue if pd.processID ≡ pid return pd for ProcessDescriptor pd : suspendedProcesses if pd.processID ≡ pid return pd return null /** Find the number of processes available, independent of process state, absent the idle process. Returns: The number avaialble processes which are not the idle process. */ int processCount() return readyQueue.size() + suspendedProcesses.size() /** Return a ready-to-run process. Returns: The head of the run queue or the idle process if the run queue’s empty. */ ProcessDescriptor readyProcess() return readyQueue.isEmpty() ? idleProcess : readyQueue.get(0) /** Find the number of ready processes. Returns: The number of ready processes, absent the idle process. */ int readyProcessCount() return readyQueue.size() /** Remove a process from the queue. pd: A reference to the descriptor of the process to remove. */ void remove(ProcessDescriptor pd) if pd ≡ idleProcess SystemSim.panic("Trying to remove the idle process.") if !readyQueue.remove(pd) SystemSim.panic("Removing a process that’s not on the process queue.") /** Move a process from the suspended set to the ready queue. p: A reference to the suspended process. */ void resumeProcess(ProcessDescriptor p) assert !suspendedProcesses.isEmpty() if !suspendedProcesses.remove(p) SystemSim.panic("Trying to resume a process that’s not suspended.") readyQueue.add(p) /** Suspend the ready process (the process at the run-queue head). */ void suspendReadyProcess() assert !readyQueue.isEmpty() suspendedProcesses.add(readyQueue.remove(0)) /** The idle process. */ private final ProcessDescriptor idleProcess = new ProcessDescriptor( -1, Hardware.Address.idleStart, Hardware.Address.idleEnd) /** The processes ready to run, not counting the idle process. */ private final ArrayList<ProcessDescriptor> readyQueue = new ArrayList<ProcessDescriptor>() /** The processes not ready to run because they’ve been suspended for various reasons (waiting for a disk operation to finish, for example). */ private final Set<ProcessDescriptor> suspendedProcesses = new HashSet<ProcessDescriptor>()
DefinesProcessQueue.java(links are to index).
〈StorageBlocks.java〉=/** A straightforward contiguous segment allocator using bit maps and first fit. */ import java.util.Arrays class StorageBlocks /** Allocate a contiguous segment of free user-space blocks. sizeInBlocks: The number of blocks in the allocated segment. Returns: The primary-store address of the first (leftmost, smallest indexed) word of the allocated segment, or -1 if it’s not possible to allocate a segment. */ int allocate(int sizeInBlocks) if sizeInBlocks < 1 SystemSim.panic("Allocating a non-positive number of blocks.") int start = blocksInUserSpace - sizeInBlocks while (start > -1) final int end = start + sizeInBlocks, i = firstValueMatching(start, end, false) if i < 0 Arrays.fill(freeBlocks, start, end, false) return Hardware.Address.userBase + start*Hardware.Disk.blockSize start = i - sizeInBlocks return -1 /** Deallocate a contiguous sequence of user-space blocks. startAddress: The starting (lowest, leftmost) primary-store address of the sequence. blockCount: The number of blocks in the sequence. */ void deallocate(int startAddress, int blockCount) assert (Hardware.Address.userBase ≤ startAddress) ∧ (startAddress ≤ Hardware.Address.userTop - Hardware.Disk.blockSize) : "start address assertion failed" assert (0 < blockCount) ∧ (blockCount ≤ Hardware.Address.userSize) : "block count assertion failed" final int startBlock = (startAddress - Hardware.Address.userBase)/Hardware.Disk.blockSize, endBlock = startBlock + blockCount assert firstValueMatching(startBlock, endBlock, true) ≡ -1 Arrays.fill(freeBlocks, startBlock, endBlock, true) /** Find the first (leftmost, smallest) matching value in a sequence. start: The first (leftmost, smallest) index in the sequence. end: One more than the last (rightmost, largest) index in the sequence. b: The value to match. Returns: The first (leftmost, smallest) index in [start, end) of a sequence value matching b, or -1 if no sequence value in [start, end) matches b. */ private int firstValueMatching(int start, int end, boolean b) assert start ≤ end for int i = start; i < end; i++ if freeBlocks[i] ≡ b return i return -1 /** Create a new storage manager. */ StorageBlocks() Arrays.fill(freeBlocks, true) /** The number of blocks in user space. */ private final static int blocksInUserSpace = Hardware.Address.userSize/Hardware.Disk.blockSize /** freeBlocks[i] is true iff user-space block i is free to be allocated. */ private final boolean freeBlocks [] = new boolean [blocksInUserSpace]
DefinesStorageBlocks.java(links are to index).
DiskInterruptHandler.java〉: D1
os.java〉: D1
ProcessDescriptor.java〉: D1
ProcessQueue.java〉: D1
StorageBlocks.java〉: D1