LOCK-X(D1)
WAIT
WAIT
شکل ۳-۳- نمونه‌ای از نحوه رخ دادن بن‌بست
در شکل ۳-۴، نیز مثال دیگری از نحوه ایجاد بن‌بست را مشاهده می‌نمایید. تراکنش T1 در انتظار است زیرا درخواست قفل روی داده D2 را دارد که در اختیار تراکنش T2 است. تراکنش T2 در انتظار است زیرا درخواست قفل روی داده D3 را دارد که در اختیار تراکنش T3 است. تراکنش T3 در انتظار است زیرا درخواست قفل روی داده D4 را دارد که در اختیار تراکنش T4 است. تراکنش T4 در انتظار است زیرا درخواست قفل روی داده D1 را دارد که در اختیار تراکنش T1 است. به این ترتیب هر چهار تراکنش به حالت انتظار رفته و امکان خروج از این حالت را ندارند و مشکل بن‌بست رخ داده است.
زمان
T3
T4
T1
T2
LOCK-X(D1)
LOCK-X(D2)
WAIT
LOCK-X(D2)
LOCK-X(D3)
WAIT
LOCK-X(D3)
LOCK-X(D4)
WAIT
LOCK-X(D4)
LOCK-X(D1)
WAIT
شکل ۳-۴- مثال برای بن‌بست

راه حل‌های مشکل بن‌بست
الف) الگوریتم‌های کنترل همروندی که از بن‌بست پیش‌گیری می‌کنند:

• • پروتکل ۲PL محافظه‌کارانه (در بخش ۳-۲ به آن اشاره شده است.)

• • قفل‌گذاری براساس یک نظم خاص (در بخش ۳-۲، به آن اشاره شده است.)

• • استفاده از زمان‌مهر (در قسمت ۳-۳-۲، توضیح داده خواهد شد.)

• • الگوریتم WD

• • الگوریتم WW

• • تکنیک عدم انتظار (NW)^[38]

• • تکنیک انتظارمحتاطانه (CW)^[39]

ب) الگوریتم‌های کنترل همروندی که به تشخیص یا کشف بن‌بست می‌پردازند:

• • روش مهلت زمانی

• • روش بررسی متناوب درخواست قفل‌گذاری

تکنیک‌های زمان‌مهر
زمان‌مهرِ هر تراکنش مقداری یکتا است، که سیستم به هر تراکنش می‌دهد. سیستم می‌تواند براساس این مقادیر یکتا تراکنش‌ها را منظم کند. این مقدار معمولاً تشکیل شده است از:

• • ساعت

• • تاریخ عرضه تراکنش به سیستم

• • شماره پردازنده‌ای که تراکنش به آن عرضه می‌شود (این مورد برای معماری موازی لازم است.)

مقدار زمان‌مهر تراکنش را با TS(T) نشان می‌دهیم و تراکنش‌ها به ترتیب زمان ورودشان به سیستم مرتب می‌شوند. اگر تراکنش T_i پیش از تراکنش T_j به سیستم عرضه و شروع شده باشد، آن‌گاه آن را با TS(T_i)<TS(T_j) نشان خواهند داد. برای استفاده از تکنیک زمان‌مهر برای تراکنش‌ها دو الگوریتم وجود دارد: