پاورپوینت محدودیت متقابل

***3

محرومیت  متقابل:( هم زمانی در سیستم های درهم ریخته)

سیستم های درگیر با فرایند های چند گانه  اغلب به صورت برنامه ریزی شده به

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

 آوردن  تحت اطلا عات مربوط خاص  در ساختار هاست  . این وارد یک واحد

 بحرانی می شود برای رسیدن به محرومیت متقابل  و تضمین می کنند که دیگر          فرایند ها  استفاد خواهند کرد  از ساختارهای اظلا عاتی مربوط به صورت هم        زماندر سیستم های پردازشگر منفرد ، مناطق بحرانی  حفظ می کنند مخابره ها  را  ، مانیتور ها  را ساختار مشابه را . ما اکنون به مثال های  چند از چگونگی  مناطق بحرانی و محرومیت متقابل که می توانند در سیستم های بخش مورد استفاده قرار می گیرند نگاه می کنیم برای یک رده بندی و فهرست  منابع دیگر روش ها RAYNAL را 

ببندید دیگر کاها را از ElabbadiوAgrabbadliوchandyوsandersمورد بحث  قرار می گیرند

***5

1.2.3 یک الگوریتم مرکزی:

 مستقیم ترین روش برای رسیدن  به محرومیت های متقابل در یک سیستم  بخشی برای وانمود کردن اینکه چگونه این در یک سیستم با یک پردازشگر انجام می شود  می باشد یک فرایند انتخاب می شود به عنوان همراه ، که یک فرایند  می خواهد وارد یک منطقه بحرانی شود  این یک پیام در خواست می فرستد برای بیان همراهی در منطقه  بحرانی این می خواهد وارد شود و اجازه می خواهد . اگردیگر فرایند ها در منطقه بحرانی  باشند همراه کننده یک پاسخ را برای اجاره به عقب می فرستند، همان طور در شکل 8-3 دیده می شود  وقتی پاسخ رسید ، درخواست  فرایند وارد یک منطقه بحرانی می شود . اکنون فرض می کنیم  که دیگر فرایند ، 2 در شکل8-3 ، برای اجازه برای ورود به منطقه بحرانی  مشابه است همراهی می کنند می داند که یک فرایند متفاوت در منطقه بحرانی وجود دارد بنابراین  این نمی تواند  اجازه اهدا را بدهد در شکل (b)8-3  ، همراه کننده فقط  اجتناب می کند از پاسخ  . بنابراین  فرایند 2 متوقف می شود که منتظر یک پاسخ است . این می تواند یک پاسخ را بفرستد  که می گوید اجازه داده شده  ، روش ورودی .

***6

این ردیف ها درخواست می شوند  از 2 برای دادن زمان  وقتی فرایند (1) در منطقه بحرانی وجود دارد . این یک پیام را برای اجازه  همراهی می فرستد که دسترس می باشد همانطور که در شکل (2)8-3 است. همراه کننده اولین آیتم را برای صف های در خواست های آن دارد و می فرستد یک پیام  اهدایی را . اگر فرایند متوقف شود  این غیر متوقف است و وارد منطقه بحرانی  می شود . اگر یک  پیام واضع اجازه فرستاده ، فرایند برای دریافت  ترافیک وتردد می شود یا بعداً  متوقف می شود. روش ، وقتی اهدایی را  ببندد . این می تواند وارد منظقه بحرانی شود . این آسان است برای دیدن ضمانت های الگوریتم  در محرومیت متقابل همراه کننده  فقط اجازه می دهد یک فرایند در زمان  برای هر منطقه بحرانیاین در خواست می کند و اجازه می دهد به اهدایی در ترتیبی در آن دریافت شوند . فرایند منتظر نیست .این طرح آسان است برای اجرا ، و نیازی  دارد فقط به 3 پیام در هر استفاده از منطقه بحرانی (  در خواست – اهدا – رهایی)  این می تواند  مورد استفاده قرار گیرد  برای منبع بیشتر  نسبت به فقط کنترول مناطق بحرانی.رویکرد مرکزی کردن خلاصه است .

