ऑपरेटिंग सिस्टम साक्षात्कार: Priority Inversion कैसे होता है, और Priority Inheritance क्या गारंटी देता है?

प्रांप्ट और प्रासंगिक संदर्भ

एक सिंगल-कोर, फिक्स्ड-प्रायोरिटी, प्रीमेप्टिव रियल-टाइम सिस्टम में तीन टास्क हैं। एक बड़ी प्रायोरिटी संख्या का अर्थ उच्च प्रायोरिटी है:

t=0 पर, L म्यूटेक्स का स्वामी है। H फिर जागता है, L को प्रीमेम्प्ट करता है, म्यूटेक्स प्राप्त करने का प्रयास करता है, और ब्लॉक हो जाता है। H के 1ms तक ब्लॉक रहने के बाद, M रनेबल (runnable) हो जाता है। एक सामान्य म्यूटेक्स और प्रायोरिटी इनहेरिटेंस के साथ निष्पादन क्रम (execution order) की व्याख्या करें, H के लॉक वेट पर एक बाउंड की गणना करें, और निम्नलिखित बिंदुओं को संबोधित करें:

• क्या चीज़ इसे एक अनबाउंडेड (unbounded) प्रायोरिटी इन्वर्जन बनाती है;
• मल्टीपल म्यूटेक्स, वेटर्स और नेस्टेड ब्लॉकिंग के साथ प्रायोरिटी कैसे प्रोपेगेट होती है और रीस्टोर होती है;
• प्रायोरिटी इनहेरिटेंस और प्रायोरिटी-सीलिंग प्रोटोकॉल के बीच ट्रेड-ऑफ;
• एक साधारण सेमाफोर, एक छोटा टाइम स्लाइस, या H की प्रायोरिटी में एक और वृद्धि एक समान समाधान क्यों नहीं है;
• शेड्यूलर ट्रेस और डेडलाइन मेट्रिक्स कैसे साबित कर सकते हैं कि यह समाधान काम करता है।

यह प्रश्न एम्बेडेड, RTOS, रियल-टाइम लिनक्स, रोबोटिक्स, ऑडियो/वीडियो, इंडस्ट्रियल-कंट्रोल और सिस्टम-सॉफ्टवेयर भूमिकाओं के लिए उपयुक्त है। प्रायोरिटीज़ और 3ms, 20ms, और 10ms के मान अभ्यास के प्रतिबंध (exercise constraints) हैं, किसी विशेष RTOS प्रायोरिटी रेंज या प्रोडक्शन थ्रेशोल्ड का दावा नहीं हैं।

साक्षात्कारकर्ता क्या मूल्यांकन कर रहा है

पहला स्तर प्रत्यक्ष संसाधन ब्लॉकिंग (direct resource blocking) को असंबंधित कार्य द्वारा शुरू किए गए विलंब से अलग करना है। L द्वारा संसाधन जारी करने की प्रतीक्षा कर रहा H पहले से ही एक प्रायोरिटी इन्वर्जन है। वह भाग जो पूर्वानुमेयता (predictability) को नष्ट करता है, वह यह है कि M संसाधन का उपयोग नहीं करता है, फिर भी वह कम-प्रायोरिटी वाले लॉक ओनर L को बार-बार प्रीमेम्प्ट कर सकता है, जिससे H की प्रतीक्षा मीडियम-प्रायोरिटी वाले काम की मनमानी मात्रा से बढ़ जाती है।

दूसरा स्तर केवल परिभाषा रटने के बजाय घटना अनुक्रम (event sequence) को चित्रित करना है। एक सामान्य म्यूटेक्स के साथ, H के ब्लॉक होने के बाद L रनेबल होता है, लेकिन M के जागने पर प्रीमेम्प्ट हो जाता है। H, M के 20ms और L के शेष 3ms, यानी लगभग 23ms तक प्रतीक्षा करता है, जो 10ms की डेडलाइन से अधिक है। इनहेरिटेंस के साथ, H ब्लॉक होते ही L को इफेक्टिव प्रायोरिटी 90 डोनेट कर देता है। M, L को प्रीमेम्प्ट नहीं कर सकता, इसलिए प्रांप्ट की मान्यताओं के तहत H लगभग L के शेष 3ms और शेड्यूलर ओवरहेड तक प्रतीक्षा करता है।

तीसरा स्तर कार्यान्वयन स्थिति (implementation state) को समझना है। एक लॉक को एक ओनर और प्रायोरिटी-ऑर्डर्ड वेटर्स की आवश्यकता होती है। जब कोई टास्क कई लॉक्स का स्वामी होता है, तो उसकी इफेक्टिव प्रायोरिटी उसकी बेस प्रायोरिटी और प्रत्येक लाइव डोनेशन का अधिकतम (maximum) होती है। यदि उच्चतम वेटर का टाइमआउट हो जाता है, उसे रद्द कर दिया जाता है, या लॉक जारी होने के कारण प्रतीक्षा करना बंद कर देता है, तो प्रायोरिटी को बिना शर्त बेस वैल्यू पर रीसेट करने के बजाय पुनर्गणना (recomputed) की जानी चाहिए। यदि बूस्ट किया गया ओनर किसी अन्य लॉक पर ब्लॉक हो जाता है, तो डोनेशन को PI श्रृंखला (chain) के साथ प्रोपेगेट होना चाहिए।

