This assignment is due on Tuesday, 18 June, no later than 2:00 p.m.. See
the submissions page (last modified on 9 July 2002) for information about submitting
your assignment.
This assignment implements a simple batch-oriented operating system, which
behaves as follows:
- After the operating system boots up, it reads a program from the
batch disk and executes it.
- The operating system supports multiprocessing; that is, whenever
possible, there may be more than one program executing at the same time.
- When all programs have been executed, the operating system halts.
The operating system should execute as many programs as possible. In
particular, if one program fails due to some error condition, the operating
system should throw it out and continue to tend to the other running programs
(if any). Under no circumstances should a failing program cause the operating
system itself to fail.
A
batch disk is a disk containing a set of programs to be run.
Programs occupy consecutive disk blocks starting with disk block 1, the second
block on the disk. A program always occupies a positive number of blocks, and
each program follows the next with no wasted disk blocks between them. The
first word of the first block of every program contains the first word of the
program.
The
index block - disk block 0, the first block on the disk - contains
an index of the programs in the disk. The ith word of the index block
contains the size in disk blocks of the ith program in the batch disk.
Unused entries in the index block are set to zero. Every batch disk contains
an index block.
For example, this diagram
shows a batch disk containing three programs. The first program has size 3;
that is, the first program occupies three disk blocks. The second program has
size 1 and the third program has size 2.
A program is laid out on disk as a sequence of disk blocks. The order of the
program's contents on disk must be preserved in primary storage when a program
is loaded into primary storage for execution. The program's disk-block
contents must not be re-arranged in primary storage, and all the program's disk
blocks must be read into primary storage before the program can be run.
A program is loaded in User Space in order of increasing addresses. The
contents of the program's first disk block is loaded into User Space starting at
location i; the contents of the program's second disk block is loaded into
User Space starting at location i + disk_block_size; and so on. The
program's blocks must all fit in User Space. A program may be loaded anywere in
User Space it can fit.
Once loaded into primary storage, the program's first instruction has address
i, the address of the first word of the program. The program counter
should be set to i when the program first executes.
After boot-up initialization, the operating system should load and begin
executing the first program on the batch disk; word 0 of the index block
contains information on the first program. If the batch disk contains no
programs, the operating system should halt.
Your operating system needs to support three system calls: fork,
join, and exit. These are the first of many system calls you will be
implementing in these assignments, so you might want to give some though to
designing an easily changeable system-call implementation (or you have to be
willing to throw-away and rewrite your system-call implementation several
times, which is probably the better approach to take).
-
exit system call (
system_call::exit) -
The currently executing process is finished. There is no return from this
system call.
The exit value is the value returned in a join system call.
-
fork system call (
system_call::fork) -
The calling process requests that a copy of the program specified in register 1
be read from the disk and executed.
After the fork system call returns, register 0 contains the system call status
status::ok | command completed successfully |
status::bad_id | there is no program with the given id |
and register 1 contains an identifier for the newly created process.
A fork system call copies the contents of registers 0 through 10 from the
parent to the child when creating the child. When the child begins execution,
the contents of its registers 0 through 10 are identical to the contents of the
parent's registers at the time the parent made the fork system call. After the
fork, the register contents could differ as the parent and child change them
independently of one another.
-
join system call (
system_call::join) -
The calling process suspends execution until the process specified in register
1 exits.
After the join system call returns, register 0 contains the system call status
status::ok | command completed successfully |
status::bad_id | there is no process with the given id |
If register 0 contains status::ok, then register 1 contains the value the
joined process passed in register 1 for the exit system call. The
contents of register 1 is undefined if register 0 contains a value different
from status::ok.
A process may join with a process that has exited before the join system call.
A process may be the target of at most one join statement.
If more than one process is trying to join with the same process, exactly one
of the joining processes will win and the rest will lose. The choice if the
winner is arbitrary among the joiners. The losing processes have
status::bad_id codes in register 0.
You will need to implement three interrupt handlers for this assignment: the
reboot-interrupt handler, the disk-interrupt handler, and the system-call interrupt handler. The
reboot interrupt handler installs your operating system in the hardware; the
disk interrupt handler takes care of interrupts from the disk; and the
system-call interrupt handles system calls from the executing process. As with
system calls, you'll be implementing and re-implementing several other
interrupt handlers in later assignments, so some thought now may save you some
pain later.
The directory /export/home/class/cs-438-505/pa1 contains some batch disks you can use to test
your operating system:
pa1-empty.dsk - The empty disk; it contains no programs.
pa1-solo.dsk - A disk containing a single program that just makes an
exit system call.
pa1-forks.dsk - A disk containing programs that just fork and exit
without doing any joins.
pa1-forkjoin.dsk - A disk containing program that forks and joins with
another program.
pa1-tree.dsk - A disk containing program that forks into a
fifteen-process complete binary tree and then joins back to a single process,
passing values up and down the tree.
pa1-bad.dsk - A disk containing programs that do bad things.
My solution to the first programming assignment, os1, is available in
/export/home/class/cs-438-505/misc. You should not be concerned about matching your operating system's
timing to the timings from os1; timing varies depending on implementation
details. However, the SYSC system-call instruction counts - obtained with
the ins_cnts flag - from your operating system should
match exactly the instruction counts from os1.
If you're looking for a way to proceed, you might want to consider the
following steps:
- Get disk io working so the operating system handles the empty disk (the
os must read the disk to discover it's emtpy). This requires implementing a
disk-interrupt handler as well as code to read the disk. It also requires a
simple scheduler to run the idle process.
- Modifiy the scheduler and disk manager to read in and execute a
program; this lets the operating system run the solo disk. You'll also have to
add a system-call interrupt handler and implement the exit system call.
- Implement the fork system call to handle the forks disk.
- Implement the join system call to handle the forkjoin disk. At this
point your operating system should be complete. The remaining batch disk don't
require any functions other than what your operating system should now contain.
- At this point your operating system should contain enough code to
execute the rest of the batch disks.
This page last modified on 28 June 2002.