निर्माता-उपभोक्ता समस्या: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
[[कम्प्यूटिंग]] में, निर्माता-उपभोक्ता समस्या (जिसे बाउंडेड-बफर समस्या के रूप में भी जाना जाता है) 1965 से एडजर डब्ल्यू. डिज्कस्ट्रा द्वारा वर्णित समस्याओं का एक परिवार है।
[[कम्प्यूटिंग]] में, निर्माता-उपभोक्ता समस्या (जिसे बाउंडेड-बफर समस्या के रूप में भी जाना जाता है) 1965 से एडजर डब्ल्यू. डिज्कस्ट्रा द्वारा वर्णित समस्याओं का एक परिवार है।


डीजक्स्ट्रा ने निर्माता-उपभोक्ता समस्या का समाधान पाया क्योंकि उन्होंने [[इलेक्ट्रोलॉजिका]] X1 और X8 कंप्यूटरों के लिए एक सलाहकार के रूप में काम किया: निर्माता-उपभोक्ता का पहला उपयोग आंशिक रूप से सॉफ्टवेयर, आंशिक रूप से हार्डवेयर था: स्टोर और परिधीय के बीच सूचना परिवहन की देखभाल करने वाला घटक 'एक चैनल' कहा जाता था ... सिंक्रनाइज़ेशन को दो काउंटिंग सेमाफोर द्वारा नियंत्रित किया जाता था जिसे अब हम निर्माता/उपभोक्ता व्यवस्था के रूप में जानते हैं: एक सेमाफोर लाइन की लंबाई का संकेत देता है, CPU द्वारा (V में) बढ़ाया गया था और घटाया गया था (एक P में) चैनल द्वारा, अन्य एक, अनजाने पूर्णताओं की संख्या की गणना करते हुए, चैनल द्वारा बढ़ाया गया था और CPU द्वारा घटाया गया था। [दूसरा सेमाफोर धनात्मक होने के कारण संबंधित इंटरप्ट फ्लैग को उठाएगा।]<ref>[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1303.html Dijkstra; 2000; EWD1303 My recollections of operating system design]</ref>
डीजक्स्ट्रा ने निर्माता-उपभोक्ता समस्या का समाधान पाया क्योंकि उन्होंने [[इलेक्ट्रोलॉजिका]] X1 और X8 कंप्यूटरों के लिए एक सलाहकार के रूप में काम किया: निर्माता-उपभोक्ता का पहला उपयोग आंशिक रूप से सॉफ्टवेयर, आंशिक रूप से हार्डवेयर था: स्टोर और परिधीय के बीच सूचना परिवहन की देखभाल करने वाला घटक 'एक चैनल' कहा जाता था ... सिंक्रनाइज़ेशन को दो काउंटिंग सेमाफोर द्वारा नियंत्रित किया जाता था जिसे अब हम निर्माता/उपभोक्ता व्यवस्था के रूप में जानते हैं: एक सेमाफोर लाइन की लंबाई का संकेत देता है, CPU द्वारा (V में) बढ़ाया और घटाया गया था (एक P में) चैनल द्वारा, अन्य एक, अनजाने पूर्णताओं की संख्या की गणना करते हुए, चैनल द्वारा बढ़ाया गया था और CPU द्वारा घटाया गया था। [दूसरा सेमाफोर धनात्मक होने के कारण संबंधित इंटरप्ट फ्लैग को उठाएगा।]<ref>[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1303.html Dijkstra; 2000; EWD1303 My recollections of operating system design]</ref>


