Hệ điều hành Chương VI: Tắc nghẽn (Deadlock)

Chöông 6 : Taéc ngheõn(Deadlock)

 Baøi toaùn deadlock

 Moâ hình heä thoáng

 Caùc tính chaát cuûa deadlock

 Phöông phaùp giaûi quyeát deadlock

 Deadlock prevention

 Deadlock avoidance

 Deadlock detection

 Deadlock recovery

Khoa KTMT

Chapter Objectives

 To develop a description of deadlocks,

which prevent sets of concurrent processes from completing their tasks

 To present a number of different methods for preventing or avoiding deadlocks in a computer system

Vaán ñeà deadlock

 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

– 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

 Ví duï 2

kia.

– Semaphore A vaø B, khôûi taïo baèng 1

Khoa KTMT

P0 wait(A); wait(B); P1 wait(B); wait(A);

Bridge Crossing Example

 Traffic only in one direction  Each section of a bridge can be viewed as a resource  If a deadlock occurs, it can be resolved if one car backs up (lui l

i) ạ

(preempt (dành quy n) resources and rollback)

ề

 Several cars may have to be backed up if a deadlock occurs  Starvation is possible  Note – Most OSes do not prevent or deal with deadlocks

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:

 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

– CPU cycle, khoâng gian boä nhôù, thieát bò I/O, file, semaphore,…

ñöôïc ñaùp öùng ngay

 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

– Söû duïng (use): process söû duïng taøi nguyeân – Hoaøn traû (release): process hoaøn traû taøi nguyeân

Ñò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 (starvation)

(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

Ñ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í dụ: 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

Ñoà thò caáp phaùt taøi nguyeân ( Resource Allocation Graph)

Laø ñoà thò coù höôùng, vôùi taäp ñænh V vaø taäp caïnh

 Taäp ñænh V goàm 2 loaïi:

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

– P = {P1, P2,…, Pn } – R = {R1, R2,…, Rm }

(Taát caû caùc loaïi taøi nguyeân trong

 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

heä thoáng)

Resource Allocation Graph (tt)

 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

Ví duï veà RAG

R3

R1

P1

P3

P2

R2

R4

Khoa KTMT

Resource Allocation Graph With A Deadlock

R3

R1

P1

P3

P2

Deadlock xaûy ra!

R2

R4

Khoa KTMT

Graph With A Cycle But No 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

P4

Khoa KTMT

Basic Facts

 RAG khoâng chöùa chu trình (cycle) (cid:222)

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å (cid:222)

deadlock

– Neáu moãi loaïi taøi nguyeân coù nhieàu thöïc theå (cid:222)

coù

theå xaûy ra deadlock

Khoa KTMT

Caùc phöông phaùp giaûi quyeát deadlock

• 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) 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. 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

Ngaên deadlock (tt)

2. 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öø DVD drive sang 1 file treân disk, saép xeáp file treân disk, roài in keát quaû ra printer.

– Khuyeát ñieåm:

 Hieäu suaát söû duïng taøi nguyeân (resource

utilization) thaáp

Khoa KTMT

 Quaù trình coù theå bò starvation

Ngaên deadlock (tt)

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

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



Khoa KTMT

F laø haøm ñònh nghóa thöù töï treân taäp caùc loaïi taøi nguyeân.

Ngaên deadlock (tt)

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

R1 – Khi moät process yeâu caàu moät thöïc theå cuûa loaïi taøi

P2 P1

nguyeân Rj thì noù phaûi traû laïi caùc taøi nguyeân Ri vôùi F(Ri) > F(Rj).

R4 R2 –

“Chöùng minh” giaû söû toàn taïi moät chu trình deadlock  R3



Khoa KTMT

P4 P3 

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

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 ñ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 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 toái ña cuûa caùc process.

Khoa KTMT

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

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

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

Khoa KTMT

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

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

heä thoáng laø an

– Coøn 3 tape drive saün saøng. – Chuoãi laø chuoãi an toaøn (cid:222)

toaøn

Khoa KTMT

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

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

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

Khoa KTMT

Traïng thaùi safe/unsafe vaø deadlock khoâng deadlock. coù theå daãn

 Neáu heä thoáng ñang ôû traïng thaùi safe (cid:222)  Neáu heä thoáng ñang ôû traïng thaùi unsafe (cid:222)

ñeán deadlock.

 Traùnh deadlock baèng caùch baûo ñaûm heä thoáng khoâng

ñi ñeán traïng thaùi unsafe.

unsafe

safe

Khoa KTMT

deadlock

Avoidance algorithms

 Single instance of a resource type – Use a resource-allocation graph

 Multiple instances of a resource type

– Use the banker’s algorithm

Khoa KTMT

ResourceAllocation Graph Scheme  Claim edge (caïnh thænh caàu) Pi ﬁ Rj indicated that process Pj may request resource Rj; represented by a dashed line

 Claim edge converts to request edge when a process

requests a resource

 Request edge converted to an assignment edge when the

resource is allocated to the process

 When a resource is released by a process, assignment edge

reconverts to a claim edge

 Resources must be claimed a priori in the system

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

P1 P2

Khoa KTMT

Unsafe State In ResourceAllocation Graph

P2 P1

Khoa KTMT

ResourceAllocation Graph Algorithm

 Suppose that process Pi requests a resource Rj

 The request can be granted only if converting the request

edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph

Giaûi thuaät banker

 Nhieàu instance.

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

 Moãi process phaûi khai baùo soá löôïng 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

 Khi process ñaõ coù ñöôïc ñaày ñuû taøi nguyeân thì phaûi hoaøn traû trong moät khoaûng thôøi gian höõu haïn naøo ñoù.

Khoa KTMT

Data Structures for the Banker’s Algorithm

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

Available: vector ñoä daøi m

Available[ j ] = k (cid:219)

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



 Max: ma traän n · Max[ i, j ] = k (cid:219) loaïi taøi nguyeân Rj Allocation: ma traän n · Allocation[i, j] = k (cid:219)

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



Need: ma traän n · Need[i, j] = k (cid:219)

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

Need[i, j] = Max[i, j] – Allocation[i, j] Kyù hieäu Y £

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

Khoa KTMT

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

Giaûi thuaät an toaøn

1. Goïi Work vaø Finish laø hai vector ñoä daøi laø m vaø n.

Khôûi taïo

2. Tìm i thoûa

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

Work (a) Finish[i] = false (b) Needi £

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

4. Neáu Finish[i] = true, i = 1,…, n, thì heä thoáng ñang ôû

traïng thaùi safe

Khoa KTMT

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

Giaûi thuaät yeâu caàu taøi nguyeân cho tieán trình Pi

Pi caàn k instance cuûa taøi

Requesti laø request vector cuûa process Pi . Requesti [ j ] = k (cid:219) 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.

Available thì qua böôùc 3. Neáu

2. Neáu Requesti £

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

 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 Banker – Ví duï

 5 process P0 ,…, P4  3 loaïi taøi nguyeân:

