लॉकलेस एलगोरिदम: मेक, राइट, (ट्राई अगेन) मॉडल

पिछली बार हमने जिस परमाणु गुणन को लागू किया था, वह एक अधिक सामान्य मॉडल का उदाहरण है, जिसे रेमंड ने "डू, राइट, (पुन: प्रयास करें)" कहा।

 के लिए (;)) {
  // साझा चर का प्रारंभिक मूल्य लें,
  // जिसे हम बदलने जा रहे हैं
  oldValue = shareVariable;

  ... अन्य मापदंडों के प्रारंभिक मान लें ...

  newValue = ... नए मान का उपयोग करके गणना करें
                 oldValue और अन्य मापदंडों की प्रतियां ...

  // एक्सएक्सएक्स के बजाय एक्वायर, रिलीज, या कुछ भी नहीं हो सकता है
  अगर (InterlockedCompareExchangeXxx (
             & साझा करने योग्य,
             newValue, oldValue) == oldValue) {
   तोड़;  // रिकॉर्ड विफल
  }

  ... NewValue निकालें ...

 } // फिर से प्रयास करें

हम नए मान की गणना करते हैं, और फिर इसे एक साझा चर में लिखने के InterlockedCompareExchange कॉल करते हैं केवल तभी जब इसका मूल्य नहीं बदला है। अगर यह बदल गया है, तो एक और धारा हमारे पास है; इस मामले में, हम शुरू से ही एक नए तरीके से प्रदर्शन करने की कोशिश करेंगे, इस उम्मीद में कि अगली बार कोई हमें "काट" नहीं सकता।

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

अनुवादक ने अपने स्वयं के सादृश्य के साथ आने का साहस किया: मैकडॉनल्ड्स का बॉक्स ऑफिस एक महल है, जिसके पीछे ग्राहकों की प्रतीक्षा की एक पंक्ति है। अगर चेकआउट करने वाला एक ग्राहक छोटी चीज़ों के लिए अपनी जेब से रगड़ रहा है, तो बाकी ग्राहक और कैशियर प्रत्याशा में हैं; एक पूरे के रूप में प्रणाली निष्क्रिय है। दूसरी ओर, रेस्तरां में वेटर एक महल रहित संसाधन है। प्रत्येक ग्राहक उसे दोपहर के भोजन के लिए भुगतान करने के लिए कहता है; लेकिन एक और ग्राहक "हिला" और रास्ते में वेटर को रोक सकता है। यह ज्ञात नहीं है कि वेटर को कितनी बार विचलित किया जाएगा जब तक वह अंततः आपकी मेज पर नहीं पहुंचता; लेकिन दूसरी तरफ, अगर वह आपके अनुरूप नहीं है, तो अब वह किसी और की सेवा कर रहा है। सामान्य तौर पर, सिस्टम निष्क्रिय नहीं है।

---

अंतिम पोस्ट से InterlockedMultiply फ़ंक्शन यहां दिए गए टेम्प्लेट से मेल खाती है लगभग क्रिया: "एक और पैरामीटर" फ़ंक्शन पैरामीटर द्वारा प्रेषित गुणक है; "नया अर्थ" एक काम है। यदि नए मूल्य की रिकॉर्डिंग विफल हो गई, तो किसी और ने इसे बदल दिया, और हम फिर से ऑपरेशन शुरू करते हैं।

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

मॉडल का एक और "अनुकूलित" संस्करण "करो, लिखो, (निराशा)" है। इसमें कोई लूप भी नहीं है: यदि कोई नया मान लिखना विफल हो जाता है, तो फ़ंक्शन विफलता को घातक मानता है, और आगे के प्रयासों के लिए पुनर्वित्त करता है। यह है, उदाहरण के लिए, TryEnterCriticalSection । यह InterlockedCompareExchangeAcquire का उपयोग करता है: किसी महत्वपूर्ण अनुभाग के अंदर से किए गए परिवर्तन को मेमोरी में नहीं लिखा जाना चाहिए, इससे पहले कि यह रिकॉर्ड हो कि अनुभाग व्यस्त है।

