ডিমান্ড পেজিং

১ · ভার্চুয়াল মেমরি ও ডিমান্ড পেজিং কী

ভার্চুয়াল মেমরি (Virtual Memory)Virtual Memoryএকটি প্রসেসের লজিক্যাল অ্যাড্রেস স্পেসকে প্রকৃত ফিজিক্যাল মেমরির চেয়ে বড় হতে দেওয়ার কৌশল — বাকি অংশ ডিস্কে (swap space) থাকে। হলো এমন একটি কৌশল যা একটি প্রসেসের লজিক্যাল অ্যাড্রেস স্পেসকে কম্পিউটারে আসলে থাকা ফিজিক্যাল RAM-এর চেয়েও বড় হতে দেয়। M7-এর পেজিং (L29) আমাদের দেখিয়েছিল কীভাবে একটি প্রসেসের পেজগুলো ফিজিক্যাল ফ্রেমে ম্যাপ হয় — কিন্তু সেখানে ধরে নেওয়া হয়েছিল প্রসেসের সবগুলো পেজ একসাথে মেমরিতে থাকে। ভার্চুয়াল মেমরি এই ধারণা ভেঙে দেয়: যেকোনো মুহূর্তে শুধু প্রসেসটি এখন সক্রিয়ভাবে যা ব্যবহার করছে তা-ই মেমরিতে থাকা যথেষ্ট, বাকিটা ডিস্কের একটি সংরক্ষিত এলাকায় (swap space/page file) অপেক্ষা করে।

ডিমান্ড পেজিং (Demand Paging)Demand Pagingএকটি পেজ ডিস্ক থেকে ফিজিক্যাল মেমরিতে লোড হয় শুধু তখনই, যখন প্রসেস সেই পেজে প্রথমবার সত্যিকারের অ্যাক্সেস করে — আগে থেকে নয়। হলো ভার্চুয়াল মেমরি বাস্তবায়নের প্রধান কৌশল — "চাহিদা অনুযায়ী" পেজিং। একটি পেজ ডিস্ক থেকে মেমরিতে লোড হয় শুধু প্রথমবার সত্যিকারের অ্যাক্সেস হলে, প্রসেস শুরু হওয়ার সময় সবকিছু আগেভাগে (eagerly) লোড করে নয়। এর ফলে একটি প্রসেস দ্রুত শুরু হতে পারে (প্রথম কয়েকটি প্রয়োজনীয় পেজ ছাড়া আর কিছু লোড করার দরকার নেই) এবং যে পেজগুলো কখনোই ব্যবহৃত হয় না (যেমন একটি প্রোগ্রামের এরর-হ্যান্ডলিং কোড যা কখনো ট্রিগার হয় না) সেগুলো ডিস্ক থেকে মেমরিতে আনার খরচও লাগে না।

২ · Valid/Invalid বিট, পেজ ফল্ট (Page Fault) ও রিজিউম

ডিমান্ড পেজিং বাস্তবায়ন করতে প্রতিটি পেজ টেবিল এন্ট্রিতে একটি অতিরিক্ত valid/invalid বিট যোগ করা হয়। valid মানে পেজটি এখন সত্যিই কোনো ফিজিক্যাল ফ্রেমে আছে — MMU সরাসরি ফ্রেম নাম্বার পেয়ে যায় (L29/L31-এর স্বাভাবিক অনুবাদ)। invalid মানে পেজটি এখনো ডিস্কেই আছে, ফিজিক্যাল মেমরিতে আনা হয়নি।

যখন একটি প্রসেস একটি invalid পেজে অ্যাক্সেস করার চেষ্টা করে, হার্ডওয়্যার একটি পেজ ফল্ট (Page Fault)Page Faultএকটি ইনভ্যালিড (মেমরিতে অনুপস্থিত) পেজে অ্যাক্সেসের চেষ্টা — হার্ডওয়্যার OS-কে ট্র্যাপ করায়, যাতে OS পেজটি ডিস্ক থেকে লোড করে দেয়। তৈরি করে এবং OS-কে ট্র্যাপ করায়। তারপর OS নিচের ধাপগুলো অনুসরণ করে:

৩ · পেজ ফল্টের রেট ও প্রকৃত খরচ — Effective Access Time

