بن‌بست (علوم رایانه)

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

هر دو پروسهٔ P1 و P2 برای ادامه‌یافتن به منابع نیاز دارند. P1 در حالی که جزو R2 است، به منبع اضافی R1 نیاز دارد. P2 هم در حالی که جزو R1 است، به منبع اضافی R2 نیاز دارد. پس هیچ‌یک از دو پروسه ادامه نخواهند یافت.

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

در سیستم ارتباطاتی بن‌بست اساساً ناشی از سیگنال‌های از دست رفته یا خراب شده‌است و مربوط به رقابت بر سر منابع نمی‌شود.

شرایط لازم

یک وضعیت بن‌بست در رابطه با منابع فقط و فقط زمانی رخ می‌دهد که تمام شرایط زیر همزمان در یک سیستم برقرار باشند:

انحصار متقابل: حداقل یک منبع باید در یک وضعیت غیرقابل اشتراک نگه داشته شود، در غیر این صورت نمی‌توان فرایندها را از استفاده از منابع در هنگام لزوم بازداشت. فقط یک فرایند می‌تواند در هر لحظه از منبع استفاده کند.

نگه داشتن و انتظار یا نگه داشتن منبع: یک فرایند حداقل یک منبع را در اختیار می‌گیرد و درخواست منابع دیگری می‌کند که توسط فرایندهای دیگر نگه داشته شده‌اند.

نبود بازپس گیری: یک منبع فقط به صورت داوطلبانه توسط پروسه ای که آن را در اختیار تام گرفته‌است قابل آزاد شدن است.

انتظار حلقوی: هر پروسه باید برای منبعی که توسط پروسه دیگری نگه داشته شده‌است منتظر بماند و پروسهٔ دیگر نیز منتظر پروسهٔ اول است تا منبع را آزاد کند. به‌طور کلی مجموعه ای از پروسه‌های در حال انتظار وجود دارند، P = {P₁, P₂, …, P_N}، به گونه ای که P₁ منتظر منبعی است که توسط P₂ نگه داشته شده‌است و P₂ منتظر منبعی هست که توسط P₃ نگه داشته شده‌است و به همین شکل ادامه پیدا می‌کند تا زمانی که P_n منتظر منبعی است که توسط P₁ نگه داشته شده‌است.

این چهار شرایط با نام شرایط کافمن شناخته می‌شوند.

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

روش‌های مقابله

اکثر سیستم‌های عامل کنونی نمی‌توانند از بن‌بست‌ها پیشگیری کنند. زمانیکه یک بن‌بست رخ می‌دهد، سیستم‌های عامل مختلف به شیوه‌های غیر استاندارد مختلفی به آن‌ها پاسخ می‌دهند. در اکثر روش‌ها از رخ دادن یکی از چهار شرایط کافمن خصوصاً مورد چهارم پیشگیری می‌کنند. روش‌های اصلی به قرار زیر هستند:

نادیده گرفتن بن‌بست

در این روش فرض بر این است که بن‌بست هرگز رخ نخواهد داد. این روش همان استفاده از الگوریتم شترمرغ است. این روش در ابتدا توسط MINIX و UNIX استفاده شد. از این روش زمانی استفاده می‌شود که فاصله‌های زمانی بین وقوع بن‌بست‌ها طولانی است و از دست دادن داده در هر بار قابل تحمل است.

روش نادیده گرفتن بن‌بست‌ها را می‌توان با اطمینان زمانی انجام داد که به‌طور رسمی ثابت شده باشد که هیچ وقت بن‌بستی رخ نخواهد داد. یک مثال در این رابطه چهارچوب RTIC است.

شناسایی

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

بعد از این که یک بن‌بست شناسایی شد با استفاده از یکی از روشهای زیر می‌توان آن را اصلاح کرد:

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

خارج کردن منبع از انحصار: ممکن است بتوان منابعی که به پروسه‌های مختلف اختصاص داده شده‌اند، را بترتیب از انحصار خارج کرد و به سایر پروسه‌ها اختصاص داد تا زمانی که بن‌بست مرتفع شود.

پیشگیری

پیشگیری از بن‌بست‌ها با اجتناب از یکی از شرایط چهارگانه کافمن امکان‌پذیر است:

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

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

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

آخرین وضعیت مورد بررسی وضعیت انتظار حلقوی است. روش‌هایی که از انتظارهای حلقوی پیشگیری می‌کنند عبارتند از: غیرفعال کردن وقفه‌ها در زمان قسمت‌های بحرانی و استفاده از یک سلسله مراتب برای تعیین یک ترتیب سهمی منابع. اگر هیچ سلسله مرتبهٔ واضحی وجود نداشته باشد، حتی از آدرس حافظهٔ منابع می‌توان برای تعیین ترتیب استفاده کرد و منابع به ترتیب افزایش عدد آن‌ها درخواست می‌شوند. از راه حل دیکسترا نیز می‌توان استفاده کرد.

جستارهای وابسته

منابع

↑ Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. p. 716. ISBN 978-0-273-76059-7.
↑ Padua, David (2011). Encyclopedia of Parallel Computing. Springer. p. 524. ISBN 9780387097657.
↑ Silberschatz, Abraham (2006). Operating System Principles (7th ed.). Wiley-India. p. 237. ISBN 9788126509621.
↑ Schneider, G. Michael (2009). Invitation to Computer Science. Cengage Learning. p. 271. ISBN 978-0324788594.
↑ Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 239. ISBN 9788126509621.
↑ "ECS 150 Spring 1999: Four Necessary and Sufficient Conditions for Deadlock". nob.cs.ucdavis.edu. Archived from the original on 29 April 2018. Retrieved 29 April 2018.
↑ Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill Education. p. 446. ISBN 9780070145894.
↑ "Operating Systems: Deadlocks". www.cs.uic.edu. Retrieved 2020-04-25. If a resource category contains more than one instance, then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for example, Figures 7.3 and 7.4 below:
↑ Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 237. ISBN 9788126509621.
↑ Stuart, Brian L. (2008). Principles of operating systems (1st ed.). Cengage Learning. p. 446. ISBN 9781418837693.
↑ Tanenbaum, Andrew S. (1995). Distributed Operating Systems (1st ed.). Pearson Education. p. 117. ISBN 9788177581799.
↑ https://rtic.rs/0.5/book/en/
↑ "IBM Knowledge Center". www.ibm.com. Archived from the original on 19 March 2017. Retrieved 29 April 2018.
↑ Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 244. ISBN 9788126509621.

[coulouris-1] Coulouris, George (2012). Distributed Systems Concepts and Design. Pearson. p. 716. ISBN 978-0-273-76059-7.

[para_enclo-2] Padua, David (2011). Encyclopedia of Parallel Computing. Springer. p. 524. ISBN 9780387097657.

[os_galvin-3] Silberschatz, Abraham (2006). Operating System Principles (7th ed.). Wiley-India. p. 237. ISBN 9788126509621.

[invi_comp-4] Schneider, G. Michael (2009). Invitation to Computer Science. Cengage Learning. p. 271. ISBN 978-0324788594.

[5] Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 239. ISBN 9788126509621.

[6] "ECS 150 Spring 1999: Four Necessary and Sufficient Conditions for Deadlock". nob.cs.ucdavis.edu. Archived from the original on 29 April 2018. Retrieved 29 April 2018.

[embb-7] Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill Education. p. 446. ISBN 9780070145894.

[8] "Operating Systems: Deadlocks". www.cs.uic.edu. Retrieved 2020-04-25. If a resource category contains more than one instance, then the presence of a cycle in the resource-allocation graph indicates the possibility of a deadlock, but does not guarantee one. Consider, for example, Figures 7.3 and 7.4 below:

[9] Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 237. ISBN 9788126509621.

[pric_os-10] Stuart, Brian L. (2008). Principles of operating systems (1st ed.). Cengage Learning. p. 446. ISBN 9781418837693.

[distri_tanen-11] Tanenbaum, Andrew S. (1995). Distributed Operating Systems (1st ed.). Pearson Education. p. 117. ISBN 9788177581799.

[12] ttps://rtic.rs/0.5/book/en/

[13] "IBM Knowledge Center". www.ibm.com. Archived from the original on 19 March 2017. Retrieved 29 April 2018.

[14] Silberschatz, Abraham (2006). Operating System Principles (7 ed.). Wiley-India. p. 244. ISBN 9788126509621.