موضوع مقاله: بن‌بست (علوم رایانه) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بن‌بست (علوم رایانه) | مقدمه: بن‌بست یا مخمصه در محاسبات همروند وضعیتی است که در آن هر عضوی از یک گروه منتظر عضو دیگری یا حتی منتظر خودش است تا شروع به کاری کند مثلاً یک پیام بفرستد یا اینکه به‌طور شایع تر یک قفل را آزاد کند. | ## بخش 1: بن‌بست (علوم رایانه) | بن‌بست‌ها مشکل شایعی در سیستم‌های چند پروسه ای، محاسبات موازی، و سیستم‌های توزیع شده هستند. در سیستم عامل، بن‌بست زمانی رخ می‌دهد که یک فرایند یا یک ریسمان در یک وضعیت انتظار قرار می‌گیرد چون منبع مورد نیاز آن، توسط یک پروسهٔ منتظر دیگر در انحصار قرار گرفته‌است که آن پروسه نیز منتظر منبع دیگری است که توسط یک پروسهٔ منتظر دیگری در انحصار قرار گرفته‌است. نبود بازپس گیری: یک منبع فقط به صورت داوطلبانه توسط پروسه ای که آن را در اختیار تام گرفته‌است قابل آزاد شدن است. انتظار حلقوی: هر پروسه باید برای منبعی که توسط پروسه دیگری نگه داشته شده‌است منتظر بماند و پروسهٔ دیگر نیز منتظر پروسهٔ اول است تا منبع را آزاد کند. به‌طور کلی مجموعه ای از پروسه‌های در حال انتظار وجود دارند، P = {P1, P2, …, PN}، به گونه ای که P1 منتظر منبعی است که توسط P2 نگه داشته شده‌است و P2 منتظر منبعی هست که توسط P3 نگه داشته شده‌است و به همین شکل ادامه پیدا می‌کند تا زمانی که Pn منتظر منبعی است که توسط P1 نگه داشته شده‌است. زمانیکه یک بن‌بست رخ می‌دهد، سیستم‌های عامل مختلف به شیوه‌های غیر استاندارد مختلفی به آن‌ها پاسخ می‌دهند. در اکثر روش‌ها از رخ دادن یکی از چهار شرایط کافمن خصوصاً مورد چهارم پیشگیری می‌کنند. روش‌های اصلی به قرار زیر هستند: نادیده گرفتن بن‌بست در این روش فرض بر این است که بن‌بست هرگز رخ نخواهد داد. | ## بخش 2: بن‌بست (علوم رایانه) | از این روش زمانی استفاده می‌شود که فاصله‌های زمانی بین وقوع بن‌بست‌ها طولانی است و از دست دادن داده در هر بار قابل تحمل است. روش نادیده گرفتن بن‌بست‌ها را می‌توان با اطمینان زمانی انجام داد که به‌طور رسمی ثابت شده باشد که هیچ وقت بن‌بستی رخ نخواهد داد. سپس وضعیت سیستم بررسی می‌شود تا مشخص شود که آیا بن‌بست رخ داده‌است تا اصلاح گردد. بعد از این که یک بن‌بست شناسایی شد با استفاده از یکی از روشهای زیر می‌توان آن را اصلاح کرد: پایان دادن پروسه: می‌توان یک یا بیش از یک پروسه دخیل در بن‌بست را نیمه کاره پایان داد. این روش مطمئناً و به سرعت موجب حذف بن‌بست می‌شود، اما هزینه آن زیاد است، زیرا محاسبات نیمه کاره از بین خواهند رفت. یا اینکه می‌توان در هر زمان فقط یک پروسه را نیمه کاره پایان داد تا زمانیکه بن‌بست مرتفع شود. این روش موجب سربار زیادی می‌شود زیرا بعد از هر ختم پروسه، یک الگوریتم باید مشخص کند که آیا سیستم هنوز در بن‌بست قرار دارد یا خیر. در هنگام انتخاب یک پروسه برای ختم دادن نیمه کاره، باید چندین فاکتور را مدنظر قرارداد، نظیر: اولویت و عمر پروسه. | ## بخش 3: بن‌بست (علوم رایانه) | پیشگیری پیشگیری از بن‌بست‌ها با اجتناب از یکی از شرایط چهارگانه کافمن امکان‌پذیر است: حذف شرایط انحصار متقابل: به این معنی است که هیچ پروسه ای دسترسی انحصاری به یک منبع نداشته باشد. الگوریتم‌هایی که مانع از انحصار متقابل می‌شوند الگوریتم‌های همزمان سازی غیر مسدود کننده نام دارند. همچنین یک پروسه که نیازمند یک منبع پر استفاده است ممکن است برای مدت نامتناهی منتظر بماند، زیرا چنین منبعی ممکن است همیشه به یک پروسه اختصاص داده شده باشد، که منجر به قحطی منبع می‌شود. به این الگوریتم‌ها (مثلاً توکن‌های متوالی) الگوریتم‌های همه یا هیچ نیز می‌گویند. اجتناب از توقف اجباری ممکن است دشوار یا غیرممکن باشد زیرا یک فرایند باید این امکان را داشته باشد تا یک منبع را برای مدت مشخصی از زمان در اختیار داشته باشد وگرنه نتیجه پروسه ممکن است ناسازگار باشد یا اینکه زد و خورد ممکن است رخ دهد. خارج کردن یک منبع قفل شده از انحصار به‌طور کلی موجب بازگشت به مرحله قبل می‌شود و باید از آن اجتناب شود زیرا از نظر سربار بسیار هزینه بر است. | ## جمع‌بندی | الگوریتم‌هایی که اجازه متوقف کردن اجباری پروسه‌ها را می‌دهند، عبارتند از الگوریتم‌های بدون قفل و بدون انتظار و همچنین کنترل همروندی خوشبینانه.