تشخیص بن بست در سیتم های توزیع شده

تشخیص بن بست در سیتم های توزیع شده

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