परीक्षण के साथ घिरा-इंतज़ार कर म्युचुअल बहिष्करण और

Question

मैं (एवी Silberschatz, पीटर बाएर गैल्विन, ग्रेग गैग्ने) संस्करण 9 के प्रसिद्ध ऑपरेटिंग सिस्टम अवधारणाओं किताब पढ़ रहा हूँ सेट: http://codex.cs.yale.edu/avi/os-book/OS9/

प्रक्रिया तुल्यकालन अध्याय में, वहाँ एक है "test_and_set साथ पारस्परिक अपवर्जन घिरा-इंतज़ार कर" के रूप में पालन के लिए एल्गोरिथ्म:

do { 
    waiting[i] = true; 
    key = true; // <-- Boolean variable that I do not see its utility 
    while (waiting[i] && key) // <-- the value of the key variable here is always true 
     key = test_and_set(&lock); // <-- it might become false here, but what is the point? 
    waiting[i] = false; 

    /* critical section */ 

    j = (i + 1) % n; 
    while ((j != i) && !waiting[j]) 
     j = (j + 1) % n; 
    if (j == i) 
     lock = false; 
    else 
     waiting[j] = false; 

    /* remainder section */ 
} while (true); 

मैं बूलियन चर key (3, ऊपर कोड की 4 और 5 लाइनों में प्रयुक्त) की भूमिका नहीं देख सकते हैं, मैं देखें कि हम इसे एल्गोरिदम पर किसी भी विशेष प्रभाव के बिना हटा सकते हैं, क्या मैं सही हूं या मैंने कुछ याद किया है?

Answer 1

आप के लिए एल्गोरिथ्म को आसान बनाने में कर सकते हैं:

do { 
    waiting[i] = true; 
    while (waiting[i] && test_and_set(&lock)) ; 
    waiting[i] = false; 

    /* critical section */ 

    j = (i + 1) % n; 
    while ((j != i) && !waiting[j]) 
     j = (j + 1) % n; 
    if (j == i) 
     lock = false; 
    else 
     waiting[j] = false; 

    /* remainder section */ 
} while (true); 

और यह ठीक उसी होगा। मुझे लगता है कि लेखकों ने key का उपयोग किया क्योंकि उन्होंने सोचा था कि यह कोड को पढ़ने में आसान बना देगा।

के रूप में टिप्पणी में पूछा:

आम तौर पर, जब test_and_set का उपयोग कर आप बस while(test_and_set(&lock)) ; है। हालांकि इस मामले में आप यह सुनिश्चित करना चाहते हैं कि थ्रेड केवल लॉक के लिए सीमित समय की प्रतीक्षा करे। यह waiting सरणी के साथ पूरा किया जाता है। जब हम अनलॉक करते हैं तो महत्वपूर्ण अनुभाग के अंत में, हम केवल lock को गलत पर सेट नहीं करते हैं, इस प्रकार आप इसे आम तौर पर अनलॉक करते हैं। इसके बजाय हम लॉक की प्रतीक्षा कर रहे अगले थ्रेड को खोजने का प्रयास करते हैं। अगले तक, मेरा मतलब है कि थ्रेड आईडी में वृद्धि करना और फिर n (j = (j + 1) % n; भाग) पर हमला करते समय लूपिंग करना। यदि ऐसा धागा j पाया जाता है तो हम के बजाय waiting[j]false पर सेट करते हैं।

यह उन परिदृश्यों को रोकता है जहां 2 या अधिक धागे लगातार ताला पकड़ रहे हैं जबकि धागे का एक और धागा हमेशा प्रतीक्षा कर रहा है। उदाहरण के लिए, 3 थ्रेड एक ही लॉक (थ्रेड 0, 1 और 2) के लिए प्रतीक्षा कर रहे हैं। कहें थ्रेड 0 लॉक जारी करता है और फिर थ्रेड 1 इसे पकड़ लेता है। जबकि थ्रेड 1 में लॉक थ्रेड 0 है, फिर लॉक को फिर से पकड़ने की कोशिश करता है और जब थ्रेड 1 लॉक थ्रेड जारी करता है तो 0 थ्रेड के बजाय इसे पकड़ता है। यह अनिश्चित काल तक दोहरा सकता है और थ्रेड 2 लॉक कभी नहीं मिलता है।

waiting सरणी का उपयोग करके इस बाउंडिंग प्रतीक्षा एल्गोरिदम में यह व्यवहार नहीं हो सकता है। यदि तीन थ्रेड लगातार लॉक को पकड़ रहे हैं तो थ्रेड आईडी के मामले में अगला थ्रेड अगला होगा, उदा। थ्रेड 0 लॉक को ले जाएगा और लॉक को बाद में थ्रेड 1 के बाद और फिर थ्रेड 2 के बाद रिलीज़ करेगा। ऐसा इसलिए है क्योंकि प्रत्येक थ्रेड lock या waiting सरणी में false बनने के लिए प्रतीक्षा कर रहा है। यदि कोई थ्रेड लॉक को रिलीज़ करने के बारे में लॉक के लिए इंतजार कर रहा है तो यह प्रविष्टि lock के बजाय स्पिन प्रतीक्षा से केवल उस थ्रेड को रिलीज़ करता है। यह लॉक के लिए अनिश्चित काल तक इंतजार कर रहे एक या अधिक धागे के रोगजनक मामले को रोकता है।