بن بست و گرسنگی

بن بست و گرسنگی

اسلاید 1: فصل ششم:همزمانی:بن بست و گرسنگی

اسلاید 2: مباحث این فصل:اصول بن بستپیشگیری از بن بستاجتناب از بن بستکشف بن بستیک راهبرد مجتمع برای بن بستسؤالات دوره ای

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

اسلاید 4: مثالی از بن بست:یک مثال بن بست، ترافیک است.در رانندگی قانون این است که هر خودرو باید تسلیم خودروی سمت راست باشد.در این صورت در حالت زیر چه رخ میدهد؟

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

اسلاید 6: منابع قابل استفاده مجدد:منابعی هستند که در هر لحظه از زمان تنها توسط یک فرایند قابل استفاده اند و استفاده از آنها موجب به پایان رسیدن آنها نمیشود(بدون آسیب دیدن آزاد میشوند)فرایند ها منابع را بدست می آورند و سپس آنها را برای استفاده مجدد توسط سایر فرایند ها آزاد میکنند.پردازنده، کانالهای I/O، حافظه اصلی و ثانوی، دستگاه ها و ساختمان داده هایی مثل پرونده ها، پایگاه های داده و راهنماها از این دسته اند.بن بست زمانی رخ میدهد که یک فرایند منابع را نگه دارد و منبع دیگری درخواست کند.

اسلاید 7: منابع مصرف شدنی:این منابع تولید میشوند و از بین میروندوقفه ها، علامتها، پیامها و اطلاعات بافر I/O از این نمونه اند.کشف بن بستهای حاصل از این منابع بسیار مشکل است و ممکن است ترکیب نادری از حوادث آنها را ایجاد کند.

اسلاید 8: شرایط لازم برای ایجاد بن بست:انحصار متقابل(Mutual Exclusion): در هر لحظه تنها یک فرایند میتواند از یک منبع استفاده کند.گرفتن و منتظر ماندن(Hold and Wait):هنگام درخواست منبع جدید فرایند منابع قبلی تخصیص یافته را آزاد نمیکند.قبضه نکردن یا نبود پس گیری(No Preemption):منابع به زور قابل پسگیری نیستند.

اسلاید 9: شرایط لازم برای ایجاد بن بست:انتظار مدور(Circular Wait):زنجیر بسته ای از فرایند ها وجود دارد، بطوریکه هر یک حداقل یک منبع مورد نیاز فرایند بعد در زنجیره را نگه دارد.

اسلاید 10: گراف تخصیص منابع:گراف تخصیص منابع یک گراف جهت دار است که نحوه تخصیص منابع به فرایند ها را در هر لحظه از زمان نشان میدهد.برای تشخیص بن بست باید گراف تخصیص منابع را بعد از هر درخواست، هر تخصیص، یا هر ترخیص به روز کرد.در گراف ، منابع را با و فرایند را با نشان میدهیم.وجود چرخه در گراف بیانگر بروز بن بست است.PSPSفرایند P منبع S را در اختیار داردفرایند P در انتظار منبع S است

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

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

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

اسلاید 14: پیشگیری از بن بست:نقض شرط انتظار مدور: مرتب کردن منابع به صورت خطی:به هر منبع یک شاخص نسبت داده میشود. در این صورت فرایند میتواند ابتدا منبع Ri و سپس منبع Rj را درخواست کند اگر i<j معایب این روش:کند شدن فرایندهارد کردن غیر ضروری دسترسی به منابع

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

اسلاید 16: اجتناب از بن بست:عدم شروع فرایند:سیستمی از n فرایند و m نوع مختلف از منابع را در نظر بگیرید. بردارها و ماتریسهای زیر را تعریف میکنیم:آرایه R[i] آرایه Available[i] : تعداد منابع موجود هر یک از منابع را نشان می دهد.ماتریس دو بعدی Allocation[i][j]: تعداد هر یک از انواع منابع در اختیار فعلی هر یک ار فرآیندهاآرایه max[i][j]: حداکثر نیاز فرآیند i به منبع jماتریس دوبعدی Need[i][j]: نیاز باقی مانده هر یک از فرآیند ها از منابع برای تکمیل کار خود

