Bài giảng Hệ điều hành - Chương 4: Deadlock - Thoại Nam

Nội dung text: Bài giảng Hệ điều hành - Chương 4: Deadlock - Thoại Nam

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âucaàu(request): process phaûi chôø neáu yeâu caàu khoâng ñöôïc ñaùp öùng ngay – Söû duïng (use) –Hoaøntraû(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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.3- Ñ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: toàn taïi moät chu kyø ñoùng caùc yeâu caàu taøi nguyeân. P1 P2 Deadlock coù theå xaûy ra neáu 4 ñieàu kieän xuaát hieän ñoàng thôøi. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.4- 2
2. RAG ñang bò deadlock R 1 R 3 P2 P3 P1 R R 2 4 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.7- Cycle RAG khoâng deadlock R 1 P2 P P1 3 R 2 P4 ☺ 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. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.8- 4
3. 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ôù, Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.11- 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 hôïp leä: tape drive → disk drive → Printer 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 p1-request R1 R2 R3 R4 R5 R6 p2 p2 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.12- 6
4. 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.15- 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ätsoágiaûthieát – Moãi process phaûi khai baùo soá löôïng toái ña taøi nguyeân moãi loaïi maø process ñoù caàn ñeå hoaøn taát coâng vieäc. – 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ù. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.16- 8
5. 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; Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.19- 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 Max Available Need A BAC A B C B C A B C P0 0 1 0 7 5 3 3 3 2 7 4 3 P1 2 0 0 3 2 2 1 2 2 P2 3 0 2 9 0 2 6 0 0 P3 2 1 1 2 2 2 0 1 1 P4 0 0 2 4 3 3 4 3 1 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.20- 10
6. 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.23- 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 phaùt hieän chu kyø coù ñoä phöùc taïp laø O(n2), vôùi n laø soá ñænh cuûa graph. P5 P5 R1 R3 R4 P1 P2 P3 P1 P2 P3 R2 P4 R5 P4 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.24- 12
7. 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 BAC A B C B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Caáp phaùt theo thöù töï seõ coù keát quaû laø ∀i Finish[i] = true ⇒ heä thoáng khoâng bò deadlock. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.27- 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 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. ⇒ Toàn taïi deadlock, bao goàm caùc processe P1, P2, P3, vaø P4. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.28- 14
8. 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -8.31- 16