مفاهیم پایه
تعریف 1-گراف- انتظار- برای (WFG): یک گراف جهتدار است که وابستگی بین فرایندها را نشان می دهد و در آن گره ها فرایندها و یالها نشان دهنده درخواست منابع است.
تعریف2- چرخه[1] بن بست: یک چرخه جهتدار در گراف- انتظار- برای (WFG) است.
تعریف3- بن بست دروغین: به بن بستی گفته می شود که در حقیقت وجود ندارد.
تعریف4- درستی الگوریتم های تشخیص بن بست توزیع شده: اثبات درستی الگوریتم های تشخیص
بن بست توزیع شده با 2 ویژگی زیر تعیین می شود:
- ویژگی پیشرفت (Progress): بدین معنی که هر بن بستی که واقع شود در نهایت باید تشخیص داده شود.
- ویژگی امنیت(Safety): اگر بن بستی توسط الگوریتم تشخیص داده شود، باید واقعاً وجود داشته باشد.
1-2- انواع مدلهای بن بست براساس سیستم تبادل پیام
براساس سیستم تبادل پیام، دو نوع بن بست وجود دارد:
* بن بست منبعی
* بن بست ارتباطی
در بن بستهای ارتباطی، پیامها منابعی هستند که فرایندها برای آن متنظراند. تفاوت اصلی بین بن بست منبعی و بن بست ارتباطی در این است که بن بست منبعی از شرایط AND استفاده می کند و بن بست ارتباطی از شرط OR با تعریف ذیل استفاده می کند:
1-3- انواع مدلهای بن بست براساس نوع درخواست منبع
تقسیم بندی مدلهای بن بست براساس سیستم تبادل پیام به دو نوع بن بست ارتباطی و منبع به منظور شناسایی الگوریتمهای تشخیص بن بست کافی نیست. بنابراین که ویژگی های بیشتری از این الگوریتمها مدنظر قرار گیرد. یکی از این ویژگی ها نوع درخواست منبع است. در این بخش سلسله مراتبی از مدلهای منبع که می تواند در تقسیم بندی الگوریتمها تشخیص بن بست مورد استفاده قرار گیرد و مبتنی بر مدل بن بست ارائه شده توسط Knapp است، ارائه می شود
[1] - Deadlock cycle
تشخیص بن بست در سیستم‌های توزیع شده