فهرست مطالب
مقدمه............................................................................................... 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