पाठक-लेखक समस्या

कंप्यूटर विज्ञान में, पाठकों-लेखकों की समस्याएं समवर्ती (कंप्यूटर विज्ञान) में एक सामान्य कंप्यूटिंग समस्या का उदाहरण हैं। समस्याओं की कम से कम तीन विविधताएँ हैं, जो उन स्थितियों से निपटती हैं जिनमें निष्पादन के कई समवर्ती सूत्र (कंप्यूटर विज्ञान) एक ही समय में समान साझा संसाधन तक पहुँचने का प्रयास करते हैं।

कुछ धागे पढ़ सकते हैं और कुछ लिख सकते हैं, इस बाधा के साथ कि कोई धागा पढ़ने या लिखने के लिए साझा संसाधन तक नहीं पहुंच सकता है जबकि दूसरा धागा इसे लिखने के कार्य में है। (विशेष रूप से, हम एक से अधिक थ्रेड को एक साथ साझा संसाधन को संशोधित करने से रोकना चाहते हैं और एक ही समय में दो या अधिक पाठकों को साझा संसाधन तक पहुंचने की अनुमति देना चाहते हैं)। एक पाठक-लेखक लॉक एक डेटा संरचना है जो पाठकों-लेखकों की एक या अधिक समस्याओं को हल करती है।

मूल पाठक-लेखक समस्या को सबसे पहले कोर्टोइस एट अल द्वारा तैयार और हल किया गया था।

पहले पाठक-लेखक समस्या

मान लीजिए कि हमारे पास एक साझा मेमोरी क्षेत्र (महत्वपूर्ण खंड) है जिसमें ऊपर वर्णित बुनियादी बाधाएं हैं। आपसी बहिष्करण म्युटेक्स के पीछे साझा किए गए डेटा की रक्षा करना संभव है, जिस स्थिति में कोई भी दो धागे एक ही समय में डेटा तक नहीं पहुंच सकते हैं। हालाँकि, यह समाधान उप-इष्टतम है, क्योंकि यह संभव है कि एक पाठक R₁लॉक हो सकता है, और फिर एक अन्य पाठक आर₂पहुँच का अनुरोध करता है। आर के लिए यह मूर्खता होगी₂आर तक प्रतीक्षा करने के लिए₁अपना रीड ऑपरेशन शुरू करने से पहले किया गया था; इसके बजाय, आर₂आर के साथ संसाधन पढ़ने की अनुमति दी जानी चाहिए₁क्योंकि रीड्स डेटा को संशोधित नहीं करते हैं, इसलिए समवर्ती रीड्स सुरक्षित हैं। यह 'पहले पाठक-लेखक समस्या' की प्रेरणा है, जिसमें यह बाधा जोड़ी जाती है कि यदि शेयर वर्तमान में पढ़ने के लिए खोला जाता है तो कोई पाठक प्रतीक्षा नहीं करेगा। इसे 'पाठक-वरीयता' भी कहा जाता है, इसके समाधान के साथ: <सिंटैक्सहाइलाइट लैंग = सी लाइन = 1> सेमाफोर संसाधन = 1; सेमाफोर आरम्यूटेक्स = 1; रीडकाउंट = 0;

