›

Bài giảng nguyên lý hệ điều hành - Chương 9: Bộ nhớ ảo

pdf 11 trang huongle 7180
Download
Bạn đang xem tài liệu "Bài giảng nguyên lý hệ điều hành - Chương 9: Bộ nhớ ảo", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_nguyen_ly_he_dieu_hanh_chuong_9_bo_nho_ao.pdf

Nội dung text: Bài giảng nguyên lý hệ điều hành - Chương 9: Bộ nhớ ảo

  1. Nội dung chương 9 BÀI GIẢNG NGUYÊN LÝ HỆ ĐIỀU HÀNH „ Kiến thức cơ bản „ Phân trang theo yêu cầu - Demand Paging „ Thay trang - Page Replacement Chương 9: Bộ nhớảo „ Phân phối các Frames - Allocation of Frames „ Thrashing Phạm Quang Dũng Bộ môn Khoa học máy tính „ Phân đoạn theo yêu cầu - Demand Segmentation Khoa Công nghệ thông tin Trường Đại học Nông nghiệp Hà Nội Website: fita.hua.edu.vn/pqdung Bài giảng Nguyên lý Hệ điều hành 9.2 Phạm Quang Dũng ©2008 Mục tiêu 9.1. Kiến thức cơ bản „ Virtual memory –sự tách riêng của bộ nhớ logic người sử „ Mô tả các lợi ích của bộ nhớảo. dụng khỏi bộ nhớ vật lý. z Kích thước bộ nhớ vật lý có hạn ⇒ giới hạn kích thước ch.trình „ Giải thích các khái niệm phân trang theo yêu cầu, các z Thực tế, chỉ một phần của chương trình cần phải đưa vào bộ nhớ giải thuật thay trang, phân phối các page frame (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ư RAM z Do đó 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ình z Cho phép một số tiến trình chia sẻ không gian địa chỉ. z 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: z Demand paging (Windows, Linux ) z Demand segmentation (IBM OS/2) Bài giảng Nguyên lý Hệ điều hành 9.3 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.4 Phạm Quang Dũng ©2008 1
  2. Bộ nhớ ảo lớn hơn bộ nhớ vật lý 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ật lý nó có thể được lưu trong các page frame không liên tục. - MMU đảm nhận việc ánh xạ các trang logic vào các page frame trong bộ nhớ vật lý. (page table for demand paging) disk (cache for disk) kích thước bộ nhớảo chỉ bị giới hạn bởi dung lượng đĩa Bài giảng Nguyên lý Hệ điều hành 9.5 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.6 Phạm Quang Dũng ©2008 Shared Library Using Virtual Memory 9.2. Phân trang theo yêu cầ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 bắt đầu 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 Bài giảng Nguyên lý Hệ điều hành 9.7 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.8 Phạm Quang Dũng ©2008 2
  3. Chuyển một vùng nhớ phân trang tới không gian đĩa Valid-Invalid Bit „ 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 0 „ Ví dụ bảng phân trang: Frame # valid-invalid bit 1 1 1 1 0 M 0 0 Demand paging ⇔ Paging with swapping „ Khi thông dịch địa chỉ,nếu v–inv bit bằng 0 ⇒ page fault. However, Demand paging use a lazy swapper Bài giảng Nguyên lý Hệ điều hành 9.9 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.10 Phạm Quang Dũng ©2008 Bảng phân trang khi một số trang không ở trong bộ nhớ chính Các bước xử lý page fault 1. Khi có tham chiếu tới trang, đầu tiên 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: Bộ nhớ logic của tiến trình z tham chiếu không hợp lệ ⇒ hủy bỏ. kết thúc tại đây z không có trong bộ nhớ ⇒ đưa vào bộ nhớ. Các trang 3. Nhận frame rỗi không sử dụng (tham chiếu 4. Copy/Hoán đổi trang vào frame. không hợp lệ) 5. Cập nhật lại bảng phân trang (thiết lập v-inv bit = 1), cập nhật disk danh sách frame rỗi. 6. Khởi động lại lệnh gây page fault Bài giảng Nguyên lý Hệ điều hành 9.11 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.12 Phạm Quang Dũng ©2008 3
  4. Các bước xử lý page fault (tiếp) Hiệu năng của phân trang theo yêu cầ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 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ành 9.13 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.14 Phạm Quang Dũng ©2008 Ví dụ Điều gì xảy ra khi không có frame rỗi? „ Thời gian xử lý page-fault: 8 ms „ Thay trang – tìm một số trang trong bộ nhớ nhưng đang „ Thời gian truy nhập bộ nhớ (ma): 200 ns không được sử dụng để đưa ra ngoài. „ EAT = (1-p) x 200 + p x 8,000,000 ns z giải thuật? = 200 + 7,999,800 x p ns z hiệu năng? – muốn có một giải thuật tác động đến số lượng tối thiểu page faults. 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ó 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.0000025 Bài giảng Nguyên lý Hệ điều hành 9.15 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.16 Phạm Quang Dũng ©2008 4
  5. 9.3. Thay trang Page Replacement Cá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ọn một frame nạn nhân. 3. Đưa 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ỗi. 4. Khởi động lại tiến trình. Bài giảng Nguyên lý Hệ điều hành 9.17 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.18 Phạm Quang Dũng ©2008 Các giải thuật thay trang Đồ thị liên hệ giữa Page Faults và số Frame „ Mục đích: 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 cụ thể các tham chiếu bộ nhớ và tính số page faults trên chuỗi đó. „ 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. Bài giảng Nguyên lý Hệ điều hành 9.19 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.20 Phạm Quang Dũng ©2008 5
  6. a) First-In-First-Out (FIFO) Algorithm FIFO Page Replacement „ 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 có thể nạp vào bộ nhớ tại một thời điểm) 1 1 4 5 2 2 1 3 9 page faults 3 3 2 4 „ 4 frames 1 1 5 4 2 2 1 5 10 page faults 3 3 2 4 4 3 „ FIFO Replacement – Sự bất thường của Belady z nhiều frames ⇒ nhiều page faults Bài giảng Nguyên lý Hệ điều hành 9.21 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.22 Phạm Quang Dũng ©2008 Minh họa sự bất thường của Belady b) Optimal Algorithm „ Thay trang có thời gian 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 1 4 2 6 page faults 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 giá các giải thuật khác. Bài giảng Nguyên lý Hệ điều hành 9.23 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.24 Phạm Quang Dũng ©2008 6
  7. Optimal Page Replacement c) Least Recently Used (LRU) Algorithm „ Thay trang có khoảng thời gian 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 1 1 1 1 5 2 2 2 2 2 8 page faults 3 5 5 4 4 4 4 3 3 3 Sự thực hiện của Bộ đếm (Counter) z Mọi phần tử bảng có một bộ đếm, mọi thời điểm trang được tham chiếu qua phần tử 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 định trang nào làm nạn nhân. Bài giảng Nguyên lý Hệ điều hành 9.25 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.26 Phạm Quang Dũng ©2008 LRU Page Replacement LRU Algorithm (tiếp) 2. Sử dụng Stack z Dùng một stack của các 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 danh sách liên kết kép, cần 6 con trỏ để đổi trang z Không cần tìm kiếm để thay thế „ Cách xác định trang không sử dụng lâu nhất? 1. Sử dụng Bộ đếm (Counter) z Mọi phần tử bảng có một bộ đếm, mọi thời điểm trang được tham chiếu qua phần tử 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 định trang nào làm nạn nhân. Bài giảng Nguyên lý Hệ điều hành 9.27 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.28 Phạm Quang Dũng ©2008 7
  8. d) Các giải thuật tương tự LRU Giải thuật thay trang "cơ hội thứ hai" „ 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ó tồn tại „ Giải thuật cơ hội 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 đó cơ hội 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 kế tiếp (theo FIFO) với luật tương tự. z Một cách thực hiện giải thuật là sử dụng queue vòng tròn. Bài giảng Nguyên lý Hệ điều hành 9.29 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.30 Phạm Quang Dũng ©2008 e) Các giải thuật dựa trên số liệu thống kê 9.4. Phân phối các Frame „ Dành ra một bộ đếm số tham chiếu đến mỗi trang. „ Mỗi tiến trình cần số lượng trang tối thiểu để thực hiện. „ Ví dụ: IBM 370 – cần 6 trang để thực hiện lệnh SS „ Least Frequently Used (LFU) Algorithm: thay trang đếm MOVE: được ít nhất (có tần số truy nhập nhỏ nhất). z lệnh độ dài 6 bytes, có thể chứa trong 2 trang. „ Most Frequently Used (MFU) Algorithm: thay trang đếm z 2 trang để thực hiện from. được nhiều nhất (có tần số truy nhập cao nhất), dựa trên z 2 trang để thực hiện to. lý luận rằng trang đếm được ít nhất là có thể vừa được „ Hai cách phân phối chính: đưa vào bộ nhớ và chưa kịp được sử dụng. z phân phối cố định (fixed allocation) z phân phối theo mức ưu tiên (priority allocation) Bài giảng Nguyên lý Hệ điều hành 9.31 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.32 Phạm Quang Dũng ©2008 8
  9. Phân phối cố định Phân phối theo mức ưu tiên 1. Phân phối công bằng–vdnếu có 100 frames và 5 „ Nếu tiến trình Pi phát sinh một page fault, tiến trình, cho mỗi tiến trình 20 trang. z chọn thay thế một trong số các frame của nó. 2. Phân phối theo kích thước của tiến trình 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. si = size of process pi m = 64 S = ∑si si = 10 m = total number of frames s2 = 127 si 10 ai = allocation for pi = × m a = × 64 ≈ 5 S 1 137 127 a = × 64 ≈ 59 2 137 Bài giảng Nguyên lý Hệ điều hành 9.33 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.34 Phạm Quang Dũng ©2008 Global vs. Local Allocation 9.5. Thrashing „ Global replacement – tiến trình chọn một frame thay thế „ Nếu một tiến trình không có “đủ”trang, tỷ lệ page fault là rất cao. Điều này dẫn đến: từ tập tất cả các frame; một tiến trình có thể lấy một z sử dụng CPU thấp. frame từ một tiến trình khác. z HĐH cho rằng nó cần phải tăng mức đa chương trình. „ Local replacement – mỗi tiến trình chỉ chọn một frame z một tiến trình khác được thêm vào hệ thống, nó cố gắng thay thế từ chính tập các frame đã phân phối cho nó. giành frame từ các tiến trình đang thực hiện ⇒ tỷ lệ page fault càng tăng „ Thrashing ≡ các tiến trình mất nhiều thời gian (bận rộn) với việc hoán đổi các trang vào-ra hơn là thời gian thực hiện. Bài giảng Nguyên lý Hệ điều hành 9.35 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.36 Phạm Quang Dũng ©2008 9
  10. Thrashing (tiếp) Lược đồ tần số Page-Fault „ Thiết lập tỷ lệ page-fault “có thể chấp nhận được” z Nếu tỷ lệ thực tế quá thấp, tiến trình làm mất frame. z Nếu tỷ lệ thực tế quá cao, tiến trình tăng thêm frame. Bài giảng Nguyên lý Hệ điều hành 9.37 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.38 Phạm Quang Dũng ©2008 Windows XP Solaris „ Sử dụng phân trang theo yêu cầu có phân cụm (clustering): đưa vào „ Duy trì danh sách các trang rỗi để gán các faulting process. bộ nhớ fauling page và một số trang tiếp sau. „ Lotsfree – tham số ngưỡng (dung lượng bộ nhớ rỗi) để bắt đầu „ Các tiến trình được ấn định working set minimum và working set phân trang. maximum „ Desfree –tham số ngưỡng để tăng phân trang „ Working set minimum là số lượng trang nhỏ nhất mà tiến trình được đảm bảo có trong bộ nhớ. „ Minfree – tham số ngưỡng để thực hiện swapping „ Một tiến trình có thể được gán cho càng nhiều trang càng tốt không „ Phân trang được thực hiện bởi tiến trình pageout vượt quá working set maximum của nó. „ Pageout quét các trang sử dụng giải thuật clock có sửa đổi „ Khi dung lượng bộ nhớ rỗi của hệ thống nhỏ hơn một ngưỡng, „ Scanrate là tốc độ các trang được quét. Dải này từ slowscan automatic working set trimming được thực hiện để khôi phục lại dung lượng bộ nhớ rỗi. đến fastscan „ Working set trimming loại bỏ số trang của các tiến trình vượt quá „ Pageout được gọi càng thường xuyên phụ thuộc vào dung working set minimum của chúng. lượng bộ nhớ rỗi khả dụng. Bài giảng Nguyên lý Hệ điều hành 9.39 Phạm Quang Dũng ©2008 Bài giảng Nguyên lý Hệ điều hành 9.40 Phạm Quang Dũng ©2008 10
  11. Solaris 2 Page Scanner End of Chapter 9 Bài giảng Nguyên lý Hệ điều hành 9.41 Phạm Quang Dũng ©2008 11