Online Tools: "SandBox" Virtual Machine, OS Language Compiler, Download.zip
Other Resources: Exam Review, OS Modules List, Process Manager, MiniOS, File System Design, Understanding Code

Recent Changes
(2004 May 5):  Updated Exam Review for final
(2004 April 20):  Additional comments on GUI philosophy and Event-driven systems.

New Grading Criteria

Midterm exam 15%
Previous assignments 5%
Final exam 20%
"10-page" paper focus on one OS topic (clarity+scope 20, grammar+spell 8, citations+style 2) 30%
Working code in same topic (credible attempt 10, compiles 5, actually runs 10, no serious bugs 5) 30%

Security ____
Memory Allocation Vickie, Jon
Concurrency/Kernel Josh, Lisa
Performance Analysis ____
Virtual Memory Jeremy
File System Pam,Jeff
GUI Matt

Assignments

Due Mar.25: Add to MiniOS (or to your own system) enough code to make the SandBox memory manager hardware work at allocating pages to programs as loaded. Two pathological programs (FormText and Stacker) have been added to the RunThese folder on the G:\ drive so you can test your code. FormText is like TextForm, but it calls the memory allocator a zillion times; Stacker calls itself recursively a zillion times (give it a number like 8 or 9 for worst case; 0 or 1 comes out quickly). Also in the same folder is the current MiniOS source file. It has some MMU test code, which you can look at to see how the MMU works. Give it the command "MMUtest" to turn on the MMU (everything hopefully still runs).Please mark up your listing to show what is your own code, or else turn in an abbreviated listing of only your own code. Please provide evidence that your system actually runs, or else tell me that it does not.

OK, I spent about an hour writing my version of this assignment... then I discovered that you cannot load the MMU address from user mode. Not only is it foolish (your code or stack might suddenly get mapped to some other location), but it turns out the hardware misbehaves. So you need some interrupt-level code to do it, perhaps another SysCall. I used #17:

    case 17:
      MMU.address = mmPEEK(SemSP-8);

About this far into it, I realized that you can fulfill the requirements of the assignment if you successfully run Stacker once, giving it depth n=9. Stacker runs to completion for me with n=9. The MMU has been upgraded to save processor state in I/O registers in case of a double fault (trying to push into non-existing stack space). See the revised SandBox docs.

So what counts as "successfully running Stacker once"? Currently MiniOS does not access the memory space between 08000-17FFF (it needs the MMU to get to it). Load your program in there and run it. Recall that the disk driver in MiniOS does not behave well with the MMU, but you can use it to read the program into a low-memory buffer, then copy the code up to the MMU-accessed space using a while loop. At least that's how I did it. I first tried to modify the disk driver to work with the MMU, but that proved too complex. Almost your whole job is inside LoadProgram. The easy way to access 08000-17FFF there is to make a fake MMU table that maps every page to itself (bytes 0-31 get 128-159, bytes 32-63 get 224-255), but byte 62, which normally points to page 126, you can redirect it to point to your data load space, 1K at a time. There are other more complicated ways to do the same thing.

Here's what you minimally need to modify:

Major revision (70%) of LoadProgram(), to buffer your disk data and copy it into place, and set up PIB
One line added to SwapOut(), to set the MMU.address when you swap processes
Three lines added to DoSysCall(), to implement #17

It appears that a lot of people are really confused about how the MMU hardware works. MMU.address is the real-memory address of a 64-byte (int[32]) page table. Each byte of that table chooses any one of the 127 real-memory pages for that 1K block in its program's address space. Each memory reference in a mapped process consists of 6 bits of page table access (picks one of the 64 page bytes) and 10 bits of offset in that page. If that page does not exist (mapped to page 126) or is not writeable (page table byte is less than 128) when the program sties to store to it, then you get an interrupt, and the whole 16-bit virtual address is stored in MMU.fault. Only the top 6 bits of tha fault address refers to the failed page number, so you probably need to shift the whole address right 10 places (MemMgrTbl+MMU.fault>>10), but if you allocated your table as int[32], then the top five bits index the table, and the next bit selects the high or low byte of it. At interrupt level, it may be easier to just use a byte offset with PEEK and POKE, being careful  to access one location before the actual byte you want, then stripping off and/or preserving the high byte of the 2-byte int that PEEK and POKE work with there, thus:

pageAd = PEEK(CurPro+4)+((MMU.fault>>10)&63)-1; /* assume MMU table address in PIB[2] */
if ((PEEK(pageAd)&0x7F)==126)       /* replace unallocated page with real page... */
  POKE(pageAd, (PEEK(pageAd)&0xFF00)+GetPage()); /* GetPage() allocates a page */

