Operating Systems, Fall 2000

Programming Assignment 2 - An Example Solution

Table of Contents

Introduction

 This assignment involved extending the simple, batch-oriented operating system built for the prvious assignment to include system calls for device I-O.

The Disk Routines

 The disk routines are broken into two parts: the handler and the driver. The disk driver is the low-level part responsible for actually performing disk I-O. The disk manager is the high-level part responsible for implementing the system-call interface using the facilities provided by the disk handler.

The OS can access the disk either though the disk driver or the disk manager. Although it's cleaner to have all access go through the disk manager; it's simpler to have the os access the disk more-or-less directly via the disk driver.

The Disk Manager

Device ids for the disk are represented by an ever-increasing sequence of integers, starting at 0. The static variable next_device_id is the next available device id. The set of all valid disk device identifers (that is, device identifiers allocated but not yet released) are stored in the set device_ids. 
<the disk device id representation>= (U->)

#include <set>

static int next_disk_id = 0;
static set<int> disk_ids;
Defines disk_ids, next_disk_id, (links are to index).

When scheduling a disk i-o operation with the disk driver, the disk manager includes a call-back function and a void * pointer to be used as an argument to the call-back function when its called.

The void * pointer is a pointer to a disk_cb_info structure, which contains the information the call-back function needs to complete the disk i-o system call: 

<the disk call-back information>= (U->)

struct disk_cb_info {
  ptab_iter pte;
  unsigned bno;
  disk_io::operation op;
  disk_cb_info(ptab_iter & p, unsigned b, disk_io::operation o) :
    pte(p), bno(b), op(o) { }
  };
Defines disk_cb_info (links are to index).

According to disk allocation policy, it should always be possible to open the disk, which leads to a simple disk open procedure. 

<the disk open procedure>= (U->)

void open(void) {
  word dev_id = next_disk_id++;
  disk_ids.insert(dev_id);
  store(1, dev_id, disk_mgr::open);
  store(0, device::ok, disk_mgr::open);
  }
Defines disk_mgr::open (links are to index).

To close a disk connection, just remove the disk id from the set of active disk ids. 

<the disk close procedure>= (U->)

void close(word dev_id) {
  assert(is_valid_id(dev_id));
  disk_ids.erase(dev_id);
  store(0, device::ok, disk_mgr::close);
  }
Defines disk_mgr::close (links are to index).

Perform the disk i-o operation op using Primary Store location loc and disk block n on behalf of the currently executing process. 

<the disk operation procedure>= (U->)

void operation(
  system_call::system_calls op, word dev_id, address loc, unsigned n) {

  assert(is_valid_id(dev_id));
  assert((op == system_call::read) || (op == system_call::write));

  const disk_io::operation dop = 
    (op == system_call::read ? disk_io::read : disk_io::write);

  disk_dvr::request(
    dop, n, loc, dsk_cb, new disk_cb_info(running_process, n, dop));

  sleep_scheduler();
  }
Defines disk_mgr::operation (links are to index).

If the device id dev_id is a member of the set of active disk device ids, then it's a valid device id for the disk; otherwise, it isn't. 

<the disk id predicate>= (U->)

bool is_valid_id(word dev_id) {
  return disk_ids.find(dev_id) != disk_ids.end();
  }
Defines disk_mgr::is_valid_id (links are to index).

dsk_cb() is called when a user process disk-io operation has been completed with disk status s. 

<the disk-io callback>= (U->)

static void dsk_cb(disk_io::status s, void * arg) {
  disk_cb_info * dcbi = reinterpret_cast<disk_cb_info *>(arg);
  dcbi->pte->registers[0] = s;
  if (dcbi->op == disk_io::read)
    dcbi->pte->registers[1] = dcbi->bno;
  ready_scheduler(dcbi->pte);
  delete dcbi;
  }
Defines dsk_cb (links are to index).

<disk-mgr.cc>=
#include "disk-mgr.h"
#include "os.h"
#include "scheduler.h"
#include "disk-dvr.h"

<the disk device id representation>

<the disk call-back information>

<the disk-io callback>

namespace disk_mgr {
  <the disk open procedure>
  <the disk close procedure>
  <the disk operation procedure>
  <the disk id predicate>
  }
Defines disk-mgr.cc (links are to index).

<disk-mgr.h>=

#ifndef _disk_mgr_h_
#define _disk_mgr_h_

#include "system.h"

namespace disk_mgr {
  void open(void);
  void close(word);
  void operation(
    system_call::system_calls op, word dev, address loc, unsigned n);
  bool is_valid_id(word);
  }
#endif
Defines disk-mgr.h (links are to index).

The Terminal Manager

The terminal could be handled in the same way that the disk was: with a low-level driver and a high-level manager. However, the OS doesn't use the terminal, so it's easier to collaps both parts into a single part and treat it as the terminal manager.

The terminal management policy permits the terminal to be opened at most once, which leads to a simple open routine. If the terminal is free, allocate it; otherwise, indicate regrets. 

<the terminal open procedure>= (U->)

void open(void) {
  if (tty_free) {
    tty_free = false;
    store(0, device::ok, terminal_mgr::open);
    store(1, tty_id, terminal_mgr::open);
    }
  else
    store(0, device::device_busy, terminal_mgr::open);
  }
Defines terminal_mgr::open (links are to index).

Free up the terminal; this code assumes dev_id is a valid terminal identifier. 

<the terminal close procedure>= (U->)

void close(word dev_id) {
  assert(is_valid_id(dev_id));
  tty_free = true;
  store(0, device::ok, terminal_mgr::close);
  }
Defines terminal_mgr::close (links are to index).

Perform the terminal operation op on the terminal indicated by dev_id using the n characters found at address loc. 

<the terminal operation procedure>= (U->)

void operation(system_call::system_calls op, word dev_id, address loc, unsigned n) {
  assert(is_valid_id(dev_id));

  <check the null terminal operation>

  <check for valid terminal io addresses>

  if (op == system_call::read) {
    mass.memory->set_ihandler(terminal_i, read_terminal_ih);
    store(terminal_command_register,terminal_io::read,terminal_mgr::operation);
    }
  else {
    assert(op == system_call::write);
    mass.memory->set_ihandler(terminal_i, write_terminal_ih);
    fetch(loc, b, terminal_mgr::operation);
    store(terminal_data_register, b, terminal_mgr::operation);
    store(terminal_command_register,terminal_io::write,terminal_mgr::operation);
    }

  tty_proc = running_process;
  sleep_scheduler();

  tty_loc = loc;
  tty_n = n;
  tty_cnt = 0;
  }
