IPC, तुल्यकालन व गतिरोध

ये तीन उप-वस्तुएँ तीन विषय नहीं अपितु एक तर्क हैं, और उन्हें उस रूप में पढ़ना अधिकांश प्रश्नों को यथास्थान बैठा देता है। अंतर-प्रक्रिया संचार वह है जिससे पृथक् प्रक्रियाएँ सूचना का आदान-प्रदान करती हैं, और ठीक दो कुल हैं: साझा स्मृति, जहाँ कर्नेल एक क्षेत्र को दो पता-स्थानों में मानचित्रित कर देता है और फिर हट जाता है, तथा संदेश-प्रेषण, जहाँ प्रत्येक आदान-प्रदान कर्नेल से होकर जाता है। सौदा एक बार बताया और बारंबार पूछा जाता है — साझा स्मृति तीव्र है क्योंकि प्रति पहुँच कर्नेल संलग्न नहीं, और उसी कारण से वह तुल्यकालन को प्रोग्रामर की समस्या बना देती है; संदेश-प्रेषण मंद है क्योंकि प्रत्येक संदेश एक सिस्टम कॉल है, और उसी कारण से उसे किसी ताले की आवश्यकता नहीं। जिससे दूसरी वस्तु आती है: तुल्यकालन इसलिए विद्यमान है कि सहवर्ती प्रवाहों द्वारा पढ़ी व लिखी जाती साझा अवस्था ऐसे परिणाम देती है जो अंतर्वेशन पर निर्भर हैं, और दौड़ की स्थिति ठीक वही निर्भरता है। उपकरण सेमाफ़ोर है: दो अखंडित संक्रियाओं सहित एक पूर्णांक, P (प्रतीक्षा, घटाव) व V (संकेत, वृद्धि), और जानने योग्य सर्वाधिक उपयोगी बात यह है कि k पर आरंभित गणक सेमाफ़ोर क्रांतिक खंड में ठीक k प्रक्रियाएँ प्रवेश देता है, अतः म्यूटेक्स k = 1 की स्थिति है। तत्पश्चात् गतिरोध, जो असावधान रहने पर तुल्यकालन आपको खरीद देता है: चार शर्तें एक साथ सत्य होनी चाहिए — पारस्परिक अपवर्जन, धारण-और-प्रतीक्षा, अपूर्वाधिकरण, चक्रीय प्रतीक्षा — और प्रत्येक निवारण-रणनीति ठीक उनमें से एक पर आक्रमण है। संसूचन व परिवर्जन भिन्न प्रश्न हैं, और बैंकर कलनविधि परिवर्जन का उत्तर देती है: गतिरोध है क्या नहीं अपितु इस निवेदन को स्वीकारना कभी गतिरोध तक ले जा सकता है क्या।

साझा करने के दो मार्ग, तथा उनके बीच का सौदा

साझा स्मृति बनाम संदेश-प्रेषण
पक्षसाझा स्मृतिसंदेश-प्रेषण
कर्नेल की संलग्नताएक बार, क्षेत्र स्थापित करने हेतुप्रत्येक संदेश — प्रत्येक एक सिस्टम कॉल
गतितीव्रतर, स्मृति की गति परमंदतर, सिस्टम-कॉल की गति पर
तुल्यकालनप्रोग्रामर की समस्या — तालों की आवश्यकताकर्नेल की पंक्ति द्वारा सँभाला जाता
संजाल के आर-पारनहीं — एक भौतिक स्मृतिहाँ, इसीलिए वितरित तंत्र उसे प्रयोग करते हैं
ℹ️ उत्पादक–उपभोक्ता सेमाफ़ोर, तथा गिनतियाँ कहाँ से आती हैं
उत्पादक व उपभोक्ता द्वारा साझा n खानों का परिबद्ध बफ़र ठीक तीन सेमाफ़ोर चाहता है, और प्रत्येक आरंभिक मान निष्पादनीय है, यादृच्छिक नहीं। mutex = 1 स्वयं बफ़र-संरचना की रक्षा करता है — एक समय एक लेखक, अतः k = 1 की स्थिति। empty = n, क्योंकि आरंभ में n खाने हैं जिन्हें उत्पादक भर सकता है। full = 0, क्योंकि आरंभ में ऐसा कुछ नहीं जो उपभोक्ता ले सके। उत्पादक करता है P(empty); P(mutex); …; V(mutex); V(full) और उपभोक्ता full व empty बदले सहित दर्पण-प्रतिबिंब। इसके विषय में दो बातें परीक्षित होती हैं। प्रथम दो प्रतीक्षाओं का क्रम महत्व रखता है: स्थान की जाँच से पूर्व म्यूटेक्स लें और भरा बफ़र उत्पादक को सोते समय ताला धारण करते छोड़ देता है, अतः उपभोक्ता उसे कभी खाली नहीं कर सकता — सही अंशों से गलत क्रम में बना गतिरोध। तथा empty + full किसी संक्रिया के दौरान अपरिवर्ती नहीं, केवल उनके बीच, और इसीलिए किसी यादृच्छिक क्षण पर मान पूछते प्रश्न का उत्तर अंतर्वेशन से देना होता है, योग से नहीं।

