स्मृति प्रबंधन, आभासी स्मृति व फ़ाइल तंत्र

आभासी स्मृति एक विचार है जिससे बड़ी मात्रा में अंकगणित लटका है: किसी प्रोग्राम को विद्यमान से अधिक स्मृति पता देने दें, और RAM में केवल वही पृष्ठ रखें जिनका वह प्रयोग कर रहा है। पृष्ठन तंत्र है। आभासी पता पृष्ठ संख्या व विचलन में विभक्त होता है, पृष्ठ संख्या पृष्ठ-सारणी में सूची बनाकर फ़्रेम संख्या देती है, और विचलन अछूता पार ले जाया जाता है — और वही तथ्य प्रत्येक पता-अनुवाद प्रश्न को यांत्रिक बनाता है, क्योंकि विचलन की चौड़ाई पृष्ठ-आकार से नियत है और शेष सब उसी से निकलता है। तत्पश्चात् दो लागतें प्रकट होती हैं, और दोनों आंकिक रूप से परीक्षित हैं। प्रथम समय है: स्मृति में पृष्ठ-सारणी का अर्थ है प्रत्येक पहुँच को दो स्मृति-पहुँचें चाहिए, और इसीलिए TLB है, और इसीलिए प्रत्याशित पहुँच-समय एक भारित औसत है जिसे आप निकालते हैं, स्मरण नहीं करते। द्वितीय स्थान है: 4 KB पृष्ठों सहित 32-बिट पता-स्थान को 220 प्रविष्टियाँ चाहिए, अतः एक-स्तरीय पृष्ठ-सारणी प्रति प्रक्रिया 4 MB है, और इसीलिए वास्तविक पृष्ठ-सारणियाँ बहु-स्तरीय हैं। तत्पश्चात् पृष्ठ प्रतिस्थापन, जहाँ प्रश्न लगभग पूर्णतः दी गई संदर्भ-माला पर पृष्ठ-दोष गिनना हैं — और जहाँ एक परिणाम पहले साथ ले जाने योग्य है, क्योंकि वह गहराई से सहज-बोध-विरुद्ध है: अधिक फ़्रेम का अर्थ अधिक पृष्ठ-दोष हो सकता है। वही बेलेडी की विसंगति है, वह FIFO में होती है, और वह LRU या OPT में एक संरचनात्मक कारण से नहीं हो सकती जो कंठस्थ करने के बजाय समझने योग्य है। अंततः फ़ाइल तंत्र, जो एक दर्जन वेशों में पूछे जाते एक प्रश्न पर सिमट आते हैं: किसी फ़ाइल के खंड कहाँ हैं यह अंकित करने की इस विधि को देखते हुए, सबसे बड़ी फ़ाइल क्या है, और आप खंड k तक उससे पूर्व वाले पढ़े बिना पहुँच सकते हैं क्या?

पृष्ठ-सारणी की दो लागतें

पृष्ठ-सारणी स्मृति में रहती है, अतः भोली खोज प्रति अनुदेश दो स्मृति-पहुँचों की लागत रखती है — एक प्रविष्टि पढ़ने हेतु व एक आँकड़े लाने हेतु। TLB हाल के अनुवादों का लघु सहचारी कैश है जो मेल पर प्रथम पहुँच हटा देता है, और तब प्रत्याशित समय मेल व चूक पर भारित औसत है। लें 20 ns की TLB पहुँच, 100 ns की स्मृति-पहुँच, तथा 80% मेल-अनुपात, इस परिपाटी सहित कि TLB पहले देखा जाता है व स्मृति पश्चात्। मेल पर लागत 20 + 100 = 120 ns; चूक पर 20 + 100 + 100 = 220 ns, क्योंकि आप विफल खोज, फिर पृष्ठ-सारणी, फिर आँकड़े का मूल्य चुकाते हैं। अतः EMAT = 0.8(120) + 0.2(220) = 96 + 44 = 140 ns। मेल-अनुपात 90% करें और वह 130 ns हो जाता है — मेल-अनुपात के प्रत्येक 10 अंक ठीक एक स्मृति-पहुँच के मूल्य के हैं, जो किसी भी उत्तर पर उपयोगी विवेक-जाँच है।