Defines terminal_mgr::operation (links are to index).

If the user process isn't moving any characters, then - viola! - the operation has been succesfully completed. 

<check the null terminal operation>= (<-U)

if (n == 0) {
  store(0, device::ok, terminal_mgr::operation);
  store(1, 0, terminal_mgr::operation);
  return;
  }

This code checks for a full range of valid addresses, which is a little eager, but still safe. 

<check for valid terminal io addresses>= (<-U)

#define valid_addr(_a) \
 (((_a) < pc_register) || ((((address) b) <= (_a)) && ((_a) < ((address) t))))

word b, t;
fetch(base_register, b, terminal_mgr::operation);
fetch(top_register, t, terminal_mgr::operation);
if (!valid_addr(loc) || ((op == system_call::write) && !valid_addr(loc + n))) {
  store(0, device::bad_address, terminal_mgr::operation);
  return;
  }

If the terminal is open and the device id matches the terminal id, then the device id is valid; otherwise, the device id isn't valid. 

<the terminal id predicate>= (U->)

bool is_valid_id(word dev_id) {
  return (dev_id == tty_id) && !tty_free;
  }
Defines terminal_mgr::is_valid_id (links are to index).

<the terminal read interrupt handler>= (U->)

static void read_terminal_ih(void) {

  word w;
  fetch(terminal_status_register, w, read_terminal_ih);
  assert(w == terminal_io::ok);

  <save the terminal character read>

  <continue (or not) the terminal read>
  }
Defines read_terminal_ih (links are to index).

Copy the character from the terminal data register to the user process's address, checking for a bad address. 

<save the terminal character read>= (<-U)

device::status s = device::ok;
fetch(terminal_data_register, w, read_terminal_ih);
if (w != device::eof_char)
  if (!tty_loc >= (address) (tty_proc->registers[top_register]))
    s = device::bad_address;
  else {
    if (tty_loc < pc_register)
      tty_proc->registers[tty_loc] = w;   
    else
      store(tty_loc, w, read_terminal_ih);
    tty_cnt++;
    tty_loc++;
    }

If n characters have been read, or there's an end-of-file, or an error, then terminal reading is at an end. Otherwise, to around and read the next character. 

<continue (or not) the terminal read>= (<-U)

if ((tty_cnt == tty_n) || (w == device::eof_char) || (s != device::ok)) {
  tty_proc->registers[0] = s;
  tty_proc->registers[1] = tty_cnt;
  ready_scheduler(tty_proc);
  }
else
  store(terminal_command_register, terminal_io::read, read_terminal_ih);

The previous terminal write is done. If there's more characters to write, go to it; otherwise, wake up the requesting user process and indicate the status of the terminal write. 

<the terminal write interrupt handler>= (U->)

static void write_terminal_ih(void) {

  word w;
  fetch(terminal_status_register, w, write_terminal_ih);
  assert(w == terminal_io::ok);

  if (++tty_cnt == tty_n) {
    tty_proc->registers[0] = device::ok;
    tty_proc->registers[1] = tty_cnt;
    ready_scheduler(tty_proc);
    }
  else {
    <continue the terminal write>
    }
  }
Defines write_terminal_ih (links are to index).

Ship off the next character to be written to the terminal. 

<continue the terminal write>= (<-U)

tty_loc++;
fetch(tty_loc, w, write_terminal_ih);
store(terminal_data_register, w, write_terminal_ih);
store(terminal_command_register, terminal_io::write, write_terminal_ih);

This is the standard device interface. 

<terminal-mgr.h>=

#ifndef _terminal_mgr_h_
#define _terminal_mgr_h_

#include "system.h"

namespace terminal_mgr {
  void open(void);
  void close(word);
  void operation(
    system_call::system_calls op, word dev, address loc, unsigned n);
  bool is_valid_id(word);
  }
#endif
Defines terminal-mgr.h (links are to index).

Because the terminal can only be opened at most once, the terminal data structures are simple:

tty_id
The terminal identifier; this is, perhaps, too cute, but it works.

tty_free
True if and only if the terminal isn't open.

tty_proc
If the terminal is open, the process that did the opening. This is the process that's sleeping on terminal I-O.

tty_cnt
The number of characters dealt with in the current terminal I-O operation.

tty_n
The number of characters to deal with in the current terminal I-O operation.

tty_loc
The user-process address associated with the characters involved in the current terminal I-O operation. 
<the terminal data structures>= (U->)

static unsigned tty_cnt, tty_n;
static address tty_loc;
static ptab_iter tty_proc;
static bool tty_free = true;
const int tty_id = 1956;
Defines tty_cnt,, tty_free, tty_loc,, tty_n,, tty_proc, (links are to index).

<terminal-mgr.cc>=

#include "terminal-mgr.h"
#include "os.h"
#include "scheduler.h"

<the terminal data structures>

<the terminal write interrupt handler>
<the terminal read interrupt handler>

namespace terminal_mgr {
  <the terminal open procedure>
  <the terminal close procedure>
  <the terminal operation procedure>
  <the terminal id predicate>
  }
Defines terminal-mgr.cc (links are to index).

The Disk Driver

The disk driver is responsible for actually doing disk I-O. This code is essentially a repackaging of the disk driver code from assignment 1. The main difference is that this code uses call-backs to inform waiting processes (which includes the operating system) when a disk operation is done. 
<disk-dvr.h>=

#ifndef _disk_dvr_h_
#define _disk_dvr_h_

#include "system.h"

namespace disk_dvr {

  typedef void (* callback)(disk_io::status, void *);

  extern void initialize(void);

  extern void request(
    disk_io::operation op,
    unsigned bno,
    address loc,
    callback f,
    void * arg);
  };

#endif
Defines disk-dvr.h (links are to index).

The information associated with each disk I-O operation issued is stored in a request data structure. 

<disk driver data structures>= (U->) [D->]

struct request {
  unsigned bno;
  address loc;
  disk_io::operation op;
  disk_dvr::callback f;
  void * arg;  
  };

Request data structures are stored in a queue until they can be sent to the disk. This is simple first-come, first-serve scheduling. 

<disk driver data structures>+= (U->) [<-D->]

typedef queue<request> Requests;
static Requests pending;

in_progress is true if and only if there is a disk operation currently in progress. 

<disk driver data structures>+= (U->) [<-D]

static bool in_progress = false;

A process P calls disk_dvr::request() to have a disk operation made on P's behalf. Because the disk operation completes at an unpredictable time, P includes the call-back function f, which the disk manager will call when the I-O operation completes. Because P could have several pending disk I-O requests, the disk manager passes the value arg, given by P, in the call to f. The disk manager does not interpret or use arg in any way, it just passes it along in the call back; presumably, P will use arg as an disk-io operation identifier of some kind. 

<the disk manager request procedure>= (U->)
void request(
  disk_io::operation op, unsigned bno, address loc, callback f, void * arg) {

  ::request req;
  req.bno = bno;
  req.loc = loc;
  req.op = op;
  req.f = f;
  req.arg = arg;
  pending.push(req);

  dskmgr_poke();
  }
Defines disk_dvr::request (links are to index).

When a disk interrupt occurs, disk_ih() notifies the requestor via its call-back function and then starts the next disk I-O operation, if any. 

<the disk interrupt handler>= (U->)

static void disk_ih(void) {

  assert(!pending.empty());
  const request & req = pending.front();
  word w;
  fetch(disk_status_register, w, disk_dvr::disk_ih);
  (req.f)((disk_io::status) w, req.arg);
  pending.pop();
  in_progress = false;
  
  dskmgr_poke();
  }
Defines disk_ih (links are to index).

dskmgr_poke() checks to see if it's possible to start a new disk I-O operation. If there's no disk I-O operation in progress and there's a request waiting, then dskmgr_poke() can start a new disk I-O operation, otherwise it does nothing. 

<the disk manager wake-up procedure>= (U->)

  static void dskmgr_poke(void) {
    if (!in_progress && !pending.empty()) {
      const request & req = pending.front();
      store(disk_address_register, req.loc, dskmgr_poke);
      store(disk_block_register, req.bno, dskmgr_poke);
      store(disk_command_register, req.op, dskmgr_poke);
      in_progress = true;
      }
    }
Defines dskmgr_poke (links are to index).

<the disk manager initialization procedure>= (U->)
  void initialize(void) {
    mass.memory->set_ihandler(disk_i, disk_ih);
    }
Defines disk_dvr::initialization (links are to index).

<disk-dvr.cc>=
#include "disk-dvr.h"
#include "os.h"
#include <queue>

<disk driver data structures>

<the disk manager wake-up procedure>
<the disk interrupt handler>

namespace disk_dvr {
  <the disk manager request procedure>
  <the disk manager initialization procedure>
  }
Defines disk-dvr.cc (links are to index).

The Scheduler

The scheduler is responsible for managing the process table and for moving processes into and out of the cpu. The public scheduler routines are 
<the scheduler interface>= (U->) [D->]

  extern void poke_scheduler(void);
  extern void start_scheduler(void);
  extern void sleep_scheduler(void);
  extern void ready_scheduler(ptab_iter &);
  extern void add_scheduler(process_table_entry &);
  extern void exit_scheduler(void);
  extern bool scheduler_done(void);
  extern void halt(void);

The scheduler also exports a data structure: a pointer to the process-table entry of the running process. 

<the scheduler interface>+= (U->) [<-D]

  extern ptab_iter running_process;

The remaining scheduler procedures and data structures are private to the scheduler.

In addition to the global running_process variable, declare idle_process, a file-local pointer to the idle process, and initialize the process id counter process_table_entry::next_id. 

<the scheduler data structures>= (U->)

  static process_table ptab;
  ptab_iter running_process;
  static ptab_iter idle_process;

  unsigned process_table_entry::next_id = 0;
Defines idle_process, ptab (links are to index).

load_cpu() loads into the CPU the process associated with the process-table entry pointed to by pi. This code assumes the process currently executing (if any) has been saved and its state can be trashed. 

<the scheduler routines>= (U->) [D->]

  static void load_cpu(ptab_iter & pi) {

    pi->status = executing;
    pi->restore_state();
    running_process = pi;

    debugp(dbp_execute, "At time %d, process %d runs.\n", 
           read_clock(), running_process->id);
    }
Defines load_cpu (links are to index).

readyp defines a predicate that returns true if the process associated with the process-table entry pte is a ready processes. runningp defines a predicate that's true if the process associated with the process-table entry pte is the executing processes. 

<the scheduler routines>+= (U->) [<-D->]

  class readyp {
    public:
      bool operator()(process_table_entry & pte) const { 
        return pte.status == ready;
        }
    };

  class runningp {
    public:
      bool operator()(process_table_entry & pte) const { 
        return pte.status == executing;
        }
    };
Defines readyp, runningp (links are to index).

poke_scheduler() gets called whenever something changes in the process table. Figure out what changed and handle it. 

<the scheduler routines>+= (U->) [<-D->]

  void poke_scheduler(void) {

    ptab_iter end = ptab.end();
    ptab_iter next_process;

    <swap-out the idle process>
    <swap-in a ready process>
    <handle the process table changes>
    }
Defines poke_scheduler (links are to index).

If the idle process is currently executing, replace it with a ready process, if any. 

<swap-out the idle process>= (U->)

if (idle_process->status == executing) {
  next_process = find_if(ptab.begin(), end, readyp());
  if (next_process != end) {
    idle_process->status = ready;
    load_cpu(next_process);
    }
  return;
  }

If there's nothing running (because the currently executing process has been swapped out of the CPU), find a ready process to run. There should always be a ready process because the idle process is always ready. 

<swap-in a ready process>= (U->)

next_process = find_if(ptab.begin(), end, runningp());
if (next_process == end) {
  next_process = find_if(ptab.begin(), end, readyp());
  if (next_process == end)
    panic("can't find a ready process in poke_scheduler()");
  load_cpu(next_process);
  return;
  }

