Operating Systems Concepts, Fall 2001

Programming Assignment 1 - An Example Solution

Table of Contents

Introduction

This page presents a solution to the first programming assignment, which involves writing a process manager.

Design

The operating system is made up of managers for the disk, the CPU, User Space, and the interrupts:
overall os structure
Circles represent operating-system manager software; non circles represent resources, either hardware (such as the disk) or software (messages). Arrows between managers indicate interactions via subroutine calls; the caller is pointing and the called is being pointed at. The labels associated with each arrow gives the system event that triggers the subroutine call. For example the arrow labeled "Exit" from the Process Manager to the Disk Manager indicates that the Process Manager makes a subroutine call to the Disk Manager (via a routine provided by the Disk Manager) whenever a process exits the system.

The disk manager is responsible for loading programs. The interrupt handler is responsible for initializing the other managers on system boot-up; these interactions are not shown in the diagram.

The Interrupt Handlers

Handle a system-call interrupt. On boot-up, install the system-call interrupt handler and initialize the process, storage, and disk resource managers. The disk resource manager starts reading in the programs. 
<interrupt handlers>+= (U->) [<-D]

void reboot_ih(void) {
  mass.memory->set_ihandler(system_call_i, syscall_ih);
  process::init();
  storage::init(usr_base, usr_size/disk_block_size);
  disk::init();
  }
Defines reboot_ih (links are to index).

The Process Manager

A process is identified by a unsigned integer unique among all existent processes. process::add() creates a new process from the program loaded into User Space at the location given by sc. process::exit() deletes the running process, freeing up all resources held by the process. process::init() initializes the process manager; process::done() returns true if and only if the idle process is the only remaining process; process::halt() halts the simulation. process::block() suspends the currently running process and schedules a replacement, returning the newly blocked process's id. process::ready() makes the blocked process identified by pid ready to run. Some of the other managers need to be able to store values into the saved register context for a particular process; process::put_register() makes that possible. A process may be blocked waiting for a non-cpu resource, ready to use the cpu, or executing in the cpu. A process-table entry contains all the information needed to manage a process, including the process's id, its status, its saved register context, and information about the User Space storage allocated to it.

The process table entry also contains code to allocate process ids and save and restore process register contexts.

Process-table entries are stored in a list, with special iterators indicating the entries for the currently running process and the idle process (which may, on occasion, be the same process). Loading a process into the cpu involves changing the process's state to executing and restoring the saved register state. Return an iterator to the process-table entry with id equal to pid; die with an error if there's no such entry. A couple of helper predicates to find process-table entries of ready or running processes. If the idle process is running, check the process table for a ready process and run it if found. If no process is running (because the running process exited) find a ready process and run it (this should always be possible because the idle process is always around and always ready).

If, after all this, the idle process is still running, then it's time to halt the system if both the process and disk managers are done.

Create a process from the program loaded into allocated space given by sc. The new process is ready to run. The initial value of the PC is one past the start of the program to skip over the program size value (however, the size value is part of the program, so the base register should be set to the start of the program). Block the currently running process and start another. The process manager's done when the idle process is the only process left to manage. However, that doesn't mean execution is done because the disk may still be at work loading programs. The only resource held by an exiting process is its allocated storage, which is returned to the storage manager. Poke the disk in case it's suspended program loading until more space has been freed. Halting the system has pie-like easiness. The process manager initializes by defining and running the idle process, which is a permanent resident of the process table. Store a value in one of a process's saved registers. When changing a process's status to ready, be sure to re-check the process-table to see if the new process can run immediately.

The Disk Manager

Because this version of the operating system doesn't make the disk available to the user processes, the only thing the code managing the disk has to do is to read programs into User Space, an activity which doesn't require too much in the way of an interface.

The init() procedure initializes the disk and begins program reading. The done() procedure returns true when all programs have been read from disk; if programs remain on disk to be read, done() returns false.

The disk code tries to read as many programs as it can as soon as it can; ideally, it would read all the programs on disk at one go. However, if there's more programs on disk than can fit in User Space, then the disk code has to pause until more space is freed up. The poke() routine, when called, tries to re-start program reading if it's been stalled; it's usually called after a process has exited and freed up some User Space.

On disk initialization, the next disk block to read is the first block on the disk, no program reading is currently being done, and not all programs have been read. If there's more programs to read and reading isn't in progress, then start another read. Otherwise, either there's no more programs to read or a read is in progress; in which case there's no reason to start another read. The disk is done of program reading is done. Handle a disk-interrupt that is the result of reading in a program's block. If all the program's blocks have been read in, then the program is ready to run; hand it off to the process manager and go read then next program. Otherwise, schedule a disk-read for the next block in the program. Handle the disk interrupt that results from reading a program's first block. If the program size is zero, there's no more programs on the disk and program reading is over. If there's no more process to run, then execution's over too.

