دانلود پاورپوینت Distributed Mutual Exclusion

توضیحات محصول

دانلود پاورپوینت Distributed Mutual Exclusion با فرمت ppt ودر 41 اسلاید قابل ویرایش

قسمتی از متن پاورپوینت Distributed Mutual Exclusion

مقدمه

•حفظ جامعیت یک منبع مشترک از طریق پی در پی سازی درخواست‌های استفاده از آن

▫برای مثال: مدیریت Directory در یک سیستم توزیع شده

•در محیط متمرکز، به واسطه وجود حافظه مشترک، از طریق متغیر مشترک (سمافور) قابل حل است. ولی در سیستم توزیع شده، هم منابع مشترک و هم کاربران توزیع شده وجود دارند و البته حافظه مشترکی هم وجود ندارد.

دسته بندی الگوریتم‌ها

•الگوریتم‌های نامهره بنیاد

▫حداقل 2 دور تبادل پیغام نیاز است.

–هر سایت یک Assertion را ارزیابی می‌کند که اگر درست بود وارد Critical Section می‌شود.

•الگوریتم‌های مهره بنیاد

▫با تضمین اینکه همواره يک مهره داریم و این مهره مادامی که در اختیار پردازه‌ای است به پردازه دیگر داده نمی‌شود.

▫در واقع هر زمان که مهره به پردازه‌ای رسید، نوبت او برای ورود به ناحیه بحرانی است.

تعاریف اولیه

•مدل سیستم:

▫در صورت وجود تعدادی درخواست CS در یک سایت، درخواست‌ها به ترتیب در یک صف قرار گرفته و یکباره سرویس داده می‌شوند.

▫

•حالت هر سایت از دیدگاه CS:

▫Requesting CS ç سایت بیکار است.

▫Executing CS

▫Idle

ملزومات الگوریتم های M.E.

•علاوه بر ممانعت دو جانبه در هر الگوریتم، موارد زیر نیز اهمیت دارند:

▫عاری بودن از بن بست – Deadlock

▫عاری بودن از قحطی – Starvation

–انتظار بینهایت !!!!

▫Fairness

–درخواست‌های ورود به CS به ترتیب وارد CS شوند.

▫تحمل خطا

معیارهای کارآیی

•معیارهای سنجش کارآیی برای الگوریتم‌های M.E.:

▫تعداد پیغام‌های لازم برای ورود به CS

▫تاخیر همگامی: فاصله زمانی بین خروج یک سایت و ورود سایت دیگر به CS

▫زمان پاسخ: از لحظه ارسال درخواست تا پایان اجرای CS

▫Throughput: نرخ درخواست های اجرا شده CS

الگوريتم عمومي ! (Generalized)

•به هر درخواست CS يك زمان مهر مبتني بر روش لمپورت الصاق مي‌شود. از زمان‌مهر براي اولويت‌دهي درخواست‌هاي برخوردار استفاده مي‌شود.

•درخواست CS:

▫هر سايت پيغام ممهور REQUEST را به همه سايت‌ها در مجموعه درخواست (Ri) خود مي‌فرستد.

▫با رسيدن REQUEST، Si:

–آن را در صف درخواست‌ها (مرتب بر اساس زمان مهر) قرار مي‌دهد.

–اگر CSSTAT نشان دهد كه CS خالي است، GRANT را به سر صف مي‌فرستد و آن‌را از سر صف برمي‌دارد. اگر گيرنده GRANT در Sti است سپس CSSTAT نشان مي‌دهد كه آن سايت در CS است.

الگوريتم عمومي (Generalized)-ادامه

•اجراي CS

▫در صورتيكه GRANT را از همه سايت‌هاي Ri دريافت كرده باشد.

•خروج از CS

▫در خروج يك RELEASE را به مجموعه Ii (inform set) مي فرستد.

▫با رسيدن RELEASE، Si:

–CSSTAT را به آزاد مقداردهی می‌کند.

–اگر صفش غير خالي است، GRANT را به عنصر سر صف ارسال و آن را از صف حذف مي‌كند. اگر گيرنده در Sti است، CSSTAT را به آن سايت مقداردهي مي‌كند.

–آن‌قدر تكرار مي‌كند تا CSSTAT نشان دهد كه يك سايت در CS است و يا صف خالي است.