سیستم بن بست فصل۶

سیستم بن بست فصل۶

اسلاید 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 DeadlockP1. . .. . .Receive(P2);Send(P2, M1);P2. . .. . .Receive(P1);Send(P1, M2);

اسلاید 11: Conditions for Deadlockانحصار متقابلنگه داشتن و انتظارراه حل: یک فرآیند تمام منابع مورد نیاز را در یک لحظه درخواست کند.عدم بازپس گیریانتظار حلقوی

اسلاید 12: Conditions for Deadlockانتظار حلقویمی توان با اعمال یک نظم خطی به منابع از این موضوع جلوگیری نمود.

اسلاید 13: DeadLock Preventionنقض حداقل یکی از چهار شرط قبل (؟)

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

اسلاید 15: Deadlock Avoidanceروش اول: جلوگیری از شروع فرآیندبردار منابع R=(R1, R2, …, Rm) بردار منابع موجود V =(V1, V2, …, Vm)ماتریس درخواستها C ماتریس تخصیص A

اسلاید 16: Process Initiation Denial

اسلاید 17: Process Initiation Denial

اسلاید 18: Process Initiation Denialفقط در صورت برقراری شرط زیر، فرآیند n+1 را شروع کنید:for all j

اسلاید 19: Resource Allocation Denialروش دوم: عدم تخصیص منابعالگوریتم بانکدار وضعیت سیستم برابر است با تخصیص جاری منابع به فرآیندهاحالت امنحالت غیر امن

اسلاید 20: Determination of a Safe State Initial State

اسلاید 21: Determination of a Safe State P2 Runs to Completion

اسلاید 22: Determination of a Safe State P1 Runs to Completion

اسلاید 23: Determination of a Safe State P3 Runs to Completion

اسلاید 24: Determination of an Unsafe State

اسلاید 25: Determination of an Unsafe State

اسلاید 26:

اسلاید 27: Deadlock Detectionفرآیندی که در ماتریس تخصیص دارای یک ردیف برابر صفر است را علامت بزنید.بردار W را برابر بردار منابع موجود یعنی V بگیرید.در ماتریس نیازها دنبال فرآیند بدون علامتی بگردید که درخواستهای آن از W کمتر است. اگر چنین فرآیندی وجود ندارد و بعضی فرآیندها علامت نخورده اند، سیستم در بن بست به سر می برد.در غیر این صورت، این فرآیند را علامت بزنید و منابع تخصیص یافته را از آن پس بگیرید و به W اضافه کنید. سپس به مرحله 3 بروید.

اسلاید 28: Deadlock Detection

اسلاید 29: Strategies once Deadlock Detectedتمام فرآیندهایی که در بن بست گیر کرده اند را خاتمه دهید.فرآیندهایی که در بن بست گیر کرده اند را به نقاط کنترلی از پیش تعیین شده برگردانید.یکی یکی فرآیندها را خاتمه دهید تا وقتیکه بن بست حذف شود.یکی یکی فرآیندها را قبضه کنید تا وقتیکه بن بست حذف شود.

اسلاید 30: Selection Criteria Deadlocked Processesتا کنون کمترین مقدار ممکن از وقت پردازنده مصرف شده باشد.تا کنون کمترین مقدار خروجی تولید شده باشد.زمان باقیمانده تخمینی آن بیشترین باشد.تا کنون مجموع منابع تخصیص یافته به آن کمترین باشد.کمترین اولویت را داشته باشد.

اسلاید 31: Dining Philosophers Problem

اسلاید 32: Dining Philosophers Problem