Bài giảng Hệ điều hành - Chương 10: Giao tiếp giữa các tiến trình
Tiến trình độc lậpkhô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 m
Tóm tắt nội dung Bài giảng Hệ điều hành - Chương 10: Giao tiếp giữa các tiến trình, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
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.
File đính kèm:
Bài giảng Hệ điều hành - Chương 10 Giao tiếp giữa các tiến trình.pdf
