Thực hành Hệ điều hành - Bài thực hành số 8.1: Các chiến lược thay thế trang

Nội dung text: Thực hành Hệ điều hành - Bài thực hành số 8.1: Các chiến lược thay thế trang

1. Trang 2 1.1 Câu hỏi 1 Giả sử hệ thống không hạn chế số trang thật dành cho process P1, việc truy xuất trang của process P1 ở trên sẽ gây ra bao nhiêu lỗi truy xuất trang ? Tối thiểu cần phân phối cho P1 bao nhiêu trang thật ₫ể ₫ạt ₫ược số lỗi truy xuất trang tối thiểu như trên ? Xét trình tự truy xuất trang ở trên, ta thấy process cần truy xuất 6 trang ảo khác nhau (chỉ số từ 0 tới 5), do ₫ó tối thiểu là tạo ra 6 lỗi truy xuất trang khác nhau. Để số lỗi truy xuất trang tối thiểu như trên, ₫ừng bao giờ giải phóng trang mà sau ₫ó ta cần truy xuất lại. Khi cần nạp trang 0, thay vì nạp vào trang thật mới, ta có thể nạp vào trang thật ₫ang chứa trang 5 vì trang 5 không bao giờ cần truy xuất lại. Ngược lại khi nạp trang 1 thì không nên ₫è lên trang 0 vì trang 0 sẽ ₫ược truy xuất lại, ta nên dùng thật khác. Tương tự, khi nạp trang 2 thì nên dùng trang thật mới. Tương tự, khi nạp trang 3 thì nên dùng trang thật mới. Tương tự, khi nạp trang 4 thì nên dùng trang thật mới. Tóm lại tối thiểu cần cấp phát cho P1 5 trang thật thì việc nạp trang ảo ₫ể thực thi P1 mới hiệu quả nhất (số lần gây lỗi truy xuất trang thấp nhất = 6 lần). Ta nói việc cấp phát này là tối ưu, với ₫iều kiện là P1 chỉ tham khảo trang 5, không ghi nội dung vào trang 5, vì nếu ghi nội dung vào trang 5 thì hệ thống phải tốn nhiều thời gian ₫ể ghi nội dung trang 5 lên ₫ĩa trước khi dùng lại nó ₫ể chứa trang khác (trang 0), ₫iều này làm chậm việc thi hành P1 lại. 1.2 Câu hỏi 2 Miêu tả qui trình tiến triển của bảng quản lý trang và số lần lỗi truy xuất trang nếu hệ thống chỉ cấp phát cho P1 3 trang thật. Có tất cả 8 lần lỗi truy xuất trang như sau : 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 1 1 1 1 1 X 1 1 1 1 1 1 2 2 2 X 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 3 2 2 2 2 2 2 2 2 X 4 1 1 1 X 5 0 0 0 X D D D D D D D D 2. Giải thuật thây thế trang FIFO (First in - First out) Tinh thần của giải thuật này là mỗi lần có lỗi truy xuất trang, hệ thống tìm và giải phóng trang ₫ược nạp vào bộ nhớ thật cũ nhất (lâu nhất so với hiện tại). 2.1 Câu hỏi 3 Giả sử process P1 truy xuất bộ nhớ theo thứ tự các trang sau ₫ây : 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 Miêu tả qui trình tiến triển của bảng quản lý trang và số lần lỗi truy xuất trang nếu hệ thống chỉ cấp phát cho P1 3 trang thật. Có tất cả 12 lần lỗi truy xuất trang như sau :
2. Trang 4 4.1 Câu hỏi 5 Giả sử process P1 truy xuất bộ nhớ theo thứ tự các trang sau ₫ây : 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 Miêu tả qui trình tiến triển của bảng quản lý trang và số lần lỗi truy xuất trang nếu hệ thống chỉ cấp phát cho P1 3 trang thật. Có tất cả 10 lần lỗi truy xuất trang như sau : 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 5 0 1 2 0 3 0 4 2 3 0 3 2 1 5 0 1 2 2 3 0 4 2 2 0 3 3 D D D D D D D D D D 5. Giải thuật dùng Working set Working set là 1 chuỗi có thứ tự các hoạt ₫ộng truy xuất trang theo thời gian. Số trang trong working set thay ₫ổi theo chức năng truy xuất. Định kỳ, working set ₫ược cập nhật ₫ể chỉ giữ lại các trang ₫ược truy xuất trong khoảng thời gian gần nhất so với hiện tại. 5.1 Câu hỏi 6 Giả sử process P1 truy xuất bộ nhớ theo thứ tự các trang sau ₫ây : 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 Giả sử working set ₫ược cập nhật theo chu kỳ có 3 lần truy xuất bộ nhớ và ta chỉ giữ lại các trang ₫ược truy xuất trong 3 lần cuối. Miêu tả qui trình tiến triển của working set và số lần lỗi truy xuất trang. Có tất cả 9 lần lỗi truy xuất trang như sau : 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 5 0 1 2 0 3 0 4 2 3 0 3 2 1 5 0 1 2 3 0 4 2 0 3 5 1 2 3 0 4 2 0 3 5 2 4 0 5 D D D D D D D D D