Hệ điều hành - Quản lý bộ nhớ

Nội dung text: Hệ điều hành - Quản lý bộ nhớ

1. HỆ ĐIỀU HÀHH Quản lý bộ nhớ
2. Quaûn lyù boä nhôù  Caùc kieåu ñòa chæ nhôù  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 á phaphanân trang (paging) – Cô cheá phaân ñoaïn (segmentation) -9.2-
3. Vì sao phải quản lý bộ nhớ  Một chương trình muốn chạy thì phải được nạp vào trong bộ nhớ chính. – Vấn đề:  Khi nào nạp?  Nạp vào đâu?  Nạp những phần nào?  Quản lý bộ nhớ giúp tối ưu hóa hoạt động của bộ nhớ Tối ưu hóa số tiến trình cùng lúc ở trong bộ nhớ chính nâng cao tính đa chương Tận dụng tối đa bộ nhớ của máy tính -9.3-
4. Bộ nhớ  Là một dãy các ô nhớ liên tục nhau  Mỗi ô nhớ (một word) có một địa chỉ  Chương trình = tập các câu lệnh (chỉ thị máy) + dữ liệu  Nạp chương trình vào bộ nhớ  đặt các chỉ thị và dữ liệu vào các ô nhớ  xác định ánh xạ giữa các chỉ thị, dữ liệu vào địa chỉ trong bộ nhớ 0 MOV AX, 10 4 MOV BX, 20 8 ADD AX, AX, BX 12 16 -9.4-
5. Caùc kieåu ñòa chæ nhôù  Ñòa chæ vaät lyù (physical address) (ñòa chæ thöïc, ñòa chæ tuyeät ñoái) 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ôù ñoäc laäp vôùi caáu truùc, toå chöùc vaät lyù cuûa boä nhôù. – Caùc trình bieân dòò(ch (com p)piler) taoï ra maõ leäägnh chöông trình maø tron g ñoù moïi tham chieáu boä nhôù ñeàu laø ñòa chæ luaän lyù  Ñòòga chæ töông ñoái (()äòäyrelative 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 ñieåm xaùc ñònh naøo ñoù trong chöông trình (ví duï: 12 byte so vôùi ñieåm baét ñaàu chöông trình)  Khi moät leänh ñöôïc thöïc thi, caùc tham chieáu ñeán ñòa chæ luaän lyù ppïyhaûi ñöôïc chuyeån ñoåi thaønh ñ òa chæ thö ïc. Thao taùc chu yeån ñoåi naøy thöôøng coù söï hoã trôï cuûa phaàn cöùng ñeå ñaït hieäu suaát cao. -9.5-
6. 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: napnaïp load module vavaoøo boä nhôù chính System Library static linking dynamic linking StSystem Library -9.6-
7. Cô cheá thöïc hieän linking 0 0 Module A Relocatable Module A object modules CALL B LthLLength L JMP “L” L-1 Return L-1 Return L Module B 0 Module B JMP “L+M” CALL C Length M Load module L+M-1 Return Return M-1 L+M Module C 0 Module C Length N L+M+N-1 Return Return N-1 -9.7-
8. Chuyeån ñoåi ñòa chæ nhôù  Chuyeån ñoåi ñòa chæ laø 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.  BieBieuåudie dienãn ñòa chæ nhô ù – Trong source code: symbolic (caùc bieán, haèng, pointer, ) – Thôøi ñieåm bieân dòch: laø ñòa chæ khaû taùi ñònh vò (relocatable address), hayyò laø ñòa chæ töôn g(g ñoái (relative address ) . Ví duï: a ôû vò trí 14 bytes so vôùi phaàn header cuûa module. – Thôøi ñieåm linking/loading: laø ñòa chæ tuyeät ñoái. Ví duï: döõ lieäu naèm taïi ñòa chæ boä nhôù thöïc: 2030 0 2000 int I; goto p1; p1 250 2250 Symbolic address Relocatable address Absolute address (Phys ica l memory ) -9.8-
9. Chuyeån ñoåi ñòa chæ  Ñòa chæ cuûåûa leänh (instruction) vaø döõ lieäu (data) ñöôïc chuyeån ñoåi thaønh ñòa chæ vaät lyù, vieäc naøy 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ôù thì coù theå keát gaùn ñòa chæ vaät lyù luùc bieân dòch. . Ví du du:ï: chöông trình .COM cua cuûaMS MS-DOS, phat phaùtbie bieuåu assemply . Khuyeát ñieåm: phaûi bieân dòch laïi neáu thay ñoåi ñòa chæ – Load time: taïi thôøi ñieåm bieân dòch, neáu khoâng bieát ñòa chæ thöïc thì vaøo thôøi ñieåm loading, phaûi chuyeån ñoåi ñòa chæ khaû taùi ñònh vòò( (relocatable ) theo mo ät ñ òa chæ neàn (base address ). . Ñòa chæ thöïc ñöôïc tính toaùn laïi vaøo thôøi ñieåm chöông trình thöïc thi phaûi tieán haønh reload neáu ñòa chæ base thay ñoåi. -9.9-
10. Chuyeån ñoåi ñòa chæ vaøo thôøi ñieåm thöïc thi – Execution time: quaù trình chuyeån ñoåi ñöôïc trì hoaõn ñeán thôøi ñieåm thöïc thi Relative (relocatable) (run time) addresses . TùìhhhiùTrong quaù trình thöïc thi, process coù theå ñöôïc di chuyeån töø segment naøy 0 sang segment khaùc trong boä nhôù. . CPU taotaïo ra cacacùc ñòa chæ töông ñoñoiái JMP 400 cho process 400 . Caàn söï hoã trôï cuûa phaàn cöùng cho vieäc aùnh xaï ñòa chæ (ví duï coù thanh LOAD 1200 ghi b ase vaø lim it, ) . Söû duïng trong ña soá caùc OS ña duïng (general-purpose) trong ñoù coù caùc cô cheá swappin g, p ag ing, 1200 segmentation max = 2000 -9.10-
11. Dynamic linking  Quaù trình link moät soá 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) –Ví duï: ttoron g Win dos,dows, m odueodule n goaacacgoaøi laø caùc fil e .DLL ;co; coøn totron gUg Unix , caùc module ngoaøi laø caùc file .so (shared library)  Load module chæ chöùa caùc tham chieáu (()reference) ñeán caùc external module. Caùc tham chieáu naøy coù theå ñöôïc chuyeån ñoåi vaøo hai thôøi ñieåm sau: – Loading time (load-time dynamic linking) – Run time: khi coù moät lôøi goïi ñeán thuû tuïc ñöôïc ñònh nghóa trong external module (run-time dynamic linking)  Heä ñieàu haønh chòu traùch nhieäm tìm caùc external module vaø keát noái vaøo load module (kieåm tra xem external module ñaõ naïp vaøo boä nhôù chöa) -9.11-
12. Ö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ângg,ò caàn söûa ñoåi, bieân dòch laïi.  Chia seû maõma (code sharing): moät external module chæ cacanànnapva naïp vaoø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.  Dynamic linking caàn söï hoã trôï cuûa OS trong vieäc kieåm tra xem moät thu û tuctuïc nanaoøoño ñoù coù theå ñöôcñöôïc chia seû giögiöaõaca cacù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). -9.12-
13. Dynamic loading  Cô cheá: chæ khi naøo ñöôï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))ïïgg bôûi vì caùc thuû tuïc ít ñöôïc duøng seõ khoâng chieám choã trong boä nhôù  Raát hieääqu quaû trong tröôøng hôïp toàn taiïï khoái löônggg lôùn maõ chöông trình khoâng ñöôïc söû duïng thöôøng xuyeân (ví duï caùc thuû tuïc xöû lyù loãi)  Khoâng caàn söï hoã trôï ñaëc bieät cuûa 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öônggy 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 -9.13-
14. Cô cheá 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ânggg gian bo änhôù caá p cho p rocess ñoù.  Cô cheá naøy ñöôïc ñieàu khieån bôûi ngöôøi söû duïng (thoâng qua söï hoã trôï cua cuûaca cacùc thö vieän laäp trình) chöù khokhongâng cacanànsöho söï hoã trôï cua cuûa heä ñieàu haønh -9.14-
15. Cô cheá overlay (tt) Pass 1 70KB symbol Pass 2 80KB 20KB Symbol table 20KB table Common routines 30KB Assembler common routines 30KB Total memory available = 150KB overlay 10KB driver 80KB pass 1 pass 2 70KB -9.15-
16. Cô cheá 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ñöôïc napnaïp lailaïi vavaoøoboänhô boä nhôù ñeå tietiepáptuc tuïc quaù trình thöïc thi – Round-robin: swap-out A, swap-in B, thöïc thi C – Roll out, roll in – duøng trong cô cheá ñònh thôøi theo ñoä öu tieân (priority-based scheduling) . Process coù ñoääpòp öu tieân thaáp hôn seõ bò swap-out nhöôøng choã cho process coù ñoä öu tieân cao hôn ñöôïc naïp vaøo boä nhôù ñeå thöïc thi – Medium-term scheduler -9.16-
17. Minh hoïa cô cheá swapping -9.17-
18. Moâ hình quaûn lyù boä nhôù thöïc  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öø vieäc söû duïng cô cheá overlay).  Caùc cô cheá quaûn lyù boä nhôù thöïc 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, tuy nhieân ñoù laø caùc yù töôtöôngûng cô sôû cho moâ hình quan quaûnly lyù boä nhôù aaoûo sau nay: naøy: – Phaân chia coá ñònh (fixed partitioning) – Phaân chia ñoäng (dynamic partitioning) – PhaPhanân trang ñôn giagianûn (simple paging) – Phaân ñoaïn ñôn giaûn (simple segmentation) -9.18-
19. Phaân maûnh (fragmentation)  Phaân maûnh ngoaïi (external fragmentation) – Kích thöôùc khoâng gian boä nhôù coøn troáng ñuû ñeå thoûa maõn moät yeyeuâuca cauàuca capáp phat phaùt, tuy nhienhienânkho khongâng gian nhô ù nanayøykho khongâng lielienân tuïc phaûi duøng cô cheá keát khoái (compaction).  Phaâ n maû nh noäi (int ernal f ragment ati on) – Kích thöôùc vuøng nhôù ñöôïc caáp phaùt 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 (physical memory) ñöôï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) -9.19-
20. Phaân maûnh noäi operating yeâu caàu keá tieáp laø 18.462 bytes!!! system (used) 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 yeâu caàu cuûa process dö ra 2 byyggtes khoâng duøng! -9.20-
21. Fixed partitioning  Chia boä nhôù chính thaønh nhieàu phaàn khoâng truøng laáp 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ëëgc baèng kích thöôùc partition thì coù theå 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 chieám troïn moät partition. -9.21-
22. Chieán löôïc placement  Partition coù kích thöôùc baèng nhau – Coøn moät partition troáng process môùi ñöôïïïppc naïp vaøo partition ñoù – 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 ch oã ch o process môùi .  Partition coù kích thöôùc khoâng baèng nhau – GùGaùn mo ãi process va øo part iiition n hûhoû nhaát phuø hôïp vôùi noù – Coù haøng ñôïi cho moãi partition – GiaGiamûmthie thieuåu phan phaânma manhû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 thöôùc töông öng) öùng) vaø hahangøng ñôiñôïi daøy ñaëc -9.22-
23. Chieán löôïc placement (tt)  Partition coù kích thöôùc khoâng baèng nhau – Chæ coù moäägt haøng ñôiï chung cho caùc partition – Khi caàn naïp moät process vaøo boä nhôù chính choïn partiiition n ho ûn ha át coø n troá ng -9.23-
24. Dynamic partitioning  Soá löôïng partition khoâng coá ñònh vaø partition 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 (external fragmentation) -9.24-
25. 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 thieåu chi phí compaction (time consuming)  CaCacùc c hie án löôc öôïcpace placem ent – 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 ñ auà tienâ keå töø vòtíò trí caáp phaùt cuoái cuøng – Worst fit: choïn khoái nhôù trotrongáng lôlônùn nhanhatát -9.25-
26. Phaân trang (paging)  Cô cheá phaân trang cho pheùp khoâng gian ñòa chæ thöïc (physical address space) cuûa moät process coù theå khoâng lieân tuïc nhau.  Boä nhôù thöcthöïc ñöôcñöôïc chia thathanhønh cacacùckho khoiái kích thöôc thöôùcco coá ñònh bang baèng nhau goïi laø frame. – Thoâng thöôøng 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) cuõng ñöôïc chia thaønh khoái cuøng kích thöôùc goïi laø trang nhôù (page).  Heä ñieñieuàuha hanhønh phai phaûithie thietátlaäpmoät laäp moät babangûng phan phaân trang (page table) ñeå aùnh xaï ñòa chæ aûo, luaän lyù thaønh ñòa chæ thöïc – Moãi process coù moät baûng phaân trang ñöôïc quaûn lyù baèng moät con troû löu gggiöõ trong PCB. Coân g vieäc naïp baûn g phaân tran g vaøo heä thoán g (do CPU dispatcher thöïc hieän) laø moät phaàn cuûa chuyeån ngöõ caûnh  Cô cheá phaân trang khieán boä nhôù bò phaân maûnh noäi, tuy nhieân laïi khaéc phuïc ñöôïc phaân maûnh ngoaïi. -9.26-
27. Cô cheá phaân trang frame number 0 page 0 0 1 1 page 0 page 1 1 4 2 page 2 2 3 3 page 2 page 3 3 5 4 page 1 logical memory page table 5 page 3 physical memory -9.27-
28. Moâ hình chuyeån ñoåi ñòa chæ  Ñòa chæ nhôù do CPU taïo ra (logical address) goàm coù: – Page number (p) – ñöôïc duøng laøm chæ muïc trong baûng phaân trang. Mo ãi muïc trong ba ûng p ha ân trang c höùa ñòa c hæ c ô s ôû (hay chæ soá frame) cuûa trang töông öùng trong boä nhôù thöïc. – Page offset (d) – ñöôïc keát hôïp vôùi ñòa chæ cô sôû (base address) ñeå ñònh vò moät ñòa chæ thöïc.  Neáu kích thöôùc cuûa khoâng gian ñòa chæ aûo laø 2m, kích thöôthöôcùccu cuaûatrangla trang laø 2n page number page offset p d m-n bits n bits (ñònh vò töø 0  2m-n -1) (ñònh vò töø 0  2n-1) Do ñoù, baûng phaân trang seõ coù toång coäng 2m/2n = 2m-n muïc -9.28-
29. Paging hardware physical f logical address address f000 0000 CPU p d f d f111 1111 p f ppyhysical Neáu kích thöôùc cuûa khoâng memory gian nhôù thöïc laø 2l bytes, page table thì moãi muïc cuûa baûng phaân frame number frame offset tùtrang coù l-n bits f (l-n bits)d (n bits) -9.29-
30. Chuyeån ñoåi boä nhôù vôùi paging -9.30-
31. Hieän thöïc baûng phaân trang  Baûng phaân trang ñöôïc löu giöõ trong boä nhôù chính (kernel memory) – MãiMoãi process co ùmo ätbûät baûng p hâhaân trang – Thanh ghi page-table base (PTBR) troû ñeán baûng phaân trang – Thanh ghi page-table length (PTLR) bieåu thi kích thöôùc cuûa baûng phaân trang (vaø duøng ñeå baûo veä boä nhôù)  MoMoiãita tacùc vuï truy caäp döõ lieäu/leänh can caàn hai thao tac taùctruyxua truy xuatát vuøng nhôù – Moät thao taùc truy xuaát baûng phaân trang (page number: p) vaø moät thao tac taùctruyxua truy xuatátdö döõ lieäu/leänh (page offset: d – displacement) – 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) -9.31-
32. Associative register (hardware)  Thanh ghi keát hôïp (associative register): hoã trôï tìm kieám truy xuaát döõ lieäu ñoàng thôøi vôùi toác ñoä cöïc nhanh. Soá muïc cuûa TLB page # frame # khoaûng 8  2048 TLB la ø“ cache” cucuaûa baûng phaân trang Khi coù chuyeån ngöõ cacanhûnh, TLB bò xoxoaùa Khi TLB bò ñaày, thay theá baèng LRU AÙnh xaï ñòa chæ aûo (A’, A’’) –Neáu A’ naèm trong TLB (hit) laáy ngay ñöôïc chæ soá frame tieát kieäm ñöôïc ~ 10% thôøi gian tìm kieám. –Ngöôïc laïi (miss), phaûi tìm chæ soá frame töø baûng phaân trang nhö bình thöôøng. -9.32-
33. Paging hardware vôùi TLB -9.33-
34. 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). Caùc bit naøy bieåu thò caùc thuoäc tính sau –read-onldly, read-write, execu te-only  NgoaNgoaiøira,co ra, conønco coù moät valid-invalid bit gaganénvô vôiùimo moiãimuctrongba muïc trong bangûng phaân trang – “valid”: cho bieát laø trang boä nhôù töông öùng naèm trong khoâng gian nhôù ñòa chæ ao aûocu cuaûa process, do ño ù laø moät trang hô hôpïp leä . – “invalid”: cho bieát laø trang boä nhôù töông öùng khoâng naèm trong khoâng gian nhôù ñòa chæ aûo cuûa process, do ñoù laø moät trang baát hôïp leä. -9.34-
35. Baûo veä baèng valid-invalid bit 00000 0 page 0 frame number valid-invalid bit 1 page 1 0 2v 2 page 0 page 2 1 3v 3 page 1 2 page 3 4v 4 page 2 3 7 v 5 page 4 4 6 10468 8v page 5 7 page 3 12287 5 9v page 6 6 0i 8 page 4 9 page 5 page 7 7 0i  Moãi trang nhôù coù kích thöôùc 2KB = 2048 bytes page n  Process coù kích thöôùc 10,468bytes phaân maûnh noäi ôû page 5 cacacùc ñòa chæ > 12287 laø cacacùc ñòa chæ invalid.  Duøng PTLR ñeå kieåm tra kích thöôùc baûng phaân trang -9.35-
36. Hierarchical page table  Caùc heä thoáng hieän ñaïi ñeàu hoã trôï khoâng gian ñòa chæ aûo raát lôùn (232 ñeán 264). – Kích thöôc thöôùc trang nhô ù laø 4KB ( = 2 12) babangûng phan phaân trang se õ coù ~ 232/212 = 220 = 1M entries. – Giaû söû moãi phaàn töû laø moät con troû 32 bit thì moãi process caàn 4MB cho babangûng phan phaântrang trang   Moät giaûi phaùp ñöôïc ñaët ra laø chia thaønh nhieàu baûng phaân trang quaûn lyù caùc vuøng khoâng gian boä nhôù aûo khaùc nhau – baûng ña möùc (multilevel paging table).  Cô cheá taïo baûng phaân trang 2-möùc (two-level page table), hay coøn ñöôïc goïi laø forward-mapped page table trong heä thoáng Intel PtiPentium®-II -9.36-
37. Moâ hình baûng 2-möùc (two-level) -9.37-
38. Phaân trang 2-möùc  Moät ñòa chæ luaän lyù (treân heä thoáng 32-bit vôùi trang nhôù 4KB) ñöôïc chia thaønh caùc phaàn sau: –Page nu mbe r: 20 b it . Neáu moãi muïc 4 byte page # offset 220 * 4 byte = 4 MB 20 bit 12 bit – Page offset: 12 bit  Baûng phaân trang cuõng bò chia nhoû neân page number cuõng ñöôïc chia nhoû thathanhønh 2 phan: phaàn: – 10-bit page number page number page offset – 10-bit page offset p1 p2 d 10 bit 10 bit 12 bbtit  Vì vaäy, moät ñòa luaän lyù seõ bieåu dieãn nhö hình veõ –p1 : chæ muïc cuûa baûng ngoaøi (outer page table)-möùc 1 – p2 :ñoädô: ñoä dôiøi (displacement) ô û trong trang mömöcùc 2 (xa(xacùcñònhbô ñònh bôiûi *p1) -9.38-
39. Sô ñoà aùnh xaï ñòa chæ  Sô ñoà aùnh xaï ñòa chæ (address-translation scheme) cho kieán truùc baûng phaân trang 2 möùc, 32-bit ñòa chæ Memory Address: A A -9.39-
40. Phaân trang ña möùc (multilevel)  Khoâng gian ñòa chæ luaän lyù 64-bit vôùi trang nhôù 4KB – Trong sô ñoà phaân trang 2-möùc, soá muïc cuûa baûng phaân trang = 252 (264/212 = 252) quaù lôùn. Thöïc hieän töông töï moâ hình 2 möùc, phâhaân chi hithøhbûa thaønh baûng 3 34, 4, , n-möùc page number page offset page number page offset 52 12 42 10 12 page number page offset page number page offset 32 10 10 2 22 10 10 10 2 – Heä thoáng SPARC 32-bit hoã trôï cô cheá 3-möùc coøn caùc heä thoáng Motorolla 68030 32 bit hoã trôï cô cheá 4-möùc. Heä thoáng 64bit UltraSPARC thì d ungø bangû phanâ t7trang 7-möùc – Hieäu suaát cuûa heä thoáng phaân trang ña möùc? -9.40-
41. Baûng baêm (hashed page table)  Duøng baûng baêm ñeå giaûm bôùt khoâng gian baûng phaân trang, taêng toác ñoä tìm kieám trang. –Raatát p h oå bi eán tr on g caccaùc h eä t ho án g l ôùn h ôn 32 bi t ñòa c hæ.  Ñeå giaûi quyeát ñuïng ñoä, moãi entry cuûa baûng phaân trang ñöôïc gaùn moät danh sasachùch lien lieânke ket.át. MoMoiãi phaphanàntö töû danh sasachùch chöa chöùachæso chæ soá trang aaoûo (virtual page number) vaø chæ soá frame töông öùng. – Chæ soá trang aûo ñöôïc bieán ñoåi qua haøm baêm thaønh moät hashed value. Caùc thoâng tin nhö chæ soá trang aûo vaø chæ soá frame seõ ñöôïc löu vaøo danh saùch lieân keát taïi vò trí öùng vôùi hashed value.  Giaûi thuaät doø tìm trang: – Chæ soá trang aûo ñöôïc bieán ñoåi thaønh hashed value (vôùi cuøng haøm baêm nhö treân). Hashed value ñöôïc duøng ñeå truy xuaát ñeán entry töông öùng trong baûng phaân trang. Sau ñoù, doø tìm trong danh saùch lieân keát phaàn töû chöchöaùachæso chæ soá trang aaoûoñe ñeå trích rurutùt ra ñöôcñöôïc so á frame töông öng öùng. -9.41-
42. Hashed page tables  Caùc heä thoáng 64-bit ñòa chæ thöôøng duøng clustered page table, i.e. moãi muïc trong has h ta ble th am c hie áu ñe án n hie àu trang (~ 16 t rang) thay vì 1 trang. -9.42-
43. Chia seû caùc trang nhôù Process 1 0 ed 1 0 3 1 data 1 ed 2 1 4 2 data 3 6 Process 2 ed 3 2 3ed 1 3 1 ed 1 4 ed2d 2 data 1 0 3 ed 2 1 4 5 2 6 6ed 3 ed 3 ed 1 3 7 7 data 2 0 3 data 2 8 ed 2 1 4 9 ed 2 2 6 2 10 data 3 3 Process 3 -9.43-
44. 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á ppgïäppïhaâ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 ppï(g)pïäòäy,haân ñoaïn (segment). Moãi phaân ñoaïn laø moät ñôn vò luaän lyù, ví duï nhö: – main program, procedure, function, local variables, global variables, common block, stack, symbol table, arrays  Cô cheá phaân ñoaïn laø moâ hình quaûn lyù boä nhôù hoã trôï user-view – Khoâng gian ñòa chæ aûo laø moät taäp caùc phaân ñoaïn (segment), moãi phaân ñ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 phaân ñoaïn vaø ñoä dôøi (offset) beân trong phaân ñoaïn ñoù -9.44-
45. 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õ stack töï ñoänggy xaây döïn g caùc se gment. procedure symbol  Ví duï, trình bieân dòch Pascal seõ taïo table ra cacacùc segment sau: function – Global variables sqrt – Procedure call stack main program – Procedure/function code – Local variable  Trình loader seõ gaganùnmo moiãi segment moät soá ñònh danh rieâng. Logical address space -9.45-
46. Moâ hình cô cheá phaân ñoïan user space physical memory space 1 1 4 2 3 4 3 2 -9.46-
47. Toå chöùc cuûa cô cheá phaân ñoaïn  Ñòa chæ luaän lyù laø moät caëp giaù trò  Baûng phaân ñoaïn (segment table) – base – chöùa ñòa chæ khôûi ñaàu cuûa phaân ñoaïn trong boä nhôù – limit – xaxacùc ñònh kích thöôc thöôùccu cuaûa phaphanânñoan ñoaïn  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á segment cuûa chöông trình MäthæMoät chæ soá segmentlt s laø hôïp l e ä neuá s < STLR -9.47-
48. Moät ví duï veà cô cheá phaân ñoaïn stack 1400 procedure segment 0 segment 3 2400 limit base segment 0 symbol 0 1000 1400 3200 table 1 400 6300 segment 3 2 400 4300 function segment 4 4300 sqrt 3 1100 3200 segment 2 main program 4 1000 4700 4700 segment segment 1 segment 4 table segment 2 5700 6300 segment 1 Logical address space 6700 physical memory space -9.48-
49. Phaàn cöùng hoã trôï phaân ñoaïn segment s table limit base CPU sd yes physical < + memory no tdditrap; addressing error -9.49-
50. Chuyeån ñoåi boä nhôù phaân ñoaïn -9.50-
51. Chia seû caùc phaân ñoaïn editor limit base 43062 data 1 0 25286 43062 1 4425 68348 segment 0 segment 1 editor segment table process P1 Logical address space 68348 data 1 process P1 72773 editor limit base data 2 90003 0 25286 43062 dtdata 2 segment 1 1 8850 90003 segment 0 98553 segment table process P LilddLogical address space 2 physical memory process P2 -9.51-