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

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

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

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

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

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

/*

  resource.P() is equivalent to wait(resource)
  resource.V() is equivalent to signal(resource)
  rmutex.P() is equivalent to wait(rmutex)
  rmutex.V() is equivalent to signal(rmutex)

• /

writer() {

   resource.P();          //Lock the shared file for a writer

   <CRITICAL Section>
   // Writing is done

   <EXIT Section>
   resource.V();          //Release the shared file for use by other readers. Writers are allowed if there are no readers requesting it.

}

reader() {

   rmutex.P();           //Ensure that no other reader can execute the <Entry> section while you are in it
   <CRITICAL Section>
   readcount++;          //Indicate that you are a reader trying to enter the Critical Section
   if (readcount == 1)   //Checks if you are the first reader trying to enter CS
       resource.P();     //If you are the first reader, lock the resource from writers. Resource stays reserved for subsequent readers
   <EXIT CRITICAL Section>
   rmutex.V();           //Release

   // Do the Reading

   rmutex.P();           //Ensure that no other reader can execute the <Exit> section while you are in it
   <CRITICAL Section>
   readcount--;          //Indicate that you no longer need the shared resource. One fewer reader
   if (readcount == 0)   //Checks if you are the last (only) reader who is reading the shared file
       resource.V();     //If you are last reader, then you can unlock the resource. This makes it available to writers.
   <EXIT CRITICAL Section>
   rmutex.V();           //Release

} </syntaxhighlight>

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

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

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

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

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

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

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

//READER reader() { <ENTRY Section>

 readTry.P();                 //Indicate a reader is trying to enter
 rmutex.P();                  //lock entry section to avoid race condition with other readers
 readcount++;                 //report yourself as a reader
 if (readcount == 1)          //checks if you are first reader
   resource.P();              //if you are first reader, lock  the resource
 rmutex.V();                  //release entry section for other readers
 readTry.V();                 //indicate you are done trying to access the resource

<CRITICAL Section> //reading is performed

<EXIT Section>

 rmutex.P();                  //reserve exit section - avoids race condition with readers
 readcount--;                 //indicate you're leaving
 if (readcount == 0)          //checks if you are last reader leaving
   resource.V();              //if last, you must release the locked resource
 rmutex.V();                  //release exit section for other readers

}

//WRITER writer() { <ENTRY Section>

 wmutex.P();                  //reserve entry section for writers - avoids race conditions
 writecount++;                //report yourself as a writer entering
 if (writecount == 1)         //checks if you're first writer
   readTry.P();               //if you're first, then you must lock the readers out. Prevent them from trying to enter CS
 wmutex.V();                  //release entry section
 resource.P();                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource

<CRITICAL Section>

 //writing is performed
 resource.V();                //release file

<EXIT Section>

 wmutex.P();                  //reserve exit section
 writecount--;                //indicate you're leaving
 if (writecount == 0)         //checks if you're the last writer
   readTry.V();               //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
 wmutex.V();                  //release exit section

} </syntaxhighlight>

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

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

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

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

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

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

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

int readcount;                // init to 0; number of readers currently accessing resource

// all semaphores initialised to 1
semaphore resource;           // controls access (read/write) to the resource. Binary semaphore.
semaphore rmutex;             // for syncing changes to shared variable readcount
semaphore serviceQueue;       // FAIRNESS: preserves ordering of requests (signaling must be FIFO)

//READER
reader() {
<ENTRY Section>
  serviceQueue.P();           // wait in line to be serviced
  rmutex.P();                 // request exclusive access to readcount
  readcount++;                // update count of active readers
  if (readcount == 1)         // if I am the first reader
    resource.P();             // request resource access for readers (writers blocked)
  serviceQueue.V();           // let next in line be serviced
  rmutex.V();                 // release access to readcount
    
<CRITICAL Section>
//reading is performed
    
<EXIT Section>
  rmutex.P();                 // request exclusive access to readcount
  readcount--;                // update count of active readers
  if (readcount == 0)         // if there are no readers left
    resource.V();             // release resource access for all
  rmutex.V();                 // release access to readcount
}

//WRITER
writer() {
<ENTRY Section>
  serviceQueue.P();           // wait in line to be serviced
  resource.P();               // request exclusive access to resource
  serviceQueue.V();           // let next in line be serviced
    
<CRITICAL Section>
// writing is performed
    
<EXIT Section>
  resource.V();               // release resource access for next reader/writer
}

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

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

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

कृपया ध्यान दें कि यह समाधान सामान्य मामले की तुलना में सरल हो जाता है क्योंकि इसे निर्माता-उपभोक्ता समस्या समस्या के समतुल्य बनाया जाता है, और इसलिए केवल 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