चौथा स्तर तंत्र की सीमाएं (mechanism boundaries) हैं। इनहेरिटेंस मीडियम-प्रायोरिटी वाले टास्क के कारण होने वाले अनबाउंडेड विलंब को सीमित करता है। यह क्रिटिकल सेक्शन के अंदर I/O, इंटरप्ट-डिसेबल्ड क्षेत्रों, नॉन-प्रीमेम्प्टिबल कोड या हार्डवेयर ऑपरेशंस को छोटा नहीं करता है, और यह डेडलॉक को समाप्त नहीं करता है। एक प्रायोरिटी सीलिंग अधिक स्थिर ब्लॉकिंग विश्लेषण के बदले अग्रिम कॉन्फ़िगरेशन का ट्रेड-ऑफ करती है। एक अद्वितीय ओनर के बिना एक काउंटिंग सेमाफोर बूस्ट करने के लिए कोई निश्चित टास्क प्रदान नहीं करता है।

अंत में, साक्षात्कारकर्ता वेरिफिकेशन अनुशासन चाहता है। एक मजबूत उत्तर लॉक-वेट अवधि, उस समय की तुलना करता है जब L म्यूटेक्स रखते हुए रनेबल है लेकिन चल नहीं रहा है, क्या M उस अंतराल में प्रवेश करता है, H की डेडलाइन मिस, और नेस्टेड-लॉक व टाइमआउट पाथ। औसत CPU उपयोग या "सिस्टम हैंग नहीं हुआ" एक रियल-टाइम बाउंड साबित नहीं करता है।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• प्रायोरिटी किस दिशा में चलती हैं, और शेड्यूलिंग नीति क्या है? प्रांप्ट कहता है कि 90, 50 से अधिक है और सिंगल-कोर फिक्स्ड-प्रायोरिटी प्रीमेम्प्शन निर्दिष्ट करता है। कुछ RTOS में प्रायोरिटी विपरीत दिशा में क्रमांकित होती हैं, और एक सामान्य टाइम-शेयरिंग शेड्यूलर सीधे उसी टाइमलाइन का समर्थन नहीं करता है।
• क्या 3ms वॉल-क्लॉक समय है या वास्तविक CPU निष्पादन समय? यहाँ यह क्रिटिकल सेक्शन के अंदर L का शेष CPU कार्य है। PI किसी डिवाइस प्रतीक्षा या नॉन-प्रीमेम्प्टिबल क्षेत्र को भौतिक रूप से तेज़ नहीं बना सकता है।
• H की 10ms की डेडलाइन कब शुरू होती है? यहाँ यह तब शुरू होती है जब H जागता है। यदि डेडलाइन अनुरोध के आगमन या आवधिक रिलीज पर शुरू होती है, तो पहले की कतार (queueing) को भी रिस्पांस-टाइम गणना में शामिल किया जाना चाहिए।
• क्या प्रायोरिटी 90 से ऊपर कोई इंटरप्ट या टास्क हैं? अभ्यास उन्हें पहली गणना से बाहर रखता है। एक वास्तविक बाउंड में उच्च-प्रायोरिटी का हस्तक्षेप, अधिकतम इंटरप्ट-डिसेबल्ड समय, शेड्यूलर ओवरहेड और कैश प्रभाव शामिल होने चाहिए।
• क्या bus_mutex वास्तव में एक ओनर-ट्रैकिंग म्यूटेक्स है? एक बाइनरी सेमाफोर समान दिख सकता है लेकिन इसमें ओनर, केवल ओनर द्वारा अनलॉक, या PI सिमेंटिक्स होना आवश्यक नहीं है।
• क्या L किसी अन्य लॉक का स्वामी है या किसी की प्रतीक्षा कर रहा है? यह निर्धारित करता है कि डोनेशन को रिकर्सिव रूप से प्रोपेगेट होना चाहिए या नहीं और यह डेडलॉक विश्लेषण और ब्लॉकिंग बाउंड दोनों को बदलता है।
• लक्षित कार्यान्वयन किन प्रोटोकॉल का समर्थन करता है? POSIX, PTHREAD_PRIO_INHERIT और PTHREAD_PRIO_PROTECT को प्रदर्शित करता है। मल्टीपल लॉक्स, टाइमआउट्स, रिकर्सिव लॉक्स और डीबूस्टिंग के लिए RTOS का व्यवहार भिन्न होता है, इसलिए सटीक संस्करण का दस्तावेज़ीकरण मायने रखता है।

30-सेकंड उत्तर का ढांचा

