The code in the book is written for a hypothetical machine called the CRA-1. When it came time to develop a simulator for the code, I found out that it would be easier to use an existing simulator than to create a new one so I adapted the one used in NACHOS. This required some changes in the SOS code to accommodate the different machine and the simulation environment. The following two sections describe the MIPS simulator and the changes to SOS (from the book's version) that have been made to make it run on this simulator.
sossim
which is SOS and the MIPS simulator linked together
in an executable program.
All user programs run on the MIPS simulator and so have to be in MIPS machine language. This requires an assembler or compiler that produces MIPS machine language and a linker that will link it. This is hard if you don't happen to have a MIPS machine around.
To make this simpler I have created several user programs that
you can use directly.
They all started out as C programs.
For each one there is a .c version
and a .flat version.
The .flat version is ready to load into the MIPS simulator
and run.
Here is a list of the programs and what they do:
sossim
This will display a message that looks like this:
The following sections discuss each of the commands.
Welcome to the SOS simulator
Commands are:
copy -- copy file into the simulated disk
ip -- set first block of initial process
run -- run the simulation to completion
mem -- set the memory management policy
quantum -- set dispatching time quantum
trace -- turn tracing on (1) or off (0)
debug -- set debug flags (dim or dima for lots)
step -- run the simulation one step (until an interrupt)
help -- print this message
exit -- exit SOS
quit -- exit SOS
copy command will do this.
First it will display the names of all available MIPS executable
files, then it will ask for a file name, and finally it will ask
for the starting disk sector to copy the file to.
It will copy as many sectors and necessary to copy the whole file.
It will report how many sectors it copies and where it puts them.
If you want to cancel the copy command, just type carriage return
to the prompts.
You can verify that the data was written to the disk by looking at the file DISK which holds the contents of the simulated disk. In UNIX, you can dump this file in hex with the command:
od -x DISK
ip command can be used to change this setting.
run command runs the simulation with the current
parameters. You can change parameters and rerunning the
simulation as many times as you want. For example, you can copy
a program in, set ip, and run the simulation. Then copy in another
program, set ip (if necessary), and run that program. And so on.
mem command gives you a menu of memory models
and asks you to choose one.
quit or exit commands will
exit from the simulator.
sossim.
Then run the simulation again.
If you have any bugs, just use whatever C++ debugger you
would normally use (like gdb).
The bulk of the SOS code is unchanged from the book but certain changes were necessary because of the change to the MIPS machine and because of the fact that the operating system is not running on the simulator. We will go through the files and describe the changes in each file.
Tracing calls have been added throughout the operating system to trace the execution and make it more visible to people running the simulation.
The system constants have been changed from const int
to #define constants.
This was to make the compiler happy.
All SOS global data was combined into a single structure
described by struct OSData.
This is a more logical arrangement and takes the operating
system one step closer to being an object.
It also makes clear what variable are SOS globals.
These globals would be in the machine memory in a real operating system.
This change also makes it easier to simulate a two-processor system
by putting the SOS globals in shared memory.
All of the code is changed by this since every access
to a SOS global variable must be prefixed by
sosData->.
The Queue data structure in the book has been replaced
by a List data structure.
This avoids the use of templates since List uses
void pointers instead of templates.
It was convenient to do this since the MIPS simulation implemented
the List data structure.
The book assumed the programs on disk were exact memory images that
just had to be read into memory and executed.
This required the create process system call to know how long
the file was.
I have changed to the next simplest executable format.
An executable file (which has a .flat postfix)
starts with one word which is the length of the executable image.
The executable image follows this one word.
The code has been changed to handle this executable format.
We get the effect of busy waiting for disk IO by calling
TheSimulation->TheInterrupt->Idle().
Because we cannot read from the disk directly into user memory
we have to read into a buffer in the system space and then
use CopyFromSystemSpace to copy the buffer
into user memory.
I have added code here to copy the disk block from the system
memory to the user memory (using CopyFromSystemSpace)
after a block has been read in.
The special case (sosData->pending_disk_request==0)
in DiskInterruptHandler occurs when CreateProcess
uses busy waiting to read in a program image.
In that case we will get a disk completion event but no request
will be pending.
The other changes are in IssueDiskRead
and IssueDiskWrite where we use the
simulator interface to the disk drive instead of the
device register interface used in the book.
This is an example of where the simulation is less realistic
than a full simulation.
In adding a file system, it was necessary to have a general mechanism
whereby a system call could wait for the disk read (or write) and
then continue on where it was.
In the book, we assumed we had system-mode processes and so the
system calls could just suspend and wait.
Each process had a separate kernel-mode stack and it was used to
save the state of the system call.
The solution is impossible to implement using the simulation
architecture that I am using here.
The problem is that the system code does not run on the simulator.
So I have devised a different method for processes to wait.
The first part of this method is some space allocated in each
process descriptor to save the necessary state, that is, the
data required to restart the system call.
Processes only need to wait for disk transfers.
When a system call needs to wait for a disk read or write,
it saves the system call data in the process descriptor
and calls the DiskIO with an event identifier
which indicates which system call needs to be restarted.
One word of data can also be passed to the DiskIO
to be stored with the disk request.
When the disk request completes that event identifier and the
one word of data are passed to the Dispatcher.
The dispatcher then looks at the event identifier and,
if necessary, restarts the system call that was delayed.
System calls are started over from the beginning, not
resumed in the middle.
This is easier but some work is done over again.
I have added code to handle the case of delayed system calls. The delayed system call is called again with the parameters saved in the process descriptor.
The other change here is how a process is started.
In the book, we loaded the registers and used a return
from interrupt instruction to switch to the user program.
Here the interface is totally different.
We load the register with
TheSimulation->TheMachine->WriteRegister,
set the timer with TheSimulation->TheTimer->SetTimer,
and execute the program with TheSimulation->TheMachine->Run.
Change from book????
This is the initialization of the operating system.
I have moved the location of the
system parameters TimeQuantum,
InitialProcessDiskBlock,
and InitialProcessNumberOfBlocks.
I have added a separate initialization function for each of the four subsystems of the operating system: process, memory, IO, and file.
This code was not in the book. It is part of the simulator rather than part of the operating system. It reads the command line and does special things like load programs onto the simulated disk.
The main loop is executed once for each event that occurs. It looks at the event type and executes the proper operating system routine to respond to that event. This code is simulating what hardware interrupt vectoring would do.
This file is extensively changed from the general dynamic memory allocator in the book.
This file is entirely new and shows the code for paged memory management.
The only change here is how the hardware timer is turned off.
This file is not in the book. It contains the tracing procedure for the simulation.
The way the process state is saved is changed due to the form of this simulation. We simply call a procedure to save the state. In the book, the operating system was using the same registers as the user and so it had to be sure to save registers before it used them.
The MIPS machine requires the interrupt handler to modify the program counter (and next program counter) so that the return will start executing past the system call instruction.
The way the timer is reset is changed in the simulation. We no longer use the device register interface.
We have changed the registers used to conform to MIPS conventions. The system call number is in register 2 (not 8 as in the book) and the arguments to the system call are in registers 4 and 5 (not 9 and 10 as in the book).
The registers are accessed using ReadRegister
rather than directly from the registers (as in the book).
The message queues are handled a little differently because
they are not Queues but Lists.
This requires a few more type casts since List
uses null pointers.
Two new system calls WriteString
and WriteInt have been added so that
user programs can print things out.
These are necessary because SOS has no I/O other than disk I/O.
These system calls allow the effect of tracing in the user processes.
The only change here is how the state of the user process is saved. Since we are not running on the same machine as the user it is no longer necessary to be careful not to destroy the state before saving it. We simply call a procedure which saves the state.
The tracing is an artifact of the simulation and not part of the operating system.
The process state is saved by saving all the registers. Note that the PC and the base and limit registers are part of the register array and are not separate as they are in the book.
Copying data to and from system space is different due to
the nature of the simulation.
In the book we just had to simulate the base register.
Here we have to use the special simulator procedures
ReadMem and WriteMem
to read and write user memory.
We have to set up the correct memory address space for the user
process before the transfer.
The strategy used in this simulator is to only run user-mode programs in the simulator and run the operating system as a regular program on the host machine. This makes the simulation a little less realistic but make the simulator easier to develop and port to other systems. It also makes debugging operating system code easier. The first thing to do is to clearly understand what I mean by this.
Suppose we are developing an operating system for a real, physical computer. We have a cross-compiler on another system that will produce executable code for the target computer. We write the operating system on the development system, move the executable code to the target system, and run the operating system directly on the target system.
Another strategy uses a simulation of the target computer. We write (on the development system) a simulator that exactly reproduces the behavior of the target computer system. The main part of this is the simulation of the instruction set of the machine, but it also includes simulations of the memory-mapping system (maybe a paging system), the disk drives, and the other devices attached to the target computer. After the operating system is compiled and loaded on the development system, the executable is loaded into the simulator and run there. This method of development is easier than using the real target computer because it can all be done on the development system. In addition, it can be done before the target computer is operational.
From the viewpoint of simulating an instructional operating system, the simulator approach is very attractive. It means that you can write an operating system for a computer system that is simulated and so it can run on any computer. Students can run the simulator and operating system on their own computer. However, there are two problems with this solutions. One is that you need a complete development system for the target computer and the other is that you can't use your favorite debugging tools.
Let's explain that with an example from this simulator. This simulator simulates the MIPS instruction set. Any program that runs on this simulator must be a MIPS executable. This means that to use this simulator you need an assembler and a compiler that produce MIPS machine code. In addition, you need a loader that will load MIPS executable and you need MIPS libraries. If you are running the simulator on a SPARC machine. You must have SPARC programs that do all these things, that is, SPARC executables to assemble, compile, and load MIPS executables. And you need a library (in the format understood by the MIPS loader) of support programs that are MIPS executable. All of this can be developed but it is a lot of work to do and a lot of work to port them to many different systems.
An alternative approach is used in this simulator. The actual operating system is not run on the simulator but is run on whatever machine the simulator is running on. The operating system and the simulator are linked together in a single executable. Suppose you are running on a SPARC machine The operating system is not MIPS executable but a SPARC executable that runs as a normal user process under UNIX. When the operating system wants to run a user program, it passes control to the MIPS simulator. This is done by the dispatcher in the operating system. The MIPS simulator runs the program until an exception or interrupt occurs and it needs to pass control back to the operating system. When this happens the MIPS simulator records the necessary information about the exception or interrupt and returns control back to the operating system. The operating system uses this information to simulate the effects of an interrupt and branch to the appropriate interrupt handler.
The advantages of this approach are that it is easy to port the MIPS simulator to other systems. The MIPS simulator is a straightforward C++ program that ports easily. The operating system code is compiled on the development system so there is no need to port a suite of development tools. The operating system is a normal C++ program and can be debugged with any debugging tools available on the host system. This might be an easy-to-use, graphical debugging system.
There are some disadvantages to this approach also. They will be described in the next section. The main problem is that the simulation is less realistic.
The simulation is a C++ object and it is only necessary to create the object. The code looks like this:
#include "simulation.h"
TheSimulation = new Simulation;
TheSimulation->TheMachine->Run();
This will execute the user program until an exception or interrupt occurs. Before you run a program you need to set up the registers and load the program (and data) into the simulated memory. After the simulator returns the information about the exception or interrupt is contains in a global variable. The next section discusses these issues.
Sometimes there is no user process to run and you need to wait until the next interrupt occurs. This is done with a call to the idle procedure:
TheSimulation->TheMachine->Idle();
The simulator has an array that contains the memory of the simulated MIPS machine. This memory is divided into pages which are used when paged memory management is turned on. The default size of the memory is 32 pages of 128 bytes each, or 4K bytes of memory. This can be changed when the simulator is initialized.
There are three options for memory management. The default is a base and limit register system. The other two options are a paged system and a TLB-only system.
When the base and limit register system is operating, each address generated by the simulator will be checked against the limit register and the base register will be added to it before the memory is accessed.
See the code simulator for the operation of the paging system.
You can read and write the MIPS memory with the following code:
TheSimulation->TheMachine->ReadMem(mips_addr, size, buffer_addr);
TheSimulation->TheMachine->WriteMem(mips_addr, size, new_value);
mips_addr is an integer and the address in
the (simulated) memory of the MIPS machine.
size is either 1,2, or 4 (bytes).
buffer_addr is an integer pointer of the place
(in the development machine's memory) to put the value.
new_value is value to write into the memory.
A MIPS machine has 32 general-purpose registers. In addition it has a few other register that are used for other purposes. This includes the program counter register. Since the MIPS uses branch delay slots, it also has a nest-program-counter register which contains the next instruction to execute.
The simulator keeps a few registers that are not in a real MIPS processor. These are used to implement the simulation. For example, some of these are used to implement load delays.
With these additional registers there are a total of 41 registers in the simulated MIPS machine.
You can read and write the MIPS registers with the following code:
register_value = TheSimulation->TheMachine->ReadRegister(register_number);
TheSimulation->TheMachine->WriteRegister(register_number, new_register_value );
Here is a list of the registers that are defined:
The simulator contains a small simulated disk. The only operations on the disk are to read or write one disk sector (also called a disk block). The disk has sectors of 128 bytes, 32 sectors per track, and 32 tracks. This is a total of 1024 sectors or 128 K bytes. The sectors on the disk are numbered sequentially from 0 to 1023. You can have the disk interrupt after the completion of an operation or you can inhibit the interrupt.
You can read and write the disk with these instructions:
TheSimulation->TheDisk->ReadRequest(sector_number, buffer, int_enable);
TheSimulation->TheDisk->WriteRequest(sector_number, buffer, int_enable);
sector_number is the sector number on the disk.
buffer is the address (in the development machine's memory)
to read the block into or write the sector from.
int_enable determines whether an interrupt will be generated
when the operation completes.
It is not possible to read from (or write to) the disk into the simulated MIPS memory, that is, into user memory. It is only possible to read and write from operating system memory.
When you call Run, the simulator executes instructions until an event occurs. This event is either an interrupt, an exception or the completion of a disk operation (with no interrupt). When an event occurs, the type of the event is recorded in a global variable and control is returned from Run.
Here is some example code of how you use this global variable.
This code is taken from the file main.cc.
TheSimulation->TheMachine->ReasonForInterrupt = OSInitialization;
while( 1 ) {
// Remember why we got here (what type of interrupt)
ExceptionType reason = TheSimulation->TheMachine->ReasonForInterrupt;
// Clear the interrupt
TheSimulation->TheMachine->ReasonForInterrupt = NoException;
switch( reason ) { // switch on the reason for the interrupt
case NoException:
break;
case OSInitialization:
sos_main();
break;
case SyscallException:
SystemCallInterruptHandler();
break;
case TimerInterrupt:
TimerInterruptHandler();
break;
case DiskInterrupt:
DiskInterruptHandler();
break;
case ReadOnlyException:
case BusErrorException:
case AddressErrorException:
case OverflowException:
case IllegalInstrException:
ProgramErrorInterruptHandler();
break;
case PageFaultException:
case ConsoleWriteInterrupt:
case ConsoleReadInterrupt:
case NetworkSendInterrupt:
case NetworkReceiveInterrupt:
printf( "Unhandled reason for interrupt (%d)\n",
TheSimulation->TheMachine->ReasonForInterrupt );
exit( 2 );
}
}