Cấp độ khó Trung bình
Thường được hỏi trong đàn bà gan dạ Nhận thức thực tế thiết lập microsoft PayPal
Tag Hệ điều hành Lý thuyết
Các hệ điều hành hiện đại sử dụng phân trang để quản lý bộ nhớ và nhiều khi cần phải thay thế trang. Thay thế trang là quá trình thay thế một trang hiện có trong bộ nhớ bằng một trang cần thiết nhưng không có trong bộ nhớ. Tình trạng như vậy được gọi là Lỗi trang.
Mục tiêu của Thuật toán Thay thế Trang là giảm số lượng Lỗi Trang để tăng hiệu suất tổng thể. Có nhiều thuật toán để thay thế trang. Chúng tôi đang thảo luận về một số ở đây.
First In First Out [FIFO]
Vào trước ra trước Thuật toán thay thế trang là thuật toán đơn giản nhất để thay thế trang. Nó duy trì một hàng đợi để theo dõi tất cả các trang. Chúng tôi luôn thêm một trang mới vào cuối hàng đợi. Khi mà hàng đợi đã đầy và có Lỗi Trang, chúng tôi xóa trang hiện diện ở đầu hàng đợi và thêm một trang mới vào cuối hàng đợi.
Theo cách này, chúng tôi duy trì kỹ thuật nhập trước xuất trước, tức là trang nào được đưa vào bộ nhớ trước sẽ bị xóa khỏi bộ nhớ trước.
Ví dụ
Gọi chuỗi tham chiếu trang là {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1} và có tổng số 4 vị trí trang. Sau đó,
Sự bất thường của Belady
Belady đã chứng minh rằng có thể đối với một số chuỗi tham chiếu trang, việc tăng vị trí trang có thể dẫn đến số lỗi trang cao hơn.
Ví dụHãy xem xét chuỗi tham chiếu trang {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4} với 3 vị trí trang và 4 vị trí trang.Lỗi trang với 3 vị trí trang = 3
Lỗi trang với 4 vị trí trang = 4
Thay thế Trang Tối ưu
Thuật toán này nói rằng nếu chúng ta biết mình sẽ sử dụng trang nào trong tương lai thì chúng ta có thể tối ưu hóa kỹ thuật thay thế trang.
Theo thuật toán Thay thế Trang Tối ưu, việc thay thế trang sẽ được sử dụng ít nhất trong tương lai luôn là tối ưu.
Ví dụ
Gọi chuỗi tham chiếu trang là {2, 3, 4, 2, 1, 3, 7, 5, 4, 3} và có tổng cộng 3 vị trí trang. Sau đó,
Sử dụng nhất là gần đây
Thuật toán này dựa trên kỹ thuật bộ nhớ đệm. Thuật toán nói rằng hãy thay thế trang ít được sử dụng nhất trong thời gian gần đây.
Ví dụ
Gọi chuỗi tham chiếu trang là {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4} và có tổng số 3 vị trí trang. Sau đó,
Thực hiện trước ra trước
Mã Java cho các thuật toán thay thế trang trong hệ điều hành
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
class FirstInFirstOutPageReplacement {
private static int pageFaults[int[] pageString, int pageSlots] {
int faults = 0;
// Set to store the elements present in queue, used to check if a page is present or not
HashSet set = new HashSet[];
// Queue to maintain the order of insertion
Queue queue = new LinkedList[];
// traverse the page string
for [int i = 0; i < pageString.length; i++] {
// if there are some empty slots
if [queue.size[] < pageSlots] {
if [!set.contains[pageString[i]]] {
// and the current page is missing
// add the page to set
set.add[pageString[i]];
// add the page to queue
queue.add[pageString[i]];
// it is a page fault, increment faults
faults++;
}
} else {
// there are no empty slots and if current page is absent
if [!set.contains[pageString[i]]] {
// remove the first page in queue
int removedPage = queue.poll[];
// remove the page from set
set.remove[removedPage];
// add the new page to set
set.add[pageString[i]];
// add the new page to queue
queue.add[pageString[i]];
// it is page fault, increment faults
faults++;
}
}
}
// return total number of page faults
return faults;
}
public static void main[String[] args] {
// Example
int pageString[] = new int[] {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
int pageSlots = 4;
System.out.println[pageFaults[pageString, pageSlots]];
}
}Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 48
Mã C ++ cho các thuật toán thay thế trang trong hệ điều hành
#include
using namespace std;
int pageFaults[int *pageString, int pageSlots, int n] {
int faults = 0;
// Set to store the elements present in queue, used to check if a page is present or not
unordered_set set;
// Queue to maintain the order of insertion
queue q;
// traverse the page string
for [int i = 0; i < n; i++] {
// if there are some empty slots
if [q.size[] < pageSlots] {
if [set.find[pageString[i]] == set.end[]] {
// and the current page is missing
// add the page to set
set.insert[pageString[i]];
// add the page to queue
q.push[pageString[i]];
// it is a page fault, increment faults
faults++;
}
} else {
// there are no empty slots and if current page is absent
if [set.find[pageString[i]] == set.end[]] {
// remove the first page in queue
int removedPage = q.front[];
q.pop[];
// remove the page from set
set.erase[removedPage];
// add the new page to set
set.insert[pageString[i]];
// add the new page to queue
q.push[pageString[i]];
// it is page fault, increment faults
faults++;
}
}
}
return faults;
}
int main[] {
// Example
int pageString[] = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
int pageSlots = 4;
cout