कैप्टिव-मुक्त एल्गोरिदम: मॉडल "इसे करें, इसे लिखें, (इसे दूसरे पर चार्ज करें)"

हैब्रोपोलिस की सलाह के बाद, मैं " लॉक-फ़्री " शब्द के अनुवाद का एक नया संस्करण आज़मा रहा हूं

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

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

किसी ऑब्जेक्ट पर कार्रवाई करने से पहले, सबसे पहले, हम इसे कैप्चर करते हैं, एटोमिकली संबंधित झंडे को सेट करते हैं। यदि यह पता चलता है कि ऑब्जेक्ट पहले ही कब्जा कर लिया गया है, तो हम दूसरे झंडे को सेट करके अपनी कार्रवाई के निष्पादन को कैप्चर स्ट्रीम में सौंप देंगे।

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

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

• AddWait: सूची में एक नया ईवेंट हैंडल जोड़ें।
• SignalAll: सूची में सभी घटनाओं को सेट करें, स्वचालित रूप से प्रत्येक ईवेंट को उसी समय हटा रहा है जैसे वह सेट है। अगली बार जब सिग्नल को सेट करने की घटना के लिए सिग्नल ऑल को बुलाया जाता है, तो उसे फिर से सूची में जोड़ा जाना चाहिए।

ऑब्जेक्ट को केवल हैंडल की सूची के रूप में कार्यान्वित किया जाता है। यह स्पष्ट है कि इसे बिना किसी पेचीदा, स्नेपलेस मॉडल के लागू किया जा सकता था: उदाहरण के लिए, विंडोज एक्सपी के बाद से लागू की गई सूचियों पर परमाणु कार्यों का उपयोग करना। नमूना कोड के साथ मौखिक विवरण के साथ ही कार्य का चयन किया जाता है। एक थ्रेड-सुरक्षित सूची को लागू करने के लिए GroupWait को एक मॉडल के रूप में न लें।

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

 // चेतावनी!  यदि आप इस कोड का उपयोग करते हैं, तो आप एक आईडी हैं - पाठ के बारे में जानें

 संरचना NODE;
 NODE * Node (LONG_PTR कुंजी) {वापसी reinterpret_cast <NODE *> (कुंजी);  }

 एनम {
  लॉक्ड = 1,
  संकेतित = 2,
 };

 संरचना NODE {
  NODE * pnNext;
  हाथ का निशान;

  LONG_PTR कुंजी () {return reinterpret_cast <LONG_PTR> (यह);  }
  NODE * Ptr () {रिटर्न नोड (की () और ~ (लॉक्ड | सिग्नलेड));  }
 };

 #define NODE_INVALID नोड (-1)

 वर्ग GroupWait {
 सार्वजनिक:
  GroupWait (): m_pnRoot (NULL) {}
  ~ ग्रुपवाइट ();
  BOOL AddWait (HANDLE hEvent);
  शून्य सिग्नलआल ();
 निजी:
  NODE * m_pnRoot;
 };

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

हम अपने मानों को प्रपत्र p|S|L छोटे क्षेत्रों के रूप में चित्रित करेंगे p|S|L : p - सूची के अगले तत्व के लिए सूचक; एस - काम का झंडा; और L कैप्चर फ्लैग है। सेट फ्लैग एस का मतलब है कि आपको सूची के सभी तत्वों को संसाधित करने की आवश्यकता है, जो निम्न से शुरू होती है - कल्पना करें कि यह तत्व के अंदर नहीं, बल्कि बाहर जाने वाले तीर पर चिह्नित है।

उदाहरण के लिए:

    m_pnRoot
   + -------- + - + - +
   |  * | 0 | 1 |
   + --- | ---- + - + - +
       |
       v
   + -------- + - + - + --------- +
 ए |  * | 1 | | |  hEvent1 |
   + --- | ---- + - + - + --------- +
       |
       v
   + -------- + - + - + --------- +
 B |  * | | | |  hEvent2 |
   + --- | ---- + - + - + --------- +
       |
       v
   + -------- + - + - + --------- +
 सी |  नल | | | | |  hEvent3 |
   + -------- + - + - + --------- +

चित्रित एक GroupWait ऑब्जेक्ट है जिसमें तीन हैंडल हैं। सूची के शीर्ष पर रीसेट ध्वज S का मतलब है कि hEvent1 घटना को सेट करने के लिए किसी की आवश्यकता नहीं है। इसके विपरीत, तत्व ए में सेट फ्लैग एस का मतलब है कि आपको ए के बाद सभी तत्वों के चारों ओर जाने की आवश्यकता है और संबंधित घटनाओं को सेट करें - अर्थात्, hEvent2 और hEvent3। विशेष रूप से, तत्वों बी और सी में ध्वज एस का मूल्य कोई फर्क नहीं पड़ता; इन तत्वों को किसी भी स्थिति में संसाधित किया जाएगा, क्योंकि तत्व A में S ध्वज को इसकी आवश्यकता है। इस प्रकार, सूची के अंतिम तत्व में S ध्वज का मान कभी भी मायने नहीं रखता है।

L ध्वज का उपयोग केवल सूची के प्रमुख पर किया जाता है; अन्य सभी तत्वों में यह कोई फर्क नहीं पड़ता।

तो तैयारी पूरी है; सूची में एक नया हैंडल जोड़ें।

 BOOL GroupWait :: AddWait (हाथ हिलाना)
 {
  NODE * pnInsert = new (nothrow) NODE;
  अगर (pnInsert == NULL) FALSE;
  pnInsert-> hEvent = hEvent;

  NODE * pn;
  NODE * pnNew;
  करो {
   pn = InterlockedReadAcquire (& m_pnRoot, NODE_INVALID);
   pnInsert-> pnNext = pn;
   pnNew = Node (pnInsert-> Key () | (pn-> Key () और Locked));
  } जबकि (InterlockedCompareExchangeRelease (& m_pnRoot, pnNew, pn)! = pn);
  TRUE लौटाओ;
 }

