Tài liệu môn học Hệ điều hành (operating systems)

eå bò starvation Khoa KTMT 206 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 Khoa KTMT 207 Ngaên deadlock (tt) 4. Ngaên Circular Wait: gaùn moät thöù töï cho taát caû caùc taøi nguyeân trong heä thoáng. ‟ Taäp hôïp loaïi taøi nguyeân: R={R 1 , R 2, ,R m } Haøm aùnh xaï: F: R->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. Khoa KTMT 208 Ngaên deadlock (tt) 4. Ngaên Circular Wait (tt) ‟ 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 (ñònh nghóa bôûi haøm F) 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 ‟ Khi moät process yeâu caàu moät thöïc theå cuûa loaïi taøi nguyeân R j thì noù phaûi traû laïi caùc taøi nguyeân R i vôùi F(R i ) > F(R j ). ‟ “Chöùng minh” giaû söû toàn taïi moät chu trình deadlock  F(R 4 ) < F(R 1 )  F(R 1 ) < F(R 2 )  F(R 2 ) < F(R 3 )  F(R 3 ) < F(R 4 ) „ Vaäy F(R 4 ) < F(R 4 ), maâu thuaãn! P1 R1 P2 P4 P3 R3 R2 R4 Khoa KTMT 209 2. Traùnh taéc ngheõn 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 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. Khoa KTMT 210 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 (thöù tự)ï an toaøn (safe sequence).  Moät chuoãi quaù trình <P 1 , P 2 ,, P n > laø moät chuoãi an toaøn neáu ‟ Vôùi moïi i = 1,,n, yeâu caàu toái ña veà taøi nguyeân cuûa P i coù theå ñöôïc thoûa bôûi  taøi nguyeân maø heä thoáng ñang coù saün saøng (available)  cuøng vôùi taøi nguyeân maø taát caû P j , 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. Khoa KTMT 211 Chuoãi an toaøn (tt) Ví duï: Heä thoáng coù 12 tape drives vaø 3 quaù trình P 0 , P 1 , P 2  Taïi thôøi ñieåm t 0 ‟ Coøn 3 tape drive saün saøng. ‟ Chuoãi <P 1 , P 0 , P 2 > laø chuoãi an toaøn  heä thoáng laø an toaøn Maximum needs Current needs P 0 10 5 P 1 4 2 P 2 9 2 Khoa KTMT 212 Chuoãi an toaøn (tt)  Giaû söû taïi thôøi ñieåm t 1 , P 2 yeâu caàu vaø ñöôïc caáp phaùt 1 tape drive ‟ coøn 2 tape drive saün saøng  Heä thoáng coøn an toaøn khoâng? P 0 10 5 P 1 4 2 P 2 9 3 caàn toái ña ñang giöõ Khoa KTMT 213 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ù theå 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 Khoa KTMT 214 Giaûi thuaät ñoà thò caáp phaùt taøi nguyeân  Khaùi nieäm caïnh thænh caàu P 1 P 2 P 1 P2 R 1 R 2 R 1 R 2 Khoa KTMT 215 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ù. Khoa KTMT 216 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 R j coù k instance saün saøng Max: ma traän n  m Max[ i, j ] = k  quaù trình P i yeâu caàu toái ña k instance cuûa loaïi taøi nguyeân R j 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) Khoa KTMT 217 Giaûi thuaät banker (tt) 1.Giaûi thuaät 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) Need i  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 + Allocation i 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·n 2 ) Khoa KTMT 218 Giaûi thuaät banker (tt) 2. Giaûi thuaät yeâu caàu (caáp phaùt) taøi nguyeân Goïi Request i laø request vector cuûa process P i . Request i [ j ] = k  P i caàn k instance cuûa taøi nguyeân R j . 1. Neáu Request i  Need i 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 Request i  Available thì qua böôùc 3. Neáu khoâng, P i phaûi chôø vì taøi nguyeân khoâng coøn ñuû ñeå caáp phaùt. 3. Giaû ñònh caáp phaùt taøi nguyeân ñaùp öùng yeâu caàu cuûa P i baèng caùch caäp nhaät traïng thaùi heä thoáng nhö sau: Available := Available ‟ Request i Allocation i := Allocation i + Request i Need i := Need i ‟ Request i Khoa KTMT 219 Giaûi thuaät banker (tt) 2.Giaûi thuaät yeâu caàu taøi nguyeân 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 P i .  Neáu traïng thaùi laø unsafe thì P i phaûi ñôïi, vaø „ phuïc hoài traïng thaùi: Available := Available + Request i Allocation i := Allocation i ‟ Request i Need i := Need i + Request i Khoa KTMT 220 Giaûi thuaät kieåm tra traïng thaùi an toaøn – Ví duï  Coù 5 process P 0 ,, P 4  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 T 0 Allocation Max Available Need A B C A B C A B C A B C P 0 0 1 0 7 5 3 3 3 2 7 4 3 P 1 2 0 0 3 2 2 1 2 2 P 2 3 0 2 9 0 2 6 0 0 P 3 2 1 1 2 2 2 0 1 1 P 4 0 0 2 4 3 3 4 3 1      Khoa KTMT 221 GT (kieåm tra traïng thaùi)an toaøn – Vd (tt) Allocation Need Work 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 <P 1 , P 3 , P 4 , P 2 , P 0 > 7 4 3 7 4 5 10 4 7 10 5 7 5 3 2 P1 P3 P4 P2 Khoa KTMT 222 GT caáp phaùt taøi nguyeân – Ví duï  Yeâu caàu (1, 0, 2) cuûa P 1 coù thoûa ñöôïc khoâng? ‟ Kieåm tra ñieàu kieän Request 1  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ø <P 1 , P 3 , P 4 , P 0 , P 2 >), vaäy coù theå caáp phaùt taøi nguyeân cho P 1 . Allocation Need Available A B C A B C A B C P 0 0 1 0 7 4 3 2 3 0 P 1 3 0 2 0 2 0 P 2 3 0 2 6 0 0 P 3 2 1 1 0 1 1 P 4 0 0 2 4 3 1 P4 (3, 3, 0) ? P0 (0, 2, 0) ? P3 (0, 2, 1)? Khoa KTMT 223 3. Phaùt hieän deadlock (Deadlock detection)  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å Khoa KTMT 224 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öø P i ñeán P j  P i ñang chôø taøi nguyeân töø P j  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 P2 P1 P3 P5 R2 R5 P4 P2 P1 P3 P5 P4 Khoa KTMT 225 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 Khoa KTMT 226 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 Allocation i  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ø Request i  Work „ Neáu khoâng toàn taïi i nhö theá, ñeán böôùc 4. 3. Work := Work + Allocation i 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ì P i bò deadlocked. thôøi gian chaïy cuûa giaûi thuaät O(m·n2) Khoa KTMT 227 Giaûi thuaät phaùt hieän deadlock – Ví duï  Heä thoáng coù 5 quaù trình P 0 ,, P 4 „ 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 P 0 0 1 0 0 0 0 0 0 0 P 1 2 0 0 2 0 2 P 2 3 0 3 0 0 0 P 3 2 1 1 1 0 0 P 4 0 0 2 0 0 2 Chaïy giaûi thuaät, tìm ñöôïc chuoãi <P 0 , P 2 , P 3 , P 1 , P 4 > vôùi Finish[ i ] = true, i = 1,, n, vaäy heä thoáng khoâng bò deadlocked. Khoa KTMT 228 Giaûi thuaät phaùt hieän deadlock – Ví duï (tt)  P 2 yeâu caàu theâm moät instance cuûa C. Ma traän Request nhö sau: Request A B C P 0 0 0 0 P 1 2 0 2 P 2 0 0 1 P 3 1 0 0 P 4 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 P 0 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 P 1 , P 2 , P 3 , vaø P 4 . Khoa KTMT 229 Phuïc hoài deadlock (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 Khoa KTMT 230 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, hoaëc ‟ 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å choïn process caàn ñöôïc chaám döùt? ‟ Ñ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 process caàn ñöôïc chaám döùt ‟ Process laø interactive process hay batch process Khoa KTMT 231 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,...) ‟ Trôû laïi traïng thaùi tröôùc deadlock (Rollback): rollback process bò laáy laïi taøi nguyeân trôû veà traïng thaùi safe, tieáp tuïc 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. ‟ Ñoùi taøi nguyeân (Starvation): ñeå traùnh 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. Khoa KTMT 232 Phöông phaùp keát hôïp ñeå giaûi quyeát Deadlock  Keát hôïp 3 phöông phaùp cô baûn  Ngaên chaën (Prevention)  Traùnh (Avoidance)  Phaùt hieän (Detection) Cho pheùp söû duïng caùch giaûi quyeát toái öu cho moãi lôùp taøi nguyeân trong heä thoáng.  Phaân chia taøi nguyeân thaønh caùc lôùp theo thöù baäc. ‟ Söû duïng kyõ thuaät thích hôïp nhaát cho vieäc quaûn lyù deadlock trong moãi lôùp naøy. Khoa KTMT 233 Baøi taäp  Baøi 01: Lieät keâ 3 tröôøng hôïp xaûy ra deadlock trong ñôøi soáng  Baøi 02: R1 R3 P1 P2 P3 R2 R4 Deadlock ? Khoa KTMT 234 Baøi taäp  Baøi 03:  A) Tìm Need  B) Heä thoáng coù an toaøn khoâng  C)Neáu P 1 yeâu caàu (0,4,2,0) thì coù theå caáp phaùt cho noù ngay khoâng? Khoa KTMT 235 Chöông 7. Quaûn lyù boä nhôù  Khaùi nieäm cô sôû  Caùc kieåu ñòa chæ nhôù (physical address , logical address)  Chuyeån ñoåi ñòa chæ nhôù  Overlay vaø swapping  Moâ hình quaûn lyù boä nhôù ñôn giaûn ‟ Fixed partitioning ‟ Dynamic partitioning ‟ Cô cheá phaân trang (paging) ‟ Cô cheá phaân ñoaïn (segmentation) ‟ Segmentation with paging Khoa KTMT 236 Khaùi nieäm cô sôû  Chöông trình phaûi ñöôïc mang vaøo trong boä nhôù vaø ñaët noù trong moät tieán trình ñeå ñöôïc xöû lyù  Input Queue ‟ Moät taäp hôïp cuûa nhöõng tieán trình treân ñóa maø ñang chôø ñeå ñöôïc mang vaøo trong boä nhôù ñeå thöïc thi.  User programs traûi qua nhieàu böôùc tröôùc khi ñöôïc xöû lyù. Khoa KTMT 237 Khaùi nieäm cô sôû  Quaûn lyù boä nhôù laø coâng vieäc cuûa heä ñieàu haønh vôùi söï hoã trôï cuûa phaàn cöùng nhaèm phaân phoái, saép xeáp caùc process trong boä nhôù sao cho hieäu quaû.  Muïc tieâu caàn ñaït ñöôïc laø naïp caøng nhieàu process vaøo boä nhôù caøng toát (gia taêng möùc ñoä ña chöông)  Trong haàu heát caùc heä thoáng, kernel seõ chieám moät phaàn coá ñònh cuûa boä nhôù; phaàn coøn laïi phaân phoái cho caùc process.  Caùc yeâu caàu ñoái vôùi vieäc quaûn lyù boä nhôù ‟ Caáp phaùt boä nhôù cho caùc process ‟ Taùi ñònh vò (relocation): khi swapping, ‟ Baûo veä: phaûi kieåm tra truy xuaát boä nhôù coù hôïp leä khoâng ‟ Chia seû: cho pheùp caùc process chia seû vuøng nhôù chung ‟ Keát gaùn ñòa chæ nhôù luaän lyù cuûa user vaøo ñòa chæ thöïc Khoa KTMT 238 Caùc kieåu ñòa chæ nhôù  Ñòa chæ vaät lyù (physical address) (ñòa chæ thöïc) laø moät vò trí thöïc trong boä nhôù chính.  Ñòa chæ luaän lyù (logical address) laø moät vò trí nhôù ñöôïc dieãn taû trong moät chöông trình ( coøn goïi laø ñòa chæ aûo virtual address) ‟ Caùc trình bieân dòch (compiler) taïo ra maõ leänh chöông trình maø trong ñoù moïi tham chieáu boä nhôù ñeàu laø ñòa chæ luaän lyù ‟ Ñòa chæ töông ñoái (relative address) (ñòa chæ khaû taùi ñònh vò, relocatable address) laø moät kieåu ñòa chæ luaän lyù trong ñoù caùc ñòa chæ ñöôïc bieåu dieãn töông ñoái so vôùi moät vò trí xaùc ñònh naøo ñoù trong chöông trình.  Ví duï: 12 byte so vôùi vò trí baét ñaàu chöông trình, ‟ Ñòa chæ tuyeät ñoái (absolute address): ñòa chæ töông ñöông vôùi ñòa chæ thöïc. Khoa KTMT 239 Naïp chöông trình vaøo boä nhôù  Boä linker: keát hôïp caùc object module thaønh moät file nhò phaân khaû thöïc thi goïi laø load module.  Boä loader: naïp load module vaøo boä nhôù chính System library System library static linking dynamic linking Khoa KTMT 240 Cô cheá thöïc hieän linking Module A CALL B Return length L Module B CALL C Return length M Module C Return length N 0 L  1 Module A JMP “L” Return Module B JMP “L+M” Return Module C Return L L  M  1 L  M L  M  N  1 relocatable object modules load module 0 L  1 0 M  1 0 N  1 Khoa KTMT 241 Chuyeån ñoåi ñòa chæ  Chuyeån ñoåi ñòa chæ: quaù trình aùnh xaï moät ñòa chæ töø khoâng gian ñòa chæ naøy sang khoâng gian ñòa chæ khaùc.  Bieåu dieãn ñòa chæ nhôù ‟ Trong source code: symbolic (caùc bieán, haèng, pointer,) ‟ Thôøi ñieåm bieân dòch: thöôøng laø ñòa chæ khaû taùi ñònh vò  Ví duï: a ôû vò trí 14 bytes so vôùi vò trí baét ñaàu cuûa module. ‟ Thôøi ñieåm linking/loading: coù theå laø ñòa chæ thöïc. Ví duï: döõ lieäu naèm taïi ñòa chæ boä nhôù thöïc 2030 0 250 2000 2250 relocatable address physical memory symbolic address int i; goto p1; p1 Khoa KTMT 242 Chuyeån ñoåi ñòa chæ (tt)  Ñòa chæ leänh (instruction) vaø döõ lieäu (data) ñöôïc chuyeån ñoåi thaønh ñòa chæ thöïc coù theå xaûy ra taïi ba thôøi ñieåm khaùc nhau ‟ Compile time: neáu bieát tröôùc ñòa chæ boä nhôù cuûa chöông trình thì coù theå keát gaùn ñòa chæ tuyeät ñoái luùc bieân dòch.  Ví duï: chöông trình .COM cuûa MS-DOS  Khuyeát ñieåm: phaûi bieân dòch laïi neáu thay ñoåi ñòa chæ naïp chöông trình ‟ Load time: Vaøo thôøi ñieåm loading, loader phaûi chuyeån ñoåi ñòa chæ khaû taùi ñònh vò thaønh ñòa chæ thöïc döïa treân moät ñòa chæ neàn (base address).  Ñòa chæ thöïc ñöôïc tính toaùn vaøo thôøi ñieåm naïp chöông trình  phaûi tieán haønh reload neáu ñòa chæ neàn thay ñoåi. Khoa KTMT 243 Sinh ñòa chæ tuyeät ñoái vaøo thôøi ñieåm dòch Symbolic addresses PROGRAM JUMP i LOAD j DATA i j Source code Absolute addresses 1024 JUMP 1424 LOAD 2224 1424 2224 Absolute load module Compile Link/Load Physical memory addresses 1024 JUMP 1424 LOAD 2224 1424 2224 Process image Khoa KTMT 244 Sinh ñòa chæ thöïc vaøo thôøi ñieåm naïp Relative (relocatable) addresses 0 JUMP 400 LOAD 1200 400 1200 Relative load module Symbolic addresses PROGRAM JUMP i LOAD j DATA i j Source code Compile Link/Load Physical memory addresses 1024 JUMP 1424 LOAD 2224 1424 2224 Process image Khoa KTMT 245 Chuyeån ñoåi ñòa chæ (tt)  Execution time: khi trong quaù trình thöïc thi, process coù theå ñöôïc di chuyeån töø segment naøy sang segment khaùc trong boä nhôù thì quaù trình chuyeån ñoåi ñòa chæ ñöôïc trì hoaõn ñeán thôøi ñieåm thöïc thi ‟ Caàn söï hoã trôï cuûa phaàn cöùng cho vieäc aùnh xaï ñòa chæ.  Ví duï: tröôøng hôïp ñòa chæ luaän lyù laø relocatable thì coù theå duøng thanh ghi base vaø limit, ‟ Söû duïng trong ña soá caùc OS ña duïng (general-purpose) trong ñoù coù caùc cô cheá swapping, paging, segmentation Relative (relocatable) addresses 0 JUMP 400 LOAD 1200 400 1200 MAX = 2000 Khoa KTMT 246 Khoâng gian ñòa chæ  Ñòa chæ ñöôïc taïo bôûi CPU ‟ Ñòa chæ logic (logical address). Taäp hôïp ñòa chæ logic goïi laø khoâng gian ñòa chæ logic  Ñòa chæ naïp vaøo MAR ‟ ñòa chæ vaät lyù (physical address). Taäp hôïp ñòa chæ vaät lyù goïi laø khoâng gian ñòa chæ vaät lyù  compile-time and load-time: ‟ Ñòa chæ Logical vaø physical laø xaùc ñònh  Taïi thôøi ñieåm thöïc thi: ñòa chæ logic khaùc vaät lyù, thöôøng goïi laø ñòa chæ aûo  Vieäc aùnh xaï giöõa hai ñòa chæ ñöôïc thöïc thi bôûi Memory Management Unit (MMU) Khoa KTMT 247 MMU Taùi ñònh vò söû duïng relocation register memory CPU relocation register + logical address 642 physical address 7642 7000 Khoa KTMT 248 Lieân keát ñoäng(Dynamic linking)  Quaù trình link ñeán moät module ngoaøi (external module) ñöôïc thöïc hieän sau khi ñaõ taïo xong load module (i.e. file coù theå thöïc thi, executable) ‟ Ví duï trong Windows: module ngoaøi laø caùc file .DLL coøn trong Unix, caùc module ngoaøi laø caùc file .so (shared library)  Load module chöùa caùc stub tham chieáu (refer) ñeán routine cuûa external module. ‟ Luùc thöïc thi, khi stub ñöôïc thöïc thi laàn ñaàu (do process goïi routine laàn ñaàu), stub naïp routine vaøo boä nhôù, töï thay theá baèng ñòa chæ cuûa routine vaø routine ñöôïc thöïc thi. ‟ Caùc laàn goïi routine sau seõ xaûy ra bình thöôøng  Stub caàn söï hoã trôï cuûa OS (nhö kieåm tra xem routine ñaõ ñöôïc naïp vaøo boä nhôù chöa). Khoa KTMT 249 Öu ñieåm cuûa dynamic linking  Thoâng thöôøng, external module laø moät thö vieän cung caáp caùc tieän ích cuûa OS. Caùc chöông trình thöïc thi coù theå duøng caùc phieân baûn khaùc nhau cuûa external module maø khoâng caàn söûa ñoåi, bieân dòch laïi.  Chia seû maõ (code sharing): moät external module chæ caàn naïp vaøo boä nhôù moät laàn. Caùc process caàn duøng external module naøy thì cuøng chia seû ñoaïn maõ cuûa external module  tieát kieäm khoâng gian nhôù vaø ñóa.  Phöông phaùp dynamic linking caàn söï hoã trôï cuûa OS trong vieäc kieåm tra xem moät thuû tuïc naøo ñoù coù theå ñöôïc chia seû giöõa caùc process hay laø phaàn maõ cuûa rieâng moät process (bôûi vì chæ coù OS môùi coù quyeàn thöïc hieän vieäc kieåm tra naøy). Khoa KTMT 250 Naïp ñoäng(Dynamic loading)  Cô cheá: chæ khi naøo caàn ñöôïc goïi ñeán thì moät thuû tuïc môùi ñöôïc naïp vaøo boä nhôù chính  taêng ñoä hieäu duïng cuûa boä nhôù (memory utilization) bôûi vì caùc thuû tuïc khoâng ñöôïc goïi ñeán seõ khoâng chieám choã trong boä nhôù  Raát hieäu quaû trong tröôøng hôïp toàn taïi khoái löôïng lôùn maõ chöông trình coù taàn suaát söû duïng thaáp, khoâng ñöôïc söû duïng thöôøng xuyeân (ví duï caùc thuû tuïc xöû lyù loãi)  Hoã trôï töø heä ñieàu haønh ‟ Thoâng thöôøng, user chòu traùch nhieäm thieát keá vaø hieän thöïc caùc chöông trình coù dynamic loading. ‟ Heä ñieàu haønh chuû yeáu cung caáp moät soá thuû tuïc thö vieän hoã trôï, taïo ñieàu kieän deã daøng hôn cho laäp trình vieân. Khoa KTMT 251 Cô cheá phuû laép (overlay)  Taïi moãi thôøi ñieåm, chæ giöõ laïi trong boä nhôù nhöõng leänh hoaëc döõ lieäu caàn thieát, giaûi phoùng caùc leänh/döõ lieäu chöa hoaëc khoâng caàn duøng ñeán.  Cô cheá naøy raát höõu duïng khi kích thöôùc moät process lôùn hôn khoâng gian boä nhôù caáp cho process ñoù.  Cô cheá naøy ñöôïc ñieàu khieån bôûi ngöôøi söû duïng (thoâng qua söï hoã trôï cuûa caùc thö vieän laäp trình) chöù khoâng caàn söï hoã trôï cuûa heä ñieàu haønh Khoa KTMT 252 Pass 1 70K Pass 2 80K Symbol table 20K Common routines 30K Assembler Total memory available = 150KB Cô cheá overlay (tt) symbol table 20K common routines 30K overlay driver 10K pass 1 pass 2 80K 70K Ñôn vò: byte naïp vaø thöïc thi Khoa KTMT 253 Cô cheá hoaùn vò (swapping)  Moät process coù theå taïm thôøi bò swap ra khoûi boä nhôù chính vaø löu treân moät heä thoáng löu tröõ phuï. Sau ñoù, process coù theå ñöôïc naïp laïi vaøo boä nhôù ñeå tieáp tuïc quaù trình thöïc thi. Swapping policy: hai ví duï ‟ Round-robin: swap out P 1 (vöøa tieâu thuï heát quantum cuûa noù), swap in P 2 , thöïc thi P 3 , ‟ Roll out, roll in: duøng trong cô cheá ñònh thôøi theo ñoä öu tieân (priority-based scheduling)  Process coù ñoä öu tieân thaáp hôn seõ bò swap out nhöôøng choã cho process coù ñoä öu tieân cao hôn môùi ñeán ñöôïc naïp vaøo boä nhôù ñeå thöïc thi  Hieän nay, ít heä thoáng söû duïng cô cheá swapping treân Khoa KTMT 254 Minh hoïa cô cheá swapping Khoa KTMT 255 Moâ hình quaûn lyù boä nhôù  Trong chöông naøy, moâ hình quaûn lyù boä nhôù laø moät moâ hình ñôn giaûn, khoâng coù boä nhôù aûo.  Moät process phaûi ñöôïc naïp hoaøn toaøn vaøo boä nhôù thì môùi ñöôïc thöïc thi (ngoaïi tröø khi söû duïng cô cheá overlay).  Caùc cô cheá quaûn lyù boä nhôù sau ñaây raát ít (haàu nhö khoâng coøn) ñöôïc duøng trong caùc heä thoáng hieän ñaïi ‟ Phaân chia coá ñònh (fixed partitioning) ‟ Phaân chia ñoäng (dynamic partitioning) ‟ Phaân trang ñôn giaûn (simple paging) ‟ Phaân ñoaïn ñôn giaûn (simple segmentation) Khoa KTMT 256 Phaân maûnh (fragmentation)  Phaân maûnh ngoaïi (external fragmentation) ‟ Kích thöôùc khoâng gian nhôù coøn troáng ñuû ñeå thoûa maõn moät yeâu caàu caáp phaùt, tuy nhieân khoâng gian nhôù naøy khoâng lieân tuïc  coù theå duøng cô cheá keát khoái (compaction) ñeå gom laïi thaønh vuøng nhôù lieân tuïc.  Phaân maûnh noäi (internal fragmentation) ‟ Kích thöôùc vuøng nhôù ñöôïc caáp phaùt coù theå hôi lôùn hôn vuøng nhôù yeâu caàu.  Ví duï: caáp moät khoaûng troáng 18,464 bytes cho moät process yeâu caàu 18,462 bytes. ‟ Hieän töôïng phaân maûnh noäi thöôøng xaûy ra khi boä nhôù thöïc ñöôïc chia thaønh caùc khoái kích thöôùc coá ñònh (fixed-sized block) vaø caùc process ñöôïc caáp phaùt theo ñôn vò khoái. Ví duï: cô cheá phaân trang (paging). Khoa KTMT 257 Phaân maûnh noäi operating system (used) yeâu caàu keá tieáp laø 18,462 bytes !!! hole kích thöôùc 18,464 bytes caàn quaûn lyù khoaûng troáng 2 bytes !?! OS seõ caáp phaùt haún khoái 18,464 bytes cho process  dö ra 2 bytes khoâng duøng! Khoa KTMT 258 Fixed partitioning  Khi khôûi ñoäng heä thoáng, boä nhôù chính ñöôïc chia thaønh nhieàu phaàn rôøi nhau goïi laø caùc partition coù kích thöôùc baèng nhau hoaëc khaùc nhau  Process naøo coù kích thöôùc nhoû hôn hoaëc baèng kích thöôùc partition thì coù theå ñöôïc naïp vaøo partition ñoù.  Neáu chöông trình coù kích thöôùc lôùn hôn partition thì phaûi duøng cô cheá overlay.  Nhaän xeùt ‟ Khoâng hieäu quaû do bò phaân maûnh noäi: moät chöông trình duø lôùn hay nhoû ñeàu ñöôïc caáp phaùt troïn moät partition. Khoa KTMT 259 Chieán löôïc placement (tt)  Partition coù kích thöôùc baèng nhau ‟ Neáu coøn partition troáng  process môùi seõ ñöôïc naïp vaøo partition ñoù ‟ Neáu khoâng coøn partition troáng, nhöng trong ñoù coù process ñang bò blocked  swap process ñoù ra boä nhôù phuï nhöôøng choã cho process môùi.  Partition coù kích thöôùc khoâng baèng nhau: giaûi phaùp 1 ‟ Gaùn moãi process vaøo partition nhoû nhaát phuø hôïp vôùi noù ‟ Coù haøng ñôïi cho moãi partition ‟ Giaûm thieåu phaân maûnh noäi ‟ Vaán ñeà: coù theå coù moät soá haøng ñôïi troáng khoâng (vì khoâng coù process vôùi kích thöôùc töông öùng) vaø haøng ñôïi daøy ñaëc Khoa KTMT 260 Chieán löôïc placement (tt)  Partition coù kích thöôùc khoâng baèng nhau: giaûi phaùp 2 ‟ Chæ coù moät haøng ñôïi chung cho moïi partition ‟ Khi caàn naïp moät process vaøo boä nhôù chính  choïn partition nhoû nhaát coøn troáng Khoa KTMT 261 Dynamic partitioning  Soá löôïng partition khoâng coá ñònh vaø partition coù theå coù kích thöôùc khaùc nhau  Moãi process ñöôïc caáp phaùt chính xaùc dung löôïng boä nhôù caàn thieát  Gaây ra hieän töôïng phaân maûnh ngoaïi Khoa KTMT 262 Chieán löôïc placement  Duøng ñeå quyeát ñònh caáp phaùt khoái boä nhôù troáng naøo cho moät process  Muïc tieâu: giaûm chi phí compaction  Caùc chieán löôïc placement ‟ Best-fit: choïn khoái nhôù troáng nhoû nhaát ‟ First-fit: choïn khoái nhôù troáng phuø hôïp ñaàu tieân keå töø ñaàu boä nhôù ‟ Next-fit: choïn khoái nhôù troáng phuø hôïp ñaàu tieân keå töø vò trí caáp phaùt cuoái cuøng ‟ Worst-fit: choïn khoái nhôù troáng lôùn nhaát Bài Tập  Giả sử bộ nhớ chính được phân thành các phân vùng có kích thước là 600K, 500K, 200K, 300K ( theo thứ tự ), cho biết các tiến trình có kích thước 212K, 417K, 112K và 426K ( theo thứ tự ) sẽ được cấp phát bộ nhớ như thế nào, nếu sử dụng : a) Thuật toán First fit b) Thuật toán Best fit c) Thuật toán Worst fit d) Thuật toán Next fit Thuật toán nào cho phép sử dụng bộ nhớ hiệu qủa nhất trong trường hợp trên ? Khoa KTMT 263 Khoa KTMT 264 Caáp phaùt khoâng lieân tuïc 1.Cô cheá phaân trang (paging) Boä nhôù vaät lyù khung trang (frame). ‟ Kích thöôùc cuûa frame laø luõy thöøa cuûa 2, töø khoaûng 512 byte ñeán 16MB.  Boä nhôù luaän lyù (logical memory) hay khoâng gian ñòa chæ luaän lyù laø taäp moïi ñòa chæ luaän lyù maø moät chöông trình baát kyø coù theå sinh ra  page. ‟ Ví duï „ MOV REG,1000 //1000 laø moät ñòa chæ luaän lyù  Baûng phaân trang (page table) ñeå aùnh xaï ñòa chæ luaän lyù thaønh ñòa chæ thöïc Khoa KTMT 265 1.Cô cheá phaân trang (tt) logical memory 1 4 3 5 0 1 2 3 page table page 0 page 2 physical memory frame number 0 1 2 3 page 1 4 5 page 3 page number 0 1 2 3 Khoa KTMT 266 1.Cô cheá phaân trang (tt) A) Chuyeån ñoåi ñòa chæ trong paging ‟ Ñòa chæ luaän lyù goàm coù:  Soá hieäu trang (Page number) p  Ñòa chæ töông ñoái trong trang (Page offset) d ‟ Neáu kích thöôùc cuûa khoâng gian ñòa chæ luaän lyù laø 2m, vaø kích thöôùc cuûa trang laø 2 n (ñôn vò laø byte hay word tuøy theo kieán truùc maùy) thì Baûng phaân trang seõ coù toång coäng 2 m /2 n = 2 m  n muïc (entry) p d page number page offset m  n bits (ñònh vò töø 0  2m  n  1) n bits (ñònh vò töø 0  2n  1) Khoa KTMT 267 1.Cô cheá phaân trang (tt) CPU p d f d f p page table logical address physical address physical memory f 0000 f 1111 f frames A) Chuyeån ñoåi ñòa chæ trong paging Khoa KTMT 268 1.Cô cheá phaân trang (tt) Ví duï: Chuyeån ñoåi ñòa chæ nhôù trong paging Ví dụ Xét một không gian địa chỉ có 8 trang, mỗi trang có kích thước 1KB. ánh xạ vào bộ nhớ vật lý có 32 khung trang a) Địa chỉ logic gồm bao nhiêu bit ? b) Địa chỉ physic gồm bao nhiêu bit ? c) Bảng trang có bao nhiêu mục?Mỗi mục trong bảng trang cần bao nhiêu bit? Khoa KTMT 269 Khoa KTMT 270 1.Cô cheá phaân trang (tt) Tröôùc khi vaø sau khi caáp phaùt cho Process môùi Khoa KTMT 271 B) Caøi ñaët baûng trang (Paging hardware)  Baûng phaân trang thöôøng ñöôïc löu giöõ trong boä nhôù chính ‟ Moãi process ñöôïc heä ñieàu haønh caáp moät baûng phaân trang ‟ Thanh ghi page-table base (PTBR) troû ñeán baûng phaân trang ‟ Thanh ghi page-table length (PTLR) bieåu thò kích thöôùc cuûa baûng phaân trang (coù theå ñöôïc duøng trong cô cheá baûo veä boä nhôù)  Thöôøng duøng moät boä phaän cache phaàn cöùng coù toác ñoä truy xuaát vaø tìm kieám cao, goïi laø thanh ghi keát hôïp (associative register) hoaëc translation look-aside buffers (TLBs) Khoa KTMT 272 B) Caøi ñaët baûng trang (Paging hardware)  Duøng thanh ghi Page-Table Base Register (PTBR) p Khoa KTMT 273 Paging hardware vôùi TLB Khoa KTMT 274 C) Effective access time (EAT) „ Tính thôøi gian truy xuaát hieäu duïng (effective access time, EAT)  Thôøi gian tìm kieám trong TLB (associative lookup):   Thôøi gian moät chu kyø truy xuaát boä nhôù: x  Hit ratio: tæ soá giöõa soá laàn chæ soá trang ñöôïc tìm thaáy (hit) trong TLB vaø soá laàn truy xuaát khôûi nguoàn töø CPU ‟ Kí hieäu hit ratio:   Thôøi gian caàn thieát ñeå coù ñöôïc chæ soá frame ‟ Khi chæ soá trang coù trong TLB (hit)  + x ‟ Khi chæ soá trang khoâng coù trong TLB (miss)  + x + x  Thôøi gian truy xuaát hieäu duïng EAT = ( + x) + ( + 2x)(1 ‟ ) = (2 ‟ )x +  Khoa KTMT 275 C) Effective access time (EAT)  Ví duï 1: ñôn vò thôøi gian nano giaây  Associative lookup = 20  Memory access = 100  Hit ratio = 0.8  EAT = (100 + 20)  0.8 + (200 + 20)  0.2 = 1.2  100 + 20 = 140  Ví duï 2  Associative lookup = 20  Memory access = 100  Hit ratio = 0.98  EAT = (100 + 20)  0.98 + (200 + 20)  0.02 = 1.02  100 + 20 = 122 Ví dụ Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính. a) Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 200nanoseconds, thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ? b) Nếu sử dụng TLBs với hit-ratio ( tỉ lệ tìm thấy) là 75%, thời gian để tìm trong TLBs xem như bằng 0, tính thời gian truy xuất bộ nhớ trong hệ thống ( effective memory reference time) Khoa KTMT 276 Khoa KTMT 277 D) Toå chöùc baûng trang - Phaân trang ña caáp  Caùc heä thoáng hieän ñaïi ñeàu hoã trôï khoâng gian ñòa chæ aûo raát lôùn (2 32 ñeán 2 64 ), ôû ñaây giaû söû laø 2 32 ‟ Giaû söû kích thöôùc trang nhôù laø 4KB (= 212)  baûng phaân trang seõ coù 232/212 = 220 = 1M muïc. ‟ Giaû söû moãi muïc goàm 4 byte thì moãi process caàn 4MB cho baûng phaân trang  VD: Phaân trang hai caáp P2 d Soá trang Ñoä dôøi trang P1 10 bit 10 bit 12 Phân trang đa cấp (tt) Khoa KTMT 278 Khoa KTMT 279 D) Toå chöùc baûng trang Phaân trang ña caáp Khoa KTMT 280 D) Toå chöùc baûng trang  Baûng trang nghòch ñaûo: söû duïng cho taát caû caùc Process i Khoa KTMT 281 E) Baûo veä boä nhôù  Vieäc baûo veä boä nhôù ñöôïc hieän thöïc baèng caùch gaén vôùi frame caùc bit baûo veä (protection bits) ñöôïc giöõ trong baûng phaân trang. Caùc bit naøy bieåu thò caùc thuoäc tính sau ‟ read-only, read-write, execute-only  Ngoaøi ra, coøn coù moät valid/invalid bit gaén vôùi moãi muïc trong baûng phaân trang ‟ “valid”: cho bieát laø trang cuûa process, do ñoù laø moät trang hôïp leä. ‟ “invalid”: cho bieát laø trang khoâng cuûa process, do ñoù laø moät trang baát hôïp leä. Khoa KTMT 282 Baûo veä baèng valid/invalid bit  Moãi trang nhôù coù kích thöôùc 2K = 2048  Process coù kích thöôùc 10,468  phaân maûnh noäi ôû frame 9 (chöùa page 5), caùc ñòa chæ aûo > 12287 laø caùc ñòa chæ invalid.  Duøng PTLR ñeå kieåm tra truy xuaát ñeán baûng phaân trang coù naèm trong baûng hay khoâng. 00000 10468 12287 2 v 3 v 4 v 7 v 8 v 9 v 0 i 0 i frame number valid/ invalid bit 0 1 2 3 4 5 6 7 0 1 2 page 0 3 page 1 4 page 2 5 6 7 page 3 8 page 4 9 page 5 ... page n 16383 14 bit Khoa KTMT 283 F) Chia seû caùc trang nhôù Process 1 ed 1 ed 2 ed 3 data 1 ed 1 ed 2 ed 2 data 3 Process 3 3 4 6 2 0 1 2 3 3 4 6 1 0 1 2 3 Process 2 ed 1 ed 2 ed 3 data 2 3 4 6 7 0 1 2 3 0 1 data 1 2 data 3 3 ed 1 4 ed 2 5 6 ed 3 7 data 2 8 9 10 Boä nhôù thöïc Khoa KTMT 284 2.Phaân ñoaïn (segmentation)  Nhìn laïi cô cheá phaân trang ‟ user view (khoâng gian ñòa chæ aûo) taùch bieät vôùi khoâng gian boä nhôù thöïc. Cô cheá phaân trang thöïc hieän pheùp aùnh xaï user-view vaøo boä nhôù thöïc.  Trong thöïc teá, döôùi goùc nhìn cuûa user, moät chöông trình caáu thaønh töø nhieàu ñoaïn (segment). Moãi ñoaïn laø moät ñôn vò luaän lyù cuûa chöông trình, nhö ‟ main program, procedure, function ‟ local variables, global variables, common block, stack, symbol table, arrays, Khoa KTMT 285 User view cuûa moät chöông trình  Thoâng thöôøng, moät chöông trình ñöôïc bieân dòch. Trình bieân dòch seõ töï ñoäng xaây döïng caùc segment.  Ví duï, trình bieân dòch Pascal seõ taïo ra caùc segment sau: ‟ Global variables ‟ Procedure call stack ‟ Procedure/function code ‟ Local variable  Trình loader seõ gaùn moãi segment moät soá ñònh danh rieâng. procedure stack symbol table function sqrt main program Logical address space Khoa KTMT 286 Phaân ñoaïn  Duøng cô cheá phaân ñoaïn ñeå quaûn lyù boä nhôù coù hoã trôï user view ‟ Khoâng gian ñòa chæ aûo laø moät taäp caùc ñoaïn, moãi ñoaïn coù teân vaø kích thöôùc rieâng. ‟ Moät ñòa chæ luaän lyù ñöôïc ñònh vò baèng teân ñoaïn vaø ñoä dôøi (offset) beân trong ñoaïn ñoù (so saùnh vôùi phaân trang!) Khoa KTMT 287 Phaân ñoaïn (tt) logical address space physical memory space segment 1 segment 2 segment 3 segment 4 Khoa KTMT 288 Caøi ñaët phaân ñoaïn  Ñòa chæ luaän lyù laø moät caëp giaù trò (segment number, offset)  Baûng phaân ñoaïn (segment table): goàm nhieàu muïc, moãi muïc chöùa ‟ base, chöùa ñòa chæ khôûi ñaàu cuûa segment trong boä nhôù ‟ limit, xaùc ñònh kích thöôùc cuûa segment  Segment-table base register (STBR): troû ñeán vò trí baûng phaân ñoaïn trong boä nhôù  Segment-table length register (STLR): soá löôïng segment cuûa chöông trình  Moät chæ soá segment s laø hôïp leä neáu s < STLR Khoa KTMT 289 Moät ví duï veà phaân ñoaïn procedure stack symbol table function sqrt main program segment 0 segment 3 segment 1 segment 2 segment 4 procedure stack main symbol table function sqrt limit base 0 1000 1400 1 400 6300 2 400 4300 3 1100 3200 4 1000 4700 segment table logical address space physical memory space 1400 2400 3200 4300 4700 5700 6300 Khoa KTMT 290 Phaàn cöùng hoã trôï phaân ñoaïn CPU  + physical memory no trap; addressing error limit base s s d yes segment table Khoa KTMT 291 Chuyeån ñoåi ñòa chæ trong cô cheá phaân ñoaïn Ví duï Khoa KTMT 292 Chia seû caùc ñoaïn editor data 1 segment 0 segment 1 logical address space process P1 editor data 2 segment 0 segment 1 logical address space process P2 limit base 0 25286 43062 1 4425 68348 segment table process P1 limit base 0 25286 43062 1 8850 90003 segment table process P2 editor data 1 data 2 physical memory 43062 72773 68348 90003 98853 Khoa KTMT 293 3.Keát hôïp phaân trang vaø phaân ñoaïn  Keát hôïp phaân trang vaø phaân ñoaïn nhaèm keát hôïp caùc öu ñieåm ñoàng thôøi haïn cheá caùc khuyeát ñieåm cuûa phaân trang vaø phaân ñoaïn: ‟ Vaán ñeà cuûa phaân ñoaïn: Neáu moät ñoaïn quaù lôùn thì coù theå khoâng naïp noù ñöôïc vaøo boä nhôù. ‟ YÙ töôûng giaûi quyeát: paging ñoaïn, khi ñoù chæ caàn giöõ trong boä nhôù caùc page cuûa ñoaïn hieän ñang caàn. Logic Addr = Khoa KTMT 294 3.Keát hôïp phaân trang vaø phaân ñoaïn Khoa KTMT 295 3.Keát hôïp phaân trang vaø phaân ñoaïn Bài Tập  Xét một không gian có bộ nhớ luận lý kích thước 1 trang là 1KB. Tính số trang và độ dời (offset) của từng địa chỉ sau: a) 2.375 b) 19.366 c) 30.000 d) 256 e) 16.385 Khoa KTMT 296 Bài Tập  Xét một không gian có bộ nhớ luận lý có 64 trang, mỗi trang có 1024 từ, mỗi từ là 2 byte được ánh xạ vào bộ nhớ vật lý có 32 trang: a) Địa chỉ bộ nhớ vật lý có bao nhiêu bit? b) Địa chỉ bộ nhớ luận lý có bao nhiêu bit? c) Có bao nhiêu mục trong bảng phân trang? Mỗi mục chứa bao nhiêu bit? Khoa KTMT 297 Bài tập Xét một hệ thống sử dụng kỹ thuật phân trang, với bảng trang được lưu trữ trong bộ nhớ chính. a) Nếu thời gian cho một lần truy xuất bộ nhớ bình thường là 100 nanoseconds, thì mất bao nhiêu thời gian cho một thao tác truy xuất bộ nhớ trong hệ thống này ? b) Nếu sử dụng TLBs với hit-ratio ( tỉ lệ tìm thấy) là 85%, thời gian để tìm trong TLBs là 20 nanosecond, tính thời gian truy xuất bộ nhớ trong hệ thống ( effective memory reference time) Khoa KTMT 298 Bài tập Xét bảng phân đoạn sau đây : Cho biết địa chỉ vật lý tương ứng với các địa chỉ logic sau đây : a. 0,430 b. 1,100 c. 2,500 d. 3,400 e. 4,112 Khoa KTMT 299 Segment Base Length 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96 Chöông 8 Boä Nhôù AÛo Khoa KTMT 301 Noäi dung trình baøy  Toång quan veà boä nhôù aûo  Caøi ñaët boä nhôù aûo : demand paging  Caøi ñaët boä nhôù aûo : Page Replacement – Caùc giaûi thuaät thay trang (Page Replacement Algorithms)  Vaán ñeà caáp phaùt Frames  Vaán ñeà Thrashing  Caøi ñaët boä boä nhôù aûo : Demand Segmentation Khoa KTMT 302 1. Toång quan boä nhôù aûo  Nhaän xeùt: khoâng phaûi taát caû caùc phaàn cuûa moät process caàn thieát phaûi ñöôïc naïp vaøo boä nhôù chính taïi cuøng moät thôøi ñieåm „ Ví duï – Ñoaïn maõ ñieàu khieån caùc loãi hieám khi xaûy ra – Caùc arrays, list, tables ñöôïc caáp phaùt boä nhôù (caáp phaùt tónh) nhieàu hôn yeâu caàu thöïc söï – Moät soá tính naêng ít khi ñöôïc duøng cuûa moät chöông trình – Caû chöông trình thì cuõng coù ñoaïn code chöa caàn duøng  Boä nhôù aûo (virtual memory): Boä nhôù aûo laø moät kyõ thuaät cho pheùp xöû lyù moät tieán trình khoâng ñöôïc naïp toaøn boä vaøo boä nhôù vaät lyù Khoa KTMT 303 1. Boä nhôù aûo (tt) Öu ñieåm cuûa boä nhôù aûo – Soá löôïng process trong boä nhôù nhieàu hôn – Moät process coù theå thöïc thi ngay caû khi kích thöôùc cuûa noù lôùn hôn boä nhôù thöïc – Giaûm nheï coâng vieäc cuûa laäp trình vieân  Khoâng gian traùo ñoåi giöõa boä nhôù chính vaø boä nhôù phuï(swap space). „ Ví duï: – swap partition trong Linux – file pagefile.sys trong Windows Khoa KTMT 304 2. Caøi ñaët boä nhôù aûo  Coù hai kyõ thuaät: – Phaân trang theo yeâu caàu (Demand Paging) – Phaân ñoaïn theo yeâu caàu (Segmentation Paging)  Phaàn cöùng memory management phaûi hoã trôï paging vaø/hoaëc segmentation  OS phaûi quaûn lyù söï di chuyeån cuûa trang/ñoaïn giöõa boä nhôù chính vaø boä nhôù thöù caáp  Trong chöông naøy, – Chæ quan taâm ñeán paging – Phaàn cöùng hoã trôï hieän thöïc boä nhôù aûo – Caùc giaûi thuaät cuûa heä ñieàu haønh Khoa KTMT 305 2.1.Phaân trang theo yeâu caàu demand paging „ Demand paging: caùc trang cuûa quaù trình chæ ñöôïc naïp vaøo boä nhôù chính khi ñöôïc yeâu caàu.  Khi coù moät tham chieáu ñeán moät trang maø khoâng coù trong boä nhôù chính (valid bit) thì phaàn cöùng seõ gaây ra moät ngaét (goïi laø page-fault trap) kích khôûi page-fault service routine (PFSR) cuûa heä ñieàu haønh.  PFSR: 1. Chuyeån process veà traïng thaùi blocked 2. Phaùt ra moät yeâu caàu ñoïc ñóa ñeå naïp trang ñöôïc tham chieáu vaøo moät frame troáng; trong khi ñôïi I/O, moät process khaùc ñöôïc caáp CPU ñeå thöïc thi 3. Sau khi I/O hoaøn taát, ñóa gaây ra moät ngaét ñeán heä ñieàu haønh; PFSR caäp nhaät page table vaø chuyeån process veà traïng thaùi ready. Khoa KTMT 306 2.2. Loãi trang vaø caùc böôùc xöû lyù Khoa KTMT 307 2.3. Thay theá trang nhôù  Böôùc 2 cuûa PFSR giaû söû phaûi thay trang vì khoâng tìm ñöôïc frame troáng, PFSR ñöôïc boå sung nhö sau 1. Xaùc ñònh vò trí treân ñóa cuûa trang ñang caàn 2. Tìm moät frame troáng: a. Neáu coù frame troáng thì duøng noù b. Neáu khoâng coù frame troáng thì duøng moät giaûi thuaät thay trang ñeå choïn moät trang hy sinh (victim page) c. Ghi victim page leân ñóa; caäp nhaät page table vaø frame table töông öùng 3. Ñoïc trang ñang caàn vaøo frame troáng (ñaõ coù ñöôïc töø böôùc 2); caäp nhaät page table vaø frame table töông öùng. Khoa KTMT 308 2.3. Thay theá trang nhôù (tt) Khoa KTMT 309 2.4. Caùc thuaät toaùn thay theá trang „ Hai vaán ñeà chuû yeáu:  Frame-allocation algorithm – Caáp phaùt cho process bao nhieâu frame cuûa boä nhôù thöïc?  Page-replacement algorithm – Choïn frame cuûa process seõ ñöôïc thay theá trang nhôù – Muïc tieâu: soá löôïng page-fault nhoû nhaát – Ñöôïc ñaùnh giaù baèng caùch thöïc thi giaûi thuaät ñoái vôùi moät chuoãi tham chieáu boä nhôù (memory reference string) vaø xaùc ñònh soá laàn xaûy ra page fault  Ví duï „ Thöù töï tham chieáu caùc ñòa chæ nhôù, vôùi page size = 100: „ 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105  caùc trang nhôù sau ñöôïc tham chieáu laàn löôït = chuoãi tham chieáu boä nhôù (trang nhôù) „ 1, 4, 1, 6, 1, „ 1, 1, 1, 6, 1, „ 1, 1, 1, 6, 1, „ 1, 1, 1, 6, 1, „ 1 Khoa KTMT 310 a) Giaûi thuaät thay trang FIFO  Caùc döõ lieäu caàn bieát ban ñaàu: – Soá khung trang – Tình traïng ban ñaàu – Chuoãi tham chieáu – Trang nhớ cũ nhất sẽ được thay thế Bộ nhớ chính cấp cho process 3 frame Khoa KTMT 311 Nghòch lyù Belady Khoa KTMT 312 Nghòch lyù Belady Baát thöôøng (anomaly) Belady: soá page fault taêng maëc daàu quaù trình ñaõ ñöôïc caáp nhieàu frame hôn. Khoa KTMT 313 2.4 b)Giaûi thuaät thay trang OPT(optimal)  Giaûi thuaät thay trang OPT – Thay theá trang nhôù seõ ñöôïc tham chieáu treã nhaát trong töông lai – Khó hiện thực?  Ví duï: moät process coù 7 trang, vaø ñöôïc caáp 3 frame Khoa KTMT 314 c) Giaûi thuaät laâu nhaát chöa söû duïng Least Recently Used (LRU)  Ví duï:  Moãi trang ñöôïc ghi nhaän (trong baûng phaân trang) thôøi ñieåm ñöôïc tham chieáu  trang LRU laø trang nhôù coù thôøi ñieåm tham chieáu nhoû nhaát (OS toán chi phí tìm kieám trang nhôù LRU naøy moãi khi coù page fault)  Do vaäy, LRU caàn söï hoã trôï cuûa phaàn cöùng vaø chi phí cho vieäc tìm kieám. Ít CPU cung caáp ñuû söï hoã trôï phaàn cöùng cho giaûi thuaät LRU. Khoa KTMT 315 LRU vaø FIFO  So saùnh caùc giaûi thuaät thay trang LRU vaø FIFO chuoãi tham chieáu trang nhôù             Khoa KTMT 316 Giải thuật cơ hội thứ hai  Sử dụng các bit tham khảo tại những khoản thời gian đều đặn  Dùng một byte cho mỗi trang trong một bảng nằm trong bộ nhớ  Dùng một thanh ghi dịch chứa lịch sử tham khảo trong 8 lần gần nhất VD: 00110101, 00000000, 11111111  Là giải thuật thay thế FIFO, trước khi thay thế một trang xem xét bit tham khảo của nó  Đôi khi sử dụng hai bit: tham khảo và sửa đổi như một cặp (x,x): – (0,0) không được dùng mới đây và không được sửa đổi-là trang tốt nhất để thay thế. – (0,1) không được dùng mới đây nhưng được sửa đổi-không thật tốt vì trang cần được viết ra trước khi thay thế. – (1,0) được dùng mới đây nhưng không được sửa đổi-nó có thể sẽ nhanh chóng được dùng lại. – (1,1) được dùng mới đây và được sửa đổi-trang có thể sẽ nhanh chóng được dùng lại và trang sẽ cần được viết ra đĩa trước khi nó có thể được thay thế. Khoa KTMT 317 Giải thuật cơ hội thứ hai (tt) Khoa KTMT 318 2.5.Soá löôïng frame caáp cho process  OS phaûi quyeát ñònh caáp cho moãi process bao nhieâu frame. – Caáp ít frame  nhieàu page fault – Caáp nhieàu frame  giaûm möùc ñoä multiprogramming  Chieán löôïc caáp phaùt tónh (fixed-allocation) – Soá frame caáp cho moãi process khoâng ñoåi, ñöôïc xaùc ñònh vaøo thôøi ñieåm loading vaø coù theå tuøy thuoäc vaøo töøng öùng duïng (kích thöôùc cuûa noù,)  Chieán löôïc caáp phaùt ñoäng (variable-allocation) – Soá frame caáp cho moãi process coù theå thay ñoåi trong khi noù chaïy  Neáu tyû leä page-fault cao  caáp theâm frame  Neáu tyû leä page-fault thaáp  giaûm bôùt frame – OS phaûi maát chi phí ñeå öôùc ñònh caùc process Khoa KTMT 319 a) Chieán löôïc caáp phaùt tónh  Caáp phaùt baèng nhau: Ví duï, coù 100 frame vaø 5 process  moãi process ñöôïc 20 frame  Caáp phaùt theo tæ leä: döïa vaøo kích thöôùc process  Caáp phaùt theo ñoä öu tieân m S s pa m sS ps i ii i ii      for allocation frames ofnumber total process of size 5964 137 127 564 137 10 127 10 64 2 1 2      a a s s m i Ví duï: Khoa KTMT 320 Baøi taäp  Bài 01: Một máy tính 32-bit địa chỉ, sử dụng một bảng trang nhị cấp. Địa chỉ ảo được phân bổ như sau : 9 bit dành cho bảng trang cấp 1, 11 bit cho bảng trang cấp 2, và cho offset. Cho biết kích thước một trang trong hệ thống, và địa chỉ ảo có bao nhiêu trang ?  Bài 02: Xét chuỗi truy xuất bộ nhớ sau: 1, 2 , 3 , 4 , 3 , 5 , 1 , 6 , 2 , 1 , 2 , 3 , 7 , 5 , 3 , 2 , 1 , 2 , 3 , 6 Có bao nhiêu lỗi trang xảy ra khi sử dụng các thuật toán thay thế sau đây, giả sử có 4 khung trang và ban đầu các khung trang đều trống ? a) LRU b) FIFO c) Optimal d) Cơ hội thứ 2 Bài tập Cho một process có số frame truy cập như sau: 1,2,4,3,5,2,3,5,6,7,8,9,1,2,3,4,5,2,3,7,6,4, 5,6,7,9,8,1,2,5 Cho biết có biêu nhiêu tập làm việc (working set)? Liệt kê các frame trong từng working set? Biết  = 7. Khoa KTMT 321 Bài tập Hệ thống tại một thời điểm có 5 process: process 1 cần 5 frame, process 2 cần 15 frame, process 3 cần 10 frame, process 4 cần 9 frame, process 5 cần 11 frame. Hệ thống hiện có 30 frame. Tính xem mỗi process được cấp bao nhiêu frame? Phân bổ đều? Theo tỷ lệ? Khoa KTMT 322