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

Chia sẻ: Hkmghnjm Hkmghnjm | Ngày: | Loại File: PDF | Số trang:36

Thêm vào BST

Báo xấu

185
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ù Deadlock 11/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 gia 11/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éc 11/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ân 11/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 ra 11/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 → Pi 11/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 Rj 11/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 Cycle but No Deadlock: 11/7/2005 Trần Hạnh Nhi 13
Deadlock Prevention Ñaûm baûo Deadlock khoâng theå xaûy ra Tìm caùch loaïi boû ít nhaát 1 trong 4 ñieàu kieän caàn ñeå xaûy ra Deadlock Nhaéc laïi 4 ñieàu kieän caàn Mutual Exclusion Hold and Wait No preemption Circular wait Ñeå xem... 11/7/2005 Trần Hạnh Nhi 14
Deadlock Prevention Mutual Exclusion Khoâng caàn ñaûm baûo ñoäc quyeàn truy xuaát taøi nguyeân ? Thinking... Thinking... Thinking... Vôùi caùc shareable resources : dó nhieân ! Vôùi caùc non-shareable resource : “Mission Impossible” ??? Laøm gì : virtualize, spooling... Raát haïn cheá, ñaëc bieät ñoái vôùi taøi nguyeân phaàn meàm Keát luaän : Khoâng theå loaïi boû 11/7/2005 Trần Hạnh Nhi 15
Deadlock Prevention Hold and Wait Khoâng cho vöøa chieám giöõ vöøa yeâu caàu theâm taøi nguyeân No Wait Caáp cho tieán trình taát caû caùc taøi nguyeân caàn thieát tröôùc khi baét ñaàu xöû lyù Laøm sao bieát ? No Hold Tieán trình khoâng xin ñöôïc taøi nguyeân môùi : traû laïi taøi nguyeân cuõ, vaø chôø xin laïi laàn sau “Traû laïi” taøi nguyeân ôû traïng thaùi naøo ? Söû duïng taøi nguyeân keùm hieäu quaû, coù theå starvation Keát luaän : thaät söï khoù khaû thi, khoâng theå loaïi boû 11/7/2005 Trần Hạnh Nhi 16
Deadlock Prevention No Preemption Heä ñieàu haønh chuû ñoäng thu hoài caùc taøi nguyeân cuûa tieán trình blocked Taøi nguyeân naøo coù theå thu hoài ? CPU :OK Printer : Hu hu Caùc taøi nguyeân bò thu hoài seõ ñöôïc boå sung vaøo danh saùch taøi nguyeân tieán trình caàn xin laïi. Tieán trình chæ coù theå tieáp tuïc xöû lyù khi xin laïi ñuû caùc taøi nguyeân naøy (cuõ vaø môùi) Keát luaän : thaät söï khoù loaïi boû hoaøn toaøn 11/7/2005 Trần Hạnh Nhi 17
Deadlock Prevention Traät töï naøo ? Circular Wait Khoâng ñeå xaûy ra chu trình trong ñoà thò caáp phaùt taøi nguyeân Caáp phaùt taøi nguyeân theo 1 traät töï nhaát ñònh Goïi R = {R1, R2,...,Rm} laø taäp caùc loaïi taøi nguyeân. Caùc loaïi taøi nguyeân ñöôïc phaân caáp theo ñoä öu tieân F(R) thuoäc [1-N] Ví duï : F(ñóa) = 2, F(maùy in) = 12 Caùc tieán trình khi yeâu caàu taøi nguyeân phaûi tuaân thuû quy ñònh : khi tieán trình ñang chieám giöõ taøi nguyeân Ri thì chæ coù theå yeâu caàu caùc taøi nguyeân Rj neáu F(Rj) > F(Ri). R1 F(R1) = 1; F(R2) = 2; P1 P2 R2 11/7/2005 Trần Hạnh Nhi 18
Deadlock Prevention Ñaûm baûo Deadlock khoâng theå xaûy ra Khoâng theå loaïi boû ít nhaát 1 trong 4 ñieàu kieän caàn ñeå xaûy ra Deadlock Quaù khaét khe, khoâng khaû thi... 11/7/2005 Trần Hạnh Nhi 19
Deadlock Avoidance Moät soá ñònh nghóa cô baûn Traïng thaùi an toaøn (Safe): heä thoáng coù theå thoûa maõn caùc nhu caàu taøi nguyeân (cho ñeán toái ña) cuûa taát caû caùc tieán trình theo moät thöù töï naøo ñoù maø khoâng daãn ñeán taéc ngheõn. Vieäc caáp phaùt taøi nguyeân khoâng hình thaønh chu trình naøo trong ñoà thò caáp phaùt Moät chuoãi caáp phaùt an toaøn: moät thöù töï keát thuùc caùc tieán trình sao cho vôùi moãi tieán trình Pi nhu caàu taøi nguyeân cuûa Pi coù theå ñöôïc thoûa maõn vôùi caùc taøi nguyeân coøn töï do cuûa heä thoáng, coäng vôùi caùc taøi nguyeân ñang bò chieám giöõ bôûi caùc tieán trình Pj khaùc, vôùi j