Overview

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

Virtual Memory

File System

Terminal I/O

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

Processes

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

System Calls

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 own features.

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 sosh .

Implementation strategies

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 debugging purposes.

Project Plan

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 values.

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 management.

Implement clock driver.

Write a driver for the timer functions of the GT chip, according to the supplied specification.

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 chip.

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 sub-process.

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 functionality.

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 Unix files.

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 writing.

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 system!

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 network protocol).