Due Mar.9: Add to MiniOS (or to your own system) enough code to make semaphores work, then write a program with two threads (or two separate programs), one to read keystrokes and the other to display them on the screen. Use a properly synchronized queue to transfer the data from one process to the other. Please mark up your listing to show what is your own code, or else turn in an abbreviated listing of only your own code. Please provide evidence that your system actually runs, or else tell me that it does not.
 

Midterm Exam March 11.
 

Due Feb.26: Add to MiniOS (or to your own system) enough code to implement a Batch OS operating system. Please mark up your listing to show what is your own code. You can use the existing disk file I/O or (this would be a good time to get started) implement your own. Read a file containing the names of programs to run, then run each program in sequence. If you prefer, you can take the names of the programs from a (single) command line typed in, because that exercises the same technology. Unlike the previous exercise, this can be done (mostly) in user-level code.

Caution: There were bugs in the MiniOS file system, the SandBox emulator, and the OSL compiler, which were corrected today, 2004 February 20, and uploaded tonight.

There are three different programs in the RunThese folder on the G drive, that you can run in your system. You need to compile them if necessary, convert each to a virtual floppy, then copy them to your virtual hard drive using something like the CopyFlop program included in the 2004 February 19 version of MiniOS. From there your OS should be able to run them sequentially:

PacMaze will run stand-alone, so you can see how it should look running in your system. It quits/returns when the last pill has been consumed.
John1 must run in your OS, as it depends on file services. It writes a disk file named "TextData" consisting of the first chapter of John's gospel from the KJV. This program is available in ".ftx" form only, because it has been hacked together by hand.
TextForm must run in your OS, as it depends on file services. It opens a disk file named "TextData" and formats the words to 72-character lines, initially to the screen, but eventually for the printer.

Due Feb.17: Add SysCall handler code to MiniOS (or to your own system) to implement pseudo-files from the keyboard and to the screen. Your implementation should work properly with the built-in Read() and Write() functions imported from package Files. For this assignment it is not necessary to open or close the "files", but eventually you will need to support a call to Open() in order to get a valid FileID to distinguish these files from other (disk) files.

My solution in MiniOS:

a.  File-oriented WriteScr (called from inside SysCall), to output the text to the screen.
b.  A large circular buffer, to store the key codes in DoKeyInts
c.  File-oriented ReadLine (called from inside SysCall), to wait for a full line by backing up the caller's PC, then to copy the bytes over.
d.  A user-level ReadStr, where the accumulation could have been done in a more straight-forward way, by repeatedly calling Read() until the whole line had been received.

Clarification: Apparently some students are confused about what they should be doing for Feb.17. Try to remember that you are writing the Operating System; it's your job to make life pleasant for the application programmer, who only gets to use system calls hidden in APIs like Read() and Write(). It is the nature of this assignment to make those system calls work properly for Keyboard input and Screen output. You can use any code you have available (notably, MiniOS) as models and/or building blocks. There is some new text in the page on Processes to help clarify what is supposed to happen.

This description mostly describes how the parameter(s) to the Open() function make it into the SysCall handler; it's your responsibility to add code to the existing handler to deal with the Keyboard input. It's not necessary to handle Open, because for this assignment the file can be assumed to be already open. It is necessary to handle Read (you can look at the new code to see how that works for the disk read), and also tho handle Write to the screen.

There is one subtle problem you need to deal with in some way, preferably in the OS: When the Read() function is called by the applicaiton program, the user probably has not typed in a whole line (perhaps none at all yet), so you need to decide how to deal with that. One solution (acceptable for this assignment, but not in the general case) would be to return the zero bytes you have currently buffered, and force the user program to deal with assembling the occasional keystroke into a coherent line by calling the function repeatedly. It would be much better (but somewhat tricky) to assemble a whole line in the OS before returning to the user program. The tricky part comes from the fact that the SysCall operation disables interrupts, so you cannot get any more key interrupts until you return.

After you implement process management in your operating system, you just switch context, thus blocking the user application program until the buffer is filled. However, that is not part of the assignment, and may be too hard to do in one weekend. If you poke around in the sample code, you may hit on another way to solve the problem.
 

Due Feb.3: Write a program to continuously display the current date and time at the current mouse coordinates. Don't forget to erase the old date when the mouse moves. Turn in a source listing.

The main() of my implementation was 34 lines and used only available subroutines (for example, those below). The binary code is in the Examples folder on the G drive, which you can mount and run in the virtual machine. Here's what mine displays (yours need not be exactly the same; the point is to get you into the virtual machine, not make life difficult):

Here are some functions you may find helpful:

