Bài giảng Hệ điều hành - Chương 7: Bộ nhớ ảo - Thoại Nam

Nội dung text: Bài giảng Hệ điều hành - Chương 7: Bộ nhớ ảo - Thoại Nam

1. Cô cheá phaân trang (t.t) fra m e num ber 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.3- 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 doø tìm trong baûng phaân trang. Moãi muïc trong baûng phaân trang chöùa ñòa chæ 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öôùc cuûa trang laø 2n page num ber 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.4- 2
2. 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) – Moãi process coù 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 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) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.7- 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” cuûa baûng phaân trang Khi coù chuyeån ngöõ caûnh, TLB bò xoùa Khi TLB bò ñaày, AÙnh xaï ñòa chæ aûo (A’, A’’) thay theá baèng LRU –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. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.8- 4
3. Effective Access Time (t.t) ‰ Ví duï 1 ‰ Ví duï 2 – Associate lookup = 20 – Associate lookup = 20 – Memory access = 100 – Memory access = 100 – Hit ratio = 0.8 – Hit ratio = 0.98 – EAT = (100 + 20) * 0.8 + – EAT = (100 + 20) * 0.98 + (200 + 20) * 0.2 (200 + 20) * 0.02 = 1.2 * 100 + 20 = 1.02 * 100 + 20 = 140 = 122 40% slow in memory 22% slow in memory access time access time Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.11- 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-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 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ä. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.12- 6
4. Moâ hình baûng 2-möùc (two-level) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.15- Phaân trang 2-möùc ‰ Moät ñòa chæ luaän lyù (treân heä thoáng 32-bit vôùi trang nhôù 4K) ñöôïc chia thaønh caùc phaàn sau: – Page number: 20 bit page # offset ƒ Neáu moãi muïc 4 byte 20 bit 12 bit ⇒ 220 * 4 byte = 4 MB – 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 page num ber page offset – 10-bit page offset p1 p2 d 10 bit 10 bit 12 bit ‰ Vì vaäy,moät ñòa luaän lyù seõ nhö hình veõ beân –p1: chæ muïc cuûa baûng ngoaøi (outer page table)-möùc 1 –p2 : ñoä dôøi (displacement) ôû trong trang möùc 2 (xaùc ñònh bôûi *p1) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.16- 8
5. Baûng baêm (hashed page table) ‰ Duøng yù töôûng cuûa 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 phaàn töû cuûa baûng phaân trang quaûn lyù moät danh saùch lieân keát. Moãi phaàn töû danh saùch chöùa chæ soá trang aûo vaø chæ soá frame töông öùng. – Chæ soá trang aûo (virtual page number) ñöôï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å tìm ra phaàn töû töông öùng trong baûng phaân trang. Sau ñoù, doø tìm trong danh saùch lieân keát vôùi chæ soá trang aûo ñeå trích ruùt ra ñöôïc frame töông öùng. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.19- 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 hash table tham chieáu ñeán nhieàu trang (~ 16 trang) thay vì 1 trang. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.20- 10
6. 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 stack seõ töï ñoäng xaây döïng caùc procedure segment. sym bol ‰ Ví duï, trình bieân dòch Pascal seõ table taïo ra caùc segment sau: function sqrt – Global variables main program – Procedure call stack – Procedure/function code – Local variable ‰ Trình loader seõ gaùn moãi segment moät soá ñònh danh rieâng. Logical address space Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.23- Moâ hình cô cheá phaân ñoïan user space physical memory space 1 1 4 2 3 4 3 2 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.24- 12
7. Phaàn cöùng hoã trôï phaân ñoaïn segm ent s table limit base CPU s d yes physical < + memory no trap; addressing error Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.27- Chuyeån ñoåi boä nhôù phaân ñoaïn Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.28- 14
8. Quaù trình thöïc thi cuûa process ‰ OS naïp moät soá phaàn cuûa chöông trình vaøo boä nhôù ‰ Moãi baûng phaân trang/ñoaïn coù theâm moät present bit cho bieát phaàn töông öùng coù naèm trong boä nhôù chính hay khoâng. ‰ Khi coù moät tham chieáu naèm trong phaàn khoâng coù trong boä nhôù chính (present bit = 0) thì moät ngaét ñöôïc kích hoaït goïi laø memory fault ‰ Process chuyeån veà traïng thaùi Blocking ‰ OS phaùt ra moät yeâu caàu ñoïc ñóa ñeå naïp phaàn ñöôïc tham chieáu vaøo boä nhôù chính vaø trong khi ñoù, moät process khaùc ñöôïc chieám quyeàn thöïc thi ‰ Sau khi I/O hoaøn taát, moät ngaét ñöôïc kích hoaït, baùo cho OS chuyeån process töông öùng veà traïng thaùi Ready Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.31- Öu ñieåm cuûa boä nhôù aûo ‰ Soá löôïng process trong boä nhôù nhieàu hôn ‰ Moät process coù theå thöïc thi ngay caû khi kích thöôùc cuûa noù lôùn hôn boä nhôù thöïc ‰ Boä nhôù tham chieáu bôûi moät ñòa chæ luaän lyù ñöôïc goïi laø boä nhôù aûo (virtual memory) – Bao goàm boä nhôù thöïc + moät phaàn boä nhôù thöù caáp (ñóa cöùng, ) – Nhaèm ñaït hieäu quaû cao, caùc dòch vuï file system thöôøng ñöôïc boû qua; ñoïc/ghi ñóa tröïc tieáp vôùi caùc khoái döõ lieäu lôùn hôn so vôùi khoái cuûa heä thoáng file. – Thoâng thöôøng phaàn boä nhôù aûo ñöôïc löu tröõ ôû moät vuøng ñaëc bieät goïi laø khoâng gian traùo ñoåi (swap space). Ví duï file system swap trong Unix/Linux, file pagefile.sys trong Windows2K ‰ Vieäc chuyeån ñoåi töø ñòa chæ luaän lyù thaønh ñòa chæ thöïc ñöôïc thöïc hieän vôùi söï hoã trôï cuûa phaàn cöùng (memory management hardware) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.32- 16
9. Keát hôïp trang vaø ñ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 hai moâ hình phaân trang vaø phaân ñoaïn ‰ Coù raát nhieàu moâ hình keát hôïp. Sau ñaây laø moät moâ hình ñôn giaûn ‰ Moãi process seõ coù: – Moät baûng phaân ñoaïn – Nhieàu baûng phaân trang: moãi phaân ñoaïn coù moät baûng phaân trang ‰ Moät ñòa chæ luaän lyù (ñòa chæ aûo) bao goàm: – segment number: laø chæ muïc cuûa moät phaàn töû trong baûng phaân ñoaïn, phaàn töû naøy chöùa ñòa chæ cô sôû (base address) cuûa baûng phaân trang trong phaân ñoaïn ñoù – page number: laø chæ muïc trong baûng phaân trang, duøng ñeå tính ra chæ soá frame trong boä nhôù thöïc töông öùng – offset: duøng ñeå ñònh vò moät vò trí nhôù trong frame noùi treân. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.35- Sô ñoà chuyeån ñoåi ñòa chæ Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.36- 18
10. Fetch & placement policy ‰ Fetch Policy – Xaùc ñònh thôøi ñieåm neân naïp trang nhôù vaøo boä nhôù. Coù hai chieán löôïc thoâng duïng – Demand paging: chæ naïp trang vaøo boä nhôù chính khi vaø chæ khi coù tham chieáu ñeán trang ñoù (i.e.: chæ naïp theo yeâu caàu maø thoâi) ƒ Khi process môùi thöïc thi thì coù nhieàu page fault nhöng sau ñoù soá page fault seõ giaûm daàn – Pre-paging naïp tröôùc caùc trang nhôù: döïa treân tính locality ‰ Placement policy – Xaùc ñònh vò trí ñaët moät trang nhôù cuûa process trong boä nhôù thöïc – Vôùi heä thoáng segmentation thuaàn tuùy: first-fit, next fit – Vôùi heä thoáng paging hoaëc keát hôïp pagin/segmentation: ƒ Phaàn cöùng quaûn lyù boä nhôù quyeát ñònh vò trí ñaët trang, tuy nhieân vì caùc trang nhôù coù kích thöôùc nhö nhau neân khoâng gaëp phaûi khoù khaên gì Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.39- Replacement Policy ‰ Giaûi quyeát vaán ñeà choïn löïa moät trang trong boä nhôù chính seõ bò thay theá khi coù moät trang môùi caàn naïp vaøo boä nhôù chính. Tình huoáng naøy xaûy ra khi boä chính ñaày (khoâng coøn frame troáng naøo) ‰ Khoâng phaûi toaøn boä trang trong boä nhôù ñeàu coù theå ñöôïc thay, coù moät soá frames bò locked – Ña soá caùc kernel löu giöõ caùc thoâng tin ñieàu khieån vaø caùc caáu truùc döõ lieäu quan troïng cuûa heä thoáng trong caùc locked frames ‰ Caùc giaûi thuaät thay theá trang – Least recently used (LRU) – First-in, first-out (FIFO) –Clock ‰ Caùc giaûi thuaät thay theá trang phuï thuoäc vaøo resident set (soá frame caáp cho moãi process) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.40- 20
11. Least Recently Used (LRU) ‰ Thay theá trang nhôù khoâng ñöôïc tham chieáu laâu nhaát ‰ Ví duï: moät process coù 5 trang; resident set = 3 ‰ Moãi trang ñöôïc ghi nhaän (trong baûng phaân trang) thôøi ñieåm ñöôïc tham chieáu ⇒ trang LRU laø trang nhôù coù giaù trò thôøi gian tham chieáu nhoû nhaát (caàn moät chi phí tìm kieám trang nhôù LRU naøy moãi khi coù page fault) ‰ Do vaäy, LRU caàn söï hoã trôï raát lôùn cuûa phaàn cöùng vaø chi phí khaù cao cho vieäc tìm kieám. Tuy nhieân, raát ít heä thoáng maùy tính cung caáp ñuû söï hoã trôï phaàn cöùng cho chieán löôïc LRU Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.43- Giaûi thuaät FIFO ‰ Xem caùc frame ñöôïc caáp phaùt cho process nhö laø circular buffer – Khi boä ñeäm ñaày, trang nhôù cuõ nhaát seõ ñöôïc thay theá: first-in, first-out – Moät trang nhôù hay ñöôïc duøng thoâng thöôøng seõ laø trang cuõ nhaát ⇒ hay bò thay theá bôûi giaûi thuaät FIFO – Hieän thöïc ñôn giaûn: chæ caàn moät con troû xoay voøng caùc frame cuûa process ‰ So saùnh FIFO vaø LRU Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.44- 22
12. Ví duï veà giaûi thuaät clock Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.47- So saùnh Clock, FIFO vaø LRU ‰ Daáu *: use bit töông öùng ñöôïc thieát laäp trò 1 ‰ Giaûi thuaät Clock baûo veä caùc trang thöôøng ñöôïc tham chieáu baèng caùch thieát laäp use bit baèng 1 vôùi moãi laàn tham chieáu ‰ Moät soá keát quaû thöïc nghieäm cho thaáy clock coù hieäu suaát gaàn vôùi LRU Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.48- 24
13. Thrashing ‰ Neáu moät process khoâng coù ñuû soá frame caàn thieát thì tæ suaát page-fault raát cao. Ñieàu naøy khieán giaûm hieäu suaát CPU raát nhieàu ‰ Ví duï moät voøng laëp N laàn, moãi laàn tham chieáu ñeán ñòa chæ naèm trong 4 trang nhôù trong khi ñoù process chæ ñöôïc caáp 3 frames. ‰ Thrashing ≡ hieän töôïng moät process bò hoaùn chuyeån vaøo/ra lieân tuïc caùc trang nhôù. 1 1 2 3 4 2 3 2 4 1 3 3 4 1 2 4 3 1 2 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.51- Thrashing Diagram Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.52- 26
14. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.55- Minh hoïa moâ hình Working-Set Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -X.56- 28