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

# FIFO বনাম Optimal বনাম LRU -- একই রেফারেন্স স্ট্রিং ও ফ্রেম সংখ্যায় তিনটি বাস্তব অ্যালগরিদম

from collections import OrderedDict

# L33-এর সাথে অভিন্ন -- তুলনা যাতে ন্যায্য হয়
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 = []
    faults = 0
    for page in reference_string:
        if page in frames:
            continue
        faults += 1
        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
        faults += 1
        if len(frames) < num_frames:
            frames.append(page)
        else:
            future = reference_string[i + 1:]
            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


def lru(reference_string, num_frames):
    frames = OrderedDict()   # বাম প্রান্ত = সবচেয়ে কম-সাম্প্রতিক, ডান প্রান্ত = সবচেয়ে সাম্প্রতিক
    faults = 0
    for page in reference_string:
        if page in frames:
            frames.move_to_end(page)      # HIT -- সবচেয়ে সাম্প্রতিক হিসেবে চিহ্নিত করা হলো
            continue
        faults += 1                        # FAULT
        if len(frames) >= num_frames:
            frames.popitem(last=False)     # সবচেয়ে কম-সাম্প্রতিক পেজ সরানো হলো
        frames[page] = None
    return faults


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

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