Bài giảng Hệ điều hành - Chương 5: Deadlock

Mục tiêu chính của chương 5 Deadlock thuộc bài giảng Hệ điều hành nêu các nội dung chính định nghĩa Deadlock, mô hình hệ thống của Deadlock, điều khiển phát sinh Deadlock, xử lý Deadlock, sau bài giảng có ví dụ minh họa giúp sinh viên tiếp thu bài học nhanh.
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành - Chương 5: Deadlock Baøi giaûng 5 : Deadlock Ñònh nghóa Deadlock Moâ hình heä thoáng Ñieàu kieän phaùt sinh Deadlock Xöû lyù Deadlock11/7/2005 Trần Hạnh Nhi 1 Dining Philosophers Naêm trieát gia ngoài chung quanh baøn aên moùn spaghetti (yum..yum) Treân baøn coù 5 caùi nóa ñöôïc ñaët giöõa 5 caùi ñóa (xem hình) Ñeå aên moùn spaghetti moãi ngöôøi caàn coù 2 caùi nóa Trieát gia thöù i: Thinking... Eating... Chuyeän gì coù theå xaûy ra ?11/7/2005 Trần Hạnh Nhi 2 Dining Philosophers : Tình huoáng nguy hieåm 2 trieát gia “giaønh giaät” cuøng 1 caùi nóa Tranh chaáp Caàn ñoàng boä hoaù hoaït ñoäng cuûa caùc trieát gia11/7/2005 Trần Hạnh Nhi 3 Dining Philosophers : Giaûi phaùp ñoàng boä semaphore fork[5] = 1; Philosopher (i) { while(true) { down(fork[i]); down(fork[i+1 mod 5]) eat; up(fork[i]); up(fork[i+1 mod 5]); think; Deadlock }11/7/2005 Trần Hạnh Nhi 4 Ñònh nghóa Deadlock Deadlock : Chôø ñôïi moät söï kieän khoâng bao giôø xaûy ra Caùc tieán trình trong taäp hôïp chôø ñôïi laãn nhau Starvation Chôø ñôïi khoâng coù giôùi haïn moät söï kieän maø chöa thaáy xaûy ra Deadlock keùo theo Starvation Ñieàu ngöôïc laïi khoâng chaéc11/7/2005 Trần Hạnh Nhi 5 Moâ hình heä thoáng Heä thoáng bao goàm moät soá xaùc ñònh caùc loaïi taøi nguyeân seõ ñöôïc chia seû cho caùc tieán trình coù nhu caàu Moãi loaïi taøi nguyeân coù theå coù nhieàu theå hieän Moãi tieán trình söû duïng taøi nguyeân theo trình töï Request : yeâu caàu taøi nguyeân, neáu yeâu caàu khoâng ñöôïc thoaõ maõn nay, tieán trình phaûi ñôïi Use : söû duïng taøi nguyeân ñöôïc caáp phaùt Release : giaûi phoùng taøi nguyeân11/7/2005 Trần Hạnh Nhi 6 Caùc ñieàu kieän xaûy ra Deadlock Coffman, Elphick vaø Shoshani (1971) ñaõ ñöa ra 4 ñieàu kieän caàn coù theå laøm xuaát hieän taéc ngheõn: Mutual exclusion: heä thoáng coù söû duïng nhöõng loaïi taøi nguyeân mang baûn chaát khoâng chia seû ñöôïc. Wait for : Tieán trình tieáp tuïc chieám giöõ caùc taøi nguyeân ñaõ caáp phaùt cho noù trong khi chôø ñöôïc caáp phaùt theâm moät soá taøi nguyeân môùi. No preemption: Taøi nguyeân chæ ñöôïc thu hoài khi tieán trình ñang chieám giöõ chuùng töï nguyeän trao traû. Circular wait: Toàn taïi moät chu kyø trong ñoà thò caáp phaùt taøi nguyeân . Hoäi ñuû 4 ñieàu kieän treân ñaây : Deadlock coù theå xaûy ra11/7/2005 Trần Hạnh Nhi 7 Ñoà thò caáp phaùt taøi nguyeân 2 loaïi nodes: P = {P1, P2, ..., Pn}, taäp caùc tieán trình R = {R1, R2, ..., Rm}, taäp caùc loaïi taøi nguyeân Tieán trình yeâu caàu taøi nguyeân : Pi → Rj Taøi nguyeân ñöôïc caáp phaùt cho tieán trình : Rj → Pi11/7/2005 Trần Hạnh Nhi 8 Ví duï ñoà thò caáp phaùt taøi nguyeân Pi Process Rj Moät loaïi taøi nguyeân vôùi 4 theå hieän Pi yeâu caàu 1 theå hieän cuûa Rj Pi Rj Pi ñang giöõ 1 theå hieän cuûa Rj Pi Rj11/7/2005 Trần Hạnh Nhi 9 Ví duï ñoà thò caáp phaùt taøi nguyeân Example:11/7/2005 Trần Hạnh Nhi 10 Nhaän xeùt cô baûn Neáu ñoà thò khoâng coù chu trình ⇒ no deadlock. Neáu ñoà thò coù 1 chu trình ⇒ Neáu moãi taøi nguyeân chæ coù 1 theå hieän ⇒ deadlock. Neáu moãi taøi nguyeân coù nhieàu theå hieän ⇒ coù theå coù deadlock.11/7/2005 Trần Hạnh Nhi 11 Ví duï ñoà thò caáp phaùt taøi nguyeân Deadlocked:11/7/2005 Trần Hạnh Nhi 12 Ví duï ñoà thò caáp phaùt taøi nguyeân With Cyc ...