SOS (Simple Operating System) Simulator

This page contains the documentation for SOS, the simple operating system for use with the book Operating Systems: A Design-Oriented Approach by Charles Crowley.

Introduction and Overview

The book Operating Systems: A Design-Oriented Approach by Charles Crowley contains code for an example operating system. The purpose of this simulator is to allow you to execute this code and observe how it runs. It also allows you to make changes in the code, run them, and debug them.

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.

Running SOS on the Simulator

Compile the MIPS Simulator and SOS

The Makefile should do this for you. It will create an executable called sossim which is SOS and the MIPS simulator linked together in an executable program.

Obtaining User Programs to Run

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:

Running the Simulator

The simulator has a simple command line interface. You are it by running the executable:

sossim This will display a message that looks like this:

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
The following sections discuss each of the commands.
Loading the user programs onto the simulated disk
The simulator cannot run user programs from the file system of the development system. It can only run user programs from its simulated disk. The 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

Setting the location of the initial process
When you run the simulator you have to tell it where to find the program to execute in the initial process. The default is to load the initial process from the MIPS executable at sector 0 of the disk. The ip command can be used to change this setting.
Running the simulation
The 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.
Setting the memory model
There are two memory models that can be used: static allocation (as is used in chapter five of the book) and dynamic allocation (as described in chapter 10 of the book). Both use base and limit registers for memory mapping. The mem command gives you a menu of memory models and asks you to choose one.
Setting the trace variable
The simulator prints out trace statements whenever something of interest in the operating system happens. You can turn this off by setting trace to 0. The default value is 1.
Setting the time quantum
This sets the time quantum used in the round robin scheduling. The units of the quantum is number of MIPS instructions. The default value is 30 so that even short programs will get timer interrupts and context switches.
Setting the debug variable
The debug variable prints out debugging information at the MIPS machine level. It is turns off by default. It consists of a string of up to four letters. The valid letters are: dima. Reasonable values are dim, dima, and m.
Stepping the simulation
This command does not work yet.
Exiting from sossim
Either the quit or exit commands will exit from the simulator.

Modifying SOS

If you want to experiment with SOS you can do it easily. First, modify the code and remake sossim. Then run the simulation again. If you have any bugs, just use whatever C++ debugger you would normally use (like gdb).

Changes to SOS (from the book)

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

Tracing calls have been added throughout the operating system to trace the execution and make it more visible to people running the simulation.

sos.h

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.

createproc.cc

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.

diskdriver.cc

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.

Delayed system calls

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.

dispatcher.cc

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.

filesystem.cc

Change from book????

initialize.cc

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.

main.cc

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.

mem.cc

This file is extensively changed from the general dynamic memory allocator in the book.

mempaged.cc

This file is entirely new and shows the code for paged memory management.

proginthandler.cc

The only change here is how the hardware timer is turned off.

simutils.cc

This file is not in the book. It contains the tracing procedure for the simulation.

syscallhandler.cc

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.

timerinthandler.cc

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.

utils.cc

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 MIPS Simulator

This section describes the MIPS simulator used in the SOS simulation. It is not necessary to understand or even read this section in order to run the simulator. It is here so that you can understand how it works if you are interested.

Overview

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 Interface to the MIPS Simulator

Setting up the Simulation

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;

Calling the Simulator

To run the simulator, make the following call:


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

Reading and Writing the State of the Simulator

The MIPS Memory

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.

The MIPS Registers

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 Disk

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.

Interrupts and Exceptions

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