CS330 - Operating Systems
Memory Management, Address Binding, Swapping, Paging & Segmentation
Memory management is crucial for multiprogramming. The OS must:
Main memory and registers are the only storage CPU can access directly.
If check fails → Trap to OS (addressing error)
Programs must be brought into memory and placed within a process for execution.
| Binding Time | Description | Address Type | Flexibility |
|---|---|---|---|
| Compile Time | If memory location known a priori, absolute code can be generated | Absolute addresses | Must recompile if starting location changes |
| Load Time | Compiler generates relocatable code | Relocatable addresses | Final binding delayed until load time |
| Execution Time | Binding delayed until run time | Dynamic addresses | Process can move during execution |
Logical Address: Generated by CPU; also called virtual address
Physical Address: Address seen by memory unit
Logical and physical addresses are the same in compile-time and load-time schemes; different in execution-time scheme
Physical Address = Logical Address + Relocation Register
The user program deals with logical addresses; it never sees real physical addresses
A process can be swapped temporarily out of memory to backing store and then brought back for continued execution.
Swap Out / Swap In
Process size: 100MB
Backing store transfer rate: 50MB/sec
Transfer time = 100MB / 50MB/sec = 2 seconds
Total swap time (out + in) = 4 seconds
Main memory is divided into two partitions:
Allocate the first hole that is big enough
✓ Fast
✗ May create small fragments
Allocate the smallest hole that is big enough
✓ Leaves larger holes
✗ Slower, creates tiny fragments
Allocate the largest hole
✓ May reduce fragmentation
✗ Poor utilization
Note: First-fit and best-fit are generally better than worst-fit in terms of speed and storage utilization
Total memory space exists to satisfy request, but it is not contiguous
Problem: Can't allocate 150K even though total free = 150K
Solution: Compaction or Paging
Allocated memory may be larger than requested memory
Example: Process needs 18K, gets 20K block
Occurs in: Fixed partition schemes, Paging
Given N allocated blocks, another N/2 blocks will be lost to external fragmentation
One-third of memory may be unusable!
Paging allows physical address space of a process to be noncontiguous
Small, fast-lookup hardware cache containing page-table entries
EAT = α × (TLB_access + Memory_access) + (1-α) × (TLB_access + 2×Memory_access)
Where α = TLB hit ratio
Example: Memory access = 100ns, TLB access = 20ns, Hit ratio = 80%
EAT = 0.80 × 120 + 0.20 × 220 = 96 + 44 = 140ns
| Structure Type | Description | Advantage |
|---|---|---|
| Hierarchical | Two or more levels of page tables | Reduces memory overhead for sparse address spaces |
| Hashed | Hash table with linked list for collisions | Good for sparse address spaces > 32 bits |
| Inverted | One entry per physical frame | Decreases memory needed for page tables |
Valid/Invalid Bit: Indicates if page is in process's logical address space
Memory-management scheme that supports user view of memory
A program is a collection of segments:
| Segment | Base | Limit | Description |
|---|---|---|---|
| 0 | 1400 | 1000 | Main Program |
| 1 | 6300 | 400 | Subroutine |
| 2 | 4300 | 400 | Stack |
| 3 | 3200 | 1100 | Data Segment |
| 4 | 4700 | 1000 | Symbol Table |
| Aspect | Paging | Segmentation |
|---|---|---|
| Division | Fixed-size pages | Variable-size segments |
| User View | Invisible to programmer | Visible to programmer |
| External Fragmentation | No | Yes |
| Internal Fragmentation | Yes (last page) | No |
| Sharing | Difficult | Easy (logical units) |
| Protection | Page level | Segment level |
Combines advantages of both schemes:
Supports both segmentation and paging
Logical address → Linear address (via segmentation) → Physical address (via paging)
Given: Page size = 1KB (1024 bytes), Logical address = 3085
Given: 256 pages with 4KB page size, mapped to 64 frames
Given: Process size = 72,766 bytes, Page size = 2048 bytes
Q1. Which memory allocation strategy is generally fastest?
Answer: First-fit (searches from beginning and allocates first suitable hole)
Q2. External fragmentation occurs in:
Answer: Variable-size contiguous allocation and pure segmentation
Q3. Internal fragmentation occurs in:
Answer: Fixed-size partitioning and pure paging
Q4. TLB stands for:
Answer: Translation Look-aside Buffer
Q5. Compare paging and segmentation with respect to memory overhead.
Answer:
Paging: Requires one entry per page. For large address spaces, page tables can be huge.
Segmentation: Requires only two registers per segment (base and limit). Much less overhead.
Q6. Why do mobile operating systems like iOS and Android not support swapping?
Answer:
Q7. Calculate physical address for logical address (1, 500) in paging system:
Page size = 1024 bytes, Page 1 mapped to Frame 6
| Term | Definition |
|---|---|
| Logical Address | Address generated by CPU; virtual address |
| Physical Address | Address seen by memory unit |
| MMU | Memory Management Unit - hardware for address translation |
| Page | Fixed-size block in logical memory |
| Frame | Fixed-size block in physical memory |
| Page Table | Data structure for page-to-frame mapping |
| TLB | Translation Look-aside Buffer - cache for page table |
| Segment | Logical unit in user's view (code, data, stack) |
| External Fragmentation | Free memory exists but not contiguous |
| Internal Fragmentation | Allocated memory larger than needed |
| Compaction | Shuffle memory to place free memory together |
| Swapping | Move process between main memory and disk |
| Base Register | Holds smallest legal physical address |
| Limit Register | Contains range of logical addresses |
[Insert base and limit register protection diagram]
[Insert TLB and page table interaction diagram]
[Insert first-fit, best-fit, worst-fit visual comparison]
[Insert logical to physical address mapping in segmentation]
Note: Please provide the actual diagrams from your course materials to replace these placeholders.