Introduction to Memory Management

Space v. Time Multiplexing

Time multiplexing: sharing a resource by dividing up access to it over time.

Space multiplexing: sharing a resource by dividing it into smaller pieces.

Memory allocation happens in several steps:

A process requests large chunks of memory from the OS kernel…
…and then divides available memory up using a process-level allocation library (such as malloc).

You’re probably more familiar with the second step, but we’re going to focus on the first. (Although allocators are fascinating and still an area of active research…)

How do processes know where their code and data is located?

int data[128];
...
data[5] = 8; // Where the heck is data[5]?
...
result = foo(data[5]); // Where the heck is foo?

Fragmentation: when a request for contiguous memory fails despite the fact that there is enough unused memory available (on the system).

Note that it is not always feasible to split data structures across multiple pieces of discontiguous memory:

int data[10240]; // I had better be contiguous.

Limited to the amount of physical memory on the machine.
Potentially discontiguous allocations.
Potential for fragmentation to reduce allocation efficiency.
Can I enforce my allocations?
- Not without checking every memory access. Way too slow, but hardware could help…
Can I safely reclaim unused memory?
- Leads to increased discontiguity and suffers from the same enforcement problem.

Grant: the kernel should be able to allocate memory to processes statically (at startup) and dynamically (as needed).
Enforce: the kernel should be able to enforce memory allocations efficiently.
Reclaim: the kernel should be able to repurpose unused memory without destroying its contents.
Revoke: the kernel should be able to stop a process from using memory that it was previously allocated.

We provide every process with an identical view of memory that makes it appear:

Figure 2. The Address Space

Figure 3. The Address Space

Figure 4. The Address Space

Figure 5. The Address Space

Figure 6. The Address Space

The uniformity of address spaces simplifies process layout:

Process layout is specified by the Executable and Linker Format (ELF) file. (Remember ELF?)
Some layout is the function of convention.
Example: why not load the code at 0x0?
- To catch possibly the most common programmer error: NULL pointer problems!
- Leaving a large portion of the process address space starting at 0x0 empty allows the kernel to catch these errors, including offsets against NULL caused by NULL structures:

struct bar * foo = NULL;
foo->bar = 10;