There's a running process, and it's not the idle process; leave well enough alone. 

<handle the process table changes>= (U->)

return;

start_scheduler() adds the idle process to the process table so there's always something to execute. Because there's no other processes yet, load the idle process for execution.

Ideally, the idle process should have priority lower than any other ready process so the idle process will automatically be pre-empted when another process comes ready for execution. However, to avoid dealing with priorities, this code cheats a bit by maintaining the idle process at the end of the process table and then searching the process table from beginning to end. If there is an ready process, it will be found before the idle process. 

<the scheduler routines>+= (U->) [<-D->]

void start_scheduler(void) {

  process_table_entry idle_pte;
  idle_pte.status = ready;
  idle_pte.registers[pc_register] = idle_start;
  idle_pte.registers[base_register] = idle_start;
  idle_pte.registers[top_register] = idle_end;
  idle_pte.registers[sw_register] = 0;
  idle_process = ptab.insert(ptab.begin(), idle_pte);

  load_cpu(idle_process);
  }
Defines start_scheduler (links are to index).

sleep_scheduler() sleeps the executing process and select a ready process for execution. 

<the scheduler routines>+= (U->) [<-D->]

void sleep_scheduler(void) {
  running_process->save_state();
  running_process->status = sleeping;
  poke_scheduler();
  }
Defines sleep_scheduler (links are to index).

ready_scheduler() readys the executing process and select a ready process for execution. 

<the scheduler routines>+= (U->) [<-D->]

void ready_scheduler(ptab_iter & pp) {
  pp->status = ready;
  poke_scheduler();
  }
Defines ready_scheduler (links are to index).

exit_scheduler() deletes the currently executing process from the process table and poke the scheduler get the next one (if any) ready for execution. The exiting process frees up some user space, so also poke the program loader in case it was waiting for more user space. 

<the scheduler routines>+= (U->) [<-D->]

void exit_scheduler(void) {
  debugp(dbp_execute, "At time %d, process %d exits.\n", 
         read_clock(), running_process->id);

  us_free(running_process->registers[base_register]);
  ptab.erase(running_process);
  poke_scheduler();
  pgm_loader::poke();
  }
Defines exit_scheduler (links are to index).

add_scheduler() adds the process-table entry new_pte to the process table. new_pte is assumed to be ready to run, so it is passed to ready_scheduler() to make it so. 

<the scheduler routines>+= (U->) [<-D->]

void add_scheduler(process_table_entry & new_pte) {
  ptab.push_front(new_pte);
  ptab_iter npte = ptab.begin();
  ready_scheduler(npte);
  }
Defines add_scheduler (links are to index).

scheduler_done() returns true if and only if the scheduler has nothing to do, which happens when only the idle process remains. This does not mean the system is done, because the program loader could still be at work. 

<the scheduler routines>+= (U->) [<-D->]

bool scheduler_done(void) {
  return (ptab.size() == 1);
  }
Defines scheduler_done (links are to index).

halt() shuts down the system. 

<the scheduler routines>+= (U->) [<-D]

void halt(void) { 
  store(halt_register, 0, halt);
  }
Defines halt (links are to index).

<scheduler.cc>=

#include "scheduler.h"
#include "pgm-loader.h"
#include "us-mgt.h"
#include <algorithm>

<the scheduler data structures>

<the scheduler routines>
Defines scheduler.cc (links are to index).

<scheduler.h>=

#ifndef _scheduler_h_defined_
#define _scheduler_h_defined_

#include "proc-tab.h"

<the scheduler interface>

#endif
Defines scheduler.h (links are to index).

The Sleeper

The sleeper routines are responsible for handling sleep system calls and countdown interrupts. The public interface to the sleeper routines comprises two routines: the countdown-interrupt handler countdown_ih() and sleep scheduler do_sleep(). All other routines and data structures used to implement sleeping are private to the file sleeper.cc. 
<the sleeper interface>= (U->)

extern void countdown_ih(void);
extern void do_sleep(int);

A sleeping process is represented as the pair (w, p), where w is the earliest absolute clock time the sleeper should be woken up and p is a pointer to the sleeper's process-table entry. 

<representing sleeping processes>= (U->) [D->]

typedef pair<unsigned, ptab_iter>  sleeper;

#define get_wake_up_time(_s) (_s).first
#define get_sleeper(_s)      (_s).second

Sleeper a is less sleeper b if and only if a's wake-up time is earlier than b's wake-up time (this has to be expressed backwards to get a minimum priority queue in the STL). 

<representing sleeping processes>+= (U->) [<-D->]

struct uc {
  bool operator()(const sleeper & a, const sleeper & b) const {
    return get_wake_up_time(a) > get_wake_up_time(b);
    }
  };

Sleeping processes are kept in a minimum priority queue ordered on absolute wake-up time. The head of the sleeper queue (if any) is the process with the earliest wake-up time. 

<representing sleeping processes>+= (U->) [<-D]

static priority_queue<sleeper, vector<sleeper>, uc> wake_up_calls;

schedule_countdown() schedules a countdown interrupt for the process at the front of the sleeper queue. 

<a countdown scheduler macro>= (U->)

#define schedule_countdown(_w) \
  do {assert(!wake_up_calls.empty()); \
      store(clock_countdown_register, \
            get_wake_up_time(wake_up_calls.top()) - read_clock(), _w); \
     } while (false)
Defines schedule_countdown (links are to index).

do_sleep() is called when the currently executing process has issued a sleep system call for delta clock ticks. 

<the sleep system-call handler>= (U->)

void do_sleep(int delta) {

  const unsigned c = read_clock();

  <ignore invalid requests>
  <queue the sleeper>
  sleep_scheduler();
  }
Defines do_sleep (links are to index).

If the requested sleep time is not positive, nothing happens. 

<ignore invalid requests>= (U->)

debugp(dbp_sleep, "At time %d, process %d sleeps for %d ticks",
       c, running_process->id, delta);

if (delta < 1) {
  debugp(dbp_sleep, ", nothing done.\n");
  return;
  }

debugp(dbp_sleep, ".\n");

