Deadlock چیست؟ – توضیح بن بست در سیستم عامل به زبان ساده

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

Deadlock چیست؟

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

برای آشنایی بهتر در همین ابتدای مطلب، پیشنهاد می‌کنیم ویدیوی آموزشی رایگان زیر را تماشا کنید:

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

مثال واقعی برای درک مفهوم Deadlock

شرایطی را در نظر بگیرید که در آن دو همکلاسی با نام‌های سهیل و رادین باید تکالیف خود را انجام دهند. این دو نفر برای انجام تکالیف خود به یک خودکار و یک خط‌کش نیاز دارند درصورتی‌که تنها یک خودکار و یک خط‌کش موجود است. در نتیجه، شرایط زیر رخ می‌دهد.

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

بن بست در کامپیوتر چگونه رخ می‌دهد؟

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

• فایل‌ها
• حافظه
• چاپگر
• قفل‌های نرم‌افزاری

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

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

شرایط وقوع بن بست در Deadlock چیست؟

برای وقوع بن بست در سیستم‌عامل باید ۴ شرط به صورت همزمان برقرار شود. به این شرایط در اصطلاح «شرایط کافمن» (Coffman conditions) گفته می‌شود که برگرفته از نام پژوهشگری است که نخستین بار این ۴ شرط را تعریف کرد.

در ادامه ۴ شرط وقوع Deadlock در سیستم‌عامل آورده شده است.

• انحصار متقابل
• نگه‌داشتن و انتظار
• غیرقابل سلب بودن منبع
• انتظار چرخشی

فیلم آموزش سیستم‌عامل جامع و کاربردی در فرادرس

کلیک کنید

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

شرط انحصار متقابل در Deadlock چیست؟

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

نگه‌داشتن و انتظار

«نگه‌داشتن و انتظار» (Hold and Wait) زمانی رخ می‌دهد که یک فرایند منبعی را در اختیار دارد، ولی برای ادامه کار به منبع دیگری نیاز دارد و منتظر آن باقی می‌ماند. به عنوان مثال، فرض کنید که یک فرایند چاپگر را در اختیار دارد، ولی برای ادامه کار به اسکنر نیاز دارد و اسکنر نیز در اختیار منبع دیگری قرار دارد. در نتیجه، فرایند منتظر باقی می‌ماند، در حالی که چاپگر را همچنان در اختیار دارد.

غیرقابل سلب بودن منبع

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

شرط انتظار چرخشی در وقوع Deadlock چیست؟

«انتظار چرخشی» (Circular Wait) به این معنی است که چند فرایند منتظر منابعی هستند که به‌صورت زنجیره‌ای در اختیار یکدیگر قرار دارند و این زنجیره به فرایند اول باز می‌گردد. به عنوان مثال، فرض کنید که فرایند A منبعی را از فرایند B می‌خواهد، فرایند B منتظر منبعی از فرایند C است و فرایند C نیز به منبعی نیاز دارد که در اختیار فرایند A قرار دارد. در نتیجه، هر سه فرایند منتظر یکدیگر باقی می‌مانند.

در جدول زیر شرایط وقوع Deadlock در سیستم‌عامل به صورت خلاصه آورده شده است.

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

یادگیری سیستم‌عامل با فرادرس

مجموعه آموزش سیستم عامل – از دروس دانشگاهی تا کاربردی

۱۸ آموزش۵۸,۴۰۹ دانشجو۸۲ ساعت

آموزش نصب و راه اندازی سیستم عامل لینوکس Linux (رایگان)

۷,۷۲۸ دانشجو۱۴ دقیقه

آموزش سیستم عامل لینوکس Linux – مقدماتی + گواهینامه

۱۱,۰۴۳ دانشجو۱۵ ساعت

گواهینامه

آموزش سیستم عامل – جامع و کاربردی + گواهینامه

۱۴,۴۲۷ دانشجو۱۱ ساعت

گواهینامه

آموزش Ubuntu (اوبونتو) – ۱۰ گام پس از نصب (رایگان)

۹,۱۹۷ دانشجو۵۷ دقیقه

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

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

• فیلم آموزش سیستم عامل جامع و کاربردی با گواهینامه فرادرس
• فیلم آموزش سیستم عامل لینوکس Linux در سطح مقدماتی با گواهینامه فرادرس
• فیلم آموزش سیستم عامل با مرور و تست کنکور ارشد فرادرس
• فیلم آموزش سیستم عامل کالی لینوکس Kali Linux در سطح مقدماتی با گواهینامه فرادرس
• فیلم آموزش سیستم عامل ربات ها رآس ROS در سطح مقدماتی فرادرس
• فیلم آموزش پیکربندی پیشرفته سیستم عامل ویندوز و برنامه های کاربردی با گواهینامه فرادرس

روش های مدیریت Deadlock در سیستم عامل چیست؟

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

به طور کلی چهار روش اصلی زیر برای مدیریت بن بست در سیستم‌عامل وجود دارد.

• پیشگیری از بن بست
• اجتناب از بن بست
• تشخیص بن بست
• بازیابی از بن بست

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

پیشگیری از بن بست

پیشگیری از بن بست به این معنی است که سیستم‌عامل شرایطی را ایجاد می‌کند که امکان وقوع بن بست وجود نداشته باشد. برای این کار حداقل یکی از ۴ شرط اصلی وقوع بن بست نباید برقرار شود.

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

اجتناب از بن بست

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

یکی از روش‌های شناخته‌ شده برای اجتناب از بن بست، «الگوریتم بانکداران» (Banker's Algorithm) است. این الگوریتم با بررسی منابع موجود و نیاز فرایندها در مورد تخصیص منابع تصمیم‌گیری می‎‌کند.

تشخیص بن بست

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

به عنوان مثال، فرض کنید که فرایند A یک چاپگر را در اختیار دارد و منتظر اسکنر است. در همین زمان نیز فرایند B اسکنر را در اختیار دارد و منتظر چاپگر است. اگر هیچ‌کدام از این دو فرایند نتوانند کار خود را ادامه دهند، آنگاه سیستم‌عامل می‌تواند با بررسی وضعیت منابع بن بست را شناسایی کند.

بازیابی از بن بست

فیلم آموزش الگوریتم زمان‌ بندی HRRN در فرادرس

کلیک کنید

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

الگوریتم بانکداران در سیستم عامل و ارتباط آن با Deadlock چیست؟

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

الگوریتم بانکدار به زبان ساده

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

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

وضعیت امن در الگوریتم بانکدار چیست؟

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

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

تاثیرات Deadlock چیست؟

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

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

کلیک کنید

در ادامه، مهم‌ترین آثار مخرب بن بست در سیستم‌عامل آورده شده است.

• کاهش کارایی سیستم
• گرسنگی فرایندها
• پاسخگو نبودن سیستم

کاهش کارایی سیستم

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

نقش Deadlock در گرسنگی فرایندها چیست؟

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

پاسخگو نبودن سیستم

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

به این ترتیب، بهتر درک می‌کنیم که نقش Deadlock در فرایند‌های سیستم عامل چیست.

تفاوت بن بست و گرسنگی در سیستم عامل چیست؟

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

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

مثالی از تفاوت بن بست و گرسنگی

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

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

جمع‌بندی

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

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