CMSC 412


Feb 27, 1999

Toy OS

1. Overview

We describe in pseudo-code a toy OS for a computer system consisting of cpu, memory, timer, and io device. The OS provides the services of process termination and synchronous io. Synchronous io means that when a user process makes an io request, the process is blocked until the io is complete.

The OS has the following interrupt handlers:

The system has the following (pcb) processes: The OS uses interrupt disabling to achieve atomic execution of OS handlers. That is, interrupts are disabled by the hardware action of an interrupt, and they are enabled in the return from interrupt to resume user process (by popping appropriate value into

2. Data structures

3. Macros, Functions, Interrupt Handlers

 macro UpdateRunQPCB() { 
   /* Called within an OS interupt/trap/syscall handler.
      Assumes runQ contains PCB of the process last running,
      cpu.sp points to stack top of runQ.pcb.
      Stack top has the values of ps and pc just before the interrupt.
      This pc value points to the next user instruction to execute:
         - if here by interrupt, then the next instruction after
           the interrupted instruction,
         - if here by trap, then the next instruction after
           the trapped instruction,
         - if here by syscall, then the next instruction after
           the syscall instruction,
      Interrupts disabled.
   runQ.PCB.gpr := cpu.gpr ;
   runQ.PCB.hi := ;
   runQ.PCB.lo := ;
   runQ.PCB.pc/ps := pc/ps values on top of cpu.sp stack ;
   runQ.PCB.sp := cpu.sp appropriately modified to equal
                  value just prior to interrput ;
   cpu.sp := top of OS stack   // "optional"
   Update runQ.PCB accounting info ;
   // No Return_from_function because this is a macro
   // Why is this a macro and not a function

 function Scheduler() {
   // Called within an OS interrupt handler.
   // Assumes runQ is empty, interrupts disabled, ...
   while readyQ is empty do {
     // busy wait with interrupts enabled := ON ; := OFF ; 

   // readyQ not empty
   choose a pcb in readyQ ; // based on scheduling discipline
   move the pcb to runQ ;

   // dispatch
   cpu.gpr := runQ.PCB.gpr ;
   cpu.sp := runQ.PCB.sp ;
   cpu.hi := runQ.PCB.hi ;
   cpu.lo := runQ.PCB.lo ;
   push runQ.PCB.pc/ps on cpu.sp stack ;
   Return_from_Interrupt ;    // pops pc and ps atomically

 interruptHandler Syscall( PROC_TERM ) {
   remove runQ.pcb ;
   Scheduler() ;

 interruptHandler Syscall( IO, params ) {
   UpdateRunQPCB() ;
   RunQ.PCB.ioParams := params ;
   if ioWaitQ is empty // io device not busy
     then ioDevice.controlReg := params ; // start io
   move RunQ.PCB to ioWaitQ.PCB ;
   /* ioWaitQ has one or more PCBs. io device is handling
      the io request of the PCB at the head of ioWaitQ.
   Scheduler() ;

 interruptHandler Trap( INVALID_OP ) {
   remove runQ.pcb ;
   Scheduler() ;

 interruptHandler HwIntrpt( TIMER ) { 
   /* control here after timer interrupt.
      Interrupts are disabled, the top of the stack pointed to by cpu.sp
      has the value of cpu.pc/ps just prior to the interrupt.
      The interrupted process is a pcb process (WHY?) and its pcb is in runQ
   UpdateRunQPCB() ;
   move runQ.pcb to readyQ ;
   Scheduler() ;
   // no need for Return_from_Interrupt because control never comes here

 interruptHandler HwIntrpt( IO ) {
   /* control here after io device interrupts.
      The interrupted process is a pcb process and its pcb is in runQ.
      ioWaitQ is not empty, and the interrupt signals completion
      of the io request of the pcb process at head of ioWaitQ.
   move ioWaitQ.head.PCB to readyQ ;
   if ioWaitQ is not empty
     then // start io of next waiting process
          ioDevice.controlReg := ioWaitQ.head.pcb.ioParams ;
   Return_from_Interrupt ;  // interrupted process is resumed

   /* This handler uses the stack of the interrupted process.
      The interrupt has nothing to do with this process.
      No context switch is done.