Hệ điều hành Chương VI: Tắc nghẽn (Deadlock)

Các loại tài nguyên, kí hiệu R1, R2,…, Rm , bao gồm:CPU cycle, không gian bộ nhớ, thiết bị I/O, file, semaphore,…Mỗi loại tài nguyên Ri có Wi thực thể (instance).Giả sử tài nguyên tái sử dụng theo kỳ (Serially Reusable Resources) Yêu cầu (request): process phải chờ nếu yêu cầu không được đáp ứng ngaySử dụng (use): process sử dụng tài nguyênHoàn trả (release): process hoàn trả tài nguyênCác tác vụ yêu cầu (request) và hoàn trả (release) đều là system call. Ví dụRequest / release deviceOpen / close fileAllocate / free memoryWait / signal...
Nội dung trích xuất từ tài liệu:
Hệ điều hành Chương VI: Tắc nghẽn (Deadlock) Chöông6:Taécngheõn(Deadlock) Baøi toaùn deadlock Moâ hình heä thoáng Caùc tính chaát cuûa deadlock Phöông phaùp giaûi quyeát deadlock Deadlock prevention Deadlock avoidance Deadlock detection Deadlock recovery Khoa KTMT 1 ChapterObjectives To develop a description of deadlocks, which prevent sets of concurrent processes from completing their tasks To present a number of different methods for preventing or avoiding deadlocks in a computer system Vaánñeàdeadlock 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 – 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 3 BridgeCrossingExample Traffic only in one direction Each section of a bridge can be viewed as a resource If a deadlock occurs, it can be resolved if one car backs up (lui l ại) (preempt (dành quyền) resources and rollback) Several cars may have to be backed up if a deadlock occurs Starvation is possible Note – Most OSes do not prevent or deal with deadlocks Moâhìnhhoùaheäthoáng 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 5 Ñò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ôø 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 (starvation) (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 6 Ñieàukieäncaànñeåxaûyradeadlock 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í dụ: 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 7 Ñieàukieäncaànñeåxaûyradeadlock(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 8 Ñoàthòcaápphaùttaøinguyeân (ResourceAllocationGraph)Laø ñoà thò coù höôùng, vôùi taäp ñænh V vaø taäp caïnh E Taäp ñænh V goàm2 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àm2 loaïi: – Caïnh yeâu caàu (Request edge): ø Pi Rj – Caïnh caáp phaùt (Assignment edge): Rj Pi Khoa KTMT 9 ResourceAllocationGraph(tt) Process: Pi Rj Loaïi taøi nguyeân vôùi 4 thöïc theå: Rj ...