Bài giảng môn Hệ điều hành (Operating Systems)

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ä