পেজ রিপ্লেসমেন্ট অ্যালগরিদম — FIFO ও Optimal

১ · পেজ রিপ্লেসমেন্ট কেন দরকার

L32-এ আমরা দেখেছি ডিমান্ড পেজিং-এ একটি পেজ ফল্ট ঘটলে OS একটি ফ্রি ফ্রেম খুঁজে সেখানে পেজ লোড করে। কিন্তু বাস্তবে ফিজিক্যাল মেমরি সীমিত — একসময় সব ফ্রেম ভরে যায়। তখন নতুন একটি পেজ ফল্ট ঘটলে OS-কে একটি সিদ্ধান্ত নিতে হয়: বর্তমানে মেমরিতে থাকা কোন পেজটিকে সরিয়ে (evict) নতুন পেজের জন্য জায়গা করা হবে? এই সিদ্ধান্ত নেওয়ার নিয়মটাই পেজ রিপ্লেসমেন্ট অ্যালগরিদম (Page Replacement Algorithm)Page Replacement Algorithmমেমরি পূর্ণ থাকা অবস্থায় একটি নতুন পেজ ফল্ট হলে বর্তমানে মেমরিতে থাকা কোন পেজটি সরানো হবে তা ঠিক করার নিয়ম।। একটি খারাপ পছন্দ ভবিষ্যতে আরও বেশি পেজ ফল্ট ঘটাতে পারে — তাই এই অ্যালগরিদমগুলোর কার্যকারিতা সরাসরি সামগ্রিক সিস্টেম পারফরম্যান্সে প্রভাব ফেলে (সরাসরি L32-এর Effective Access Time আলোচনার সাথে যুক্ত)।

এই পাঠ ও পরের পাঠে (L34) আমরা একটি নির্দিষ্ট রেফারেন্স স্ট্রিং (পেজ অ্যাক্সেসের ক্রম) ও নির্দিষ্ট সংখ্যক ফ্রেম ব্যবহার করব যাতে তিনটি অ্যালগরিদমের (FIFO, Optimal, LRU) ফল্ট সংখ্যা সরাসরি তুলনাযোগ্য হয়।

২ · FIFO (First-In, First-Out)

FIFOFirst-In, First-Outযে পেজ সবচেয়ে বেশিদিন ধরে মেমরিতে আছে (সবার আগে ঢুকেছিল) তাকে সরিয়ে দেওয়ার নিয়ম, তার সাম্প্রতিক ব্যবহার বিবেচনা না করেই। হলো সবচেয়ে সরল রিপ্লেসমেন্ট অ্যালগরিদম — একটি সাধারণ queue দিয়েই বাস্তবায়ন করা যায়। যে পেজ সবার আগে মেমরিতে ঢুকেছিল, নতুন জায়গা দরকার হলে তাকেই সরানো হয় — সেই পেজ কতবার বা কত সম্প্রতি ব্যবহৃত হয়েছে তা একেবারেই বিবেচনা করা হয় না।

৩ · Optimal (OPT) — তাত্ত্বিক সেরা

Optimal (OPT)Optimal Page Replacementযে পেজ ভবিষ্যতে সবচেয়ে দেরিতে ব্যবহৃত হবে (বা আর কখনোই ব্যবহৃত হবে না) তাকে সরানোর নিয়ম — প্রমাণিতভাবে যেকোনো রেফারেন্স স্ট্রিং ও ফ্রেম সংখ্যার জন্য সর্বনিম্ন সম্ভাব্য ফল্ট দেয়। সরায় ঠিক সেই পেজ যেটি ভবিষ্যতে সবচেয়ে দূরে আবার ব্যবহৃত হবে — বা আর কখনোই ব্যবহৃত হবে না। এটি প্রমাণিতভাবে যেকোনো রেফারেন্স স্ট্রিং ও ফ্রেম সংখ্যার জন্য সর্বনিম্ন সম্ভাব্য পেজ-ফল্ট সংখ্যা দেয়। সমস্যা হলো — এটি বাস্তবায়ন করতে ভবিষ্যতের অ্যাক্সেস প্যাটার্ন আগে থেকে জানা লাগে, যা একটি সত্যিকারের চলমান সিস্টেমে অসম্ভব। তাই Optimal শুধু একটি তাত্ত্বিক বেঞ্চমার্ক হিসেবে ব্যবহৃত হয় — বাস্তব বাস্তবায়নযোগ্য অ্যালগরিদম (যেমন L34-এর LRU) ঠিক কতটা ভালো/খারাপ পারফর্ম করছে তা মাপার জন্য।

