خوش آمد گویی www.Pro3.ir

تشخیص بن بست در سیتم های توزیع


تشخیص بن بست در سیتم های توزیع

تعداد صفحات :100صفحه قیمت : رایگان معرفی به دوستان
-1- مفاهیم پایه
تعریف 1-گراف- انتظار- برای (WFG): یک گراف جهتدار است که وابستگی بین فرایندها را نشان می دهد و در آن گره ها فرایندها و یالها نشان دهنده درخواست منابع است.
تعریف2- چرخه  بن بست: یک چرخه جهتدار در گراف- انتظار- برای (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 است. به آن مدل ارتباطی نیز می گویند. در این مدل به منظور تشخیص بن بست، تنها تشخیص یک چرخه در گراف-انتظار-برای کافی نیست، یافتن  بن بست شامل پیدا کردن یک گره در گراف-انتظار-برای است.

499 بار دانلود دانلود
قیمت : رایگان


مشابه ها

نظر کاربران


ارسال پیام
 
  
 
 
کد را وارد کنید