Unit 3: Memory management
Operating System notes · PTU syllabus (PGCA1903)
On this page
Unit summary
Memory management places programs in memory, protects them and lets them be larger than RAM. This unit covers address binding, dynamic linking and loading, contiguous and non-contiguous allocation, fragmentation, paging, segmentation, virtual memory and demand paging, page replacement algorithms, frame allocation and thrashing.
After this unit you can
- Explain address binding, dynamic loading and linking
- Compare contiguous and non-contiguous allocation and fragmentation
- Translate addresses with paging and segmentation
- Apply page replacement algorithms and explain frame allocation and thrashing
PTU syllabus topics
- Address binding
- dynamic linking and loading
- contiguous and non-contiguous memory allocation
- fragmentation types
- paging
- segmentation
- virtual memory and demand paging
- page replacement algorithms
- frame allocation
- thrashing
FIFO
Oldest page in memory
Simple; suffers Belady's anomaly
Optimal
Page not used for the longest time ahead
Best possible; needs the future
LRU
Least recently used page
Close to optimal; widely used
LFU
Least frequently used page
Can keep old heavy pages too long
Topic 1
Address binding, dynamic loading and dynamic linking
- Address binding: mapping program addresses to memory addresses at compile time (absolute code), load time (relocatable code) or execution time (dynamic, using an MMU).
- Relocation: adjusting addresses when a program is loaded at a different location — relocation register adds a base value.
- Loading: static loading (whole program before execution) vs dynamic loading (routines loaded when called).
- Linking: static linking (libraries copied into the executable) vs dynamic linking (shared libraries — .dll, .so — linked at run time).
Topic 2
Logical and physical addresses, swapping
A logical address is generated by the CPU; a physical address is the actual location in memory. The Memory Management Unit (MMU) maps logical to physical addresses at run time, for example by adding a relocation (base) register value. Swapping temporarily moves a process from memory to disk (backing store) and back, so that more processes can run than fit in memory at once.
Topic 3
Contiguous allocation and fragmentation
Partitions
Memory divided into fixed-size parts in advance
Created to fit each process as it arrives
Fragmentation
Internal
External
Degree of multiprogramming
Limited by the number of partitions
Flexible
Placement strategies for variable partitions: first fit (first hole big enough — fast), best fit (smallest hole big enough — least leftover), worst fit (largest hole).
- Internal fragmentation: wasted space inside an allocated partition.
- External fragmentation: enough total free memory exists, but not in one contiguous block. Compaction shuffles processes together to create one large free block.
Placement
Whole process in one block
Process spread over many blocks (pages or segments)
Fragmentation
External fragmentation; compaction needed
Paging removes external fragmentation (some internal)
Address translation
Base and limit registers
Page or segment tables
Example
MFT, MVT
Paging, segmentation
Topic 4
Paging and segmentation
Paging divides logical memory into fixed-size pages and physical memory into frames of the same size. A page table maps each page to a frame, so a process need not be contiguous. Paging removes external fragmentation.
- Logical address = (page number p, offset d); physical address = frame number × page size + d.
Segmentation divides a program into variable-size logical segments (code, data, stack). A segment table stores each segment's base and limit.
Unit
Fixed-size pages
Variable-size segments
View
Physical, invisible to the programmer
Logical, matches program structure
Fragmentation
Internal (last page)
External
Table
Page table
Segment table with base and limit
Logical address split
Page number = address ÷ page size; offset = address mod page size
Physical address
Frame number × page size + offset
Effective access time with TLB
EAT = h (t + m) + (1 − h)(t + 2m), with hit ratio h, TLB time t and memory time m
Example
Page size 1 KB, logical address 3,100: page 3, offset 28. If page 3 is in frame 7: physical address = 7 × 1024 + 28 = 7,196.
Topic 5
Virtual memory, demand paging and page replacement
Virtual memory lets a process run even if only part of it is in memory. Demand paging loads a page only when it is needed; accessing a page not in memory causes a page fault.
FIFO
The oldest page in memory
Simple; Belady's anomaly possible
Optimal
The page not needed for the longest time
Lowest faults; needs future knowledge
LRU
The least recently used page
Good approximation of optimal
Example
Reference string 7, 0, 1, 2, 0, 3, 0, 4 with 3 frames under FIFO gives 7 page faults: 7, 0, 1, 2, 3, 0, 4 (only the 5th reference, 0, is a hit).
Frame allocation can be equal or proportional to process size. Thrashing happens when processes have too few frames and spend more time paging than executing; it is controlled with the working-set model or by reducing multiprogramming.
Example
Reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 3 frames: FIFO gives 10 page faults; LRU 9; optimal 7.
Topic 6
Allocation of frames
Equal allocation
m frames ÷ n processes each
Simple; ignores process size
Proportional allocation
Frames in proportion to process size: aᵢ = (sᵢ ÷ S) × m
Larger processes get more frames
Priority allocation
Proportional to priority
Important processes run better
Global vs local replacement
Replace from all frames, or only the process's own
Global gives better throughput; local gives predictable performance
Example
62 frames, processes of 10 and 127 pages: frames = 10/137 × 62 ≈ 4 and 127/137 × 62 ≈ 57.
Topic 7
Thrashing
- Thrashing: a process spends more time paging than executing because it has too few frames for its active pages; CPU utilisation collapses while the OS may wrongly add more processes.
- Working-set model
- Keep each process's recently used pages (window Δ) in memory; suspend a process if total demand exceeds frames
- Page-fault frequency
- Give more frames when the fault rate is too high, take frames when it is low
- Reduce multiprogramming
- Swap out some processes
- Locality
- Programs use clusters of pages; allocate enough for the current locality
Key terms
- Address binding
- Mapping program addresses to memory addresses
- Dynamic linking
- Linking library routines at run time
- Page
- Fixed-size block of logical memory
- TLB
- Fast cache of page-table entries
- Thrashing
- Excessive paging that stalls useful work
Quick revision
- Compile-, load- and execution-time binding; dynamic loading and linking; MMU.
- Logical vs physical addresses; swapping.
- MFT, MVT; first, best, worst fit; internal and external fragmentation; compaction.
- Paging, page tables, TLB, EAT; segmentation.
- Demand paging; FIFO, LRU, optimal; Belady's anomaly; equal, proportional allocation; thrashing, working set, PFF.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Distinguish logical and physical addresses.
- Q2.What is dynamic linking?
- Q3.Distinguish internal and external fragmentation.
- Q4.Find page and offset for address 5,000 with 1 KB pages.
- Q5.What is Belady's anomaly?
- Q6.What causes thrashing?
Long-answer questions
- Q1.Explain address binding, dynamic loading and linking.
- Q2.Explain contiguous allocation and fragmentation.
- Q3.Explain paging with address translation and the TLB.
- Q4.Explain page replacement algorithms with a numerical example and thrashing.
Stuck on this unit?
Message SBS on WhatsApp for help with Operating System, or to ask about studying M.Sc IT at Synetic.