सेमाफ़ोर, तथा उनका अंकगणित

गणक सेमाफ़ोर एक पूर्णांक तथा एक पंक्ति है, दो अखंडित संक्रियाओं सहित। P(S), S घटाता है; यदि परिणाम ऋणात्मक हो तो बुलाने वाला पंक्ति में रखा जाता है व अवरुद्ध होता है। V(S), S बढ़ाता है; यदि परिणाम अभी भी ≤ 0 हो तो कोई प्रतीक्षा में था, अतः एक प्रक्रिया मुक्त होती है। उस परिपाटी में मान एक साथ दो सूचनाएँ धारण करता है: जब S धनात्मक हो तो वह उन अतिरिक्त प्रक्रियाओं की संख्या है जो बिना अवरुद्ध हुए आगे बढ़ सकती हैं, और जब S ऋणात्मक हो तो |S| उस पर वर्तमान में अवरुद्ध प्रक्रियाओं की संख्या है। तब अंकगणित को कोई स्थिति-विश्लेषण चाहिए ही नहीं। s पर आरंभित सेमाफ़ोर p प्रतीक्षा-संक्रियाओं व v संकेत-संक्रियाओं के पश्चात् s − p + v मान रखता है, वे किसी भी क्रम में हुई हों, क्योंकि प्रत्येक संक्रिया अशर्त ±1 देती है। अतः 7 पर आरंभित सेमाफ़ोर 20 P व 15 V संक्रियाओं के पश्चात् 7 − 20 + 15 = 2 पर बैठता है।

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

गतिरोध: चार शर्तें, तथा बैंकर का प्रश्न

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

बैंकर कलनविधि परिवर्जन का उत्तर देती है। लें तीन संसाधन-प्रकार जिनका कुल (10, 5, 7) है तथा पाँच प्रक्रियाएँ जिनका आवंटन व अधिकतम नीचे दिया है। पाँचों में कुल आवंटित (7, 2, 5) है, अतः उपलब्ध = (3, 3, 2), तथा आवश्यकता = अधिकतम − आवंटन। कोई अवस्था सुरक्षित है यदि कोई क्रम विद्यमान हो जिसमें प्रत्येक प्रक्रिया समाप्त कर सके, प्रत्येक अपना आवंटन छोड़ते हुए अगली की सहायता करे। जाँच चलाएँ: केवल P1 (आवश्यकता 1,2,2) व P3 (आवश्यकता 0,1,1) ही (3, 3, 2) के भीतर बैठते हैं, अतः उनमें से एक को पहले जाना होगा; P1 लें, और उपलब्ध (5, 3, 2) हो जाता है; फिर P3 छोड़ता है, जिससे (7, 4, 3); और वहाँ से P0, P2 व P4 सब किसी क्रम में बैठ जाते हैं। अवस्था सुरक्षित है।

