Đã cho số trang và kích thước trang; nhiệm vụ là tìm số lần truy cập và số lần bỏ lỡ như khi chúng tôi phân bổ khối bộ nhớ cho một trang bằng Thuật toán Thay thế Trang Tối ưu.
Thuật toán thay thế trang tối ưu là gì?
Thuật toán thay thế trang tối ưu là một thuật toán thay thế trang. Thuật toán thay thế trang là một thuật toán quyết định trang bộ nhớ nào sẽ được thay thế. Trong Thay thế trang tối ưu, chúng tôi thay thế trang không được đề cập đến trong tương lai gần, mặc dù nó không thể được triển khai trên thực tế, nhưng đây là trang tối ưu nhất và ít bỏ sót nhất và là trang tối ưu nhất.
Hãy hiểu bằng cách sử dụng một ví dụ và giải thích nó theo sơ đồ.
Ở đây sau khi cấp phát 1, 2 và 3 bây giờ bộ nhớ đã đầy, vì vậy để chèn 4, chúng ta sẽ tìm kiếm trang không được giới thiệu nữa trong tương lai gần từ 1, 2 và 3 vì vậy trang 3 không có trong tương lai gần nên chúng ta thay thế trang đó. trang với trang 4 mới, và cứ tiếp tục như vậy, chúng tôi sẽ lặp lại các bước cho đến khi kết thúc.
Ví dụ
Input: page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
fn=3
Output: Hits = 3
Misses = 10
Input: page[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 }
fn = 4
Output: Hits = 7
Misses= 6 Phương pháp tiếp cận mà chúng tôi đang sử dụng để giải quyết vấn đề trên -
- Lấy đầu vào của các trang dưới dạng một mảng.
- Tìm kiếm trang được cấp phát hiện có trong tương lai gần, nếu không, hãy thay thế trang đó trong bộ nhớ bằng trang mới,
- Nếu trang đã có lượt truy cập gia số, thì lượt truy cập khác sẽ bị bỏ lỡ.
- Lặp lại cho đến khi chúng tôi đến phần tử cuối cùng của mảng.
- In số lần truy cập và số lần bỏ lỡ.
Thuật toán
Start
Step 1-> In function int predict(int page[], vector<int>& fr, int pn, int index)
Declare and initialize res = -1, farthest = index
Loop For i = 0 and i < fr.size() and i++
Loop For j = index and j < pn and j++
If fr[i] == page[j] then,
If j > farthest
Set farthest = j
End If
Set res = i
break
If j == pn then,
Return i
Return (res == -1) ? 0 : res
Step 2-> In function bool search(int key, vector<int>& fr)
Loop For i = 0 and i < fr.size() and i++
If fr[i] == key then,
Return true
Return false
Step 3-> In function void opr(int page[], int pn, int fn)
Declare vector<int> fr
Set hit = 0
Loop For i = 0 and i < pn and i++
If search(page[i], fr) then,
Increment hit by 1
continue
If fr.size() < fn then,
fr.push_back(page[i])
Else
Set j = predict(page, fr, pn, i + 1)
Set fr[j] = page[i]
Print the number of hits
Print the number of misses
Step 4-> In function int main()
Declare and assign page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
Set pn = sizeof(page) / sizeof(page[0])
Set fn = 3
opr(page, pn, fn)
Stop Ví dụ
#include <bits/stdc++.h>
using namespace std;
int predict(int page[], vector<int>& fr, int pn, int index) {
// Store the index of pages which are going
// to be used recently in future
int res = -1, farthest = index;
for (int i = 0; i < fr.size(); i++) {
int j;
for (j = index; j < pn; j++) {
if (fr[i] == page[j]) {
if (j > farthest) {
farthest = j;
res = i;
}
break;
}
}
// Return the page which are
// are never referenced in future,
if (j == pn)
return i;
}
// If all of the frames were not in future,
// return any of them, we return 0. Otherwise
// we return res.
return (res == -1) ? 0 : res;
}
bool search(int key, vector<int>& fr) {
for (int i = 0; i < fr.size(); i++)
if (fr[i] == key)
return true;
return false;
}
void opr(int page[], int pn, int fn) {
vector<int> fr;
int hit = 0;
for (int i = 0; i < pn; i++) {
// Page found in a frame : HIT
if (search(page[i], fr)) {
hit++;
continue;
}
//If a page not found in a frame : MISS
// check if there is space available in frames.
if (fr.size() < fn)
fr.push_back(page[i]);
// Find the page to be replaced.
else {
int j = predict(page, fr, pn, i + 1);
fr[j] = page[i];
}
}
cout << "Hits = " << hit << endl;
cout << "Misses = " << pn - hit << endl;
}
// main Function
int main() {
int page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 };
int pn = sizeof(page) / sizeof(page[0]);
int fn = 3;
opr(page, pn, fn);
return 0;
} Đầu ra
Hits = 3 Misses = 10