डेकर एल्गोरिथम क्या है? 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);

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

म्यूच्यूअल एक्सक्लूशन
प्रोग्रेस
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)

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

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

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

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

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

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

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

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

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

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

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

Related Post

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

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

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

Leave a Reply Cancel reply

You missed

पूजा स्थल अधिनियम: अगली सुनवाई तक कोई नया मुकदमा दर्ज नहीं किया जाएगा-सुप्रीम कोर्ट

प्रस्तावना के ‘समाजवादी’ व ‘धर्मनिरपेक्ष’ शब्दों को चुनौती और सर्वोच्च अदालत का फैसला

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

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