Giáo trình môn Hệ điều hành - Chương 7. Quản lý bộ nhớ

Khoa KTMT 1 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 2 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 3 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 4 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 5 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 6 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 7 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 8 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 9 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 10 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 11 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 12 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 13 MMU Taùi ñònh vò söû duïng relocation register memory CPU relocation register + logical address 642 physical address 7642 7000 Khoa KTMT 14 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 15 Ö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 16 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 17 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 18 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 19 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 20 Minh hoïa cô cheá swapping Khoa KTMT 21 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 22 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 23 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 24 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 25 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 26 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 27 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 28 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 29 Khoa KTMT 30 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 31 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 32 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 33 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 34 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) ng trang bao nhiêu c? i c trong ng trang n bao nhiêu bit? Khoa KTMT 35 Khoa KTMT 36 1.Cô cheá phaân trang (tt) Tröôùc khi vaø sau khi caáp phaùt cho Process môùi Khoa KTMT 37 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 38 B) Caøi ñaët baûng trang (Paging hardware)  Duøng thanh ghi Page-Table Base Register (PTBR) p Khoa KTMT 39 Paging hardware vôùi TLB Khoa KTMT 40 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 41 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 42 Khoa KTMT 43 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 44 Khoa KTMT 45 D) Toå chöùc baûng trang Phaân trang ña caáp Khoa KTMT 46 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 47 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 48 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 49 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 50 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 51 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 52 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 53 Phaân ñoaïn (tt) logical address space physical memory space segment 1 segment 2 segment 3 segment 4 Khoa KTMT 54 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 55 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 56 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 57 Chuyeån ñoåi ñòa chæ trong cô cheá phaân ñoaïn Ví duï Khoa KTMT 58 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 59 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 60 3.Keát hôïp phaân trang vaø phaân ñoaïn Khoa KTMT 61 3.Keát hôïp phaân trang vaø phaân ñoaïn Bài tập Xét một hệ thống với 30 bit địa chỉ logic. Nếu kích thước trang là 1K bytes thì kích thước bảng trang là bao nhiêu giả sử mỗi mục trong bảng trang chứa 4 bytes. Khoa KTMT 62 Bài tập  Cho bảng trang của tiến trình P1. – Địa chỉ ảo 2345 sẽ được chuyển thành địa chỉ vật lý bao nhiêu? – Địa chỉ vật lý 9876 sẽ được chuyển thành địa chỉ ảo bao nhiêu?  Biết rằng kích thước mỗi frame là 1K bytes Khoa KTMT 63 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à 100K, 400K, 200K, 300K và 500K ( 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 64 Bài tập  Cho bảng trang của tiến trình P1. – Địa chỉ ảo 3333 sẽ được chuyển thành địa chỉ vật lý bao nhiêu? – Địa chỉ vật lý 8888 sẽ được chuyển thành địa chỉ ảo bao nhiêu?  Biết rằng kích thước mỗi frame là 1K bytes Khoa KTMT 65 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 66 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 67 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 68 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 69 Segment Base Length 0 219 600 1 2300 14 2 90 100 3 1327 580 4 1952 96