Hệ điều hành - Giao tiếp giữa các tiến trình

Giao tiếp giữa các tiến trình KHOA CÔNG NGHỆ THÔNG TIN TRƯỜNG ĐẠI HỌC BÁCH KHOA TP HỒ CHÍ MINH HỆ ĐIỀU HÀNH 2Một số khái niệm cơ bản* ƒ Tiến trình độc lập không ảnh hưởng và không bị ảnh hưởng bởi việc thực thi của các tiến trình khác. ƒ Tiến trình hợp tác (không độc lập) có thể ảnh hưởng và bị ảnh hưởng bởi việc thực thi của các tiến trình khác. ƒ Ưu điểm của việc hợp tác tiến trình: ƒ Chia sẻ thông tin ƒ Tăng tốc tính toán (xử lý song song) ƒ Tính module hóa ƒ Tiện lợi 3Một số khái niệm cơ bản* ƒ Các tiến trình sử dụng và cập nhập dữ liệu chia sẻ như các biến, file và cơ sở dữ liệu dùng chung. ƒ Thao tác ghi phải độc lập từng đôi một để ngăn ngừa tình trạng đụng độ, có thể dẫn đến tính không toàn vẹn dữ liệu. ƒ Các miền găng dùng để cung cấp sự toàn vẹn dữ liệu. ƒ Một tiến trình đòi hỏi miền găng phải không bị chờ mãi mãi: deadlock 4Đụng độ (race condition) ƒ Race condition: tình huống mà nhiều tiến trình cùng truy cập và thao tác dữ liệu chia sẻ một cách đồng thời. Dữ liệu cuối cùng phụ thuộc vào tiến trình cuối cùng. ƒ Để ngăn ngừa đụng độ, các tiến trình đồng hành phải được đồng bộ hóa. 5Đụng độ (race condition) 6Miền găng (critical section) ƒ n tiến trình đấu tranh với nhau để sử dụng một số dữ liệu nào đó. ƒ Mỗi tiến trình có một đoạn mã, gọi là miền găng (critical section (CS)), tại đó dữ liệu chia sẻ được truy cập. ƒ Vấn đề: bảo đảm rằng khi một tiến trình đang thực thi trong miền găng của nó, không có tiến trình nào khác được quyền thực thi trong miền găng của nó. 7Ngữ cảnh miền găng ƒ Khi một tiến trình thi hành đoạn mã thao tác trên dữ liệu chia sẻ (hay tài nguyên), chúng ta nói rằng tiến trình đó đang trong miền găng của nó. ƒ Việc thực thi các miền găng phải có tính duy nhất: tại bất kỳ thời điểm nào, chỉ có duy nhất một tiến trình được quyền thực thi trong miền găng của nó (ngay cả với nhiều bộ xử lý). ƒ Vì vậy mỗi tiến trình phải yêu cầu quyền trước khi vào miền găng. 8Ngữ cảnh miền găng ƒ Đoạn mã thể hiện yêu cầu này được gọi làEntry Section (ES). ƒ Miền găng (CS) có thể theo sau là Leave/Exit Section (LS). ƒ Phần đoạn mã còn lại là Remainder Section (RS). ƒ Vấn đề của miền găng là thiết kế một giao thức mà các tiến trình có thể sử dụng để hành động của chúng sẽ không phụ thuộc vào thứ tự mà sự thi hành của chúng được chen vào. 9Giải pháp cho vấn đề miền găng ƒ Có 3 yêu cầu mà một giải pháp đúng cần phải thỏa mãn: 1. Mutual Exclusion: không có 2 tiến trình cùng ở trong miền găng một lúc 2. Progress: Một tiến trình bên ngoài miền găng không được ngăn cản các tiến trình khác vào miền găng 3. Bounded Waiting: không có tiến trình nào phải chờ vô hạn để vào miền găng ƒ Chỉ cần một trong ba điều kiện trên sai thì giải pháp đưa ra là sai. 10 Cấu trúc của các tiến trình ƒ Cấu trúc tổng quát của tiến trình Pi (Pj) do { entry section critical section leave section remainder section } while (1); ƒ Lưu ý: Các tiến trình có thể chia sẻ các biến dùng chung để đồng bộ hóa hoạt động của chúng. 11 Phân loại các giải pháp cho CS ƒ Giaûi phaùp busy-waiting ƒ Alg. 1 & 2, Peterson, Dekker, Bakery, ƒ TSL, Interrupt ƒ Giaûi phaùp sleep and wake-up ƒ Semaphore ƒ Monitor 12 Giaûi thuaät 1 ƒ Bieán chia seû ƒ int turn; /* khôûi ñaàu turn = 0 */ ƒ neáu turn = i⇒ Pi ñöôïc pheùp vaøo critical section ƒ Process Pi do { while (turn != i) ; critical section(); turn = j; remainder section(); } while (1); ƒ Thoaû maõn mutual exclusion (1) ƒ Progress (2) & bounded-waiting (3) ? 13 Giaûi thuaät 1 Process P0: do while(turn !=0 ); Critical_Section(); turn=1; Remainder_Section(); while (1); Process P1: do while(turn!=1); Critical_Section(); turn=0; Remainder_Section(); while (1); Ví duï: P0 coù RS raát lôùn vaø P1 coù RS nhoû. Neáu turn=0, P0 ñöôïc vaøo CS vaø sau ñoù thöïc thi vuøng RS (turn=1). Ñeán P1 vaøo CS vaø sau ñoù thöïc thi RS (turn=0) vaø tìm caùch vaøo CS moät laàn nöõa nhöng yeâu caàu bò töø choái !!! P1 phaûi chôø P0 !!!. 14 Giaûi thuaät 2 ƒ Bieán chia seû ƒ boolean flag[2]; /* khôûi ñaàu flag [0] = flag [1] = false. */ ƒ Neáu flag [i] = true⇒ Pi saün saøng vaøo critical section ƒ Process Pi do { flag[i] = true; while (flag[j]) ; Critical_Section(); flag [i] = false; Remainder_Section(); } while (1); 15 Giaûi thuaät 3 (Peterson) ƒ Bieán chia seû: keát hôïp caû giaûi thuaät 1 vaø 2. ƒ Process Pi do { flag [i]= true; turn = j; while (flag [j] and turn == j) ; Critical_Section(); flag [i] = false; Remainder_Section(); } while (1); 16 Giaûi thuaät Bakery: N process ƒ Tröôùc khi vaøo CS, process Pi nhaän moät con soá. Process naøo giöõ con soá nhoû nhaát thì ñöôïc vaøo CS ƒ Tröôøng hôïp Pi vaø Pj cuøng nhaän ñöôïc moät chæ soá: ƒ Neáu i < j thì Pi ñöôïc vaøo tröôùc, ngöôïc laïi Pj ñöôïc vaøo tröôùc. ƒ Khi ra khoûi CS, Pi ñaët laïi soá cuûa mình baèng 0 ƒ Cô cheá caáp soá cho caùc process thöôøng taïo caùc soá theo cô cheá taêng daàn, ví duï 1,2,3,3,3,3,4,5... 17 Leänh TSL (Test-and-Set Lock) ƒ Kieåm tra vaø caäp nhaät moät bieán trong moät thao taùc ñôn (atomic) bool TestandSet(bool &target) { bool rv = target; target = true; return rv; } nShared data: bool lock = false; nProcess Pi while (1) { while (TestandSet(lock)) ; Critical_Section; lock = false; Remainder_Section; } 18 Semaphores ƒ Là một công cụ đồng bộ hóa được cung cấp bởi HĐH không đòi hỏi “busy waiting”. ƒ Một semaphore S là một biến nguyên mà ngoài lệnh khởi tạo ra, chỉ có thể được truy xuất thông qua hai thao tác độc quyền truy xuất và nguyên tố: ƒ wait(S) ƒ signal(S) 19 Semaphores ƒ Truy cập với 2 thao tác wait (S): while S≤ 0 do no-op; S--; signal (S): S++; ƒ Để tránh “busy waiting”: khi một tiến trình phải đợi, nó sẽ được đặt vào hàng đợi block. ƒ Khi một tiến trình phải đợi một semaphore S, nó sẽ bị block và đặt vào hàng đợi của semaphore tương ứng. ƒ Thao tác signal lấy một tiến trình từ trong hàng đợi và đặt nó vào trong danh sách các tiến trình ở trạng thái sẵn sàng. 20 Semaphores ƒ Định nghĩa cấu trúc: typedef struct { int value; struct process *L; } semaphore; ƒ Giả sử có 2 thao tác cơ bản: ƒ Block tạm cho tiến trình chờ. ƒ wakeup(P) khôi phục lại sự thi hành của tiến trình bị block P. 21 Semaphores wait(S): S.value--; if (S.value < 0) { add this process to S.L; block; } signal(S): S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } -8.22- 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); -8.23- 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). ‰ Process thöôøng söû duïng taøi nguyeân theo thöù töï sau – 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 -8.24- Ñ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. 2. 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öõ. -8.25- Ñieàu kieän caàn ñeå xaûy ra deadlock (tt) 3. No 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 chu trình cuûa caùc yeâu caàu taøi nguyeân vaø taøi nguyeân ñaõ ñöôïc caáp phaùt. P1 P2 -8.26- 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û 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 -8.27- Resource Allocation Graph (tt) Kyù hieäu ‰ Process: ‰ Loaïi taøi nguyeân vôùi 4 thöïc theå: ‰ Pi yeâu caàu moät thöïc theå cuûa Rj : ‰ Pi ñang giöõ moät thöïc theå cuûa Rj : Pi Pi Pi R j R j R j -8.28- Ví duï veà RAG R1 R3 P1 P2 P3 R2 R4 -8.29- Ví duï veà RAG (tt) R1 R3 P1 P2 P3 R2 R4 Deadlock xaûy ra! -8.30- 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 P1 P2 P3R2 P4 -8.31- 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 -8.32- Caùc phöông phaùp giaûi quyeát deadlock ‰ Duøng moät giao thöùc (protocol) ñeå ngaên (preventing) hoaëc traùnh (avoiding) deadlock, baûo ñaûm raèng heä thoáng khoâng rôi vaøo tình traïng deadlock. ‰ 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. ‰ 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. -8.33- Ngaên deadlock Ngaên deadlock baèng caùch ngaên moät trong 4 ñieàu kieän gaây 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 -8.34- 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 ƒ Quaù trình coù theå bò starvation -8.35- 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ò laáy laïi. Tuy nhieân heä thoáng chæ laáy laïi caùc taøi nguyeân maø process khaùc yeâu caàu -8.36- 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. -8.37- 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 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å cuûa loaïi taøi nguyeân Rj thì noù phaûi traû laïi caùc taøi nguyeân Ri vôùi F(Ri) > F(Rj). – Chöùng minh baèng phaûn chöùng: ƒ F(R4) < F(R1) ƒ F(R1) < F(R2) ƒ F(R2) < F(R3) ƒ F(R3) < F(R4) ƒ Vaäy F(R4) < F(R4), maâu thuaån! P1 R 1 P2 P4 P3 R 3 R 2 R 4 -8.38- Deadlock avoidance ‰ Deadlock prevention söû duïng taøi nguyeân khoâng hieäu quaû. ‰ Deadlock avoidance vaãn ñaûm baûo hieäu suaát söû duïng taøi nguyeân toái ña ñeán möùc coù theå. ‰ Yeâu caàu moãi process khai baùo soá löôïng taøi nguyeân toái ña caàn ñeå thöïc hieän coâng vieäc ‰ Giaûi thuaät deadlock-avoidance seõ kieåm tra traïng thaùi caáp phaùt taøi nguyeân (resource-allocation state) ñeå baûo ñaûm heä thoáng khoâng bao giôø rôi vaøo deadlock. ‰ Traïng thaùi caáp phaùt taøi nguyeân ñöôïc ñònh nghóa döïa treân soá taøi nguyeân coøn laïi, soá taøi nguyeân ñaõ ñöôïc caáp phaùt vaø yeâu caàu toái ña cuûa caùc process. -8.39- Traïng thaùi safe vaø unsafe ‰ Moät traïng thaùi cuûa heä thoáng ñöôïc goïi laø an toaøn (safe) neáu toàn taïi moät chuoãi an toaøn (safe sequence). -8.40- Chuoãi an toaøn ‰ Moät chuoãi quaù trình laø moät chuoãi an toaøn neáu – Vôùi moïi i = 1,, n, taøi nguyeân (maø Pi coøn coù theå yeâu caàu) coù theå ñöôïc thoûa bôûi taøi nguyeân ñang saün saøng (available) cuøng vôùi taøi nguyeân maø taát caû Pj , j < i, ñang giöõ. ‰ Moät traïng thaùi cuûa heä thoáng ñöôïc goïi laø khoâng an toaøn (unsafe) neáu khoâng toàn taïi moät chuoãi an toaøn. -8.41- Chuoãi an toaøn (tt) Ví duï: Heä thoáng coù 12 tape drives vaø 3 quaù trình P0, P1, P2 ‰ Taïi thôøi ñieåm t0 – Coøn 3 tape drive saün saøng. – Chuoãi laø chuoãi an toaøn ⇒ heä thoáng laø an toaøn P0 10 5 P1 4 2 P2 9 2 caàn toái ña ñang giöõ -8.42- Chuoãi an toaøn (tt) ‰ Giaû söû taïi thôøi ñieåm t1, P2 yeâu caàu vaø ñöôïc caáp phaùt 1 tape drive • Heä thoáng trôû neân khoâng an toaøn. P0 10 5 P1 4 2 P2 9 3 caàn toái ña ñang giöõ -8.43- ‰ Khi moät process yeâu caàu moät taøi nguyeân ñang saün saøng (available), heä thoáng seõ kieåm tra: neáu vieäc caáp phaùt naøy khoâng daãn ñeán tình traïng unsafe thì seõ caáp phaùt ngay. -8.44- Traïng thaùi safe/unsafe vaø deadlock ‰ Neáu heä thoáng ñang ôû traïng thaùi safe ⇒ khoâng deadlock. ‰ Neáu heä thoáng ñang ôû traïng thaùi unsafe ⇒ coù khaû naêng daãn ñeán deadlock. ‰ Traùnh deadlock baèng caùch baûo ñaûm heä thoáng khoâng ñi ñeán traïng thaùi unsafe. safe deadlock unsafe -8.45- Giaûi thuaät banker ‰ AÙp duïng cho heä thoáng caáp phaùt taøi nguyeân trong ñoù moãi loaïi taøi nguyeân coù theå coù nhieàu instance. ‰ Baét chöôùc nghieäp vuï ngaân haøng (banking) ‰ Ñieàu kieän – Moãi process phaûi khai baùo soá löôïng thöïc theå (instance) toái ña cuûa moãi loaïi taøi nguyeân maø noù caàn – Khi process yeâu caàu taøi nguyeân thì coù theå phaûi ñôïi maëc duø taøi nguyeân ñöôïc yeâu caàu ñang coù saün – Khi process ñaõ coù ñöôïc ñaày ñuû taøi nguyeân thì phaûi hoaøn traû trong moät khoaûng thôøi gian höõu haïn naøo ñoù. -8.46- Giaûi thuaät banker (tt) n: soá process, m: soá loaïi taøi nguyeân Caùc caáu truùc döõ lieäu Available: vector ñoä daøi m Available[ j ] = k⇔ loaïi taøi nguyeân Rj coù k instance saün saøng Max: ma traän n × m Max[ i, j ] = k ⇔ quaù trình Pi yeâu caàu toái ña k instance cuûa loaïi taøi nguyeân Rj Allocation: ma traän n × m Allocation[i, j] = k ⇔ Pi ñaõ ñöôïc caáp phaùt k instance cuûa Rj Need: ma traän n × m Need[i, j] = k ⇔ Pi caàn theâm k instance cuûa Rj Nhaän xeùt: Need [i, j] = Max[i, j] – Allocation [i, j] Kyù hieäu Y ≤ X⇔ Y[i] ≤ X[i], ví duï (0, 3, 2, 1) ≤ (1, 7, 3, 2) -8.47- Giaûi thuaät kieåm tra traïng thaùi an toaøn Tìm moät chuoãi an toaøn 1. Goïi Work vaø Finish laø hai vector ñoä daøi laø m vaø n. Khôûi taïo Work := Available Finish[i] := false, i = 1,, n 2. Tìm i thoûa (a) Finish [i] = false (b) Needi ≤Work (haøng thöù i cuûa Need) Neáu khoâng toàn taïi i nhö vaäy, ñeán böôùc 4. 3. Work := Work + Allocationi Finish[i] := true quay veà böôùc 2. 4. Neáu Finish[i] = true, i = 1,, n, thì heä thoáng ñang ôû traïng thaùi safe Thôøi gian chaïy cuûa giaûi thuaät laø O(m·n2) -8.48- Giaûi thuaät caáp phaùt taøi nguyeân Goïi Requesti laø request vector cuûa process Pi. Requesti [j] = k ⇔ Pi caàn k instance cuûa taøi nguyeân Rj. 1. Neáu Requesti ≤ Needi thì ñeán böôùc 2. Neáu khoâng, baùo loãi vì process ñaõ vöôït yeâu caàu toái ña. 2. Neáu Requesti ≤ Available thì qua böôùc 3. Neáu khoâng, Pi phaûi chôø vì taøi nguyeân khoâng coøn ñuû ñeå caáp phaùt. -8.49- Giaûi thuaät caáp phaùt taøi nguyeân (tt) 3. Giaû ñònh caáp phaùt taøi nguyeân ñaùp öùng yeâu caàu cuûa Pi baèng caùch caäp nhaät traïng thaùi heä thoáng nhö sau: Available := Available – Requesti Allocationi := Allocationi + Requesti Needi := Needi – Requesti Aùp duïng giaûi thuaät kieåm tra traïng thaùi an toaøn leân traïng thaùi treân ƒ Neáu traïng thaùi laø safe thì taøi nguyeân ñöôïc caáp thöïc söï cho Pi . ƒ Neáu traïng thaùi laø unsafe thì Pi phaûi ñôïi, vaø • phuïc hoài traïng thaùi: Available := Available + Requesti Allocationi := Allocationi – Requesti Needi := Needi + Requesti -8.50- Ví duï ‰ Coù 5 process P0 ,, P4 ‰ Coù 3 loaïi taøi nguyeân: A (coù 10 instance), B (5 instance) vaø C (7 instance). ‰ Sô ñoà caáp phaùt trong heä thoáng taïi thôøi ñieåm T0 Allocation Max Available Need A B C A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 7 4 3 P1 2 0 0 3 2 2 1 2 2 P2 3 0 2 9 0 2 6 0 0 P3 2 1 1 2 2 2 0 1 1 P4 0 0 2 4 3 3 4 3 1 n o p q r -8.51- Vd (tt) Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 3 3 2 P1 2 0 0 1 2 2 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Chuoãi an toaøn 7 4 3 7 4 5 10 4 7 10 5 7 5 3 2 -8.52- GT. caáp phaùt taøi nguyeân – Ví duï ‰ Yeâu caàu (1, 0, 2) cuûa P1 coù thoûa ñöôïc khoâng? – Kieåm tra ñieàu kieän Request1 ≤ Available: ƒ (1, 0, 2) ≤ (3, 3, 2) laø ñuùng – Giaû ñònh thoûa yeâu caàu, kieåm tra traïng thaùi môùi coù phaûi laø safe hay khoâng. – Traïng thaùi môùi laø safe (chuoãi an toaøn laø ), vaäy coù theå caáp phaùt taøi nguyeân cho P1. Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 -8.53- Phaùt hieän deadlock ‰ Chaáp nhaän xaûy ra deadlock trong heä thoáng, kieåm tra traïng thaùi heä thoáng baèng giaûi thuaät phaùt hieän deadlock. ‰ Neáu coù deadlock thì tieán haønh phuïc hoài heä thoáng ‰ Caùc giaûi thuaät phaùt hieän deadlock thöôøng söû duïng moâ hình RAG. ‰ Heä thoáng caáp phaùt taøi nguyeân ñöôïc khaûo saùt trong moãi tröôøng hôïp sau 1. Moãi loaïi taøi nguyeân chæ coù moät thöïc theå (instance) 2. Moãi loaïi taøi nguyeân coù theå coù nhieàu thöïc theå -8.54- Moãi loaïi taøi nguyeân chæ coù moät thöïc theå ‰ Söû duïng wait-for graph – Wait-for graph ñöôïc daãn xuaát töø RAG baèng caùch boû caùc node bieåu dieãn taøi nguyeân vaø gheùp caùc caïnh töông öùng. ƒ Coù caïnh töø Pi ñeán Pj⇔ Pi ñang chôø taøi nguyeân töø Pj ‰ Moät giaûi thuaät kieåm tra coù toàn taïi chu trình trong wait-for graph hay khoâng seõ ñöôïc goïi ñònh kyø. Giaûi thuaät phaùt hieän chu trình coù thôøi gian chaïy laø O(n 2), vôùi n laø soá ñænh cuûa graph. R1 R3 R4 P2P1 P3 P5 R2 R5P4 P2P1 P3 P5 P4 -8.55- Moãi loaïi taøi nguyeân coù nhieàu thöïc theå ‰ Phöông phaùp duøng wait-for graph khoâng aùp duïng ñöôïc cho tröôøng hôïp moãi loaïi taøi nguyeân coù nhieàu instance. ‰ Caùc caáu truùc döõ lieäu duøng trong giaûi thuaät phaùt hieän deadlock • Available: vector ñoä daøi m • soá instance saün saøng cuûa moãi loaïi taøi nguyeân • Allocation: ma traän n × m • soá instance cuûa moãi loaïi taøi nguyeân ñaõ caáp phaùt cho moãi process • Request: ma traän n × m • yeâu caàu hieän taïi cuûa moãi process. • Request [i,j] = k ⇔ Pi ñang yeâu caàu theâm k instance cuûa Rj -8.56- Giaûi thuaät phaùt hieän deadlock 1. Goïi Work vaø Finish laø vector kích thöôùc m vaø n. Khôûi taïo: Work := Available i = 1, 2,, n, neáu Allocationi ≠ 0 thì Finish[i] := false coøn khoâng thì Finish[i] := true 2. Tìm i thoûa maõn: Finish[i] := false vaø Requesti ≤ Work • Neáu khoâng toàn taïi i nhö theá, ñeán böôùc 4. 3. Work := Work + Allocationi Finish[i] := true quay veà böôùc 2. 4. Neáu Finish[i] = false, vôùi moät i = 1,, n, thì heä thoáng ñang ôû traïng thaùi deadlock. Hôn theá nöõa, Finish[i] = false thì Pi bò deadlocked. thôøi gian chaïy cuûa giaûi thuaätO(m·n2) -8.57- Ví duï ‰ Heä thoáng coù 5 quaù trình P0 ,, P4 • 3 loaïi taøi nguyeân: A (7 instance), B (2 instance), C (6 instance). Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Chaïy giaûi thuaät, tìm ñöôïc chuoãi vôùi Finish[i] = true, i = 1,, n, vaäy heä thoáng khoâng bò deadlocked. -8.58- Ví duï (tt) ‰ P2 yeâu caàu theâm moät instance cuûa C. Ma traän Request nhö sau: Request A B C P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2 – Traïng thaùi cuûa heä thoáng laø gì? ƒ Coù theå thu hoài taøi nguyeân ñang sôû höõu bôûi process P0 nhöng vaãn khoâng ñuû ñaùp öùng yeâu caàu cuûa caùc process khaùc. • Vaäy toàn taïi deadlock, bao goàm caùc process P1, P2, P3, vaø P4 . -8.59- Deadlock Recovery ‰ Khi deadlock xaûy ra, ñeå phuïc hoài – baùo ngöôøi vaän haønh (operator) hoaëc – heä thoáng töï ñoäng phuïc hoài baèng caùch beû gaõy chu trình deadlock: ƒ chaám döùt moät hay nhieàu quaù trình ƒ laáy laïi taøi nguyeân töø moät hay nhieàu quaù trình -8.60- Deadlock Recovery: Chaám döùt quaù trình ‰ Phuïc hoài heä thoáng bò deadlock baèng caùch chaám döùt quaù trình – Chaám döùt taát caû process bò deadlocked – Chaám döùt laàn löôït töøng process cho ñeán khi khoâng coøn deadlock ƒ Söû duïng giaûi thuaät phaùt hieän deadlock ñeå xaùc ñònh coøn deadlock hay khoâng ‰ Döïa treân yeáu toá naøo ñeå chaám döùt process? – Ñoä öu tieân cuûa process – Thôøi gian ñaõ thöïc thi cuûa process vaø thôøi gian coøn laïi – Loaïi taøi nguyeân maø process ñaõ söû duïng – Taøi nguyeân maø process caàn theâm ñeå hoaøn taát coâng vieäc – Soá löôïng processes caàn ñöôïc chaám döùt – Process laø interactive process hay batch process -8.61- Deadlock recovery: Laáy laïi taøi nguyeân ‰ Laáy laïi taøi nguyeân töø moät process, caáp phaùt cho process khaùc cho ñeán khi khoâng coøn deadlock nöõa. ‰ Caùc vaán ñeà trong chieán löôïc thu hoài taøi nguyeân: – Choïn “naïn nhaân” ñeå toái thieåu chi phí (coù theå döïa treân soá taøi nguyeân sôû höõu, thôøi gian CPU ñaõ tieâu toán,...) – Rollback: rollback process bò laáy laïi taøi nguyeân trôû veà traïng thaùi safe, baét ñaàu process töø traïng thaùi ñoù. Heä thoáng caàn löu giöõ moät soá thoâng tin veà traïng thaùi caùc process ñang thöïc thi. – Starvation: phaûi baûo ñaûm khoâng coù process seõ luoân luoân bò laáy laïi taøi nguyeân moãi khi deadlock xaûy ra.