This assignment is due by Wednesday, 4 March, no later than 11:50 p.m.. This is
the final deadline; assignments cannot be submitted for grades after Wednesday,
4 March, at 11:50 p.m.. See the turn-in page (last modified on 2015 February 7) for
information about turning in your assignment.
Make sure you have read and understand the simulator and
hardware documentation before you wade into this
assignment. There are links into relevant parts of these documents below, but
you need to have an over-all view of the simulator and the hardware for the
parts to make sense.
This assignment continues developing the simple batch-oriented operating system
created for the previous assignment. The extensions involve new
process system calls and new interrupt handlers. The new system calls extend
the process-management facilities developed in the previous assignment and
enable inter-process communication.
The operating system should execute as many process as possible. In
particular, if one process fails due to some error condition, the operating
system should throw it out and continue to tend to the other running processes
(if any). Under no circumstances should a failing process cause the operating
system itself to fail.
In this assignment, development involves two areas:
- Implementing interrupt handlers for the previously unhandled
countdown, illegal instruction, and
invalid address interrupts described in the hardware documentation.
- Implementing four new system calls (the exec, yield, put-slot, and
get-slot system calls) described below.
There is no change to the structure and use of the batch disks described in the
previous assignment. This assignment adds new batch disks, described below,
for the operating system to execute. The batch disks from the previous
assignment should continue to work with the revised operating system.
You may implement any scheduler you want, but it must be a pre-emptive
scheduler. Simple round-robin pre-emption will be fine, however the
choice is yours to make.
The pa2 operating system supports four new system calls (exec, yield,
putSlot and getSlot) in addition to the exit system call
implemented in the previous assignment.
The system calls can be split into two groups: process-management system calls
and inter-process communication system calls.
- exec system call (
OperatingSystem.SystemCall.exec) -
The calling process requests that a new process start executing. Register 1
contains the word number of the batch-disk index block for the program
associated with the new process.
After the exec system call returns, the caller’s register 0 contains
the system call status
Hardware.Status.ok | command completed successfully |
Hardware.Status.badPid | there is no program with the given id |
Hardware.Status.noResource | required resource not available |
and register 1 contains the new process’s id if the exec was
successful; otherwise the contents of register 1 is undefined.
The contents of registers 0 and 2 through 10 in the new process (the
child process) are identical to the contents of the associated
registers in the process that issued the exec (the parent process).
Register 1 in the child process contains the parent process’s id.
- yield system call (
OperatingSystem.SystemCall.yield) -
The calling process gives up the CPU.
The yield system call returns when the caller regains the CPU, unless the
caller is the only non-idle processes available, in which case the yield system
call returns immediately. Register 0 should always contain Hardware.Status.ok.
Each process has a one-word slot which can be read and written using the
get-slot and put-slot system calls. A process writes a value into a slot using
put-slot; a process reads the value from a slot using get-slot.
A process can write a value into any existing process’s slot (including
itself); a process can read a value only from its own slot.
- put-slot system call (
OperatingSystem.SystemCall.putSlot) -
The calling process writes a value into the slot associated with a process.
Register 1 contains the id of the process receiving the value; register 2
contains the value to be written into the receiving process’s slot.
After the put-slot system call returns, the caller’s register 0
contains the system call status
Hardware.Status.ok | command completed successfully |
Hardware.Status.badPID | there is no process with the given id |
Hardware.Status.noResource | required resource not available |
If register 0 contains Hardware.Status.ok when the put-slot call returns, then the
given value was successfully written into the receiving process’s slot
(note that this does not imply that the receiving process has read the value
from its slot). If register 0 contains Hardware.Status.noResource, then the attempt to
write the given value into receiver’s slot has failed because the slot
already contains an unread value.
- get-slot system call (
OperatingSystem.SystemCall.getSlot) -
The calling process reads a value from its slot.
After the get-slot system call returns, the caller’s register 0
contains the system call status
Hardware.Status.ok | command completed successfully |
Hardware.Status.noResource | required resource not available |
If register 0 contains Hardware.Status.ok when the get-slot call returns, then register
1 contains the value read from the slot and register 2 contains the id of the
process that put the value. If register 0 contains Hardware.Status.noResource, then
the slot was empty, and the contents of registers 1 and 2 are undefined. A
slot is considered empty before the first value is put, and between the most
recent get and the immediately following get.
In addition to the reboot, disk, and system-call interrupts implemented in the
previous assignment, the operating system needs to implement handlers for the
remaining three interrupts:
- the countdown interrupt handler: deal with countdown-time
expiry, most likely for the pre-emptive scheduler.
- the invalid address interrupt handler: deal with mis-behaving
processes (such as those in the
pa2-bad.dsk batch disk).
- the illegal instruction interrupt handler: deal with
mis-behaving processes (such as those in the
pa2-bad.dsk batch disk).
As with system calls, you’ll be implementing and re-implementing
interrupt handlers in later assignments, so some thought now may save you some
pain later.
The directory /export/home/class/mucsos/pa2 contains some batch disks
you can use to test your operating system:
pa2-bad.dsk - A disk containing a program
that does bad things. Despite all the bad things that are going on, there
should be no output other than the usual end of execution information.
pa2-execs.dsk - A disk containing two programs. The first program
sets a count and execs the second program. The second program reduces the
count by one and, if the count is still positive, execs another copy of
itself.
pa2-dcs.dsk - The first, client, program execs the second,
server, program and sends it a value. The doubling server receives a value,
doubles it and sends it back to the client. Then both processes exit.
pa2-ydcs.dsk - Like the dcs disk but the client yields if the
get-slot system call fails.
pa2-tree.dsk - A root program execs two child programs, each of
which execs two child programs and so on until they form a seven-process
complete binary tree, then the leaves pass values back to their parents and
exit, and so on.
pa2-ytree.dsk - Same as pa2-tree.dsk except processes yield whenever a
put- or get-slot system call fails.
Here are timed example runs for each disk:
$ time java -ea -cp pa2/arcsim.jar:. main os pa1-empty.dsk
The system is halted.
Total execution time: 10 ticks, idle time: 9 ticks (90%).
real 0m0.394s
user 0m0.328s
sys 0m0.048s
$ time java -ea -cp pa2/arcsim.jar:. main os pa1-solo.dsk
The system is halted.
Total execution time: 429 ticks, idle time: 99 ticks (23%).
real 0m0.378s
user 0m0.264s
sys 0m0.092s
$ time java -ea -cp pa2/arcsim.jar:. main os pa2-bad.dsk
The system is halted.
Total execution time: 43 ticks, idle time: 27 ticks (62%).
real 0m0.332s
user 0m0.216s
sys 0m0.092s
$ time java -ea -cp pa2/arcsim.jar:. main os pa2-dcs.dsk
The system is halted.
Total execution time: 149 ticks, idle time: 72 ticks (48%).
real 0m0.340s
user 0m0.228s
sys 0m0.088s
$ time java -ea -cp pa2/arcsim.jar:. main os pa2-execs.dsk
The system is halted.
Total execution time: 187 ticks, idle time: 72 ticks (38%).
real 0m0.338s
user 0m0.240s
sys 0m0.072s
$ time java -ea -cp pa2/arcsim.jar:. main os pa2-tree.dsk
The system is halted.
Total execution time: 441 ticks, idle time: 129 ticks (29%).
real 0m0.353s
user 0m0.256s
sys 0m0.072s
$ time java -ea -cp pa2/arcsim.jar:. main os pa2-ydcs.dsk
The system is halted.
Total execution time: 141 ticks, idle time: 72 ticks (51%).
real 0m0.344s
user 0m0.252s
sys 0m0.064s
$ time java -ea -cp pa2/arcsim.jar:. main os pa2-ytree.dsk
The system is halted.
Total execution time: 443 ticks, idle time: 129 ticks (29%).
real 0m0.358s
user 0m0.268s
sys 0m0.064s
$
As long as your operating system runs correctly the numbers produced by your
operating system don’t matter. As a sanity check, however, the numbers
produced should be within 50% of the numbers shown above.
If you’re looking for a way to proceed, you might want to consider the
following steps:
- Get your os to work with pa2-execs.dsk, which requires
implementing the exec system call.
- Implement the illegal-instruction and bad-address interrupts and run
pa2-bad.dsk.
- Add the yield, put- and get-slot system calls to your os; it
should now be able to run pa2-ydcs.dsk.
- Make your os scheduler pre-emptive; it should now be able to run all the
batch disks (the recommended testing order for the remaining disks is dcs,
ytree, and tree).
This page last modified on 2015 February 12.