3. Đổi trang

-Bộ nhớ ảo > bộ nhớ thực và chế độ đa chương trình -> có lúc không còn khung nào trống để nạp trang mới.

-Giải pháp:

+Kết thúc tiến trình.

+Trao đổi tiến trình ra đĩa và chờ thời điểm thuận lợi hơn.

+Đổi trang.

a. Thao tác đổi trang

-Nếu không còn khung nào trống, HDH chọn 1 khung đã cấp phát

và có thể thay đổi => cần có cơ chế biến đổi địa chỉ logic thành vật lý.

-Cấm truy cập trái phép: tiến trình này truy cập tới phần MEM của tiến trình khác nhưng hiện không dùng tới và giải phóng nó.

-Quá trình đổi trang:

+B1: Xác định trang cần nạp vào trên đĩa.

+B2: Nếu có khung trống thì chuyển sang B4.

+B3:

*Lựa chọn 1 khung để giải phóng, theo 1 thuật toán nào đó.

*Ghi nội dung khung bị đổi ra đĩa (nếu cần), cập nhật bảng trang và bảng khung.

+B4: Đọc trang cần nạp vào khung vừa giải phóng; cập nhật bảng trang và bảng khung.

+B5: Thực hiện tiếp tiến trình từ điểm bị dừng trước khi đổi trang.

-Đổi trang có ghi và đổi trang không ghi:

+Việc ghi trang bị đổi ra đĩa làm tăng đáng kể thời gian nạp trang.

+=> nhận biết các trang không thay đổi từ lúc nạp và không ghi ngược ra đĩa.

+Sử dụng thêm bit sửa đổi M trong khoản mục trang để đánh dấu trang đã bị sửa đổi (1) hay chưa (0).

-Các khung bị khóa

+Một số khung sẽ không bị giải phóng trong quá trình tìm kiếm khung để đổi trang => các khung bị khóa.

+VD: Khung chứa tiến trình nhân của HDH, chứa các cấu trúc thông tin điều khiển quan trọng.

+Nhận biết bởi 1 bit riêng chứa trong khoản mục.

b. Các chiến lược đổi trang

-Đổi trang tối ưu (OPT):

+Chọn trang sẽ không được dùng tới trong khoảng thời gian lâu nhất để đổi.

+Cho phép giảm tối thiểu sự kiện thiếu trang và do đó là tối ưu theo tiêu chuẩn này.

+HDH không đoán trước được nhu cầu sử dụng các trang trong tương lai.

+=> không áp dụng trong thực tế mà chỉ để so sánh với các chiến lược khác.

-Vào trước ra trước (FIFO):

+Trang nào được nạp vào trước thì bị đổi ra trước.

+Đơn giản nhất.

+Trang bị trao đổi là trang nằm lâu nhất trong bộ nhớ.

-Đổi trang ít sử dụng nhất trong thời gian cuối (LRU):

+Trang bị đổi là trang mà thời gian từ lần truy cập cuối cùng đến thời điểm hiện tại là lâu nhất.

+Theo nguyên tắc cục bộ về thời gian, đó chính là trang ít có khả năng sử dụng tới nhất trong tương lai.

+Thực tế LRU cho kết quả tốt gần như phương pháp đổi trang tối ưu.

-Đổi trang ít sử dụng nhất trong thời gian cuối (LRU):

+Xác định được 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?

+Sử dụng biến đếm:

*Mỗi khoản mục của bảng phân trang sẽ có thêm một trường chứa thời gian truy cập trang lần cuối - Là thời gian logic.

*CPU cũng được thêm một bộ đếm thời gian lôgic này.

*Chỉ số của bộ đếm tăng mỗi khi xảy ra truy cập bộ nhớ.

*Mỗi khi một trang nhớ được truy cập, chỉ số của bộ đếm sẽ được ghi vào trường thời gian truy cập trong khoản mục của trang đó.

*=> trường thời gian luôn chứa thời gian truy cập trang lần cuối.

*=> trang bị đổi là trang có giá trị thời gian nhỏ nhất.

+Sử dụng ngăn xếp:

*Ngăn xếp đặc biệt được sử dụng để chứa các số trang.

*Mỗi khi một trang nhớ được truy cập, số trang sẽ được chuyển lên đỉnh ngăn xếp.

*Đỉnh ngăn xếp sẽ chứa trang được truy cập gần đây nhất.

*Đáy ngăn xếp chính là trang LRU, tức là trang cần trao đổi.

*Tránh tìm kiếm trong bảng phân trang.

*Thích hợp thực hiện bằng phần mềm.

-Thuật toán đồng hồ (CLOCK):

+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ại 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.