💻 computer science

Recursive Mutexes in Separation Logic

यह शोध पत्र मानक म्यूटेक्स (mutexes) के लिए सेपरेशन लॉजिक स्पेसिफिकेशन्स को रिकर्सिव म्यूटेक्स (recursive mutexes) तक विस्तारित करता है, जो इस आधार पर एक ही थ्रेड द्वारा कई अधिग्रहणों (acquisitions) और रिलीजों (releases) के लिए समान उपचार प्रदान करता है कि क्लाइंट लॉक को धारण करता है या नहीं।

मूल लेखक: Ke Du, William Mansky, Paolo G. Giarrusso, Gregory Malecha

प्रकाशित 2026-02-02

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Ke Du, William Mansky, Paolo G. Giarrusso, Gregory Malecha

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक बहुत ही व्यस्त, उच्च-सुरक्षा वाली तिजोरी (vault) के प्रबंधक हैं। कंप्यूटर प्रोग्रामिंग की दुनिया में, यह तिजोरी एक म्यूटेक्स (mutex) (एक लॉक) है, और इसके अंदर की मूल्यवान वस्तुएं डेटा हैं जिन्हें कई लोग (थ्रेड्स) बदलना चाह सकते हैं।

समस्या: "वन-एंड-डन" (One-and-Done) लॉक

मानक प्रोग्रामिंग में, इस तिजोरी के लिए एक नियम है: यदि आप पहले से ही चाबियाँ थामे हुए अंदर हैं, तो आप दरवाजे को दोबारा लॉक नहीं कर सकते।

कल्पना कीजिए कि आप एक तिजोरी को ठीक करने के लिए अंदर हैं। आपको बाहर से एक औज़ार लेने के लिए गलियारे में जाने की आवश्यकता है, लेकिन आप ऐसा नहीं कर सकते क्योंकि आपको दूसरों को बाहर रखने के लिए दरवाजा बंद रखना होगा। यदि आप दोबारा लॉक करने की कोशिश करते हैं जबकि चाबियाँ पहले से ही आपके पास हैं, तो सिस्टम क्रैश हो जाता है या फ्रीज हो जाता है। यह एक "नॉन-रिकर्सिव" (non-recursive) म्यूटेक्स है। यह सख्त है: या तो आप लॉक के मालिक हैं, या आप नहीं हैं। आप अपने ही "लॉक" किए गए राज्य में दोबारा प्रवेश नहीं कर सकते।

समाधान: "रिकर्सिव" (Recursive) लॉक

यह शोध पत्र एक रिकर्सिव म्यूटेक्स पेश करता है। इसे एक जादुई चाबी के रूप में सोचें जो आपको दरवाजा दोबारा लॉक करने की अनुमति देती है, भले ही आप पहले से ही उसे पकड़े हुए हों।

यह कैसे काम करता है: यदि आप तिजोरी के अंदर हैं और आपको दोबारा दरवाजा लॉक करने की आवश्यकता है (शायद किसी सहायक फंक्शन को कॉल करने के लिए जिसे सुरक्षित रहने की आवश्यकता है), तो आप ऐसा कर सकते हैं। सिस्टम घबराता नहीं है; यह बस गिनता है कि आपने कितनी बार लॉक किया है।
सावधानी: आपको दरवाजा खोलने के लिए उतनी ही बार अनलॉक करना होगा जितनी बार आपने उसे लॉक किया था।

चुनौती: यह सिद्ध करना कि यह सुरक्षित है

लेखक (Du, Mansky, Giarrusso, और Malecha) सेपरेशन लॉजिक (Separation Logic) नामक एक गणितीय प्रणाली का उपयोग करके यह सिद्ध कर रहे हैं कि यह "जादुई चाबी" सुरक्षित रूप से उपयोग करने योग्य है।

आमतौर पर, एक लॉक को सुरक्षित साबित करना ऐसा कहने जैसा है: "यदि मेरे पास चाबी है, तो मुझे खजाना देखने का अधिकार है।"
लेकिन रिकर्सिव लॉक के साथ, यह पेचीदा हो जाता है। यदि मेरे पास पहले से ही चाबी है, और मैं इसे दोबारा लॉक करता हूँ, तो क्या मुझे दो खजाने मिलेंगे? नहीं, वह नियमों को तोड़ देगा।

शोध पत्र का नया नियम (द "काउंटर" सिस्टम):
एक साधारण "हाँ/नहीं" के बजाय कि आपके पास चाबी है या नहीं, लेखक एक काउंटर सिस्टम का प्रस्ताव करते हैं:

