Project: A Simple Operating System
The aim of the assignment is to implement a Simple Operating System (SOS)
server on top of the L4 micro-kernel. The SOS server is expected provide
a specified system call interface to its clients.
SOS features the following:
demand-paged virtual memory,
a network file system,
a terminal device for input and output to the serial port,
a high-resolution timer,
primitives to read and write files and directory entries,
primitives to create and delete processes from memory images in the file
system and to obtain process status information.
Network A user-level network driver,
consisting of an ethernet driver and a UDP stack, will be
provided. SOS will use this to access a Unix file system maintained
on a remote server.
Virtual Memory The
virtual memory system implements demand-paging using an LRU
approximation based on a single reference bit (second-chance
algorithm). Paging is done across the the network to the Unix file server.
File System The SOS file system features a flat directory
structure, containing files and the terminal device
``console''. Files have attributes (like size, creation time,
permissions) that can be accessed. All I/O primitives provided by SOS
are synchronous (blocking), with the exception of console reads (see below).
Terminal I/O Terminal I/O
is to be achieved using file-system primitives on console. The
console is a multiple writer, single reader device, i.e., more
that one process can concurrently open the device for writing, but only
one process can open the device for reading.
Reading console is a non-blocking operation: a read operation
returns, without waiting, up to the number of bytes presently available,
possibly zero. The reader client is expected to poll for input.
High-Resolution Timer SOS has a high-resolution timer feature,
usable for benchmarking etc. This is based on a clock chip on the U4600
board which has a 50MHz resolution. You will write a user-level driver
for that clock chip to provide the SOS timing service.
SOS processes are single threaded and run in their own address space independent
of any other running processes. They can be created from any of the executable
files in the file system. These are expected to be standard ELF files
as produced by the cross compiler. The files can be run more than once
and more than one can run concurrently.
Processes can be created and deleted by any other process. Processes
that attempt to access memory they do not have access to, or take an exception,
are deleted by SOS.
Startup SOS is running as
an ``initial server'' under L4, i.e., it is started up by once L4 has booted up. Similarly, SOS
must start up at least one user task once it has initialised
itself. That initial user task is defined as the first executable
file in the boot image which is not an initial server. All other
user tasks will be started from executables contained in the file system.
system calls are described in detail in the header file sos.h.
You are expected to write a C library that provides the described
function calls and interfaces with your operating system to provide the
correct functionality. You must conform to the documented
interface, or at least be compatible with it if you choose to add your
We will test your system by linking our test code, which will use the
interface, to your C library. For your own testing, and to demonstrate
further the expected use of the system call, you may find the SOS Shell (sosh) useful, which
will be supplied shortly. This can be run as an initial user program and
can be used to test out your system calls. However, you will have to
have at least the file system essentially working before you can run
Implement a system compatible to Windows-NT and demonstrate superior
performance compared to Microsoft's version. You'll be guaranteed a HD
grade for the subject.
Remember, you have very limited debugging facilities. On the OS side you
can use the kprintf routine provided with the pager example. On the client side you will
initially have to use a variant of the ttyout server used in
that example. However, it is not easy to use this all the time,
particularly if your client code never gets far enough to send a message
to the tty server.
The Makefile features two special targets: caching
and noncaching. This allows you to switch between a ``caching''
and a ``non-caching'' system. The former makes use of the CPU caches,
while the latter bypasses them. A non-caching system will run about an
order of magnitude slower than a caching system, hence your final
submission is expected to work with caching enabled. Caching can change
the semantics of memory accesses for two reasons: devices registers are
not cached, and arbitrary page mappings can lead to cache
incoherencies. Therefore a non-caching system may be advantageous for
Implement clock driver.
Write a driver for the timer functions of the GT chip, according to the
Implement a memory manager.
This will first set up a frame table and then attempt to request all
frames which are not in the L4 reserved areas from . It will also reserve some memory for SOS'
own use (e.g. for the frame table). It will provide a memory allocator
which returns a previously unallocated frame.
Do not worry at this stage about what exactly needs to be in the frame
table, you can extend your data structures later on.
Implement a pager,
based on the memory manager (and the sample pager).
In its initial form, the pager will simply map pages containing the boot
image when requested by the client process. Other page faults will be
satisfied by allocating a new frame and mapping it to the client
process. This allows execution of user processes ``in place'', i.e. from
the boot image. Note that in general a program can only be executed
in-place once, afterwards global variables may have incorrect
This constitutes Milestone 1,
due Week 4. You will demonstrate that you can execute a program
in-place, but with a high stack pointer (> 0x800000) using the above memory
Start off by setting and reading the appropriate GT device registers,
setting timers and receiving interrupts.
This constitutes Milestone 2,
due Week 5. You will demonstrate a rudimentary driver (code
inspection) and show (test code producing appropriate messages) that you
can initialise and set the clock, and can receive interrupts from the GT
Design an RPC protocol and complete the clock driver.
Design the RCP protocol for the system call interface. Implement the
client side of the system call interface based on that RPC
protocol. Implement system-side server code which accepts IPC requests
and replies to them, after printing (kprintf) a ``not yet
implemented'' message, except for the time() function,
which should work at this stage. Test your interface with a simple
This constitutes Milestone
3, due Week 6. You will demonstrate (code inspection) and
explain the RPC protocol and parameter marshaling. You will also demonstrate
(code inspection and test code) the operation of the complete timer
It is advisable that you write your interface up at this stage, as it
will be required as part of the system documentation later on.
Implement network communication.
Write an interface to the supplied network driver, which sends packages of up to
4kB across the ethernet. Write a UNIX-side interface which dumps network
packets into a file, and sends the contents of a file across the network
to the u4600.
This constitutes Milestone 4, due Week 7. You
will demonstrate the operation of your network interface by having the
u4600 operate as loop-back device, which reads packets from the network,
sends them right back, and occasionally prints a packet count and
checksum to the serial port. The Unix-side code should check the
received packets for correctness and also display packet counts and
checksums for verification.
Implement demand paging.
Implement on the Unix host the ability to read and write random blocks
of a swap file. Use this as the backing store for your
operating system. Implement the second-chance page-replacement
algorithm. Test your paging system by reducing the amount of ``free''
RAM to a few frames, and run a user program which accesses more frames
than are available.
Note that the MIPS does not feature hardware-maintained
reference and dirty bits, you'll need to do this in software! (How?)
This constitutes Milestone 5,
due Week 8. You will explain the implementation of your
demand-paging system and demonstrate its operation by running a process
which is bigger than the available memory.
Implement the file system.
You will need to maintain file descriptors containing a present read
position in the file. This requires some minimal process descriptor
block (PCB) data structure. Again, don't worry at this stage about the
exact final contents of the PCB, you can extend them later on. You may
wish to initially only deal with a single client process, data on which
is kept in a single PCB variable. This avoids dealing with process IDs for
the time being.
The low-level file system is implemented by the Unix file system on
your host machine. The Unix side of your network code needs to interface
to the Unix file system to allow SOS on the u4600 to create and access
Your Unix file server process should make accessible to SOS regular
files in its working directory, and should allow SOS to create new files
in that directory. You can ignore everything in the Unix working
directory which is not a plain file, in particular subdirectories.
Paging I/O should go to a single file, called swap, in the
directory. SOS should, when booting, create that file if it does not
exist already, and ignore any previous content if it does.
SOS must (eventually) be able to execute any executable file (of the
correct format) in the Unix directory. Hence, once the file system is
fully operational, there is no longer a need for your boot image to
contain more than L4, device drivers, and the SOS binary. Everything
else should be executed from the file system.
One exception is the file console, which represents the
serial port, and has therefore no equivalent on the Unix side. Handling
of console I/O can be done by special code in your file
system. Console output is easy, you've essentially done it already. For
console reads you'll need a thread which registers itself as the console
reader and then waits for bytes from the console which are stored in a
fixed-size buffer. The file system will read the input data from that
buffer. Make sure you are using concurrency control on that buffer!
Implement and test the system calls to open, read and close
files. Create a few (small to medium size) data files in your Unix
directory, so you can open and list them. Implement file creation and
This constitutes Milestone 6, due
Week 9. You will demonstrate (by running a program such as
sosh ) that your SOS applications can read and write any file in
the Unix server's directory, and can use the console file. You
are, at this stage, not yet required to be able to execute files across
the network, you can still package all executables into the boot
image. You will explain data structures and algorithms. Again, in your
own interest, write your documentation as you go along.
Implement process management.
Write a process allocator which first donates all available L4 tasks to
itself, and then maintains an array of PCBs from which new processes can
be allocated. Implement the process_create() system call. All
child processes may at this stage be running in-place. Implement the
remaining process-related system calls.
This constitutes Milestone 7,
due Week 10. You will demonstrate (by running a sosh)
that your system works as long as each program is executed at most once.
Be prepared to explain data structures and algorithms.
Congratulations, you have now written a rudimentary operating
This is at least as far as you should get by the end of
session. You will get at least a passing mark for the project if
your system for the most part works as required by this Milestone (minus
some less important things, like process_delete), and you
deliver some minimum documentation. You may skip the reminder of the
implementation if you are running out of time (at the expense of losing
marks, of course.)
Implement full process, memory, and I/O management.
This requires that when creating a process, its code and data section
are loaded from the file system into some free memory, and a page table
is set up which will satisfy page faults to the text and data sections
from the correct frames. The OS's loader must interpret the contents of
the executable file (in ELF format). Sample
code for reading ELF files is provided.
Note: You can specify an explicit (hexadecimal) starting
address for the text segment using the -T linker option,
e.g. -T 0x1000. The linker will allocate the text segment at
the smallest correctly aligned address not less than the specified
address. The data segment will, by default, be allocated so that it
starts in a page greater than the last text page. The ELF linker will
allocate text and data segments such that their virtual page offsets are
the same as the physical offsets in the object file, which supports
efficient paging. (But note that the end of text and the beginning of
data may share the same physical page block in the executable file.)
In your own interest, do not map the text section to page
zero! If you make sure that page zero needs never be mapped, you can
catch most cases of use of uninitialised pointers -- a
great help in debugging!
Instead of copying the whole image on process creation, you may choose
to copy on demand at page-fault time (which is, of course, how a decent
virtual memory system does it).
We also expect your system to perform all I/O asynchronously at this
stage. In other words, you system must not block waiting on completion
of file system or paging I/O, but should be able to run any process that
is ready while other processes are blocked on I/O completion.
Finally, SOS's sleep() system call must use your
device driver and interrupt handler for the GT chip.
This constitutes Milestone 8, due Week 11. You
will demonstrate (by running a sosh ) that your system works
even with repeated and concurrent executions, and that you can execute
every file (of the right contents) from your Unix directory.
Complete the system documentation.
The Final Milestone is the
delivery of your system documentation, due Week 12. It will
describe your RPC interface and the internal structure of your operating
system well enough that another student in your class could take the
project over at this stage and debug or extend your system. Be sure to
point out known limitations. Document important assumptions (like
protocols used for concurrency control of system data structures, your
You now have a fairly respectable little operating system
-- fair reason to feel proud about your achievement!
Bonus Features (aka Stuff for Masochists)
The following features, if demonstrated and submitted together with
your Milestone 8, will give bonus marks.
Implement the shared memory via the share_vm()
system call and demonstrate operation with some application which has
processes communicating via shared memory.
Clock driver loaded from file system
Rather than loading your clock driver from the boot image, load it from
the file system and run it as a separate L4 task.
File system caching
Reserve a part of RAM as a file system cache. Implement caching of
directory information and file data, as well as read-ahead, to improve
file system performance.
Dynamic file system (only valid with full file system caching).
Have your SOS file system behave correctly even if files are
added/removed in the Unix file system while your SOS is running. Do this
without significantly degrading performance.
Paging OS data structures
- Don't go wild on this. I'll look at any OS that pages itself with
suspicion, it's likely that this is to cover up some problem.
What can make sense to page is page tables and PCBs of blocked
processes (essentially swapping a process). Something for REAL
Implement NFS protocol
- Rather than talking to your own (primitive) Unix file system
interface, implement the NFS protocol and talk to a proper NFS server on
the Unix side. We'll set up an NFS server on sniffy if someone
is going to tackle this.
Here is an incomplete list of simplifications you may choose. Obviously,
omitting features required above will cost you marks, but better a
slightly restricted system that is working than a system that is not
good for anything. I strongly recommend that you implement the
simpler versions first before tacking any more sophisticated stuff.
Some students have in the past been lost in complexity by trying to
tackle too much at once!
I repeat: Make it work before adding whistles and bells. This
also applies to bonus items.
- Synchronous I/O
- There are two parts of your system which perform disk I/O: the file
system and the paging system. Ideally, all I/O should be asynchronous so
fault on a non-resident page or a file I/O request does not block the
system. However, you may want to keep things simple and make all network
- Small address spaces
Ideally, 64-bit address spaces, or at least the 40-bit address spaces
actually supported by the hardware, will be supported by your operating
system, but you may chose to support less. This has implications on your
page table structure. I do expect you to support a 31-bit address space
at the least.
- Fewer system calls
You may want to omit some system calls, which are not essential for a
``demonstration prototype''. This includes process and file deletion,
and implementing the sleep() system call using L4 timeouts.
Final code submission
By the end of Week 11 you are to submit electronically the final
version of your code according to the final
code submission guidelines we will supply. You will not be awarded
any marks for Milestone 8 until the
electronic submission has been received.
Note: Recent changes are marked red,
while other changes made since the original release are in this colour.
School of Computer Science and Engineering,
University of New South Wales
This page is maintained by
Last modified: Tuesday, 24-Oct-2000 14:47:24 AEDT