Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume44/toy_os/part01

Internet Message Format | 1994-09-05 | 59.5 KB

From: [e-mail] (Kiselyov Oleg)
Newsgroups: comp.sources.misc
Subject: v44i053:  toy_os - yet another OS & hardware emulator, in full C++, Part01/04
Date: 5 Sep 1994 13:18:36 -0500
Organization: University of North Texas
Sender: [e-mail]
Approved: [e-mail]
Message-ID: <csm-v44i053=[e-mail]>
Reply-To: [e-mail], [e-mail]
Summary: UNIX-like OS running on emulated hardware, in full C++ (cf nachos)
Keywords: Operating System, C++, hardware emulation, nachos
X-Md4-Signature: f79c19cdaeb98dd4979dd7768407678f

Submitted-by: [e-mail] (Kiselyov Oleg)
Posting-number: Volume 44, Issue 53
Archive-name: toy_os/part01
Environment: GNU C++ 2.2

Highlights: UNIX-like OS kernel with semaphores, virtual memory and
asynchronous I/O, hardware emulator, "bus" paradigm for both OS and
hardware (classes), extensibility to multi-processor architecture, C++
in full grace.

This is yet another UNIX-like (maybe not so toy) operating system,
which operates on the emulated hardware. It was an (extended) class
project, so I wasn't at liberty to choose architecture, the
instruction set, and system calls to implement.

The operating system supports a minimal set of multiprocessing system
calls like fork, wait, P and V semaphore operations, and I/O
initiation.  Process scheduling is round-robin with fixed time
quants. A memory manager handles page faults and provides address
translation (for channel instructions), page locking/unlocking, page
reservation, etc.  common memory services. Two different page
replacement strategies were implemented and compared: "swap out" and
"local LRU" (with working set quotas like those in VAX/VMS). I ran a
suite of test "jobs" and compared the number of page faults,
etc. There is a report as to how the two strategies fare (it wasn't
actually a part of the class project, I did it just for the heck of
it). The I/O is asynchronous, that is, an I/O processor (channel) runs
concurrently with the main CPU, there can be several active i/o
requests, and many more may be submitted simultaneously. There are
extensive recording facilities, which print the status of the system
and different units as the system runs.  I have a few full traces of
system runs, but they're too big (and too monotonous) to include in
the submission, please mail me if interested.  Sorry, it's only the
kernel stuff, there is no file system (it wasn't a project requirement -:)

The hardware looks suspiciously like IBM/370, though with pure page
virtual memory (not page-segmented), but with several "I/O channels"
that understand their own set of "channel commands" and run
asynchronously with the main CPU. See references below for history of
the project. The hardware emulator is made of classes Memory,
MemoryManagementUnit (to handle the virtual memory), CPU, IOBus,
IOChannel, and devices LinePrinter, CardReader (so quaint -:), and the
HardDisk. The entire project makes a great deal of use of a "bus
architecture" paradigm. Say, on the hardware side, there is a class
"Computer" that holds all units and gives necessary references from
one unit to another at the "construction time". This format makes it a
snap to have a computer with two CPUs "connected" to a single memory
bank, two CPUs with two memory banks, etc.

BTW, there is a class Context that holds all CPU registers and other
control info. The class CPU is based on Context, so is a class PCB
(Process Control Block). So, it makes saving/restoring of the CPU
context during a process switch look as a simple assignment.

As OS was designed, some (elementary) basic classes have
"precipitated".  One of the fundamental classes is BasicQueue, that
provides _asynchronous_ access to a double-linked list of
QueueLink's. The class lets one do simple searches on id or key (two
int properties of QueueLink), add or delete elements, performing
locking where necessary: it's assumed that several threads may want to
operate a queue "simultaneously".  Other OS classes, like PCB or
Semaphore, are based on QueueLink, so it lets one right upfront queue
PCBs and access them simultaneously.

Operating System classes are built upon the hardware classes,
moreover, they mirror the hardware classes.  Say, MemoryManager is
based on Memory, CPUManager is based on the CPU (as well as on
ProcessTable, etc), IOChannelManager is based on the IOChannel. So,
the OS is considered and designed as an "extension" of the
hardware. The class OperatingSystem is based on the class Computer.
It holds all managers and provides for their mutual references, so
it's kind of "software bus". BTW, OperatingSystem is the *only* object
created (in the module bootstrap). All other components are
"physically" parts of the OperatingSystem object and know of each other
through the "bus".

Unlike nachos, I used C++ in its full, with very multiple
inheritance (sometimes to the point of breaking the compiler), static
classes, virtual classes, operator/function overloads, etc. That's was
the whole point actually, I bet (literally) that all specific C++
features are very useful in designing the OS. The code is _well_
commented!  I tried to make the OS as fool-proof as possible, so as to
minimize the probability of a misbehaved/malicious process crashing
the OS or seriously affecting other processes.

The submission consists of a README file (you're reading it
now), and quite a few source code files. File OS.dr lists all of them
and tells briefly what they're for.

