सेमाफोर (प्रोग्रामिंग)

अन्य उपयोगों के लिए, सेमाफोर देखें.

कम्प्यूटर विज्ञान में, सेमाफोर (Semaphore) एक संरक्षित (protected) वेरिएबल या एब्स्ट्रैक्ट डाटा टाइप है, जो किसी समानांतर प्रोग्रामिंग वातावरण में साझा संसाधनों, जैसे साझा मेमोरी, के अभिगम को नियंत्रित करने वाली क्लासिक विधि का गठन करता है। गणना करनेवाला सेमाफोर (Counting Semaphore) किसी एकल संसाधन का बंद/खुला फ्लैग नहीं, बल्कि उपलब्ध संसाधनों के एक समूह का काउंटर होता है। इसका आविष्कार एड्स्गर डिज्कस्ट्रा (Edsger Dijkstra) ने किया था। सेमाफोर डाइनिंग फिलोसोफेर समस्या (Dining Philisophers problems) में रेस स्थितियों (Race Conditions) को रोकने का क्लासिक समाधान हैं, हालांकि वे संसाधन गतिरोध को नहीं रोकते हैं।साँचा:category handler

परिचय

सेमफोर तक अभिगमन निम्नलिखित कार्यों के उपयोग से ही संभव है। जिन्हें एटॉमिक के रूप में चिन्हित किया गया हो उन्हें व्यवधान उत्पन्न नहीं किया जाना चाहिए (अर्थात, यदि सिस्टम ने यह निर्धारित किया हो कि अब इस कार्य को कर रहे प्रोग्राम की "बारी है", तो उसे इन निर्देशों के बीच में इसे नहीं रोकना चाहिए), इसके कारण नीचे स्पष्ट किये गए हैं।

P(Semaphore s) //Acquire Resource { wait until s > 0, then s := s-1; /* Testing and decrementing s must be atomic to avoid race conditions* / }

V(Semaphore s) //Release Resource { s := s+1; /*Must be atomic*/ }

Init (Semaphore s, Integer v) { s := v; }

ध्यान दें कि वेरिएबल s की वृद्धि को बाधित नहीं किया जाना चाहिए तथा s का मान 0 से बड़ा प्राप्त होने पर कार्य P में व्यवधान उत्पन्न नहीं किया जाना चाहिए.यह एक विशेष निर्देश, जैसे test-and-set (यदि संरचना का निर्देश-समूह इसका समर्थन करता हो), के प्रयोग द्वारा, अथवा (एकल प्रोसेसर वाले सिस्टम पर) अन्य प्रक्रियाओं को सक्रिय होने से रोकने के लिए व्यवधानों (Interrupts) को उपेक्षित करके किया जा सकता है।

एक सेमाफोर का मान संसाधन में रिक्त इकाइयों की संख्या के बराबर होता है। (यदि केवल एक ही संसाधन हो, तो 0 और 1 मानों वाले एक "बाइनरी सेमाफोर" का प्रयोग किया जाता है।) कार्य P व्यस्त-प्रतीक्षारत रहता है (अपनी बारी का उपयोग कुछ न करने के लिए करता है) या शायद तब तक सोया (Sleeps) रहता है (सिस्टम से कोई बारी न देने को कहता है), जब तक कि कोई संसाधन उपलब्ध न हो जाए और फिर तुरंत एक संसाधन पर दावा करता है।V इसका विपरीत है; प्रक्रिया द्वारा संसाधन का प्रयोग पूर्ण हो जाने पर यह केवल संसाधन उपलब्ध कराता है।Init का प्रयोग कोई भी निवेदन किये जाने से पहले सेमाफोर को केवल प्रारम्भिक मान प्रदान करने (Initialization) के लिए किया जाता है। कार्य P तथा V एटॉमिक होने चाहिए, जिसका अर्थ यह है कि उसी सेमाफोर पर कोई अन्य कार्य करने के लिए किसी भी प्रक्रिया को उन कार्यों के बीच में कभी भी रोका नहीं जाना चाहिए.

