سیستم هاي عامل جلسه ششم
فصل ششم
همزمانی: بن بست و گرسنگی
اصول بن بست:
- بن بست را به صورت مسدود بودن دائمی مجموعه ای از فرآیند ها که برای منابع سیستم رقابت می کنند یا با یکدیگر در ارتباط هستند .
- راه حل کارامدی برای بن بست وجود ندارد.
- تمام بن بستهابی نیاز های متضاد دو فرآیند یا بیشتر ،برای منابع هم راه هستند.
انواع منابع:
منابع قابل استفاده مجدد: بدون صدمه توسط یک فرآیند می توان در هر زمان مورد استفاده قرار می گیردو تمام نمی شود.
مثل :پردازنده ها،حافظه اصلی و ثانویه و...
- منابع مصرف شدنی: منبعی هستند که می تواند ایجاد ونابود گردد.
نوعا روی تعداد منابع مصرف شدنی از یک نوع به خصوص ،حدی وجود ندارد.
شرایط بن بست:
- انحصار متقابل : (شرط لازم)
یک فرآیند از یک منبع.
- نگهداشتن و انتظار: (شرط لازم)
با داشتن منبع دیگری در خواست منبع جدید می کند.
در این صورت یک منبع به مدت طولانی در اختیار یک فرآیند خواهد بود.
- قبضه نکردن: (شرط لازم)
- منبع را نمی توان به زور پس گرفت.
تنها وقتی ازبن بست جلوگیری می کند :که منابع دارای اولویت باشند.
- انتظار مدور: (شرط لازم و کافی)
چند فرآیند درخواست منبع هایی می کنند که در اختیار منبع دیگر است
و به همین سبب در انتظار چرخشی قرار می گیرند.
موجب کند کردن فرآیند ها و رد کردن غیز ضروری دسترسی منابع می شود
سه رویکرد در برخورد با بن بست
- پیشگیری
- کشف
- اجتناب
پیشگیری از بن بست:
- روش غیر مستقیم : پیشگیری از حالتهای 1و2و3 (انحصار متقابل، نگهداشتن و انتظار، قبضه نکردن)
روش مستقیم : پیشگیری از بروز انتظار مدور
مزایای پیشگیری از بن بست:
- در مورد فرآیند هایی که فعالیت هایی زیادی انجام می دهند.
- عدم نیاز به قبضه کردن.
- معایب:
- نا کارامدی.
- تاخیر شروع فرآیند.
کشف:
- سیاست تخصیص منابع: بسیار زیاد ،در صورت امکان تخصیص داده می شود.
- طرح های مختلف: احضار دورهای برای بررسی بن بست.
- مزایای اصلی:
- عدم تاخیر در آغاز فرآیند .
- تسهیل پردازش در حین کار.
- معایب اصلی:
- ضرر های ذاتی قبضه.
اجتناب:
- سیاست تخصیص منابع: انتخاب راهی بین پیشگیری و کشف.
- طرح های مختلف: دستکاری برای یافتن حداقل یک مسیر امن.
- مزایای اصلی:
- عدم نیاز به قبضه کردن.
- معایب اصلی:
- ضرورت اطلاع از منابع مورد نیاز آینده
- امکان مسدود شدن طولانی فرآیند.
دو رویکرد برای اجتناب از بن بست
- عدم شروع فرایندی که ممکن است درخواستهایش به بن بست منتهی شود
- عدم پاسخ به درخواستهای منبع اضافی از فرایندی که با این تخصیص ممکن است منجر به بن بست شود.
عدم تخصیص:
- الگوریتم بانکداران نیز می گویند.
- حالت سیستم تخصیص منابع به فرآیند ها است.
- دارای دو حالت :
- حالت امن:
حداقل یکی از فرآیند ها اجرا شود.
2_حالت نا امن:
حالتی است که امن نباشد.
در این روش باید منابع با دقت به درخواست کننده ها ارائه شود که دچار کمبود منابع نشویم .
امتیاز اجتناب از بن بست:
- حداکثر منابع مورد نیاز هر فرآیند باید پیش بینی شود.
- فرآیندهای مورد نیاز باید مستقل باشند.
- تعداد منابع تخصص باید ثابت باشند.
- فرآیندی که منبعی را در اختیار دارد نمی تواند خارج شود.
ترمیم : (بعد از کشف بن بست)
- قطع تمام فرآیندهای بن بست.
- برگشت هر یک از فرآیندهای بن بست به نقطه قبل از آن.
- قطع پی درپی بن بست تا جایی که بن بستی وجود نداشته باشد.
- قبضه کردن منابع تا جایی که بن بستی وجود نداشته باشد.
راهبرد مجتمع برای بن بست:
- تقسیم بندی منابع در تعدادی از گروههای مختلف.
- استفاده از راهبرد مرتب سازی خطی.
- استفاده از مناسب ترین الگوریتم.
به عنوان مثال استفاده از بهترین الگوریتم:
- فضای قابل مبادله: بلوک هایی از حافظه ثانویه برای استفاده در مبادله فرآیند.
- منابع فرآیند: دستگاههای قابل تخصیص.
- حافظه اصلی: حافظه قابل تخصیص به فرآیندها.
- منابع داخلی: مثل کانالهای ورودی و خروجی.
مسئله تغذیه فیلسوفان:
- هر فیلسوفی که می خواست غذا بخورد به جایی که در این میز منظور شده بود می رفت وبا استفاده از دو چنگال کنار بشقابش غذا می کشد مشکل این است که باید چاره ای برای رفع گرسنگی سایرین نیز داشته باشیم.
- برای این مشکل هر فیلسوف ابتدا چنگال سمت چپ وسپس چنگال سمت راست خود را بردارد که باز هم در این روش مسئله بن بست پیش می آید.
- مسائل اصلی بن بست گرسنگی را تشریح می کند.
راهکارهای هم زمانی در unix :
- لوله ها:
- پیا م ها:
- حافظه مشترک :
- راهنماها:
علائم
- لوله ها:
یکی از مهم ترین کمکهای unix به ایجاد و توسعه سیستم های عامل است.
بر اساس مدل تولید کننده و مصزف کننده با هم ارتیاط برقرار می کند.
صف خروجی به ترتیب ورودی است.دو نوع لوله بی نام و با نام وجود دارد.
- پیا م ها:
بلوکی از متن به همراه یک نوع است.از فراخوان سیستمی msgsnd و msgrcv برا ی فرآیندهای درگیر در تبادل پیام استفاده می کنند.
- حافظه مشترک:
سریعترین شکل ارتباط بین فرآیندها است.بلوکی از حافظه مجازی است که توسط فرآیند های متعدد مورد اشتراک قرار می گیرد .
- راهنماها:
از اولیه های wait و signalاست.عملیات متعددی به صورت هم زمان اجرا می شود.یک راهنما شامل عناصر زیر است:
1-مقدار جاری راهنما.
2-شناسه.
3-تعداد فرآیندهای منتظرمقدار راهنما از مقدار جاری انها بزرگتر باشد.
4--تعداد فرآیندهای منتظرمقدار راهنما ی آنها صفر باشد...
- علائم:
یک راهکارنرم افزاری است که از بروز یک حادثه نا بهنگام خبر می دهد.
اولیه های همگام سازی نخ در solaris:
- قفل های انحصار متقابل:
از پیش رفت یک نخ جلوگیری می کند.
- راهنماها:
راهنماهای شمارنده کلاسیک را ارائه می دهد.
- قفل های چند خواننده و یک نویسنده:
اجازه می دهد نخ های متعدد هم زمان به شیءکه تحت حفاظت است دسترسی فقط خواندنی داشته باشد.
- متغییر های شرط:
برا ی انتظار تا برقراری شرط خاصی.
راهکارهای همزمانی در windows NT:
- فرآیند: احضار یک برنامه .
- نخ: موجودیت قابل اجرا .
- پرونده: نمونه پرونده باز.
- ورودی میز کار: یک میانگیر صفحه نمایش متنی.
- اعلام تغییر پرونده: تغییر سیستم پرونده.
Mutex - (انحصار متقابل).
- راهنما: شمارنده تعدادنخ های برنامه را تنظیم می کند.
- حادثه: یک حادثه سیستمی اتفاق افتاده است.
- زمان سنج قابل انتظار: شمارنده برای ثبت گذشت زمان.