tailieunhanh - Chuong 08 - Deadlock

8. Deadlock. Moâ hình heä thoáng. Resource Allocation Graph (RAG). Phöông phaùp giaûi quyeát deadlock. Deadlock prevention. Deadlock avoidance. Deadlock detection. Deadlock recovery. Khoa Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin 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 Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin 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). Process thöôøng söû duïng taøi nguyeân theo thöù töï 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): 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. Khoa Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin Ñ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 deadlock1. 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. 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 Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin Ñieàu kieän caàn ñeå xaûy ra. deadlock (tt).3. 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ù . 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 Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin 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:. Request edge: caïnh coù höôùng töø Pi ñeán Rj. Assignment edge: caïnh coù höôùng töø Rj ñeán Pi. Khoa Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin Resource Allocation Graph (tt)Kyù hieäu. Pi. Process: Rj Loaïi taøi nguyeân vôùi 4 thöïc theå: Rj. Pi. Pi yeâu caàu moät thöïc theå cuûa Rj :. Rj. Pi. Pi ñang giöõ moät thöïc theå cuûa Rj :. Khoa Kyõ thuaät Maùy tính – Tröôøng Ñaïi hoïc Coâng ngheä Thoâng tin duï veà RAG. R1 R3.