- Khi tìm một phần tử có khoá key trong bảng băm, hàm băm h(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1, tìm phần tử khoá key trong bảng băm xuất phát từ địa chỉ i. Hàm băm lại lần i được biểu diễn bằng công thức sau: f(key)=(f(key)+i) %M với f(key) là hàm băm chính của bảng băm.
Các câu hỏi Chọn trang nạn nhân ? => Chiến lược thay trang Chọn trang để nạp ? => Chiến lược nạp Chiến lược thay trang FIFO: trang “già” Tần suất lỗi trang thấp Không khả thi ! LRU :trang lâu chưa sử dụng đến khứ add Công ? Không xét đến tính sủ dụng ! TỐI ƯU : trang lâu sử dụng đến tương lai victim Dự đoán tương lai LRU = MIN ? victim AGBDCABCABCGABC Cur page victim AGBDCABCABCGABC Cur page Chiến lược nạp Demand paging : nạp trang yêu cầu Khi ? Nạp sau : tần suất lỗi trang cao ? => pure demand paging Nạp trước : biết ? =>prepaging ld init pages ld page ld page ld page init pages = ? Thrashing = ảo tưởng sụp đổ ! Các tiến trình hệ thống yêu cầu nhớ nhiều khả cung cấp hệ thống ! P1 P2 P3 Real mem Tất tiến trình đầu bận rộn xử lý lỗi trang ! IO hoạt động 100 %, CPU rảnh ! Hệ thống ngừng trệ 10 Nguyên nhân Thrashing Tiến trình không tái sử dụng nhớ (quá khứ != tương lai) Tiến trình tái sử dụng nhớ, với kích thươc lớn Quá nhiều tiến trình hệ thống Chỉ kiểm soát thrashing nguyên nhân 11 Giải thrasing với mô hình Working set Working set = tập hợp trang tiến trình truy xuất thời điểm Hệ điều hành : Chỉ nạp tiến trình có đủ khung trang tự cho working set Kiểm soát mức độ đa chương hệ thống : Nếu tổng số khung trang yêu cầu tiến trình hệ thống vượt khung trang sử dụng, chọn tiến trình để tạm dừng, ngược lại, tổng working set bé số khung trang tự do, nạp thêm tiến trình 12 ... xuất thời điểm Hệ điều hành : Chỉ nạp tiến trình có đủ khung trang tự cho working set Kiểm soát mức độ đa chương hệ thống : Nếu tổng số khung trang yêu cầu tiến trình hệ thống vượt khung... đổ ! Các tiến trình hệ thống yêu cầu nhớ nhiều khả cung cấp hệ thống ! P1 P2 P3 Real mem Tất tiến trình đầu bận rộn xử lý lỗi trang ! IO hoạt động 100 %, CPU rảnh ! Hệ thống ngừng trệ 10... paging : nạp trang yêu cầu Khi ? Nạp sau : tần suất lỗi trang cao ? => pure demand paging Nạp trước : biết ? =>prepaging ld init pages ld page ld page ld page init pages = ? Thrashing = ảo