Deadlock and Starvation
اسلاید 1: Concurrency: Deadlock and Starvationفصل ششم
اسلاید 2: Deadlockبه مسدود شدن دائمی مجموعه ای از فرآیندها در اثر رقابت برای منابع سیستم یا ارتباط با همدیگر گفته می شود.هیچ راه حل موثری ندارد.
اسلاید 3:
اسلاید 4:
اسلاید 5:
اسلاید 6: Reusable Resourcesدر یک زمانی توسط فرآیند مصرف می گردد اما تمام نمی گردد.فرآیندها منابع قابل مصرف مجدد را بعد از در اختیار گرفتن و استفاده آزاد می کنند تا دیگران نیز از آن استفاده کنند.پردازنده ها، کانالهای I/O، حافظه اصلی و جانبی، فایلها، پایگاههای داده و سمافورها از این دسته هستند.در صورتی که فرآیندی یک منبع را در اختیار بگیرد و منبع دیگری را درخواست کند احتمال بن بست وجود دارد.
اسلاید 7: Example of Deadlock
اسلاید 8: Another Example of Deadlockفرض کنید حداکثر حافظه قابل تخصیص برابر 200K باشد و رخدادهای زیر اتفاق بیفتند:اگر هر دو فرآیند به درخواست دوم خود برسند بن بست اتفاق می افتد.P1. . .. . .Request 80K bytes;Request 60K bytes;P2. . .. . .Request 70K bytes;Request 80K bytes;
اسلاید 9: Consumable Resourcesفرآیندها این منابع را ایجاد می کنند و از بین می برند.وقفه ها، سیگنالها، پیغامها و اطلاعات موجود در بافرهای I/O از دسته منابع مصرفی هستند.اگر دریافت پیغام بصورت blocking باشد احتمال بن بست وجود دارد.البته در حالت کلی، ترکیبات نادری از رخدادها منجر به بن بست می شوند.
اسلاید 10: Example of Deadlockدر این مثال اگر دریافت پیغام بصورت blocking باشد بن بست اتفاق می افتد.P1. . .. . .Receive(P2);Send(P2, M1);P2. . .. . .Receive(P1);Send(P1, M2);
اسلاید 11: Conditions for Deadlockانحصار متقابلدر هر لحظه از زمان فقط یک فرآیند منبع را در اختیار داشته باشد.نگه داشتن و انتظارمنبعی را در اختیار بگیریم و منبع دیگری را درخواست کنیم.راه حل: یک فرآیند تمام منابع مورد نیاز را در یک لحظه درخواست کند.ایراد:هدر رفتن وقت فرآیند و CPUهدر رفتن منابععدم تعلیقبه حالتی گفته می شود که نتوان به زور منابعی که فرآیند در اختیار دارد را پس گرفت. راه حل: اگر درخواستهای بعدی یک فرآیند قابل انجام نباشند، آن فرآیند موظف است که منابعی را که در اختیار دارد پس دهد.راه حل: اگرفرآیندی منبعی را درخواست کند که در اختیار فرآیند دیگری است، سیستم عامل ممکن است فرآیند دوم را به حالت تعلیق درآورد و از او بخواهد که منابع را پس دهد.
اسلاید 12: Conditions for Deadlockانتظار حلقویمی توان با اعمال یک نظم خطی به منابع از این موضوع جلوگیری نمود.
اسلاید 13: Deadlock Avoidanceهر بار که درخواست یک تخصیص جدید بررسی می شود، بصورت دینامیک تصمیم می گیریم که آیا انجام این تخصیص ممکن است به بن بست منجر شود یا نه؟نیاز است که از درخواستهای آینده فرآیندها اطلاع داشته باشیم.
اسلاید 14: Deadlock Avoidanceروش اول: جلوگیری از شروع فرآیندبردار منابع R=(R1, R2, …, Rm) بردار منابع خالی (موجود( V =(V1, V2, …, Vm)ماتریس درخواستها C ماتریس تخصیص A
اسلاید 15: جلوگیری از شروع فرآینداگر تخصیص یک منبع به فرآیند منجر به بن بست می شود، آن منبع را به فرآیند ندهید. یعنی فقط در صورت برقراری شرط زیر، فرآیند n+1 را شروع کنید:
اسلاید 16: Resource Allocation Denialروش دوم: عدم تخصیص منابعتحت عنوان الگوریتم بانکدار شناخته می شود.وضعیت سیستم برابر است با تخصیص جاری منابع به فرآیندهااگر حداقل یک دنباله وجود داشته باشد که منجر به بن بست نشود می گوییم آن حالت امن است.حالت غیر امن حالتی است که تمام دنباله ها به بن بست منجر می شوند.
اسلاید 17: Determination of a Safe State Initial State
اسلاید 18: Determination of a Safe State P2 Runs to Completion
اسلاید 19: Determination of a Safe State P1 Runs to Completion
اسلاید 20: Determination of a Safe State P3 Runs to Completion
اسلاید 21: Determination of an Unsafe State
اسلاید 22: Determination of an Unsafe State
اسلاید 23: Deadlock Avoidanceتعداد درخواستهای هر منبع باید پیشاپیش مشخص باشد.فرایند تحت بررسی باید مستقل باشد.تعداد منابع قابل تخصیص باید مشخص باشد.هیچ فرآیندی در حین داشتن منابع خارج نشود.
اسلاید 24: Deadlock Detectionفرآیندی که در ماتریس تخصیص دارای یک ردیف برابر صفر است را علامت بزنید.بردار W را برابر بردار منابع موجود یعنی V بگیرید.در ماتریس نیازها دنبال فرآیند بدون علامتی بگردید که درخواستهای آن از W کمتر است. اگر چنین فرآیندی وجود ندارد و بعضی فرآیندها علامت نخورده اند، سیستم در بن بست به سر می برد.در غیر این صورت، این فرآیند را علامت بزنید و منابع تخصیص یافته را از آن پس بگیرید و به W اضافه کنید. سپس به مرحله 3 بروید.
اسلاید 25: Deadlock Detection
اسلاید 26: Strategies once Deadlock Detectedتمام فرآیندهایی که در بن بست گیر کرده اند را خاتمه دهید.فرآیندهایی که در بن بست گیر کرده اند را به نقاط کنترلی از پیش تایین شده برگردانید.احتمال دارد همان بن بست دوباره اتفاق بیفتد.یکی یکی فرآیندها را خاتمه دهید تا وقتیکه بن بست حذف شود.یکی یکی فرآیندها را تخلیه کنید تا وقتیکه بن بست حذف شود.
اسلاید 27: Selection Criteria Deadlocked Processesتا کنون کمترین مقدار ممکن از وقت پردازنده مصرف شده باشد.تا کنون کمترین مقدار خروجی تولید شده باشد.زمان باقیمانده تخمینی آن بیشترین باشد.تا کنون مجموع منابع تخصیص یافته به آن کمترین باشد.کمترین اولویت را داشته باشد.
اسلاید 28: A Integrated solutionگروه بندی منابعاستفاده از یک نظام ترتیبی بین گروههااستفاده از یک الگوریتم مناسب بین اعضای گروهگروهها:قابل جابجایی: مثل حافظه ثانویهپیش گیری: تمام منابع مورد نیاز را در یک لحظه درخواست کند. (نقض نگه داشتن و انتظار)منابع فرآیند: دستگاههای قابل تخصیص مثل فایلهاجلوگیری: مثل الگوریتم بانکدارحافظه اصلیپیش گیری: تعلیق فرآیندمنابع داخلی: دستگاههای I/Oپیش گیری: ترتیب خطی
اسلاید 29: Dining Philosophers Problem
اسلاید 30: UNIX Concurrency Mechanismsلولهپیغامحافظه مشترکسمافور سیگنال
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.