Table of Contents

• Introduction
• The Scheduler
• The Sleeper
• The Program Loader
• The Reboot Interrupt Handler
• Utilities
  • Intervals
  • The Process Table
  • User-Space Management
  • OS Utilities
• Index

The operating system's principle objective is that it correctly execute all the batch programs, a secondary objective is that it manage the computing system resources with high throughput and minimal idle time.

Breaking the problem up into pieces, there seems to be three major parts of the computing hardware that need to be dealt with: the disk, which contains the programs, the CPU, which executes the programs, and the clock, which times the sleeping processes. These three parts don't make up all the hardware, but they are the crucial parts in that they need to be managed efficiently (the CPU) or they have their own behaviors that need to be dealt with (the disk and clock interrupts).

It seems a sensible first-cut design to have the structure of the operating system echo the three-part hardware division. The operating system would have three components, each of which deals with one of the three hardware parts identified in the previous paragraph. There would be other components to carry out various other operating-system functions, but the disk, cpu, and clock components would be the central components around which the rest of the operating system is built.

The function of each operating-system component would be related to its associated hardware component. The disk component would be responsible for reading in programs from the disk and storing them in Primary Store; the CPU component would be responsible for shuffling processes into and out of the CPU; and the clock component would be responsible for taking care of the clock and sleeping processes.

These three components have to interact with each other to carry out their tasks. For example, the disk component will have to tell the CPU component when a new process is available for execution. The clock component will also have to tell the CPU component when the current process needs to be swapped out of the CPU because its exited or sleeping. In addition, the the scheduler has to tell the disk component when an exiting process frees up more program storage space.

The code given on this page follows the brief design outline given above. The three main software components are the scheduler (the CPU manager), the program loader (the disk manager) and the sleeper (the clock manager). In addition, there are other components to take care of system initialization and system calls, as well as providing support routines.

The Scheduler

• start_scheduler() - initializes the scheduler.

• poke_scheduler() - notify the scheduler that the process table's changed.

• scheduler_done() - true if the scheduler's done.

• halt() - halt the system.

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

extern void poke_scheduler(void);
extern void start_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->)

ptab_iter running_process;
static ptab_iter idle_process;
unsigned process_table_entry::next_id = 0;

Defines idle_process (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 an 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;

  <handle the process table change>
  }

Defines poke_scheduler (links are to index).

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

<handle the process table change>= (U->) [D->]

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 bowed out), find a ready process and run that. There should always be a ready process because the idle process is always ready.

<handle the process table change>+= (U->) [<-D]

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>=

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_process = ptab.insert(ptab.begin(), idle_pte);

  load_cpu(idle_process);
  }

Defines start_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 <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 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.

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

#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(0)

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 sleeper routines>+= (U->) [<-D->]

void do_sleep(int delta) {

  const unsigned c = read_clock();

  <handle a sleep request>
  }

Defines do_sleep (links are to index).

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

<handle a sleep request>= (U->) [D->]

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.

<handle a sleep request>+= (U->) [<-D->]

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

Save the executing process' state, change its status, and inform the scheduler of the change to the executing process.

<handle a sleep request>+= (U->) [<-D]

running_process->save_state();
running_process->status = sleeping;
poke_scheduler();

That's it for the sleep system call.

countdown_ih() is the countdown-interrupt handler.

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

void countdown_ih(void) {

  const unsigned now = read_clock();

  <handle a countdown interrupt>
  }

Defines countdown_ih (links are to index).

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

<handle a countdown interrupt>= (<-U) [D->]

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.

<handle a countdown interrupt>+= (<-U) [<-D->]

do {
  sleeper s = wake_up_calls.top();
  debugp(dbp_sleep,
         "At time %d, process %d wakes up.\n", now, get_sleeper(s)->id);
  get_sleeper(s)->status = ready;
  wake_up_calls.pop();
  }
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.

<handle a countdown interrupt>+= (<-U) [<-D->]

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

Let the scheduler know about the new ready-to-execute processes.

<handle a countdown interrupt>+= (<-U) [<-D->]

poke_scheduler();