– A (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

Max

Available

Need

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

    

0 0 2

4 3 3

4 3 1

Khoa KTMT

Ví duï (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

7 4 5

0 0 2

4 3 1

10 5 7

10 4 7

Khoa KTMT

Ví duï: P1 yeâu caàu (1, 0, 2)

Available laø (1, 0, 2) £

(3, 3, 2) (cid:222)

 Kieåm tra Request1 £

ñuùng

Allocation Need Available

A B C A B C A B C

0 1 0 7 4 3 2 3 0 P0

3 0 2 0 2 0 P1

3 0 2 6 0 0 P2

2 1 1 0 1 1 P3

0 0 2 4 3 1 P4

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

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

Khoa KTMT

P3 (0, 2, 1)?

Ví duï: P4 yeâu caàu (3, 3, 0)

Available laø (3, 3, 0) £

(3, 3, 2) (cid:222)

 Kieåm tra Request4 £

ñuùng

Allocation Need Available

A B C A B C A B C

0 1 0 7 4 3 0 0 2 P0

3 0 2 1 2 2 P1

3 0 2 6 0 0 P2

2 1 1 0 1 1 P3

3 3 2 1 0 1 P4

– Traïng thaùi môùi laø unsafe , vaäy khoâng theå caáp phaùt taøi

Khoa KTMT

nguyeân cho P4.

Ví duï: P0 yeâu caàu (0, 2, 0)

Available laø (0, 2, 0) £

(3, 3, 2) (cid:222)

 Kieåm tra Request0 £

ñuùng

Allocation Need Available

A B C A B C A B C

0 3 0 7 2 3 3 1 2 P0

3 0 2 1 2 2 P1

3 0 2 6 0 0 P2

2 1 1 0 1 1 P3

0 0 2 4 3 1 P4

– Traïng thaùi môùi laø safe, chuoãi an toan (P3, P1, P2 ,P0 ,P4 ) vaäy

Khoa KTMT

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

3. Phaùt hieän deadlock (Deadlock detection)

 Chaáp nhaän xaûy ra deadlock trong heä thoáng.

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

 Cô cheá phuïc hoài.

Khoa KTMT

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

 Söû duïng wait-for graph

 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ø. Neáu coù chu trình thì toàn taïi deadlock.

 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

– Caùc Node laø caùc process. – Pi →Pj neáu Pi chôø taøi nguyeân töø Pj

ResourceAllocation Graph and Waitfor Graph

Resource-Allocation Graph Corresponding wait-for graph

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

 Available: vector ñoä daøi m chæ soá instance saün saøng cuûa

moãi loaïi taøi nguyeân

 Allocation: ma traän n ·

m ñònh nghóa 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 chæ ñònh yeâu caàu hieän taïi cuûa

moãi process. • Request [i, j ] = k (cid:219)

Pi ñang yeâu caàu theâm k instance

cuûa Rj

Khoa KTMT

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

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

0 thì Finish[ i ] := false a. Work = Available b. For i = 1, 2,…, n, neáu Allocationi „

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

coøn khoâng thì Finish[ i ] := true

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

Khoa KTMT

Work a. Finish[ i ] = false b. Requesti £

Giaûi thuaät phaùt hieän (tt)

3. Work = Work + Allocationi

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

4. Neáu Finish[ i ] = false, vôùi moät soá 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.

Thôøi gian chaïy cuûa giaûi thuaät O(m·n2)

Khoa KTMT

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

 5 quaù trình P0 ,…, P4 3 loaïi taøi nguyeân:

A (7 instance), B (2 instance), C (6 instance).

 Taïi thôøi ñieåm T0

Allocation

Request

Available

A B C

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

Chuoãi seõ cho keát quaû Finish[ i ] = true, i = 1,…, n

Khoa KTMT

Ví duï (tt)

 P2 yeâu caàu theâm moät instance cuûa C. Ma traän Request

nhö sau:

Allocation

Request

Available

A B C

0 0 0

0 1 0

2 0 0

2 0 2

3 0 3

0 0 1

2 1 1

1 0 0

0 0 2

– Traïng thaùi cuûa heä thoáng laø gì? P0 ,

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

Khoa KTMT

P4 .

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:

 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

Khoa KTMT

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

 Chaám döùt quaù trình bò deadlock  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 deadlock hay khoâng

 Döïa treân yeáu toá naøo ñeå 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 hay batch

Khoa KTMT

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.

 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,...)

 Trôû laïi traïng thaùi tröôùc deadlock (Rollback):

rollback process bò 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.

 Ñoùi taøi nguyeân (Starvation): ñeå traùnh

starvation, phaûi baûo ñaûm khoâng coù process seõ 51 Khoa KTMT 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 nguyeân trong heä thoáng.

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

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

deadlock trong moãi lôùp naøy.

Khoa KTMT