Virtual memory: page faults और replacement
लक्ष्य और मान्यताएँ
FIFO, LRU और optimal replacement trace करें; faults को replacements से अलग करें; समान units में fault cost निकालें। पूर्वज्ञान: paging/address translation। उदाहरणों में एक process, तीन शुरू में खाली frames, fixed pages और दी हुई reference string है। हर reference को resident page चाहिए; missing page का पहला reference fault है। Prefetching, pinning और shared-page complications नहीं हैं। Page numbers labels हैं, उन्हें फिर page size से divide नहीं करना।
1. छोटी workbench, बड़ा store
कारीगर जरूरी tools छोटी workbench पर रखता है; बाकी store में हैं। Missing tool लाना पड़ता है। Bench full हो तो पहले कोई tool हटाना पड़ेगा। Demand paging में legal पर nonresident page भी fault देकर frame माँग सकता है। Free frame eviction बचाता है, fault नहीं। हर fault disk I/O नहीं: नई zero-filled page पुराने file data को पढ़े बिना बन सकती है। Invalid/prohibited access fail भी हो सकती है; OS हर माँगी page दे सके, जरूरी नहीं।
Dirty victim बदली हुई है और frame reuse से पहले writeback माँग सकती है। Unchanged file से backed clean page discard करके बाद में reread की जा सकती है। इसलिए केवल fault count से real time पूरी तरह तय नहीं होता। यहाँ traces faults गिनते हैं, device transactions नहीं।
2. FIFO loading याद रखता है, LRU use
FIFO current pages में सबसे पहले resident हुई page हटाता है। Hit उसे FIFO queue के अंत में नहीं भेजती। LRU उस resident page को हटाता है जिसका सबसे हाल का reference सबसे पुराना है। LRU में hit recency बदलती है, भले fault नहीं। Free frame में missing page लाना भी fault है।
तीन initially empty frames और string 1,2,3,1,4,1,2,5 लें। नीचे resident sets केवल readability के लिए sorted हैं; policy state आगे समझाई गई है।
| Step | Page | FIFO resident set | FIFO result | LRU resident set | LRU result |
|---|---|---|---|---|---|
| 1 | 1 | {1} | F | {1} | F |
| 2 | 2 | {1,2} | F | {1,2} | F |
| 3 | 3 | {1,2,3} | F | {1,2,3} | F |
| 4 | 1 | {1,2,3} | H | {1,2,3} | H |
| 5 | 4 | {2,3,4} | F | {1,3,4} | F |
| 6 | 1 | {1,3,4} | F | {1,3,4} | H |
| 7 | 2 | {1,2,4} | F | {1,2,4} | F |
| 8 | 5 | {1,2,5} | F | {1,2,5} | F |
FIFO में 7 faults और 4 evictions; पहली तीन faults खाली frames लेती हैं। Step 5 पर FIFO page 1 हटाता है क्योंकि step-4 hit ने loading order नहीं बदला। LRU में 6 faults, 3 evictions। Step 5 पर page 2 हटती है, जिसका last use step 2 था। Step 7 पर page 3 (last use 3), step 8 पर page 4 (last use 5) हटती है। केवल sets लिखना पर्याप्त नहीं; loading/recency records भी चाहिए।
3. Optimal भविष्य देखता है
OPT वह page हटाता है जिसका अगला reference सबसे दूर है; फिर कभी use न होने वाली page अनंत दूर मानी जाती है। यह benchmark है; ordinary online OS को ऐसा future knowledge नहीं मिलता। उसी string में तीन initial faults और 1 पर hit के बाद 4 लाते समय 3 हटाएँ: वह फिर नहीं आएगी, जबकि 1 और 2 आएँगे। अगली 1,2 hits हैं। 5 पर fault है; उसके बाद कोई reference नहीं, इसलिए कोई भी resident victim समान रूप से सही है। कुल OPT faults=5। पाँच अलग pages हैं; empty frames/no prefetch में कम-से-कम पाँच first-reference faults चाहिए। यहाँ OPT उस lower bound तक पहुँचता है।
4. अधिक frames: क्या निश्चित है?
FIFO में Belady's anomaly हो सकती है: कुछ strings पर अधिक frames से अधिक faults। हर larger FIFO run खराब होगी, ऐसा दावा नहीं। LRU stack algorithm है: compatible initial states में हर prefix के बाद k-frame resident set, k+1-frame set का subset होता है। इसलिए frames बढ़ाने पर LRU faults नहीं बढ़ते। OPT का minimum achievable count भी अधिक frames से नहीं बढ़ता; अतिरिक्त capacity को नुकसानदेह उपयोग करना जरूरी नहीं। इन guarantees को हर approximate policy या बदलते workload पर लागू न करें।
5. Fault cost और thrashing
Normal access=100 ns, faulting reference की कुल cost=5 ms लें, जिसमें handling और eventual completion शामिल हैं। Fault probability p=10^−5। समान units: 5 ms=5,000,000 ns। Effective time=(1−p)×100+p×5,000,000=149.999 ns। यदि प्रश्न केवल extra fault penalty दे, तो normal cost+p×extra penalty लें। Normal access दो बार charge न करें; ms और ns न मिलाएँ।
Active working sets उपलब्ध frames से बहुत बड़ी हों तो repeated faults useful work पर भारी पड़ सकते हैं: thrashing। अधिक multiprogrammed processes जोड़ना throughput सुधारने की बजाय pressure बढ़ा सकता है। Working set recent reference window से जुड़ा है; अब तक छुई हर page का set जरूरी नहीं।
Self-check
Initial frames, order, policy और tie rules लिखें। Hits भी सावधानी से mark करें। हर reference पर FIFO age या LRU recency अपडेट करें। Fault count और eviction count अलग हैं; fault probability और TLB-miss probability भी अलग हैं।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
VM01. तीन initially empty frames में FIFO और string 1,2,3,1,4,1,2,5 है। Prefetching नहीं। कितनी page faults?
A. 5 B. 6 C. 7 D. 8
उत्तर: C
A: पाँच यहाँ OPT count है, FIFO नहीं।
B: छह यहाँ LRU count है।
C: केवल step 4 hit; बाकी सात faults हैं।
D: Step 4 पर 1 hit है।
VM02. तीन initially empty frames और LRU में string 1,2,3,1,4,1,2,5 की कितनी page faults हैं?
A. 5 B. 6 C. 7 D. 8
उत्तर: B
A: पाँच OPT count है।
B: Steps 1,2,3,5,7,8 faults; 4,6 hits।
C: सात FIFO है; LRU step 5 पर हाल में used 1 बचाता है।
D: दो hits हैं, इसलिए आठ faults नहीं।
VM03. तीन initially empty frames और string 1,2,3,1,4,1,2,5 में page 4 पर OPT किसे हटाए?
A. 1 B. 2 C. 3 D. 4
उत्तर: C
A: 1 अगले reference में चाहिए।
B: 2 आगे चाहिए; 3 फिर नहीं चाहिए।
C: 3 भविष्य में नहीं आती, इसलिए farthest-next-use victim है।
D: 4 requested page है, अभी resident victim नहीं।
VM04. Normal reference=100 ns; faulting reference की total cost completion सहित 5,000,000 ns है। Fault probability=0.00001। Effective time?
A. 100 ns B. 149.999 ns C. 50 ns D. 5,000,100 ns
उत्तर: B
A: Faulting references छूटे हैं।
B: 0.99999×100+0.00001×5,000,000=149.999 ns।
C: 50 ns केवल weighted fault contribution है।
D: हर reference को fault माना और included completion दोबारा जोड़ी।
VM05. Same string और initially empty memory में frames बढ़ाने पर कौन सी policy अधिक faults दे सकती है?
A. LRU B. Optimal minimum-fault replacement C. FIFO D. इनमें कोई नहीं
उत्तर: C
A: इन conditions में LRU stack property रखता है।
B: अधिक capacity optimum खराब नहीं करती।
C: FIFO में Belady anomaly संभव है।
D: FIFO इस universal claim का counterexample है।
VM06. एक legal nonresident page refer होती है; एक unused frame है और prefetch नहीं हुआ। Demand-paging model में क्या जरूरी है?
A. Fault और eviction B. Fault, पर eviction जरूरी नहीं C. न fault न eviction D. TLB hit premise के विपरीत residence सिद्ध करती है
उत्तर: B
A: Free frame existing page eviction बचाता है।
B: Page missing है इसलिए fault; free frame capacity देता है।
C: Nonresident page को fault handling चाहिए।
D: Valid resident translation दी nonresident condition को नहीं बदल सकती।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन