bảng trang tương ứng rồi đến bước 5Chuyển trang muốn truy xuất từ bộ nhớ phụ vào bộ nhớ chính : nạp trang cần truyxuất vào khung trang trống đã chọn (hay vừa mới làm trống ) ; cập nhật nội dungbảng trang, bảng khung trang tương ứng.Tái kích hoạt tiến trình người sử dụng.(Câu hỏi thêm ai là người quyết định thứ tự của các trang được thực hiện à User vìhọ chạy lệnh nào thì nó sẽ thực hiện trang đó, ví dụ vừa soạn thảo, sau đó phânkhung….)Câu 25: Đánh giá các thuật toán thay trang (Page Replacement) trong kỹthuật sử dụng Bộ nhớ ảo.Vấn đề chính khi thay thế trang là chọn lựa một trang « nạn nhân » để chuyển ra bộnhớ phụ. Có nhiều thuật toán thay thế trang khác nhau, nhưng tất cả cùng chungmột mục tiêu chọn trang « nạn nhân » là trang mà sau khi thaythế sẽ gây ra ít lỗitrang nhất. Có thể đánh giá hiệu qủa của một thuật toán bằng cách xử lý trên một chuỗi các địachỉ cần truy xuất và tính toán số lượng lỗi trang phát sinh.-FIFO : chọn các trang đã được nạp vào bộ nhớ trong lâu nhất để thaythế à thuật toán này dễ hiểu, dễ cài đặt . Tuy nhiên khi thực hiện không phảilúc nào cũng có kết qủa tốt: trang được chọn để thay thế có thể là trang chứanhiều dữ liệu cần thiết, thường xuyên được sử dụng nên được nạp sớm, dovậy khi bị chuyển ra bộ nhớphụ sẽ nhanh chóng gây ra lỗi trang cho nhữnglần truy xuất sau. Số lượng lỗi trang xảy ra sẽ tăng lên khi số lượng khungtrang sử dụng tăng. Hiện tượng này gọi là nghịch lý Belady.-OPT : thay thế trang sẽ lâu được sử dụng nhất trong tương laià thuậttoán này hoàn hảo về mặt ý tưởng nhưng không khả thi về mặt thực tế.Thuật toán này bảo đảm số lượng lỗi trang phát sinh là thấp nhất , nó cũngkhông gánh chịu nghịch lý Belady, tuy nhiên, đây là một thuật toán khôngkhả thi trong thực tế, vì không thể biết trước chuỗi truy xuất của tiến trìnhtrong tương lai!-LRU : thay thế trang lâu nhất trong bộ nhớ chưa được sử dụng à dùngquá khứ gần để đoán tương lai, FIFO để biết thời điểm nạp vào, tối ưu thờiđiểm sẽ truy cập, LRU đòi hỏi phần cứng phải hỗ trợ khá nhiều : biến bộđếm, stack.Câu 26: Nêu ngắn gọn các thuật toán Thay thế trang trong kỹ thuật bộ nhớảo, Trình bày và giải thích bằng ví dụ thuật toán FIFO.-Như trên-Ví dụ đại loại thế này-Câu 27: Nêu ngắn gọn các thuật toán Thay thế trang trong kỹ thuật bộ nhớảo, Trình bày và giải thích bằng ví dụ thuật toán Tối ưu OPT.-Như trên-Ví dụ đại loại như sau : Câu 28: Nêu ngắn gọn các thuật toán Thay thế trang trong kỹ thuật bộ nhớảo, Trình bày và giải thích bằng ví dụ thuật toán LRU.-Như trên-Ví dụCâu 29: Phân biệt hai hiện tượng phân mảnh nội (internal fragmentation) vàphân mảnh ngoài (external fragmentation), chúng xuất hiện khi nào và tạisao?-Phân mảnh ngoại (external fragmentation): là hiện tượng khi kích thướckhông gian nhớ còn trống đủ để thỏa mãn yêu cầu cấp phát nhưng không giannhớ này lại không liên tục. Hiện tượng phân mảnh ngoại xảy ra khi bạn thườngxuyên cấp phát vùng nhớ mới, sau đó xóa đi những phần vùng nhớ đã cấp phát mộtcáchkhôngthứtự.-Phân mảnh nội (internal fragmentation): là hiện tượng sẽ có vùng nhớ dư Upload your study docs or become a Course Hero member to access this document Upload your study docs or become a Course Hero member to access this document End of preview. Want to read all 28 pages? Upload your study docs or become a Course Hero member to access this document
Hình VIII‑6 giải thuật thay thế trang FIFO Giải thuật thay thế trang FIFO rất dễ hiểu và lập trình. Tuy nhiên, năng lực của nó không luôn tốt. Trang được cho để thay thế có thể là trang chức nhiều dữ liệu cần thiết, thường xuyên được sử dụng nên được nạp sớm, do vậy khi chuyển ra bộ nhớ phụ sẽ nhanh chóng gây ra lỗi trang. Để hiển thị các vấn đề có thể phát sinh với giải thuật thay thế trang FIFO, chúng ta xem xét chuỗi tham khảo sau: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Hình VIII-7 hiển thị đường cong lỗi trang khi so sánh với số khung sẳn dùng. Chúng ta chú ý rằng số lượng lỗi cho 4 khung (10) là lớn hơn số lượng lỗi cho 3 khung (9). Hầu hết các kết quả không mong đợi này được gọi là sự nghịch lý Belady; đối với một số giải thuật thay thế trang, tỉ lệ lỗi trang có thể tăng khi số lượng khung được cấp phát tăng. Chúng ta sẽ mong muốn rằng cho nhiều bộ nhớ hơn tới một quá trình sẽ cải tiến năng lực của nó. Trong một vài nghiên cứu trước đây, các nhà điều tra đã kết luận rằng giả thuyết này không luôn đúng. Sự không bình thường của Belady được phát hiện như là một kết quả.  Hình VIII‑7 Đường cong lỗi trang cho thay thế FIFO trên chuỗi tham khảo Thay thế trang tối ưu hoáKết quả phát hiện sự nghịch lý của Belady là tìm ra một giải thuật thay thế trang tối ưu. Giải thuật thay thế trang tối ưu có tỉ lệ lỗi trang thấp nhất trong tất cả các giải thuật và sẽ không bao giờ gặp phải sự nghịch lý của Belady. Giải thuật như thế tồn tại và được gọi là OPT hay MIN. Nó đơn giản là: thay thế trang mà nó không được dùng cho một khoảng thời gian lâu nhất. Sử dụng giải thuật thay thế trang đảm bảo tỉ lệ lỗi trang nhỏ nhất có thể cho một số lượng khung cố định. Thí dụ, trên một chuỗi tham khảo mẫu, giải thuật thay thế trang tối ưu sẽ phát sinh 9 lỗi trang, như được hiển thị trong hình VIII-8. 3 tham khảo đầu tiên gây ra lỗi điền vào 3 khung trống. Tham khảo tới trang 2 thay thế trang 7 vì 7 sẽ không được dùng cho tới khi tham khảo 18, trái lại trang 0 sẽ được dùng tại 5 và trang 1 tại 14. Tham khảo tới trang 3 thay thế trang 1 khi trang 1 sẽ là trang cuối cùng của 3 trang trong bộ nhớ được tham khảo lần nữa. Với chỉ 9 lỗi trang, thay thế tối ưu là tốt hơn nhiều giải thuật FIFO, có 15 lỗi. (Nếu chúng ta bỏ qua 3 lỗi đầu mà tất cả giải thuật phải gặp thì thay thế tối ưu tốt gấp 2 lần thay thế FIFO.) Thật vậy, không có giải thuật thay thế nào có thể xử lý chuỗi tham khảo trong 3 khung với ít hơn 9 lỗi. Tuy nhiên, giải thuật thay thế trang tối ưu là khó cài đặt vì nó yêu cầu kiến thức tương lai về chuỗi tham khảo. Do đó, giải thuật tối ưu được dùng chủ yếu cho nghiên cứu so sánh. Thí dụ, nó có thể có ích để biết rằng, mặc dù một giải thuật không tối ưu nhưng nó nằm trong 12.3% của tối ưu là tệ, và trong 4.7% là trung bình. Hình VIII‑8 giải thuật thay thế trang tối ưu Thay thế trang lruNếu giải thuật tối ưu là không khả thi, có lẽ một xấp xỉ giải thuật tối ưu là có thể. Sự khác biệt chủ yếu giữa giải thuật FIFO và OPT là FIFO dùng thời gian khi trang được mang vào bộ nhớ; giải thuật OPT dùng thời gian khi trang được sử dụng. Nếu chúng ta sẽ dụng quá khứ gần đây như một xấp xỉ của tương lai gần thì chúng ta sẽ thay thế trang mà nó không được dùng cho khoảng thời gian lâu nhất (hình VIII-9). Tiếp cận này là giải thuật ít được dùng gần đây nhất (least-recently-used (LRU) ). |
