निर्माता-उपभोक्ता समस्या: Difference between revisions
No edit summary |
No edit summary |
||
| Line 14: | Line 14: | ||
== दिज्क्स्ट्रा का सीमित बफर समाधान == | == दिज्क्स्ट्रा का सीमित बफर समाधान == | ||
प्रारंभिक सेमाफोर सीमित बफर समाधान [[ALGOL]] शैली में लिखा गया था। बफर N भागों या तत्वों को स्टोर कर सकता है। कतारबद्ध भागों की संख्या [[सेमाफोर (प्रोग्रामिंग)]] बफर में भरे हुए स्थानों की गणना करता है, खाली पदों की संख्या सेमाफोर बफर में खाली स्थानों की गणना करता है और सेमाफोर बफर हेरफेर बफर पुट और ऑपरेशन प्राप्त करने के लिए [[ म्युटेक्स ]] के रूप में काम करता है। यदि बफ़र भरा हुआ है, यानी खाली स्थिति की संख्या शून्य है, तो निर्माता थ्रेड P (खाली स्थिति की संख्या) ऑपरेशन में प्रतीक्षा करेगा। यदि बफ़र खाली है, यानी कतारबद्ध भागों की संख्या शून्य है, तो उपभोक्ता धागा P (कतारबद्ध भागों की संख्या) ऑपरेशन में प्रतीक्षा करेगा। V() ऑपरेशन सेमाफोर जारी करते हैं। साइड इफेक्ट के रूप में, एक थ्रेड प्रतीक्षा कतार से तैयार कतार में जा सकता है। P() ऑपरेशन सेमाफोर मान को घटाकर शून्य कर देता है। V() ऑपरेशन सेमाफोर मान को बढ़ाता है।<ref>[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html#4.3.%20The%20Bounded%20Buffer. Dijkstra; 1965; EWD123 Cooperating sequential processes, section 4.3. The Bounded Buffer.]</ref> | |||
<syntaxhighlight lang="pascal"> | <syntaxhighlight lang="pascal"> | ||
| Line 40: | Line 40: | ||
end | end | ||
</syntaxhighlight> | </syntaxhighlight> | ||
C++ 20 के अनुसार, सेमाफोर भाषा का | C++ 20 के अनुसार, सेमाफोर भाषा का भाग हैं। डीजक्स्ट्रा के समाधान को आधुनिक C++ में आसानी से लिखा जा सकता है। परिवर्तनीय बफर_मैनिपुलेशन एक म्यूटेक्स है। एक थ्रेड में प्राप्त करने और दूसरे थ्रेड में रिलीज़ करने की सेमाफोर सुविधा की आवश्यकता नहीं है। लॉक() और अनलॉक() जोड़ी के अतिरिक्त लॉक_गार्ड() कथन सी ++ आरएआईआई है। लॉक_गार्ड डिस्ट्रक्टर अपवाद के मामले में लॉक रिलीज सुनिश्चित करता है। यह समाधान एकाधिक उपभोक्ता धागे और/या एकाधिक निर्माता धागे को संभाल सकता है। | ||
<वाक्यविन्यास प्रकाश लैंग = सी ++> | <वाक्यविन्यास प्रकाश लैंग = सी ++> | ||
Revision as of 13:59, 6 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++ में आसानी से लिखा जा सकता है। परिवर्तनीय बफर_मैनिपुलेशन एक म्यूटेक्स है। एक थ्रेड में प्राप्त करने और दूसरे थ्रेड में रिलीज़ करने की सेमाफोर सुविधा की आवश्यकता नहीं है। लॉक() और अनलॉक() जोड़ी के अतिरिक्त लॉक_गार्ड() कथन सी ++ आरएआईआई है। लॉक_गार्ड डिस्ट्रक्टर अपवाद के मामले में लॉक रिलीज सुनिश्चित करता है। यह समाधान एकाधिक उपभोक्ता धागे और/या एकाधिक निर्माता धागे को संभाल सकता है।
<वाक्यविन्यास प्रकाश लैंग = सी ++>
- सम्मिलित <थ्रेड>
- सम्मिलित <म्यूटेक्स>
- सम्मिलित <सेमाफोर>
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;
मॉनिटर एक वस्तु है जिसमें चर होते हैं buffer, head, tail और count एक परिपत्र बफर का एहसास करने के लिए, स्थिति चर nonempty और nonfull तुल्यकालन और तरीकों के लिए append और remove बंधे हुए बफर तक पहुँचने के लिए। मॉनिटर ऑपरेशन प्रतीक्षा सेमाफोर ऑपरेशन पी या अधिग्रहण से मेल खाती है, सिग्नल वी या रिलीज से मेल खाता है। गोलाकार ऑपरेशन (+) को मोडुलो एन लिया जाता है। प्रस्तुत पास्कल शैली छद्म कोड एक होरे मॉनिटर दिखाता है। एक मेसा (प्रोग्रामिंग भाषा) मॉनिटर उपयोग करता है while count के अतिरिक्त if count. एक प्रोग्रामिंग भाषा C++ संस्करण है:
<वाक्यविन्यास प्रकाश लैंग = सी ++> वर्ग Bounded_buffer {
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;
}
};
सी ++ संस्करण को तकनीकी कारणों से अतिरिक्त म्यूटेक्स की आवश्यकता है। यह बफ़र जोड़ने और हटाने के संचालन के लिए पूर्व शर्त लागू करने के लिए जोर का उपयोग करता है।
चैनलों का उपयोग करना
इलेक्ट्रोलॉजिका कंप्यूटरों में सबसे पहले निर्माता-उपभोक्ता समाधान ने 'चैनल' का इस्तेमाल किया। होरे परिभाषित चैनल (प्रोग्रामिंग): स्रोत और गंतव्य के स्पष्ट नामकरण का एक विकल्प एक बंदरगाह का नाम देना होगा जिसके माध्यम से संचार होना है। पोर्ट नाम प्रक्रियाओं के लिए स्थानीय होंगे, और जिस तरीके से बंदरगाहों के जोड़े को चैनलों से जोड़ा जाना है, उसे समानांतर कमांड के प्रमुख में घोषित किया जा सकता है।[9] ब्रिन्च हैनसेन ने प्रोग्रामिंग भाषाओं जॉयस (प्रोग्रामिंग भाषा) # संचार और सुपर पास्कल # चैनल और संचार में चैनलों को कार्यान्वित किया। प्लान 9 ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज एलेफ (प्रोग्रामिंग लैंग्वेज), इन्फर्नो ऑपरेटिंग सिस्टम प्रोग्रामिंग लैंग्वेज लिम्बो (प्रोग्रामिंग भाषा) में चैनल हैं। निम्नलिखित सी स्रोत कोड यूजर स्पेस से प्लान 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);
}
कार्यक्रम का प्रवेश बिंदु कार्य कर रहा है threadmain. समारोह कॉल ch = chancreate(sizeof(ulong), 1) चैनल बनाता है, फ़ंक्शन कॉल करता है sendul(ch, i) चैनल और फ़ंक्शन कॉल में मान भेजता है p = recvul(ch) चैनल से मूल्य प्राप्त करता है। प्रोग्रामिंग लैंग्वेज गो (प्रोग्रामिंग लैंग्वेज)#Concurrency: goroutines और channel में चैनल भी हैं। एक जाओ उदाहरण:
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] स्मृति संसाधनों का आवंटन, प्रसंस्करण संसाधनों का आवंटन और संसाधनों का सिंक्रनाइज़ेशन स्वचालित रूप से प्रोग्रामिंग भाषा द्वारा किया जाता है।
सेमाफोर या मॉनिटर के बिना
लेस्ली लामपोर्ट ने एक निर्माता और एक उपभोक्ता के लिए एक बाध्य बफर निर्माता-उपभोक्ता समाधान प्रलेखित किया: हम मानते हैं कि बफर अधिकतम बी संदेशों को पकड़ सकता है, बी> = 1। हमारे समाधान में, हम के को बी से अधिक निरंतर होने देते हैं, और चलो s और r पूर्णांक चर हैं जो 0 और k-1 के बीच मान मानते हैं। हम मानते हैं कि शुरू में s=r और बफर खाली है। k को b का एक बहु होने के लिए चुनकर, बफर को एक सरणी B [0: b - 1] के रूप में लागू किया जा सकता है। निर्माता बस प्रत्येक नए संदेश को B[s mod b] में डालता है, और उपभोक्ता प्रत्येक संदेश को B[r mod b] से लेता है।[11] एल्गोरिदम नीचे दिखाया गया है, अनंत के लिए सामान्यीकृत।
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;
लैमपोर्ट समाधान शेड्यूलर में प्रतीक्षा करने के अतिरिक्त थ्रेड में व्यस्त प्रतीक्षा का उपयोग करता है। यह समाधान असुविधाजनक समय पर अनुसूचक थ्रेड स्विच के प्रभाव की उपेक्षा करता है। यदि पहले थ्रेड ने मेमोरी से वैरिएबल मान पढ़ा है, तो शेड्यूलर दूसरे थ्रेड पर स्विच करता है जो वेरिएबल मान को बदलता है, और शेड्यूलर पहले थ्रेड पर वापस स्विच करता है, फिर पहला थ्रेड वेरिएबल के पुराने मान का उपयोग करता है, वर्तमान मान का नहीं . परमाणु पढ़ें-संशोधित-लिखें | पढ़ें-संशोधित-लेखन इस समस्या को हल करता है। आधुनिक सी ++ ऑफर atomic मल्टी-थ्रेड प्रोग्रामिंग के लिए चर और संचालन। एक निर्माता और एक उपभोक्ता के लिए निम्नलिखित व्यस्त प्रतीक्षा सी ++ 11 समाधान परमाणु पठन-संशोधित-लेखन संचालन का उपयोग करता है fetch_add और fetch_sub परमाणु चर पर count.
<वाक्यविन्यास प्रकाश लैंग = सी ++> एनम {एन = 4}; संदेश बफर [एन]; एसटीडी :: परमाणु <अहस्ताक्षरित> गिनती {0}; शून्य निर्माता () {
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();
}
परिपत्र बफर सूचकांक चर head और tail थ्रेड-लोकल हैं और इसलिए मेमोरी स्थिरता के लिए प्रासंगिक नहीं हैं। चर count निर्माता और उपभोक्ता धागे की व्यस्त प्रतीक्षा को नियंत्रित करता है।
यह भी देखें
- परमाणु संचालन
- डिजाइन पैटर्न (कंप्यूटर विज्ञान)
- फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)
- पाइपलाइन (सॉफ्टवेयर)
- चैनल (प्रोग्रामिंग)
- जावा में कार्यान्वयन: जावा संदेश सेवा
संदर्भ
- ↑ Dijkstra; 2000; EWD1303 My recollections of operating system design
- ↑ Dijkstra; 1965; EWD123 Cooperating sequential processes, section 4.1. Typical Uses of the General Semaphore.
- ↑ Dijkstra; 1965; EWD123 Cooperating sequential processes, section 4.3. The Bounded Buffer.
- ↑ Dijkstra; 1972; EWD329 Information Streams Sharing a Finite Buffer
- ↑ Wirth; 1969; Letter from Niklaus Wirth, July 14, 1969 in Brinch Hansen; 2004; A programmer's story, chapter 4 Young Man in a Hurry
- ↑ Dijkstra; 1965; EWD123 Cooperating sequential processes, section 4.3. The Bounded Buffer.
- ↑ Per Brinch Hansen; 1973; Operating System Principles, 3.4.7. Event Queues
- ↑ C.A.R. Hoare; 1974; Monitors: An Operating System Structuring Concept, 4. Example: Bounded Buffer
- ↑ Hoare; 1978; Communicating Sequential Processes, 7.3 Port Names
- ↑ A tour of Go, Channels
- ↑ Lamport, Leslie; 1977; Proving the Correctness of Multiprocess Programs, The Producer/Consumer Example
अग्रिम पठन
- Mark Grand Patterns in Java, Volume 1, A Catalog of Reusable Design Patterns Illustrated with UML
- C/C++ Users Journal (Dr.Dobb's) January 2004, "A C++ Producer-Consumer Concurrency Template Library", by Ted Yuan, is a ready-to-use C++ template library. The small template library source code and examples can be found here
- Ioan Tinca, The Evolution of the Producer-Consumer Problem in Java
| General | |
|---|---|
| Process calculi | |
| Classic problems | |
