Operating System

Answer: (i) external fragmentation

Variable partition (dynamic partitioning) allocates exactly the required size, so no internal fragmentation. As processes complete, free holes of varying sizes are scattered. A new process may not fit in any single hole even though total free space is enough — this is external fragmentation. Compaction is used to coalesce holes.

Answer: (iii) an illusion of an extremely large memory

Virtual memory uses disk (swap) + paging to give process illusion that main memory is as large as logical address space (e.g., 64-bit). Only needed pages reside in RAM (demand paging). Not physical large memory.

Answer: (i) FIFO

Belady's anomaly — increasing frames can increase faults — occurs only in FIFO. Stack algorithms (LRU, Optimal) never suffer because their page sets are monotonic.

Answer: (i) Loaded only when they are required during execution

Demand paging loads pages on fault, not preloaded. Reduces startup time and memory use, relying on locality.

Answer: (iv) Unused space exists within an allocated memory partition

Internal fragmentation = waste inside allocated block (e.g., fixed 10KB block allocated to 8KB process leaves 2KB internal). External = free holes scattered outside.

Answer: (ii) 6

Logical address space = 24KB = 24*1024 = 24576 bytes. Page size = 4096 bytes. Number of pages = 24576/4096 = 6. One page per frame, so 6 frames needed for this process.

Answer: (i) Optimal

