فرمت:word۱- مفاهیم پایهتعریف ۱-گراف- انتظار- برای (WFG): یک گراف جهتدار است که وابستگی بین فرایندها را نشان می دهد و در آن گره ها فرایندها و یالها نشان دهنده درخواست منابع است.تعریف۲- چرخه[۱] بن بست: یک چرخه جهتدار در گراف- انتظار- برای (WFG) است.تعریف۳– بن بست دروغین: به بن بستی گفته می شود که در حقیقت وجود ندارد.تعریف۴– درستی الگوریتم های تشخیص بن بست توزیع شده: اثبات درستی الگوریتم های تشخیصبن بست توزیع شده با ۲ ویژگی زیر تعیین می شود: ویژگی پیشرفت (Progress): بدین معنی که هر بن بستی که واقع شود در نهایت باید تشخیص داده شود. ویژگی امنیت(Safety): اگر بن بستی توسط الگوریتم تشخیص داده شود، باید واقعاً وجود داشته باشد.۱-۲- انواع مدلهای بن بست براساس سیستم تبادل پیامبراساس سیستم تبادل پیام، دو نوع بن بست وجود دارد:* بن بست منبعی* بن بست ارتباطیدر بن بستهای ارتباطی، پیامها منابعی هستند که فرایندها برای آن متنظراند. تفاوت اصلی بین بن بست منبعی و بن بست ارتباطی در این است که بن بست منبعی از شرایط AND استفاده می کند و بن بست ارتباطی از شرط OR با تعریف ذیل استفاده می کند:۱-۳- انواع مدلهای بن بست براساس نوع درخواست منبعتقسیم بندی مدلهای بن بست براساس سیستم تبادل پیام به دو نوع بن بست ارتباطی و منبع به منظور شناسایی الگوریتمهای تشخیص بن بست کافی نیست. بنابراین که ویژگی های بیشتری از این الگوریتمها مدنظر قرار گیرد. یکی از این ویژگی ها نوع درخواست منبع است. در این بخش سلسله مراتبی از مدلهای منبع که می تواند در تقسیم بندی الگوریتمها تشخیص بن بست مورد استفاده قرار گیرد و مبتنی بر مدل بن بست ارائه شده توسط Knapp است، ارائه می شود.۱-۳-۱- مدل گراف- انتظار- برایاین گراف به کلاس گراف های جهت دار تعلق دارد. گره ها در این گراف برای مدل کردن فرایندها بکار می روند. یالهای جهتدار در گراف نشان دهنده روابط مسدود شدن بین فرایندها . یک گره با یک یال خارج شده از آن به یک فرایند مسدود شده تعلق دارد.بن بست با یک چرخه در این گراف مشخص می شود. ارتباط بین بن بستها و این گراف در بخشهای زیر نشان داده شده است[۱۳].۱-۳-۲- مدل تک- منبعی(One-Resource Model)مدل تک منبعی، ساده ترین مدل درخواست منبع است. در این مدل یک فرایند تنها یک درخواست منبع در یک زمان می تواند داشته باشد،بدان معنی که ماکزیمم یال خروجی از یک گره در گراف-انتظار- برای برابر یک است.برای یافتن بن بست در یک سیستم که مدل درخواست آن تک منبعی است، لازم است یک چرخه در گراف-انتظار-برای پیدا شود. یک الگوریتم ساده برای تشخیص بن بست براساس این مدل توسط میچل و مریت[۲] است.۱-۳-۳- مدل ANDاین مدل عمومی تر از مدل تک منبعی است. در این مدل یک به یک فرایند اجازه داده می شود که مجموعه ای از منابع را درخواست نماید. تا زمانی مسدود می ماند که همه منابعی را که درخواست نموده بود، به دست آورد به عبارتی فرایندی که نیاز به منابعی برای اجرا دارد، زمانی می تواند پیش رود که همه منابعش را به دست آورد.همانند مدل تک منبعی برای یافتن بن بست در یک سیستم با مدل این مدل درخواست، لازم است یک چرخه در گراف-انتظار-برای پیدا شود. نمونه ای از این الگوریتمها توسط چندی- میسرا-هاس ، منساس و مانتز و اوبرمارک، ارائه شده است.۱-۳-۴- مدلORاین مدل جالبی از مدل درخواست AND است. به آن مدل ارتباطی نیز می گویند. در این مدل به منظور تشخیص بن بست، تنها تشخیص یک چرخه در گراف-انتظار-برای کافی نیست، یافتن بن بست شامل پیدا کردن یک گره در گراف-انتظار-برای است.فرایندی که نیاز به منابعی برای اجرا دارد،زمانی می تواند پیش رود که حداقل یکی از منابعش را به دست آورد.دلیلی که شرط OR برای بن بست ارتباطی استفاده شده است این است که اغلب ساختارهای کنترل توزیع شده غیرقطعی[۲] هستند و یک فرایند ممکن است در انتظار یک پیام از چندین فرایند باشد.۱-۳-۵- مدل AND-ORمدل AND و مدل OR هردو از مدل AND-OR مشتق شده اند. مفهوم اصلی این مدل این است که این نوع درخواست ترکیبی از و یا در درخواست منبع است. تصور کنیدa ،b ، c، d منابع هستند که در کامپیوتر های متفاوتی قرار دارند. درخواست به این شکلd and ((c or b) a and) امکان پذیر است. تشخیص بن بست در این مدل می تواند با تکرار تست برای مدل تشخیص OR با فرض اینکه بن بست یک مشخصه پایدار است، انجام شود.۱-۳-۶- مدل p-out-of-qاین مدل بدین معنی است که یک فرایند به طور همزمان درخواست q منبع را می نماید و تا زمانی که p منبع را بدست آورد،مسدود می ماند. این مدل نوع دیگر AND-OR است که ترکیبی از مدلهای OR و AND است به عنوان مثال(b OR c) AND q