"एक सामान्य म्यूटेक्स के साथ, H ब्लॉक हो जाता है क्योंकि L के पास bus_mutex का स्वामित्व है। L अन्यथा अपने शेष 3ms को पूरा कर सकता था, लेकिन 1ms के बाद प्रायोरिटी 50 पर M, प्रायोरिटी 10 पर L को प्रीमेम्प्ट करता है और 20ms तक चलता है। M कभी भी म्यूटेक्स को नहीं छूता है फिर भी अप्रत्यक्ष रूप से प्रायोरिटी 90 पर H को प्रतीक्षा कराता है। इसलिए H का लॉक वेट लगभग 20+3=23ms है, जो 10ms की डेडलाइन से परे है। यदि मीडियम-प्रायोरिटी वाले जॉब्स आते रहते हैं, तो L की क्रिटिकल-सेक्शन लंबाई अब उस अतिरिक्त प्रतीक्षा को सीमित नहीं करती है।

प्रायोरिटी इनहेरिटेंस के साथ, H का ब्लॉक होना L की इफेक्टिव प्रायोरिटी को 90 तक बढ़ा देता है। M के जागने के बाद वह L को प्रीमेम्प्ट नहीं कर सकता। L लगभग 3ms के बाद म्यूटेक्स जारी करता है, शेष वेटर्स और स्वामित्व वाले म्यूटेक्स से अपनी प्रायोरिटी की पुनर्गणना करता है, और H लॉक प्राप्त करता है। PI असंबंधित मीडियम-प्रायोरिटी वाले कार्य से होने वाले विलंब को नियंत्रित करता है। यह शून्य ब्लॉकिंग का वादा नहीं करता है या लंबे क्रिटिकल सेक्शन, डेडलॉक या इंटरप्ट-डिसेबल्ड कोड को ठीक नहीं करता है।

मैं एक डिटर्मिनिस्टिक रिलीज अनुक्रम चलाऊंगा और सामान्य और PI म्यूटेक्स के लिए H के ब्लॉक और अनब्लॉक, L के ओनरशिप अंतराल, M के निष्पादन अंतराल, और प्रत्येक डेडलाइन मिस को रिकॉर्ड करूंगा। मैं यह साबित करने के लिए कि बूस्टिंग और डीबूस्टिंग दोनों सही हैं, चेन्ड डोनेशन, मल्टीपल वेटर्स, वेटर टाइमआउट और कई लॉक्स के वृद्धिशील (incremental) रिलीज का भी परीक्षण करूंगा।"

चरण-दर-चरण गहन विश्लेषण

चरण 1: एक सामान्य म्यूटेक्स के लिए अनबाउंडेड-इन्वर्जन टाइमलाइन बनाएं

H के जागने को रिलेटिव समय 0ms के रूप में उपयोग करें। L के पास पहले से ही लॉक का स्वामित्व है और 3ms का CPU कार्य शेष है:

H जागने से लेकर म्यूटेक्स अधिग्रहण तक लगभग 23ms प्रतीक्षा करता है, जिससे वह अपनी 10ms की डेडलाइन मिस कर देता है। यदि H के ब्लॉक रहने के दौरान M जैसे जॉब्स का आना जारी रहता है, तो H की प्रतीक्षा अब L के शेष 3ms क्रिटिकल सेक्शन से बाउंडेड नहीं रहती है। यही यहाँ अनबाउंडेड इन्वर्जन है। इसका मतलब यह नहीं है कि एक अनंत प्रतीक्षा गणितीय रूप से अपरिहार्य है; इसका मतलब है कि डिज़ाइन संरक्षित संसाधन से प्राप्त कोई परिमित (finite), ऑडिट योग्य ब्लॉकिंग बाउंड की आपूर्ति नहीं करता है।

डेडलॉक, स्टारवेशन और ओवरलोड में अंतर करें। एक डेडलॉक में एक प्रतीक्षा चक्र (wait cycle) होता है जिसमें कोई भी टास्क आवश्यक संसाधन जारी करने में सक्षम नहीं होता है। स्टारवेशन में लॉक ओनर का शामिल होना आवश्यक नहीं है। CPU ओवरलोड आमतौर पर कई टास्क की डेडलाइन मिस करने का कारण बनता है। इन्वर्जन साक्ष्य श्रृंखला विशिष्ट है: H, L के स्वामित्व वाले संसाधन की प्रतीक्षा करता है जबकि M, जिसकी उस संसाधन पर कोई निर्भरता नहीं है, L को निष्पादित होने से रोकता है।

चरण 2: प्रायोरिटी इनहेरिटेंस जोड़ें और पुनर्गणना करें

जब H, 0ms पर ब्लॉक होता है, तो म्यूटेक्स अपने उच्चतम वेटर की प्रायोरिटी 90 ओनर L को डोनेट करता है। L बेस प्रायोरिटी 10 बरकरार रखता है और अस्थायी रूप से इफेक्टिव प्रायोरिटी 90 रखता है:

3ms का निष्कर्ष प्रांप्ट पर निर्भर करता है: कोई उच्च-प्रायोरिटी वाला टास्क, लंबा इंटरप्ट-डिसेबल्ड क्षेत्र, नॉन-प्रीमेम्प्टिबल सेक्शन, पेज फॉल्ट, या ब्लॉकिंग I/O नहीं है, और म्यूटेक्स वास्तव में PI लागू करता है। वास्तविक रिस्पांस टाइम में H का निष्पादन और सभी उच्च-प्रायोरिटी हस्तक्षेप भी शामिल होने चाहिए। PI का मुख्य लाभ यह है कि M का 20ms अब H के लिए इस संसाधन-ब्लॉकिंग अंतराल में प्रवेश नहीं करता है।