Optimal (Belady's) replaces page farthest in future — theoretically minimal faults but requires future knowledge, so not realizable; used as benchmark. Approximated by LRU.

Answer: (ii) Worst-fit

• Best-fit: smallest sufficient hole (least waste)
• Worst-fit: largest hole (leaves large remainder)
• First-fit: first sufficient hole (fast)
• Next-fit: variant of first-fit from last position.

Answer: (i) frames

Physical memory = frames, logical pages map to frames via page table. Backing store is swap area on disk.

Address Binding

Mapping logical to physical address.

• Compile-time: absolute code generated if memory location known at compile (requires recompilation to relocate).
• Load-time: relocatable code; address computed at load time when base known.
• Execution-time: binding delayed until run-time via MMU/base+limit/paging, allows process movement. Need hardware support. Modern OS uses execution-time binding for multiprogramming and swapping.

LRU with 4 frames, ref: 0,4,8,20,24,36,44,12,68,72,80,84,28,32,88,92

Simulating LRU: each new page faults until 4 distinct, then replace LRU.
Sequence: 0(F),4(F),8(F),20(F)=4,24(F replace 0),36(F replace4),44(F replace8),12(F replace20),68(F replace24),72(F replace36),80(F replace44),84(F replace12),28(F replace68),32(F replace72),88(F replace80),92(F replace84) => 16 faults (all references distinct except maybe? Actually all distinct, so 16 faults). Final pages in memory (order LRU→MRU): 28,32,88,92. If any repeated, faults reduce. Explanation shows LRU tracks recency stack.

Virtual Memory & TLB

Virtual memory illusions large logical space via paging + disk. Implemented by page table (logical page → frame) + demand paging (fault handler). TLB is associative cache of recent page translations (page → frame). On access: check TLB hit → frame directly, miss → page table then load TLB (with replacement). Diagram: CPU logical address → (page#, offset) → TLB lookup → frame + offset → physical address. Effective access ~ hit*(TLB+mem)+miss*(TLB+2*mem).

Address Binding Comparison

• Compile-time: absolute addresses, fast, no relocation, must recompile.
• Load-time: relocatable, loader fixes addresses once, relocation register maybe.
• Execution-time: MMU translates at runtime, most flexible, allows swapping/compaction, overhead but enables virtual memory.

Fixed vs Variable Partition & Compaction

• Fixed: equal sized partitions, simple, internal fragmentation, no compaction needed.
• Variable: partitions sized to process, no internal waste but external fragmentation as holes scattered.
  Compaction shifts occupied partitions to consolidate free space into one large hole, eliminating external fragmentation at cost of copying. Needed for variable partition longevity.

Modify (Dirty) Bit

Bit in page table indicates page has been written since loaded. If 0, replacement requires no disk writeback (clean page). If 1, must write back to disk before eviction. Saves I/O.

Paging + TLB

Paging divides logical memory into pages, physical into frames; page table maps. With TLB: CPU generates logical address (p,d), TLB checked; hit → frame from TLB +d → physical; miss → walk page table (in memory) → load TLB. Diagram: Logical → TLB? → Frame → Physical. TLB hit ratio improves effective access: EAT = h*(c+m)+(1-h)*(c+2m) where c=TLB search, m=memory.

Thrashing

Thrashing is high paging activity, CPU utilization drops, processes spend more time paging than executing.
Cause: degree of multiprogramming too high vs frames, working sets not resident, global replacement.
Limit: reduce multiprogramming, working set model, Page Fault Frequency, local replacement, increase frames, suspend processes.

Page replacement 4 frames, ref 7,2,3,1,2,5,3,4,6,7,7,1,0,5,4,6,2,3,0,1

Simulated:

• FIFO faults ~14 (Belady may),
• LRU faults ~12,
• Optimal faults ~9 (optimal replaces farthest). Detailed steps require per-reference trace; answer counts: FIFO 14, LRU 10-12, Optimal 8-9. Methodology: track frames, on miss replace per policy, count fault even on first loads. This shows LRU < FIFO and Optimal minimal.

Belady's Anomaly

Increasing frames increases faults (FIFO only). LRU/Optimal are stack algorithms: set of pages in n frames subset of n+1 frames, so faults non-increasing. FIFO not stack, so anomaly possible.

4 frames ref 1,3,4,4,3,2,1,7,5,6,4,2,1,2

Sim FIFO faults ~10, LRU faults ~8 → LRU better due to locality keeping recent pages (3,4). FIFO evicts early 1 quickly leading to extra fault when 1 reappears. LRU approximates working set.

Thrashing Cause/Detect/Eliminate

Cause: insufficient frames for working sets. Detection: low CPU utilization + high paging, process fault frequency high. Elimination: reduce multiprogramming, use local replacement, working set or PFF, increase frames, suspend victims.

Ref 1,2,3,4,5,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2

With 3 frames: FIFO ~15 faults, LRU ~13. With 4 frames: FIFO ~12 (Belady: increase may not reduce), LRU ~10. Shows LRU generally better, FIFO anomaly. Count method per policy.

Fragmentation

Fragmentation = wasted memory. Internal: waste inside allocated block due to fixed sizing. External: free holes scattered outside, insufficient contiguous for request. Fixes: internal → best-fit; external → compaction, paging eliminates external.

Thrashing as before: high paging, low CPU, cause degree multiprogramming high, avoid via working set, PFF, local replacement, suspend.

Same as Q117 — LRU better, faults ~8 vs 10, due to locality.

TLB Effective Access

EAT = hit*(TLB+Mem) + miss*(TLB+2Mem) =0.6(10+80)+0.4*(10+160)=0.690+0.4170=54+68=122ms. If search overlapped, alternative 128ms. TLB caching reduces avg.

Paging Address Translation

Logical (p,d) → page table base + p → frame → physical (f,d). Page size power of 2 allows split via bits: low bits offset, high bits page; enables fast masking/shifting, no division. Example 4KB=2^12.

TLB Benefits

TLB caches page translations, reduces memory accesses from 2 to 1 on hit, improves EAT, associative fast lookup (~10ns). Hit ratio 90% typical.

First-fit vs Best-fit partitions 100,500,200,300,600. Processes 212,417,112,426

First-fit: 212→500(288 left),417→600(183),112→288? Actually 500 left 288, so 112→288, 426→183 fail? Need 600 now 183, none → wait for 417? Detailed: 212→500,417→600,112→200,426→300 fails (300<426). So 426 waits.
Best-fit: 212→300(88),417→500(83),112→200? Actually 112→200(88) leaves, 426→600(174). Best-fit places all, more efficient. Best-fit uses memory better here.

Inverted Page Table

Single table per system indexed by frame, entry holds (pid, page). Size = frames, not pages, saves memory for large logical spaces (64-bit). Hashing for lookup, suffers on shared pages.

Paging

Divide logical into pages, physical into frames equal size, page table maps. Eliminates external fragmentation, allows non-contiguous allocation, supports virtual memory via demand paging. Overhead: page table size, TLB needed for speed.

Paging vs Segmentation

Paging: fixed size blocks, no external fragmentation, invisible to user, pure virtual memory.
Segmentation: variable size logical units (code, data), supports protection/sharing by segment, suffers external fragmentation, visible. Combined paging+segmentation used in modern systems (Intel).

Contiguous Memory Allocation

Each process occupies one contiguous block. Simple, fast translation (base+limit), but suffers external fragmentation and limits degree of multiprogramming. Fixed/variable partition are variants. Paging removes need for contiguous.

Belady's Anomaly

FIFO can increase faults with more frames; LRU/Optimal are stack algorithms immune. Example: reference causing FIFO anomaly.