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