نام فایل : بررسي آشكار سازي بن بست در سيستم عامل توزيع شده

فرمت : .DOC

تعداد صفحه/اسلاید : 16

حجم : 71 کیلوبایت

بررسي آشكار سازي بن بست در سيستم عامل توزيع شده
چكيده
آشكار سازي بن بست يكي از جدي ترين مسائل در سيستم عامل‌‌هاي توزيع شده است. در اين مقاله ما يك بررسي وضعيت هنري الگوريتم‌هاي آشكار سازي بن بست توزيع شده كه در ادبيات مطرح شده است ارائه مي كنيم. در اين حوزه ما يك نگاهي به مقالات آشنا درباره اين عنوان داريم و تلاش مي كنيم تا معروف ترين الگوريتم‌ ها را گروه بندي مي كنيم.
1- مقدمه
در طول دهه گذشته سيستمهاي محاسبه گر پيشرفت سريعي داشته اند كه تأثير زيادي بر سيستم عاملهاي توزيع شده دارد. در حاليكه سيستم‌هاي تجاري به تدريج پيشرفت مي كنند، چالشهاي جديد بوسيله ارتباط گسترده جهاني سيستم‌هاي كامپيوتري وضع شده است.
اين جريان يك نياز رشد كننده‌‌اي براي راه حلهاي توزيع شده با مقياس بالا ايجاد مي‌كند. در آينده، سيستم عاملهاي توزيع شده بايد صدها و حتي هزاران سايت و ميليونها مراجع را حمايت كنند و بنابراين با چالشهاي بزرگي در ارتباط با اجرا، در دسترس بودن و مديريت مواجه خواهند شد. يكي از چالشهايي كه ما بايد حل كنيم در اين حوزه مشكل بن بست است. همچنين نسبت يكي از جدي ترين مشكلات در سيستم‌ هاي برنامه ريزي رايج چند كاره است.
بقيه مقاله مثل زير سازمان دهي شد. بخش 2 مختصرا بن بست و حوزه آن در سيستم عاملهاي توزيع شده را توزيع مي دهد.
در حاليكه بخش 3 يك شرحي از مشكل بن بست ارائه مي دهد و 2 الگوي بن بست كه به طور كلي در سيستم‌هاي بانك اطلاعاتي توزيع شده به كار مي رود. يك گروه بندي از الگوريتم‌‌هاي توزيع شده براي اين الگوها و نماينده‌هاي گروه هاي مختلف در بخش 4 شرح داده شده است. نهايتا، ما در بخش 5 خلاصه مي كنيم، در حاليكه بخش 6 مرجهاي ما را توصيف مي كند.
2- پيش زمينه
در اين بخش ما تلاش مي كنيم تا نگاهي بر مقالات بررسي كه بوسيله ديگران در روش آشكار سازي بن بست ارائه شده است داشته باشيم.
متون بن بست رسما يك بن بست را به عنوان يك مجموعه فرايندي كه بن بست است، اگر هر فرايند در مجموعه منتظر يك رويدادي است كه تنها فرايند ديگري در مجموعه مي تواند موجب شود. تعريف مي كند. [2 و 1]. يك تعريف غيررسمي تر اين است كه بن بست‌ها مي تواند هر زماني كه 2 يا چند فرايند براي منابع محدودي رقابت مي كنند و فرايندها براي يافتن و حفظ يك منبع فراهم شده است اتفاق بيافتد. اگر يك فرايند براي منبعي، انتظار بكشد، هر منبعي كه آن حفظ براي فرايندهاي ديگر در دسترس نيستند. اگر فرايندي براي منبعي كه بوسيله فرايند ديگري حفظ شده است انتظار مي‌كشد، كه در بازكش در حال انتظار براي يكي از منابع نگهداري آن ما يك بنسبت داريم. هنگاميكه يك سيستم به اين وضعيت مي رسد، به طور مؤثر، بسته مي شود: و بايد مشكل را براي ادامه عملكرد حل كنيم.
4 شرط وجود دارد كه يك بن بست نياز دارد:
1- حذف متقابل: هر منبعي مي تواند به يك منبع خاص تخصيص يافته شود.
2- حفظ و انتظار: فرايندها مي توانند يك منبع و درخواست بيشتر حفظ كنند.
3- بدون پريامپشن: منابع نمي توانند بالاجبار از يك فرايند حذف شوند.
4- انتظار حلقوي: بايد يك زنجيره حلقوي از فرايند وجود داشته باشد هر انتظاري براي يك منبع نه بوسيله شماري از زنجيره‌هاي بعدي نزديك حفظ شده است.
به طور معمول 4 روش در ارتباط با بن بستها به كاربرده شده است
1- ناديده گرفتن مشكل
2- آشكار سازي بن بست
3- جلوگيري از بن بست
4- اجتناب از بن بست
ناديده گرفتن بن بستها آسانترين برنامه براي تكميل است. آشكار سازي بن بست تلاش مي كند تا بن بست ها را قرار دهد و حل كند. اجتناب از بن بست روشهايي را شرح مي دهد كه تلاش مي كند تا تعيين كند آيا يك بنبست در زماني كه يك منبع درخواست مي شود و نسبت به درخواستي در يك حالتي كه از بن بست اجتناب مي‌شود عكس عمل نشان مي دهد. اتفاق خواهد افتاد. جلوگيري از بن بست ساختن يك سيستمي در يك حالتي كه يكي از 4 شرط ضروري براي بن بست امكان پذير نباشد است. هر گروه راه حل متناسب با يك نوع خاص محيط است و فوايد و نقايص دارد. در اين مقاله ما به آشكار سازي بن بست كه شايع ترين راه حل بن بست تكميل شده است تمركز مي كنيم.
در سيستم‌هاي بانك‌ها اطلاعاتي توزيع شده، آشكار سازي بن بست خيلي پيچيده مي‌شود به عنوان يك نتيجه‌اي از بي ثباتي در وضعيت سيستم جهاني. اگر چه الگوريتم‌هاي آشكار سازي بن بست زيادي در سيستم هاي بانك اطلاعاتي توزيع شده مطرح شده است اكثر آنها به خاطر سربارهاي سيستم بالا غير عمل هستند.
2 روش اصلي در آشكار سازي بن بست توزيع شده شكل گرفته است. ابتدا يكي كه براي ساخت وضعيت يك سيستم جهاني است و دومي براي تلاش در جهت عبور از يك پيغام خاص از طريق ترانكش‌ هاي بلوكه شده به منظور آشنا ساختن يك چرخه بن بست است. يك روش از روش دومي آشكار سازي بن بست توزيع شده بر پايه دليل همان طور كه توسط چندي و مسيرا و هس مطرح شده است. تركيب اصلي اين متد اين است كه هيچ وضعيت سيستم جهاني مورد نياز نيست.
الگوريتم آشكار سازي بن بست كندي بر پايه احتمالي از طريق سايتهاي مختلف است. تنها فرايندهايي كه در مرز سايتهاي يافت مي شود مي تواند پيغام‌هاي بررسي را آغاز كند. الگوريتم كندي مي تواند براي آشكار سازي بن بست توزيع شده بر پايه بررسي كندي در [2] ارائه شد. به عنوان يك نتيجه از سربازهاي سيستم بالا كه در حفظ جدول وابستگي براي
...