That's it for the countdown interrupt; back to the user process.

<handle a countdown interrupt>+= (<-U) [<-D]

return;

<sleeper.cc>=

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

<representing sleeping processes>

<the sleeper routines>

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

start_pgm_loader() - the disk interrupt handler for the program index block.

pgm_loader_done() - indicates when program loading is done.

poke_pgm_loader() - wake up the program loader.

<the program loader interface>= (U->) [D->]

extern void start_pgm_loader(void);
extern bool pgm_loader_done(void);
extern void poke_pgm_loader(void);

Also available is a constant indicating to where in user space the program-index block will be read.

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

const address pgm_index_address = usr_base;

Defines pgm_index_address (links are to index).

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).

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->) [D->]

#  define check_disk_io(_w) \
    do {word w; fetch(disk_status_register, w, _w); \
        if (w != disk_io::ok) \
          panic("disk read failed with status %d", w); } while (false)

Defines check_disk_io (links are to index).

pgm_loader() is the disk-interrupt handler that gets called when the disk read for a batch-program block is finished.

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

static void pgm_loader(void) {

  check_disk_io(pgm_loader);

  <handle a disk interrupt>
  }

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

<handle a disk interrupt>= (U->) [D->]

if (program_blocks_read-- > 0) {
  disk_op(disk_io::read, next_disk_block + program_blocks_read,
          new_pte.registers[base_register] + program_blocks_read*disk_block_size,
          disk_ih);
  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.

<handle a disk interrupt>+= (U->) [<-D->]

pgm_load_in_progress = false;
new_pte.status = ready;
ptab.push_front(new_pte);
poke_scheduler();

Start reading in the next program, if any.

<handle a disk interrupt>+= (U->) [<-D->]

poke_pgm_loader();

That's it for the disk interrupt - back to the user process.

<handle a disk interrupt>+= (U->) [<-D]

return;

start_pgm_loader() 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 pgm_index_address.

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

void start_pgm_loader(void) {

  check_disk_io(disk_ih);

  <handle the program-index disk interrupt>
  }

Defines start_pgm_loader (links are to index).

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

<handle the program-index disk interrupt>= (U->) [D->]

unsigned nxt_blk = 1;
for (unsigned i = 0; i < disk_block_size; i++) {
  word s;
  fetch(pgm_index_address + i, s, start_pgm_loader);
  if (s == 0) break;
  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.

<handle the program-index disk interrupt>+= (U->) [<-D->]

poke_pgm_loader();
if (pgm_loader_done()) halt();

That's it for the disk interrupt; back to the user process.

<handle the program-index disk interrupt>+= (U->) [<-D]

return;

poke_pgm_loader() 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).

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

void poke_pgm_loader(void) {
  <take advantage of new user space>
  }

Defines poke_pgm_loader (links are to index).

If a program load is already in progress, the new user space will be dealt with when the current program load is done.

<take advantage of new user space>= (U->) [D->]

if (pgm_load_in_progress)
  return;

If there's no more programs to load, there's nothing to do.

<take advantage of new user space>+= (U->) [<-D->]

if (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.

<take advantage of new user space>+= (U->) [<-D->]

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.

<take advantage of new user space>+= (U->) [<-D->]

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;

Read in blocks associated with the next batch program.

<take advantage of new user space>+= (U->) [<-D->]

pgm_load_in_progress = true;
program_blocks_read = get_block_cnt(pdi) - 1;
next_disk_block = get_block_no(pdi);
disk_op(disk_io::read, next_disk_block + program_blocks_read,
        pgm_start + program_blocks_read*disk_block_size,
        disk_ih);

All further disk interrupts get handled by the program loader.

<take advantage of new user space>+= (U->) [<-D]

mass.memory->set_ihandler(disk_i, pgm_loader);

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.

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

bool pgm_loader_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"

<program loader data structures>

<program loader procedures>

Defines pgm-loader.cc (links are to index).

<pgm-loader.h>=

#ifndef _pgm_loader_h_defined_
#define _pgm_loader_h_defined_

#include "system.h"

<the program loader interface>

#endif

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

The Reboot Interrupt Handler

<os start-up procedures>= (U->) [D->]

static void syscall_ih(void) {

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

  if (syscall_code == system_call::exit) {
    <handle an exit system call>
    }
  else if (syscall_code == system_call::sleep) {
    <handle a sleep system call>
    }
  else 
    panic("unknown system call type %d in syscall_ih()", syscall_code);
  }

Defines syscall_ih (links are to index).

The exit system call. The current process is done; drop it 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.

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

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

ptab.erase(running_process);
poke_scheduler();
poke_pgm_loader();

If the scheduler and the program loader are done, then we are outta here.

<handle an exit system call>+= (<-U) [<-D]

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);

What to do when the system boots (or reboots).

<os start-up procedures>+= (U->) [<-D->]

void reboot_ih(void) {
  <initialize interrupt handlers>
  <initialize disk i-o>
  <initialize the scheduler>
  }

Defines reboot_ih (links are to index).

Install the interrupt handlers.

<initialize interrupt handlers>= (<-U)

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

Start reading the program index from disk into the first block of user space.

<initialize disk i-o>= (<-U)

disk_op(disk_io::read, 0, usr_base, reboot_ih);

Start the scheduler, and return to the user process (the idle process, created and run by start_scheduler()).

<initialize the scheduler>= (<-U)

start_scheduler();
return;

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

<os start-up procedures>+= (U->) [<-D]

unsigned read_clock(void) {
  word c;
  fetch(clock_register, c, read_clock);
  return c;
  }

Defines read_clock (links are to index).

<pa1-os.cc>=

#include "os.h"
#include "pgm-loader.h"
#include "scheduler.h"
#include "sleeper.h"

<os start-up procedures>

Defines pa1-os.cc (links are to index).

Utilities

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 the first-fit strategy to find an interval of the proper size.

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

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

  iset_citr e = free.end();

  for (iset_itr i = free.begin(); i != e; i++) {
    const interval r = *i;
    const unsigned rs = r.size();
    <is r an exact fit?>
    <is r larger than needed?>
    }
  return false;
  }