बूस्टिंग इफेक्टिव प्रायोरिटी को बदलती है; इसे L की बेस प्रायोरिटी को स्थायी रूप से अधिलेखित (overwrite) नहीं करना चाहिए। यदि अनलॉक के बाद कोई अन्य डोनेशन नहीं बचता है, तो L वापस 10 पर आ जाता है। यदि प्रायोरिटी-80 वेटर अभी भी किसी अन्य म्यूटेक्स पर प्रतीक्षा कर रहा है जिसका स्वामित्व L के पास है, तो L केवल 80 पर डीबूस्ट हो सकता है, सीधे 10 पर नहीं।

चरण 3: मल्टीपल वेटर्स, मल्टीपल लॉक्स और एक PI श्रृंखला को संभालना

मान लीजिए कि L, R1 और R2 दोनों का स्वामी है, H90, R1 पर प्रतीक्षा करता है, और X70, R2 पर प्रतीक्षा करता है। L की इफेक्टिव प्रायोरिटी 90 है। L द्वारा R1 जारी करने के बाद, H अब L को डोनेट नहीं करता है, लेकिन X अभी भी R2 की प्रतीक्षा करता है, इसलिए L घटकर 70 हो जाता है। यह R2 जारी करने के बाद ही बेस प्रायोरिटी 10 पर लौटता है। उच्चतम वेटर द्वारा टाइमआउट या रद्दीकरण को उसी पुनर्गणना को ट्रिगर करना चाहिए।

अब मान लीजिए कि L, R3 की प्रतीक्षा कर रहा है, जिसका स्वामी K है। केवल L को बूस्ट करने से H का लॉक जारी नहीं हो सकता क्योंकि L स्वयं अपनी प्रतीक्षा से आगे नहीं चल सकता है। प्रायोरिटी 90 को H → R1 → L → R3 → K के साथ प्रोपेगेट होना चाहिए। K, R3 जारी करता है, जिससे L आगे बढ़ सकता है और अंततः R1 जारी कर सकता है। लिनक्स rt-mutex इसे प्रत्येक म्यूटेक्स के लिए प्रायोरिटी-ऑर्डर्ड वेटर सेट और ओनर के PI वेटर सेट में प्रत्येक स्वामित्व वाले म्यूटेक्स से उच्चतम वेटर के साथ बनाए रखता है।

चेन्ड डोनेशन खराब लॉक ऑर्डरिंग को ठीक नहीं करता है। यदि L, K की प्रतीक्षा करता है जबकि K, L की प्रतीक्षा करता है, तो PI केवल एक प्रतीक्षा चक्र में टास्क को बूस्ट करता है; कोई निष्पादन योग्य रिलीज पाथ दिखाई नहीं देता है। इंजीनियरिंग नियंत्रणों में अभी भी एक ग्लोबल लॉक ऑर्डर, बाउंडेड नेस्टिंग, म्यूटेक्स रखते हुए कोई ब्लॉकिंग I/O न होना, और एक ऑडिट योग्य वर्स्ट-केस क्रिटिकल-सेक्शन अवधि शामिल है।

चरण 4: प्रायोरिटी सीलिंग के साथ प्रायोरिटी इनहेरिटेंस की तुलना करें

POSIX म्यूटेक्स प्रोटोकॉल इस अंतर को ठोस बनाते हैं:

• PTHREAD_PRIO_INHERIT: एक ओनर को केवल तभी बूस्ट किया जाता है जब वह वास्तव में एक उच्च-प्रायोरिटी वाले थ्रेड को ब्लॉक करता है। इसकी इफेक्टिव प्रायोरिटी इसकी बेस प्रायोरिटी और लाइव वेटर डोनेशन का अधिकतम बन जाती है, और नेस्टेड ब्लॉकिंग रिकर्सिव रूप से प्रोपेगेट होती है।
• PTHREAD_PRIO_PROTECT: जब कोई थ्रेड किसी म्यूटेक्स का स्वामी होता है, तो वह कम से कम उस म्यूटेक्स की कॉन्फ़िगर की गई प्रायोरिटी सीलिंग पर निष्पादित होता है, भले ही कोई वेटर वर्तमान में मौजूद हो या न हो।

कंटेंशन होने पर इनहेरिटेंस रनटाइम बहीखाता (bookkeeping) और चेन-प्रोपेगेशन लागतों का भुगतान करता है, लेकिन इसके लिए प्रत्येक उपयोगकर्ता की अधिकतम प्रायोरिटी के पूर्व ज्ञान की आवश्यकता नहीं होती है। एक सीलिंग के लिए टास्क/संसाधन सेट को ज्ञात और सही ढंग से कॉन्फ़िगर करने की आवश्यकता होती है, जिसके बदले में अधिक स्थिर, विश्लेषण योग्य ब्लॉकिंग सीमा मिलती है। क्या कोई विशेष सीलिंग प्रोटोकॉल डेडलॉक के एक वर्ग को रोकता है, यह उस सिस्टम में पूर्ण सीलिंग-एडमिशन नियमों पर भी निर्भर करता है। केवल "सीलिंग" शब्द डेडलॉक स्वतंत्रता को साबित नहीं करता है।