পেজ ফল্ট কেন এত গুরুত্বপূর্ণ একটি বিষয়? কারণ একটি ফল্ট হ্যান্ডল করতে একটি ডিস্ক I/O লাগে — যা সাধারণ মেমরি অ্যাক্সেসের চেয়ে কয়েক হাজার থেকে কয়েক লক্ষ গুণ ধীর। এই বাস্তব খরচ গণনা করার একটি প্রমিত সূত্র হলো Effective Access Time (EAT) — যদি $p$ পেজ-ফল্ট রেট (০ থেকে ১-এর মধ্যে একটি ভগ্নাংশ), $ma$ সাধারণ মেমরি অ্যাক্সেস টাইম, এবং $fault\_time$ একটি ফল্ট হ্যান্ডল করতে যে সময় লাগে:

$$ EAT = (1-p) \times ma + p \times fault\_time $$

একটি বাস্তব উদাহরণ দেখা যাক: ধরা যাক সাধারণ মেমরি অ্যাক্সেস $ma = 100$ ন্যানোসেকেন্ড, একটি পেজ ফল্ট হ্যান্ডল করতে $fault\_time = 8{,}000{,}000$ ন্যানোসেকেন্ড (৮ মিলিসেকেন্ড, একটি ডিস্ক সিকের বাস্তবসম্মত মান) লাগে, এবং পেজ-ফল্ট রেট মাত্র $p = 0.001$ (অর্থাৎ প্রতি ১০০০ অ্যাক্সেসে গড়ে ১টি ফল্ট)। তাহলে —

$$ EAT = (0.999 \times 100) + (0.001 \times 8{,}000{,}000) = 99.9 + 8000 = 8099.9 \text{ ন্যানোসেকেন্ড} $$

৪ · সিমুলেশন: ডিমান্ড পেজিং বাস্তবে কীভাবে কাজ করে

নিচের কোড সেলে একটি ছোট্ট, বাস্তব ডিমান্ড-পেজিং সিমুলেশন — একটি পেজ টেবিল (valid/invalid এন্ট্রিসহ), একটি ফিজিক্যাল মেমরি (৪টি ফ্রেম) এবং একটি access_page() ফাংশন যা প্রতিটি অ্যাক্সেসে হিট না ফল্ট তা ঠিক করে, ফল্ট হলে প্রকৃতপক্ষে একটি ফ্রি ফ্রেমে পেজ "লোড" করে।

# ডিমান্ড পেজিং সিমুলেশন -- বাস্তব ডিস্ক/RAM নয়, শুধুই ধারণা বোঝানোর টয় ডেটা স্ট্রাকচার

NUM_FRAMES = 4

# page_table: page_number -> {"valid": bool, "frame": frame_number or None}
page_table = {}

# physical_memory: frame_number -> page_number (কোন ফ্রেমে এখন কোন পেজ আছে)
physical_memory = {}
free_frames = list(range(NUM_FRAMES))

fault_count = 0
hit_count = 0

def access_page(page_number, page_table, physical_memory, free_frames):
    global fault_count, hit_count
    entry = page_table.get(page_number, {"valid": False, "frame": None})

    if entry["valid"]:
        hit_count += 1
        print(f"পেজ {page_number}: HIT  (আগে থেকেই ফ্রেম {entry['frame']}-এ আছে)")
        return entry["frame"]

    # --- পেজ ফল্ট ---
    fault_count += 1
    if not free_frames:
        print(f"পেজ {page_number}: FAULT -> কিন্তু কোনো ফ্রি ফ্রেম নেই! "
              f"(কাকে সরানো হবে তা ঠিক করা page-replacement অ্যালগরিদমের কাজ -- দেখুন পরবর্তী পাঠ, L33)")
        return None

    frame = free_frames.pop(0)
    physical_memory[frame] = page_number
    page_table[page_number] = {"valid": True, "frame": frame}
    print(f"পেজ {page_number}: FAULT -> ডিস্ক থেকে লোড, ফ্রেম {frame}-এ বসানো হলো")
    return frame

# ৪টি ফ্রেম, কিন্তু মাত্র ৪টি ভিন্ন পেজ ব্যবহৃত হচ্ছে -- তাই কখনো রিপ্লেসমেন্টের দরকার হবে না
reference_sequence = [1, 2, 3, 1, 4, 2, 1, 3, 4, 2]

for pg in reference_sequence:
    access_page(pg, page_table, physical_memory, free_frames)

print("\n--- ফলাফল ---")
print("মোট অ্যাক্সেস:", len(reference_sequence))
print("পেজ ফল্ট:", fault_count)
print("পেজ হিট:", hit_count)
print(f"পেজ-ফল্ট রেট: {fault_count/len(reference_sequence):.2f}")