एक गैर-अवरुद्ध एल्गोरिथ्म के लाभ - न केवल प्रदर्शन में इतना ही नहीं

मुझे उम्मीद है कि श्रृंखला के अंतिम पोस्ट, तीन पिछले वाले के विपरीत, जो बहुत कट्टर हो गए थे, यह न केवल हेब्रा पब्लिक में दार्शनिक रुचि पैदा करेगा।

गैर-अवरुद्ध एल्गोरिदम की एक श्रृंखला पर चेन के कमेंटेटरों में से एक ने उन परिस्थितियों के बारे में पूछा जिनके तहत ये अधिक जटिल एल्गोरिदम महत्वपूर्ण ब्लॉकिंग जैसे सरल ब्लॉकिंग प्राइमेटिव को बेहतर रूप से बेहतर बनाते हैं।

वह पूरी तरह से सही है कि प्रदर्शन को मापने के द्वारा एक सरल एल्गोरिथ्म से एक जटिल में परिवर्तन को उचित ठहराया जाना चाहिए: यदि एक सरल एल्गोरिथ्म अपने कार्य को संतोषजनक ढंग से पूरा करता है, तो अच्छे से अच्छे की तलाश करने के लिए कुछ भी नहीं है।

लेकिन गैर-अवरोधक सिंक्रनाइज़ेशन के फायदे अवरुद्ध होने की सामान्य आदिम की तुलना में बेहतर प्रदर्शन तक सीमित नहीं हैं। (बाद में इस पोस्ट में, हम देखेंगे कि कैसे आप पूरी तरह से गैर-अवरोधक तुल्यकालन के लिए आगे बढ़े बिना इन अप्रभावी लाभों को प्राप्त कर सकते हैं।)

एक एकल गैर-अवरोधक एल्गोरिथ्म के बजाय एक सिंगलटन के आरंभीकरण की रक्षा करने के लिए मान लें, हमने सामान्य महत्वपूर्ण अनुभाग का उपयोग करने का निर्णय लिया है:

 CRITICAL_SECTION g_csSingletonX;  X * g_px = NULL;  X * GetSingletonX () {EnterCriticalSection (& g_csSingletonX);  if (g_px == NULL) {g_px = new (nothrow) X ();  } लीव क्रिटिकलसेक्शन (& g_csSingletonX);  वापसी g_px;  } 

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

तालों के पदानुक्रम के निर्माण के दौरान, यह पता चल सकता है कि कुछ तालों को हमेशा एक ही क्रम में नहीं पकड़ा जा सकता है, और इसलिए उन्हें संयुक्त करने की आवश्यकता है। तुल्यकालन कठिन हो रहा है। उदाहरण के लिए, यह पता चल सकता है कि g_csSingletonX को सभी सिंगलटन कंस्ट्रक्टर्स के ताले के साथ जोड़ा जाना चाहिए, साथ ही साथ X के सभी तरीकों के ताले के साथ।

 CRITICAL_SECTION g_csCommon;

 X * GetSingletonX ()
 {
 EnterCriticalSection (& g_csCommon);
 अगर (g_px == NULL)
 {
 g_px = new (nothrow) X ();
 }
 लीव क्रिटिसलाईट (& g_csCommon);
 वापसी g_px;
 }

 Y * GetSingletonY ()
 {
 EnterCriticalSection (& g_csCommon);
 अगर (g_py == NULL)
 {
 g_py = new (nothrow) Y ();
 }
 लीव क्रिटिसलाईट (& g_csCommon);
 वापसी g_py;
 }

 शून्य X :: DoSomething ()
 {
 EnterCriticalSection (& g_csCommon);
 .. कुछ ..
 लीव क्रिटिसलाईट (& g_csCommon);
 }

जी! एक छोटे और असंगत महत्वपूर्ण खंड से, एक वैश्विक ब्लॉक प्राप्त किया गया था, जिसके लिए बहुत सारे धागे लगातार प्रतिस्पर्धा कर रहे हैं।

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

क्या आप ऐसे उत्पादों से मिले हैं, यदि किसी एक घटक में कोई त्रुटि होती है, तो आप केवल कंप्यूटर को रिबूट करके काम की स्थिति में लौट सकते हैं? गैर-अवरोधक उन कार्यक्रमों को बनाना आसान बनाता है जो इस तरह से व्यवहार नहीं करते हैं।

---

