OS Modules List & Grading Algorithm

(Original) Term Project Grading Algorithm

A comprehensive operating system is too big for one person to implement alone in one semester. However, a simple system is a reasonable term project for one person working diligently, as would also be the integration of a much more complex system plus implementation of one or more components of it. Either of these two options would adequately expose the student to the necessary design principles and implementation trade-offs, and exercise the thinking processes required to demonstrate a thorough understanding of the course material.

The minimal acceptable operating system turned in for this course will run two or more of the supplied application programs concurrently, with their output orderly delivered to the simulated printer (file). This requires implementation at a certain level of process and memory management, a minimal file system, and proper I/O handling.  An asterisk* marks the minimum modules necessary for this level of performance.

A more complete system will implement a graphical user interface, provide reasonable security against malicious software (also to be supplied) and deliver a high system throughput with minimal operator involvement.

This is a senior-level course. Students are expected to exercise initiative and discernment in choosing which features to include and which modules to implement to attain their chosen objectives. Students are also responsible for getting a timely start on their development, so that projects dependent on their code will be operational by the end of the semester, and for choosing collaboration partners (if any) consistent with their own performance objectives.

{Additional details on each module will be forthcoming upon request}

Modules (Details below)

[50]  Net minimal points*

I/O Drivers

[01] Synchronous disk driver (provided) *
[05]   Simple hard disk driver  *
[15]   Async floppy & hard disk driver
[20]   Buffered disk driver (cache)
[01] Synchronous printer driver (to be provided) *
[08]   Async printer driver
[01] Monospace screen text driver (provided) *
[10]   Proportional screen text with font selection
[01] Synchronous keyboard driver (provided) *
[08]   Async keyboard driver
[08] Mouse driver
[08] Clock driver


[01] Interrupt handling (provided) *
[10] Program startup & shutdown *
[10] Coop task manager  *
[15]   Pre-emptive process manager
[06] Prioritized processes
[06] User-level threads
[15] Event management
[08] Inter-process messages
[07] Resource management
[07] Deadlock mitigation
[05] Processor utilization accounting

Memory Management

[01] Unmapped (provided) *
[10]   First-fit/paged
[20]   Disk-based virtual memory

File System

[01] Flat sequential (provided) *
[10] Allocation blocks
[10] Simple hierarchical directories
[08] Links
[07] File-level locks
[15] Unix-like file permissions
[10] Unix-like pipes


[01] None (console text only) *
[15]   Icon-based shell
[15] Simple (text) window manager
[10] Pull-down menus
[15] Event management-
[10] 2-click job invocation
[20] DragonDrop
[10] Proportional screen text with font selection-
[05] Font manager


[01] None *
[10] Password-protected login
[15] Unix-like file permissions-


[05] Batch job control *
[10] Program startup & shutdown-*
[10] Text-based shell-
[01] File-copy utility (provided) *
[10] 2-click job invocation-


[21]  Net minimal points*

[10] Runs programs concurrently *
[08] Successfully runs all supplied application programs *
[09]   Partially operational, but fails to run all applications concurrently
[05]   Non-functional, but appears to be reasonably complete and a good design
[02]   Non-functional with serious design flaws
[01]   Non-functional and incomplete
[01] Command line interface *
[10]   Modern (GUI) user interface
[02] Minimal user operating manual, listing commands and options *
[01] User documentation, accurately describing how to use features, {each major element}
[03] API and descriptive (programmer/user) documentation, {each (sharable) module}

[10] At least 95% of best throughput in class
[10] Difficulty adjustment (up to 10 points), if some module turns out to be too hard

The point scores for modules represent their estimated relative implementation effort and/or learning value, estimated at approximately one hour/point on the average. If any module is taking more than twice as many hours to complete as its point value, something is wrong and you should get help. Thatís what office hours are for.

The point scores for modules will be degraded by 10% for minor bugs, up to 30% for major bugs but functional, 50% if they are complete but non-functional, and proportionately more if they are incomplete.

A perfect score for any one studentís delivered system is 100 points. The minimal but completely funtional solo system (asterisk* modules) is 71 points, which is a low C grade, assuming comparable performance in the rest of the classwork. A student electing to go it alone should plan on implementing several additional modules and/or higher performance levels to earn an A. Note that indented items represent higher (or lower) performance levels of the unindented modules immediately preceding, so their points are instead of, rather than in addition to the replaced modules.

