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