Defines get (links are to index).

If the free interval r is exactly the size needed, shift it from the free list to the in-use list and return it.

<is r an exact fit?>= (<-U)

if (rs == size) {
  free.erase(i);
  in_use.insert(r);
  start = r.left;
  return true;
  }

If the free interval r is larger than the size needed, chop it down to size and allocate the right-sized piece, moving it from the free list to the in-use list.

<is r larger than needed?>= (<-U)

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

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 would follow the new interval when 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: to integers to represent the left and right ends of the interval, a less-than operator to order the intervals, and a size function return an interval' size.

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

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).

sameint is a predicate that returns true if and only if the interval i starts (has a left end) equal to start.

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

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).

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

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).

<intervals.h>=

#ifndef _intervals_h_defined_
#define _intervals_h_defined_

#include <set>

class intervals {

  public:

    <public interval methods>

  private:

    <private interval methods>
  };

#endif

The Process Table

<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;
unsigned       disk_block_count;
unsigned       first_disk_block;                
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;
extern process_table ptab;

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).

<proc-tab.cc>=

#include "proc-tab.h"

// Where the processes are.

   process_table ptab;

// A pointer to the idle process.

   ptab_iter idle_process;

User-Space Management

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

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

<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

• <find the allocated interval>: U1, D2
• <find the free-list insert point>: U1, D2
• <handle a countdown interrupt>: U1, D2, D3, D4, D5, D6
• <handle a disk interrupt>: U1, D2, D3, D4, D5
• <handle a sleep request>: U1, D2, D3, D4
• <handle a sleep system call>: U1, D2
• <handle an exit system call>: U1, D2, D3
• <handle the process table change>: U1, D2, D3
• <handle the process table changes>: D1
• <handle the program-index disk interrupt>: U1, D2, D3, D4
• <initialize disk i-o>: U1, D2
• <initialize interrupt handlers>: U1, D2
• <initialize the scheduler>: U1, D2
• <interval routines>: D1, D2, D3, D4, U5
• <intervals.cc>: D1
• <intervals.h>: D1
• <is r an exact fit?>: U1, D2
• <is r larger than needed?>: U1, D2
• <merge with the left interval>: U1, D2
• <merge with the right interval>: U1, D2
• <os start-up procedures>: D1, D2, D3, U4
• <os.h>: D1
• <os.h utilities>: D1, D2, D3, U4
• <pa1-os.cc>: D1
• <pgm-loader.cc>: D1
• <pgm-loader.h>: D1
• <private interval methods>: D1, D2, D3, U4
• <process data structures>: D1, D2, D3, U4
• <process state transfer>: D1, U2
• <process-table entry state>: D1, U2
• <proc-tab.cc>: D1
• <proc-tab.h>: D1
• <program loader data structures>: D1, D2, D3, D4, D5, D6, U7
• <program loader procedures>: D1, D2, D3, D4, D5, U6
• <public interval methods>: D1, D2, D3, U4
• <re-assign the freed interval>: U1, D2
• <representing sleeping processes>: D1, D2, D3, U4
• <scheduler.cc>: D1
• <scheduler.h>: D1
• <sleeper.cc>: D1
• <sleeper.h>: D1
• <take advantage of new user space>: U1, D2, D3, D4, D5, D6, D7
• <the program loader interface>: D1, D2, U3
• <the scheduler data structures>: D1, U2
• <the scheduler interface>: D1, D2, U3
• <the scheduler routines>: D1, D2, D3, D4, D5, D6, U7
• <the sleeper interface>: D1, U2
• <the sleeper routines>: D1, D2, D3, U4
• <us-mgt.cc>: D1
• <us-mgt.h>: D1