⚠️ TLB परिपाटी बताएँ, क्योंकि दो प्रचलन में हैं
वही संख्याएँ दो भिन्न उचित पाठों में भिन्न उत्तर देती हैं, और जो प्रश्न न बताए कि उसका अर्थ कौन-सा है वह कठिन के बजाय अस्पष्ट है। TLB-फिर-स्मृति में (ऊपर प्रयुक्त) मेल की लागत TLB + स्मृति = 120 ns। अतिव्यापी खोज में, जहाँ स्मृति-पहुँच आरंभ होते समय TLB खोजा जाता है, मेल की लागत केवल स्मृति-पहुँच, 100 ns, और चूक-दंड वह है जो TLB समय जोड़ता है। तीसरा प्रकार चूक पर केवल एक स्मृति-पहुँच लेता है, पृष्ठ-सारणी को कैश्ड मानते हुए। अतः: प्रश्न में TLB पहुँच समय बनाम TLB खोज अतिव्यापी है शब्द पढ़ें, और यदि वह चुप हो, तो TLB-फिर-स्मृति प्रयोग करें व वह बताएँ — लगभग प्रत्येक भारतीय पाठ्यपुस्तक व पूर्व GATE पेपर वही परिपाटी प्रयोग करता है। जो कभी परिवर्तनीय नहीं वह संरचना है: EMAT = (मेल अनुपात)(मेल की लागत) + (चूक अनुपात)(चूक की लागत), और बचने योग्य अंकगणित-चूक यह भूलना है कि चूक अपना व्यर्थ किया TLB समय अभी भी चुकाती है।
🧠 पृष्ठ-सारणी का आकार, तथा दो स्तर क्यों
सब कुछ विचलन से आता है। 4 KB पृष्ठों सहित विचलन 12 बिट है, अतः 32-बिट आभासी पता 20 बिट पृष्ठ-संख्या छोड़ता है और अतः 220 = 1,048,576 पृष्ठ। प्रति प्रविष्टि 4 बाइट पर वह 222 बाइट = 4 MB पृष्ठ-सारणी है, प्रति प्रक्रिया, स्थायी, चाहे प्रक्रिया उतनी स्मृति प्रयोग करे या न करे — और बहु-स्तरीय अभिकल्प की सम्पूर्ण प्रेरणा वही है। अब उसे विभक्त करें: 4 KB / 4 बाइट = 1024 = 210 प्रविष्टियाँ सारणी के एक पृष्ठ में बैठती हैं, अतः 20-बिट पृष्ठ-संख्या 10 | 10 में विभक्त होती है, जिससे दो-स्तरीय 32-बिट योजना का प्रसिद्ध 10 | 10 | 12 विभाजन मिलता है। बचत कुल आकार में नहीं अपितु इसमें है कि क्या स्थायी होना चाहिए: बाह्य सारणी एक पृष्ठ है, और केवल वे आंतरिक सारणियाँ विद्यमान होनी चाहिए जो वस्तुतः प्रयुक्त पृष्ठों को ढकती हैं। वही अंकगणित विपरीत प्रश्न का उत्तर भी देता है — स्तरों की संख्या पूछी जाए, तो पृष्ठ-संख्या की चौड़ाई को log₂(प्रति पृष्ठ प्रविष्टियाँ) से भाग दें व ऊपर पूर्णांकित करें।
ℹ️ पृष्ठन आंतरिक रूप से खंडित करता है; खंडन बाह्य रूप से
दोनों योजनाएँ विपरीत प्रकार से विफल होती हैं, और शब्दों का यह युग्म सीधे परीक्षित होता है। पृष्ठन नियत-आकार फ़्रेम प्रयोग करता है, अतः कोई निवेदन सदा किसी मुक्त फ़्रेम में ठीक बैठता है और आवंटनों के बीच कभी अप्रयोज्य अंतराल नहीं होता — किंतु किसी प्रक्रिया का अंतिम पृष्ठ प्रायः अंशतः रिक्त होता है, जो आंतरिक खंडन है, प्रति प्रक्रिया औसतन आधा पृष्ठ। खंडन तार्किक इकाइयों से मिलाए चर-आकार खंड प्रयोग करता है, अतः खंड के भीतर कुछ व्यर्थ नहीं जाता — किंतु भिन्न आकारों के खंड मुक्त करना ऐसे छिद्र छोड़ता है जो प्रयोग हेतु बहुत छोटे हैं, जो बाह्य खंडन है, और उसे सुधारने हेतु संहनन चाहिए। संक्षिप्त कथन: पृष्ठन अंतिम आवंटन के भीतर स्थान व्यर्थ करता है, खंडन आवंटनों के बीच। संयुक्त योजनाएँ (पृष्ठित खंडन) ठीक इसलिए विद्यमान हैं कि खंडन का तार्किक दृश्य रखा जाए और केवल पृष्ठन की आंतरिक लागत चुकाई जाए।

