بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
مقدمه
- حفظ جامعیت یک منبع مشترک از طریق پی در پی سازی درخواستهای استفاده از آن
▫برای مثال: مدیریت Directory در یک سیستم توزیع شده
- در محیط متمرکز، به واسطه وجود حافظه مشترک، از طریق متغیر مشترک (سمافور) قابل حل است. ولی در سیستم توزیع شده، هم منابع مشترک و هم کاربران توزیع شده وجود دارند و البته حافظه مشترکی هم وجود ندارد.
اسلاید 2 :
دسته بندی الگوریتمها
- الگوریتمهای نامهره بنیاد
▫حداقل 2 دور تبادل پیغام نیاز است.
هر سایت یک Assertion را ارزیابی میکند که اگر درست بود وارد Critical Section میشود.
- الگوریتمهای مهره بنیاد
▫با تضمین اینکه همواره يک مهره داریم و این مهره مادامی که در اختیار پردازهای است به پردازه دیگر داده نمیشود.
▫در واقع هر زمان که مهره به پردازهای رسید، نوبت او برای ورود به ناحیه بحرانی است.
اسلاید 3 :
تعاریف اولیه
- مدل سیستم:
▫در صورت وجود تعدادی درخواست CS در یک سایت، درخواستها به ترتیب در یک صف قرار گرفته و یکباره سرویس داده میشوند.
▫
- حالت هر سایت از دیدگاه CS:
▫Requesting CS ç سایت بیکار است.
▫Executing CS
▫Idle
اسلاید 4 :
ملزومات الگوریتم های M.E.
- علاوه بر ممانعت دو جانبه در هر الگوریتم، موارد زیر نیز اهمیت دارند:
▫عاری بودن از بن بست - Deadlock
▫عاری بودن از قحطی - Starvation
انتظار بینهایت !!!!
▫Fairness
درخواستهای ورود به CS به ترتیب وارد CS شوند.
▫تحمل خطا
اسلاید 5 :
معیارهای کارآیی
- معیارهای سنجش کارآیی برای الگوریتمهای M.E.:
▫تعداد پیغامهای لازم برای ورود به CS
▫تاخیر همگامی: فاصله زمانی بین خروج یک سایت و ورود سایت دیگر به CS
▫زمان پاسخ: از لحظه ارسال درخواست تا پایان اجرای CS
▫Throughput: نرخ درخواست های اجرا شده CS
▫
اسلاید 6 :
الگوریتم لمپورت
- Ri: سایت هایی که برای ورود به CS باید از آنها مجوز گرفت.
▫در این الگوریتم:
▫
- هرسایت یک request_queuei دارد که درخواستها به ترتیب زمان مهر در آن قرار دارند.
- فرض بر وجود FIFO Order بین هر زوج سایت داریم.
اسلاید 7 :
الگوریتم لمپورت (درخواست ورود به CS)
.1ارسال REQUEST (tsi, i) به همه سایتهای موجود در Ri و قرار دادن درخواست در صف محلی سایت.
.2با رسیدن درخواست ورود REQUEST (tsi, i) در سایت Sj ، Sj یک پیغام REPLY مهمور به Si فرستاده و درخواست را در request_queuej میگذارد.
اسلاید 8 :
الگوریتم لمپورت (اجرای CS)
- با فراهم آمدن شرایط زیر، هر سایت Si وارد CS میشود:
.1Si درخواست (پيغام) با زمان مهر بزرگتر از (tsi,i) از همه دیگر سایتها دریافت کرده باشد.
.2درخواست Si در سَرِ صفِ request_queuei باشد.
اسلاید 9 :
الگوریتم لمپورت (خروج از CS)
- Si درخواست خود را از سر صف برداشته و یک پیغام RELEASE مهمور به همه سایتهای موجود در Ri خود میفرستد.
- وقتی Sj پیغام RELEASE را از Si دریافت کرد، درخواست Si را از صف خود حذف میکند.
حال درخواست یک سایت که سر صف قرار دارد بر اساس شرایط اسلاید قبل میتواند باعث ورود یک سایت به CS شود.
قضیه: روش لمپورت ممانعت دوجانبه را فراهم میکند.
اثبات: با تناقض (Contradiction) ....................
اسلاید 10 :
مثال