Circles represent operating-system manager software; non circles represent resources, either hardware (such as the disk) or software (exited processes). Arrows between managers indicate interactions via subroutine calls; the caller is pointing and the called is being pointed at. The labels associated with each arrow gives the system event that triggers the subroutine call. For example the arrow labeled "Exit" from the Process Manager to the Disk Manager indicates that the Process Manager makes a subroutine call to the Disk Manager (via a routine provided by the Disk Manager) whenever a process exits the system.

The disk manager is responsible for loading programs. The interrupt handler is responsible for initializing the other managers on system boot-up; these interactions are not shown in the diagram.

<interrupt handlers>= (U->) [D->]

void interrupt_handler(interrupt_types i) {

  switch (i) {
    case disk_i:
      disk::ihandler();
      break;

    case reboot_i:
      reboot_ih();      
      break;

    case system_call_i:
      syscall_ih();
      break;

    default:
      panic("Unrecognized interrupt %d in interrupt_handler()", i);
    }

  if (process::done() and disk::idle())
     process::halt();
  }

Defines interrupt_handler (links are to index).

<interrupt handlers>+= (U->) [<-D->]

static void syscall_ih(void) {

  word w;
  fetch_mem(0, w, syscall_ih);
  switch (w) {

    case system_call::exit:
      fetch_mem(1, w, syscall_ih);
      process::exit(w);
      break;

    case system_call::fork:
      fetch_mem(1, w, syscall_ih);
      disk::load(w);
      break;

    case system_call::join:
      fetch_mem(1, w, syscall_ih);
      process::join(w);
      break;

    default:
      store_mem(0, status::bad_system_call, syscall_ih);
    }
  }

Defines syscall_ih (links are to index).

<interrupt handlers>+= (U->) [<-D]

void reboot_ih(void) {
  process::init();
  storage::init(usr_base, usr_size/disk_block_size);
  disk::init();
  }

Defines reboot_ih (links are to index).

*

<interrupts.cc>=

#include "os.h"
#include "disk.h"
#include "storage.h"
#include "process.h"

// Deja vu c++ style.

static void reboot_ih(void);
static void syscall_ih(void);

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

<interrupt handlers>

Defines interrupts.cc (links are to index).

<process interface declarations>= (U->) [D->]

typedef unsigned id;

Defines process::id (links are to index).

<process interface declarations>+= (U->) [<-D->]

id add(const storage::chunk &, id = 0);

void exit(word);
void join(id);

<process interface declarations>+= (U->) [<-D->]

void init(void);
bool done(void);
void halt(void);

<process interface declarations>+= (U->) [<-D->]

id block(void);
void ready(id pid);

<process interface declarations>+= (U->) [<-D]

void put_register(id pid, unsigned r, word v);

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

enum process_status {
  proc_ready     = 0x01,
  proc_executing = 0x02,
  proc_blocked   = 0x04,
  proc_exited    = 0x08
  };

Defines process_status (links are to index).

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

struct process_table_entry {

  static process::id next_id;
  process_table_entry() : id(next_id++), joiner_waiting(false) { }
  
