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}
[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.
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,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.
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.
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.
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.
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.
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.
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.
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.
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