The maximum number of points that can be earned on a solo project implementation is somewhat greater than 450, reflecting the fact that no student is expected to fully implement all the modules at their maximum level, and no system is expected to include all performance levels of the same function.

Open Source

In the Open Source option, a student may elect to make available to other students an advanced version of a module, in exchange for comparable modules implemented by other contributors to the open source pool. Each student receives full credit for all modules personally implemented, plus 10% credit for each student who uses your module without modification, or 5% if they need to modify it. Be careful to write robust and portable code that will not need modification to make work in their system. Please sign your modules: unattributed shared code will be presumed plagiarized from some third party and given no credit at all. The advantage of using shared code is the greater functionality it affords; the only disadvantage is that you get no points for writing that part. The integration points are not sharable.

For example, suppose five students each built a system consisting of the minimum (*) levels of all modules, except that:

One student wrote and shared async drivers for printer and mouse,
One student wrote and shared async drivers for keyboard and clock,
One student wrote and shared the event manager,
One student wrote and shared a text window manager, and
One student wrote and shared an icon shell.
Each student has earned 66 points from the minimal modules implemented, plus the 15 points shared, plus the 9 extra points for having a GUI user interface. Each earns 6 additional points (15 x 4 x 10%) from sharing, for a total of 90 points each. Other combinations may give you a shot at the best-performance points.

There is a disadvantage to depending on shared code: if the other implementors do not deliver on time, or if it doesnít work properly in your system, you are penalized for the non-functionality. You might consider having a fall-back plan in place for such eventualities.

Module Details

Disk Driver & File System

The virtual hard disk and virtual floppy drive share a single controller. These disks are preformatted with 256-byte sectors, so all your driver needs to do is define a directory structure, create named files in that directory structure, and transfer the data. The MiniOS sample code includes a simple sequential allocation scheme and a single directory accomodating up to 7 (expandable but not expanded to 31) files of maximum length 65534 bytes, in which only one new file can be open at a time, and at most 3 files open simultaneously. It also uses polled I/O transfer (not interrupts), so sector seek time is simply wasted. This is barely adequate for a minimal implementation, but you can do much better.

You may convert the driver to be interrupt-driven, where the waiting process is blocked until the transfer is completed. This requires integrating the disk driver into the Process Manager.

You can add a block allocation scheme to the file system, so that more than one new file can be open at the same time, and pre-existing files can be extended indefinitely. This requires that you maintain a table of available blocks (typically a clump of several sectors) or extents, from which the file system picks out an available (preferably nearby) block for extending a file as it grows. The block allocation table is usually stored on the disk as a bitmap, one bit for each allocated block. It is kept in memory for usage, and written back to the disk from time to time. If your system crashes with the block table not written out, you will need to detect that and possibly implement some kind of recovery/verification routine. You probably also need to use a better way to define the file size than a single 2-byte number, so that files can actually exceed 64K in size.

The MiniOS sample allows for a single directory at the front of the volume. A much better structure involves a hierarchical directory tree. To do this, you need to flag directory files (they are just files) in their parent directories as directories, so that your file system knows not to treat them as data files. You might replaced the fixed-size directory in the sample code with a link to the root directory, which can then be located anywhere on the disk. In any case you should still be prepared to deal with floppy disks as formatted by the MakeFloppy button, since that is how you will get your compiled code.

Other interesting features you might consider adding to your file system are symbolic links (multiple directory entries to the same data, which requires that you track how many entries point to this one file), file- and block-level locks so that multiple programs accessing the same file data can coexist properly, and unix-like permissions. Unix achieves their permissions control by maintaining a second level of (hidden) directory, called "I-nodes" where the actual file locations and permissions (but no names) are stored; files names are in the visible directories. Thus changing the permissions in one directory entry changes it for everybody. Deleting one name for a file does not delete the file until all the links have been deleted.

