يک سيستم توزيع شده شبکه‎ای از سايت‎ها است که توسط ارسال پيغام با يکديگر تبادل اطلاعات می‎کنند. يکی از مهم‎ترين کاربردهای سيستم‎های توزيع شده امکان به اشتراک گذاشتن منابع بين سيستم‎ها است. در چنين محيط‎هايي اگر چنانچه يک دنباله از تخصيص منابع به پردازه‎ها تحت کنترل نباشد، امکان به وجود آمدن بن‎بست وجود دارد.
يک بن‎بست هنگامی روی مي‎دهد که پردازه‎هايي که برخی منابع را گرفته‎اند برای در اختيار گرفتن منابعی که توسط ديگر پردازه‎های در همان مجموعه گرفته شده اند درخواست بدهند. ساده‎ترين توصيف يک بن‎بست از دو پردازه تشکيل می‎شود، که هر کدام از آنها منبع متفاوتی را در حالت انحصاری در اختيار گرفته‎اند و برای گرفتن منبعی که در اختيار ديگری است درخواست می‎دهند. جز در حالتی که بن بست رفع می‎شود، تمامی پردازه‎های شامل بن بست به طور نامتناهی مسدود هستند. در نتيجه، يک بن‎بست نياز به دقت پردازه¬ای در بيرون پردازه‎هايي که مسدود شده¬اند دارد که آنرا تشخيص و حل کند.
يک بن‎بست توسط سقط کردن يک يا چند پردازه در بن‎بست رفع می‎شود. با سقط شدن پردازه(ها) منابعي که در اختيار آنها بود به ديگر پردازه‎های موجود در بن‎بست داده می‎شود تا بتوانند به کار خود ادامه دهند.
در سالهای اخير مسأله‎ی بن‎بست در تحقيقات زيادی مد نظر قرار گرفته است. اين تحقيقات شامل بن‎بست در سيستم‎های اشتراکی حافظه و سيستم‎های توزيع شده بوده است. در سيستم‎های توزيع‎شده مشکل همچنان پابرجاست. در اين سيستم‎ها به طور مشخص بايستی الگويي وجود داشته باشد که بن‎بست را تشخيص دهد (detection) و همچنين متعاقب آن روشي برای رفع بن‎بست موجود باشد (resolution).
در الگوريتم‎های تشخيص و رفع بن‎بست استفاده از يک روش اثبات صوری اجتناب‎ناپذير است. در فصل‎های بعدی نشان خواهيم داد که چرا نگرش در سيستم‎های توزيع شده ناچار به سمت روش‎های صوری پيش رفته است. در اين گزارش پس از بررسی کارهای ديگر صوری انجام گرفته در اين زمينه، بررسی الگوريتم‎های توزيع‎شده بر مبنای اتوماتاهای محدوديت امکان سنجی خواهيم نمود.

---

برچسب ها: تشخیص بن بست در سیتم های توزیع شده بن بست در سیستم توزیع شده توزیع شده پایگاه داده سیستم توزیع شده سیستم عامل کشف بن بست رفع بن بست deadlock distributed