सिंक्रोनाइज़ेशन: रेस, क्रिटिकल सेक्शन और लॉक्स
सीखने के लक्ष्य और model
Lost-update trace बनाना, critical section पहचानना, safety और progress का अंतर समझना तथा सही mutex का उपयोग परखना सीखें। पूर्वज्ञान: threads का address space साझा होता है, लेकिन execution contexts अलग होते हैं। उदाहरण abstract pseudocode हैं, चलाने योग्य C या C++ नहीं। दिखाया गया हर read या write atomic है, interleaving हर thread के statements का क्रम रखती है, और सभी threads एक sequentially consistent memory history देखते हैं। साधारण unsynchronized C/C++ accesses पर यह model लागू मानना गलत है: data race से program का behavior undefined हो सकता है।
यह आधारभूत पाठ basic mutual exclusion तक सीमित है। Semaphores, condition variables, formal deadlock analysis और memory-order primitives आगे के पाठों में चाहिए। नीचे जानबूझकर गलत दिए pseudocode को programming का तरीका न मानें।
1. Source का एक statement हमेशा एक operation नहीं
दो threads shared count को एक-एक बार बढ़ाना चाहते हैं और शुरू में count=0 है। Abstract increment के तीन चरण हैं:
- Shared count को thread के private register r में पढ़ना।
- Private r को r+1 करना।
- r को वापस shared count में लिखना।
T1 का register r1 और T2 का r2 है। अलग-अलग reads और writes atomic हों, तब भी पूरी read–modify–write sequence अपने आप atomic नहीं हो जाती। अलग-अलग सही increments के बाद count=2 होना चाहिए, लेकिन interleaving एक update खो सकती है।
| चरण | क्रिया | Shared count | Private परिणाम |
|---|---|---|---|
| 1 | T1 count पढ़ता है | 0 | r1=0 |
| 2 | T2 count पढ़ता है | 0 | r2=0 |
| 3 | T1 r1 बढ़ाता है | 0 | r1=1 |
| 4 | T2 r2 बढ़ाता है | 0 | r2=1 |
| 5 | T1 r1 लिखता है | 1 | r1=1 |
| 6 | T2 r2 लिखता है | 1 | r2=1 |
दोनों threads ने increment के instructions चलाए, लेकिन अंतिम count 1 है। Serial क्रम “पहले पूरा T1, फिर पूरा T2” में T2 मान 1 पढ़ता है और परिणाम 2 आता है। ठीक इसी दो-thread, हर thread के एक-increment वाले model में अंतिम मान 1 या 2 हो सकते हैं, 0 या मनमाना कोई मान नहीं। सभी वैध interleavings गिनकर इसे जाँचा जा सकता है; केवल “कुछ भी हो सकता है” कहना पर्याप्त नहीं।
Race condition में concurrent actions की timing या ordering परिणाम को इस तरह प्रभावित करती है कि अपेक्षित शर्त टूट सकती है। Language-level शब्द data race की उस भाषा के memory model में अधिक निश्चित परिभाषा होती है। Abstract traces से वास्तविक code पर जाते समय यह अंतर याद रखें।
2. पूरी तार्किक क्रिया बचाएँ, केवल अंतिम write नहीं
Critical section वह हिस्सा है जो shared state access करता है और दूसरे conflicting accesses के साथ overlap नहीं होना चाहिए। ऊपर increment में count को पढ़ना, बदलना और लिखना, तीनों protected operation के हिस्से हैं। यदि केवल अंतिम write lock में हो, तो दोनों threads पहले ही 0 पढ़ सकते हैं और lost update फिर भी हो सकता है।
Entry section अनुमति लेता है और exit section उसे छोड़ता है। जिस code को यह protection नहीं चाहिए वह remainder section है। सही shared mutex m शुरू में unlocked है और हर भाग लेने वाला thread ऐसा करता है:
lock(m) count को private r में पढ़ें r = r+1 r को count में लिखें unlock(m)
मानें कि lock acquisition atomic है और mutex की memory-synchronization guarantees लागू हैं। एक समय पर अधिकतम एक thread m का owner होगा। T1 owner हो तो T2 उसके release करने तक protected section में नहीं आ सकता। फिर T2 पहले पूरे हुए increment का count पढ़ता है और दोनों के समाप्त होने पर count=2 मिलता है। क्रम T1 फिर T2 हो या T2 फिर T1, दोनों सही हैं।
दोनों threads को एक ही mutex इस्तेमाल करना होगा और हर conflicting access को protocol मानना होगा। दो अलग locks threads के बीच तालमेल नहीं बनाते। तीसरा thread m लिए बिना count बदलता है तो protection को bypass करता है। कई fields पर फैले invariant के लिए केवल एक field का atomic increment भी कम पड़ सकता है; पूरी consistency requirement की रक्षा करें।
3. आकर्षक, पर गलत lock
Shared Boolean busy शुरू में false लें। हर thread busy को तब तक पढ़ता है जब तक false न दिखे, फिर busy=true लिखकर critical section में जाता है और अंत में busy=false लिखता है।
यहाँ जाँच और दावा अलग operations हैं। T1 false पढ़ सकता है और true लिखने से पहले T2 भी false पढ़ सकता है। फिर दोनों true लिखकर अंदर चले जाते हैं। Atomic reads और atomic writes से संयुक्त “जाँचो और अपना करो” operation atomic नहीं बनता। सही mutex के नीचे उचित atomic read–modify–write primitive जैसी व्यवस्था और पूरा locking protocol चाहिए। साधारण flag जोड़ देना या बुरा schedule कभी न आने की आशा रखना प्रमाण नहीं है।
4. Safety और liveness के प्रश्न अलग हैं
Mutual exclusion safety property है: दो participants protected section में एक साथ न हों। यह बुरी घटना रोकती है। लेकिन कोई protocol किसी को कभी अंदर न जाने दे तो उसमें भी mutual exclusion है, जबकि वह उपयोगी नहीं।
Progress माँगता है कि critical section खाली हो और कुछ participants प्रवेश चाहते हों तो चयन अनिश्चित काल तक टाला न जाए; संबंधित contenders चयन कर सकें। Bounded waiting किसी participant के प्रवेश माँगने और उसे मिलने के बीच दूसरों के प्रवेशों की संख्या पर सीमा माँगता है। ये संबंधित, पर एक जैसे विचार नहीं हैं।
हल किया गया counterexample: strict-turn rule में T1 केवल turn=1 और T2 केवल turn=2 पर प्रवेश करता है; बाहर आते समय turn दूसरे thread को देता है। यदि turn=2 है लेकिन T2 हमेशा अपने remainder section में रहता है, तो T1 खाली critical section में भी नहीं जा सकता। यह progress की विफलता है, भले दो threads साथ अंदर कभी न आएँ। खराब synchronization के लिए दो threads का टकराना आवश्यक नहीं।
केवल mutex interface से fairness या bounded waiting की गारंटी नहीं मिलती। सबके समाप्त होने का दावा करने से पहले eventual scheduling, finite critical sections और eventual release की मान्यताएँ लिखें। Non-reentrant mutex लेने वाला thread उसे छोड़े बिना उसी mutex को फिर लेने की कोशिश करे तो स्वयं block हो सकता है। “और lock लगाना” अपने आप अधिक सुरक्षित नहीं।
5. Spinning, blocking और एक-CPU तर्क
Spinning waiter किसी condition को बार-बार जाँचता है और CPU समय लेता है। Blocking mutex waiter को तब तक सुला सकता है जब तक वह फिर कोशिश न कर सके। केवल इन तरीकों से fairness सिद्ध नहीं होती। Preemptive scheduling वाले एक CPU पर spinner को रोका जा सकता है ताकि owner चलकर lock छोड़े। ऐसी scheduling के बिना यदि spinner owner को कभी चलने ही न दे, तो progress रुक सकती है। इसलिए यह कहने से पहले कि spinlock एक CPU पर हमेशा चलता है या कभी नहीं चलता, scheduling की मान्यताएँ पहचानें।
Race के लिए दो physical CPUs जरूरी नहीं। Read और उसके बाद write के बीच context switch ही पहले वाला lost-update trace बना सकता है। दूसरी ओर mutex “सभी threads रोकता” नहीं; केवल उस locking protocol को मानने वाले participants को protected operation से बाहर रखता है। असंबंधित काम जारी रह सकता है।
मुख्य बातें और सामान्य गलतियाँ
- Trace से पहले atomic steps और अपेक्षित invariant लिखें।
- Private registers में shared value की पुरानी copies हो सकती हैं।
- पूरी conflicting read–modify–write sequence को एक ही shared lock से बचाएँ।
- सामान्य check और उसके बाद set, atomic test-and-set नहीं हैं।
- Mutual exclusion अकेला progress, fairness या bounded waiting सिद्ध नहीं करता।
- Abstract pseudocode के परिणाम को data-racy C/C++ program की guarantee न मानें; एक CPU होने से race समाप्त नहीं होती।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें। प्रश्न की सभी मान्यताएँ लागू रहेंगी।
C01. दो threads count=0 से शुरू करके एक-एक बार count पढ़ते, private register बढ़ाते और count लिखते हैं। दिए atomic-step, sequentially consistent model में कौन-से अंतिम मान संभव हैं?
A. केवल 2 B. केवल 1 C. 0, 1 और 2 D. 1 और 2
उत्तर: D
A: Lost-update interleaving में 1 भी संभव है।
B: Serial execution में 2 भी संभव है।
C: हर अंतिम write बढ़ाया हुआ मान रखता है; इस खास model में कोई वैध execution 0 पर समाप्त नहीं होता।
D: दोनों reads को 0 मिले तो परिणाम 1; एक पूरा increment दूसरे read से पहले हो तो 2।
C02. दोनों threads एक सही mutex इस्तेमाल करते हैं, लेकिन increment के केवल अंतिम write के आसपास। क्या अंतिम count अब भी 1 हो सकता है?
A. नहीं, atomic writes हमेशा पूरे increment को atomic बनाते हैं। B. हाँ, दोनों अलग protected writes से पहले 0 पढ़कर 1 निकाल सकते हैं। C. नहीं, shared mutex process के पूरे code को अपने आप बचाता है। D. हाँ, लेकिन केवल दो physical CPUs पर।
उत्तर: B
A: अंतिम चरण की atomicity पहले read–modify sequence को नहीं बचाती।
B: Writes क्रम में होंगे, लेकिन दोनों पुरानी value से निकला 1 ही लिख सकते हैं।
C: केवल तय locked protocol मानने वाले accesses के बीच तालमेल होता है।
D: एक preemptive CPU की interleaving भी वही lost update बना सकती है।
C03. प्रस्तावित lock अलग से busy=false पढ़ता है और बाद में प्रवेश से पहले busy=true लिखता है। Mutual exclusion क्यों विफल हो सकता है?
A. किसी के flag claim करने से पहले दोनों false देख सकते हैं। B. Boolean दो states नहीं दिखा सकता। C. हर read busy को true कर देता है। D. Mutual exclusion के लिए अनंत critical section चाहिए।
उत्तर: A
A: Test और claim एक atomic operation नहीं हैं, इसलिए दोनों अंदर जा सकते हैं।
B: Boolean दो states दर्शाता है; समस्या protocol की atomicity है।
C: केवल read उसके बाद वाला write नहीं करता।
D: अनंत section progress बिगाड़ेगा; entry race हल नहीं करेगा।
C04. Strict-turn protocol में turn=2 है और T2 हमेशा remainder section में रहता है। T1 खाली critical section में प्रवेश चाहता है, पर नहीं कर सकता। सीधे कौन-सी आवश्यकता टूटती है?
A. Mutual exclusion, क्योंकि दोनों अंदर हैं B. हर individual read की atomicity C. Progress, क्योंकि turn rule प्रवेश की मांग अनिश्चित काल तक रोकती है D. हर thread के अलग register state की आवश्यकता
उत्तर: C
A: उदाहरण में कोई simultaneous entry नहीं; exclusion सही रह सकता है।
B: हर read और write atomic हो तब भी यह विफलता रहती है।
C: Section खाली है, फिर भी प्रवेश न चाहने वाला thread turn न दे तो T1 अंदर नहीं जाता।
D: Register ownership इस progress counterexample का कारण नहीं।
C05. दो threads एक ही सही mutex के भीतर count को एक-एक बार बढ़ाते हैं। शुरू में count=7 है; दोनों समाप्त होते हैं और हर conflicting access lock protocol मानता है। अंतिम count क्या है?
A. 7 B. 8 C. 8 या 9 D. 9
उत्तर: D
A: दोनों पूरे हुए protected increments का प्रभाव होगा।
B: आठ में update खोता है; पूरी क्रिया की सही protection इसे रोकती है।
C: मान्यताएँ पूरे increments को serial बनाती हैं और 8 को रोकती हैं।
D: क्रम कोई हो, increments serial हैं: 7→8→9।
C06. Lock mutual exclusion देता है, लेकिन specification fairness की गारंटी नहीं देती। केवल mutual exclusion से कौन-सा निष्कर्ष उचित है?
A. हर waiting thread दो turns में प्रवेश करता है। B. एक समय पर अधिकतम एक protocol मानने वाला thread protected critical section में है। C. Scheduling कुछ भी हो, हर thread अंततः प्रवेश करता है। D. CPU कभी spinning में समय नहीं लगाता।
उत्तर: B
A: प्रतीक्षा की संख्यात्मक सीमा के लिए अतिरिक्त guarantee और मान्यताएँ चाहिए।
B: Protocol मानने वाले threads के लिए यही mutual exclusion की safety guarantee है।
C: अंततः प्रवेश के लिए liveness और scheduling की मान्यताएँ चाहिए; safety पर्याप्त नहीं।
D: Mutual exclusion spinning या blocking से हो सकता है; यह waiting का तरीका तय नहीं करता।
स्रोत और दायरा
यह मौलिक प्रारंभिक पाठ आधिकारिक GATE 2027 CS syllabus के Section 8, Operating System, से जुड़ा है। इससे OS या पूरा syllabus समाप्त नहीं होता। Syllabus विषय की प्रासंगिकता और मूल textbook references आधारभूत concepts की जाँच के लिए हैं। उदाहरण, समयरेखाएँ और अभ्यास मौलिक हैं।
- Official GATE 2027 CS syllabus
- OSTEP: Concurrency: An Introduction
- OSTEP: Locks
- C++ working draft: Data races
स्रोत जाँचे गए: 2026-10-14।
प्रगति सहेजने के लिए साइन इन करें। साइन इन