Unit 4 operating system
Memory management: contiguous, paging, segmentation, and paged segmentation
Memory management techniques include contiguous allocation (simple but prone to fragmentation)
and non-contiguous allocation methods like paging (fixed-size blocks), segmentation (variable-sized
logical units), and paged segmentation (hybrid). Each has trade-offs in efficiency, flexibility, and
complexity
Core ideas and terms
• Logical vs physical address: Program logical addresses use karta hai; OS aur hardware
(MMU) inhe physical addresses me translate karte hain.
• Fragmentation:
o External fragmentation: Free memory scattered hoti hai, par required size ka
continuous block nahi milta.
o Internal fragmentation: Allocate kiye gaye block/page ke andar thoda space bach
jaata hai, jo use nahi hota.
• Relocation and protection:
o Relocation: Process ko memory me shift karna; base/limit ya page/segment tables ke
through address adjust kiya jata hai.
o Protection: Har process ki memory ko isolate karna (bounds checks, permissions).
• Hardware support: MMU address translate karta hai; TLB frequently used translations cache
karta hai; page/segment tables mapping rakhte hain.
Contiguous allocation
Contiguous allocation me har process ko ek continuous physical block milta hai. Simple hai, fast hai,
par fragmentation ki badi problem hoti hai.
Fixed partitioning
• Idea: RAM ko fixed partitions me divide kar dete hain; har partition me max ek process.
• Pros: Simplicity: Manage karna easy; overhead low.
• Cons: Internal fragmentation: Process chhota ho toh bacha space waste hota hai. Degree of
multiprogramming limited: Partitions ki count fixed hoti hai.
Dynamic partitioning
• Idea: Partitions runtime par process size ke hisaab se banaye jaate hain (variable-size blocks).
• Placement algorithms:
o First fit: Pehla itna bada free block jahan fit ho jaaye.
o Best fit: Sabse chhota block jo fit ho; fragmentation kam karne ki koshish.
o Worst fit: Sabse bada block; future ke liye large blocks bachane ki hope.
• Pros: Better utilization: Fixed se behtar space usage.
• Cons: External fragmentation: Time ke saath free space tukdon me toot jaata hai.
• Compaction:
o Idea: Free blocks ko ek saath laane ke liye processes ko move karna.
o Cost: CPU time high; real-time systems me problematic; tabhi kiya jaata hai jab
zarurat ho.
Address translation (base/limit)
• Mechanism: Har process ke liye base register + limit register. Logical address (\ell) ko check
kiya jaata hai: agar (\ell < \text{limit}), to physical address (p = \text{base} + \ell).
• Protection: Bounds violation par trap/exception.
Paging (non-contiguous, fixed-size)
Paging me logical memory ko equal-sized pages me aur physical memory ko frames me divide kiya
jaata hai. Mapping page tables ke through hoti hai.
Structure and translation
• Page/frame size: Typically power-of-two (e.g., 4 KB).
• Logical address split:
o Page number (p): High-order bits.
o Offset (d): Low-order bits; (,0 \le d < \text{page size}).
• Physical address: Page table se frame number (f) nikal ke (paddr = f \times \text{page size} +
d).
• Example:
o Given: Page size = 4 KB, logical address (,0x1234).
o Compute: (,p = \lfloor 0x1234 / 0x1000 \rfloor = 0x1), (,d = 0x234).
o Frame: PageTable[1] = frame 9 ⇒ (paddr = 9 \times 4096 + 0x234).
Page table design
• Single-level: Small address spaces ke liye simple; large me bulky.
• Multilevel paging: Page directory + page tables, sirf used parts ko memory me rakhna.
• TLB: Translation Lookaside Buffer hot paths ko cache karta hai; TLB hit pe translation fast
hota hai.
• Inverted page table: Per-frame entry; large physical memories me table size control.
Pros and cons
• Pros: No external fragmentation, easy allocation: Frames free list se mil jaate hain;
relocation simple. Sharing: Code/data pages share ho sakte hain (read-only).
• Cons: Internal fragmentation: Last page me unused bytes waste. Overhead: Page tables +
TLB management complexity.
Advanced: demand paging and replacement
• Demand paging: Pages tabhi load hote hain jab needed ho (page fault par).
• Replacement policies:
o LRU: Recently used pages ko retain karna.
o Clock/Second-chance: Efficient LRU approximation.
o FIFO: Simple par thrashing risk.
• Copy-on-write (COW): Fork ke baad pages shared until write; write pe duplicate page.
• Thrashing: Excessive page faults jab working set ke liye frames kam pad jaate hain; scheduler
+ frame allocation ko tune karna hota hai.
Segmentation (non-contiguous, variable-size)
Segmentation logical structure ko respect karta hai: program ke parts (code, stack, heap, modules) ko
alag segments ke roop me treat kiya jaata hai.
Structure and translation
• Logical address split:
o Segment number (s)
o Offset (d)
• Segment table entry: Base + limit + protection bits.
• Physical address: Agar (,d < \text{limit}), to (paddr = \text{base} + d); warna fault.
Pros and cons
• Pros: Logical alignment: Modules, arrays, functions naturally separate. Protection/sharing:
Per-segment permissions; libraries shareable. Growth: Stack/heap independently grow sakte
hain (agar space ho).
• Cons: External fragmentation: Variable sizes ki wajah se gaps bante hain. Allocation
complexity: Suitable block dhundhna costly; compaction ki zarurat pad sakti hai.
Use cases
• Protection domains: Har segment par R/W/X bits.
• Shared libraries/modules: Multiple processes logically same segment share kar sakte hain.
Paged segmentation (hybrid)
Hybrid approach me har segment ko pages me tod diya jaata hai—logical grouping milti hai, aur
allocation paging ke fixed frames se hoti hai.
Structure and translation
• Logical address split:
o Segment number (s)
o Page number within segment (p)
o Offset (d)
• Tables: Segment table pointers to per-segment page tables.
• Physical address: SegmentTable[s] ⇒ PageTable_s[p] ⇒ frame (f); (paddr = f \times
\text{page size} + d).
Pros and cons
• Pros: Logical view + no external fragmentation: Segments logical, allocation frame-based.
Protection/sharing: Per-segment policies; pages enable granular sharing.
• Cons: Complexity and overhead: Two-level metadata (segment + page tables), TLB entries
larger or multi-part; memory overhead higher.
Comparison and practical notes
Side-by-side comparison
Overhead
Allocation Protection and
Technique Fragmentation and Typical use
style sharing
complexity
Low
Single Early OS,
Contiguous External high; complexity;
continuous Basic via base/limit embedded/simple
allocation internal low compaction
block RT systems
needed
Non- Page tables,
External none;
contiguous, Page-level R/W/X; TLB; Most modern
Paging internal
fixed-size shared pages replacement general-purpose OS
possible
frames policies
Non- External
Allocation + Legacy/protection
contiguous, possible; Strong logical
Segmentation compaction domains; some
variable-size internal protection/sharing
costs architectures
segments minimal
Systems needing
Segments External none; Segment-level Highest
Paged logical grouping
paged into internal semantics + page- metadata;
segmentation with paging
frames possible level control complex TLB
efficiency
What real OS do
• Modern OS (Linux, Windows, macOS): Primarily paging with demand paging, multi-level
page tables, TLBs, COW. Logical separation (code/data/stack) maintained via sections, but
physical allocation frame-based.
• Segmentation: Largely minimized in mainstream 64-bit systems (e.g., x86-64) for user
processes; paging is the main mechanism for protection and translation.
• Embedded/RT: Kabhi-kabhi contiguous schemes simplicity ke liye, ya fixed-size pools.
Quick worked examples
Contiguous allocation bounds check
• Given: Base = 10000, Limit = 6000, Logical (\ell = 5230).
• Check: (\ell < 6000) ⇒ valid.
• Physical: (p = 10000 + 5230 = 15230).
Paging address split
• Given: Logical space = 16-bit, page size = 1 KB.
• Derive: (1,\text{KB} = 1024 = 2^{10}) ⇒ offset = 10 bits, page number = 6 bits.
• Max pages: (2^6 = 64) pages; offset range (0) to (1023).
Paged segmentation lookup
• Given: Segment 3, page 5, offset 72; PageTable_3[5] ⇒ frame 40; page size = 256.
• Physical: (paddr = 40 \times 256 + 72 = 10272).
Key insights
• Contiguous is simple but suffers from external fragmentation and compaction costs.
• Paging removes external fragmentation, enables demand paging and sharing, but adds
internal fragmentation and metadata overhead.
• Segmentation mirrors program structure and enables fine-grained protection, yet
reintroduces external fragmentation.
• Paged segmentation combines logical clarity with frame-based efficiency, at the cost of
added complexity.
Agar tumhe exam-focused notes chahiye (short mnemonics, typical viva questions, or diagrams ke
ASCII sketches), bolo—main turant add kar dunga.
Here’s a clear and structured explanation of the topics you mentioned from your syllabus:
Virtual Memory – Concept
• Definition: Virtual memory is a memory management technique that gives an application
the illusion of having a large, continuous block of memory, even if the physical RAM is
smaller.
• Purpose: It allows programs to run as if they have more memory than physically available, by
using disk space as an extension of RAM.
• Key Benefit: Enables multitasking and execution of large programs without requiring huge
physical memory.
Overlay
• Concept: Overlaying is an old technique used before virtual memory existed. It involves
loading only the required part of a program into memory at a time.
• Use Case: Helps run large programs in limited memory systems.
• Limitation: Programmer must manually divide the program into modules and manage
loading/unloading.
Dynamic Linking and Loading
• Dynamic Linking: Linking of program modules at runtime instead of compile time. Shared
libraries (like .dll in Windows or .so in Linux) are loaded when needed.
• Dynamic Loading: A routine is not loaded into memory until it is called. This saves memory
and improves efficiency.
• Advantage: Reduces memory usage and allows updates to libraries without recompiling
applications.
•
Implementation of Virtual Memory by Demand Paging
• Demand Paging: Pages are loaded into memory only when they are required (on demand).
• Steps:
1. Program requests a page.
2. If the page is not in memory → Page Fault occurs.
3. OS loads the page from disk into RAM.
• Benefits: Efficient use of memory, supports large address spaces.
• Drawback: Page faults can slow down performance if frequent.
Memory Management in Unix/Linux & Windows
Unix/Linux
• Uses paging and segmentation.
• Implements demand paging with copy-on-write.
• Provides swap space for virtual memory.
• Uses shared libraries (.so files) for dynamic linking.
• Tools like top, vmstat, and /proc/meminfo show memory usage.
Windows
• Uses paging with a page file ([Link]).
• Supports dynamic linking via DLLs.
• Implements demand paging and copy-on-write.
• Provides virtual address space isolation for each process.
• Tools like Task Manager and Resource Monitor show memory usage.
In short:
• Virtual Memory gives the illusion of infinite memory.
• Overlay is a manual technique for limited memory systems.
• Dynamic Linking/Loading improves efficiency and modularity.
• Demand Paging is the modern way to implement virtual memory.
• Unix/Linux & Windows both use paging, demand paging, and dynamic linking, but differ in
tools and implementation details.
Would you like me to create a comparison table of Unix/Linux vs Windows memory management for
easier exam revision?