طراحی، مدل‌سازی و مدیریت سیستم‌های پایگاه داده: بن‌بست در پایگاه داده - پرسش و پاسخ

پرسش:

بن بست (Deadlock) در سیستم های پایگاه داده چیست و چگونه رخ می دهد؟

پاسخ:

بن بست زمانی رخ می دهد که دو یا چند تراکنش در پایگاه داده منتظر یکدیگر برای آزادسازی منابعی باشند که توسط تراکنش دیگر در اختیار گرفته شده اند. این وضعیت منجر به توقف کامل و بی بازگشت تراکنش ها می شود. برای مثال، تراکنش A قفل روی منبع X دارد و برای دسترسی به منبع Y منتظر است، در حالی که تراکنش B قفل روی منبع Y دارد و برای دسترسی به منبع X منتظر است. هر دو تراکنش در وضعیت انتظار بی پایان قرار می گیرند.

پرسش:

شرایط لازم برای وقوع بن بست در پایگاه داده چیست؟ (شرایط کُپمن)

پاسخ:

چهار شرط لازم و کافی برای وقوع بن بست که توسط ریچارد کُپمن مطرح شد، عبارتند از: ۱. انحصار متقابل (Mutual Exclusion): حداقل یک منبع باید به صورت انحصاری در اختیار یک تراکنش باشد. ۲. نگهداری و انتظار (Hold and Wait): تراکنشی که حداقل یک منبع را در اختیار دارد، منتظر تخصیص منابع دیگری است که در حال حاضر توسط تراکنش های دیگر اشغال شده اند. ۳. عدم پیش دستی (No Preemption): منابع نمی توانند به زور از تراکنشی که آن ها را در اختیار دارد، گرفته شوند؛ منابع فقط پس از تکمیل کار تراکنش آزاد می شوند. ۴. انتظار چرخه ای (Circular Wait): مجموعه ای از تراکنش ها وجود دارد به طوری که $T_0$ منتظر منبعی است که توسط $T_1$ اشغال شده، $T_1$ منتظر منبعی است که توسط $T_2$ اشغال شده، ...، و $T_{n-1}$ منتظر منبعی است که توسط $T_n$ اشغال شده، و $T_n$ منتظر منبعی است که توسط $T_0$ اشغال شده است.

پرسش:

روش های تشخیص بن بست در پایگاه داده چیست؟

پاسخ:

روش اصلی تشخیص بن بست، استفاده از گراف انتظار (Wait-for Graph) است. در این گراف، گره ها نشان دهنده تراکنش ها هستند و یال جهت دار از تراکنش $T_i$ به تراکنش $T_j$ به این معنی است که $T_i$ منتظر منبعی است که توسط $T_j$ اشغال شده است. وجود یک حلقه در این گراف نشان دهنده وقوع بن بست است. سیستم پایگاه داده باید این گراف را به طور منظم بازسازی و تحلیل کند تا بن بست ها را شناسایی نماید.

پرسش:

چگونه می توان از بن بست با استفاده از روش تخصیص منابع در زمان درخواست جلوگیری کرد؟

پاسخ:

روش تخصیص منابع در زمان درخواست (Acquire all resources at once) یکی از روش های جلوگیری از بن بست است. در این روش، هر تراکنش قبل از شروع پردازش، تمام منابعی را که نیاز دارد، درخواست می کند. اگر تمام منابع در دسترس باشند، به تراکنش تخصیص داده می شوند و تراکنش شروع به کار می کند. اما اگر حتی یک منبع مورد نیاز در دسترس نباشد، تراکنش هیچ منبعی را دریافت نمی کند و منتظر می ماند تا تمام منابع مورد نیازش آزاد شوند. این روش شرط 'نگهداری و انتظار' را نقض می کند و از بن بست جلوگیری می نماید، اما ممکن است منجر به کاهش بهره وری و استفاده ناکارآمد از منابع شود.

پرسش:

نقش زمان بندی (Timestamp) در جلوگیری یا تشخیص بن بست چیست؟

پاسخ:

زمان بندی (Timestamp ordering) یک روش پیشگیری از بن بست است. در این روش، به هر تراکنش یک زمان منحصر به فرد (timestamp) تخصیص داده می شود. تراکنش ها بر اساس زمان ثبت شده خود اولویت بندی می شوند. دو رویکرد اصلی وجود دارد: ۱. رویکرد 'Wait-Die': اگر تراکنش $T_i$ منابعی را از تراکنش $T_j$ بخواهد و زمان $T_i$ بزرگتر از زمان $T_j$ باشد (یعنی $T_i$ جدیدتر باشد)، $T_i$ منتظر می ماند. اگر زمان $T_i$ کوچکتر از زمان $T_j$ باشد، $T_i$ 'می میرد' (خاتمه می یابد) و دوباره با همان زمان قبلی شروع به کار می کند. ۲. رویکرد 'Wound-Wait': اگر $T_i$ بخواهد منابع $T_j$ را بگیرد و زمان $T_i$ کوچکتر از زمان $T_j$ باشد، $T_j$ 'زخمی' (wound) می شود، منابعش را از دست می دهد و دوباره شروع به کار می کند. اگر زمان $T_i$ بزرگتر از زمان $T_j$ باشد، $T_i$ منتظر می ماند. این رویکرد ها با اجبار به عدم انتظار چرخه ای یا خاتمه زودهنگام تراکنش های جدیدتر، از بن بست جلوگیری می کنند.

پرسش:

استراتژی انتخاب قربانی (Victim Selection) در بازیابی از بن بست چیست و چه معیارهایی دارد؟

پاسخ:

هنگامی که بن بست رخ می دهد، لازم است یک یا چند تراکنش به عنوان قربانی انتخاب و خاتمه داده شوند تا بن بست شکسته شود. معیار های انتخاب قربانی می تواند شامل موارد زیر باشد: ۱. حداقل پیشرفت (Minimum progress): تراکنشی که کم ترین تغییر را در پایگاه داده ایجاد کرده است. ۲. حداقل منابع آزاد شده (Minimum resources released): تراکنشی که با خاتمه دادن آن، کم ترین منابع آزاد می شود. ۳. حداقل تعداد تراکنش های درگیر (Minimum number of transactions involved): تراکنشی که خاتمه آن، کمتر تراکنش دیگری را تحت تأثیر قرار می دهد. ۴. اولویت تراکنش (Transaction priority): تراکنش های با اولویت پایین تر ممکن است به عنوان قربانی انتخاب شوند.