A Simple Example of a Multiprogramming OS

(Used in Homework 1 and Projects 1 and 2)

Memory model: Variable-length partitions

This is, at least conceptually, one of the simplest memory models. It was used in the CDC 6600. (Tanenbaum, pp. 26-27; p. 196)

Each process occupies a consecutive chunk of RAM. This chunk is assigned when the process is created, and does not change. The length of the chunk required is specified by the object file for the process.

An inherent drawback to this scheme is external fragmentation ; the free space in memory gets divided into small unusuable blocks. For example, in the above figure, after processes C and E exit, there are three chunks of free space open, of sizes 20M, 16M, and 16M. If process G of size 30M enters, there is no place to put it, even though there is considerably more than 30M free in memory.

Address translation

There are two registers that deal with address translation. The base register holds the starting address of the active process. The limit register holds the size of the starting address. Translating a virtual address VA to an physical address PA involves the following two steps. For example, when D is executing, the base register is 56M and the limit register is 24M. The virtual address 10M gets translated to the physical address 66M.

A drawback is that this requires an integer add (a relatively slow operation) for every address translation -- i.e. once or twice per machine instruction. Of course, this is built into the hardware, but even so it is a delay.

Another drawback is that each process has to predict, at loading time, the amount of memory it needs. If it overestimates, then space is wasted, and it may have to wait longer for a slot to open up. If it underestimates, then it will crash when it runs out of memory. Therefore everyone overestimates, leading to underuse of multiprogramming, and unnecessarily long turnaround times.

User processes certainly are not permitted to write to the base and limit registers, and probably not allowed to read them.

Memory management

There are two issues in memory management: (1) How do you keep track of free space? (2) How, there is a choice, do you choose the placement of a new process? Here is one solution to these; we will discuss several others later in the course.

(Tanenbaum section 4.2.2, pp. 200-202). A simple data structure for keeping track of free space is the free list a linked list of records, recording the starting address and size of each free chunk of memory, sorted in increasing order of starting address. We will discuss later the algorithm for maintaining this list.

A simple criterion for allocating a partition to a process is "first-fit": go through the free list until reaching the first free chunk large enough to accommodate the process, and allocate the process at the bottom of that chunk.

Scheduling: Round robin

(Tanenbaum, pp. 142-143). One of the most common and most important schedulers is round robin. This is not the simplest scheduler, but it is the simplest preemptive scheduler. It works as follows: Suppose the time quantum is 50 msec, process P is executing, and it blocks after 20 msec. When it unblocks, and gets through the ready queue, it gets the standard 50 msec again; it doesn't somehow "save" the 30 msec that it missed last time. (You could do things this way, but people don't.)