به نام خدا
اصول همزمانی و بن بست در سیستم عامل
Operating Systems
مباحث این فصل:
اصول بن بست
پیشگیری از بن بست
اجتناب از بن بست
کشف بن بست
یک راهبرد مجتمع برای بن بست
سوالات دوره ای
سیستم های بی درنگ
سیستم های بی درنگ یا زمان واقعی یک سیستم عامل چند وظیفه ای است که معمولاً بعنوان یک کنترل کننده در یک کاربرد خاص استفاده می شوند. سیستم در این حالت می بایست در زمانی مشخص و معین حتماً جواب مورد نظر را بدهد. سیستم های کنترل آزمایش های علمی، تصویربرداری پزشکی، کنترل صنعتی و برخی از سیستم های نمایش از این دسته اند. هدف اصلی استفاده از سیستم های بی درنگ واکنش سریع و تضمین شده در برابر یک رویداد خارجی می باشد. در سیستم های بی درنگ معمولاً وسایل ذخیره سازی ثانویه وجود ندارد و به جای آن از حافظه های ROM استفاده می شود. سیستم عامل های پیشرفته نیز در این سیستم ها وجود ندارند چرا که سیستم عامل کاربر را از سخت افزار جدا می کند و این جداسازی باعث عدم قطعیت در زمان پاسخ گویی می شود.
سیستم های چند کاربره
سیستم های چند کاربره اجازه می دهند تا کاربران متعدد بصورت همزمان به یک سیستم کامپیوتری دسترسی داشته باشند. سیستم های اشتراک زمانی و کارساز وب را می توان بعنوان سیستم های چند کاربره طبقه بندی کرد. در سیستم های اشتراک زمانی تنها یک پردازنده قرار دارد که توسط مکانیزم های زمانبندی بین برنامه های مختلف کاربرها با سرعت زیاد سوئیچ می شود و بنابراین هر کاربر تصور می کند کل رایانه در اختیار اوست
بن بست:
بن بست را به صورت مسدود بودن دائمی مجموعه ای از فرایندها، که برای منابع سیستم رقابت میکنند یا با یکدیگر در ارتباط هستند. تعریف میکنند .
برای بن بست راه حل کارآمدی وجود ندارد.
تمام بن بست ها با نیازهای متضاد دو فرایند یا بیشتر، برای منابع همراه هستند.
مثالی از بن بست:
یک مثال بن بست، ترافیک است.در رانندگی قانون این است که هر خودرو باید تسلیم خودروی سمت راست باشد.در این صورت در حالت زیر چه رخ میدهد؟
مثالی از بن بست در فرایند ها:
ساده ترین نوع بن بست زمانی اتفاق می افتد که 2 فرایند مجزا و همزمان منتظر بدست آوردن منبعی هستند که در اختیار دیگریست و خود نیز منابعشان را تا اتمام فرایند آزاد نمیکنند.
Process P :
Get A
Get B
Release A
Release B
.
.
Process Q :
Get B
Get A
Release B
Release A
.
.
انواع منابع:
منابع نقش تعیین کننده ای در بن بست دارند.
منابع به دو دسته تقسیم میشوند:
منابع قابل استفاده مجدد
منابع مصرف شدنی یا غیر قابل استفاده مجدد
منابع قابل استفاده مجدد:
منابعی هستند که در هر لحظه از زمان تنها توسط یک فرایند قابل استفاده اند و استفاده از آنها موجب به پایان رسیدن آنها نمیشود(بدون آسیب دیدن آزاد میشوند)
فرایند ها منابع را بدست می آورند و سپس آنها را برای استفاده مجدد توسط سایر فرایند ها آزاد میکنند.
پردازنده، کانالهای I/O، حافظه اصلی و ثانوی، دستگاه ها و ساختمان داده هایی مثل پرونده ها، پایگاه های داده و راهنماها از این دسته اند.
بن بست زمانی رخ میدهد که یک فرایند منابع را نگه دارد و منبع دیگری درخواست کند.
مثالی از بن بست منابع قابل استفاده مجدد:
فرض کنید فضای حافظه که میتواند به فرایند ها تخصیص یابد KB 200 باشد.در این صورت ترتیب زیر موجب بروز بن بست میشود.
P1
. . .
. . .
Request 80 Kbytes;
Request 60 Kbytes;
P2
. . .
. . .
Request 70 Kbytes;
Request 80 Kbytes;
منابع مصرف شدنی:
این منابع تولید میشوند و از بین میروند
وقفه ها، علامتها، پیامها و اطلاعات بافر I/O از این نمونه اند.
کشف بن بستهای حاصل از این منابع بسیار مشکل است و ممکن است ترکیب نادری از حوادث آنها را ایجاد کند.
مثالی از بن بست منابع قابل استفاده مجدد:
در صورتیکه عمل Receive مسدود کننده باشد بن بست اتفاق می افتد.
P1
. . .
. . .
Receive(P2);
Send(P2, M1);
P2
. . .
. . .
Receive(P1);
Send(P1, M2);
شرایط لازم برای ایجاد بن بست:
انحصار متقابل:
در هر لحظه تنها یک فرایند میتواند از یک منبع استفاده کند.
نگهداشت و انتظار:
هنگام درخواست منبع جدید فرایند منابع قبلی تخصیص یافته را آزاد نمیکند.
قبضه نکردن:
منابع به زور قابل پسگیری نیستند.
شرایط لازم برای ایجاد بن بست:
انتظار مدور:
زنجیر بسته ای از فرایند ها وجود دارد، بطوریکه هر یک حداقل یک منبع مورد نیاز فرایند بعد
در زنجیره را نگه دارد.
گراف تخصیص منابع:
گراف تخصیص منابع یک گراف جهت دار است که نحوه تخصیص منابع به فرایند ها را در هر لحظه از زمان نشان میدهد.
برای تشخیص بن بست باید گراف تخصیص منابع را بعد از هر درخواست، هر تخصیص، یا هر ترخیص به روز کرد.
در گراف ، منابع را با و فرایند را با نشان میدهیم.
وجود چرخه در گراف بیانگر بروز بن بست است.
P
S
P
S
فرایند P منبع S را در اختیار دارد
فرایند P در انتظار منبع S است
جلوگیری از بن بست:
جلوگیری از بن بست با نقض کردن یکی از شرایط 4 گانه لازم برای بن بست انجام میشود:
انحصار متقابل: این شرط را نمیتوان رد کرد، چرا که بعضی از منابع ذاتاً انحصاری هستند. مثلاً یک چاپگر تنها میتواند به یک فرایند پاسخ دهد یا نوشتن بر روی یک بانک اطلاعاتی تنها توسط یک فرایند انجام میشود.
جلوگیری از بن بست:
نقض نگهداشت و انتظار: میتوان فرایند ها را ملزم ساخت که اختصاص منابع تنها زمانی انجام شود که تمام منابع مورد نیاز فرایند آزاد باشد و حتی اگر یک منبع آماده نبود هیچ اختصاصی انجام نشود.
معایب این روش:
انتظار طولانی فرایند برای تکمیل منابعش
بیکار ماندن یک منبع به مدت طولانی
عدم پیش بینی منابع مورد نیاز در آینده
جلوگیری از بن بست:
نقض شرط غیر قابل استفاده مجدد
پاسخ به درخواست منبع جدید در صورت آزاد شدن منابع قبلی
قبضه کردن فرایند با اولویت پایینتر: زمانی که یک فرایند نیاز به منبعی دارد که فرایند دیگری آنرا نگه داشته است، سیستم عامل آنرا قبضه کرده و منابعش را آزاد میکند.
در فرایند های اولویت بندی شده استفاده میشود.
حالت منبع باید براحتی قابل ذخیره باشد تا بعدها بازیابی شود.
جلوگیری از بن بست:
نقض شرط انتظار مدور: مرتب کردن منابع به صورت خطی:به هر منبع یک شاخص نسبت داده میشود. در این صورت فرایند میتواند ابتدا منبع Ri و سپس منبع Rj را درخواست کند اگر i<j
معایب این روش:
کند شدن فرایندها
رد کردن غیر ضروری دسترسی به منابع
اجتناب از بن بست:
در این استراتژی سعی در پیش بینی آینده داریم و تلاش میکنیم به دو صورت مانع از بروز بن بست شویم:
عدم شروع فرایندی که ممکن است درخواست هایش موجب بن بست شود.
عدم پاسخ به درخواست فرایندی برای منبع که این تخصیص موجب بن بست میشود.
اجتناب از بن بست:
عدم شروع فرایند:
سیستمی از n فرایند و m نوع مختلف از منابع را در نظر بگیرید. بردارها و ماتریسهای زیر را تعریف میکنیم:
آرایه R[i]
آرایه Available[i]
ماتریس دو بعدی Allocation[i][j]
آرایه max[i][j]
ماتریس دوبعدی Need[i][j]
اجتناب از بن بست:
C11 C12 … C1m
C21 C22 … C2m
: : : :
Cn1 Cn2 … Cnm
A11 A12 … A1m
A21 A22 … A2m
: : : :
An1 An2 … Anm
تعداد منابع کل اولیه از منبع نوع i
تعداد منابع آزاد از منبع نوع i
فرایند i حداکثر k تا منبع نوع j نیاز دارد
به فرایند i، k تا منبع نوع j تخصیص یافته
Resource={R1,R2,R3,…,Rm} R[i]=
Available={A1,A2,A3,…,Am} A[i]=
Max= max[i][j]=k
Allocation= A[i][j]=k
اجتناب از بن بست:
3 نکته بدیهی است:
تعداد منابع یا تخصیص داده شده اند یا موجودند.
هیچ فرایندی نمیتواند بیش از کل منابع سیستم درخواست کند.
تعداد فرایندهای اختصاص یافته نمیتواند بیش از حداکثر نیاز فرایند باشد.
بنابراین برای اجتناب از بن بست فرایند را تنها درصورتی شروع میکنیم که:
اجتناب از بن بست:
عدم تخصیص منبع: به این راهبرد الگوریتم بانکداران نیز گفته میشود.
حالت سیستم، تخصیص جاری منابع به فرایندها است، لذا حالت سیستم شامل دو بردار Available,Resource و دو ماتریس Max,Allocation میباشد.
حالت مطمئن: حالتی است که در آن حداقل یک ترتیب از فرایندها وجود دارد که میتوانند اجرا و کامل شوند، بدون اینکه حالت بن بست ایجاد شود.
الگوریتم بانکداران:
مقادیر مورد نیاز هر فرایند را بدست می آوریم.(Need)
کمترین را در نظر میگیریم. اگر کمترین مقدار از مقادیر منبع باقیمانده بیشتر بود، نتیجه میگیریم که حالت ناامن است. در غیر این صورت فرایند با کمترین نیاز را حذف میکنیم و تعداد منابع تخصیص یافته آنرا را آزاد میکنیم و مراحل را دوباره تکرار میکنیم.
الگوریتم بانکداران:
توجه : در حل مسائل بانکداران باید جداول و اطلاعات زیر را داشته باشیم:
جدول Allocation
جدول Max یا جدول Need
جدول Resource یا جدول Available
سپس بر حسب ورودی باید جداول زیر را بدست آوریم:
جدول Allocation
جدول Need
Available
الگوریتم بانکداران:
با توجه به جداول زیر بگویید آیا حالت امن است؟
این جدول بیان میکند تنها یک نوع منبع داریم.
فرایند A به 6 منبع نیاز دارد و در حال حاضر 1 منبع به آن اختصاص یافته است.(برای فرایندB نیز به همین صورت)
در حال حاظر از کل تعداد منابع تنها 2 منبع آزاد است.(Available=2)
Press Enter
محاسبه Need :
(Need=Max-Allocation)
6 – 1
5
5 – 1
4
4 – 2
2
7 – 4
3
6
1
5
1
4
2
7
4
Press Enter
الگوریتم بانکداران:
پیدا کردن کوچکترین مقدارNeed:
2<2(Available)
Available=Available + 2
4
الگوریتم بانکداران:
Press Enter
پیدا کردن کوچکترین مقدارNeed:
3<4(Available)
Available=Available + 4
8
Press Enter
الگوریتم بانکداران:
پیدا کردن کوچکترین مقدارNeed:
4<8(Available)
Available=Available + 1
9
الگوریتم بانکداران:
Press Enter
پیدا کردن کوچکترین مقدارNeed:
5<9(Available)
Available=Available + 1
10
Press Enter
الگوریتم بانکداران
چون توانستیم تمام فرایند ها را حذف کنیم بنابراین حالت داده شده در صورت مساله امن است.
توجه داشته باشید که در این مساله فرض شد که تنها یک نوع منبع وجود دارد . در مثال بعدی مساله را با انواع مختلف منابع بررسی میکنیم.
الگوریتم بانکداران
Press Enter
الگوریتم بانکداران:
در این حالت نیز همانند قبل عمل میکنیم. با این تفاوت که کمترین تعداد نیاز یک سطر است.
بنابراین ابتدا مقدار نیاز را محاسبه میکنیم.
تعداد نیاز های هر فرایند را جمع میزنیم و کمترین را انتخاب میکنیم.
اگر سطر مربوط به کمترین مقدار از مقادیر منبع باقیمانده بیشتر بود، نتیجه میگیریم که حالت ناامن است. در غیر این صورت
فرایند با کمترین نیاز را حذف میکنیم و تعداد منابع تخصیص یافته آنرا را آزاد میکنیم و مراحل را دوباره تکرار میکنیم.
الگوریتم بانکداران:
مثال: آیا حالت زیر یک حالت امن است ؟
Press Enter
مرحله اول :جدول Need را محاسبه میکنیم.
الگوریتم بانکداران:
Press Enter
جدول Available را محاسبه میکنیم.
6 – 5
1
3 – 3
0
4 – 2
2
2 – 2
0
6
3
4
2
5
3
2
2
الگوریتم بانکداران:
Press Enter
با توجه به جدول Need کدام فرایند کمترین تعداد منابع را نیاز دارد؟
مقدار این سطر را با منابع باقیمانده مقایسه میکنیم
1
0
2
0
چون مقدار آن از منابع باقیمانده کمتر است سطر را حذف و منابع را آزاد میکنیم.
عملیات را برای بقیه سطر ها نیز انجام میدهیم.
الگوریتم بانکداران:
Press Enter
معایب الگوریتم بانکداران:
الگوریتم بانکداران و اجتناب از بن بست نمیتواند به طور حتم بروز بن بست را پیشبینی کند. گاهی آنرا حدس میزند و گاهی آنرا اطمینان میدهد.
معایب روش اجتناب از بن بست:
حداکثر منابع باید از قبل مشخص باشد.
فرایند های مورد نظر باید مستقل باشند (همگام سازی نشده باشند)
تعداد منابع تخصیصی باید ثابت باشد.
فرایندی که منبعی را در اختیار داشته باشد نمیتواند خارج گردد
کشف بن بست:
روشی است که در آن اجازه برای انجام فرایند و هر تخصیص منبع داده میشود و سیستم عامل مرتباً وجود بن بست را بررسی میکند.
در راهبرد کشف بن بست به صورت زیر عمل میشود:
قطع تمام فرایندهای در بن بست
برگشت هر یک از فرایند های در بن بست به نقاطی که از قبل برای بررسی تعیین شده اند و شروع مجدد تمام فرایند ها
قطع پیگیری فرایندهای در بن بست تا جایی که دیگر بن بست وجود نداشته باشد
قبضه کردن پی در پی منابع تا جایی که دیگر بن بست وجود نداشته باشد.
کشف بن بست:
برای بند های 3 و 4 معیار انتخاب میتواند یکی از موارد زیر باشد:
کمترین وقت مصرفی از پردازنده تا کنون
کمترین خروجی تولید شده تا کنون
بیشترین زمان باقیمانده تخمینی
کمترین منابع تخصیص داده شده تا کنون
کمترین اولویت
راهبرد مجتمع برای بن بست:
هر راهبرد بن بست مزایا و معایب مخصوص به خود را دارد شاید بهتر باشد از ترکیبی از راهبرد ها استفاده کنیم:
تقسیم بندی منابع در تعدادی گروه های مختلف
استفاده از راهبرد مرتب سازی خطی
در داخل یک گروه از منابع استفاده از بهترین الگوریتم برای آن گروه
خلاصه رویکرد های پیشگیری، اجتناب و کشف بن بست:
سوال و پاسخ :
? ? ? ? ?
سوال اول:
برای منابع قابل استفاده مجدد و منابع مصرف شدنی مثالی بزنید؟
برای منابع قابل استفاده مجدد میتوان به پردازنده، کانال های ورودی خروجی، حافظه اصلی و ثانویه، دستگاه ها، و ساختمان داده هایی چون پرونده ها، پایگاه داده ها، و راهنما ها اشاره کرد.
وقفه ها، سیگنالها، پیامها و اطلاعات میانگیر ورودی خروجی مثالهایی از منابع غیر قابل استفاده مجدد هستند.
سوال دوم:
سه شرط لازم برای بروز بن بست را نام ببرید؟
انحصار متقابل: در هر زمان فقط یک فرایند میتواند از منبع استفاده کند.
نگهداشت و انتظار: در حالی که فرایند منبع تخصیص داده شده را نگه میدارد منتظر تخصیص منبع دیگری است.
قبضه نکردن:هنگامی که فرایندی منبعی را در اختیار دارد نتوان آن را به زور باز پس گرفت.
سوال سوم:
چهار شرطی که بن بست را بوجود می آورند نام ببرید؟
سه شرط بالا بعلاوه : انتظار مدور: زنجیره بسته ای از فرایند ها وجود دارد که هر یک حداقل یک منبع مورد نیاز برای فرایند بعد در زنجیره را نگه میدارد.
سوال چهارم:
چگونه از شرط نگه داشت و انتظار میتوان پیشگیری کرد؟
با ملزم کردن فرایند به درخواست یکباره تمام منابع مورد نیاز و مسدود کردن آن تا موقعی که تمام منابع در اختیارش گذاشته شود میتوان از بروز شرط نگه داشتن و انتظار جلوگیری کرد.
سوال پنجم:
دو راه پیشگیری از شرط قبضه نکردن را نام ببرید؟
ابتدا اگر فرایندی برخی منابع را نگه داشته است درخواست های بعدیش رد میشود، فرایند باید منابعی را که در دست دارد آزاد کند سپس در صورت نیاز درخواست منبع میکند و به آن منبع دیگری داده میشود.
همچنین در صورتیکه یک فرایند درخواست منبعی را دارد که توسط فرایند دیگر نگه داشته میشود، سیستم عامل ممکن است فرایند دوم را قبضه کند و منابع آن را آزاد کند.
سوال ششم:
چگونه میتوان از شرط انتظار مدور پیشگیری کرد؟
با تعریف یک ترتیب خطی از انواع منابع میتوان از بروز شرط انتظار مدور جلوگیری کرد.اگر فرایندی منبعی از نوع R را به خود اختصاص داده، در ادامه فقط منابعی را میتواند درخواست کند که (در ترتیب خطی) نوع آنها بعد از R قرار گرفته باشد.
سوال هفتم:
تفاوت بین اجتناب از بن بست، کشف بن بست و پیشگیری از بن بست چیست؟
پیشگیری از بن بست: در این راهبرد با کنترل کردن درخواست های منابع از بروز یکی از شرایط 4 گانه بروز بن بست جلوگیری میشود. میتوان به طور غیر مستقیم با پیشگیری از وقوع یکی از3 شرط لازم برای وقوع بن بست از آن پیشگیری کرد و یا به طور مستقیم از وقوع شرط چهارم (انتظار مدور) پیشگیری کرد.
سوال هفتم:
اجتناب از بن بست: این روش اجازه وقوع شرایط 3 کانه را میدهد اما در انتخابها به گونه ای عمل میکند که اطمینان حاصل کند که بن بستی رخ نمیدهد.
کشف بن بست: در این روش منابع در صورت امکان به فرایند ها اختصاص می یابند، به صورت دوره ای سیستم عامل الگوریتمی را برای شناسایی شرط انتطار مدور انجام میدهد.
با تشکر از توجه شما