- Authors
- Name
- Youngju Kim
- @fjvbn20031
Background
Basic Concepts
The only storage directly accessible by the CPU is registers and main memory. Data on disk must be loaded into memory before the CPU can process it.
Memory access takes time, so a cache is placed between the CPU and memory to bridge the speed gap.
CPU <-> Registers (~1ns) <-> Cache (~10ns) <-> Main Memory (~100ns)
Address Binding
The process of translating addresses used by a program into actual memory addresses. There are three types based on binding time.
[Address Binding Timing]
1. Compile-time Binding
- Memory location determined at compile time
- Recompilation needed if location changes
- Example: MS-DOS .COM programs
2. Load-time Binding
- Address determined when loading program into memory
- Uses relocatable code
- Address cannot change after loading
3. Execution-time Binding (Modern OS)
- Addresses dynamically translated during execution
- Requires MMU (Memory Management Unit) hardware
- Processes can be moved within memory
Logical and Physical Addresses
- Logical Address: Address generated by the CPU. Also called virtual address
- Physical Address: Actual address of memory hardware
[Address Translation via MMU]
CPU --[Logical addr: 346]--> MMU --[Physical addr: 14346]--> Memory
|
Relocation Register
(base value: 14000)
Physical address = Logical address + Relocation register value
346 + 14000 = 14346
User programs deal only with logical addresses and cannot see physical addresses directly.
Dynamic Loading and Dynamic Linking
Dynamic Loading: Loads routines into memory only when they are called. Unused routines do not occupy memory, improving memory utilization.
Dynamic Linking: Links libraries at runtime.
[Static Linking vs Dynamic Linking]
Static Linking:
Program A: [code + libc copy] -- 50MB
Program B: [code + libc copy] -- 50MB
Total memory: 100MB
Dynamic Linking (Shared Libraries):
Program A: [code + libc ref] -- 10MB
Program B: [code + libc ref] -- 10MB
libc.so: [shared library] -- 40MB
Total memory: 60MB
Linux: .so files (Shared Object)
Windows: .dll files (Dynamic-Link Library)
Contiguous Memory Allocation
The simplest memory management approach, placing each process in a contiguous memory region.
Memory Protection
[Base Register and Limit Register]
Base Limit
| |
v v
+-------+=======================+-------+
| OS | Process P's region | Other |
+-------+=======================+-------+
0 300040 420940
For address addr generated by CPU:
if (addr >= base && addr < base + limit)
Access allowed -> Physical memory access
else
Trap raised -> OS handles error
Memory Allocation Strategies
Methods for allocating memory to processes from the free space (hole) list.
[Memory Allocation Example]
Initial state:
|---OS---|--P1--|-------free-------|--P3--|---free---|
Allocation strategies:
1. First Fit: Allocate in the first sufficiently large hole
Pros: Fast
2. Best Fit: Allocate in the smallest sufficient hole
Pros: Creates small remaining space
Cons: Full search needed, creates very small fragments
3. Worst Fit: Allocate in the largest hole
Pros: Remaining space is large enough to reuse
Cons: Full search needed
Fragmentation
[External vs Internal Fragmentation]
External Fragmentation:
|P1| free |P2| free |P3| free |P4|
100KB 50KB 80KB
Total free space: 230KB, but cannot load a 200KB process!
(Not contiguous)
Solution: Compaction - Move processes to one end
|P1|P2|P3|P4|-----230KB free-----|
Internal Fragmentation:
When memory is allocated in fixed-size blocks
If process is smaller than block, space is wasted inside
Process size: 18,462 bytes
Block size: 20,000 bytes
Internal fragmentation: 1,538 bytes wasted
Paging
Paging is a technique that allocates logical address space non-contiguously, completely eliminating external fragmentation.
Basic Concepts
- Page: Fixed-size blocks of logical memory
- Frame: Same-size blocks of physical memory
- Page Table: Table mapping pages to frames
[Paging Address Translation]
Logical address = Page number(p) + Page offset(d)
Example: Page size 4KB (2^12), 32-bit logical address
Upper 20 bits = Page number (max 2^20 = 1M pages)
Lower 12 bits = Offset (0 ~ 4095)
+--------+--------+
| p (20) | d (12) | Logical address
+--------+--------+
|
v
[Page Table]
p -> f (frame number)
|
v
+--------+--------+
| f (20) | d (12) | Physical address
+--------+--------+
[Paging Example]
Logical Memory (4 pages): Physical Memory (8 frames):
+------+ +------+
|Page 0| ----+ | | Frame 0
+------+ | +------+
|Page 1| --+ | |Page 2| Frame 1
+------+ | | +------+
|Page 2| -+| | | | Frame 2
+------+ || | +------+
|Page 3| || +------------>|Page 0| Frame 3
+------+ || +------+
|+--------------->|Page 1| Frame 4
| +------+
+---------------->|Page 2| Frame 5 (X)
+------+
|Page 3| Frame 6
+------+
| | Frame 7
+------+
Page Table:
Page 0 -> Frame 3
Page 1 -> Frame 4
Page 2 -> Frame 1
Page 3 -> Frame 6
TLB (Translation Lookaside Buffer)
Looking up the page table in memory every time doubles memory accesses. The TLB serves as a cache for the page table.
[Address Translation via TLB]
CPU --logical addr(p, d)--> TLB lookup
|
+---------------+---------------+
| |
TLB Hit TLB Miss
(fast, ~1ns) (slow)
| |
Get frame f Page table lookup
| Get frame f
| Add to TLB
| |
+---------------+---------------+
|
Access memory with
physical addr (f, d)
Effective Access Time (EAT) calculation:
TLB hit rate = 99% (typical)
Memory access time = 100ns
TLB access time = 10ns
EAT = 0.99 * (10 + 100) + 0.01 * (10 + 100 + 100)
= 0.99 * 110 + 0.01 * 210
= 108.9 + 2.1
= 111ns
Without TLB: 200ns (2 memory accesses)
With TLB: 111ns (44.5% improvement)
Page Table Structures
When a process's address space is large (e.g., 64-bit), the page table itself becomes very large.
Hierarchical Page Table (Multi-level Page Table)
[Two-level Page Table]
32-bit address, 4KB pages:
+--------+--------+--------+
| p1(10) | p2(10) | d(12) |
+--------+--------+--------+
Outer Page Table (Level 1)
+---+
| 0 |---> Level 2 Table A
+---+ +---+
| 1 |--+ | 0 |--> Frame number
+---+ | +---+
| 2 | | | 1 |--> Frame number
+---+ | +---+
| | ...|
| +---+
|
+-> Level 2 Table B
+---+
| 0 |--> Frame number
+---+
| ...|
+---+
Advantage: Level 2 tables for unused regions are not created
-> Memory savings
Hashed Page Table
[Hashed Page Table]
Input logical page number p to hash function
-> Maps to hash table slot
-> Search chain (linked list) for p
-> Return corresponding frame number
Useful for very large address spaces like 64-bit
Inverted Page Table
[Inverted Page Table]
Regular page table: One per process (logical -> physical)
Inverted page table: One for the system (physical frame -> process, page)
One entry for each physical memory frame:
Frame 0: (PID=5, Page=3)
Frame 1: (PID=2, Page=7)
Frame 2: (empty)
Frame 3: (PID=5, Page=0)
...
Advantage: Table size proportional to physical memory
Disadvantage: Full table search needed for translation (solved with hashing)
Swapping
A technique that moves all or part of a process to disk to free memory.
[Standard Swapping]
Main Memory Backing Store (Disk)
+---------+ +---------+
| OS | | |
+---------+ | P2's |
| P1 | <-- swap in --- | image |
+---------+ | |
| P3 | --- swap out --> | |
+---------+ +---------+
| free |
+---------+
Modern systems swap at page granularity
rather than swapping entire processes
[Page-level Swapping]
Only specific pages of a process are moved to disk:
- Swap out pages not used for a long time
- Swap in again when needed
- Foundation technology for virtual memory
Memory Protection
Memory protection in a paging environment is implemented by adding protection bits to page table entries.
[Page Table Entry Structure]
+-------+-----+-----+-----+-------+
| Frame | Valid| Read| Write| Exec |
| Number| Bit | OK | OK | OK |
+-------+-----+-----+-----+-------+
Valid bit:
1 = This page belongs to the process's logical address space
0 = Invalid page (trap raised on access)
Protection bits:
Write attempt on read-only page -> Hardware trap
Code pages: Allow execute only, deny writes
// Memory protection example: mprotect system call
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
void segfault_handler(int sig) {
printf("Segmentation fault! Attempted access to protected memory\n");
exit(1);
}
int main() {
signal(SIGSEGV, segfault_handler);
// Allocate memory in page-size units
size_t page_size = getpagesize(); // Usually 4096
void *ptr = aligned_alloc(page_size, page_size);
// Write data
*(int *)ptr = 42;
printf("Value: %d\n", *(int *)ptr);
// Protect memory as read-only
mprotect(ptr, page_size, PROT_READ);
// Write attempt -> Segmentation fault!
*(int *)ptr = 100;
free(ptr);
return 0;
}
Summary
Main memory management is a core function for providing efficient and safe memory space to processes. The MMU translates logical addresses to physical addresses, paging eliminates external fragmentation, and the TLB ensures address translation performance. Hierarchical page tables and inverted page tables efficiently manage large address spaces, and protection bits ensure memory isolation between processes.