  const process::id id;
  process_status    status;
  word              registers[next_register];
  word              exit_value;
  storage::chunk    sc;
  bool              joiner_waiting;
  process::id       joiner_pid;

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

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

unsigned process_table_entry::next_id = 1000;

Defines process_table_entry, restore_state, save_state (links are to index).

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

typedef std::list<process_table_entry>  process_table;
typedef process_table::iterator         ptab_iter;

static process_table ptab;
static ptab_iter running_process;
static ptab_iter idle_process;

Defines idle_process, process_table, ptab, ptab_iter, running_process (links are to index).

<process procedure definitions>= (U->) [D->]

static void load_cpu(ptab_iter & pi) {

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

  debugp(dbp_execute, dbpe_format "runs.\n", 
         read_clock(), running_process->id);
  }

Defines load_cpu (links are to index).

<process procedure definitions>+= (U->) [<-D->]

static unsigned status_count(process_status status_flags) {

  unsigned i = 0;

  for (ptab_iter ptabi = ptab.begin(); ptabi != ptab.end(); ptabi++)
    if (ptabi->status & status_flags)
      i++;

  return i;
  }

Defines status_count (links are to index).

<process procedure definitions>+= (U->) [<-D->]

static bool matching_pid(const process_table_entry pte, process::id pid) {
  return pte.id == pid;
  }

ptab_iter find_proc(process::id pid) {
  
  const ptab_iter & e = ptab.end();
  ptab_iter i = find_if(ptab.begin(), e, bind2nd(ptr_fun(matching_pid), pid));

  if (i == e)
    oops("Can't find the process with process-id %d", pid);

  return i;
  }

Defines find_proc (links are to index).

<process procedure definitions>+= (U->) [<-D->]

bool exists_proc(process::id pid) {
  const ptab_iter & e = ptab.end();
  return find_if(ptab.begin(), e, bind2nd(ptr_fun(matching_pid), pid)) != e;
  }

Defines exists_proc (links are to index).

<process procedure definitions>+= (U->) [<-D->]

static bool readyp(process_table_entry & pte) { 
  return pte.status == proc_ready;
  }

static bool runningp(process_table_entry & pte) { 
  return pte.status == proc_executing;
  }

Defines readyp, runningp (links are to index).

<process procedure definitions>+= (U->) [<-D->]

static void reschedule(void) {

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

  if (idle_process->status == proc_executing) {
    <re-schedule the idle process, if possible>
    }
  else {
    <schedule a running process, if necessary>
    }
  }

Defines reschedule (links are to index).

<re-schedule the idle process, if possible>= (<-U)

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

<schedule a running process, if necessary>= (<-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 process::reschedule()");
  load_cpu(next_process);
  }

<process procedure definitions>+= (U->) [<-D]

static void ready_proc(ptab_iter ptei) {
  ptei->status = proc_ready;
  reschedule();
  }

Defines ready_proc (links are to index).

<process interface definitions>= (U->) [D->]

id add(const storage::chunk & sc, id parent) {

  process_table_entry new_pte;
  const address a = storage::chunk_address(sc);

  if (parent) {
    ptab_iter old_ptei = find_proc(parent);
    for (unsigned i = 0; i < next_register; i++)
      new_pte.registers[i] = old_ptei->registers[i];
    }

  new_pte.registers[base_register] = a;
  new_pte.registers[top_register] = 
    a + storage::chunk_size(sc)*disk_block_size;
  new_pte.registers[pc_register] = a;
  new_pte.registers[sw_register] = 0;
  new_pte.sc = sc;

  ptab.push_front(new_pte);
  ready_proc(ptab.begin());

  return new_pte.id;
  }

Defines process::add (links are to index).

<process interface definitions>+= (U->) [<-D->]

id block(void) {
  running_process->save_state();
  running_process->status = status;
  process::id pid = running_process->id;

  reschedule();

  return pid;
  }

Defines process::block (links are to index).

<process interface definitions>+= (U->) [<-D->]

bool done(void) {
  return status_count(static_cast<process_status>(proc_ready | proc_executing)) < 2;
  }

Defines process::done (links are to index).

If a process is waiting to join with the exiting process

<process interface definitions>+= (U->) [<-D->]

void exit(word eval) {

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

  storage::release(running_process->sc);
  disk::poke();

  <handle a join>

  reschedule();
  }

Defines process::exit (links are to index).

<handle a join>= (<-U)

if (running_process->joiner_waiting) {
  const ptab_iter joiner = find_proc(running_process->joiner_pid);
  joiner->registers[0] = status::ok;
  joiner->registers[1] = eval;
  joiner->status = proc_ready;

  debugp(dbp_forkjoin, 
         "At time %4d, process %2d joins with exited process %2d, passing value %d.\n", 
         read_clock(), running_process->joiner_pid, running_process->id, eval);

  ptab.erase(running_process);
  }
else {
  running_process->status = proc_exited;
  running_process->exit_value = eval;
  }

<process interface definitions>+= (U->) [<-D->]

void join(id pid) {

  if (!exists_proc(pid)) {
    store_mem(0, status::bad_id, proc::join);
    return;
    }

  ptab_iter ptei = find_proc(pid);
  if (ptei->joiner_waiting) {
    store_mem(0, status::bad_id, proc::join);
    return;
    }

  debugp(dbp_forkjoin, "At time %4d, process %2d waits to join with process %2d.\n", 
         read_clock(), running_process->id, pid);

  <do a join>
  }

Defines process::join (links are to index).

<do a join>= (<-U)

if (ptei->status == proc_exited) {
  debugp(dbp_forkjoin, "At time %4d, process %2d joins with process %2d passing value %d.\n", 
         read_clock(), running_process->id, pid, ptei->exit_value);
  store_mem(0, status::ok, proc::join);
  store_mem(1, ptei->exit_value, proc::join);
  ptab.erase(ptei);
  }
else {
  ptei->joiner_waiting = true;
  ptei->joiner_pid = running_process->id;
  process::block(proc_blocked);
  }

Halting the system has pie-like easiness.

<process interface definitions>+= (U->) [<-D->]

void halt(void) { 
  store_mem(halt_register, 0, halt);
  } 

Defines process::halt (links are to index).

<process interface definitions>+= (U->) [<-D->]

void init(void) {

  process_table_entry idle_pte;
  idle_pte.status = proc_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 process::init (links are to index).

<process interface definitions>+= (U->) [<-D->]

void put_register(id pid, unsigned r, word v) {
  assert(r < next_register);
  ptab_iter pti = find_proc(pid);
  pti->registers[r] = v;
  }

Defines process::put_register (links are to index).

<process interface definitions>+= (U->) [<-D]

void ready(id pid) {
  find_proc(pid)->status = proc_ready;
  reschedule();
  }

Defines process::ready (links are to index).

*

<process.h>=

#ifndef _process_h_defined_
#define _process_h_defined_

#include "storage.h"

namespace process {
  <process interface declarations>
  };

#endif

<process.cc>=

#include <algorithm>
#include <list>
#include <functional>
#include "process.h"
#include "disk.h"
#include "storage.h"
#include "os.h"

using std::ptr_fun;
using std::bind2nd;

#define dbpe_format "At time %4d, process %2d "

<process data structures>

<process procedure definitions>

namespace process {
  <process interface definitions>
  }

Defines process.cc, process.h (links are to index).

• init() initializes the disk manager.

• ihandler() handles disk interrupts.

• load() reads a program from disk and schedules it for execution.

• poke() wakes up the disk manager in case it's been suspended until more resources (usually User Space) become available.

• idle() returns true if the disk manager has no programs to load.

<disk interface declarations>= (U->)

void init(void);
void ihandler(void);
void load(unsigned);
void poke(void);
bool idle(void);

<disk interface definitions>= (U->) [D->]

  void init(void) {
    next_block_to_read = 0;
    next_program_address = usr_base;
    program_being_read = true;
    disk_read(disk::init);
    }

Defines disk::init (links are to index).

<disk procedure definitions>= (U->) [D->]
static void handle_index_block(void) {

  check_disk_error(handle_index_block);

  unsigned start = 1;

  for (unsigned i = 0; i < disk_block_size; i++) {
    word w;
    fetch_mem(next_program_address + i, w, handle_index_block);
    if ((w < 0) or (w > usr_size/disk_block_size))
      panic("invalid program size %d read from batch disk", w);
    if (w == 0)
      break;
    program_index.push_back(program_location(w, start));
    start += w;
    }

  program_being_read = false;
  if (!program_index.empty())
    queue_request(0, 0);
  }

Defines handle_index_block (links are to index).

<disk interface definitions>+= (U->) [<-D->]

void load(unsigned i) {  

  if (i >= program_index.size())
    store_mem(0, status::bad_id, syscall_ih);
  else
    queue_request(i, process::block());
  }

Defines disk::load (links are to index).

<disk interface definitions>+= (U->) [<-D->]

void poke(void) {

  if (load_requests.empty() or program_being_read)
    return;

  const program_location & pl = program_index[load_requests.front().pno];

  program_chunk = storage::get_chunk(pl.size);
  if (storage::chunk_size(program_chunk) > 0) {
    program_being_read = true;
    blocks_to_read = pl.size - 1;
    next_block_to_read = pl.start + blocks_to_read;
    next_program_address = 
      storage::chunk_address(program_chunk) + blocks_to_read*disk_block_size;
    disk_read(poke);
    }
  }

Defines disk::poke (links are to index).

<disk interface definitions>+= (U->) [<-D->]

bool idle(void) {
  return load_requests.empty() and !program_being_read;
  }

Defines disk::idle (links are to index).

<disk interface definitions>+= (U->) [<-D]

void ihandler(void) {

  static bool first_time = true;

  if (first_time) {
    handle_index_block();
    first_time = false;
    }
  else
    handle_next_block();
  }

Defines disk::ihandler (links are to index).

<disk procedure definitions>+= (U->) [<-D->]

static void queue_request(unsigned i, process::id parent) {
  load_requests.push_back(load_request(i, parent));
  disk::poke();
  }

Defines queue_request (links are to index).

<disk procedure definitions>+= (U->) [<-D]

static void handle_next_block(void) {

  check_disk_error(handle_next_block);

  if (blocks_to_read-- == 0) {
    <ready the new process>
    }
  else {
    next_block_to_read--;
    next_program_address -= disk_block_size;
    disk_read(handle_next_block);
    }
  }

Defines handle_next_block (links are to index).

<ready the new process>= (<-U)

assert(!load_requests.empty());
const load_request & req = load_requests.front();

if (req.pid != 0) {
  process::put_register(req.pid, 0, status::ok);
  process::put_register(req.pid, 1, process::add(program_chunk, req.pid));
  process::ready(req.pid);
  }
else 
  process::add(program_chunk);

load_requests.pop_front();
program_being_read = false;
disk::poke();

<disk macro definitions>= (U->) [D->]

#define check_disk_error(_caller) \
  do { \
    word w; \
    fetch_mem(disk_status_register, w, _caller); \
    if (w != status::ok)  \
      panic("disk read error %d in " #_caller "()", w); \
    } while (false)

Defines check_disk_error (links are to index).

<disk macro definitions>+= (U->) [<-D]

#define disk_read(_caller) \
  do { store_mem(disk_block_register, next_block_to_read, _caller); \
       store_mem(disk_address_register, next_program_address, _caller); \
       store_mem(disk_command_register, disk_io::read, _caller); } while (false)

Defines disk_read (links are to index).

The location information on programs in the batch disk are stored in a vector indexed by the program's index-block index.

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

struct program_location {
  unsigned start, size;
  program_location(unsigned size, unsigned start) 
    : start(start), size(size) { }
  };

static std::vector<program_location> program_index;

Defines program_index, program_location (links are to index).

• pno - the program-information index for the new process.

• pid - the forking process's (parent's) id. If there is no parent, pid is 0.

The program-load requests are queued in load_requests.

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

struct load_request {

  unsigned pno;
  process::id pid;

  load_request(unsigned pno, process::id pid) 
    : pno(pno), pid(pid) { }
  };

static std::deque<load_request> load_requests;

Defines load_request, load_requests (links are to index).

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

static bool program_being_read;

Defines program_being_read (links are to index).

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

static unsigned blocks_to_read;

Defines blocks_to_read (links are to index).

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

static unsigned next_block_to_read;

Defines next_block_to_read (links are to index).

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

static address next_program_address;

Defines next_program_address (links are to index).

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

storage::chunk program_chunk;

Defines program_chunk (links are to index).

*

<disk.h>=

#ifndef _disk_h_defined_
#define _disk_h_defined_

namespace disk {
  <disk interface declarations>
  };

#endif

<disk.cc>=

#include <vector>
#include <deque>
#include "os.h"
#include "disk.h"
#include "storage.h"
#include "process.h"

<disk manager data structures>

<disk macro definitions>

<disk procedure definitions>

namespace disk {
  <disk interface definitions>
  };

Defines disk.cc, disk.h (links are to index).

Correspondingly, the data representation for allocated storage is simple too. Each chunk of user space allocated to a program is represented by a pair of numbers giving the lowest user-space address and size of the chunk in disk blocks.

<storage-management interface definitions>= (U->) [D->]

 typedef std::pair<address, unsigned> chunk;

 inline address chunk_address(const chunk & sc) {
   return sc.first;
   }

 inline unsigned chunk_size(const chunk & sc) { 
   return sc.second;
   }

Defines chunk, chunk_address, chunk_size (links are to index).

<storage-management interface definitions>+= (U->) [<-D->]

 void init(address base, unsigned size);

<storage-management interface definitions>+= (U->) [<-D->]

 chunk get_chunk(unsigned);

<storage-management interface definitions>+= (U->) [<-D]

void release(const chunk & sc);

base_address keeps track of the lowest address in allocatable storage.

<allocatable-storage data structures>= (U->) [D->]

static std::vector<bool> free_blocks;

static address base_address;

Defines base_address, free_blocks (links are to index).

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

typedef std::pair<unsigned, unsigned> index_range;
#define range_start(_r) (_r).first
#define range_size(_r)  (_r).second

Defines index_range, range_size, range_start (links are to index).

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

static index_range sc2ir(const storage::chunk & sc) {
  return std::make_pair(
           (storage::chunk_address(sc) - base_address)/disk_block_size,
           storage::chunk_size(sc));
  }

static storage::chunk ir2sc(const index_range & ir) {
  return std::make_pair(base_address + range_start(ir)*disk_block_size, 
                        range_size(ir));
  }

Defines ir2sc, sc2ir (links are to index).

<storage routine definitions>= (U->) [D->]

static index_range find_free_range(unsigned size) {
  
  for (unsigned i = 0; i < free_blocks.size() - size + 1; i++)
    if (free_blocks[i]) {
      bool found = true;
      for (unsigned j = i + 1; (j < i + size) and found; j++)
        found = free_blocks[j];
      if (found) 
        return std::make_pair(i, size);
      }

  return std::make_pair(static_cast<unsigned>(0), static_cast<unsigned>(0));
  }

Defines find_free_range (links are to index).

<storage routine definitions>+= (U->) [<-D]

static void set_range(const index_range & ir, bool bv) {

  const unsigned e = range_start(ir) + range_size(ir);
  assert(e <= free_blocks.size());

  for (unsigned i = range_start(ir); i < e; i++) {
    assert(free_blocks[i] != bv);
    free_blocks[i] = bv;
    }
  }

#define release_range(_ir)  set_range(_ir, true)
#define allocate_range(_ir) set_range(_ir, false)

Defines allocate_range, release_range, set_range (links are to index).

<storage namespace definitions>= (U->) [D->]

void init(address start, unsigned size) {
  assert(size > 0);
  base_address = start;
  while (size-- > 0)
    free_blocks.push_back(true);
  }

Defines storage::init (links are to index).

<storage namespace definitions>+= (U->) [<-D->]

chunk get_chunk(unsigned s) {
  index_range free_range = find_free_range(s);
  allocate_range(free_range);
  return ir2sc(free_range);
  }

Defines storage::get_chunk (links are to index).

<storage namespace definitions>+= (U->) [<-D]

void release(const chunk & sc) {
  release_range(sc2ir(sc));
  }

Defines storage::release (links are to index).

<storage testing code>= (U->)

#ifdef TESTING_STORAGE

// g++ -DTESTING_STORAGE -g -o testing-storage -ansi -pedantic -Wall -I ../arch storage.cc && ./testing-storage

int main() {
  storage::init(1024, 32);
  storage::chunk sc = storage::get_chunk(32);
  assert(storage::chunk_address(sc) == 1024);
  assert(storage::chunk_size(sc) == 32);

  storage::chunk sc2 = storage::get_chunk(1);
  assert(storage::chunk_size(sc2) == 0);

  storage::release(sc);

  sc2 = storage::get_chunk(1);
  assert(storage::chunk_size(sc2) == 1);
  sc = storage::get_chunk(32);
  assert(storage::chunk_size(sc) == 0);
  sc = storage::get_chunk(31);
  assert(storage::chunk_size(sc) == 31);
  assert(storage::chunk_address(sc) == 1024 + disk_block_size);
  }

#endif

*

<storage.h>=

#ifndef _storage_h_defined_
#define _storage_h_defined_

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

namespace storage {
  <storage-management interface definitions>
  };

#endif

<storage.cc>=

#include <vector>
#include "storage.h"
#include <cassert>

<allocatable-storage data structures>

<storage routine definitions>

namespace storage {
  <storage namespace definitions>
  };

<storage testing code>

Defines storage.cc, storage.h (links are to index).

<os.h>=

#ifndef _os_h_defined_
#define _os_h_defined_

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

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

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

#define dbp_execute   dbp_f31
#define dbp_forkjoin  dbp_f30

extern unsigned read_clock(void);

#endif

Defines dbp_execute, fetch_mem, os.h, store_mem (links are to index).