प्राथमिकता व्युत्क्रमण
कंप्यूटर विज्ञान में, प्राथमिकता व्युत्क्रमण शेड्यूलिंग (कंप्यूटिंग) में एक परिदृश्य है जिसमें एक उच्च प्राथमिकता वाले कार्य (कंप्यूटिंग) को अप्रत्यक्ष रूप से कम प्राथमिकता वाले कार्य द्वारा प्रतिस्थापित किया जाता है, जिससे कार्यों की निर्दिष्ट प्राथमिकताओं को प्रभावी ढंग से उलट दिया जाता है। यह प्राथमिकता मॉडल का उल्लंघन करता है कि उच्च-प्राथमिकता वाले कार्यों को केवल उच्च-प्राथमिकता वाले कार्यों द्वारा चलने से रोका जा सकता है। व्युत्क्रम तब होता है जब कम-प्राथमिकता वाले कार्य के साथ संसाधन विवाद होता है जिसे तब मध्यम-प्राथमिकता वाले कार्य द्वारा प्रीएम्प्शन (कंप्यूटिंग) किया जाता है।
सूत्रीकरण
क्रमशः उच्च और निम्न प्राथमिकता वाले दो कार्यों H और L पर विचार करें, जिनमें से कोई भी साझा संसाधन R का विशेष उपयोग प्राप्त कर सकता है। यदि L द्वारा R को प्राप्त करने के बाद H उसे प्राप्त करने का प्रयास करता है, तो H तब तक अवरुद्ध हो जाता है जब तक L संसाधन को त्याग नहीं देता। एक अच्छी तरह से डिज़ाइन किए गए सिस्टम में एक विशेष-उपयोग संसाधन (इस मामले में आर) को साझा करने में आम तौर पर एल को आर को तुरंत छोड़ना शामिल होता है ताकि एच (एक उच्च प्राथमिकता वाला कार्य) अत्यधिक समय तक अवरुद्ध न रहे। हालाँकि, अच्छे डिज़ाइन के बावजूद, यह संभव है कि मध्यम प्राथमिकता वाला तीसरा कार्य M, L' के R के उपयोग के दौरान चलने योग्य हो जाता है। इस बिंदु पर, M, L की तुलना में प्राथमिकता में अधिक है, L को रोकता है (चूंकि एम, आर पर निर्भर नहीं है), जिसके कारण एल तुरंत आर को छोड़ने में सक्षम नहीं है, जिसके परिणामस्वरूप एच - सर्वोच्च प्राथमिकता वाली प्रक्रिया - चलने में असमर्थ है (अर्थात, एच को एम जैसे कम प्राथमिकता वाले कार्यों के कारण अप्रत्यक्ष रूप से अप्रत्याशित रुकावट का सामना करना पड़ता है। ).
परिणाम
कुछ मामलों में, प्राथमिकता उलटाव तत्काल नुकसान पहुंचाए बिना हो सकता है - उच्च-प्राथमिकता वाले कार्य के विलंबित निष्पादन पर किसी का ध्यान नहीं जाता है, और अंततः, कम-प्राथमिकता वाला कार्य साझा संसाधन जारी करता है। हालाँकि, ऐसी भी कई स्थितियाँ हैं जिनमें प्राथमिकता उलटने से गंभीर समस्याएँ पैदा हो सकती हैं। यदि उच्च-प्राथमिकता वाले कार्य को संसाधनों की कमी के कारण छोड़ दिया जाता है, तो इससे सिस्टम में खराबी हो सकती है या पूर्व-परिभाषित सुधारात्मक उपायों को ट्रिगर किया जा सकता है, जैसे कि निगरानी घड़ी पूरे सिस्टम को रीसेट कर रहा है। 1997 में मंगल ग्रह पथप्रदर्शक लैंडर द्वारा अनुभव की गई परेशानी[1][2] वास्तविक समय कंप्यूटिंग प्रणालियों में प्राथमिकता व्युत्क्रमण के कारण होने वाली समस्याओं का एक उत्कृष्ट उदाहरण है।
प्राथमिकता उलटा सिस्टम के कथित प्रदर्शन को भी कम कर सकता है। कम-प्राथमिकता वाले कार्यों की प्राथमिकता आमतौर पर कम होती है क्योंकि उनके लिए तुरंत समाप्त करना महत्वपूर्ण नहीं है (उदाहरण के लिए, वे बैच कार्य या अन्य गैर-संवादात्मक गतिविधि हो सकते हैं)। इसी तरह, एक उच्च-प्राथमिकता वाले कार्य की उच्च प्राथमिकता होती है क्योंकि यह सख्त समय की बाधाओं के अधीन होने की अधिक संभावना है - यह एक इंटरैक्टिव उपयोगकर्ता को डेटा प्रदान करना हो सकता है, या वास्तविक समय प्रतिक्रिया गारंटी के अधीन कार्य करना हो सकता है। क्योंकि प्राथमिकता व्युत्क्रमण के परिणामस्वरूप निम्न-प्राथमिकता वाले कार्य का निष्पादन उच्च-प्राथमिकता वाले कार्य को अवरुद्ध कर देता है, इससे सिस्टम की प्रतिक्रिया कम हो सकती है या यहां तक कि प्रतिक्रिया समय की गारंटी का उल्लंघन भी हो सकता है।
जल्द से जल्द समय सीमा का पहला निर्धारण#डेडलाइन इंटरचेंज नामक एक समान समस्या अर्लीएस्ट डेडलाइन फर्स्ट शेड्यूलिंग (ईडीएफ) के भीतर हो सकती है।
समाधान
इस समस्या का अस्तित्व 1970 के दशक से ज्ञात है। लैम्पसन और रेडेल [3] प्राथमिकता व्युत्क्रमण समस्या को इंगित करने वाले पहले पत्रों में से एक प्रकाशित किया। UNIX कर्नेल जैसे सिस्टम पहले से ही splx() प्रिमिटिव के साथ समस्या का समाधान कर रहे थे। स्थिति की भविष्यवाणी करने का कोई अचूक तरीका नहीं है। हालाँकि, कई मौजूदा समाधान हैं, जिनमें से सबसे आम हैं:
- महत्वपूर्ण अनुभागों की सुरक्षा के लिए सभी व्यवधानों को अक्षम करना
- जब इंटरप्ट को अक्षम करने का उपयोग प्राथमिकता व्युत्क्रमण को रोकने के लिए किया जाता है, तो केवल दो प्राथमिकताएं होती हैं: प्रीएम्प्टेबल, और इंटरप्ट अक्षम। तीसरी प्राथमिकता के बिना, व्युत्क्रमण असंभव है। चूँकि लॉक डेटा का केवल एक टुकड़ा (इंटरप्ट-सक्षम बिट) है, गलत तरीके से लॉक करना असंभव है, और इसलिए गतिरोध उत्पन्न नहीं हो सकता है। चूंकि महत्वपूर्ण क्षेत्र हमेशा पूरा होने तक चलते हैं, इसलिए हैंग नहीं होते हैं। ध्यान दें कि यह केवल तभी काम करता है जब सभी व्यवधान अक्षम हों। यदि केवल एक विशेष हार्डवेयर डिवाइस का इंटरप्ट अक्षम किया गया है, तो हार्डवेयर द्वारा इंटरप्ट की प्राथमिकता को प्राथमिकता व्युत्क्रमण द्वारा पुनः प्रस्तुत किया जाता है। UNIX के शुरुआती संस्करणों में, splx(0) ... splx(7) नामक प्राइमेटिव्स की एक श्रृंखला ने दी गई प्राथमिकता के माध्यम से सभी व्यवधानों को अक्षम कर दिया। महत्वपूर्ण अनुभाग में प्रवेश करने वाले किसी भी व्यवधान की सर्वोच्च प्राथमिकता को सही ढंग से चुनकर, सभी व्यवधानों को लॉक किए बिना प्राथमिकता व्युत्क्रम समस्या को हल किया जा सकता है। सीलिंग को दर-मोनोटोनिक शेड्यूलिंग |रेट-मोनोटोनिक क्रम में सौंपा गया था, यानी धीमी डिवाइसों की प्राथमिकताएं कम थीं।
- कई सीपीयू सिस्टम में, एक साधारण बदलाव, सिंगल शेयर्ड-फ्लैग लॉकिंग का उपयोग किया जाता है। यह योजना साझा मेमोरी में एक एकल ध्वज प्रदान करती है जिसका उपयोग सभी सीपीयू द्वारा सभी इंटर-प्रोसेसर महत्वपूर्ण अनुभागों को व्यस्त-प्रतीक्षा के साथ लॉक करने के लिए किया जाता है। अधिकांश एकाधिक सीपीयू सिस्टम पर इंटरप्रोसेसर संचार महंगा और धीमा है। इसलिए, ऐसी अधिकांश प्रणालियाँ साझा संसाधनों को न्यूनतम करने के लिए डिज़ाइन की गई हैं। परिणामस्वरूप, यह योजना वास्तव में कई व्यावहारिक प्रणालियों पर अच्छा काम करती है। इन विधियों का व्यापक रूप से सरल अंतः स्थापित प्रणाली में उपयोग किया जाता है, जहां उन्हें उनकी विश्वसनीयता, सादगी और कम संसाधन उपयोग के लिए मूल्यवान माना जाता है। इन योजनाओं में महत्वपूर्ण अनुभागों को बहुत संक्षिप्त रखने के लिए चतुर प्रोग्रामिंग की भी आवश्यकता होती है। कई सॉफ्टवेयर इंजीनियर इन्हें सामान्य प्रयोजन के कंप्यूटरों में अव्यवहारिक मानते हैं।[citation needed]
- प्राथमिकता छत प्रोटोकॉल
- प्राथमिकता सीलिंग प्रोटोकॉल के साथ, साझा पारस्परिक बहिष्करण प्रक्रिया (जो ऑपरेटिंग सिस्टम कोड को चलाती है) की अपनी एक विशेषता (उच्च) प्राथमिकता होती है, जिसे म्यूटेक्स को लॉक करने का कार्य सौंपा जाता है। यह अच्छी तरह से काम करता है, बशर्ते कि अन्य उच्च-प्राथमिकता वाले कार्य जो म्यूटेक्स तक पहुंचने का प्रयास करते हैं, उनकी प्राथमिकता अधिकतम प्राथमिकता से अधिक न हो।
- प्राथमिकता विरासत
- प्राथमिकता विरासत की नीति के तहत, जब भी किसी उच्च-प्राथमिकता वाले कार्य को निष्पादित कम-प्राथमिकता वाले कार्य के साथ साझा किए गए कुछ संसाधनों के लिए इंतजार करना पड़ता है, तो कम-प्राथमिकता वाले कार्य को अस्थायी रूप से उसकी अवधि के लिए उच्चतम प्रतीक्षा प्राथमिकता वाले कार्य की प्राथमिकता सौंपी जाती है। साझा संसाधन का स्वयं का उपयोग, इस प्रकार मध्यम प्राथमिकता वाले कार्यों को (मूल रूप से) कम प्राथमिकता वाले कार्य को रोकने से रोकता है, और इस प्रकार प्रतीक्षारत उच्च प्राथमिकता वाले कार्य को भी प्रभावित करता है। एक बार संसाधन जारी होने के बाद, कम प्राथमिकता वाला कार्य अपने मूल प्राथमिकता स्तर पर जारी रहता है।
- यादृच्छिक बूस्टिंग
- जब तक वे महत्वपूर्ण अनुभाग से बाहर नहीं निकल जाते, तब तक लॉक रखने वाले तैयार कार्यों को प्राथमिकता में यादृच्छिक वृद्धि किया जाता है। इस समाधान का उपयोग Microsoft Windows में किया जाता है.[4]
- ब्लॉक करने से बचें
- क्योंकि प्राथमिकता व्युत्क्रमण में उच्च-प्राथमिकता वाले कार्य को अवरुद्ध करने वाला कम-प्राथमिकता वाला कार्य शामिल होता है, प्राथमिकता व्युत्क्रमण से बचने का एक तरीका अवरोधन से बचना है, उदाहरण के लिए पढ़ें-कॉपी-अपडेट करें जैसे गैर-अवरुद्ध एल्गोरिदम का उपयोग करना।
यह भी देखें
संदर्भ
- ↑ Glenn Reeves, What Really Happened on Mars, JPL Pathfinder team, retrieved 2019-01-04
- ↑ Explanation of priority inversion problem experienced by Mars Pathfinder (PDF), 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
