This assignment is due on Wednesday, 10 October, no later than 2:00 p.m.. See
the submissions page (last modified on 20 December 2001) 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 programs from the
batch disk and executes them.
- 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 read and executed, the operating system
terminates.
For simplicity, you may assume the programs are to be run in the order they're
read from the batch disk. That is, it is not required that the operating
system scan the batch disk with the idea of packing primary storage with as
many programs as possible; first-come, first-serve scheduling is good enough
for this assignment.
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 read the next program. 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 0, the first
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 every program (that is, the first word of the first block of
every program) contains the number of blocks making up the program.
If the batch disk is not full, the last program is immediately followed by an
end-of-programs block, the first word of which contains a zero. If the batch
disk is full, the last program ends the disk and the end-of-programs block is
omitted.
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. Because the batch disk is not empty,
the third and last program is immediately followed by an end-of-programs block.
A
message is a two-word set; one of the words is known as the
message tag and the other is known as the
message data.
The operating system manages a
message pool available to all processes.
Processes may put messages into the message pool and get messages from the
message pool using the get_msg and get_msg system calls. The message pool must be able to hold at least 16
messages; it may hold more.
The message pool is empty when the operating system boots. Messages remain in
the message pool until removed by a process; a message's lifetime is
independent of the lifetime of the process that put the message in the message
pool. The contents of the message pool has no influence over when the
operating system terminates; the operating system terminates when there are no
more processes left to execute, independent of the number of messages available
in the message pool.
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.
The program is loaded in primary storage in increasing address order. The
contents of the program's first disk block is loaded into primary storage
starting at location i; the contents of the program's second disk block is
loaded into primary storage starting at location i + disk_block_size;
and so on.
Once loaded into primary storage, the program's first instruction has address
i + 1, the address of the second word of the program (the first word
contains the block count). The program counter should be set to i + 1
when the program first executes.
The test programs your operating system will execute make three system calls:
exit, get_msg, put_msg; part of this
assignment is to implement these system calls. 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 anyway).
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/devices
pa1-empty.dsk- The empty disk; it contains no programs.
pa1-nomsgs.dsk- A disk of programs that call only the exit system
call; they don't call the message routines.
pa1-selfmsg.dsk- A disk containing a single program, which puts a
message in the message pool, retrieves the message from the message pool, and
then exits.
pa1-circle.dsk- A disk of programs that organize themselves into
a circle and pass messages around the circle.
If you're looking for a way to proceed, you might want to consider the
following steps:
- Get your operating system to work with the empty disk. This makes sure
your operating system uses the disk correctly.
- Get your operating system to work with the nomsg disk by adding a
serial scheduler that reads in a program, executes it until it exits, reads in
the next program, and so on. A serial scheduler lets you concentrate on
getting the mechanics of executing a program right.
- Replace the serial scheduler with a multi-tasking one that always tries
to read and execute as many programs as possible. Because the programs in
nomsg don't make any system calls except exit, there won't be any multi-taking
in the sense of more than one program running at the same time. However, this
step makes sure your operating system properly keeps track of processes and
memory.
- Get your operating system to work with the selfmsg disk. This step
requires that your operating system handle message send and receive system
calls.
- Get your operating system to work with the circle disk. This step
requires nothing new in your operating system, but it does require that
everything in your operating system be working correctly.
This page last modified on 1 October 2001.