कुल (10, 5, 7); उपलब्ध = (3, 3, 2); आवश्यकता = अधिकतम − आवंटन
प्रक्रियाआवंटनअधिकतमआवश्यकता(3,3,2) में बैठती?
P0(0, 1, 0)(7, 5, 3)(7, 4, 3)नहीं
P1(2, 0, 0)(3, 2, 2)(1, 2, 2)हाँ
P2(3, 0, 2)(9, 0, 2)(6, 0, 0)नहीं
P3(2, 1, 1)(2, 2, 2)(0, 1, 1)हाँ
P4(0, 0, 2)(4, 3, 3)(4, 3, 1)नहीं
🎯 “वह” सुरक्षित अनुक्रम जैसी कोई वस्तु नहीं — इस अवस्था के 16 हैं
इन पाँच प्रक्रियाओं के सभी 120 क्रमों पर चलने से ठीक 16 सुरक्षित अनुक्रम मिलते हैं, उनमें P1→P3→P0→P2→P4, P1→P3→P4→P0→P2 व P3→P4→P1→P0→P2। अतः वह सुरक्षित अनुक्रम पूछता प्रश्न इस अवस्था पर कुरचित है, और अवस्था सुरक्षित है क्या यह पूछता प्रश्न स्वच्छ उत्तर रखता है, क्योंकि सुरक्षा का अर्थ है कम से कम एक ऐसा क्रम विद्यमान है। यहाँ वस्तुतः निर्धारित है आरंभ: उन 16 में प्रत्येक P1 या P3 से आरंभ होता है, और कारण अंतिम स्तंभ में दृश्य है — किसी अन्य प्रक्रिया की आवश्यकता (3, 3, 2) के भीतर नहीं बैठती। परीक्षा में वही आकार खोजने योग्य है। “कौन-सी प्रक्रिया को पहले स्वीकृति मिल सकती है?” सुरचित है और उत्तर {P1, P3} है; “सुरक्षित अनुक्रम क्या है?” हेतु प्रश्न को कोई बराबरी-भंजन नियम नियत करना चाहिए, और यदि उसने न किया हो, तो उस विकल्प को खोजें जो सुरक्षित अनुक्रम है, उसे नहीं जो आपने निकाल लिया।
🧠 एक-संसाधन सूत्र: m ≥ n(k − 1) + 1
एक संसाधन-प्रकार, n प्रक्रियाएँ, प्रत्येक को अंततः k इकाइयों तक चाहिए। तंत्र ठीक तब गतिरोध-मुक्त प्रत्याभूत है जब m ≥ n(k − 1) + 1, और निष्पादन एक बार करने योग्य है क्योंकि वह सूत्र को अविस्मरणीय बना देता है। निकृष्टतम स्थिति है प्रत्येक प्रक्रिया k − 1 इकाइयाँ धारण करती और एक और माँगती; उस अवस्था में n(k − 1) इकाइयाँ प्रतिबद्ध हैं और सब अटके हैं। एक अतिरिक्त इकाई उसे तोड़ देती है: उसे किसी भी प्रक्रिया को दें, वह प्रक्रिया k तक पहुँचती है, समाप्त करती है, और शेष हेतु सब k छोड़ देती है। अतः सीमा कुल निकृष्टतम धारण से ठीक एक ऊपर है। दो दिशाएँ पूछी जाती हैं। अग्रगामी: प्रत्येक अधिकतम 3 इकाइयों वाली 4 प्रक्रियाएँ m ≥ 4(2) + 1 = 9 सहित सुरक्षित हैं। पश्चगामी: m = 12 इकाइयों व प्रत्येक k = 4 सहित, n(3) + 1 ≤ 12 हल करें जिससे n ≤ 3.67, अतः अधिकतम 3 प्रक्रियाएँ — और निम्नतम पूर्णांक पर ध्यान दें, क्योंकि 4 प्रक्रियाओं को 13 चाहिए होते।

