Absolute code
If the final location is known, the compiler emits absolute addresses. Moving the program requires recompilation.
Least flexible
PART 3 • MEMORY & STORAGE
Translate Every Address and Place Every Process Safely
Follow a program address from CPU to RAM, enforce protection with bounds, compare contiguous placement strategies and understand why paging removes external fragmentation.
BY THE END, YOU CAN
Reason about memory placement
- Separate logical and physical addresses.
- Explain compile-, load- and execution-time binding.
- Translate base/limit and paged addresses.
- Calculate internal and external fragmentation.
- Compare paging with segmentation.
A Program Uses Addresses before It Knows Its Final RAM Location
Address binding maps program references to memory locations. The later binding occurs, the more freely the OS can move a process.
Relocatable code
The compiler leaves relative addresses; the loader selects a physical region and completes relocation.
Move before executionDynamic relocation
Hardware translates every reference while the program runs, allowing movement and virtual memory.
Most flexible; requires MMU support
CPU logical address
→
MMU translation + protection
→
Physical memory address
Calculate the Address, Then Check Protection
Switch between base/limit relocation, paging and segmentation. Each mode shows the formula and rejects an invalid reference rather than silently translating it.
Enter a logical address
The formula and protection decision will appear here.
—
One Process, One Continuous Physical Region
Take the first sufficient hole
Search from the beginning and stop immediately when a large enough hole appears.
Fast search; early memory may fragmentTake the smallest sufficient hole
Search all suitable holes and leave the smallest immediate remainder.
May create many tiny unusable holesTake the largest hole
Preserve medium-size holes by splitting the largest available region.
Large holes disappear quicklyExternal fragmentation
Total free memory may be sufficient, but it is divided into non-contiguous holes and no single hole fits the request.
Compaction can combine holes, but moving memory costs time.Internal fragmentation
An allocated fixed-size unit is larger than the request, so unused space remains inside the assigned region.
Paging can create waste in the final page/frame.Compare First Fit, Best Fit and Worst Fit on the Same Holes
Choose a dataset, algorithm and process size. The lab highlights the selected hole and calculates the remaining holes.
Ready to allocate
Select an algorithm and process size.
Paging Separates Logical Pages from Physical Frames
page number p
offset d
p = floor(address / page size)
d = address mod page size
frame number f
same offset d
physical = f × frame size + d
No external fragmentation
A process’s frames need not be adjacent, so any free frame can hold any page.
Possible internal fragmentation
The last allocated page may not be completely used.
Page-table overhead
Each process needs mappings and metadata; large address spaces require structured page tables.
TLB acceleration
A Translation Lookaside Buffer caches recent page-table entries to reduce translation cost.
Segmentation Matches the Program’s Own Structure
Segment 0 • code
Segment 1 • data
Segment 2 • heap
Segment 3 • stack
Logical address = ⟨segment, offset⟩
The segment table stores a base and limit for each segment. If offset < limit, physical address = base + offset; otherwise the reference traps.
- Natural protection per logical unit
- Easy sharing of a code segment
- Variable sizes cause external fragmentation
- Segments can grow differently
Paging and Segmentation Solve Different Problems
| Question | Paging | Segmentation |
|---|---|---|
| Unit size | Fixed-size pages and frames | Variable-size logical segments |
| Programmer view | Usually transparent | Matches code, data, stack and modules |
| Fragmentation | Internal possible; no external | External possible |
| Address parts | Page number + offset | Segment number + offset |
| Protection/sharing | Per page | Natural per logical segment |
| Modern use | Dominant basis of virtual memory | Ideas often combined with paging/protection regions |
Ten Misconception-Specific Checks
Each option explains the exact address or fragmentation error.
Answered correctly: 0 of 10
University and Placement Questions
- Logical versus physical address?
- Define relocation.
- Internal versus external fragmentation?
- What is a page table?
- What does a TLB store?
- Explain address binding.
- Compare placement algorithms.
- Translate a paged address.
- Explain segmentation.
- Compare paging and segmentation.
- Why does paging remove external fragmentation?
- Why is the offset preserved?
- Can paging waste memory?
- What happens on a TLB miss?
- Why use multi-level page tables?
Show a strong answer: “Paging address translation”
- Divide the logical address by page size to obtain page number and offset.
- Validate the page number and page-table entry.
- Read the frame number from the page table, possibly through the TLB.
- Combine frame number with the unchanged offset.
- Physical address = frame × frame size + offset.
LEVEL 8 SUMMARY
You Can Now Explain Where a Program Address Goes
- Binding connects symbolic/logical references to physical placement.
- Base and limit provide relocation plus bounds protection.
- Contiguous allocation can suffer external fragmentation.
- Paging maps fixed-size pages to frames and preserves the offset.
- Segmentation represents variable-size logical program units.
COURSE CHECKPOINT
Mark Level 8 after you can translate one paged address and distinguish internal from external fragmentation.
Saved only in this browser.