पृष्ठ प्रतिस्थापन, एक माला पर गिना गया

नीचे की सारणी मानक संदर्भ-माला 1 2 3 4 1 2 5 1 2 3 4 5 को तीनों कलनविधियों से दोनों, 3 व 4 फ़्रेम पर चलाती है, क्योंकि रोचक तथ्य सब तुलनाएँ हैं और एकमात्र पंक्ति उनमें कोई नहीं दिखाती। दोष अनुकरण द्वारा गिनें: पहले से स्थित पृष्ठ का संदर्भ मेल है और (LRU हेतु) नवीनता-क्रम के अतिरिक्त कुछ नहीं बदलता; अनुपस्थित पृष्ठ का संदर्भ दोष है, और यदि प्रत्येक फ़्रेम भरा हो तो कलनविधि का नियम शिकार चुनता है — FIFO सर्वाधिक पूर्व लादा पृष्ठ निकालती है, LRU सर्वाधिक पूर्व प्रयुक्त, OPT वह जिसका अगला प्रयोग भविष्य में सर्वाधिक दूर है।

1 2 3 4 1 2 5 1 2 3 4 5 पर पृष्ठ-दोष, अनुकरण द्वारा गणना
कलनविधि3 फ़्रेम4 फ़्रेमयुग्म क्या दिखाता है
FIFO910बेलेडी की विसंगति — अधिक फ़्रेम, अधिक दोष
LRU108स्टैक कलनविधि — अधिक फ़्रेम सहित कभी निकृष्ट नहीं
OPT76अप्राप्य निम्न परिबंध, जिसे भविष्य चाहिए
🎯 FIFO निकृष्ट क्यों हो सकती है और LRU नहीं: स्टैक गुणधर्म
कोई कलनविधि स्टैक कलनविधि है जब n फ़्रेम में वह जो पृष्ठ-समुच्चय रखती है वह सदा उस समुच्चय का उपसमुच्चय हो जो वह n + 1 फ़्रेम में रखती। यदि वह टिके, तो n फ़्रेम पर प्रत्येक मेल n + 1 पर भी मेल है, अतः दोष-गणना बढ़ नहीं सकती और बेलेडी की विसंगति असंभव है। LRU में वह गुणधर्म है: वह जो पृष्ठ धारण करती है वे n सर्वाधिक नवीन प्रयुक्त हैं, और n सर्वाधिक नवीन सदा n + 1 सर्वाधिक नवीन में हैं। OPT में वही कारण भूत के स्थान पर भविष्य सहित है। FIFO में नहीं, और कारण यह है कि उसका चयन प्रयोग की पूर्णतः अवहेलना करता है — वह लादने के क्रम से निकालती है, अतः फ़्रेम जोड़ना निष्कासनों का आगमन-प्रतिरूप बदल देता है और ऐसा पृष्ठ फेंक सकता है जिसे लघुतर संरूपण ने संयोगवश रखा था। वह अंकगणित का दोष नहीं; वह वास्तविक व्यवहार है, और ऊपर का 9 → 10 वही है। अतः परीक्षणीय कथन सटीक है: बेलेडी की विसंगति FIFO में हो सकती है, LRU या OPT में नहीं हो सकती, और कारण उपसमुच्चय-संबंध है, कलनविधियाँ कितनी अच्छी हैं इसके विषय में कुछ नहीं।
⚠️ LRU सदा FIFO से श्रेष्ठ नहीं — इसी माला पर वह निकृष्ट है
3-फ़्रेम स्तंभ पुनः पढ़ें: FIFO 9 दोष लेती है और LRU 10। LRU श्रेष्ठ अनुमानक है — वह यह दाँव लगाकर OPT का सन्निकटन करती है कि नवीन प्रयोग भावी प्रयोग की भविष्यवाणी करता है — किंतु अनुमानक एक दाँव है, और किसी विशेष माला पर वह हार सकता है। यह माला 1, 2, 3, 4 से ऐसे चक्रित होती है कि ठीक वही पृष्ठ निकलता रहे जो अभी चाहिए होगा, जो नवीनता को दंडित करता है। अतः दो दावे पृथक् रखने चाहिए, क्योंकि विकल्प उन्हें नित्य मिला देते हैं। सत्य: LRU बेलेडी की विसंगति कभी नहीं भोगती, क्योंकि वह स्टैक कलनविधि है। असत्य: LRU सदा FIFO से कम दोष उत्पन्न करती है। प्रथम एक कलनविधि के विषय में फ़्रेम-गणनाओं के आर-पार प्रमेय है; द्वितीय नियत फ़्रेम-गणना पर कलनविधियों के बीच तुलना है, और ऐसी कोई प्रत्याभूति विद्यमान नहीं। यदि प्रश्न आपको माला दे, तो गिनें — इससे तर्क न करें कि कौन-सी कलनविधि अधिक चतुर मानी जाती है।