हम सूची में सबसे ऊपर एक नया तत्व जोड़ते हैं, और सुनिश्चित करते हैं कि L ध्वज पुराने तत्व से नए में परिवर्तित होता है: अन्यथा यह पता चल सकता है कि किसी अन्य थ्रेड ने पहले ही सूची पर कब्जा कर लिया है, और हम अनजाने में इसे "जारी" कर देते हैं। जोड़े जा रहे आइटम में S ध्वज साफ़ किया गया है: किसी ने अभी तक एक नई घटना सेट करने की मांग नहीं की है। हम सूची के प्रमुख के लिए एक तत्व जोड़ते हैं, परिचित मॉडल "करो, लिखो, (फिर से कोशिश करो") के अनुसार - यह जाँचना कि किसी ने हमारे पीछे की सूची को नहीं बदला है। कृपया ध्यान दें कि "ABA समस्या" उत्पन्न नहीं होती है: भले ही m_pnRoot का अपरिवर्तित मान किसी अन्य ऑब्जेक्ट को इंगित करता है, हम अभी भी केवल सूचक का उपयोग करते हैं, और ऑब्जेक्ट की सामग्री का नहीं।

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

सिग्नलऑल विधि इतनी जटिल है कि इसे भागों में पढ़ना बेहतर है।

 शून्य GroupWait :: SignalAll ()
 {
  NODE * pnCapture;
  NODE * pnNew;
  करो {
   pnCapture = InterlockedReadAcquire (& m_pnRoot, NODE_INVILID);

   अगर (pnCapture-> कुंजी () और लॉक किया गया) {
    pnNew = नोड (pnCapture-> कुंजी () | संकेतित);
   } {
    pnNew = Node (Locked);
   }
  } जबकि (InterlockedCompareExchangeAcquire (& m_pnRoot,)
                               pnNew, pnCapture); = pnCapture);

  अगर (pnCapture-> कुंजी () और बंद) वापसी;

  ...

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

एस ध्वज को सेट करके, हमने अपना काम थ्रेड को सौंप दिया जिसने सूची पर कब्जा कर लिया। सूची के सिर में सेट S ध्वज का अर्थ है कि आपको सूची के सभी तत्वों को संसाधित करने की आवश्यकता है - सिर के पीछे - अर्थात आम तौर पर सूची के सभी तत्व; बस हमें जो चाहिए। सूची पर कब्जा करने वाला धागा सूची जारी होने पर ध्वज की जांच करेगा, और हमारे लिए काम करेगा।

यदि सूची पर कब्जा नहीं किया गया था, तो हमारी कार्रवाई से हमने इसे पकड़ लिया। चोरी किए गए सामान अन्य थ्रेड्स के लिए दिखाई नहीं देते हैं, इसलिए एक ही समय में अलग-अलग थ्रेड्स से सिग्नलआल को कॉल करने से कई इवेंट नहीं होंगे।

  ...
  NODE * pnNext;
  NODE * pn;
  for (pn = pnCapture-> Ptr (); pn; pn = pnNext) {
   सेटईवेंट (pn-> hEvent);
   pnNext = pn-> pnNext-> Ptr ();
   हटाना;
  }
  ...

"चोरी" सूची को दरकिनार करके थ्रेड-सेफ्टी के लिए किसी भी चिंता के बिना, बहुत ही सरल तरीके से लागू किया जाता है; बस तत्व से तत्व लेते हैं, घटना को सेट करते हैं, और तत्व को हटाते हैं। एकमात्र विशेषता यह है कि Ptr को पॉइंटर से अगले तत्व तक झंडे को हटाने के लिए कॉल किया जाए।

अब सूची को अनलॉक करने की आवश्यकता है। आरंभ करने के लिए:

  ...
  pnCapture = pnNew;
  ...

विधि की शुरुआत में, हमने pnNew को m_pnRoot लिखा था, और यदि यह मान सूची के प्रमुख में सहेजा गया था, तो हम आसान हो गए: जब हम इसके साथ काम कर रहे थे, तो किसी ने भी इस सूची को एक्सेस नहीं किया।

  ...
  के लिए (;)) {
   pnNew = Node (pnCapture-> Key () & ~ लॉक्ड);
   यदि (InterlockedCompareExchangeRelease (& m_pnRoot)
                       pnNew, pnCapture) == pnCapture) {
    वापसी;
   }
  ...

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

  ...
   pnCapture = InterlockedReadAcquire (& m_pnRoot, NODE_INVILID);

   NODE * pnNew = नोड (pnCapture-> कुंजी () और ~ (लॉक | सिग्नलेड)));
   NODE ** ppn = & pnNew;
   NODE * pn;
   NODE * pnNext;

   BOOL fSignalSeen = FALSE;
   for (pn = pnNew; pn-> Ptr (); pn = pnNext) {
    pnNext = pn-> Ptr () -> pnNext;
    अगर (fSignalSeen) {
     सेटइवेंट (pn-> Ptr () -> hEvent);
     हटाना pn-> Ptr ();
    } और यदि (pn-> कुंजी () और संकेतित) {
     fSignalSeen = TRUE;
     (* पीपीएन) = नोड (बंद);  // चोरी, छोड़ दिया कब्जा
     सेटइवेंट (pn-> Ptr () -> hEvent);
     हटाना pn-> Ptr ();
    } {
     ppn = & pn-> Ptr () -> pnNext;
    }
   }
  } // फिर से अनलॉक करने का प्रयास करें
 } // फ़ंक्शन का अंत

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

---

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