The available memory in SandBox is relatively small, so there may not be much sense in implementing a disk cache, but you can try it. The idea is to read a whole track of data at once on the assumption that future calls will need it, thus saving on the initial seek time for successive sectors. Whether this actually save much time in this virtual machine, or if it takes too much memory, thereby forcing processes to thrash, is not known at this time.

Related to the file system, but not necessarily using disk space is the unix concept of Pipes. A pipe looks like a file to the application program, but really consists of nothing more than a queue between sending and receiving processes, which are controlled by semaphores. The buffer could be as small as a single byte or word, but a larger buffer will reduce thrashing.

Printer Driver

The printer is fairly simple-minded hardware. A semi-synchronous driver is not significantly harder than a simple screen driver. Interrupts only occur at line ends, so the driver should block the client process only when printing a return (or newline) character, then resume it when the line completes. A fully synchronous driver can be simulated by using the interrupt driver to clear a "print busy" flag that is set when outputting the line end, and backing up the client process whenever it tries to print with that flag in the busy state.

Screen Text Driver

The MiniOS has sample code showing how to do a simple (5x7) monospace font. This is good enough for your minimal implementation. For better appearance you can add a proportional font capability, and different font sizes. Fonts taller than 16 pixels require a double pass through the Video hardware text generator; this is not worth the trouble for this exercise. Proportional fonts will need to store with the pixels a character cell width for each character, and possibly also an offset where each chacter's pixels start (you can do it in one extra table by calculating the character cell width from the difference between offsets). Building font tables can be very time-consuming; you might consider doing just one or two abbreviated fonts to prove capability. There is no requirement that you do font orientations other than normal Roman left-to-right. Rotated text is cute, but messy.

Keyboard Driver

