Chuyển đổi địa chỉ:

Mỗi địa chỉ ảo là một bộ <s,d>:

số hiệu phân đoạn s : được sử dụng như chỉ mục đến bảng phân đoạn

địa chỉ tương đối d : có giá trị trong khoảng từ 0 đến giới hạn chiều dài của phân đoạn. Nếu địa chỉ tương đối hợp lệ, nó sẽ được cộng với giá trị chứa trong thanh ghi nền để phát sinh địa chỉ vật lý tương ứng.

First-fit: cấp phát phân đoạn tự do đầu tiên đủ lớn.

Best-fit: cấp phát phân đoạn tự do nhỏ nhất nhưng đủ lớn để thõa mãn nhu cầu.

Worst-fit: cấp phát phân đoạn tự do lớn nhất.

. Các thuật toán thay thế trang

II.2.1. Thuật toán FIFO

iếp cận: Ghi nhận thời điểm một trang được mang vào bộ nhớ chính. Khi cần thay thế trang, trang ở trong bộ nhớ lâu nhất sẽ được chọn

Ví dụ : sử dụng 3 khung trang , ban đầu cả 3 đều trống:

II.2.2. Thuật toán tối ưu

Tiếp cận: Thay thế trang sẽ lâu được sử dụng nhất trong tương lai.

Ví dụ : sử dụng 3 khung trang, khởi đầu đều trống:

.2.3. Thuật toán «Lâu nhất chưa sử dụng» ( Least-recently-used LRU)

Tiếp cận: Với mỗi trang, ghi nhận thời điểm cuối cùng trang được truy cập, trang được chọn để thay thế sẽ là trang lâu nhất chưa được truy xuất.

Ví dụ: sử dụng 3 khung trang, khởi đầu đều trống:

) Thuật toán « cơ hội thứ hai»

Tiếp cận: Sử dụng một bit reference duy nhất. Thuật toán cơ sở vẫn là FIFO, tuy nhiên khi chọn được một trang theo tiêu chuẩn FIFO, kiểm tra bit reference của trang đó:

Nếu giá trị của bit reference là 0, thay thế trang đã chọn.

Ngược lại, cho trang này một cơ hội thứ hai, và chọn trang FIFO tiếp theo.

Khi một trang được cho cơ hội thứ hai, giá trị của bit reference được đặt lại là 0, và thời điểm vào Ready List được cập nhật lại là thời điểm hiện tại.

Một trang đã được cho cơ hội thứ hai sẽ không bị thay thế trước khi hệ thống đã thay thế hết những trang khác. Hơn nữa, nếu trang thường xuyên được sử dụng, bit reference của nó sẽ duy trì được giá trị 1, và trang hầu như không bao giờ bị thay thế.

Thuật toán «cơ hội thứ hai» nâng cao (Not Recently Used - NRU)

Tiếp cận : xem các bit reference và dirty bit như một cặp có thứ tự.

Với hai bit này, có thể có 4 tổ hợp tạo thành 4 lớp sau:

(0,0) không truy xuất, không sửa đổi: đây là trang tốt nhất để thay thế.

(0,1) không truy xuất gần đây, nhưng đã bị sửa đổi: trường hợp này không thật tốt, vì trang cần được lưu trữ lại trước khi thay thế.

(1,0) được truy xuất gần đây, nhưng không bị sửa đổi: trang có thể nhanh chóng được tiếp tục được sử dụng.

(1,1) được truy xuất gần đây, và bị sửa đổi: trang có thể nhanh chóng được tiếp tục được sử dụng, và trước khi thay thế cần phải được lưu trữ lại.