Hệ điều hành 1 - Chương 6: Deadlock

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:46

Thêm vào BST

Báo xấu

77
lượt xem 6
download

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

Khái niệm tài nguyên (Resource) Là tất cả những gì được yêu cầu bởi tiến trình để xử lý Tài nguyên có thể ở nhiều loại Tài nguyên tái sử dụng theo kỳ (Serially Reusable Resources) CPU cycles, memory space, I/O devices, files Yêu cầu - sử dụng - trả lại (release) Tài nguyên tiêu thụ (Consumable Resources) Được sản sinh bởi một tiến trình, cần bởi một tiến trình - e.g. Messages, buffers of information, interrupts Tạo ra -yêu cầu -sử dụng...

Chủ đề:

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

Lưu

Nội dung Text: Hệ điều hành 1 - Chương 6: Deadlock

Chöông 6 : Deadlock  Moâ hình heä thoáng  Ñònh nghóa  Ñieàu kieän caàn cuûa deadlock  Resource Allocation Graph (RAG)  Phöông phaùp giaûi quyeát deadlock  Deadlock prevention  Deadlock avoidance  Deadlock detection  Deadlock recovery  Phöông phaùp keát hôïp ñeå giaûi quyeát Deadlock Khoa KTMT
Vaán ñeà deadlock trong heä thoáng  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 – Giaû söû 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); Khoa KTMT
Moâ hình hoùa heä thoáng  Khaùi nieäm taøi nguyeân (Resource)  Laø taát caû nhöõng gì ñöôïc yeâu caàu bôûi tieán trình ñeå xöû lyù  Taøi nguyeân coù theå ôû nhieàu loaïi  Taøi nguyeân taùi söû duïng theo kyø (Serially Reusable Resources) – CPU cycles, memory space, I/O devices, files – Yeâu caàu -> söû duïng -> traû laïi (release)  Taøi nguyeân tieâu thuï (Consumable Resources) – Ñöôïc saûn sinh bôûi moät tieán trình, caàn bôûi moät tieán trình - e.g. Messages, buffers of information, interrupts – Taïo ra ->yeâu caàu ->söû duïng Khoa KTMT
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 , 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ôø xảy ra. Thoâng thöôøng, coù nhieàu hôn moät tieán trình bò lieân quan trong moät deadlock.  Moät tieán trình goïi laø indefinitely postponed neáu noù bò trì hoaõn moät khoaûng thôøi gian daøi laëp ñi laëp laïi trong khi heä thoáng ñaùp öùng cho nhöõng tieán trình khaùc .  i.e. Moät tieán trình saün saøng ñeå xöû lyù nhöng noù khoâng bao giôø nhaän ñöôïc CPU. Khoa KTMT
Ñieàu kieän caàn ñeå xaûy ra deadlock Boán ñieàu kieän caàn (necessary condition) ñeå xaûy ra deadlock 1. Mutual exclusion: ít nhaát moät taøi nguyeân ñöôïc giöõ theo nonsharable mode (ví duï: printer; ví duï sharable resource: read- only files). 2. Hold and wait: moät process ñang giöõ ít nhaát moät taøi nguyeân vaø ñôïi theâmtaøi nguyeân do quaù trình khaùc ñang giöõ. Khoa KTMT
Ñieàu kieän caàn ñeå xaûy ra deadlock (tt) 3. No preemption: (=no resource preemption) taøi nguyeân khoâng theå bò laáy laïi, maø chæcoù theå ñöôïc traû laïi töø process ñang giöõ taøi nguyeân ñoù khi noù muoán. 4. Circular wait: toàn taïi moät taäp {P0,…,Pn} caùc quaù trình ñang ñôïi sao cho P0 ñôïi moät taøi nguyeân maø P1 ñang giöõ P1 ñôïi moät taøi nguyeân maø P2 ñang giöõ … Pn ñôïi moät taøi nguyeân maø P0 ñang giöõ Khoa KTMT
Resource Allocation Graph  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 Khoa KTMT
Resource Allocation Graph (tt) Kyù hieäu  Process: Pi Rj  Loaïi taøi nguyeân vôùi 4 thöïc theå: Rj Pi  Pi yeâu caàu moät thöïc theå cuûa Rj : Rj Pi  Pi ñang giöõ moät thöïc theå cuûa Rj : Khoa KTMT
Ví duï veà RAG R1 R3 P1 P2 P3 R2 R4 Khoa KTMT
Ví duï veà RAG (tt) R1 R3 P1 P2 P3 Deadlock xaûy ra! R2 R4 Khoa KTMT
RAG vaø deadlock  Ví duï moät RAG chöùa chu trình nhöng khoâng xaûy ra deadlock: P4 coù theå traû laïi instance cuûa R2. R1 P2 P1 R2 P3 P4 Khoa KTMT
RAG vaø deadlock (tt)  RAG khoâng chöùa chu trình (cycle) ⇒ khoâng coù deadlock  RAG chöùa moät (hay nhieàu) chu trình – 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 KTMT
Caùc phöông phaùp giaûi quyeát deadlock (1) • Ba phöông phaùp • 1) Baûo ñaûm raèng heä thoáng khoâng rôi vaøo tình traïng deadlock baèng caùch ngaên (preventing) hoaëc traùnh (avoiding) deadlock. • Khaùc bieät – Ngaên deadlock: khoâng cho pheùp (ít nhaát) moät trong 4 ñieàu kieän caàn cho deadlock – Traùnh deadlock: caùc quaù trình caàn cung caáp thoâng tin veà taøi nguyeân noù caàn ñeå heä thoáng caáp phaùt taøi nguyeân moät caùch thích hôïp Khoa KTMT
Caùc phöông phaùp giaûi quyeát deadlock (2) • 2) Cho pheùp heä thoáng vaøo traïng thaùi deadlock, nhöng sau ñoù phaùt hieän deadlock vaø phuïc hoài heä thoáng. • 3) Boû qua moïi vaán ñeà, xem nhö deadlock khoâng bao giôø xaûy ra trong heä thoáng. Khaù nhieàu heä ñieàu haønh söû duïng phöông phaùp naøy. – Deadlock khoâng ñöôïc phaùt hieän, daãn ñeán vieäc giaûm hieäu suaát cuûa heä thoáng. Cuoái cuøng, heä thoáng coù theå ngöng hoaït ñoäng vaø phaûi ñöôïc khôûi ñoäng laïi. Khoa KTMT
Ngaên deadlock  Ngaên deadlock baèng caùch ngaên moät trong 4 ñieàu kieän caàn cuûa deadlock 1. Ngaên mutual exclusion – ñoái vôùi nonsharable resource (vd: printer): khoâng laøm ñöôïc – ñoái vôùi sharable resource (vd: read-only file): khoâng caàn thieát Khoa KTMT
Ngaên deadlock (tt) 2. Ngaên Hold and Wait – Caùch 1: moãi process yeâu caàu toaøn boä taøi nguyeân caàn thieát moät laàn. Neáu coù ñuû taøi nguyeân thì heä thoáng seõ caáp phaùt, neáu khoâng ñuû taøi nguyeân thì process phaûi bò blocked. – Caùch 2: khi yeâu caàu taøi nguyeân, process khoâng ñöôïc giöõ baát kyø taøi nguyeân naøo. Neáu ñang coù thì phaûi traû laïi tröôùc khi yeâu caàu. – Ví duï ñeå so saùnh hai caùch treân: moät quaù trình copy döõ lieäu töø tape drive sang disk file, saép xeáp disk file, roài in keát quaû ra printer. – Khuyeát ñieåm cuûa caùc caùch treân:  Hieäu suaát söû duïng taøi nguyeân (resource utilization) thaáp Khoa KTMT
Ngaên deadlock (tt) 3. Ngaên No Preemption: neáu process A coù giöõ 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 caáp phaùt ngay ñöôïc thì – Caùch 1: Heä thoáng laáy laïi moïi taøi nguyeân maø A ñang giöõ  A chæ baét ñaàu laïi ñöôïc khi coù ñöôïc caùc taøi nguyeân ñaõ bò laáy laïi cuøng vôùi taøi nguyeân ñang yeâu caàu – Caùch 2: Heä thoáng seõ xem taøi nguyeân maø A yeâu caàu  Neáu taøi nguyeân ñöôïc giöõ bôûi moät process khaùc ñang ñôïi theâm taøi nguyeân, taøi nguyeân naøy ñöôïc heä thoáng laáy laïi vaø caáp phaùt cho A.  Neáu taøi nguyeân ñöôïc giöõ bôûi process khoâng ñôïi taøi nguyeân, A phaûi ñôïi vaø taøi nguyeân cuûa A bò Khoa KTMT
Ngaên deadlock (tt) 4. Ngaên Circular Wait: taäp caùc loaïi taøi nguyeân trong heä thoáng ñöôïc gaùn moät thöù töï hoaøn toaøn. – Ví duï: F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12  F laø haøm ñònh nghóa thöù töï treân taäp caùc loaïi taøi nguyeân. Khoa KTMT
Ngaên deadlock (tt) 4. Ngaên Circular Wait (tt) – Caùch 1: moãi process chæ coù theå yeâu caàu thöïc theå cuûa moät loaïi taøi nguyeân theo thöù töï taêng daàn (ñònh nghóa bôûi haøm F) cuûa loaïi taøi nguyeân. Ví duï  Chuoãi yeâu caàu thöïc theå hôïp leä: tape drive → disk drive → printer  Chuoãi yeâu caàu thöïc theå khoâng hôïp leä: disk drive → tape drive – Caùch 2: Khi moät process yeâu caàu moät thöïc theå R1 cuûa loaïi taøi nguyeân Rj thì noù phaûi traû laïi caùcP taøi nguyeân Ri vôùi P2 1 F(Ri) > F(Rj). – R4 “Chöùng minh” cho caùch 1: phaûn chöùng R2  F(R4) < F(R1) R3  F(R1) < F(R2) P4 P3  F(R2) < F(R3) Khoa KTMT  F(R ) < F(R )