प्राथमिकता व्युत्क्रमण
कंप्यूटर विज्ञान में, प्राथमिकता व्युत्क्रमण शेड्यूलिंग (कंप्यूटिंग) में एक रूपरेखा है जिसमें एक उच्च प्राथमिकता वाले कार्य (कंप्यूटिंग) को अप्रत्यक्ष रूप से कम प्राथमिकता वाले कार्य द्वारा प्रतिस्थापित किया जाता है, जिससे कार्यों की निर्दिष्ट प्राथमिकताओं को प्रभावी ढंग से बदल दिया जाता है। यह प्राथमिकता प्रतिरूपण का उल्लंघन करता है कि उच्च-प्राथमिकता वाले कार्यों को केवल उच्च-प्राथमिकता वाले कार्यों द्वारा संचालित करने रोका जा सकता है। जब कम-प्राथमिकता वाले कार्य के साथ संसाधन विवाद होता है जिसे मध्यम-प्राथमिकता वाले कार्य द्वारा पूर्वाधिकृत किया जाता है तब व्युत्क्रम होता है।
सूत्रीकरण
क्रमशः उच्च और निम्न प्राथमिकता वाले दो कार्यों H और L पर विचार करें, जिनमें से कोई भी संयुक्त संसाधन R का विशेष उपयोग प्राप्त कर सकता है। यदि L द्वारा R को प्राप्त करने के बाद H उसे प्राप्त करने का प्रयास करता है, तो H तब तक अवरुद्ध हो जाता है जब तक L संसाधन को त्याग नहीं देता है। अच्छी तरह से डिज़ाइन किए गए तंत्र में एक विशेष-उपयोग संसाधन R को साझा करने में सामान्यतौर पर L को R को तुरंत छोड़ना होता है ताकि H (एक उच्च प्राथमिकता वाला कार्य) अत्यधिक समय तक अवरुद्ध न रहे। हालाँकि, अच्छे डिज़ाइन के बावजूद, यह संभव है कि मध्यम प्राथमिकता वाला तीसरा कार्य M, L के R के उपयोग के दौरान सञ्चालन योग्य हो सकता है। इस बिंदु पर L की तुलना में M प्राथमिकता में अधिक है और M, R पर निर्भर नहीं है इसलिए L को पूर्वाधिकृत करता है जिसके कारण L तुरंत R को छोड़ने में सक्षम नहीं होता है, जिसके परिणामस्वरूप H - सर्वोच्च प्राथमिकता वाली प्रक्रिया -सञ्चालन में असमर्थ हो जाती है। अर्थात, H को M जैसे कम प्राथमिकता वाले कार्यों के कारण अप्रत्यक्ष रूप से अप्रत्याशित रुकावट का सामना करना पड़ता है।
परिणाम
कुछ स्थितियों में, उच्च-प्राथमिकता वाले कार्य के विलंबित निष्पादन पर किसी का ध्यान नहीं जाता है, और अंततः, कम-प्राथमिकता वाला कार्य साझा संसाधन जारी करता है जिसके परिणाम स्वरुप प्राथमिकता व्युत्क्रमण तत्काल क्षति पहुंचाए बिना हो सकता है । हालाँकि, ऐसी भी कई स्थितियाँ हैं जिनमें प्राथमिकता बदलने से गंभीर समस्याएँ पैदा हो सकती हैं। यदि उच्च-प्राथमिकता वाले कार्य को संसाधनों की कमी के कारण छोड़ दिया जाता है, तो इससे तंत्र में खराबी हो सकती है या पूर्व-परिभाषित संशोधक उपायों को सक्रिय किया जा सकता है, जैसे कि संरक्षक अवधि पूरे तंत्र को प्रतिस्थापित कर रहा है। वास्तविक समय गणना प्रणालियों में प्राथमिकता व्युत्क्रमण के कारण होने वाली समस्याओं का एक उत्कृष्ट उदाहरण 1997 में मंगल ग्रह पथप्रदर्शक लैंडर द्वारा अनुभव की गई परेशानी है।[1] [2]
प्राथमिकता व्युत्क्रमण तंत्र के कथित प्रदर्शन को भी कम कर सकता है। कम-प्राथमिकता वाले कार्यों की प्राथमिकता सामान्यतौर पर कम होती है, उदाहरण के लिए, वे बैच कार्य या अन्य गैर-संवादात्मक गतिविधि हो सकते हैं क्योंकि उनके लिए कार्य तुरंत समाप्त करना महत्वपूर्ण नहीं है। इसी तरह, एक उच्च-प्राथमिकता वाले कार्य की उच्च प्राथमिकता होती है क्योंकि यह सख्त समय की बाधाओं के अधीन होने की अधिक संभावना है - यह एक संवादात्मक उपयोगकर्ता को डेटा प्रदान करना हो सकता है, या वास्तविक समय प्रतिक्रिया गारंटी के अधीन कार्य करना हो सकता है। क्योंकि प्राथमिकता व्युत्क्रमण के परिणामस्वरूप निम्न-प्राथमिकता वाले कार्य का निष्पादन उच्च-प्राथमिकता वाले कार्य को अवरुद्ध कर देता है, इससे तंत्र की प्रतिक्रिया कम हो सकती है या यहां तक कि प्रतिक्रिया समय की गारंटी का उल्लंघन भी हो सकता है।
जल्द से जल्द समय सीमा का पहला निर्धारण#डेडलाइन इंटरचेंज नामक एक समान समस्या अर्लीएस्ट डेडलाइन फर्स्ट शेड्यूलिंग (ईडीएफ) के भीतर हो सकती है।
समाधान
इस समस्या का अस्तित्व 1970 के दशक से ज्ञात है। लैम्पसन और रेडेल [3] प्राथमिकता व्युत्क्रमण समस्या को इंगित करने वाले पहले पत्रों में से एक प्रकाशित किया। UNIX कर्नेल जैसे तंत्र पहले से ही splx() प्रिमिटिव के साथ समस्या का समाधान कर रहे थे। स्थिति की भविष्यवाणी करने का कोई अचूक तरीका नहीं है। हालाँकि, कई मौजूदा समाधान हैं, जिनमें से सबसे आम हैं:
- महत्वपूर्ण अनुभागों की सुरक्षा के लिए सभी व्यवधानों को अक्षम करना
- जब इंटरप्ट को अक्षम करने का उपयोग प्राथमिकता व्युत्क्रमण को रोकने के लिए किया जाता है, तो केवल दो प्राथमिकताएं होती हैं: प्रीएम्प्टेबल, और इंटरप्ट अक्षम। तीसरी प्राथमिकता के बिना, व्युत्क्रमण असंभव है। चूँकि लॉक डेटा का केवल एक टुकड़ा (इंटरप्ट-सक्षम बिट) है, गलत तरीके से लॉक करना असंभव है, और इसलिए गतिरोध उत्पन्न नहीं हो सकता है। चूंकि महत्वपूर्ण क्षेत्र हमेशा पूरा होने तक चलते हैं, इसलिए हैंग नहीं होते हैं। ध्यान दें कि यह केवल तभी काम करता है जब सभी व्यवधान अक्षम हों। यदि केवल एक विशेष हार्डवेयर डिवाइस का इंटरप्ट अक्षम किया गया है, तो हार्डवेयर द्वारा इंटरप्ट की प्राथमिकता को प्राथमिकता व्युत्क्रमण द्वारा पुनः प्रस्तुत किया जाता है। UNIX के शुरुआती संस्करणों में, splx(0) ... splx(7) नामक प्राइमेटिव्स की एक श्रृंखला ने दी गई प्राथमिकता के माध्यम से सभी व्यवधानों को अक्षम कर दिया। महत्वपूर्ण अनुभाग में प्रवेश करने वाले किसी भी व्यवधान की सर्वोच्च प्राथमिकता को सही ढंग से चुनकर, सभी व्यवधानों को लॉक किए बिना प्राथमिकता व्युत्क्रम समस्या को हल किया जा सकता है। सीलिंग को दर-मोनोटोनिक शेड्यूलिंग |रेट-मोनोटोनिक क्रम में सौंपा गया था, यानी धीमी डिवाइसों की प्राथमिकताएं कम थीं।
- कई सीपीयू तंत्र में, एक साधारण व्युत्क्रमण, सिंगल शेयर्ड-फ्लैग लॉकिंग का उपयोग किया जाता है। यह योजना साझा मेमोरी में एक एकल ध्वज प्रदान करती है जिसका उपयोग सभी सीपीयू द्वारा सभी इंटर-प्रोसेसर महत्वपूर्ण अनुभागों को व्यस्त-प्रतीक्षा के साथ लॉक करने के लिए किया जाता है। अधिकांश एकाधिक सीपीयू तंत्र पर इंटरप्रोसेसर संचार महंगा और धीमा है। इसलिए, ऐसी अधिकांश प्रणालियाँ साझा संसाधनों को न्यूनतम करने के लिए डिज़ाइन की गई हैं। परिणामस्वरूप, यह योजना वास्तव में कई व्यावहारिक प्रणालियों पर अच्छा काम करती है। इन विधियों का व्यापक रूप से सरल अंतः स्थापित प्रणाली में उपयोग किया जाता है, जहां उन्हें उनकी विश्वसनीयता, सादगी और कम संसाधन उपयोग के लिए मूल्यवान माना जाता है। इन योजनाओं में महत्वपूर्ण अनुभागों को बहुत संक्षिप्त रखने के लिए चतुर प्रोग्रामिंग की भी आवश्यकता होती है। कई सॉफ्टवेयर इंजीनियर इन्हें सामान्य प्रयोजन के कंप्यूटरों में अव्यवहारिक मानते हैं।
- प्राथमिकता छत प्रोटोकॉल
- प्राथमिकता सीलिंग प्रोटोकॉल के साथ, साझा पारस्परिक बहिष्करण प्रक्रिया (जो प्रचालन तंत्र कोड को चलाती है) की अपनी एक विशेषता (उच्च) प्राथमिकता होती है, जिसे म्यूटेक्स को लॉक करने का कार्य सौंपा जाता है। यह अच्छी तरह से काम करता है, बशर्ते कि अन्य उच्च-प्राथमिकता वाले कार्य जो म्यूटेक्स तक पहुंचने का प्रयास करते हैं, उनकी प्राथमिकता अधिकतम प्राथमिकता से अधिक न हो।
- प्राथमिकता विरासत
- प्राथमिकता विरासत की नीति के तहत, जब भी किसी उच्च-प्राथमिकता वाले कार्य को निष्पादित कम-प्राथमिकता वाले कार्य के साथ साझा किए गए कुछ संसाधनों के लिए इंतजार करना पड़ता है, तो कम-प्राथमिकता वाले कार्य को अस्थायी रूप से उसकी अवधि के लिए उच्चतम प्रतीक्षा प्राथमिकता वाले कार्य की प्राथमिकता सौंपी जाती है। साझा संसाधन का स्वयं का उपयोग, इस प्रकार मध्यम प्राथमिकता वाले कार्यों को (मूल रूप से) कम प्राथमिकता वाले कार्य को रोकने से रोकता है, और इस प्रकार प्रतीक्षारत उच्च प्राथमिकता वाले कार्य को भी प्रभावित करता है। एक बार संसाधन जारी होने के बाद, कम प्राथमिकता वाला कार्य अपने मूल प्राथमिकता स्तर पर जारी रहता है।
- यादृच्छिक बूस्टिंग
- जब तक वे महत्वपूर्ण अनुभाग से बाहर नहीं निकल जाते, तब तक लॉक रखने वाले तैयार कार्यों को प्राथमिकता में यादृच्छिक वृद्धि किया जाता है। इस समाधान का उपयोग Microsoft Windows में किया जाता है.[4]
- ब्लॉक करने से बचें
- क्योंकि प्राथमिकता व्युत्क्रमण में उच्च-प्राथमिकता वाले कार्य को अवरुद्ध करने वाला कम-प्राथमिकता वाला कार्य शामिल होता है, प्राथमिकता व्युत्क्रमण से बचने का एक तरीका अवरोधन से बचना है, उदाहरण के लिए पढ़ें-कॉपी-अपडेट करें जैसे गैर-अवरुद्ध L्गोरिदम का उपयोग करना।
यह भी देखें
संदर्भ
- ↑ Explanation of priority inversion problem experienced by Mars Pathfinder (PDF), retrieved 2019-01-04
- ↑ Glenn Reeves, What Really Happened on Mars, JPL Pathfinder team, retrieved 2019-01-04
- ↑ Lampson, B; Redell, D. (June 1980). "MESA में प्रक्रियाओं और मॉनिटरों के साथ अनुभव". Communications of the ACM. 23 (2): 105–117. CiteSeerX 10.1.1.46.7240. doi:10.1145/358818.358824. S2CID 1594544.
- ↑ Priority Inversion on MSDN
