सिगरेट पीने वालों की समस्या

This article is about the computer science problem. For problems that may affect cigarette smokers, see Health effects of tobacco.

सिगरेट धूम्रपान करने वालों की समस्या कंप्यूटर विज्ञान में एक समवर्ती कंप्यूटिंग समस्या है, जिसे मूल रूप से 1971 में सुहास पाटिल द्वारा वर्णित किया गया था। इस समस्या की उन प्रतिबंधों के लिए आलोचना की गई है जिन्हें व्यावहारिक कारणों से उचित नहीं ठहराया जा सकता है।

समस्या विवरण

पाटिल की समस्या में काफी मनमानी भी शामिल हैप्रतिबंध है कि सामग्री की आपूर्ति करने वाली प्रक्रिया को बदला नहीं जा सकता है और किसी सशर्त बयान का उपयोग नहीं किया जा सकता है। मान लें कि एक सिगरेट को बनाने और धूम्रपान करने के लिए तीन सामग्रियों की आवश्यकता होती है: तम्बाकू, कागज और माचिस। एक मेज के चारों ओर तीन धूम्रपान करने वाले हैं, जिनमें से प्रत्येक के पास तीन सामग्रियों में से एक की अनंत आपूर्ति है - एक धूम्रपान करने वाले के पास तम्बाकू की अनंत आपूर्ति है, दूसरे के पास कागज है, और तीसरे के पास माचिस है।

एक गैर-धूम्रपान एजेंट भी है जो धूम्रपान करने वालों को मनमाने ढंग से (गैर-नियतात्मक एल्गोरिदम | गैर-निर्धारिती) टेबल पर रखने के लिए आपूर्ति में से दो का चयन करके अपनी सिगरेट बनाने में सक्षम बनाता है। जिस धूम्रपान करने वाले के पास तीसरी आपूर्ति है, उसे सिगरेट बनाने के लिए (अपनी खुद की आपूर्ति के साथ) मेज से दो वस्तुओं को हटा देना चाहिए, जिसे वे थोड़ी देर के लिए धूम्रपान करते हैं। एक बार जब धूम्रपान करने वाला अपनी सिगरेट समाप्त कर लेता है, तो एजेंट मेज पर दो नई यादृच्छिक वस्तुएँ रखता है। यह प्रक्रिया सदा चलती रहती है।

मेज पर वस्तुओं का प्रतिनिधित्व करने के लिए तीन सेमाफोर (प्रोग्रामिंग) का उपयोग किया जाता है; एजेंट उपयुक्त सेमाफोर को यह संकेत देने के लिए बढ़ाता है कि एक आइटम को टेबल पर रखा गया है, और धूम्रपान करने वाले आइटम को हटाते समय सेमाफोर को कम कर देते हैं। इसके अलावा, प्रत्येक धूम्रपान करने वाले के पास एक संबद्ध सेमाफोर होता है जिसका उपयोग वे एजेंट को संकेत देने के लिए करते हैं कि विशेष धूम्रपान करने वाला धूम्रपान कर चुका है; एजेंट के पास एक प्रक्रिया होती है जो एजेंट को यह बताने के लिए प्रत्येक धूम्रपान करने वाले के सेमाफोर पर प्रतीक्षा करती है कि वह टेबल पर नए आइटम रख सकता है।

धूम्रपान करने वाले, जिसके पास तंबाकू की आपूर्ति है, का एक सरल स्यूडोकोड कार्यान्वयन निम्नलिखित जैसा दिखाई दे सकता है:

def tobacco_smoker():
    repeat:
        paper.wait()
        matches.wait()
        smoke()
        tobacco_smoker_done.signal()

हालाँकि, इससे गतिरोध हो सकता है; यदि एजेंट मेज पर कागज और तम्बाकू रखता है, तम्बाकू के साथ धूम्रपान करने वाला कागज को हटा सकता है और माचिस के साथ धूम्रपान करने वाला तम्बाकू ले सकता है, जिससे दोनों अपनी सिगरेट बनाने में असमर्थ हो जाते हैं। समाधान अतिरिक्त प्रक्रियाओं और सेमाफोर को परिभाषित करना है जो एजेंट को संशोधित किए बिना डेडलॉक को रोकते हैं।

आलोचना

पाटिल ने सिगरेट पीने वालों की समस्या पर निम्नलिखित प्रतिबंध लगाए:

1. एजेंट कोड बदला नहीं जा सकता।
2. समाधान को सशर्त बयानों का उपयोग करने की अनुमति नहीं है।

पाटिल ने पेट्री नेट के संदर्भ में एक सबूत का इस्तेमाल किया, यह दावा करने के लिए कि सिगरेट धूम्रपान करने वालों की समस्या का समाधान एडवर्ड डिजस्ट्रा के सेमाफोर आदिम का उपयोग करना असंभव है, और यह सुझाव देने के लिए कि एक अधिक शक्तिशाली आदिम आवश्यक है।हालांकि, डेविड पारनास ने प्रदर्शित किया कि पाटिल का प्रमाण अपर्याप्त है यदि सेमाफोर के सरणियों का उपयोग किया जाता है, एक समाधान की पेशकश करता है जो सहायक प्रक्रियाओं का उपयोग करता है जो उपयुक्त धूम्रपान करने वाले को आगे बढ़ने के लिए संकेत देने के लिए अंकगणित करता है।

एलन बी डाउनी के अनुसार, पहला प्रतिबंध समझ में आता है, क्योंकि यदि एजेंट एक ऑपरेटिंग सिस्टम का प्रतिनिधित्व करता है, तो हर बार एक नया एप्लिकेशन आने पर इसे संशोधित करना अनुचित या असंभव होगा। हालाँकि, पारनास का तर्क है कि दूसरा प्रतिबंध अनुचित है:

<ब्लॉककोट>पाटिल द्वारा बताई गई सीमाएँ उनके आदिम की सीमाएँ हैं, लेकिन वे दिज्क्स्ट्रा द्वारा वर्णित आदिम पर सीमाएँ नहीं हैं। … हालांकि, यह महत्वपूर्ण है कि इस तरह की जांच [दिज्क्स्त्र आदिमों की] कृत्रिम प्रतिबंधों के तहत इन आदिमों की शक्ति की जांच न करें। कृत्रिम से हमारा अभिप्राय उन प्रतिबंधों से है जिन्हें व्यावहारिक दृष्टि से उचित नहीं ठहराया जा सकता। इस लेखक की राय में, सशर्त या सेमाफोर सरणियों को प्रतिबंधित करने वाले प्रतिबंध कृत्रिम हैं।</ब्लॉककोट>

यह भी देखें

• भोजन दार्शनिकों की समस्या
• पाठकों-लेखकों की समस्या
• सोने वाले नाइयों की समस्या