Chương 8: Bộ nhớ ảo

Chia sẻ: Lê Tẹt | Ngày: | Loại File: PPT | Số trang:25

Thêm vào BST

Báo xấu

70
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhận xét: không phải tất cả các phần của một process cần thiết phải được nạp vào bộ nhớ chính tại cùng một thời điểm Ví dụ Đoạn mã điều khiển các lỗi hiếm khi xảy ra Các arrays, list, tables được cấp phát bộ nhớ (cấp phát tĩnh) nhiều hơn yêu cầu thực sự Một số tính năng ít khi được dùng của một chương trình Cả chương trình thì cũng có đoạn code chưa cần dùng Bộ nhớ ảo (virtual memory): Bộ nhớ ảo là một kỹ thuật cho phép xử lý một tiến trình không được nạp toàn bộ vào bộ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 8: Bộ nhớ ảo

Chöông 8 Boä Nhôù AÛo
Noäi dung trình baøy  Toång quan veà boä nhôù aûo  Caøi ñaët boä nhôù aûo : demand paging  Caøi ñaët boä nhôù aûo : Page Replacement – Caùc giaûi thuaät thay trang (Page Replacement Algorithms)  Vaán ñeà caáp phaùt Frames  Vaán ñeà Thrashing  Caøi ñaët boä boä nhôù aûo : Demand Segmentation Khoa KTMT 2
1. Toång quan boä nhôù aûo  Nhaän xeùt: khoâng phaûi taát caû caùc phaàn cuûa moät process caàn thieát phaûi ñöôïc naïp vaøo boä nhôù chính taïi cuøng moät thôøi ñieåm • Ví duï – Ñoaïn maõ ñieàu khieån caùc loãi hieám khi xaûy ra – Caùc arrays, list, tables ñöôïc caáp phaùt boä nhôù (caáp phaùt tónh) nhieàu hôn yeâu caàu thöïc söï – Moät soá tính naêng ít khi ñöôïc duøng cuûa moät chöông trình – Caû chöông trình thì cuõng coù ñoaïn code chöa caàn duøng  Boä nhôù aûo (virtual memory): Boä nhôù aûo laø moät kyõ thuaät cho pheùp xöû lyù moät tieán trình khoâng ñöôïc naïp toaøn boä vaøo boä nhôù vaät lyù Khoa KTMT 3
1. Boä nhôù aûo (tt) Ö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 – Giaûm nheï coâng vieäc cuûa laäp trình vieân  Khoâng gian traùo ñoåi giöõa boä nhôù chính vaø boä nhôù phuï(swap space). • Ví duï: – swap partition trong Linux – file pagefile.sys trong Windows Khoa KTMT 4
2. Caøi ñaët boä nhôù aûo  Coù hai kyõ thuaät: – Phaân trang theo yeâu caàu (Demand Paging) – Phaân ñoaïn theo yeâu caàu (Segmentation Paging)  Phaàn cöùng memory management phaûi hoã trôï paging vaø/hoaëc segmentation  OS phaûi quaûn lyù söï di chuyeån cuûa trang/ñoaïn giöõa boä nhôù chính vaø boä nhôù thöù caáp  Trong chöông naøy, – Chæ quan taâm ñeán paging – Phaàn cöùng hoã trôï hieän thöïc boä nhôù aûo – Caùc giaûi thuaät cuûa heä ñieàu haønh Khoa KTMT 5
2.1.Phaân trang theo yeâu caàu demand paging • Demand paging: caùc trang cuûa quaù trình chæñöôïc naïp vaøo boä nhôù chính khi ñöôïc yeâu caàu.  Khi coù moät tham chieáu ñeán moät trang maø khoâng coù trong boä nhôù chính (valid bit) thì phaàn cöùng seõ gaây ra moät ngaét (goïi laø page-fault trap) kích khôûi page-fault service routine (PFSR) cuûa heä ñieàu haønh.  PFSR: 1. Chuyeån process veà traïng thaùi blocked 2. Phaùt ra moät yeâu caàu ñoïc ñóa ñeå naïp trang ñöôïc tham chieáu vaøo moät frame troáng; trong khi ñôïi I/O, moät process khaùc ñöôïc caáp CPU ñeå thöïc thi 3. Sau khi I/O hoaøn taát, ñóa gaây ra moät ngaét ñeán heä ñieàu haønh; PFSR caäp nhaät page table vaø chuyeån process veà traïng thaùi ready. Khoa KTMT 6
2.2. Loãi trang vaø caùc böôùc xöû lyù Khoa KTMT 7
2.3. Thay theá trang nhôù  Böôùc 2 cuûa PFSR giaû söû phaûi thay trang vì khoâng tìm ñöôïc frame troáng, PFSR ñöôïc boå sung nhö sau 1. Xaùc ñònh vò trí treân ñóa cuûa trang ñang caàn 2. Tìm moät frame troáng: a. Neáu coù frame troáng thì duøng noù b. Neáu khoâng coù frame troáng thì duøng moät giaûi thuaät thay trang ñeå choïn moät trang hy sinh (victim page) c. Ghi victim page leân ñóa; caäp nhaät page table vaø frame table töông öùng 3. Ñoïc trang ñang caàn vaøo frame troáng (ñaõ coù ñöôïc töø böôùc 2); caäp nhaät page table vaø frame table töông öùng. Khoa KTMT 8
2.3. Thay theá trang nhô (tt)ù Khoa KTMT 9
2.4. Caùc thuaät toaùn thay theá trang • Hai vaán ñeà chuû yeáu:  Ví duï  Frame-allocation algorithm • Thöù töï tham chieáu caùc – Caáp phaùt cho process bao ñòa chæ nhôù, vôùi page nhieâu frame cuûa boä nhôù size = 100: thöïc? • 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102,  Page-replacement algorithm 0103, 0104, 0101, 0609, 0102, – Choïn frame cuûa process 0105 seõ ñöôïc thay theá trang nhôù ⇒ caùc trang nhôù sau ñöôïc – Muïc tieâu: soá löôïng page- tham chieáu laàn löôït = fault nhoû nhaát chuoãi tham chieáu boä – Ñöôïc ñaùnh giaù baèng nhôù (trang nhôù) caùch thöïc thi giaûi thuaät • 1, 4, 1, 6, 1, ñoái vôùi moät chuoãi tham • 1, 1, 1, 6, 1, chieáu boä nhôù (memory • 1, 1, 1, 6, 1, reference string) vaø xaùc • 1, 1, 1, 6, 1, ñònh soá laàn xaûy ra page • 1 fault Khoa KTMT 10
a) Giaûi thuaät thay trang FIFO  Caùc döõ lieäu caàn bieát ban ñaàu: – Soá khung trang – Tình traïng ban ñaàu – Chuoãi tham chieáu Khoa KTMT 11
Nghòch lyù Belady Khoa KTMT 12
Nghòch lyù Belady Baát thöôøng (anomaly) Belady: soá page fault taêng maëc daàu quaù trình ñaõ ñöôïc caáp nhieàu frame hôn. Khoa KTMT 13
2.4 b)Giaûi thuaät thay trang OPT(optimal)  Giaûi thuaät thay trang OPT – Thay theá trang nhôù seõ ñöôïc tham chieáu treã nhaát trong töông lai  Ví duï: moät process coù 7 trang, vaø ñöôïc caáp 3 frame Khoa KTMT 14
c) Giaûi thuaät laâu nhaát chöa söû duïng Least Recently Used (LRU)  Ví duï:  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ù thôøi ñieåm tham chieáu nhoû nhaát (OS toán 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ôï cuûa phaàn cöùng vaø chi phí cho vieäc tìm kieám. Ít CPU cung caáp ñuû söï hoã trôï phaàn cöùng cho giaûi thuaät LRU. Khoa KTMT 15
LRU vaø FIFO  So saùnh caùc giaûi thuaät thay trang LRU vaø FIFO chuoãi tham chieáu trang nhôù → → → → → → → → → → → → Khoa KTMT 16
2.5.Soá löôïng frame caáp cho process  OS phaûi quyeát ñònh caáp cho moãi process bao nhieâu frame. – Caáp ít frame ⇒ nhieàu page fault – Caáp nhieàu frame ⇒ giaûm möùc ñoä multiprogramming  Chieán löôïc caáp phaùt tónh (fixed-allocation) – Soá frame caáp cho moãi process khoâng ñoåi, ñöôïc xaùc ñònh vaøo thôøi ñieåm loading vaø coù theå tuøy thuoäc vaøo töøng öùng duïng (kích thöôùc cuûa noù,…)  Chieán löôïc caáp phaùt ñoäng (variable-allocation) – Soá frame caáp cho moãi process coù theå thay ñoåi trong khi noù chaïy  Neáu tyû leä page-fault cao ⇒ caáp theâm frame  Neáu tyû leä page-fault thaáp ⇒ giaûm bôùt frame – OS phaûi maát chi phí ñeå öôùc ñònh caùc process Khoa KTMT 17
a) Chieán löôïc caáp phaùt tónh  Caáp phaùt baèng nhau: Ví duï, coù 100 frame vaø 5 process → moãi process ñöôïc 20 frame  Caáp phaùt theo tæ leä: döïa vaøo kích thöôùc process si = size of process pi Ví duï: m = 64 S = ∑ si s1 =10 s2 =127 m = total number of frames 10 a1 = ×64 ≈ 5 137 si 127 ai = allocation for pi = ×m a2 = ×64 ≈ 59 S 137  Caáp phaùt theo ñoä öu tieân Khoa KTMT 18
3. Trì trệ treân toaøn boä heä thoáng Thrashing  Neáu moät process khoâng coù ñuû soá frame caàn thieát thì tæsoá page faults/sec raát cao.  Thrashing: hieän töôïng caùc trang nhôù cuûa moät process bò hoaùn chuyeån vaøo/ra lieân tuïc. Khoa KTMT 19
a ) Mo â h ìn h c u ïc b o ä ( Lo c a lit y )  Ñeå haïn cheá thrashing, heä ñieàu haønh phaûi cung caáp cho process caøng “ñuû” frame caøng toát. Bao nhieâu frame thì ñuû cho moät process thöïc thi hieäu quaû? Nguyeân lyù locality (locality principle) – Locality laø taäp caùc trang ñöôïc tham chieáu gaàn nhau – Moät process goàm nhieàu locality, vaø trong quaù trình thöïc thi, process seõ chuyeån töø locality naøy sang locality khaùc  Vì sao hieän töôïng thrashing xuaát hieän? Khi Σ size of locality > memory size Khoa KTMT 20