صفحه 1:
صفحه 2:
به مسدود شدن دائمی مجموعه ای از فر آیندها در اثر رقابت
برای منابع سیستم یا ارتباط با همدیگر گفته می شود.
#هیچ راه حل موثری ندارد.
صفحه 3:
صفحه 4:
ofQ
4
Release
A
24 Release
Required 1
Geta
3 3 0
Required ۳
Geta 74
4
Progress
> ote
GetA Gel B_ Release A Release B
نس
۲۰۳ سب
B Required
Figure 6.2. Example of Deadlock [BACO98]
صفحه 5:
Progress
of Q
a
Release
2 Release
Required 9
Geta
8
Required
Get B
GetA ReleaseA Get B Release B
eyo Ey
A Required B Required
Figure 6.3 Example of No Deadlock [BACO98]
صفحه 6:
در یک زمانی توسط فرآیند مصرف می گردد اما تمام نمی
گردد.
فرآیندها منابع قابل مصرف مجدد را بعد از در اختیار گرفتن و
استفاده آژادمی کند تا دیگران یز از آن استفاده sa
# پردازنده هاء کانالهای WO حافظه اصلی و جانبی» فایلها؛
پایگاههای داده و سمافورها از این دسته هستند.
85
"اد صورتي كد فر ييدى .يكك منيع زا دز أختيا يرد و منبع
ديكرى را درخواست كند احتماً بن بست وجود دارد.
صفحه 7:
ترا سس 42
Process P Process Q
Action Action
Po Request (D) ‘Request (T)
۳ Lock (D) Lock (T)
رز |Request (T) Request (D)
p; | Lock (T) Lock (D)
ير __| Perform function Perform function
ps | Unlock (D) Unlock (T)
pg _| Unlock (T) Unlock (D)
Figure 6.4 Example of Two Processes Competing for Reusable Resources
صفحه 8:
سلسم تم اسم دم مد
فرض کنید حداکثر حافظه قابل تخصیص برابر 660606
باشد و رخدادهای زیر اتفاق بیفتند:
scat 04 yes a 70K nes
Request 60K bytes; Request 80K bytes;
۴ اگر هر دو فرآیند به درخواست دوم خود برسند بن بست اتفاق
می افتد.
صفحه 9:
* فرآيندها اين منابع را ايجاد مى كنند و از بين مى برند.
© وقفه هاء سيكنالهاء بيغامها و اطلاعات موجود در بافرهاى WO
از دسته منابع مصرفى هستند.
#اكر دريافت پیغام بصورت ۲۳۳ باشد احتمال بن بست
وجود دارد.
#البته در حالت کلی» تر کیبات نادری از رخدادها منجر به بن
Hye ae
صفحه 10:
ین مثال اگر دریافت پیغام بصورت bhoobieny باشد بن
بست اتفاق می افتد.
P2
Receive(P1);
(P1, M2);
صفحه 11:
۴ انحصار متقابل
۰ در هر لحظه از زمان فقط یک فرآیند منبع را در اختیار داشته باشد.
© نگه داشتن و انتظار
© منیعی را در اختیار بگيريم و منبع دیگری را درخواست کنیم.
* راه حل: یک فرآیند تمام منابع مورد نیاز را در یک لحظه درخواست
aig
©0000 هدر رفن وقت فرآيند و *
* هدر رقتن متابع
9. عدم تعليق
* به حالنى كفته مى شود که نتوان به زور منابعی که فرآیند در اختیار دارد را پس گرفت.
* راه حل: اگر درخواستهای بعدی یک فرآیند قابل انجام نباشنده آن فرآیند موظف است که
منابعی را که در اختبار دارد پس دهد.
* راه حل: اگرف رآیندی مت | درخواست کند که در اختیار فر آیند د: است Ne
ee بت سمل
صفحه 12:
#انتظار حلقوی
* مى توان با اعمال یک نظم خطی به منابع از اين موضوع جلو كيرى
نمود:
Resource
Figure 6.5 Circular Wait
صفحه 13:
هر بار که درخواست یک تخصیص جدید بررسی می شود؛
ee @ 1 5
بصورت. دینامیک تصمیم می گیریم که آیا انجام اين تخصیص
(Les ت به بن بست منجر شود يا نه؟
#نیاز است که از درخواستهای آینده فرآیندها اطلاع داشته
با
eee
صفحه 14:
4 eid
*روش اول: جلوگیری از شروع ف رآیند
0-68, Roy oR) le shy”
O FO Oey +5 On) 3354) HE بردار منابع *
6 ماتریس درخواستها *
7 ماتریس تخصیص 4
صفحه 15:
زااه ها رم + را عر .1
a
2 Cy = Rj for alli,j
Ay Ala 3. Ay = Cy forall sj
Allocation = A= [42 422+ Arm
Ant مش Aguy
eng ip a oe pe TS 4 Coe OS ana FI آن منیع را به ف رآیند
ندهید. یعنی فقط در صورت برقراری شرط زیر فرآیند 0+ را شروع کنید:
a
R2Crayt LC,
صفحه 16:
روش دوم: عدم تخصیص منابع
* تحت عنوان الگوریتم بانکدار شناخته می شود.
* وضعیت سیستم برابر است با تخصیص جاری منابع به فرآیندها
اگر حداقل یکک دنباله وجود داشته باشد که منجر به بن بست نشود
می گوییم آن حالت امن است.
حالت غیر امن حالتی است که تمام دنباله ها به بن بست منجر می
شوند.
صفحه 17:
۱۹۱ TAR RR Che Colne ead he Reed oa
‘Aflocation Matrix
Available Vector
(a) Initial stato
صفحه 18:
207 صا جص جا) ©15) جزور©) وخام5) ه خأص جمشمواجوسجاج2)
25 231 22 253
۰*۶
1
Available Vector
1
1
5
Claim Matris, Allocation Mateise
(b) F2 runs to completion
صفحه 19:
تمرم مر و ۱۱۱
2۱ 22 R3
7]
Available Vector
Allocation Matrizt
(c) Pl runs to completion
صفحه 20:
۱۱۱ برس و a Gl Ameo kN se ea @aracr
81 82 83
81 82 BB
| 9 1 31 4
a |
cm
0
7 Available Vector
21
0
0
Claim Mairi, Allocation Matrixx
(@) P3 runs to completion
صفحه 21:
ears
Resource Vector
RLOR BB
Alle cation Matraz 2] 1] 2
Available Vector
(a) Initial state
صفحه 22:
Oda cd 0 هم رس و ۱2
RI
oft
Available Vecior
Allocation Matrix
(b) Pl requests one amit each of RI and R3
صفحه 23:
© +
تعداد در < هر منبع پیشاپیش مشخص باشد.
ای
Li وت ْ
: ی بخرباند ایشا پیش مد
تعداد منابع قابل oe ۱
0 1 تخ ۱ | |
تخصيص بايد مشخ
ید مشخص باشد.
e
هیچ فرآیند
ى در حين داش
شتن منابع خا ae
ارج نشود.
صفحه 24:
فرآیندی که در ماتریس تخصیص دارای یک ردیف برابر صفر است
را علامت بزنید.
بردار 40 را برابر بردار منابع موجود یعنی () بگیرید.
در ماتریس نیازها دنبال فرآیند بدون علامتی بگردید که درخواستهای
آن از 0) کمتر است. اگر چنین فرآیندی وجود ندارد و بعضی
فرآیندها علامت نخورده اند» سیستم در بن بست به سر می برد.
در غير اين صورتء اين فرآيند را علامت بزنید و منابع تخصيص يافته
را از آن پس بگیرید و به 0 اضافه کنید. سپس به مرحله ۳ بروید.
صفحه 25:
Request Matrix Q Allocation Matrix A
Available Vector
Figure 6.9 Example for Deadlock Detection
صفحه 26:
* تمام فرآيندهايى كه در بن بست كير كرده اند را خاتمه دهید.
فرآیندهایی که در بن بست گیر کرده اند را به نقاط کنترلی از
پیش تایین شده بر گردانید.
؟ احتمال دارد همان بن بست دوباره اتفاق بیفتد.
یکی یکی فرآیندها را خاتمه دهید تا وقتیکه بن بست حذف
شود.
یکی یکی فرآیندها را تخليه كنيد تا وقتيكه بن بست حذف
شود.
صفحه 27:
0 مهس اک مت 0) جمتامواح 8
#تا کنون کمترین مقدار ممکن از وقت پردازنده مصرف شده
باشد.
# تا کنون کمترین مقدار خروجی تولید شده باشد.
زمان باقیمانده تخمینی OT بیشترین باشد.
تا کنون مجموع منابع تخصیص يافته به آن کمترین باشد.
# کمترین اولویت را داشته باشد.
صفحه 28:
4 ONS ead ae cael اب
* گروه بندی منایع
؟ استفاده از یک نظام ترتیبی بین گروهها
* استفاده از یک الگوریتم مناسب بین اعضای گروه
* كروهها:
* قابل جابجایی: مثل حافظه انویه
پیش گیری: نمام منابع مورد نياز را در یک لحظه درخواست کند. (نقض نگه داشتن و انتظار)
* منابع فرآیند: دستگاههای قابل تخصیص مثل فایلها
* جلوگیری: مثل الگوریتم بانکدار
* حافظه اصلى
* پیش گیری: تعیقفرآیند
0 منابع داخلی: دستگاههای 1/0
* پیش گیری: ترتيب خطى
صفحه 29:
۱۱ ۹۳ ۱7 0
صفحه 30:
20206 Or Uaacc vs سس