// PrintNum, a string-free number display (uses PrintChar from MiniOS)
void PrintNum(int theNum) {
  if (theNum==32768) { // special-case, it has no positive..
    PrintChar('-');
    PrintChar('3');
    theNum = 2768;}
  else if (theNum<0) {
    PrintChar('-');
    theNum = -theNum;}
  if (theNum>9) {
    PrintNum(theNum/10);
    theNum = theNum%10;}
  PrintChar(CHR(theNum+48));} // ~PrintNum

// Date extraction functions: (note, YearOf() returns 4 for 2004)
int YearOf(int datehours) {return (datehours>>1)/4383;}
int HourOf(int datehours) {return (datehours-24000)%24;}
int JulianOf(int datehours) {return (datehours-YearOf(datehours)*8766)/24;}
int MonthDayOf(int datehours) {
  final int[] mons = {31,28,31,30,31,30,31,31,30,31,30,31};
  int yr = YearOf(datehours);
  int dy = JulianOf(datehours);
  int mo = 0;
  while (dy>=mons[mo]) {
    dy = dy-mons[mo];
    mo = mo+1;
    if (mo==2) dy = dy-1;}
  return mo*100+dy+101;} // ~MonthDayOf
int MonthOf(int datehours) {return MonthDayOf(datehours)/100;}
int DayOf(int datehours) {return MonthDayOf(datehours)%100;}

The most egregious compiler bug was fixed.

Here is my solution:

// DateMouse.osl -- my solution -- 2004 January 29

import Hardware;
import Dangerous;

int Vrow = 1;
int Vcol = 2;
final int TextColor = DoText+white-minRed; // lite blue
final int ScreenBgnd = FillRect+minRed+minGreen; // dark brown

final int[] FontBits = { 0, 0, 0, 0, 0,   0, 0, 190, 0, 0, // sp
   0, 14, 0, 14, 0,          40, 124, 40, 124, 40,
   76, 146, 511, 146, 100,   66, 37, 146, 328, 132,
   96, 150, 137, 118, 208,   0, 0, 14, 0, 0,
   0, 124, 130, 257, 0,      0, 257, 130, 124, 0,
   8, 42, 28, 42, 8,         16, 16, 124, 16, 16,
   0, 512, 448, 192, 0,      16, 16, 16, 16, 16,
   0, 192, 192, 0, 0,        0, 384, 96, 24, 6,
   56, 68, 130, 68, 56,      0, 4, 254, 0, 0,              // 0
   132, 194, 162, 146, 140,  68, 130, 146, 146, 108,
   48, 40, 36, 254, 32,      78, 138, 138, 138, 114,
   120, 148, 146, 146, 96,   2, 2, 226, 26, 6,
   108, 146, 146, 146, 108,  12, 146, 146, 82, 60,
   0, 204, 204, 0, 0,        0, 716, 460, 0, 0,
   0, 16, 40, 68, 130,       40, 40, 40, 40, 40,
   0, 130, 68, 40, 16,       4, 2, 162, 18, 12 };

void PrintChar(char ch) {
  if (ch<' ' || ch>'?' || Vcol>633) return;
  Video.address = ORD(ch)*10-320+&FontBits;
  Video.left = Vcol;
  Video.right = Vcol+5;
  Vcol = Vcol+6;
  Video.top = Vrow;
  Video.bottom = Vrow+12;
  Video.datum = TextColor;} // ~PrintChar

// PrintNum, a string-free number display (uses PrintChar from MiniOS)
void PrintNum(int theNum) {/* see above */} // ~PrintNum

int YearOf(int datehours) {/* etc. see above */}

void main() {
  int t=0, l=0, b=480, r=640; // the last place drawn
  int tm; // current time, so it doesn't rollover between mins/seconds
  int mh=0, mv=0; // last known mouse coordinates
  while (true) {
    if (Mouse.H==mh) if (Mouse.V==mv) continue;
    mv = Mouse.V;
    mh = Mouse.H;
    Video.top = t;
    Video.left = l;
    Video.bottom = b;
    Video.right = r;
    Video.datum = ScreenBgnd;
    if (mh>600) continue;
    if (mv<10) continue;
    t = mv-10;
    l = mh;
    b = mv+2;
    Vrow = t;
    Vcol = l;
    PrintNum(YearOf(Date.hours)+2000);
    PrintChar('/');
    PrintNum(MonthOf(Date.hours));
    PrintChar('/');
    PrintNum(DayOf(Date.hours));
    PrintChar(' ');
    tm = Date.seconds;
    PrintNum(HourOf(Date.hours));
    PrintChar(':');
    if (tm<600) PrintChar('0');
    PrintNum(tm/60);
    PrintChar(':');
    if (tm%60<10) PrintChar('0');
    PrintNum(tm%60);
    r = Vcol;}} // ~main

Rev. 2004 May 5