मुख्य बिंदु

  • साझा स्मृति तीव्र है व तालों की आवश्यकता रखती; संदेश-प्रेषण मंद है व किसी की नहीं — वही एक तथ्य दो बार।
  • k पर आरंभित गणक सेमाफ़ोर ठीक k प्रक्रियाएँ भीतर देता है; म्यूटेक्स k = 1 की स्थिति है।
  • p प्रतीक्षा व v संकेत के पश्चात् s पर आरंभित सेमाफ़ोर s − p + v रखता है, किसी भी क्रम में।
  • जब S ऋणात्मक हो, |S| उस पर अवरुद्ध प्रक्रियाओं की संख्या है।
  • उत्पादक–उपभोक्ता: mutex = 1, empty = n, full = 0 — और P(empty), P(mutex) से पूर्व आना चाहिए।
  • क्रांतिक-खंड समाधान की परीक्षा पहले प्रगति पर करें: एक प्रक्रिया को प्रवेश माँगना बंद करा दें।
  • चारों गतिरोध-शर्तें एक साथ सत्य होनी चाहिए; निवारण ठीक एक पर आक्रमण करता है, प्रायः चक्रीय प्रतीक्षा पर।
  • चक्र गतिरोध का अर्थ केवल प्रति प्रकार एक प्रति सहित है; सुरक्षा का अर्थ कम से कम एक सुरक्षित अनुक्रम विद्यमान है।

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

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

  1. कोई गणक सेमाफ़ोर 7 पर आरंभित है। तत्पश्चात् उस पर किसी अंतर्वेशित क्रम में 20 P (प्रतीक्षा) व 15 V (संकेत) संक्रियाएँ निष्पादित होती हैं। सेमाफ़ोर का अंतिम मान ______ है

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

    उत्तर देखें

    उत्तर: 2

    2। प्रत्येक P अशर्त −1 देता है और प्रत्येक V अशर्त +1, अतः अंतिम मान 7 − 20 + 15 = 2 है, और अंतर्वेशन उसे बदल नहीं सकता — इसीलिए प्रश्न “किसी अंतर्वेशित क्रम में” कह सकता है और कुछ भी अनिर्दिष्ट नहीं छोड़ता। क्रम पर अवरोध निर्भर है, अंकगणित नहीं: वह P जो मान को ऋणात्मक कर दे अपने बुलाने वाले को अवरुद्ध करता है, और पश्चात्वर्ती V एक को मुक्त करता है, पर दोनों ने पूर्णांक को एक से हिलाया ही। यहाँ अंतिम मान जो बताता है वह ध्यान देने योग्य है: 2 धनात्मक है, अतः कोई प्रक्रिया अवरुद्ध शेष नहीं, और दो और प्रक्रियाएँ बिना प्रतीक्षा पार हो सकती थीं। यदि उत्तर ऋणात्मक आया होता, तो उसका परिमाण अभी पंक्तिबद्ध प्रक्रियाओं की संख्या होता।

  2. तीन संसाधन-प्रकारों का कुल (10, 5, 7) है। आवंटन P0 (0,1,0), P1 (2,0,0), P2 (3,0,2), P3 (2,1,1), P4 (0,0,2) हैं, तथा अधिकतम माँग P0 (7,5,3), P1 (3,2,2), P2 (9,0,2), P3 (2,2,2), P4 (4,3,3)। किसी सुरक्षित अनुक्रम में प्रथम पूर्ण होने वाली प्रक्रियाएँ कौन हो सकती हैं?

    1. P1
    2. P2
    3. P3
    4. P0
    उत्तर देखें

    उत्तर: A — P1; C — P3

    P1 व P3। कुल आवंटित (7, 2, 5) है, अतः उपलब्ध = (10,5,7) − (7,2,5) = (3, 3, 2), और आवश्यकता = अधिकतम − आवंटन देता है P0 (7,4,3), P1 (1,2,2), P2 (6,0,0), P3 (0,1,1), P4 (4,3,1)। कोई प्रक्रिया प्रथम पूर्ण केवल तब हो सकती है जब उसकी सम्पूर्ण आवश्यकता वर्तमान उपलब्ध के भीतर बैठे, और प्रत्येक घटक जाँचने पर: P1 (1,2,2) ≤ (3,3,2) ✓ तथा P3 (0,1,1) ≤ (3,3,2) ✓, जबकि P0 प्रथम घटक पर विफल (7 > 3), P2 भी प्रथम पर विफल (6 > 3) यद्यपि उसे B या C कुछ नहीं चाहिए, और P4 भी प्रथम पर विफल (4 > 3)। सभी 120 क्रमों पर सम्पूर्ण चाल इसकी पुष्टि करती है: 16 सुरक्षित अनुक्रम हैं और उनमें प्रत्येक P1 या P3 से आरंभ होता है। ध्यान दें P2 शिक्षाप्रद गलत उत्तर है — दो संसाधन-प्रकारों की शून्य इकाइयाँ चाहना लगभग संतुष्ट होने जैसा दिखता है, पर सदिश तुलना घटकवार है और एक विफल घटक पर्याप्त है।

  3. एक संसाधन-प्रकार की m समरूप इकाइयाँ हैं, जो n प्रक्रियाओं द्वारा साझा हैं, प्रत्येक को अधिकतम k इकाइयाँ चाहिए। तंत्र गतिरोध-मुक्त कब प्रत्याभूत है?

    1. m ≥ nk
    2. m ≥ n(k − 1) + 1
    3. m ≥ n + k
    4. m ≥ nk − 1
    उत्तर देखें

    उत्तर: B — m ≥ n(k − 1) + 1

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

  4. किसी संसाधन-आवंटन ग्राफ में एक चक्र है। कौन-सा निष्कर्ष सही है?

    1. तंत्र गतिरुद्ध है
    2. तंत्र गतिरुद्ध केवल तब है यदि चक्र के प्रत्येक संसाधन-प्रकार की एकमात्र प्रति हो
    3. तंत्र गतिरुद्ध नहीं है
    4. तंत्र गतिरुद्ध केवल तब है यदि चक्र की लंबाई सम हो
    उत्तर देखें

    उत्तर: B — तंत्र गतिरुद्ध केवल तब है यदि चक्र के प्रत्येक संसाधन-प्रकार की एकमात्र प्रति हो

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

  5. परिबद्ध-बफ़र उत्पादक–उपभोक्ता समाधान में उत्पादक P(mutex) को P(empty) के पूर्व निष्पादित करता है, पश्चात् नहीं। परिणाम क्या है?

    1. कुछ नहीं बदलता; दोनों सेमाफ़ोर किसी भी प्रकार लिए जाते हैं
    2. पारस्परिक अपवर्जन का उल्लंघन होता है
    3. गतिरोध, जब उत्पादक म्यूटेक्स धारण करते हुए भरे बफ़र पर सो जाता है
    4. बफ़र n वस्तुओं से आगे अतिप्रवाहित हो सकता है
    उत्तर देखें

    उत्तर: C — गतिरोध, जब उत्पादक म्यूटेक्स धारण करते हुए भरे बफ़र पर सो जाता है

    गतिरोध। क्रम उलटने पर, भरे बफ़र का सामना करता उत्पादक पहले म्यूटेक्स लेता है और फिर empty पर अवरुद्ध होता है, अतः वह ताला धारण करते हुए ही सो जाता है। उपभोक्ता को अब वस्तु हटाने हेतु वही म्यूटेक्स चाहिए, वह उसे पा नहीं सकता, और अतः वह empty का संकेत कभी नहीं दे सकता — वह एकमात्र घटना जो उत्पादक को जगाती। प्रत्येक ऐसी वस्तु की प्रतीक्षा करता है जो केवल दूसरा दे सकता है, और वह दो ऐसी संक्रियाओं से जो व्यक्तिगत रूप से सही हैं। विकल्प A वही सहज बोध है जिसकी परीक्षा हो रही है और वह ठीक इसलिए गलत है कि अवरुद्ध प्रक्रिया अपना धारित नहीं छोड़ती। विकल्प B विफलता का प्रकार नहीं: पारस्परिक अपवर्जन यहाँ संरक्षित है, और वही इस दोष को समीक्षा में छूटने योग्य बनाता है। विकल्प D हेतु empty छोड़ा जाना चाहिए, केवल पुनर्क्रमित नहीं; गिनती अभी भी जाँची जाती है, बस बहुत देर से। यह जो सामान्य नियम दिखाता है: ताला धारण करते हुए कभी अवरुद्ध न हों।

  6. दो-प्रक्रिया क्रांतिक-खंड समाधान एकमात्र साझा चर turn प्रयोग करता है, प्रत्येक प्रक्रिया तब तक प्रतीक्षा करती है जब तक turn उसे नामित न करे। यह किस अपेक्षा में विफल है?

    1. पारस्परिक अपवर्जन
    2. प्रगति
    3. परिबद्ध प्रतीक्षा
    4. वह तीनों में किसी में विफल नहीं
    उत्तर देखें

    उत्तर: B — प्रगति

    प्रगति। एकमात्र turn चर कठोर एकांतरण लागू करता है, और वह समस्या की अपेक्षा से अधिक बलवान है। पारस्परिक अपवर्जन पूर्णतः टिकता है — turn का एक मान है, अतः कभी एक ही प्रक्रिया प्रवेश पाती है — और इसीलिए समाधान सही दिखता है। किंतु मानें P0 अपना क्रांतिक खंड छोड़ता है, turn को 1 करता है, और फिर पुनः कभी प्रवेश नहीं चाहता। P1 प्रवेश करती है, turn को पुनः 0 करती है, और अब स्थायी रूप से बाहर बंद है: क्रांतिक खंड रिक्त है, P1 भीतर आना चाहती है, और कोई प्रक्रिया भीतर नहीं, तथापि P1 आगे नहीं बढ़ सकती। वही ठीक प्रगति का उल्लंघन है। परिबद्ध प्रतीक्षा (विकल्प C) वस्तुतः संतुष्ट है — कठोर एकांतरण अतिक्रमण को एक पर परिबद्ध करता है, और यही इस समाधान की विडंबना है। पीटरसन की कलनविधि flag सरणी जोड़कर प्रगति सुधारती है, अतः प्रक्रिया घोषित करती है कि वह भीतर आना चाहती है और turn केवल वास्तविक बराबरी तोड़ने हेतु देखा जाता है।

  7. संदेश-प्रेषण की तुलना में साझा-स्मृति IPC तीव्रतर है क्योंकि:

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

    उत्तर: B — क्षेत्र मानचित्रित होने के पश्चात् कर्नेल प्रत्येक पहुँच में संलग्न नहीं होता

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

  8. प्रत्येक प्रक्रिया से संसाधन केवल किसी वैश्विक क्रमांकन के बढ़ते क्रम में माँगने की अपेक्षा किस गतिरोध-शर्त पर आक्रमण करती है?

    1. धारण-और-प्रतीक्षा
    2. पारस्परिक अपवर्जन
    3. चक्रीय प्रतीक्षा
    4. अपूर्वाधिकरण
    उत्तर देखें

    उत्तर: C — चक्रीय प्रतीक्षा

    चक्रीय प्रतीक्षा, और तर्क एक पंक्ति का है: प्रतीक्षारत प्रक्रियाओं के चक्र में किनारों का अनुसरण करते चारों ओर घूमकर आप वहीं लौटते हैं जहाँ से चले थे, अतः संसाधन-संख्याओं को पूरे चक्कर बढ़ते रहकर किसी लघुतर मान पर लौटना पड़ता, जो पूर्ण क्रम में असंभव है। चक्र की संभावना हटाना गतिरोध हटा देता है, क्योंकि चारों शर्तें एक साथ चाहिए। यही वह निवारण-रणनीति भी है जिसे वास्तविक तंत्र वस्तुतः अपनाते हैं — ताला-क्रम — क्योंकि शेष तीन आक्रमण अव्यावहारिक या महँगे हैं: पारस्परिक अपवर्जन प्रायः छोड़ा नहीं जा सकता (विकल्प B: प्रिंटर साझा योग्य नहीं), अपूर्वाधिकरण केवल वहाँ चलता है जहाँ संसाधन की अवस्था संचित व पुनःस्थापित हो सके (विकल्प D), और धारण-और-प्रतीक्षा तोड़ने का अर्थ है सब कुछ पहले ही माँगना (विकल्प A), जो क्षमता व्यर्थ करता है और लोकप्रिय संसाधन चाहती प्रक्रिया को भूखा रख सकता है।