تشخیص بن بست در سیستمهای توزیع شده پروژه دوره کارشناسی مهندسی نرم‌افزار ارائه شده به: گروه علمی کامپیوترفهرست مطالب عنوان صفحه مقدمه 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- سلسله مراتب الگوریتمهای تشخیص بن بست 6 شکل 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 مقدمه امروزه کمتر سیستمی را می توان یافت که روی یک کامپیوتر متمرکز باشد. رشد روزافزون استفاده از سیستمهای توزیع شده، اهمیت تحقیق و پژوهش در راستای حل موانع و مشکلات موجود در این سیستمها را بیشتر آشکار می نماید. از جمله سیستمهای توزیع شده می توان به بانکهای اطلاعاتی توزیع شده، سیستم عاملهای توزیع شده، و سیستمهای کارگزار موبایل اشاره نمود. سیستم توزیع شده از مجموعه ای از فرآیندهایی که از طریق ارسال پیام با یکدیگر در ارتباط اند،تشکیل شده است.یکی از مسائل مهم در سیستمهای توزیع شده در راستای مدیریت منابع، تشخیص بن بست توزیع شده است. مدیریت منابع زمانی که فرایندهای درخواست کننده در سطح شبکه در مکانهای مختلف توزیع شده اند،فرایند تشخیص را نسبت به سیستمهای متمرکز، دشوارتر می نماید. طی دهه اخیر الگوریتم های زیادی برای تشخیص بن بست در سیستم های توزیع شده ارائه شده است که تعداد زیادی از آنها موفق به تشخیص بن بست نمی شوند و یا بن بست هایی را گزارش می کنند که در واقع وجود ندارند و یا اینکه اثبات شده است که نادرست اند. هدف از این تحقیق مطالعه و بررسی روشهای مختلف تشخیص بن بست در سیستمهای توزیع شده، شناسایی مشکلات، محدودیت های آنها و ارائه راه حل عملی مبتنی بر واقعیات موجود در سیستمهای توزیع شده در خصوص مشکلات شناسایی شده است.