एक POSIX आरंभीकरण स्केच नीचे दिया गया है। प्रोडक्शन कोड को कार्यान्वयन समर्थन, रिटर्न वैल्यू, शेड्यूलिंग विशेषाधिकार और म्यूटेक्स लाइफटाइम की जांच करनी चाहिए:

pthread_mutexattr_t attr;
int rc = pthread_mutexattr_init(&attr);
if (rc == 0) {
  rc = pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
}
if (rc == 0) {
  rc = pthread_mutex_init(&bus_mutex, &attr);
}
pthread_mutexattr_destroy(&attr);

लिनक्स पर सामान्य SCHED_OTHER थ्रेड्स के लिए विशेषता सेट करना एक हार्ड रियल-टाइम डेडलाइन गारंटी नहीं है। शेड्यूलिंग क्लास, रियल-टाइम-प्रायोरिटी विशेषाधिकार, PREEMPT_RT या टारगेट-कर्नेल व्यवहार, और हर अन्य एप्लिकेशन ब्लॉकिंग स्रोत को अभी भी सत्यापन की आवश्यकता है।

चरण 5: सही प्रिमिटिव चुनें और क्रिटिकल सेक्शन को छोटा करें

PI एक निश्चित ओनर पर निर्भर करता है। जब एक उच्च-प्रायोरिटी वाला वेटर ब्लॉक होता है, तो कर्नेल को पता होना चाहिए कि किस टास्क को बूस्ट करना है। साझा स्थिति (shared state) को एक ओनर-ट्रैकिंग म्यूटेक्स से सुरक्षित रखें जिसे ओनर अनलॉक करता है। रिसोर्स काउंट या नोटिफिकेशन के लिए उपयोग किए जाने वाले काउंटिंग सेमाफोर का कोई अद्वितीय ओनर नहीं हो सकता है, इसलिए यह कोई विश्वसनीय डोनेशन लक्ष्य प्रदान नहीं करता है। एक बाइनरी सेमाफोर केवल इसलिए म्यूटेक्स PI सिमेंटिक्स प्राप्त नहीं करता है क्योंकि इसका मान शून्य या एक तक सीमित है।

PI के साथ भी, क्रिटिकल सेक्शन को गणना योग्य बनाएं। लॉक के तहत केवल आवश्यक स्थिति कॉपी करें। डिवाइस ट्रांसफर, लॉगिंग, आवंटन, और वे कॉल जो स्लीप में जा सकते हैं, उन्हें इसके बाहर ले जाएं। एक धीमे डिवाइस तक सीरियलाइज़्ड एक्सेस के लिए, एक समर्पित उच्च-प्रायोरिटी सर्विस टास्क और मैसेज पासिंग एक बेहतर आर्किटेक्चर हो सकता है। एक लॉक-फ्री संरचना म्यूटेक्स ब्लॉकिंग को कम कर सकती है लेकिन रिक्लेमेशन, ABA, रिट्रीज़, और संभावित रूप से बदतर वर्स्ट-केस निष्पादन समय का परिचय देती है। एक लेबल के बजाय डेडलाइन विश्लेषण के आधार पर चुनाव करें।

H की प्रायोरिटी बढ़ाने से यह प्रांप्ट हल नहीं हो सकता: H पहले से ही उच्चतम टास्क है और ब्लॉक होने पर चल नहीं सकता है। एक छोटा टाइम स्लाइस केवल M को अधिक बार शेड्यूल करता है; यह प्रायोरिटी-10 L को प्रायोरिटी-50 M से आगे नहीं निकलने देता है। प्रीमेम्प्शन को अक्षम करने से प्रत्येक टास्क के लिए रिस्पांस लेटेंसी बढ़ जाती है और समस्या एक नॉन-प्रीमेम्प्टिबल क्षेत्र में स्थानांतरित हो जाती है।

चरण 6: एक पुनरुत्पादनीय (Reproducible) ट्रेस के साथ ब्लॉकिंग बाउंड सत्यापित करें

एक निश्चित रिलीज क्रम बनाएं: L पहले लॉक करता है, एक बैरियर स्वामित्व की पुष्टि करता है, H रिलीज होता है, फिर H के ब्लॉक होने के 1ms बाद M रिलीज होता है। साधारण, PI, और प्रायोरिटी-सीलिंग म्यूटेक्स वेरिएंट को बार-बार चलाएं और रिकॉर्ड करें:

