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

Các loại tài nguyên, kí hiệu R1, R2, , Rm , bao gồm: CPU cycle, không gian bộ nhớ, thiết bị I/O, file, semaphore, Mỗi loại tài nguyên Ri có Wi thực thể (instance). Giả sử tài nguyên tái sử dụng theo kỳ (Serially Reusable Resources) Yêu cầu (request): process phải chờ nếu yêu cầu không được đáp ứng ngay Sử dụng (use): process sử dụng tài nguyên Hoàn trả (release): process hoàn trả tài nguyên Các tác vụ yêu cầu (request) và hoàn trả (release) đều là system call. Ví dụ Request / release device Open / close file Allocate / free memory Wait / signal. | Khoa KTMT 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 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 Khoa KTMT 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 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); 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 . | Khoa KTMT 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 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 Khoa KTMT 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 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); 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 Khoa KTMT 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, 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 Ñò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,