اسلاید 17: اجتناب از بن بست:C11 C12 … C1mC21 C22 … C2m : : : :Cn1 Cn2 … CnmA11 A12 … A1mA21 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]=kAllocation= A[i][j]=k

اسلاید 18: اجتناب از بن بست:3 نکته بدیهی است:تعداد منابع، یا تخصیص داده شده اند یا موجودند.هیچ فرایندی نمیتواند بیش از کل منابع سیستم درخواست کند.تعداد فرایندهای اختصاص یافته نمیتواند بیش از حداکثر نیاز فرایند باشد.بنابراین برای اجتناب از بن بست فرایند را تنها درصورتی شروع میکنیم که:

اسلاید 19: اجتناب از بن بست:عدم تخصیص منبع: به این راهبرد الگوریتم بانکداران نیز گفته میشود.حالت سیستم، تخصیص جاری منابع به فرایندها است، لذا حالت سیستم شامل دو بردار Available,Resource و دو ماتریس Max,Allocation میباشد.حالت مطمئن: حالتی است که در آن حداقل یک ترتیب از فرایندها وجود دارد که میتوانند اجرا و کامل شوند، بدون اینکه حالت بن بست ایجاد شود.

اسلاید 20: الگوریتم بانکداران:مقادیر مورد نیاز هر فرایند را بدست می آوریم.(Need)کمترین را در نظر میگیریم. اگر کمترین مقدار از مقادیر منبع باقیمانده بیشتر بود، نتیجه میگیریم که حالت ناامن است. در غیر این صورت فرایند با کمترین نیاز را حذف میکنیم و تعداد منابع تخصیص یافته آنرا را آزاد میکنیم و مراحل را دوباره تکرار میکنیم.

اسلاید 21: الگوریتم بانکداران:توجه : در حل مسائل بانکداران باید جداول و اطلاعات زیر را داشته باشیم:جدول Allocationجدول Max یا جدول Needجدول Resource یا جدول Availableسپس بر حسب ورودی باید جداول زیر را بدست آوریم:جدول Allocationجدول NeedAvailable

اسلاید 22: الگوریتم بانکداران: با توجه به جداول زیر بگویید آیا حالت امن است؟این جدول بیان میکند تنها یک نوع منبع داریم.فرایند A به 6 منبع نیاز دارد و در حال حاضر 1 منبع به آن اختصاص یافته است.(برای فرایندB نیز به همین صورت)در حال حاظر از کل تعداد منابع تنها 2 منبع آزاد است.(Available=2)Press Enter

اسلاید 23: محاسبه Need : (Need=Max-Allocation)6 - 155 - 144 - 227 - 4361514274Press Enterالگوریتم بانکداران:

اسلاید 24: پیدا کردن کوچکترین مقدارNeed:Availavle=2Availavle=2Availavle=2Availavle=2فرایندAllocationMaxNeedA165B154M242S4732<2(Available)Available=Available + 24الگوریتم بانکداران:Press Enter

اسلاید 25: Availavle=4Availavle=4Availavle=4Availavle=4فرایندAllocationMaxNeedA165B154M242S473پیدا کردن کوچکترین مقدارNeed:3<4(Available)Available=Available + 48Press Enterالگوریتم بانکداران:

اسلاید 26: Availavle=8Availavle=8Availavle=8Availavle=8فرایندAllocationMaxNeedA165B154M242S473پیدا کردن کوچکترین مقدارNeed:4<8(Available)Available=Available + 19الگوریتم بانکداران:Press Enter

اسلاید 27: Availavle=9Availavle=9Availavle=9Availavle=9فرایندAllocationMaxNeedA165B154M242S473پیدا کردن کوچکترین مقدارNeed:5<9(Available)Available=Available + 110Press Enterالگوریتم بانکداران

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

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

اسلاید 30: الگوریتم بانکداران:مثال: آیا حالت زیر یک حالت امن است ؟ResourceResourceنوعتعدادR6S3T4U2Press Enter

