সি++ প্রোগ্রাম: অপ্টিমাল পেজ রিপ্লেসমেন্ট অ্যালগরিদম

পেজ নম্বর এবং পেজ সাইজ দেওয়া আছে; কাজ হল অপ্টিমাল পেজ রিপ্লেসমেন্ট অ্যালগরিদম ব্যবহার করে মেমরি ব্লকে পেজ বরাদ্দ করার সময় হিট এবং মিসের সংখ্যা খুঁজে বের করা।

অপ্টিমাল পেজ রিপ্লেসমেন্ট অ্যালগরিদম কী?

অপ্টিমাল পেজ রিপ্লেসমেন্ট একটি পেজ রিপ্লেসমেন্ট অ্যালগরিদম। পেজ রিপ্লেসমেন্ট অ্যালগরিদম হল একটি অ্যালগরিদম যা সিদ্ধান্ত নেয় কোন মেমরি পেজটি রিপ্লেস করা হবে। অপ্টিমাল পেজ রিপ্লেসমেন্টে আমরা সে পেজটি রিপ্লেস করি যা নিকট ভবিষ্যতে রেফারেন্স করা হবে না। যদিও এটি ব্যবহারিকভাবে বাস্তবায়ন করা সম্ভব নয়, তবে এটি সবচেয়ে অপ্টিমাল এবং ন্যূনতম মিস রেট রাখে।

চলুন একটি উদাহরণ এবং ডায়াগ্রাম দিয়ে এটি বুঝি।

এখানে ১, ২ এবং ৩ বরাদ্দ করার পর মেমরি ফুল হয়ে যায়। এখন ৪ ইনসার্ট করার জন্য ১, ২ এবং ৩ থেকে সে পেজটি খুঁজে বের করব যা নিকট ভবিষ্যতে আর রেফারেন্স করা হবে না। তাই পেজ ৩ রিপ্লেস হয়ে নতুন পেজ ৪ আসে, এবং এই প্রক্রিয়া শেষ পর্যন্ত চলতে থাকে।

উদাহরণ

ইনপুট: page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }   fn=3
আউটপুট: Hits = 3   Misses = 10

ইনপুট: page[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 }   fn = 4
আউটপুট: Hits = 7   Misses = 6

সমাধানের পদ্ধতি

• পেজের অ্যারে ইনপুট হিসেবে নিন।
• বরাদ্দ করা পেজটি নিকট ভবিষ্যতে আছে কিনা চেক করুন। না থাকলে সেটি রিপ্লেস করে নতুন পেজ বসান।
• পেজ যদি ইতিমধ্যে মেমরিতে থাকে তবে হিট বাড়ান, নাহলে মিস বাড়ান।
• অ্যারেতে শেষ এলিমেন্ট পর্যন্ত এই প্রক্রিয়া दुহরান।
• হিট এবং মিসের সংখ্যা প্রিন্ট করুন।

অ্যালগরিদম

Start
Step 1→ ফাংশন int predict(int page[], vector& fr, int pn, int index) এ
    res = -1, farthest = index ডিক্লেয়ার ও ইনিশিয়ালাইজ করুন
    For i = 0; i < fr.size(); i++ লুপ
        For j = index; j < pn; j++ লুপ
            If fr[i] == page[j] হয়
                If j > farthest হয়
                    farthest = j, res = i সেট করুন
                Break করুন
            If j == pn হয়
                Return i
    Return (res == -1) ? 0 : res

Step 2→ ফাংশন bool search(int key, vector& fr) এ
    For i = 0; i < fr.size(); i++ লুপ
        If fr[i] == key হয় Return true
    Return false

Step 3→ ফাংশন void opr(int page[], int pn, int fn) এ
    vector fr ডিক্লেয়ার করুন
    hit = 0 সেট করুন
    For i = 0; i < pn; i++ লুপ
        If search(page[i], fr) হয়
            hit বাড়ান, continue করুন
        If fr.size() < fn হয়
            fr.push_back(page[i])
        Else
            j = predict(page, fr, pn, i + 1) সেট করুন
            fr[j] = page[i] সেট করুন
    হিট এবং মিসের সংখ্যা প্রিন্ট করুন

Step 4→ ফাংশন int main() এ
    page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 } ডিক্লেয়ার করুন
    pn = sizeof(page) / sizeof(page[0]) সেট করুন
    fn = 3 সেট করুন
    opr(page, pn, fn) কল করুন
Stop

সি++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int predict(int page[], vector& fr, int pn, int index) {
    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;
            }
        }
        if (j == pn)
            return i;
    }
    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++) {
        if (search(page[i], fr)) {
            hit++;
            continue;
        }
        if (fr.size() < fn)
            fr.push_back(page[i]);
        else {
            int j = predict(page, fr, pn, i + 1);
            fr[j] = page[i];
        }
    }
    cout << "Hits = " << hit << endl;
    cout << "Misses = " << pn - hit << endl;
}

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