لینک فایل مقاله درباره تشخیص بن بست در سیستمهای توزیع شده -95 صفحه
مشخصات فایل
عنوان: مقاله درباره تشخیص بن بست در سیستمهای توزیع شده
قالب بندی: word
تعداد صفحات:95
محتویات
فهرست مطالب
عنوان صفحه
مقدمه................................................................................................................................................................................ 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
د
مقدمه
امروزه کمتر سیستمی را می توان یافت که روی یک کامپیوتر متمرکز باشد. رشد روزافزون استفاده از سیستمهای توزیع شده، اهمیت تحقیق و پژوهش در راستای حل موانع و مشکلات موجود در این سیستمها را بیشتر آشکار می نماید. از جمله سیستمهای توزیع شده می توان به بانکهای اطلاعاتی توزیع شده، سیستم عاملهای توزیع شده، و سیستمهای کارگزار موبایل اشاره نمود.
سیستم توزیع شده از مجموعه ای از فرآیندهایی که از طریق ارسال پیام با یکدیگر در ارتباط اند،تشکیل شده است.یکی از مسائل مهم در سیستمهای توزیع شده در راستای مدیریت منابع، تشخیص بن بست توزیع شده است. مدیریت منابع زمانی که فرایندهای درخواست کننده در سطح شبکه در مکانهای مختلف توزیع شده اند،فرایند تشخیص را نسبت به سیستمهای متمرکز، دشوارتر می نماید.
طی دهه اخیر الگوریتم های زیادی برای تشخیص بن بست در سیستم های توزیع شده ارائه شده است که تعداد زیادی از آنها موفق به تشخیص بن بست نمی شوند و یا بن بست هایی را گزارش می کنند که در واقع وجود ندارند و یا اینکه اثبات شده است که نادرست اند.
هدف از این تحقیق مطالعه و بررسی روشهای مختلف تشخیص بن بست در سیستمهای توزیع شده، شناسایی مشکلات، محدودیت های آنها و ارائه راه حل عملی مبتنی بر واقعیات موجود در سیستمهای توزیع شده در خصوص مشکلات شناسایی شده است.
فصل اول:
تشخیص بن بست در سیستم های توزیع شده
1-1- مفاهیم پایه
تعریف 1-گراف- انتظار- برای (WFG): یک گراف جهتدار است که وابستگی بین فرایندها را نشان می دهد و در آن گره ها فرایندها و یالها نشان دهنده درخواست منابع است.
تعریف2- چرخه[1] بن بست: یک چرخه جهتدار در گراف- انتظار- برای (WFG) است.
تعریف3- بن بست دروغین: به بن بستی گفته می شود که در حقیقت وجود ندارد.
تعریف4- درستی الگوریتم های تشخیص بن بست توزیع شده: اثبات درستی الگوریتم های تشخیص
بن بست توزیع شده با 2 ویژگی زیر تعیین می شود:
- ویژگی پیشرفت (Progress): بدین معنی که هر بن بستی که واقع شود در نهایت باید تشخیص داده شود.
- ویژگی امنیت(Safety): اگر بن بستی توسط الگوریتم تشخیص داده شود، باید واقعاً وجود داشته باشد.
1-2- انواع مدلهای بن بست براساس سیستم تبادل پیام
براساس سیستم تبادل پیام، دو نوع بن بست وجود دارد:
* بن بست منبعی
* بن بست ارتباطی
در بن بستهای ارتباطی، پیامها منابعی هستند که فرایندها برای آن متنظراند. تفاوت اصلی بین بن بست منبعی و بن بست ارتباطی در این است که بن بست منبعی از شرایط AND استفاده می کند و بن بست ارتباطی از شرط OR با تعریف ذیل استفاده می کند:
1-3- انواع مدلهای بن بست براساس نوع درخواست منبع
تقسیم بندی مدلهای بن بست براساس سیستم تبادل پیام به دو نوع بن بست ارتباطی و منبع به منظور شناسایی الگوریتمهای تشخیص بن بست کافی نیست. بنابراین که ویژگی های بیشتری از این الگوریتمها مدنظر قرار گیرد. یکی از این ویژگی ها نوع درخواست منبع است. در این بخش سلسله مراتبی از مدلهای منبع که می تواند در تقسیم بندی الگوریتمها تشخیص بن بست مورد استفاده قرار گیرد و مبتنی بر مدل بن بست ارائه شده توسط Knapp است، ارائه می شود.
1-3-1- مدل گراف- انتظار- برای
این گراف به کلاس گراف های جهت دار تعلق دارد. گره ها در این گراف برای مدل کردن فرایندها بکار می روند. یالهای جهتدار در گراف نشان دهنده روابط مسدود شدن بین فرایندها . یک گره با یک یال خارج شده از آن به یک فرایند مسدود شده تعلق دارد.
بن بست با یک چرخه در این گراف مشخص می شود. ارتباط بین بن بستها و این گراف در بخشهای زیر نشان داده شده است[13].
1-3-2- مدل تک- منبعی(One-Resource Model)
مدل تک منبعی، ساده ترین مدل درخواست منبع است. در این مدل یک فرایند تنها یک درخواست منبع در یک زمان می تواند داشته باشد،بدان معنی که ماکزیمم یال خروجی از یک گره در گراف-انتظار- برای برابر یک است.
برای یافتن بن بست در یک سیستم که مدل درخواست آن تک منبعی است، لازم است یک چرخه در گراف-انتظار-برای پیدا شود. یک الگوریتم ساده برای تشخیص بن بست براساس این مدل توسط میچل و مریت[2] است.
1-3-3- مدل AND
این مدل عمومی تر از مدل تک منبعی است. در این مدل یک به یک فرایند اجازه داده می شود که مجموعه ای از منابع را درخواست نماید. تا زمانی مسدود می ماند که همه منابعی را که درخواست نموده بود، به دست آورد به عبارتی فرایندی که نیاز به منابعی برای اجرا دارد، زمانی می تواند پیش رود که همه منابعش را به دست آورد.
همانند مدل تک منبعی برای یافتن بن بست در یک سیستم با مدل این مدل درخواست، لازم است یک چرخه در گراف-انتظار-برای پیدا شود. نمونه ای از این الگوریتمها توسط چندی- میسرا-هاس ، منساس و مانتز و اوبرمارک، ارائه شده است.
1-3-4- مدلOR
این مدل جالبی از مدل درخواست AND است. به آن مدل ارتباطی نیز می گویند. در این مدل به منظور تشخیص بن بست، تنها تشخیص یک چرخه در گراف-انتظار-برای کافی نیست، یافتن بن بست شامل پیدا کردن یک گره در گراف-انتظار-برای است.
فرایندی که نیاز به منابعی برای اجرا دارد،زمانی می تواند پیش رود که حداقل یکی از منابعش را به دست آورد.دلیلی که شرط OR برای بن بست ارتباطی استفاده شده است این است که اغلب ساختارهای کنترل توزیع شده غیرقطعی[2] هستند و یک فرایند ممکن است در انتظار یک پیام از چندین فرایند باشد.
1-3-5- مدل AND-OR
مدل AND و مدل OR هردو از مدل AND-OR مشتق شده اند. مفهوم اصلی این مدل این است که این نوع درخواست ترکیبی از و یا در درخواست منبع است. تصور کنیدa ،b ، c، d منابع هستند که در کامپیوتر های متفاوتی قرار دارند. درخواست به این شکلd and ((c or b) a and) امکان پذیر است. تشخیص بن بست در این مدل می تواند با تکرار تست برای مدل تشخیص OR با فرض اینکه بن بست یک مشخصه پایدار است، انجام شود.
1-3-6- مدل p-out-of-q
این مدل بدین معنی است که یک فرایند به طور همزمان درخواست q منبع را می نماید و تا زمانی که p منبع را بدست آورد،مسدود می ماند. این مدل نوع دیگر AND-OR است که ترکیبی از مدلهای OR و AND است به عنوان مثال(b OR c) AND q.
1-4- شرایط وجود بن بست
شرط وجود بن بست در یک سیستم با استفاده از مدل AND این است که یک چرخه وجود داشته باشد. در یک سیستم با شرط OR ، وجود چرخه ممکن است باعث بن بست بشود یا نشود. شرط وجود بن بست در سیستمی با استفاده از شرط OR، وجود یک گره[3] است. یک گره(k) شامل مجموع از گره ها است که برای هر گره a در k همه گره ها در k و تنها گره های در k ، از گره a قابل در دسترس باشند.
1-5- طبقه بندی الگوریتم های تشخیص بن بست توزیع شده
الگوریتم های تشخیص بن بست توزیع شده مطابق روشی که اطلاعات وضعیت سیستم نگهداری می شود و یا متدلوژِی که برای جستجو شرایط بن بست استفاده می شود طبقه بندی می شوند.
الگوریتم های تشخیص بن بست توزیع شده توسط Sighal[5] به 3 گروه زیر طبقه بندی شده است:
- متمرکز( Centralized)
- توزیع شده ( Distributed)
- سلسله مراتبی(Hierarchical)
1-5-1- الگوریتم های متمرکز برای تشخیص بن بست در سیستم های توزیع شده
در الگوریتم های متمرکز برای تشخیص بن بست مکانی طراحی شده که اغلب به آن سایت کنترل گفته می شود و مسئولیت نگهداری اطلاعات وضعیت کلی سیستم و جستجوی آن برای شرایط بن بست را برعهده دارد. اطلاعات وضعیت کلی سیستم از طریق پیگیری کردن اطلاعات وضعیت سیستم به طور پریودیک و بهنگام نمودن آن ، انجام می شود. هرزمان که وضعیت سیستم تغییر یابد، نیاز به محاسبات تشخیص بن بست است.
سایت مرکزی به عنوان یک سیستم عمومی مانیتور نیگ می تواند تلقی شود نوع بن بستی که می تواند تشخیص داده شود نیز متفاوت است. اگرچه برای سادگی اغلب الگوریتمها محدودیتی روی اطلاعات جمع آوری شده و الگوریتمی که برای جستجوبن بست به کار برده می شود، اعمال می نماید. به عنوان مثال جستجو برای چرخه به جای جستجو برای گره که منجر به محدود کردن نوعی بن بستی می شود که تشخیص داده می شود.
باتوجه به اینکه سایت کنترل دید کلی نسبت به تمام سیستم دارد، لذا سیاست حل بن بست نسبتاً آسان است. الگوریتم های متمرکز از لحاظ مفهومی ساده بوده و پیاده سازی آسانی دارند اما خیلی ناکارا و غیرقابل اطمینان می باشد.سایت مرکزی ناچار به اطلاع از همه عملیات درخواست آزاد کردن منابع در طول سیستم است. همچنین زمان پاسخ طولانی برای کاربر، سربار ارتباطی زیاد و ازدحام لینکهای ارتباطی در نزدیکی سایت مرکزی از جمله در مسائلی است که ناشی از سیستم های متمرکز می شود. در نتیجه منجر به سربارهای ارتباطی و محاسباتی در الگوریتم های تشخیص بن بست می شود.
1-5-2- انواع الگوریتم های توزیع شده تشخیص و حل بن بست
تشخیص بن بست شامل 2 کار اصلی است: نگهداری وضعیت سیستم در قالب گراف- انتظار- برای عمومی(GWFG) و جستجوی وضعیت سیستم برای وجود شرط بن بست (چرخه یا گره).
الگوریتم های تشخیص بن بست می توانند مطابق روشی که اطلاعات وضعیت سیستم نگهداری
می شود یا الگوریتم های تشخیص بن بست بکار برده می شود، طبقه بندی شوند.Sighal[5] الگوریتم های تشخیص بن بست را براساس متدلوژی مورد استفاده در جستجو به 3 نوع متمرکز، توزیع شده و سلسله مراتبی تقسیم نموده است.
Knapp[1] روش دیگری را جهت طبقه بندی الگوریتم های تشخیص بن بست ارائه نموده است. در این تقسیم بندی الگوریتم های توزیع شده برای تشخیص متمرکز بن بست به 4 گروه ذیل تقسیم می شود:
- تعقیب کردن یال(Edge Chasing )
- ماجراجویی مسیر(Path Pushing)
- محاسبات پخش شدن(Diffusing Computation)
- تشخیص وضعیت عمومی(Global state Detection)
در این بخش هرکدام از روشهای فوق توضیح داده می شود و در فصل بعد نمونه ای از الگوریتم های تشخیص و حل بن بست در هرکدام از گروه های فوق ارائه می گردد.
شکل1-1- سلسله مراتب الگوریتمهای تشخیص بن بست
1-5-2-1- الگوریتم های تعقیب کردن یال(Edge Chasing)
این کلاس از الگوریتم ها این نام را به دلیل روشی که برای جستجو چرخه در گراف وضعیت سیستم توزیع شده بکار می گیرد، گرفته اند.
در این الگوریتم ها یک پیام مخصوص که به آن کاوشگر(Prob) گفته می شود ، آغاز می شود و در طول یالها منتشر می شود به همین دلیل به آنها الگوریتم تعقیب کردن یال می گویند. اگر آغاز کننده پیام کاوشگر، در نهایت کاوشگری مطابق آنچه که خود آغاز کرده بود دریافت نماید، چرخه تشخیص داده می شود. بدلیل اینکه این کلاس از الگوریتم ها تنها می تواند چرخه ها را تشخیص دهند، لذا تنها قادر به حل مدل های بن بست با پیچیدگی زیاد و مدل AND هستند.
الگوریتم مبتنی بر الویت کاوشگر،توسعه ای از الگوریتم های تعقیب کردن یال هستند. از الویت برای کاهش پیامهای کاوشگر و حل بن بست استفاده می شود. چندین الگوریتم مبتنی بر الویت پیشنهاد شده است. از جمله الگوریتم میچل و مریت[2]، الگوریتم سینها و ناتارجان[4] که توسط چودهری[7] و همکارانش توسعه داده شد. تمامی این الگوریتمها برای مدل بن بست منبع منفرد طراحی شده اند.
1-5-2-2- الگوریتم های ماجراجویی مسیر( Path Pushing)
ایده اصلی این الگوریتم ها ، ساختن یک فرم ساده ای از گراف وضعیت عمومی سیستم در هر سایت است که برای تشخیص بن بست کافی است. زمانی که یک محاسبه بن بست آغاز می شود ،هر سایت اطلاعات وضعیت محلی را از همسایگان دریافت می نماید و گراف وضعیت محلی بهنگام می شود و سپس اطلاعات وی نیز به سایر همسایگان عبور داده می شود.این رویه تا زمانی که اغلب سایتها تصویر کامل و کافی از گراف وضعیت عمومی سیستم داشته باشند و بتوانند بن بست را اعلان نمایند یا اینکه اطمینان دهند که بن بستی وجود ندارد، تکرار می شود.
1-5-2-3- الگوریتم های محاسبات پخش شدن(Diffusing Computation)
در یک سیستم محاسبات پخش شدن می تواند به یک گراف جهتدار به گونه ای متناظر بشوند که هر گره نشان دهنده یک وظیفه[4] و هر یال نشان دهنده ارتباط بین دو وظیفه نهایی باشند. تصور شده است که یک گره آغازگر ریشه بدون یال ورودی بوده و محاسبات پراکندگی از آن انجام می شود وجود دارد.Dijikstra [28] به گره آغازکننده به دلیل ارتباط آن با بقیه گراف، عنوان محیط[5] را داده است. به
گره هایی به غیر از محیط، گره داخلی گفته می شود.پیامها از یک گره به بعد هایش در زمانی که سیگنالها در جهت عکس جهت یالها منتشر می شود، ارسال می شود. محاسبات پخش شدن به وسیله ارسال پیامها توسعه پیدا کرده و با دریافت سیگنالها جمع می شود. به همین دلیل به این نام گذاشته شده است. هر گره محاسبه پخش شدن با یک وضعیت طبیعی آغاز می شود. محیط، محاسبه را با ارسال پیامهایی به بعدهایش آغاز می نماید.در محاسبات پخش شدن، اولین پیامی که به بک گره ارسال می شود، پیام به کار گرفتن[6] گفته می شود و به آخرین پیامی که به وسیله یک گره فرستاده می شود که در پاسخ به پیاک بکار گرفتن است، سیگنال به کار گرفتن گفته می شود. به محض دریافت اولین پیام بعنان مثال پیامx یک گره وضعیت
طبیعی اش را ترک نموده و بکار گرفته می شود . یک گره درگیر شده داخلی آزاد است که پیامهایی را انتشار نماید شامل پیام درگیری به بعدش و آزاد است که سیگنالهایی را از بعدی هایش دریافت نماید. یک گره درگیر شده یک سیگنال درگیری به قبلی اش تنها زمانی ارسال می کند که سیگنال درگیری را از همه بعدی هایش دریافت نماید. پیام بکار گرفتن در جهت یالهای گراف ارسال می شود و سیگنال درگیر شدن در خلاف جهت یالهای گراف ارسال می شود.
یک فرایند در وضعیت طبیعی است اگر تفاضل تعداد ورودی های به یک گره از خروجی هایش صفر شود.محاسبات پخش شدن زمانی که ریشه به وضعیت طبیعی اش برگردد، خاتمه می یابد. یا بعبارتی زمانی که محاسبات پخش شدن به سمت ریشه جمع شود.
یک فرایند مسدود شده می تواند با آغاز یک محاسبه پخش شده، تعیین نماید که دچار بن بست شده است یا نه. اگر یک آغاز کننده پاسخ هایی را از همه پرس و جوهایی که ارسال نموده است دریافت نماید، دچار بن بست شده است. تعدادی الگوریتم تشخیص بن بست براساس محاسبه پخش شدن توسط Chandy و Misra[2] ارائه شده است.
1-5-2-4- تشخیص وضعیت عمومی(Global State Detection)
در این الگوریتم ها یک فرایند می تواند یک وضعیت عمومی سیستم را در حال محاسبه تعیین نماید. محاسبات تحتانی شامل مجموعه ای از پردازش ها است. فرایندها با ارسال پیام با یکدیگر ارتباط برقرار
می کنند. و این ارتباط ها توسط لایه تحتانی سیستم انجام می شود. وضعیت عمومی یک سیستم توزیع شده عبارتست از مجموعه ای از همه وضعیت های محلی فرایندها در زمان خاص. بنابراین وضعیت عمومی بطور تئوری براساس وضعیت محلی سیستم ساخته می شود . به منظور تشخیص بن بست ، وضعیت سیستم یک گراف- انتظار- برای است که به منظور تبادل اطلاعات گراف- انتظار- برای، زمانبندی شده است. یک فرایند در زمان خاصی دچار بن بست شده است اگر در گراف- انتظار- برای دچار بن بست شده باشد.
1-5-3- الگوریتم های سلسله مراتبی تشخیص بن بست
در الگوریتم های سلسله مراتبی جهت تشخیص بن بست توزیع شده، سایت ها به طور سلسله مراتبی سازماندهی می شود. هر سایت مسئول تشخیص بن بست هایی که خودش در آنها دخیل است و سایت هایی فرزندانش است. در اغلب سیستم هایی که بطور سلسله مراتبی سازماندهی شده اند الگوی دسترسی منبع محلی شده است به گونه ای از سایتهایی که متعلق اند به همان سایت پدر، بنابراین بازدهی می تواند بهینه شود اگر یک الگوریتم تشخیص بن بست سلسله مراتبی ،ساختار سلسله مراتبی از سیستم تحتانی اش را منعکس نماید.
یک وظیفه مسدود شده محاسبات بن بست را با ارسال یک پرس و جو به وظایف در یک مجموعه وابسته آغاز می نماید. یک وظیفه در حال اجرا همه پرس و جوها و پاسخ ها را نادیده می گیرد. به عبارت دیگر اگر محاسبات پراکندگی به یک وظیفه مسدود شده برسد، سپس وظیفه مسدود شده درگیر شده و در محاسبات مشارکت می کند. به یک پرس و جو زمانی که به یک وظیفه درگیر شده می رسد، پاسخ داده
می شود. همه پرس و جوهایی که آغاز شده اند، در صورتی که تشخیص چرخه می دهند که محاسبات پراکندگی خاتمه یابد و آغاز کننده به وضعیت طبیعی اش برگردد. متعاقباً آغاز کننده بن بست زده شده است اگر به وضعیت طبیعی اش بازگردد. نمونه ای از الگوریتم سلسله مراتبی توسطHo و Ramamoorthy [24] ارائه شده است.
فصل دوم:
مروری بر الگوریتم های تشخیص بن بست در
سیستم های توزیع شده
مقدمه
سیستم توزیع شده از مجموعه ای از فرایندهایی که از طریق ارسال پیام با یکدیگر در ارتباط اند، تشکیل شده است. بن بست به شرایطی گفته می شود که در آن مجموعه ای از پردازشگرها مسدود شده اند و هرکدام منتظر دیگری است تا منابعش را آزاد نماید.
تعداد زیادی از الگوریتم های تشخیص بن بست در سیستم های توزیع شده اثبات شده است که نادرست اند، دلیل آن عمدتاً عبارتست از نادیده گرفتن اثبات درستی ، استفاده از آرگومآنهای غیررسمی/ فرضی برای اثبات درستی، استفاده از تکنیک شبیه سازی برای نشان دادن درستی الگوریتم. آرگومآنهای غیررسمی منجر به خطا می شوند.اثبات های غیررسمی نسبتاً غیر قابل اطمینان هستند و خیلی از الگوریتمها که اینگونه توسط نویسندگان ادعا شده که درست اند، بعدها اثبات شده که نادرست اند. تعدادی از این الگوریتمها بعنوان نمونه در این فصل نشان داده می شود.
در ادامه این فصل تعدادی از الگوریتم های تشخیص بن بست در سیستم های توزیع شده در گروه های متمرکز، توزیع شده و سلسله مراتبی، مورد بررسی قرار گرفته و نحوه عملکرد آنها، مزایا و معایب ارائه
می گردد.
2-1- نمونه ای از الگوریتم متمرکز جهت تشخیص بن بست در سیستمها توزیع شده
2-1-1- الگوریتم هو- رامامورتی
الگوریتم هو-رامامورتی [24] دو الگوریتم که به آنها یک-مرحله ای[7] و دو- مرحله ای[8] گفته می شود، جهت تشخیص بن بست ارائه نمودند.پروتکلهای آنها قصد حل مشکلات بن بست در مدلهای AND را داشت، زیرا در آنها تنها چرخه ها برای تشخیص آنها تنها چرخه ها برای تشخیص بن بست جستجو می شوند،اگرچه این محدودیت، ضروری نیست. یک الگوریتم جستجو بن بست خیلی پیچیده می تواند در یک سایت کنترلی به منظور اداره نمودن مدلهای پیچیده بن بست طراحی شود.
در پروتکل دو-مرحله ای ، تشخیص بن بست هر سایت یک جدول وضعیتی برای همه وظایفی که در آن سایت آغاز شده اند، نگهداری می کند. جدول وضعیت هر وظیفه ای منابعی را که هر وظیفه بدست آورده است و منابعی که وظیفه منتظر آنها است را نگهداری می نماید. این سایت کنترلی بطور پریودیک جدول وضعیت همه سایت ها را جمع آوری می کند و وضعیت عمومی سیستم را می سازد.
اگر وضعیت عمومی سیستم شامل هیچ چرخه ای نباشد ، بنابراین بن بستی وجود ندارد در غیر اینصورت سایت مرکزی دوباره درخواست گزارش های جدول وضعیت را از هر سایت می نماید. تنها وظایف که در هر دو گزارش آمده اند برای ساختن فاز وضعیت عمومی سیستم بکار گرفته می شود . اگر همان چرخه دوباره ، در فاز دو وضعیت عمومی سیستم تشخیص داده شود ، سیستم دچار بن بست شده است. هو- مارامورتی ادعا نموده اند که یک دید سازگار از سیستم با استفاده از پروتکل تشخیص بن بست دو مرحله ای، تنظیم می شود. اگر چه jayannathan و vasudevan (25) ادعای آنها را با یک مثال نقض انکار نموده اند.
مثال آنها تشخیص بن بست نادرست را نشان می دهد. استفاده از دو مرحله گزارش احتمال تشخیص بن بست نادرست را کاهش می دهد ولی آن را حذف نمی کند. بعبارت دیگر پروتکل تشخیص بن بست یک مرحله ای، بن بست در یک مرحله ارتباطی تشخیص می دهد. دو جدول تحت عنوان جدول وضعیت های منابع و وظیفه ها در هر سایتی نگهداری می شوند و توسط سایت کنترلی طراحی شده ،گردآوری می شوند. اثبات درستی پروتکل تشخیص بن بست یک مرحله ای توسط هو-مارامورتی ارائه شده است. بن بست نادرستی توسط این پروتکل تشخیص داده نمی شود زیرا ناسازگاری ها با استفاده از اطلاعات جمع آوری شده دو جدول وضعیت از بین می رود. در این الگوریتم تمامی بن بست ها سرانجام بوسیله پروتکل بدلیل مشخصه پایدار بودن بن بست ها تشخیص داده خواهد شد. پروتکل یک مرحله ای از پروتکل دو مرحله ای سریعتر است و نیاز به تعداد پیام های کمتری دارد. اما نیاز به حافظه بیشتری برای نگهداری جداول وضعیت در هر سایت و همینطور برای تبادل دو جدول وضعیت در هر مرحله ارتباط دارند .
2-2- نمونه هایی از الگوریتم های تشخیص بن بست سلسله مراتبی
2-2-1- الگوریتم منساس- مانتز
این الگوریتم یک الگوریتم سلسله مراتبی تشخیص بن بست است که برای بانک های اطلاعاتی توزیع شده ارائه شد. در آن بانک اطلاعاتی به مجموعه از زیر مجموعه های بانک اطلاعاتی تقسیم می شود . قفل کردو و کنترل های بن بست در ساختار درخت سازماندهی می شوند. هر کنترلر برگ یک زیرمجموعه را اداره می نماید، در حالیکه کنترلرهایغیربرگ مسئول تشخیص بن بست هستند. یک کنترلر برگ بخشی از گراف کاهش یافته را نگهداری می کند که کنترلر آن را اداره می نماید.
یک کنترلر غیر-برگ اطلاعاتی را شامل کنترلرهای بچه هایش را نگهداری می کند و مسئول تشخیص بن بست هایی که تنها شامل کنترلرهای بچه هایشاند، می باشد. یک کنترلر غیر-برگ، مراقب تغییرات مانند تخصیص، انتظار و رها کردن منبع کنترلرهای بچه هایش است. این کار می تواند بطور پریودیک انجام شود. بعد از هر بهنگام سازی گراف عمومی ، تشخیص بن بست توطی یک گره غیر برگ انجام می شود. این الگوریتم برای مدل AND طراحی شده است و بدنبال چرخه می گردد(26).
2-2-2- الگوریتم هو-رامامورتی
[1] - Deadlock cycle
[2] - None deterministic
[3] - knot
[4] - Task
[5] - Environment
[6] - Engaging
[7] - One-phase
[8] -Two-phase
کلمات کلیدی : مقاله درباره تشخیص بن بست در سیستمهای توزیع شده, تشخیص بن بست در سیستمهای توزیع ,انواع مدلهای بن‌بست بر اساس سیستم تبادل پیام,انواع مدلهای
در این سایت هیچ فایلی برای فروش قرار نمی گیرد. برای پشتیبانی و خرید فایل به سایت اصلی فروشنده مراجعه بفرمائید:
لینک دریافت فایل از سایت اصلی
لینک منبع :لینک فایل مقاله درباره تشخیص بن بست در سیستمهای توزیع شده -95 صفحه