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

HỆ ĐIỀU HÀHH Quản lý bộ nhớ 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á phaân trang (paging)– – Cô cheá phaân ñoaïn (segmentation) -9.2- 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- 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 4MOV AX, 10 8 12 MOV BX, 20 ADD AX, AX, BX 16 -9.4- 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 (compiler) tao 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) 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ù phaûi ñöôïc chuyeån ñoåi thaønh ñòa chæ thöïc. Thao taùc chuyeån ñoåi -9.5- naøy thöôøng coù söï hoã trôï cuûa phaàn cöùng ñeå ñaït hieäu suaát cao. 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: nap load module vaøo boä nhôù chính ï System Library static linking S t -9.6- ys em Library dynamic linking Cô cheá thöïc hieän linking Module A CALL B L th L 0 Module A JMP “L” Relocatable object modules 0 Return eng L-1 Return Module BL L-1 Module B CALL C Length M JMP “L+M”Load module 0 Return Module C Return Module C L+M-1 L+MM-1 0 Return Length N ReturnL+M+N-1 N-1 -9.7- 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.  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: laø ñòa chæ khaû taùi ñònh vò (relocatable address), hay laø ñòa chæ töông ñ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 2000int I; goto p1; 250 2250 Relocatable address Absolute address (Ph i l ) Symbolic address p1 -9.8- ys ca memory Chuyeån ñoåi ñòa chæ û å Ñòa chæ cua leänh (instruction) vaø döõ lieäu (data) ñöôïc chuyen ñ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: chöông trình COM cuûa MS DOS phaùt bieå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- 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 (run time) T ù ì h h hi ù Relative (relocatable) addresses rong qua tr n t öïc t , process co theå ñöôïc di chuyeån töø segment naøy sang segment khaùc trong boä nhôù.  CPU tao ra caùc ñòa chæ töông ñoái 0 JMP 400 ï cho process  Caàn söï hoã trôï cuûa phaàn cöùng cho vieäc aùnh xaï ñòa chæ (ví duï coù thanh hi b ø li it ) LOAD 1200 400 g ase va m ,...  Söû duïng trong ña soá caùc OS ña duïng (general-purpose) trong ñoù coù caùc cô cheá swapping, paging, 1200 segmentation max = 2000 -9.10- 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: 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æ 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- Ö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 nap 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.  Dynamic linking caàn söï hoã trôï cuûa OS trong vieäc kieåm tra xem moät thuû tuc 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). -9.12- 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) bôûi vì caùc thuû tuïc ít ñöôïc duøng seõ khoâng chieám choã trong boä nhôù  Raát hieäu quaû trong tröôøng hôp toàn tai khoái löông 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öô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 -9.13- 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â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 -9.14- Cô cheá overlay (tt) Pass 1 70KB Pass 2 80KB Symbol table 20KB symbol table 20KB Common routines 30KB Assembler common Total memory available = 150KB routines 30KB overlay driver 10KB 80KB pass 1 pass 2 -9.15- 70KB 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 nap lai vaøo boä nhôù ñeå tieáp tuc ï ï ï ï 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ä ö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- Minh hoïa cô cheá swapping -9.17- 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öôûng cô sôû cho moâ hình quaûn lyù boä nhôù aûo sau naøy: – 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) -9.18- 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 yeâu caàu caáp phaùt tuy nhieân khoâng gian nhôù naøy khoâng lieân , tuïc  phaûi duøng cô cheá keát khoái (compaction). Ph â û h äi (i t l f t ti ) an man no n erna ragmen a 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 cau 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- Phaân maûnh noäi operating system yeâu caàu keá tieáp laø 18.462 bytes!!! (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 bytes khoâng duøng! -9.20- 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ëc 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ø -9.21- lôùn hay nhoû ñeàu chieám troïn moät partition. Chieán löôïc placement  Partition coù kích thöôùc baèng nhau – Coøn moät partition troáng  process môùi ñöôïc 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ï höôø h ã h ôùin ng c o c o process m .  Partition coù kích thöôùc khoâng baèng nhau G ù ãi ø i i h û– an mo process vao part t on n o 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 -9.22- ï daøy ñaëc Chieán löôïc placement (tt)  Partition coù kích thöôùc khoâng baèng nhau – Chæ coù moät haøng ñôi chung ï cho caùc partition – Khi caàn naïp moät process vaøo boä nhôù chính  choïn i i h û h á ø ápart t on n o n at con trong -9.23- 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- 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)  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 h ø hô ñ à ti â k å töø ò t íp u ïp au en e v r caáp phaùt cuoái cuøng – Worst fit: choïn khoái nhôù troáng lôùn nhaát -9.25- 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öc ñöôc chia thaønh caùc khoái kích thöôùc coá ñònh 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àu haønh phaûi thieát laäp moät baûng 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 giöõ trong PCB. Coâng vieäc naïp baûng phaân trang vaøo heä thoáng (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- Cô cheá phaân trang frame number page 0 page 1 10 page 0 0 1 page 2 page 3 4 3 5 1 2 3 page 2 2 3 logical memory page table page 14 5 page 3 -9.27- physical memory 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 t M ãi t b û h â t höù ñò hæ ô ôû (hrang. o muïc rong ang p an rang c a a c c s ay 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öôùc cuûa trang laø 2n d page number page offset p m-n bits (ñònh vò töø 0  2m-n -1) n bits (ñònh vò töø 0  2n-1) -9.28- Do ñoù, baûng phaân trang seõ coù toång coäng 2m/2n = 2m-n muïc Paging hardware logical physical address f000 0000 f CPU p d f d address p f1111111 f physical Neáu kích thöôùc cuûa khoâng gian nhôù thöïc laø 2l bytes, thì moãi muïc cuûa baûng phaân t ù l bit frame number frame offset page table memory -9.29- rang co -n s f (l-n bits) d (n bits) Chuyeån ñoåi boä nhôù vôùi paging -9.30- 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 ãi ù ät b û h â t– o process co mo ang p an rang – 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ôù)  Moãi taùc vu truy caäp döõ lieäu/leänh caàn hai thao taùc truy xuaát ï vuøng nhôù – Moät thao taùc truy xuaát baûng phaân trang (page number: p) vaø moät thao taùc truy xuaát 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- - 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. page # frame # Soá muïc cuûa TLB khoaûng 8  2048 TLB laø “cache” cuûa Khi coù chuyeån ngöõ caûnh TLB bò xoùa baûng phaân trang , 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. -9.32- –Ngöôïc laïi (miss), phaûi tìm chæ soá frame töø baûng phaân trang nhö bình thöôøng. Paging hardware vôùi TLB -9.33- 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 d l d it t l– rea -on y, rea -wr e, execu e-on y  Ngoaøi ra, coøn coù moät valid-invalid bit gaén vôùi moãi muc trong baûng ï phaân trang – “valid”: cho bieát laø trang boä nhôù töông öùng naèm trong khoâng gian nhôù ñòa chæ aûo cuûa process do ñoù laø moät trang hô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- Baûo veä baèng valid-invalid bit page 0 00000 page 1 2 v frame number valid-invalid bit 0 0 1 2 page 0 page 2 page 3 3 v 4 v 7 1 2 3 3 page 1 4 page 2 5 10468 page 4 page 5 12287 v 8 v 9 v 4 5 6 7 page 3 page 6 0 i 0 i 6 7page 7 8 page 4 9 page 5 ...  Moãi trang nhôù coù kích thöôùc 2KB = 2048 bytes  Process coù kích thöôùc 10,468bytes  phaân maûnh noäi ôû page 5  caùc ñòa chæ > 12287 laø caùc ñòa chæ invalid page n -9.35- .  Duøng PTLR ñeå kieåm tra kích thöôùc baûng phaân trang 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 trang nhôù laø 4KB ( 212) baûng 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 baûng phaân 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 P ti ® II -9.36- en um - Moâ hình baûng 2-möùc (two-level) -9.37- 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 number: 20 bit  Neáu moãi muïc 4 byte  220 * 4 byte = 4 MB – Page offset: 12 bit 20 bit page # offset 12 bit  Baûng phaân trang cuõng bò chia nhoû neân page number cuõng ñöôïc chia nhoû thaønh 2 phaàn: – 10-bit page number – 10-bit page offset p2 page number page offset dp1 10 bit10 bit 12 bit  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 p : ñoä dôøi (displacement) ôû trong trang möùc 2 (xaùc ñònh bôûi *p ) -9.38- – 2 1 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æ A Memory Address: A -9.39- 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, h â hi th ø h b û 3 4 öùp an c a an ang , ,..., n-m c page number page offset 52 12 page number page offset 42 10 12 b ff t b ff tpage num er page o se 32 10 10 2 page num er page o se 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 Ult SPARC thì d ø b û h â t 7 öù -9.40- ra ung ang p an rang -m c – Hieäu suaát cuûa heä thoáng phaân trang ña möùc? 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. – Raát phoå bieán trong caùc heä thoáng lôùn hôn 32 bit ñòa chæ.  Ñeå giaûi quyeát ñuïng ñoä, moãi entry cuûa baûng phaân trang ñöôïc gaùn moät danh saùch lieân keát. Moãi phaàn töû danh saùch chöùa chæ soá trang aû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öùa chæ soá trang aûo ñeå trích ruùt ra ñöôc soá frame töông öùng -9.41- ï . Hashed page tables  Caùc heä thoáng 64-bit ñòa chæ thöôøng duøng clustered page table, i.e. ãi t h h t bl th hi á ñ á hi à t ( 16 t ) -9.42- mo muïc rong as a e am c eu en n eu rang ~ rang thay vì 1 trang. Chia seû caùc trang nhôù Process 1 ed 1 30 0 1 data 1 ed 2 ed 3 4 6 1 1 2 3 Process 2 ed 1 2 data 3 3 ed 1 4 d 2 data 1 ed 2 ed 3 3 4 6 0 1 2 e 5 6 ed 3 ed 1 ed 2 3 4 0 1 data 2 73 7 data 2 8 ed 2 data 3 6 2 2 3 9 10 -9.43- Process 3 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 phaâ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- 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. procedure stack  Ví duï, trình bieân dòch Pascal seõ taïo ra caùc segment sau: symbol table – Global variables – Procedure call stack – Procedure/function code function sqrt main program – Local variable  Trình loader seõ gaùn moãi segment moät soá ñònh danh rieâng. Logical address space -9.45- Moâ hình cô cheá phaân ñoïan user space physical memory space 1 1 2 4 3 4 3 2 -9.46- 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 – xaùc ñònh kích thöôùc cuûa phaân ñoan ï  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 ät hæ á t l ø hô l ä á STLR o c so segmen s a ïp e neu s < -9.47- Moät ví duï veà cô cheá phaân ñoaïn stack 1400 procedure symbolsegment 0 segment 3 segment 0 limit base 0 1000 1400 2400 3200 table function sqrt segment 4 segment 3 segment 2 1 400 6300 2 400 4300 3 1100 3200 4300 main program segment 1 segment 2 segment 4 4 1000 4700 segment table 4700 5700 segment 1 Logical address space 6300 6700 -9.48- physical memory space Phaàn cöùng hoã trôï phaân ñoaïn s segment table limit base CPU s d < + physicalmemory yes no t dd i -9.49- rap; a ress ng error Chuyeån ñoåi boä nhôù phaân ñoaïn -9.50- Chia seû caùc phaân ñoaïn editor data 1 limit base 0 25286 43062 43062 segment 0 segment 1 1 4425 68348 segment table process P1 editor Logical address space process P1 data 1 72773 68348 editor data 2 limit base 0 25286 43062 d t 2 90003 segment 0 segment 1 L i l dd 1 8850 90003 segment table process P2 a a 98553 -9.51- og ca a ress space process P2 physical memory