Bài giảng Hệ điều hành - Chương 4: Deadlock - Thoại Nam
Chöông 4. Deadlock
ꢀ Moâ hình heä thoáng
ꢀ Resource Allocation Graph(RAG)
ꢀ Phöông phaùp giaûi quyeát deadlock
– Deadlock prevention (ngaên chaën deadlock)
– Deadlock avoidance (traùnh deadlock)
– Deadlock detection (phaùt hieän deadlock)
– Deadlock recovery (phuïc hoài deadlock)
-8.1-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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 coù.
ꢀ 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
wait (A);
wait (B);
P1
wait(B)
wait(A)
-8.2-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
1
Moâ hình hoùa heä thoáng
ꢀ 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,
monitor,...
– Moãi loaïi taøi nguyeân Ri coù Wi thöïc theå (instance).
ꢀ Quaù trình söû duïng taøi nguyeân cuûa moãi process nhö sau
– 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)
– Hoaøn traû (release)
ꢀ Caùc taùc vuï yeâu caàu (request) vaø hoaøn traû (release) ñeàu
laø system call
– Request/release device, open/close file, allocate/free memory
– Wait/signal
-8.3-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Ñieàu kieän toàn taïi deadlock
ꢀ Mutual exclusion: vôùi moãi taøi nguyeân, chæ coù moät
process söû duïng taïi moät thôøi ñieåm.
ꢀ Hold and wait: moät process vaãn sôû höõu taøi nguyeân ñaõ
ñöôïc caáp phaùt trong khi yeâu caàu moät taøi nguyeân khaùc.
ꢀ No preemption: moät taøi nguyeân khoâng theå bò ñoaït laïi töø
chính process ñang sôû höõu taøi nguyeân ñoù.
ꢀ Circular wait: ton tai mot chu kyø ñoùng caùc yeu cau tai
n
P2
P1
Deadlock coù theå xaûy ra neáu 4 ñieàu kieän xuaát hieän ñoàng thôøi.
-8.4-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
2
Resource Allocation Graph(RAG)
ꢀ RAG laø ñoà thò coù höôùng, 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û taøi nguyeân trong heä thoáng)
– Taäp caïnh E goàm 2 loaïi
ꢁ Request edge: caïnh coù höôùng töø Pi → Rj
ꢁ Assignment edge: caïnh coù höôùng töø Rj → Pi
Pi
ꢀ Process
Ri
ꢀ Loaïi taøi nguyeân vôùi 4 thöïc theå
Pi
ꢀ Pi yeâu caàu moät thöïc theå cuûa Rj
Rj
ꢀ Pi ñang giöõ moät thöïc theå cuûa Rj
Pi
Rj
-8.5-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Ví duï veà RAG
R1
R3
P3
P
P
R4
R2
-8.6-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
3
RAG ñang bò deadlock
R1
R3
P3
P2
P1
R4
R2
-8.7-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Cycle RAG khoâng deadlock
R1
P2
P3
P1
R2
☺ RAG khoâng toàn taïi chu kyø (cycle) ⇒ khoâng coù deadlock.
ꢂ RAG coù ít nhaát moät chu kyø (cycle)
–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.
-8.8-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
4
Caùc p.p giaûi quyeát deadlock
ꢀ Duøng moät giao thöùc (protocol) ñeå ngaên chaën hoaëc
traùnh deadlock, baûo ñaûm raèng heä thoáng khoâng bao
giôø bò rôi vaøo tình traïnh deadlock.
– Deadlock prevention
– Deadlock avoidance
ꢀ Heä thoáng coù theå rôi vaøo traïng thaùi deadlock, sau ñoù
phaùt hieän deadlock vaø phuïc hoài heä thoáng.
ꢀ Boû qua moïi vaán ñeà, xem nhö khoâng bao giôø coù
deadlock xaûy ra trong heä thoáng
☺ Khaù nhieàu heä ñieàu haønh söû duïng p.p naøy.
– Deadlock khoâng phaùt hieän, giaûi quyeát ⇒ 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 khôûi ñoäng laïi.
-8.9-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Deadlock Prevention
ꢀ Tìm caùch ngaên chaën sao cho ít nhaát moät trong 4 ñieàu
kieän gaây deadlock khoâng xaûy ra.
1) Mutual Exclusion: khoâng caàn thieát ñoái vôùi sharable
resource nhöng baét buoäc phaûi thoûa maõn ñoái vôùi non-
sharable resource ⇒ khoâng haïn cheá ñöôïc.
2) Hold and Wait: söû duïng cô cheá “all-or-none”
– Caùch 1: baét buoäc moãi process phaûi yeâu caàu toaøn boä taøi nguyeân
ù
phaùt, neáu khoâng ñuû taøi nguyeân thì process phaûi bò block
– Caùch 2: khi yeâu caàu taøi nguyeân, process khoâng ñöôïc sôû höõu 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
– Khuyeát ñieåm:
ꢁ
ꢁ
Hieäu suaát söû duïng taøi nguyeân raát thaáp
Coù khaû naêng bò starvation
-8.10-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
5
Deadlock Prevention (t.t)
3) No Preemption: neáu process A coù sôû höõu 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 ñaùp öùng ñöôïc thì.
– Caùch 1: A phaûi traû cho heä thoáng moïi taøi nguyeân ñang sôû höõu
ꢁ
A phaûi baét ñaàu laïi töø ñaàu, yeâu caàu caùc taøi nguyeân ñaõ bò ñoaït
laïi vaø caû taøi nguyeân ñang yeâu caàu
– Caùch 2: Heä thoáng seõ kieåm tra taøi nguyeân maø A yeâu caàu
ꢁ
Neáu taøi nguyeân laø sôû höõu cuûa process ñang yeâu caàu vaø ñôïi
theâm taøi nguyeân, taøi nguyeân naøy ñöôïc heä thoáng ñoaït laïi vaø
caáp phaùt cho A.
ꢁ
Neáu taøi nguyeân laø sôû höõu cuûa process khoâng ñôïi taøi nguyeân,
A phaûi ñôïi vaø taøi nguyeân cuûa A bò ñoaït laïi. Tuy nhieân heä
thoáng chæ ñoaït laïi caùc taøi nguyeân maø process khaùc yeâu caàu
ꢀ Thöôøng aùp duïng cho taøi nguyeân coù theå deã daøng löu vaø khoâi phuïc
traïng thaùi nhö CPU register, boä nhôù, ...
-8.11-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Deadlock Prevention (t.t)
4) Circular Wait: caùc taøi nguyeân trong heä thoáng ñöôïc ñaùnh
soá thöù töï tuyeán tính
– Ví duï: F(tape drive) = 1, F(disk drive) = 5, F(Printer) = 12
ꢁ
F laø haøm ñònh nghóa thöù töï döïa treân hieäu suaát söû duïng cuûa
taøi nguyeân.
– Caùch 1: Baét buoäc moãi process yeâu caàu taøi nguyeân theo thöù töï
tuyeán tính taêng daàn. Ví duï
ãä
Chuoãi yeâu caàu khoâng hôïp leä: disk drive tape drive
– Caùch 2: Khi moät process yeâu caàu moät taøi nguyeân Rj thì phaûi traû
laïi caùc taøi nguyeân Ri vôùi F(Ri) > F(Rj)
p1-request
p1
R1
R2
R3
R4
R5
R6
p2
p2
-8.12-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
6
Deadlock Avoidance
ꢀ Deadlock prevention söû duïng taøi nguyeân khoâng hieäu quaû.
ꢀ Deadlock avoidance chæ döïa treân ñieàu kieän thöù 4 ñeå
traùnh deadlock maø vaãn ñaûm baûo hieäu suaát söû duïng taøi
nguyeân toái ña ñeán möùc coù theå.
ꢀ Yeâu caàu moãi process khai baùo soá löôïng taøi nguyeân toái
ña caàn ñeå thöïc hieän coâng vieäc
ꢀ Giaûi thuaät deadlock-avoidance seõ kieåm tra traïng thaùi caáp
phaùt taøi nguyeân (resource-allocation state) ñeå baûo ñaûm
heä thoáng khoâng bao giôø rôi vaøo deadlock.
ꢀ Traïng thaùi caáp phaùt taøi nguyeân ñöôïc ñònh nghóa döïa treân
soá taøi nguyeân coøn laïi, soá taøi nguyeân ñaõ ñöôïc caáp phaùt vaø
yeâu caàu cöïc ñaïi cuûa caùc process
-8.13-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Traïng thaùi “safe” vaø “unsafe”
ꢀ Moät traïng thaùi ñöôïc goïi laø “safe” neáu toàn taïi ít nhaát moät caùch
maø trong moät khoaûng thôøi gian höõu haïn naøo ñoù, heä thoáng coù
theå caáp phaùt taøi nguyeân thoûa maõn cho taát caû process thöïc thi
hoaøn taát .
ꢀ Khi moät process yeâu caàu moät taøi nguyeân ñang saün coù, heä
thoáng seõ kieåm tra: neáu vieäc caáp phaùt naøy khoâng daãn ñeán tình
traïng unsafe thì seõ caáp phaùt ngay.
need
need
A
B
C
8
2
1
10
5
3
A
B
C
1
4
5
4
6
8
Available =1
Available = 2
Traïng thaùi unsafe
Traïng thaùi safe
-8.14-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
7
Safe,unsafe vaø deadlock
ꢀ Neáu heä thoáng ñang ôû traïng thaùi “safe” ⇒ khoâng deadlock.
ꢀ Neáu heä thoáng ñang ôû traïng thaùi “unsafe” ⇒ coù khaû naêng
daãn ñeán deadlock.
ꢀ Deadlock avoidance ⇒ baûo ñaûm heä thoáng khoâng bao giôø
ñi ñeán traïng thaùi “unsafe”.
deadlock
unsafe
safe
-8.15-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Giaûi thuaät Banker
ꢀ AÙp duïng cho heä thoáng caáp phaùt taøi nguyeân trong
ñoù moãi loaïi taøi nguyeân coù theå coù nhieàu instance.
ꢀ Moâ phoûng nghieäp vuï ngaân haøng (banking)
ꢀ Moät soá giaû thieát
– Moãi process phaûi khai baùo soá löôïng toái ña taøi nguyeân
– Khi process yeâu caàu moät taøi nguyeân thì coù theå phaûi
ñôïi maëc duø taøi nguyeân ñöôïc yeâu caàu ñang coù saün
– Khi process ñaõ coù ñöôïc ñaày ñuû taøi nguyeân thì phaûi
hoaøn traû trong moät khoaûn thôøi gian höõu haïn naøo ñoù.
-8.16-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
8
Giaûi thuaät Banker (t.t)
Moät soá giaû thieát trong giaûi thuaät Banker:
ꢃ n = soá processes
haïn cheá cuûa
giaûi thuaät Banker
ꢃ m = soá loaïi taøi nguyeân
ꢃ Max[n, m]
ꢄ Max[ i, j ] = k ⇔ soá instance cöïc ñaïi maø Pi yeâu caàu ñoái vôùi Rj.
ꢃ Available[m]
ꢄ Available[j] = k ⇔ loaïi taøi nguyeân Rj ñang saün coù k instance.
ꢃ Allocation[n, m]
ꢄ Allocation[i,j] = k ⇔ Pi ñaõ ñöôïc caáp phaùt k instance cuûa Rj.
ꢃ Need: ma traän n x m .
ꢄ Need[i,j] = k ⇔ Pi caàn theâm k instance cuûa Rj.
Need [i,j] = Max[i,j] – Allocation [i,j].
-8.17-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Giaûi thuaät kieåm tra traïng thaùi
1. Goïi Work vaø Finish laø hai vector kích thöôùc töông öùng
laø m, n. Khôûi taïo ban ñaàu
Work[i] := Available[i]
Finish[j] = false, ∀j
2. Tìm i thoûa ñieàu kieän sau
Ñoä phöùc taïp
(a) Finish [i] = false
cuûa giaûi thuaät
(b) Need≤ Work (haøng thöù i cuûa Need)
)
3. Work := Work + Allocationi
Finish[i] := true
quay veà böôùc 2.
4. Neáu Finish[i] = true ∀i, heä thoáng ñang ôû traïng thaùi safe
Y ≤ X ⇔ Y[i] ≤ X[i], ví duï (0, 3, 2, 1) ≤ (1, 7, 3, 2)
-8.18-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
9
Giaûi thuaät caáp phaùt taøi nguyeân
Goïi Requesti[m] laø request vector cuûa process Pi.
Requesti [j] = k ⇔ Pi caàn k instance cuûa taøi nguyeân Rj.
1. Neáu Requesti ≤ Needi ⇒ ñeán böôùc 2. Ngöôïc laïi, baùo loãi vì process
ñaõ vöôït quaù giôùi haïn yeâu caàu cöïc ñaïi.
2. Neáu Requesti ≤ Available ⇒ qua böôùc 3. Ngöôïc laïi, Pi phaûi chôø vì
taøi nguyeân khoâng coøn ñuû ñeå caáp phaùt.
3. Giaû ñònh caáp phaùt taøi nguyeân ñaùp öùng yeâu caàu cuûa Pi thöû caäp nhaät
traïng thaùi heä thoáng nhö sau:
Available := Available - Requesti;
Allocationi := Allocationi + Requesti;
Needi := Needi – Requesti;
Neáu traïng thaùi laø safe ⇒ taøi nguyeân ñöôïc caáp thöïc söï cho Pi.
Neáu unsafe ⇒ Pi phaûi ñôïi. Phuïc hoài traïng thaùi
Available := Available + Requesti;
Allocationi := Allocationi - Requesti;
Needi := Needi + Requesti;
-8.19-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Giaûi thuaät Banker – Ví duï (t.t)
ꢀ Coù 5 process P0 – P4
ꢀ Coù 3 loaïi taøi nguyeân: A (coù 10 instance), B (5 instance)
vaø C (7 instance).
ꢀ Sô ñoà caáp phaùt trong heä thoáng taïi thôøi ñieåm T0
Allocation
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
Max
Available
3 3 2
Need
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
7 4 3
1 2 2
6 0 0
0 1 1
4 3 1
P0
P1
P2
P3
P4
ꢉ
ꢅ
ꢈ
ꢆ
ꢇ
-8.20-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
10
Kieåm tra söï an toaøn
Chuoãi caáp phaùt an toaøn < P1, P3, P4, P2, P0>
Allocation
ABC
010
Need
ABC
743
122
600
011
431
Available
A B C
P0
P1
3 3 2
200
5 3 2
7 4 3
7 4 5
10 4 7
P2
P3
P4
302
211
002
10 5 7
-8.21-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Ví duï:
ꢀ Yeâu caàu (1,0,2) cuûa P1 coù thoûa ñöôïc khoâng? Kieåm tra ñieàu
kieän Request ≤ Available
(1,0,2) ≤ (3,3,2) = TRUE
ꢀ Kieåm tra traïng thaùi hieän taïi coù phaûi laø safe hay khoâng?
Allocation
Need
Available
A B C
A
2
3
2
0
B
0
0
1
0
C
0
2
1
2
A B C
0 2 0
6 0 0
0 1 1
4 3 1
P1
P2
P3
P4
ꢀ BT: yeâu caàu (3,3,0) cuûa P4, yeâu caàu (0,2,0) cuûa P0 coù theå thoûa
maõn hay khoâng?
-8.22-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
11
Deadlock Detection
ꢀ Chaáp nhaän xaûy ra deadlock trong heä thoáng,
kieåm tra traïng thaùi heä thoáng baèng giaûi thuaät
phaùt hieän deadlock.
ꢀ Neáu coù deadlock thì tieán haønh phuïc hoài heä
thoáng
ꢀ Caùc giaûi thuaät phaùt hieän deadlock thöôøng söû
duïng moâ hình RAG.
ꢀ Coù hai moâ hình heä thoáng caáp phaùt taøi nguyeân
ñöôïc khaûo saùt
1. Single-Instance: moãi loaïi taøi nguyeân chæ coù moät
instance
2. Multiple-Instance: moãi loaïi taøi nguyeân coù theå coù nhieàu
instance
-8.23-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Moâ hình Single-Instance
ꢀ Söû duïng wait-for graph (moät bieán theå cuûa RAG), trong
ñoù, caùc node cuûa graph laø caùc process.
– Wait-for graph ñöôïc daãn xuaát töø RAG baèng caùch boû caùc node
bieåu dieãn taøi nguyeân vaø gheùp caùc caïnh töông öùng.
– Pi → Pj ⇔ Pi ñang chôø taøi nguyeân töø Pj
ꢀ Moät giaûi thuaät ñöôïc goïi ñònh kyø (!) ñeå kieåm tra coù toàn taïi
chu kyø (cycle) trong wait-for graph hay khoâng? Giaûi thuaät
p
ñænh cuûa graph.
P5
P5
R1
P1
R2
R3
R4
P3
R5
P1
P2
P4
P3
P2
P4
-8.24-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
12
Moâ hình Multiple-Instance
ꢀ Moâ hình wait-for graph khoâng aùp duïng ñöôïc cho
tröôøng hôïp moãi loaïi taøi nguyeân coù nhieàu instance.
ꢀ Caùc caáu truùc döõ lieäu duøng trong giaûi thuaät phaùt
hieän deadlock
– Available[m]: # instance saün coù cuûa moãi loaïi taøi
nguyeân
– Allocation[n,m]: # instance ñaõ caáp phaùt cho moãi
process
– Request[n,m]: yeâu caàu hieän taïi cuûa process. Request
[i,j] = k ⇔ Pi ñang yeâu caàu theâm k instance cuûa Rj
-8.25-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Detection Algorithm
1. Goïi Work vaø Finish laø vector kích thöôùc m vaø n:
(a) Work := Available
(b) Vôùi i = 1,2, …, n, neáu Allocationi ≠ 0 ⇒ Finish[i] = false
ngöôïc laïi
⇒ Finish[i] = true
2. Tìm i thoûa maõn:
Finish[i] = false vaø Requesti ≤ Work,
Ñoä phöùc taïp
3. Work = Work + Allocationi
O(m.n2)
Finish[i] = true
quay veà böôùc 2.
4. ∃i,1≤ i ≤ n: Finish[i] = false ⇒ heä thoáng ñang ôû traïng thaùi
deadlock. Hôn theá nöõa, Finish[i] = false ⇒ Pi bò deadlock.
-8.26-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
13
Detection Algorithm – Ví duï
ꢀ Coù 5 processes P0 – P4
ꢀ
3 loaïi taøi nguyeân A (7 instance), B (2 instance), C (6 instance).
Allocation Request Available
A B C
0 1 0
2 0 0
3 0 3
2 1 1
0 0 2
A B C
0 0 0
2 0 2
0 0 0
1 0 0
0 0 2
A B C
0 0 0
P0
P1
P2
P3
P4
ꢀ Caáp phaùt theo thöù töï <P0, P2, P3, P1, P4> seõ coù keát quaû
laø ∀i Finish[i] = true ⇒ heä thoáng khoâng bò deadlock.
-8.27-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Detection Algorithm – Ví duï (t.t)
ꢀ P2 yeâu caàu theâm moät instance cuûa C. Ma traän Request
nhö sau:
Request
A B C
P0 0 0 0
P1 2 0 1
P0 0 1
P4 0 0 2
ꢀ Traïng thaùi cuûa heä thoáng laø gì?
– Coù theå thu hoài taøi nguyeân ñang sôû höõu bôûi process P0 nhöng vaãn
khoâng ñuû ñaùp öùng yeâu caàu cuûa caùc process khaùc.
⇒ Toàn taïi deadlock, bao goàm caùc processe P1, P2, P3, vaø P4.
-8.28-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
14
Deadlock Recovery
ꢀ Phuïc hoài heä thoáng bò deadlock chuû yeáu laø beû gaõy chu kyø
wait-for cuûa caùc process bò deadlock.
– Huûy boû taát caû process bò deadlock .
– Huûy boû laàn löôït töøng process vaø thu hoài taøi nguyeân cho ñeán khi
khoâng coøn deadlock.
ꢀ Döïa treân cô sôû naøo ñeå huûy process ?
– Ñoä öu tieân cuûa process ?
– Thôøi gian ñaõ thöïc thi cuûa process vaø thôøi gian coøn laïi ?
– Loaïi taøi nguyeân maø process ñaõ söû duïng ?
– Taøi nguyeân maø process caàn ñeå hoaøn taát coâng vieäc ?
– Soá löôïng processes caàn huûy boû ?
– Process laø interactive process hay batch process?
– ...
-8.29-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Thu hoài taøi nguyeân
ꢀ Ñoaït taøi nguyeân töø moät process, caáp phaùt cho
process khaùc cho ñeán khi khoâng coøn deadlock
nöõa.
ꢀ Caùc vaán ñeà trong chieán löôïc thu hoài taøi nguyeân:
– Choïn “naïn nhaân” – toái thieåu chi phí (coù theå döïa treân
soá taøi nguyeân sôû höõu, thôøi gian CPU ñaõ tieâu toán,...)
– Rollback – quay trôû veà traïng thaùi safe, baét ñaàu caùc
check-point rollback
ꢁ Heä thoáng caàn löu giöõ moät soá thoâng tin veà traïng thaùi
caùc process ñang thöïc thi
– Starvation – phaûi baûo ñaûm khoâng coù process seõ luoân
luoân bò ñoaït taøi nguyeân moãi khi deadlock xaûy ra
-8.30-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
15
Phöông phaùp toång hôïp
ꢀ Phaân hoaïch taøi nguyeân thaønh caùc nhoùm coù phaân caáp
⇒ duøng phöông phaùp linear ordering ñeå phoøng choáng
deadlock ñoái vôùi caùc nhoùm. Trong moãi nhoùm, duøng giaûi
thuaät phuø hôïp nhaát ñeå giaûi quyeát deadlock.
ꢀ Moät soá ví duï
– Swappable space: khoái boä nhôù hoaëc thieát bò löu tröõ phuï duøng
laøm boä nhôù traùo ñoåi taïm (swap memory)
ꢁ Hold-and-Wait Prevention + Avoidance
– Process resource: assignable device nhö tape drive, file,...
ꢁ Avoidance hoaëc Resource Ordering
– Main memory: memory page/segment
ꢁ Preemption
– Internal resource: PCB, I/O channel,…
ꢁ Resource Ordering
-8.31-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
16
16 trang
20040
Free
Bạn đang xem tài liệu "Bài giảng Hệ điều hành - Chương 4: Deadlock - Thoại Nam", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_he_dieu_hanh_chuong_4_deadlock_thoai_nam.pdf