दिज्क्स्ट्रा ने असीमित बफर की स्थिति के बारे में लिखा: हम दो प्रक्रियाओं पर विचार करते हैं, जिन्हें क्रमशः 'निर्माता' और 'उपभोक्ता' कहा जाता है। निर्माता एक चक्रीय प्रक्रिया है और हर बार जब यह अपने चक्र से गुजरता है तो यह सूचना का एक निश्चित भाग उत्पन्न करता है, जिसे उपभोक्ता द्वारा संसाधित किया जाना है। उपभोक्ता भी चक्रीय प्रक्रिया है और हर बार जब वह अपने चक्र से गुजरता है, तो वह सूचना के अगले हिस्से को संसाधित कर सकता है, जैसा कि निर्माता द्वारा निर्मित किया गया है ... हम मानते हैं कि इस उद्देश्य के लिए दो प्रक्रियाओं को एक बफर के माध्यम से असीमित क्षमता के साथ जोड़ा जाना चाहिए।<ref>[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html#4.1.%20Typical%20Uses%20of%20the%20General%20Semaphore. Dijkstra; 1965; EWD123 Cooperating sequential processes, section 4.1. Typical Uses of the General Semaphore.]</ref>
दिज्क्स्ट्रा ने असीमित बफर की स्थिति के बारे में लिखा: हम दो प्रक्रियाओं पर विचार करते हैं, जिन्हें क्रमशः 'निर्माता' और 'उपभोक्ता' कहा जाता है। निर्माता एक चक्रीय प्रक्रिया है और हर बार जब यह अपने चक्र से गुजरता है तो यह सूचना का एक निश्चित भाग उत्पन्न करता है, जिसे उपभोक्ता द्वारा संसाधित किया जाना है। उपभोक्ता भी चक्रीय प्रक्रिया है और हर बार जब वह अपने चक्र से गुजरता है, तो वह सूचना के अगले हिस्से को संसाधित कर सकता है, जैसा कि निर्माता द्वारा निर्मित किया गया है ... हम मानते हैं कि इस उद्देश्य के लिए दो प्रक्रियाओं को एक बफर के माध्यम से असीमित क्षमता के साथ जोड़ा जाना चाहिए।<ref>[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html#4.1.%20Typical%20Uses%20of%20the%20General%20Semaphore. Dijkstra; 1965; EWD123 Cooperating sequential processes, section 4.1. Typical Uses of the General Semaphore.]</ref>
Line 40: Line 40:
end
end
</syntaxhighlight>
</syntaxhighlight>
C++ 20 के अनुसार, सेमाफोर भाषा का भाग हैं। डीजक्स्ट्रा के समाधान को आधुनिक C++ में आसानी से लिखा जा सकता है। परिवर्तनीय बफर_मैनिपुलेशन एक म्यूटेक्स है। एक थ्रेड में प्राप्त करने और दूसरे थ्रेड में रिलीज़ करने की सेमाफोर सुविधा की आवश्यकता नहीं है। लॉक() और अनलॉक() जोड़ी के अतिरिक्त लॉक_गार्ड() कथन सी ++ आरएआईआई है। लॉक_गार्ड डिस्ट्रक्टर अपवाद के मामले में लॉक रिलीज सुनिश्चित करता है। यह समाधान एकाधिक उपभोक्ता धागे और/या एकाधिक निर्माता धागे को संभाल सकता है।
C++ 20 के अनुसार, सेमाफोर भाषा का भाग हैं। डीजक्स्ट्रा के समाधान को आधुनिक C++ में आसानी से लिखा जा सकता है। परिवर्तनीय बफर_मैनिपुलेशन एक म्यूटेक्स है। एक थ्रेड में अधिग्रहण करने और दूसरे थ्रेड में रिलीज करने की सेमफोर विशेषता की आवश्यकता नहीं है। लॉक() और अनलॉक() जोड़ी के अतिरिक्त लॉक_गार्ड() कथन C++ RAII है। लॉक_गार्ड डिस्ट्रक्टर अपवाद की स्थिति में लॉक रिलीज सुनिश्चित करता है। यह समाधान कई उपभोक्ता थ्रेड और/या कई निर्माता थ्रेड को संभाल सकता है।
 
<वाक्यविन्यास प्रकाश लैंग = सी ++>
#सम्मिलित <थ्रेड>
#सम्मिलित <थ्रेड>
#सम्मिलित <म्यूटेक्स>
#सम्मिलित <म्यूटेक्स>
Line 86: Line 84:


== मॉनिटर का प्रयोग ==
== मॉनिटर का प्रयोग ==
प्रति ब्रिंच हैनसेन ने मॉनिटर को परिभाषित किया: मैं एक साझा चर और उस पर सार्थक संचालन के सेट को निरूपित करने के लिए मॉनिटर शब्द का उपयोग करूंगा। एक मॉनिटर का उद्देश्य एक निश्चित नीति के अनुसार अलग-अलग प्रक्रियाओं के बीच संसाधनों की समयबद्धता को नियंत्रित करना है।<ref>Per Brinch Hansen; 1973; Operating System Principles, 3.4.7. Event Queues</ref> [[टोनी होरे]] ने मॉनिटर के लिए सैद्धांतिक नींव रखी।<ref>C.A.R. Hoare; 1974; Monitors: An Operating System Structuring Concept, 4. Example: Bounded Buffer</ref>
प्रति ब्रिंच हैनसेन ने मॉनिटर को परिभाषित किया: मैं एक साझा चर और उस पर सार्थक संचालन के सेट को निरूपित करने के लिए मॉनिटर शब्द का उपयोग करूंगा। एक मॉनिटर का उद्देश्य निश्चित नीति के अनुसार अलग-अलग प्रक्रियाओं के बीच संसाधनों की समयबद्धता को नियंत्रित करना है।<ref>Per Brinch Hansen; 1973; Operating System Principles, 3.4.7. Event Queues</ref> [[टोनी होरे]] ने मॉनिटर के लिए सैद्धांतिक नींव रखी थी।<ref>C.A.R. Hoare; 1974; Monitors: An Operating System Structuring Concept, 4. Example: Bounded Buffer</ref>


<syntaxhighlight lang="Pascal">
<syntaxhighlight lang="Pascal">
Line 113: Line 111:
end bounded buffer;
end bounded buffer;
</syntaxhighlight>
</syntaxhighlight>
मॉनिटर एक वस्तु है जिसमें चर होते हैं <code>buffer</code>, <code>head</code>, <code>tail</code> और <code>count</code> एक परिपत्र बफर का एहसास करने के लिए, स्थिति चर <code>nonempty</code> और <code>nonfull</code> तुल्यकालन और तरीकों के लिए <code>append</code> और <code>remove</code> बंधे हुए बफर तक पहुँचने के लिए। मॉनिटर ऑपरेशन प्रतीक्षा सेमाफोर ऑपरेशन पी या अधिग्रहण से मेल खाती है, सिग्नल वी या रिलीज से मेल खाता है। गोलाकार ऑपरेशन (+) को मोडुलो एन लिया जाता है। प्रस्तुत पास्कल शैली [[छद्म कोड]] एक होरे मॉनिटर दिखाता है। एक [[मेसा (प्रोग्रामिंग भाषा)]] मॉनिटर उपयोग करता है <code>while count</code> के अतिरिक्त <code>if count</code>. एक प्रोग्रामिंग भाषा C++ संस्करण है:
मॉनिटर एक वस्तु है जिसमें चर होते हैं <code>बफर,</code> <code>हेड,</code> <code>टेल</code> और <code>काउंट</code> एक परिपत्र बफर का एहसास करने के लिए, स्थिति चर जो तुल्यकालन के लिए <code>अरिक्त</code> और <code>नॉनफुल</code> होता है और विधियों को संलग्न और निर्दिष्ट बफर तक पहुंचने के लिए हटा देता है। मॉनिटर ऑपरेशन वेट सेमाफोर ऑपरेशन P या अधिग्रहण से मेल खाती है, सिग्नल वी या रिलीज से मेल खाता है। गोलाकार ऑपरेशन (+) को मोडुलो N लिया जाता है। प्रस्तुत पास्कल शैली [[छद्म कोड|सूडो कोड]] एक होयर मॉनिटर दिखाता है। एक [[मेसा (प्रोग्रामिंग भाषा)]] <code>गिनती</code> के अतिरिक्त मॉनिटर उपयोग करता है। एक प्रोग्रामिंग भाषा C++ संस्करण है:


<वाक्यविन्यास प्रकाश लैंग = सी ++>
वर्ग Bounded_buffer {
   class Bounded_buffer {
   class Bounded_buffer {


Line 149: Line 145:
  };
  };


 
C++ संस्करण को तकनीकी कारणों के अतिरिक्त म्यूटेक्स की आवश्यकता है। यह बफ़र जोड़ने और हटाने के संचालन के लिए पूर्व शर्त लागू करने के लिए दृढ़ता का उपयोग करता है।
सी ++ संस्करण को तकनीकी कारणों से अतिरिक्त म्यूटेक्स की आवश्यकता है। यह बफ़र जोड़ने और हटाने के संचालन के लिए पूर्व शर्त लागू करने के लिए जोर का उपयोग करता है।


== चैनलों का उपयोग करना ==
== चैनलों का उपयोग करना ==
इलेक्ट्रोलॉजिका कंप्यूटरों में सबसे पहले निर्माता-उपभोक्ता समाधान ने 'चैनल' का इस्तेमाल किया। होरे परिभाषित [[चैनल (प्रोग्रामिंग)]]: स्रोत और गंतव्य के स्पष्ट नामकरण का एक विकल्प
इलेक्ट्रोलॉजिका कंप्यूटरों में सबसे पहले निर्माता-उपभोक्ता समाधान ने 'चैनल' का उपयोग किया। होरे परिभाषित [[चैनल (प्रोग्रामिंग)]]: स्रोत और गंतव्य के स्पष्ट नामकरण का एक विकल्प एक पोर्ट का नाम देना होगा जिसके माध्यम से संचार होना है। पोर्ट नाम प्रक्रियाओं के लिए स्थानीय होंगे, और जिस तरीके से पोर्ट के जोड़े को चैनलों से जोड़ा जाना है, उसे समानांतर कमांड के प्रमुख में घोषित किया जा सकता है।<ref>Hoare; 1978; Communicating Sequential Processes, 7.3 Port Names</ref> ब्रिन्च हैनसेन ने प्रोग्रामिंग भाषाओं जॉयस (प्रोग्रामिंग भाषा) संचार और सुपर पास्कल चैनल और संचार में चैनलों को कार्यान्वित किया। प्लान 9 ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज एलेफ (प्रोग्रामिंग लैंग्वेज), इन्फर्नो ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज [[ लिम्बो (प्रोग्रामिंग भाषा) ]] में चैनल हैं। निम्नलिखित C स्रोत कोड [[यूजर स्पेस से प्लान 9]] पर संकलित है:
एक बंदरगाह का नाम देना होगा जिसके माध्यम से संचार होना है। पोर्ट नाम प्रक्रियाओं के लिए स्थानीय होंगे, और जिस तरीके से बंदरगाहों के जोड़े को चैनलों से जोड़ा जाना है, उसे समानांतर कमांड के प्रमुख में घोषित किया जा सकता है।<ref>Hoare; 1978; Communicating Sequential Processes, 7.3 Port Names</ref> ब्रिन्च हैनसेन ने प्रोग्रामिंग भाषाओं जॉयस (प्रोग्रामिंग भाषा) # संचार और सुपर पास्कल # चैनल और संचार में चैनलों को कार्यान्वित किया। प्लान 9 ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज एलेफ (प्रोग्रामिंग लैंग्वेज), इन्फर्नो ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज [[ लिम्बो (प्रोग्रामिंग भाषा) ]] में चैनल हैं। निम्नलिखित सी स्रोत कोड [[यूजर स्पेस से प्लान 9]] पर संकलित है:


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 189: Line 183:
}
}
</syntaxhighlight>
</syntaxhighlight>
कार्यक्रम का प्रवेश बिंदु कार्य कर रहा है <code>threadmain</code>. समारोह कॉल <code>ch = chancreate(sizeof(ulong), 1)</code> चैनल बनाता है, फ़ंक्शन कॉल करता है <code>sendul(ch, i)</code> चैनल और फ़ंक्शन कॉल में मान भेजता है <code>p = recvul(ch)</code> चैनल से मूल्य प्राप्त करता है। प्रोग्रामिंग लैंग्वेज गो (प्रोग्रामिंग लैंग्वेज)#Concurrency: goroutines और channel में चैनल भी हैं। एक जाओ उदाहरण:
फलन का प्रवेश बिंदु <code>थ्रेडमेन</code>कार्य कर रहा है, फ़ंक्शन कॉल <code>ch = chancreate(sizeof(ulong), 1)</code> चैनल बनाता है, फ़ंक्शन कॉल करता है <code>sendul(ch, i)</code> चैनल और फ़ंक्शन कॉल में मान भेजता है <code>p = recvul(ch)</code> चैनल से मूल्य प्राप्त करता है। प्रोग्रामिंग लैंग्वेज गो (प्रोग्रामिंग लैंग्वेज) में चैनल भी हैं। एक गो उदाहरण:


<syntaxhighlight lang="Go">
<syntaxhighlight lang="Go">
Line 227: Line 221:


== सेमाफोर या मॉनिटर के बिना ==
== सेमाफोर या मॉनिटर के बिना ==
[[लेस्ली लामपोर्ट]] ने एक निर्माता और एक उपभोक्ता के लिए एक बाध्य बफर निर्माता-उपभोक्ता समाधान प्रलेखित किया: हम मानते हैं कि बफर अधिकतम बी संदेशों को पकड़ सकता है, बी> = 1। हमारे समाधान में, हम के को बी से अधिक निरंतर होने देते हैं, और चलो s और r पूर्णांक चर हैं जो 0 और k-1 के बीच मान मानते हैं। हम मानते हैं कि शुरू में s=r और बफर खाली है।
[[लेस्ली लामपोर्ट]] ने एक निर्माता और एक उपभोक्ता के लिए बाध्य बफर निर्माता-उपभोक्ता समाधान प्रलेखित किया: हम मानते हैं कि b बफर अधिकतम b >= 1 संदेशों को पकड़ सकता है। हमारे समाधान में, हम k को b से अधिक निरंतर होने देते हैं, और चलो s और r पूर्णांक चर हैं जो 0 और k-1 के बीच मान मानते हैं। हम मानते हैं कि शुरू में s=r और बफर खाली है। k को b का एक बहु होने के लिए चुनकर, बफर को एक सरणी B [0: b - 1] के रूप में लागू किया जा सकता है। निर्माता बस प्रत्येक नए संदेश को B[s mod b] में डालता है, और उपभोक्ता प्रत्येक संदेश को B[r mod b] से लेता है।<ref>Lamport, Leslie; 1977; Proving the Correctness of Multiprocess Programs, The Producer/Consumer Example</ref> एल्गोरिथ्म नीचे दिखाया गया है, अपरिमित k के लिए सामान्यीकृत किया गया है।
k को b का एक बहु होने के लिए चुनकर, बफर को एक सरणी B [0: b - 1] के रूप में लागू किया जा सकता है। निर्माता बस प्रत्येक नए संदेश को B[s mod b] में डालता है, और उपभोक्ता प्रत्येक संदेश को B[r mod b] से लेता है।<ref>Lamport, Leslie; 1977; Proving the Correctness of Multiprocess Programs, The Producer/Consumer Example</ref> एल्गोरिदम नीचे दिखाया गया है, अनंत के लिए सामान्यीकृत।


<syntaxhighlight lang="Pascal">
<syntaxhighlight lang="Pascal">
Line 242: Line 235:
       goto L;
       goto L;
</syntaxhighlight>
</syntaxhighlight>
लैमपोर्ट समाधान शेड्यूलर में प्रतीक्षा करने के अतिरिक्त थ्रेड में व्यस्त प्रतीक्षा का उपयोग करता है। यह समाधान असुविधाजनक समय पर अनुसूचक थ्रेड स्विच के प्रभाव की उपेक्षा करता है। यदि पहले थ्रेड ने मेमोरी से वैरिएबल मान पढ़ा है, तो शेड्यूलर दूसरे थ्रेड पर स्विच करता है जो वेरिएबल मान को बदलता है, और शेड्यूलर पहले थ्रेड पर वापस स्विच करता है, फिर पहला थ्रेड वेरिएबल के पुराने मान का उपयोग करता है, वर्तमान मान का नहीं . परमाणु पढ़ें-संशोधित-लिखें | पढ़ें-संशोधित-लेखन इस समस्या को हल करता है। आधुनिक सी ++ ऑफर <code>atomic</code> मल्टी-थ्रेड प्रोग्रामिंग के लिए चर और संचालन। एक निर्माता और एक उपभोक्ता के लिए निम्नलिखित व्यस्त प्रतीक्षा सी ++ 11 समाधान परमाणु पठन-संशोधित-लेखन संचालन का उपयोग करता है <code>fetch_add</code> और <code>fetch_sub</code> परमाणु चर पर <code>count</code>.
लैमपोर्ट समाधान शेड्यूलर में प्रतीक्षा करने के अतिरिक्त थ्रेड में व्यस्त प्रतीक्षा का उपयोग करता है। यह समाधान असुविधाजनक समय पर शेड्यूलर थ्रेड स्विच के प्रभाव की उपेक्षा करता है। यदि पहले थ्रेड ने स्मृति से एक चर मूल्य पढ़ा है, शेड्यूलर दूसरे थ्रेड पर स्विच करता है जो चर मूल्य को बदलता है, और शेड्यूलर पहले थ्रेड में वापस स्विच करता है, तो पहला थ्रेड वेरिएबल के पुराने मूल्य न कि वर्तमान मूल्य का उपयोग करता है। परमाणु रीड-मोडिफाई-राइट इस समस्या को हल करते हैं। आधुनिक C++ ऑफर <code>अटामिक</code> मल्टी-थ्रेड प्रोग्रामिंग के लिए परमाणु चर और संचालन प्रदान करता है। एक निर्माता और एक उपभोक्ता के लिए निम्नलिखित व्यस्त प्रतीक्षा C++11 समाधान एटम रीड-मोडिफाई-राइट ऑपरेशन <code>fetch_add</code> और <code>fetch_sub</code> का उपयोग करता है।
 
<वाक्यविन्यास प्रकाश लैंग = सी ++>
एनम {एन = 4};
संदेश बफर [एन];
एसटीडी :: परमाणु <अहस्ताक्षरित> गिनती {0};
शून्य निर्माता () {
   enum {N = 4 };
   enum {N = 4 };


Line 281: Line 268:
   t2.join();
   t2.join();
  }
  }
