Programming Assignment 1 - Process Management

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

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.

fork system call (system_call::fork)

The calling process requests that a copy of itself be created.

After the fork system call returns, register 0 in both processes contains the system call status. In the calling process, register 1 contains the process id of the newly created process. In the newly created process, register 1 contains 0 (which means that 0 can't be a letitimate process id).

status::ok	command completed successfully
status::bad_count	out of space (too many processes)

exec system call (system_call::exec)

The calling process is replaced by the process running the program identified in register 1.

Normally, exec never returns (because the new process starts executing from its beginning). If the exec system call returns, some error happened and register 0 contains the system call status. If an exec system call returns, the calling process is still running.

status::ok	command completed successfully
status::bad_id	there is no program with the given id
status::bad_count	no more space

clock system call (system_call::clock)

Create a lock.

Register 1 contains 0 if the lock is to be unlocked when created; otherwise, if register 1 contains any value other than 0, the lock is locked. After the call, register 0 contains the call status and register 1 contains the newly created lock's id if there were no errors; if there were errors, the contents of register 1 is arbitrary.

status::ok	command completed successfully
status::bad_count	no more space

flock system call (system_call::flock)

Free a lock.

Register 1 contains a valid lock id; after the call, the lock id is no longer valid.

status::ok	command completed successfully
status::bad_id	invalid lock id

llock system call (system_call::llock)

Lock a lock.

Register 1 contains a valid lock id. If the specified lock is unlocked, it is locked by the calling process and the call returns. If the specified lock is locked, the call blocks and process waits until the lock is unlocked.

ulock system call (system_call::ulock)

Unlock a lock.

Register 1 contains a valid lock id. If the specified lock l is locked, it is unlocked by the calling process. If there are processes blocked on the l waiting to lock it, one of them should be made ready to execute so it can try to lock l again. If l is unlocked, nothing happens; it is not an error to unlock an unlocked lock.

status::ok	command completed successfully
status::bad_id	invalid lock id

pa1-empty.dsk - The empty disk; it contains no programs.

$ ./os1 -d /export/home/class/cs-505/devices/pa1-empty.dsk 

The system is halted.
Total execution time:  10 ticks, idle time:  9 ticks (90%).

$ 

pa1-solo.dsk - A disk containing a single program that just makes an exit system call.

$ ./os1 -Df31 -d /export/home/class/cs-505/devices/pa1-solo.dsk  
At time    0 process 10 runs.
At time  120 process 11 runs.
At time  439 process 11 exits.
At time  439 process 10 runs.

The system is halted.
Total execution time:  439 ticks, idle time:  109 ticks (24%).

$ 

pa1-forks.dsk - A disk containing a program that just forks itself ten times and then exits.

$ ./os1 -Df31 -d /export/home/class/cs-505/devices/pa1-solo.dsk  
At time    0 process 10 runs.
At time  120 process 11 runs.
At time  439 process 11 exits.
At time  439 process 10 runs.

The system is halted.
Total execution time:  439 ticks, idle time:  109 ticks (24%).

$ ./os1 -Df31 -d /export/home/class/cs-505/devices/pa1-forks.dsk 
At time    0 process 10 runs.
At time   21 process 11 runs.
At time   24 process 11 forks itself as process 12.
At time   33 process 11 forks itself as process 13.
At time   42 process 11 forks itself as process 14.
At time   51 process 11 forks itself as process 15.
At time   60 process 11 forks itself as process 16.
At time   69 process 11 forks itself as process 17.
At time   78 process 11 forks itself as process 18.
At time   87 process 11 forks itself as process 19.
At time   96 process 11 forks itself as process 20.
At time  105 process 11 forks itself as process 21.
At time  112 process 11 exits.
At time  112 process 21 runs.
At time  119 process 21 exits.
At time  119 process 20 runs.
At time  128 process 20 exits.
At time  128 process 19 runs.
At time  137 process 19 exits.
At time  137 process 18 runs.
At time  146 process 18 exits.
At time  146 process 17 runs.
At time  155 process 17 exits.
At time  155 process 16 runs.
At time  164 process 16 exits.
At time  164 process 15 runs.
At time  173 process 15 exits.
At time  173 process 14 runs.
At time  182 process 14 exits.
At time  182 process 13 runs.
At time  191 process 13 exits.
At time  191 process 12 runs.
At time  200 process 12 exits.
At time  200 process 10 runs.

The system is halted.
Total execution time:  200 ticks, idle time:  19 ticks (9%).

$ 

pa1-execs.dsk - A disk containing program that execs through five programs.

$ ./os1 -Df31 -d /export/home/class/cs-505/devices/pa1-execs.dsk  
At time    0 process 10 runs.
At time   21 process 11 runs.
At time   26 process 11 execs program 1.
At time   26 process 10 runs.
At time   37 process 11 runs.
At time   42 process 11 execs program 2.
At time   42 process 10 runs.
At time   53 process 11 runs.
At time   58 process 11 execs program 3.
At time   58 process 10 runs.
At time   69 process 11 runs.
At time   74 process 11 execs program 4.
At time   74 process 10 runs.
At time   85 process 11 runs.
At time   90 process 11 exits.
At time   90 process 10 runs.

The system is halted.
Total execution time:  90 ticks, idle time:  59 ticks (65%).

$ 

pa1-tree.dsk - A disk containing a program that forks into a 3-process complete binary tree and then uses locks to synchronize with its children.

$ ./os1 -Df31 -d /export/home/class/cs-505/devices/pa1-tree.dsk   
At time    0 process 10 runs.
At time   87 process 11 runs.
At time   97 process 11 forks itself as process 12.
At time  110 process 11 forks itself as process 13.
At time  117 process 13 runs.
At time  132 process 13 exits.
At time  132 process 12 runs.
At time  147 process 12 exits.
At time  147 process 11 runs.
At time  166 process 11 exits.
At time  166 process 10 runs.

The system is halted.
Total execution time:  166 ticks, idle time:  79 ticks (47%).

$ 

pa1-bad.dsk - A disk containing programs that do bad things. The last bad thing done is an illegal memory access. No output (except possibly for the illegal memory access) means everything was handled properly.

$ ./os1 -d /export/home/class/cs-505/devices/pa1-bad.dsk        

The system is halted.
Total execution time:  81 ticks, idle time:  49 ticks (60%).

$ 

My solution to the first programming assignment, os1, is available in /export/home/class/cs-505/os/bin where os is either SunOS or Linux. 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. os1 also implements the f31 debug flag to print process execution behavior, as shown in the examples above.

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 scheduler to run the idle process.

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

3. Implement the fork system call to handle the forks disk.

4. Implement the exec system call to handle the forkexec 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.

5. At this point your operating system should contain enough code to execute the rest of the batch disks.