Bài giảng Hệ điều hành: Chương 6 - ThS. Hà Lê Hoài Thương

Chương 6 Tắc nghẽn (Deadlock) thuộc bài giảng hệ điều hành nhằm trình bày về các kiến thức: mô hình hệ thống, điều kiện cần của deadlock, Resource Allocation Graph (RAG), phương pháp giải quyết Deadlock, phương pháp kết hợp để giải quyết Deadlock.
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành: Chương 6 - ThS. Hà Lê Hoài Thương Chöông 6 : Taéc ngheõn(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 1 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 2 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 3 Ñò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, 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ø trì hoaõn voâ haïn ñònh (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 4 Ñ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 deadlock1. Loaïi tröø hoã töông (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. Giöõ vaø chôø caáp theâm taøi nguyeân (Hold and wait): moät process ñang giöõ ít nhaát moät taøi nguyeân vaø ñôïi theâm taøi nguyeân do quaù trình khaùc ñang giöõ. Khoa KTMT 5 Ñieàu kieän caàn ñeå xaûy ra deadlock (tt)3. Khoâng tröng duïng (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. Chu trình ñôïi (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 6 Resource Allocation Graph (tt)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 Khoa KTMT 7 Ñoà thò caáp phaùt taøi nguyeân 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:  Caïnh yeâu caàu (Request edge): ø Pi Rj  Caïnh caáp phaùt (Assignment edge): Rj Pi Khoa KTMT 8Ví duï veà RAG R1 R3 P1 P2 P3 R2 R4 Khoa KTMT 9Ví duï veà RAG (tt) R1 R3 P1 P2 P3 ...