주어진 페이지 번호와 페이지 크기 작업은 Optimal Page Replacement Algorithm을 사용하여 페이지에 메모리 블록을 할당할 때와 같이 적중 횟수와 누락 횟수를 찾는 것입니다.
최적 페이지 교체 알고리즘이란 무엇입니까?
최적 페이지 교체 알고리즘은 페이지 교체 알고리즘입니다. 페이지 교체 알고리즘은 교체될 메모리 페이지를 결정하는 알고리즘입니다. Optimal page replacement에서는 가까운 미래에 언급되지 않은 페이지를 교체하지만 실제로 구현할 수는 없지만 이것이 가장 최적이고 누락이 최소화되고 가장 최적입니다.
예를 들어 도식적으로 설명하면서 이해합시다.
여기에서 1, 2 및 3을 할당한 후 메모리가 가득 차서 4를 삽입하기 위해 1, 2 및 3에서 가까운 장래에 다시 참조되지 않는 페이지를 찾아 페이지 3이 가까운 미래가 아니므로 다음으로 교체합니다. 페이지를 새 페이지 4로 변경하는 식으로 마지막에 도달할 때까지 단계를 반복합니다.
예시
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 위의 문제를 해결하기 위해 사용하는 접근 방식 -
- 페이지의 입력을 배열로 취합니다.
- 할당된 페이지가 가까운 장래에 있는지 확인하고, 없으면 메모리에 있는 해당 페이지를 새 페이지로 교체합니다.
- 페이지에 이미 증분 히트가 있는 경우, 그렇지 않으면 증분 미스가 있습니다.
- 배열의 마지막 요소에 도달할 때까지 반복합니다.
- 적중률과 누락 횟수를 출력합니다.
알고리즘
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 예시
#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;
} 출력
Hits = 3 Misses = 10