Bài giảng Deadlock

Bài giảng Deadlock cung cấp cho các bạn những kiến thức về mô hình hóa hệ thống; đồ thị cấp phát tài nguyên; phương pháp giải quyết deadlock; ngăn deadlock; tránh, phát hiện, phục hồi khỏi deadlock. Bài giảng phục vụ cho các bạn chuyên ngành Công nghệ thông tin và những ngành có liên quan.
Nội dung trích xuất từ tài liệu:
Bài giảng Deadlock Deadlock Moâ hình hoùa heä thoáng Ñoà thò caáp phaùt taøi nguyeân Phöông phaùp giaûi quyeát deadlock Ngaên deadlock Traùnh deadlock Phaùt hieän deadlock Phuïc hoài khoûi deadlock 1From A.Gottlieb 2 Vaán ñeà deadlock trong heä thoáng Moät taäp caùc process laø deadlock(ed) khi moãi process trong taäp naøy giöõ taøi nguyeân vaø chôø taøi nguyeân maø moät process khaùc trong taäp ñang giöõ Ví duï ● Giaû söû heä thoáng coù moät printer vaø moät DVD drive. Quaù trình P1 ñang giöõ DVD drive, quaù trình P2 ñang giöõ printer. Baây giôø P1 yeâu caàu printer vaø phaûi ñôïi, vaø P2 yeâu caàu DVD drive vaø phaûi ñôïi 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 ● Taøi nguyeân: CPU cycle, khoâng gian boä nhôù, thieát bò I/O, file,…• Moãi loaïi taøi nguyeân Ri coù Wi thöïc theå (instance) Process söû duïng taøi nguyeân theo caùc böôùc ● 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 4 Caùc taùc vuï yeâu caàu vaø hoaøn traû ñöôïc goïi qua system call. Ví duï ● request/release device ● open/close file ● allocate/free memory 5 Deadlock: Ñieàu kieän caàn (1/2) Boán ñieàu kieän caàn (necessary condition) ñeå xaûy ra deadlock1. Mutual exclusion: moät taøi nguyeân coù theå ñöôïc caáp phaùt cho nhieàu laém laø 1 quaù trình (töùc laø khoâng chia seû ñöôïc)2. Hold and wait: moät quaù trình ñang giöõ taøi nguyeân ñöôïc pheùp yeâu caàu theâm taøi nguyeân khaùcNhaän xeùt: “mutual exclusion” ôû ñaây vaø “mutual exclusion” trong chöôngveà ñoàng boä laø hai khaùi nieäm khaùc nhau 6 Deadlock: Ñieàu kieän caàn (2/2)3. No preemption: (= no resource preemption) khoâng laáy laïi taøi nguyeân ñaõ caáp phaùt cho quaù trình, ngoaïi tröø khi quaù trình töï hoaøn traû noù4. Circular wait: toàn taïi moät taäp {P1,…,Pn} caùc quaù trình ñang ñôïi sao cho P1 ñôïi moät taøi nguyeân maø P2 ñang giöõ P2 ñôïi moät taøi nguyeân maø P3 ñang giöõ … Pn ñôïi moät taøi nguyeân maø P1 ñang giöõ Ñeå yù: Neáu moät taøi nguyeân goàm nhieàu instance thì “taøi nguyeân” ñeà caäp ôû treân laø moät instance cuûa taøi nguyeân 7 Boán ñieàu kieän caàn cho deadlock: nhaän xeùt Lieân quan ñeán chính saùch caáp phaùt taøi nguyeân cuûa heä thoáng Ñaëc ñieåm tónh cuûa heä thoáng vaø caùc taøi nguyeân ● Luoân ñuùng hoaëc luoân sai, khoâng thay ñoåi theo thôøi gian 8 Resource Allocation Graph (1/2) 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 9 Resource Allocation Graph (2/2)Kyù hieäu Process: Pi Rj Loaïi taøi nguyeân vôùi 4 thöïc theå: Rj Pi yeâu caàu moät thöïc theå cuûa Rj : Pi Rj Pi ñang giöõ moät thöïc theå cuûa Rj : Pi 10 Ví duï veà RAG (1/2) R1 R3P1 P2 P3 R2 R4 11 Ví duï veà RAG (2/2) R1 R3P1 P2 P3 Deadlock xaûy ra! R2 R4 12 RAG vaø deadlock (1/2) Ví duï moät RAG chöùa chu trình nhöng khoâng xaûy ra deadlock: tröôøng hôïp P4 traû laïi instance cuûa R2. R1 P2 P1 R2 P3 ...