गिनती (The Count): हर बार जब आप दरवाजा लॉक करते हैं, तो आपका व्यक्तिगत काउंटर 1 से बढ़ जाता है। हर बार जब आप अनलॉक करते हैं, तो यह 1 से कम हो जाता है।
अनुमति (The Permission): जब तक आपका काउंटर शून्य से अधिक है, आप खजाने (डेटा) को देखने के लिए अधिकृत हैं।
सुरक्षा (The Safety): गणित यह सिद्ध करता है कि भले ही आप इसे 5 बार लॉक करें, आपको अभी भी खजाना केवल एक ही बार प्राप्त होगा। आप केवल इसलिए डेटा को दो बार नहीं चुरा सकते क्योंकि आपने इसे दो बार लॉक किया है।

प्रोग्रामरों के लिए "जादुई ट्रिक"

इस शोध पत्र का सबसे उपयोगी हिस्सा प्रोग्रामर के काम को सरल बनाना है।

इस शोध पत्र से पहले:
यदि एक प्रोग्रामर एक ऐसा फंक्शन लिखता था जिसे लॉक करने की आवश्यकता होती थी, तो उसे पूछना पड़ता था: "रुको, क्या मैं पहले से ही अंदर हूँ? यदि मैं हूँ, तो मैं इसे दोबारा लॉक नहीं कर सकता। मुझे अपने कोड के दो अलग संस्करण लिखने होंगे: एक उस स्थिति के लिए जब मैं अंदर हूँ, और एक उस स्थिति के लिए जब मैं बाहर हूँ।" यह अव्यवस्थित है और गलतियों की संभावना बढ़ाता है।

इस शोध पत्र के साथ:
प्रोग्रामर बस कह सकता है: "दरवाजा लॉक करो, अपना काम करो, अनलॉक करो।"

यदि वे पहले से ही अंदर थे, तो काउंटर बढ़ जाता है, वे काम करते हैं, और काउंटर वापस कम हो जाता है।
यदि वे बाहर थे, तो काउंटर 0 से 1 होता है, वे काम करते हैं, और यह वापस 0 पर चला जाता है।

गणित गारंटी देता है कि दोनों परिदृश्यों में, डेटा सुरक्षित और सुसंगत रहता है। प्रोग्रामर को लॉक के इतिहास को जानने की आवश्यकता नहीं है; उन्हें बस यह जानना है कि जब तक वे लॉक (काउंटर > 0) रखते हैं, वे सुरक्षित रूप से डेटा को छू सकते हैं।

"टुपल" (Tuple) फिक्स

शोध पत्र एक "टुपल्स" (जानकारी को समूहबद्ध करने का एक तरीका) से संबंधित एक छोटा तकनीकी सुधार भी उल्लेख करता है।
कल्पना कीजिए कि खजाना केवल सोने का ढेर नहीं है, बल्कि सोने की एक विशिष्ट मात्रा है (जैसे, "500 सिक्के")।

पुराना तरीका: जब आप दरवाजा खोलते हैं, तो आप शायद यह भूल जाते हैं कि वहां वास्तव में कितने सिक्के थे, केवल यह याद रहता है कि "वहां कुछ सोना था।"
नया तरीका: लेखकों की प्रणाली यह सुनिश्चित करती है कि विशिष्ट संख्या (तर्क/arguments) आपके लॉक काउंट के साथ जुड़ी रहती है। भले ही आप कई बार लॉक और अनलॉक करें, आप डेटा की सटीक स्थिति को कभी नहीं खोते हैं।

सारांश

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

तकनीकी सारांश: सेपरेशन लॉजिक में रिकर्सिव म्यूटेक्स (Recursive Mutexes)

