Programming Assignment 1 - Process Management

Operating Systems, Fall 2004

Table of Contents

Due Date

This assignment is due on Tuesday, 12 October, no later than 2:00 p.m.. See the submissions page (last modified on 24 September 2004) for information about turning in your assignment.

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 program executing at the same time.

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

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

The Scheduler

You may implement any scheduler you want, but it must be a pre-emptive scheduler (see pages 258-9 of the text). 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, put_slot and get_slot. 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 (system_call::exit)
The currently executing process is finished. There is no return from this system call. exit sys call arguments and results

exec system call (system_call::exec)
The calling process requests that a new process start executing. Register 1 contains the batch-disk index of 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

status::okcommand completed successfully
status::bad_idthere is no process with the given id
status::no_resourcerequired 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 (system_call::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 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 (system_call::put_slot)
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

status::okcommand completed successfully
status::bad_idthere is no process with the given id
status::no_resourcerequired resource not available

If register 0 contains 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 status::no_resource, 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 (system_call::get_slot)
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

status::okcommand completed successfully
status::no_resourcerequired resource not available

If register 0 contains 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 status::no_resource, 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 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.

Test Batch Disks

The directory /export/home/classes/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 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. Each second program reduces the count by one and, if the count is still positive, execs another copy of the second program.

    pa1-dcs.dsk - The first, client, process execs the second, server, process 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 process execs two child processes, each of which execs two child processes and so on until they all 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.

My solution to the first programming assignment, sys-os1 where sys is either solaris or linux, is available in /export/home/classes/cs-438-505/pa1. In addition to the debug-flag values accepted by the simulator, os1 also implements the following:

f31 - print process activity to std-err.
f30 - print successful put- and get-slot activity to std-err.

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:

  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, tree, ytree, then bad).

This page last modified on 13 November 2004.