Stick the executing process in the sleeper's queue. If the executing process makes it to the front of the sleeper's queue (because it has the earliest wake-up time among all sleepers), the countdown timer has to be rescheduled for an earlier interrupt.

This code cheats a bit by assuming the executing process always makes it to the front of the sleeper queue, and automatically reschedules the countdown timer to the wake-up time at the front of the queue. This may result in unnecessary rescheduling the countdown timer (when the executing process doesn't have the earliest wake-up time), but it eliminates the need to keep track of the front of the queue and when it changes. 

<queue the sleeper>= (U->)

wake_up_calls.push(sleeper(delta + c, running_process));
schedule_countdown(do_sleep);

countdown_ih() is the countdown-interrupt handler. 

<the countdown interrupt handler>= (U->)

void countdown_ih(void) {

  const unsigned now = read_clock();

  <countdown interrupt sanity checks>
  <wake up the sleepers>
  <schedule a new countdown interrupt>
  }
Defines countdown_ih (links are to index).

Some sleeping process must have issued this request, and that process' wake-up time should not be in the future. 

<countdown interrupt sanity checks>= (U->)

assert(!wake_up_calls.empty());
assert(get_wake_up_time(wake_up_calls.top()) <= now);

As long as its wake-up time not in the future, pop off the sleeper at the head of the queue (if any) and make it ready for execution. 

<wake up the sleepers>= (U->)

do {
  sleeper s = wake_up_calls.top();
  wake_up_calls.pop();

  debugp(dbp_sleep,
         "At time %d, process %d wakes up.\n", now, get_sleeper(s)->id);
  ready_scheduler(get_sleeper(s));
  }
while (!wake_up_calls.empty() && (get_wake_up_time(wake_up_calls.top()) <= now));

If there are still some sleepers in the queue, schedule a countdown interrupt for the earliest riser. 

<schedule a new countdown interrupt>= (U->)

if (!wake_up_calls.empty())
  schedule_countdown(countdown_ih);


<sleeper.cc>=

#include <algorithm>
#include <queue>
#include <vector>
#include "sleeper.h"
#include "scheduler.h"
#include "os.h"

<representing sleeping processes>

<a countdown scheduler macro>
<the sleep system-call handler>
<the countdown interrupt handler>
Defines sleeper.cc (links are to index).

<sleeper.h>=

#ifndef _sleeper_h_
#define _sleeper_h_

<the sleeper interface>

#endif
Defines sleeper.h (links are to index).

The Program Loader

There are three functions in the program loader's public interface:

  • pgm_loader::initialize() - the disk interrupt handler for the program index block.

  • pgm_loader::done() - indicates when program loading is done.

  • pgm_loader::poke() - wake up the program loader. 
    • <the program loader interface>= (U->)

extern void initialize(void);
extern bool done(void);
extern void poke(void);

    Each program in a batch disk is characterized by the pair (f, n), where a program starts at disk block f and contains n disk blocks. 

    <program loader data structures>= (U->) [D->]

typedef pair<unsigned, unsigned> pgm_disk_info;

#define get_block_no(_p)  (_p).first
#define get_block_cnt(_p) (_p).second
    Defines get_block_cnt, get_block_no, pgm_disk_info (links are to index).

    The program pairs that have yet to be read into the system are kept in the list pgm_index. 

    <program loader data structures>+= (U->) [<-D->]

static list<pgm_disk_info> pgm_index;
    Defines pgm_index (links are to index).

    next_disk_block holds the number of the next block to read from disk. 

    <program loader data structures>+= (U->) [<-D->]

static word next_disk_block;
    Defines next_disk_block (links are to index).

    program_blocks_read holds the number of blocks left to read in the current program load. 

    <program loader data structures>+= (U->) [<-D->]

static word program_blocks_read;
    Defines program_blocks_read (links are to index).

    pgm_load_in_progress is true if and only if there's a program load in progress. 

    <program loader data structures>+= (U->) [<-D->]

static bool pgm_load_in_progress;
    Defines pgm_load_in_progress (links are to index).

    <program loader data structures>+= (U->) [<-D->]

static const address index_block_address = usr_base;
    Defines index_block_address (links are to index).

    A process-table entry to store information about the program being loaded. 

    <program loader data structures>+= (U->) [<-D]

static process_table_entry new_pte;
    Defines new_pte (links are to index).

    Procedure _w calls check_disk_io() to check the results of the last disk operation. 

    <program loader procedures>= (U->)

#define check_disk_io(_s, _w) \
  if ((_s) != disk_io::ok) panic("disk read failed with status %d", _s)
    Defines check_disk_io (links are to index).

    pgm_block() is the disk-io call back that gets called when the disk read for a batch-program block is finished. 

    <the program block call back>= (U->)

static void pgm_block(disk_io::status s, void *) {

  check_disk_io(s, pgm_loader);

  <read another program disk block>
  <add new process table entry>

  pgm_loader::poke();
  }
    Defines pgm_block (links are to index).

    If program being loaded still has more blocks on disk, start reading the next block and return to the user process. 

    <read another program disk block>= (U->)

if (program_blocks_read-- > 0) {
  disk_dvr::request(
    disk_io::read,
    next_disk_block + program_blocks_read,
    new_pte.registers[base_register] + program_blocks_read*disk_block_size,
    pgm_block,
    0);
  return;
  }

    The program has been read into primary store. Install it in the process table and let the scheduler know there's a new process available. 

    <add new process table entry>= (U->)

add_scheduler(new_pte);
pgm_load_in_progress = false;


    <the index block call back>= (U->)

static void index_block(disk_io::status s, void *) {

  check_disk_io(s, disk_ih);

  <copy the program index information>
  <start loading programs>
  }
    Defines index_block (links are to index).

    Copy the program index information out of the disk block and into the local data structure pgm_index. 

    <copy the program index information>= (<-U)

unsigned nxt_blk = 1;
for (unsigned i = 0; i < disk_block_size; i++) {
  word s;
  fetch(index_block_address + i, s, index_block);
  if (s == 0) break;
  if (s*disk_block_size > usr_size)
    panic("program %d has size %d words, larger than user space"
          " (%d words)", i + 1, s*disk_block_size, usr_size);
  pgm_index.push_back(pgm_disk_info(nxt_blk, s));
  nxt_blk += s;
  }

    Start the program loader. If the program loader's done, there's no programs to load and this show is over. 

    <start loading programs>= (<-U)

pgm_loader::poke();
if (pgm_loader::done()) halt();

    pgm_loader::initialize() is the disk-interrupt handler that gets called when the disk read for the program-index block has been completed. The program-index block has been read into a block of user space starting at address index_block_address. 

    <program loader initialization procedure>= (U->)

void initialize(void) {
  <read the index block>
  }
    Defines pgm_loader::initialize (links are to index).

    <read the index block>= (U->)

disk_dvr::request(
  disk_io::read,
  0,
  index_block_address, 
  index_block, 
  0);

    pgm_loader::poke() gets called whenever the amount of free user space increases. If program loading stopped because there wasn't any enough free user space, the additional free user space may allow program loading to continue (or maybe not, if there still isn't enough free user space). 

    <the program load procedure>= (U->)

