تقسیم بندی مدلهای بن بست براساس سیستم تبادل پیام به دو نوع بن بست ارتباطی و منبع به منظور شناسایی الگوریتمهای تشخیص بن بست کافی نیست. بنابراین که ویژگی های بیشتری از این الگوریتمها مدنظر قرار گیرد. یکی از این ویژگی ها نوع درخواست منبع است. در این بخش سلسله مراتبی از مدلهای منبع که می تواند در تقسیم بندی الگوریتمها تشخیص بن بست مورد استفاده قرار گیرد و مبتنی بر مدل بن بست ارائه شده توسط Knapp است، ارائه می شود.
1-3-1- مدل گراف- انتظار- برای
این گراف به کلاس گراف های جهت دار تعلق دارد. گره ها در این گراف برای مدل کردن فرایندها بکار می روند. یالهای جهتدار در گراف نشان دهنده روابط مسدود شدن بین فرایندها . یک گره با یک یال خارج شده از آن به یک فرایند مسدود شده تعلق دارد.
بن بست با یک چرخه در این گراف مشخص می شود. ارتباط بین بن بستها و این گراف در بخشهای زیر نشان داده شده است[13].
1-3-2- مدل تک- منبعی(One-Resource Model)
مدل تک منبعی، ساده ترین مدل درخواست منبع است. در این مدل یک فرایند تنها یک درخواست منبع در یک زمان می تواند داشته باشد،بدان معنی که ماکزیمم یال خروجی از یک گره در گراف-انتظار- برای برابر یک است.
برای یافتن بن بست در یک سیستم که مدل درخواست آن تک منبعی است، لازم است یک چرخه در گراف-انتظار-برای پیدا شود. یک الگوریتم ساده برای تشخیص بن بست براساس این مدل توسط میچل و مریت[2] است.
1-3-3- مدل AND
این مدل عمومی تر از مدل تک منبعی است. در این مدل یک به یک فرایند اجازه داده می شود که مجموعه ای از منابع را درخواست نماید. تا زمانی مسدود می ماند که همه منابعی را که درخواست نموده بود، به دست آورد به عبارتی فرایندی که نیاز به منابعی برای اجرا دارد، زمانی می تواند پیش رود که همه منابعش را به دست آورد.
همانند مدل تک منبعی برای یافتن بن بست در یک سیستم با مدل این مدل درخواست، لازم است یک چرخه در گراف-انتظار-برای پیدا شود. نمونه ای از این الگوریتمها توسط چندی- میسرا-هاس ، منساس و مانتز و اوبرمارک، ارائه شده است.
1-3-4- مدلOR
این مدل جالبی از مدل درخواست AND است. به آن مدل ارتباطی نیز می گویند. در این مدل به منظور تشخیص بن بست، تنها تشخیص یک چرخه در گراف-انتظار-برای کافی نیست، یافتن بن بست شامل پیدا کردن یک گره در گراف-انتظار-برای است.
فرایندی که نیاز به منابعی برای اجرا دارد،زمانی می تواند پیش رود که حداقل یکی از منابعش را به دست آورد.دلیلی که شرط OR برای بن بست ارتباطی استفاده شده است این است که اغلب ساختارهای کنترل توزیع شده غیرقطعی[1] هستند و یک فرایند ممکن است در انتظار یک پیام از چندین فرایند باشد.
[1] - None deterministic
مقدمه 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
شامل 97 صفحه فایل word
دانلود پایان نامه تشخیص بن بست در سیستمهای توزیع شده