الگوریتم‌های جلوگیری از بن‌بست

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

بن بست توزیع شد

بن بست‌های توزیع شده در رایانش توزیع‌شده زمانی که تراکنش توزیع شده یا کنترل همروندی استفاده می‌شود،اتفاق میفتد. بن بست‌های توزیع شده توسط ساخت نمودار سراسری (انتظار-برای) نیز از نمودارهای محلی (انتظار-برای) در تشخیص دهنده‌های بن بست یا با الگوریتم‌های توزیع شده مانند الگوریتم تعقیب لبه شناسایی می‌شوند.
بن بست‌های فانتوم ،بن بست‌هایی هستند که در سیستم‌های توزیع شده به سبب تاخیر داخلی سیستم شناسایی شده‌اند. اما در واقع در زمان شناسایی دیگر وجود ندارند.

مسایلی که در بالا توضیح داده نشده است

سر در گمی‌های بسیاری حول مسیله توقف وجود دارد. اما این منطق مسئله توقف را حل نمی‌کند چون شرایطی که قفل اتفاق میفتد شناخته شده‌است. دادن یک راه حل خاص (به جای راه حل‌های ضروری و عمومی دیگری که مسیله توقف نیاز دارد) هنوز این قفل‌کننده از تمام بن بست‌هایی که فقط از این منطق استفاده می‌کند جلوگیری می‌کند. اما اگر از ساز و کار بقیه قفل شدن‌ها استفاده کند قفلی که شروع شده‌است هیچ وقت باز نمی‌شود ( به جز زمانی که بدون بازشدن به صورت نامحدود با قفل به حلقه میفتد یا کد را خطا میزند و فراموش می‌کند بازشدن را فراخوانی کند در چنین شرایطی به بیرون میپرد) بن بست بسیار امکان‌پذیر است. برای افزایش این شرایط باید مسیله توقف را حل کنیم چون اگر با چنین شرایطی روبرو شود درین باره چیزی ندانسته و نمی‌تواند آن را تغییر دهد.
مسیله بعدی مسیله آدرس ندادن به بن بست موقتی است (در واقع بن بست نیست اما کارایی را از بین میبرد) جایی که دو یا چند ریسه باهم قفل می‌شوند اما هم زمان ریسه‌ای که نامرتبط است در حال اجرا است. این بن بست‌های موقتی منحصراً ممکن است ریسه در حال اجرا را با خود داشته باشند. تا همسانی را افزایش دهند. اما به دلیل نحوه کار شناسایی بن بست‌های توزیع شده برای تمام قفل‌ها و زیر مجموعه‌هایی که در آن‌ها نیست. ریسه نا مربوط که در حال اجراست باید قبل از اجرای منطق ریسه بزرگ کامل شده تا بن بست‌های موقتی را از بین ببرد.
همانطور که در بالا ماجرای قفل-زنده موقتی را میبینید. اگر ریسه نامربوط دیگری قبل از آن که اولین ریسه نامربوط وجود داشته باشد شروع به اجرا بکند دوره دیگری برای بن بست موقتی به وجود میاید. اگر این اتفاق پشت سر هم بیفتد ( به شدت نادر است ) بن بست موقتی ،تا دقیقاً زمانی‌که برنامه به وجود بیاید ادامه خواهد داشت. البته بقیه ریسه‌های نا مرتبط با ضمانت به اتمام رسیده‌اند ( چون ضمانت می‌شود که هر ریسه تا زمانی که کامل شود همیشه اجرا خواهد شد)

توضیحات اضافی

این مطلب توضیحات اضافی است، شامل منطق بیشتر برای افزایش همسانی جایی که بن بست‌های موقتی ممکن است رخ دهد. اما برای هر مرحله که منطق بیشتری اضافه مینماییم , به ابتدای آن بیشترافزوده می‌شود.
دو مثال: گسترش ساز و کار قفل شدن ریسه بزرگ توزیع شده با توجه به زیر مجموعه‌هایی که برای قفل‌ها وجود دارد. الگوریتم نمودار (انتظار-برای) که تمام چرخه‌هایی که موجب بن بست می‌شود را دنبال می‌کند (شامل بن بست‌های موقتی نیز می‌شود) و الگوریتم سلسله مراتبی که صددرصد مکانهایی که احتمال بن بست موقتی وجود دارد نیازی به افزایش همسانی ندارد. اما به جای سازش با اینکه آن‌ها در فضای کافی که کارایی/ فوقانی در مقایسه با همسانی قابل قبول باشد حل نماییم( برای مثال: هر فرایندی که در دسترس است در راستای پیدا کردن چرخه‌های بن بست کمتر از تعداد فرایندها + ۱ عمق کار محاسبه مینماییم)