Operating Systems, Spring 2015

Programming Assignment 1 - An Example Solution

Table of Contents

Introduction

This page presents a solution to the first programming assignment, which involves writing a disk driver and implementing the exit system call.

The Operating System

<os.java>=
/**
   A simple operating system without virtual storage and with almost no
   scheduling. 
 */


import java.util.Arrays


class os
implements OperatingSystem


  <Handle a system call>


  <Handle an interrupt>


  /**
     Create an instance of this operating system.

     hw: The hardware on which this os will be running.
   */

  public 
  os(Hardware hw)
    this.hw = hw
    idleProcess =
      new ProcessDescriptor(
        Hardware.Address.idleStart, Hardware.Address.idleEnd, hw)


  /**
     Run a process loaded into primary store.

     process: The process to run.
   */

  private void
  runProcess(ProcessDescriptor process)
    process.restoreRegisters()


  <The disk-index interrupt handler>

  <The program-load interrupt handler>

  <Operating system instance variables>


  /**
     A reference to the hardware on which this os runs.
   */

  private final Hardware hw
Defines os, os.java (links are to index).

Interrupt Handling

Figure out what the interrupt is, and handle it. 
<Handle an interrupt>= (<-U)
/**
   Handle an interrupt.

   it: The interrupt to handle.
 */

public void
interrupt(Hardware.Interrupt it)

  switch it

    <Handle disk interrupt>

    <Handle reboot interrupt>

    case systemCall

      doSystemCall(hw.fetch(0))

      break

    default

      SystemSim.panic("Unhandled " + it + " interrupt!")
Defines interrupt (links are to index).

Implementing System Calls

Figure out what the system call is, and implement it. 
<Handle a system call>= (<-U)
/**
   Handle a system-call interrupt

   sc: The system-call identifier.
 */

private void
doSystemCall(int sc)

  switch sc

    case OperatingSystem.SystemCall.exit

      <Handle an exit system call>

      break

    default

      SystemSim.panic(
        "Oh no! " + OperatingSystem.SystemCall.toString(sc) + " (= " + 
        sc + ") is an unhandled system call!")
Defines doSystemCall (links are to index).

Stopping the system on an exit system call is absolutely the wrong thing to do, but it works for the first set of batch disks, so go with it for now. 

<Handle an exit system call>= (<-U)
hw.store(Hardware.Address.haltRegister, 0)

The Disk-Interrupt Handlers

Dealing with disk interrupts is a pain because there are several reasons why an interrupt could occur:
  1. The disk-index block has been read.
  2. A block from the first program to run has been read.
The second reason can be further divided into
  1. A program block that's not the last block needed has been read.
  2. 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 provides a technique for managing the different ways of handling disk interrupts: define an abstract class encapsulating the common activities needed by all disk-interrupt handlers. Each particular disk-interrupt handler establishes its particular requirements by implementing concrete children of the disk-interrupt handler abstract class. For this assignment, only two children are needed to handle block-index interrupts and interrupts resulting from program loads. 

