موضوع مقاله: الگوریتم‌های جلوگیری از بن‌بست | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم‌های جلوگیری از بن‌بست | مقدمه: در علم رایانه الگوریتم‌های جلوگیری از بن بست در برنامه‌های هم روند، زمانی که چندین فرایند باید به بیش از یک منبع مشترک دست یابند استفاده می‌شود. | ## بخش 1: الگوریتم‌های جلوگیری از بن‌بست | موقعیتی پیش میاید که هر فرایند به هر منبعی که نیاز دارد فرایند دیگر نیز به آن منبع نیازمند است. جلوگیری از قفل بازگشتی انحصار متقابل نه جلوگیری می‌کند از یک ریسه که چندین بار به قفل مشابه بیشتر از یکبار وارد شود بن بست توزیع شد بن بست‌های توزیع شده در رایانش توزیع‌شده زمانی که تراکنش توزیع شده یا کنترل همروندی استفاده می‌شود،اتفاق میفتد. بن بست‌های توزیع شده توسط ساخت نمودار سراسری (انتظار-برای) نیز از نمودارهای محلی (انتظار-برای) در تشخیص دهنده‌های بن بست یا با الگوریتم‌های توزیع شده مانند الگوریتم تعقیب لبه شناسایی می‌شوند. بن بست‌های فانتوم ،بن بست‌هایی هستند که در سیستم‌های توزیع شده به سبب تاخیر داخلی سیستم شناسایی شده‌اند. جلوگیری از بن بست درجاییکه قفل‌های بازگشتی است راه‌های بسیاری برای افزایش همسانی وجود دارد در غیر این صورت منجر به بن بست خواهد شد . برخی مثال‌ها مشمول: قفل سلسله مراتبی، قفل مرجع– شمارش و پیش دستی (استفاده به صورت ورژنی یا اجازه به انحراف داده‌ها زمانی که پیش دستی رخ می‌دهد) - الگوریتم نمودار(انتظار-برای) تمام این‌ها چرخه‌ای را دنبال می‌کنند که باعث به وجود آمدن بن بست می‌شود (شامل بن بست‌های موقتی) و الگوریتم‌های اکتشافی ،که به افزایش همسانی صددرصد از مکان‌هایی که در آن امکان وقوع بن بست وجود دارد نیاز ندارند. اما به جای سازش توسط حل آن‌ها در فضای کافی که (کارایی\ فوقانی) در مقایسه با همسانی است قابل قبول است. نظر به این که “وقتی دو قطار در تقاطع بهم نزدیک می‌شوند” جلوگیری (فقط-در-زمان) مانند این است شخصی در تقاطع با سوییچی ایستاده است که توسط آن اجازه می‌دهد فقط یک قطار وارد بزرگترین ریل شود که جلوتر از قطارهای در حال انتظار برود. برای قفل‌های غیر بازگشتی، یک قفل ممکن است فقط یک بار وارد شود (جایی که ریسه تنها دو بار بدون قفل شدن وارد می‌شود و باعث بن بست می‌شود. یا استثنا به سمت اجرای جلوگیری از انتظار چرخشی میرود.) برای قفل‌های بازگشتی فقط یک ریسه اجازه دارد که از قفل عبور کند. | ## بخش 2: الگوریتم‌های جلوگیری از بن‌بست | اگر ریسه دیگری وارد قفل شود باید منتظر شود تا ریسهٔ داخلی به تعداد دفعات مختلف وارد و کامل شود. اما دومی دوباره تعریف می‌شود که از از ماجرای بن بستی که اولی به آن آدرس نمی‌دهد جلوگیری کند. اگر ریسه دیگری وارد قفل شود باید منتظر شود تا ریسهٔ داخلی به صورت کامل به تعداد دفعات مختلف وارد شود و عبور کند. اما اگر تعداد ریسه‌هایی که وارد و قفل می‌شوند می‌شوند با تعداد قفل شده‌ها برابر باشد , یک ریسه به عنوان بزرگترین ریسه شناخته می‌شود و فقط آن اجازه اجرا دارد ( تعداد دفعاتی که وارد می‌شوند \ خارج شدن از قفل شمارش و پیگیری می کنید) تا کامل شود. بعد از آن که بزرگترین ریسه به اتمام رسید شرایط به زمانی که از منطق قفل بازگشتی استفاده می‌شود باز میگردد. و بزرگترین ریسه که وجود دارد: ۱- خودش را به وضعیتی تغییر می‌دهد که بزرگترین ریسه نیست ۲- به بقیه قفل‌کننده‌ها خبر می‌دهد که بقیه قفل هستند و ریسه‌های منتظر باید این وضعیت را دوباره بررسی نمایند. اگر ماجرای بن بست وجود داشته باشد ریسه بزرگ دیگری مشخص میگردد و از آن منطق پیروی مینماید. مسایلی که در بالا توضیح داده نشده است سر در گمی‌های بسیاری حول مسیله توقف وجود دارد. اما این منطق مسئله توقف را حل نمی‌کند چون شرایطی که قفل اتفاق میفتد شناخته شده‌است. دادن یک راه حل خاص (به جای راه حل‌های ضروری و عمومی دیگری که مسیله توقف نیاز دارد) هنوز این قفل‌کننده از تمام بن بست‌هایی که فقط از این منطق استفاده می‌کند جلوگیری می‌کند. | ## بخش 3: الگوریتم‌های جلوگیری از بن‌بست | اما اگر از ساز و کار بقیه قفل شدن‌ها استفاده کند قفلی که شروع شده‌است هیچ وقت باز نمی‌شود ( به جز زمانی که بدون بازشدن به صورت نامحدود با قفل به حلقه میفتد یا کد را خطا میزند و فراموش می‌کند بازشدن را فراخوانی کند در چنین شرایطی به بیرون میپرد) بن بست بسیار امکان‌پذیر است. برای افزایش این شرایط باید مسیله توقف را حل کنیم چون اگر با چنین شرایطی روبرو شود درین باره چیزی ندانسته و نمی‌تواند آن را تغییر دهد. مسیله بعدی مسیله آدرس ندادن به بن بست موقتی است (در واقع بن بست نیست اما کارایی را از بین میبرد) جایی که دو یا چند ریسه باهم قفل می‌شوند اما هم زمان ریسه‌ای که نامرتبط است در حال اجرا است. اما به دلیل نحوه کار شناسایی بن بست‌های توزیع شده برای تمام قفل‌ها و زیر مجموعه‌هایی که در آن‌ها نیست. ریسه نا مربوط که در حال اجراست باید قبل از اجرای منطق ریسه بزرگ کامل شده تا بن بست‌های موقتی را از بین ببرد. اگر ریسه نامربوط دیگری قبل از آن که اولین ریسه نامربوط وجود داشته باشد شروع به اجرا بکند دوره دیگری برای بن بست موقتی به وجود میاید. اگر این اتفاق پشت سر هم بیفتد ( به شدت نادر است ) بن بست موقتی ،تا دقیقاً زمانی‌که برنامه به وجود بیاید ادامه خواهد داشت. البته بقیه ریسه‌های نا مرتبط با ضمانت به اتمام رسیده‌اند ( چون ضمانت می‌شود که هر ریسه تا زمانی که کامل شود همیشه اجرا خواهد شد) توضیحات اضافی این مطلب توضیحات اضافی است، شامل منطق بیشتر برای افزایش همسانی جایی که بن بست‌های موقتی ممکن است رخ دهد. اما برای هر مرحله که منطق بیشتری اضافه مینماییم , به ابتدای آن بیشترافزوده می‌شود. دو مثال: گسترش ساز و کار قفل شدن ریسه بزرگ توزیع شده با توجه به زیر مجموعه‌هایی که برای قفل‌ها وجود دارد. | ## جمع‌بندی | الگوریتم نمودار (انتظار-برای) که تمام چرخه‌هایی که موجب بن بست می‌شود را دنبال می‌کند (شامل بن بست‌های موقتی نیز می‌شود) و الگوریتم سلسله مراتبی که صددرصد مکانهایی که احتمال بن بست موقتی وجود دارد نیازی به افزایش همسانی ندارد.