• check_disk_io: D1, U2, U3
• countdown_ih: U1, D2, U3, U4
• do_sleep: U1, D2, U3, U4
• free: U1, U2, U3, U4, U5, U6, U7, U8, D9
• get: U1, D2, U3, U4
• get_block_cnt: D1, U2, U3, U4
• get_block_no: D1, U2
• halt: U1, D2, U3, U4
• idle_process: D1, U2, U3, U4
• interval: U1, U2, U3, U4, D5, U6, U7
• intervals: U1, D2, U3, U4, U5, U6, U7, U8
• in_use: U1, U2, U3, U4, U5, D6
• iset: D1
• iset_citr: U1, U2, D3
• iset_itr: U1, U2, U3, U4, D5
• load_cpu: D1, U2, U3, U4
• new_pte: D1, U2, U3, U4
• next_disk_block: D1, U2, U3
• pa1-os.cc: D1
• pgm_disk_info: D1, U2, U3, U4
• pgm_index: D1, U2, U3, U4, U5
• pgm_index_address: D1, U2
• pgm_loader: D1, U2
• pgm-loader.cc: D1
• pgm_loader_done: U1, U2, D3, U4
• pgm-loader.h: U1, D2, U3
• pgm_load_in_progress: D1, U2, U3, U4, U5
• poke_pgm_loader: U1, U2, U3, D4, U5
• poke_scheduler: U1, D2, U3, U4, U5, U6, U7
• process_status: D1, U2
• process_table: D1, U2
• process_table_entry: U1, U2, U3, U4, U5, D6, U7
• proc-tab.h: U1, U2, D3, U4
• program_blocks_read: D1, U2, U3
• ptab_citer: D1
• ptab_iter: U1, U2, U3, U4, U5, D6, U7
• put: U1, D2, U3, U4
• read_clock: U1, U2, U3, U4, U5, D6, U7
• readyp: D1, U2, U3
• reboot_ih: D1, U2
• runningp: D1, U2
• sameint: U1, D2
• schedule_countdown: D1, U2, U3
• scheduler.cc: D1
• scheduler_done: U1, D2, U3
• scheduler.h: U1, D2, U3, U4, U5
• sleeper.cc: D1
• sleeper.h: U1, D2, U3
• start_pgm_loader: U1, D2, U3, U4
• start_scheduler: U1, D2, U3
• syscall_ih: D1, U2, U3

This page last modified on 19 October 2000.