لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه:21
فهرست مطالب
چکیده
1- مقدمه
2- پیش زمینه
3- مشکل بن بست عمومی
1-3- انتظار برای نمودار
2-3- نمونه‌‌‌های بن بست متفاوت
4- الگوریتمهای آشکار سازی بن بست توزیع شده
1-4- راه حل بن بست
2-4- روش تایم اوت (زمان سپری شده)
3-4- گروه بندی الگوریتمهای توزیع شده
4-4- الگوریتم های هل دادن (فشار) مسیر (جریان کار)
5-4- الگوریتم هایی بر پایه تحقیق
1-5-4- الگوریتمهای جستجوی لبه
2-5-4- منتشر کردن محاسبه
5- خلاصه ای از الگوریتمهای آشکار سازی بن بست توزیع شده
آشکار سازی بن بست یکی از جدی ترین مسائل در سیستم عاملهای توزیع شده است. در این مقاله ما یک بررسی وضعیت هنری الگوریتمهای آشکار سازی بن بست توزیع شده که در ادبیات مطرح شده است ارائه می کنیم. در این حوزه ما یک نگاهی به مقالات آشنا درباره این عنوان داریم و تلاش می کنیم تا معروف ترین الگوریتم ها را گروه بندی می کنیم.
- مقدمه
در طول دهه گذشته سیستمهای محاسبه گر پیشرفت سریعی داشته اند که تأثیر زیادی بر سیستم عاملهای توزیع شده دارد. در حالیکه سیستمهای تجاری به تدریج پیشرفت می کنند، چالشهای جدید بوسیله ارتباط گسترده جهانی سیستمهای کامپیوتری وضع شده است.
این جریان یک نیاز رشد کننده‌‌ای برای راه حلهای توزیع شده با مقیاس بالا ایجاد می‌کند. در آینده، سیستم عاملهای توزیع شده باید صدها و حتی هزاران سایت و میلیونها مراجع را حمایت کنند و بنابراین با چالشهای بزرگی در ارتباط با اجرا، در دسترس بودن و مدیریت مواجه خواهند شد. یکی از چالشهایی که ما باید حل کنیم در این حوزه مشکل بن بست است. همچنین نسبت یکی از جدی ترین مشکلات در سیستم های برنامه ریزی رایج چند کاره است.
بقیه مقاله مثل زیر سازمان دهی شد. بخش 2 مختصرا بن بست و حوزه آن در سیستم عاملهای توزیع شده را توزیع می دهد.
در حالیکه بخش 3 یک شرحی از مشکل بن بست ارائه می دهد و 2 الگوی بن بست که به طور کلی در سیستمهای بانک اطلاعاتی توزیع شده به کار می رود. یک گروه بندی از الگوریتمهای توزیع شده برای این الگوها و نماینده‌های گروه های مختلف در بخش 4 شرح داده شده است. نهایتا، ما در بخش 5 خلاصه می کنیم، در حالیکه بخش 6 مرجهای ما را توصیف می کند.
2- پیش زمینه
در این بخش ما تلاش می کنیم تا نگاهی بر مقالات بررسی که بوسیله دیگران در روش آشکار سازی بن بست ارائه شده است داشته باشیم.
متون بن بست رسما یک بن بست را به عنوان یک مجموعه فرایندی که بن بست است، اگر هر فرایند در مجموعه منتظر یک رویدادی است که تنها فرایند دیگری در مجموعه می تواند موجب شود. تعریف می کند. [2 و 1]. یک تعریف غیررسمی تر این است که بن بستها می تواند هر زمانی که 2 یا چند فرایند برای منابع محدودی رقابت می کنند و فرایندها برای یافتن و حفظ یک منبع فراهم شده است اتفاق بیافتد. اگر یک فرایند برای منبعی، انتظار بکشد، هر منبعی که آن حفظ برای فرایندهای دیگر در دسترس نیستند. اگر فرایندی برای منبعی که بوسیله فرایند دیگری حفظ شده است انتظار می‌کشد، که در بازکش در حال انتظار برای یکی از منابع نگهداری آن ما یک بنسبت داریم. هنگامیکه یک سیستم به این وضعیت می رسد، به طور مؤثر، بسته می شود: و باید مشکل را برای ادامه عملکرد حل کنیم.
4 شرط وجود دارد که یک بن بست نیاز دارد:
1- حذف متقابل: هر منبعی می تواند به یک منبع خاص تخصیص یافته شود.
2- حفظ و انتظار: فرایندها می توانند یک منبع و درخواست بیشتر حفظ کنند.
3- بدون پریامپشن: منابع نمی توانند بالاجبار از یک فرایند حذف شوند.
4- انتظار حلقوی: باید یک زنجیره حلقوی از فرایند وجود داشته باشد هر انتظاری برای یک منبع نه بوسیله شماری از زنجیره‌های بعدی نزدیک حفظ شده است.
به طور معمول 4 روش در ارتباط با بن بستها به کاربرده شده است
1- نادیده گرفتن مشکل
2- آشکار سازی بن بست
3- جلوگیری از بن بست
4- اجتناب از بن بست
نادیده گرفتن بن بستها آسانترین برنامه برای تکمیل است. آشکار سازی بن بست تلاش می کند تا بن بست ها را قرار دهد و حل کند. اجتناب از بن بست روشهایی را شرح می دهد که تلاش می کند تا تعیین کند آیا یک بنبست در زمانی که یک منبع درخواست می شود و نسبت به درخواستی در یک حالتی که از بن بست اجتناب می‌شود عکس عمل نشان می دهد. اتفاق خواهد افتاد. جلوگیری از بن بست ساختن یک سیستمی در یک حالتی که یکی از 4 شرط ضروری برای بن بست امکان پذیر نباشد است. هر گروه راه حل متناسب با یک نوع خاص محیط است و فواید و نقایص دارد. در این مقاله ما به آشکار سازی بن بست که شایع ترین راه حل بن بست تکمیل شده است تمرکز می کنیم.
در سیستمهای بانک‌ها اطلاعاتی توزیع شده، آشکار سازی بن بست خیلی پیچیده می‌شود به عنوان یک نتیجه‌ای از بی ثباتی در وضعیت سیستم جهانی. اگر چه الگوریتمهای آشکار سازی بن بست زیادی در سیستم های بانک اطلاعاتی توزیع شده مطرح شده است اکثر آنها به خاطر سربارهای سیستم بالا غیر عمل هستند.
2 روش اصلی در آشکار سازی بن بست توزیع شده شکل گرفته است. ابتدا یکی که برای ساخت وضعیت یک سیستم جهانی است و دومی برای تلاش در جهت عبور از یک پیغام خاص از طریق ترانکش های بلوکه شده به منظور آشنا ساختن یک چرخه بن بست است. یک روش از روش دومی آشکار سازی بن بست توزیع شده بر پایه دلیل همان طور که توسط چندی و مسیرا و هس مطرح شده است. ترکیب اصلی این متد این است که هیچ وضعیت سیستم جهانی مورد نیاز نیست.
الگوریتم آشکار سازی بن بست کندی بر پایه احتمالی از طریق سایتهای مختلف است. تنها فرایندهایی که در مرز سایتهای یافت می شود می تواند پیغام‌های بررسی را آغاز کند. الگوریتم کندی می تواند برای آشکار سازی بن بست توزیع شده بر پایه بررسی کندی در [2] ارائه شد. به عنوان یک نتیجه از سربازهای سیستم بالا که در حفظ جدول وابستگی برای mpa ایجاد شد انتظار می رود عملکرد سیستم یک شکل اساسی داشته باشد. یک نسخه پشرقه از MPA (EPA) با جایگزینی جدول استقلال (وابستگی) با یک انتظار برای نوشتن تعریف شد.
مقاله بررسی آشکار سازی بن بست در سیستم عامل توزیع شده
