Hệ điều hành 1 - Chương 8: Bộ nhớ ảo

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:32

Thêm vào BST

Báo xấu

77
lượt xem 5
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...

Chủ đề:

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

Lưu

Nội dung Text: Hệ điều hành 1 - Chương 8: Bộ nhớ ảo

Chöông 8 Boä Nhôù AÛo
Noäi dung trình baøy  Taïi sao caàn phaûi coù boä nhôù aûo ?  Toång quan veà hieän thöïc boä nhôù aûo  Hieän thöïc boä nhôù aûo : demand paging  Hieän thöïc 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  Hieän thöïc boä nhôù aûo : Demand Segmentation Khoa KTMT
Taïi sao caàn coù boä nhôù aûo ? Nhìn laïi paging vaø segmentation :  Caùc tham chieáu ñeán boä nhôù ñöôïc chuyeån ñoåi ñoäng thaønh ñòa chæ thöïc luùc process ñang thöïc thi CPU The CPU sends virtual package addresses to the MMU CPU Disk Memory controller MMU Bus The MMU sends physical addresses to the memory MMU: memory management unit  Moät process goàm caùc phaàn nhoû (page hay segment), caùc phaàn naøy ñöôïc naïp vaøo caùc vuøng coù theå khoâng lieân tuïc trong boä nhôù chính Khoa KTMT
Boä nhôù aûo (1)  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 • Ngay caû khi toaøn boä chöông trình ñeàu caàn duøng thì coù theå khoâng caàn duøng toaøn boä cuøng moät luùc. Khoa KTMT
Boä nhôù aûo (2)  Boä nhôù aûo (virtual memory) – Cô cheá ñöôïc hieän thöïc trong heä ñieàu haønh ñeå cho pheùp thöïc thi moät quaù trình maø chæ caàn giöõ trong boä nhôù chính moät phaàn cuûa khoâng gian ñòa chæ luaän lyù cuûa noù, coøn phaàn coøn laïi ñöôïc giöõ treân boä nhôù phuï (ñóa).  Ö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 Khoa KTMT
Boä nhôù aûo (3)  Thoâng thöôøng phaàn cuûa khoâng gian ñòa chæ luaän lyù cuûa quaù trình, neáu chöa caàn naïp vaøo boä nhôù chính, ñöôïc giöõ ôû moät vuøng ñaëc bieät treân ñóa goïi laø khoâng gian traùo ñoåi (swap space). • Ví duï: – swap partition trong Linux – file pagefile.sys trong Windows 2K Khoa KTMT
Toång quan veà hieän thöïc boä nhôù aûo  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
Phaàn cöùng hoã trôï boä nhôù aûo  Söï hoã trôï cuûa phaàn cöùng ñoái vôùi phaân trang ñaõ ñöôïc khaûo saùt trong chöông tröôùc. Chæ coù moät ñieåm khaùc bieät laø moãi muïc cuûa baûng phaân trang coù theâm caùc bit traïng thaùi ñaëc bieät – Present bit = 1 ⇒ trang hôïp leä vaø hieän trong memory • = 0 ⇒ trang khoâng hôïp leä hoaëc khoâng trong memory – Modified bit: cho bieát trang coù thay ñoåi keå töø khi ñöôïc naïp vaøo memory hay khoâng Khoa KTMT
Hieän thöïc boä nhôù aûo: 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 (present bit =0) 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
Page fault vaø caùc böôùc xöû lyù Khoa KTMT
Thay theá trang nhôù (1)  Böôùc 2 cuûa PFSR giaû söû tìm ñöôïc frame troáng. Ñeå xöû lyù ñöôïc caû tröôøng hôïp 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
Thay theá trang nhôù (2) Khoa KTMT
Hieän thöïc demand paging • 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
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ù 5 trang, vaø ñöôïc caáp 3 frame chuoãi tham chieáu trang nhôù Khoa KTMT
Giaûi thuaät thay trang Least Recently Used (LRU)  Thay theá trang nhôù khoâng ñöôïc tham chieáu laâu nhaát Ví duï:  chuoãi thammoät chieáu process coù 5 trang, vaø ñöôïc caáp 3 frame trang nhôù  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
Giaûi thuaät thay trang 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 seõ thöôøng 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 caùc giaûi thuaät thay trang LRU vaø FIFO chuoãi tham chieáu trang nhôù → → → → → → → → → → → → Khoa KTMT
Giaûi thuaät FIFO: Belady’s anomaly 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
Giaûi thuaät thay trang clock (1)  Caùc frame caáp cho process ñöôïc xem nhö moät boä ñeäm xoay voøng (circular buffer)  Khi moät trang ñöôïc thay, con troû seõ chæ ñeán frame keá tieáp trong buffer  Moãi frame coù moät use bit. Bit naøy ñöôïc thieát laäp trò 1 khi – Moät trang ñöôïc naïp laàn ñaàu vaøo frame – Trang chöùa trong frame ñöôïc tham chieáu  Khi caàn thay theá moät trang nhôù, trang nhôù naèm trong frame ñaàu tieân coù use bit baèng 0 seõ ñöôïc thay theá. – Treân ñöôøng ñi tìm trang nhôù thay theá, taát caû use bit Khoa KTMT
Giaûi thuaät thay trang clock (2) Khoa KTMT
So saùnh LRU, FIFO, vaø clock chuoãi tham chieáu trang nhôù  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 KTMT