প্রদত্ত পৃষ্ঠা নম্বর এবং পৃষ্ঠার আকার; কাজটি হল হিট এবং মিসের সংখ্যা খুঁজে বের করা যেমন আমরা যখন অনুকূল পৃষ্ঠা প্রতিস্থাপন অ্যালগরিদম ব্যবহার করে একটি পৃষ্ঠায় মেমরি ব্লক বরাদ্দ করি।
অপ্টিমাল পেজ রিপ্লেসমেন্ট অ্যালগরিদম কি?
সর্বোত্তম পৃষ্ঠা প্রতিস্থাপন অ্যালগরিদম একটি পৃষ্ঠা প্রতিস্থাপন অ্যালগরিদম। একটি পৃষ্ঠা প্রতিস্থাপন অ্যালগরিদম হল একটি অ্যালগরিদম যা সিদ্ধান্ত নেয় কোন মেমরি পৃষ্ঠাটি প্রতিস্থাপন করা হবে। সর্বোত্তম পৃষ্ঠা প্রতিস্থাপনে আমরা সেই পৃষ্ঠাটিকে প্রতিস্থাপন করি যা নিকট ভবিষ্যতে উল্লেখ করা হয় না, যদিও এটি কার্যত বাস্তবায়িত করা যায় না, তবে এটি সবচেয়ে অনুকূল এবং সর্বনিম্ন মিস আছে এবং এটি সবচেয়ে অনুকূল৷
আসুন একটি উদাহরণ ব্যবহার করে এবং এটি চিত্রগতভাবে ব্যাখ্যা করে বুঝতে পারি।
এখানে 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