<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>
Defines DiskInterruptHandler (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.

Given the DiskInterruptHandler abstract class, the operating system defines an instance variable of type DiskInterruptHandler to represent the action to be taken when the next disk interrupt arrives. 
<Operating system instance variables>= (<-U) [D->]
/**
   How to handle the next disk interrupt.
 */

private DiskInterruptHandler diskInterruptHandler


/** 
   The user process of last resort.
*/

private final ProcessDescriptor idleProcess
Defines diskInterruptHandler, idleProcess (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
Defines diskInterruptHandler (links are to index).

In addition to defining the abstract method handleInterrupt(), the disk-interrupt abstract class also defines a bunch of common disk-manipulation routines useful to disk-interrupt-handling child classes. 

<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
Defines checkDiskStatus, diskBlockLoad, loadComplete (links are to index).

The state needed by every DiskInterruptHandler child class. 

<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
Defines blockCount, firstBlock, startAddress (links are to index).

And finally, the file containing the DiskInterruptHandler abstract class. 

<DiskInterruptHandler.java>=
/**
   An abstract disk-interrupt handler.
 */

  <Disk-interrupt handler abstract class>
Defines DiskInterruptHandler, DiskInterruptHandler.java (links are to index).

Index-Block Disk-Interrupt Handling

The first disk interrupt that occurs after reboot results from reading the batch disk's index block. The DiskIndexInterruptHandler reads the disk-index block and turns it into a data-structure the rest of the operating system can use. 
<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]


    // Issue a load request for the first program.

       diskInterruptHandler = 
         new ProgramLoadInterruptHandler(primaryStore, 0, startAddress)

       diskInterruptHandler.diskBlockLoad()
Defines DiskIndexInterruptHandler (links are to index).

The disk index is made available to the rest of the operating system in an unsophisticated data structure: a pair of private instance-variable arrays giving the programs' start location and size. It should probably be gussied up with at least a class, but for this assignment even a pair of arrays isn't really necessary. 

<Operating system instance variables>+= (<-U) [<-D]
/**
   An array of program sizes.  The ith element in the array gives the 
   size in disk blocks of the i>th program on the disk.
*/

private int programBlockCount []


/**
   An array of program locations.  The ith element in the array gives the 
   location on disk of the ith program.
*/

private int programFirstBlock []
Defines programBlockCount, programFirstBlock (links are to index).

When the reboot interrupt arrives, the operating system handles it by creating and then kicking-off a handler to read the program-index block off the batch disk. 

<Handle reboot interrupt>= (<-U)
case reboot:

  diskInterruptHandler = new DiskIndexInterruptHandler(hw)
  diskInterruptHandler.diskBlockLoad()

  idleProcess.restoreRegisters()

  break

Program-Load Disk-Interrupt Handling

The second source of disk interrupts in the first assignment is programs being loaded as the result of exec system calls. Loading a program requires reading a sequence of disk blocks into user space and executing the associated process once the program's been loaded. The ProgramLoadInterruptHandler child concrete class of the DiskIndexInterruptHandler abstract class is responsible for loading a program and then executing the resulting process.

ProgramLoadInterruptHandler's implementation leans heavily on the property that the first set of batch disk only ever load one program. This property is not true for subsequent batch disks, which may load several programs at the same time. The code shown here will not handle concurrent program loads and will have to be rewritten, but for now it's good enough. 
<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 program block just got read.  Turn the program into a
      // process and run it.

         runProcess(
           new ProcessDescriptor(
             startAddress,
             startAddress + Hardware.Disk.blockSize*programBlockCount[programIndex],
             primaryStore))
   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.

     requester: The process making the load request.
   */

  ProgramLoadInterruptHandler(
    PrimaryStore ps, int pi, int sa)

    super(ps, programFirstBlock[pi], sa, programBlockCount[pi])

    programIndex = pi


  /**
     The disk-index block index of the program being loaded.
   */

  private final int programIndex
Defines ProgramLoadInterruptHandler (links are to index).

Process Descriptors

Process descriptors aren't needed for the first assignment. Having a process-descriptor class available for use makes the code neater and sets the stage for later assignments, when process descriptors are necessary. 
<ProcessDescriptor.java>=
/**
   Describe a process's resources and state.
 */

class ProcessDescriptor


  /**
     Represent a process.

     start: The process's lowest (leftmost) address.

     end: One past the process's highest (rightmost) address.

     ps: A reference to primary store.
   */

  ProcessDescriptor(int start, int end, PrimaryStore ps)

    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

    primaryStore = ps


  /**
     Move  the process's register set to the hardware registers.
   */

  void
  restoreRegisters()
    for int i = 0; i < Hardware.Address.registerSetSize; i++
      primaryStore.store(i, registers[i])


  /**
     A place to save registers.
   */

  private final int registers[] = new int [Hardware.Address.registerSetSize]


  /**
     A reference to primary store.
   */

  private final PrimaryStore primaryStore
Defines ProcessDescriptor, ProcessDescriptor.java (links are to index).

Index

This page last modified on 2015 March 3.