Synchronization: atomic primitives, Peterson और conditions
लक्ष्य और reasoning model
Atomic read-modify-write split test/set race क्यों सुधारता है, Peterson का two-thread trace कैसे करें और condition variable में lost wake-up कैसे रोकें, सीखें। पूर्वज्ञान: प्रकाशित critical-sections और semaphore पाठ। सभी traces atomic shared reads/writes, sequential consistency, updates की visibility और runnable threads के eventual execution मानते हैं। Critical sections समाप्त होते हैं। Pseudocode सीधे portable C/C++ नहीं; वास्तविक language/CPU में सही atomics, memory ordering और libraries चाहिए।
1. एक atomic key dispenser
खराब dispenser पहले key मौजूद होने की जाँच करता है, बाद में निकालता है। दो लोग जाँच पास कर सकते हैं। Atomic dispenser जाँच और निकालने को indivisible action बनाता है। test_and_set(L) atomically पुराना L लौटाकर L=1 करता है। शुरू में L=0। Return value 1 रहे तो repeat करें; 0 मिले तो acquire हुआ। Release के लिए implementation में required release semantics के साथ 0 store करें।
हल किया collision: A,B दोनों acquire करते हैं। Atomic operations का क्रम होगा। A पहले हो तो 0 लौटाकर L=1 करता है। अगला B operation 1 लौटाता है, इसलिए B enter नहीं कर सकता। लगभग साथ शुरू होने से दोनों एक ही पुराना 0 नहीं ले सकते। सभी protocol मानें तो mutual exclusion सुधरता है।
पर bounded waiting नहीं मिलती। Release पर नया या पहले सफल thread पुराने waiter से पहले फिर जीत सकता है। Spinning CPU लेता है; एक CPU पर holder न चल रहा हो तो खास तौर पर waste है। केवल एक processor के interrupts disable करने से दूसरे processor का shared-data access नहीं रुकता।
2. Peterson: इच्छा और tie-breaker
ठीक दो threads i∈{0,1}, j=1−i लें। शुरू में flag[0]=flag[1]=false; turn कुछ भी हो। Thread i entry:
flag[i]=true; turn=j; जब तक (flag[j] और turn==j), spin।
फिर critical section; exit पर flag[i]=false। Flag interest बताता है; दोनों interested हों तो turn दूसरे को priority देता है। अकेला कोई एक variable दोनों काम नहीं करता।
हल किया contention: T0 flag[0]=true, turn=1 करता है। फिर T1 flag[1]=true, turn=0 करता है। दोनों flags true, final turn=0। T0 की condition flag[1] और turn==1 false है; T0 enter कर सकता है। T1 की flag[0] और turn==0 true है; वह wait करता है। T0 flag[0] clear करे तो T1 enter कर सकता है। आखिरी turn writer दूसरे को मौका देता है; “turn उसी thread को बताता है जिसे wait करना है” गलत shortcut है।
Declared model में algorithm mutual exclusion, progress और bounded overtaking देता है। ये algorithmic properties हैं, scheduling रुक जाए तो wall-clock deadline नहीं। Proof intuition: दोनों flags true होने पर turn एक साथ 0 और 1 नहीं हो सकता; दोनों interested रहते हुए दोनों के enter करने के लिए चाहिए वैसी दोनों wait conditions false नहीं हो सकतीं। पूर्ण proof flag/turn write order भी देखता है। कोई line न हटाएँ और यही two-thread code सीधे n threads पर न लगाएँ।
3. Condition variables predicate की प्रतीक्षा करती हैं
Condition variable doorbell जैसी है: parcel आया या नहीं, जाँचें। Bell parcel नहीं और स्थायी “एक parcel” token भी नहीं। Mutex M से protected shared predicate ready रखें।
यह single-publication notification उदाहरण है: शुरू में ready=false और producer ठीक एक item केवल एक बार publish करता है। Reusable bounded buffer में not-full predicate और producer का संबंधित wait भी चाहिए, जैसा पिछले semaphore पाठ में था। इस check के बिना producer बार-बार चलाने पर unconsumed item overwrite हो सकता है।
Consumer: lock(M); जब तक ready false: wait(CV,M); item consume करें; ready=false; unlock(M)।
Producer: lock(M); item बनाएँ; ready=true; signal(CV); unlock(M)।
wait atomically M छोड़कर thread की waiting व्यवस्थित करता है और लौटने से पहले M फिर लेता है। इससे ऐसा gap नहीं रहता जिसमें consumer false जाँच चुका हो पर waiting शुरू करने से पहले producer update/signal कर दे। Sleep में M पकड़े रखने पर producer predicate बदल ही नहीं पाएगा।
4. Loop और persistent state क्यों?
यहाँ Mesa-style semantics हैं: signal waiter को eligible बनाता है, mutex तुरंत transfer नहीं करता और predicate true बने रहने की guarantee नहीं। कोई दूसरा consumer M लेकर item पहले consume कर सकता है। Spurious wake-ups भी allowed हो सकती हैं। इसलिए wake के बाद while से predicate फिर जाँचें, एक बार if से नहीं।
हल किया early-producer case: किसी consumer के wait करने से पहले producer ready=true और signal करता है। Signal स्वयं याद रहना जरूरी नहीं। बाद का consumer M लेकर ready=true देखता है और wait छोड़ देता है। इसलिए work नहीं खोता। Producer केवल bell बजाए और predicate न रखे तो बाद का consumer पुराने event के बावजूद सदा wait कर सकता है। Zero-initialized semaphore signal token रख सकता है; bare condition notification अलग है।
5. Classic problems specifications हैं
Producer-consumer पहले empty/full/mutex से हल हुआ। Readers-writers में concurrent readers allowed हैं, पर active writer readers और अन्य writers दोनों को exclude करता है। Continuous readers में reader-preference writer को starve कर सकती है; writer-preference readers को delay कर सकती है। Fairness safety से अलग बतानी है। Dining philosophers circular acquisition दिखाता है: common strict fork order cycle तोड़ता है, जैसा deadlock lesson में lock-order proof था। कहीं एक mutex जोड़ देना correctness/fairness का प्रमाण नहीं।
Self-check
Atomic step और memory model बताएँ। Mutual exclusion को bounded waiting से अलग रखें। हर condition wait का mutex-protected predicate पहचानें। Atomic acquire को ordinary check-then-write से न बदलें; wake-up को resource ownership न मानें।
मौलिक अभ्यास: छह single-correct MCQ
हर प्रश्न में ठीक एक विकल्प चुनें। हर प्रश्न की आवश्यक मान्यताएँ उसी में दी गई हैं।
SY01. L=0। दो threads atomic test_and_set(L) करते हैं: पुराना L लौटे, 1 लिखा जाए। बीच में release नहीं। Operation order में return values?
A. 0,0 B. 0,1 C. 1,0 D. 1,1
उत्तर: B
A: Atomicity दोनों को update से पहले 0 पढ़ने से रोकती है।
B: पहला 0 देखकर 1 करता है; दूसरा 1 देखता है।
C: पहला initial 0 देखेगा।
D: Prior writer नहीं, इसलिए पहला 1 नहीं देख सकता।
SY02. Simple test-and-set spinlock mutual exclusion देता है पर waiter ordering नहीं बताता। कौन सी अतिरिक्त property guaranteed नहीं?
A. अधिकतम एक holder B. Atomic acquisition attempt C. हर contender की bounded waiting D. Failed attempt held lock देख सकती है
उत्तर: C
A: यही stated mutual exclusion है।
B: Primitive atomic परिभाषित है।
C: Fairness के बिना contender releases के बाद बार-बार हार सकता है।
D: 1 देखना सामान्य failed-acquisition result है।
SY03. Peterson में flag[i]=true; turn=j; while(flag[j] और turn==j) wait है। दोनों flags true, final turn=0, कोई enter नहीं हुआ। कौन loop पार कर सकता है?
A. केवल T0 B. केवल T1 C. दोनों D. कोई नहीं
उत्तर: A
A: T0 के लिए j=1, turn==1 false है।
B: T1 में j=0, wait condition दोनों true हैं।
C: T1 की condition true है।
D: T0 की wait condition false है।
SY04. सही mutex/condition-variable wait में wait के दौरान और लौटने पर mutex का क्या होता है?
A. Sleep भर held, लौटते समय unlocked B. Waiting के लिए atomically released, return से पहले reacquired C. नष्ट फिर बनाया जाता है D. हमेशा के लिए release, reacquire नहीं
उत्तर: B
A: Mutex पकड़े रहने से producer protected state नहीं बदल पाएगा।
B: Test-to-sleep gap रुकता है और return पर protected access मिलता है।
C: Wait mutex नष्ट नहीं करता।
D: Predicate सुरक्षित जाँचने के लिए caller को lock फिर चाहिए।
SY05. Mesa-style condition signaling में consumer if की जगह while(not ready) wait क्यों करे?
A. Signal स्थायी resource ownership देता है B. Mutex reacquire करने से पहले predicate फिर false हो सकता है C. while से mutex की जरूरत खत्म D. Condition variable unlimited tokens रखती है
उत्तर: B
A: Signal स्थायी ownership नहीं देता।
B: दूसरा consumer या spurious wake-up assumption बदल सकता है।
C: Shared predicate को synchronized access चाहिए।
D: यह condition notification का contract नहीं।
SY06. Producer M पकड़े ready=true करके किसी waiter से पहले signal करता है। बाद में consumer M लेकर while में ready जाँचता है। बीच में दूसरा consumer नहीं। क्या होगा?
A. पुराना signal न होने से अवश्य सोएगा B. ready=true देखकर wait नहीं करेगा C. जाँचने से पहले ready reset जरूरी D. M lock किए बिना enter करेगा
उत्तर: B
A: Available work persistent predicate रखता है, remembered signal नहीं।
B: While condition false है; stored state से आगे बढ़ता है।
C: पहले reset availability जानकारी मिटा देगा।
D: Protocol ready देखने से पहले M lock करता है।
स्रोत और दायरा
यह मौलिक पाठ GATE 2026 course के मौजूदा OS foundations को आगे बढ़ाता है। इसका संबंध आधिकारिक 2026 syllabus के Section 8 से है; यह पूरे OS या GATE 2027 की पूर्ण तैयारी का दावा नहीं है। अभ्यास मौलिक हैं, पिछले वर्षों के प्रश्न नहीं।
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन