กำหนดหมายเลขหน้าและขนาดหน้า ภารกิจคือการค้นหาจำนวนการเข้าชมและพลาดเหมือนกับเมื่อเราจัดสรรบล็อกหน่วยความจำไปยังหน้าโดยใช้อัลกอริธึมการเปลี่ยนหน้าที่เหมาะสมที่สุด
อัลกอริธึมการเปลี่ยนหน้าที่เหมาะสมที่สุดคืออะไร
อัลกอริธึมการแทนที่หน้าที่เหมาะสมที่สุดคืออัลกอริธึมการแทนที่หน้า อัลกอริธึมการแทนที่หน้าเป็นอัลกอริธึมที่ตัดสินใจว่าจะแทนที่หน้าหน่วยความจำใด ในการแทนที่หน้าที่เหมาะสมที่สุด เราจะแทนที่หน้าที่ไม่ได้อ้างถึงในอนาคตอันใกล้นี้ แม้ว่าจะใช้งานจริงไม่ได้ แต่ก็เป็นหน้าที่เหมาะสมที่สุดและมีข้อผิดพลาดน้อยที่สุด และเหมาะสมที่สุด
มาทำความเข้าใจโดยใช้ตัวอย่างและอธิบายเป็นแผนภาพ
ที่นี่หลังจากจัดสรร 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
