Mô tả:
Chöông 6 : Taéc ngheõn(Deadlock)
Moâ hình heä thoáng
Ñònh nghóa
Ñieàu kieän caàn cuûa deadlock
Resource Allocation Graph (RAG)
Phöông phaùp giaûi quyeát deadlock
Deadlock prevention
Deadlock avoidance
Deadlock detection
Deadlock recovery
Phöông phaùp keát hôïp ñeå giaûi quyeát Deadlock
Khoa KTMT
1
Vaán ñeà deadlock trong heä thoáng
Tình huoáng: moät taäp caùc process bò blocked, moãi process giöõ taøi
nguyeân vaø ñang chôø taøi nguyeân maø process khaùc trong taäp ñang giöõ.
Ví duï 1
– Giaû söû heä thoáng coù 2 file treân ñóa.
– P1 vaø P2 moãi process ñang môû moät file vaø yeâu caàu môû file kia.
Ví duï 2
– Semaphore A vaø B, khôûi taïo baèng 1
P0
P1
wait(A);
wait(B);
wait(B);
wait(A);
Khoa KTMT
2
Moâ hình hoùa heä thoáng
Heä thoáng goàm caùc loaïi taøi nguyeân, kí hieäu R1, R2,…, Rm , bao goàm:
– CPU cycle, khoâng gian boä nhôù, thieát bò I/O, file, semaphore,…
Moãi loaïi taøi nguyeân Ri coù Wi thöïc theå (instance).
Giaû söû taøi nguyeân taùi söû duïng theo kyø (Serially Reusable
Resources)
– Yeâu caàu (request): process phaûi chôø neáu yeâu caàu khoâng ñöôïc ñaùp öùng
ngay
– Söû duïng (use): process söû duïng taøi nguyeân
– Hoaøn traû (release): process hoaøn traû taøi nguyeân
Caùc taùc vuï yeâu caàu (request) vaø hoaøn traû (release) ñeàu laø system
call. Ví duï
–
–
–
–
request/release device
open/close file
allocate/free memory
wait/signal
Khoa KTMT
3
Ñònh nghóa
Moät tieán trình goïi laø deadlocked neáu noù ñang ñôïi moät
söï kieän maø seõ khoâng bao giôø xaûy ra.
Thoâng thöôøng, coù nhieàu hôn moät tieán trình bò lieân quan trong
moät deadlock.
Moät tieán trình goïi laø trì hoaõn voâ haïn ñònh (indefinitely
postponed) neáu noù bò trì hoaõn moät khoaûng thôøi gian daøi
laëp ñi, laëp laïi trong khi heä thoáng ñaùp öùng cho nhöõng
tieán trình khaùc .
i.e. Moät tieán trình saün saøng ñeå xöû lyù nhöng noù khoâng bao giôø
nhaän ñöôïc CPU.
Khoa KTMT
4
Ñieàu kieän caàn ñeå xaûy ra deadlock
Boán ñieàu kieän caàn (necessary condition) ñeå xaûy ra
deadlock
1. Loaïi tröø hoã töông (Mutual exclusion): ít nhaát moät taøi
nguyeân ñöôïc giöõ theo nonsharable mode (ví duï: printer;
ví duï sharable resource: read-only files).
2. Giöõ vaø chôø caáp theâm taøi nguyeân (Hold and wait): moät
process ñang giöõ ít nhaát moät taøi nguyeân vaø ñôïi theâm taøi
nguyeân do quaù trình khaùc ñang giöõ.
Khoa KTMT
5
Ñieàu kieän caàn ñeå xaûy ra deadlock (tt)
3. Khoâng tröng duïng (No preemption): (= no resource
preemption) taøi nguyeân khoâng theå bò laáy laïi, maø chæ coù
theå ñöôïc traû laïi töø process ñang giöõ taøi nguyeân ñoù khi
noù muoán.
4. Chu trình ñôïi (Circular wait): toàn taïi moät taäp {P0,…,Pn} caùc
quaù trình ñang ñôïi sao cho
P0 ñôïi moät taøi nguyeân maø P1 ñang giöõ
P1 ñôïi moät taøi nguyeân maø P2 ñang giöõ
…
Pn ñôïi moät taøi nguyeân maø P0 ñang giöõ
Khoa KTMT
6
Resource Allocation Graph (tt)
Kyù hieäu
Process:
Pi
Rj
Loaïi taøi nguyeân vôùi 4 thöïc theå:
Pi yeâu caàu moät thöïc theå cuûa Rj :
Pi ñang giöõ moät thöïc theå cuûa Rj :
Khoa KTMT
Rj
Pi
Rj
Pi
7
Ñoà thò caáp phaùt taøi nguyeân
Resource Allocation Graph
Resource allocation graph (RAG) laø ñoà thò coù höôùng, vôùi
taäp ñænh V vaø taäp caïnh E
– Taäp ñænh V goàm 2 loaïi:
P = {P1, P2,…, Pn }
(Taát caû process trong heä thoáng)
R = {R1, R2,…, Rm } (Taát caû caùc loaïi taøi nguyeân trong heä thoáng)
– Taäp caïnh E goàm 2 loaïi:
Caïnh yeâu caàu (Request edge): ø Pi Rj
Caïnh caáp phaùt (Assignment edge): Rj Pi
Khoa KTMT
8
Ví duï veà RAG
R3
R1
P1
P3
P2
R2
R4
Khoa KTMT
9
Ví duï veà RAG (tt)
R3
R1
P1
P3
P2
Deadlock xaûy ra!
R2
R4
Khoa KTMT
10
RAG vaø deadlock
Ví duï moät RAG chöùa chu trình nhöng khoâng xaûy ra
deadlock: P4 coù theå traû laïi instance cuûa R2.
P1
R1
P2
R2
P3
Lý do vì sao không
xảy ra deadlock ?
P4
Khoa KTMT
11
Ví dụ
số
R3
R1
P1
lượng P, R?
Xác định Pi dang năm giữ tài nguyên
nào? Yêu cầu tài nguyên nào?
Xét điều kiện cần deadlock? ĐK 1, 2, 4
P3
P2
Deadlock ?
R2
R4
Khoa KTMT
12
RAG vaø deadlock (tt)
RAG khoâng chöùa chu trình (cycle) khoâng coù deadlock
RAG chöùa moät (hay nhieàu) chu trình
– Neáu moãi loaïi taøi nguyeân chæ coù moät thöïc theå deadlock
– Neáu moãi loaïi taøi nguyeân coù nhieàu thöïc theå coù theå xaûy ra
deadlock
Khoa KTMT
13
Caùc phöông phaùp giaûi quyeát deadlock (1)
Ba phöông phaùp
1) Baûo ñaûm raèng heä thoáng khoâng rôi vaøo tình traïng
deadlock baèng caùch ngaên (preventing) hoaëc traùnh
(avoiding) deadlock.
Khaùc bieät
– Ngaên deadlock: khoâng cho pheùp (ít nhaát) moät trong 4 ñieàu
kieän caàn cho deadlock
– Traùnh deadlock: caùc quaù trình caàn cung caáp thoâng tin veà
taøi nguyeân noù caàn ñeå heä thoáng caáp phaùt taøi nguyeân moät
caùch thích hôïp
Khoa KTMT
14
Caùc phöông phaùp giaûi quyeát deadlock (2)
2) Cho pheùp heä thoáng vaøo traïng thaùi deadlock,
nhöng sau ñoù phaùt hieän deadlock vaø phuïc hoài heä
thoáng.
3) Boû qua moïi vaán ñeà, xem nhö deadlock khoâng
bao giôø xaûy ra trong heä thoáng.
Khaù nhieàu heä ñieàu haønh söû duïng phöông phaùp naøy.
– Deadlock khoâng ñöôïc phaùt hieän, daãn ñeán vieäc giaûm
hieäu suaát cuûa heä thoáng. Cuoái cuøng, heä thoáng coù theå
ngöng hoaït ñoäng vaø phaûi ñöôïc khôûi ñoäng laïi.
Khoa KTMT
15
1. Ngaên deadlock (deadlock prevention)
Ngaên deadlock baèng caùch ngaên moät trong 4 ñieàu kieän
caàn cuûa deadlock
1. Ngaên mutual exclusion
– ñoái vôùi nonsharable resource (vd: printer): khoâng laøm ñöôïc
– ñoái vôùi sharable resource (vd: read-only file): khoâng caàn thieát
Khoa KTMT
16
Ngaên deadlock (tt)
2. Ngaên Hold and Wait
– Caùch 1: moãi process yeâu caàu toaøn boä taøi nguyeân caàn thieát moät
laàn. Neáu coù ñuû taøi nguyeân thì heä thoáng seõ caáp phaùt, neáu khoâng
ñuû taøi nguyeân thì process phaûi bò blocked.
– Caùch 2: khi yeâu caàu taøi nguyeân, process khoâng ñöôïc giöõ baát kyø
taøi nguyeân naøo. Neáu ñang coù thì phaûi traû laïi tröôùc khi yeâu caàu.
– Ví duï ñeå so saùnh hai caùch treân: moät quaù trình copy döõ lieäu töø
tape drive sang disk file, saép xeáp disk file, roài in keát quaû ra
printer.
– Khuyeát ñieåm cuûa caùc caùch treân:
Hieäu suaát söû duïng taøi nguyeân (resource utilization) thaáp
Quaù trình coù theå bò starvation
Khoa KTMT
17
Ngaên deadlock (tt)
3. Ngaên No Preemption: neáu process A coù giöõ taøi nguyeân vaø ñang
yeâu caàu taøi nguyeân khaùc nhöng taøi nguyeân naøy chöa caáp phaùt ngay
ñöôïc thì
– Caùch 1: Heä thoáng laáy laïi moïi taøi nguyeân maø A ñang giöõ
A chæ baét ñaàu laïi ñöôïc khi coù ñöôïc caùc taøi nguyeân ñaõ bò laáy
laïi cuøng vôùi taøi nguyeân ñang yeâu caàu
– Caùch 2: Heä thoáng seõ xem taøi nguyeân maø A yeâu caàu
Neáu taøi nguyeân ñöôïc giöõ bôûi moät process khaùc ñang ñôïi
theâm taøi nguyeân, taøi nguyeân naøy ñöôïc heä thoáng laáy laïi vaø
caáp phaùt cho A.
Neáu taøi nguyeân ñöôïc giöõ bôûi process khoâng ñôïi taøi nguyeân,
A phaûi ñôïi vaø taøi nguyeân cuûa A bò laáy laïi. Tuy nhieân heä
thoáng chæ laáy laïi caùc taøi nguyeân maø process khaùc yeâu caàu
Khoa KTMT
18
Ngaên deadlock (tt)
4. Ngaên Circular Wait: gaùn moät thöù töï cho taát caû caùc taøi nguyeân trong
heä thoáng.
–
Taäp hôïp loaïi taøi nguyeân: R={R1, R2,…,Rm }
Haøm aùnh xaï: F: R->N
–
Ví duï: F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12
F laø haøm ñònh nghóa thöù töï treân taäp caùc loaïi taøi nguyeân.
Khoa KTMT
19
Ngaên deadlock (tt)
4. Ngaên Circular Wait (tt)
–
Moãi process chæ coù theå yeâu caàu thöïc theå cuûa moät loaïi taøi nguyeân theo
thöù töï taêng daàn (ñònh nghóa bôûi haøm F) cuûa loaïi taøi nguyeân. Ví duï
Chuoãi yeâu caàu thöïc theå hôïp leä: tape drive disk drive printer
Chuoãi yeâu caàu thöïc theå khoâng hôïp leä: disk drive tape drive
–
Khi moät process yeâu caàu moät thöïc theå cuûa loaïi taøi nguyeân Rj thì noù phaûi
traû laïi caùc taøi nguyeân Ri vôùi F(Ri) > F(Rj).
–
“Chöùng minh” giaû söû toàn taïi moät chu trình deadlock
P1
F(R4) < F(R1)
F(R1) < F(R2)
F(R2) < F(R3)
R4
F(R3) < F(R4)
Vaäy F(R4) < F(R4), maâu thuaãn!
P4
Khoa KTMT
R1
P2
R2
R3
P3
20
- Xem thêm -