/*

  संसाधन। पी () प्रतीक्षा (संसाधन) के बराबर है
  संसाधन। वी () सिग्नल (संसाधन) के बराबर है
  rmutex.P () प्रतीक्षा के बराबर है (rmutex)
  rmutex.V () सिग्नल के बराबर है (rmutex)

• /

लेखक () {

   संसाधन पी (); // एक लेखक के लिए साझा की गई फ़ाइल को लॉक करें

   <गंभीर खंड>
   // लिखा गया है

   <निकास अनुभाग>
   संसाधन वी (); // अन्य पाठकों द्वारा उपयोग के लिए साझा की गई फ़ाइल को रिलीज़ करें। यदि कोई पाठक अनुरोध नहीं कर रहा है तो लेखकों को अनुमति दी जाती है।

}

पाठक () {

   rmutex.P (); //सुनिश्चित करें कि जब आप इसमें हैं तो कोई अन्य पाठक <प्रविष्टि> अनुभाग को निष्पादित नहीं कर सकता है
   <गंभीर खंड>
   रीडकाउंट ++; // इंगित करें कि आप एक पाठक हैं जो महत्वपूर्ण अनुभाग  में प्रवेश करने का प्रयास कर रहे हैं
   if (readcount == 1) // चेक करता है कि क्या आप CS में प्रवेश करने का प्रयास करने वाले पहले पाठक हैं
       संसाधन पी (); // यदि आप पहले पाठक हैं, तो लेखकों के संसाधन को लॉक कर दें। संसाधन बाद के पाठकों के लिए आरक्षित रहता है
   <एग्जिट क्रिटिकल सेक्शन>
   rmutex.V (); //मुक्त करना

   // पढ़ना करो

   rmutex.P (); //सुनिश्चित करें कि जब आप इसमें हैं तो कोई अन्य पाठक <बाहर निकलें> अनुभाग को निष्पादित नहीं कर सकता है
   <गंभीर खंड>
   रीडकाउंट--; // इंगित करें कि अब आपको साझा संसाधन की आवश्यकता नहीं है। एक कम पाठक
   अगर (रीडकाउंट == 0) // चेक करता है कि क्या आप अंतिम (केवल) पाठक हैं जो साझा फ़ाइल पढ़ रहे हैं
       संसाधन वी (); // यदि आप अंतिम पाठक हैं, तो आप संसाधन को अनलॉक कर सकते हैं। यह इसे लेखकों के लिए उपलब्ध कराता है।
   <एग्जिट क्रिटिकल सेक्शन>
   rmutex.V (); //मुक्त करना

} </वाक्यविन्यास हाइलाइट>

पाठकों/लेखकों की समस्या के इस समाधान में, यदि उपलब्ध हो तो पहले पाठक को संसाधन (साझा फ़ाइल) को लॉक करना होगा। एक बार जब फ़ाइल लेखकों से लॉक हो जाती है, तो इसे बाद के कई पाठकों द्वारा इसे फिर से लॉक किए बिना उपयोग किया जा सकता है।

क्रिटिकल सेक्शन में प्रवेश करने से पहले, प्रत्येक नए पाठक को एंट्री सेक्शन से गुजरना चाहिए। हालाँकि, एक समय में प्रवेश अनुभाग में केवल एक ही पाठक हो सकता है। यह पाठकों पर दौड़ की स्थिति से बचने के लिए किया जाता है (इस संदर्भ में, एक दौड़ की स्थिति एक ऐसी स्थिति है जिसमें दो या दो से अधिक धागे एक साथ जाग रहे हैं और महत्वपूर्ण खंड में प्रवेश करने की कोशिश कर रहे हैं; आगे की बाधा के बिना, व्यवहार गैर-नियतात्मक है। उदाहरण के लिए दो पाठक एक ही समय में रीडकाउंट बढ़ाते हैं, और दोनों संसाधन को लॉक करने का प्रयास करते हैं, जिससे एक पाठक ब्लॉक हो जाता है)। इसे पूरा करने के लिए, प्रत्येक पाठक जो <प्रविष्टी अनुभाग> में प्रवेश करता है, वह अपने लिए <प्रविष्टि अनुभाग> को तब तक लॉक कर देगा जब तक कि वे इसे पूरा नहीं कर लेते। इस बिंदु पर पाठक संसाधन को लॉक नहीं कर रहे हैं। वे केवल एंट्री सेक्शन को लॉक कर रहे हैं ताकि कोई अन्य पाठक इसमें प्रवेश न कर सके। एक बार जब पाठक प्रवेश अनुभाग को क्रियान्वित कर लेता है, तो वह म्यूटेक्स को संकेत देकर इसे अनलॉक कर देगा। इसे सिगनल देना इसके बराबर है: उपरोक्त कोड में म्यूटेक्स.वी ()। वही <निकास अनुभाग> के लिए मान्य है। एक समय में एक्ज़िट सेक्शन में एक से अधिक पाठक नहीं हो सकते हैं, इसलिए, प्रत्येक पाठक को इसका उपयोग करने से पहले अपने लिए एक्ज़िट सेक्शन का दावा और लॉक करना होगा।

एक बार जब पहला पाठक प्रवेश अनुभाग में आ जाता है, तो यह संसाधन को लॉक कर देगा। ऐसा करने से कोई भी लेखक इसे एक्सेस करने से रोकेगा। बाद के पाठक लॉक (लेखकों से) संसाधन का उपयोग कर सकते हैं। पाठक को अंत में समाप्त करने के लिए (रीडकाउंट चर द्वारा इंगित) संसाधन को अनलॉक करना होगा, इस प्रकार यह लेखकों के लिए उपलब्ध होगा।

इस समाधान में, प्रत्येक लेखक को व्यक्तिगत रूप से संसाधन का दावा करना चाहिए। इसका मतलब यह है कि पाठकों की एक धारा बाद में सभी संभावित लेखकों को बाहर कर सकती है और सेंटउन्हें खोजें। ऐसा इसलिए है, क्योंकि पहले पाठक द्वारा संसाधन को लॉक करने के बाद, कोई भी लेखक इसे रिलीज़ होने से पहले लॉक नहीं कर सकता है। और यह केवल अंतिम पाठक द्वारा जारी किया जाएगा। इसलिए, यह समाधान निष्पक्षता को संतुष्ट नहीं करता है।

दूसरा पाठक–लेखक समस्या

पहला समाधान उप इष्टतम है, क्योंकि यह संभव है कि एक पाठक आर₁लॉक हो सकता है, एक लेखक डब्ल्यू लॉक की प्रतीक्षा कर रहा होगा, और फिर एक पाठक आर₂पहुँच का अनुरोध करता है। आर के लिए यह अनुचित होगा₂डब्ल्यू के आगे, तुरंत कूदने के लिए; यदि ऐसा अक्सर होता है, तो डब्ल्यू भुखमरी का संसाधन करेगा। इसके बजाय, डब्ल्यू को जल्द से जल्द शुरू करना चाहिए। यह 'दूसरी पाठक-लेखक समस्या' के लिए प्रेरणा है, जिसमें यह बाधा जोड़ी जाती है कि कोई भी लेखक, एक बार कतार में जुड़ जाने के बाद, बिल्कुल आवश्यक से अधिक समय तक प्रतीक्षा नहीं करेगा। इसे 'लेखक-वरीयता' भी कहते हैं।

लेखकों-वरीयता परिदृश्य का समाधान है: <सिंटैक्सहाइलाइट लैंग = सी लाइन = 1> इंट रीडकाउंट, राइटकाउंट; //(प्रारंभिक मान = 0) सेमाफोर rmutex, wmutex, readTry, संसाधन; //(प्रारंभिक मान = 1)

// पाठक पाठक () { <प्रविष्टि अनुभाग>

 रीडट्री। पी (); // इंगित करें कि एक पाठक प्रवेश करने का प्रयास कर रहा है
 rmutex.P (); // अन्य पाठकों के साथ दौड़ की स्थिति से बचने के लिए प्रवेश अनुभाग को लॉक करें
 रीडकाउंट ++; // एक पाठक के रूप में खुद को रिपोर्ट करें
 if (readcount == 1) // चेक करता है कि क्या आप पहले पाठक हैं
   संसाधन पी (); // यदि आप पहले पाठक हैं, तो संसाधन को लॉक कर दें
 rmutex.V (); // अन्य पाठकों के लिए प्रवेश अनुभाग जारी करें
 readTry.V (); // इंगित करें कि आप संसाधन तक पहुँचने का प्रयास कर रहे हैं

<गंभीर खंड> // पठन किया जाता है

<निकास अनुभाग>

 rmutex.P (); // रिजर्व एग्जिट सेक्शन - पाठकों के साथ दौड़ की स्थिति से बचा जाता है
 रीडकाउंट--; // इंगित करें कि आप जा रहे हैं
 अगर (रीडकाउंट == 0) // चेक करता है कि क्या आप अंतिम पाठक जा रहे हैं
   संसाधन वी (); // यदि अंतिम हो, तो आपको लॉक किए गए संसाधन को रिलीज़ करना होगा
 rmutex.V (); // अन्य पाठकों के लिए निकास खंड जारी करें

}

// लेखक लेखक () { <प्रविष्टि अनुभाग>

 wmutex.पी (); // लेखकों के लिए आरक्षित प्रविष्टि अनुभाग - दौड़ की स्थिति से बचा जाता है
 राइटकाउंट ++; // प्रवेश करने वाले लेखक के रूप में खुद को रिपोर्ट करें
 अगर (राइटकाउंट == 1) // चेक करता है कि क्या आप पहले लेखक हैं
   रीडट्री। पी (); // यदि आप पहले हैं, तो आपको पाठकों को लॉक करना होगा। उन्हें सीएस में प्रवेश करने की कोशिश करने से रोकें
 wmutex.V (); // रिलीज़ एंट्री सेक्शन
 संसाधन पी (); // अपने लिए संसाधन आरक्षित करें - अन्य लेखकों को साझा संसाधन को एक साथ संपादित करने से रोकता है

<गंभीर खंड>

 // लेखन किया जाता है
 संसाधन वी (); // रिलीज फ़ाइल

<निकास अनुभाग>

 wmutex.पी (); // रिजर्व एग्जिट सेक्शन
 राइटकाउंट--; // इंगित करें कि आप जा रहे हैं
 अगर (राइटकाउंट == 0) // चेक करता है कि क्या आप आखिरी लेखक हैं
   readTry.V (); // यदि आप अंतिम लेखक हैं, तो आपको पाठकों को अनलॉक करना होगा। उन्हें पढ़ने के लिए सीएस में प्रवेश करने की कोशिश करने की अनुमति देता है
 wmutex.V (); // रिलीज़ एग्जिट सेक्शन

} </वाक्यविन्यास हाइलाइट>

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

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

संसाधन सेमाफोर को लेखक और पाठक दोनों द्वारा उनके प्रवेश अनुभाग में लॉक किया जा सकता है। वे रीडट्री सेमाफोर को पहली बार लॉक करने के बाद ही ऐसा करने में सक्षम होते हैं, जो एक समय में उनमें से केवल एक के द्वारा ही किया जा सकता है।

जैसे ही वर्तमान पाठक पढ़ना समाप्त कर लेगा और भविष्य के सभी पाठकों को बाहर कर देगा, तब यह संसाधन पर नियंत्रण कर लेगा। बाद के सभी पाठक रीडट्री सेमाफोर पर लटके रहेंगे और लेखकों के संसाधन समाप्त होने और गेट खोलने की प्रतीक्षा करेंगेपठन-पाठन जारी करना।

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

तीसरा पाठक–लेखक समस्या

वास्तव में, दोनों समस्या कथनों द्वारा निहित समाधान भुखमरी का कारण बन सकते हैं - पहला कतार में लेखकों को भूखा रख सकता है, और दूसरा पाठकों को भूखा रख सकता है। इसलिए, तीसरी पाठक-लेखक समस्या कभी-कभी प्रस्तावित की जाती है, जो बाधा को जोड़ती है कि 'किसी भी धागे को भूखा नहीं रहने दिया जाएगा'; यानी, साझा किए गए डेटा पर लॉक प्राप्त करने का ऑपरेशन हमेशा सीमित समय में समाप्त हो जाएगा। पाठकों और लेखकों दोनों के लिए निष्पक्षता वाला समाधान इस प्रकार हो सकता है:

<सिंटैक्सहाइलाइट लैंग = सी लाइन = 1> इंट रीडकाउंट; // init से 0; वर्तमान में संसाधन तक पहुँचने वाले पाठकों की संख्या

// सभी सेमाफोर 1 से शुरू होते हैं सेमाफोर संसाधन; // संसाधन तक पहुंच (पढ़ने/लिखने) को नियंत्रित करता है। बाइनरी सेमाफोर। सेमाफोर रम्यूटेक्स; // साझा चर रीडकाउंट में परिवर्तनों को समन्वयित करने के लिए सेमाफोर सर्विस क्यू; // निष्पक्षता: अनुरोधों के क्रम को बरकरार रखता है (संकेत फीफो होना चाहिए)

// पाठक पाठक () { <प्रविष्टि अनुभाग>

 सर्विस क्यू। पी (); // सेवित होने के लिए लाइन में प्रतीक्षा करें
 rmutex.P (); // रीडकाउंट के लिए विशेष पहुंच का अनुरोध करें
 रीडकाउंट ++; // सक्रिय पाठकों की अद्यतन संख्या
 if (readcount == 1) // अगर मैं पहला पाठक हूं
   संसाधन पी (); // पाठकों के लिए संसाधन एक्सेस का अनुरोध करें (लेखक अवरोधित हैं)
 सर्विस क्यू। वी (); // अगली पंक्ति में सर्विस होने दें
 rmutex.V (); // रीडकाउंट तक पहुंच जारी करें
   

<गंभीर खंड> // पठन किया जाता है

<निकास अनुभाग>

 rmutex.P (); // रीडकाउंट के लिए विशेष पहुंच का अनुरोध करें
 रीडकाउंट--; // सक्रिय पाठकों की अद्यतन संख्या
 if (readcount == 0) // यदि कोई पाठक नहीं बचा है
   संसाधन वी (); // सभी के लिए संसाधन एक्सेस जारी करें
 rmutex.V (); // रीडकाउंट तक पहुंच जारी करें

}

// लेखक लेखक () { <प्रविष्टि अनुभाग>

 सर्विस क्यू। पी (); // सेवित होने के लिए लाइन में प्रतीक्षा करें
 संसाधन पी (); // संसाधन के लिए विशेष पहुंच का अनुरोध करें
 सर्विस क्यू। वी (); // अगली पंक्ति में सर्विस होने दें
   

<गंभीर खंड> // लेखन किया जाता है

<निकास अनुभाग>

 संसाधन वी (); // अगले पाठक/लेखक के लिए संसाधन एक्सेस जारी करें

} </वाक्यविन्यास हाइलाइट>

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

सबसे सरल पाठक लेखक समस्या

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

कृपया ध्यान दें कि यह समाधान सामान्य मामले की तुलना में सरल हो जाता है क्योंकि इसे निर्माता-उपभोक्ता समस्या समस्या के समतुल्य बनाया जाता है, और इसलिए केवल N पाठकों को समानांतर में प्रवेश करने की अनुमति है, N बफर का आकार होना।

पाठक

do {
    wait(read)
    ............
    reading data
    ............
    signal(write)
} while (TRUE);

लेखक

do {
    wait(write)
    .............
    writing data
    .............
    signal(read)
} while (TRUE);

एल्गोरिथम

1. रीड सेमाफोर के कारण पाठक लेखक के पीछे भागेगा।
2. राइटर लिखना बंद कर देगा जब राइट सेमाफोर 0 पर पहुंच जाएगा।
3. जब रीड सेमाफोर 0 पर पहुंच जाएगा तो पाठक पढ़ना बंद कर देगा।

राइटर में राइट सेमाफोर का मान सेमाफोर को पढ़ने के लिए दिया जाता है और रीडर में लूप के पूरा होने पर लिखने के लिए रीड का मान दिया जाता है।

यह भी देखें

• एबीए समस्या
• निर्माता-उपभोक्ता समस्या
• भोजन दार्शनिकों की समस्या
• सिगरेट पीने वालों की समस्या
• नींद नाई की समस्या
• पाठक-लेखक ताला
• seqlock
• पढ़ें-कॉपी-अपडेट

संदर्भ

• Morris JM (1979). A starvation-free solution to the mutual exclusion problem. Inf Process Lett 8:76–80
• Fair Solution to the Reader-Writer-Problem with Semaphores only. H. Ballhausen, 2003 arXiv:cs/0303005
• Faster Fair Solution for the Reader–Writer Problem. V. Popov, O. Mazonka 2013 arXiv:1309.4507

बाहरी संबंध

• Algorithmic description of the third readers–writers problem