Bài giảng Hệ điều hành: Chương 6 - ThS. Hà Lê Hoài Thương

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

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

 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);

Khoa KTMT

nguyeân vaø ñang chôø taøi nguyeân maø process khaùc trong taäp ñang giöõ.

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

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

Resources) ‟ Yeâu caàu (request): process phaûi chôø neáu yeâu caàu khoâng ñöôïc ñaùp öùng

Khoa KTMT

call. Ví duï ‟ request/release device ‟ open/close file ‟ allocate/free memory ‟ wait/signal

Ñò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 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 .

moät deadlock.

 i.e. Moät tieán trình saün saøng ñeå xöû lyù nhöng noù khoâng bao giôø

Khoa KTMT

nhaän ñöôïc CPU.

Ñ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

Ñ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

Resource Allocation Graph (tt)

Kyù hieäu

 Process:

 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

Ñ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át caû caùc loaïi taøi nguyeân trong heä thoáng)

(Taát caû process trong heä thoáng)

‟ Taäp ñænh V goàm 2 loaïi:  P = {P1, P2,…, Pn }  R = {R1, R2,…, Rm }

‟ Taäp caïnh E goàm 2 loaïi:

 Caïnh yeâu caàu (Request edge): ø Pi Rj

Khoa KTMT

 Caïnh caáp phaùt (Assignment edge): Rj Pi

Ví duï veà RAG

R3

R1

P1

P3

P2

R2

R4

Khoa KTMT

Ví duï veà RAG (tt)

R3

R1

P1

P3

P2

Deadlock xaûy ra!

R2

R4

Khoa KTMT

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.

P2

R1

P1

P3

R2

Lý do vì sao không xảy ra deadlock ?

P4

Khoa KTMT

RAG vaø deadlock (tt)

khoâng coù deadlock

 RAG khoâng chöùa chu trình (cycle)  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å ‟ Neáu moãi loaïi taøi nguyeân coù nhieàu thöïc theå deadlock coù theå xaûy ra

Khoa KTMT

deadlock

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

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

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

Khoa KTMT

‟ ñ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

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.

‟ 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.

‟ 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.

‟ Khuyeát ñieåm cuûa caùc caùch treân:

Khoa KTMT

 Hieäu suaát söû duïng taøi nguyeân (resource utilization) thaáp  Quaù trình coù theå bò starvation

Ngaên deadlock (tt)

3. Ngaên No Preemption: neáu process A coù giöõ taøi nguyeân vaø ñang

‟ Caùch 1: Heä thoáng laáy laïi moïi taøi nguyeân maø A ñang giöõ

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ì

 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.

Khoa KTMT

 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

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

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

heä thoáng. ‟ Taäp hôïp loaïi taøi nguyeân: R={R1, R2,…,Rm }

Ngaên deadlock (tt)

disk drive

printer

‟ 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  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

 F(R4) < F(R1)  F(R1) < F(R2)  F(R2) < F(R3)  F(R3) < F(R4)

„ Vaäy F(R4) < F(R4), maâu thuaãn!

Khoa KTMT

4. Ngaên Circular Wait (tt)

2. Traùnh taéc ngheõn Deadlock avoidance

 Deadlock prevention söû duïng taøi nguyeân khoâng hieäu quaû.

 Deadlock avoidance vaãn ñaûm baûo hieäu suaát söû duïng taøi nguyeân toái

 Yeâu caàu moãi process khai baùo soá löôïng taøi nguyeân toái ña caàn ñeå

ña ñeán möùc coù theå.

 Giaûi thuaät deadlock-avoidance seõ kieåm tra traïng thaùi caáp phaùt taøi

thöïc hieän coâng vieäc

„ 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 (resource-allocation state) ñeå baûo ñaûm heä thoáng khoâng rôi vaøo deadlock.

Khoa KTMT

nguyeân coøn laïi, soá taøi nguyeân ñaõ ñöôïc caáp phaùt vaø yeâu caàu toái ña cuûa caùc process.

Traïng thaùi safe vaø unsafe

 Moät traïng thaùi cuûa heä thoáng ñöôïc goïi laø an toaøn (safe) neáu toàn taïi moät chuoãi (thöù tự)ï an toaøn (safe sequence).  Moät chuoãi quaù trình laø moät chuoãi an toaøn

neáu

‟ Vôùi moïi i = 1,…,n, yeâu caàu toái ña veà taøi nguyeân cuûa Pi coù theå

ñöôïc thoûa bôûi

 Moät traïng thaùi cuûa heä thoáng ñöôïc goïi laø khoâng an toaøn

(unsafe) neáu khoâng toàn taïi moät chuoãi an toaøn.

Khoa KTMT

 taøi nguyeân maø heä thoáng ñang coù saün saøng (available)  cuøng vôùi taøi nguyeân maø taát caû Pj , j < i, ñang giöõ.

Chuoãi an toaøn (tt)

Ví duï: Heä thoáng coù 12 tape drives vaø 3 quaù trình P0, P1, P2  Taïi thôøi ñieåm t0

Maximum needs

Current needs

10 5

4 2

9 2 P0 P1 P2

Khoa KTMT

heä thoáng laø an toaøn ‟ Coøn 3 tape drive saün saøng. ‟ Chuoãi laø chuoãi an toaøn

Chuoãi an toaøn (tt)

 Giaû söû taïi thôøi ñieåm t1, P2 yeâu caàu vaø ñöôïc caáp phaùt 1

tape drive ‟ coøn 2 tape drive saün saøng

ñang giöõ caàn toái ña

10 5

4 2

 Heä thoáng coøn an toaøn khoâng?

Khoa KTMT

P0 P1 P2

Traïng thaùi safe/unsafe vaø deadlock

khoâng deadlock.

 Neáu heä thoáng ñang ôû traïng thaùi safe  Neáu heä thoáng ñang ôû traïng thaùi unsafe  Traùnh deadlock baèng caùch baûo ñaûm heä thoáng khoâng ñi ñeán traïng

coù theå daãn ñeán deadlock.

deadlock

thaùi unsafe.

unsafe

Khoa KTMT

safe

Giaûi thuaät ñoà thò caáp phaùt taøi nguyeân

 Khaùi nieäm caïnh thænh caàu

Khoa KTMT

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.

 Baét chöôùc nghieäp vuï ngaân haøng (banking)

 Ñieàu kieän

‟ Moãi process phaûi khai baùo soá löôïng thöïc theå (instance) toái ña

cuûa moãi loaïi taøi nguyeân maø noù caàn

‟ Khi process yeâu caàu 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

Khoa KTMT

moät khoaûng thôøi gian höõu haïn naøo ñoù.

Giaûi thuaät banker (tt)

n: soá process, m: soá loaïi taøi nguyeân

Caùc caáu truùc döõ lieäu

Available[ j ] = k

loaïi taøi nguyeân Rj coù k instance saün saøng

Max: ma traän n m

quaù trình Pi yeâu caàu toái ña k instance cuûa loaïi

Max[ i, j ] = k taøi nguyeân Rj

Available: vector ñoä daøi m

Pi ñaõ ñöôïc caáp phaùt k instance cuûa Rj

Allocation[i, j] = k Need: ma traän n m

Need[i, j] = k

Pi caàn theâm k instance cuûa Rj

Nhaän xeùt: Need[i, j] = Max[i, j] ‟ Allocation[i, j]

Kyù hieäu Y X

Y[i] X[i], ví duï (0, 3, 2, 1) (1, 7, 3, 2)

Khoa KTMT

Allocation: ma traän n m

Giaûi thuaät banker (tt) 1.Giaûi thuaät an toaøn

Work := Available Finish[ i ] := false, i = 1,…, n

Tìm moät chuoãi an toaøn 1. Goïi Work vaø Finish laø hai vector ñoä daøi laø m vaø n. Khôûi taïo

(a) Finish[ i ] = false (b) Needi Work (haøng thöù i cuûa Need)

Neáu khoâng toàn taïi i nhö vaäy, ñeán böôùc 4.

2. Tìm i thoûa

3. Work := Work + Allocationi Finish[ i ] := true quay veà böôùc 2.

Khoa KTMT

4. Neáu Finish[ i ] = true, i = 1,…, n, thì heä thoáng ñang ôû traïng thaùi safe Thôøi gian chaïy cuûa giaûi thuaät laø O(m·n2)

Giaûi thuaät banker (tt) 2. Giaûi thuaät yeâu caàu (caáp phaùt) taøi nguyeân

Goïi Requesti 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 thì ñeán böôùc 2. Neáu khoâng, baùo

loãi vì process ñaõ vöôït yeâu caàu toái ña.

2. Neáu Requesti Available thì qua böôùc 3. Neáu khoâng, 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

baèng caùch caäp nhaät traïng thaùi heä thoáng nhö sau:

Khoa KTMT

