Module 9: Memory Managment

Introduction

When we speak of memory in this module, we are referring to RAM (so-called "random access memory").
RAM is generally the highest speed memory and memory that is not persistent (it will lose its state when
power is off). Generally, this memory is more expensive than persistent memory (such as on your disks or
on flash), but a computer requires this to execute programs. In a multiprogramming environment, memory
is to be shared between multiple processes and the operating system kernel.

Some of this module and the next module will introduce and explain paging and swapping. Paging and
swapping are mechanisms that help your system run programs and multiple processes that require more
RAM than is physically available by using slower memory (such as a disk partition) as temporary storage
for running processes. With computers now coming with larger and larger storage in RAM, swapping and
paging may not be as important (today, most computers come with at least 4 GB of memory, and it is
becoming more common for a system to have more than 4 GB — the system I just received for work
came with 16 GB of memory). However, it does seem that as memory increases, so does the memory
requirements for more complex and larger programs that run on the systems. So, even if swapping and
paging might seem to be on the way out, it will probably come back some day.

In this module, we examine basic memory management, swapping, and we will introduce the concept of
virtual memory (i.e. we will sneak a few topics from section 3.3 in here).

Basic Memory Management

The simplest model for memory management is simply monoprogramming. The operating system runs a
single program at a time and that program always occupies the same location in memory. Thus, the
executing image can be linked so that the actual physical memory locations are specified. Tanenbaum
doesn't discuss here what would happen if the program is larger than available memory; but he does
allude to this at the start of the discussion on virtual memory in section 3.3. In this case, the program can
be broken up into separate overlays, which either the OS or the application can load into memory when
necessary (wiping out the previous overlay, or at least part of it).

One of the important issues here is when we talk about loading a program into non-predetermined areas
of memory. When this occurs, the memory references in the process image itself can no longer be
absolute. One solution your text talks about, the base and limit registers, not only offers a solution to the
relocation issue, but also has the benefit of assuring that a process doesn't access or modify memory
outside its allocated partition.

Likewise, note Tanenbaum's discussion of the IBM 360 in section 3.1.1, where memory was split up into
common sized blocks, each with their own "Program Status Word". Let's see how this evolves into today's
memory management techniques as we continue our discussion.
Swapping

The rest of this module, and the remainder of our discussion of memory management (including next
week's module) will center on the related topics of Swapping, Paging, and Virtual Memory.

First, let’s introduce swapping. As processes move into memory, eventually the sum of the memory
requirements of the processes in memory may exceed available memory; plus, there may be processes
in memory which are blocked waiting for some resource that may not be available for a very long time
(e.g. a process waiting for input from the terminal when the user has left the office for an afternoon
meeting). In this case the a process called the "memory scheduler" (which could be called the "swapper")
takes a process from the "blocked" scheduling queue and moves it out of RAM onto secondary storage
(typically the hard disk). So, one distinction that will become important later is that the swapper moves an
entire process out from memory to disk. Note that this is the running image of the process; it is not as if
the process was terminated, and then later restarted.

The first examples of swapping shown in your text presume the processes reside in contiguous memory.
This presents some issues. First off, the processes may be in different memory locations at different times
after it is swapped out and then back in. Thus, the memory accesses must be able to be relocated.
Secondly, depending on where the processes go when they are brought into memory, fragmentation of
memory may result. In this case, the fragmentation can prevent a process from moving from the swap
area into memory, even though the sum of available memory could be much larger than the size of the
process in the swap area. Also, processes can change in size — a process' stack can naturally grow by
the process making function calls and allocating automatic variables. A process can also allocate global
or persistent memory from the 'heap'. Recall from Module 3 that the heap and stack usually grow toward
each other. Using a contiguous memory approach, the room available for growth (between the stack and
the heap) is usually pre-allocated. Use too much room here, and memory is wasted — not enough, and a
process might easily run out of memory in this area. If a process uses up its pre-allocated memory, what
should it do? If the stack can no longer grow, the process will likely be killed. If the heap can't grow, the
alloc() call will fail, and the process catch this failure and then can decide what to do. Or, alternatively, the
operating system could re-map the process into a larger area of memory, to grow the space between the
stack and the heap. However, that is an expensive process and is therefore rarely done.

Managing Free Memory

There are a couple of approaches in managing free memory.

• Bitmaps
• Linked Lists

And, there are several approaches in selecting the process to move into a free memory area:

• First Fit
• Next Fit
• Best Fit
• Worst Fit
• Quick Fit
Introduction to Virtual Memory

We will discuss virtual memory in depth in the next module, but I would like to introduce it in this module.
As an approach to memory management, swapping and the use of contiguous memory does present
some issues, as we have seen. An additional issue is a fairly straightforward one — what if a process
requires more memory than is physically present in the system? In other words, what if a process, when it
starts, requires 1GB of memory, and the system only has 512 MB of memory? That issue may seem a bit
silly, but in fact in the late 1970's a project called Macsyma at UC Berkeley was based in Lisp. Lisp
required a great deal of memory and was in fact one of the major drivers in implementing virtual memory
in UNIX. In an operating system that uses virtual memory, a process can automatically be broken up into
pages. Some of the pages of the process can be in main memory and some pages can be in the swap
area on secondary storage. Thus, using this approach it is possible to have a process be bigger than
physical memory.

Virtual memory wasn't invented in UNIX; it actually had its genesis back in the late 1960's. As the concept
evolved, hardware was developed to more efficiently implement virtual memory (as we will discuss in the
next module). Thus, when virtual memory was implemented in UNIX, hardware support for it (to some
degree) was already there in the VAX-11/780. (The native operating system on the VAX-11/780 was
VMS, which stood for "Virtual Memory System".)

Virtual memory is thus a way to provide a façade of contiguous memory, while underneath the memory is
managed in non-contiguous pages. Thus there are two memory references — the virtual address and the
physical address — to each memory location. Each page is handled pretty much as described above with
the use of the base and limit registers — the base is the physical location of the page, and the limit is
fixed (as pages are all of the same fixed size).

Other Resources

• http://dropsafe.crypticide.com/article/3848 — Interesting article on swapping on MacOSX