Programming Assignment 1 - Process Management

Operating Systems, Spring 2012

Table of Contents

Due Date

This assignment is due on Wednesday, 22 February, no later than 11:30 p.m.. See the turn-in page (last modified on 2012 March 6) for information about turning in your assignment.

Prerequsites

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 both the simulator and the hardware for the parts to make sense.

Introduction

This assignment implements a simple batch-oriented operating system, which behaves as follows:

  1. After the operating system boots up, it reads a program from the batch disk and executes it.

  2. The operating system supports multiprocessing; that is, whenever possible, there may be more than one process executing at the same time.

  3. When there are no more processes executing, the operating system halts the system.

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 these assignments, implementing an operating system involves two parts:
  1. Implementing the interrupt handlers. In this first assignment, this means implementing the six interrupts (the countdown, disk, illegal instruction, invalid address, reboot, and system-call interrupts) described in the hardware documentation.
  2. Implementing system calls. Your system-call interrupt interrupt handler has to implement the five system calls (the exec, exit, yeild, put-slot, and get-slot system calls) described below.

The Batch Disk

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

an example batch disk

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.

Loading Programs for Execution

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 + Hardware.Disk.blockSize, 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 process 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.

The Scheduler

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.

System Calls

Your operating system needs to support five system calls: exec, exit, yield, putSlot and getSlot. 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).

The system calls can be split into two groups: process-management system calls and inter-process communication system calls.

Process Management System Calls

exit system call (OperatingSystem.SystemCall.exit)
The currently executing process is finished. There is no return from this system call.

exit sys call arguments and results

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.

exec sys call arguments and results

After the exec system call returns, the caller's register 0 contains the system call status

Hardware.Status.okcommand completed successfully
Hardware.Status.badPidthere is no program with the given id
Hardware.Status.noResourcerequired 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.

yield sys call arguments and results

The yield system call returns when the caller regains the CPU; register 0 should always contain Hardware.Status.ok.

Inter-Process Communication System Calls

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.

put-slot sys call arguments and results

After the put-slot system call returns, the caller's register 0 contains the system call status

Hardware.Status.okcommand completed successfully
Hardware.Status.badPIDthere is no process with the given id
Hardware.Status.noResourcerequired resource not available

If register 0 contains Hardware.Status.ok when the put-slot call returns, then the given value was succsfully 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.

get-slot sys call arguments and results

After the get-slot system call returns, the caller's register 0 contains the system call status

Hardware.Status.okcommand completed successfully
Hardware.Status.noResourcerequired 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 didn't contain a value, and the contents of registers 1 and 2 are undefined.

Interrupt Handlers

You will need to implement six interrupt handlers for this assignment:
  1. the reboot interrupt handler: install the operating system at system boot.
  2. the disk interrupt handler: take care of disk interrupts.
  3. the system-call interrupt handler: implement system calls.
  4. the countdown interrupt handler: deal with countdown-time expiry, most likely for the pre-emptive scheduler.
  5. the invalid address interrupt handler: deal with mis-behaving processes (such as those in the pa1-bad.dsk batch disk).
  6. the illegal instruction interrupt handler: deal with mis-behaving processes (such as those in the pa1-bad.dsk batch disk).
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.

Test Batch Disks

The directory /export/home/class/cs-os/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 single program does nothing for a while and then calls exit.

    pa1-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.

    pa1-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.

    pa1-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.

    pa1-ydcs.dsk - Like dcs but the client yields if the get-slot system call fails.

    pa1-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.

    pa1-ytree.dsk - Same as pa1-tree.dsk except processes yield whenever a put- or get-slot system call fails.

If you're looking for a way to proceed, you might want to consider the following steps:

  1. 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 (non-pre-emptive) scheduler to run the idle process.

  2. Modifiy the (still non-pre-emptive) scheduler and disk manager to read in a program and execute the associated process; 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.

  3. Get your os to work with pa1-execs.dsk, which requires implementing the exec system call.

  4. Add the yield, put- and get-slot system calls to your os; it should now be able to run pa1-ydcs.dsk.

  5. 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 2012 February 17.