Concurrency Controlالتحكم في التزامن
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- Lock-Based Protocols
- Deadlock Handling
أقسام الفصل
- 1Locks and lock modesالأقفال وأنماطها
- 2Two-phase locking and lock conversionsالقفل ثنائي المرحلة وتحويل الأقفال
- 3Deadlocks and starvationالجمود والتجويع
- 4Implementation of locking: lock manager and lock tableتنفيذ القفل: مدير الأقفال وجدول الأقفال
- 5Deadlock detection: the wait-for graphكشف الجمود: مخطط الانتظار
- 6Deadlock prevention: wait-die, wound-wait and timeoutsمنع الجمود: انتظر-مت، وجرح-انتظر، والمهلة
- 7Deadlock recoveryالتعافي من الجمود
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
Lock-based protocolsالأقفال
Locks and lock modes
A mechanism to control concurrent access to a data item. Requests go to the concurrency-control manager; the transaction proceeds only after the request is granted.
Exclusive (X) modeحصري
- Data item can be both read and written
- Requested with lock-X
Shared (S) modeمشترك
- Data item can only be read
- Requested with lock-S
| Requested \ held | S held | X held |
|---|---|---|
| S requested | compatible (granted) | not compatible (wait) |
| X requested | not compatible (wait) | not compatible (wait) |
- Any number of transactions can hold shared locks on an item; if any transaction holds an exclusive lock, no other transaction may hold any lock on it.
- If a lock cannot be granted, the requester waits till all incompatible locks have been released.
Why a locking protocol?لماذا بروتوكول القفل؟
Locks and lock modes
- Locking as above is not sufficient to guarantee serializability: if A and B get updated in-between the read of A and B, the displayed sum would be wrong.
A set of rules followed by all transactions while requesting and releasing locks; locking protocols restrict the set of possible schedules.
Two-phase lockingالقفل ثنائي المرحلة
Phase 1: growing
- May obtain locks
- May not release locks
- With conversions: lock-S, lock-X, upgrade S → X
Phase 2: shrinking
- May release locks
- May not obtain locks
- With conversions: release S/X, downgrade X → S
- Ensures conflict-serializable schedules: transactions can be serialized in the order of their lock points (where each acquired its final lock).
- Still relies on the programmer to insert the locking instructions.
Deadlocksالجمود
| T3 | T4 |
|---|---|
| lock-X(B) | |
| read(B) | |
| B := B − 50 | |
| write(B) | |
| lock-S(A) | |
| read(A) | |
| lock-S(B) | |
| lock-X(A) |
- T4's lock-S(B) waits for T3 to release B; T3's lock-X(A) waits for T4 to release A — neither can make progress: a deadlock.
- To handle it, one of T3 or T4 must be rolled back and its locks released.
- Two-phase locking does not ensure freedom from deadlocks.
Starvationالتجويع
Occurs if the concurrency control manager is badly designed — e.g., a transaction waits for an X-lock while other transactions keep being granted S-locks on the same item, or the same transaction is repeatedly rolled back due to deadlocks.
Reasons for starvation (slide 10)
- Unfair waiting scheme (priority queue)
- Victim selection: same victim repeatedly
- Resource leak
- Denial-of-service attack
Lock manager and lock tableمدير الأقفال وجدولها
- The lock manager can be a separate process: it replies to a lock request with a lock grant message (or a message asking the transaction to roll back, in case of a deadlock); the requester waits for the answer.
- The lock table records granted locks and pending requests (and the lock type); usually an in-memory hash table indexed on the name of the data item.
Lock table rules (slide 12)
- 1
A new request is added to the end of the queue for the data item; it is granted if it is compatible with all earlier locks.
- 2
An unlock deletes the request; later requests are checked to see if they can now be granted.
- 3
If a transaction aborts, all its waiting or granted requests are deleted.
Deadlock detectionكشف الجمود
V = all the transactions; an edge Ti → Tj means Ti is waiting for Tj to release a data item. It is inserted when Ti requests an item held by Tj and removed when Tj no longer holds an item needed by Ti.
The system is in a deadlock state if and only if the wait-for graph has a cycle. A deadlock-detection algorithm must be invoked periodically.
Deadlock preventionمنع الجمود
There is a set of transactions such that every transaction in the set is waiting for another transaction in the set.
Prevention protocols ensure the system never enters a deadlock state (slide 15)
- Pre-declaration: each transaction locks all its data items before it begins execution.
- Partial ordering of all data items: a transaction locks items only in that order.
A transaction waits for a lock only for a specified time, then is rolled back and restarted — deadlocks are not possible. Simple to implement, but starvation is possible, and a good timeout value is difficult to determine.
Wait-die and wound-waitانتظر-مت وجرح-انتظر
Deadlock prevention: wait-die, wound-wait and timeouts
| T1 requests an item held by T2 | Wait-die (non-preemptive) | Wound-wait (preemptive) |
|---|---|---|
| T1 older: TS(T1) < TS(T2) | T1 waits | T1 wounds T2: T2 is rolled back |
| T1 younger: TS(T1) > TS(T2) | T1 dies (rolled back) | T1 waits |
| Do older transactions wait? | Yes, for younger ones | Never wait for younger ones |
| Aborts and rollbacks | Higher | Lesser |
حدد ما يحدث قبل الكشف.
Wait-die
TS(T1) = 5, TS(T2) = 10. T2 requests an item locked by T1.
T2 is younger than the holder, so **T2 dies** (rolled back) and is restarted later **with the same timestamp 10**.
Wound-wait
Same timestamps. T1 requests an item locked by T2.
T1 is older, so **T1 wounds T2**: T2 is rolled back and restarted later with its timestamp 10.
- In both schemes a rolled-back transaction keeps its original timestamp: older transactions gain precedence and starvation is avoided.
Deadlock recoveryالتعافي من الجمود
- Victim
Roll back some transaction (a victim): choose the one that will incur minimum cost.
- How far
Total rollback (abort and restart), or — more effective — roll back only as far as necessary to break the deadlock.
- Starvation
Happens if the same transaction is always the victim: include the number of rollbacks in the cost factor.
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Locks and lock modesالأقفال وأنماطها
- Two-phase locking and lock conversionsالقفل ثنائي المرحلة وتحويل الأقفال
- Deadlocks and starvationالجمود والتجويع
- Implementation of locking: lock manager and lock tableتنفيذ القفل: مدير الأقفال وجدول الأقفال
- Deadlock detection: the wait-for graphكشف الجمود: مخطط الانتظار
- Deadlock prevention: wait-die, wound-wait and timeoutsمنع الجمود: انتظر-مت، وجرح-انتظر، والمهلة
- Deadlock recoveryالتعافي من الجمود