परिपत्र बफर सूचकांक चर <code>head</code> और <code>tail</code> थ्रेड-लोकल हैं और इसलिए मेमोरी स्थिरता के लिए प्रासंगिक नहीं हैं। चर <code>count</code> निर्माता और उपभोक्ता धागे की व्यस्त प्रतीक्षा को नियंत्रित करता है।
परिपत्र बफर सूचकांक चर <code>हेड</code> और <code>टेल</code> थ्रेड-लोकल हैं और इसलिए मेमोरी स्थिरता के लिए प्रासंगिक नहीं हैं। चर <code>गिनती</code> निर्माता और उपभोक्ता थ्रेड की व्यस्त प्रतीक्षा को नियंत्रित करता है।


== यह भी देखें ==
== यह भी देखें ==

Revision as of 12:53, 7 June 2023

कम्प्यूटिंग में, निर्माता-उपभोक्ता समस्या (जिसे बाउंडेड-बफर समस्या के रूप में भी जाना जाता है) 1965 से एडजर डब्ल्यू. डिज्कस्ट्रा द्वारा वर्णित समस्याओं का एक परिवार है।

डीजक्स्ट्रा ने निर्माता-उपभोक्ता समस्या का समाधान पाया क्योंकि उन्होंने इलेक्ट्रोलॉजिका X1 और X8 कंप्यूटरों के लिए एक सलाहकार के रूप में काम किया: निर्माता-उपभोक्ता का पहला उपयोग आंशिक रूप से सॉफ्टवेयर, आंशिक रूप से हार्डवेयर था: स्टोर और परिधीय के बीच सूचना परिवहन की देखभाल करने वाला घटक 'एक चैनल' कहा जाता था ... सिंक्रनाइज़ेशन को दो काउंटिंग सेमाफोर द्वारा नियंत्रित किया जाता था जिसे अब हम निर्माता/उपभोक्ता व्यवस्था के रूप में जानते हैं: एक सेमाफोर लाइन की लंबाई का संकेत देता है, CPU द्वारा (V में) बढ़ाया और घटाया गया था (एक P में) चैनल द्वारा, अन्य एक, अनजाने पूर्णताओं की संख्या की गणना करते हुए, चैनल द्वारा बढ़ाया गया था और CPU द्वारा घटाया गया था। [दूसरा सेमाफोर धनात्मक होने के कारण संबंधित इंटरप्ट फ्लैग को उठाएगा।][1]

दिज्क्स्ट्रा ने असीमित बफर की स्थिति के बारे में लिखा: हम दो प्रक्रियाओं पर विचार करते हैं, जिन्हें क्रमशः 'निर्माता' और 'उपभोक्ता' कहा जाता है। निर्माता एक चक्रीय प्रक्रिया है और हर बार जब यह अपने चक्र से गुजरता है तो यह सूचना का एक निश्चित भाग उत्पन्न करता है, जिसे उपभोक्ता द्वारा संसाधित किया जाना है। उपभोक्ता भी चक्रीय प्रक्रिया है और हर बार जब वह अपने चक्र से गुजरता है, तो वह सूचना के अगले हिस्से को संसाधित कर सकता है, जैसा कि निर्माता द्वारा निर्मित किया गया है ... हम मानते हैं कि इस उद्देश्य के लिए दो प्रक्रियाओं को एक बफर के माध्यम से असीमित क्षमता के साथ जोड़ा जाना चाहिए।[2]

उन्होंने सीमित बफर की स्थिति के बारे में लिखा: हमने निर्माता और उपभोक्ता को एक बफर के माध्यम से असीमित क्षमता के साथ अध्ययन किया है ... जो बफर के माध्यम से असीम क्षमता के साथ जुड़ा हुआ है . संबंध सममित हो जाता है, अगर दोनों परिमित आकार के बफर के माध्यम से जोड़े जाते हैं, N भाग कहते हैं।"[3]

और कई निर्माता-उपभोक्ता की स्थिति के बारे में: हम कई निर्माता/उपभोक्ता जोड़े पर विचार करते हैं, जहां जोड़ी को एक सूचना धारा के माध्यम से जोड़ा जाता है जिसमें ni भाग होते हैं। हम मानते हैं ... परिमित बफ़र जिसमें सभी धाराओं के सभी भाग सम्मिलित होने चाहिए, जिसमें 'टॉट' भाग की क्षमता होनी चाहिए।[4]

प्रति ब्रिन्च हैनसेन और निकोलस विर्थ ने जल्द ही सेमाफोर की समस्या को देखा: मैं सेमाफोर के संबंध में एक ही निष्कर्ष पर पहुंचा हूं, अर्थात् वे उच्च स्तरीय भाषाओं के लिए उपयुक्त नहीं हैं। इसके अतिरिक्त, प्राकृतिक तुल्यकालन घटनाएँ संदेश का आदान-प्रदान हैं।[5]


दिज्क्स्ट्रा का सीमित बफर समाधान

प्रारंभिक सेमाफोर सीमित बफर समाधान ALGOL शैली में लिखा गया था। बफर N भागों या तत्वों को स्टोर कर सकता है। कतारबद्ध भागों की संख्या सेमाफोर (प्रोग्रामिंग) बफर में भरे हुए स्थानों की गणना करता है, खाली पदों की संख्या सेमाफोर बफर में खाली स्थानों की गणना करता है और सेमाफोर बफर हेरफेर बफर पुट और ऑपरेशन प्राप्त करने के लिए म्युटेक्स के रूप में काम करता है। यदि बफ़र भरा हुआ है, यानी खाली स्थिति की संख्या शून्य है, तो निर्माता थ्रेड P (खाली स्थिति की संख्या) ऑपरेशन में प्रतीक्षा करेगा। यदि बफ़र खाली है, यानी कतारबद्ध भागों की संख्या शून्य है, तो उपभोक्ता धागा P (कतारबद्ध भागों की संख्या) ऑपरेशन में प्रतीक्षा करेगा। V() ऑपरेशन सेमाफोर जारी करते हैं। साइड इफेक्ट के रूप में, एक थ्रेड प्रतीक्षा कतार से तैयार कतार में जा सकता है। P() ऑपरेशन सेमाफोर मान को घटाकर शून्य कर देता है। V() ऑपरेशन सेमाफोर मान को बढ़ाता है।[6]