औपचारिक नामों, P और V की उत्पत्ति डच शब्दों के प्रथम अक्षरों से हुई है।V का अर्थ है verhogen, अथवा "वृद्धि".P के लिए विभिन्न व्याख्याएं दीं गईं हैं ("परीक्षण करना" के लिए proberen, "पारण (Pass)" के लिए passeer, "प्रयास" probeer तथा "पकड़ना" pakken सहित), लेकिन वस्तुत: डिज्कस्ट्रा ने लिखा है कि P से उनका आशय निर्मित-शब्द prolaag था, जो probeer te verlagen, या "प्रयास करो-और-घटाओ (try-and-decrease)" का संक्षिप्त रूप है, (एक कम अस्पष्ट और ज्यादा सटीक अनुवाद होगा "घटाने-का -प्रयास करो (try-to-decrease)".यह भ्रम इस तथ्य के कारण उत्पन्न होता है कि डच भाषा में वृद्धि (Increase) तथा कमी (Decrease) दोनों के लिए प्रयोग होने वाले शब्द V वर्ण से ही शुरू होते हैं और इन शब्दों के पूर्ण रूप का प्रयोग गैर-डच-वक्ताओं के लिए असंभव रूप से भ्रामक होगा.

प्रोग्रामिंग भाषा ALGOL 68 में, लिनक्स कर्नेल में तथा कुछ अंग्रेजी पाठ्यपुस्तकों में कार्यों, P और V को, क्रमश: डाउन तथा अप कहा जाता है। सॉफ्टवेयर इंजीनियरिंग की पद्धति में उन्हें अक्सर wait तथा signal, या acquire तथा release (जिनका प्रयोग मानक जावा लाइब्ररी में होता है), या pend तथा post कहा जाता है। मूल डच आद्याक्षरों से मिलान करने के लिए कुछ पुस्तकों में इन्हें procure तथा vacate कहा जाता है।

व्यस्त-प्रतीक्षा (busy-waiting) से बचने के लिए सेमाफोर में प्रक्रियाओं की एक सम्बद्ध कतार (queue) हो सकती है (सामान्यत: फर्स्ट-इन, फर्स्ट-आउट).यदि कोई प्रक्रिया किसी ऐसे सेमफोर पर एक P कार्य करती है, जिसका मान शून्य है, तो इस प्रक्रिया को सेमफोर की क्यू में जोड़ दिया जाता है। जब कोई अन्य प्रक्रिया V कार्य करके सेमाफोर को बढ़ाती है और क्यू में प्रक्रियाएं उपस्थित हैं, तो उनमें से एक को क्यू से हटा दिया जाता है और उसका क्रियान्वयन पुन: प्रारम्भ होता है। जब प्रक्रियाओं की प्राथमिकताएं (Priorities) भिन्न होती हैं, तो क्यू को प्राथमिकता के क्रम में रखा जा सकता है, ताकि उच्चतम प्राथमिकता वाली प्रक्रिया को क्यू से सबसे पहले लिया जाए.

अनुरूपता

माना कि 'संसाधन' सार्वजनिक प्रसाधन-गृह के शौचालय हैं तथा शौचालयों का अभिगमन चाहने वाली 'प्रक्रियाएं' या तो वे लोग हैं, जो एक कतार में खड़े होकर किसी भी शौचालय के उपलब्ध होने की प्रतीक्षा कर रहे हैं, अथवा वे लोग हैं, जो पहले से ही शौचालय का प्रयोग कर रहे हैं। शौचालय के बाहर बैठा व्यक्ति इस बात का ध्यान रखता है कि इस समय कितने शौचालय उपलब्ध हैं और इसके बाद किसे भीतर जाना चाहिए.

रिक्त शौचालयों की संख्या सेमाफोर का मान है, जो उपलब्ध रिक्त संसाधनों (शौचालयों) की संख्या बताता है। जब कोई प्रक्रिया (व्यक्ति) शौचालय का अभिगमन करना चाहता है, तो सेमाफोर (प्रभारी) उसे यह बताएगा कि उसे कतार में प्रतीक्षा करनी होगी या वह शौचालय का प्रयोग कर सकता है। यदि शौचालय रिक्त है तो उस व्यक्ति (प्रक्रिया) को अभिगम प्राप्त होता है और रिक्त शौचालयों की संख्या में से 1 कम कर दिया जाता है (P अथवा डाउन कार्य).इसका अर्थ यह हुआ कि रिक्त शौचालयों की संख्या 1 कम हो गई है। यदि रिक्त शौचालयों की संख्या 0 है, तो व्यक्ति (प्रक्रिया) को तब तक कतार में प्रतीक्षा करनी होगी, जब तक कि यह रिक्त न हो जाए (अर्थात प्रक्रिया को s>0 तक सोना पड़ेगा).एक बार जब व्यक्ति शौचालय का प्रयोग कर लेता है (प्रक्रिया किसी संसाधन के साथ कार्य पूरा कर लेती है), तो अगला व्यक्ति उसका प्रयोग कर सकता है। इसका अर्थ यह है कि रिक्त शौचालयों की संख्या में अब 1 की वृद्धि हो गई है (यह V अथवा अप कार्य को कॉल करने के ही सामान है).अब s का मान 0 से बड़ा हो गया है तथा प्रतीक्षा कर रहा व्यक्ति (सो रही प्रक्रिया) अब शौचालय (संसाधन) का अभिगमन कर सकता है।

उपलब्ध शौचालयों की मांग करने (इस बात की जांच कि क्या संसाधन रिक्त है), रिक्त शौचालयों (संसाधनों) की संख्या को अद्यतन करने तथा कतार में प्रतीक्षा करने की प्रक्रिया को किसी भी अन्य प्रक्रिया द्वारा बाधित नहीं किया जाना चाहिए.इसे एटॉमिक कार्य कहा जाता है।

यह कतार एक फर्स्ट-इन फर्स्ट-आउट क्यू है, जिसका अर्थ यह है कि कतार में सबसे पहले खड़े व्यक्ति को रिक्त शौचालय के प्रयोग का अवसर सबसे पहले मिलेगा.हालांकि यदि कतार में किसी अन्य स्थान पर खड़ा व्यक्ति शौचालय का प्रयोग तत्काल करना चाहता है (यदि किसी प्रक्रिया की प्राथमिकता अधिक है), तो कतार को व्यवस्थित किया जा सकता है।

सेमाफोर से एक से अधिक 'इकाई' की मांग करने या इसे लौटाने की क्षमता के द्वारा काउंटिंग सेमाफोर की अवधारणा का विस्तार किया जा सकता है। वस्तुत: UNIX सेमाफोर इसी प्रकार कार्य करता है। संशोधित P तथा V कार्य इस प्रकार संचालित होते हैं:

P(Semaphore s, integer howmany) { wait until s >= howmany; s:=s - howmany; /*must be atomic operation*/ }

V(Semaphore s, integer howmany) { s:=s + howmany; /*must be atomic*/ }

इस बात को समझने के लिए कि यह P के सरल संस्करण को 'howmany' बार कॉल करने से बेहतर क्यों है, निम्न समस्या पर विचार करें.हम यह मान लेते हैं कि आपके पास N संसाधनों का एक संग्रह (Pool) है, जिसे हम निश्चित आकार वाला बफर (Fixed size buffer) कहेंगे.संभवत: आप उपलब्ध बफ़र्स का हिसाब रखने के लिए एक काउंटिंग सेमाफोर का प्रयोग करना चाहेंगे, जिसे N द्वारा इनीशलाइज़ किया गया हो.जब कोई प्रक्रिया एक बफर आवंटित करना चाहती है, तो वह सेमाफोर पर P को कॉल करती है और एक बफर प्राप्त करती है। यदि कोई बफर उपलब्ध न हों, तो एक प्रक्रिया तब तक प्रतीक्षा करती है, जब तक कोई अन्य प्रक्रिया किसी बफर को मुक्त नहीं कर देती और सेमाफोर पर V को कॉल नहीं कर लेती.

यह मानें कि दो प्रक्रियाएं हैं, जो क्रमश: बफ़र्स K<N तथा L<N को इस प्रकार प्राप्त करना चाहती हैं कि K+L>N हो. इसका सरल क्रियान्वयन यह होगा कि पहली प्रक्रिया P के सरल घटाव रूपांतरण (Simple Decrementing Variant) को सेमाफोर पर K बार कॉल करेगी और यह दूसरी प्रक्रिया द्वारा P के सरल घटाव रूपांतरण को सेमाफोर पर L बार कॉल कराएगी.हालांकि, इस पद्धति के फलस्वरूप गतिरोध (Deadlock) उत्पन्न हो सकता है: कल्पना करें कि ऑपरेटिंग सिस्टम पहली प्रक्रिया को क्रियान्वित होने की अनुमति देता है। तब, जब कि पहली प्रक्रिया ने केवल Z बफ़र्स का ही नियंत्रण प्राप्त किया हो (इस प्रकार कि Z<K तथा Z+L>N), तो दूसरी प्रक्रिया को क्रियान्वयन का समय देने के लिए ऑपरेटिंग सिस्टम पहली प्रक्रिया को रोक देता है। दूसरी प्रक्रिया बफ़र्स को प्राप्त करना शुरू करती है। हालांकि, जब दूसरी प्रक्रिया (N-Z) बफ़र्स प्राप्त करती है, तो सेमाफोर 0 हो जाता है और दूसरी प्रक्रिया किसी अन्य प्रक्रिया द्वारा कुछ और बफ़र्स मुक्त किये जाने तक निलंबित हो जाती है (क्योंकि L>N-Z है).अंतत: ऑपरेटिंग सिस्टम पहली प्रक्रिया को शेष (K-Z) बफ़र्स, जिनकी इसे आवश्यकता है, की खोज आगे बढ़ाने के लिए पुन: शुरू होने की अनुमति देता है। दुर्भाग्य से, चूंकि सेमाफोर 0 है, अतः पहली प्रक्रिया इस कार्य को पूर्ण नहीं कर सकती, अत: यह भी किसी अन्य प्रक्रिया द्वारा और अधिक बफ़र्स मुक्त किये जाने की प्रतीक्षा करते हुए निलंबित हो जाती है। न तो पहली और न ही दूसरी प्रक्रिया कार्य को जारी रखने के लिए पर्याप्त बफ़र्स प्राप्त कर सकती हैं और इसलिए दोनों में से कोई भी प्रक्रिया संग्रह (Pool) को कोई बफर नहीं लौटाती.इस प्रकार, वे एक गतिरोध (Deadlock) की स्थिति में फंस जाती हैं।

सेमाफोर के संशोधित संस्करण में, पहली प्रक्रिया K बफ़र्स (या अधिक शुद्ध रूप से, सेमाफोर इकाइयों) की मांग करेगी, जो उसे एक एटॉमिक कार्य के द्वारा प्राप्त होंगी, जिसके बाद सेमाफोर में N-K इकाइयां शेष रह जाएंगी.तब दूसरी प्रक्रिया आएगी, जो सेमाफोर को N-K-L तक घटाएगी और चूंकि यह एक ऋणात्मक संख्या है, अत: प्रतीक्षा करेगी.जब पहली प्रक्रिया बफ़र्स को मुक्त करती है और सेमाफोर को बढ़ाती है, तब जैसे ही सेमाफोर 0 पर पहुंचता है, तो इसका अर्थ यह है कि संग्रह में L तत्व उपलब्ध हैं, दूसरी प्रक्रिया प्रारम्भ हो सकती है और इसके सभी बफ़र्स प्राप्त कर सकती है।

इस बात पर ध्यान दिया जाना चाहिए कि सेमाफोर की गणना (Semaphore Count) संग्रह में उपलब्ध बफ़र्स की संख्या के बराबर होना आवश्यक नहीं है।P में दो बार S>=0 शर्त को जांचना और इसके लिए प्रतीक्षा करना इस बात की गारंटी देने के लिए आवश्यक है कि सेमाफोर की प्रतीक्षा सूची में जुड़ती जाने वाली विभिन्न प्रक्रियाएं एक दूसरे के निवेदनों में बाधा उत्पन्न न करतीं: एक प्रक्रिया तब तक सेमाफोर की गणना को नहीं बदलती, जब तक कि वह क्यू में अगली प्रक्रिया न हो.वास्तविक कार्यान्वयन में यह कार्य मध्यवर्ती चरण के लिए प्रतीक्षा प्रक्रिया को यथार्थ में सक्रिय किये बिना किया जाता है।

प्रोग्रामर्स द्वारा आज प्रयोग किये जाने वाले सेमाफोर

सेमाफोर का प्रयोग आज भी उन प्रोग्रामिंग भाषाओं में प्रचलित है, जो आतंरिक रूप से सिन्क्रोनाइज़ेशन के अन्य रूपों का समर्थन नहीं करतीं.वे अनेक ऑपरेटिंग सिस्टम्स में सिन्क्रोनाइज़ेशन के प्रारम्भिक तंत्र हैं। हालांकि, प्रोग्रामिंग भाषाओं के विकास का झुकाव सिन्क्रोनाइज़ेशन के अधिक संरचित रूपों की ओर है, जैसे मॉनीटर (हालांकि ये उन्नत संरचनाएं पृष्ठभूमि में सेमाफोर का ही प्रयोग करती हैं). सेमाफर (बहु-संसाधन) गतिरोधों से निबटने की अपनी अपर्याप्तता के साथ ही एक प्रक्रिया द्वारा पहले ही लिए जा चुके सेमाफोर को दुबारा लेने और लिए जा चुके सेमाफोर को मुक्त करना भूल जाने जैसी गलतियों से भी प्रोग्रामर को नहीं बचाते.

प्रयोग के उदाहरण

चूंकि सेमाफोर के साथ एक गणना जुड़ी होती है, अत: उनका प्रयोग उस समय किया जा सकता है, जब अनेक थ्रेड्स को साथ मिलकर किसी उद्देश्य को प्राप्त करने की आवश्यकता हो.इस उदाहरण पर विचार करें:

A नामक एक थ्रेड को आगे बढ़ने से पूर्व दो डाटाबेस से सूचना प्राप्त करने की आवश्यकता है। इन डाटाबेस में अभिगमन दो पृथक थ्रेड्स B तथा C द्वारा नियंत्रित किया जाता है। इन दो थ्रेड्स में एक सन्देश-प्रक्रिया लूप है; जो भी व्यक्ति इनमें से किसी डाटाबेस का प्रयोग करना चाहता हो, वह संबंधित थ्रेड की मैसेज क्यू में एक सन्देश भेजता है। थ्रेड A सेमाफोर s को init(s,-1) द्वारा इनीशलाइज़ करता है। तब A, सेमाफोर S का एक पॉइंटर शामिल करते हुए, B तथा C दोनों को एक डाटा निवेदन भेजता है। A तब P(S) को कॉल करता है, जो रोक देता है। उस दौरान शेष दो थ्रेड्स सूचना को प्राप्त करने हेतु उनके लिए आवश्यक समय लेते हैं; जब प्रत्येक थ्रेड सूचना को प्राप्त करने का कार्य पूरा कर लेता है, तो वह भेजे गए सेमाफोर पर V(S) को कॉल करता है। दोनों थ्रेड्स के पूर्ण हो जाने के बाद ही सेमाफोर का मान धनात्मक होगा और A आगे बढ़ पाने में सक्षम होगा.इस प्रकार प्रयोग किये जाने वाले सेमाफोर को "काउंटिंग सेमाफोर" कहा जाता है।

काउंटिंग सेमाफोर के अलावा, एक "ब्लॉकिंग सेमाफोर" भी होता है। ब्लॉकिंग सेमाफोर एक ऐसा सेमाफोर होता है, जिसे 0 से इनिशलाइज़ किया जाता है। इसका प्रभाव यह है कि कोई भी ऐसा थ्रेड, जो सेमाफोर पर P कार्य करता हो, वह अवरुद्ध हो जाता है।

हार्डवेयर समर्थन

सेमाफोर के प्रयोग के लिए सामान्यत: उन कार्यों की आण्विकता (Aomicity) की गारंटी देने हेतु हार्डवेयर समर्थन की जरुरत होती है, जिन्हें इसकी आवश्यकता हो.कम्प्युटर की मशीनी भाषाएं विशिष्टत: उन निर्देशों को सम्मिलित करती हैं, जिन्हें विशेष रूप से सेमाफोर का ध्यान रखते हुए तैयार किया जाता है। ये विशेष निर्देश मेमोरी में एक पढ़ें-बदलें-लिखें (Read-Modify-Write) चक्र को पूरा करते हैं, जो न केवल व्यवधान उत्पन्न न किये जा सकने योग्य (Uninterruptible) होता है, बल्कि किसी भी अन्य प्रोसेसर या इनपुट/आउटपुट उपकरण द्वारा मेमोरी में उसी स्थान पर किये जा रहे अन्य सभी कार्यों को हटा भी देता है। विशेष निर्देश इस बात की गारंटी देते हैं कि उनका प्रयोग करके एक सेमाफोर विधि एकल, एटॉमिक कार्य में किसी सेमाफोर का परीक्षण व उसमें परिवर्तन कर सकती है।

बाइनरी सेमाफोर बनाम म्युटेक्स

एक म्यूटेक्स (Mutex) एक बाइनरी सेमाफोर होता है, जिसमें सामान्यत: स्वामित्व अथवा प्राथमिकता व्युत्क्रमण (Priority Inversion) संरक्षण जैसी अतिरिक्त विशेषताएं शामिल होती हैं। म्यूटेक्स तथा सेमाफोर में अंतर ऑपरेटिंग सिस्टम पर निर्भर होते हैं। म्यूटेक्स का प्रयोग केवल पारस्परिक अपवर्जन (Mutual Exclusion) में करना अभीष्ट है तथा बाइनरी सेमाफोर्स घटना की अधिसूचना (Event Notification) और पारस्परिक अपवर्जन, दोनों में प्रयोग के लिए बनाए गए हैं।

इन्हें भी देखें

• सिगरेट धूम्रपान करने वालों की समस्या
• भोजन करने वाले दार्शनिकों की समस्या
• पाठकों-लेखकों की समस्या
• सोने वाले नाई की समस्या
• निर्माता-उपभोक्ताओं की समस्या
• पुन: प्रवेशक म्युटेक्स, जो गणन सेमाफोर की तरह "गणना" कर सकते हैं।

सन्दर्भ

• एलन बी. डाउने के द्वारा द लिटिल बुक ऑफ सेमाफोर्स, ग्रीन टी प्रेस.

बाहरी कड़ियाँ

• ओवर सेइनपैलेन (EWD 74), जिसमें डिज्कस्ट्रा ने अवधारणा (डच में) का परिचय दिया है
• semaphore.h प्रोग्रामिंग इंटरफेस (अंतरफलक) - द ओपन ग्रूप बेस स्पेसिफिकेशंस, अंक 6, IEEE Std 1003.1
• एलन बी. डाउने के द्वारा "द लिटिल बुक ऑफ सेमाफोर्स"