COMP9242 Project: SOS [an error occurred while processing this directive] Project: A Simple Operating System Overview 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. Processes 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 The SOS 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 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. 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 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 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). You now have a quite respectable little operating system -- fair reason to feel proud about your achievement! Go GPL it and change the world :-) Bonus Features (aka Stuff for Masochists) The following features, if demonstrated and submitted together with your Milestone 8, will give bonus marks. Shared memory 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 masochists. 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. Super Bonus: Windows-2000-compatible OS. 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. Implementation Shortcuts 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! 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 I/O blocking. 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. I repeat: Make it work before adding whistles and bells. This also applies to bonus items. 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. Good Luck! Note: Recent changes are marked red, while other changes made since the original release are in this colour. Last modified: 20 Aug 2002. [an error occurred while processing this directive]
