Concurrency control: locking, deadlocks और timestamps
लक्ष्य और मान्यताएँ
Shared/exclusive locks, two-phase locking (2PL) और उसके variants समझें, wait-for cycles पहचानें और basic timestamp ordering trace करें। यहाँ explicit releases वाले item-level locks तथा single-version timestamp rules हैं, जब तक अलग न कहा जाए। Guarantee तभी है जब सभी transactions protocol मानें। केवल read/write schedule से held locks पता नहीं चलते, जब तक locking protocol बताया न गया हो।
1. Shared और exclusive locks
Shared S(X) lock, X पढ़ने की अनुमति देता है। Exclusive X(X) lock, X पढ़ने तथा लिखने की अनुमति देता है। अलग transactions एक item पर साथ में S locks रख सकती हैं। X lock दूसरे transaction के S या X से incompatible है। इससे readers साथ चल सकते हैं, लेकिन writer के साथ दूसरे reader/writer को रोकते हैं। Item X और lock mode X को अलग समझें।
S से X upgrade माँग सकते हैं, लेकिन दूसरे incompatible holders हटने तक इंतजार होगा। X से S downgrade permission घटाता है। 2PL में upgrade growing-phase acquisition है; downgrade shrinking phase शुरू करता है या उसका हिस्सा है। Lock लेना access की permission है, actual access नहीं।
उदाहरण: T1 तथा T2 दोनों S(A) लेकर A पढ़ते हैं। दोनों S locks बनाए रखकर X(A) upgrade माँगें तो हर एक दूसरे के release का इंतजार करेगा। Conversion से भी deadlock हो सकता है। Lock manager wait दूर करने के लिए दोनों को exclusive lock नहीं दे सकता।
2. 2PL और उसके variants
Basic 2PL की growing phase में locks acquire होते हैं, release नहीं; shrinking phase में release हो सकते हैं लेकिन नया lock नहीं मिलता। आखिरी lock acquisition का समय lock point है। Transactions को lock points के क्रम में रखने पर conflict-equivalent serial order मिलता है, इसलिए 2PL conflict serializability देता है। फिर भी deadlock संभव है। Commit से पहले exclusive lock release करने पर dirty reads भी संभव हैं।
Violation: lock-S(A),read(A),unlock(A),lock-X(B),write(B)। Release के बाद नया lock लिया, इसलिए यह 2PL नहीं, भले actual schedule serializable निकल जाए। Protocol guarantee के लिए sufficient condition है, हर serializable schedule के लिए necessary नहीं।
इस पाठ की convention में strict 2PL सभी exclusive locks commit/abort तक रखता है और बाकी locks पर सामान्य 2PL मानता है। इससे conflict serializability तथा strict schedules मिलते हैं। Shared locks पहले तभी छोड़ सकते हैं जब आगे कोई lock acquisition/upgrade न हो। Rigorous 2PL shared तथा exclusive दोनों locks commit/abort तक रखता है; इसका serial order commit order में हो सकता है। कुछ materials rigorous variant को ही strict 2PL कहते हैं; label की जगह दी हुई definition पढ़ें।
Conservative/static 2PL data operations से पहले सभी needed locks लेता है, atomically या wait-without-holding policy से। इसलिए hold-and-wait deadlocks नहीं होते। बदले में पहले से lock set जानना पड़ता है और concurrency घट सकती है। शुरुआत में locks एक-एक करके माँगना तथा partial set पकड़े रखना deadlock-free conservative protocol नहीं है।
3. Deadlock detection तथा prevention
Wait-for graph में Ti→Tj तब है जब Ti ऐसी lock माँग पर wait कर रहा है जो Tj की held lock से incompatible है। बताए ordinary lock-wait model में directed cycle deadlock दिखाता है। Precedence graph executed conflicting operations का order लेकर serializability जाँचता है। दोनों graphs को एक न समझें।
उदाहरण: T1 के पास X(A), T2 के पास X(B) है। T1, X(B) माँगे तो T1→T2। T2, X(A) माँगे तो T2→T1। Detector victim चुनकर abort करता है, effects rollback करके locks छोड़ता है और दूसरे को चलने देता है। बार-बार एक ही victim चुनना starvation पैदा कर सकता है। Timeout deadlock का शक देता है, cycle का proof नहीं।
सभी transactions एक total item order में locks लें और conversions को protocol के अनुसार संभालें तो global lock ordering circular wait रोकता है। Timestamp prevention में छोटा timestamp older है। Wait-die में older requester, younger holder के लिए wait कर सकता है; younger requester को older holder से lock माँगने पर abort होना पड़ता है। Wound-wait में older requester, younger holder को abort कराता है; younger requester, older holder का wait करता है। Restart पर वही timestamp रखने से age बनी रहती है और सामान्य progress assumptions में starvation रोकने में सहायता होती है।
उदाहरण: old timestamp 5, young 12। Young को old की lock चाहिए तो wait-die young को abort करता, wound-wait उसे wait कराता है। Old को young की lock चाहिए तो wait-die old को wait कराता, wound-wait young को abort करता है। “Old हमेशा wait” या “young हमेशा abort” दोनों protocols में सार्वभौमिक नहीं। Deadlock prevention के बाद भी progress के लिए fairness और resources चाहिए।
4. Basic timestamp ordering
हर transaction का TS(T) लें। हर item X का R_TS(X), सफलतापूर्वक पढ़ने वाले transaction का सबसे बड़ा timestamp है; W_TS(X), सफलतापूर्वक लिखने वाले का सबसे बड़ा timestamp है। सभी timestamps positive हों तो initial values 0 रख सकते हैं। Protocol locks पर wait कराने की जगह timestamp order में serialization चाहता है।
Read rule: TS(T)<W_TS(X) हो तो T abort/restart करे, क्योंकि बाद में serialize होने वाला transaction value overwrite कर चुका है। अन्यथा read allowed और R_TS(X)=max(R_TS(X),TS(T))।
Basic write rule: TS(T)<R_TS(X) हो तो abort, क्योंकि later transaction वह value पढ़ चुका जो इस earlier write से बदलनी चाहिए थी। अन्यथा TS(T)<W_TS(X) हो तो abort, क्योंकि later write हो चुकी है। दोनों tests fail न हों तो write allowed और W_TS(X)=TS(T)। Equality failure नहीं; transaction अपनी writes access कर सकता है।
Trace: R_TS(X)=W_TS(X)=0। T20 पढ़ता है, इसलिए R_TS=20। अब T10 write चाहे तो 10<20 के कारण abort, भले W_TS=0 है। वैकल्पिक case में T20 पहले write करे तो W_TS=20; फिर T10 की read, 10<20 के कारण abort। Timestamp order transaction age है, request arrival का wall-clock order नहीं।
Basic timestamp ordering, timestamp order में conflict serializable तथा deadlock-free है क्योंकि lock waits नहीं हैं। Repeated restart से starvation हो सकती है। Basic rules अकेले recoverability/cascadelessness नहीं देते: newer transaction older की uncommitted write पढ़ सकता है। Strict timestamp variants commit-related waiting जोड़ते हैं; उन्हें basic no-wait rules से अलग रखें।
5. Thomas write rule और अतिरिक्त सीमा
Thomas write rule obsolete-write case बदलता है। पहले TS(T)<R_TS(X) test करें और सत्य हो तो abort। उसके बाद TS(T)<W_TS(X) हो तो abort की जगह write ignore कर सकते हैं। वह obsolete है क्योंकि later timestamp ने surviving version पहले दे दिया है। Read-timestamp check हटता नहीं। यह extension कुछ view-serializable लेकिन conflict-serializable न होने वाले schedules स्वीकार कर सकता है। इसलिए basic protocol की conflict-serializability guarantee ज्यों-की-त्यों न लगाएँ।
MVCC कई versions रखता है और timestamp/snapshot rules से visible version चुनता है। Older reader को newer version होने मात्र से abort या writer को block करना जरूरी नहीं रहता। लेकिन MVCC नाम अकेला serializability नहीं देता; snapshot isolation में write skew संभव है। Sets of rows वाली conditions में predicate/range locks या suitable validation चाहिए। T1 को predicate का कोई matching row न मिले और T2 ऐसा row insert करे तो केवल पहले से matching rows lock करना phantom miss कर सकता है। ये सहायक cautions हैं, हर industrial isolation implementation का पूरा वर्णन नहीं।
परीक्षा checklist
Protocol variant, lock compatibility और release points पहले लिखें। Deadlock में current holders पर waits; serializability में ordered conflicts बनाएँ। Timestamp trace में successful operations के बाद ही metadata बदलें और tests सही order में लगाएँ। Deadlock-free को starvation-free, strict को serializable, या sufficient protocol को हर individual schedule की necessary condition न मानें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. एक item पर अलग transactions के कौन-से locks compatible हैं?
A. S and S B. S and X C. X and S D. X and X
उत्तर: A
A: Shared readers साथ हो सकते हैं।
B: Exclusive lock दूसरे shared holders रोकता है।
C: Exclusive holder दूसरा reader रोकता है।
D: दो exclusive holders allowed नहीं।
P02. कौन-सा sequence basic 2PL तोड़ता है?
A. A लें, B लें, A छोड़ें, B छोड़ें B. A लें, A छोड़ें, B लें C. A लें, B लें, commit, दोनों छोड़ें D. A लें, A छोड़ें, commit
उत्तर: B
A: Release के बाद acquisition नहीं।
B: Shrinking phase में नया lock लिया।
C: Commit तक locks रखना 2PL मानता है।
D: Release के बाद नया acquisition नहीं।
P03. Partial set पकड़े बिना data operations से पहले पूरा lock set लेने वाला कौन-सा protocol deadlock-free है?
A. Basic 2PL B. Strict 2PL alone C. Conservative 2PL D. Arbitrary lock upgrades
उत्तर: C
A: Basic 2PL में circular waits हो सकते हैं।
B: Strictness lock deadlock नहीं हटाती।
C: बताई acquisition policy hold-and-wait हटाती है।
D: Competing upgrades deadlock कर सकती हैं।
P04. Wait-die में younger transaction, older holder की lock माँगता है। क्या होगा?
A. Younger wait करेगा B. Younger abort होगा C. Older abort होगा D. दोनों को exclusive access
उत्तर: B
A: यह wound-wait का younger-requester rule है, wait-die नहीं।
B: Older holder के सामने younger requester abort होता है।
C: Wait-die holder को wound नहीं करता।
D: दोनों incompatible locks नहीं मिल सकतीं।
P05. Basic timestamp ordering: TS(T)=10, R_TS(X)=20, W_TS(X)=0। T write(X) माँगता है। परिणाम?
A. Allow, W_TS=10 करें B. 10<20 के कारण abort C. Item lock का wait D. W_TS बड़ा है इसलिए ignore
उत्तर: B
A: Read timestamp check यह write रोकता है।
B: Later transaction X पढ़ चुका है।
C: Basic timestamp ordering lock wait की जगह reject करता है।
D: W_TS=0 है; failed read-timestamp check Thomas rule में भी abort करता है।
P06. Thomas rule: TS(T)=10, R_TS(X)=5, W_TS(X)=20। T की write का क्या होगा?
A. Newer value replace करके apply B. Obsolete मानकर ignore C. R_TS के कारण abort D. W_TS घटने तक block
उत्तर: B
A: Later timestamp version replace नहीं करनी चाहिए।
B: Read check पास है, लेकिन newer write से यह obsolete है।
C: 10, 5 से छोटा नहीं।
D: Request valid बनाने के लिए timestamps घटते नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Databases syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन