Cigarette smokers problem
सिगरेट पीने वालों की समस्या कंप्यूटर विज्ञान में एक समवर्ती समस्या है, जिसे मूल रूप से 1971 में सुहास पाटिल द्वारा वर्णित किया गया था। इस समस्या की आलोचना "ऐसे प्रतिबंधों के लिए की गई है जिन्हें व्यावहारिक विचारों द्वारा उचित नहीं ठहराया जा सकता है।" समस्या विवरण पाटिल की समस्या में एक "काफी मनमाना" प्रतिबंध शामिल है कि सामग्री की आपूर्ति करने वाली प्रक्रिया को बदला नहीं जा सकता है और किसी भी सशर्त कथन का उपयोग नहीं किया जा सकता है। मान लीजिए कि एक सिगरेट बनाने और धूम्रपान करने के लिए तीन सामग्रियों की आवश्यकता होती हैः तंबाकू, कागज और माचिस। एक मेज के चारों ओर तीन धूम्रपान करने वाले होते हैं, जिनमें से प्रत्येक में तीन अवयवों में से एक की अनंत आपूर्ति होती है-एक धूम्रपान करने वाले के पास तंबाकू की अनंत आपूर्ति होती है, दूसरे के पास कागज होता है, और तीसरे के पास माचिस होती है। एक धूम्रपान न करने वाला एजेंट भी होता है जो धूम्रपान करने वालों को मनमाने ढंग से (गैर-निर्धारित रूप से) मेज पर रखने के लिए दो आपूर्ति का चयन करके अपनी सिगरेट बनाने में सक्षम बनाता है। जिस धूम्रपान करने वाले के पास तीसरी आपूर्ति है, उसे मेज से दो वस्तुओं को निकालना चाहिए, उनका उपयोग करके (अपनी आपूर्ति के साथ) एक सिगरेट बनाना चाहिए, जिसे वे थोड़ी देर के लिए धूम्रपान करते हैं। एक बार जब धूम्रपान करने वाला अपनी सिगरेट खत्म कर लेता है, तो एजेंट मेज पर दो नई यादृच्छिक वस्तुओं को रखता है। यह प्रक्रिया हमेशा जारी रहती है। मेज पर वस्तुओं का प्रतिनिधित्व करने के लिए तीन सेमाफोर का उपयोग किया जाता है; एजेंट यह संकेत देने के लिए उपयुक्त सेमाफोर को बढ़ाता है कि एक वस्तु को मेज पर रखा गया है, और धूम्रपान करने वाले वस्तुओं को हटाते समय सेमाफोर को कम करते हैं। इसके अलावा, प्रत्येक धूम्रपान करने वाले के पास एक संबंधित सेमाफोर होता है जिसका उपयोग वे एजेंट को संकेत देने के लिए करते हैं कि विशेष धूम्रपान करने वाले ने धूम्रपान किया है; एजेंट के पास एक प्रक्रिया होती है जो प्रत्येक धूम्रपान करने वाले के सेमाफोर पर प्रतीक्षा करती है ताकि एजेंट को पता चल सके कि वह नई वस्तुओं को मेज पर रख सकता है। तंबाकू की आपूर्ति करने वाले धूम्रपान करने वाले का एक सरल छद्म कोड कार्यान्वयन निम्नलिखित जैसा दिख सकता हैः डेफ टोबैको _ स्मोकर (): दोहराएँः paper.wait () matches.wait () स्मोक () tobacco_smoker_done.signal () हालाँकि, इससे गतिरोध पैदा हो सकता है; यदि एजेंट मेज पर कागज और तंबाकू रखता है, तो तंबाकू के साथ धूम्रपान करने वाला कागज को हटा सकता है और माचिस वाला धूम्रपान करने वाला तंबाकू ले सकता है, जिससे दोनों अपनी सिगरेट बनाने में असमर्थ हो जाते हैं। समाधान अतिरिक्त प्रक्रियाओं और सेमाफोर को परिभाषित करना है जो एजेंट को संशोधित किए बिना गतिरोध को रोकते हैं। आलोचक पाटिल ने सिगरेट पीने वालों की समस्या पर निम्नलिखित प्रतिबंध लगाएः एजेंट कोड को संशोधित नहीं किया जा सकता है। समाधान को सशर्त बयानों का उपयोग करने की अनुमति नहीं है। पाटिल ने पेट्री जाल के संदर्भ में एक प्रमाण का उपयोग यह दावा करने के लिए किया कि एडस्गर डिजक्स्ट्रा के सेमाफोर आदिम का उपयोग करके सिगरेट पीने वालों की समस्या का समाधान असंभव है, और यह सुझाव देने के लिए कि एक अधिक शक्तिशाली आदिम आवश्यक है। हालांकि, डेविड पार्नास ने प्रदर्शित किया कि यदि सेमाफोर की सरणी का उपयोग किया जाता है तो पाटिल का प्रमाण अपर्याप्त है, जो एक ऐसा समाधान प्रदान करता है जो सहायक प्रक्रियाओं का उपयोग करता है जो आगे बढ़ने के लिए उपयुक्त धूम्रपान करने वाले को संकेत देने के लिए अंकगणितीय करते हैं। एलन बी. डाउनी के अनुसार, पहला प्रतिबंध समझ में आता है, क्योंकि यदि एजेंट एक ऑपरेटिंग सिस्टम का प्रतिनिधित्व करता है, तो हर बार एक नया आवेदन आने पर इसे संशोधित करना अनुचित या असंभव होगा। हालाँकि, परनास का तर्क है कि दूसरा प्रतिबंध अनुचित हैः पाटिल द्वारा बताई गई सीमाएँ उनके आदिम की सीमाएँ हैं, लेकिन वे डिज्क्स्ट्रा द्वारा वर्णित आदिम पर सीमाएँ नहीं हैं। हालाँकि, यह महत्वपूर्ण है कि इस तरह की जाँच (डिज्क्स्ट्रा प्रिमिटिव्स की) कृत्रिम प्रतिबंधों के तहत इन प्रिमिटिव्स की शक्ति की जाँच न करे। कृत्रिम से हमारा मतलब उन प्रतिबंधों से है जिन्हें व्यावहारिक विचारों द्वारा उचित नहीं ठहराया जा सकता है। इस लेखक की राय में, सशर्त या सेमाफोर सरणी को प्रतिबंधित करने वाले प्रतिबंध कृत्रिम हैं। भोजन दार्शनिकों की समस्या पाठकों-लेखकों की समस्या नींद नाई की समस्या संदर्भ विरोधाभास समरूपता (कंप्यूटर विज्ञान) उदाहरण के साथ लेख छद्म कोड