Available := Available ‟ Requesti Allocationi := Allocationi + Requesti Needi := Needi ‟ Requesti

Giaûi thuaät banker (tt) 2.Giaûi thuaät yeâu caàu taøi nguyeân

Available := Available + Requesti Allocationi := Allocationi ‟ Requesti Needi := Needi + Requesti

Khoa KTMT

AÙp duïng giaûi thuaät kieåm tra traïng thaùi an toaøn leân traïng thaùi treân  Neáu traïng thaùi laø safe thì taøi nguyeân ñöôïc caáp thöïc söï cho Pi .  Neáu traïng thaùi laø unsafe thì Pi phaûi ñôïi, vaø „ phuïc hoài traïng thaùi:

Giaûi thuaät kieåm tra traïng thaùi an toaøn – Ví duï

 Coù 5 process P0 ,…, P4  Coù 3 loaïi taøi nguyeân: A (coù 10 instance), B (5 instance) vaø C (7

 Sô ñoà caáp phaùt trong heä thoáng taïi thôøi ñieåm T0

instance).

Allocation Max Available Need

A B C A B C A B C A B C

7 5 3 3 3 2 0 1 0 7 4 3

2 0 0 3 2 2 1 2 2

3 0 2 9 0 2 6 0 0

2 1 1 2 2 2 0 1 1

    

Khoa KTMT

0 0 2 4 3 3 4 3 1 P0 P1 P2 P3 P4

GT (kieåm tra traïng thaùi)an toaøn – Vd (tt)

Chuoãi an toaøn

Allocation Need

Work

A B C

0 1 0

7 4 3

3 3 2

2 0 0

1 2 2

5 3 2

3 0 2

6 0 0

7 4 3

2 1 1

0 1 1

0 0 2

4 3 1

7 4 5

P0 P1 P2 P3 P4

10 5 7

10 4 7

Khoa KTMT

GT caáp phaùt taøi nguyeân – 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 Request1 Available:

 (1, 0, 2) (3, 3, 2) laø ñuùng

‟ Giaû ñònh thoûa yeâu caàu, kieåm tra traïng thaùi môùi coù phaûi laø safe hay

Allocation

Need

Available

A B C

2 3 0

0 1 0

7 4 3

3 0 2

0 2 0

3 0 2

6 0 0

2 1 1

0 1 1

P4 (3, 3, 0) ? P0 (0, 2, 0) ? P3 (0, 2, 1)?

0 0 2

4 3 1

P0 P1 P2 P3 P4

khoâng.

‟ Traïng thaùi môùi laø safe (chuoãi an toaøn laø ), vaäy coù

theå caáp phaùt taøi nguyeân cho P1.

Khoa KTMT