• H का म्यूटेक्स-अधिग्रहण लेटेंसी डिस्ट्रीब्यूशन और 10ms डेडलाइन मिस की संख्या;
• संचयी समय जब L म्यूटेक्स का स्वामी होते हुए रनेबल है लेकिन चल नहीं रहा है;
• H के ब्लॉक रहने के दौरान M के निष्पादन अंतराल;
• L की बेस और इफेक्टिव प्रायोरिटी, म्यूटेक्स ओनर, उच्चतम वेटर, और अनलॉक समय;
• शेड्यूलर स्विच, वेक-अप, इंटरप्ट-डिसेबल्ड समय, और नॉन-प्रीमेम्प्टिबल अंतराल।

साधारण म्यूटेक्स ट्रेस में M को अंतराल में प्रवेश करते हुए और H को लगभग 23ms प्रतीक्षा करते हुए दिखाना चाहिए। PI वेरिएंट में, उस अंतराल के दौरान M को प्रीमेम्प्ट नहीं करना चाहिए जहां H प्रतीक्षा करता है और L म्यूटेक्स का स्वामित्व रखते हुए रनेबल है; प्रांप्ट के लोड के तहत, H को 23ms के बजाय 3ms के करीब प्रतीक्षा करनी चाहिए। उच्चतम वर्तमान डोनेशन के विरुद्ध बूस्ट और डीबूस्ट को सत्यापित करने के लिए प्रायोरिटी 70 पर एक दूसरा वेटर, एक नेस्टेड म्यूटेक्स, वेटर टाइमआउट, और L के दो लॉक्स की वृद्धिशील रिलीज जोड़ें।

स्वीकृति मानदंड (acceptance criterion) में यह नहीं कहा जाना चाहिए कि "PI का अर्थ है कोई और टाइमआउट नहीं।" एक सशर्त बाउंड का उपयोग करें: मापे गए अधिकतम क्रिटिकल सेक्शन, उच्चतम-प्रायोरिटी हस्तक्षेप, अधिकतम इंटरप्ट-डिसेबल्ड समय, और शेड्यूलर-ओवरहेड बजट को देखते हुए, H की वर्स्ट-केस प्रतिक्रिया 10ms से नीचे रहती है, जिसमें तनाव और फॉल्ट इंजेक्शन भी शामिल है।

मजबूत नमूना उत्तर

"मैं पहले प्रायोरिटी दिशा और समय की उत्पत्ति तय करूंगा: 90 उच्चतम है, और H का 10ms तब शुरू होता है जब H जागता है। एक सामान्य म्यूटेक्स के साथ, H, L को प्रीमेम्प्ट करता है, पाता है कि bus_mutex का स्वामित्व किसी के पास है, और ब्लॉक हो जाता है। L 1ms के लिए फिर से शुरू होता है, फिर प्रायोरिटी-50 M जागता है और 20ms के लिए L को प्रीमेम्प्ट करता है। L अंततः अपने शेष 2ms को निष्पादित करता है और अनलॉक करता है। इसलिए H जागने से लेकर म्यूटेक्स अधिग्रहण तक लगभग 23ms लेता है और निश्चित रूप से अपनी डेडलाइन मिस कर देता है। M कभी म्यूटेक्स का उपयोग नहीं करता है, लेकिन अप्रत्यक्ष रूप से उच्चतम-प्रायोरिटी H को चलने से रोकता है। यदि मीडियम-प्रायोरिटी वाला काम आना जारी रह सकता है, तो L का 3ms क्रिटिकल सेक्शन इस अतिरिक्त ब्लॉकिंग को बाउंड नहीं कर सकता है।

PI के साथ, H ब्लॉक होने पर प्रायोरिटी 90 L को डोनेट करता है। L की बेस प्रायोरिटी 10 बनी रहती है और इसकी इफेक्टिव प्रायोरिटी 90 हो जाती है, इसलिए M 1ms पर प्रीमेम्प्ट नहीं कर सकता। L लगभग 3ms में क्रिटिकल सेक्शन को पूरा करता है और म्यूटेक्स जारी करता है, फिर H इसे प्राप्त करता है। इसलिए प्रांप्ट की मान्यताओं के तहत संसाधन ब्लॉकिंग 10ms से कम है। उच्च-प्रायोरिटी वाले टास्क, इंटरप्ट-डिसेबल्ड समय, और शेड्यूलर ओवरहेड को उस संख्या से बाहर रखा गया है और एक वास्तविक रिस्पांस-टाइम विश्लेषण में उन्हें रीस्टोर किया जाना चाहिए।

कार्यान्वयन केवल एक बूस्टेड बूलियन को स्टोर नहीं कर सकता है। प्रत्येक म्यूटेक्स को एक ओनर और उच्चतम वेटर की आवश्यकता होती है। प्रत्येक ओनर अपनी बेस प्रायोरिटी और सभी स्वामित्व वाले म्यूटेक्स के डोनेशन का अधिकतम लेता है। उच्चतम वेटर द्वारा टाइमआउट या एक लॉक के रिलीज होने से पुनर्गणना होती है। यदि L, K के लॉक पर ब्लॉक है, तो प्रायोरिटी 90 को PI श्रृंखला के साथ K तक प्रोपेगेट होना चाहिए। यदि कोई प्रतीक्षा चक्र है, तो बूस्टिंग किसी भी संसाधन को जारी नहीं कर सकती है, इसलिए लॉक-ऑर्डर और डेडलॉक जांच आवश्यक बनी रहती है।

मैं PTHREAD_PRIO_INHERIT म्यूटेक्स के साथ एक साधारण म्यूटेक्स की तुलना करने के लिए एक रिलीज अनुक्रम का उपयोग करूंगा और शेड्यूलर स्विच, लॉक स्वामित्व, इफेक्टिव प्रायोरिटी, H की ब्लॉक अवधि और डेडलाइन मिस को कैप्चर करूंगा। सीधा पासिंग साक्ष्य यह है कि M अब नहीं चलता है जबकि H ब्लॉक है और रनेबल L म्यूटेक्स का स्वामी है, और H की प्रतीक्षा लगभग 23ms से घटकर L के लगभग 3ms शेष क्रिटिकल सेक्शन और गिने गए सिस्टम हस्तक्षेप तक आ जाती है। एक दूसरा वेटर, नेस्टेड लॉक्स, टाइमआउट, और एक-एक करके अनलॉक होना चेन्ड बूस्टिंग और सही डीबूस्टिंग को सत्यापित करता है।"

सामान्य गलतियाँ

• केवल यह कहना कि "एक कम-प्रायोरिटी वाला टास्क एक उच्च-प्रायोरिटी वाले टास्क को ब्लॉक करता है" → यह छोड़ देता है कि कैसे M एक सीमित क्रिटिकल सेक्शन को अनबाउंडेड हस्तक्षेप में बदल देता है → पूर्ण H-ब्लॉक, L-रनेबल, M-प्रीमेम्प्ट अनुक्रम बनाएं।
• H के लिए केवल 3ms प्रतीक्षा की गणना करना → यह सामान्य म्यूटेक्स के तहत M के 20ms प्रीमेम्प्शन की उपेक्षा करता है → घटना क्रम का लगभग 23ms तक पालन करें और इसकी तुलना 10ms से करें।
• यह दावा करना कि PI हर प्रायोरिटी इन्वर्जन को समाप्त करता है → H को अभी भी L के शेष क्रिटिकल सेक्शन की प्रतीक्षा करनी होगी → बताएं कि PI असंबंधित मीडियम-प्रायोरिटी वाले कार्य द्वारा अनबाउंडेड विस्तार को हटाता है।
• एक अनलॉक के बाद L को सीधे 10 पर रीसेट करना → एक उच्च-प्रायोरिटी वाला वेटर किसी अन्य स्वामित्व वाले म्यूटेक्स पर बना रह सकता है → प्रत्येक लाइव डोनेशन से इफेक्टिव प्रायोरिटी की पुनर्गणना करें।
• केवल प्रत्यक्ष ओनर को बूस्ट करना → किसी अन्य लॉक पर ब्लॉक ओनर अभी भी नहीं चल सकता → PI श्रृंखला के साथ प्रोपेगेट करें और श्रृंखला की गहराई को बाउंड व निरीक्षण करें।
• PI को डेडलॉक समाधान के रूप में मानना → प्रतीक्षा चक्र में बूस्ट किए गए टास्क के पास अभी भी कोई निष्पादन योग्य रिलीज पाथ नहीं है → लॉक ऑर्डरिंग, टाइमआउट नीति, और डेडलॉक डिटेक्शन बनाए रखें।
• PI मानकर म्यूटेक्स को बाइनरी सेमाफोर से बदलना → सेमाफोर का कोई ओनर नहीं हो सकता है, जिससे बूस्ट करने के लिए कोई टास्क नहीं बचता है → संसाधन संरक्षण के लिए एक ऐसे ओनर म्यूटेक्स का उपयोग करें जो स्पष्ट रूप से PI का समर्थन करता है।
• PTHREAD_PRIO_INHERIT को हार्ड-रियल-टाइम स्विच के रूप में मानना → शेड्यूलिंग क्लास, विशेषाधिकार, कर्नेल प्रीमेम्प्शन, इंटरप्ट, और अन्य प्रतीक्षाएं अभी भी डेडलाइन को प्रभावित करती हैं → पूर्ण प्लेटफॉर्म को मान्य करें और वर्स्ट-केस रिस्पांस टाइम की गणना करें।
• केवल बेहतर औसत लेटेंसी की जाँच करना → डीबूस्ट, नेस्टेड प्रोपेगेशन, या टाइमआउट पाथ अभी भी गलत हो सकते हैं → टेल्स, डेडलाइन मिस, इफेक्टिव प्रायोरिटीज, और मल्टीपल-लॉक सीमाओं को सत्यापित करें।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: इसे अनबाउंडेड क्यों कहें यदि M यहाँ ठीक 20ms तक चलता है?