void poke(void) {
  <check for busy or done>
  <check for available user space>
  <create a new process-table entry>
  <start reading in the new program>
  }
    Defines pgm_loader::poke (links are to index).

    If a program is begin loaded, or if there's no more programs to load, there's nothing to do. 

    <check for busy or done>= (U->)

if (pgm_load_in_progress || pgm_index.empty()) return;

    If there still isn't enough room in user space for the next program, wait for more room to open up. 

    <check for available user space>= (U->)

address pgm_start;
pgm_disk_info pdi = pgm_index.front();
if (!us_alloc(get_block_cnt(pdi), pgm_start)) return;
pgm_index.pop_front();

    There's at least one more program to load, and there's enough user space to load it. Create a process table entry for the new process. 

    <create a new process-table entry>= (U->)

new_pte = process_table_entry();
new_pte.registers[base_register] = pgm_start;
new_pte.registers[top_register] = 
  pgm_start + get_block_cnt(pdi)*disk_block_size;
new_pte.registers[pc_register] = pgm_start;
new_pte.registers[sw_register] = 0;

    Start reading in the blocks associated with the next batch program. 

    <start reading in the new program>= (U->)

pgm_load_in_progress = true;
program_blocks_read = get_block_cnt(pdi) - 1;
next_disk_block = get_block_no(pdi);
disk_dvr::request(
  disk_io::read,
  next_disk_block + program_blocks_read,
  pgm_start + program_blocks_read*disk_block_size, 
  pgm_block, 
  0);

    pgm_loader::done() returns true if and only if the program loader is done, which happens when there is no program load in progress and there's no more programs to load. 

    <the loading-done predicate>= (U->)

bool done(void) {
  return pgm_index.empty() && !pgm_load_in_progress;
  }
    Defines pgm_loader::done (links are to index).

    <pgm-loader.cc>=

#include <list>
#include "proc-tab.h"
#include "us-mgt.h"
#include "pgm-loader.h"
#include "scheduler.h"
#include "disk-dvr.h"

<program loader data structures>

<program loader procedures>
<the program block call back>
<the index block call back>

namespace pgm_loader {
  <program loader initialization procedure>
  <the loading-done predicate>
  <the program load procedure>
  }
    Defines pgm-loader.cc (links are to index).

    <pgm-loader.h>=

#ifndef _pgm_loader_h_defined_
#define _pgm_loader_h_defined_

namespace pgm_loader {
  <the program loader interface>
  }

#endif
    Defines pgm-loader.h (links are to index).

    The Reboot Interrupt Handler

    Figure out the system call issued and deal with it. 
    <the system-call interrupt handler>= (U->)

static void syscall_ih(void) {

  word syscall_code;
  fetch(0, syscall_code, syscall_ih);

  debugp(dbp_syscall, "At time %d, system call %d.\n", read_clock(), syscall_code);
  switch (syscall_code) {

    case system_call::exit: {
      <handle an exit system call>
      break;
      }

    case system_call::sleep: {
      <handle a sleep system call>
      break;
      }

    case system_call::open: { 
      <handle a device open system call>
      break;
      }

    case system_call::close: { 
      <handle a device close system call>
      break;
      }

    case system_call::write:
    case system_call::read: {
      <handle a device i-o system call>
      break;
      }

    default:
      panic("unknown system call type %d in syscall_ih()", syscall_code);
    }
  }
    Defines syscall_ih (links are to index).

    The currently running process has exited. If the scheduler and the program loader are done, then we are outta here. 

    <handle an exit system call>= (<-U)

exit_scheduler();
if (scheduler_done() && pgm_loader::done()) halt();

    For a sleep system call, read the sleep time and call do_sleep() to schedule a wake-up call. 

    <handle a sleep system call>= (<-U)

word delta;
fetch(1, delta, syscall_ih);
do_sleep(delta);

    For a device open system call, read the device type and call the apropriate open procedure. 

    <handle a device open system call>= (<-U)

word dev_id;
fetch(1, dev_id, syscall_ih);
if (dev_id == device::disk)
  disk_mgr::open();
else if (dev_id == device::terminal)
  terminal_mgr::open();
else 
  store(0, device::bad_device, syscall_ih);

    For a device close system call, read the device id, find the apropriate device manager and call the close procedure. 

    <handle a device close system call>= (<-U)

word dev_id;
fetch(1, dev_id, syscall_ih);
if (disk_mgr::is_valid_id(dev_id))
  disk_mgr::close(dev_id);
else if (terminal_mgr::is_valid_id(dev_id))
  terminal_mgr::close(dev_id);
else
  store(0, device::bad_device, syscall_ih);

    For a device-io system call, read the device id, Primary Store address, and device parameter (either block id or characer count, depending on device), then go. 

    <handle a device i-o system call>= (<-U)

word dev_id, addr, n;
fetch(1, dev_id, syscall_ih);
fetch(2, addr, syscall_ih);
fetch(3, n, syscall_ih);
if (disk_mgr::is_valid_id(dev_id))
  disk_mgr::operation((system_call::system_calls) syscall_code,
                      dev_id,
                      (address) addr,
                      (unsigned) n);