اسلاید 31: مرحله اول :جدول Need را محاسبه میکنیم.AllocationAllocationAllocationAllocationAllocationMaxMaxMaxMaxNeed=max-AllocNeed=max-AllocNeed=max-AllocNeed=max-AllocNeed=max-AllocفرایندRSTURSTURSTU+A3011411111002B0100021201124C1110421031004D1101111100101E0000211021104الگوریتم بانکداران:Press Enter

اسلاید 32: جدول Available را محاسبه میکنیم.ResourceResourceنوعتعدادRSTUAllocationAllocationAllocationAllocationAllocationفرایندRSTUA3011B0100C1110D1101E0000+Available=Res[i] - A[+][i]Available=Res[i] - A[+][i]نوعتعدادRSTU6 - 513 - 304 - 222 - 2063425322الگوریتم بانکداران:Press Enter

اسلاید 33: با توجه به جدول Need کدام فرایند کمترین تعداد منابع را نیاز دارد؟ مقدار این سطر را با منابع باقیمانده مقایسه میکنیمAllocationAllocationAllocationAllocationAllocationNeedNeedNeedNeedNeedفرایندRSTURSTU+A301111002B010001124C111031004D110100101E000021104AvailableAvailableنوعتعدادRSTU1020 چون مقدار آن از منابع باقیمانده کمتر است سطر را حذف و منابع را آزاد میکنیم. عملیات را برای بقیه سطر ها نیز انجام میدهیم.الگوریتم بانکداران:Press Enter

اسلاید 34: معایب الگوریتم بانکداران:الگوریتم بانکداران و اجتناب از بن بست نمیتواند به طور حتم بروز بن بست را پیش بینی کند. گاهی آنرا حدس میزند و گاهی آنرا اطمینان میدهد.معایب روش اجتناب از بن بست:حداکثر منابع باید از قبل مشخص باشد.فرایند های مورد نظر باید مستقل باشند (همگام سازی نشده باشند)تعداد منابع تخصیصی باید ثابت باشد.فرایندی که منبعی را در اختیار داشته باشد نمیتواند خارج گردد

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

اسلاید 36: کشف بن بست:برای بند های 3 و 4 معیار انتخاب میتواند یکی از موارد زیر باشد:کمترین وقت مصرفی از پردازنده تا کنونکمترین خروجی تولید شده تا کنونبیشترین زمان باقیمانده تخمینیکمترین منابع تخصیص داده شده تا کنونکمترین اولویت

اسلاید 37: راهبرد مجتمع برای بن بست:هر راهبرد بن بست مزایا و معایب مخصوص به خود را دارد شاید بهتر باشد از ترکیبی از راهبرد ها استفاده کنیم:تقسیم بندی منابع در تعدادی گروه های مختلفاستفاده از راهبرد مرتب سازی خطیدر داخل یک گروه از منابع استفاده از بهترین الگوریتم برای آن گروه

اسلاید 38: خلاصه رویکرد های پیشگیری، اجتناب و کشف بن بست:

اسلاید 39: سؤال و پاسخ : ? ? ? ? ?

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

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

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

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

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

اسلاید 45: سؤال ششم:چگونه میتوان از شرط انتظار مدور پیشگیری کرد؟با تعریف یک ترتیب خطی از انواع منابع میتوان از بروز شرط انتظار مدور جلوگیری کرد.اگر فرایندی منبعی از نوع R را به خود اختصاص داده، در ادامه فقط منابعی را میتواند درخواست کند که (در ترتیب خطی) نوع آنها بعد از R قرار گرفته باشد.

اسلاید 46: سؤال هفتم:تفاوت بین اجتناب از بن بست، کشف بن بست و پیشگیری از بن بست چیست؟پیشگیری از بن بست: در این راهبرد با کنترل کردن درخواست های منابع از بروز یکی از شرایط 4 گانه بروز بن بست جلوگیری میشود. میتوان به طور غیر مستقیم با پیشگیری از وقوع یکی از3 شرط لازم برای وقوع بن بست از آن پیشگیری کرد و یا به طور مستقیم از وقوع شرط چهارم (انتظار مدور) پیشگیری کرد.

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