फ़ाइल आवंटन: सबसे बड़ी फ़ाइल, तथा प्रत्यक्ष पहुँच

तीनों आवंटन-रणनीतियाँ, प्रश्न जो दो बातें पूछते हैं उन पर
रणनीतिखंड k तक प्रत्यक्ष पहुँच?मुख्य दुर्बलता
सन्निहितहाँ — आरंभ + kबाह्य खंडन; फ़ाइल यथास्थान बढ़ नहीं सकती
कड़ीबद्धनहीं — k कड़ियाँ चलनी पड़ती हैंप्रत्यक्ष पहुँच नहीं; एक बिगड़ा सूचक शेष पुच्छ खो देता है
अनुक्रमित (inode)हाँ — अनुक्रमणिका खंड पढ़ेंअनुक्रमणिका स्वयं स्थान लेती है, और मापन हेतु परोक्षण चाहती है
🧠 inode की अधिकतम फ़ाइल-आकार गणना, एक बार की गई
लें 10 प्रत्यक्ष सूचकों, एक एकल-परोक्ष व एक द्वि-परोक्ष सहित inode, 1 KB खंड व 4-बाइट सूचक। सब कुछ एक संख्या से निकलता है: एक खंड 1024 / 4 = 256 सूचक रखता है। अब जोड़ें कि प्रत्येक प्रकार का सूचक कहाँ तक पहुँचता है। 10 प्रत्यक्ष सूचक 10 खंड तक पहुँचते हैं। एकल परोक्ष सूचकों के एक खंड की ओर संकेत करता है, 256 खंड तक पहुँचता है। द्वि-परोक्ष 256 सूचकों के खंड की ओर संकेत करता है, जिनमें प्रत्येक 256 सूचकों के खंड की ओर, 256 × 256 = 65,536 खंड तक पहुँचते हुए। कुल = 10 + 256 + 65,536 = 65,802 खंड, और प्रत्येक 1 KB पर वह 65,802 KB = 64.26 MB। दो आदतें इसे विश्वसनीय बनाती हैं। प्रति-खंड-सूचक पहले निकालें व लिख लें, क्योंकि प्रत्येक पश्चात्वर्ती पद उसकी घात है। और उसी इकाई में उत्तर दें जो प्रश्न माँगता है — 65,802 KB को 1000 से भाग देकर MB बनाने में बहुत से अंक खोए जाते हैं। यदि त्रि-परोक्ष उपस्थित हो तो वह 256³ = 16,777,216 खंड जोड़ता है और उससे पूर्व का सब बौना कर देता है, और इसीलिए प्रत्यक्ष सूचक लघु फ़ाइलों हेतु महत्व रखते हैं और अन्यत्र नहीं।

