He Dieu Hanh
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.
Bạn đang đọc truyện trên: LoveTruyen.Me