यहां तक ​​कि अगर आप स्पष्ट रूप से पारंपरिक अवरुद्ध आदिम पसंद करते हैं - अंत में, उनका उपयोग करना बहुत सुविधाजनक है! - फिर आपको नॉन-ब्लॉकिंग एल्गोरिदम पर करीब से नज़र डालनी चाहिए। निम्नलिखित कोड में मान लीजिए:

 CRITICAL_SECTION g_cs;
 GORILLADATA g_data;

 शून्य PokeGorilla (दोहरी तीव्रता)
 {
 EnterCriticalSection (& g_cs);
 DeformGorilla (तीव्रता, और g_data);
 जालीदार (& g_data.spline);
 int stress = CalculateTension (& g_data.spline);
 if (तनाव <25) g_data.mood = संबंधित;
 अगर (तनाव <50) g_data.mood = ANNOYED;
 और g_data.mood = ANGRY;
 DeleteObject (g_data.hbmGorilla);
 g_data.hbmGorilla = RenderGorilla (& g_data);
 लीव क्रिटिसलाईट (& g_cs);
 }

- कई विवादित स्थान हैं। सबसे पहले, तालों के पदानुक्रम का सम्मान किया जाता है? उदाहरण के लिए, Reticulate() फ़ंक्शन को एक ताला की आवश्यकता हो सकती है जो ज्यामितीय संचालन की सुरक्षा करता है; और यह पता चल सकता है कि पदानुक्रम के अनुसार, इस लॉक को g_cs से पहले g_cs ।

यदि g_cs लिए प्रतिस्पर्धा करने वाले कई धागे हैं, तो हमें उस समय को कम करना चाहिए जो PokeGorilla() लॉक रखता है। RenderGorilla() संभवतः एक जटिल और धीमा ऑपरेशन है। (आप स्वयं जानते हैं कि यथार्थवादी फर को चित्रित करना कितना कठिन है।) फिर, RenderGorilla() को कॉल के दौरान, g_cs लॉक व्यर्थ में आयोजित किया जाता है।

दोनों समस्याओं का एक संभावित समाधान एक गैर-अवरुद्ध सिंक्रनाइज़ेशन के लिए संक्रमण है; लेकिन यह बहुत मुश्किल है! (लगभग यथार्थवादी फर जितना कठिन है।) हो सकता है कि हम गैर-अवरोधक के लाभों का 80% प्राप्त करने के लिए अपने काम का केवल 20% खर्च कर सकें?

void PokeGorilla(double intensity)
{
//
EnterCriticalSection(&g_cs);
GORILLADATA data = g_data;
LeaveCriticalSection(&g_cs);

//
DeformGorilla(intensity, &data);
Reticulate(&data.spline);
int stress = CalculateTension(&data.spline);
if (stress < 25) data.mood = RELAXED;
else if (stress < 50) data.mood = ANNOYED;
else data.mood = ANGRY;
data.hbmGorilla = RenderGorilla(&data);

//
EnterCriticalSection(&g_cs);
HBITMAP hbmToDelete = g_data.hbmGorilla;
g_data = data;
LeaveCriticalSection(&g_cs);
DeleteObject(hbmToDelete);
}

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

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

फिर हम संस्करण काउंटर के साथ "करते हैं, लिखते हैं, (फिर से कोशिश करें)" मॉडल पर लौटते हैं:

LONG g_lCounter;

void PokeGorilla(double intensity)
{
BOOL fSuccess;

do {
//
EnterCriticalSection(&g_cs);
GORILLADATA data = g_data;
LONG lCounter = g_lCounter;
LeaveCriticalSection(&g_cs);

//
DeformGorilla(intensity, &data);
Reticulate(&data.spline);
int stress = CalculateTension(&data.spline);
if (stress < 25) data.mood = RELAXED;
else if (stress < 50) data.mood = ANNOYED;
else data.mood = ANGRY;
data.hbmGorilla = RenderGorilla(&data);

//
EnterCriticalSection(&g_cs);
HBITMAP hbmToDelete;
if (lCounter == g_lCounter)
{
hbmToDelete = g_data.hbmGorilla;
g_data = data;
g_lCounter++;
fSuccess = TRUE;
} else {
hbmToDelete = data.hbmGorilla;
fSuccess = FALSE;
}
LeaveCriticalSection(&g_cs);
DeleteObject(hbmToDelete);
} while (!fSuccess);
}

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