Memory Management
Lecture Outline
Introduction: The Memory Management Problem
The Memory Abstraction: Address Spaces
Fundamental Concepts:
Address Binding
Logical vs. Physical Addresses
The Memory Management Unit (MMU)
Basic Management Schemes:
Fixed and Dynamic Partitions
Swapping
Free Memory Management:
Bitmaps
Linked Lists
Allocation Algorithms
Fragmentation
Introduction to the Memory Management Problem
Main memory (RAM) is a critical, scarce, and fast resource. It is the only large
storage area that the CPU can access directly.
The Memory Manager is the part of the operating system responsible for:
Tracking which parts of memory are in use and which are free.
Allocating memory to processes when they need it.
Deallocating memory when processes terminate.
Protecting processes from each other, ensuring a process cannot access the
memory of another process.
The Memory Hierarchy
To be executed, a program must be in main memory.
➢ Registers (Fastest, Smallest)
➢ L1 Cache
➢ L2 Cache
➢ Main Memory (RAM) (Our focus today)
➢ Magnetic Disk / SSD (Slowest, Largest)
The memory manager handles the movement of data
and processes between Main Memory and Disk.
Logical vs. Physical Addresses
Logical Address (or Virtual Address):
➢ An address generated by the CPU.
➢ This is the address the program sees (e.g., "load from address 1000").
➢ Part of the process's address space.
Physical Address:
➢ An address seen by the main memory hardware.
➢ This is the actual address (the specific RAM chip) where the data is stored.
➢ The mapping from logical to physical addresses is the central task of memory
management.
No Memory Abstraction
Before we had memory managers, the earliest and simplest model was to have no
abstraction at all.
➢ In this model, the logical addresses generated by the program are the physical
addresses sent to memory.
➢ Only one process can be in memory at a time (monoprogramming).
➢ The OS typically resides in a fixed portion of memory (e.g., low RAM), and the single
user process gets the rest.
No Memory Abstraction
Three simple ways of organizing memory with an operating system and one user process.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
No Memory Abstraction
How it works: A program is loaded at a specific physical address (e.g., 0x1000).
When the CPU executes JUMP 0x2040, it jumps directly to physical address 0x2040.
Disadvantages:
➢ No Protection: A malicious or buggy user program can easily overwrite the operating
system, crashing the entire computer.
➢ No Concurrency: To run a second program, the first one must be completely
terminated, and its memory space overwritten.
➢ Inflexible: The program must be loaded at the exact address it was compiled for.
No Memory Abstraction
Illustration of the relocation problem.
(a) A 16-KB program.
(b) Another 16-KB program.
(c) The two programs loaded consecutively into memory.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The Memory Abstraction: Address Spaces
To make memory management easier, the OS provides an abstraction to each
process: the Address Space.
An address space is the set of all logical addresses that a process can generate.
From the process's point of view, it has its own private memory, starting at address 0 and
going up to some maximum.
The OS's job is to map this "fake" logical address space onto the real physical memory.
Address Binding
When does a symbolic memory address (like a variable name x) get bound to a real physical address?
Compile Time:
➢ If you know exactly where the process will live in memory, the compiler can generate absolute physical
addresses.
➢ Problem: You must recompile the code if the load address changes. Very inflexible.
Load Time:
➢ The compiler generates relocatable code (addresses relative to 0).
➢ When the program is loaded, the OS (loader) determines the base physical address and "relocates" all
logical addresses.
➢ Problem: The process cannot be moved in memory once it has started running.
Execution Time (Runtime):
➢ This is the modern approach.
➢ Address binding is delayed until the program is actually running.
➢ Requires hardware support (an MMU).
➢ Advantage: The OS can move the process around in physical memory while it is running.
The MMU (Memory Management Unit)
The MMU is a hardware chip that translates logical addresses into physical
addresses at runtime.
➢ It sits between the CPU and main memory.
➢ The CPU sends a logical address to the MMU.
➢ The MMU looks up its mapping and sends a physical address to the
memory bus.
➢ This happens on every single memory access.
The MMU (Memory Management Unit)
The position and function of the MMU.
Here the MMU is shown as being a part
of the CPU chip because it commonly is nowadays.
However, logically it could be a separate chip
and was years ago.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
The MMU (Memory Management Unit)
The simplest form of an MMU uses two hardware registers:
➢ Base Register: Stores the starting physical address of the process.
➢ Limit Register: Stores the size of the process's logical address space.
Example:
➢ CPU generates a logical address (e.g., 2000).
➢ MMU checks: Is logical_addr < limit_reg?
➢ Is 2000 < 5000? Yes. (If no, send a "segmentation fault" trap to the OS).
➢ MMU computes: Physical_addr = base_reg + logical_addr
➢ Physical_addr = 100000 + 2000 = 102000
➢ The address 102000 is sent to the memory bus.
The MMU (Memory Management Unit)
Base and limit registers can be used to give
each process a separate address space.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Basic Management Schemes (Fixed Partitions)
One of the oldest and simplest schemes.
➢ Memory is divided into a fixed number of partitions.
➢ Each partition can hold exactly one process.
➢ Static: Partition sizes are set at boot time and do not change.
Problem: A 20K process in a 32K partition wastes 12K. A 33K process
can't run at all.
Basic Management Schemes (Dynamic Partitions)
A more flexible scheme.
➢ The OS maintains a list of which parts of memory are occupied and which
are free (called holes).
➢ When a process arrives, the OS searches for a hole that is large enough for
the process.
➢ The hole is then split into two: one part for the process, and a new, smaller
hole.
➢ When a process terminates, its memory is returned and merged with any
adjacent holes.
Example: (Dynamic Partitions)
➢ OS has 640K. Process A (200K) arrives.
➢ OS has a 200K block (A) and a 440K hole.
➢ Process B (300K) arrives.
➢ OS has 200K(A), 300K(B), and a 140K hole.
➢ Process A terminates.
➢ OS has a 200K hole, 300K(B), and a 140K hole.
➢ Process C (130K) arrives...
➢ Where does it go? This is the "Allocation Algorithm" problem.
Dynamic Partitions
Memory allocation changes as processes come into memory and leave it.
The shaded regions are unused memory.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Swapping
What if there's no hole big enough?
➢ If all of memory is full, or the holes are all too small, no new processes can
start.
➢ Swapping: The OS can temporarily move an entire process from main
memory to a special backing store (a fast disk).
➢ This frees up memory (a new hole) for another process to be "swapped in"
from the disk.
Example: Swapping
➢ Memory is full with processes A, B, and C.
➢ Process D wants to run.
➢ The OS decides to swap out Process A. It copies A's entire address space to
the backing store.
➢ The memory used by A becomes a free hole.
➢ The OS swaps in Process D, loading it into the new hole.
➢ Later, when D finishes or blocks, the OS can swap A back in.
Swapping Issues
➢ Context-Switch Time: Swapping is extremely slow. Disk I/O is 1000s of
times slower than memory access. The time to move a 100MB process can be
very high.
➢ Growing Processes: What if a process needs to grow its stack or heap? If
it's adjacent to another process, it can't. The OS might have to swap it out
and find a bigger hole to swap it back into.
Memory Configurations
(a) Allocating space for a growing data segment.
(b) Allocating space for a growing stack and a growing data segment.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Free Memory Management
Now that we have dynamic partitions, the OS must have a way to track the free
memory "holes."
➢ Two common methods:
Bitmaps
Linked Lists
Free Memory Management (Bitmaps)
Memory is divided into fixed-size allocation units (e.g., 4KB).
The OS keeps a bitmap (an array of bits) with one bit for each unit.
➢ 1 = Unit is in use
➢ 0 = Unit is free
A 4GB memory with 4KB units needs 1,048,576 bits (or 128KB) for the bitmap.
Free Memory Management (Bitmaps)
Pros:
➢ Simple to implement.
➢ Efficient for tracking a fixed-size chunk of memory.
Cons:
➢ Searching is slow. To find a hole for a 1MB process (256 units), the OS must
search the bitmap for 256 consecutive 0s.
➢ Overhead: A small unit size is good for reducing waste, but it makes the
bitmap larger.
Free Memory Management (Linked Lists)
The OS maintains a linked list of segments (allocated blocks and free holes).
Each node in the list specifies:
➢ Whether it's a Process (P) or a Hole (H).
➢ The starting address.
➢ The length (size).
➢ A pointer to the next node.
Free Memory Management (Linked Lists)
Example: A visual representation of memory:
[P: 0, 100K] -> [H: 100K, 20K] -> [P: 120K, 50K] -> [H: 170K, 30K]
This means:
➢ Process 1 is at 0K (size 100K)
➢ Hole 1 is at 100K (size 20K)
➢ Process 2 is at 120K (size 50K)
➢ Hole 2 is at 170K (size 30K)
Free Memory Management (Linked Lists)
Example: A visual representation of memory:
[P: 0, 100K] -> [H: 100K, 20K] -> [P: 120K, 50K] -> [H: 170K, 30K]
What happens when Process 2 (at 120K) terminates?
Its 50K segment becomes a new hole.
The OS must check its neighbors in the list.
It sees it is adjacent to Hole 1 (before) and Hole 2 (after).
It merges all three segments into one new, large hole.
[P: 0, 100K] -> [H: 100K, 100K] (The new hole is at 100K with size 20K + 50K + 30K
= 100K)
Free Memory Management
(a) A part of memory with five processes and three holes. The tick marks show the memory allocation units.
The shaded regions (0 in the bitmap) are free.
(b) The corresponding bitmap. (c) The same information as a list.
Tanenbaum & Bo, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
Allocation Algorithms
We have a linked list of holes.
A new process arrives and needs N bytes.
Which hole should we give it?
This choice dramatically affects memory performance.
Allocation Algorithms (First Fit)
Algorithm: Scan the linked list from the beginning. Allocate the first hole that is big
enough.
Example: If we need 16KB, and the holes are [10K, 20K, 15K, 30K], First Fit
chooses the 20K hole.
Pros: Very fast.
Cons: Tends to create small, useless holes at the beginning of the list.
Allocation Algorithms (Next Fit)
Algorithm: Same as First Fit, but it keeps a pointer to where it last left off.
Example: After allocating the 20K hole, the pointer stays there. The next search
starts from the 15K hole.
Pros: Slightly worse performance than First Fit, but spreads usage across memory,
avoiding heavy fragmentation at the start.
Allocation Algorithms (Best Fit)
Algorithm: Scan the entire list of holes. Allocate the smallest hole that is big
enough.
Example: If we need 16KB, and the holes are [10K, 20K, 17K, 30K], Best Fit
chooses the 17K hole.
Pros: Wastes the least memory.
Cons: Slower, as it must search the whole list. Produces tiny, unusable "leftover"
holes.
Allocation Algorithms (Worst Fit)
Algorithm: Scan the entire list. Allocate the largest hole.
Example: If we need 16KB, and holes are [10K, 20K, 17K, 30K], Worst Fit chooses
the 30K hole.
Pros: The leftover hole (14K) is large and likely to be useful.
Cons: Slower (like Best Fit). Tends to quickly "destroy" large holes, making it hard
to run large processes.
Allocation Algorithms (Quick Fit)
Algorithm: Maintain separate linked lists for common hole sizes.
Example: One list for 4K holes, one for 8K, one for 12K, etc.
Pros: Extremely fast allocation. No searching needed.
Cons: Merging holes upon deallocation is very complex.
The Consequence of Allocation
Fragmentation is the problem of "wasted" memory. After a while, memory
becomes broken up into many small, unusable pieces.
There are two types:
➢ External Fragmentation
➢ Internal Fragmentation
External Fragmentation
Definition: Total free memory exists to satisfy a request, but it is not contiguous
(it's not in one single block).
Cause: Dynamic partition allocation (First Fit, Best Fit, etc.).
Example: We have 50K of free RAM, but it's split into five 10K holes. A request for
a 20K process must be denied.
Internal Fragmentation
Definition: Memory that is inside an allocated partition but is not being used.
Cause: Using fixed-size allocation units.
Example: We allocate memory in 4KB blocks. A process requests 5KB. The OS
gives it two blocks (8KB total). The extra 3KB inside the second block is "wasted." It
cannot be given to any other process.
External vs. Internal Fragmentation
External: The "wasted" space is outside any allocated partition.
Internal: The "wasted" space is inside an allocated partition.
Solution to External Fragmentation: Compaction
If memory becomes too fragmented, the OS can perform compaction.
Action: Stop all running processes. Shuffle all the allocated blocks to one end of
memory, and merge all the free holes into one, large, contiguous hole.
Problem: This is extremely time-consuming. It requires moving gigabytes of data.
It's generally not done in modern, real-time systems.
The Fundamental Problem
All the schemes we've seen today (Base/Limit, Swapping, Dynamic Partitions) share a
few problems:
The entire process must be in physical memory to run.
The process's address space cannot be larger than the physical RAM.
They all suffer from external fragmentation (except fixed partitions).
What if we could break this rule?
What if a process could be larger than physical RAM?
What if we only loaded the parts of the process we needed right now?
What if the process's memory didn't even have to be contiguous?