v44i053: toy_os - yet another OS & hardware emulator, in full C++, Part01/04
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
ol...@ponder.csci.unt.edu or ol...@unt.edu 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 ol...@ponder.csci.unt.edu
Xor ol...@unt.edu. 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...
Kiselyov Oleg
Posting-number: Volume 44, Issue 54
Archive-name: toy_os/part02
Environment: GNU C++ 2.2
#! /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: channel.cc hardware.h io_manager.h memory.cc myenv.h
# oper_system.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 2 (of 4)."'
if test -f 'channel.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'channel.cc'\"
else
echo shar: Extracting \"'channel.cc'\" \(10755 characters\)
sed "s/^X//" >'channel.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X * Input/Output Channel
X *
X * The present file emulates operations of the I/O channel and the
X * divice driver.
X *
X * Note that all the channels are connected to the I/O bus and gets its
X * number from it (so the channel numbers tell the order the channels are
X * connected to the bus). The channel itself consists of the device-
X * independent part (that performs fetching and decoding of the CCW,
X * moves data between io_buffer and memory, handles error conditions
X * and raises the interrupt) and the device-dependent part. The latter
X * is responsible for specific for each device operations necessary to
X * transmit data between the io_buffer and the "media".
X *
X * Once started, the channel executes the given sequence of CCW (channel
X * program) until the program is over (no command chain flag set at the
X * last CCW) or some error occured. When the channel stops, 'intr_signal'
X * is raised to inform the OS. The status of the completed program is
X * available through q_status().
X *
X * Note each read/write channel operation transmit exactly one page
X * of data between the "media" and the memory. The current implementation
X * does not support address translation during I/O (and neither do most of
X * the real computing system). So, the page number specified in the
X * CCW is supposed to be the number of a page in the physical memory
X * (page frame). It implies that the OS is responsible for address
X * translation itself if necessary when constructing the channel program.
X * Channel program itself should also be in the physical memory.
X *
X ************************************************************************
X */
X
X#pragma implementation
X#include "hardware.h"
X#include "myenv.h"
X#include <std.h>
X#include <sys/file.h>
X
X
X/*
X *------------------------------------------------------------------------
X * I/O Bus operations
X */
X
XIOBus::IOBus(void)
X{
X no_channels = 0;
X}
X
X // Connect a channel to the i/o bus
X // Return the channel number on the bus,
X // an integer starting from 1
Xint IOBus::connect_channel(IOChannel * channel)
X{
X assure(++no_channels < max_no_channels, "Too many channels in the program");
X channels[no_channels - 1] = channel;
X return no_channels;
X}
X
X // Dump the status of all the channels
Xvoid IOBus::dump(void)
X{
X register int i;
X for(i=0; i<no_channels; i++)
X channels[i]->dump();
X}
X
X // Start a channel program on a specified
X // channel. Return FALSE if the operation
X // was rejected upfront
Xint IOBus::start(const unsigned short channel_no, const Address ccw_ptr)
X{
X if( channel_no == 0 || channel_no > no_channels )
X {
X console("Channel no. %d is not in 1..%d, can't start the channel program",
X channel_no,no_channels);
X return 0;
X }
X channels[channel_no-1]->start(ccw_ptr);
X return 1;
X}
X
X/*
X *------------------------------------------------------------------------
X * Channel general initialization
X */
X
XIOChannel::IOChannel(Memory& _memory,IOBus& io_bus)
X : memory(_memory),
X stopped("Channel operation",0),
X intr_signal("Channel interrupt",0)
X{
X
X channel_no = io_bus.connect_channel(this);
X
X cpc = 0;
X file_handle = -1;
X rec_count = 0;
X status = OK;
X
X if( !newproc("Channel process",1) )
X { // This is a channel process
X for(;;)
X {
X stopped--; // Wait until can run again
X if( (status = execute_CCW()) == OK && current_CCW.keep_going )
X stopped++; // If everything was fine, keep going
X else
X intr_signal++;
X }
X }
X}
X
X // Starting a channel
Xvoid IOChannel::start(Address channel_program_ptr)
X{
X if( !is_running() )
X single_message("Channel: starting the program at %6o",channel_program_ptr),
X cpc = channel_program_ptr,
X stopped++;
X else
X _error("FATAL: tried to start a running channel");
X}
X
X/*
X *------------------------------------------------------------------------
X * Emulates a single channel operation
X *
X * In other words, fetch a CCW at current cpc, analyse it, have the
X * device driver do its part and move the data to/from the computer main
X * memory. The program returns the STATCODE.
X * Note, that cpc always points to the CCW following the one which has been
X * executed (or failed).
X *
X */
X
XIOChannel::STATCODE IOChannel::execute_CCW(void)
X{
X if( file_handle == EOF )
X {
X console("Channel %d: file has not been open",channel_no);
X return DEVICE;
X }
X
X if( memory[cpc].out_of_range )
X return CCWADDR;
X
X // Fetch the CCW
X *(Word *)¤t_CCW = memory[cpc++].contents;
X opcode = (CCWOpCodes)current_CCW.opcode;
X buf_page = current_CCW.page_no;
X
X // Print the trace info
X begin_printing();
X message("\nChannel %d: Executing instruction", channel_no);
X message("\n CPC Opcode Chain Page no"
X "\n%4ob %3d %s %2d",
X cpc-1,opcode, (current_CCW.keep_going ? "Y" : "N"), buf_page);
X message("\n");
X end_printing();
X // Interpret the instruction
X switch( opcode )
X {
X case ILLEGAL_CCW:
X return ILLEGOP;
X
X case SETMAP:
X if( buf_page != 0 )
X _error("Sorry, address translation during I/O isn't implemented");
X return OK;
X
X case SETPTBR:
X _error("FATAL: address translation during I/O isn't implemented");
X
X case SETPTL:
X _error("FATAL: not implemented yet");
X
X case SEEKOP:
X return device_driver(DEV_SEEK);
X
X case READOP:
X { // Read a record
X STATCODE read_status = device_driver(DEV_READ);
X if( read_status != OK )
X return read_status;
X }
X if( put_record(buf_page) ) // Put the read record into
X return OK; // the memory
X else
X return MEMORY;
X
X case WRITEOP:
X if( !get_record(buf_page) ) // Get a record to write
X return MEMORY;
X return device_driver(DEV_WRITE);
X
X default:
X return ILLEGOP;
X }
X
X return OK;
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Non-device specific channel operations
X */
X
X // Tell what's going on
Xvoid IOChannel::dump(void) const
X{
X}
X
X // Get a record to write from the main memory
X // to the io_buffer.
X // Return FALSE if we've got a memory problem
Xint IOChannel::get_record(const int page_no)
X{
X register int i;
X for(i=0; i<rec_size; i++)
X {
X Memory::MemoryAnswer ans = memory[page_no*Memory::pagesize+i];
X if( ans.out_of_range )
X return 0;
X else
X io_buffer[i] = ans.contents;
X }
X return 1;
X}
X
X // Put a read record to the main memory
X // from the io_buffer.
X // Return FALSE if we've got a memory problem
Xint IOChannel::put_record(const int page_no)
X{
X register int i;
X for(i=0; i<rec_size; i++)
X {
X Memory::MemoryAnswer ans = memory[page_no*Memory::pagesize+i];
X if( ans.out_of_range )
X return 0;
X else
X ans.contents = io_buffer[i];
X }
X return 1;
X}
X
X // Open the UNIX file the channel is associated
X // with
Xvoid IOChannel::associate_with_unix_file(const char * file_name)
X{
X message("\nOpening the file %s\n",file_name);
X file_handle = open(file_name,O_RDWR,0);
X if( file_handle < 0 )
X perror("File opening error"),
X console("Channel %d will be unoperational due to the reason above",
X channel_no);
X else
X console("Channel %d is operational and associated with the file '%s'",
X channel_no,file_name);
X}
X
X/*
X *------------------------------------------------------------------------
X * Device-specific processing
X */
X
XCardReader::CardReader(Memory & main_memory, IOBus& io_bus)
X : IOChannel(main_memory,io_bus)
X{
X in_file = (void *)0;
X}
X
X // Card reader device driver
X // Note, the driver reads a record from
X // the file to the io_buffer until '\n' or
X // the entire record is read (whichever
X // comes first). In the former case,
X // the record is padded with blanks
XIOChannel::STATCODE CardReader::device_driver(const DEVICE_OP dev_op)
X{
X if( dev_op == DEV_SEEK )
X return OK;
X if( dev_op != DEV_READ )
X return ILLEGOP;
X
X if( in_file == (void *)0 )
X if( (in_file = fdopen(file_handle,"r")) == (void *)0 )
X {
X perror("Error opening the card reader file");
X console("Card reader (channel %d) is no longer operational",
X q_channel_no());
X file_handle = -1;
X return DEVICE;
X }
X
X if( fgets((char *)io_buffer,sizeof(io_buffer),(FILE *)in_file) == (void *)0 )
X if( feof((FILE *)in_file) )
X {
X console("Card reader has nothing to read");
X return END_FILE;
X }
X else
X {
X perror("I/O error on the card reader");
X return DEVICE;
X }
X
X register char *p;
X if( (p = strchr((char *)io_buffer,'\n')) != 0 )
X while( p < (char *)io_buffer + sizeof(io_buffer) )
X *p++ = ' ';
X else
X { // Read the last char into buffer
X p = (char *)io_buffer + sizeof(io_buffer) - 1;
X int c = fgetc((FILE *)in_file);
X if( c == EOF || c == '\n' )
X c = ' ';
X *p = c;
X }
X rec_count++;
X return OK;
X}
X
X // Line printer device driver
X // Note, the driver automatically writes
X // '\n' after any write operation.
X // DEV_SEEK is interpreted as writing
X // '\n' (advance the paper)
XIOChannel::STATCODE LinePrinter::device_driver(const DEVICE_OP dev_op)
X{
X char new_line = '\n';
X
X if( dev_op == DEV_SEEK )
X { // Seek is just advance the paper
X if( write(file_handle,&new_line,1) != 1 )
X {
X perror("Line printer file error");
X return DEVICE;
X }
X rec_count++;
X return OK;
X }
X
X if( dev_op != DEV_WRITE )
X return ILLEGOP;
X
X if( write(file_handle,(char *)io_buffer,sizeof(io_buffer))
X != sizeof(io_buffer) )
X {
X perror("Line printer file error");
X return DEVICE;
X }
X return device_driver(DEV_SEEK);
X}
X
X
X // Hard disk device driver
XIOChannel::STATCODE HardDisk::device_driver(const DEVICE_OP dev_op)
X{
X assert( sizeof(io_buffer) == disk_sector_size );
X switch(dev_op)
X {
X case DEV_SEEK:
X rec_count = q_buf_page(); // It should contain the
X if( rec_count > hi_disk_addr ) // seek addr
X {
X console("HardDisk: disk sector address %d is too big",
X rec_count);
X return SEEKADDR;
X }
X if( lseek(file_handle,rec_count*disk_sector_size,0) < 0 )
X {
X perror("HardDisk: seek failed");
X return DEVICE;
X }
X return OK;
X
X case DEV_READ:
X if( read(file_handle,(char *)io_buffer,sizeof(io_buffer)) !=
X sizeof(io_buffer) )
X {
X perror("HardDisk: read failed");
X return DEVICE;
X }
X rec_count++;
X return OK;
X
X case DEV_WRITE:
X if( write(file_handle,(char *)io_buffer,sizeof(io_buffer)) !=
X sizeof(io_buffer) )
X {
X perror("HardDisk: write failed");
X return DEVICE;
X }
X rec_count++;
X return OK;
X
X default:
X return ILLEGOP;
X }
X return OK;
X}
END_OF_FILE
if test 10755 -ne `wc -c <'channel.cc'`; then
echo shar: \"'channel.cc'\" unpacked with wrong size!
fi
# end of 'channel.cc'
fi
if test -f 'hardware.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'hardware.h'\"
else
echo shar: Extracting \"'hardware.h'\" \(10975 characters\)
sed "s/^X//" >'hardware.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X * Hardware
X *
X * The present file describes blocks of hardware (units) the VM_UNT
X * is made of, namely, CPU, diagnostic panel, memory, channels, etc.
X * See the document vm_unt.txt for details
X *
X ************************************************************************
X */
X
X#ifndef _hardware_h
X#define _hardware_h 1
X#pragma interface
X
X#include "mult_proc.h"
X#include "instruction_set.h"
X
X/*
X *------------------------------------------------------------------------
X * Printing diagnostic info
X */
X
Xclass DiagnosticPanel
X{
X // It is necessary for output from one process
X // not to get messed up with that of
X // other processes
X static Semaphore printing_diagnostics;
X
Xpublic:
X short is_tracing;
X
X DiagnosticPanel(void);
X virtual ~DiagnosticPanel(void) {}
X
X // This routine displays the message
X // only if tracing is on
X void single_message(const char * message,...);
X // This program always displays the
X // message
X void console(const char * message,...);
X // The following function bracket the
X // block of diagnostic info that
X // should not be broken by other processes
X // output
X void begin_printing(void);
X void end_printing(void);
X};
X
X/*
X *------------------------------------------------------------------------
X * Virtual and Real memory
X */
X
Xtypedef short Word;
Xtypedef unsigned short Address;
X
X
X // This is a physical memory of the computer
Xclass Memory : public DiagnosticPanel
X{
X Word array[1024]; // Memory itself
X int drum_fh; // File handle of a drum device
X
Xpublic:
X const Address hiaddr = 1023; // The largest memory address
X const short pagesize = 32; // Size of the memory page in words
X // = size of the drum sector
X const short no_drum_sectors = 256;
X const short no_pages; // No of physical pages into the memory
X
Xpublic:
X Memory(void);
X ~Memory(void) {}
X
X // Basic operation to get hold of a
X // word of memory given its address
X struct MemoryAnswer {char out_of_range; Word& contents;};
X MemoryAnswer operator [] (const Address addr)
X { if( addr > hiaddr )
X { static Word dummy; MemoryAnswer ans = {1,dummy}; return ans;}
X else {MemoryAnswer ans = {0,array[addr]}; return ans;} }
X
X
X void dump(const Address from, const Address to); // Dump the memory context
X
X void drum_open(const char * file_name);
X void drum_read(const int sector_addr, const int pageframeno);
X void drum_write(const int pageframeno,const int sector_addr);
X // Load a program from the drum into the
X // memory and return its starting address
X Address drum_load(const int pageframeno);
X};
X
X
Xstruct MMUContext // This is the context of the MMU
X{
X Address page_table_addr; // Page table addr in the phys memory
X short page_table_len; // No of entries in the page table
X // (size of the virtual space in pages)
X char enabled_address_translation;
X
X struct VirtualMemoryAddr {
X unsigned short
X offset : 5, // Offset within the page
X page_no : 5, // Page no
X reserved: 6;
X };
X
X struct PageTableEntry {
X unsigned short
X phys_page_no: 5, // No for the physical page
X reserved: 3, // Reserved (always 0)
X valid: 1, // 0 means no access is possible
X any_access: 1, // 1 means READ/WRITE/EXEC is allowed
X read_only: 1, // 1 means WRITE access is forbidden
X exec_only: 1, // 1 means only EXEC access is allowed
X was_ref: 1, // The page was referenced
X was_written: 1; // The page was modified by WRITE
X };
X
X
X MMUContext(void);
X virtual ~MMUContext(void) {}
X};
X
X // This part is responsible for the virtual-to
X // real address translation
Xclass MemoryManagementUnit : public MMUContext
X{
Xpublic:
X Memory& memory; // Memory this unit manages
X
Xpublic:
X enum MemoryFault {None, OutofRange, WrongPageTable, WrongVPageNo,
X PageInvalidated, NoAccess, ReadOnly, ExecOnly};
Xprivate:
X MemoryFault mem_error;
X VirtualMemoryAddr current_VA; // Address under translation
X
Xpublic:
X MemoryManagementUnit(Memory& phys_memory);
X virtual ~MemoryManagementUnit(void) {}
X
X Word fetch(const Address addr); // Fetch a word from memory in
X // an EXECUTE memory mode
X Word get(const Address addr); // Read a word from memory
X // Write a word to memory
X void put(const Address addr,const Word data);
X
X MemoryFault what_fault(void) const { return mem_error; }
X int got_fault(void) const { return mem_error != None; }
X VirtualMemoryAddr q_current_VA(void) { return current_VA; }
X void clear_error(void) { mem_error = None; }
X
X // Dump the physical memory
X void dump_phys_memory(const Address from, const Address to)
X { memory.dump(from,to); }
X // Load a program from the drum into the
X // memory and return its starting address
X // The program is in absolute format
X Address absolute_drum_load(const int pageframeno)
X { return memory.drum_load(pageframeno); }
X
X void dump(void) const; // Dump the info in the table
X};
X
X/*
X *------------------------------------------------------------------------
X * A Central Processing Unit
X */
X
Xstruct Context
X{
X Word Registers[16]; // Registers pool
X Word pc; // Program Counter
X
X Context(void); // Constructor (initializer)
X ~Context(void) {}
X
X Word& operator [] (const int reg_number); // Get a ref to the register
X void copy_context(const Context& a_context);
X void dump(void) const; // Dump the context
X};
X
Xclass CentralProcessingUnit :
X public Context, public MemoryManagementUnit, public DiagnosticPanel
X{
X Semaphore stopped; // 0 if running, 1 can run, -1 stopped
X
X // Instruction being executed
X enum OpCodes opcode; // Opcode of the current instruction
X short inst_length; // Length in words
X InstructionWord1 iword1;
X InstructionWord2 iword2;
X short svcop; // The code of the SVC instruction
X Address EA; // Effective address
X
X int execute_instruction(void); // Execute the current instruction
X // Return true if can continue
X
Xpublic:
X short clock; // Generate a trap when going negative
X
X enum TRAPCODE { NONE, ILLEGOP, SVCCALL, CLOCKINT, MEMORY };
Xprivate:
X Semaphore trap_signal; // V(trap_signal) when any traps occurs
X enum TRAPCODE trap_code;
X
Xpublic:
X CentralProcessingUnit(Memory & cpu_memory);
X ~CentralProcessingUnit(void) {}
X
X void start(void); // Start the CPU from the current value
X // of PC. Do nothing if already running
X void stop(void); // Stop the CPU after executing the
X // current instruction
X
X // CPU status inquires
X int is_running(void) { return !stopped.awaited(); }
X void wait_for_trap(void) { trap_signal--; }
X
X TRAPCODE q_trap_code(void) const { return trap_code; }
X OpCodes q_opcode(void) const { return opcode; }
X short q_svcop(void) const { return svcop; }
X Word q_RegA(void) const { return iword1.areg; }
X Address q_EA(void) const { return EA; }
X
X void dump(void) const; // Tell what's going on
X};
X
X/*
X *------------------------------------------------------------------------
X * An I/O channel processing unit
X */
X
Xclass IOChannel;
X
X // I/O bus all the channels are hooked to
Xclass IOBus : public DiagnosticPanel
X{
X // Note, the numeration of channels
X const int max_no_channels = 4; // starts from one
X unsigned short no_channels;
X IOChannel * channels[max_no_channels];
X
Xpublic:
X IOBus(void);
X ~IOBus(void) {}
X
X // Connects a channel to the i/o bus
X // and returns its number on the bus
X int connect_channel(IOChannel * channel);
X
X // Start a channel program on a
X // specified channel. Return FALSE
X // if the operation was rejected
X // upfront
X int start(const unsigned short channel_no, const Address ccw_ptr);
X
X void dump(void); // Dump info about all the channels
X};
X
X
Xclass IOChannel : public DiagnosticPanel
X{
Xprivate:
X Semaphore stopped; // 0 if running, 1 can run, -1 stopped
X short channel_no; // Starts with 1
X
Xpublic:
X Memory& memory; // Memory to read/write to/from
X
Xprivate:
X // CCW being executed
X Address cpc; // Channel program counter
X CCW current_CCW;
X enum CCWOpCodes opcode; // Opcode of the current CCW
X unsigned short buf_page; // Page no of the I/O buffer
X
Xprotected:
X // Current I/O status
X const int rec_size = Memory::pagesize;// For any I/O operation
X unsigned short rec_count; // The number of the current records
X // to transfer
X Word io_buffer[rec_size]; // I/O buffer
X
X int file_handle; // File handle of the UNIX device that
X // emulates the channel
X
Xprivate:
X // Transfer between the memory and the
X // i/o buffer. The routines below return
X // FALSE if a problem occurred.
X int get_record(const int page_no); // Get a record from memory
X int put_record(const int page_no); // Put a record from memory
X
Xpublic:
X enum STATCODE { OK, CCWADDR, MEMORY, ILLEGOP, END_FILE, SEEKADDR, DEVICE };
Xprivate:
X enum STATCODE status;
X
X Semaphore intr_signal; // V(intr_signal) when any channel
X // interrupt occurs
X STATCODE execute_CCW(void); // Execute the current CCW and report
X // the status
Xprotected:
X // This routine performs device-specific
X // operations. The routine should transfer
X // the io_buffer to/from the device and set
X // the rec_counter.
X enum DEVICE_OP {DEV_READ, DEV_SEEK, DEV_WRITE};
X virtual STATCODE device_driver(const DEVICE_OP dev_op) = 0;
X
Xpublic:
X IOChannel(Memory& main_memory, IOBus& io_bus);
X ~IOChannel(void) {}
X
X void start(Address channel_program_ptr);// Start the channel
X
X // Channel status inquires
X int q_channel_no(void) const { return channel_no; }
X int is_running(void) { return !stopped.awaited(); }
X void wait_for_interrupt(void) { intr_signal--; }
X
X STATCODE q_status(void) const { return status; }
X int q_buf_page(void) const { return buf_page; }
X
X void dump(void) const; // Tell what's going on
X
X // Open the UNIX file the channel is associated
X // with
X void associate_with_unix_file(const char * file_name);
X};
X
X // Device specific stuff
Xclass CardReader : public IOChannel
X{
X void * in_file; // FILE * in_file
X
X virtual STATCODE device_driver(const DEVICE_OP dev_op);
X
Xpublic:
X CardReader(Memory& main_memory, IOBus& io_bus);
X ~CardReader(void) {}
X};
X
Xclass LinePrinter : public IOChannel
X{
X virtual STATCODE device_driver(const DEVICE_OP dev_op);
X
Xpublic:
X LinePrinter(Memory& main_memory, IOBus& io_bus) :
X IOChannel(main_memory,io_bus) {}
X ~LinePrinter(void) {}
X};
X
Xclass HardDisk : public IOChannel
X{
X const int hi_disk_addr = 1023;
X const int disk_sector_size = Memory::pagesize * sizeof(Word); // in bytes
X
X virtual STATCODE device_driver(const DEVICE_OP dev_op);
X
Xpublic:
X HardDisk(Memory& main_memory, IOBus& io_bus) :
X IOChannel(main_memory,io_bus) {}
X ~HardDisk(void) {}
X};
X
X#endif
X
END_OF_FILE
if test 10975 -ne `wc -c <'hardware.h'`; then
echo shar: \"'hardware.h'\" unpacked with wrong size!
fi
# end of 'hardware.h'
fi
if test -f 'io_manager.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'io_manager.h'\"
else
echo shar: Extracting \"'io_manager.h'\" \(4764 characters\)
sed "s/^X//" >'io_manager.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X * I/O Manager
X *
X * Handles I/O devices and I/O requests asynchronously of the
X * CPU manager. There is a separate I/O manager thread associated with
X * each device. Communication between the CPU manager and I/O manager
X * is asynchronous and based on queue of request blocks.
X *
X ************************************************************************
X */
X
X#ifndef _io_manager_h
X#define _io_manager_h 1
X#pragma interface
X
X#include "hardware.h"
X#include "sysqueues.h"
X#include "processes.h"
X
X/*
X *------------------------------------------------------------------------
X * I/O requests
X * I/O request presents a unit of work for the I/O channel manager.
X * It keeps all the information necessary to initiate the I/O and reply
X * the results back.
X */
X
Xtypedef unsigned short RID; // I/O Request ID
Xconst RID NIL_rid = 0; // Other RIDs are positive
X
Xclass IORequestTable;
Xclass IOManager;
Xclass IOChannelManager;
X
Xclass IORequest : public QueueLink
X{
X friend class IORequestTable;
X friend class IOManager;
X friend class IOChannelManager;
X
X PID pid; // PID of the process requested I/O
X enum {IO_READ, IO_WRITE} operation; // The following describes the I/O
X Word device_no; // to perform
X Address buffer_ptr;
X Word rec_count;
X Word disk_address;
X Address return_code_vptr; // This is a virtual memory ptr
X Address return_code_pptr; // This is a physical memory ptr
X int return_code; // Return code of the operation
X
X const int max_no_recs = 8; // Physical addresses of the pages
X Address io_pages[max_no_recs]; // to transmit during the I/O
X
Xpublic:
X IORequest(void);
X ~IORequest(void) {}
X void dump(void) const; // Tell what's going on
X void dispose(void); // Dispose of the given request block
X};
X
X
Xclass IORequestTable
X{
X IORequest * reqs; // Array of IOrequests
X const int nslots; // No. of request slots
X
X BasicQueue freeIORs; // Queue of free IORequests
X
Xpublic:
X IORequestTable(const int no_slots);
X ~IORequestTable(void) {}
X
X IORequest& operator [] (const RID pid) const; // Get a IORequest by its id
X RID new_request(void); // Create a new request
X void dispose(const RID rid); // Dispose of the request
X void dump(void) const; // Tell what's going on
X};
X
X/*
X *------------------------------------------------------------------------
X * Input/output request managers
X */
X
X // Class IOManager provides the data structures
X // and function which are used both by CPU
X // manager and I/O Channel manager threads to
X // talk to each other.
Xclass IOChannelManager;
Xclass CPUManager;
X
Xclass IOManager : public DiagnosticPanel
X{
X CPUManager& cpu_manager;
X
X const int max_no_channels = 4; // Note, the channel no. starts from 1
X IOChannelManager * channel_managers[max_no_channels];
X
Xpublic:
X IORequestTable requests;
X
X IOManager(CPUManager& _cpu_manager);
X ~IOManager(void) {}
X void dump(void) const; // Tell what's going on
X
X // Register a channel manager with
X // the IO manager
X void register_channel(const int chan_no,IOChannelManager * _channel_manager);
X
X // The following procedures are used by
X // the CPU manager thread to submit the request
X // Return FALSE in case of problem
X int submit_request(const PID pid,const OpCodes opcode,Address IO_params);
X int scrutinize_request(IORequest& req);// and perform locking and translation
X void queue_request(IORequest& req); // and queue the request
X
X // The following procedures are used by the
X // I/O channel manager thread to reply back
X void request_completed(IORequest& req);// Handle the request completion
X
X Address reserve_physical_page(); // Reserve a page and give its address
X};
X
X // Manager of a channel
Xclass IOChannelManager
X{
X IOChannel& channel; // Channel to handle
X IOManager& io_manager; // General I/O manager
X IORequest * serviced_request; // The IO request being serviced
X
X BasicQueue to_serviceIORs; // Queue of requests to service
X
X Address ccw_area; // Reserved page of the physical
X // memory for constructing CCW
X
Xpublic:
X IOChannelManager(IOChannel& _channel, IOManager& _io_manager);
X ~IOChannelManager(void) {}
X
X void dump(void) const; // Tell what's going on
X void submit_request(IORequest& req) // Submit the request
X { to_serviceIORs.append(req); }
X int initiate_io(RID rid); // Initiate the I/O for the request
X
X // Read/write a word from/to the
X // PHYSICAL memory associated with
X // the channel
X // Error is fatal
X void read_word_phys_memory(const Address ra, Word& dest);
X void write_word_phys_memory(const Address ra, Word src);
X};
X
X#endif
END_OF_FILE
if test 4764 -ne `wc -c <'io_manager.h'`; then
echo shar: \"'io_manager.h'\" unpacked with wrong size!
fi
# end of 'io_manager.h'
fi
if test -f 'memory.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'memory.cc'\"
else
echo shar: Extracting \"'memory.cc'\" \(10930 characters\)
sed "s/^X//" >'memory.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X * Handle real and virtual memory requests and the "drum"
X *
X * One part of the present file implements the Mememory Management Unit,
X * a piece of hardware located between the CPU and the bus and responsible
X * for translation of virtual addresses into the "real" ones.
X * The other part of the present file emulates the physical memory,
X * which is connected to the bus and responds to read/write word
X * requests posted on the bus. The drum is a secondary memory device
X * which is hooked to the physical memory and can transmit sectors
X * of the drum to/from pages of the memory. The drum is assummed to be
X * very fast, so all the drum operations can be thought of as "instant"
X * ones.
X *
X ************************************************************************
X */
X
X#pragma implementation
X#include "hardware.h"
X#include "myenv.h"
X#include <std.h>
X#include <sys/file.h>
X
X
X/*
X *========================================================================
X * Virtual memory handling
X */
X
XMMUContext::MMUContext(void)
X{
X page_table_addr = 0;
X page_table_len = 0;
X enabled_address_translation = 0;
X}
X
XMemoryManagementUnit::MemoryManagementUnit(Memory& phys_memory)
X : memory(phys_memory)
X{
X *(Word *)¤t_VA = 0;
X clear_error();
X};
X
X // Perform dump of the translation tables
Xvoid MemoryManagementUnit::dump(void) const
X{
X if(!enabled_address_translation)
X {
X message("\nVirtual memory is disabled\n");
X return;
X }
X message("\nProcess virtual space is %d pages long\n",page_table_len);
X message("\nAddress range\tAccess\tMapped to \tWritten\tReferenced\n");
X register int i;
X for(i=0; i<page_table_len; i++)
X {
X const PageTableEntry& pte =
X *(PageTableEntry*)&memory[page_table_addr+i].contents;
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 %s\t %s\n",pte.was_written ? "Y" : "N",
X pte.was_ref ? "Y" : "N");
X }
X message("\n");
X}
X
XWord MemoryManagementUnit::fetch(const Address addr)
X{
X Address phys_addr;
X if(enabled_address_translation)
X {
X *(Address *)¤t_VA = addr;
X if(current_VA.page_no >= page_table_len)
X mem_error = WrongVPageNo;
X else if( memory[page_table_addr+current_VA.page_no].out_of_range )
X mem_error = WrongPageTable;
X if( mem_error )
X return 0;
X PageTableEntry& pte = *(PageTableEntry *)&memory[
X page_table_addr+current_VA.page_no].contents;
X if(!pte.any_access && !pte.read_only && !pte.exec_only )
X mem_error = NoAccess;
X else if( !pte.valid )
X mem_error = PageInvalidated;
X else
X current_VA.page_no = pte.phys_page_no,
X pte.was_ref = 1;
X
X if( mem_error )
X return 0;
X phys_addr = *(Address *)¤t_VA;
X }
X else
X phys_addr = addr;
X
X Memory::MemoryAnswer result = memory[phys_addr];
X if(result.out_of_range)
X {
X mem_error = enabled_address_translation ? WrongPageTable : OutofRange;
X return 0;
X }
X
X return result.contents;
X}
X
X
XWord MemoryManagementUnit::get(const Address addr)
X{
X Address phys_addr;
X if(enabled_address_translation)
X {
X *(Address *)¤t_VA = addr;
X if(current_VA.page_no >= page_table_len)
X mem_error = WrongVPageNo;
X else if( memory[page_table_addr+current_VA.page_no].out_of_range )
X mem_error = WrongPageTable;
X if( mem_error )
X return 0;
X PageTableEntry& pte = *(PageTableEntry *)&memory[
X page_table_addr+current_VA.page_no].contents;
X if(!pte.any_access && !pte.read_only && !pte.exec_only )
X mem_error = NoAccess;
X else if( pte.exec_only )
X mem_error = ExecOnly;
X else if( !pte.valid )
X mem_error = PageInvalidated;
X else
X current_VA.page_no = pte.phys_page_no,
X pte.was_ref = 1;
X
X if( mem_error )
X return 0;
X phys_addr = *(Address *)¤t_VA;
X }
X else
X phys_addr = addr;
X
X Memory::MemoryAnswer result = memory[phys_addr];
X if(result.out_of_range)
X {
X mem_error = enabled_address_translation ? WrongPageTable : OutofRange;
X return 0;
X }
X
X return result.contents;
X}
X
Xvoid MemoryManagementUnit::put(const Address addr,const Word data)
X{
X Address phys_addr;
X if(enabled_address_translation)
X {
X *(Address *)¤t_VA = addr;
X if(current_VA.page_no >= page_table_len)
X mem_error = WrongVPageNo;
X else if( memory[page_table_addr+current_VA.page_no].out_of_range )
X mem_error = WrongPageTable;
X if( mem_error )
X return;
X PageTableEntry& pte = *(PageTableEntry *)&memory[
X page_table_addr+current_VA.page_no].contents;
X if(!pte.any_access && !pte.read_only && !pte.exec_only )
X mem_error = NoAccess;
X else if( pte.read_only )
X mem_error = ReadOnly;
X else if( pte.exec_only )
X mem_error = ExecOnly;
X else if( !pte.valid )
X mem_error = PageInvalidated;
X else
X current_VA.page_no = pte.phys_page_no,
X pte.was_ref = 1,
X pte.was_written = 1;
X
X if( mem_error )
X return;
X phys_addr = *(Address *)¤t_VA;
X }
X else
X phys_addr = addr;
X
X Memory::MemoryAnswer result = memory[phys_addr];
X if(result.out_of_range)
X mem_error = enabled_address_translation ? WrongPageTable : OutofRange;
X else
X result.contents = data;
X}
X
X
X/*
X *========================================================================
X * Physical Memory handling
X */
X
X/*
X *------------------------------------------------------------------------
X * Initialization
X */
X
XMemory::Memory(void)
X : no_pages((hiaddr+1)/pagesize)
X{
X memset(array,0,sizeof(array)); // Clear the memory
X drum_fh = -1;
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Basic memory handling functions
X */
X
X#if 0
Xstruct MemoryAnswer Memory::operator [] (const Address addr) //return ans
X{
X if( addr > hiaddr )
X ans.out_of_range = 1, contents = array[0];
X else
X ans.out_of_range = 0, contents = array[addr];
X}
X#endif
X
X/*
X *------------------------------------------------------------------------
X * Memory Dump
X * Memory contents is printed in rows of 8 words in each.
X * Rows of zeros are skipped. Contents of a memory word is printed in octal.
X */
X
Xvoid Memory::dump(const Address from_addr,const Address to_addr)
X{
X register Address first_addr = from_addr & ~7; // Adjust to the 8 word
X register Address last_addr = to_addr & ~7 + 8;// boundary
X if( last_addr == 0 || last_addr > hiaddr+1 )
X last_addr = hiaddr+1;
X
X begin_printing();
X message("\n\n%s\n\n\t\t\tVM UNT Memory Dump\n\n",_Minuses);
X for(; first_addr < last_addr; first_addr += 8)
X {
X register int i;
X int skip = 1;
X for(i=first_addr; skip && i<first_addr+8; i++)
X if( array[i] != 0 )
X skip = 0;
X if( skip )
X continue; // Skip a line of zeros
X message("%4o: ",first_addr);
X for(i=first_addr; i<first_addr+8; i++)
X message(" %06o ",array[i]);
X message("\n");
X }
X end_printing();
X}
X
X/*
X *------------------------------------------------------------------------
X * Drum operations
X * Note, that the program to be loaded from the drum into the main memory
X * is written started from the 1st drum sector. The 0th drum sector contains
X * the header, starting address of the program, VM memory page to load
X * the program at, and the size of the program in pages (i.e. in drum sectors).
X */
X
Xvoid Memory::drum_open(const char * file_name)
X{
X drum_fh = open(file_name,O_RDWR,0);
X if( drum_fh < 0 )
X perror("Drum file opening error"),
X _error("Failure to open the drum due to the reason above");
X single_message("Drum file '%s' has been opened",file_name);
X}
X
X // Read one 32 word page from drum
X // sector to memory physical page
X // 'pageframeno'
Xvoid Memory::drum_read(const int sector_addr, const int pageframeno)
X{
X single_message("DRUM: reading from sector %d in memory page %d",
X sector_addr,pageframeno);
X if( sector_addr < 0 || sector_addr >= no_drum_sectors )
X _error("FATAL: drum sector %d is out of range [0,%d]",
X sector_addr,no_drum_sectors-1);
X
X if( pageframeno < 0 || pageframeno >= no_pages )
X _error("FATAL on drum operation: page frame no %d is out of range [0,%d]",
X pageframeno,no_pages-1);
X
X if( lseek(drum_fh,sector_addr*pagesize*sizeof(Word),0) < 0 )
X perror("FATAL: drum seek failed"),
X _error("System crashes due to the reason above");
X
X if( read(drum_fh,&array[pageframeno*pagesize],pagesize*sizeof(Word))
X != pagesize*sizeof(Word) )
X perror("FATAL: drum read failed"),
X _error("System crashes due to the reason above");
X}
X
X // Write a page of physical memory into
X // the drum
Xvoid Memory::drum_write(const int pageframeno,const int sector_addr)
X{
X single_message("DRUM: writing to sector %d from memory page %d",
X sector_addr,pageframeno);
X if( sector_addr < 0 || sector_addr >= no_drum_sectors )
X _error("FATAL: drum sector %d is out of range [0,%d]",
X sector_addr,no_drum_sectors-1);
X
X if( pageframeno < 0 || pageframeno >= no_pages )
X _error("FATAL on drum operation: page frame no %d is out of range [0,%d]",
X pageframeno,no_pages-1);
X
X if( lseek(drum_fh,sector_addr*pagesize*sizeof(Word),0) < 0 )
X perror("FATAL: drum seek failed"),
X _error("System crashes due to the reason above");
X
X if( write(drum_fh,&array[pageframeno*pagesize],pagesize*sizeof(Word))
X != pagesize*sizeof(Word) )
X perror("FATAL: drum write failed"),
X _error("System crashes due to the reason above");
X}
X
X // Load a program from a drum to
X // memory starting at physical page
X // 'pageframeno'
XAddress Memory::drum_load(const int pageframeno)
X{
X if( pageframeno < 0 || pageframeno >= no_pages )
X _error("FATAL on loading operation: "
X "page frame no %d is out of range [0,%d]",
X pageframeno,no_pages-1);
X
X struct AbsExecHeader { // Header of the executable abs file
X Word start_addr; // Starting address
X Word load_page_no; // VM page to load the program
X Word size; // in pages
X } header;
X
X if( lseek(drum_fh,0,0) < 0 ) // Read the drum header
X perror("FATAL: drum seek failed"),
X _error("System crashes due to the reason above");
X if( read(drum_fh,&header,sizeof(header)) != sizeof(header) )
X perror("FATAL: drum read failed"),
X _error("System crashes due to the reason above");
X
X single_message("Loading a program (size %d, start addr %06o) on %d-th page",
X header.size*pagesize,header.start_addr,header.load_page_no);
X register int i;
X for(i=0; i<header.size; i++)
X drum_read(1+i,header.load_page_no+i);
X return header.start_addr;
X}
X
END_OF_FILE
if test 10930 -ne `wc -c <'memory.cc'`; then
echo shar: \"'memory.cc'\" unpacked with wrong size!
fi
# end of 'memory.cc'
fi
if test -f 'myenv.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'myenv.h'\"
else
echo shar: Extracting \"'myenv.h'\" \(1362 characters\)
sed "s/^X//" >'myenv.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X//************************************************************************
X//
X// A standard environment
X// I am accustomed to
X
X//#pragma once
X#ifndef _myenv_h
X
X#define _myenv_h
X#pragma interface
X
X /* Strings of symbols */
X /* They may be used as a delimiting lines*/
Xextern const char _Minuses [];
Xextern const char _Asteriscs [];
Xextern const char _Equals [];
X
X /* Print an error message at stderr and */
X /* abort */
Xvolatile void _error(
X const char * message, /* Message to be printed */
X ... /* Additional args to printf */
X );
X
X /* Print a message at stderr */
Xvoid message(
X const char * text, /* Message to be printed */
X ... /* Additional args to printf */
X );
X
X
X//------------------------------------------------------------------------
X// Verify the assertion
X
X#if 0
X /* Print a message and abort*/
Xextern volatile void _error( const char * message,... );
X#endif
X
X#define assert(ex) \
X (void)((ex) ? 1 : \
X (_error("Failed assertion " #ex " at line %d of `%s'.\n", \
X __LINE__, __FILE__), 0))
X#define assertval(ex) assert(ex)
X
X#define assure(expr,message) \
X if (expr) ; \
X else _error("%s\n at line %d of '%s'.",message,__LINE__, __FILE__);
X
X
X#endif
END_OF_FILE
if test 1362 -ne `wc -c <'myenv.h'`; then
echo shar: \"'myenv.h'\" unpacked with wrong size!
fi
# end of 'myenv.h'
fi
if test -f 'oper_system.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'oper_system.cc'\"
else
echo shar: Extracting \"'oper_system.cc'\" \(11496 characters\)
sed "s/^X//" >'oper_system.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 "oper_system.h"
X#include "oper_system.h"
X#include "myenv.h"
X
X/*
X *------------------------------------------------------------------------
X * Initializing the operating system
X */
X
XOperatingSystem::OperatingSystem(void)
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 OperatingSystem::commence(void)
X{
X running_pcb = &(*this)[new_pid()];
X running_pcb->status = PCB::Ok;
X running_pcb->pc = memory.drum_load(0);
X prepare_for_running();
X CPU.start();
X}
X
X/*
X *------------------------------------------------------------------------
X * TRAP handler
X */
X
XHANDLER_STATUS
XOperatingSystem::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
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 single_message("Memory Fault");
X return DISPATCH;
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 OperatingSystem::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 semaphore for a process
Xvoid OperatingSystem::prepare_for_running(void)
X{
X assert( running_pcb != 0 );
X assert( !CPU.is_running() );
X CPU.load_context(*running_pcb);
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 OperatingSystem::save_context(void)
X{
X assert( running_pcb != 0 );
X assert( !CPU.is_running() );
X (*running_pcb).load_context((Context&)CPU);
X}
X
X // Terminate the currently running process
XHANDLER_STATUS OperatingSystem::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 OperatingSystem::dispatch(void)
X{
X if( readyPCBs.is_empty() )
X Halt++;
X running_pcb = &(*this)[readyPCBs.get_from_head()->id];
X prepare_for_running();
X}
X
X/*
X *------------------------------------------------------------------------
X * Dump whatever goes on in the system
X */
X
Xvoid OperatingSystem::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 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 OperatingSystem::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.status = PCB::Ok;
X son_pcb.parent = dad_pcb.id;
X son_pcb.lchild = son_pcb.rchild = NIL_pid;
X son_pcb.load_context(dad_pcb);
X son_pcb[rega] = dad_pcb.id;
X son_pcb.pc = EA;
X
X if( dad_pcb.lchild == NIL_pid )
X dad_pcb.lchild = son_pcb.id;
X else
X dad_pcb.rchild = son_pcb.id;
X dad_pcb[rega] = son_pcb.id;
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 OperatingSystem::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 OperatingSystem::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 kill((*this)[pid]);
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 */
X
Xvoid OperatingSystem::kill(PCB& 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 OperatingSystem::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 * OperatingSystem::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 OperatingSystem::semaphore_p(const SID sid)
XHANDLER_STATUS OperatingSystem::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}
END_OF_FILE
if test 11496 -ne `wc -c <'oper_system.cc'`; then
echo shar: \"'oper_system.cc'\" unpacked with wrong size!
fi
# end of 'oper_system.cc'
fi
echo shar: End of archive 2 \(of 4\).
cp /dev/null ark2isdone
Kiselyov Oleg
Posting-number: Volume 44, Issue 55
Archive-name: toy_os/part03
Environment: GNU C++ 2.2
#! /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: bootstrap.cc computer.h cpu_manager.h five.a io_manager.cc
# mem_manager.h page_manager.cc processes.cc semaphores.cc
# Wrapped by kent@sparky on Mon Sep 5 13:12:56 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 3 (of 4)."'
if test -f 'bootstrap.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'bootstrap.cc'\"
else
echo shar: Extracting \"'bootstrap.cc'\" \(4388 characters\)
sed "s/^X//" >'bootstrap.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 * "Booting up" the virtual machine
X *
X * This is the main module that boots up the virtual machine and lets
X * it run.
X * Parameters (specified in the command while calling the vm_unt)
X *
X * vm_unt [-card=card_file] [-lp=printer_file] [-harddisk=disk_file]
X * drum_file_name
X *
X * where drum_file_name specifies the file to be used for drum
X * operations.
X *
X * $Id: bootstrap.cc,v 5.0 1992/11/15 18:17:39 oleg Exp oleg $
X *
X ************************************************************************
X */
X
X#pragma implementation "hardware.h"
X#pragma implementation "computer.h"
X#pragma implementation "oper_system.h"
X#include "oper_system.h"
X#include "myenv.h"
X#include <std.h>
X#include <stdarg.h>
X
X/*
X *------------------------------------------------------------------------
X * Diagnostics
X */
X
XSemaphore DiagnosticPanel::printing_diagnostics("Diagnostics",1);
X
XDiagnosticPanel::DiagnosticPanel(void)
X{
X is_tracing = 1;
X}
X
X // Print the message only if tracing is on
Xvoid DiagnosticPanel::single_message(const char * text,...)
X{
X if( !is_tracing )
X return;
X printing_diagnostics--;
X va_list args;
X va_start(args,text);
X fprintf(stderr,"\n");
X vfprintf(stderr,text,args);
X fprintf(stderr,"\n");
X printing_diagnostics++;
X}
X
X // Print a message on the operator console
Xvoid DiagnosticPanel::console(const char * text,...)
X{
X printing_diagnostics--;
X va_list args;
X va_start(args,text);
X fprintf(stderr,"\n");
X vfprintf(stderr,text,args);
X fprintf(stderr,"\n");
X printing_diagnostics++;
X}
X
Xvoid DiagnosticPanel::begin_printing(void)
X{
X printing_diagnostics--;
X}
X
Xvoid DiagnosticPanel::end_printing(void)
X{
X printing_diagnostics++;
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Root module of the VM UNT
X */
X
X
X // Print the help as how to use the program
Xstatic volatile void help_usage(const char * error_message)
X{
X message("\n%s\n",error_message);
X message("\n\n\t\tRunning the UNT Virtual Machine\n");
X message("\nUsage");
X message("\n\tvm_unt [-card=card_file] [-lp=printer_file]");
X message("\n\t\t[-harddisk=disk_file] drum_file_name");
X message("\n\nwhere\n");
X message("\tfile names specify files to be used by the corresponding\n");
X message("\tVM_UNT \"devices\"\n");
X message("\n\nExample:");
X message("\n\tvm_unt test.dat\n\n");
X exit(4);
X}
X
Xstatic char card_file_name[40];
Xstatic char printer_file_name[40];
Xstatic char hdisk_file_name[40];
X
X // Scan through the command parameters in
X // search for options.
X // Return the no. of options parsed
Xstatic int parse_options(const int argc, char * argv[])
X{
X int noptions;
X for(noptions=0; noptions < argc-1; noptions++)
X {
X char * str = argv[1+noptions]; // argv[0] is a pgm name, skip
X if( *str++ != '-' ) // Option should begin with -
X break;
X
X char * p = strchr(str,'=');
X if( p == 0 )
X message("\nFailed to find '=' in option '%s'\n",str),
X help_usage("");
X
X if( strncmp(str,"card",p-str) == 0 )
X strncpy(card_file_name,p+1,sizeof(card_file_name)-1);
X else if( strncmp(str,"lp",p-str) == 0 )
X strncpy(printer_file_name,p+1,sizeof(printer_file_name)-1);
X else if( strncmp(str,"harddisk",p-str) == 0 )
X strncpy(hdisk_file_name,p+1,sizeof(hdisk_file_name)-1);
X else
X message("Unknown option - '%s'\n",str),
X help_usage("");
X }
X return noptions;
X}
X
X
X // This is a bootstrap
Xmain(const int argc, const char * argv[])
X{
X extern int _stackint;
X const int noptions = parse_options(argc,argv);
X if( argc != 1 + noptions + 1 )
X help_usage("One parameter (drum file name) has got to be specified");
X
X asm("movl %esp,__stackinit");
X static OperatingSystem VM_UNT;
X VM_UNT.memory.drum_open(argv[1+noptions]);
X if( card_file_name[0] != '\0' )
X VM_UNT.card_reader.associate_with_unix_file(card_file_name);
X if( printer_file_name[0] != '\0' )
X VM_UNT.line_printer.associate_with_unix_file(printer_file_name);
X if( hdisk_file_name[0] != '\0' )
X VM_UNT.hard_disk.associate_with_unix_file(hdisk_file_name);
X VM_UNT.cpu_manager.commence();
X
X VM_UNT.cpu_manager.wait_for_halt();
X message("\n\n\n>>>>>>>>>>>>>>>>>> Computer is halted "
X "<<<<<<<<<<<<<<<<<<<<<\n\n");
X}
END_OF_FILE
if test 4388 -ne `wc -c <'bootstrap.cc'`; then
echo shar: \"'bootstrap.cc'\" unpacked with wrong size!
fi
# end of 'bootstrap.cc'
fi
if test -f 'computer.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'computer.h'\"
else
echo shar: Extracting \"'computer.h'\" \(778 characters\)
sed "s/^X//" >'computer.h' <<'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 file describes the configuarion of the virtual computer,
X * i.e. all the pieces it is built from
X *
X ************************************************************************
X */
X
X#ifndef _computer_h
X#define _computer_h 1
X#pragma interface
X
X#include "hardware.h"
X
Xclass Computer
X{
Xpublic:
X Memory memory;
X CentralProcessingUnit CPU;
X IOBus io_bus;
X CardReader card_reader;
X LinePrinter line_printer;
X HardDisk hard_disk;
X
Xpublic:
X Computer(void) : CPU(memory), card_reader(memory,io_bus),
X line_printer(memory,io_bus),
X hard_disk(memory,io_bus) {}
X
X ~Computer(void) {}
X};
X
X#endif
X
END_OF_FILE
if test 778 -ne `wc -c <'computer.h'`; then
echo shar: \"'computer.h'\" unpacked with wrong size!
fi
# end of 'computer.h'
fi
if test -f 'cpu_manager.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'cpu_manager.h'\"
else
echo shar: Extracting \"'cpu_manager.h'\" \(3955 characters\)
sed "s/^X//" >'cpu_manager.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X *
X * CPU Manager
X * Manages the most important and the leading resource in the computer.
X * It handles all the interrupts (which are CPU interrupts), and
X * all the system gets activity through it. Implements the concept of
X * the process.
X *
X ************************************************************************
X */
X
X#ifndef _cpu_manager_h
X#define _cpu_manager_h 1
X#pragma interface
X
X#include "hardware.h"
X#include "semaphores.h"
X#include "mem_manager.h"
X
Xenum SVCCODE { DUMP_STATUS=1, FORK, WAIT_KIDS, SEMINIT, SEM_P, SEM_V, KILL };
Xenum HANDLER_STATUS { RESUME, DISPATCH };
X
Xclass IOManager;
X
Xclass CPUManager : public ProcessTable
X{
X CentralProcessingUnit& CPU; // CPU to manage
X MemoryManager& memory_manager; // Manager of the memory
X IOManager& io_manager; // Manager of I/O
X
X const int Time_quant = 10; // In clock units
X Semaphore Halt; // V(Halt) to halt the system
X
X PCB * running_pcb; // Ptr to the running PCB (which is
X // in none of the queues)
X
X BasicQueue readyPCBs; // Queue of ready processes
X SemaphoreTable * semas;
X
X // Handlers
X HANDLER_STATUS trap_handler(const CentralProcessingUnit::TRAPCODE trap_code);
X HANDLER_STATUS svc_handler(const SVCCODE svc_code);
X HANDLER_STATUS mfault_handler(const MemoryManagementUnit::MemoryFault code);
X HANDLER_STATUS initiate_IO(const OpCodes opcode,Address IO_params);
X
X HANDLER_STATUS terminate(); // Terminate the current process
X void dispatch(); // Pick up a new process to run
X void prepare_for_running(); // Prepare running_pcb for running
X void save_context(); // Save the CPU context in
X // the running_pcb
X void kill(PCB & pcb); // Kill the process
X void dump(void); // Dump the current OS status
X
X // Create a new process at EA.
X HANDLER_STATUS fork(const int rega,Address EA); // put PID in rega
X HANDLER_STATUS wait_for_kids(void); // Wait for kids to terminate
X HANDLER_STATUS shoot(const PID pid); // Try to kill the process
X
X // Create a new semaphore with
X // initial value EA. Put SID in rega
X HANDLER_STATUS create_semaphore(const int rega,Address EA);
X
X // Check to see that the Sema is valid
X // to perform P or V operation on.
X Sema * valid_semaphore(const SID sid);
X // Semaphore P-operation
X HANDLER_STATUS semaphore_p(const SID sid);
X // Semaphore P-operation
X HANDLER_STATUS semaphore_v(const SID sid);
X
Xpublic:
X CPUManager(CentralProcessingUnit& _CPU,MemoryManager& _mem_manager,
X IOManager& _io_manager);
X ~CPUManager(void) {}
X void commence(); // Load a program from the drum
X // and run it
X void wait_for_halt(void) { Halt--; }
X
X // Post the completion of the I/O
X // request
X void io_request_completed(const PID pid);
X
X // Read/write a word from/to the
X // (virtual) address space of a
X // current process
X // Return FALSE if failed
X int read_word(const Address va, Word& dest);
X int write_word(const Address va, Word src);
X
X // Read/write a word from/to the
X // PHYSICAL address space
X // Error is fatal
X void read_word_phys_memory(const Address ra, Word& dest);
X void write_word_phys_memory(const Address ra, Word src);
X
X // Lock the page of the running process
X // at the specified VA
X int lock_page(Address va);
X // Unlock the page of a given process
X // at the specified VA
X void unlock_page(const PID pid,Address va);
X
X
X // Translate the virtual address to physical
X // one using the translation tables of the
X // running process. The page has to be loaded
X // Returns 0 if fails
X Address translate_va(Address va);
X
X // Reserve the physical page for the system
X // Returns the physical address it starts
X Address reserve_physical_page()
X { return memory_manager.reserve_physical_page(); }
X};
X
X#endif
END_OF_FILE
if test 3955 -ne `wc -c <'cpu_manager.h'`; then
echo shar: \"'cpu_manager.h'\" unpacked with wrong size!
fi
# end of 'cpu_manager.h'
fi
if test -f 'five.a' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'five.a'\"
else
echo shar: Extracting \"'five.a'\" \(3864 characters\)
sed "s/^X//" >'five.a' <<'END_OF_FILE'
X^ register names
X R0 EQU 0
X R1 EQU 1
X R2 EQU 2
X R3 EQU 3
X R4 EQU 4
X R5 EQU 5
X R6 EQU 6
X R7 EQU 7
X R8 EQU 8
X R9 EQU 9
X R10 EQU 10
X R11 EQU 11
X R12 EQU 12
X R13 EQU 13
X R14 EQU 14
X R15 EQU 15
X^ SVC operations
X DMPSYS EQU 1
X FORK EQU 2
X WAIT EQU 3
X GETSEM EQU 4
X P EQU 5
X V EQU 6
X KILL EQU 7
X^
X CARD EQU 1
X PRINT EQU 2
X DISK EQU 3
X^
X^ This program tests the I/O
X^ operations of vm_unt.
X^
X MAPPED
X ENTRY START
X^
X^ First test simple I/O operations.
X^
X START SVC R0,,0,GETSEM
X SVC R1,,SUB1,FORK
X SVC R2,,SUB2,FORK
X SVC ,,,WAIT
X^
X^ Now test the completion codes
X^ returned by I/O opertions.
X^
X SVC R1,,SUB3,FORK
X SVC ,,,WAIT
X^
X^ now test a few packet errors.
X^
X SVC R1,,SUB4,FORK
X SVC ,,,WAIT
X^
X^ Finally, see what happens to
X^ processes which are killed while
X^ waiting for I/O.
X^
X READ ,,PAC8
X LOADI R0,,0
X SVC R1,,0,GETSEM
X SVC R2,,0,GETSEM
X SVC R3,,SUB5,FORK
X SVC R2,,,P
X SVC ,,,DMPSYS
X SVC R3,,,KILL
X HALT
X^
X^ Process SUB1 reads two cards from
X^ the cardreader, modifies the secon
X^ card slightly, and writes the cards
X^ out on the disk. Process SUB2 then
X^ reads the cards from disk, modifies
X^ the second card again, and prints
X^ the cards on the printer. The
X^ cards which are output should be
X^ identical to the two input cards
X^ except that the 'o' on the second
X^ card is changed to a '2'.
X^
X^
X SUB1 READ ,,PAC1
X LOAD R15,,BUF+46b
X LOADI R14,,1
X ADD R15,R14
X STORE R15,,BUF+46b
X WRITE ,,PAC2
X SVC R0,,,V
X HALT
X^
X SUB2 SVC R0,,,P
X READ ,,PAC2
X LOAD R15,,BUF+46b
X LOADI R14,,1
X ADD R15,R14
X STORE R15,,BUF+46b
X WRITE ,,PAC3
X HALT
X^
X^
X^ Process SUB3 tries to read two
X^ cards from the cardreader. The
X^ first read should be successful,
X^ but the second should return an
X^ end-of-file completion code.
X^
X SUB3 READ ,,PAC4
X LOAD R15,,PAC4+1
X BRPOS R15,,ERROR
X BRNEG R15,,ERROR
X READ ,,PAC4
X LOAD R15,,PAC4+1
X LOADI R14,,4
X SUBT R15,R14
X BRPOS R15,,ERROR
X BRNEG R15,,ERROR
X HALT
X ERROR IOPR
X^
X^
X^ Process SUB4 tries three write
X^ operrations with invalid I/O
X^ packets. The first uses a non-
X^ existent device, the second
X^ references an unused page, and
X^ the third tries to write to the
X^ cardreader.
X^
X^
X SUB4 WRITE ,,PAC5
X WRITE ,,PAC6
X WRITE ,,PAC7
X HALT
X^
X^ process SUB5 increments the
X^ count stored in R0 and then
X^ forks itself recursively. It
X^ then adds the count to the
X^ card image stored in BUF and
X^ prints the cards on the printer.
X^ Several copies of SUB5 will
X^ probably be waiting for I/O
X^ when the KILL request from the
X^ main process is executed. The
X^ exact number of card images
X^ printed will depend on your
X^ scheduling policies and is not
X^ important.
X^
X SUB5 LOADI R15,,1
X ADD R0,R15
X SVC R3,,SUB5,FORK
X LOAD R15,,BUF+13
X ADD R15,R0
X STORE R15,,BUF+13
X WRITE ,,PAC9
X SVC R2,,,V
X SVC R1,,,P
X IOPR
X^
X^
X SETPC 1000b
X BUF RES 100b
X^
X PAC1 DATA CARD,0,BUF,2,0
X^
X PAC2 DATA DISK,0,BUF,2,13b
X^
X PAC3 DATA PRINT,0,BUF,2,0
X^
X PAC4 DATA CARD,999,BUF,1,0
X^
X PAC5 DATA CARD+DISK,0,BUF,1,13b
X PAC6 DATA DISK,0,BUF,5,13b
X PAC7 DATA CARD,0,BUF,1,0
X^
X PAC8 DATA DISK,0,BUF,2,0
X PAC9 DATA PRINT,0,BUF,2,0
END_OF_FILE
if test 3864 -ne `wc -c <'five.a'`; then
echo shar: \"'five.a'\" unpacked with wrong size!
fi
# end of 'five.a'
fi
if test -f 'io_manager.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'io_manager.cc'\"
else
echo shar: Extracting \"'io_manager.cc'\" \(9696 characters\)
sed "s/^X//" >'io_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 * Input/Output managers
X *
X * A single I/O channel managers is almost an exact copy of the CPU manager.
X * It picks up the first request from its to_serve request queue, initiates
X * the channel and handles the channel interrupts. When there is nothing
X * to serve the manager waits until some request shows up in the queue.
X * The I/O manager is a separate thread. The fact that the request
X * block looks (and acts) like the Process Control Block for CPU completes
X * the analogy. There is some differences, though. The process running on the
X * CPU can be suspended (because it requested some service from OS or
X * just the CPU managers feels so) and then run again. But the channel program
X * once initiated, cannot be interrupted until it completes (or fails).
X * In either case, when the channel program is over, it is over and cannot
X * be resumed. Therefore, there is no need to save the channel context
X * in the IORequest block.
X *
X ************************************************************************
X */
X
X#pragma implementation "io_manager.h"
X#include "io_manager.h"
X#include "cpu_manager.h"
X#include "myenv.h"
X
X/*
X *------------------------------------------------------------------------
X * Initializing the IO manager
X */
X
XIOManager::IOManager(CPUManager& _cpu_manager)
X : requests(5),
X cpu_manager(_cpu_manager)
X{
X register int i;
X for(i=0; i<max_no_channels; i++)
X channel_managers[i] = 0;
X}
X
Xvoid IOManager::register_channel
X (const int chan_no, IOChannelManager * _channel_manager)
X{
X assert( chan_no > 0 && chan_no <= max_no_channels );
X assert( channel_managers[chan_no-1] == 0 );
X channel_managers[chan_no-1] = _channel_manager;
X message("\nRegistered channel %d",chan_no);
X}
X
X // Tell what's going on with the manager
Xvoid IOManager::dump(void) const
X{
X register int i; // Dump status of all registered
X for(i=0; i<max_no_channels; i++) // channels
X if( channel_managers[i] != 0 )
X channel_managers[i]->dump();
X}
X
X // Reserve the physical page for the system
X // Returns the physical address it starts
XAddress IOManager::reserve_physical_page()
X{
X return cpu_manager.reserve_physical_page();
X}
X
X/*
X *------------------------------------------------------------------------
X * Initiating the I/O
X *
X * The following functions are executed as a part of the CPU manager thread.
X * Note, that during the initiation the requesting process is still current
X *
X */
X
Xint IOManager::submit_request
X (const PID pid,const OpCodes opcode,Address IO_params)
X{
X RID rid = requests.new_request();
X if( rid == NIL_rid )
X {
X console("No free request blocks to serve the process %d"
X "\nThe process has to die",pid);
X return 0;
X }
X
X IORequest& req = requests[rid];
X
X req.pid = pid; // Filling out the request block
X if( opcode == READ )
X req.operation = IORequest::IO_READ;
X else if( opcode == WRITE )
X req.operation = IORequest::IO_WRITE;
X else
X {
X console("Invalid I/O operation");
X return 0;
X }
X
X if( !cpu_manager.read_word(IO_params,req.device_no) ||
X // Write the completion code 0
X // just to test the writability
X !cpu_manager.write_word(req.return_code_vptr=IO_params+1,0) ||
X !cpu_manager.read_word(IO_params+2,req.buffer_ptr) ||
X !cpu_manager.read_word(IO_params+3,req.rec_count) ||
X !cpu_manager.read_word(IO_params+4,req.disk_address) )
X return 0;
X
X message("\nInitiating I/O");
X req.dump();
X
X if( !cpu_manager.lock_page(req.return_code_vptr) )
X return 0;
X if( (req.return_code_pptr = cpu_manager.translate_va(req.return_code_vptr))
X == 0 ) // Try to translate the address
X return 0; // where to write the return code to
X req.return_code = 0;
X
X scrutinize_request(req);
X queue_request(req);
X
X return 1;
X}
X
X // Scrutinize the request and check its
X // validity. Lock all the pages to be taking
X // part into I/O and translate their virtual
X // addresses into the physical one.
X // In case of error, just set the return_code
X // and schedule to queue to
X // any channel handler (for termination)
X // Since the process initiating the I/O is
X // still current, we still can enjoy
X // address translation and page locking
Xint IOManager::scrutinize_request(IORequest& req)
X{
X if( req.rec_count >= req.max_no_recs )
X {
X console("I/O request by pid #%d: too many pages, %d, are involved",
X req.pid,req.rec_count);
X req.return_code = -1;
X return 0;
X }
X
X if( req.buffer_ptr & (Memory::pagesize-1) )
X {
X console("I/O request by pid #%d: buffer address, %o, is misaligned",
X req.pid,req.buffer_ptr);
X req.return_code = -1;
X return 0;
X }
X
X register int i;
X register Address addr = req.buffer_ptr;
X for(i=0; i<req.rec_count; i++,addr += Memory::pagesize)
X if( !cpu_manager.lock_page(addr) ||
X (req.io_pages[i] = cpu_manager.translate_va(addr)) == 0 )
X {
X console("I/O request by pid #%d: failed to lock and translate addr %o",
X req.pid,addr);
X req.return_code = -1;
X return 0;
X }
X
X return 1;
X}
X
X // Queue the request to the appropriate
X // channel. If device_no is invalid,
X // set the return code and queue to the
X // first channel to take care of the error
X // later
Xvoid IOManager::queue_request(IORequest& req)
X{
X if( req.device_no >= max_no_channels || req.device_no == 0 ||
X channel_managers[req.device_no-1] == 0 )
X {
X console("I/O request by pid #%d: device %d is invalid or inoperational",
X req.pid,req.device_no);
X req.return_code = -1;
X req.device_no = 1; // Make the IOChannel manager do all
X } // the clean-up
X channel_managers[req.device_no-1]->submit_request(req);
X}
X
X/*
X *------------------------------------------------------------------------
X * Handle the completion of the request
X *
X * The following function is executed within the I/O Channel manager thread
X */
X
Xvoid IOManager::request_completed(IORequest& req)
X{
X single_message("I/O request of pid %d is completed with code %d",
X req.pid,req.return_code);
X cpu_manager.write_word_phys_memory(req.return_code_pptr,req.return_code);
X cpu_manager.unlock_page(req.pid,req.return_code_vptr);
X
X if( req.io_pages[0] != 0 )
X { // Some pages were locked
X assert(req.rec_count < req.max_no_recs );
X assert( (req.buffer_ptr & (Memory::pagesize-1)) == 0 );
X
X register int i;
X register Address addr = req.buffer_ptr;
X for(i=0; i<req.rec_count && req.io_pages[i] != 0;
X i++,addr += Memory::pagesize)
X cpu_manager.unlock_page(req.pid,addr),
X req.io_pages[i] = 0;
X }
X
X cpu_manager.io_request_completed(req.pid);
X requests.dispose(req.id);
X}
X
X/*
X *------------------------------------------------------------------------
X * A channel manager
X */
X
XIOChannelManager::IOChannelManager(IOChannel& _channel,IOManager& _io_manager)
X : channel(_channel),
X io_manager(_io_manager)
X{
X serviced_request = 0;
X io_manager.register_channel(channel.q_channel_no(),this);
X ccw_area = io_manager.reserve_physical_page();
X
X if( !newproc("Channel managing",1) )
X { // This is a channel manager thread
X for(;;)
X {
X // Wait for the request
X if( initiate_io(to_serviceIORs.get_from_head()->id) )
X {
X channel.wait_for_interrupt(); // Wait for the I/O completion
X serviced_request->return_code = channel.q_status();
X }
X io_manager.request_completed(*serviced_request);
X serviced_request = 0;
X }
X }
X}
X
X // Tell what's going on
Xvoid IOChannelManager::dump(void) const
X{
X message("\nChannel %d: ",channel.q_channel_no());
X
X if( serviced_request == 0 )
X message("Idling\n");
X else
X message("Processing the I/O request for pid #%d\n",serviced_request->pid),
X message("There are %d more requests in the queue\n",
X to_serviceIORs.q_no_elems()),
X channel.dump();
X}
X
X
X // Build the channel program and initiate
X // i/o for the request.
X // Return FALSE if error was found and I/O
X // hasn't been initiated
Xint IOChannelManager::initiate_io(RID rid)
X{
X IORequest& req = io_manager.requests[rid];
X assert( serviced_request == 0 );
X serviced_request = &req;
X
X message("\nChannel %d: selecting the request of pid %d for execution\n",
X channel.q_channel_no(),req.pid);
X
X if( req.return_code != 0 )
X return 0; // Request has been cancelled
X
X // Constructing a channel program
X CCW ccw;
X Address ccw_ptr = ccw_area;
X
X ccw.opcode = SEEKOP;
X ccw.keep_going = 1;
X ccw.page_no = req.disk_address;
X write_word_phys_memory(ccw_ptr++,*(Word*)&ccw);
X
X register int i;
X for(i=0; i<req.rec_count; i++)
X {
X ccw.opcode = (req.operation == IORequest::IO_READ ? READOP : WRITEOP);
X ccw.keep_going = (i+1 == req.rec_count ? 0 : 1);
X ccw.page_no = req.io_pages[i] / Memory::pagesize;
X write_word_phys_memory(ccw_ptr++,*(Word*)&ccw);
X }
X assert(i<Memory::pagesize);
X
X channel.start(ccw_area);
X return 1;
X}
X
X // Read/write a word from/to the
X // PHYSICAL address space
X // Error is fatal
Xvoid IOChannelManager::read_word_phys_memory(const Address ra, Word& dest)
X{
X Memory::MemoryAnswer ans = channel.memory[ra];
X if( ans.out_of_range )
X _error("IOChannel %d reading phys memory failed at %o",
X channel.q_channel_no(),ra);
X dest = ans.contents;
X}
X
Xvoid IOChannelManager::write_word_phys_memory(const Address ra, Word src)
X{
X Memory::MemoryAnswer ans = channel.memory[ra];
X if( ans.out_of_range )
X _error("IOChannel %d reading phys memory failed at %o",
X channel.q_channel_no(),ra);
X ans.contents = src;
X}
END_OF_FILE
if test 9696 -ne `wc -c <'io_manager.cc'`; then
echo shar: \"'io_manager.cc'\" unpacked with wrong size!
fi
# end of 'io_manager.cc'
fi
if test -f 'mem_manager.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'mem_manager.h'\"
else
echo shar: Extracting \"'mem_manager.h'\" \(8748 characters\)
sed "s/^X//" >'mem_manager.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X *
X * Real, Virtual and Swap memory manager
X * Data structures
X *
X * The concept of the working set is now supported. See mem_manager.cc
X * for details.
X *
X ************************************************************************
X */
X
X#ifndef _mem_manager_h
X#define _mem_manager_h 1
X#pragma interface
X
X#include "hardware.h"
X#include "sysqueues.h"
X
X/*
X *------------------------------------------------------------------------
X * Managing pages of physical memory
X */
X
Xtypedef unsigned short PFN; // Page Frame No
Xconst PFN NIL_pfn = (unsigned)(-1);
X
Xclass PageFrameTable;
X
X // Note, QueueLink.id is the page frame no
Xclass PageFrame : public QueueLink
X{
X friend class PageFrameTable;
X
Xpublic:
X PageFrame(void);
X ~PageFrame(void) {}
X};
X
Xclass PageFrameTable
X{
X const int no_page_frames;
X PageFrame * page_frames;
X
X BasicQueue freePFs;
X
Xpublic:
X const int sys_page_frame = 0; // Permanently allocated to OS
X
X PageFrameTable(const int no_phys_pages);
X ~PageFrameTable(void) {}
X
X // Get a Page Frame given its no
X PageFrame& operator [] (const PFN pfn) const;
X PFN allocate(void); // Allocate a new physical page, return NIL
X // if no physical page is available
X void dispose(const PFN pfn); // Dispose of a given page
X void dump_status(void) const; // Print info about physical memory allocation
X};
X
X/*
X *------------------------------------------------------------------------
X * Managing pages of virtual memory
X * Virtual space of the system is essentially the collection of drum sectors
X * (pages). Therefore, virtual page number is exactly the drum sector
X * number. A virtual page may be free or allocated (to one or several
X * processes if it is a code page shared between the processes), may exist
X * only on the drum or loaded to the physical memory into some page frame.
X * If the page is shared between several processes, it might be mapped
X * (actually referenced or accessed) by all or only several of them.
X * Virtual pages of the program images that were inserted on the drum
X * by the linker (task builder) are declared private, in that they are
X * never put into the free list (even if the process that uses them is
X * over), i.e. the contents of the private page is preserved. It implies
X * the same drum file can be used in different runs of VM UNT.
X * The mapped page may be locked, it means the page remains mapped until
X * it is unlocked explicitly; this feature is used primarily to make sure
X * that the pages needed for I/O would would not suddenly get swapped
X * in the middle of I/O. Locking is implemented as increasing the reference
X * counter and setting the 'locked_page' bit. Note that the locked page
X * may be locked again (without any effect, though).
X *
X */
X
Xtypedef unsigned short VPN; // (Virtual) Page No
Xconst VPN NIL_vpn = (unsigned)(-1);
X
Xclass VirtualPageTable;
X
X // Note, QueueLink.id is the VPN
Xclass VirtualPage : public QueueLink
X{
X friend class VirtualPageTable;
X
X short own_count; // How many processes own this page
X short ref_count; // How many processes are actually
X // using, i.e. accessing this page
X unsigned char
X private_page : 1, // TRUE means the page belongs to
X // the exec image and is not to be
X // overwritten or disposed
X data_page : 1, // 1 - data page, 0 - code page
X locked_page : 1;
X
Xpublic:
X PFN page_frame; // Page frame the page is mapped to
X
X VirtualPage(void);
X ~VirtualPage(void) {}
X int q_data_page(void) const { return data_page; }
X void declare_data_page(void) { data_page = 1; }
X int is_shared(void) const { return own_count > 1; }
X int is_shared_mapped(void) const { return ref_count > 1; }
X int is_mapped(void) const { return ref_count > 0; }
X int is_locked(void) const { return locked_page; }
X};
X
Xclass VirtualPageTable
X{
X const int no_pages;
X VirtualPage * pages;
X BasicQueue freeVPs;
X PageFrameTable page_frames;
X Memory& physical_memory;
X int no_locked_pages;
X
Xpublic:
X
X VirtualPageTable(Memory& _physical_memory,
X const int no_phys_pages,const int no_virtual_pages);
X ~VirtualPageTable(void) {}
X
X // Get a Virtual Page given its no
X VirtualPage& operator [] (const VPN vpn) const;
X // Allocate a new virtual page, return NIL
X // if no page is available
X VPN allocate(void);
X VirtualPage& allocate(VPN desired_vpn);
X void declare_page_private(VPN vpn);
X void copy(const VPN to, const VPN from);
X void dispose(const VPN vpn); // Dispose of a given page
X void dump_status(void) const; // Print info about virtual memory allocation
X PFN reference(const VPN vpn); // The page is being demanded, reference it
X // The page is to be swapped out, unreference
X // and swap it out if needed
X void unreference(const VPN vpn,const int to_write);
X void lock(const VPN vpn); // Lock the mapped page
X void unlock(const VPN vpn); // Unlock the mapped page
X
X // Reserve the physical page for the system
X // Returns the physical address it starts
X Address reserve_physical_page();
X};
X
X/*
X *------------------------------------------------------------------------
X * Memory manager itself
X */
X
Xclass MemoryManager;
X
X // OS Memory manangement context of a process
Xclass MMContext : public MMUContext
X{
X friend class MemoryManager;
X const int process_virtual_space = 32; // in pages
X short no_mapped_pages; // Current size of the working set
X const short working_set_quota = 14; // Max no. of mapped pages allowed
X VPN vm_map[process_virtual_space]; // Process virtual space
X PageTableEntry page_table[process_virtual_space];
X short time_since_last_ref[process_virtual_space]; // for each page
X long no_page_faults;
X
X // Given vm_map, map of the process virtual
X // space, construct the page table
X void build_page_table(const VirtualPageTable& virtual_space);
X
Xpublic:
X MMContext(void);
X virtual ~MMContext(void) {}
X
X void load_MMU(MemoryManagementUnit& mmu); // Load and save the hardware
X void save_MMU(const MemoryManagementUnit& mmu);// (MMU) context
X void dump(void) const; // Dump whatever's in the context
X};
X
Xclass MemoryManager : public DiagnosticPanel
X{
X Memory& physical_memory;
X VirtualPageTable virtual_space;
X
X short no_programs; // No of programs on the drum.
X const short max_no_programs = 14;
X struct ProgDescr { Address pc; Word mem_map; }
X prog_descriptors[max_no_programs];
X
X // Simple rule to partition the
X // virtual space of the program
X // into the data and code space
X int is_text_segment(const int page_no) const { return page_no <= 15; }
X
Xpublic:
X MemoryManager(Memory& _physical_memory);
X ~MemoryManager(void) {}
X
X int q_no_programs(void); // Read the drum header and tell the
X // number of programs on the drum
X
X void dump_status(void) const; // Tell what's going on with memory
X
X // Load program and return starting PC
X Address load_program(MMContext& context,const unsigned int prog_no);
X
X // Take care of son's virtual space
X // Return FALSE if some problem
X // occurred
X int fork_son(MMContext& son_context,const MMContext& dad_context);
X
X // Load the virtual page from the
X // drum and establish mapping to
X // a physical page
X enum MMAnswer {Ok, PhysMemoryExhausted, LethalFault };
X MMAnswer load_the_page(MMContext& context,
X MMUContext::VirtualMemoryAddr culprit_VA);
X
X // Release the virtual memory
X // occupied by the process
X void dispose(MMContext& context);
X
X // Swap out a victim - forcibly
X // deprive it of the mapped pages
X // Return 0 if no page frame was
X // released (unsuccessful swapping)
X int swap_out(MMContext& context);
X
X // Run the LRU page replacement
X // strategy to find out the least
X // referenced page and push it out
X void replace_LRU_page(MMContext& context);
X
X // Lock the page that contains the
X // specified virtual address. The page
X // should be already mapped
X // Return FALSE if failed
X int lock_loaded_page(MMContext& context,const Address addr);
X
X // Unlock the page that contains the
X // specified virtual address. The page
X // should be already mapped & locked
X void unlock_page(MMContext& context,const Address addr);
X
X // Translate the virtual address to
X // physical one. The page has to be
X // loaded. Returns 0 if fails
X Address translate_va(MMContext& context,const Address addr);
X
X // Reserve the physical page for the
X // system. Returns the physical
X // address where it starts
X Address reserve_physical_page()
X { return virtual_space.reserve_physical_page(); }
X};
X
X#endif
END_OF_FILE
if test 8748 -ne `wc -c <'mem_manager.h'`; then
echo shar: \"'mem_manager.h'\" unpacked with wrong size!
fi
# end of 'mem_manager.h'
fi
if test -f 'page_manager.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'page_manager.cc'\"
else
echo shar: Extracting \"'page_manager.cc'\" \(9071 characters\)
sed "s/^X//" >'page_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 * Managing pages of real and virtual memory
X *
X ************************************************************************
X */
X
X#include "mem_manager.h"
X#include "myenv.h"
X
X/*
X *========================================================================
X * Managing pages of physical memory
X */
X
XPageFrame::PageFrame(void)
X{
X id = key = 0;
X}
X
X/*
X *------------------------------------------------------------------------
X * Constructing the physical page table
X */
X
XPageFrameTable::PageFrameTable(const int no_phys_pages)
X : no_page_frames(no_phys_pages)
X{
X assure(no_page_frames > 4,"Number of physical pages must be at least 5");
X page_frames = new PageFrame[no_page_frames];
X
X register PFN i;
X for(i=0; i<no_page_frames; i++)
X {
X PageFrame& pf = (*this)[i];
X pf.id = i;
X pf.key = 0;
X if( i > sys_page_frame )
X freePFs.append(pf);
X }
X}
X
X/*
X *------------------------------------------------------------------------
X * Elementary Page Frame operations
X */
X
X // Get a Page Frame given its no
XPageFrame& PageFrameTable::operator [] (const PFN pfn) const
X{
X if( pfn == NIL_pfn )
X _error("FATAL: Requested page frame number is NIL");
X if( pfn >= no_page_frames )
X _error("FATAL: Page Frame Number %d is too big",pfn);
X return page_frames[pfn];
X}
X
X // Print info about physical memory allocation
Xvoid PageFrameTable::dump_status(void) const
X{
X message("\nPhysical memory: %d pages total, %d pages free\n",
X no_page_frames,freePFs.q_no_elems());
X}
X
X // Allocate a new physical page, return NIL
X // if no physical page is available
XPFN PageFrameTable::allocate(void)
X{
X if( freePFs.is_empty() )
X return NIL_pfn;
X return freePFs.get_from_head()->id;
X}
X
X
X // Dispose of the given page
Xvoid PageFrameTable::dispose(const PFN pfn)
X{
X assure( pfn > sys_page_frame, "May not dispose of a system page frame" );
X PageFrame& pf = (*this)[pfn];
X assert( pfn == pf.id );
X freePFs.append(pf);
X}
X
X/*
X *========================================================================
X * Managing pages of virtual memory
X */
X
X
XVirtualPage::VirtualPage(void)
X{
X own_count = 0;
X ref_count = 0;
X page_frame = NIL_pfn;
X private_page = data_page = locked_page = 0;
X}
X
X/*
X *------------------------------------------------------------------------
X * Constructing the virtual page table
X */
X
XVirtualPageTable::VirtualPageTable
X (Memory& _physical_memory,const int no_phys_pages, const int no_virtual_pages)
X : no_pages(no_virtual_pages),
X page_frames(no_phys_pages),
X physical_memory(_physical_memory)
X{
X assure(no_pages > 4,"Number of virtual pages must be at least 5");
X pages = new VirtualPage[no_pages];
X
X register VPN i;
X for(i=0; i<no_pages; i++)
X {
X VirtualPage& vp = (*this)[i];
X vp.id = i;
X vp.key = 0;
X freeVPs.append(vp);
X }
X no_locked_pages = 0;
X}
X
X/*
X *------------------------------------------------------------------------
X * Elementary Virtual Page operations
X */
X
X // Get a Virtual Page given its no
XVirtualPage& VirtualPageTable::operator [] (const VPN vpn) const
X{
X if( vpn == NIL_vpn )
X _error("FATAL: Requested virtual page number is NIL");
X if( vpn >= no_pages )
X _error("FATAL: Virtual Page Number %d is too big",vpn);
X return pages[vpn];
X}
X
X // Print info about physical memory allocation
Xvoid VirtualPageTable::dump_status(void) const
X{
X message("\nVirtual memory: %d pages total, %d pages free, %d pages locked\n",
X no_pages,freeVPs.q_no_elems(),no_locked_pages);
X page_frames.dump_status();
X}
X
X // Allocate a new virtual page, return NIL
X // if no page is available
XVPN VirtualPageTable::allocate(void)
X{
X if( freeVPs.is_empty() )
X return NIL_vpn;
X VirtualPage& vp =(*this)[freeVPs.get_from_head()->id];
X assert( vp.own_count == 0 && vp.ref_count == 0 );
X vp.own_count++;
X vp.page_frame = NIL_pfn;
X return vp.id;
X}
X
X // Allocate a specified virtual page.
X // If it's already allocated, increment
X // the ownership count
XVirtualPage& VirtualPageTable::allocate(VPN desired_vpn)
X{
X VirtualPage& vp = (*this)[desired_vpn];
X if( vp.own_count++ == 0 ) // If the page has been free,
X freeVPs.dequeue(vp); // dequeue it from the free list
X return vp;
X}
X
X // Declare a page being private
X // Note, a page which is already private
X // or shared may not be declared private
Xvoid VirtualPageTable::declare_page_private(VPN vpn)
X{
X VirtualPage& vp = allocate(vpn);
X assure( vp.own_count == 1 && vp.private_page == 0,
X "Illegal attempt to declare a page private" );
X vp.private_page = 1;
X}
X
X // Copy virtual pages. system page frame is
X // used as a copy buffer
Xvoid VirtualPageTable::copy(const VPN to, const VPN from)
X{
X const VirtualPage& from_vp = (*this)[from];
X
X if( from_vp.page_frame != NIL_pfn ) // 'From' page is already in the memory
X physical_memory.drum_write(from_vp.page_frame,to);
X else
X { // Else read it from the drum
X physical_memory.drum_read(from,PageFrameTable::sys_page_frame);
X physical_memory.drum_write(PageFrameTable::sys_page_frame,to);
X }
X}
X
X // Dispose of the given page
Xvoid VirtualPageTable::dispose(const VPN vpn)
X{
X VirtualPage& vp = (*this)[vpn];
X assert( vpn == vp.id && vp.own_count > 0 ); // Consistency check
X
X if( vp.is_locked() )
X unlock(vpn);
X
X if( --vp.own_count > 0 )
X return; // The page is still in use
X assert( vp.ref_count == 0 ); // The page should be unreferenced
X assert( vp.locked_page == 0 ); // The page should be unlocked
X if( vp.page_frame != NIL_pfn )
X page_frames.dispose(vp.page_frame),
X vp.page_frame = NIL_pfn,
X vp.ref_count = 0;
X
X if( vp.private_page ) // Page of exec image, should not
X return; // be spoiled or disposed
X vp.data_page = 0;
X freeVPs.append(vp);
X}
X
X // The page is being demanded, reference it
X // If necessary, the physical page frame is
X // allocated and the page is loaded.
X // NIL_pfn means the physical memory is
X // exhausted
XPFN VirtualPageTable::reference(const VPN vpn)
X{
X VirtualPage& vp = (*this)[vpn];
X assert( vpn == vp.id && vp.own_count > 0 ); // Consistency check
X message("\nMap: page %d, own count %d, prev. ref count %d",
X vpn,vp.own_count,vp.ref_count);
X assert( vp.ref_count < vp.own_count );
X if( vp.ref_count > 0 ) // The page has already been referenced
X {
X assert( vp.page_frame != NIL_pfn );
X vp.ref_count++;
X message(": already mapped to page frame %d",vp.page_frame);
X return vp.page_frame;
X }
X if( (vp.page_frame = page_frames.allocate()) == NIL_pfn )
X return NIL_pfn; // Physical space is exhausted
X
X message(": to be read into page frame %d",vp.page_frame);
X physical_memory.drum_read(vp.id,vp.page_frame); // Load the page
X vp.ref_count++;
X return vp.page_frame;
X}
X
X // The page is to be swapped out, unreference
Xvoid VirtualPageTable::unreference(const VPN vpn,const int to_write)
X{
X VirtualPage& vp = (*this)[vpn];
X assert( vpn == vp.id && vp.own_count > 0 ); // Consistency check
X message("\nUnmap: virtual page %d, own count %d, ref count %d, "
X "from page frame %d",
X vpn,vp.own_count,vp.ref_count,vp.page_frame);
X assert( vp.ref_count > 0 && vp.page_frame != NIL_pfn );
X if( --vp.ref_count > 0 )
X return; // The page is still referenced
X if( to_write )
X physical_memory.drum_write(vp.page_frame,vp.id);
X page_frames.dispose(vp.page_frame);
X vp.page_frame = NIL_pfn;
X}
X
X // Lock the mapped page
X // Note, the page may not be shared
X // If the page is already locked,
X // locking it again has no effect
Xvoid VirtualPageTable::lock(const VPN vpn)
X{
X VirtualPage& vp = (*this)[vpn];
X assert( vpn == vp.id && vp.own_count > 0 ); // Consistency check
X message("\nLock: virtual page %d, own count %d, ref count %d, "
X "on page frame %d",
X vpn,vp.own_count,vp.ref_count,vp.page_frame);
X assert( vp.ref_count > 0 && vp.page_frame != NIL_pfn );
X if( vp.is_locked() )
X return;
X assert( vp.ref_count == 1 );
X vp.locked_page = 1;
X vp.ref_count++;
X no_locked_pages++;
X}
X
X // Unlock the mapped page
X // Unlocking the no page that hasn't been
X // locked has no effect
Xvoid VirtualPageTable::unlock(const VPN vpn)
X{
X VirtualPage& vp = (*this)[vpn];
X assert( vpn == vp.id && vp.own_count > 0 ); // Consistency check
X message("\nUnlock: virtual page %d, own count %d, ref count %d, "
X "on page frame %d",
X vpn,vp.own_count,vp.ref_count,vp.page_frame);
X if( !vp.is_locked() )
X return;
X assert( --no_locked_pages >= 0 );
X assert( vp.ref_count > 0 && vp.page_frame != NIL_pfn );
X assert( vp.locked_page == 1 );
X vp.locked_page = 0;
X unreference(vpn,1);
X}
X
X // Reserve the physical page for the system
X // Returns the physical address it starts
XAddress VirtualPageTable::reserve_physical_page()
X{
X PFN pfn = page_frames.allocate();
X assure( pfn != NIL_pfn, "Failed to reserve a physical page for the system" );
X return pfn * Memory::pagesize;
X}
X
END_OF_FILE
if test 9071 -ne `wc -c <'page_manager.cc'`; then
echo shar: \"'page_manager.cc'\" unpacked with wrong size!
fi
# end of 'page_manager.cc'
fi
if test -f 'processes.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'processes.cc'\"
else
echo shar: Extracting \"'processes.cc'\" \(4313 characters\)
sed "s/^X//" >'processes.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 * Process handling and scheduling
X *
X * The present file implements primitive operations on separate PCBs
X * as well on their collection, PCB table. Advanced process scheduling,
X * etc. is the concern of the CPUManager.
X *
X ************************************************************************
X */
X
X#include "processes.h"
X#pragma implementation
X
X#include "myenv.h"
X
X/*
X *------------------------------------------------------------------------
X * Constructing the PCB
X */
X
XPCB::PCB(void)
X{
X parent = lchild = rchild = NIL_pid;
X status = Dead;
X}
X
X/*
X *------------------------------------------------------------------------
X * Elementary PCB operations
X */
X
Xvoid PCB::dump(void)
X{
X message("\n---> Process %d", id);
X message(", Status %s",
X status == Wait_for_kids ? "Waiting for kids to terminate" :
X status == Wait_on_sema ? "Waiting on semaphore" :
X status == Dead ? "Dead" :
X status == Doing_io ? "Doing I/O" :
X status == Shall_die ? "Shall die" :
X "OK");
X message(", \t PC = %06o",pc);
X message("\n\t\tParent: ");
X parent == NIL_pid ? message("None") : message("%d",parent);
X message(", Children: ");
X if( lchild == NIL_pid && rchild == NIL_pid )
X message("None");
X else
X {
X if( lchild != NIL_pid )
X message("%d ",lchild);
X if( rchild != NIL_pid )
X message("%d ",rchild);
X }
X message("\n");
X MMContext::dump();
X}
X
X // Fork this PCB from dad's
Xvoid PCB::fork_from_dad(PCB& dad_pcb)
X{
X status = Ok;
X parent = dad_pcb.id;
X lchild = rchild = NIL_pid;
X copy_context(dad_pcb);
X if( dad_pcb.lchild == NIL_pid )
X dad_pcb.lchild = (*this).id;
X else
X dad_pcb.rchild = (*this).id;
X}
X
X // PCB for a brand-new process
Xvoid PCB::brand_new(void)
X{
X status = Ok;
X}
X
X // Save the full hardware context
Xvoid PCB::save_context(const CentralProcessingUnit& cpu_hardware)
X{
X copy_context((const Context&)cpu_hardware);
X MMContext::save_MMU((const MemoryManagementUnit&)cpu_hardware);
X}
X
X // Load the context into the hardware
Xvoid PCB::load_context(CentralProcessingUnit& cpu_hardware)
X{
X cpu_hardware.copy_context((Context&)*this);
X MMContext::load_MMU((MemoryManagementUnit&)cpu_hardware);
X}
X
X/*
X *------------------------------------------------------------------------
X * Constructing the process table
X */
X
XProcessTable::ProcessTable(const int _nslots)
X : nslots(_nslots)
X{
X assure(nslots > 4,"No of slots in a process table must be at least 5");
X pcbs = new PCB[nslots];
X resume_scan_pid = NIL_pid;
X
X register PID i;
X for(i=1; i<=nslots; i++)
X {
X PCB& pcb = (*this)[i];
X pcb.id = i;
X pcb.key = 0;
X freePCBs.append(pcb);
X }
X}
X
X/*
X *------------------------------------------------------------------------
X * Elementary ProcessTable operations
X */
X
X // Get a PCB given its index
XPCB& ProcessTable::operator [] (const PID id)
X{
X assure(id != NIL_pid,"NIL index");
X if( id > nslots )
X _error("FATAL: PCB index %d is too big",id);
X return pcbs[id-1];
X}
X
X // Dump info about all processes in the system
Xvoid ProcessTable::dump(void)
X{
X message("\n\t\t=============== System Processes ================\n");
X register PID i;
X for(i=1; i<=nslots; i++)
X {
X PCB& pcb = (*this)[i];
X if( pcb.status != PCB::Dead )
X pcb.dump();
X }
X}
X
X // Get PID of a new process to create
X // Return NIL_pid if no free PCB is available
XPID ProcessTable::new_pid(void)
X{
X if( freePCBs.is_empty() )
X return NIL_pid;
X return freePCBs.get_from_head()->id;
X}
X
X
X // Dispose of the PCB
Xvoid ProcessTable::dispose(const PID pid)
X{
X PCB& pcb = (*this)[pid];
X assert( pid == pcb.id );
X pcb.status = PCB::Dead;
X freePCBs.append(pcb);
X}
X
X // Find nex pcb according to the criterion
XPID ProcessTable::next_pcb(const SEARCH_CRIT crit)
X{
X if( resume_scan_pid == NIL_pid || resume_scan_pid > nslots )
X return NIL_pid; // Scan is over or wasn't started
X for(;resume_scan_pid <= nslots; resume_scan_pid++)
X {
X const PCB& pcb = (*this)[resume_scan_pid];
X if( pcb.status == PCB::Dead )
X continue;
X if( (pcb.status == PCB::Ok) == (crit == Ready) )
X return resume_scan_pid++;
X }
X return NIL_pid;
X}
END_OF_FILE
if test 4313 -ne `wc -c <'processes.cc'`; then
echo shar: \"'processes.cc'\" unpacked with wrong size!
fi
# end of 'processes.cc'
fi
if test -f 'semaphores.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'semaphores.cc'\"
else
echo shar: Extracting \"'semaphores.cc'\" \(4442 characters\)
sed "s/^X//" >'semaphores.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 * Operations on semaphores
X *
X ************************************************************************
X */
X
X#include "semaphores.h"
X#pragma implementation
X
X#include "myenv.h"
X#include <std.h>
X
X/*
X *------------------------------------------------------------------------
X * Constructing the Semaphore
X */
X
XSema::Sema(void) : lock("Sema lock",1)
X{
X owner = NIL_pid;
X value = 0;
X}
X
X/*
X *------------------------------------------------------------------------
X * Elementary Semaphore operations
X */
X // Perform P-operation. If value goes
X // negative, return FALSE and queue the
X // pcb into the internal queue
Xint Sema::p(PCB& pcb)
X{
X lock--; // Start a critical section
X if( --value < 0 )
X waiting_list.append(pcb);
X register int result = (value >= 0);
X lock++; // End the critical section
X return result;
X}
X
X // Perform V-operation. If value was negative
X // get a process from waiting list and
X // return its PID. Otherwise return NIL_pid
XPID Sema::v(void)
X{
X PID pid_to_awake = NIL_pid;
X lock--; // Start a critical section
X if( value++ < 0 )
X pid_to_awake = (waiting_list.get_from_head())->id;
X lock++; // End the critical section
X return pid_to_awake;
X}
X
X // Dispose of an active semaphore
Xvoid Sema::dispose(void)
X{
X lock--; // Start a critical section
X owner = NIL_pid;
X for(; value < 0; value++)
X (void)waiting_list.get_from_head();
X value = 0;
X lock++; // End the critical section
X}
X
X // Purge a process pid from a waiting queue,
X // (if any)
Xvoid Sema::purge(const PID pid)
X{
X if( value >= 0 )
X return; // No waiting queue for this semaphore
X
X lock--; // Start a critical section
X if( waiting_list.purge_id(pid) )
X ++value; // Increment the counter, if purged
X lock++; // End the critical section
X}
X
X/*
X *------------------------------------------------------------------------
X * Constructing the semaphore table
X */
X
XSemaphoreTable::SemaphoreTable(const int _nslots)
X : nslots(_nslots)
X{
X assure(nslots > 4,"No of slots in a process table must be at least 5");
X slots = new Sema[nslots];
X
X register SID i;
X for(i=1; i<=nslots; i++)
X {
X Sema& sem = (*this)[i];
X sem.id = i;
X sem.key = 0;
X freeSEMs.append(sem);
X }
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Elementary SemaphoreTable operations
X */
X
X // Get a Semaphore given its index
XSema& SemaphoreTable::operator [] (const SID id)
X{
X assure(id != NIL_sid,"NIL index");
X if( id > nslots )
X _error("FATAL: Semaphore id %d is too big",id);
X return slots[id-1];
X}
X
X // Check to see if SID is active
Xint SemaphoreTable::is_active(const SID id)
X{
X if( id == NIL_sid || id > nslots || (*this)[id].owner == NIL_pid )
X return 0;
X return 1;
X}
X
X // Get a new SID or NIL if it is not
X // possible
XSID SemaphoreTable::new_semaphore(const int in_value, const PID owner)
X{
X if( freeSEMs.is_empty() )
X return NIL_sid;
X Sema& sem = (*this)[freeSEMs.get_from_head()->id];
X sem.owner = owner;
X sem.value = in_value;
X return sem.id;
X}
X
X // Print info about all active semaphores
Xvoid SemaphoreTable::dump(void)
X{
X if( freeSEMs.q_no_elems() == nslots )
X {
X message("\nNo active semaphores\n");
X return;
X }
X
X message("\nActive semaphores:\n");
X register SID i;
X for(i=1; i<=nslots; i++)
X {
X Sema& sem = (*this)[i];
X if( sem.owner != NIL_pid )
X message("\tID = %d, process-owner = %d, value = %d\n",
X i,sem.owner,sem.value);
X }
X}
X
X // Get SID of a semaphore owned by a
X // given owner
XSID SemaphoreTable::owned_by(const PID owner)
X{
X register SID i;
X for(i=1; i<=nslots; i++)
X {
X Sema& sem = (*this)[i];
X if( sem.owner == owner )
X return sem.id;
X }
X return NIL_sid;
X}
X
X // Dispose of a given semaphore
Xvoid SemaphoreTable::dispose(const SID sid)
X{
X Sema& sem = (*this)[sid];
X assert( sem.owner != NIL_pid && sem.id == sid );
X sem.dispose();
X freeSEMs.append(sem);
X}
X
X // Purge the process PID from the semaphore
X // queue
Xvoid SemaphoreTable::purge(const PID pid)
X{
X register SID i; // Purge from any active
X for(i=1; i<=nslots; i++) // semaphore queue
X {
X Sema& sem = (*this)[i];
X if( sem.owner != NIL_pid )
X sem.purge(pid);
X }
X}
END_OF_FILE
if test 4442 -ne `wc -c <'semaphores.cc'`; then
echo shar: \"'semaphores.cc'\" unpacked with wrong size!
fi
# end of 'semaphores.cc'
fi
echo shar: End of archive 3 \(of 4\).
cp /dev/null ark3isdone
Kiselyov Oleg
Posting-number: Volume 44, Issue 56
Archive-name: toy_os/part04
Environment: GNU C++ 2.2
#! /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: Makefile OS.dr c++ card_file four.1.a four.2.a four.3.a
# instruction_set.h io_requests.cc mult_proc.cc mult_proc.h myenv.cc
# oper_system.h print_file processes.h semaphores.h sysqueues.cc
# sysqueues.h virt_mem_comp.txt
# Wrapped by kent@sparky on Mon Sep 5 13:12:57 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 4 (of 4)."'
if test -f 'Makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Makefile'\"
else
echo shar: Extracting \"'Makefile'\" \(1137 characters\)
sed "s/^X//" >'Makefile' <<'END_OF_FILE'
XCC=./c++
XCCL=./c++l
X.SUFFIXES: .cc
XLIBMOD=mult_proc.cc cpu.cc memory.cc cpu_manager.cc processes.cc \
X sysqueues.cc semaphores.cc page_manager.cc mem_manager.cc \
X channel.cc io_requests.cc io_manager.cc
X
X
X# Rules
X.cc.o:
X $(CC) -O0 -fcaller-saves -fvolatile $*.cc
X
X.o: $*.o
X $(CCL) $*.o -o $*
X ./$*
X
X.cc: $*.cc
X $(CC) $*.cc
X $(CCL) $*.o -o $*
X ./$*
X
X# Primary goal
X
Xbootstrap: bootstrap.o
X $(CCL) bootstrap.o kernel.a oslib -o vm_unt
X# vm_unt three.1.dat
X# vm_unt three.2.dat
X# vm_unt three.3.dat
X# vm_unt three.4.dat
X# vm_unt four.1.dat
X# vm_unt four.2.dat
X# vm_unt four.3.dat
X# vm_unt four.123.dat
X vm_unt -card=card_file -lp=print_file -harddisk=hdisk five.ld
X
X# Library
X
Xlib: kernel.a
X
Xkernel.a: $(LIBMOD)
X# Compile the source files that have been changed
X $(CC) -O0 $?
X listobj=`echo $? | sed s/.cc/.o/g` ; \
X ar rv kernel.a $$listobj && \
X rm $$listobj
X (ar d kernel.a __.SYMDEF && ranlib kernel.a)
X
X# Specific dependent goals
X
Xmult_proc.o: mult_proc.cc mult_proc.h
X $(CC) -O0 -fcaller-saves -fvolatile -DDEBUG $*.cc
X
Xbootstrap.o: bootstrap.cc hardware.h oper_system.h
X $(CC) -O0 -fcaller-saves -fvolatile $*.cc
END_OF_FILE
if test 1137 -ne `wc -c <'Makefile'`; then
echo shar: \"'Makefile'\" unpacked with wrong size!
fi
# end of 'Makefile'
fi
if test -f 'OS.dr' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'OS.dr'\"
else
echo shar: Extracting \"'OS.dr'\" \(2176 characters\)
sed "s/^X//" >'OS.dr' <<'END_OF_FILE'
X CSCI 5540 - Operating System Design
X
XMakefile How to build it all
X
Xmult_proc.h Multiprocessing stuff - semaphores, etc.
Xmult_proc.cc Interface with the thread library
X
X Emulation of the VM_UNT hardware
Xhardware.h Describes the pieces of hardware
Xinstruction_set.h Instruction set that CPU and channel execute
Xcpu.cc Emulate CPU operations
Xmemory.cc Handle real & virtual memory requests and drum
Xchannel.cc I/O Channel hardware
Xcomputer.h Describes the computer as a whole
X
X VM_UNT Operating system
Xsysqueues.h System queues
Xsysqueues.cc Basic queue operations
X
Xmem_manager.h Memory manager data structures
Xpage_manager.cc Managing pages of physical and virtual memory
Xmem_manager.cc Memory manager itself
X
Xprocesses.h Defines the PCB and a process table
Xprocesses.cc Basic operations servicing PCB and the PCB table
Xsemaphores.h Definition of Sema (VM_UNT semaphore) & a Sema table
Xsemaphores.cc Implementation of the semaphore operations
X
Xcpu_manager.h Trap handler and top level process manager data struct
Xcpu_manager.cc Trap handler and high-level process manager
X
Xio_manager.h I/O manager data structures
Xio_requests.cc I/O requests manager
Xio_manager.cc I/O managers
X
Xoper_system.h Puts together all the pieces of OS
Xbootstrap.cc Booting the VM
X
X
Xvirt_mem_comp.txt Comparison of swap out / local LRU page replacement
X strategies
X
X Examples of test jobs in VM UNT assembler. These
X files are written by Prof. Cui-Qing Yang (cqy...@cs.unt.edu)
X and included here as an example. Please contact him
X for more info if you're interested
X
Xfour.1.a Test simple forks and sharing code/data spaces
Xfour.2.a Test sharing of code pages among siblings
Xfour.3.a Test of two memory-greedy processes
Xfive.a Test of asynchronous i/o
Xcard_file Input of the card reader (for the test five.a)
X
X Full traces of system runs - the following files are
X too big (and too monotonous) to include into submission.
X Mail me if you need them.
Xprocess_sched.lst Process scheduling
Xvirt_mem_swap.lst Virtual memory with swapping
Xvirt_mem_lru.lst VM with local LRU page replacement strategy
X
Xio_management.lst Doing asynchronous i/o (see five.a job suite)
END_OF_FILE
if test 2176 -ne `wc -c <'OS.dr'`; then
echo shar: \"'OS.dr'\" unpacked with wrong size!
fi
# end of 'OS.dr'
fi
if test -f 'c++' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'c++'\"
else
echo shar: Extracting \"'c++'\" \(404 characters\)
sed "s/^X//" >'c++' <<'END_OF_FILE'
X#!/bin/csh
X# GNU C++ compilation
X/usr/local/bin/gcc -c -O -pipe -W -Wall -Wpointer-arith -Wenum-clash -Woverloaded-virtual \
X-Wstrict-prototypes -Wmissing-prototypes # -Wredundant-decls \
X-finline-functions -fforce-mem # -funsigned-char # -fshort-enums \
X-fforce-addr -fstrict-prototype -felide-constructors # -fexternal-templates \
X-fsave-memoized -fomit-frame-pointer -freg-struct-return \
X-I. -I- $*
END_OF_FILE
if test 404 -ne `wc -c <'c++'`; then
echo shar: \"'c++'\" unpacked with wrong size!
fi
# end of 'c++'
fi
if test -f 'card_file' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'card_file'\"
else
echo shar: Extracting \"'card_file'\" \(193 characters\)
sed "s/^X//" >'card_file' <<'END_OF_FILE'
X000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
END_OF_FILE
if test 193 -ne `wc -c <'card_file'`; then
echo shar: \"'card_file'\" unpacked with wrong size!
fi
# end of 'card_file'
fi
if test -f 'four.1.a' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'four.1.a'\"
else
echo shar: Extracting \"'four.1.a'\" \(2296 characters\)
sed "s/^X//" >'four.1.a' <<'END_OF_FILE'
X^ This program tests simple
X^ forks and waits to make sure
X^ code is shared and data is not.
X^
X MAPPED
X ENTRY START
X^
X^ First, try a simple fork and
X^ examing the process memory maps.
X^
X START LOAD R15,,DATA1
X SVC R1,,SUB1,FORK
X SVC ,,,WAIT
X^
X^ Now make sure that data is not
X^ shared after a fork.
X^
X SVC R0,,0,GETSEM
X LOADI R15,,111b
X STORE R15,,DATA2
X SVC R1,,SUB2,FORK
X LOADI R15,,777b
X STORE R15,,DATA3
X SVC R0,,,V
X SVC ,,,WAIT
X^
X^ Finally, make sure that code pages
X^ are made execute only.
X^
X SVC R1,,SUB3,FORK
X SVC ,,,WAIT
X^
X^ Program should now terminate
X^ with a HALT at octal location 32.
X^
X HALT
X^
X^ Process SUB1 merely dumps the
X^ system status after being forked.
X^
X^
X SUB1 SVC ,,,DMPSYS
X HALT
X^
X^
X^ Subprogram SUB2 compares the values
X^ which it finds in locations DATA2
X^ and DATA3. DATA2 is initialized to
X^ 777b, but is changed to 111b by the
X^ main process before SUB2 is forked.
X^ DATA3 is initialized to 111b and is
X^ not changed by the main process
X^ until after SUB2 is forked. There-
X^ fore SUB2 should find DATA2 and
X^ DATA3 to be equal, and should
X^ terminate with a HALT.
X^
X SUB2 SVC R0,,,P
X LOAD R14,,DATA2
X LOAD R15,,DATA3
X SUBT R14,R15
X BRZERO R14,,SKIP
X IOPR
X SKIP HALT
X^
X^
X^ Process SUB3 merely tries to
X^ load part of its own code into
X^ a register. This should be a fatal
X^ error.
X^
X^
X SUB3 LOAD R15,,SUB3
X IOPR
X^
X^
X^ DATA1 is in the first data page
X^ of this program. DATA2 AND DATA3
X^ are in the second data page.
X^
X^
X SETPC 1000b
X DATA1 DATA 0b
X^
X SETPC 1040b
X DATA2 DATA 777b
X DATA3 DATA 111b
END_OF_FILE
if test 2296 -ne `wc -c <'four.1.a'`; then
echo shar: \"'four.1.a'\" unpacked with wrong size!
fi
# end of 'four.1.a'
fi
if test -f 'four.2.a' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'four.2.a'\"
else
echo shar: Extracting \"'four.2.a'\" \(1947 characters\)
sed "s/^X//" >'four.2.a' <<'END_OF_FILE'
X^ This program checks to see that
X^ code is shared properly.
X^
X MAPPED
X ENTRY START
X START SVC R0,,0,GETSEM
X SVC R1,,0,GETSEM
X SVC R2,,0,GETSEM
X SVC R3,,0,GETSEM
X^
X^ First check to see that code
X^ pages are shared among siblings.
X^
X SVC R4,,SUB1,FORK
X SVC R5,,SUB2,FORK
X SVC R0,,,V
X SVC R2,,,P
X SVC ,,,DMPSYS
X SVC R3,,,V
X SVC R3,,,V
X SVC ,,,WAIT
X^
X^ Now check to see that code pages
X^ are shared properly between parents
X^ and offspring.
X^
X SVC R4,,SUB3,FORK
X SVC R0,,,P
X BRSUBR R15,,PAGE7
X SVC ,,,DMPSYS
X SVC R3,,,V
X SVC ,,,WAIT
X^
X^ Program should now terminate
X^ with a HALT at octal location 44.
X^
X HALT
X^
X^ Process SUB1 and SUB2 both
X^ access virtual page 5. Semaphores
X^ are used to see that the accesses
X^ occur in a particular order.
X^
X^
X SUB1 SVC R0,,,P
X BRSUBR R15,,PAGE5
X SVC R1,,,V
X SVC R3,,,P
X HALT
X^
X SUB2 SVC R1,,,P
X BRSUBR R15,,PAGE5
X SVC R2,,,V
X SVC R3,,,P
X HALT
X^
X^
X^ The main process and subprocess
X^ SUB4 both access virtuyal page 7.
X^
X^
X SUB3 SVC R4,,SUB4,FORK
X SVC ,,,WAIT
X HALT
X^
X SUB4 BRSUBR R15,,PAGE7
X SVC R0,,,V
X SVC R3,,,P
X HALT
X^
X^
X SETPC 240b
X PAGE5 BR ,R15
X^
X SETPC 340b
X PAGE7 BR ,R15
END_OF_FILE
if test 1947 -ne `wc -c <'four.2.a'`; then
echo shar: \"'four.2.a'\" unpacked with wrong size!
fi
# end of 'four.2.a'
fi
if test -f 'four.3.a' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'four.3.a'\"
else
echo shar: Extracting \"'four.3.a'\" \(2597 characters\)
sed "s/^X//" >'four.3.a' <<'END_OF_FILE'
X^ This program checks to see that
X^ user processes are swapped out
X^ when physical memory is exhausted.
X^ The main process forks two child
X^ processes each of which accesses
X^ every page in its virtual address
X^ space. Therefore, at least one of
X^ the child processes will have to
X^ be swapped out if the program is
X^ to run to completion.
X^
X MAPPED
X ENTRY START
X START SVC R0,,SUB,FORK
X SVC R1,,SUB,FORK
X SVC ,,,WAIT
X HALT
X^
X^
X SUB LOADI R0,,40b
X^
X LOADI R1,,700b
X LOOP1 BRSUBR R15,R1,40b
X SUBT R1,R0
X BRPOS R1,,LOOP1
X^
X LOADI R1,,1000b
X LOOP2 SUBT R1,R0
X STORE R1,R1,1000b
X BRPOS R1,,LOOP2
X^
X LOADI R1,,1000b
X LOOP3 SUBT R1,R0
X LOAD R2,R1,1000b
X SUBT R2,R1
X BRPOS R2,,ERROR
X BRNEG R2,,ERROR
X BRPOS R1,,LOOP3
X^
X HALT
X^
X ERROR IOPR
X^
X^
X SETPC 100b
X BR ,R15,0b
X SETPC 140b
X BR ,R15,0b
X SETPC 200b
X BR ,R15,0b
X SETPC 240b
X BR ,R15,0b
X SETPC 300b
X BR ,R15,0b
X SETPC 340b
X BR ,R15,0b
X SETPC 400b
X BR ,R15,0b
X SETPC 440b
X BR ,R15,0b
X SETPC 500b
X BR ,R15,0b
X SETPC 540b
X BR ,R15,0b
X SETPC 600b
X BR ,R15,0b
X SETPC 640b
X BR ,R15,0b
X SETPC 700b
X BR ,R15,0b
X SETPC 740b
X BR ,R15,0b
X^
X SETPC 1000b
X DATA 0b
X SETPC 1040b
X DATA 0b
X SETPC 1100b
X DATA 0b
X SETPC 1140b
X DATA 0b
X SETPC 1200b
X DATA 0b
X SETPC 1240b
X DATA 0b
X SETPC 1300b
X DATA 0b
X SETPC 1340b
X DATA 0b
X SETPC 1400b
X DATA 0b
X SETPC 1440b
X DATA 0b
X SETPC 1500b
X DATA 0b
X SETPC 1540b
X DATA 0b
X SETPC 1600b
X DATA 0b
X SETPC 1640b
X DATA 0b
X SETPC 1700b
X DATA 0b
X SETPC 1740b
X DATA 0b
END_OF_FILE
if test 2597 -ne `wc -c <'four.3.a'`; then
echo shar: \"'four.3.a'\" unpacked with wrong size!
fi
# end of 'four.3.a'
fi
if test -f 'instruction_set.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'instruction_set.h'\"
else
echo shar: Extracting \"'instruction_set.h'\" \(2734 characters\)
sed "s/^X//" >'instruction_set.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X * A set of instructions that CPU and channel execute
X *
X ************************************************************************
X */
X
X#ifndef _instruction_set_h
X#define _instruction_set_h 1
X#pragma interface
X
X // Word 1 of the CPU instruction
Xstruct InstructionWord1
X{
X unsigned short
X breg : 4, // 2nd register (source or index)
X areg : 4, // 1st register (respondent)
X opcode : 7, // Operation code
X reserved : 1; // always zero
X};
X
X // Word 2 of the CPU instruction
X // (if present)
Xstruct InstructionWord2
X{
X unsigned short
X ea : 10, // Effective Address
X indirect : 1, // Flag of indirect addressing
X svcop : 5; // Code for the SVC operation
X};
X
Xenum OpCodes
X{
X // One word instructions
X HALT, // Halt the CPU
X DUMP, // Dump regs and memory R(a) to R(b)
X LOADR, // R(a) := R(b)
X ADD, // R(a) +:= R(b)
X SUBT, // R(a) -:= R(b)
X MULT, // R(a) *:= R(b) (single word product)
X DIV, // R(a) /:= R(b) (no trap on 0 divide)
X AND, // R(a) &:= R(b)
X OR, // R(a) |:= R(b)
X XOR, // R(a) ^:= R(b)
X SHIFTL, // R(a) <<:= R(b)
X SHIFTR, // R(a) >>:= R(b)
X NOP, // Naught
X IOPR, // Illegal operation
X // Two word instructions
X TWO_WORD, // 1st two-word code
X LOAD = TWO_WORD, // R(a) := C(ea)
X LOADI, // R(a) := ea
X STORE, // C(ea) := R(a)
X BR, // pc := ea
X BRNEG, // if R(a) < 0 then pc := ea
X BRZERO, // if R(a) = 0 then pc := ea
X BRPOS, // if R(a) > 0 then pc := ea
X BRSUBR, // R(a) := pc+2; pc := ea
X READ, // Cause trap
X WRITE, // Cause trap
X SVC, // Cause SVC trap
X LAST_INSTR
X};
X
X/*
X *------------------------------------------------------------------------
X * Channel commands
X */
X
X // Note each device reads or writes records
X // of exactly page size. The I/O buffer should
X // be on the page boundary. That's why it's
X // enough to specify only page no of I/O buffer
X
X // Channel Command Word
Xstruct CCW
X{
X unsigned short
X page_no : 10, // Page no to be used in the op
X keep_going : 1, // CCW chain flag
X opcode : 4, // Operation code
X reserved : 1; // always zero
X};
X
Xenum CCWOpCodes
X{
X ILLEGAL_CCW, // Illegal operation
X SETMAP, // Switch I/O address mapping
X SETPTBR, // Set page base reg | for address
X SETPTL, // Set page len | translation
X SEEKOP, // Seek operation for disk,
X SKIPOP = SEEKOP, // Skip, CR for printer
X READOP, // Read
X WRITEOP, // Write
X LAST_CCW_CODE
X};
X
X#endif
X
END_OF_FILE
if test 2734 -ne `wc -c <'instruction_set.h'`; then
echo shar: \"'instruction_set.h'\" unpacked with wrong size!
fi
# end of 'instruction_set.h'
fi
if test -f 'io_requests.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'io_requests.cc'\"
else
echo shar: Extracting \"'io_requests.cc'\" \(2955 characters\)
sed "s/^X//" >'io_requests.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 * Managing input/output requests
X * by which the CPU and I/O managers communicate with each other
X *
X ************************************************************************
X */
X
X#include "io_manager.h"
X#include "myenv.h"
X
X/*
X *------------------------------------------------------------------------
X * Elementary operations on the contents of a
X * single request
X */
X
XIORequest::IORequest(void)
X{
X pid = NIL_pid;
X device_no = 0;
X buffer_ptr = return_code_vptr = return_code_pptr = 0;
X rec_count = disk_address = 0;
X return_code = 0;
X
X register int i;
X for(i=0; i<max_no_recs; i++)
X io_pages[i] = 0;
X}
X
Xvoid IORequest::dump(void) const
X{
X message("\nI/O request block #%d for %s operation of process #%d"
X "\n\ton device #%d, to record buffer %o, record count %d, "
X "from sector %d."
X "\n\tReturn code is to be written at %o. Return code so far is %d\n",
X id, (operation == IO_READ ? "read" : "write"), pid,
X device_no,buffer_ptr,rec_count,disk_address,return_code_vptr,
X return_code);
X}
X
X // Dispose of the request block
Xvoid IORequest::dispose(void)
X{
X pid = NIL_pid;
X device_no = 0;
X buffer_ptr = return_code_vptr = return_code_pptr = 0;
X rec_count = disk_address = 0;
X return_code = 0;
X
X assert( io_pages[0] == 0 ); // Just to make sure the pages were
X // unlocked
X}
X
X/*
X *------------------------------------------------------------------------
X * Constructing the request table
X */
X
XIORequestTable::IORequestTable(const int no_slots)
X : nslots(no_slots)
X{
X assure(nslots > 4,"Number of I/O request slots must be at least 5");
X reqs = new IORequest[nslots];
X
X register RID i;
X for(i=1; i<=nslots; i++)
X {
X IORequest& req = (*this)[i];
X req.id = i;
X req.key = 0;
X freeIORs.append(req);
X }
X}
X
X/*
X *------------------------------------------------------------------------
X * Elementary request table operations
X */
X
X // Get a request given its no
XIORequest& IORequestTable::operator [] (const RID rid) const
X{
X if( rid == NIL_rid )
X _error("FATAL: Requested IORequest id is NIL");
X if( rid > nslots )
X _error("FATAL: IORequest id %d is too big",rid);
X return reqs[rid-1];
X}
X
X // Print info about requests
Xvoid IORequestTable::dump(void) const
X{
X register int i;
X for(i=1; i<=nslots; i++)
X {
X IORequest& req = (*this)[i];
X if( req.pid != NIL_pid )
X req.dump();
X }
X}
X
X // Allocate a new request, return NIL
X // if the system run out of templates
XRID IORequestTable::new_request(void)
X{
X if( freeIORs.is_empty() )
X return NIL_rid;
X return freeIORs.get_from_head()->id;
X}
X
X
X // Dispose of the given IORequest
Xvoid IORequestTable::dispose(const RID rid)
X{
X IORequest& req = (*this)[rid];
X assert( rid == req.id );
X req.dispose();
X freeIORs.append(req);
X}
END_OF_FILE
if test 2955 -ne `wc -c <'io_requests.cc'`; then
echo shar: \"'io_requests.cc'\" unpacked with wrong size!
fi
# end of 'io_requests.cc'
fi
if test -f 'mult_proc.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'mult_proc.cc'\"
else
echo shar: Extracting \"'mult_proc.cc'\" \(3707 characters\)
sed "s/^X//" >'mult_proc.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * Multiprocessing under VM_UNT - Virtual OS
X *
X * The present file contains interfaces with the system library
X * of VM_UNT.
X * Important!
X * Turn off optimization while compiling the present flag. This
X * would prevent the compiler from keeping too much data in registers
X * across the function calls. A call to proc_switching(), either explicit
X * or implicit (through the P-semaphor operation), leads potentially to
X * the thread switching. As experience shows, some registers would not
X * be restored after the thread gets control back.
X *
X * Note, if the preprocessor symbol DEBUG is set, some debug information
X * as to setting/releasing the locks, etc. is printed FYI.
X *
X ************************************************************************
X */
X
X#include "mult_proc.h"
X#pragma implementation "mult_proc.h"
X
X#include "myenv.h"
X#include <setjmp.h>
X#include <std.h>
X
X/*
X *------------------------------------------------------------------------
X * Semaphores
X */
X
Xextern "C" { // VM_UNT library calls
X void p(void *);
X void v(void *);
X int sem_awaited(void *);
X void * seminit(const char * name, const int size);
X}
X
X // Create a semaphore with a specified name
X // and assign an initial value to it
XSemaphore::Semaphore(const char * _name, const int in_value)
X{
X assert( _name != 0 );
X assure( in_value >= 0, "Initial value of the semaphore cannot be negative");
X strncpy(name,_name,sizeof(name)-1);
X value = in_value;
X
X assert( (_sem_ptr = seminit(name,in_value)) != 0 );
X#ifdef DEBUG
X message("\nSemaphore '%s' (ID=%x), in_value %d has been set up",name,
X (int)_sem_ptr,value);
X#endif
X}
X
X // P-semaphore operation
Xvoid Semaphore::operator -- (void)
X{
X#ifdef DEBUG
X message("\nAbout to perform P-operation on '%s' (ID=%x), value %d",
X name,(int)_sem_ptr,value);
X#endif
X value--;
X asm("pushl %esi");
X ::p(_sem_ptr);
X asm("popl %esi");
X#ifdef DEBUG
X message("\nWoke up after sleeping on P-operation on '%s' (ID=%x), value %d",
X name,(int)_sem_ptr,value);
X#endif
X}
X
X // V-semaphore operation
Xvoid Semaphore::operator ++ (void)
X{
X#ifdef DEBUG
X message("\nAbout to perform V-operation on '%s' (ID=%x), value %d",
X name,(int)_sem_ptr,value);
X#endif
X value++;
X ::v(_sem_ptr);
X}
X
X // Check to see if somebody is waiting on
X // this semaphore
Xint Semaphore::awaited(void)
X{
X return ::sem_awaited(_sem_ptr);
X}
X
X/*
X *------------------------------------------------------------------------
X * Threads of CPU control
X */
X // System calls in VM_UNT
Xextern "C" {
X // Create a thread. Return 0 if we're
X // in the child thread, and 1 otherwise
X // (kind of like fork())
X int newproc(const char * name, const short priority);
X volatile void endproc(void); // Terminate the thread
X}
X
Xstatic char Was_stack_saved = 0;
X
X // Create a thread with a specified name
X // and have it run the procedure we want
X // until it is over
XThread::Thread(const char * name, const short priority, Thread_body((*body)))
X{
X if( !Was_stack_saved )
X {
X Was_stack_saved = 1;
X extern int _stackinit; // The following instructions save
X asm("movl %esp,__stackinit"); // the stack of the calling proc
X asm("addl $28,__stackinit"); // 28 = (4+3) long words in stack
X }
X
X assert( name != 0 );
X
X if( !newproc(name,priority) )
X { // We're in the child thread now
X#ifdef DEBUG
X message("\nRunning a thread '%s', priority %d\n",name,priority);
X#endif
X body();
X#ifdef DEBUG
X message("\nThread '%s' is through\n",name);
X#endif
X endproc();
X }
X // We're in the parent thread now
X}
X
END_OF_FILE
if test 3707 -ne `wc -c <'mult_proc.cc'`; then
echo shar: \"'mult_proc.cc'\" unpacked with wrong size!
fi
# end of 'mult_proc.cc'
fi
if test -f 'mult_proc.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'mult_proc.h'\"
else
echo shar: Extracting \"'mult_proc.h'\" \(2564 characters\)
sed "s/^X//" >'mult_proc.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * Multiprocessing under VM_UNT - Virtual OS
X * Declaration of basic primitives
X *
X * The present file contains description of operations that provide
X * multiprocessing and synchronization under Dr. C.-Q. Young's
X * virtual operating system, which is running on Sequent Symmetry
X * series computer.
X *
X ************************************************************************
X */
X
X#ifndef _mult_proc_h
X#define _mult_proc_h 1
X#pragma interface
X
X/*
X *------------------------------------------------------------------------
X * Semaphores
X */
X
Xclass Semaphore
X{
X void * _sem_ptr; // Pointer to the internal structure
X char name[20]; // Semaphore name
X short value; // Semaphore current value
X
Xpublic:
X Semaphore(const char * name, const int in_value);
X ~Semaphore(void) {}
X void operator -- (void); // P-operation
X void operator ++ (void); // V-operation
X int awaited(void); // True if somebody is waiting on
X // the semaphore
X
X // This would make assignment of the Semaphore
X // illegal (because it's stupid).
X Semaphore(Semaphore& dummy);
X Semaphore& operator = (Semaphore& dummy);
X};
X
X/*
X *------------------------------------------------------------------------
X * Threads of CPU control
X */
X
X#if 0
Xtypedef void (*Thread_body)(void); // Describes what the thread has
X // got to do
X#endif // Too bad, the compiler failed to take
X#define Thread_body(X) void X(void) // that, so we had to rely on CPP
X
X#if 1
Xextern "C" void proc_switching(void); // This is what to call to switch
X // to another thread
Xextern "C" {
X // Create a thread. Return 0 if we're
X // in the child thread, and 1 otherwise
X // (kind of like fork())
X int newproc(const char * name, const short priority);
X volatile void endproc(void); // Terminate the thread
X}
X
Xclass Thread
X{
X
Xpublic:
X Thread(const char * name, const short priority, Thread_body((*body)));
X ~Thread(void) {} // No way to kill it
X};
X#else
X // Disregard the following, please
Xextern void proc_switching(void); // This is what to call to switch
X // to another thread
Xextern void ManageThreads(void); // This is what to call to get
X // into multiprocessing
X
Xtypedef unsigned short TID; // Thread ID - index of the TCB in TCT
X
Xclass Thread
X{
X TID thread_id;
X
Xpublic:
X Thread(const char * name, const short priority, Thread_body((*body)));
X ~Thread(void) {} // No way to kill it
X};
X#endif
X
X#endif
X
END_OF_FILE
if test 2564 -ne `wc -c <'mult_proc.h'`; then
echo shar: \"'mult_proc.h'\" unpacked with wrong size!
fi
# end of 'mult_proc.h'
fi
if test -f 'myenv.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'myenv.cc'\"
else
echo shar: Extracting \"'myenv.cc'\" \(1950 characters\)
sed "s/^X//" >'myenv.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X * Service C++ functions
X * that support the standard environment for me
X */
X
X#pragma implementation
X
X#include "myenv.h"
X#include <builtin.h>
X#include <stdarg.h>
X
X/*
X *-----------------------------------------------------------------------
X * Some global constant pertaining to input/output
X */
X
Xconst char _Minuses [] = "\
X-------------------------------------------------------------------------------";
X
Xconst char _Asteriscs [] = "\
X*******************************************************************************";
X
Xconst char _Equals [] = "\
X===============================================================================";
X
X
X/*
X *------------------------------------------------------------------------
X * Print an error message at stderr and abort
X * Synopsis
X * volatile void _error(const char * message,... );
X * Message may contain format control sequences %x. Items to print
X * with the control sequences are to be passed as additional arguments to
X * the function call.
X */
X
Xvolatile void _error(const char * message,...)
X{
X va_list args;
X va_start(args,message); /* Init 'args' to the beginning of */
X /* the variable length list of args*/
X fprintf(stderr,"\n_error:\n");
X vfprintf(stderr,message,args);
X fputs("\n",stderr);
X abort();
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Print a message at stderr
X * Synopsis
X * void message(const char * text,... );
X * Message may contain format control sequences %x. Items to print
X * with the control sequences are to be passed as additional arguments to
X * the function call.
X */
X
Xvoid message(const char * text,...)
X{
X va_list args;
X va_start(args,text); /* Init 'args' to the beginning of */
X /* the variable length list of args*/
X vfprintf(stderr,text,args);
X}
X
END_OF_FILE
if test 1950 -ne `wc -c <'myenv.cc'`; then
echo shar: \"'myenv.cc'\" unpacked with wrong size!
fi
# end of 'myenv.cc'
fi
if test -f 'oper_system.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'oper_system.h'\"
else
echo shar: Extracting \"'oper_system.h'\" \(1110 characters\)
sed "s/^X//" >'oper_system.h' <<'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 * This file describes the configuarion of the OS,
X * i.e. all the pieces it is built from
X *
X ************************************************************************
X */
X
X#ifndef _oper_system_h
X#define _oper_system_h 1
X#pragma interface
X
X#include "computer.h"
X#include "cpu_manager.h"
X#include "mem_manager.h"
X#include "io_manager.h"
X
Xclass OperatingSystem : public Computer
X{
Xpublic:
X MemoryManager mem_manager;
X CPUManager cpu_manager;
X IOManager io_manager;
X IOChannelManager cr_dev_manager;
X IOChannelManager lp_dev_manager;
X IOChannelManager hd_dev_manager;
X
Xpublic:
X OperatingSystem(void) : cpu_manager(CPU,mem_manager,io_manager),
X mem_manager(memory), io_manager(cpu_manager),
X cr_dev_manager(card_reader,io_manager),
X lp_dev_manager(line_printer,io_manager),
X hd_dev_manager(hard_disk,io_manager)
X {}
X ~OperatingSystem(void) {}
X};
X
X#endif
END_OF_FILE
if test 1110 -ne `wc -c <'oper_system.h'`; then
echo shar: \"'oper_system.h'\" unpacked with wrong size!
fi
# end of 'oper_system.h'
fi
if test -f 'print_file' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'print_file'\"
else
echo shar: Extracting \"'print_file'\" \(524 characters\)
sed "s/^X//" >'print_file' <<'END_OF_FILE'
X
X0000000000000000000000000000000000000000000000000000000000000000
X0000000000002000000000000000000000000000000000000000000000000000
X
X0000000000000000000000000010000000000000000000000000000000000000
X0000000000000000000000000000000000000000000000000000000000000000
X
X0000000000000000000000000020000000000000000000000000000000000000
X0000000000000000000000000000000000000000000000000000000000000000
X
X0000000000000000000000000030000000000000000000000000000000000000
X0000000000000000000000000000000000000000000000000000000000000000
END_OF_FILE
if test 524 -ne `wc -c <'print_file'`; then
echo shar: \"'print_file'\" unpacked with wrong size!
fi
# end of 'print_file'
fi
if test -f 'processes.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'processes.h'\"
else
echo shar: Extracting \"'processes.h'\" \(1982 characters\)
sed "s/^X//" >'processes.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X *
X * Process handling and scheduling
X *
X ************************************************************************
X */
X
X#ifndef _processes_h
X#define _processes_h 1
X#pragma interface
X
X#include "hardware.h"
X#include "sysqueues.h"
X#include "mem_manager.h"
X
Xtypedef unsigned short PID; // Process ID
Xconst PID NIL_pid = 0; // Other PIDs are positive
X
X // Process Control Block
Xclass PCB : public Context, public QueueLink, public MMContext
X{
Xpublic:
X enum PCB_STATUS { Ok, Wait_for_kids, Wait_on_sema, Dead, Doing_io,
X Shall_die } status;
X
X PID parent; // Parent process ID (may be NIL_pid)
X PID lchild; // Left child ID
X PID rchild; // Right child ID
X
X PCB(void);
X ~PCB(void) {}
X void dump(void); // Print all the info about this
X // PCB
X void fork_from_dad(PCB& dad); // Fork this PCB from dad's
X void brand_new(void); // PCB for a brand-new process
X void save_context(const CentralProcessingUnit& cpu_hardware);
X void load_context(CentralProcessingUnit& cpu_hardware);
X};
X
Xclass ProcessTable : public DiagnosticPanel
X{
X PCB * pcbs; // Array of PCB
X const int nslots; // No. of slots (max value for Index)
X
X BasicQueue freePCBs; // Queue of free PCB's
X
X PID resume_scan_pid; // PID for scanning a blocked process
X
Xpublic:
X ProcessTable(const int nslots);
X ~ProcessTable(void) {}
X PCB& operator [] (const PID pid); // Get a PCB by its id
X void dump(void); // Dump info on processes in system
X PID new_pid(void); // Get PID of a process to create
X void dispose(const PID pid); // Dispose of the PCB
X void start_scan(void) { resume_scan_pid = 1; }
X enum SEARCH_CRIT { Blocked, Ready };
X PID next_pcb(const SEARCH_CRIT crit); // Find next pcb according to some crit
X int q_all_free(void) { return freePCBs.q_no_elems() == nslots; }
X};
X
X#endif
END_OF_FILE
if test 1982 -ne `wc -c <'processes.h'`; then
echo shar: \"'processes.h'\" unpacked with wrong size!
fi
# end of 'processes.h'
fi
if test -f 'semaphores.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'semaphores.h'\"
else
echo shar: Extracting \"'semaphores.h'\" \(1990 characters\)
sed "s/^X//" >'semaphores.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * UNT Virtual Machine
X *
X * Operations on semaphores
X *
X ************************************************************************
X */
X
X#ifndef _semaphores_h
X#define _semaphores_h 1
X#pragma interface
X
X#include "processes.h"
X
Xtypedef unsigned short SID; // Semaphore ID
Xconst SID NIL_sid = 0; // Other SIDs are positive
X
Xclass SemaphoreTable;
X
Xclass Sema : public QueueLink
X{
X friend class SemaphoreTable;
X
X PID owner; // Process-owner
X int value; // Current semaphore value
X Semaphore lock; // Mutual exclusion lock
X BasicQueue waiting_list; // Waiting list of processes
X
X void dispose(void); // Inactivate the semaphore
X void purge(const PID pid); // Purge a process pid from
X // any waiting queue, if any
X
Xpublic:
X Sema(void);
X ~Sema(void) {}
X PID q_owner(void) const { return owner; }
X // Perform P-operation. If value goes
X // negative, return FALSE and queue the
X // pcb into the internal queue
X int p(PCB& pcb);
X // Perform V-operation. If value was negative
X // get a process from waiting list and
X // return its PID. Otherwise return NIL_pid
X PID v(void);
X};
X
Xclass SemaphoreTable : public DiagnosticPanel
X{
X Sema * slots;
X const int nslots;
X
X BasicQueue freeSEMs;
X
Xpublic:
X SemaphoreTable(const int _nslots);
X ~SemaphoreTable(void) {}
X // Get a Semaphore given its id
X Sema& operator [] (const SID id);
X // Get a new SID or NIL if it is not
X // possible
X SID new_semaphore(const int in_value, const PID owner);
X void dump(void); // Print info about all active semas
X
X int is_active(const SID id); // Check to see if SID is active
X SID owned_by(const PID owner);// Get SID owned by a given owner
X void dispose(const SID sid); // Dispose of a given semaphore
X void purge(const PID pid); // Purge the process pid from a semaphore
X // queue
X};
X
X#endif
END_OF_FILE
if test 1990 -ne `wc -c <'semaphores.h'`; then
echo shar: \"'semaphores.h'\" unpacked with wrong size!
fi
# end of 'semaphores.h'
fi
if test -f 'sysqueues.cc' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'sysqueues.cc'\"
else
echo shar: Extracting \"'sysqueues.cc'\" \(3396 characters\)
sed "s/^X//" >'sysqueues.cc' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * Basic Queue Operations
X *
X ************************************************************************
X */
X
X#include "sysqueues.h"
X#pragma implementation "sysqueues.h"
X
X#include "myenv.h"
X
X/*
X *------------------------------------------------------------------------
X * Constructing and destructing
X */
X
X // Create an empty BasicQueue
XBasicQueue::BasicQueue(void)
X : no_elements(0),
X access_lock("mutual exclusion lock",1),
X queue_sema("count",0)
X{
X head = tail = 0;
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Basic Queue Operations
X *
X */
X
X // Get the element from the top of the
X // queue. Wait if nothing is available
XQueueLink * BasicQueue::get_from_head(void)
X{
X queue_sema--; // Tell the intention to get, or
X // wait if nothing available
X access_lock--; // Get access to queue control fields
X assure(no_elements > 0,"The Basic queue is empty - nothing to get");
X no_elements--;
X QueueLink& el = *head;
X assert( el.prev == 0 ); // Head el should not have any
X // predecessors
X if( el.next != 0 )
X el.next->prev = 0;
X if( tail == &el )
X tail = el.prev;
X head = el.next;
X el.next = el.prev = 0;
X access_lock++; // Release the lock - done with update
X return ⪙
X}
X
X // Add an element to the end of the Queue
Xvoid BasicQueue::append(QueueLink& el)
X{
X access_lock--; // Get access to queue control fields
X if( head == 0 )
X head = ⪙
X el.next = 0;
X el.prev = tail;
X if( tail != 0 )
X tail->next = ⪙
X tail = ⪙
X no_elements++;
X access_lock++; // Release the lock - done with update
X queue_sema++; // Tell everybody we just enqueued smth
X}
X
X // Dequeue a given element from the queue
X // An element should already be in the
X // queue
Xvoid BasicQueue::dequeue(QueueLink& el)
X{
X assure(no_elements > 0,"The Basic queue is empty - cannot dequeue");
X queue_sema--; // Decrease the count. Always succeds
X // due to the condition above
X access_lock--; // Get access to queue control fields
X no_elements--;
X if( el.prev != 0 )
X el.prev->next = el.next;
X if( el.next != 0 )
X el.next->prev = el.prev;
X if( tail == &el )
X tail = el.prev;
X if( head == &el )
X head = el.next;
X el.next = el.prev = 0;
X access_lock++; // Release the lock - done with update
X}
X
X
X/*
X *------------------------------------------------------------------------
X * Service Queue Operations
X */
X
X // Dump IDs of elements in the queue
Xvoid BasicQueue::dump_ids(void)
X{
X access_lock--; // Get access to queue control fields
X
X if( no_elements == 0 )
X message("\nQueue is empty\n");
X else
X {
X register QueueLink * el = head;
X assert( el != 0 );
X message("\nID's of queue elements: ");
X for(; el != 0; el = el->next)
X message("%d ",el->id);
X message("\n");
X }
X access_lock++; // Release the lock
X}
X
X // If an element with the ID in a queue,
X // delete it from the queue
X // Return TRUE if it was successful
Xint BasicQueue::purge_id(const int id)
X{
X if( no_elements != 0 )
X {
X register QueueLink * el = head;
X assert( el != 0 );
X for(; el != 0; el = el->next)
X if( el->id == id )
X {
X dequeue(*el);
X return 1;
X }
X }
X return 0;
X}
X
X
END_OF_FILE
if test 3396 -ne `wc -c <'sysqueues.cc'`; then
echo shar: \"'sysqueues.cc'\" unpacked with wrong size!
fi
# end of 'sysqueues.cc'
fi
if test -f 'sysqueues.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'sysqueues.h'\"
else
echo shar: Extracting \"'sysqueues.h'\" \(2972 characters\)
sed "s/^X//" >'sysqueues.h' <<'END_OF_FILE'
X// This may look like C code, but it is really -*- C++ -*-
X/*
X ************************************************************************
X *
X * Generic Asynchronous Queue
X *
X * The present file declares classes to handle simple double-linked queues
X * in a multiple access mode. Two semaphores are provided to resolve
X * possible conflicts due to the access to the queue by several concurrently
X * running processes (threads). One semaphore counts the no. of available
X * resources (elements of the queue). A thread requesting the unavailable
X * resource, i.e. wanting to get an element from the empty queue, is to be
X * put down to sleep until somebody else would enqueue smth into the queue.
X * It means, the dequeuing process performs P-operation and the enqueuing
X * one needs to do V-operation on the count semaphore of the queue. Another
X * semaphor provides for the establishing of the critical section when
X * the process updates control structures of the queue.
X *
X * The queue is double-linked and allows a variety of operations,
X * inserting an element to the head/tail of the queue, dequeuing an element
X * from the head as well as from arbitrary position of the queue,
X * search on id and key. A queue element (slot) contains, besides
X * linking pointers, two integer fields, id and key, which the user
X * can use in any way he thinks fit. Queue opeartions do not change them,
X * though some functions are provided for searching for the id and the key.
X *
X * The implementation of queues is based on the double-linked list.
X *
X ************************************************************************
X */
X
X#ifndef _sysqueues_h
X#define _sysqueues_h 1
X#pragma interface
X
X#include "mult_proc.h"
X
Xclass BasicQueue;
X
X // This is how an element of the queue
X // looks like
Xclass QueueLink
X{
X friend class BasicQueue;
X
X QueueLink * prev; // Ptr to the prev element
X QueueLink * next; // Ptr to the next element
X
Xpublic:
X int id; // Some ID
X int key; // Arbitrary key
X
X QueueLink(void) : prev(0), next(0) {}
X virtual ~QueueLink(void) {}
X};
X
Xclass BasicQueue
X{
X int no_elements; // No. of occupied slots
X QueueLink * head; // Ptr to the 1st element in the
X // queue
X QueueLink * tail; // Ptr to the last element in the
X // queue
X Semaphore access_lock;
X Semaphore queue_sema;
X
Xpublic:
X
X BasicQueue(void); // Create a queue of a given capacity
X ~BasicQueue(void) {}
X
X // Inquires
X
X // Return TRUE if the queue is empty
X int is_empty() const { return no_elements == 0; }
X
X // Return the no. elems in the queue
X int q_no_elems() const { return no_elements; }
X void dump_ids(void); // Dump IDs of elements in the queue
X
X QueueLink * get_from_head(void); // Get and dequeue the top element
X void append(QueueLink& el); // Add an element to the end of queue
X void dequeue(QueueLink& el); // Dequeue a given element
X int purge_id(const int id); // Purge a queue from a given element
X};
X
X#endif
END_OF_FILE
if test 2972 -ne `wc -c <'sysqueues.h'`; then
echo shar: \"'sysqueues.h'\" unpacked with wrong size!
fi
# end of 'sysqueues.h'
fi
if test -f 'virt_mem_comp.txt' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'virt_mem_comp.txt'\"
else
echo shar: Extracting \"'virt_mem_comp.txt'\" \(2454 characters\)
sed "s/^X//" >'virt_mem_comp.txt' <<'END_OF_FILE'
X Comparison of page replacement startegies
X
X
XTest example:
XSet of 3 jobs running concurrently in VM UNT
XDrum file with program images: prog4/four.123.dat
X
X
XSWAP OUT STRATEGY
Xallocate page until physical memory is exhausted, then find a victim
Xand swap it out.
X
X
X PID NF PID NF PID NF PID NF PID NF Total
XJob #1 4 0 9 2 10 1 1 3 6
X
XJob #2 5 2 7 0 12 2 11 1 2 2 7
X
XJob #3 6 43 8 30 3 2 75
X ---------------
X 88
XNote,
X PID - process ID of a process in the job
X NF - the total number of the page faults the process
X has incurred by the time it finishes
X
X
XLOCAL LRU STRATEGY
XThe working set quota is set to 14 and reinforced. Any process that
Xfills its working set up to the quota and still needs more pages,
Xshould first unreference (and swap out) the least recently used
Xpage. The current context of the process keeps a count of the time
X(in runs of the process on CPU) a page has last been used. The present
Xstrategy is somewhat similar to that implemented in VAX/VMS.
X
X
X PID NF PID NF PID NF PID NF PID NF Total
XJob #1 4 0 9 2 10 1 1 3 6
X
XJob #2 5 2 7 0 12 2 11 1 2 1 6
X
XJob #3 6 47 8 32 3 1 80
X ---------------
X 92
X
XCONCLUSION
X
XThe grand total number of page faults is slightly higher than with the
Xsimple "rob-first-appropriate" page replacement strategy. Yet one has
Xto keep in mind that processes #6 and #8 are far from being "local",
Xthey were designed to systematically access all their address space.
XTypically a process spends most of the time fooling around a limited
Xsegment of data and code. Anyway, it should be stressed that the
Xpresent system run has completed without any process swapping. In
Xreality, process swapping is actually quite expensive and involves a
Xlot of flurry. The process performance suffers from that as well (if
Xthe process is interactive, the user notices that right away). Note
Xthat with the local LRU strategy, only a memory-greedy process
Xincurres some extra page faults. But it does not affect other process.
XIn fact, the number of page faults of other processes is as small as
Xpossible. It means, the process with large memory requirements would
Xsuffer a little from its greed, but it would not punish "moderate"
Xprocesses. So, the bottom line is, the overall system performance
Xwith the local LRU strategy seems to be better.
X
END_OF_FILE
if test 2454 -ne `wc -c <'virt_mem_comp.txt'`; then
echo shar: \"'virt_mem_comp.txt'\" unpacked with wrong size!
fi
# end of 'virt_mem_comp.txt'
fi
echo shar: End of archive 4 \(of 4\).
cp /dev/null ark4isdone