The MiniOS has sample code showing how to do a simple interrupt-driven keyboard driver that holds up the computer while waiting for the input line to finish, and discards input until the client has accepted the previous line. This is good enough for a minimal implementation. You can use a separate process to queue keys in a circular buffer, and to signal a waiting process upon line completion (or on key arrival, if it's waiting for a single keystroke).

Mouse Driver

There is no sample code for a mouse driver, but the implementation should be pretty simple. The current mouse coordinates and button state are tracked in real time by the virtual hardware. Since there are no interrupts associated with the mouse, your driver must take time during the clock interrupt to monitor these. Fortunately, you do not need to move a cursor around the screen, because this is done by the host operating system. If you are properly handling events, then you will need to save the previous values for H, V, and button, so to detect a new state that may generate an event.

Clock Driver

The MiniOS has sample code showing how to handle a clock interrupt, but it does not do anything with it. Your code should use this interrupt to track the mouse (if you are doing that), and to monitor the execution time of the current process. If you implement timer events, this driver must also process them, or aty least wake up a user-level process to do the job.


The MiniOS has sample code showing how to minimally handle three kinds of interrupts. Your system needs to fill in the rest. Interrupts can happen at any time, so it is important to get the process management right here, so that they are not disable for too long. If your system spends too much time with interrupts disabled, you will lose interrupts and data will get lost. That's a bug. If you are not reasonably careful with thread management, you might knock out an interrupt handler entirely; that's a bigger bug.

Program Startup

The OSL compiler generates code that begins execution with "function #0", which behaves like a real function, executing an Enter instruction, initializing the global variables, calling the main(), and then finally leaving by means of an Exit. You should make sure that your system sets up the four registers correctly, typically by storing values in the new program's stack frame space, then doing a CoCall to get it going. Unlike the MiniOS, your client processes normally will not share the code and global spaces with the system, so you can set them up with numbers appropriate to where you loaded the program in memory. Also unlike the MiniOS, you should arrange for the final Exit to return to your OS, possibly by means of a SysCall.

Program Termination

The MiniOS sample code main() simply runs to completion then exits to address 0000, which is a halt. Your system probably needs to be able to kill programs that refuse to quit, which you could do by forcing their PC to point to an Exit SysCall. This system call should de-allocate their memory and close any open files.

Process Mamagement

The simplest form of process manager requires the application program to yield control of the CPU to another task. Because so much of the process management job is integrated into the hardware, you should be able to implement a complete pre-emptive manager, which allocates a certain amount (quantum) of time for a given process, then swaps it out for another process when it exceeds that time and there is another process ready.

A more complex arrangement sets different priorities for different processes, so that all processes of the highest priority execute in preference to processes of lower priority. For the highest levels of priority, such as system services, you might want to simply starve the lower priorities; this assumes that you are designing these higher priority processes to politely and timely block themselves. Where the user is permitted to set priority, a more equitable method gives one processing quantum to the next lower priority level for each n quanta given to the higher priority, and recursively down through the implemented levels. You can dynamically adjust the priority of a process even if the user is not given direct control, by raising the priority of processes that block themselves on I/O (or graciously yield) before their time quantum is up, and lowering it on processes that consistently outlast their time quantum. This way I/O-bound processes won't be starved out by compute-bound processes, on the assumption that they will get in and get out quickly.

Threads are nothing more than multiple processes within a single program. To support them in your OS, you need to provide system calls for starting up a new process within the user code space, perhaps working like the Posix fork() function. Of course you also need to support semaphores or monitors so that these threads can cooperate without stepping on each other.

Events are nothing more than messages sent by the system to a process that is prepared to receive them. Inter-process messages are something like pipes, but more structured. To implement them you will need to provide system calls for sending and receiving messages. A minimal system will generate events for mouse clicks and keystrokes, and probably also for losing and regaining focus. Other useful events include periodic idle events, and mouse tracking events like enter(a region) and leave it, used for roll-over management. Tracking the mouse position with respect to regions on the screen requires additional system calls to register these regions and associate them with particular events.

There are three ways to implement an event-driven system. When you have an OOPS (object-oriented) system, the system can provide an interface or abstract class containing the methods to respond to each possible event, and each program can register objects subclassed from that basis to catch them. Alternatively, the client programs could register their own event handlers as procedure pointers. Because OSL is not OOPS at this time, and because it does not support procedure pointers, you must use the other (original) method for event handling, which is make a system call to request a generic event record, then decode it and dispatch the event using a switch statement. This can be simplified for the client somewhat if the system call affords a second parameter with a bit map (the sum of powers of 2) designating which events it is prepared to accept. For example, a MouseDown event might be 1, MouseUp 2, KeyDown 4, KeyUp 8, window Activate and Deactivate 16 and 32 respectively, and so on. The program able to accept only keystrokes and mouse clicks would put forth a mask of 5 (=1+4). It's usually better (and more in keeping with the philosophy of the GUI) for the client program to just accept everything and dispatch accordingly.

Resource Management

A key duty of any operating system is to manage the allocation of various hardware and software resources among its processes. Memory management iand screen management are special cases with their own topics, but you must also choose an appropriate strategy for allocating the printer and floppy disk to their various clients in a non-overlaping way, and perhaps also to schedule the disk access for improved performance. There are not a lot of resources to manage.

Memory Manager

Memory management happens in two stages, which can be coordinated or else run entirely independently. Nearest to the heart of the OS is the allocation of physical memory pages to running processes. If you are doing unmapped memory as in MiniOS, this can be ignored, but you will be limited in how big a program you can run, and how many you can run at one time.

Using the MMU hardware doubles the available physical memory you can use to run programs. Because this is a paged memory system, there is no problem allocating pages to processes so long as there is memory available, although the first quadrant is more valuable than the other three quadrants, due to the need to locate semaphores and MMU tables there.

With disk-based Virtual Memory, the only limitation is how many process info blocks (PIBs) you can pack into the first quadrant of real memory. There is no obligation to allocate a whole page to each process or program; it might be sufficient to allocate 80 bytes for each separate program, plus maybe 16 bytes for each additional thread PIB in the same program (using a shared MMU table). Interrupt drivers also need their code and data (stack) space in the first or last quadrants, but their requirements can be kept minimal. The rest of real memory can be allocated dynamically to whatever processes need it. If you do this, then swap-file allocation must also be considered, just as if it were real memory (see Heap Allocation below), except that you are dealing with a much larger address space, big enough to support all possible simultaneously active programs. Alternatively, you can allocate a single 64K swap file for each active program, and pass the burden of page allocation off to the file manager.

Heap Allocation. Within each process, you must also respond to requests for memory allocation (new), by allocating memory within the process' heap space. This may be coordinated with the page allocation, or it can completely ignore page alocation and just allocate the next block available in whatever allocation scheme is being used for that program in its address space, then let the MMU interrupt assign it to real memory as actually used.


Philosophy The most important thing to understand in the modern event-driven user interface is that the apparent locus of control is vested in the user. This does not, as is often supposed, make errors more likely; rather, the correct implementation prevents errors without depriving the user of a full range of options that are error-free. Errors that only the user can detect are not preventable, but the well-designed system makes their correction or repair easy. We say "apparent" locus of control, because of course the computer is always under the full control of the system software; however the user can be made to feel more in control or less, depending on the varieties of choices and the ways they are offered.

When the users are narrowly guided through a complex sequence of screens in a particular sequence, they feel that the computer is in control. If instead, all of the options are visible all of the time, but possibly disabled (grayed out), then they feel more in charge. The only real difference is how much the user sees of the total set of choices, not necessarily how many of them are operable. However, with a little extra programming effort, the software can make alternative sequences of user steps equally viable. For example, an income tax program can force the user to enter the data in a particular order to make the programmer's job easier; alternatively, the software can accept the data in any order the user chooses, and then constantly recalculate the results on the basis of available data. If some calculation is not possible until the user has selected an input value (for example, a non-zero divisor), then the program can display a colored (or otherwise distinctive) notice that there is missing data in place of the calculated result. Clicking on the notice could then take the user to the place where it needs to be supplied, but if the user chooses to do some other task first, that should be possible.

The essense of the GUI, therefore, is not so much that it is graphical, but that the full panoply of user choices are visible and available for selection, insofar as that makes sense. It may be perfectly reasonable to prevent the user from choosing an action that depends on data not yet provided. In that case the action button or menu should be visibly disabled (but not invisible), and a notice identifying the missing data posted where the user can see it -- either as a popup "tool-tip" activated by rollover when the user approaches the button or menu, or else some kind of message box triggered by the (possibly repeated) attempt to do the disabled action. Users usually can figure out that the computer won't let them do something, and often (but not always) they can figure out why. It is not necessary to give them information they already have. This is why there is usually a delay of one or more seconds before tool-tips pop up.

Implementing a Graphical User Interface requires management of the screen real estate, plus directing the user interface event stream to the appropriate window process(es). The programs offered to run in SandBox are not GUI-aware, so they are not capable of refreshing their own screen data. Ordinarily, event-driven software expects to receive Redraw events with the other events, and responds to them by redrawing its own window(s). This kind of software is much harder to write and get right. The best you will be able to do with what you have is a simple shell around each program that stores the displayed text and redraws it.

Window refresh aside, you can still implement a window manager that clips each (or wraps) program's text to its own text window. This means that the screen text output calls must be aware of which program is running and where its window is located on the screen, so to offset its text drawing to be relative to the window coordinates. You could at the same time capture and save the output text in case it is needed for refresh.

Menus can be attached to each program window, or else globally placed at the top (as in Macintosh) or the bottom (like the Windows taskbar). Again, unless you have a GUI-aware program, it will not be able to manage its own menus, limiting you to a few simple menu items like "Quit". Note that when the user clicks on a menu label, the popup menu items are something like a little window widget that partially obscures the window(s) behind it. You could cause a refresh event on that area when the menu is dismissed, provided that you have some way to persuade each program to refresh its own windows. Because the SandBox hardware does not give you access to the pixels on screen, you cannot do as the original Macintosh menus, saving the pixels behind a menu and restoring them when it is dismissed. Sorry about that.

Somewhat more productively for this exercise, you can implement icons representing files in windows representing directories. When the user 2-clicks an icon, if it's a document file, find its owner program, then open the program. It's somewhat simpler (and perfectly adequate for this exercise) to open only executable icons this way.

Although the programs are not particularly event-aware, you can certainly attach an event queue to each program, so to capture (mouse clicks and) keystrokes intended for that program and only then accumulate them into that programs ".K" file input. This focus management is an important part of event management, and counts as a large part of doing a GUI in this context.

Drag'n'Drop is a wonderfully easy way for the user to transfer data between structured windows. However, it obeys the Law of Conservation of Complexity: it's pretty tricky to implement. Essentially you need event- and GUI- and drag-aware programs. The sending program accepts mouse clicks and/or drags to select some data to send, then builds a prescribed data package when the user drags the mouse. The receiving program or window must accept the drag-enter event, and use it to query the data package to see if the data type is acceptable, and if so, to highlight the destination structures as the mouse passes over them. When the mouse button is released, the system sends the receiving program a drop event, whereupon it accesses the data package to extract the data and insert it into its own window and file structures. Dragging a package into the trash can triggers a special event to the sending program, to delete the original data. It is customary to build a transient visual representation of the data in the package, and to have that image follow the mouse around. There's a lot here, folks.

Implementing a proportional screen font a a little bit easier, and somewhat independent of the other GUI issues. The supplied font capability in MiniOS can calculate where each character needs to be displayed, based on the fixed size of the previous character. To do a proportional font requires some kind of image editing tool (I have used ASCII graphics for this in the past, one pixel per character) to visually create the font, then another program to collect the pixels into bits in the proper format. For the MiniOS font, I edited the font in a Macintosh font-editing tool, then printed a complete alphabet onto a large blank window, which I captured the image of in "RAW" graphics mode, then I wrote a HyperCard program (something like Visual Basic or Perl) to re-arrange the bits and output the bytes as text. For a proportional font, you would also need your tool to capture the character boundaries so to measure the individual character widths, then build a width and offset table from which you can construct the character cell in your DrawChar() subroutine. This is doable, but not to be taken lightly. You can implement font selection in a menu (if you do menus), or by double-clicking its icon (if you do icons), or by means of a command line tool. I would recommend you put each font with its metrics in a formatted file, one of which is deemed by the system to be active and loaded into memory.


Realistically, build a single-user system. Making your system robust against malicious programs is not too hard, but probably should be part of a comprehensive security plan, including file protections. Even a single-user system can have a user-setable "Locked" bit associated with each file, so that it cannot be written nor deleted if the bit is set. Similarly, giving each user program its own address space (using the MMU) prevents that program from accidentally or purposefully trashing the system. A rogue program can still attempt to trash the file system by rewriting system files, if you let it, but it's pretty hard to write such a program (meaning: I won't try, unless somebody tells me they want to build a secure system).

