Hệ điều hành - Chương 7: Virtual Memory (bộ nhớ ảo)

Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Chương 7 Virtual Memory(bộ nhớ ảo)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Mục đích và yêu cầuMục đích:Nắm được khái niệm phân trang và phân đọan. Hiểu được cơ chế quản lý bộ nhớ ảoYêu cầu:Nắm được các chiến lược quản lý và thể hiện được các giải thuật cung cấp frame.Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Nội dungThông tin cơ bản - BackgroundPhân trang theo yêu cầu – Demand PagingThay trang – Page ReplacementPhân phối các Frames – Allocation of FramesThrashingPhân đoạn theo yêu cầu – Demand SegmentationKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Thông tin cơ bảnVirtual memory – sự tách riêng của bộ nhớ logic (của user) khỏi bộ nhớ vật lýKích thước bộ nhớ vật lý có hạn => nó giới hạn kích thước chương trình.Thực tế, chỉ cần 1 phần của chương trình cần phải đưa vào bộ nhớ (vật lý) để thực hiện => có thể chứa chương trình ở đâu ?- virtual memory.Do đó ko gian địa chỉ logic có thể lớn hơn ko gian địa chỉ vật lý rất nhiều => cung cấp bộ nhớ rất lớn cho người lập trình.Cho phép 1 số process chia sẻ ko gian địa chỉ.Cho phép tạo process hiệu quả hơn.Bộ nhớ ảo có thể được thực hiện thông qua:Demand paging (windows, linux)Demand segmentation (IBM. OS/2)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Bộ nhớ ảo lớn hơn bộ nhớ vật lýKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Phân trang theo yêu cầuĐưa một trang vào bộ nhớ chỉ khi nó được cần đến:Cần ít thao tác vào ra hơnCần ít bộ nhớ hơnĐáp ứng nhanh hơn: process bắt đầu ngay sau khi số trang tối thiểu được nạp vào bộ nhớ.Nhiều user/process hơn do mỗi process dùng ít bộ nhớ hơnKhi trang được cần đến (khi process tham chiếu đến nó)Tham chiếu ko hợp lệ => hủy bỏKo trong bộ nhớ => đưa vào bộ nhớCó trong bộ nhớ => truy nhậpKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Chuyển một vùng nhớ phân trang tới không gian ổ đĩaKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Valid-invalid BitKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Bảng phân trang khi 1 số trangko ở trong bộ nhớ chínhKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Page FaultKhi có tham chiếu tới trang, đầu tiên tham chiếu sẽ lập bẫy với Os => phát hiện page faultOs tìm trong bảng khác để quyết định:Tham chiếu ko hợp lệ => hủy bỏKhông có trong bộ nhớ => đưa vào bộ nhớNhận Frame rỗiCopy/Hoán đổi trang vào frameCập nhật lại bảng phân trang (thiết lập v-inv bit =1), cập nhật danh sách frame rỗi.Khởi động lại lệnh.Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Các bước xử lý Page FaultKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Điều gì xẩy ra khi ko có frame rỗiThay trang – tìm một số trang trong bộ nhớ nhưng đang ko được sử dụng để đưa ra ngoài.Giải thuật?Hiệu năng? – muốn có 1 giải thuật tác động đến số lượng tối thiểu page faults.Một trang có thể được đưa vào bộ nhớ nhiều lần.Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Hiệu năng của phân trang theo yêu cầuTỷ lệ Page Fault – p : 0≤ p ≤ 1P=0 ; ko có page faultP=1 ; mọi tham chiếu đều là faultThời gian truy nhập hiệu quả -Effective Access Time (EAT) EAT = (1-p)x ma + px(thời gian xử lý page fault)Trong đó:+ ma: memory access – thời gian truy nhập bộ nhớ (10-200 ns)+ Thời gian xử lý page-fault: gồm 3 vấn đề chínhPhục vụ ngắt page fault (1-100 μs, có thể giảm bằng coding)Đọc trang vào bộ nhớ (khoảng 25 ms)Khởi động lại process (1 – 100 μs, có thể giảm bằgn coing)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Ví dụThời gian xử lý page-fault 25msThời gian truy nhập bộ nhớ (ma): 100 nsEAT =(1-p) x 100 + p x 25,000.000 ns.= 100 + 24,999.990 x p nsEAT tỷ lệ thuật với page fault, nếu p càng lớn thì EAT càng lớn  máy càng chậmMuốn hiệu năng giảm dưới 10% ta cần có110 > 100 + 25.000.000 x p p < 0.0000004Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Page Replacement (thay trang)Các bước thay trang:Tìm vị trí của trang được yêu cầu trên đĩa.Tìm 1 frame rỗi:Nếu có frame rỗi thì sử dụng nóNếu ko có, sử dụng giải thuật thay trang để chọn 1 frame nạn nhân.Đọc trang được yêu cầu vào frame rỗi. Cập nhật bảng phân trang và bảng quản lý frame rỗiKhởi động lại processKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Quá trình thay thế trang nhớKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Các giải thuật thay trangMục tiêu: giảm thiểu tỷ lệ 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 riêng biệt các tham chiếu bộ nhớ và tính số page fault trên chuỗi đó.Các giải thuật thay thế trang phụ thuộc vào resident set (số frame cấp cho mỗi process)Trong tất cả các ví dụ. Chuỗi tham chiếu là1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Least Recently Used (LRU)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Giải thuật FIFOKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Giải thuật Clock (second–chance)Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Vì dụ về giải thuật clockKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*So sánh Clock, FIFO và LRUKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Khoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Mô hình tần suất Page-FaultKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Ưu điểm của bộ nhớ ảoKhoa Công Nghệ Thông Tin – Đại Học Công Nghiệp TP Hồ Chí Minh*Câu hỏi và bài tậpMiêu tả cơ chế phân trang và phân đọan?Mục đích của phân trang. Phân đọan là gi?Ưu điểm của bộ nhớ ảo?Dưới tình huống nào các “fault” trang xuất hiện? Miêu tả các hành động của hệ điều hành khi một lỗi trang xuất hiện.Làm các bt 10.11 và 10.16 trong sgk, làm các bt theo các giải thuật thay thế trang LRU, FIFO,OTP