I did this project two years ago, so now I would've done a few
things differently. Besides, I spent only 3 weeks (though pretty tough
3 weeks) implementing the software and "hardware". I even repeated my
personal record of 2,000 lines of *working* C++ code per week.
Anyway, I guess I proved, at least to myself, that C++ in its full
grace is quite useful (and efficient) for the OS design. Actually, I
personally have always taken it for granted, but I was surprised to
come across some people thinking otherwise. As to the OS development,
well, I still have hankering for it. So if something in this project
turns out to be useful in any respect, but some changes/rework seems
necessary, well, I can do it (not overnight, of course, but I'll try -:)

References & Credits: The code for vm_unt was originally written in
Modula (called vm_537) at University of Wisconsin-Madison by Raphael
Finkel. The program is adopted into C by Cui-Qing Yang at University
of North Texas.  However, I don't use even a shred of this code, my
implementation is made completely from scratch.  Yet it was mandatory
to implement the same system call format and functionality as in that
system. Sorry, but I had no choice in that.

The OS code is using a C thread library: "The Toy Operating System" by
Robert S. Fabry, Computer Science Division, Dept. of Electrical
Engineering and Computer Sciences, University of California, Berkeley
Well, I myself was thinking something along these lines, and even
started to implement my own threads. But then I came across this
library and gave up on mine (hey, it was a class project, time was
kind of tight). Anyway, if somebody wants to try VM UNT and can't get
hold of this threads library, I solemnly promise to implement my ideas
then (and I'll do it in C++).

I'm not a frequent reader of this newsgroup, please mail me at
[e-mail] or [e-mail] should you want to comment.

---------
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# Contents:  README c++l cpu.cc cpu_manager.cc mem_manager.cc
# Wrapped by kent@sparky on Mon Sep  5 13:12:54 1994
PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin:$PATH ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 1 (of 4)."'
if test -f 'README' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'README'\"
else
  echo shar: Extracting \"'README'\" \(6680 characters\)
  sed "s/^X//" >'README' <<'END_OF_FILE'
XHighlights: UNIX-like OS kernel with semaphores, virtual memory and
Xasynchronous I/O, hardware emulator, "bus" paradigm for both OS and
Xhardware (classes), extensibility to multi-processor architecture, C++
Xin full grace.
X
XThis is yet another UNIX-like (maybe not so toy) operating system,
Xwhich operates on the emulated hardware. It was an (extended) class
Xproject, so I wasn't at liberty to choose architecture, the
Xinstruction set, and system calls to implement.
X
XThe operating system supports a minimal set of multiprocessing system
Xcalls like fork, wait, P and V semaphore operations, and I/O
Xinitiation.  Process scheduling is round-robin with fixed time
Xquants. A memory manager handles page faults and provides address
Xtranslation (for channel instructions), page locking/unlocking, page
Xreservation, etc.  common memory services. Two different page
Xreplacement strategies were implemented and compared: "swap out" and
X"local LRU" (with working set quotas like those in VAX/VMS). I ran a
Xsuite of test "jobs" and compared the number of page faults,
Xetc. There is a report as to how the two strategies fare (it wasn't
Xactually a part of the class project, I did it just for the heck of
Xit). The I/O is asynchronous, that is, an I/O processor (channel) runs
Xconcurrently with the main CPU, there can be several active i/o
Xrequests, and many more may be submitted simultaneously. There are
Xextensive recording facilities, which print the status of the system
Xand different units as the system runs.  I have a few full traces of
Xsystem runs, but they're too big (and too monotonous) to include in
Xthe submission, please mail me if interested.  Sorry, it's only the
Xkernel stuff, there is no file system (it wasn't a project requirement
X-:)
X
XThe hardware looks suspiciously like IBM/370, though with pure page
Xvirtual memory (not page-segmented), but with several "I/O channels"
Xthat understand their own set of "channel commands" and run
Xasynchronously with the main CPU. See references below for history of
Xthe project. The hardware emulator is made of classes Memory,
XMemoryManagementUnit (to handle the virtual memory), CPU, IOBus,
XIOChannel, and devices LinePrinter, CardReader (so quaint -:), and the
XHardDisk. The entire project makes a great deal of use of a "bus
Xarchitecture" paradigm. Say, on the hardware side, there is a class
X"Computer" that holds all units and gives necessary references from
Xone unit to another at the "construction time". This format makes it a
Xsnap to have a computer with two CPUs "connected" to a single memory
Xbank, two CPUs with two memory banks, etc.
X
XBTW, there is a class Context that holds all CPU registers and other
Xcontrol info. The class CPU is based on Context, so is a class PCB
X(Process Control Block). So, it makes saving/restoring of the CPU
Xcontext during a process switch look as a simple assignment.
X
XAs OS was designed, some (elementary) basic classes have
X"precipitated".  One of the fundamental classes is BasicQueue, that
Xprovides _asynchronous_ access to a double-linked list of
XQueueLink's. The class lets one do simple searches on id or key (two
Xint properties of QueueLink), add or delete elements, performing
Xlocking where necessary: it's assumed that several threads may want to
Xoperate a queue "simultaneously".  Other OS classes, like PCB or
XSemaphore, are based on QueueLink, so it lets one right upfront queue
XPCBs and access them simultaneously.
X
XOperating System classes are built upon the hardware classes,
Xmoreover, they mirror the hardware classes.  Say, MemoryManager is
Xbased on Memory, CPUManager is based on the CPU (as well as on
XProcessTable, etc), IOChannelManager is based on the IOChannel. So,
Xthe OS is considered and designed as an "extension" of the
Xhardware. The class OperatingSystem is based on the class Computer.
XIt holds all managers and provides for their mutual references, so
Xit's kind of "software bus". BTW, OperatingSystem is the *only* object
Xcreated (in the module bootstrap). All other components are
X"physically" parts of the OperatingSystem object and know of each other
Xthrough the "bus".
X
X    Unlike nachos, I used C++ in its full, with very multiple
Xinheritance (sometimes to the point of breaking the compiler), static
Xclasses, virtual classes, operator/function overloads, etc. That's was
Xthe whole point actually, I bet (literally) that all specific C++
Xfeatures are very useful in designing the OS. The code is _well_
Xcommented!  I tried to make the OS as fool-proof as possible, so as to
Xminimize the probability of a misbehaved/malicious process crashing
Xthe OS or seriously affecting other processes.
X
X    The submission consists of a README file (you're reading it
Xnow), and quite a few source code files. File OS.dr lists all of them
Xand tells briefly what they're for.
X
X    I did this project two years ago, so now I would've done a few
Xthings differently. Besides, I spent only 3 weeks (though pretty tough
X3 weeks) implementing the software and "hardware". I even repeated my
Xpersonal record of 2,000 lines of *working* C++ code per week.
XAnyway, I guess I proved, at least to myself, that C++ in its full
Xgrace is quite useful (and efficient) for the OS design. Actually, I
Xpersonally have always taken it for granted, but I was surprised to
Xcome across some people thinking otherwise. As to the OS development,
Xwell, I still have hankering for it. So if something in this project
Xturns out to be useful in any respect, but some changes/rework seems
Xnecessary, well, I can do it (not overnight, of course, but I'll try
X-:)
X
XReferences & Credits: The code for vm_unt was originally written in
XModula (called vm_537) at University of Wisconsin-Madison by Raphael
XFinkel. The program is adopted into C by Cui-Qing Yang at University
Xof North Texas.  However, I don't use even a shred of this code, my
Ximplementation is made completely from scratch.  Yet it was mandatory
Xto implement the same system call format and functionality as in that
Xsystem. Sorry, but I had no choice in that.
X
XThe OS code is using a C thread library: "The Toy Operating System" by
XRobert S. Fabry, Computer Science Division, Dept. of Electrical
XEngineering and Computer Sciences, University of California, Berkeley
XWell, I myself was thinking something along these lines, and even
Xstarted to implement my own threads. But then I came across this
Xlibrary and gave up on mine (hey, it was a class project, time was
Xkind of tight). Anyway, if somebody wants to try VM UNT and can't get
Xhold of this threads library, I solemnly promise to implement my ideas
Xthen (and I'll do it in C++).
X
XShould you want to comment, please mail me at [e-mail]
Xor [e-mail]. I'd appreciate that!
END_OF_FILE
  if test 6680 -ne `wc -c <'README'`; then
    echo shar: \"'README'\" unpacked with wrong size!
  fi
  # end of 'README'
fi
if test -f 'c++l' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'c++l'\"
else
  echo shar: Extracting \"'c++l'\" \(313 characters\)
  sed "s/^X//" >'c++l' <<'END_OF_FILE'
X#!/bin/csh
X#    GNU C++ linking
X/usr/local/bin/gcc -O -pipe -W -Wall -Wpointer-arith -Wenum-clash -Woverloaded-virtual \
X-Wstrict-prototypes -Wmissing-prototypes \
X-finline-functions  -fforce-mem -funsigned-char \
X-fforce-addr -fomit-frame-pointer \
X-L{$HOME}/croot/c++serv \
X$* -lserv -liostream -liberty -lg++ -lm
END_OF_FILE
  if test 313 -ne `wc -c <'c++l'`; then
    echo shar: \"'c++l'\" unpacked with wrong size!
  fi
  # end of 'c++l'
fi
if test -f 'cpu.cc' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'cpu.cc'\"
else
  echo shar: Extracting \"'cpu.cc'\" \(7459 characters\)
  sed "s/^X//" >'cpu.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X *               UNT Virtual Machine
X *             Central Processing Unit
X *
X * The present file implemements a central processing unit, i.e. emulates
X * all the operations the "regular" CPU would perform.
X * Once started, the CPU runs until it gets stopped or trap occures. In
X * the latter case, 'trap_signal' is raised so the trap handler can
X * wake up and handle the trap. The trap handler is not a part of CPU,
X * though, and runs as a separate thread within the "hardware".
X *
X ************************************************************************
X */
X
X#pragma implementation
X#include "hardware.h"
X#include "myenv.h"
X#include <std.h>
X
X/*
X *------------------------------------------------------------------------
X *                  Initialization
X */
X
Xint _ebx_save;                // newproc() spoils %ebx on the
X                    // second return. So we have to
X                    // save it.
X
XCentralProcessingUnit::CentralProcessingUnit(Memory& _memory)
X    : MemoryManagementUnit(_memory),
X      stopped("CPU operation",0),
X      trap_signal("CPU trap",0)
X{
X  pc = 0;
X  clock = -1;
X  trap_code = NONE;
X
X//  message("\ntrap_signal ptr %x, val =%x",&trap_signal,*(int *)&trap_signal);
X  asm("movl %ebx,__ebx_save");        // Saving %ebx. It's a shame we need
X                    // to resort to such a kludge!
X  if( !newproc("CPU process",1) )
X  {                    // This is a main CPU process
X    for(;;)
X    {
X      stopped--;            // Wait until can run again
X      if( execute_instruction() )
X    stopped++;            // If everything was fine, keep going
X      else
X    trap_signal++;
X    }
X  }
X
X  asm("movl __ebx_save,%ebx");        // Restore %ebx. I wish I didn't
X                    // have to do this!
X//  message("\ntrap_signal ptr %x, val =%x",&trap_signal,*(int *)&trap_signal);
X}
X
X/*
X *------------------------------------------------------------------------
X *              Starting and stopping the CPU
X */
X
Xvoid CentralProcessingUnit::start(void)
X{
X  if( !is_running() )
X    single_message("CPU: has been stopped, starting..."),
X    stopped++;
X  else
X    single_message("CPU: already running");
X}
X
Xvoid CentralProcessingUnit::stop(void)
X{
X  if( is_running() )
X    single_message("CPU: has been running, stopping..."),
X    stopped--;
X  else
X    single_message("CPU: already stopped");
X}
X
X/*
X *------------------------------------------------------------------------
X *           Emulates a single CPU operation
X *       Fetch an instruction at current pc and execute it
X * Returns 0 if trap or other interrupt has occurred that makes continuation
X * useless. Otherwise returns 1.
X * Note, that pc always points to the instruction following the one
X * which has been executed or which has caused the interrupt.
X *
X */
X
Xint CentralProcessingUnit::execute_instruction(void)
X{
X  trap_code = NONE;
X
X  if( clock == 0 )            // Handle the clock and generate
X  {                    // interrupt if necessary
X    trap_code = CLOCKINT;        // (Clock is to turn negative)
X    --clock;
X    return 0;
X  }
X  else if( clock > 0 )
X    --clock;
X
X  inst_length = 0;                // Fetch and examine the
X  pc++; inst_length++;                // 1st word of the instruction
X  if( *(Word *)&iword1 = fetch(pc-1), got_fault() )
X  {
X    trap_code = MEMORY;
X    pc -= inst_length;                // Set pc to repeat the
X    return 0;                    // operation after recovery
X  }
X  opcode = (OpCodes)iword1.opcode;
X  Word& reg_a = (*this)[iword1.areg];
X  Word  reg_b = (*this)[iword1.breg];
X  EA = 0;
X  if( opcode >= TWO_WORD )
X  {                    // Fetch the second word of instruction
X    ++pc, ++inst_length;
X    if( *(Word *)&iword2 = fetch(pc-1), got_fault() )
X    {
X      trap_code = MEMORY;
X      pc -= inst_length;            // Set pc to repeat the
X      return 0;                    // operation after recovery
X    }
X    EA = iword2.ea;
X                    // Fetch the indirect address
X    if( iword2.indirect && (EA = get(EA), got_fault() ) )
X    {
X      trap_code = MEMORY;
X      pc -= inst_length;            // Set pc to repeat the
X      return 0;                    // operation after recovery
X    }
X    if( iword1.breg != 0 )        // Add the index to the address
X      EA += reg_b;
X  }
X
X                // Print the trace info
X  begin_printing();
X  message("\nCPU: Executing instruction");
X  message("\n  PC  Clock Opcode Areg Breg  R(Areg) R(Breg) SvcOp Ind   EA"
X      "  C(EA)"
X      "\n%4ob %3d    %2d    %2d   %2d    %06o  %06o",
X      pc-inst_length,clock,opcode,iword1.areg,iword1.breg,
X      reg_a,reg_b);
X  if( opcode >= TWO_WORD )
X    message("    %2d   %1d %4ob %06o",iword2.svcop,iword2.indirect,EA,
X        get(EA)), clear_error();    // Clear possible error due to get()
X  message("\n");
X  end_printing();
X
X                // Interpret the instruction
X  switch( opcode )
X  {
X    case HALT:
X         trap_code = ILLEGOP;
X     return 0;
X
X    case DUMP:
X     Context::dump();
X     dump_phys_memory(reg_a,reg_b);
X     break;
X
X    case LOADR:
X     reg_a = reg_b;
X     break;
X
X    case ADD:
X         reg_a += reg_b;
X     break;
X
X    case SUBT:
X         reg_a -= reg_b;
X     break;
X
X    case MULT:
X         reg_a *= reg_b;
X     break;
X
X    case DIV:
X     if( reg_b != 0 )
X       reg_a /= reg_b;
X     break;
X
X    case AND:
X         reg_a &= reg_b;
X     break;
X
X    case OR:
X         reg_a |= reg_b;
X     break;
X
X    case XOR:
X         reg_a ^= reg_b;
X     break;
X
X    case SHIFTL:
X         reg_a <<= reg_b;
X     break;
X
X    case SHIFTR:
X         reg_a >>= reg_b;
X     break;
X
X    case NOP:
X     break;
X
X    case IOPR:
X         trap_code = ILLEGOP;
X     return 0;
X
X    case LOAD:
X     register Word ea_cont = get(EA);
X     if( got_fault() )
X     {
X       trap_code = MEMORY;
X       pc -= inst_length;            // Set pc to repeat the
X       return 0;                // operation after recovery
X     }
X     reg_a = ea_cont;
X     break;
X
X    case LOADI:
X     reg_a = EA;
X     break;
X
X    case STORE:
X     if( put(EA,reg_a), got_fault() )
X     {
X       trap_code = MEMORY;
X       pc -= inst_length;            // Set pc to repeat the
X       return 0;                // operation after recovery
X     }
X     break;
X
X    case BR:
X     pc = EA;
X     break;
X
X    case BRNEG:
X     if( reg_a < 0 )
X       pc = EA;
X     break;
X
X    case BRZERO:
X     if( reg_a == 0 )
X       pc = EA;
X     break;
X
X    case BRPOS:
X     if( reg_a > 0 )
X       pc = EA;
X     break;
X
X    case BRSUBR:
X     reg_a = pc;
X     pc = EA;
X     break;
X
X    case READ:
X    case WRITE:
X         trap_code = ILLEGOP;
X     return 0;
X
X    case SVC:
X     svcop = iword2.svcop;
X         trap_code = SVCCALL;
X     return 0;
X
X    default:
X         trap_code = ILLEGOP;
X     return 0;
X  }
X  return 1;
X}
X
X
X/*
X *------------------------------------------------------------------------
X *                Dump the context
X */
X
Xvoid CentralProcessingUnit::dump(void) const
X{
X  Context::dump();
X  MemoryManagementUnit::dump();
X}
X
Xvoid Context::dump(void) const
X{
X  register int i;
X  message("\n\t\t\tContext Dump\n");
X  message("\n   R0     R1     R2     R3     R4     R5     R6     R7\n");
X  for(i=0; i<=7; i++)
X    message(" %06o",Registers[i]);
X  message("\n\n   R8     R9     R10    R11   R12    R13    R14    R15\n");
X  for(i=8; i<=15; i++)
X    message(" %06o",Registers[i]);
X  message("\n\nPC = %06o\n\n",pc);
X}
X
X/*
X *------------------------------------------------------------------------
X *             Processor context functions
X */
X
X                // Clean up the context at the very beginning
XContext::Context(void)
X{
X  memset(Registers,0,sizeof(Registers));
X  pc = 0;
X}
X
X                // Get ref to a given register
XWord& Context::operator [] (const int reg_number)
X{
X  assure( reg_number >= 0 && reg_number <= 15, "Bad register no" );
X  return Registers[reg_number];
X}
X
X                // Copy the context from another one
Xvoid Context::copy_context(const Context& a_context)
X{
X  memcpy(this,&a_context,sizeof(Context));
X}
X
X
END_OF_FILE
  if test 7459 -ne `wc -c <'cpu.cc'`; then
    echo shar: \"'cpu.cc'\" unpacked with wrong size!
  fi
  # end of 'cpu.cc'
fi
if test -f 'cpu_manager.cc' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'cpu_manager.cc'\"
else
  echo shar: Extracting \"'cpu_manager.cc'\" \(18467 characters\)
  sed "s/^X//" >'cpu_manager.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X *               UNT Virtual Machine
X *
X *         This is the core of the operating system
X *
X * The functions defined in the present file are executed within the
X * TRAP-handler thread that gets control if CPU raised the trap signal.
X * While CPU is stopped during the trap handling, the trap thread
X * handles traps and system requests (SVC traps) and performs all the
X * high level process scheduling.
X *
X ************************************************************************
X */
X
X#pragma implementation "cpu_manager.h"
X#include "cpu_manager.h"
X#include "io_manager.h"
X#include "myenv.h"
X
X/*
X *------------------------------------------------------------------------
X *            Initializing the operating system
X */
X
XCPUManager::CPUManager(CentralProcessingUnit& _CPU,
X               MemoryManager& _mem_manager,IOManager& _io_manager)
X    : CPU(_CPU),
X      memory_manager(_mem_manager),
X      io_manager(_io_manager),
X      Halt("Computer halt",0),
X      ProcessTable(20)
X{
X  semas = new SemaphoreTable(20);
X  running_pcb = 0;
X  if( !newproc("TRAP handling",1) )
X  {                    // This is a CPU trap handler
X    for(;;)
X    {
X      CPU.wait_for_trap();        // Wait for the trap
X      if( trap_handler(CPU.q_trap_code()) == DISPATCH )
X    dispatch();
X      CPU.start();
X    }
X  }
X}
X
X
X                // Load a program from the drum and run it
Xvoid CPUManager::commence(void)
X{
X  int no_programs = memory_manager.q_no_programs();
X  console("There are %d programs on the drum to run",no_programs);
X  register int i;
X  for(i=0; i<no_programs; i++)
X  {
X    PCB& pcb = (*this)[new_pid()];
X    pcb.brand_new();
X    pcb.pc = memory_manager.load_program(pcb,i);
X    readyPCBs.append(pcb);
X  }
X  dispatch();
X  CPU.start();
X}
X
X/*
X *------------------------------------------------------------------------
X *                TRAP handler
X */
X
XHANDLER_STATUS
XCPUManager::trap_handler(const CentralProcessingUnit::TRAPCODE trap_code)
X{
X  save_context();            // Save the CPU context anyway
X  switch(trap_code)
X  {
X    case CentralProcessingUnit::ILLEGOP:
X         if( CPU.q_opcode() == HALT )
X       console("Current process has terminated normally (by HALT)");
X     else if( CPU.q_opcode() == READ || CPU.q_opcode() == WRITE )
X       return initiate_IO(CPU.q_opcode(),CPU.q_EA());
X     else
X       console("Illegal operation (dec code %d)",CPU.q_opcode());
X     return terminate();
X
X    case CentralProcessingUnit::SVCCALL:
X     return svc_handler((SVCCODE)CPU.q_svcop());
X
X    case CentralProcessingUnit::CLOCKINT:
X     single_message("Clock Interrupt");
X     if( readyPCBs.is_empty() )
X       return RESUME;        // We've got only a single process
X     readyPCBs.append(*running_pcb);
X     return DISPATCH;        // Else pick up smth else
X
X    case CentralProcessingUnit::MEMORY:
X     return mfault_handler(CPU.what_fault());
X
X    default:
X         _error("FATAL: Trap handler has been entered with illegal "
X        "trap code %d",trap_code);
X  }
X  return DISPATCH;
X}
X
X/*
X *------------------------------------------------------------------------
X *                SVC Handler
X */
X
XHANDLER_STATUS CPUManager::svc_handler(const SVCCODE svc_code)
X{
X  single_message("SVC interrupt %d",svc_code);
X  switch(svc_code)
X  {
X    case DUMP_STATUS:            // Dump the OS status
X         dump();
X         return RESUME;
X
X    case FORK:                // Fork a process.
X                    // reg_a := PID of a kid or parent
X     return fork(CPU.q_RegA(),CPU.q_EA());    // EA = start address of a kid
X
X    case WAIT_KIDS:            // Wait for kid processes to terminate
X     return wait_for_kids();
X
X    case SEMINIT:            // Create a semaphor for a process
X         return create_semaphore(CPU.q_RegA(),CPU.q_EA());
X
X    case SEM_P:                // P-operation on semaphore
X     return semaphore_p((SID)CPU[CPU.q_RegA()]);
X
X    case SEM_V:                // V-operation on semaphore
X     return semaphore_v((SID)CPU[CPU.q_RegA()]);
X
X    case KILL:                // Try to kill the process
X     return shoot((PID)CPU[CPU.q_RegA()]);
X
X    default:
X         console("Illegal SVC call %d, program is being tossed out",
X         svc_code);
X     return terminate();
X  }
X  return DISPATCH;
X}
X
X/*
X *------------------------------------------------------------------------
X *          Elementary process scheduling functions
X */
X
X                // Prepare the process for running
X                // on the CPU
Xvoid CPUManager::prepare_for_running(void)
X{
X  assert( running_pcb != 0 );
X  assert( !CPU.is_running() );
X  (*running_pcb).load_context(CPU);
X  CPU.clock = Time_quant;
X}
X
X                // Save the status of the currently
X                // running process as the process is
X                // going to lose the CPU control
Xvoid CPUManager::save_context(void)
X{
X  assert( running_pcb != 0 );
X  assert( !CPU.is_running() );
X  (*running_pcb).save_context(CPU);
X}
X
X                // Terminate the currently running process
XHANDLER_STATUS CPUManager::terminate(void)
X{
X  console("Terminating the process PID %d",running_pcb->id);
X  (*running_pcb).dump();
X  kill(*running_pcb);
X  return DISPATCH;            // Pick up a new process to run
X}
X
X                // Pick up a new process to run and make
X                // it current
Xvoid CPUManager::dispatch(void)
X{
X  if( q_all_free() )            // Check if all processes are trough
X    Halt++;
X  running_pcb = &(*this)[readyPCBs.get_from_head()->id]; // Implies waiting
X  single_message("Dispatchung process %d...",running_pcb->id);
X  prepare_for_running();
X}
X
X/*
X *------------------------------------------------------------------------
X *              Dump whatever goes on in the system
X */
X
Xvoid CPUManager::dump(void)
X{
X  begin_printing();
X  message("\n%s\n\n\t\t\tOperating System Status\n",_Minuses);
X  message("\nCurrent process\n");
X  (*running_pcb).dump();
X  ProcessTable::dump();
X  (*semas).dump();
X  memory_manager.dump_status();
X  io_manager.dump();
X  end_printing();
X}
X
X/*
X *------------------------------------------------------------------------
X *               Making new processes
X */
X
X                // Create a child process at EA of
X                // the currently running process
X                // Put PID of the son into the parent rega,
X                // and PID of the parent into the son rega
XHANDLER_STATUS CPUManager::fork(const int rega,Address EA)
X{
X  assert( running_pcb != 0 );
X  if( running_pcb -> lchild != NIL_pid && running_pcb -> rchild != NIL_pid )
X  {
X    console("ABEND: attempt to create the 3d child");
X    return terminate();
X  }
X
X  PID son_id = new_pid();
X  if( son_id == NIL_pid )
X  {
X    console("ABEND: can't create a process - too many are running");
X    return terminate();
X  }
X
X  PCB& son_pcb = (*this)[son_id];
X  PCB& dad_pcb = *running_pcb;
X  single_message("Creating a child %d for a parent %d",son_pcb.id,dad_pcb.id);
X
X  son_pcb.fork_from_dad(dad_pcb);
X  son_pcb[rega] = dad_pcb.id;
X  son_pcb.pc    = EA;
X
X  dad_pcb[rega] = son_pcb.id;
X
X  if( !memory_manager.fork_son((MMContext&)son_pcb,(const MMContext&)dad_pcb) )
X  {                    // If some problem occurred during
X    kill(son_pcb);            // memory allocation for the son
X    return RESUME;
X  }
X
X  readyPCBs.append(dad_pcb);
X  readyPCBs.append(son_pcb);
X  return DISPATCH;
X}
X
X                // Wait until all the kids of the
X                // running process are through.
X                // Return RESUME if the running process
X                // has got no kids.
XHANDLER_STATUS CPUManager::wait_for_kids(void)
X{
X  assert( running_pcb != 0 );
X  if( running_pcb->lchild == NIL_pid && running_pcb->rchild == NIL_pid )
X    return RESUME;                // No kids
X  running_pcb->status = PCB::Wait_for_kids;    // The PCB remains unqueued
X  return DISPATCH;
X}
X
X                // Try to kill the process
XHANDLER_STATUS CPUManager::shoot(const PID pid)
X{
X  single_message("An attempt to shoot a process %d",pid);
X  if( pid == running_pcb->id )
X  {
X    console("The current process %d shot himself",pid);
X    return terminate();
X  }
X
X  if( pid == NIL_pid )
X  {
X    console("An attempt to kill a nonexistent process");
X    return terminate();
X  }
X
X  if( pid != running_pcb->lchild && pid != running_pcb->rchild )
X  {
X    console("Process %d has no right to shoot %d",running_pcb->id,pid);
X    return terminate();
X  }
X
X  PCB& victim = (*this)[pid];
X  if( victim.status == PCB::Doing_io )
X    victim.status = PCB::Shall_die;
X
X  kill(victim);
X  return RESUME;
X}
X
X/*
X *------------------------------------------------------------------------
X *                Kill the process
X * The program performs the clean-up and releases all the resources
X * that process occupied.
X *     - Kids are terminated
X *     - Parent is notified and turned ready if has been waiting
X *     - Owned semaphores are destroyed and all the processes being
X *      waiting on it are terminated
X *     - the process is purged of all semaphore waiting lists if
X *      it has been waiting on P operation
X *    - dispose of the memory of the deseased process
X */
X
Xvoid CPUManager::kill(PCB& pcb)
X{
X  assert(pcb.status != PCB::Dead);
X
X  readyPCBs.purge_id(pcb.id);        // Purge from the ready queue
X                    // (if any)
X  if( pcb.lchild != NIL_pid )
X    kill((*this)[pcb.lchild]);
X
X  if( pcb.rchild != NIL_pid )
X    kill((*this)[pcb.rchild]);
X
X  if( pcb.parent != NIL_pid )
X  {
X    PCB& dad_pcb = (*this)[pcb.parent];
X    if( dad_pcb.lchild == pcb.id )
X      dad_pcb.lchild = NIL_pid;
X    else if( dad_pcb.rchild == pcb.id )
X      dad_pcb.rchild = NIL_pid;
X    else
X      _error("FATAL: parent doesn't know of his son");
X
X                // If dad has been waiting for kids, it may go
X    if( dad_pcb.lchild == NIL_pid && dad_pcb.rchild == NIL_pid &&
X       dad_pcb.status == PCB::Wait_for_kids )
X      dad_pcb.status = PCB::Ok,
X      readyPCBs.append(dad_pcb);
X    pcb.parent = NIL_pid;
X  }
X
X                    // Release all owned semaphores
X  SID sid;
X  while( (sid = (*semas).owned_by(pcb.id)) != NIL_sid )
X  {
X    (*semas).dispose(sid);
X  }
X
X  if( pcb.status == PCB::Wait_on_sema )
X    (*semas).purge(pcb.id);
X
X  memory_manager.dispose((MMContext&)pcb);
X  dispose(pcb.id);
X}
X
X/*
X *------------------------------------------------------------------------
X *            Processes and Semaphores
X */
X                // Create a new semaphore with initial value EA
X                // Put SID in rega
X                // Return RESUME if everything is fine
XHANDLER_STATUS CPUManager::create_semaphore(const int rega,Address EA)
X{
X  assert( running_pcb != 0 );
X
X  SID semid = (*semas).new_semaphore(EA,running_pcb->id);
X  if( semid == NIL_sid )
X  {
X    console("ABEND: Can't create a semaphore - too many are in use");
X    return terminate();
X  }
X
X  single_message("Semaphore %d (in_value %d) has been allocated for PID %d",
X         semid,EA,running_pcb->id);
X
X  CPU[rega] = semid;
X  return RESUME;
X}
X
X                // Check to see that the Sema is valid
X                // to perform P or V operation on.
X                // It should be active and belong to
X                // the running process or its ancestor
XSema * CPUManager::valid_semaphore(const SID sid)
X{
X  if( !(*semas).is_active(sid) )
X    return 0;
X  Sema& sem = (*semas)[sid];
X  PID owner = sem.q_owner();            // Check ownership
X  PID id    = running_pcb->id;            // through the chain of
X  for(; id != NIL_pid; id = (*this)[id].parent)    // ancestorship
X    if( id == owner )
X      return &sem;
X  return 0;
X}
X
X                // Semaphore P-operation
X                // Return RESUME if the process is to
X                // be resumed
XHANDLER_STATUS CPUManager::semaphore_p(const SID sid)
X{
X  single_message("\nP-operation on semaphore %d",sid);
X  assert( running_pcb != 0 );
X  Sema * semp;
X  if( (semp = valid_semaphore(sid)) == 0 )
X  {
X    console("Semaphore %d may not be used by process %d",sid,
X        running_pcb->id);
X    return terminate();
X  }
X
X  if( !(*semp).p(*running_pcb) )
X  {                    // Suspend the current process
X    single_message("Process %d should wait on semaphore %d",
X           running_pcb->id,sid);
X    running_pcb->status = PCB::Wait_on_sema;
X    return DISPATCH;
X  }
X
X  return RESUME;
X}
X
X
X                // Semaphore V-operation
X                // Return RESUME if the process is to
X                // be resumed
XHANDLER_STATUS CPUManager::semaphore_v(const SID sid)
X{
X  single_message("V-operation on semaphore %d",sid);
X  assert( running_pcb != 0 );
X  Sema * semp;
X  if( (semp = valid_semaphore(sid)) == 0 )
X  {
X    console("Semaphore %d may not be used by process %d",sid,
X        running_pcb->id);
X    return terminate();
X  }
X
X  PID pid_to_wake;
X  if( (pid_to_wake = (*semp).v()) != NIL_pid )
X  {                    // Wake up pid_to_wake
X    single_message("Process %d is being woken up",pid_to_wake);
X    PCB& pcb_to_wake = (*this)[pid_to_wake];
X    pcb_to_wake.status = PCB::Ok;
X    readyPCBs.append(pcb_to_wake);
X  }
X
X  return RESUME;
X}
X
X/*
X *------------------------------------------------------------------------
X *            Preliminary Memory Fault Handling
X * Advance memory handling is done by the MemoryManager
X */
X
XHANDLER_STATUS CPUManager::mfault_handler
X    (const MemoryManagementUnit::MemoryFault code)
X{
X  MMUContext::VirtualMemoryAddr culprit_VA = CPU.q_current_VA();
X
X  switch(code)
X  {
X    case MemoryManagementUnit::OutofRange:
X         console("ABEND: Virtual address %o is out of range",culprit_VA);
X     return terminate();
X
X    case MemoryManagementUnit::WrongPageTable:
X         console("ABEND: Page table has wrong format for VA %o",culprit_VA);
X     return terminate();
X
X    case MemoryManagementUnit::WrongVPageNo:
X         console("ABEND: Wrong virtual page number in VA %o",culprit_VA);
X     return terminate();
X
X    case MemoryManagementUnit::PageInvalidated:
X     break;                    // Try to handle that
X
X    case MemoryManagementUnit::NoAccess:
X         console("ABEND: Access to the virtual page denied, VA %o",culprit_VA);
X     return terminate();
X
X    case MemoryManagementUnit::ReadOnly:
X         console("ABEND: May not write to a read-only page, VA %o",culprit_VA);
X     return terminate();
X
X    case MemoryManagementUnit::ExecOnly:
X         console("ABEND: EXEConly page may only be fetched, VA %o",culprit_VA);
X     return terminate();
X
X    default:
X     _error("FATAL: unknown memory fault %d, cannot handle",code);
X  }
X
X  single_message("Missing the page at VA %6o",*(Address*)&culprit_VA);
X
X                    // We've access to the page not in
X                    // the physical memory. Try to bring
X                    // it to there
X  enum {Begin, Blocked, Ready} swap_status = Begin;
X  for(;;)
X    switch(memory_manager.load_the_page((MMContext&)*running_pcb,culprit_VA))
X    {
X      case MemoryManager::Ok:
X           CPU.clear_error();
X           (*running_pcb).load_context(CPU);
X           return RESUME;
X
X      case MemoryManager::PhysMemoryExhausted:
X       message("\nMemory exhausted: ");
X       PID victim_pid;
X       switch(swap_status)
X       {
X         case Begin:
X              start_scan();
X          swap_status = Blocked;
X
X         case Blocked:
X          if( (victim_pid = next_pcb(ProcessTable::Blocked))
X              != NIL_pid )
X          {
X            PCB& pcb = (*this)[victim_pid];
X            message("Blocked PID %d is to be swapped out",victim_pid);
X            memory_manager.swap_out((MMContext&)pcb);
X            continue;
X          }
X              start_scan();
X          swap_status = Ready;
X
X         case Ready:
X          if( (victim_pid = next_pcb(ProcessTable::Ready))
X              != NIL_pid )
X          {
X            if( victim_pid == running_pcb->id )
X              continue;
X            PCB& pcb = (*this)[victim_pid];
X            message("Ready PID %d is to be swapped out",victim_pid);
X            memory_manager.swap_out((MMContext&)pcb);
X            continue;
X          }
X          console("We've tried hard enough, but there is no "
X              "free physical memory");
X          return terminate();
X       }
X       break;
X
X      case MemoryManager::LethalFault:
X       return terminate();
X    }
X}
X
X/*
X *------------------------------------------------------------------------
X *    The following utilities help handle the parameter block
X * the process has prepared in the memory
X * They operate in the current process virtual memory. Page table is
X * assumed to be loaded.
X * The program return FALSE if some problem occured. Usually it is the
X * reason for process termination.
X */
X
X                // Read a word from the (virtual)
X                // address space of a current process
Xint CPUManager::read_word(const Address va, Word& dest)
X{
X  if( dest = CPU.get(va), CPU.got_fault() )
X    if( mfault_handler(CPU.what_fault()) != RESUME )
X      return 0;                // Incorrectable memory fault
X
X  if( dest = CPU.get(va), CPU.got_fault() )
X    return 0;                // Second fault - also bad
X  return 1;
X}
X
X                // Write a word to the (virtual)
X                // address space of a current process
Xint CPUManager::write_word(const Address va, Word src)
X{
X  if( CPU.put(va,src), CPU.got_fault() )
X    if( mfault_handler(CPU.what_fault()) != RESUME )
X      return 0;                // Incorrectable memory fault
X
X  if( CPU.put(va,src), CPU.got_fault() )
X    return 0;                // Second fault - also bad
X  return 1;
X}
X                // Lock the page of the current process
X                // at the specified VA
Xint CPUManager::lock_page(Address va)
X{
X                    // First, try to read this address
X                    // and load the page if necessary
X  if( CPU.get(va), CPU.got_fault() )
X    if( CPU.what_fault() != MemoryManagementUnit::PageInvalidated ||
X        mfault_handler(CPU.what_fault()) != RESUME )
X      return 0;                // Incorrectable memory fault
X  return memory_manager.lock_loaded_page((MMContext&)*running_pcb,va);
X}
X
X                // Unlock the page of a given process
X                // at the specified VA
Xvoid CPUManager::unlock_page(const PID pid,Address va)
X{
X  memory_manager.unlock_page((MMContext&)(*this)[pid],va);
X}
X
X                // Translate the virtual address to physical
X                // one using the translation tables of the
X                // running process
X                // running process. The page has to be loaded
X                // Returns 0 if fails
XAddress CPUManager::translate_va(Address va)
X{
X  return memory_manager.translate_va((MMContext&)*running_pcb,va);
X}
X
X                // Read/write a word from/to the
X                // PHYSICAL address space
X                // Error is fatal
Xvoid CPUManager::read_word_phys_memory(const Address ra, Word& dest)
X{
X  Memory::MemoryAnswer ans = CPU.memory[ra];
X  if( ans.out_of_range )
X    _error("CPU reading phys memory failed at %o",ra);
X  dest = ans.contents;
X}
X
Xvoid CPUManager::write_word_phys_memory(const Address ra, Word src)
X{
X  Memory::MemoryAnswer ans = CPU.memory[ra];
X  if( ans.out_of_range )
X    _error("CPU writing phys memory failed at %o",ra);
X  ans.contents = src;
X}
X
X/*
X *------------------------------------------------------------------------
X *            Initiate the Input/Output
X * The following program performs only preliminary I/O initiation
X */
X
XHANDLER_STATUS CPUManager::initiate_IO(const OpCodes opcode,Address IO_params)
X{
X  single_message("Processing I/O parameters");
X  if( !io_manager.submit_request(running_pcb->id,opcode,IO_params) )
X    return terminate();
X  running_pcb->status = PCB::Doing_io;
X  return DISPATCH;
X}
X
X                // Post the completion of the I/O request
Xvoid CPUManager::io_request_completed(const PID pid)
X{
X  PCB& pcb = (*this)[pid];
X  assert( pcb.status == PCB::Doing_io );
X  pcb.status = PCB::Ok;
X  readyPCBs.append(pcb);
X}
END_OF_FILE
  if test 18467 -ne `wc -c <'cpu_manager.cc'`; then
    echo shar: \"'cpu_manager.cc'\" unpacked with wrong size!
  fi
  # end of 'cpu_manager.cc'
fi
if test -f 'mem_manager.cc' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'mem_manager.cc'\"
else
  echo shar: Extracting \"'mem_manager.cc'\" \(16274 characters\)
  sed "s/^X//" >'mem_manager.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X *               UNT Virtual Machine
X *
X *             High Level Virtual Memory Manager
X *
X * This is a high-level extension of the memory unit, and uses paging to
X * manage memory requests of processes.
X * Page selection is on demand, that's the page isn't loaded until it is
X * missed by the CPU to complete the execution of an instruction.
X *
X * The present version supports the working set concept and an approximate
X * LRU page replacement strategy. Working set of a process is a set of
X * all pages that are currently referenced (mapped, i.e. loaded into
X * the physical memory) by the process. In other words, it is the set of
X * pages the process is working with. Working set quota limits the number
X * of the pages the process is allowed to have mapped. If the working set
X * is filled up to the quota, yet the process needs (demands) one more page,
X * one page of the working set should be unreferenced (and swapped out if
X * it has been modified) before the request to map new page is served.
X * To decide which page to unmap, an approximate LRU page replacement
X * strategy is used.
X * It means, the algorithm will try to find the least recently used page
X * of the working set and push it out. To figure out which page has been
X * used least recently, the memory context of the process keeps a time-since-
X * last-access count of the page usage. When the process gets control
X * of the CPU and its page table gets loaded into the hardware, was_ref
X * bit of every page is dropped. When the CPU accesses memory, the memory
X * hardware sets the was_ref bit of the accessed page. When the process
X * loses control of the CPU (because it runs into the blocking condition,
X * or because it exhausted its time slice), the time-since-last-access
X * count for all the pages that haven't been accessed during that
X * process run is incremented. Therefore, the larger the count, the
X * least recently the page has been accessed (used). Note, since
X * process switchings out occure non-uniformly (the process loses
X * the CPU control not only because of the time click, but also because
X * of blocking), the LRU count is only approximately correct. Yet,
X * interrupts in the real system occur quite regularly, so this
X * approximation seems fairly accurate.
X *
X ************************************************************************
X */
X
X#pragma implementation
X#include "mem_manager.h"
X
X#include "myenv.h"
X#include <std.h>
X
XMemoryManager::MemoryManager(Memory& _physical_memory)
X    : physical_memory(_physical_memory),
X      virtual_space(_physical_memory,(Memory::hiaddr+1)/Memory::pagesize,
X            Memory::no_drum_sectors)
X{
X  no_programs = 0;
X}
X
X
X                // Read the drum header and tell the
X                // number of programs on the drum
Xint MemoryManager::q_no_programs(void)
X{
X  virtual_space.declare_page_private(0);
X  physical_memory.drum_read(0,PageFrameTable::sys_page_frame);
X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
X  register Address curr_address = base_address;
X  no_programs = physical_memory[curr_address++].contents;
X  assert( no_programs > 0 && no_programs <= max_no_programs );
X  register int i;
X  for(i=0; i<no_programs; i++)
X    prog_descriptors[i].pc = physical_memory[curr_address++].contents,
X    prog_descriptors[i].mem_map = physical_memory[curr_address++].contents;
X
X  return no_programs;
X}
X
X
Xvoid MemoryManager::dump_status(void) const
X{
X  virtual_space.dump_status();
X}
X
X/*
X *------------------------------------------------------------------------
X *               Servicing memory requests of a process
X */
X
X                // Initializing all areas
XMMContext::MMContext(void)
X{
X  register int i;
X  for(i=0; i<process_virtual_space; i++)
X    vm_map[i] = NIL_vpn;
X  memset(page_table,0,sizeof(page_table));
X  memset(time_since_last_ref,0,sizeof(time_since_last_ref));
X  no_mapped_pages = 0;
X  no_page_faults = 0;
X}
X
X                // Given vm_map, map of the process virtual
X                // space, construct the page table
Xvoid MMContext::build_page_table(const VirtualPageTable& virtual_space)
X{
X  register int i;
X  for(i=0; i<process_virtual_space; i++)
X  {
X    PageTableEntry& pte = page_table[i];
X    pte.valid = pte.was_ref = pte.was_written = 0;
X    if( vm_map[i] == NIL_vpn )        // The page hasn't been allocated
X      pte.any_access = pte.read_only = pte.exec_only = 0;
X    else
X    {
X      pte.any_access = 1;        // The page has been allocated
X      const VirtualPage& vp = virtual_space[vm_map[i]];
X      pte.exec_only = vp.q_data_page() ? 0 : 1;
X      if( vp.page_frame != NIL_pfn)
X    pte.phys_page_no = vp.page_frame,// The page is mapped
X    pte.valid = 1;
X    }
X  }
X}
X
X
X                // Load the context to the MMU
X                // Note, the referenced bit for every page
X                // in the page table is cleared to
X                // find out which pages are going to be
X                // accessed during the time the process
X                // is running on CPU
Xvoid MMContext::load_MMU(MemoryManagementUnit& mmu)
X{
X  memcpy((MMUContext *)&mmu,this,sizeof(MMUContext));
X                    // Load the page table
X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
X  assert( page_table_len <= process_virtual_space );
X  assert( page_table_len <= Memory::pagesize );
X
X  register int i;
X  for(i=0; i<page_table_len; i++)
X  {
X    PageTableEntry& pte = page_table[i];
X    pte.was_ref = 0;            // Clear the ref bit
X    *(PageTableEntry *)&(mmu.memory[base_address+i].contents) = pte;
X  }
X  mmu.clear_error();
X}
X
X                // Save the MMU context
X                // Was_written/was_referenced fields in the
X                // page_table might have been changed. This
X                // needs to be saved. The referenced bit
X                // is used to find out which pages have been
X                // actually accessed, and to increment counter
X                // for the pages that haven't been used
Xvoid MMContext::save_MMU(const MemoryManagementUnit& mmu)
X{
X                    // Save the page table
X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
X  assert( page_table_len <= process_virtual_space );
X  assert( page_table_len <= Memory::pagesize );
X
X  register int i;
X  for(i=0; i<page_table_len; i++)
X  {
X    const PageTableEntry& pte =
X      *(PageTableEntry *)&(mmu.memory[base_address+i].contents);
X    if( pte.valid && !pte.was_ref )
X      time_since_last_ref[i]++;
X    page_table[i] = pte;
X  }
X}
X
X                // Dump whatever's in there
Xvoid MMContext::dump(void) const
X{
X  if( !enabled_address_translation )
X  {
X    message("\nVirtual memory is disabled for this process\n");
X    return;
X  }
X
X  message("\nProcess virtual space is %d pages long",page_table_len);
X  message("\nWorking set size %d, working set quota %d\n",no_mapped_pages,
X      working_set_quota);
X  message("\nAddress range\tAccess\tMapped to   Drum sector"
X      "\tWritten\tReferenced LRU time\n");
X  register int i;
X  for(i=0; i<page_table_len; i++)
X  {
X    const PageTableEntry& pte = page_table[i];
X    if( !(pte.any_access || pte.read_only || pte.exec_only) )
X      continue;                    // Page isn't allocated
X    message("%06o-%06o \t %s\t",Memory::pagesize*i,Memory::pagesize*(i+1)-1,
X        pte.exec_only ? "Exec" : pte.read_only ? "Read" : "Any");
X    if( pte.valid )
X      message("%06o  ",pte.phys_page_no*Memory::pagesize);
X    else
X      message("Not Mapped ");
X    message("\t%d\t   %s\t    %s",vm_map[i],pte.was_written ? "Y" : "N",
X        pte.was_ref ? "Y" : "N");
X    if( pte.valid )
X      message("         %d\n",time_since_last_ref[i]);
X    else
X      message("\n");
X  }
X  message("\nProcess has %d page faults\n\n",no_page_faults);
X}
X
X                    // Load program and return starting PC
XAddress MemoryManager::load_program
X    (MMContext& context,const unsigned int prog_no)
X{
X  assure(prog_no < (unsigned)no_programs,
X     "FATAL: an attempt to load nonexistent program");
X  ProgDescr& prog_descr = prog_descriptors[prog_no];
X                    // Read the memory map from the drum
X  virtual_space.declare_page_private((VPN)prog_descr.mem_map);
X  physical_memory.drum_read((VPN)prog_descr.mem_map,
X                PageFrameTable::sys_page_frame);
X                    // Set up the vm_map and page_table
X  const Address base_address = PageFrameTable::sys_page_frame*Memory::pagesize;
X  register int i;
X  for(i=0; i<MMContext::process_virtual_space; i++)
X  {
X    assert( i < Memory::pagesize );
X    int drum_sector_no = physical_memory[base_address+i].contents;
X    if( drum_sector_no == -1 )
X      context.vm_map[i] = NIL_vpn;
X    else
X    {
X      virtual_space.declare_page_private((VPN)drum_sector_no);
X      if( !is_text_segment(i) )
X    virtual_space[(VPN)drum_sector_no].declare_data_page();
X      context.vm_map[i] = drum_sector_no;
X    }
X  }
X
X  context.build_page_table(virtual_space);
X  context.no_page_faults = 0;
X  context.no_mapped_pages = 0;
X  memset(context.time_since_last_ref,0,sizeof(context.time_since_last_ref));
X
X  context.page_table_addr = PageFrameTable::sys_page_frame*Memory::pagesize;
X  context.page_table_len  = MMContext::process_virtual_space;
X  context.enabled_address_translation = 1;
X
X  return prog_descr.pc;
X}
X
X                // Take care of son's virtual space
X                // Return FALSE if we've got some problem
Xint MemoryManager::fork_son
X    (MMContext& son_context,const MMContext& dad_context)
X{
X                    // Check is everything's in real memory
X  if( !dad_context.enabled_address_translation )
X  {
X    son_context.enabled_address_translation = 0;
X    return 1;
X  }
X                      // Set up the vm_map
X  register int i;
X  son_context.no_mapped_pages = 0;
X  for(i=0; i<MMContext::process_virtual_space; i++)
X  {
X    VPN dad_vpn = dad_context.vm_map[i];
X    if( dad_vpn == NIL_vpn )
X    {
X      son_context.vm_map[i] = NIL_vpn;
X      continue;
X    }
X
X    const VirtualPage& dad_vp = virtual_space[dad_vpn];
X    if( !dad_vp.q_data_page() )
X    {                    // Code text page, to be shared
X      virtual_space.allocate(dad_vpn);
X      son_context.vm_map[i] = dad_vpn;
X      if( dad_vp.is_mapped() )        // Son would also refer to the
X    virtual_space.reference(dad_vpn),    // dad's mapped pages
X        son_context.no_mapped_pages++;
X      continue;
X    }
X
X    VPN son_vpn = virtual_space.allocate();
X    if( son_vpn == NIL_vpn )
X    {
X      console("No virtual space for the son process. It has to be killed");
X      return 0;
X    }
X
X    son_context.vm_map[i] = son_vpn;
X    virtual_space[son_vpn].declare_data_page();
X    virtual_space.copy(son_vpn,dad_vpn);
X  }
X
X  son_context.build_page_table(virtual_space);
X  son_context.no_page_faults = 0;
X  memset(son_context.time_since_last_ref,0,
X     sizeof(son_context.time_since_last_ref));
X
X  son_context.page_table_addr =
X    PageFrameTable::sys_page_frame*Memory::pagesize;
X  son_context.page_table_len  = MMContext::process_virtual_space;
X  son_context.enabled_address_translation = 1;
X
X  return 1;
X}
X
X                // Serve the request to bring a virtual page
X                // into the real memory
XMemoryManager::MMAnswer MemoryManager::load_the_page
X    (MMContext& context,MMUContext::VirtualMemoryAddr culprit_VA)
X{
X  unsigned int page_no = culprit_VA.page_no;
X  assert( page_no < (unsigned)context.page_table_len );
X  VPN vpn = context.vm_map[page_no];
X
X  if( context.no_mapped_pages >= context.working_set_quota )
X    replace_LRU_page(context);
X
X  PFN pfn = virtual_space.reference(vpn);
X  if( pfn == NIL_pfn )
X    return PhysMemoryExhausted;
X  context.no_mapped_pages++;
X  VirtualPage& vp = virtual_space[context.vm_map[page_no]];
X
X  if( !vp.is_shared_mapped() )
X    context.no_page_faults++;        // The page has been physically loaded
X  else                    // The page might have been loaded by
X    if( vp.q_data_page() )        // siblings (if it's shared)
X      _error("Non-shared data page %d turns out to be loaded into frame %d",
X         vp.id,vp.page_frame);
X
X  MMUContext::PageTableEntry& pte = context.page_table[page_no];
X  pte.phys_page_no = vp.page_frame;
X  pte.valid = 1;
X  context.time_since_last_ref[page_no] = 0;
X  return Ok;
X}
X
X                    // Release the virtual memory
X                    // occupied by the process
Xvoid MemoryManager::dispose(MMContext& context)
X{
X  if( !context.enabled_address_translation )
X    return;                // No virtual memory was occupied
X  register int i;
X  for(i=0; i<MMContext::process_virtual_space; i++)
X  {
X    VPN vpn = context.vm_map[i];
X    if( vpn == NIL_vpn )
X      continue;
X    MMUContext::PageTableEntry& pte = context.page_table[i];
X    if( pte.valid )
X      virtual_space.unreference(vpn,0),
X      context.no_mapped_pages--;
X    virtual_space.dispose(vpn);
X    context.vm_map[i] = NIL_vpn;
X  }
X  assert(context.no_mapped_pages == 0);
X  memset(context.time_since_last_ref,0,sizeof(context.time_since_last_ref));
X  context.no_page_faults = 0;
X  context.page_table_addr = 0;
X  context.page_table_len  = 0;
X  context.enabled_address_translation = 0;
X}
X
X                // Swap out a victim - forcibly deprive it
X                // of mapped pages
X                // Return 0 if no page frame was released
X                // Swapping goals were not achieved
Xint MemoryManager::swap_out(MMContext& context)
X{
X  message("\nSwapping out...");
X  if( !context.enabled_address_translation )
X    return 0;                // No virtual memory was occupied
X  register int i;
X  int swapped_something = 0;
X  for(i=0; i<MMContext::process_virtual_space; i++)
X  {
X    VPN vpn = context.vm_map[i];
X    if( vpn == NIL_vpn )
X      continue;
X    VirtualPage& vp = virtual_space[vpn];
X    MMUContext::PageTableEntry& pte = context.page_table[i];
X    if( !pte.valid )            // The page wasn't accessed by us yet
X      continue;                // (if it was allocated at all)
X    assert( pte.phys_page_no == vp.page_frame );
X    virtual_space.unreference(vpn,pte.was_written);
X    context.no_mapped_pages--;
X    pte.valid = 0;
X    pte.was_ref = pte.was_written = 0;
X    swapped_something = 1;
X  }
X  assert(context.no_mapped_pages == 0);
X  return swapped_something;
X}
X
X                // Run the LRU page replacement strategy
X                // to find out the least referenced page
X                // and push it out
Xvoid MemoryManager::replace_LRU_page(MMContext& context)
X{
X  int max_counter = -1;
X  int page_victim = -1;
X  register int i;
X  for(i=0; i<MMContext::process_virtual_space; i++)
X    if(context.page_table[i].valid &&
X       context.time_since_last_ref[i] > max_counter)
X      max_counter = context.time_since_last_ref[i],
X      page_victim = i;
X
X  assert( page_victim >= 0 );
X  VPN vpn = context.vm_map[page_victim];
X  message("\nFound LRU page %d, time since last used %d",vpn,max_counter);
X
X  MMUContext::PageTableEntry& pte = context.page_table[page_victim];
X  assert( pte.valid );
X  virtual_space.unreference(vpn,pte.was_written);
X  context.no_mapped_pages--;
X  pte.valid = 0;
X  pte.was_ref = pte.was_written = 0;
X}
X
X                // Lock the page that contains the
X                // specified virtual address. The page
X                // should be already mapped
X                // Return FALSE if failed
Xint MemoryManager::lock_loaded_page(MMContext& context,const Address addr)
X{
X  if( !context.enabled_address_translation )
X    return 0;                // Virtual memory is disabled
X
X  MMUContext::VirtualMemoryAddr va = *(MMUContext::VirtualMemoryAddr*)&addr;
X  unsigned int page_no = va.page_no;
X  assert( page_no < (unsigned)context.page_table_len );
X  VPN vpn = context.vm_map[page_no];
X
X  virtual_space.lock(vpn);
X  return 1;
X}
X
X                // Unlock the page that contains the
X                // specified virtual address. The page
X                // should be already mapped & locked
Xvoid MemoryManager::unlock_page(MMContext& context,const Address addr)
X{
X  assert( context.enabled_address_translation );
X
X  MMUContext::VirtualMemoryAddr va = *(MMUContext::VirtualMemoryAddr*)&addr;
X  unsigned int page_no = va.page_no;
X  assert( page_no < (unsigned)context.page_table_len );
X  VPN vpn = context.vm_map[page_no];
X
X  virtual_space.unlock(vpn);
X}
X
X                // Translate the virtual address to physical
X                // one. The page has to be loaded.
X                // Returns 0 if fails
XAddress MemoryManager::translate_va(MMContext& context,const Address addr)
X{
X  if( !context.enabled_address_translation )
X    return addr;                // Virtual memory is disabled
X
X  MMUContext::VirtualMemoryAddr va = *(MMUContext::VirtualMemoryAddr*)&addr;
X  unsigned int page_no = va.page_no;
X  if( page_no >= (unsigned)context.page_table_len )
X    return 0;                    // Out of range
X  const MMUContext::PageTableEntry& pte = context.page_table[page_no];
X  if( !pte.any_access )
X    return 0;                    // No access
X  if( !pte.valid )
X    return 0;                    // Not mapped
X  va.page_no = pte.phys_page_no;
X
X  return *(Address *)&va;
X}
END_OF_FILE
  if test 16274 -ne `wc -c <'mem_manager.cc'`; then
    echo shar: \"'mem_manager.cc'\" unpacked with wrong size!
  fi
  # end of 'mem_manager.cc'
fi
echo shar: End of archive 1 \(of 4\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 3 4 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 4 archives.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...