begin integer number of queueing portions, number of empty positions,
      buffer manipulation;
      number of queueing portions:= 0;
      number of empty positions:= N;
      buffer manipulation:= 1;
      parbegin
      producer: begin
              again 1: produce next portion;
                       P(number of empty positions);
                       P(buffer manipulation);
                       add portion to buffer;
                       V(buffer manipulation);
                       V(number of queueing portions); goto again 1 end;
      consumer: begin
              again 2: P(number of queueing portions);
                       P(buffer manipulation);
                       take portion from buffer;
                       V(buffer manipulation) ;
                       V(number of empty positions);
                       process portion taken; goto again 2 end
      parend
end

C++ 20 के अनुसार, सेमाफोर भाषा का भाग हैं। डीजक्स्ट्रा के समाधान को आधुनिक C++ में आसानी से लिखा जा सकता है। परिवर्तनीय बफर_मैनिपुलेशन एक म्यूटेक्स है। एक थ्रेड में अधिग्रहण करने और दूसरे थ्रेड में रिलीज करने की सेमफोर विशेषता की आवश्यकता नहीं है। लॉक() और अनलॉक() जोड़ी के अतिरिक्त लॉक_गार्ड() कथन C++ RAII है। लॉक_गार्ड डिस्ट्रक्टर अपवाद की स्थिति में लॉक रिलीज सुनिश्चित करता है। यह समाधान कई उपभोक्ता थ्रेड और/या कई निर्माता थ्रेड को संभाल सकता है।

  1. सम्मिलित <थ्रेड>
  2. सम्मिलित <म्यूटेक्स>
  3. सम्मिलित <सेमाफोर>

std::counting_semaphore<N> number_of_queueing_portions{0};

std::counting_semaphore<N> number_of_empty_positions{N};

std::mutex buffer_manipulation;

 void producer() {
  for (;;) {
    Portion portion = produce_next_portion();
    number_of_empty_positions.acquire();
    {
      std::lock_guard<std::mutex> g(buffer_manipulation);
      add_portion_to_buffer(portion);
    }
    number_of_queueing_portions.release();
  }
}

void consumer() {
  for (;;) {
    number_of_queueing_portions.acquire();
    Portion portion;
    {
      std::lock_guard<std::mutex> g(buffer_manipulation);
      portion = take_portion_from_buffer();
    }
    number_of_empty_positions.release();
    process_portion_taken(portion);
  }
}

int main() {
  std::thread t1(producer);
  std::thread t2(consumer);
  t1.join();
  t2.join();
}

मॉनिटर का प्रयोग

प्रति ब्रिंच हैनसेन ने मॉनिटर को परिभाषित किया: मैं एक साझा चर और उस पर सार्थक संचालन के सेट को निरूपित करने के लिए मॉनिटर शब्द का उपयोग करूंगा। एक मॉनिटर का उद्देश्य निश्चित नीति के अनुसार अलग-अलग प्रक्रियाओं के बीच संसाधनों की समयबद्धता को नियंत्रित करना है।[7] टोनी होरे ने मॉनिटर के लिए सैद्धांतिक नींव रखी थी।[8]

