IPC, semaphores और bounded buffers
लक्ष्य और मान्यताएँ
Message passing और shared memory में चुनाव करें; communication को synchronization से अलग रखें; semaphore ordering और bounded buffer trace करें। पूर्वज्ञान: प्रकाशित races/critical-sections पाठ। Pseudocode sequential consistency और atomic semaphore operations मानता है। Threads अपना statement order रखते हैं; fair scheduler में enabled operations अंततः पूरे होते हैं। यह reasoning model है, unsynchronized C/C++ या हर वास्तविक implementation की guarantee नहीं।
1. जानकारी साझा करने के दो तरीके
दो cooks सोचें। लिखित order एक से दूसरे को देना message passing जैसा है: send/receive channel से जानकारी पहुँचाते हैं। साझा board पर लिखना shared memory जैसा है: दोनों एक region देखते हैं। Board अधूरा update पढ़ लेने से स्वयं नहीं रोकता। इसी तरह shared memory communication देती है, races अपने-आप नहीं रोकती।
Message passing का contract भी चाहिए। क्या send receiver के ready होने तक block करेगा या message enqueue करेगा? Queue bounded है? Message boundaries बचती हैं? Byte-stream pipe और message queue समान नहीं हैं। Empty channel पर blocking receive data की प्रतीक्षा करती है, केवल CPU की नहीं। अलग senders के बीच बिना guarantee total order न मानें।
यहाँ pipe का ठोस model finite FIFO byte stream है, एक reader और एक writer के साथ। Bytes stream order में पढ़े जाते हैं; read माँगी संख्या से कम bytes लौटा सकती है। सभी write endpoints बंद होने और buffered data खत्म होने पर EOF मिलता है। Open writer वाले empty pipe को EOF न मानें। Full pipe blocking writer को रोक सकता है। इसलिए unused endpoints बंद करना महत्वपूर्ण है; यह पूरा API manual नहीं है।
2. Semaphore अनुमति गिनता है
Nonnegative-token abstraction लें। wait(S), जिसे P/down भी कहते हैं, token उपलब्ध हो तो atomically एक token लेता है; वरना caller acquire कर पाने तक block होता है। signal(S), यानी V/up/post, token जोड़ता या waiter को देता है। Test और decrement को असुरक्षित अलग operations में न बाँटें। कुछ implementations waiting threads के लिए negative counters रखती हैं; उसे इस nonnegative model में न मिलाएँ।
1 से initialized semaphore सही उपयोग पर one-at-a-time access दे सकता है। k से initialized counting semaphore k permits बताता है। Mutex में आमतौर पर ownership होती है: lock लेने वाला thread ही unlock करता है। Semaphore को दूसरा thread signal कर सकता है, इसलिए event ordering में उपयोगी है। अतिरिक्त assumptions के बिना semaphore/lock FIFO admission या starvation freedom की guarantee नहीं देता।
हल किया trace: S=2। A और B एक-एक wait पूरा करते हैं; free tokens 0। C का wait block होता है। A एक signal करे तो C released permit लेकर आगे चल सकता है। अधिकतम दो unreturned permits ही held हैं। C का इंतजार नया तीसरा permit नहीं बनाता।
3. A को B से पहले कराना
done=0 रखें। Producer: A; signal(done)। Consumer: wait(done); B। Token के बिना B अपने wait से आगे नहीं जा सकता, और producer A के बाद ही token देता है। Signal पहले हो जाए तो token बचा रहता है और consumer बाद में ले सकता है। यह bare condition-variable notification से अलग है, जो semaphore token की तरह जमा नहीं रहती।
done=1 से B, A के पहले चल सकता है। A से पहले signal कर देने से भी ordering टूटती है। अनुमानित sleep duration synchronization नहीं: उससे A पूरा होने का प्रमाण नहीं मिलता।
4. Bounded buffer: slots गिनें, structure सुरक्षित रखें
Capacity N>0 पर empty=N, full=0, mutex=1 रखें। Queue शुरू में खाली है। Producer:
wait(empty); wait(mutex); एक item insert; signal(mutex); signal(full)।
Consumer:
wait(full); wait(mutex); एक item remove; signal(mutex); signal(empty)।
empty capacity reserve करता है; full item reserve करता है; mutex queue indices और storage updates बचाता है। तीनों का काम अलग है। Capacity/item के लिए wait, mutex लेने से पहले होता है। इसलिए blocked participant queue lock रखकर दूसरे को progress से नहीं रोकता।
हल किया boundary trace: capacity 2 पर दो productions पूरे हुए और consumption नहीं हुआ। Queue में 2 items, empty=0, full=2। तीसरा producer mutex लेने से पहले empty पर block होता है। Consumer full लेता है, queue lock करके item हटाता है, unlock करके empty signal करता है। अब तीसरे producer को capacity मिल सकती है। जब कोई operation बीच में न हो, empty+full=N। बीच में reservations के कारण योग छोटा हो सकता है: wait(empty) के बाद और signal(full) से पहले slot reserve है पर full item के रूप में advertise नहीं हुआ। Boundary equation को हर instruction पर लागू न करें।
5. गलत क्रम से deadlock
Capacity 1 का buffer भरा है। गलत producer पहले mutex लेता है, फिर उसी को पकड़े empty=0 पर wait करता है। Consumer wait(full) से item reserve कर सकता है, पर mutex पर block होता है। वह item हटा या empty signal नहीं कर पाता। दोनों उस progress की प्रतीक्षा करते हैं जो दूसरा नहीं कर सकता। इसलिए हर wait को mutex में घेर देना सुरक्षित नहीं।
परीक्षा checklist
Initial values, atomic operations, blocking rules और capacity लिखें। Permits तथा physical items अलग trace करें। Correctness कहने से पहले blocked state खोजें। Shared memory को race freedom, empty channel को EOF, binary semaphore को ownership-enforcing mutex और signal को तुरंत CPU dispatch न मानें।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
IP01. दो processes common writable region map करते हैं। केवल mapping से कौन सी property मिलती है?
A. सभी compound updates atomic होते हैं B. दोनों shared region access कर सकते हैं C. Deadlock असंभव होता है D. Reads हमेशा पूरा record बनने तक रुकती हैं
उत्तर: B
A: Mapping compound updates atomic नहीं करती।
B: Shared access communication देता है; coordination के लिए protocol चाहिए।
C: Synchronization choices फिर भी deadlock कर सकती हैं।
D: Record पूरा होने की पहचान के लिए protocol चाहिए।
IP02. Nonnegative-token model में S=2। A,B एक-एक wait पूरा करते हैं; signal नहीं हुआ। अब C wait करता है। क्या होगा?
A. C तीसरा permit लेता है B. Permit उपलब्ध होने तक C block होता है C. C, S को 2 करता है D. B को terminate कर दिया जाता है
उत्तर: B
A: केवल दो permits थे।
B: A,B ने दोनों लिए; C release की प्रतीक्षा करेगा।
C: wait initial capacity reset नहीं करता।
D: Semaphore दूसरे holder को terminate नहीं करता।
IP03. Producer A; signal(S) करता है। Consumer wait(S); B करता है। केवल producer एक signal करता है। Token model में A पहले सुनिश्चित करने हेतु initial S क्या हो?
A. 0 B. 1 C. 2 D. कोई भी nonnegative value
उत्तर: A
A: Initial token नहीं; B को A के बाद signal चाहिए।
B: Initial token से B पहले चल सकता है।
C: दो initial tokens भी B को पहले चलने देते हैं।
D: Initial count ordering बदलता है।
IP04. Capacity 4 का empty buffer standard empty/full/mutex protocol लेता है। इसी क्रम में initial values क्या हैं?
A. 0,4,1 B. 4,0,1 C. 4,4,0 D. 1,0,4
उत्तर: B
A: यह full buffer के counts हैं।
B: चार free slots, शून्य items और एक mutex permit है।
C: Nonexistent items advertise करता है और queue access रोकता है।
D: Capacity और mutex counts उलटे हैं।
IP05. Capacity-1 buffer full है। Producer mutex लेकर बिना छोड़े empty=0 पर wait करता है। Consumer को item हटाने से पहले mutex चाहिए। क्या संभव है?
A. Producer-consumer deadlock B. तुरंत insertion की guarantee C. दो simultaneous removals D. Mutex अपने-आप 2 होता है
उत्तर: A
A: Producer को slot चाहिए; mutex पकड़े होने से consumer उसे खाली नहीं कर सकता।
B: Slot नहीं और removal आगे नहीं बढ़ता।
C: Mutex जरूरी removal रोक रहा है; items duplicate नहीं होते।
D: Waiting mutex permits नहीं बनाती।
IP06. Finite FIFO byte-stream pipe में buffered bytes नहीं हैं, पर एक write endpoint खुला है। Blocking model में अभी नया data न आए तो सामान्य read क्या करेगी?
A. केवल empty होने से EOF B. Data या closure condition की प्रतीक्षा C. एक zero byte बनाना D. Stream order उलटना
उत्तर: B
A: Open writer के साथ empty होना EOF नहीं।
B: Data आ सकता है; EOF में drained data और सभी writers बंद चाहिए।
C: Pipe content नहीं बनाता।
D: Wait FIFO order नहीं उलटती।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन