Fri. Nov 22nd, 2024
    टैकनोलजी

    ऑपरेटिंग सिस्टम में Dekker’s अल्गोरिथम और उसके वर्जन

    Byअनुपम कुमार सिंह

    Aug 18, 2018 #ऑपरेटिंग सिस्टम
    dekker's algorithm in hindi, operating system (os)

    विषय-सूचि

    डेकर एल्गोरिथम का परिचय (dekker’s algorithm in os in hindi)

    किसी भी ऑपरेटिंग सिस्टम में किसी तरह के म्यूच्यूअल एक्सक्लूशन, bounded वेटिंग और प्रोग्रेस को प्राप्त करने के लिए कई तरह के अल्गोरिथम इमप्लेमेंट किये जाते हैं जिनमे से एक डेकर एल्गोरिथम भी है।

    इस अल्गोरिथम को समझने के लिए सबसे पहले हमे क्रिटिकल सेक्शन की समस्या के हल को समझना होगा। किसी प्रोसेस को सामान्यतः ऐसे दिखाते हैं:

    do {
    //entry section
        critical section
    //exit section
        remainder section
} while (TRUE);

    किसी भी क्रिटिकल सेक्शन की समस्या के ओलुतिओं को ये तीन चीजों को संतुष्ट करना होगा:

    1. म्यूच्यूअल एक्सक्लूशन
    2. प्रोग्रेस
    3. bounded वेटिंग

    इन सभी फैक्टर को सुनिश्चित करने का एक तरीका पीटरसन अल्गोरिथम भी है।

    इसी के लिए Dekker’s सलूशन भी आता है। इसे क्रिटिकल सेक्शन प्रॉब्लम का पहला सही सलूशन भी माना जाता है। ये दो थ्रेड को एक सिंगल यूज रिसोर्स को शेयर करने की अनुमति देता है और वो भी बिना किसी टकराव के।

    इसमें कम्युनिकेशन के लिए केवल शेयर्ड मेमोरी का ही प्रयोग किया जाता है। ये कठिन और काम्प्लेक्स अल्गोरिथम की कठिनाइयों से निकल आता है। ये म्यूच्यूअल एक्सक्लूशन को implement करने वाले पहले अल्गोरिथम में से एक है।

    यद्दपि इस अल्गोरिथम के बहुत सारे वर्जन हैं लेकिन अंतिम पांचवे अर्जन को ही ऐसा मन गया है जो सभी उपर लिखे शर्तों को संतुष्ट करता है और इन सबमे सबसे ज्यादा efficient भी है।

    नोट– Dekker’s अल्गोरिथम सलूशन जो यहाँ बताया गया है वो केवल दो प्रोसेस के बीच ही म्यूच्यूअल एक्सक्लूशन को सुनिश्चित करता है। इसे ऐरे और वेरिएबल का सही प्रयोग कर के दो प्रोसेस से ज्यादा पर भी लगाया जा सकता है।

    अल्गोरिथम– इसे दोनों चीजें चाहिए होती है- बूलियन मान का ऐरे और इन्टिजर वेरिएबल।

    var flag: array [0..1] of boolean;
turn: 0..1;
repeat

        flag[i] := true;
        while flag[j] do
                if turn = j then
                begin
                        flag[i] := false;
                        while turn = j do no-op;
                        flag[i] := true;
                end;

                critical section

        turn := j;
        flag[i] := false;

                remainder section

