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.
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
- Check that 0 =< VA < limit. If not, raise an error.
- PA = VA + base
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.
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
- The processes that are ready to run (i.e. not blocked) are
kept in a FIFO queue, called the "Ready" queue.
- There is a fixed time quantum (50 msec is a typical number) which
is the maximum length that any process runs at a time.
- The currently active process P runs until one of two things happens:
In either case, the process at the head of the ready queue is now made
the active process.
- P blocks (e.g. waiting for input). In that case, P is taken off the
ready queue; it is in the "blocked" state.
- P exhausts its time quantum. In this case, P is pre-empted, even though
it is still able to run. It is put at the end of the ready queue.
- When a process unblocks (e.g. the input it's waiting for is complete)
it is put at the end of the ready queue.