Nguyên lý hệ điều hành – Chương 9: Bộ nhớ ảo – Tài liệu, ebook, giáo trình

„Phân phối các Frames – Allocation of Frames

„ Thrashing„ Phân đoạn theo nhu yếu – Demand Segmentatiog

11 trang | Chia sẻ : Mr Hưng| Lượt xem : 1941

| Lượt tải: 2

Nội dung tài liệu Nguyên lý hệ điều hành – Chương 9: Bộ nhớ ảo, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên

1B ÀI GIẢNG NGUYÊN LÝ HỆ ĐIỀU HÀNH Chương 9 : Bộ nhớ ảo Phạm Quang Dũng Bộ môn Khoa học máy tính Khoa Công nghệ thông tin Trường Đại học Nông nghiệp TP.HN Website : fita.hua.edu.vn/pqdung 9.2 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Nội dung chương 9 „ Kiến thức cơ bản „ Phân trang theo nhu yếu – Demand Paging „ Thay trang – Page Replacement „ Phân phối những Frames – Allocation of Frames „ Thrashing „ Phân đoạn theo nhu yếu – Demand Segmentation 9.3 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Mục tiêu „ Mô tả những quyền lợi của bộ nhớ ảo. „ Giải thích những khái niệm phân trang theo nhu yếu, những giải thuật thay trang, phân phối những page frame 9.4 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành 9.1. Kiến thức cơ bản „ Virtual memory – sự tách riêng của bộ nhớ logic người sử dụng khỏi bộ nhớ vật lý. z Kích thước bộ nhớ vật lý hạn chế ⇒ số lượng giới hạn size ch. trình z Thực tế, chỉ một phần của chương trình cần phải đưa vào bộ nhớ ( vật lý ) để thực thi ⇒ hoàn toàn có thể chứa chương trình ở đâu ? – VIRTUAL MEMORY – phần đĩa cứng được quản trị như RAM z Do đó khoảng trống địa chỉ logic hoàn toàn có thể lớn hơn khoảng trống địa chỉ vật lý rất nhiều ⇒ phân phối bộ nhớ rất lớn cho người lập trình z Cho phép 1 số ít tiến trình san sẻ khoảng trống địa chỉ. z Cho phép tạo tiến trình hiệu suất cao hơn. „ Bộ nhớ ảo hoàn toàn có thể được thực thi trải qua : z Demand paging ( Windows, Linux ) z Demand segmentation ( IBM OS / 2 ) 29.5 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Bộ nhớ ảo lớn hơn bộ nhớ vật lý size bộ nhớ ảo chỉ bị số lượng giới hạn bởi dung tích đĩa disk ( page table for demand paging ) ( cache for disk ) 9.6 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Không gian địa chỉ ảo của tiến trình – Là cách nhìn logic ( ảo ) về cách mà tiến trình được lưu trong bộ nhớ. – Tiến trình được lưu trong vùng nhớ liên tục, dù thực tiễn trong bộ nhớ vật lý nó hoàn toàn có thể được lưu trong những page frame không liên tục. – MMU đảm nhiệm việc ánh xạ những trang logic vào những page frame trong bộ nhớ vật lý. 9.7 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Shared Library Using Virtual Memory 9.8 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành 9.2. Phân trang theo nhu yếu „ Đưa một trang vào bộ nhớ chỉ khi nó được cần đến. z Cần ít thao tác vào-ra hơn z Cần ít bộ nhớ hơn z Đáp ứng nhanh hơn : tiến trình mở màn ngay sau khi số trang tối thiểu được nạp vào bộ nhớ z Nhiều người sử dụng / tiến trình hơn : do mỗi tiến trình dùng ít bộ nhớ hơn „ Khi trang được cần đến ( khi tiến trình tham chiếu đến nó ) z tham chiếu không hợp lệ ⇒ hủy bỏ z không trong bộ nhớ ⇒ đưa vào bộ nhớ z có trong bộ nhớ ⇒ truy nhập 39.9 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Chuyển một vùng nhớ phân trang tới khoảng trống đĩa Demand paging ⇔ Paging with swapping However, Demand paging use a lazy swapper 9.10 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Valid-Invalid Bit „ Mỗi thành phần trong bảng phân trang được gắn thêm một valid – invalid bit ( 1 ⇒ có trong bộ nhớ, 0 ⇒ không trong bộ nhớ ) „ Ban đầu khởi tạo tổng thể những v – inv bit bằng 0 „ Ví dụ bảng phân trang : „ Khi thông dịch địa chỉ, nếu v – inv bit bằng 0 ⇒ page fault. 1 1 1 1 0 0 0 M Frame # valid-invalid bit 9.11 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Bảng phân trang khi 1 số ít trang không ở trong bộ nhớ chính Các trang không sử dụng ( tham chiếu không hợp lệ ) Bộ nhớ logic của tiến trình kết thúc tại đây disk 9.12 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Các bước giải quyết và xử lý page fault 1. Khi có tham chiếu tới trang, tiên phong tham chiếu sẽ lập bẫy tới HĐH ⇒ phát hiện page fault 2. HĐH tìm trong bảng khác để quyết định hành động : z tham chiếu không hợp lệ ⇒ hủy bỏ. z không có trong bộ nhớ ⇒ đưa vào bộ nhớ. 3. Nhận frame rỗi 4. Copy / Hoán đổi trang vào frame. 5. Cập nhật lại bảng phân trang ( thiết lập v-inv bit = 1 ), update list frame rỗi. 6. Khởi động lại lệnh gây page fault 49.13 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Các bước giải quyết và xử lý page fault ( tiếp ) 9.14 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Hiệu năng của phân trang theo nhu yếu „ Tỷ lệ Page Fault – p : 0 ≤ p ≤ 1 z p = 0 : không có page faults ; z p = 1 : mọi tham chiếu đều là fault. „ Thời gian truy nhập hiệu quả-Effective Access Time ( EAT ) EAT = ( 1 – p ) x ma + p x [ thời hạn giải quyết và xử lý page-fault ] Trong đó : + ma : memory access – thời hạn truy nhập bộ nhớ ( 10-200 ns ) + thời hạn giải quyết và xử lý page-fault : gồm 3 yếu tố chính : – ship hàng ngắt page-fault ( 1-100 μs, hoàn toàn có thể giảm bằng coding ) – đọc trang vào bộ nhớ ( ≈ 8 ms ) – khởi động lại tiến trình ( 1-100 μs, hoàn toàn có thể giảm bằng coding ) 9.15 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Ví dụ „ Thời gian giải quyết và xử lý page-fault : 8 ms „ Thời gian truy nhập bộ nhớ ( ma ) : 200 ns „ EAT = ( 1 – p ) x 200 + p x 8,000,000 ns = 200 + 7,999,800 x p ns Nếu 1000 truy nhập có 1 page fault, EAT = 8.2 ms. Máy tính chậm hơn 40 lần vì phân trang có nhu yếu. „ EAT tỷ suất trực tiếp với tỷ suất page-fault, nếu p càng lớn thì EAT càng lớn → máy càng chậm. „ Muốn hiệu năng giảm dưới 10 %, ta cần có : 220 > 200 + 7,999,800 x p → p < 0.0000025 9.16 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Điều gì xảy ra khi không có frame rỗi ? „ Thay trang – tìm một số ít trang trong bộ nhớ nhưng đang không được sử dụng để đưa ra ngoài. z giải thuật ? z hiệu năng ? – muốn có một giải thuật tác động ảnh hưởng đến số lượng tối thiểu page faults. „ Một trang hoàn toàn có thể được đưa vào bộ nhớ nhiều lần. 59.17 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành 9.3. Thay trang Các bước thay trang : 1. Tìm vị trí của trang được nhu yếu trên đĩa. 2. Tìm một frame rỗi : - Nếu có frame rỗi thì sử dụng nó. - Nếu không có, sử dụng một giải thuật thay trang để chọn một frame nạn nhân. 3. Đưa trang được nhu yếu vào frame rỗi. Cập nhật bảng phân trang và bảng quản trị frame rỗi. 4. Khởi động lại tiến trình. 9.18 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Page Replacement 9.19 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Các giải thuật thay trang „ Mục đích : tỷ suất page-fault thấp nhất. „ Đánh giá giải thuật bằng cách chạy nó trên một chuỗi đơn cử những tham chiếu bộ nhớ và tính số page faults trên chuỗi đó. „ Trong tổng thể những ví dụ, chuỗi tham chiếu là 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. 9.20 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Đồ thị liên hệ giữa Page Faults và số Frame 69.21 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành a ) First-In-First-Out ( FIFO ) Algorithm „ Chuỗi tham chiếu : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 „ 3 frames ( với mỗi tiến trình : 3 trang hoàn toàn có thể nạp vào bộ nhớ tại một thời gian ) „ 4 frames „ FIFO Replacement – Sự không bình thường của Belady z nhiều frames ⇒ nhiều page faults 1 2 3 1 2 3 4 1 2 5 3 4 9 page faults 1 2 3 1 2 3 5 1 2 4 5 10 page faults 44 3 9.22 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành FIFO Page Replacement 9.23 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Minh họa sự không bình thường của Belady 9.24 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành b ) Optimal Algorithm „ Thay trang có thời hạn sẽ không sử dụng đến lâu nhất. „ ví dụ 4 frames 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 „ Làm cách nào để biết trang nào sẽ không được sử dụng nữa ? → Không thể biết được. „ Được sử dụng làm tiêu chuẩn nhìn nhận những giải thuật khác. 1 2 3 4 6 page faults 4 5 79.25 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Optimal Page Replacement 9.26 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành c ) Least Recently Used ( LRU ) Algorithm „ Thay trang có khoảng chừng thời hạn không dùng lâu nhất „ Chuỗi tham chiếu : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Sự thực hiện của Bộ đếm ( Counter ) zMọi thành phần bảng có một bộ đếm, mọi thời điểm trang được tham chiếu qua thành phần bảng này, copy clock vào trong bộ đếm. zKhi trang cần được hoán đổi, tìm trong bộ đếm để xác lập trang nào làm nạn nhân. 8 page faults 5 2 4 3 1 2 3 4 1 2 5 4 1 2 5 3 1 2 4 3 9.27 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành LRU Page Replacement „ Cách xác lập trang không sử dụng lâu nhất ? 1. Sử dụng Bộ đếm ( Counter ) z Mọi thành phần bảng có một bộ đếm, mọi thời điểm trang được tham chiếu qua thành phần bảng này, copy clock vào trong bộ đếm. z Khi trang cần được hoán đổi, tìm trong bộ đếm để xác lập trang nào làm nạn nhân. 9.28 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành LRU Algorithm ( tiếp ) 2. Sử dụng Stack z Dùng một stack của những số trang z Khi trang được tham chiếu : chuyển nó lên đỉnh ⇒ trang không dùng lâu nhất sẽ luôn dưới đáy dùng một list link kép, cần 6 con trỏ để đổi trang z Không cần tìm kiếm để sửa chữa thay thế 89.29 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành d ) Các giải thuật tựa như LRU „ Giải thuật dùng thêm bit tham chiếu z Gắn một bit vào mỗi trang, khởi tạo = 0 z Khi trang được tham chiếu, bit đó được thiết lập = 1. z Thay trang có bit tham chiếu = 0, nếu có sống sót „ Giải thuật thời cơ thứ hai ( Second chance ) z Cần có bit tham chiếu. Nếu bit tham chiếu = 0 thì thay trang. Trái lại cho trang đó thời cơ thứ hai và chuyển đến trang tiếp sau thiết lập bit tham chiếu = 0. để trang lại trong bộ nhớ. thay trang tiếp nối ( theo FIFO ) với luật tương tự như. z Một cách thực thi giải thuật là sử dụng queue vòng tròn. 9.30 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Giải thuật thay trang " thời cơ thứ hai " 9.31 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành e ) Các giải thuật dựa trên số liệu thống kê „ Dành ra một bộ đếm số tham chiếu đến mỗi trang. „ Least Frequently Used ( LFU ) Algorithm : thay trang đếm được tối thiểu ( có tần số truy nhập nhỏ nhất ). „ Most Frequently Used ( MFU ) Algorithm : thay trang đếm được nhiều nhất ( có tần số truy nhập cao nhất ), dựa trên lý luận rằng trang đếm được tối thiểu là hoàn toàn có thể vừa được đưa vào bộ nhớ và chưa kịp được sử dụng. 9.32 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành 9.4. Phân phối những Frame „ Mỗi tiến trình cần số lượng trang tối thiểu để thực thi. „ Ví dụ : IBM 370 – cần 6 trang để triển khai lệnh SS MOVE : z lệnh độ dài 6 bytes, hoàn toàn có thể chứa trong 2 trang. z 2 trang để thực thi from. z 2 trang để thực thi to. „ Hai cách phân phối chính : z phân phối cố định và thắt chặt ( fixed allocation ) z phân phối theo mức ưu tiên ( priority allocation ) 99.33 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Phân phối cố định và thắt chặt 1. Phân phối công minh – vd nếu có 100 frames và 5 tiến trình, cho mỗi tiến trình 20 trang. 2. Phân phối theo size của tiến trình m S spa chăm sóc sức khỏe và làm đẹp m sS ps i ii i ii × = = = ∑ = = for allocation frames of number total process of size 5964 137 127 564 137 10 127 10 64 2 1 2 ≈ × = ≈ × = = = = a a s s m i 9.34 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Phân phối theo mức ưu tiên „ Nếu tiến trình Pi phát sinh một page fault, z chọn sửa chữa thay thế một trong số những frame của nó. z frame thay vào đó được chọn từ một tiến trình có mức ưu tiên thấp hơn. 9.35 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Global vs. Local Allocation „ Global replacement – tiến trình chọn một frame sửa chữa thay thế từ tập toàn bộ những frame ; một tiến trình hoàn toàn có thể lấy một frame từ một tiến trình khác. „ Local replacement – mỗi tiến trình chỉ chọn một frame thay thế sửa chữa từ chính tập những frame đã phân phối cho nó. 9.36 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành 9.5. Thrashing „ Nếu một tiến trình không có “ đủ ” trang, tỷ suất page fault là rất cao. Điều này dẫn đến : z sử dụng CPU thấp. z HĐH cho rằng nó cần phải tăng mức đa chương trình. z một tiến trình khác được thêm vào mạng lưới hệ thống, nó cố gắng nỗ lực giành frame từ những tiến trình đang triển khai ⇒ tỷ suất page fault càng tăng „ Thrashing ≡ những tiến trình mất nhiều thời hạn ( bận rộn ) với việc hoán đổi những trang vào-ra hơn là thời hạn thực thi. 10 9.37 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Thrashing ( tiếp ) 9.38 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Lược đồ tần số Page-Fault „ Thiết lập tỷ suất page-fault “ hoàn toàn có thể đồng ý được ” z Nếu tỷ suất trong thực tiễn quá thấp, tiến trình làm mất frame. z Nếu tỷ suất thực tiễn quá cao, tiến trình tăng thêm frame. 9.39 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Windows XP „ Sử dụng phân trang theo nhu yếu có phân cụm ( clustering ) : đưa vào bộ nhớ fauling page và một số ít trang tiếp sau. „ Các tiến trình được ấn định working set minimum và working set maximum „ Working set minimum là số lượng trang nhỏ nhất mà tiến trình được bảo vệ có trong bộ nhớ. „ Một tiến trình hoàn toàn có thể được gán cho càng nhiều trang càng tốt không vượt quá working set maximum của nó. „ Khi dung tích bộ nhớ rỗi của mạng lưới hệ thống nhỏ hơn một ngưỡng, automatic working set trimming được thực thi để Phục hồi lại dung tích bộ nhớ rỗi. „ Working set trimming vô hiệu số trang của những tiến trình vượt quá working set minimum của chúng. 9.40 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Solaris „ Duy trì list những trang rỗi để gán những faulting process. „ Lotsfree – tham số ngưỡng ( dung tích bộ nhớ rỗi ) để khởi đầu phân trang. „ Desfree – tham số ngưỡng để tăng phân trang „ Minfree – tham số ngưỡng để triển khai swapping „ Phân trang được thực thi bởi tiến trình pageout „ Pageout quét những trang sử dụng giải thuật clock có sửa đổi „ Scanrate là vận tốc những trang được quét. Dải này từ slowscan đến fastscan „ Pageout được gọi càng liên tục phụ thuộc vào vào dung tích bộ nhớ rỗi khả dụng. 11 9.41 Phạm Quang Dũng © 2008B ài giảng Nguyên lý Hệ điều hành Solaris 2 Page Scanner End of Chapter 9 Các file đính kèm theo tài liệu này :

• vn_ch09_virtualmemory_5082.pdf

Source: https://vh2.com.vn
Category : Ứng Dụng