समस्या विवरण
यद्यपि मेकेनाइज्ड कन्करेंट सेपरेशन लॉजिक (mechanized concurrent separation logic), VST, BRiCk और RustBelt जैसे उपकरणों का उपयोग करके C++ और Rust जैसी भाषाओं में वास्तविक दुनिया के प्रोग्रामों को सत्यापित करने के स्तर तक उन्नत हो गया है, फिर भी मानक समवर्ती पुस्तकालयों (concurrency libraries) के औपचारिक सत्यापन (formal verification) में एक कमी बनी हुई है। विशेष रूप से, रिकर्सिव म्यूटेक्स (जो C++ और Java में सामान्य हैं) के लिए स्थापित सेपरेशन लॉजिक विनिर्देशों (specifications) का अभाव है। मानक म्यूटेक्स के विपरीत, जो एक ही थ्रेड द्वारा दोबारा प्राप्त नहीं किए जा सकते यदि वह उन्हें पहले से धारण कर रहा है, रिकर्सिव म्यूटेक्स एक ही थ्रेड को एक ही लॉक को कई बार प्राप्त करने की अनुमति देते हैं। यह क्षमता उन इडियोमैटिक कोड पैटर्न (idiomatic code patterns) को सक्षम बनाती है जहाँ एक लॉक धारण करने वाला फंक्शन सुरक्षित रूप से उसी लॉक को प्राप्त करने का प्रयास करने वाले दूसरे फंक्शन को कॉल कर सकता है (जैसे कि चित्र 1 में transfer द्वारा update_a को कॉल करना)। मानक म्यूटेक्स विनिर्देश इस पारदर्शिता और एनकैप्सुलेशन (encapsulation) का समर्थन करने में विफल रहते हैं, जिससे डेवलपर्स को अक्सर गैर-लॉकिंग वैकल्पिक फंक्शन बनाने या लॉक स्वामित्व पर जटिल केस विश्लेषण करने के लिए मजबूर होना पड़ता है।

कार्यप्रणाली (Methodology)
लेखक रिकर्सिव म्यूटेक्स के लिए एक नया सेपरेशन लॉजिक विनिर्देश प्रस्तावित करते हैं जो लॉक अधिग्रहण (acquisition) और रिलीज (release) को कॉल करने वाले थ्रेड की वर्तमान स्वामित्व स्थिति की परवाह किए बिना समान रूप से मानता है। यह कार्यप्रणाली दो प्राथमिक घटकों को पेश करती है:

फ्रैक्शनल हैंडल और थ्रेड-विशिष्ट प्रेडिकेट्स (Fractional Handles and Thread-Specific Predicates):
- एक इनवेरिएंट $P$ के साथ एक रिकर्सिव म्यूटेक्स $\gamma$ को एक फ्रैक्शनल हैंडल $\ell \mapsto_q \text{rmutex}(\gamma, P)$ से जोड़ा जाता है।
- महत्वपूर्ण रूप से, प्रत्येक थ्रेड $t$ जो म्यूटेक्स के साथ इंटरैक्ट करता है, उसके पास अपना स्वयं का प्रेडिकेट होता है: $\text{holds}(\gamma, t, n, P)$ । यहाँ, $n$ उस संख्या को दर्शाता है जितनी बार थ्रेड $t$ ने म्यूटेक्स को प्राप्त किया है।
- म्यूचुअल एक्सक्लूजन (Mutual exclusion) को इस नियम द्वारा लागू किया जाता है कि यदि दो थ्रेड म्यूटेक्स धारण करते हैं, तो कम से कम एक का काउंट शून्य होना चाहिए ( $n_1 = 0 \lor n_2 = 0$ )।
- एक थ्रेड को दो $\text{holds}$ प्रेडिकेट्स को एक साथ धारण करने से रोकने के लिए, लॉजिक यह लागू करता है कि एक थ्रेड एक साथ दो $\text{holds}$ प्रेडिकेट्स नहीं रख सकता; इस प्रकार, $\text{holds}(\gamma, t, n_1, P) * \text{holds}(\gamma, t, n_2, P) \vdash \text{False}$ ।
स्टेट ट्रांज़िशन और बोरोइंग (State Transitions and Borrowing):
- लॉक/अनलॉक: लॉक प्राप्त करने से थ्रेड का काउंट $n$ बढ़ता है ( $n \to n+1$ ), और रिलीज करने से $n$ घटता है ( $n \to n-1$ )।
- बोरोइंग नियम: एक थ्रेड संरक्षित इनवेरिएंट $P$ तक तभी पहुँच सकता है जब उसका काउंट $n > 0$ हो। यह नियम एक थ्रेड को $\text{holds}(\gamma, t, n, P)$ (जहाँ $n>0$ ) को वास्तविक संसाधनों $P$ और एक रिटेनर $\text{held}(\gamma, t, n)$ के लिए बदलने की अनुमति देता है जो काउंट को ट्रैक करता है लेकिन $P$ तक पहुँच प्रदान नहीं करता है।
- क्वांटिफाइड आर्गुमेंट्स को संभालना: उन समस्याओं को संबोधित करने के लिए जहाँ लॉक इनवेरिएंट्स में अस्तित्वगत क्वांटिफाइड वेरिएबल्स (existentially quantified variables) होते हैं (जैसे $\exists v. x \mapsto v$ ), लेखक $\text{holds}$ प्रेडिकेट में पास किए गए आर्गुमेंट्स का एक टुपल (tuple) $a$ पेश करते हैं। यह सुनिश्चित करता है कि जब कोई थ्रेड $P$ को उधार लेता है, तो वह संसाधनों (जैसे कि वेरिएबल्स के विशिष्ट मान) के बारे में विशिष्ट ज्ञान बनाए रखता है, बजाय इसके कि वह इनवेरिएंट अवस्था में लौटने पर पुन: क्वांटिफिकेशन (re-quantifying) करके जानकारी खो दे।

