صفحه 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:
توسط فرآیند مصرف می گردد اما تمام نمی گردد.
* فرآیندها منیع قابل مصرف مجدد را بعد از در اختیار گرفتن و استفاده
آزاد می کنند تا دیگران نیز از آن استفاده کنند.
* پردازنده هاء کانالهای (1/6» حافظه اصلی و جانبی فایلها؛ پایگاههای
داده و سمافورها
* در صورتی که فرآیندی یک منبع را در اختیار بگیرد و من منبع دیگری را
درخواست کند احتمال بن بست وجود دارد.
صفحه 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:
سار و رب(
حداکثر حافظه قابل تخصیص: 600000
PL 2
Request 80K bytes; Request 70K bytes;
Request 60K bytes; Request 80K bytes;
صفحه 9:
* فرآيندها اين منابع را ايجاد مى كنند و از بين مى برند.
* وقفه هاء سيكنالهاء ييغامها و اطلاعات موجود در بافرهاى 41/0
اگر دریافت پیغام بصورت ۲۳۶-۳ باشد احتمال بن بست
وجود دارد.
صفحه 10:
ASS ZAZA اکن
PL P2
Receive(P2); Receive(P1);
Send(P2, M1); Send(P1, M2);
صفحه 11:
# انحصار متقابل
0 ,21 ۳
نگه داشتن و انتظار
*راه « Te deh
را رکه sha aan gap
#عدم بازپس گیری
#انتظار حلقوى
صفحه 12:
#انتظار حلقوی
* مى توان با اعمال یک نظم خطی به منابع از اين موضوع جلو كيرى
نمود:
Resource
Figure 6.5 Circular Wait
صفحه 13:
Oe ل asl
#نقض حداقل یکی از چهار شرط قبل (؟)
صفحه 14:
هر بار که درخواست یک تخصیص جدید بررسی می شود؛
بصورت دینامیک تصمیم می گیریم
اطلاع از درخواستهای آینده فرآیندها
صفحه 15:
*روش اول: جلوگیری از شروع ف رآیند
0-68, Roy oR) le shy”
* بردار منابع موجود (,0 ...۰ ,2 ,20 0
* ماتریس درخواستها 6
7 ماتریس تخصیص 4
صفحه 16:
صفحه 17:
1. 2 < ۷+ zai for all j
2. Cy = Rp for all i,j
3. Ay < Cy, forallé,j
صفحه 18:
* فقط در صورت برقراری شرط زین فرآیند 0+" را شروع کنید:
n
R,> ری + رس
Por زاك
صفحه 19:
رام ۱۹3
#روش دوم: عدم تخصیص منابع
؟ الگوریتم بانکدار
* وضعيت سيستم برابر است با تخصیص جاری منابع به فرآیندها
*حالت امن
۴حالت غیر امن
صفحه 20:
۱۹۱ TAR RR Che Colne ead he Reed oa
‘Aflocation Matrix
Available Vector
(a) Initial stato
صفحه 21:
207 صا جص جا) ©15) جزور©) وخام5) ه خأص جمشمواجوسجاج2)
51213
Available Vector
Claim Matris, Allocation Mateise
(b) F2 runs to completion
صفحه 22:
تمرم مر و ۱۱۱
| 2| 5
Available Vector
Allocation Matrizt
(c) Pl runs to completion
صفحه 23:
۱۱۱ برس و 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
صفحه 24:
ears
Resource Vector
RLOR BB
Alle cation Matraz 2] 1] 2
Available Vector
(a) Initial state
صفحه 25:
۱2 هم رس و Oda cd
RL
3
۳
Allocation Matrix
(b) Pl requests one amit each of RI and R3
صفحه 26:
Consider a system consisting of four processes and a single resource. The current state
of the claim and allocation matrices are:
Gene
جم عم ين د
What is the minimum number of units of the resource needed to be available for this
state to be safe?
صفحه 27:
فرآیندی که در ماتریس تخصیص دارای یک ردیف برابر صفر است
را علامت بزنید.
بردار 40 را برابر بردار منابع موجود یعنی () بگیرید.
در ماتریس نیازها دنبال فرآیند بدون علامتی بگردید که درخواستهای
آن از 0) کمتر است. اگر چنین فرآیندی وجود ندارد و بعضی
فرآیندها علامت نخورده اند» سیستم در بن بست به سر می برد.
در غير اين صورتء اين فرآيند را علامت بزنید و منابع تخصيص يافته
را از آن پس بگیرید و به 0 اضافه کنید. سپس به مرحله ۳ بروید.
صفحه 28:
Request Matrix Q Allocation Matrix A
Available Vector
Figure 6.9 Example for Deadlock Detection
صفحه 29:
ل 0 ور
* تمام فرآيندهايى كه در بن بست كير كرده اند را خاتمه دهيد.
فرآیندهایی که در بن بست گیر کرده اند را به نقاط کنترلی از
پیش تعبین شده پرگردانید.
یکی یکی فر آیندها را خاتمه دهید تا وقتیکه بن بست حذف
شود.
یکی یکی فرآیندها را قبضه کنید تا وقتيكه بن بست حذف
شود.
صفحه 30:
مهس اک مت 0) جمتامواح 8
#تا کنون کمترین مقدار ممکن از وقت پردازنده مصرف شده
باشد.
# تا کنون کمترین مقدار خروجی تولید شده باشد.
* زمان باقیمانده تخمینی آن بیشترین باشد.
تا کنون مجموع منابع تخصیص يافته به آن کمترین باشد.
# کمترین اولویت را داشته باشد.
صفحه 31:
۱۱ ۹۳ ۱7
صفحه 32:
صفحه 33:
/* program diningphilosophers */
semaphore fork [5] = {1};
int i;
void philosopher (int i)
while (true) {
think ();
wait (fork[i]);
wait (fork [(i+1) mod 5]);
eat();
signal (fork [(i+1) mod 5]);
signal (fork [i]) ;
}
?
void main()
parbegin (philosopher (0), philosopher (1),
philosopher (2), philosopher (3),
philosopher (4));
صفحه 34:
/* program diningphilosophers */
semaphore fork(5] - {1};
semaphore room = {4};
int i;
void philosopher (int i)
{
while (true) {
think();
wait (room) ;
wait (fork[i]);
wait (fork [(i+1) mod 5]);
eat ();
signal (fork [(i+1) mod 5]);
signal (fork[i]);
signal (room) ;
}
void main()
parbegin (philosopher (0), philosopher (1),
philosopher (2), philosopher (3),
philosopher (4));