यदि सामान्य चर एक संख्या नहीं है, लेकिन एक संकेतक है, तो आपको यह ध्यान रखने की आवश्यकता है कि पहले से ही वर्णित "एबीए समस्या" तब नहीं होती है जब एक ही सूचक एक नई वस्तु को इंगित करता है। स्थैतिक वस्तुओं के प्रारंभ में अतिरिक्त कठिनाइयों की आवश्यकता नहीं होती है: सूचक केवल NULL से किसी चीज़ में परिवर्तित हो सकता है , और एक बार गैर-NULL हो जाने के बाद, सूचक अब परिवर्तित नहीं होता है। यदि सूचक को मनमाने ढंग से बदला जा सकता है, तो, एक नियम के रूप में, इस सूचक और "संस्करण संख्या" को एक सामान्य चर में जोड़ा जाता है, जो सूचक के प्रत्येक परिवर्तन के साथ बढ़ता है।

"डू, राइट, (फिर कोशिश करें)" मॉडल के उपयोग के निम्नलिखित उदाहरण में, संस्करण संख्या को एक सामान्य चर में संग्रहीत किया जाएगा। शुरुआत के लिए, दो सहायक कार्य:

 लंबी इंटरलाकेडरेक्वायर (LONG * pl में __, LONG LUnliks)
 {
   वापसी InterlockedCompareExchangeAcquire (pl, lUnlikely, lUnlikely);
 }

 लंबी इंटरलाकेड रिजल्ट (__ में लंबी * pl, __ लंबाई लंबी दूरी)
 {
   InterlockedCompareExchangeRelease (pl, lUnlikely, lUnlikely);
 }

LONG चर को सीधे पढ़ने के विपरीत, ये कार्य उस आदेश पर प्रतिबंध लगाते हैं जिसमें उन्हें स्मृति में लिखा जाता है। चूंकि InterlockedCompareExchange ऑपरेशन में तुलना और नए मान समान हैं, इसलिए चेक किया गया मान ऑपरेशन के किसी भी परिणाम में नहीं बदलता है। निष्पादित क्रियाएं कोड के समान हैं:

 if (* pl == lUnlikely) * pl = lUnlikely;

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

तो हमारा उदाहरण:

 लंबी g_lColorChange;  // रंग संस्करण संख्या

 ...
 WM_SYSCOLORCHANGE केस:
  इंटरलॉक्ड इंक्रीमेंट (& g_lColorChange);
  ...

 int CalculateSomethingAboutSystemColors ()
 {
  लंबी lColorChangeStart;
  करो {
   lColorChangeStart = InterlockedReadAcquire (& g_lColorChange, -1);
   COLORREF clrWindow = GetSysColor (COLOR_WINDOW);
   COLORREF clrHighlight = GetSysColor (COLOR_HIGHLIGHT);
   ... GetSysColor (...) का उपयोग कर अन्य गणना
  } जबकि (InterlockedReadRelease (
                        & g_lColorChange, -1)! = lColorChangeStart);
  वापसी iResult;
 }

हम पुराने संस्करण संख्या मान लेते हैं और अपनी गणना शुरू करते हैं। हम इसे एक्वायर ऑपरेशन के साथ लेते हैं, इसलिए रीड वर्जन नंबर को उन कलर वैल्यू से पहले मेमोरी में लिखा जाता है, जिनका इस्तेमाल हम कैलकुलेशन के लिए करते हैं।
जब गणना पूरी हो जाती है, तो हम सहेजे गए के साथ वर्तमान संस्करण संख्या की तुलना करते हैं। यदि वे मेल नहीं खाते हैं, तो हमारी गणना के दौरान रंग बदल गए हैं, इसलिए उन्हें फिर से बनाना होगा।
यदि गणना के दौरान रंग चार बिलियन बार बदल गए हैं तो एक ABA समस्या संभव है: काउंटर ओवरफ्लो के कारण हमने इसे नोटिस नहीं किया है। यह स्पष्ट है कि वास्तव में ऐसा होने की संभावना नहीं है।