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

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

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

شرایط لازم

شرایط و حالات مورد نیاز برای به وجود آمدن بن‌بست:

1. انحصار متقابل (به انگلیسی: Mutual Excusion)‏: منابعی غیرقابل اشتراکی وجود داشته باشند به این معنی که فقط یک پردازش اجازهٔ به‌کار بردن منبع را داشته باشد و اگر پردازش دیگری نیاز به آن منبع داشته باشد، پردازش درخواست‌کننده باید به تأخیر بیافتد تا منبع آزاد شود.
2. گرفتن و منتظر ماندن (به انگلیسی: Hold and Wait)‏: پردازشی باید وجود داشته باشد که منبع را به خود تخصیص دهد و منتظر منابع دیگری باشد که توسط سایر پرداش‌ها نگه‌داشته شده‌اند.
3. بدون پس‌دادن (به انگلیسی: No Preemption)‏: نتوان منبعی را از پردازش‌ها پس‌گرفت، یعنی منبع در صورتی بتواند آزاد شود که کار پردازش با آن تمام شده باشد.
4. انتظار چرخشی (به انگلیسی: Circular Wait)‏: باید مجموعه‌ای از پردازش‌ها به صورت زنجیروار به منابع اختصاص یافته مختلف یکدیگر نیاز داشته باشند.

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

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

چند روش با رفتار متقاوت برای مواجهه با مشکل بن‌بست وجود دارد.

1. ساده‌ترین روش این است که کلاً بن‌بست را نادیده گرفت. این روش بسیاری اوقات بهترین روش است، چون بن‌بست‌ها خیلی کم رخ می‌دهند، به طوری که زحمت هزینهٔ مقابله با آن‌ها از هزینهٔ رخ‌دادن آن‌ها بیشتر است، چون سیستم‌عامل برای هر پروسه‌ای که درخواست منابع کند باید بررسی کند که آیا بن‌بستی وجود دارد یا نه. الگوریتم شترمرغ دقیقاً همین کار را می‌کند، یعنی با فرض این که مشکل بسیار کم رخ می‌دهد، از آن چشم‌پوشی می‌کند، چون گاه رفع کردن مشکل ارزش زحمت نسبتاً زیاد مقابله با آن را ندارد.
2. پیشگیری از بن‌بست (به انگلیسی: Deadlock Prevention)‏
3. اجتناب از بن‌بست (به انگلیسی: Deadlock Avoidance)‏
4. آشکارسازی بن‌بست (به انگلیسی: Deadlock Detection)‏

لایولاک

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