else if (terminal_mgr::is_valid_id(dev_id))
  terminal_mgr::operation((system_call::system_calls) syscall_code,
                          dev_id,
                          (address) addr,
                          (unsigned) n);
else
  store(0, device::bad_device, syscall_ih);

    What to do when the system boots (or reboots): set the interrupt vectors, initialize the disk routines, and run the scheduler. 

    <the reboot interrupt handler>= (U->)

void reboot_ih(void) {

  mass.memory->set_ihandler(system_call_i, syscall_ih);
  mass.memory->set_ihandler(countdown_i, countdown_ih);

  disk_dvr::initialize();
  pgm_loader::initialize();

  start_scheduler();
  }
    Defines reboot_ih (links are to index).

    Not a start-up procedure, but useful to have around. 

    <a clock-reading process>= (U->)

unsigned read_clock(void) {
  word c;
  fetch(clock_register, c, read_clock);
  return c;
  }
    Defines read_clock (links are to index).

    <pa2-os.cc>=

#include "os.h"
#include "disk-dvr.h"
#include "pgm-loader.h"
#include "scheduler.h"
#include "sleeper.h"
#include "disk-mgr.h"
#include "terminal-mgr.h"

<the system-call interrupt handler>
<the reboot interrupt handler>
<a clock-reading process>
    Defines pa2-os.cc (links are to index).

    Utilities

    Intervals

     The process loader needs a simple model of User Space so it can keep track of segments of free User Space large enough to hold batch programs.

    Intervals over a fixed range of natural numbers are a simple and direct model for free space management. An interval represents a segment of free User Space; each number in the interval represents a disk-block sized piece of User Space.

    Manage the range of numbers [start, start + size - 1]. 

    <public interval methods>= (U->) [D->]

intervals(int start, unsigned size);

    Allocate the subrange [start, start + size - 1]; returning true if such a subrange exists, false otherwise. 

    <public interval methods>+= (U->) [<-D->]

bool get(unsigned size, int & start);

    Return the allocated subrange beginning at start to the list of available ranges. 

    <public interval methods>+= (U->) [<-D]

void put(int start);


    <interval routines>= (U->) [D->]

intervals::intervals(int start, unsigned size) {
  assert(size > 0);
  free.insert(interval(start, start + size - 1));
  }
    Defines intervals (links are to index).

    The caller is looking for an interval of size size. If such an interval is free, store the interval's left-endpoint in start and return true; if no such interval exists, return false.

    get() uses first fit to find an interval of the proper size. 

    <interval routines>+= (U->) [<-D->]

bool intervals::get(unsigned size, int & start) {

  <find a big-enough interval>

  const interval r = *i;

  <move the interval from free to in-use>

  return true;
  }
    Defines get (links are to index).

    Search the free list for an interval that's at least as large as the requested size. If no such interval exists, return false. The search is first fit, which probably isn't the best algorithm to use, but is the simplest to implement. 

    <find a big-enough interval>= (<-U)

iset_citr e = free.end();
iset_itr i = find_if(free.begin(), e, bigint(size));
if (i == e) return false;

    Remove the allocated interval r from the free list. If r is eaxctly the right size, put r in the in-use list; otherwise, split r into an exact-sized interval, which goes on the in-use list, and a left-over interval, which goes back on the free list. 

    <move the interval from free to in-use>= (<-U)

free.erase(i);
if (r.size() == size)
  in_use.insert(r);
else {
  in_use.insert(interval(r.left, r.left + size - 1));
  free.insert(interval(r.left + size, r.right));
  }
start = r.left;

    The allocated interval starting at start is no longer needed; return it to the free list. 

    <interval routines>+= (U->) [<-D->]

void intervals::put(int start) {

  iset_citr e = in_use.end();

  <find the allocated interval>
  <find the free-list insert point>
  <merge with the left interval>
  <merge with the right interval>
  <re-assign the freed interval>
  }
    Defines put (links are to index).

    The interval must be on the in-use list; find it. Die if the interval can't be found. 

    <find the allocated interval>= (<-U)

iset_itr i = find_if(in_use.begin(), e, sameint(start));
assert(i != e);

    Find the insertion point for the interval in the free list. i points to the interval that will follow the new interval after the new interval's been inserted into the free list. 

    <find the free-list insert point>= (<-U)

interval r = *i; 
iset_itr l = lower_bound(free.begin(), free.end(), r);

    If there's an interval to the left of the new interval on the free list, see if the two are adjacent intervals; if they are, merge them:

    [oldl, newl - 1][newl, newr] -> [oldl, newr] 
    <merge with the left interval>= (<-U)

if (l != free.begin()) {
  iset_itr p = l;
  p--;
  if (p->right + 1 == r.left) {
    r.left = p->left;
    free.erase(p);
    }
  }

    If there's an interval to the right of the new interval on the free list, see if the two are adjacent intervals; if they are, merge them. 

    <merge with the right interval>= (<-U)

if (l != e) {
  if (r.right + 1 == l->left) {
    r.right = l->right;
    free.erase(l);
    }
  }

    Remove the interval from the in-use list and add it to the free list. 

    <re-assign the freed interval>= (<-U)

in_use.erase(i);
free.insert(r);

    Run the interval code through some simple tests. 

    <interval routines>+= (U->) [<-D]

#ifdef TESTING

// g++ -g -o itst -DTESTING intervals.cc

#include <cstdlib>


int main(void) {

  const unsigned max = 32;
  intervals mm(0, max);
  int s;

  assert(!mm.get(max + 1, s));
  assert(mm.get(max, s));
  for (unsigned i = 1; i < max + 2; i++)
    assert(!mm.get(i, s) && (s == 0));
  mm.put(s);

  for (unsigned i = 0; i < max; i++)
    assert(mm.get(1, s));
  assert(!mm.get(1, s));
  for (unsigned i = 0; i < max; i += 2)
    mm.put(i);
  assert(!mm.get(2, s));
  for (unsigned i = 1; i < max; i += 2)
    mm.put(i);
  assert(mm.get(max, s) && (s == 0));

  return EXIT_SUCCESS;
  }

#endif


    <intervals.cc>=

#include "intervals.h"
#include <algorithm>

<interval routines>

    A single interval is a straightforward data structure: two integers represent the left and right ends of the interval. An interval is closed at both ends; that is, an interval [l, r] represents all intergers i such that l <= i <= r. The less-than operator orders two intervals based on end-point relation, and a size function return an interval's size, the number of integers encompassed by the range. 

    <the interval representation>= (U->)

struct interval {
  interval(int l, int r) : left(l), right(r) { assert(l <= r); }
  int left, right;
  bool operator<(const interval & i) const { return right < i.left; }
  unsigned size(void) const { return right - left + 1; }
  };
    Defines interval (links are to index).

    <private interval methods>= (U->)

typedef std::set<interval>   iset;
typedef iset::iterator       iset_itr;
typedef iset::const_iterator iset_citr;

iset free, in_use;
    Defines free, in_use, iset, iset_citr, iset_itr (links are to index).

    sameint is a predicate (after a fashion) that returns true if and only if the interval i starts (has a left end) equal to start. Because intervals don't overlap, if two intervals agree at their left end (or right end, for that matter), they must be the same interval. 

    <an interval identity predicate>= (U->)

struct sameint {
  int start;
  sameint(int s) : start(s) { }
  bool operator()(const interval & i) const { 
    return i.left == start;
    }
  };
    Defines sameint (links are to index).

    bigint is a predicate (after a fashion) that returns true if and only if the interval i is no smaller than size. 

    <an interval size predicate>= (U->)

struct bigint {
  unsigned size;
  bigint(unsigned s) : size(s) { }
  bool operator()(const interval & i) const { 
    return i.size() >= size;
    }
  };
    Defines bigint (links are to index).

    <intervals.h>=

#ifndef _intervals_h_defined_
#define _intervals_h_defined_

#include <set>

class intervals {

  public:

    <public interval methods>

  private:

    <the interval representation>
    <an interval identity predicate>
    <an interval size predicate>
    <private interval methods>
  };

#endif

    The Process Table

    A process can be in one of three states. 
    <process data structures>= (U->) [D->]
enum process_status {
  sleeping,
  ready,
  executing
  };
    Defines process_status (links are to index).

    Each process-table entry keeps track of basic information on a process. 

    <process-table entry state>= (U->)

unsigned       id;
process_status status;
word           registers[next_register];

    On a context switch, information has to be saved and restored for the two processes involved. 

    <process state transfer>= (U->)

void save_state(void) {
  for (address a = 0; a < next_register; a++)
    fetch(a, registers[a], save_state);
  }

void restore_state(void) const {
  for (address a = 0; a < next_register; a++)
    store(a, registers[a], restore_state);
  }

    %define save_state restore_state Each process gets a process id, which is assigned when the process-table entry is created. 

    <process data structures>+= (U->) [<-D->]

struct process_table_entry {

  static unsigned next_id;
  process_table_entry() : id(next_id++) { }

  <process-table entry state>

  <process state transfer>
  };
    Defines process_table_entry (links are to index).

    Process-table entries are kept in a list called ptab. 

    <process data structures>+= (U->) [<-D]

typedef std::list<process_table_entry>  process_table;
typedef process_table::iterator         ptab_iter;
typedef process_table::const_iterator   ptab_citer;
    Defines process_table, ptab_citer, ptab_iter (links are to index).

    <proc-tab.h>=

#ifndef _proc_tab_h_defined_
#define _proc_tab_h_defined_

#include <list>
#include "os.h"

<process data structures>

#endif
    Defines proc-tab.h (links are to index).

    User-Space Management

    The interval data structure useful for keeping track of free space in User Space, but slightly inconvienent because it deals only with a sequence of integers, while User Space is more apropriately represented as a sequence of blocks.

    The User-Space management routines are a simple wrapper around intervals that let the rest of the operating system manipulate free space in terms of blocks in User Space. 

    <us-mgt.h>=

#ifndef _us_mgt_h_defined_
#define _us_mgt_h_defined_

#include "system.h"

extern bool us_alloc(unsigned, address &);
extern void us_free(address);

#endif


    <us-mgt.cc>=

#include "us-mgt.h"
#include "intervals.h"


// A model of user-space allocation.  Primary store is broken up into blocks
// the same size as disk blocks; the first (lowest address) block is 0.

   static intervals us_blocks(0, (dev_base - usr_base)/disk_block_size);


bool us_alloc(unsigned size, address & start) {
  int i;
  if (!us_blocks.get(size, i)) return false;
  start = usr_base + i*disk_block_size;
  return true;
  }


void us_free(address start) {
  us_blocks.put((start - usr_base)/disk_block_size);
  }

    OS Utilities

    These are some macros defined to provide a simpler and more straightforward access to various simulator routines.

    Procedure _w calls fetch() (store()) to read (write) the value _v from (into) Primary Store address _a. If the Primary-Store access fails, the system dies with an error message. 

    <os.h utilities>= (U->) [D->]

#define fetch(_a, _v, _w) \
  do if (mem_fetch(_a, _v) != Memory::ok) \
       panic(#_a " fetch failed in " #_w "()"); while (false)

#define store(_a, _v, _w) \
  do if (mem_store(_a, _v) != Memory::ok) \
       panic(#_a " store failed in " #_w "()"); while (false)

    Procedure _w calls disk_op() to perform the disk operation _c between Primary-Store address _a and disk block _b. The system dies with an error message if if anything untoward happens while accessing the disk registers. 

    <os.h utilities>+= (U->) [<-D->]

#define disk_op(_c, _b, _a, _w) \
  do { store(disk_block_register, _b, _w); \
       store(disk_address_register, _a, _w); \
       store(disk_command_register, _c, _w); } while (false)

    Define some more memorable names for the debugging flags used by the operation system. Unfortunately, the more memorable names can't be used with the -D option on the simulator command line. 

    <os.h utilities>+= (U->) [<-D]

#define dbp_sleep       dbp_f31
#define dbp_execute     dbp_f30
#define dbp_syscall     dbp_f29


    <os.h>=

#ifndef _os_h_defined_
#define _os_h_defined_

#include <iostream>
#include "mass.h"
#include "utils.h"

<os.h utilities>

extern unsigned read_clock(void);

#endif

    Index

    This page last modified on 15 November 2000.