পেজ টেবিল স্ট্রাকচার — মাল্টিলেভেল ও TLB

১ · সমস্যা — একটি ফ্ল্যাট পেজ টেবিল স্কেল করে না

L29-এ আমরা একটি সরল, ফ্ল্যাট (single-level) পেজ টেবিল ব্যবহার করেছি — একটি সাধারণ dict, প্রতিটি পেজ নাম্বারের জন্য একটি এন্ট্রি। কিন্তু একটি বাস্তব ৩২-বিট বা ৬৪-বিট অ্যাড্রেস স্পেসে সম্ভাব্য পেজ নাম্বারের সংখ্যা কোটি কোটি হতে পারে — এবং প্রতিটি প্রসেসের নিজস্ব পেজ টেবিল লাগে। বেশিরভাগ প্রসেস তাদের সম্পূর্ণ সম্ভাব্য অ্যাড্রেস স্পেসের সামান্য অংশই ব্যবহার করে — তাই একটি সম্পূর্ণ ফ্ল্যাট টেবিল আগে থেকেই বরাদ্দ করা রাখলে বিশাল পরিমাণ মেমরি অপচয় হবে, প্রায় সবটাই অব্যবহৃত এন্ট্রির জন্য।

২ · মাল্টিলেভেল পেজ টেবিল — স্পার্স, লেজি বরাদ্দ

মাল্টিলেভেল পেজ টেবিলMultilevel (Hierarchical) Page Tableপেজ নাম্বারকে একাধিক অংশে ভেঙে ছোট পেজ টেবিলের একটি ট্রি (গাছ) তৈরি করার কৌশল — অব্যবহৃত অঞ্চলের জন্য কোনো ইনার টেবিল তৈরিই হয় না। এই সমস্যা সমাধান করে পেজ নাম্বারকে একাধিক অংশে ভেঙে — একটি আউটার টেবিল, যার প্রতিটি এন্ট্রি একটি ইনার পেজ টেবিলের দিকে নির্দেশ করে। গুরুত্বপূর্ণ অংশ — একটি ইনার টেবিল তখনই তৈরি হয় যখন সেই অঞ্চলের অন্তত একটি পেজ প্রথমবার ম্যাপ করা হয় (lazy creation) — যে অঞ্চল কখনো ব্যবহৃতই হয় না, তার জন্য কোনো মেমরিই খরচ হয় না। মূল্য — প্রতিটি ট্রান্সলেশনে এখন একাধিক ধাপে টেবিল "ওয়াক" করতে হয় (একটির বদলে দুই বা তিন ধাপ), সামান্য বেশি সময় লাগে প্রতি অ্যাক্সেসে, বিনিময়ে বিশাল জায়গা সাশ্রয় হয়।

৩ · TLB — অনুবাদ ক্যাশ করার হার্ডওয়্যার

মাল্টিলেভেল টেবিল ওয়াক করা এখনও একাধিক মেমরি অ্যাক্সেস লাগে (প্রতিটি স্তরের জন্য একটি) — প্রতিটি প্রোগ্রাম অ্যাক্সেসের জন্য এত কাজ করলে পুরো সিস্টেম ধীর হয়ে যেত। এখানেই আসে TLBTranslation Lookaside BufferCPU-এর কাছাকাছি বসানো একটি ছোট, অত্যন্ত দ্রুত হার্ডওয়্যার ক্যাশ যা সাম্প্রতিক পেজ-নাম্বার→ফ্রেম-নাম্বার ট্রান্সলেশন সংরক্ষণ করে — প্রতিটি মেমরি অ্যাক্সেসে সবার আগে চেক করা হয়। — CPU-এর কাছাকাছি বসানো একটি ছোট, অত্যন্ত দ্রুত হার্ডওয়্যার ক্যাশ। প্রতিটি মেমরি অ্যাক্সেসে প্রথমে TLB চেক করা হয় — TLB হিট হলে ফুল পেজ-টেবিল ওয়াক এড়িয়ে সরাসরি ফ্রেম নাম্বার পাওয়া যায়; শুধুমাত্র TLB মিস হলে ধীর, সম্পূর্ণ টেবিল-ওয়াক হয় — এবং তার ফলাফল পরবর্তীর জন্য TLB-তে ক্যাশ করে রাখা হয়। বাস্তব সিস্টেমে TLB হিট রেট অত্যন্ত গুরুত্বপূর্ণ — উচ্চ হিট রেট মানে বেশিরভাগ অ্যাক্সেসই ধীর টেবিল-ওয়াকের খরচ পুরোপুরি এড়িয়ে যায়।

৪ · বাস্তব বাস্তবায়ন — দুই-স্তরের পেজ টেবিল + TLB

নিচের কোড সেলে একটি দুই-স্তরের পেজ টেবিল (আউটার dict → ইনার dict, লেজি তৈরি) এবং একটি ছোট, সাইজ-সীমিত TLB (পূর্ণ হলে সবচেয়ে পুরনো এন্ট্রি সরিয়ে দেওয়া) সিমুলেট করা হয়েছে। একই কয়েকটি পেজের বারবার অ্যাক্সেস চালিয়ে হিট বনাম মিস গণনা করা হয়েছে।

# দুই-স্তরের পেজ টেবিল (lazy inner tables) + TLB (size-limited, oldest-evicted)
from collections import OrderedDict

outer_table = {}  # outer_index -> {inner_index: frame_number}

def map_page(outer_index, inner_index, frame_number):
    """একটি পেজ ম্যাপ করে -- ইনার টেবিল না থাকলে তখনই (lazily) তৈরি করে।"""
    if outer_index not in outer_table:
        outer_table[outer_index] = {}
    outer_table[outer_index][inner_index] = frame_number

def split_page_number(page_number):
    inner_index = page_number & 0xF        # নিচু ৪ বিট
    outer_index = (page_number >> 4) & 0xF  # পরের ৪ বিট
    return outer_index, inner_index

def page_table_walk(page_number):
    outer_index, inner_index = split_page_number(page_number)
    inner = outer_table.get(outer_index)
    if inner is None:
        return None  # এই অঞ্চলে কোনো ইনার টেবিলই তৈরি হয়নি
    return inner.get(inner_index)

TLB_MAX_SIZE = 3
tlb = OrderedDict()  # page_number -> frame_number, সবচেয়ে পুরনোটা সামনে
hits, misses = 0, 0

def access(page_number):
    global hits, misses
    if page_number in tlb:
        tlb.move_to_end(page_number)
        hits += 1
        return tlb[page_number], "TLB HIT"
    misses += 1
    frame = page_table_walk(page_number)
    if frame is None:
        return None, "পেজ ফল্ট (আনম্যাপড)"
    tlb[page_number] = frame
    if len(tlb) > TLB_MAX_SIZE:
        tlb.popitem(last=False)  # সবচেয়ে পুরনো এন্ট্রি সরানো
    return frame, "TLB MISS (পেজ টেবিল ওয়াক)"

# প্রাথমিক ম্যাপিং সেট আপ
map_page(0, 0, 5)
map_page(0, 1, 8)
map_page(0, 2, 2)
map_page(1, 0, 11)

sequence = [0, 1, 2, 0, 1, 16, 0, 2, 1]
for page_number in sequence:
    frame, status = access(page_number)
    print(f"পেজ {page_number:>2}: ফ্রেম={frame} | {status} | TLB={dict(tlb)}")

print(f"\nমোট হিট: {hits}, মোট মিস: {misses}")
print(f"হিট রেট: {hits / (hits + misses):.2%}")