Phân trang- FIFO, LRU, OPT

Phân trang- FIFO, LRU, OPT

I) Lý thuyết:

Page-replacement algorthm

-Chọn fram của process sẽ được thay thế trang nhớ

-Mục tiêu: số lương page-fault nhỏ nhất;

-Được đánh giá bằng cách thực thi giải thuật đói với mỗi chuỗi tham chiếu bộ nhớ( memory reference string) và xác định số lần xảy ra page fault.

Ví duï Thứ tự tham chiếu các địa chỉ nhớ,  với page size= 100:

 0100, 0432, 0101, 0612, 0102,

 0103, 0104, 0101, 0611, 0102,

 0103, 0104, 0101, 0610, 0102,

 0103, 0104, 0101, 0609, 0102,

 0105

các trang nhớ được tham chiếu lần lượt = chuổi tham chiếu bộ nhớ(trang nhớ)

1, 4, 1, 6, 1,

1, 1, 1, 6, 1,

1, 1, 1, 6, 1,

1, 1, 1, 6, 1,

1

II) Các giải thuật:

1. FIFO:

Cần biết được:- Số khung trang, tình trạng ban đầu, chuỗi tham chiếu.

Hướng tiế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, chuỗi tham chiếu: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

Ta có được bảng sau với * là các lỗi trang(page fault).

Mặc dù ban đầu trang là trống nhưng do 7 vân chưa có trong trang nhớ nên mặc định là lõi trang.

Lưu ý: Nghịc lý belady: Số lượng lỗi trang sẽ tăng lên mặc dù số khung trang sử dụng tăng lên.  

Ví dụ: Xét chuổi tham chiếu: 1.2.3.4.1.2.5.1.2.3.4.5

2. OPT:

Thay thế trang nhớ được tham chiếu trễ nhất trong tương lai.

Ưu điểm: ít xảy ra lỗi trang nhất.

Nhược điểm: Khó hiện thực được.

Ví dụ: cho chuỗi : 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

với 3 khung trang, ban đầu đều trống. 

3. LRU:

Thay thế trang nhớ được tham chiếu trễ nhất trong quá khứ.

Thuật toán FIFO sử dụng thời điểm nạp để chọn trang thay thế, thuật toán tối ưu lại dùng thời điểm trang sẽ được sử dụng, vì thời điểm này không thể xác định trước nên thuật toán LRU phải dùng thời điểm cuối cùng trang được truy xuất – dùng quá khứ gần để dự đoán tương lai. Thuật toán này đòi hỏi phải được cơ chế phần cứng hỗ trợ để xác định một thứ tự cho các trang theo thời điểm truy xuất cuối cùng.

Ví dụ: cho chuỗi : 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

Với 3 khung trang, ban đầu đều trống. 

Thêm 1 bài tập phân trang bằng LRU mà 1 bạn Công Bắc gửi về cho mình LRU.
Tổng kết: Trên đây là 3 giải thuật thay trang, cách thực hiện đơn giản, chỉ cần làm 2 bài là có thể nhuần nhuyễn rồi:). Có điều gì thắc mắc thì các bạn bình luận ở dưới trang hoặc gởi mail về cho mình thebienpronguyen2201@gmail.com

Chúc các bạn học tốt.