मुख्य बिंदु

  • विचलन अनुवाद के आर-पार अछूता जाता है, अतः पृष्ठ-आकार उसे नियत करता है और शेष सब उसी से निकलता है।
  • EMAT = (मेल)(TLB + स्मृति) + (चूक)(TLB + स्मृति + स्मृति) — चूक व्यर्थ किया TLB समय अभी भी चुकाती है।
  • 32-बिट स्थान, 4 KB पृष्ठ, 4-बाइट प्रविष्टियाँ: 220 पृष्ठ, 4 MB सपाट सारणी, तथा 10 | 10 | 12 द्वि-स्तरीय विभाजन।
  • पृष्ठन अंतिम आवंटन के भीतर स्थान व्यर्थ करता है; खंडन आवंटनों के बीच।
  • बेलेडी की विसंगति वास्तविक है: 1 2 3 4 1 2 5 1 2 3 4 5 पर FIFO 3 फ़्रेम पर 9 व 4 पर 10 दोष लेती है।
  • LRU व OPT स्टैक कलनविधियाँ हैं, अतः विसंगति नहीं हो सकती — किंतु LRU किसी माला पर FIFO से हार सकती है।
  • प्रति-खंड-सूचक पहले निकालें; प्रत्येक परोक्ष पद उसकी घात है।
  • कड़ीबद्ध आवंटन वही है जो खंड k तक प्रत्यक्ष नहीं पहुँच सकता; सन्निहित व अनुक्रमित दोनों पहुँच सकते हैं।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. TLB पहुँच 20 ns लेती है और स्मृति-पहुँच 100 ns। पृष्ठ-सारणी मुख्य स्मृति में है और TLB मेल-अनुपात 80% है। TLB पहले देखा जाता है व स्मृति पश्चात्। प्रभावी स्मृति पहुँच-समय, ns में, ______ है

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 140

    140 ns। मेल पर अनुवाद TLB से आता है और एक स्मृति-पहुँच आँकड़े लाती है: 20 + 100 = 120 ns। चूक पर TLB खोज व्यर्थ जाती है पर उसका मूल्य फिर भी चुकाया जाता है, तत्पश्चात् पृष्ठ-सारणी स्मृति से पढ़ी जाती है, तत्पश्चात् आँकड़े: 20 + 100 + 100 = 220 ns। भारण: 0.8(120) + 0.2(220) = 96 + 44 = 140। सर्वाधिक सामान्य गलत उत्तर 120 है, यह भूलने से कि चूक अतिरिक्त स्मृति-पहुँच की लागत रखती है, वही नहीं। दूसरा सर्वाधिक सामान्य 116 है, चूक पर TLB समय छोड़ने से — पर खोज हुई थी, अतः उसका मूल्य लिया जाता है। शीघ्र विवेक-जाँच: उत्तर 120 व 220 के बीच कठोरतः होना चाहिए, और प्रथम के बहुत निकट क्योंकि मेल चार गुना अधिक संभाव्य हैं।

  2. संदर्भ-माला 1 2 3 4 1 2 5 1 2 3 4 5 हेतु FIFO प्रतिस्थापन 3 फ़्रेम सहित 9 पृष्ठ-दोष व 4 फ़्रेम सहित 10 उत्पन्न करता है। यह दिखाता है कि:

    1. अनुकरण में अंकगणित त्रुटि है, क्योंकि अधिक फ़्रेम दोष बढ़ा नहीं सकते
    2. FIFO बेलेडी की विसंगति भोग सकती है, क्योंकि वह स्टैक कलनविधि नहीं है
    3. संदर्भ-माला वैध नहीं है
    4. FIFO सदा LRU से निकृष्ट है
    उत्तर देखें

    उत्तर: B — FIFO बेलेडी की विसंगति भोग सकती है, क्योंकि वह स्टैक कलनविधि नहीं है

    बेलेडी की विसंगति, और वह भूल के बजाय वास्तविक व्यवहार है। कोई कलनविधि स्टैक कलनविधि है जब n फ़्रेम में वह जो पृष्ठ धारण करती है वे सदा उनके उपसमुच्चय हों जो वह n + 1 में धारण करती; वह प्रत्याभूत करता है कि प्रत्येक मेल अतिरिक्त फ़्रेम में बचा रहे, अतः दोष बढ़ नहीं सकते। LRU में वह गुणधर्म है (n सर्वाधिक नवीन, n + 1 सर्वाधिक नवीन में हैं) और OPT में भी; FIFO में नहीं, क्योंकि वह लादने के क्रम से निकालती है और प्रयोग की पूर्णतः अवहेलना करती है, अतः फ़्रेम जोड़ना यह पुनर्व्यवस्थित कर देता है कि कौन-से पृष्ठ संयोगवश प्राचीनतम हैं। विकल्प A वही सहज बोध है जिसे तोड़ने हेतु प्रश्न विद्यमान है। विकल्प D इस प्रकार आगे बढ़ जाता है जिसका खंडन यही माला करती है — यहाँ 3 फ़्रेम पर LRU 10 दोष लेती है FIFO के 9 के सामने, अतः LRU सदा श्रेष्ठ नहीं; सदा सत्य केवल यह है कि LRU विसंगति नहीं दिखा सकती।

  3. किसी inode में 10 प्रत्यक्ष खंड-सूचक, एक एकल-परोक्ष सूचक व एक द्वि-परोक्ष सूचक हैं। खंड-आकार 1 KB है और प्रत्येक खंड-सूचक 4 बाइट। अधिकतम फ़ाइल आकार, MB में, दो दशमलव स्थान तक, ______ है

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 64.26

    64.26 MB। प्रति खंड सूचक पहले निकालें: 1024 / 4 = 256। तत्पश्चात् प्रत्येक सूचक-वर्ग उसकी एक घात देता है। प्रत्यक्ष: 10 खंड। एकल परोक्ष: सूचकों का एक खंड, अतः 256 खंड। द्वि-परोक्ष: 256 सूचक-खंड, प्रत्येक 256 सूचक धारण करता, अतः 256² = 65,536 खंड। कुल 10 + 256 + 65,536 = 65,802 खंड, और प्रति खंड 1 KB पर वह 65,802 KB। 1024 से भाग देने पर 64.26 MB। इस एक प्रश्न में दो जाल बैठे हैं। 1024 के बजाय 1000 से भाग देने पर 65.80 मिलता है, जो सर्वाधिक बार दिखता गलत उत्तर है। और ध्यान दें द्वि-परोक्ष कुल का 99.6% देता है, अतः 64 MB के निकट उत्तर सही है जबकि 0.25 MB के निकट का अर्थ है वर्ग करना छूट गया।

  4. किसी तंत्र में 32-बिट आभासी पता-स्थान, 4 KB पृष्ठ व 4-बाइट पृष्ठ-सारणी प्रविष्टियाँ हैं। प्रति प्रक्रिया एक-स्तरीय पृष्ठ-सारणी का आकार है:

    1. 1 MB
    2. 4 MB
    3. 4 KB
    4. 1 GB
    उत्तर देखें

    उत्तर: B — 4 MB

    4 MB। 4 KB पृष्ठ को 12-बिट विचलन चाहिए, जिससे 32 − 12 = 20 बिट पृष्ठ-संख्या बचती है, अतः 220 = 1,048,576 पृष्ठ हैं और अतः उतनी ही प्रविष्टियाँ। प्रत्येक 4 बाइट पर: 220 × 22 = 222 बाइट = 4 MB, प्रति प्रक्रिया, और स्थायी, चाहे प्रक्रिया उतनी स्मृति प्रयोग करे या न करे। वही आँकड़ा बहु-स्तरीय पृष्ठ-सारणियों की सम्पूर्ण प्रेरणा है — 4 KB / 4 बाइट = 1024 प्रविष्टियाँ एक पृष्ठ में बैठती हैं, अतः 20-बिट पृष्ठ-संख्या 10 | 10 में विभक्त होती है और केवल वे आंतरिक सारणियाँ विद्यमान होनी चाहिए जो वस्तुतः प्रयुक्त पृष्ठों को ढकती हैं। विकल्प A प्रविष्टि-आकार छोड़ देता है और पृष्ठों की गिनती मेगा-इकाइयों में बताता है। विकल्प C सारणी के एक पृष्ठ का आकार है, सारणी का नहीं। विकल्प D पता-स्थान के प्रति बाइट एक 4-बाइट प्रविष्टि से निकलता, जो पृष्ठ-आकार से चूकता है।

  5. पृष्ठ प्रतिस्थापन के विषय में निम्नलिखित में से कौन-से कथन सत्य हैं?

    1. बेलेडी की विसंगति FIFO प्रतिस्थापन में हो सकती है
    2. LRU अधिक फ़्रेम सहित कभी अधिक दोष उत्पन्न नहीं कर सकती
    3. उसी माला व फ़्रेम-गणना पर LRU सदा FIFO से अधिकतम उतने ही दोष उत्पन्न करती है
    4. इष्टतम कलनविधि को भावी संदर्भों का ज्ञान चाहिए
    उत्तर देखें

    उत्तर: A — बेलेडी की विसंगति FIFO प्रतिस्थापन में हो सकती है; B — LRU अधिक फ़्रेम सहित कभी अधिक दोष उत्पन्न नहीं कर सकती; D — इष्टतम कलनविधि को भावी संदर्भों का ज्ञान चाहिए

    A, B व D। A बेलेडी की विसंगति है, 1 2 3 4 1 2 5 1 2 3 4 5 पर प्रदर्शित जहाँ FIFO 3 फ़्रेम से 4 पर 9 → 10 दोष जाती है। B स्टैक गुणधर्म है: LRU n सर्वाधिक नवीन प्रयुक्त पृष्ठ धारण करती है, जो सदा n + 1 सर्वाधिक नवीन प्रयुक्त के उपसमुच्चय हैं, अतः फ़्रेम जोड़ने से कोई मेल नहीं खोता। D, OPT की परिभाषा है और वही कारण है कि वह कार्यान्वयन के बजाय मानदंड है — वह उस पृष्ठ को निकालती है जिसका अगला प्रयोग सर्वाधिक दूर है, जिसके लिए संदर्भ-माला पहले से चाहिए। C असत्य है, और वही माला उसका खंडन करती है: 3 फ़्रेम पर LRU 10 दोष लेती है FIFO के 9 के सामने। LRU श्रेष्ठ अनुमानक है, यह दाँव लगाती कि नवीन प्रयोग भावी प्रयोग की भविष्यवाणी करता है, और यह माला ठीक उसी दाँव को दंडित करने हेतु बनी है, पृष्ठों से ऐसे चक्रित होकर कि सर्वाधिक-पूर्व-प्रयुक्त पृष्ठ सदा अगला आवश्यक हो। दोनों दावे पृथक् रखें: B एक कलनविधि के विषय में फ़्रेम-गणनाओं के आर-पार है और टिकता है; C नियत फ़्रेम-गणना पर कलनविधियों के बीच तुलना है और नहीं टिकता।

  6. कौन-सी फ़ाइल आवंटन रणनीति पूर्ववर्ती खंड पढ़े बिना किसी फ़ाइल के k-वें खंड तक प्रत्यक्ष पहुँच नहीं दे सकती?

    1. सन्निहित आवंटन
    2. कड़ीबद्ध आवंटन
    3. अनुक्रमित आवंटन
    4. तीनों प्रत्यक्ष पहुँच देते हैं
    उत्तर देखें

    उत्तर: B — कड़ीबद्ध आवंटन

    कड़ीबद्ध आवंटन। प्रत्येक खंड अगले का पता संचित करता है, अतः खंड k का पता केवल खंड 0 से k − 1 तक पढ़कर ज्ञात हो सकता है — एक खंड तक पहुँचने हेतु k डिस्क-पहुँचें, और इसीलिए कड़ीबद्ध आवंटन क्रमिक फ़ाइलों के अनुकूल है और अन्यत्र नहीं। सन्निहित आवंटन पता अंकगणितीय रूप से आरंभ + k निकालता है, एकमात्र पहुँच। अनुक्रमित आवंटन अनुक्रमणिका खंड एक बार पढ़ता है और फिर सीधे k की प्रविष्टि पर जाता है। सौदा दोनों प्रकार कहने योग्य है: तीनों में कड़ीबद्ध आवंटन ही बाह्य खंडन से रहित व मुक्त वृद्धि वाला है, क्योंकि अगला खंड कहीं भी हो सकता है, और उसका मूल्य वह प्रत्यक्ष पहुँच की हानि तथा इस भंगुरता से चुकाता है कि एक भ्रष्ट सूचक फ़ाइल का सम्पूर्ण शेष पुच्छ अनाथ कर देता है।

  7. आंतरिक खंडन पृष्ठन का लक्षण है, जबकि बाह्य खंडन खंडन का। कारण है:

    1. पृष्ठ खंडों से छोटे होते हैं
    2. पृष्ठन नियत-आकार इकाइयाँ आवंटित करता है, अतः व्यर्थता अंतिम इकाई के भीतर पड़ती है; खंड आकार में भिन्न हैं, अतः व्यर्थता उनके बीच पड़ती है
    3. खंडन पृष्ठ-सारणी प्रयोग नहीं करता
    4. पृष्ठन को संहनन चाहिए और खंडन को नहीं
    उत्तर देखें

    उत्तर: B — पृष्ठन नियत-आकार इकाइयाँ आवंटित करता है, अतः व्यर्थता अंतिम इकाई के भीतर पड़ती है; खंड आकार में भिन्न हैं, अतः व्यर्थता उनके बीच पड़ती है

    कारण आवंटन-इकाई है, आकार नहीं। चूँकि प्रत्येक फ़्रेम समान आकार का है, कोई भी मुक्त फ़्रेम किसी भी निवेदन को ठीक संतुष्ट करता है, अतः आवंटनों के बीच कोई अप्रयोज्य अंतराल बन नहीं सकता — किंतु कोई प्रक्रिया विरले ही पूर्ण संख्या में पृष्ठ भरती है, अतः उसका अंतिम पृष्ठ अंशतः रिक्त होता है: आंतरिक खंडन, प्रति प्रक्रिया औसतन आधा पृष्ठ। खंड तार्किक इकाइयों के आकार के होते हैं, अतः किसी एक के भीतर कुछ व्यर्थ नहीं जाता, पर भिन्न आकारों के खंड मुक्त करना अगले निवेदन हेतु बहुत छोटे छिद्र छोड़ता है: बाह्य खंडन। विकल्प A कारणता की दिशा गलत लेता है; पृष्ठ बड़े करना आंतरिक खंडन बदलने के बजाय बढ़ाता है। विकल्प C विषय से परे है और शिथिल भी — खंडन खंड-सारणी प्रयोग करता है, और पृष्ठित खंडन दोनों। विकल्प D उपचार उलट देता है: संहनन बाह्य खंडन का समाधान करता है, अतः वह खंडन का है।

  8. ऊपर के तंत्र में TLB मेल-अनुपात 80% से 90% करना (TLB 20 ns, स्मृति 100 ns, TLB पहले देखा जाता) प्रभावी पहुँच-समय 140 ns से किस पर बदल देता है?

    1. 120 ns
    2. 130 ns
    3. 126 ns
    4. 100 ns
    उत्तर देखें

    उत्तर: B — 130 ns

    130 ns। मेल की लागत 120 ns व चूक की 220 ns है, अतः 0.9(120) + 0.1(220) = 108 + 22 = 130। संरचना पुनर्गणना के बजाय पढ़ लेने योग्य है: दोनों लागतें ठीक एक स्मृति-पहुँच, 100 ns, से भिन्न हैं, अतः मेल-अनुपात के प्रत्येक 10 अंक 10 ns के मूल्य के हैं — जो उत्तर तत्काल देता है और इन प्राचलों सहित किसी भी EMAT प्रश्न पर जाँच भी। विकल्प A स्वयं मेल की लागत है, जो अनुपात 100% के निकट पहुँचने की सीमा है पर 90% पर प्राप्त नहीं। विकल्प D भूल जाता है कि TLB पहुँच का मूल्य मेल पर भी लिया जाता है, जो केवल उस अतिव्यापी-खोज परिपाटी में सही होता जिसे यह प्रश्न प्रयोग नहीं करता। विकल्प C किसी भिन्न पाठ के बजाय भारण में अंकगणित-चूक से निकलता।