इस अभ्यास में एक M जॉब शामिल है, इसलिए परिणाम लगभग 23ms पर गणना योग्य है। "अनबाउंडेड" एक ऐसे तंत्र का वर्णन करता है जो अतिरिक्त विलंब को L के क्रिटिकल सेक्शन के आधार पर कोई सीमा नहीं देता है। यदि M-क्लास जॉब्स लगातार रिलीज हो सकते हैं, तो L बिना CPU प्राप्त किए रनेबल रह सकता है और H की प्रतीक्षा M कार्य के साथ बढ़ती जाती है। PI इस ब्लॉकिंग अंतराल से M हस्तक्षेप को हटा देता है; शेष सीमा क्रिटिकल सेक्शन और उच्च-प्रायोरिटी हस्तक्षेप से आती है।

फॉलो-अप 2: क्या होगा यदि H, L की प्रतीक्षा करता है और L, K की प्रतीक्षा करता है?

H के 90 को L को डोनेट करें, फिर इसे उस म्यूटेक्स के माध्यम से प्रोपेगेट करें जिस पर L ओनर K की प्रतीक्षा करता है। K अपने क्रिटिकल सेक्शन को इफेक्टिव प्रायोरिटी 90 पर निष्पादित करता है और जारी करता है, जिससे L जारी रह सकता है और अंततः H का लॉक जारी कर सकता है। एक ट्रेस में H → mutex1 → L → mutex2 → K पर बूस्ट और रिवर्स डीबूस्ट दिखाना चाहिए। केवल L के बूस्ट को देखने से यह साबित नहीं होता है कि चेन्ड PI सही है।

फॉलो-अप 3: एक उच्च-प्रायोरिटी वाले वेटर के टाइमआउट होने के बाद L की क्या प्रायोरिटी होनी चाहिए?

शेष बची उच्चतम मांग का उपयोग करें। यदि H90 का टाइमआउट हो जाता है लेकिन X70 अभी भी किसी अन्य म्यूटेक्स पर प्रतीक्षा करता है जिसका स्वामित्व L के पास है, तो L 90 से घटकर 70 हो जाता है। यह हर डोनेशन गायब होने के बाद ही बेस प्रायोरिटी 10 पर लौटता है। वेटर इंसर्शन, डिपार्चर, टाइमआउट, कैंसिलेशन और प्रत्येक अनलॉक को इस प्रायोरिटी-ऑर्डर्ड स्थिति को बनाए रखना चाहिए।

फॉलो-अप 4: क्या प्रायोरिटी सीलिंग हमेशा इनहेरिटेंस से बेहतर होती है?

नहीं। टास्क सेट और संसाधन-पहुंच संबंध स्थिर होने पर सीलिंग स्थिर ब्लॉकिंग विश्लेषण का समर्थन करती है, लेकिन एक खराब सीलिंग वैध पहुंच को अस्वीकार कर सकती है या विश्लेषण को अमान्य कर सकती है। इनहेरिटेंस वास्तविक कंटेंशन पर बूस्ट करता है और कम कॉन्फ़िगरेशन की आवश्यकता होती है, लेकिन इसे वेटर्स, चेन प्रोपेगेशन और डायनेमिक डीबूस्टिंग को बनाए रखना चाहिए। RTOS के सटीक प्रोटोकॉल, टास्क-सेट स्थिरता और स्वीकार्य रनटाइम ओवरहेड के आधार पर चुनें।

फॉलो-अप 5: लॉक रखते समय PI I/O को क्यों ठीक नहीं कर सकता है?

बूस्टिंग ओनर को केवल तभी CPU पहले प्राप्त करने में मदद करती है जब वह रनेबल हो। यदि L एक SPI ट्रांसफर, स्टोरेज, एक पेज फॉल्ट, या किसी अन्य घटना के लिए स्लीप करता है, तो वह स्लीप मोड में ही रहता है। यदि निष्पादन में इंटरप्ट अक्षम हैं या यह नॉन-प्रीमेम्प्टिबल है, तो शेड्यूलर भी हस्तक्षेप नहीं कर सकता है। धीमे काम को क्रिटिकल सेक्शन से बाहर ले जाएं या सर्विस टास्क या एसिंक्रोनस प्रोटोकॉल का उपयोग करें, फिर बजट में हार्डवेयर के सबसे खराब पूर्णता समय (worst completion time) को शामिल करें।

फॉलो-अप 6: आप कैसे साबित करेंगे कि यह एट्रिब्यूट वास्तव में लिनक्स यूजर स्पेस में काम करता है?

pthread_mutexattr_setprotocol और pthread_mutex_init से रिटर्न वैल्यू, _POSIX_THREAD_PRIO_INHERIT के लिए समर्थन, थ्रेड्स की वास्तविक शेड्यूलिंग नीतियां और रियल-टाइम-प्रायोरिटी विशेषाधिकार की जांच करें। फिर एक नियंत्रित H/M/L वर्कलोड चलाएं और शेड्यूलिंग के साथ-साथ futex या लॉक इवेंट्स को ट्रेस करें। L के इफेक्टिव बूस्ट, क्रिटिकल अंतराल में M की अनुपस्थिति, और अनलॉक या वेटर टाइमआउट के बाद सही डीबूस्ट की पुष्टि करें। सफल इनिशियलाइज़ेशन या एक आकस्मिक p99 सुधार अपर्याप्त साक्ष्य है।