विषय-सूचि
डेकर एल्गोरिथम का परिचय (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 1while (threadnumber == 2);// critical section// exit section// give access to the other threadthreadnumber = 2;// remainder section} while (completed == false)}Thread2(){do {// entry section// wait until threadnumber is 2while (threadnumber == 1);// critical section// exit section// give access to the other threadthreadnumber = 1;// remainder section} while (completed == false)}डेकर एल्गोरिथम का दूसरा वर्जन
लॉकस्टेप सिंक्रोनाइजेशन को हटाने के लिए ये दो फ्लैग का प्रयोग करता है जो इसका अभी का स्टेटस दिखाता है और एंट्री और एग्जिट वाले सेक्शन पर उन्हें अपडेट करता है।
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 sectionwhile (thread2 == true);// indicate thread1 entering its critical sectionthread1 = true;// critical section// exit section// indicate thread1 exiting its critical sectionthread1 = false;// remainder section} while (completed == false)}Thread2(){do {// entry section// wait until thread1 is in its critical sectionwhile (thread1 == true);// indicate thread2 entering its critical sectionthread2 = true;// critical section// exit section// indicate thread2 exiting its critical sectionthread2 = false;// remainder section} while (completed == false)}डेकर एल्गोरिथम का तीसरा वर्जन
म्यूच्यूअल एक्सक्लूशन को फिर से सुनिश्चित करने के लिए ये फ्लैग को एंट्री सेक्शन से पहले ही सेट कर देता है।
Main(){// flags to indicate if each thread is in// queue to enter its critical sectionboolean thread1wantstoenter = false;boolean thread2wantstoenter = false;startThreads();}Thread1(){do {thread1wantstoenter = true;// entry section// wait until thread2 wants to enter// its critical sectionwhile (thread2wantstoenter == true);// critical section// exit section// indicate thread1 has completed// its critical sectionthread1wantstoenter = false;// remainder section} while (completed == false)}Thread2(){do {thread2wantstoenter = true;// entry section// wait until thread1 wants to enter// its critical sectionwhile (thread1wantstoenter == true);// critical section// exit section// indicate thread2 has completed// its critical sectionthread2wantstoenter = false;// remainder section} while (completed == false)}डेकर एल्गोरिथम का चौथा वर्जन
ये कंडीशन को फिर से चेक करने के लिए एक छोटे इंटरवल का प्रयोग करता है। ये डेडलॉक को हटता है और म्यूच्यूअल एक्सक्लूशन भी सुनिश्चित करता है।
Main(){// flags to indicate if each thread is in// queue to enter its critical sectionboolean thread1wantstoenter = false;boolean thread2wantstoenter = false;startThreads();}Thread1(){do {thread1wantstoenter = true;while (thread2wantstoenter == true) {// gives access to other thread// wait for random amount of timethread1wantstoenter = false;thread1wantstoenter = true;}// entry section// wait until thread2 wants to enter// its critical section// critical section// exit section// indicate thread1 has completed// its critical sectionthread1wantstoenter = false;// remainder section} while (completed == false)}Thread2(){do {thread2wantstoenter = true;while (thread1wantstoenter == true) {// gives access to other thread// wait for random amount of timethread2wantstoenter = false;thread2wantstoenter = true;}// entry section// wait until thread1 wants to enter// its critical section// critical section// exit section// indicate thread2 has completed// its critical sectionthread2wantstoenter = 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)
ये वर्जन समस्या के पूरे समाधान कि गारंटी देता है।
इस लेख से सम्बंधित यदि आपका कोई भी सवाल या सुझाव है, तो आप उसे नीचे कमेंट में लिख सकते हैं।