3. Phaùt hieän deadlock (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.

 Heä thoáng caáp phaùt taøi nguyeân ñöôïc khaûo saùt trong moãi

tröôøng hôïp sau 1. Moãi loaïi taøi nguyeân chæ coù moät thöïc theå (instance) 2. Moãi loaïi taøi nguyeân coù theå coù nhieàu thöïc theå

Khoa KTMT

Moãi loaïi taøi nguyeân chæ coù moät thöïc theå

 Söû duïng wait-for graph

‟ 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.

 Coù caïnh töø Pi ñeán Pj

Pi ñang chôø taøi nguyeân töø Pj

 Moät giaûi thuaät kieåm tra coù toàn taïi chu trình trong wait-for graph hay khoâng seõ ñöôïc goïi ñònh kyø. Giaûi thuaät phaùt hieän chu trình coù thôøi gian chaïy laø O(n 2), vôùi n laø soá ñænh cuûa graph.

Khoa KTMT

Moãi loaïi taøi nguyeân coù nhieàu thöïc theå

 Phöông phaùp duøng wait-for graph khoâng aùp duïng ñöôïc cho tröôøng

 Caùc caáu truùc döõ lieäu duøng trong giaûi thuaät phaùt hieän deadlock

hôïp moãi loaïi taøi nguyeân coù nhieàu instance.

„ soá instance saün saøng cuûa moãi loaïi taøi nguyeân

„ Allocation: ma traän n m

„ soá instance cuûa moãi loaïi taøi nguyeân ñaõ caáp phaùt cho moãi process

„ Request: ma traän n m

„ yeâu caàu hieän taïi cuûa moãi process.

„ Request [i, j ] = k

Pi ñang yeâu caàu theâm k instance cuûa Rj

Khoa KTMT

Available: vector ñoä daøi m

Giaûi thuaät phaùt hieän deadlock

Work := Available

i = 1, 2,…, n, neáu Allocationi 0 thì Finish[ i ] := false coøn khoâng thì Finish[ i ] := true

2. Tìm i thoûa maõn:

Finish[ i ] := false vaø

Requesti Work

thôøi gian chaïy cuûa giaûi thuaät

„ Neáu khoâng toàn taïi i nhö theá, ñeán böôùc 4.

1. Goïi Work vaø Finish laø vector kích thöôùc m vaø n. Khôûi taïo:

O(m·n2)

3. Work := Work + Allocationi

Finish[ i ] := true quay veà böôùc 2.

Khoa KTMT

4. Neáu Finish[ i ] = false, vôùi moät i = 1,…, n, thì heä thoáng ñang ôû traïng thaùi deadlock. Hôn theá nöõa, Finish[ i ] = false thì Pi bò deadlocked.

Giaûi thuaät phaùt hieän deadlock – Ví duï

 Heä thoáng coù 5 quaù trình P0 ,…, P4 „ 3 loaïi taøi nguyeân: A (7 instance), B (2 instance), C (6 instance).

Allocation Request Available

A B C A B C A B C

0 0 0 0 0 0 0 1 0

2 0 0 2 0 2

3 0 3 0 0 0

2 1 1 1 0 0

0 0 2 0 0 2 P0 P1 P2 P3 P4

Khoa KTMT

Chaïy giaûi thuaät, tìm ñöôïc chuoãi vôùi Finish[ i ] = true, i = 1,…, n, vaäy heä thoáng khoâng bò deadlocked.

Giaûi thuaät phaùt hieän deadlock – Ví duï (tt)

 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 2 P2 0 0 1 P3 1 0 0 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.

„ Vaäy toàn taïi deadlock, bao goàm caùc process P1, P2, P3, vaø P4 .

Khoa KTMT

Phuïc hoài deadlock (Deadlock Recovery)

 Khi deadlock xaûy ra, ñeå phuïc hoài ‟ baùo ngöôøi vaän haønh (operator) hoaëc ‟ heä thoáng töï ñoäng phuïc hoài baèng caùch beû gaõy chu trình deadlock:

Khoa KTMT

 chaám döùt moät hay nhieàu quaù trình  laáy laïi taøi nguyeân töø moät hay nhieàu quaù trình

Deadlock Recovery: Chaám döùt quaù trình

 Phuïc hoài heä thoáng bò deadlock baèng caùch chaám döùt quaù

trình ‟ Chaám döùt taát caû process bò deadlocked, hoaëc ‟ Chaám döùt laàn löôït töøng process cho ñeán khi khoâng coøn deadlock

 Söû duïng giaûi thuaät phaùt hieän deadlock ñeå xaùc ñònh coøn

 Döïa treân yeáu toá naøo ñeå choïn process caàn ñöôïc chaám

döùt? ‟ Ñ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 theâm ñeå hoaøn taát coâng vieäc ‟ Soá löôïng process caàn ñöôïc chaám döùt ‟ Process laø interactive process hay batch process

Khoa KTMT

deadlock hay khoâng

Deadlock recovery: Laáy laïi taøi nguyeân

 Laáy laïi 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” ñeå 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,...)

laáy laïi taøi nguyeân trôû veà traïng thaùi safe, tieáp tuïc process töø traïng thaùi ñoù. 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.

‟ Trôû laïi traïng thaùi tröôùc deadlock (Rollback): rollback process bò

Khoa KTMT

‟ Ñoùi taøi nguyeân (Starvation): ñeå traùnh starvation, phaûi baûo ñaûm khoâng coù process seõ luoân luoân bò laáy laïi taøi nguyeân moãi khi deadlock xaûy ra.

Phöông phaùp keát hôïp ñeå giaûi quyeát Deadlock

 Keát hôïp 3 phöông phaùp cô baûn  Ngaên chaën (Prevention)  Traùnh (Avoidance)  Phaùt hieän (Detection) Cho pheùp söû duïng caùch giaûi quyeát toái öu cho moãi lôùp taøi

 Phaân chia taøi nguyeân thaønh caùc lôùp theo thöù baäc.

nguyeân trong heä thoáng.

‟ Söû duïng kyõ thuaät thích hôïp nhaát cho vieäc quaûn lyù deadlock trong

Khoa KTMT

moãi lôùp naøy.

Baøi taäp

 Baøi 01: Lieät keâ 3 tröôøng hôïp xaûy ra deadlock trong ñôøi