Tắc nghẽn khóa chết

Khoa KTMT 1

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 2

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 3

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 4

Ñò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ôø saû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.