bounded buffer: monitor
  begin buffer:array 0..N-1 of portion;
    head, tail: 0..N-1;
    count: 0..N;
    nonempty, nonfull: condition;
  procedure append(x: portion);
    begin if count = N then nonfull.wait;
      note 0 <= count < N;
      buffer[tail] := x;
      tail := tail (+) 1;
      count := count + 1;
      nonempty.signal
    end append;
  procedure remove(result x: portion) ;
    begin if count = 0 then nonempty.wait;
      note 0 < count <= N;
      x := buffer[head];
      head := head (+) 1;
      count := count - 1;
      nonfull.signal
    end remove;
  head := 0; tail := 0; count := 0;
end bounded buffer;

मॉनिटर एक वस्तु है जिसमें चर होते हैं बफर, हेड, टेल और काउंट एक परिपत्र बफर का एहसास करने के लिए, स्थिति चर जो तुल्यकालन के लिए अरिक्त और नॉनफुल होता है और विधियों को संलग्न और निर्दिष्ट बफर तक पहुंचने के लिए हटा देता है। मॉनिटर ऑपरेशन वेट सेमाफोर ऑपरेशन P या अधिग्रहण से मेल खाती है, सिग्नल वी या रिलीज से मेल खाता है। गोलाकार ऑपरेशन (+) को मोडुलो N लिया जाता है। प्रस्तुत पास्कल शैली सूडो कोड एक होयर मॉनिटर दिखाता है। एक मेसा (प्रोग्रामिंग भाषा) गिनती के अतिरिक्त मॉनिटर उपयोग करता है। एक प्रोग्रामिंग भाषा C++ संस्करण है:

 class Bounded_buffer {
  Portion buffer[N];    // 0..N-1
  unsigned head, tail;  // 0..N-1
  unsigned count;       // 0..N
  std::condition_variable nonempty, nonfull;
  std::mutex mtx;
public:
  void append(Portion x) {
    std::unique_lock<std::mutex> lck(mtx);
    nonfull.wait(lck, [&]{ return !(N == count); });
    assert(0 <= count && count < N);
    buffer[tail++] = x;
    tail %= N;
    ++count;
    nonempty.notify_one();
  }
  Portion remove() {
    std::unique_lock<std::mutex> lck(mtx);
    nonempty.wait(lck, [&]{ return !(0 == count); });
    assert(0 < count && count <= N);
    Portion x = buffer[head++];
    head %= N; 
    --count;
    nonfull.notify_one();
    return x;
  }
  Bounded_buffer() {
    head = 0; tail = 0; count = 0;
  }
};

C++ संस्करण को तकनीकी कारणों के अतिरिक्त म्यूटेक्स की आवश्यकता है। यह बफ़र जोड़ने और हटाने के संचालन के लिए पूर्व शर्त लागू करने के लिए दृढ़ता का उपयोग करता है।

चैनलों का उपयोग करना

इलेक्ट्रोलॉजिका कंप्यूटरों में सबसे पहले निर्माता-उपभोक्ता समाधान ने 'चैनल' का उपयोग किया। होरे परिभाषित चैनल (प्रोग्रामिंग): स्रोत और गंतव्य के स्पष्ट नामकरण का एक विकल्प एक पोर्ट का नाम देना होगा जिसके माध्यम से संचार होना है। पोर्ट नाम प्रक्रियाओं के लिए स्थानीय होंगे, और जिस तरीके से पोर्ट के जोड़े को चैनलों से जोड़ा जाना है, उसे समानांतर कमांड के प्रमुख में घोषित किया जा सकता है।[9] ब्रिन्च हैनसेन ने प्रोग्रामिंग भाषाओं जॉयस (प्रोग्रामिंग भाषा) संचार और सुपर पास्कल चैनल और संचार में चैनलों को कार्यान्वित किया। प्लान 9 ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज एलेफ (प्रोग्रामिंग लैंग्वेज), इन्फर्नो ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज लिम्बो (प्रोग्रामिंग भाषा) में चैनल हैं। निम्नलिखित C स्रोत कोड यूजर स्पेस से प्लान 9 पर संकलित है:

#include "u.h"
#include "libc.h"
#include "thread.h"

enum { STACK = 8192 };

void producer(void *v) {
  Channel *ch = v;
  for (uint i = 1; ; ++i) {
    sleep(400);
    print("p %d\n", i);
    sendul(ch, i);
  }
}
void consumer(void *v) {
  Channel *ch = v;
  for (;;) {
    uint p = recvul(ch);
    print("\t\tc %d\n", p);
    sleep(200 + nrand(600));
  }
}
void threadmain(int argc, char **argv) {
  int (*mk)(void (*fn)(void*), void *arg, uint stack);
  mk = threadcreate;
  Channel *ch = chancreate(sizeof(ulong), 1);
  mk(producer, ch, STACK);
  mk(consumer, ch, STACK);
  recvp(chancreate(sizeof(void*), 0));
  threadexitsall(0);
}

फलन का प्रवेश बिंदु थ्रेडमेनकार्य कर रहा है, फ़ंक्शन कॉल ch = chancreate(sizeof(ulong), 1) चैनल बनाता है, फ़ंक्शन कॉल करता है sendul(ch, i) चैनल और फ़ंक्शन कॉल में मान भेजता है p = recvul(ch) चैनल से मूल्य प्राप्त करता है। प्रोग्रामिंग लैंग्वेज गो (प्रोग्रामिंग लैंग्वेज) में चैनल भी हैं। एक गो उदाहरण:

package main

import (
	"fmt"
	"math/rand"
	"time"
)

var sendMsg = 0

func produceMessage() int {
	time.Sleep(400 * time.Millisecond)
	sendMsg++
	fmt.Printf("sendMsg = %v\n", sendMsg)
	return sendMsg
}
func consumeMessage(recvMsg int) {
	fmt.Printf("\t\trecvMsg = %v\n", recvMsg)
	time.Sleep(time.Duration(200+rand.Intn(600)) * time.Millisecond)
}
func main() {
	ch := make(chan int, 3)
	go func() {
		for {
			ch <- produceMessage()
		}
	}()
	for recvMsg := range ch {
		consumeMessage(recvMsg)
	}
}

गो निर्माता-उपभोक्ता समाधान उपभोक्ता के लिए मुख्य गो रूटीन का उपयोग करता है और निर्माता के लिए एक नया, अनाम गो रूटीन बनाता है। दो गो रूटीन चैनल ch से जुड़े हुए हैं। यह चैनल तीन इंट वैल्यू तक कतारबद्ध कर सकता है। कथन ch := make(chan int, 3) चैनल बनाता है, बयान ch <- produceMessage() चैनल और स्टेटमेंट में वैल्यू भेजता है recvMsg := range ch चैनल से मूल्य प्राप्त करता है।[10] स्मृति संसाधनों का आवंटन, प्रसंस्करण संसाधनों का आवंटन और संसाधनों का सिंक्रनाइज़ेशन स्वचालित रूप से प्रोग्रामिंग भाषा द्वारा किया जाता है।

सेमाफोर या मॉनिटर के बिना

लेस्ली लामपोर्ट ने एक निर्माता और एक उपभोक्ता के लिए बाध्य बफर निर्माता-उपभोक्ता समाधान प्रलेखित किया: हम मानते हैं कि b बफर अधिकतम b >= 1 संदेशों को पकड़ सकता है। हमारे समाधान में, हम k को b से अधिक निरंतर होने देते हैं, और चलो s और r पूर्णांक चर हैं जो 0 और k-1 के बीच मान मानते हैं। हम मानते हैं कि शुरू में s=r और बफर खाली है। k को b का एक बहु होने के लिए चुनकर, बफर को एक सरणी B [0: b - 1] के रूप में लागू किया जा सकता है। निर्माता बस प्रत्येक नए संदेश को B[s mod b] में डालता है, और उपभोक्ता प्रत्येक संदेश को B[r mod b] से लेता है।[11] एल्गोरिथ्म नीचे दिखाया गया है, अपरिमित k के लिए सामान्यीकृत किया गया है।

Producer:
  L:  if (s - r) mod k = b then goto L fi;
      put message in buffer;
      s := (s + 1) mod k;
      goto L;
Consumer:
  L:  if (s - r) mod k = 0 then goto L fi;
      take message from buffer;
      r := (r + 1) mod k;
      goto L;

लैमपोर्ट समाधान शेड्यूलर में प्रतीक्षा करने के अतिरिक्त थ्रेड में व्यस्त प्रतीक्षा का उपयोग करता है। यह समाधान असुविधाजनक समय पर शेड्यूलर थ्रेड स्विच के प्रभाव की उपेक्षा करता है। यदि पहले थ्रेड ने स्मृति से एक चर मूल्य पढ़ा है, शेड्यूलर दूसरे थ्रेड पर स्विच करता है जो चर मूल्य को बदलता है, और शेड्यूलर पहले थ्रेड में वापस स्विच करता है, तो पहला थ्रेड वेरिएबल के पुराने मूल्य न कि वर्तमान मूल्य का उपयोग करता है। परमाणु रीड-मोडिफाई-राइट इस समस्या को हल करते हैं। आधुनिक C++ ऑफर अटामिक मल्टी-थ्रेड प्रोग्रामिंग के लिए परमाणु चर और संचालन प्रदान करता है। एक निर्माता और एक उपभोक्ता के लिए निम्नलिखित व्यस्त प्रतीक्षा C++11 समाधान एटम रीड-मोडिफाई-राइट ऑपरेशन fetch_add और fetch_sub का उपयोग करता है।

 enum {N = 4 };
Message buffer[N];
std::atomic<unsigned> count {0};
void producer() {
  unsigned tail {0};
  for (;;) {
    Message message = produceMessage();
    while (N == count) 
      ; // busy waiting
    buffer[tail++] = message;
    tail %= N;
    count.fetch_add(1, std::memory_order_relaxed);
  }
}
void consumer() {
  unsigned head {0};
  for (;;) {
    while (0 == count) 
      ; // busy waiting
    Message message = buffer[head++];
    head %= N;
    count.fetch_sub(1, std::memory_order_relaxed);
    consumeMessage(message);
  }
}
int main() {
  std::thread t1(producer);
  std::thread t2(consumer);
  t1.join();
  t2.join();
}

परिपत्र बफर सूचकांक चर हेड और टेल थ्रेड-लोकल हैं और इसलिए मेमोरी स्थिरता के लिए प्रासंगिक नहीं हैं। चर गिनती निर्माता और उपभोक्ता थ्रेड की व्यस्त प्रतीक्षा को नियंत्रित करता है।

यह भी देखें

संदर्भ


अग्रिम पठन