آموزش سیستم مدیریت پایگاه داده - بن بست

در یک سیستم چند فرایندی، بن بست (deadlock) یک وضعیت ناخواسته است که در محیط منابع مشترک بوجود می آید، جایی که یک فرایند به طور نامحدود منتظر منبعی است که توسط فرایند دیگر نگهداری می شود.

برای مثال، فرض کنید مجموعه‌ای از تراکنش‌ها وجود دارد {T₀, T₁, T₂, ...,T_n}. T₀ برای انجام وظیفه‌اش به یک منبع X نیاز دارد. منبع X توسط T₁ نگهداری می شود و T₁ منتظر منبعی به نام Y است که توسط T₂ نگهداری می شود. T₂ منتظر منبعی به نام Z است که توسط T₀ نگهداری می شود. بنابراین، همه فرایندها منتظر ترک منابع توسط یکدیگر هستند. در این وضعیت، هیچ یک از فرایندها قادر به اتمام وظیفه‌اش نیست. این وضعیت به عنوان یک بن بست شناخته می شود.

بن بست برای یک سیستم سالم مطلوب نیست. در صورتی که سیستم در یک بن بست گیر کند، تراکنش‌های درگیر در بن بست یا باز می گردانده می شوند یا مجدداً شروع می شوند.

پیشگیری از بن بست (Deadlock Prevention)

برای جلوگیری از هر گونه وضعیت بن بست در سیستم، سامانه مدیریت پایگاه داده به طور فشرده عملیات‌ها را که تراکنش‌ها قرار است انجام دهند، بررسی می کند. سامانه مدیریت پایگاه داده عملیات‌ها را بررسی می کند و تجزیه و تحلیل می کند که آیا می تواند وضعیت بن بست ایجاد کند یا خیر. اگر بیابد که ممکن است یک وضعیت بن بست رخ دهد، در این صورت اجازه اجرای آن تراکنش را نمی دهد.

برخی از طرح‌های پیشگیری از بن بست از مکانیزم ترتیب زمانی تراکنش‌ها استفاده می کنند تا به طور پیش از برخی بن بستها پیش اززمان مشخصی شناخته شوند.

طرح انتظار-مرگ (Wait-Die Scheme)

در این طرح، اگر یک تراکنش درخواست قفل کردن یک منبع (آیتم داده) را که در حال حاضر توسط یک تراکنش دیگر با قفل منافی نگهداری می شود، ارائه کند، یکی از دو احتمال ممکن است رخ دهد −

• اگر TS(T_i) < TS(T_j) − به این معنا که T_i که درخواست قفل منافی می کند، قدیمی‌تر از T_j است − در این صورت T_i مجاز است منتظر بماند تا آیتم داده در دسترس شود.

• اگر TS(T_i) > TS(T_j) − به این معنا که T_i جوان‌تر از T_j است − در این صورت T_i نابود می شود. T_i بعدها با یک تأخیر تصادفی اما با همان برچسب زمانی مجدداً شروع می شود.

این طرح به تراکنش قدیمی اجازه می دهد منتظر بماند اما تراکنش جوان را از بین می برد.

طرح جراحی-انتظار (Wound-Wait Scheme)

در این طرح، اگر یک تراکنش درخواست قفل کردن یک منبع (آیتم داده) را که در حال حاضر توسط یک تراکنش دیگر با قفل منافی نگهداری می شود، ارائه کند، یکی از دو احتمال ممکن است رخ دهد −

• اگر TS(T_i) < TS(T_j) باشد، در این صورت T_i باعث لغو T_j می شود − به این معنا که T_i T_j را زخمی می کند. T_j بعدها با تأخیر تصادفی اما با همان برچسب زمانی مجدداً شروع می شود.

• اگر TS(T_i) > TS(T_j) باشد، در این صورت T_i مجبور است منتظر بماند تا منبع در دسترس شود.

این طرح به تراکنش جوان اجازه می دهد منتظر بماند؛ اما وقتی تراکنش قدیمی درخواست یک مورد نگهداری شده توسط تراکنش جوان را می کند، تراکنش قدیمی تراکنش جوان را مجبور به لغو و آزاد کردن مورد می کند.

در هر دو حالت، تراکنشی که در مرحله بعدی وارد سیستم می شود، لغو می شود.

اجتناب از بن بست (Deadlock Avoidance)

لغو کردن یک تراکنش همیشه رویکردی عملی نیست. به جای آن، مکانیزم های اجتناب از بن بست می توانند استفاده شوند تا به موقع هر وضعیت بن بست را شناسایی کنند. روش هایی مانند "نمودار انتظار" موجود هستند اما فقط برای سیستم هایی که تراکنش ها سبک هستند و تعداد کمتری از نمونه های منبع دارند مناسب هستند. در یک سیستم حجیم، تکنیک های جلوگیری از بن بست ممکن است به خوبی کار کنند.

نمودار انتظار (Wait-for Graph)

این روشی ساده برای پیگیری وضعیت هرگونه بن بست است. برای هر تراکنشی که وارد سیستم می شود، یک گره ایجاد می شود. وقتی تراکنش T_i برای قفل کردن یک مورد، مانند X، که توسط تراکنش دیگری به نام T_j نگهداری می شود، درخواست می دهد، یک لبه جهت دار از T_i به T_j ایجاد می شود. اگر T_j مورد X را آزاد کند، لبه بین آنها حذف می شود و T_i مورد داده را قفل می کند.

سیستم این نمودار انتظار را برای هر تراکنشی که منتظر برخی موارد داده هایی که توسط دیگران نگهداری می شوند است را حفظ می کند. سیستم بررسی می کند که آیا در گراف چرخه ای وجود دارد یا خیر.

در اینجا، می توان از دو رویکرد زیر استفاده کرد −

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

• گزینه دوم، لغو یکی از تراکنش ها است. همیشه ممکن نیست تراکنش جوان را لغو کنیم، زیرا ممکن است اهمیت بیشتری نسبت به تراکنش قدیمی داشته باشد. با کمک الگوریتم های نسبی، یک تراکنش انتخاب می شود که باید لغو شود. این تراکنش به عنوان قربانی شناخته می شود و این فرایند به عنوان انتخاب قربانی شناخته می شود.