दिन की सबसे ज़रूरी मीटिंग से पहले एक टीम लीडर मीटिंग रूम की चाबी का इंतज़ार कर रहा है। लेकिन चाबी रखने वाले नए कर्मचारी को दूसरे सीनियर बार-बार छोटे-मोटे कामों के लिए बुला लेते हैं, इसलिए वह कमरा खाली ही नहीं कर पाता। सबसे ज़रूरी काम सबसे आख़िर में होने की यह अजीब स्थिति कंप्यूटर के भीतर भी ठीक इसी तरह होती है, और इसे ‘प्राथमिकता व्युत्क्रमण (Priority Inversion)’ कहते हैं।
सरल शब्दों में, प्राथमिकता व्युत्क्रमण का अर्थ है ‘ऊँची प्राथमिकता वाला कार्य, निम्न प्राथमिकता वाले कार्य के पास मौजूद साझा संसाधन का इंतज़ार करते हुए, असल में और भी नीची प्राथमिकता पर धकेल दिया जाता है।’ यह उन रीयल-टाइम सिस्टमों में लंबे समय से जानी-पहचानी समस्या है, जहाँ कई कार्य तय प्राथमिकता के अनुसार प्रोसेसर साझा करते हैं। 1997 में मंगल यान मार्स पाथफ़ाइंडर (Mars Pathfinder) के मंगल पर बार-बार रीस्टार्ट होने के बाद यह व्यापक रूप से जानी गई।
इस लेख में हम क्रम से देखेंगे कि प्राथमिकता व्युत्क्रमण कैसे होता है, तीन कार्यों के ज़रिए इसका काम करने का तरीका, मंगल पर सचमुच हुई पाथफ़ाइंडर घटना, और अंत में इसे रोकने के उपाय व इससे मिलने वाले सबक।
जब ऊँची प्राथमिकता नीची प्राथमिकता का इंतज़ार करे
1. प्राथमिकता व्युत्क्रमण कैसे होता है?

प्राथमिकता शेड्यूलिंग में, चलने के लिए तैयार कार्यों में से सबसे ऊँची प्राथमिकता वाला कार्य हमेशा पहले प्रोसेसर पाता है। यह सीधा-सा नियम तब डगमगाने लगता है जब कई कार्य एक ही संसाधन साझा करते हैं।
(1) साझा संसाधन और लॉक
अगर कई कार्य एक साथ एक ही मेमोरी या डिवाइस को बदलें, तो डेटा गड़बड़ा जाता है। इसलिए ऑपरेटिंग सिस्टम म्यूटेक्स (Mutex) जैसे लॉक रखता है, ताकि एक समय में केवल एक कार्य संसाधन का उपयोग करे। जो कार्य पहले लॉक पकड़ लेता है, वह प्राथमिकता चाहे जो हो, काम पूरा करके लॉक छोड़ने तक संसाधन पर अकेले कब्ज़ा रखता है।
(2) उच्च कार्य का इंतज़ार
जब निम्न प्राथमिकता वाला कार्य लॉक पकड़े हुए हो और उच्च प्राथमिकता वाला कार्य वही संसाधन माँगे, तो उच्च कार्य को लॉक छूटने तक रुकना पड़ता है। निम्न कार्य अपना छोटा क्रिटिकल सेक्शन पूरा करते ही लॉक छोड़ देता है, इसलिए इतना इंतज़ार पहले से गिना जा सकने वाला ‘सीमित व्युत्क्रमण’ है।
(3) मध्यम कार्य का बीच में घुसना
असली परेशानी तब शुरू होती है जब इसी बीच लॉक से कोई संबंध न रखने वाला मध्यम प्राथमिकता का कार्य जाग जाता है। मध्यम कार्य की प्राथमिकता निम्न कार्य से ऊँची है, इसलिए वह प्रोसेसर छीन लेता है और निम्न कार्य लॉक पकड़े-पकड़े रुक जाता है। आख़िरकार उच्च कार्य को अपने से नीची प्राथमिकता वाले मध्यम कार्य के ख़त्म होने तक इंतज़ार करना पड़ता है, और मध्यम कार्य ज़्यादा हों तो इंतज़ार का कोई अंत नहीं रहता।
2. तीन कार्यों से समझें काम करने का तरीका

प्राथमिकता व्युत्क्रमण को आम तौर पर उच्च, मध्यम और निम्न तीन कार्यों से समझाया जाता है। केवल प्राथमिकता देखें तो उच्च कार्य को सबसे पहले पूरा होना चाहिए, लेकिन बीच में एक लॉक आते ही असली क्रम उलट जाता है।

- प्राथमिकता शेड्यूलिंग (Priority Scheduling): हर कार्य को प्राथमिकता देकर, तैयार कार्यों में सबसे ऊँची प्राथमिकता वाले को पहले चलाने का तरीका। उच्च कार्य जागते ही निम्न कार्य को रोककर प्रोसेसर ले लेता है।
- म्यूटेक्स (Mutex): पारस्परिक अपवर्जन (Mutual Exclusion) का संक्षिप्त रूप; ऐसा लॉक जो एक समय में केवल एक कार्य को साझा संसाधन इस्तेमाल करने देता है।
- क्रिटिकल सेक्शन (Critical Section): लॉक पकड़े रहकर साझा संसाधन पर काम करने वाला कोड का हिस्सा। यह जितना छोटा हो, दूसरे कार्यों का इंतज़ार उतना कम होता है।
- सीमित और असीमित व्युत्क्रमण (Bounded and Unbounded Inversion): अगर उच्च कार्य केवल निम्न कार्य के क्रिटिकल सेक्शन जितना इंतज़ार करे तो वह सीमित व्युत्क्रमण है; अगर मध्यम कार्य भी बीच में घुस आएँ और इंतज़ार की ऊपरी सीमा तय न हो सके, तो वह असीमित व्युत्क्रमण है।
रीयल-टाइम सिस्टम में ख़तरनाक असीमित व्युत्क्रमण है, क्योंकि तय समय में हर हाल में पूरा होने वाला कार्य कब पूरा होगा, यह जानने का कोई तरीका नहीं रहता। ऊपर से हर कार्य नियम के अनुसार प्राथमिकता का पालन करता दिखता है, फिर भी कुल नतीजा ऐसा लगता है मानो प्राथमिकताएँ उलट गई हों; यही बात इस समस्या को पकड़ना कठिन बनाती है।
3. मंगल पर हुई पाथफ़ाइंडर घटना

प्राथमिकता व्युत्क्रमण को दुनिया भर में सबसे ज़्यादा मशहूर करने वाली घटना मंगल पर हुई। 4 जुलाई 1997 को मंगल पर उतरे अमेरिकी अंतरिक्ष एजेंसी नासा (NASA) के मार्स पाथफ़ाइंडर में उतरने के कुछ दिन बाद से पूरा सिस्टम अचानक रीस्टार्ट होने लगा।
(1) बार-बार रीस्टार्ट
पाथफ़ाइंडर का कंप्यूटर विंड रिवर सिस्टम्स (Wind River Systems) के रीयल-टाइम ऑपरेटिंग सिस्टम VxWorks पर चलता था। समस्या लगभग उसी समय सामने आई जब यान ने मौसम का डेटा जुटाना शुरू किया। हर रीस्टार्ट से उस दिन का तय काम अगले दिन पर टल जाता था, इसलिए पृथ्वी पर संचालन टीम को जल्दी से कारण खोजना था।
(2) पृथ्वी पर दोहराया गया कारण
जेट प्रोपल्शन लेबोरेटरी (JPL) की टीम ने पृथ्वी पर परीक्षण उपकरण में ट्रेस (रिकॉर्डिंग) सुविधा चालू करके वही स्थिति चलाई और 18 घंटे से कम समय में रीस्टार्ट को फिर से पैदा करने में सफल रही। कारण किताबी उदाहरण जैसा प्राथमिकता व्युत्क्रमण था। निम्न प्राथमिकता वाला मौसम डेटा कार्य जब लॉक पकड़े हुए था, तब मध्यम प्राथमिकता के कार्य चलते रहे, और उसी लॉक का इंतज़ार कर रहा उच्च प्राथमिकता वाला सूचना बस प्रबंधन कार्य तय चक्र में पूरा नहीं हो सका। इसे पकड़ने वाले ऊपरी प्रबंधन कार्य ने इसे गंभीर त्रुटि माना और रीस्टार्ट कर दिया।
(3) एक ग्लोबल वेरिएबल से दूर बैठे सुधार
समस्या वाला लॉक डिफ़ॉल्ट सेटिंग से बना था, जिसमें प्रदर्शन के कारण प्राथमिकता वंशानुक्रम सुविधा बंद थी। टीम ने इस सुविधा को चालू करने के लिए एक ग्लोबल वेरिएबल का मान बदलने वाला पैच मंगल पर मौजूद यान को भेजा और समस्या हल हो गई। उसी साल दिसंबर में एक रीयल-टाइम सिस्टम सम्मेलन में बताए जाने के बाद यह मामला व्यापक रूप से चर्चित हुआ, और फ़्लाइट सॉफ़्टवेयर टीम के प्रमुख ग्लेन रीव्स (Glenn Reeves) ने भी ख़ुद पूरी घटना समझाई।
4. प्राथमिकता व्युत्क्रमण रोकने के उपाय

जब तक लॉक इस्तेमाल होते हैं, प्राथमिकता व्युत्क्रमण को पूरी तरह मिटाना कठिन है, लेकिन इंतज़ार को अंतहीन रूप से लंबा होने से रोका जा सकता है। इसके प्रमुख समाधान 1990 में Lui Sha, Ragunathan Rajkumar और John Lehoczky द्वारा प्रकाशित प्राथमिकता वंशानुक्रम प्रोटोकॉल (Priority Inheritance Protocols) संबंधी शोधपत्र में दिए गए हैं।
(1) प्राथमिकता वंशानुक्रम
जैसे ही उच्च कार्य लॉक का इंतज़ार शुरू करता है, लॉक पकड़े निम्न कार्य की प्राथमिकता कुछ देर के लिए उच्च कार्य के बराबर कर दी जाती है। तब मध्यम कार्य बीच में नहीं घुस पाता, और निम्न कार्य जल्दी क्रिटिकल सेक्शन पूरा करके लॉक छोड़ते ही अपनी मूल प्राथमिकता पर लौट आता है। पाथफ़ाइंडर को बचाने वाला तरीका यही था।
(2) प्राथमिकता सीमा प्रोटोकॉल
इसमें हर लॉक के लिए, उसे इस्तेमाल कर सकने वाले कार्यों में सबसे ऊँची प्राथमिकता को ‘सीमा’ के रूप में पहले से तय कर दिया जाता है। उसी शोधपत्र में सुझाया गया यह तरीका अधिकतम इंतज़ार को पहले से गिनने देता है और लॉकों के आपस में फँसकर सब कुछ ठप होने वाली डेडलॉक स्थिति को भी रोकता है।
(3) डिज़ाइन से मिलने वाले सबक
लॉक पकड़ने वाले हिस्सों को छोटा रखना, और ऐसा डिज़ाइन करना कि बहुत अलग प्राथमिकता वाले कार्य एक ही संसाधन साझा न करें, यह भी अहम है। आज कई रीयल-टाइम ऑपरेटिंग सिस्टम और लिनक्स भी प्राथमिकता वंशानुक्रम वाले लॉक देते हैं। पाथफ़ाइंडर का मामला यह भी दिखाता है कि एक डिफ़ॉल्ट सेटिंग की जाँच करना और समस्या को दोहरा सकने वाली ट्रेस सुविधा बचाकर रखना कितना ज़रूरी है।
‘ज़रूरी काम को रोक रहे धीमे काम को थोड़ा धक्का देकर पहले पूरा करवा देना’, यही सीधा-सा विचार प्राथमिकता व्युत्क्रमण को समझने की पहली सीढ़ी है।