प्रमुख योगदान (Key Contributions)

एकीकृत विनिर्देश (Unified Specification): यह पेपर क्लाइंट्स को यह निर्धारित करने की अनुमति देने वाला एक विनिर्देश प्रदान करता है कि क्या वे केवल यह जाँचकर कि उनका काउंट $n$ शून्य से अधिक है, म्यूटेक्स धारण करते हैं, बिना "पहली बार" अधिग्रहण और "रिकर्सिव" अधिग्रहण के बीच अंतर किए।
इडियोमैटिक रीजनिंग (Idiomatic Reasoning): ये विनिर्देश उन कोड पैटर्न के लिए प्रमाण सक्षम करते हैं जहाँ फंक्शन उन फंक्शनों को कॉल करते हैं जो उसी लॉक को भी प्राप्त करते हैं, जो विशेष "नो-लॉक" वेरिएंट के बिना मानक C++ उपयोग को दर्शाता है।
C++ कन्करेंसी का औपचारिक सत्यापन: यह कार्य BRiCk फ्रेमवर्क का उपयोग करके C++ कन्करेंसी लाइब्रेरी (विशेष रूप से std::recursive_mutex) को सत्यापित करने के लिए इन विनिर्देशों के अनुप्रयोग को प्रदर्शित करता है।

परिणाम (Results)
लेखकों ने चित्र 1 के उदाहरण को सत्यापित करने के लिए इन विनिर्देशों को सफलतापूर्वक लागू किया, जहाँ एक transfer फंक्शन एक ही रिकर्सिव म्यूटेक्स को धारण करते हुए update_a और update_b को कॉल करता है। सत्यापन पुष्टि करता है कि:

transfer फंक्शन सुरक्षित रूप से update_a का पुन: उपयोग कर सकता है भले ही दोनों एक ही म्यूटेक्स को प्राप्त करते हों।
इनवेरिएंट (balance_a और balance_b का योग) ऑपरेशन के दौरान सुरक्षित रहता है।
लॉजिक इनवेरिएंट की स्थिति को सही ढंग से संभालता है चाहे थ्रेड ने शुरू में लॉक धारण किया हो या नहीं, और कॉल स्टैक के माध्यम से विशिष्ट वेरिएबल मानों (जैसे $a$ और $b$ ) को सुरक्षित रखता है।

महत्व (Significance)
यह पेपर दावा करता है कि ये विनिर्देश रिकर्सिव म्यूटेक्स के बारे में तर्क करना सामान्य म्यूटेक्सों का उपयोग करने की तुलना में "अधिक पारदर्शी और बेहतर एनकैप्सुलेटेड" बनाता है। लॉक प्राप्त करने (n को बढ़ाना) और इनवेरिएंट को उधार लेने (n > 0 होने पर P तक पहुँचना) के कार्यों को अलग करके, यह दृष्टिकोण मुख्यधारा की भाषाओं में पाए जाने वाले सामान्य सॉफ्टवेयर इंजीनियरिंग पैटर्न का समर्थन करता है। यह कार्य C++ स्टैंडर्ड लाइब्रेरी को पूरी तरह से सत्यापित करने के व्यापक लक्ष्य की ओर एक कदम के रूप में प्रस्तुत किया गया है, जिसका उद्देश्य ऐसे तर्क सिद्धांतों को उजागर करना है जो वास्तविक दुनिया की कन्करेंट प्रोग्रामिंग के लिए व्यावहारिक हैं। लेखक उल्लेख करते हैं कि उनके वर्तमान विनिर्देश std::atomic और std::vector जैसे अन्य मानक लाइब्रेरी घटकों को भी कवर करते हैं।