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

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ạiTài nguyên tái sử dụng theo kỳ (Serially Reusable Resources) CPU cycles, memory space, I/O devices, filesYê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, interruptsTạo ra -yêu cầu -sử dụng...
Nội dung trích xuất từ tài liệu:
Hệ điều hành 1 - Chương 6: Deadlock Chöông6: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 DeadlockKhoa KTMT Vaánñeàdeadlocktrongheä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ìnhhoùaheä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ïngKhoa KTMT Moâhìnhhoùaheä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/signalKhoa KTMT Ñònhnghó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àukieäncaànñeåxaûyradeadlock Boán ñieàu kieän caàn (necessary condition) ñeå xaûy ra deadlock1. 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àukieäncaànñeåxaûyradeadlock (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 ResourceAllocationGraph 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 PiKhoa KTMT ResourceAllocationGraph(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 R4Khoa KTMT VíduïveàRAG(tt) R1 R3 P1 ...