৪ · কোডে যাচাই: একই রেফারেন্স স্ট্রিং-এ FIFO বনাম Optimal

নিচের কোড সেলে FIFO এবং Optimal — দুটোই বাস্তব অ্যালগরিদম হিসেবে বাস্তবায়ন করা হয়েছে (হার্ডকোড করা ফলাফল নয়) এবং একই রেফারেন্স স্ট্রিং ও ৩টি ফ্রেমে চালানো হয়েছে — যাতে ফলাফল সরাসরি তুলনাযোগ্য হয়। এই ঠিক এই রেফারেন্স স্ট্রিং ও ফ্রেম সংখ্যা L34-এ LRU-এর সাথে তুলনার জন্যও ব্যবহৃত হবে।

# পেজ রিপ্লেসমেন্ট: FIFO ও Optimal -- বাস্তব অ্যালগরিদম, টয় রেফারেন্স স্ট্রিং-এর ওপর

# পুরো M8 জুড়ে একই রেফারেন্স স্ট্রিং ও ফ্রেম সংখ্যা ব্যবহার করা হবে (L34-এর LRU-এর সাথে তুলনার জন্য)
REFERENCE_STRING = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
NUM_FRAMES = 3


def fifo(reference_string, num_frames):
    frames = []          # queue -- সবচেয়ে পুরনো পেজ index 0-এ
    faults = 0
    for page in reference_string:
        if page in frames:
            continue      # HIT
        faults += 1        # FAULT
        if len(frames) < num_frames:
            frames.append(page)
        else:
            frames.pop(0)          # সবচেয়ে পুরনো পেজ সরানো হলো
            frames.append(page)
    return faults


def optimal(reference_string, num_frames):
    frames = []
    faults = 0
    n = len(reference_string)
    for i, page in enumerate(reference_string):
        if page in frames:
            continue      # HIT
        faults += 1        # FAULT
        if len(frames) < num_frames:
            frames.append(page)
        else:
            future = reference_string[i + 1:]
            # প্রতিটি resident পেজ ভবিষ্যতে কতদূরে আবার ব্যবহৃত হবে তা বের করা
            farthest_use, evict_idx = -1, 0
            for idx, resident_page in enumerate(frames):
                next_use = future.index(resident_page) if resident_page in future else n
                if next_use > farthest_use:
                    farthest_use, evict_idx = next_use, idx
            frames[evict_idx] = page   # সবচেয়ে দেরিতে/কখনো-না-ব্যবহৃত পেজ সরানো হলো
    return faults


fifo_faults = fifo(REFERENCE_STRING, NUM_FRAMES)
optimal_faults = optimal(REFERENCE_STRING, NUM_FRAMES)

print("রেফারেন্স স্ট্রিং:", REFERENCE_STRING)
print("ফ্রেম সংখ্যা:", NUM_FRAMES)
print()
print("FIFO    মোট পেজ ফল্ট:", fifo_faults)
print("Optimal মোট পেজ ফল্ট:", optimal_faults)
print()
if optimal_faults <= fifo_faults:
    print(f"যাচাই সফল -> Optimal ({optimal_faults}) <= FIFO ({fifo_faults})")
else:
    print("অপ্রত্যাশিত ফলাফল -- সংখ্যা পুনরায় যাচাই করুন")