فایل تشخیص بن بست در سیستمهای توزیع شده
توضیحات
فایل تشخیص بن بست در سیستمهای توزیع شدهفهرست مطالب مقدمه............................................................................................... 1 فصل اول: تشخیص بن بست در سیستمهای توزیع شده......................................... 2 1-1- مفاهیم پایه................................................................................................. 3 1-2- انواع مدلهای بنبست بر اساس سیستم تبادل پیام............................................. 3 1-3- انواع مدلهای بنبست بر اساس نوع درخواست.............................................. 3 1-4- شرایط وجود بنبست......................................................................... 5 1-5- طبقهبندی الگوریتمهای تشخیص بنبست...................................................... 5 فصل دوم: مروری بر الگوریتمهای تشخیص بنبست............................................. 9 مقدمه............................................................................................... 10 2-1- نمونهای از الگوریتم متمرکز جهت تشخیص بنبست در سیستمهای توزیعشده............... 10 2-1-1- الگوریتم هو- رامامورتی.......................................................................................... 10 2-2- نمونهای از الگوریتمهای تشخیص بنبست سلسلهمراتبی...................................... 11 2-2-1- الگوریتم منساس – مانتر................................................................... 11 2-2-2- الگوایتم هو – رامامورثی.................................................................. 11 2-3- نمونههایی از الگوریتمهای توزیعشده......................................................... 11 2-3-1- الگوریتم تشخیص بنبست چندی – مسیرا – هاس......................................... 11 2-3-2- الگوریتم محاسبه پخش کردن چندی – مسیرا – هاس..................................... 12 2-3-3- الگوریتم براچا – توگ.................................................................... 13 2-3-4- الگوریتم منساس و مانتز2-3-5- الگوریتم ابرمارک...................................... 13 2-3-5- الگوریتم ابرمارک......................................................................... 14 2-3-6- الگوریتم بدالض........................................................................... 15 فصل سوم: مروری بر الگوریتمهای تشخیص بنبست توزیع شده تعقیب یال................... 20 مقدمه............................................................................................... 21 3-1- بررسی الگوریتمهای تشخیص بنبست تعقیب یال............................................ 22 3-1-1- الگوریتم میچل و مریت................................................................... 22 3-1-2- الگوریتم سینها و ناتارجان................................................................ 23 3-1-3- الگوریتم چودهاری – کوهلر – استنکویچ و توسلی..................................... 23 3-1-4- الگوریتم سینقال و شمکالیانی............................................................ 24 3-1-5- تشخیص بنبست توزیع شده و حل آن بر اساس ساعتهای سختافزاری................. 24 3-2- ارائه روشی برای حذف بنبست نادرست در الگوریتمهای تشخیص بنبست................ 25 الف 3-3- نتیجهگیری.................................................................................. 27 فصل چهارم: الگوریتمهای تشخیص بنبست توزیع شده تحمل خطاپذیر....................... 29 مقدمه.............................................................................................. 30 4-1- مروری بر الگوریتمهای تحملپذیر خطا جهت تشخیص بنبست............................ 31 4-2- معرفی مدل سیستم تشخیص خرابی بر اساس شاخص زمان اتصال........................ 33 4-3- یک الگوریتم تشخیص بنبست توزیع شده تحملپذیر خطا.................................. 34 4-4- اثبات درستی الگوریتم...................................................................... 37 4-5- نتیجهگیری.................................................................................. 38 فصل پنجم: تشخیص و حل بنبست در سیستمهای نماینده موبایل.............................. 39 مقدمه............................................................................................... 40 5-1- معرفی سیستمهای نماینده موبایل(نسل آینده سیستمهای توزیع شده).......................... 41 5-2- تشخیص بنبست توزیعشده در سیستمهای نماینده موبایل.................................... 41 5-3- معایب الگوریتم اصلی و مشکلات کارایی الگوریتم....................................... 44 5-4- الگوریتم تشخیص بنبست توزیع شده مبتنی بر اولویت بهبودیافته......................... 47 5-4-1- آنالیز کارایی الگوریتم بهبودیافته.......................................................................................... 48 5-4-2- اثبات درستی الگوریتم................................................................... 49 5-5- نتیجهگیری.................................................................................. 50 نتیجهگیری........................................................................................ 51 فهرست منابع..................................................................................... 53 پیوستها......................................................................................... 55 فهرست جداول جدول 2-1- مقایسه الگوریتم های بررسی شده تشخیص بن بست............................... 17 جدول 2-2- مقایسه کارایی الگوریتم های بررسی شده.......................................... 19 جدول 3-1- مقایسه مدل های الگوریتم های بررسی شده کلاس تعقیب یال..................... 27 جدول3-2- بررسی صحت الگوریتم های بررسی شده......................................... 28 فهرست شکلها شکل1-1- سلسله مراتب الگوریتمهای تشخیص بن بست........................................ 26 شکل 3-1- وضعیت فرآیندها در گراف-انتظار-برای............................................. 26 شکل 4-1- تشخیص دهنده خطا بر اساس CTI................................................. 34 شکل 4-2- مثالی از تشخیص خرابی، فلشها نشان دهنده درخواستهای منابع و خط چین نشان دهنده پیام آزادشدن منبع است. .......................... 36 شکل5-1- شمای کلی یک محیط میزبان در سیستم نماینده موبایل................................ 42 شکل 5-2- یک چرخه بن بست با درخواست قفل محلی، مربعها نشان دهنده نماینده های مصرف کننده و دایره ها نشان دهنده منابع بوده و فلشهای جهت دار نشان دهنده درخواست قفل محلی است.......................................... 44 شکل 5-3- مثالی از یک سیستم نماینده موبایل با دوچرخه بن بست: چرخه 1 شامل منابع 1، 2، 4 و چرخه دو شامل منابع 2، 4، 5، 3........... 46