همراه کننده یک منطقه منفرد و شکسته از نقص است . پس اگر شکسته شو، کل سیستم ممکن است از بین برود . اگر فرایند ها به صورت فرمان متوقف شوند  بعد از ساخت یک درخواست  . آنها می توانند  تشخیص دهند  یک همراه کننده مرده را  از یک ملیارد اجازه از  آنجایی که در هر دو مورد پیامی بر نمی گردد  بعلاوه در یک سیستم  بزرگ  یک هراه کننده منفرد می تواندیک تنگنای اجرایی باشد.

***7

  3.2.2الگوریتم در هم ریخته :

 داشتن یک نقطه شکست به صورت مکرر غیر قابل پذیرش است پس محققان محدودیت متقابل در هم ریخته را جستجو  کرده اند  لمپورت در سال 1978 همزمان ساعتی را برای اولین بار ارائه داد. رسکارت و آگرا والا در سال 1981 آن را مناسب تر  ساختند  . در این جا بخشها و روش های آنها را مورد بحث قرار خواهیم داد . الگوریتم ریکارت و آگراوا لا نیز دارند به اینکه یک ترتیب یکی از همه  حوادث  در ستم داشته باشند . برای هر جفت از حوادث  مثل پیامها  ، این باید غیر مبهم باشد که یک بار اولین بار اتفاق می افتد 

الگوریتم لمپورت  در بخش3.1.1    یک روش برای رسیدن به این ترتیب است و     می تواند مورد استفاده قرار گیرد برای ورود به یک  منطقه بحرانی این یک پیام را شامل  نام منطقه  بحرانی شامل می شود  ،  این میخواهد وارد شود. این دو فرایند آن و زمان جاری آن است  . این پیام رابه همه  دیگر فرایند ها می فرستند که شامل خودش می باشد . فرستادن پیام به نظر می رسد قابل خواندن باشد که هر پیام پذیرفته است. تبادل گروهی اگر در دسترس باشد می تواند مورد استفاده قرار  گیرد به جای پیامهای فردی.

 وقتی یک فرایند یک پیام درخواست را دریافت میکند  از دیگر فرایند ها عمل آن بستگی دارد  به حالت  آن با  محدود کردن  برای منطقه بحرانی که در پیام  نامگذاری شده است .  

***8

این موارد تشخیص داده شده اند:

1. اگردریافت گر در منطقه بحرانی نباشد و نخواهد وارد شود این یک پیام okبه عقب می فرستد به فرستنده.

2. اگر دریافت گر در نقطه بحرانی باشد این پاسخ نمی دهد در  عوض این صفوف در خواست می کنند

3. اگر دریافت گر  می خواهد وارد منطقه  بحرانی شود اما هنوز انجام نشده .  این مقایسه می کند زمان رادر پیام ورودی با یک محتوی در پیامی که هرکس می فرستد. پایین ترین آن برنده می شوند .  اگر پیام دریافتی پایین تر باشد دریافت گر یک پیام ok  به عقب می فرستد. اگر پیام یک زمان پایین تر داشته باشد دریافت گر صفوف ورودی را درخواست می کندو چیزی نمی فرستد.

 بعد از فرستادن  در خواست ها  پرسش اجازه برای ورود  به  یک منطقه بحرانی یک فرایند به عقب فرستاده می شود  و منتظر  می ماند  تا کسی اجازه   را بدهد . بزودی همه اجازه ها  در آن است . این ممکن است منطقه  بحرانی وارد شود . وقتی این  منطقه  بحرانی مجمد داشته باشد  . این پیام های ok  را می فرستد به همه فرایند ها  روی ردیف  آن  و آنها را از همه حذف می کند  . اجازه دهید تلاش  کنیم برای درک  اینکه  چرا   الگوریتم کار می کند اگر متضادی وجود ندارد  این به روشنی کار می کند.

علاوه فرض کنید  که فرایند تلاش  دارد برای درک منطقه بحرانی مشابه  به صورت همزمان  همانطور که در شکل (9-3) نشان داده می شود: