همزمانی: بن بست و گرسنگی

صفحه 1:
حهز هانی. جن جست و کر سنکی 

صفحه 2:
سوالات دوره ای 

صفحه 3:
تابن بست را به صورت مسدود بودن دائمی مجموعه ای از فرایندهاء که برای منلبع سیستم رقلبت میکنند یا با یکدیگر در ارتباط هستند. تعریف میکنند . ۴ برای بن بست راه حل کارآمدی وجود ندارد. ۴ تمام بن بست ها با نیازهای متضاد دو فرایند یا بيشترء ‎Gly‏ ‏منابع همراه هستند. 

صفحه 4:
گلیک مثال بن بست. ترافیک اسث.در رانندگی قالون لین است. که هر خوذرو باید تسلیم خودروی سمت راست باشد.در این صورت در حالت زیر چه رخ میدهد؟ 1 23 Syd ب) ين بست الف)امكان بن بست 

صفحه 5:
۴ منابع نقش تعیین کننده ای در بن بست دارند. ۴ منابع به دو دسته تقسیم میشوند: * منابع قابل استفاده مجدد * منابع مصرف شدنی يا غیر قابل استفاده مجدد 

صفحه 6:
"" منابمی هستند که در هر لحظه از زمان تنها توسط یک فرایند قابل استفاده لند و استفاده از آنها موجب به پایان رسیدن آنها نمیشود(بدون آسیب دیدن آزاد میشوند) يند ها منلبع را بدست می آورند و سپس آنها را برای استفاده مجدد توسط سایر فرآیند ها آزاد * پردازنده. کانالهای 0 حافه ایو ثانوى» دستگاه ها و ساختمان داده هایی مثل پرونده هاء پایگاه های داده و راهنماها از این دسته اند. #بن بست زمانی رخ میدهد که یک فرایند متابع را نگه دارد و منبع دیگری درخواست کند. 

صفحه 7:
‎cyl‏ منابع تولید ميشوند و از بين ميروند ‏۴ وقفه هاء علامتهاء ييامها و اطلاعات بافر ۱/0 از اين نمونه اند. ‎oy Gas‏ بستهای حاصل از این منابع بسيار مشكل است و ممکن است ترکیب نادری از حوادث آنها را ایجاد کند. 

صفحه 8:
‎«Mutual Exclusion) [lize basal ®‏ * در هر لحظه تنها یک فرایند میتواند از یک منبع استفاده کند. * گرفتن و منتظر ماندن(]۷۷۵ 3۳00 ۲۱۵۱0): * هنگام درخواست منبع جدید فرایند منابع قبلی تخصیص يافته را آزاد "" قبضه نکردن پا نبود پس گیری(۲۵6۲۲0۲۱0۳ 0): * منابع به زور قابل پسگیری نيستند. 

صفحه 9:
«Circular Wait) jo. Uss!™ ‏زنجیر بسته ای از فرایند ها وجود دارد. بطه, كه هم ک حداقا , نک‎ * re ‏منبع مورد نیاز فرایند بعد‎ در زنجيره را نكه دارد. 8 ‎ey Ns,‏ a PI P2 mo pw Le ‏وک‎ ‎Rb (©) Circular walt 

صفحه 10:
* گراف تخصیص منلبع یک گراف جهت دار است که نحوه تخصیص منلبع به فرایند ها را در هر لحظه از زمان نشان "" برای تشخیص بن بست باید گراف تخصیص منلبع را بعد از هر درخواست. هر تخصیص. يا هر ترخیص به روز کرد. كاد رات ‎gales‏ راب و فرایند راب نشان میدهیم. "" وجود چرخه در گراف ‎Ge yaa le‏ ۳ 8ه فرايند 5 منبع 5 را در اختيار دارد الم فرایند ۳ در انتظار منبع 5 است 

صفحه 11:
7 جلوكيرى ازبن بست با نقض کردن یکی از شرلیط ۴ كانه لازم براى بن بست انجام ميشود: " انحصار متقلبل: لين شرط را نميتوان رد كرد. جرا كه بعضى از منابع ذاتاً انحصاری هستند. مثلاً یک جاپگر تنها میتواند به یک فرایند پاسخ دهد یا نوشتن بر روی یک بانک اطلاعاتی تنها توسط یک فرایند انجام میشود. 

صفحه 12:
نقض نگهداشت و انتظار: میتوان فرایند ها را ملزم ساخت که اختصاص منلبع تنها زملنی انجام شود که تمام منابع مورد نیاز فرایند آزاد باشد و حتی اگر یک منبع آماده نبود هیچ اختصاصی انجام نشود. ۴ معایب این روش: * انتظار طولانی فرایند برای تکمیل منابعش * بیکار ماندن یک منبع به مدت طولانی * عدم پیش بینی منابع مورد نیاز در آینده 

صفحه 13:
۳ ‏اد‎ eee نقض شرط نبود پس گیری * پاسخ به درخواست منبع جدید در صورت آزاد شدن منابع قبلی * قبضه کردن فرایند با اولویت پایینتر: زمانی که یک فرایند نیاز به منبعی دارد که فرایند دیگری آنرا نگه داشته است. سیستم عامل آنرا قبضه کرده و منابعش را آزاد ميكند. * در فرایند های اولویت بندی شده استفاده میشود. * حالت منبع باید براحتی قابل ذخیره باشد تا بعدها بازیابی شود. 

صفحه 14:
" نقض. شرط انتظار مدور: مرتب كردن منابع به صورت خطی‌نبه هر منبع يك شاخص نسبت داده ميشود. در اين صورت فرايند ميتواند ابتدا منبع ‎8١‏ و سيس منبع ‎Vy Ri‏ درخواست کند اگر ز>ز * رد كردن غير ضرورى دسترسى به منابع 

صفحه 15:
۴ در این استراتژی سعی در پیش بینی آینده داریم و تلاش میکنیم به دو صورت مانع از بروز بن بست شویم: * عدم شروع فرایندی که ممکن است درخواست هایش موجب بن بست شود. * عدم پاسخ به درخواست فرایندی برای منبع که این تخصیص موجب 

صفحه 16:
تم شروع فرایند: #نییستمی از فرایند و ‎٩‏ نوع مختاف از بردارها و ماتریسهای زیر را تعریف * آرایه :]8 * آرایه [۸۷۵/۱۵016]1 : تعداد منابع موجود هر يك از منابع را نشان مى دهد. ماتریس دو بعدی [ز][]۸۵106000 تعداد هر يك از انواع منابع در اختيار فعلى هر يك ار فرآیندها آرایه [][۳02]11: حداکثر نیاز فرآیند أ به منبع ز * ماتریس دوبعدی [][660]1!: نیز باقی مانده هر یک از فرآیند ها از منابع برای تکمیل کار خود 

صفحه 17:
=Resource={R1,R2,R3. تعداد منایع کل اولیه از منبع نو ‎١‏ ‏,3 ده امك[ اتام » أ تعداد منابع آزاد مز منبع نوع[1أ]م (ci 612 as 1 1۳ فرايند أ حداكثر »| تا منبع نوع [ نیاز دارکا[ز][| ]۳۵۱ دع وي ۰۱/۵ 2۳ به فرایند 16 .] تا منبع نوع ‏ تخصیص یافته ا[ز][۸]1 ‎Allocation:‏ 

صفحه 18:
#! نکته بدیهی است: . * تعداد منابع, یا تخصیص داده شده اند يا موجودند. . بكء 2 +۲ 1 یچ فرایندی نمیتواند بیش از نابع سیستم درخواست ند. 1 7 > بر تعداد فرایندهای اختصاص يافته نمیتواند بیش از حدا کثر نیاز فرایند ۰ پاشند: ۲ ۱ بنابراین برای اجتناب از بن بست فرايند را تنها درصورتى شرو A, R,2 Cait D Cy for alli kel 

صفحه 19:
"عدم تخصیص منبع: : به اين راهبرد الگوریتم بانکداران نیز كفته ميشود. * حللت سیستم. تخصيص جارى منلبع به فرايندها استء لذا حالت سيستم شامل دو بردار 865010166 ,81/311361 و دو ماتريس 0 ميباشد. * حالت مطمتن: حالتی است که در آن حداقل یک ترتيب از فرایندها وجود دارد که میتوانند اجرا و کامل شهند. بدون اينکه حالت بن بست ایجاد شود. 

صفحه 20:
"" مقادیر مورد نیاز هر فرایند را بدست می آوریم.(1660) #کمترین را خر نظر میگيريم. اگر کمترین مقداز از مقادیر مشبع باقیمانده بیشتر بود. نتیجه میگیریم که حللت ناامن است. در غير اين صورت فرایند با کمترین نیاز را حذف میکنیم و تعداد متاجع اتخصيصض_نافقك أقرا و1 | رادم متكليم و«مزاجل برا“ كويازه تكرار ميكنيم. 

صفحه 21:
* توجه : در حل مسائل بانکداران باید جداول و اطلاعات زیر را داشته باشیم: * جدول ۸۵۱۱۵6۵1100 * جدول 32 يا جدول ۱660 * جدول 650۱1۲66 یا جدول ‎Available‏ ‏سپس بر حسب ورودی باید جداول زير را بدست آوریم: ۴ جدول ۸۵۱۱0۵6۵1100 * جدول ‎Need‏ ‎Available *‏ 

صفحه 22:
با توجه به جداول زیر بگویید آیا حالت امن است؟ لین جدول بیان میکند تنهایک نوع منبع داریم. فرایند ۸۵ به ۶ منبع نیاز دارد و در حال حاضر ۱ منبع.به آن اختصاص یافته است. (براى فرايند8 نیز به همین صورت) در حال حاظر از کل تعداد منلبع تنها ۲ منبع آزاد است.(2 ۵۷۵112016 § Enter Availavie=2 Max N/R] UO Allocatio n 1 1 2 4 فر ایند 2 | 0 | 5 | ما 

صفحه 23:
* محاسبه ۱1660 : ۸۷۵۱۱۵۷۱۵2۵ (Need=Max-Allocation) ‏فرایند‎ Allocatio| Ma | Nee n x d A 1 6 1 B 1 5 1 M 2 4 ۸ 5 4 7 4 2۹6 Enter 

صفحه 24:
DENSE TITAN بيدا كردن كوجكترين ‎Need Joie‏ Availavle=4 > 2<2(Available) me Available=Available + | كا ات | با 4 2 wl(M) aA] ۵ 6 60 ل Allocatio ۳ 

صفحه 25:
پیدا کردن کوچکترین ‎Need lade‏ > 3<4(Available) Available=Available + | ND Availavie=8 Ma كات | نا | حل ل Allocatio فرايند < اي اس اها 

صفحه 26:
‎py oT‏ بانتداران ‎ ‏بيدا كردن كوجكترين ‎Need Jodie‏ ‎> 4<8(Available) ‎Available=Available + ‎ ‎ ‎ ‎ ‎Availavle=9 ‎Ma ‏| شا ‎rs ‎ ‎Allocatio ‎n ‎Hl ‏بم‎ ‎ND ‎ ‏فر ایند ‏> 8 ع ها ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 27:
پیدا کردن کوچکترین مقدار 660/: ‎5<9(Available)‏ > ‎Available=Available +‏ Availavle=10 Ma Ul} Obl x rs Allocatio n 3 1 3 2 24 فرايند ‎Bl ®‏ |ج اها ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 28:
۴ چون توانستیم تمام فرایند ها را حذف کنیم بنابراین حالت داده شده در صورت مساأله امن است. توجه داشته باشید که در لین مسأله فرض شد که تنها یک نوع منبع وجود دارد . در مثال بعدی مسأله رابا انواع مختلف منابع بررسی میکنیم. Press Enter 

صفحه 29:
۴ در اين حللت نيز همانند قبل عمل ميكنيم. با اين تفاوت که کمترین تعداد نياز يك سطراست. * بنابراين ابتدا مقدار نیاز (1660) را محاسبه میکنیم. ۴ تعداد نیاز های هر فرایند را جمع میزنیم و کمترین را انتخاب میکنیم. ۴ اگر سطر مربوط به کمترین مقدار از مقادیر منبع باقیمانده بیشتر بود. یم که حالت تام است. در غیر این صورت فرایند با یبن نیاز را حذف میکنیم و تعداد منلبع تخصیص یافته آنرا را آزاد میکنیم و مراحل را دوباره تکرار می کنیم. 

صفحه 30:
ee eee 2110 D E 1101000 اكلا 010010 0 D ‏ع‎ 5 66210 B 72| ه | 2 | (0) لام لك اكه 1 | 31011 ۸ 010 8 تعداد | نوع لا 511 8 آفرایند ]| 2 ۸ Resourc e MAX Allocation الم با = 3 

صفحه 31:
2 د اذاه ۱ 2 | 8 = ۲7۱۱۳۱۱۳۱۱۵۳ 1 1 | 1 | 1 ۲ 6 1۱1 ۱1 ۱0۱4۱2 ۱1 ۱ 0 ۱3۱1 ۱0 ۱0۱ 4 85 ۱۱۵۲۳۲۱۵۵ 0 ۱2 ۱1 ۱ 2 ۵2 A ۱3۱0۱1۱1۱4۱1۱1 ۱ 1 ۱1۱1 ۱002 + | لا 8.۱۱1 ۲۱ | 6 | ۲۱۲ ۱ ۱5 | فرایند Alloc Need max- Max = Allocation Ai oS بانكدا 7 =) 

صفحه 32:
و جدول ۸۷۵/۵016 را محاسبه میکنیم. ۳190 “ee ‏رن‎ 0 Available= ‏ایند‎ ‎Ne Resourc Resli] - A+ li] 230 e ۱ 3 7 ‏تعداد نوع‎ 5۲۱۵۱۲0۱۳۱ | GG pei 8 | 645 2 ۱۱|] ‏ال‎ + | - 5 3 ‏ع‎ ۱0۱0۱0۱0 | |] 4 ۲ | 422 | + ۱513۱2121 2 ‏لا‎ | 2 

صفحه 33:
مقدار این سطر با با منایع باقیمانده مقایسه میکنیم ‎te ۰‏ جه به ‎Jase‏ 40 کدام فرایند کمترین تعداد منابع را نیاز دارد؟ Eni منایع باقمندم کمتراست سطر را حذف و منابع را آزاد ميكنيم. ‎ls | place"‏ رانا ‎"Need Available 815 5 + ‏سح‎ ‎1۱1 1010| 2 0 1 0 ۱1 ۱1 ۱2 ۱ 4 5 0 3 | 1 ۱0 0۱ 4 | ‏تا‎ 1 2 9 U 5 Uy = U 0 21111014 ‎ ‎ ‎ ‎ ‎ ‎ ‎6۱۲۳۳ | ۵ | 6۲| ‎ ‎Allocation ‏فرایند‎ | ٩ ۱ 5 | ۲ ۵ ‏۵یا‎ ‎85 ۵ a 5-5-6 ۶ 00۵ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 34:
۴ الگوریتم بانکداران و اجتناب از بن بست نمیتولند به طور حتم بروزبن بست را بینی کند. گاهی آنرا حدس میزند و گاهی انرا | 5 0 0 مار ‎ae ag‏ معایب روش اجتناب از بن بست: * حداکثر منابع باید از قبل مشخص باشد. * فرایند های مورد نظر باید مستقل باشند (همگام سازی نشده باشند) * تعداد منابع تخصیصی بای * فرایندی که منبعی را در اختیار داشته باشد نمیتواند خارج گردد ثابت باشد. 

صفحه 35:
* روشی است که در آن اجازه برای انجام فرایند و هر تخصیص منبع داده میشود و سیستم عامل مرتبا وجود بن بست را بررسی ميکند. * در راهبرد کشف بن بست به صورت زیر عمل میشود: * قطع تمام فرایندهای در بن بست * برگشت هر یک از فرایند هاى در بن بست به نقاطی که از قبل برای بررسی تعیین شده اند و شروع مجدد تمام فرایند ها قطع پیگیری فرایندهای در بن بست تا جایی که دیگر بن بست وجود نداشته باشد قبضه کردن پی در پی منابع تا جایی که دیگر بن بست وجود نداشته باشد. 

صفحه 36:
۴ برای بند های ۳ و ۴ معیار انتخاب میتولند یکی از موارد زیر باشد: * کمترین وقت مصرفی از پردازنده تا کنون * کمترین خروجی تولید شده تا کنون بیشترین زمان باقیمانده تخمینی * کمترین منابع تخصیص داده شده تا کنون * کمترین اولویت 

صفحه 37:
۲ 4 oe ۱ a ‏هر راهبرد بن بست مزایا و معایب مخصوص به خود را دارد‎ ‏شاید بهتر باشد از ترکیبی از راهبرد ها استفاده کنیم:‎ ‏تقسیم بندی منابع در تعدادی گروه های مختلف‎ * ‏استفاده از راهبرد مرتب سازی خطی‎ * ‏در داخل یک گروه از نیع استفاده از بهترین الگوریتم برای آن گروه‎ * 

صفحه 38:
Major Disadvantages اوه ‎“Delays process initiation‏ “ure resource requirements ‘aut he nora by processes ‘Preempte more fteathan Disalows incremental resource requests ‘Fucus resoutceraqutemente sust be inown by OS “Processes can be blocked for ong petods مها اوه منود ‘Works wellfoc processes that pefoem a single burst of activity “No preemption necessary Convenient hen applied to resources chose state con be saved and tesoted casi ‘Feasible to enforce vi compile-time “Needs ne nun-sinae computation since problem iz salvedin system design “No preemption ne “Never delays process inition ‘Foctates online handling Different Schemes Requesting al reson Resource ondeing Manipulate to find at least one sae path Conservative; undersommits Midway between that of| detection nd prevention ‘Very Hoel; requestedaesautc seo granted where possible Approach Avoidance Detection 

صفحه 39:


صفحه 40:
5 ‏د‎ 8 ۲ 5 3 ۳ a ‏برای منابع قابل استفاده مجدد و منابع مصرف شدنى مثالى‎ بزنید؟ * برای منلبع قلبل استفاده مجدد میتوان به پردازنده. کانال های ورودی خروجی. حافظه اصلی و انویه. دستگاه هاء و ساختمان داده هایی چون پرونده هاء پایگاه داده هاء و راهنما ها اشاره کرد. * وقفه ها. سیگنالها. پیامها و اطلاعات میانگیر ورودی خروجی مثالهایی از منابع غیر قابل استفاده مجدد هستند. 

صفحه 41:
سه شرط لازم برای بروز بن بست را نام ببرید؟ * انحصار متقابل: در هر زمان فقط یک فرایند میتواند از منبع استفاده کند. * نگهداشت و انتظار: در حالی که فرایند منبع تخصیص داده شده را نکه میدارد منتظر تخصیص منبع دیگری است. قبضه نکردن:هنگامی که فرایندی منبعی را در اختیار دارد نتوان آن را به زور باز پس گرفت. 

صفحه 42:
چهار شرطی که بن بست را بوجود می آورند نام ببرید؟ * سه شرط بالا بعلاوه : انتظار مدور: زنجیره بسته ای از فرایند ها وجود دارد که هر یک حداقل یک منبع مورد نیاز برای فرایند بعد در زنجیره را نگه میدارد. 

صفحه 43:
نه از شرط نگه داشت و انتظار میتوا پیشگیری کرد؟ 5 با ملزم کردن فرایند به درخواست یکباره تمام منابع مورد نیاز و مسدود کردن لن تا موقعی که تمام منلبع در اختیارش گذاشته شود میتوان از بروز شرط نگه داشتن و انتظار جلوگیری کرد. 

صفحه 44:
دو راه پیشگیری از شرط قبضه نکردن را نام ببرید؟ * ابتدا اگر فرایندی برخی منابع را نگه داشته است درخواست و بعديش رد ميشود. فرايند بايد منابعى را كه در د 1 دارد آزاد سيس در صورت نياز درخواست منبع ميكند وبه لن منبع ديكرى داده ميشود. * همچنین در صورتیکه یک فرایند درخواست منبعی را دارد که توسط فرايند ديكر نكه داشته ميشود. سيستم عامل ممكن است فرايند دوم را قبضه كند و منابع آن را آزاد كند. 

صفحه 45:
نه میتوان از شرط انتظار مدور پیشگیری کرد؟ 5 با تعریف یک ترتیب خطی از انواع منابع میتوان از بروز شرط انتظار مدور جلوگیری کرد.اگر فرایندی منبعی از نوع 8 را به خود اختصاص ‎vols‏ در ادامه فقط منابعی را میتواند درخواست کند که (در ترتیب خطی) نوع آنها بعد از 8 قرار گرفته باشد. 

صفحه 46:
از تفا وت بین اجتناب از بن: ب ‎RES oc‏ بن ب © و.پیشگیری بن بست چیست؟ پیشگیری از بن بست: در این راهبرد با کنترل كردن درخواست های منلبع از بروز یکی از شرلیط ۴ گلنه بروزبن بست جلوگیری ميشود. میتوان به طور غیر مستقیم با پیشگیری از وقوع یکی از۳ شرط لازم برای وقوع بن بست از آن پیشگیری کرد و پا به طور مستقیم از وقوع شرط چهارم (انتظار مدور) پیشگیری کرد. 

صفحه 47:
* اجتناب ازبن بست: این روش اجازه وقوع شرایط ۲ کلنه را میدهد اما در انتخابها به گونه ای عمل میکند که اطمینان حاصل کند که بن بستی رخ نمیدهد. * کشف‌بن بست: در اين روش منلبع در صورت امکان به فرایند ها اختصاص می یابند. به صورت دوره ای سیستم عامل الگوریتمی را برای شناسایی شرط انتظار مدور انجام میدهد.