Cho số trang và kích thước trang; nhiệm vụ là tìm số lần hit và miss khi cấp phát khối bộ nhớ cho trang bằng thuật toán thay thế trang Optimal.
Thuật toán thay thế trang Optimal là gì?
Thuật toán thay thế trang Optimal là một thuật toán thay thế trang. Thuật toán thay thế trang là thuật toán quyết định trang bộ nhớ nào sẽ bị thay thế. Trong Optimal page replacement, chúng ta thay thế trang không được tham chiếu trong tương lai gần, mặc dù không thể triển khai thực tế, nhưng đây là thuật toán tối ưu nhất và có miss tối thiểu.
Hãy hiểu qua ví dụ và giải thích bằng sơ đồ.
Ở đây sau khi cấp phát 1, 2 và 3, bộ nhớ đã đầy, nên để chèn 4, chúng ta sẽ tìm trang không được tham chiếu lại trong tương lai gần từ 1, 2 và 3. Trang 3 không nằm trong tương lai gần nên ta thay thế trang đó bằng trang mới 4, và lặp lại các bước cho đến khi hết mảng.
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 giải quyết:
- Nhập trang dưới dạng mảng.
- Tìm trang đã cấp phát có xuất hiện trong tương lai gần không, nếu không thì thay thế trang đó trong bộ nhớ bằng trang mới.
- Nếu trang đã có thì tăng hit, ngược lại tăng miss.
- Lặp lại cho đến khi đến phần tử cuối cùng của mảng.
- In số hit và miss.
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ụ mã nguồn
#include <bits/stdc++.h> using namespace std; int predict(int page[], vector<int>& fr, int pn, int index) { // Lưu chỉ số các trang sẽ được sử dụng gần đây trong tương lai 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; } } // Trả về trang không bao giờ được tham chiếu trong tương lai, if (j == pn) return i; } // Nếu tất cả các frame đều không ở trong tương lai, // trả về bất kỳ cái nào, ta trả về 0. Ngược lại // trả về 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++) { // Trang tìm thấy trong frame: HIT if (search(page[i], fr)) { hit++; continue; } // Nếu trang không tìm thấy trong frame: MISS // kiểm tra xem có không gian trống trong frames không. if (fr.size() < fn) fr.push_back(page[i]); // Tìm trang cần thay thế. 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; } Kết quả
Hits = 3 Misses = 10