Overview The aim of the assignment is to implement a simple operating system (SO
ID: 3686594 • Letter: O
Question
Overview
The aim of the assignment is to implement a simple operating system (SOS) developed in java or c++. The SOS is expected to provide a specified system allowing for processes and memory management.
Assessment
The points for the homework are obtained for timely and complete demonstration of intermediate milestones. Your solution should be able to
a. show a working solution,
b. explain how to code your written works,
c. explain any design decisions you made,
d. testing your code with the specifications,
e. inspecting your code as to how well and efficiently it is written, and
f. writing your documentation as to its completeness, appropriateness and consistency with your implementation.
Milestones
The whole system allows up to 10 processes currently stay in the memory, only one of them is running on the CPU, while the others are either in the Ready Queue, or blocked in the Disk Queue (i.e. waiting for disk I/O). Each process has its PCB, just follow the format in the textbook. For memory management, you may choose paging (page size 64 byte or larger) or other management methods. No requirement on deadlock prevention or virtual memory.
Each process has a corresponding program written in script. Although not required, the script may also involve some loop and if-then-else statements so that it will take longer time for you to view the execution of processes.
Explanation / Answer
The C++ Version of the SOS Simulator
The C++ version of the SOS simulator only works on UNIX systems and is available from http://www. cs.unm.edu/~crowley. This simulator does not implement the CRA-1. To ease the coding burden, the simulation was based on a MIPS simulator and a simulation architecture used in NACHOS (http://http.cs.berkeley.edu/~tea/nachos/). One aspect of this simulation architecture is that the operating system code itself does not run on the simulator, only the user process code does. As a consequence of this, the view of the hardware is different from that in the book. The details of saving and restoring processor state, for example, are still present in the simulation but are distinctly different from the code in the book and different from any code based on a real machine. For example, registers are set with function calls to the simulator code. As a result, this simulation comes with a special version of the SOS source code. It is still in C++ but it is changed to conform to the hardware simulation architecture. That simulation comes with commentary describing the differences from the SOS code in the book.
There are a few problems with this simulation. The main one is that it works only on UNIX systems and would require considerable effort to port to Windows. A minor problem is that it is text-only to avoid dependencies with graphics systems. Another problem is that it does not simulate the code in chapters 6 and 8 of Crowley’s Operating Systems because the parallelism cannot be easily simulated using the simulation architecture it is based on.
The Java Version of the SOS Simulator
To deal with the portability issue I have developed a Java version of the SOS source code and a virtual machine simulator (in Java) for it to run on. The main advantage of this version is that it works on all systems that support Java. It will work on a web page with a Java-enabled browser so almost anyone can run the system.
The source code of the Java version of SOS is based on the book version but many changes were necessary. Of course, the conversion from C++ to Java required many small changes although the basic look of the code is quite similar. The change in virtual machine it runs on also required a number of changes in the code.
This document describes the Java version of the SOS simulator. It documents all the changes that were necessary for the conversion.
How To Run Java SOS
The Java simulator can be run with a Java interpreter or with a Java-enabled web browser. First I will describe the Java files necessary to run the simulator and then I will discuss how to run it.
The files
The Java SOS simulation code comprises the following groups of files. All files are written in version 1.0 of Java and the AWT.
Starting the simulation using a Java interpreter.
To run the simulator you need all these files and you need to compile them into “.class ” files. Then you run the simulation by running the class “SIM” (e.g., Java SIM). The files are all written in version 1.0 of Java and the AWT.
Starting the simulation from a web browser.
You can also run the simulation from a Java-enabled web browser by loading the file SIM.html. The file SIM.class and all the other .class files all need to be in the CLASSPATH. Normally it is sufficient to have them all in the same directory as SIM.html.
Or you can run it from my web page (http://www.cs.unm.edu/~crowley/SIM.html).
Running the simulation
When the simulation starts you will see a single window (or a new web page in your browser). You can select from several choices before you run the simulation.
Modifying and testing SOS
You can edit any of the SOS files to make changes in the operation of SOS and run the simulation to see how they work. Just edit the files, recompile them, and run SIM again. You could run it under the Java
debugger if you run into exceptions. This will allow you to program all the exercises from the book that involve modifications to SOS and test them on the simulator.
The Java Virtual Machine
The hardware virtual machine in this simulator is not really too much like a real machine but it does the job of providing a base for the simulation. All of the simulation code is in HWSimulation.java and SIM.java. The simulation has several parts:
Let’s look at each of these in turn.
Simulation of running processes
There are four calls related to running processes.
Interrupt simulation
There are four interrupts: system call, timer, program error, and disk. All interrupt handlers are classes that implement the SIMIntHandler interface, which consists of one operation (HandleInterrupt(int arg)). When the system is initialized, handles to each of the four interrupt handlers is placed in specific memory location reserved for the interrupt vector area. An interrupt is handled by fetching the appropriate handler and calling its HandleInterrupt function.
Memory simulation
Memory simulation is not as realistic as it is in the book (CRA-1) or the UNIX simulator. Since Java itself takes care of allocating memory for Java classes and for loading them into memory, the SOS simulator cannot do that. Instead it only simulates part of the data memory. There is a large array of cells that represents the physical memory of the virtual machine. Currently it contains 10,000 cells. SOS uses 1000
cells for itself and allocates 1000 cells to each process. In a real machine, each cell would be a byte but in the simulation each cell is a Java Object. This allows us to store object handles (such as interrupt handlers) in the simulated memory. Most uses of the memory store integers (actually Java Integer objects) and so there are special memory access functions that treat the memory cells as integers.
Base/bound memory mapping is simulated. The simulated hardware base and bound registers can be set and read. There are mapped and unmapped versions of all the memory access functions. The unmapped versions access the array directing using the memory address provided as an array index. The mapped versions add the base register to the address provided and also check it against the limit register.
This simulated memory is accessed with the following calls:
The operating system keeps a number of things in the simulated memory.
Each process keeps a few things in the simulated physical memory. The simulated memory is the common memory between processes and the operating system and all data passed between them goes through the simulated physical memory.
Right now SOS allocates 1000 cells to each process and only base/limit memory mapping is implemented. Later versions of the Java SOS simulator will implement paging in the simulated memory and applications will use the simulated memory for calculations that test the effectiveness of the virtual memory.
Timer simulation
The simulated hardware timer is quite similar to the one defined for the CRA-1 in the book. The operating system sets the timer with a value and the timer counts the initial value down to 0. When the timer value gets to 0, a timer interrupt is generated and counting stops. There is only one call:
The timer has its own Java thread and ticks continually, even when there is no timer interval.
Disk simulation
The disk simulation is quite simple. It has its own Java thread. It is a loop that continually checks for a disk request. A disk request is made by storing into the disk’s control register. This is done by storing in memory cell 10. This then calls the appropriate call in the disk simulation. Once a disk command is issued the disk simulation delays 500 ms, transfers the data, and then generates the disk interrupt.
The disk class defines two functions:
These disk functions are never called by SOS but only by the memory simulation code which simulates memory mapped I/O by treating memory cells 10, 11, and 12 as disk registers.
Later versions of the simulator will use a more sophisticated disk simulation so that disk accesses will take more or less time depending on where the read head is located when the request is started.
The Simulation
The hardware simulation provides processes (using threads), memory (using an array of Objects), a timer (using a thread and sleep statements), a disk (also using a thread and sleep statements), and hardware services (creating processes, running processes, system call, access to memory, access to the disk). The simulation code builds on this to provide a user interface to the hardware simulation.
The simulation code generates the user interfaces described in the section How To Run Java SOS above. The user interface mainly displays trace messages sent by SOS and the application processes. Most of the simulation code is AWT calls to create and manage the user interface.
It also defines a SIMList class which subclasses the AWT List class to be a specific size.
The Test Applications
The file AppGUICounter.java creates a GUI to a simple counter. A counter was chosen because it is obvious from looking at it when it is running and when it is idle.
The file AppTests.java implements the AppTests class. An AppTests object can be any of four different applications.
These applications use simulated memory cells 101 to 103 for system call arguments, cell 100 for system call return values, and cells 200-207 for a message buffer. These applications also include calls to the Trace function to generate trace messages.
Each application suspends itself immediately after it is started. This is necessary because of the way the SOS simulator using suspend and resume for dispatching.
The SOS Files
In this section we will go through each of the files in SOS and describe what they do and how they differ from the book’s version of the same code.
SOSData.java
The SOSData class contains the data for the operating system. It is a singleton, that is, only one copy of
SOSData will ever be instantiated. The SOSProcessDescriptor class, the SOSWaitQueueItem class, and the SOSDiskRequest class are defined in their own files since Java requires that classes that are used by more than one other class be defined in their own files.
SOSDiskDriver.java
The SOSDiskDriver class implements most of the disk subsystem. The rest is implemented in the
DiskIntHandler class.
The disk queue is a Java Vector instead of the book’s Queue class so the usage is a little different.
The DiskBusy function must interface with the Java virtual machine’s disk simulation and so is different from the version I the book. This is also true of IssueDiskRead and IssueDiskWrite. We still send the commands and parameters to the disk by setting disk registers but these exist in the address space of the physical disk array in the Java virtual machine.
SOSDiskIntHandler.java
The SOSDiskIntHandler class implements the SIMIntHandler interface so it can be called by the disk simulation. Saving the process state and resetting the hardware timer are different due to differences in the Java virtual machine.
SOSDiskRequest.java
The SOSDiskRequest class must be defined in its own file because Java requires this.
SOSMem.java
The SOSMem class is not completed yet.
SOSProcessDescriptor.java
The SOSProcessDescriptor class defines the process descriptor (naturally) for SOS. The main change here is that the save area is not required because Java saves the state of the thread when we suspend it. We have no way to get to this state using Java code.
SOSProcessManager.java
The SOSProcessManager class contains the CreateProcessSysProc function and the
Dispatcher function. These are separated in the book version of SOS.
CreateProcessSysProc is different because of differences in the Java virtual machine. The CreateProcess function handles the virtual machine process creation. This was not necessary in the book version of SOS. The Java version does not allocate memory for code since this is handled automatically by Java. Space in the physical memory array is allocated.
In SelectProcessToRun, the variable next_proc has been moved from being a static local variable to being a variable in sosData. Other than the addition of tracing, this is the only change to
SelectProcessToRun.
The RunProcess function is totally different because it must interface with the Java virtual machine instead of the CRA-1 virtual machine. Setting the timer and running a process are done completely differently.
SOSProgIntHandler.java
The SOSProgIntHandler class implements the SIMIntHandler interface. This is difference from the book version of SOS. The change was required because of the change to Java.
SOSStart.java
The SOSStart class does system initialization. The interrupt vectors are handled differently in the Java version. The interrupt vector area is kept in the physical memory array as handles to the interrupt handler objects. SOSStart initializes the interrupt vector area. I have also restructured the initialization code so that the I/O system and the process system each have their own initialization procedures. This seemed more modular. Process manager initialization requires the construction of a number of Java objects in arrays. The message buffers are in the physical memory array and so are accessed differently as they are linked up. We use Java Vectors for queues and they are constructed (and used) differently than the Queue class in the book.
Java requires us to keep more handles, like the one to the disk driver that is initialized in
InitializeIOSystem.
In the Java virtual machine calls to the Dispatcher actually return since we are not manipulating actual stacks. This means we must explicitly suspend the startup process after it returns from the dispatcher. The startup thread only does this startup code and then it is no longer used.
SOSSyscallIntHandler.java
The SOSSyscallIntHandler class implements the SIMIntHandler interface. This is how we cause interrupts in the Java virtual machine. This is required by the stronger typing rules in Java.
The system call argument in the Java virtual machine are handled differently than they were in the CRA-1. The Java virtual machine has no registers and so system call arguments cannot be passed in register. In the Java virtual machine we get them out of the physical memory array. The return value of the system call is also placed in the physical memory array instead of in a register.
Resetting the timer is different in the Java virtual machine. Process state does not have to be saved in the Java virtual machine.
The message queues are implemented with Java Vectors which are used a bit differently than the Queue class postulated in the book.
Message buffers in the Java version of SOS are kept in the physical memory array so we use MemoryCopy instead of calls to transfer data between address spaces. We see this in the
TransferMessage function and the MemoryCopy function.
The GetMessageBuffer and FreeMessageBuffer functions are included in this class instead of with the global data where the book places them.
SOSTimerIntHandler.java
The SOSTimerIntHandler class handles timeout of time slices allocated to processes. The thread representing the user process must be suspended explicitly here.
SOSWaitQueueItem.java
The SOSWaitQueueItem class must be defined in its own file because Java requires this. In the book the structure definition was kept with the global data definitions.
Control Flow in Java SOS
It will help you to understand how the system works if you can see how control flows through the system. Let’s start with the path of a system call. Each user process has its own thread and it is that thread that will make the system call. This same thread handles the system call in the kernel and then returns. Here is a chart of the control flow.
App: User Thread
HW: SystemCall
SOS: SyscallIntHandler
SOS: Dispatcher
HW: RunProcess
3. Actions after system call
Note that each call is returned from normally. There are no abrupt shifts of control in a single thread as there would be in the CRA-1 simulation or in a real machine. The shifts of control are achieved by switching between threads. If this system call causes the current process to changes then action1 in the hardware RunProcess function will resume the thread of the new process. The thread of the old process will continue to run. It will return from RunProcess, return from Dispatcher, return from SyscallIntHandler and then, in the hardware SystemCall function the thread will be suspended. If the process making the system call is chosen to run again then the resume in RunProcess will have no affect since the thread is not suspended and the suspend in SystemCall will not be done. The process will then return from the hardware system call and the calling process will resume execution.
Now let us look at the flow of control when there is a timer interrupt. Two threads will be running. The first is the thread of the running process and the second is the thread of the timer. The timer thread will be sleeping. When the sleep ends it will gain control (because it has higher priority than threads for user processes). It will then take the following actions:
HW: Timer
SOS: TimerIntHandler
SOS: Dispatcher
HW: RunProcess
Now, we begin our journey.
When we reboot our computer, it must start up again, initially without any notion of an operating system. Somehow, it must load the operating system --- whatever variant that may be --- from some permanent storage device that is currently attached to the computer (e.g. a oppy disk, a hard disk, a USB dongle, etc.).
As we will shortly discover, the pre-OS environment of your computer o ers little in the way of rich services: at this stage even a simple le system would be a luxury (e.g. read and write logical les to a disk), but we have none of that. Luckily, what we do have is the Basic Input/Output Software (BIOS), a collection of software routines that are initially loaded from a chip into memory and initialised when the computer is switched on. BIOS provides auto-detection and basic control of your computer's essential devices, such as the screen, keyboard, and hard disks.
After BIOS completes some low-level tests of the hardware, particularly whether or not the installed memory is working correctly, it must boot the operating system stored on one of your devices. Here, we are reminded, though, that BIOS cannot simply load a le that represents your operating system from a disk, since BIOS has no notion of a le-system. BIOS must read speci c sectors of data (usually 512 bytes in size) from speci c physical locations of the disk devices, such as Cylinder 2, Head 3, Sector 5 (details of disk addressing are described later, in Section XXX).
So, the easiest place for BIOS to nd our OS is in the rst sector of one of the disks (i.e. Cylinder 0, Head 0, Sector 0), known as the boot sector. Since some of our disks may not contain an operating systems (they may simply be connected for additional storage), then it is important that BIOS can determine whether the boot sector of a particular disk is boot code that is intended for execution or simply data. Note that the CPU does not di erentiate between code and data: both can be interpreted as CPU instructions, where code is simply instructions that have been crafted by a programmer into some useful algorithm.
If we use a binary editor, such as TextPad [?] or GHex [?], that will let us write raw byte values to a le --- rather than a standard text editor that will convert characters such as 'A' into ASCII values --- then we can craft ourselves a simple yet valid boot sector.
e9
fd
ff
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
*
00
00
00
00
00
00
00
00
00
00
00
00
00
00
55
aa
Figure 2.1: A machine code boot sector, with each byte displayed in hexadecimal.
Note that, in Figure 2.1, the three important features are:
The initial three bytes, in hexadecimal as 0xe9, 0xfd and 0xff, are actually machine code instructions, as de ned by the CPU manufacturer, to perform an endless jump.
The last two bytes, 0x55 and 0xaa, make up the magic number, which tells BIOS that this is indeed a boot block and not just data that happens to be on a drive's boot sector.
The le is padded with zeros ('*' indicates zeros omitted for brevity), basically to position the magic BIOS number at the end of the 512 byte disk sector.
An important note on endianness. You might be wondering why the magic BIOS number was earlier described as the 16-bit value 0xaa55 but in our boot sector was written as the consecutive bytes 0x55 and 0xaa. This is because the x86 architecture handles multi-byte values in little-endian format, whereby less signi cant bytes proceed more signi cant bytes, which is contrary to our familiar numbering system --- though if our system ever switched and I had $0000005 in my bank account, I would be able to retire now, and perhaps donate a couple of quid to the needy Ex-millionaires Foundation.
Compilers and assemblers can hide many issues of endianness from us by allowing us to de ne the types of data, such that, say, a 16-bit value is serialised automatically into machine code with its bytes in the correct order. However, it is sometimes useful
especially when looking for bugs, to know exactly where an individual byte will be stored on a storage device or in memory, so endianness is very important.
This is possibly the smallest program your computer could run, but it is a valid program nonetheless, and we can test this in two ways, the second of which is much safer and better suited to our kind of experiments:
Using whatever means your current operating system will allow, write this boot block to the rst sector of a non-essential storage device (e.g. oppy disk or ash drive), then reboot the computer.
Use virtual machine software, such as VMWare or VirtualBox, and set the boot block code as a disk image of a virtual machine, then start-up the virtual machine.
You can be sure this code has been loaded and executed if your computer simply hangs after booting, without a message such as No operating system found". This is the in nite loop at work, that we put at the start of the code. Without this loop the CPU would tear o , executing every subsequent instruction in memory, most of which will be random, uninitialised bytes, until it throws itself into some invalid state and either reboots or, by chance, stumbles upon and runs a BIOS routine that formats your main disk.
Remember, it is us that program the computer, and the computer follows our in-structions blindly, fetching and executing them, until it is switched o ; so we need to make sure that it executes our crafted code rather than random bytes of data held some-where in memory. At this low level, we have a lot of power and responsibility over our computer, so we need to learn how to control it.
; A simple boot sector that prints a message to the screen using a BIOS routine.
;
mov
ah ,
0 x0e ;
int
10/ ah =
0eh ->
scrolling
teletype BIOS routine
mov
al ,
'H'
int
0x10
mov
al ,
'e'
int
0x10
mov
al ,
'l'
int
0x10
mov
al ,
'l'
int
0x10
mov
al ,
'o'
int
0x10
jmp
$
;
Jump
to the
current
address
( i.e. forever ) .
;
; Padding and magic BIOS number.
;
times 510
-( $ - $$ ) db 0 ;
Pad
the
boot sector
out
with
zeros
dw 0 xaa55
Last
two
bytes form
the
magic
number ,
e9
fd
ff
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
*
00
00
00
00
00
00
00
00
00
00
00
00
00
00
55
aa
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.