If you want to do something multi-user, then you will need to build a login shell capable of asking for a user name and password. and keep only encrypted passwords in a disk file, then have ownership and access rights associated at least with every directory, and possibly with every file.

Job Control

The supplied MiniOS has a tiny (one-line) batch system built in. A more respectable system would have some kind of shell program that could read a (disk) text file and parse out command lines, so to run programs in true batch mode.

If you were doing a graphical interface, then the shell needs to be able to track the mouse and know when it clicks on an icon (maintain in the directory or elsewhere an x-y coordinate of the icon in its window (the screen itself can be considered another window), plus the coordinates of the window frame relative to the screen, so to calculate which icon the user clicked on.

Double-clicking is accomplished by recording the time and location of a click, then comparing it to the previous recorded click to see if it's close enough both temporally (perhaps a second or half-second, or an adjustable amount), and spacially (typically 2 or 3 pixels in any direction).

If you want to open subshells, unix-style, then your system should have system calls for starting up a program. The easiest fracture plane for this boundary is to give the system a command line (typically the name of a program) to start the program. The system can then call on its own utilities to allocate memory, set up a process info block, and get it started. If that program is a shell program, then it can proceed to start programs under its own authority, again by calling the same system calls.

Killing It. One of the services your system needs to provide is the ability to terminate a program. It might be convenient to offer a system call to get the current processes (or better, the nth process from the list), then another call to alter that program's process state: changing its priority (if you can), or suspending it (block it on a semaphore that nobody ever signals), or outright kill. If it's a shell with subprocesses, you need to track that in its PIB, so to kill its subprocesses too.

A simple way to kill a single program is to capture control-C in the Keyboard input driver, and have it do the dirty work. A better long-term solution is to have control-Z automatically switch you back into your shell program, so it can take a command line to kill a process. This means that the keyboard interrupt driver needs to know who is the shell, and how to (context switch) wake it up, probably by means of a subroutine call.

Rev. 2004 April 20