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

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

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

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

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

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

  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

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

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

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

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

द्वितीय पाठक-लेखक समस्या

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

लेखक-प्राथमिकता परिदृश्य का समाधान है-

 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

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

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

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

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

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 पर पहुंच जाएगा तो पाठक पढ़ना बंद कर देगा।

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

यह भी देखें

• एबीए (ABA) समस्या
• निर्माता-उपभोक्ता समस्या
• डाइनिंग फिलॉसफर्स समस्या
• सिगरेट स्मोकर्स समस्या
• स्लीपिंग बार्बर समस्या
• पाठक-लेखक लॉक
• 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