Bài tập: Giả sử hệ điều
hành được cấp 5 khung nhớ vật lý, các trang của tiến trình được truy cập theo
thứ tự sau: 1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5. Hãy xác định thứ tự nạp vào đổi
trang sử dụng các thuật toán
1. Chiến lược đổi trang tối ưu
Với
chiến lược này, hệ điều hành sẽ chọn trang nhớ sẽ không được dùng tới trong thời
gian lâu nhất để trao đổi. Thực tế cần phải đoán trước nhu cầu sử dụng của các
trang trong tương lai, rất khó thực hiện nên chiến lực đổi trang tối ưu (OPT)
chỉ dùng để so sánh với chiến lược khác
Ban
đầu các khung đều trống nên chỉ cần đưa các trang lần lượt theo thứ tự vào, nếu
truy cập trang đã có thì không có biến đổi gì cả. Lần truy cập đầu tiên của
trang 6, ta sẽ xét tới trang 1 có thời gian sử dụng trong tương lai xa hiện tại
nhất (thực tế bài này, nó không còn được sử dụng nữa) nên sẽ được đổi ra đĩa. Tiếp
theo truy cập trang 7, thì trang số 2 có thời gian truy cập trong tương lai lâu
hơn nên bị đổi. Tương tự như vậy cho tới hết.
2. Chiến lược vào trước ra trước
(FIFO)
Là
chiến lược đơn giản nhất, vào bộ nhớ trước đổi ra trước khi có yêu cầu đổi
trang
Khi
cần truy cập tới trang 6, thực hiện đổi trang, dễ thấy trang 1 được truy cập
trước nên sẽ được đổi, tương tự truy cập trang 7 thì sẽ đổi trang 2, cứ như vậy
cho đến hết.
3. Chiến lược LRU – đổi trang ít sử dụng
nhất trong thời gian cuối
Dựa
trên nguyên tắc cục bộ về thời gian. Xác định trang có lần truy cập cuối diễn
ra cách thời điểm hiện tại lâu nhất
Trước
tiên, các khung nhớ đều trống việc truy cập các trang 1,2,3,4,5. Tới khi đổi
trang 6 không còn khung trống, sẽ xét tới trang số 1 có thời gian từ lần truy cập
cuối tới hiện tại là lâu nhất. Tiếp đến truy cập trang 7, dễ thấy trang 2 có thời
gian truy cập cuối tới hiện tại lâu nhất => đổi trang. Tương tự truy cập
trang số 8, trang số 3, 4 được truy cập gần đây hơn trang số 5 nên đổi trang 5
thành trang 8.
Thuật toán đồng hồ
Mỗi
trang được gắn thêm 1 bít sử dụng U (U =1 nếu được truy cập đọc/ghi)
Khi
có nhu cầu đổi trang, HĐH kiểm tra trang đang bị trỏ tới
·
U = 0: trang sẽ bị đổi
·
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ả trang đều =1 thì con trỏ sẽ quay đúng
1 vòng và đặt U = 0, trang hiện thời đang bị trỏ sẽ bị đổi
Mô
tả chi tiết thuật toán: Khi nạp các
trang đầu tiên, sau mỗi lần nạp trang, con trỏ sẽ di chuyển tới khung tiếp
theo. Khi trang số 6 được truy cập lần đầu, con trỏ đang ở vị trí trang số 1 và
tất cả trang đều có U = 1, do vậy con trỏ sẽ di chuyển đúng 1 vòng, xóa các bit
U về 0, quay lại vị trí cũ (trang 1), do vậy trang 1 bị đổi. Tiếp theo, khi
truy cập trang 7, con trỏ đang ở trang số 2 có U =0 nên trang 2 bị đổi. tương tự
như vậy, truy cập trang 8 thì trang số 3 bị đổi, trang số 9 thì trang số 4 bị đổi
(lưu ý: những trang đã có sẵn trong khung, U =1 thì không con trỏ không di chuyển,
nếu U = 0, con trỏ đang nằm ở đó thì chỉ đổi U =1, không dịch con trỏ).
Link
tải bài giải:https://1drv.ms/b/s!AuylDw0l1eP2hnqr-AlWnrgTwITP
0 Comments