الگوریتمپیغام به ازای هر ورودی/خروجیتاخیر قبل از ورودیمسایل

مرکزی سازی شده

۳

۲

نقص در هماهنگ کننده

توزیع شده

۲(n-1)

۲(n-1)

نقص همه پروسه ها

حلقه نشانه

۱ تا ∞

۰ تا n-1

نشانه گم شده، شکست پروسه

به منظور مقایسه با جزئیات الگوریتم‌ها، ما می‌توانیم به مشاهده سایر خصوصیات الگوریتم‌های ذکر شده در جدول ۳-۱ بپردازیم. این موارد در جدول ۳-۱ به منظور مقایسه الگوریتم‌ها ذکر شده‌اند: تعداد پیغام‌های مورد نیاز به ازای ورود/خروج از منطقه بحرانی، تاخیر قبل از ورود و همچنین مسایل عمده مربوط به هر الگوریتم ]۳۷[.
ما می‌دانیم که نشانه‌های زمانی برپایه ساعت لامپورت به هر پیغام اختصاص می‌یابند. در زمینه انحصار متقابل، ساعت‌های لامپورت بدین ترتیب عمل می‌کنند: هر پروسه یک ساعت عددی مدرج با مقدار اولیه ۰ را حفظ می‌کند. هر وقت پروسه‌ای بخواهد به منطقه بحرانی دسترسی یابد، به آن درخواست یک برچسب زمانی اختصاص داده می‌شود که یکی بیشتر از مقدار ساعت است. پروسه درخواست دارای برچسب زمانی را برای تعیین اینکه آیا می‌تواند به منطقه بحرانی دسترسی یابد یا خیر به سایر پروسه‌ها ارسال کند. هروقت پروسه‌ای یک درخواست دارای برچسب زمانی از پروسه‌ای دیگر که به دنبال اجازه دستیابی به منطقه بحرانی است دریافت می‌کند، پروسه ساعت خود را به حداکثر مقدار فعلی‌اش و برچسب زمانی درخواست به روز رسانی می‌کند]۴۲[.
قابلیت اطمینان یک معیار خیلی مهم برای راه حل‌های اکثر مسایل محافظت از منابع در شرایط واقعی می‌باشد. تعریف پذیرفته شده قابلیت اطمیان در حیطه انحصار متقابل زمانی است که در آن یک سیستم هیچ نقص و شکستی نداشته و یا قادر است کار خود را در هر شرایطی ادامه دهد]۶۵[.
در ادامه، به توصیف مدل سیستمی کلی پرداخته و مروری خواهیم داشت بر روی الگوریتم ریکارت-آگراوالا (RA[152]) که بهترین الگوریتم انحصار متقابل توزیع شده شناخته شده می‌باشد ]۶۵[.
الگوریتم RA و الگوریتم ارائه شده توسط لامپورت مدل پیش‌رو را در نظر می‌گیرند. تعداد N پروسه در سیستم وجود دارند. پروسه‌ها فقط از طریق ارسال پیام‌های همزمان در کل یک شبکه ارتباطی با یکدیگر ارتباط برقرار می‌کنند، که بدون خطا بوده، و زمان‌های ارسال پیغامی که ممکن است متفاوت باشند. فرض بر این است که پروسه‌ها به درستی کار می‌کنند. بر خلاف الگوریتم RA اما مشابه الگوریتم لامپورت، ما کانال‌های FIFO را در شبکه ارتباطی خود مفروض می‌داریم. بدون از دست دادن اصل کلی، ما فرض می‌کنیم که یک پروسه واحد در یک سایت یا گره در نمودار سیستمی شبکه اجرا می‌شود. بدین ترتیب، واژه‌های پروسه، سایت و گره را می‌توان به جای یکدیگر به کار برد.
یک پروسه با ارسال دستور “REQUEST” درخواست خود مبنی بر دسترسی به منطقه بحرانی را ارسال کرده و قبل از وارد شدن به آن منطقه بحرانی منتظر پاسخ‌های مناسب می‌ماند. در حالیکه یک پروسه در حال انتظار برای وارد شدن به CS خود است، نمی‌تواند درخواست دیگری ارسال کرده یا وارد CS دیگری شود. به هر “REQUEST” برای دسترسی به CS یک اولویت اختصاص داده می‌شود. و “REQUEST” های دسترسی به CS باید به منظور کاهش اولویت برای انحصار متقابل عادلانه همگی تایید شوند. اولویت یا شناسایی کننده، یا ReqID یک درخواست به صورت ReqID برابر است با (ترتیب شماره,PID) تعریف می‌گردد، که در آن شماره ترتیب یک عدد ترتیب اختصاصی محلی برای درخواست، و PID همان شناسایی کننده پروسه است. شماره ترتیب بدین صورت تعیین می‌گردد: هر پروسه بالاترین عدد ترتیب دیده شده (HSNS) تا به حال را، در یک HSNS متغیر محلی ذخیره می‌کند. وقتی یک پروسه یک درخواست ارسال می‌کند، از یک عدد ترتیب استفاده می‌کند که یکی بیشتر از مقدار HSNS است.
این الگوریتم از دو نوع پیغام استفاده می‌کند: “REQUEST” و REPLY. به عنوان ساختار داده، هر پروسه Pi از متغیرهای عدد صحیح محلی زیر استفاده می‌کند:
My_Sequence_Numberi, ReplyCounti, and HSNSi
الگوریتم RA در شکل ۳-۱ نمایش داده شد. همه رویه‌ها در این الگوریتم به صورت ذره‌ای انجام می‌شوند. فقط پروسه‌های با اولویت بالاتری که درخواست دسترسی به منطقه بحرانی را داده‌اند پیام‌های REPLY ارسالی توسط پروسه را مسدود می‌کنند. بدین ترتیب، وقتی یک پروسه پیغام‌های REPLY به همه درخواست‌های معوقه ارسال می‌کند، پروسه دارای بالاترین اولویت بعدی آخرین پیغام REPLY مورد نیاز را دریافت کرده و وارد CS می‌شود. اجرای درخواست‌های CS در این الگوریتم همیشه به ترتیب اولویت کاهشی است.
برای هر دسترسی به CS، دقیقا (N-1)2 پیغام وجود دارند: (N-1 REQUEST) و (N-1 REPLY). این الگوریتم عادلانه و ایمن است. هرچند، این الگوریتم دارای معایبی است، مانند داشتن قابلیت بالایی برای بروز اشتباه، داشتن یک نقطه شکست در هر پروسه و تنگنا داشتن سیستم. همچنین دارای قدرت موازی سازی کمی است. از میان این معایب، دو مورد اهمیت بیشتری به نسبت سایرین دارند، چرا که در صورتی که اتفاق بیافتند، منجر به شکست کل سیستم می‌شوند. اگر هر کدام از پروسه‌ها از کار بیافتد، همه اطلاعات شامل درخواست‌های پروسه‌ای که در صف قرار دارند و پرچم‌های مربوط به منابع از دست می‌روند. اما دو مساله دیگر فقط بر روی کارایی و سرعت سیستم تاثیر می‌گذارند.
شکل ‏۳‑۱ – : الگوریتم توزیع شده ریکارت و آگراوالا
یک “REQUEST” ارسال شده توسط پروسه Pi با عدد ترتیب x با بهره گرفتن از شناسه درخواستش مبنادهی می‌شود، بدین صورت: Ri,x. اولویت Ri;x به صورت (x, i) نشان می‌دهیم، که به صورت Pr(Ri,x) هم نشان داده می‌شود. عدد ترتیب x هر وقت هیچ ابهامی وجود نداشته باشد حذف می‌شود، و می‌گوییم که یک درخواست Ri دارای اولویت Pr(Ri) می‌باشد. از این عبارت در کل این روش استفاده شده است. وقتی گفته می‌شود دو “REQUEST” همزمان هستند که برای هر کدام از پروسه‌های درخواست کننده، “REQUEST” صادر شده توسط پروسه دیگر پس از درخواستی که توسط این پروسه ارسال شده بود دریافت گردد.
Ri و Rj در صورتی همزمان محسوب می‌شوند که “REQUEST” مربوط به Ri پس از اینکه Rj درخواست خود را ارسال کرد دریافت گردد. هر درخواست Ri که توسط Pi ارسال شده باشد دارای یک مجموعه همزمانی به نام CSeti است، که مجموعه آن “REQUEST” های Rj است که با Ri همزمان هستند. همچنین CSeti شامل Ri هم می‌شود.
همچنین، می‌دانیم که Ri، Ri، Rj}U{Ri} همگام است با CSeti = {Rj | Ri. مشاهده می کنید که رابطه “همگام است با” به صورت متقارن تعریف می‌گردد.
الگوریتم ارائه شده در ]۶۵[ همان مدل مورد استفاده در RA را در نظر می‌گیرد. همچنین فرض بر این است که کانال‌های شبکه از نوع FIFO می‌باشند. پروسه‌ای یک صف حاوی “REQUEST” ها را به ترتیب اولویت‌های دریافت شده توسط پروسه پس از ارسال آخرین “REQUEST” ایجاد می‌کند. این صف، که به آن صف درخواست‌های محلی ([۱۵۳]LRQ) گفته می‌شود، فقط حاوی “REQUEST” های همزمان است. الگوریتم جدید از پنج نوع پیغام استفاده می کند: “REQUEST”، REPLY، IN-REGION، AYA (Are You Alive)، NEWEPOACH، FLUSH، و بااختصاص هوشمندانه اهداف چندگانه به هر کدام به صرفه‌جویی دست می‌یابد. بالاخص، این صرفه‌جویی‌ها با مشاهدات کلیدی زیر به دست می‌آیند.
همه درخواست‌ها در کل مشابه الگوریتم RA بر اساس اولویت ترتیب‌دهی می‌شوند. یک پروسه دریافت کننده پیغام “REQUEST” می‌تواند به صورت آنی تعیین کند که آیا پروسه درخواست دهنده یا خودش باید اجازه ورود اول به منطقه بحرانی را داشته باشند یا خیر.


فرم در حال بارگذاری ...

کلیه مطالب این سایت فاقد اعتبار و از رده خارج است. تعطیل کامل
مداحی های محرم