until false;

    डेकर एल्गोरिथम का पहला वर्जन

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

    Main()
    {
    int thread_number = 1;
    startThreads();
    }
    Thread1()
    {
    do {
    // entry section
    // wait until threadnumber is 1
    while (threadnumber == 2)
    ;
    // critical section
    // exit section
    // give access to the other thread
    threadnumber = 2;
    // remainder section
    } while (completed == false)
    }
    Thread2()
    {
    do {
    // entry section
    // wait until threadnumber is 2
    while (threadnumber == 1)
    ;
    // critical section
    // exit section
    // give access to the other thread
    threadnumber = 1;
    // remainder section
    } while (completed == false)
    }
    उपर वाले इम्प्लीमेंटेशन में ये समस्या आती है कि ये लॉकस्टेप सिंक्रोनाइजेशन है यानी कि इसमें हर एक थ्रेड execution के लिए दूसरे पर निर्भर होता है। अगर उनमे से कोई एक प्रोसेस पूरा हो जाता है तो दूसरा प्रोसेस रन होता है और एक को पूरा एक्सेस दे देता है और अपनी बारी का इन्तजार करता है। जबकि पहला प्रोसेस पहले ही पूरा हो जाता है और और एक्सेस को दूसरे वाले को कभी वापस नहीं करता। इसीलिए दूसरा प्रोसेस हमेशा के लिए इन्तजार ही करता रह जाता है।

    डेकर एल्गोरिथम का दूसरा वर्जन

    लॉकस्टेप सिंक्रोनाइजेशन को हटाने के लिए ये दो फ्लैग का प्रयोग करता है जो इसका अभी का स्टेटस दिखाता है और एंट्री और एग्जिट वाले सेक्शन पर उन्हें अपडेट करता है।

    Main()
    {
    // flags to indicate if each thread is in
    // its critial section or not.
    boolean thread1 = false;
    boolean thread2 = false;
    startThreads();
    }
    Thread1()
    {
    do {
    // entry section
    // wait until thread2 is in its critical section
    while (thread2 == true)
    ;
    // indicate thread1 entering its critical section
    thread1 = true;
    // critical section
    // exit section
    // indicate thread1 exiting its critical section
    thread1 = false;
    // remainder section
    } while (completed == false)
    }
    Thread2()
    {
    do {
    // entry section
    // wait until thread1 is in its critical section
    while (thread1 == true)
    ;
    // indicate thread2 entering its critical section
    thread2 = true;
    // critical section
    // exit section
    // indicate thread2 exiting its critical section
    thread2 = false;
    // remainder section
    } while (completed == false)
    }
    इस वाले वर्जन में ये समस्या आती है कि इसमें म्यूच्यूअल एक्सक्लूशन ही समस्या कड़ी कर देता है।
    अगर थ्रेड को प्फ्लैग अपडेट करने के दौरान ( current_thread = true के दौरान) रीम्प्ट किया जाता है यानी कि रोका जाता है तब दोनों ही थ्रेड अपने क्रिटिकल सेक्शन में चले जाते हैं।
    फिर जब प्रीम्प्ट किये हुए थ्रेड को जब फिर से शुरू किया जाता है तो इए स्टार्ट पर भी ऐसे ही देखा जा सकता है जब दोनों फ्लैग false हो जाएँ।

    डेकर एल्गोरिथम का तीसरा वर्जन

    म्यूच्यूअल एक्सक्लूशन को फिर से सुनिश्चित करने के लिए ये फ्लैग को एंट्री सेक्शन से पहले ही सेट कर देता है।

    Main()
    {
    // flags to indicate if each thread is in
    // queue to enter its critical section
    boolean thread1wantstoenter = false;
    boolean thread2wantstoenter = false;
    startThreads();
    }
    Thread1()
    {
    do {
    thread1wantstoenter = true;
    // entry section
    // wait until thread2 wants to enter
    // its critical section
    while (thread2wantstoenter == true)
    ;
    // critical section
    // exit section
    // indicate thread1 has completed
    // its critical section
    thread1wantstoenter = false;
    // remainder section
    } while (completed == false)
    }
    Thread2()
    {
    do {
    thread2wantstoenter = true;
    // entry section
    // wait until thread1 wants to enter
    // its critical section
    while (thread1wantstoenter == true)
    ;
    // critical section
    // exit section
    // indicate thread2 has completed
    // its critical section
    thread2wantstoenter = false;
    // remainder section
    } while (completed == false)
    }
    डेडलॉक की सम्भावना इस वर्जन के साथ एक बड़ी समस्या है। दोनों फ्लैग एक साथ अपने-अपने फ्लैग को ट्रू सेट कर सकते हैं और इस तरह से दोनों ही हमेशा-हमेशा के लिए इन्तजार करते ही रह जायेंगे।

    डेकर एल्गोरिथम का चौथा वर्जन

    ये कंडीशन को फिर से चेक करने के लिए एक छोटे इंटरवल का प्रयोग करता है। ये डेडलॉक को हटता है और म्यूच्यूअल एक्सक्लूशन भी सुनिश्चित करता है।

    Main()
    {
    // flags to indicate if each thread is in
    // queue to enter its critical section
    boolean thread1wantstoenter = false;
    boolean thread2wantstoenter = false;
    startThreads();
    }
    Thread1()
    {
    do {
    thread1wantstoenter = true;
    while (thread2wantstoenter == true) {
    // gives access to other thread
    // wait for random amount of time
    thread1wantstoenter = false;
    thread1wantstoenter = true;
    }
    // entry section
    // wait until thread2 wants to enter
    // its critical section
    // critical section
    // exit section
    // indicate thread1 has completed
    // its critical section
    thread1wantstoenter = false;
    // remainder section
    } while (completed == false)
    }
    Thread2()
    {
    do {
    thread2wantstoenter = true;
    while (thread1wantstoenter == true) {
    // gives access to other thread
    // wait for random amount of time
    thread2wantstoenter = false;
    thread2wantstoenter = true;
    }
    // entry section
    // wait until thread1 wants to enter
    // its critical section
    // critical section
    // exit section
    // indicate thread2 has completed
    // its critical section
    thread2wantstoenter = false;
    // remainder section
    } while (completed == false)
    }
    इस वर्जन के साथ ये समस्या है कि ये हमेशा के लिए रुक सकता है। इसके अलावे कुछ मात्रा में समय गलत हो जाता है जो कि अल्गोरिथम किस स्थिति में इमप्लेमेंट किया जाता है इस पर निर्भर करता है। इसीलिए इसे बिज़नस क्रिटिकल सिस्टम में कभी स्वीकार नहीं किया जा सकता।

    डेकर एल्गोरिथम का पांचवा वर्जन

    इसमें फवौर किये हुए थ्रेड का प्रयोग करते हैं ताकि क्रिटिकल सेक्शन में एंट्री करने को तय किया जा सके।

    फवौर किया हुआ थ्रेड म्यूच्यूअल एक्सक्लूशन देने वाले थ्रेड और डेडलॉक अवॉयड करने के बीच में घूमता है।

    इसमें हमेशा के लिए प्रोसेस का रुक जाना और लॉकस्टेप सिंक्रोनाइजेशन भी नहीं होता है।

    Main()
    {
        // to denote which thread will enter next
        int favouredthread = 1;
        // flags to indicate if each thread is in
        // queue to enter its critical section
        boolean thread1wantstoenter = false;
        boolean thread2wantstoenter = false;
        startThreads();
    }
    Thread1()
    {
        do {
            thread1wantstoenter = true;
            // entry section
            // wait until thread2 wants to enter
            // its critical section
            while (thread2wantstoenter == true) {
                // if 2nd thread is more favored
                if (favaouredthread == 2) {
                    // gives access to other thread
                    thread1wantstoenter = false;
                    // wait until this thread is favored
                    while (favouredthread == 2)
                        ;
                    thread1wantstoenter = true;
                }
            }
            // critical section
            // favor the 2nd thread
            favouredthread = 2;
            // exit section
            // indicate thread1 has completed
            // its critical section
            thread1wantstoenter = false;
            // remainder section
        } while (completed == false)
    }
    Thread2()
    {
        do {
            thread2wantstoenter = true;
            // entry section
            // wait until thread1 wants to enter
            // its critical section
            while (thread1wantstoenter == true) {
                // if 1st thread is more favored
                if (favaouredthread == 1) {
                    // gives access to other thread
                    thread2wantstoenter = false;
                    // wait until this thread is favored
                    while (favouredthread == 1)
                        ;
                    thread2wantstoenter = true;
                }
            }
            // critical section
            // favour the 1st thread
            favouredthread = 1;
            // exit section
            // indicate thread2 has completed
            // its critical section
            thread2wantstoenter = false;
            // remainder section

        } while (completed == false)

    ये वर्जन समस्या के पूरे समाधान कि गारंटी देता है।

    इस लेख से सम्बंधित यदि आपका कोई भी सवाल या सुझाव है, तो आप उसे नीचे कमेंट में लिख सकते हैं।

    By अनुपम कुमार सिंह

    बीआईटी मेसरा, रांची से कंप्यूटर साइंस और टेक्लॉनजी में स्नातक। गाँधी कि कर्मभूमि चम्पारण से हूँ। समसामयिकी पर कड़ी नजर और इतिहास से ख़ास लगाव। भारत के राजनितिक, सांस्कृतिक और भौगोलिक इतिहास में दिलचस्पी ।

    Related Post

    टैकनोलजी

    Digital Arrest: सावधान! जागते रहो……. !

    Oct 30, 2024 Saurav Sangam
    टैकनोलजी विदेश

    एफिल टॉवर पर लहराया UPI का झंडा, डिजिटल भुगतान क्रांति हुई वैश्विक

    Feb 4, 2024 Shashi Kumar
    टैकनोलजी

    भारत सेमीकंडक्टर दौड़ में लगा रहा छलांग, सिनॉप्सिस ने नोएडा में स्थापित किया चिप डिजाइन केंद्र

    Jan 25, 2024 Shashi Kumar

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    You missed

    स्वास्थ्य

    आपको हर सुबह भीगे हुए बादाम क्यों खाने चाहिए?

    Nov 15, 2024 The Indian Wire Staff 0 Comments
    टैकनोलजी

    Digital Arrest: सावधान! जागते रहो……. !

    Oct 30, 2024 Saurav Sangam 0 Comments
    शिक्षा

    As You Like It Summary in Hindi (सारांश हिंदी में)

    Oct 26, 2024 The Indian Wire Staff 0 Comments
    मनोरंजन

    इन रंगोली डिज़ाइनों के साथ अपनी दिवाली की सजावट को बढ़ाएँ

    Oct 26, 2024 The Indian Wire Staff 0 Comments