ภาพรวมของอัลกอริทึม Optimal Page Replacement
อัลกอริทึมการแทนที่หน้าที่เหมาะสมที่สุด (Optimal Page Replacement Algorithm) เป็นอัลกอริทึมการแทนที่หน้าที่ตัดสินใจว่าจะแทนที่หน่วยความจำหน้าใด ในอัลกอริทึมนี้ เราจะแทนที่หน้าที่ไม่ได้ถูกอ้างอิงในอนาคตที่ใกล้ชิด แม้ว่าจะไม่สามารถนำไปใช้งานจริงได้ แต่เป็นอัลกอริทึมที่เหมาะสมที่สุดและมีจำนวน Miss น้อยที่สุด
ลองเข้าใจผ่านตัวอย่างและแผนภาพ:
หลังจากจัดสรร 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
แนวทางการแก้ปัญหา
- รับอินพุตของหน้าต่างๆ เป็นอาร์เรย์
- มองหาว่าหน้าที่จัดสรรอยู่ในอนาคตที่ใกล้ชิดหรือไม่ หากไม่ ให้แทนที่หน้านั้นในหน่วยความจำด้วยหน้าใหม่
- หากหน้ามีอยู่แล้ว ให้เพิ่ม Hit มิฉะนั้นเพิ่ม Miss
- ทำซ้ำจนถึงองค์ประกอบสุดท้ายของอาร์เรย์
- พิมพ์จำนวน Hits และ Misses
อัลกอริทึม
Start Step 1 → In function int predict(int page[], vector& 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 & 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 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
ตัวอย่างโค้ด C++
#include <bits/stdc++.h> using namespace std; int predict(int page[], vector& 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 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 & 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 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
