Trình bày chiến lược đổi trang sử dụng thuật toán đồng hồ.

Cải tiến FIFO nhằm tránh thay những trang mặc dù đã được nạp vào lâu nhưng vẫn có khả năng sử dụng

- Mỗi trang được gắn thêm 1 bit sử dụng U

- Khi trang được truy cập đọc/ ghi: U = 1

=> ngay khi trang được đọc vào bộ nhớ: U =1

- Các khung có thể bị đổi (các trang tương ứng) được liên kết vào 1 danh sách vòng

- Khi một trang nào đó bị đổi, con trỏ được dịch chuyển để trỏ vào trang tiếp theo trong danh sách

Khi có nhu cầu đổi trang, HDH kiểm tra trang đang bị trỏ tới

- Nếu U=0: trang sẽ bị đổi ngay

- Nếu U=1: đặt U=0 và trỏ sang trang tiếp theo, lặp lại quá trình

Nếu U của tất cả các trang trong danh sách =1 thì con trỏ sẽ quay đúng 1 vòng, đặt U của tất cả các trang =0 và trang hiện thời đang bị trỏ sẽ bị đổi

Căn cứ vào 2 thông tin để đưa ra quyết định đổi trang:

- Thời gian trang được tải vào, thể hiện qua vị trí trang trong danh sách giống như FIFO

- Gần đây trang có được sử dụng hay không, thể hiện qua bit U

Việc kiểm tra thêm bit U tương tự việc cho trang thêm khả năng được giữ trong bộ nhớ

=> thuật toán cơ hội thứ 2

 Thuật toán đồng hồ cải tiến:

- Sử dụng thêm thông tin về việc nội dung trang có bị thay đổi hay không bằng bit M

- Kết hợp bit U và M, có 4 khả năng:

- U=0, M=0: trang gần đây không được truy cập và nội dung cũng không bị thay đổi, rất thích hợp để bị đổi ra ngoài

- U=0, M=1: trang có nội dung thay đổi nhưng gần đây không được truy cập, cũng là ứng viên để đổi ra ngoài

- U=1, M=0: trang mới được truy cập gần đây và do vậy  theo nguyên lý cục bộ về thời gian có thể sắp được truy cập tiếp

- U=1, M=1: trang có nội dung bị thay đổi và mới được truy cập gần đây, chưa thật thích hợp để đổi

Các bước thực hiện đổi trang:

- Bước 1:

- Bắt đầu từ vị trí hiện tại của con trỏ, kiểm tra các trang

- Trang đầu tiên có U=0 và M=0 sẽ bị đổi

- Chỉ kiểm tra mà không thay đổi nội dung bit U, bit M

- Bước 2:

- Nếu quay hết 1 vòng mà không tìm được trang có U và M bằng 0 thì quét l danh sách lần 2

- Trang đầu tiên có U=0, M=1 sẽ bị đổi

- Đặt bit U của những trang đã quét đến nhưng được bỏ qua là 0

- Nếu chưa tìm được thì lặp lại bước 1 và cả bước 2 nếu cần