Bài giảng Nguyên lý hệ điều hành: Chương 9 - Phạm Quang Dũng

Chương 9 của bài giảng Nguyên lý hệ điều hành giới thiệu về bộ nhớ ảo trong hệ điều hành. Các nội dung chính được trình bày trong chương này gồm: Phân trang theo yêu cầu - Demand paging, thay trang - Page replacement, phân phối các frames - Allocation of frames, thrashing, phân đoạn theo yêu cầu - Demand segmentation. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nguyên lý hệ điều hành: Chương 9 - Phạm Quang DũngNội dung chương 9BÀI GIẢNGNGUYÊN LÝ HỆ ĐIỀU HÀNHKiến thức cơ bảnPhân trang theo yêu cầu - Demand PagingThay trang - Page ReplacementChương 9: Bộ nhớ ảoPhân phối các Frames - Allocation of FramesPhạm Quang DũngBộ môn Khoa học máy tínhKhoa Công nghệ thông tinTrường Đại học Nông nghiệp Hà NộiWebsite: fita.hua.edu.vn/pqdungThrashingPhân đoạn theo yêu cầu - Demand SegmentationBài giảng Nguyên lý Hệ điều hànhMục tiêu9.2Phạm Quang Dũng ©20089.1. Kiến thức cơ bảnVirtual memory – sự tách riêng của bộ nhớ logic người sửdụng khỏi bộ nhớ vật lý.Mô tả các lợi ích của bộ nhớ ảo.Kích thước bộ nhớ vật lý có hạn ⇒ giới hạn kích thước ch.trìnhGiải thích các khái niệm phân trang theo yêu cầu, cácgiải thuật thay trang, phân phối các page frameThự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 hiện ⇒ có thể chứa chương trình ở đâu? –VIRTUAL MEMORY – phần đĩa cứng được quản lý như RAMDo đó không gian địa chỉ logic có thể lớn hơn không 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ìnhCho phép một số tiến trình chia sẻ không gian địa chỉ.Cho phép tạo tiến trình hiệu quả hơn.Bộ nhớ ảo có thể được thực thi thông qua:Demand paging (Windows, Linux…)Demand segmentation (IBM OS/2)Bài giảng Nguyên lý Hệ điều hành9.3Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành9.4Phạm Quang Dũng ©20081Bộ nhớ ảo lớn hơn bộ nhớ vật lýnhớlớbộ 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 tế trong bộ nhớ vậtlý nó có thể được lưu trong cácpage frame không liên tục.- MMU đảm nhận việc ánh xạ cáctrang logic vào các page frame trongbộ nhớ vật lý.(page tablefor demand paging)disk(cache for disk)kích thước bộ nhớ ảo chỉ bị giới hạn bởi dung lượng đĩaBài giảng Nguyên lý Hệ điều hành9.5Phạm Quang Dũng ©2008Shared Library Using Virtual MemoryBài giảng Nguyên lý Hệ điều hành9.6Phạm Quang Dũng ©20089.2. 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: tiến trình bắt đầu ngay sau khi sốtrang tối thiểu được nạp vào bộ nhớ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ơnKhi trang được cần đến (khi tiến trình tham chiếu đến nó)tham chiếu không hợp lệ ⇒ hủy bỏkhông trong bộ nhớ ⇒ đưa vào bộ nhớcó trong bộ nhớ ⇒ truy nhậpBài giảng Nguyên lý Hệ điều hành9.7Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành9.8Phạm Quang Dũng ©20082Valid-Invalid BitChuyển một vùng nhớ phân trang tới không gian đĩaChuyể mộ vùnhớtớđĩMỗi phần tử 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ất cả các v–inv bit bằng 0Ví dụ bảng phân trang:Frame #valid-invalid bit11110M00Demand paging ⇔ Paging with swappingKhi thông dịch địa chỉ, nếu v–inv bit bằng 0 ⇒ page fault.However, Demand paging use a lazy swapperBài giảng Nguyên lý Hệ điều hànhPhạm Quang Dũng ©20089.9Bảng phân trang khi một số trangmộ sốkhông ở trong bộ nhớ chínhbộ nhớ chíBài giảng Nguyên lý Hệ điều hành9.10Phạm Quang Dũng ©2008Các bước xử lý page fault1. Khi có tham chiếu tới trang, đầu tiên tham chiếu sẽ lập bẫy tớiHĐH ⇒ phát hiện page fault2. HĐH tìm trong bảng khác để quyết định:Bộ nhớ logiccủa tiến trìnhkết thúc tại đâytham chiếu không hợp lệ ⇒ hủy bỏ.không có trong bộ nhớ ⇒ đưa vào bộ nhớ.Các trangkhông sử dụng(tham chiếukhông hợp lệ)3. Nhận frame rỗi4. 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), cập nhậtdiskdanh sách frame rỗi.6. Khởi động lại lệnh gây page faultBài giảng Nguyên lý Hệ điều hành9.11Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành9.12Phạm Quang Dũng ©20083Các bước xử lý page fault (tiếp)Hiệu năng của phân trang theo yêu cầuTỷ lệ Page Fault - p : 0 ≤ p ≤ 1p=0 : không có page faults;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 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ính:- phục vụ ngắt page-fault (1-100 μs, 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, có thể giảm bằng coding)Bài giảng Nguyên lý Hệ điều hànhPhạm Quang Dũng ©20089.13Ví dụBài giảng Nguyên lý Hệ điều hành9.14Phạm Quang Dũng ©2008Điều gì xảy ra khi không có frame rỗi?Điề gìcórỗThời gian xử lý page-fault: 8 msThay trang – tìm một số trang trong bộ nhớ nhưng đangkhông được sử dụng để đưa ra ngoài.Thời gian truy nhập bộ nhớ (ma): 200 ns= 200 + 7,999,800 x pnsgiải thuật?nsEAT = (1-p) x 200 + p x 8,000,000hiệu năng? – muốn có một giải thuật tác động đến số lượngtối thiểu page faults.Nếu 1000 truy nhập có 1 page fault, EAT = 8.2 ms. Máy tínhchậm hơn 40 lần vì phân trang có yêu cầu.Một trang có thể được đưa vào bộ nhớ nhiều lần.EAT tỷ lệ trực tiếp với tỷ lệ 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.0000025Bài giảng Nguyên lý Hệ điều hành9.15Phạm Quang Dũng ©2008Bài giảng Nguyên lý Hệ điều hành9.16Phạm Quang Dũng ©200849.3. Thay trangPage ReplacementCác bước thay trang:1. Tìm vị trí của trang được yêu cầ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ọnmột frame nạn nhân.3. Đưa trang được yêu cầu vào frame rỗi. Cập nhật bảngphân trang và bảng quản lý frame rỗi.4. Khởi động lại tiến trình.Bài giảng Nguyên lý Hệ điều hành9.17Phạm Quang Dũng ©2008Các gi ...