If the program's too big for its allocated space, then suspend program reading until more space frees up. Otherwise, trim the allocated space to the required amount and read in the rest of the program's blocks. Note this involves calling read_rest_program() as a continuation of the interrupt processing started by handle_first_block().

Try to read another program. If the next disk block to read is larger than the disk, then there's no more programs to read. Otherwise, allocate the largest chunk of free space available. If there's no free space available, then don't do any reading. If there if there is free space available, then read in the program's first block. Check for a disk-io error on behalf of _caller and die if found. Issue a disk read on behalf of _caller.

The Message Pool

The message pool has a simple interface, which is one of the advantages of message passing as a synchronization mechanism. Note, however, that the get() procedure doesn't return a value, which suggests the message-pool implementation will be a bit less simple than is the interface. Within the message-pool implementation, a message is represented as a (tag, data) pair. Messages sent but not yet received are stored in a list. A process that is blocked because its trying to receive a message that hasn't yet been sent is represented by the pair (i, t), where i is the process's id and t is the tag of the message being waited for. Waiting processes are put in the waiting list. Given the container values and the matching function match over elements of values, return true if values contains an element that matches on the value tag; return false otherwise. If values does have a match, set i to point to the matching element; otherwise, i contains an undefined value. Search the message pool for a message with tag t. If such a message exists, set mi to point to it and return true. If no such message exists, return false. Search the list of waiting processes for a process waiting for a message with tag t. If such a process exists, set wi to point to it and return true. If no such process exists, return false. Receive from the message pool a message having tag t. If such a message exists, remove it from the pool and store the associated data in the calling user-process's register 2. Otherwise, block the calling user process until the message shows up. Put the message having tag t and data d into the message pool. However, before doing that, search the list of waiting processes to see if there's a waiter for this message. If so, skip the message pool and transfer the data directly to the waiting process and wake it up; otherwise, add the message to the message pool.

Storage Management

The operating system's storage management characteristics are simple: programs don't change size during execution, program size can be determined statically before execution starts, and allocated space must be contiguous.

Correspondingly, the data representation for allocated storage is simple too. Each chunk of user space allocated to a program is represented by a pair of numbers giving the lowest user-space address and size of the chunk in disk blocks.

The storage manage needs to be initialized with both the lowest address and size in disk blocks of the allocatable storage. 
<storage-management interface definitions>+= (U->) [<-D->]

 void init(address base, unsigned size);

The trick to allocating storage is that the program size is unknown before the first block is read in, and the first block can't be read in until some storage is allocated for the program (That last bit isn't true, because the operating system could always read the first block into a buffer allocated in system or device space. However, to do so would require either another disk read or, more likely, a copy into user space. Both are unattractive alternatives because of extra time they'd take.)

The way out of this trick is to allocate the largest contiguous chunk of storage available. If the next program's larger than the chunk, it can't be read in anyway. 

<storage-management interface definitions>+= (U->) [<-D->]

 chunk max_chunk(void);

Once the program size is known, so is the amount of unneeded space in the allocated storage chunk. To improve storage utilization, it should be possible to adjust an allocated chunk to an exact fit (relative to block size), returning the unneeded space to the free list.

And it should be possible to return an allocated chunk to the free-storage Allocatable storage is organized into a sequence of blocks, each the size of a disk block. The whole of allocatable store is represented by a bit map, where bit i represents the availability of storage block i.

base_address keeps track of the lowest address in allocatable storage.

The internal representation of allocated storage is similar to the external representation. The only difference is using an index (into the bit map) instead of an address to indicate the start of the allocation. To avoid confusion between the representations, the internal representation is called an index range, and the external representation is called a storage chunk. There needs to be a way of converting between the internal and external representations of allocated storage. Return the next range of free blocks at or to the right of the block at start. Return a range of zero length if there's no free blocks. Set the free-map bits in the index range ir to the value bv. Die if any of the bits in the range are already equal to bv. The storage manager is initialized with the start (lowest address) and size of the storage area to be managed. Initially, all storage is free. Return the largest contiguous chunk of unallocated storage. Shrink the allocated storage sc to new_size blocks, returning the unused blocks to the free list; die if new_size is larger than sc's current size. sc is modified to reflect its new size. Return the allocated storage sc to the free list. A quick check to make sure the storage-management code is working without problems.

Miscellaneous Definitions

Some odds and ends useful to all code throughout the operating system.

Index

This page last modified on 5 December 2001.