TLB & Page Walk — ভার্চুয়াল মেমরির হার্ডওয়্যার বাংলায় | পর্ব ৫০

Q: ৪ KiB page প্রায় চার দশক ধরে টিকে আছে, অথচ RAM হাজার গুণ বেড়েছে। বড় page সব জায়গায় কেন ব্যবহার হয় না?

Virtual memory-র ধারণা প্রথম বাস্তবে আসে ১৯৬০-এর দশকের শুরুতে Manchester বিশ্ববিদ্যালয়ের Atlas কম্পিউটারে, যেখানে ছোট core memory আর বড় drum-এর মধ্যে page স্বয়ংক্রিয়ভাবে আনা-নেওয়া হতো। পরের দশকগুলোতে page size যন্ত্রভেদে ভিন্ন ছিল — ১৯৭০-এর দশকের শেষে DEC-এর VAX ৫১২ byte-এর page ব্যবহার করত। ১৯৮৫ সালে Intel 80386 x86-এ paging আনে ৪ KiB page দিয়ে, আর x86-এর বিপুল software ভিত্তির কারণে সেই আকার কার্যত মান হয়ে যায়। RISC-V-ও ৪ KiB-কে মূল page হিসেবে বেছে নিয়েছে। বড় page-এর দাম কয়েকটি। প্রথম, internal fragmentation: একটি ছোট প্রোগ্রাম বা প্রতিটি thread-এর stack-ও অন্তত একটি পুরো page নেয়; ২ MiB page-এ হাজারো ছোট process-এ অনেক RAM নষ্ট। দ্বিতীয়, copy-on-write আর disk-এ আনা-নেওয়া: একটি byte বদলালে পুরো page কপি করতে বা লিখতে হয় — page যত বড়, কাজ তত বেশি। তৃতীয়, বড় একটানা aligned physical জায়গা খুঁজে পাওয়া কঠিন, বিশেষত যন্ত্র অনেকক্ষণ চলার পর মেমরি খণ্ডিত হলে।

Q: MIPS-এর মতো কিছু RISC নকশা TLB miss software-এ সামলাত, অথচ x86 আর আজকের বেশিরভাগ RISC-V core hardware walker রাখে। এই দুই দর্শনের পার্থক্য কী, আর পাল্লা কেন hardware-এর দিকে ঝুঁকল?

১৯৮০-এর দশকের RISC আন্দোলনের মূলমন্ত্র ছিল: hardware-এ শুধু সেটুকু রাখা, যা প্রতিটি cycle-এ লাগে; বাকিটা software-এর দায়িত্ব। MIPS-এর প্রথম দিকের chip-এ একটি ছোট fully associative TLB ছিল বলে জানা যায়, আর miss হলে একটি বিশেষ exception — OS-এর কয়েক ডজন instruction-এর একটি handler টেবিল খুঁজে বিশেষ instruction দিয়ে ঘর লিখত। লাভ: chip সরল, আর OS যেকোনো টেবিল-কাঠামো (multi-level, hashed, inverted) বেছে নিতে পারে। ১৯৯০-এর দশকে DEC Alpha একই ধারণা নেয়, তবে handler রাখে PALcode নামের একটি বিশেষ firmware স্তরে। কিন্তু সময়ের সাথে পাল্লা বদলাল। প্রথম, pipeline গভীর আর out-of-order হলো (পর্ব ৪০)। Exception মানে শত instruction-এর জানালা flush করা, তারপর handler চালানো, তারপর আবার ভরা — একটি miss-এর খরচ কয়েকশো cycle ছাড়িয়ে যায়। Hardware walker-এ miss হলে শুধু সেই load অপেক্ষা করে, বাকি স্বাধীন instruction চলতে থাকে, আর একাধিক walk একসাথে চলতে পারে।

Q: Virtual machine-এর জন্য hardware-এ nested paging আসার আগে hypervisor কীভাবে মেমরি অনুবাদ সামলাত, আর nested paging কোন নতুন সমস্যা তৈরি করল?

২০০০-এর দশকের শুরুতে x86-এ virtualization জনপ্রিয় হয়, কিন্তু MMU জানত শুধু একটি টেবিল। Hypervisor তাই একটি কৌশল নিত: অতিথি OS-এর টেবিলকে hardware-এ বসানো হতো না; তার বদলে hypervisor একটি “shadow page table” বানাত, যা অতিথির virtual ঠিকানাকে সরাসরি host-এর physical ঠিকানায় নেয়। অতিথির টেবিলের page গুলো write-protected রাখা হতো, যাতে অতিথি টেবিল বদলালে trap হয় আর hypervisor shadow টেবিল হালনাগাদ করে। TLB-র গতি native-এর মতো ছিল, কিন্তু অতিথির প্রতিটি page table বদল — process তৈরি, page fault, context switch — একটি দামি trap. Process-ভারী workload-এ এটি বড় বোঝা ছিল। ২০০৭–০৮ সালের দিকে AMD (NPT/RVI) আর Intel (EPT) hardware-এ দ্বিতীয় স্তরের অনুবাদ আনে বলে জানা যায়। এখন অতিথি নিজের টেবিল স্বাধীনভাবে বদলায়, কোনো trap ছাড়া; MMU দুটি টেবিল মিলিয়ে walk করে। কিন্তু অংশ ৮-এর হিসাব অনুযায়ী সবচেয়ে খারাপ ক্ষেত্রে একটি TLB miss-এ ২৪টি PTE পড়া — native-এর ৬ গুণ।

Q: L1 data cache বহু বছর ৩২ KiB-এ আটকে ছিল, অথচ L2 আর L3 অনেক বেড়েছে। VIPT-এর নিয়ম এর পেছনে কতটা দায়ী, আর নকশাকারেরা কীভাবে এই সীমা পেরোন?

L1-এর নকশায় সবচেয়ে বড় শত্রু সময়: load-to-use latency সাধারণত মাত্র কয়েক cycle, আর প্রতিটি বাড়তি cycle প্রায় প্রতিটি নির্ভরশীল instruction-কে দেরি করায়। TLB আর cache পরপর খুঁজলে (PIPT) সময় যোগ হয়, তাই L1 প্রায় সবসময় VIPT. অংশ ৭-এর নিয়ম তখন সরাসরি আকার বেঁধে দেয়: ৪ KiB page-এ প্রতি way সর্বোচ্চ ৪ KiB. ৩২ KiB পেতে 8-way — আর way বাড়ানো সস্তা নয়: প্রতিটি way-এর জন্য একটি tag comparator, বেশি তার, বেশি শক্তি, আর ধীর বাছাই (mux). অনেক প্রজন্মের x86 core-এ ৩২ KiB 8-way L1 data cache এই ভারসাম্যের ফল বলে ব্যাপকভাবে ব্যাখ্যা করা হয়। সীমা পেরোনোর পথ কয়েকটি। প্রথম, আরও way: প্রকাশিত তথ্য অনুযায়ী সাম্প্রতিক কিছু x86 core ৪৮ KiB 12-way L1 data cache ব্যবহার করে — প্রতি way আবার ঠিক ৪ KiB. দ্বিতীয়, বড় page: কিছু ARM-ভিত্তিক প্ল্যাটফর্মের ১৬ KiB page-এ 8-way VIPT ১২৮ KiB পর্যন্ত যেতে পারে, আর এমন বড় L1 data cache-এর কথা প্রকাশিত বিশ্লেষণে এসেছে।

Q: Cache-এর জন্য hardware coherence আছে, কিন্তু TLB-র জন্য সাধারণত OS-কে shootdown করতে হয়। কেন এই পার্থক্য, আর বহু core-এর যুগে এর দাম কী?

Cache coherence (পর্ব ৫৩) নিশ্চিত করে যে একটি core মেমরিতে লিখলে অন্য core-এর cache-এ সেই line-এর পুরোনো কপি বাতিল হয়। Page table-ও মেমরিতে থাকে, তাই PTE-র লেখা অন্য core-এর data cache -এ ঠিকই পৌঁছায়। কিন্তু TLB হলো PTE-র একটি অনুবাদিত, প্রক্রিয়াজাত কপি — কোন physical ঠিকানার PTE থেকে কোন TLB ঘর এসেছে, তা TLB সাধারণত মনে রাখে না, আর walk-এর মাঝের স্তরগুলো page-walk cache-এ ছড়িয়ে থাকে। প্রতিটি TLB ঘরকে coherence-এর snoop-এ যুক্ত করা জায়গা আর শক্তিতে দামি, তাই বেশিরভাগ ISA দায়িত্ব দিয়েছে software-কে: PTE বদলে স্পষ্ট নির্দেশ দিয়ে TLB বাতিল করা — RISC-V-এ sfence.vma , x86-এ invlpg . একটি core-এ এটি সস্তা। কিন্তু একটি process-এর thread যদি ৬৪টি core-এ চলে, আর একটি thread একটি মেমরি অংশ ফেরত দেয়, তাহলে বাকি ৬৩টি core-কে জানাতে হবে। x86-এ এর জন্য inter-processor interrupt: প্রতিটি core কাজ থামিয়ে handler চালায়, ঘর বাতিল করে, উত্তর দেয়, আর পাঠানো core সবার উত্তরের জন্য অপেক্ষা করে।

এক নজরে · TL;DR

MMU প্রতিটি ঠিকানা অনুবাদ করে: প্রোগ্রামের virtual ঠিকানা ভাগ হয় VPN আর offset-এ; hardware VPN-কে PPN-এ বদলায়, offset অপরিবর্তিত থাকে, আর একই সাথে অনুমতি (পড়া, লেখা, চালানো, user) যাচাই করে।
Page table গাছের মতো, কয়েক স্তরে: ৩২-bit-এ এক স্তরের টেবিল প্রতি process-এ ৪ MiB, ৬৪-bit-এ অসম্ভব বড়। তাই RISC-V Sv32-এ ২ স্তর (10 | 10 | 12), Sv39-এ ৩ স্তর (9 | 9 | 9 | 12), x86-64-এ ৪ বা ৫ স্তর — শুধু ব্যবহৃত অংশের টেবিল থাকে।
Page walk দামি, তাই TLB: TLB miss হলে hardware walker প্রতি স্তরে একটি করে PTE পড়ে (Sv39-এ ৩টি)। TLB কয়েক ডজন থেকে কয়েক হাজার অনুবাদ রাখে; TLB reach = entry × page size, আর superpage (২ MiB, ১ GiB) reach বহু গুণ বাড়ায়। ASID থাকলে context switch-এ TLB মুছতে হয় না।
Cache-এর সাথে মিলন: L1 cache সাধারণত VIPT — index আসে page offset থেকে, তাই TLB আর cache একসাথে খোঁজা যায়। শর্ত: cache-এর আকার ≤ way × page size (৩২ KiB 8-way, ৪ KiB page — ঠিক সীমায়)।
Virtualization-এ দ্বিমাত্রিক walk: অতিথি আর host দুই স্তরের ৪-level টেবিলে একটি TLB miss সবচেয়ে খারাপ ক্ষেত্রে ২৪টি PTE পড়ে — তাই বড় TLB, page-walk cache আর huge page সেখানে আরও জরুরি।

এই পর্বে যা শিখবেন

MMU-র কাজ, virtual ঠিকানার VPN-offset ভাগ, আর এক স্তরের page table কেন অচল — পূর্ণ হিসাবসহ
RISC-V Sv32 আর Sv39-এর PTE-র প্রতিটি বিট, satp register, আর hex-এ লেখা একটি PTE হাতে decode করা
Hardware page walk ধাপে ধাপে, superpage, A/D বিট আর page fault কখন ওঠে — চালানো যায় এমন walker দিয়ে
TLB-র গঠন, TLB reach, miss সামলানোর দুই পথ, ASID আর TLB shootdown; নিজের হাতে TLB-র প্রভাব মাপা
PIPT, VIPT, VIVT cache, synonym সমস্যা, VIPT-এর আকারের সীমা, effective access time আর nested paging-এর হিসাব

১ · কেন virtual memory, আর MMU-র কাজ কী

Operating System কোর্সে (Paging, Virtual memory) আপনি দেখেছেন software-এর দিক: OS কীভাবে page বরাদ্দ করে, page fault সামলায়, কোন page বাদ দেয়। এই পর্বে আমরা দেখব সেই ব্যবস্থার নিচের hardware: প্রতিটি load, store আর instruction fetch-এ CPU-র ভেতরে কী ঘটে, কত cycle লাগে, আর নকশাকারেরা কোন কোন কৌশলে খরচটা প্রায় শূন্যে নামিয়ে আনেন।

আগে চারটি কারণ সংক্ষেপে মনে করি। Virtual memory-তে প্রতিটি process ভাবে, পুরো ঠিকানা-জগৎ (address space) তার একার।

বিচ্ছিন্নতা (isolation): এক process অন্যের বা kernel-এর মেমরি ছুঁতে পারে না — hardware প্রতিটি প্রবেশে অনুমতি যাচাই করে।
স্থানান্তর (relocation): প্রোগ্রাম সবসময় একই virtual ঠিকানায় চলে, RAM-এর যেখানেই থাকুক।
RAM-এর চেয়ে বড় জগৎ: যে page এখন দরকার নেই, তা disk-এ থাকতে পারে; ছুঁলে page fault, OS এনে দেয়।
ভাগাভাগি (sharing): একই library-র কোড বহু process-এর page table-এ একই physical frame দেখায়।

এই চারটির সবই একটি hardware অংশের ওপর দাঁড়িয়ে: MMU (memory management unit). CPU যে ঠিকানা তৈরি করে, তা virtual ঠিকানা; RAM যে ঠিকানা বোঝে, তা physical ঠিকানা. MMU-র কাজ প্রতিটি প্রবেশে প্রথমটিকে দ্বিতীয়টিতে বদলানো, আর একই সাথে অনুমতি দেখা। Page table থাকে মেমরিতে, OS তা লেখে; MMU শুধু পড়ে (A/D বিট ছাড়া, অংশ ৫-এ)।

মহল্লার গলি আর বাড়ির নম্বর ভাবুন। চিঠিতে লেখা “রোড ৭, বাড়ি ১২” — এটি virtual ঠিকানা, প্রেরকের কাছে স্থায়ী। ডাকঘরের একটি খাতায় লেখা আছে, রোড ৭ আসলে এখন কোন নতুন এলাকার কোন প্লট (physical frame). ডাকপিয়ন রোডের নম্বর খাতায় মিলিয়ে নতুন প্লট বের করেন, কিন্তু “বাড়ি ১২”-এর অংশটি বদলান না — প্লটের ভেতরে বাড়ির ক্রম একই। খাতায় পাশে লেখা থাকে “এই রোডে শুধু সরকারি চিঠি” — অনুমতির বিট। আর ডাকপিয়ন বুদ্ধিমান: সম্প্রতি দেখা কয়েকটি রোডের অনুবাদ নিজের পকেটের চিরকুটে লিখে রাখেন, যাতে প্রতিবার খাতা খুলতে না হয় — সেটিই TLB.

ঠিকানার দুই ভাগ — VPN আর offset

মেমরি ভাগ হয় সমান মাপের page-এ; এই মডিউলের সব উদাহরণে page = ৪ KiB = 2¹² byte. তাই virtual ঠিকানার নিচের ১২টি বিট হলো page offset — page-এর ভেতরে কোন byte. বাকি ওপরের বিটগুলো VPN (virtual page number). অনুবাদে VPN বদলে হয় PPN (physical page number, যাকে frame number-ও বলে), আর offset হুবহু যায়:

VA = | VPN | offset (12 bit) | → MMU → PA = | PPN | offset (12 bit) |

উদাহরণ: ৩২-bit VA 0x12345678, ৪ KiB page. Offset = নিচের ৩টি hex অঙ্ক = 0x678; VPN = 0x12345. Page table যদি বলে VPN 0x12345 → PPN 0x00ABC, তাহলে PA = 0x00ABC678. লক্ষ করুন, hex-এর প্রতিটি অঙ্ক ৪ বিট, তাই ১২ বিটের offset মানে ঠিক ৩টি অঙ্ক — পরীক্ষায় এটিই সবচেয়ে দ্রুত পথ।

ছবি ৫০.১ — প্রতিটি মেমরি-প্রবেশ আগে MMU পেরোয়। TLB hit হলে অনুবাদ প্রায় বিনা খরচে; miss হলে walker মেমরি থেকে page table পড়ে।

২ · এক স্তরের page table কেন অচল — আকারের হিসাব

সবচেয়ে সরল নকশা: একটি বড় array, যার index VPN, আর প্রতিটি ঘরে একটি page table entry (PTE). MMU শুধু ভিত্তি + VPN × PTE-র আকার ঠিকানা থেকে একটি PTE পড়ে। দ্রুত, কিন্তু আকার দেখুন:

এক স্তরের টেবিলের আকার = 2^{(VA bit − offset bit)} × PTE-র আকার

৩২-bit VA, ৪ KiB page, ৪ byte PTE: VPN = ৩২ − ১২ = ২০ বিট → 2²⁰ = ১০,৪৮,৫৭৬টি ঘর × ৪ byte = ৪ MiB প্রতি process. ১০০টি process মানে ৪০০ MiB শুধু টেবিলে — অথচ বেশিরভাগ ঘর খালি, কারণ সাধারণ প্রোগ্রাম ঠিকানা-জগতের খুব সামান্য অংশ ব্যবহার করে।
Sv39 (৩৯-bit VA), ৮ byte PTE: 2²⁷ × ৮ = ১ GiB প্রতি process.
৪৮-bit VA (x86-64-এর ৪ স্তর): 2³⁶ × ৮ = ৫১২ GiB.
পূর্ণ ৬৪-bit: 2⁵² × ৮ = ৩২ PiB — পৃথিবীর কোনো যন্ত্রে এত RAM নেই।

সমাধান: টেবিলকেও page-এ ভাগ করা, আর শুধু যে অংশ ব্যবহৃত, সেটুকুর টেবিল রাখা — multi-level page table. VPN কয়েক টুকরোয় ভাগ হয়; প্রথম টুকরো দিয়ে মূল (root) টেবিলে একটি ঘর, সেই ঘর বলে পরের স্তরের টেবিল কোথায়; শেষ স্তরের ঘরে আসল PPN. কোনো অংশের ঠিকানা ব্যবহারই না হলে ওপরের স্তরের ঘরটি “অবৈধ” — নিচের পুরো টেবিলই থাকে না। এটি একটি radix tree, আর প্রতিটি নোড ঠিক একটি page.

লাইব্রেরির ক্যাটালগ ভাবুন। এক স্তরের নকশা মানে প্রতিটি সম্ভাব্য বইয়ের নম্বরের জন্য একটি কার্ড, বই থাকুক বা না থাকুক — লক্ষ লক্ষ খালি কার্ড। বহু-স্তরের নকশা মানে প্রথমে একটি তাক-সূচি (“৫০০–৫৯৯: বিজ্ঞান, আলমারি ৩”), তারপর সেই আলমারির ভেতরে আলাদা সূচি। যে বিভাগের কোনো বই নেই, তার আলমারি-সূচি ছাপানোই হয় না। দাম একটাই: একটি বই খুঁজতে কয়েকটি সূচি পরপর দেখতে হয়।

Page table-এর বিভিন্ন ধরন (hashed, inverted) আর OS-এর দিক থেকে multi-level টেবিলের বিস্তারিত OS কোর্সের Multilevel page table অংশে আছে। এখানে আমরা দেখব একটি বাস্তব ISA ঠিক কোন বিন্যাস বেঁধে দেয়, যাতে hardware নিজে টেবিল পড়তে পারে।

৩ · RISC-V Sv32 — দুই স্তর, PTE-র বিট আর `satp`

RISC-V-এর privileged specification কয়েকটি page table বিন্যাস সংজ্ঞায়িত করে। ৩২-bit RV32-এর জন্য Sv32: VA ৩২ বিট, ভাগ 10 | 10 | 12. VPN[1] (বিট ৩১–২২) root টেবিলের index, VPN[0] (বিট ২১–১২) দ্বিতীয় স্তরের index, বাকি ১২ বিট offset. প্রতিটি PTE ৪ byte, তাই প্রতিটি টেবিলে 2¹⁰ = ১০২৪টি ঘর × ৪ = ঠিক ৪ KiB — একটি page. এটি ইচ্ছাকৃত নকশা: টেবিলও সাধারণ page-এর মতো বরাদ্দ করা যায়।

PTE-র ভেতরে — বিট ধরে ধরে

বিট	নাম	অর্থ
31–20	PPN[1] (১২ বিট)	মোট ২২ বিটের PPN → physical ঠিকানা ২২ + ১২ = ৩৪ বিট (১৬ GiB পর্যন্ত)
19–10	PPN[0] (১০ বিট)
9–8	RSW	OS-এর নিজের ব্যবহারের জন্য সংরক্ষিত; hardware উপেক্ষা করে
7	D (dirty)	এই page-এ লেখা হয়েছে
6	A (accessed)	এই page পড়া, লেখা বা চালানো হয়েছে
5	G (global)	সব address space-এ একই map (সাধারণত kernel) — TLB-তে ASID নির্বিশেষে মেলে
4	U (user)	user mode এই page ছুঁতে পারে
3	X	instruction fetch চলবে
2	W	লেখা চলবে
1	R	পড়া চলবে
0	V (valid)	এই ঘর বৈধ; ০ হলে বাকি সব বিট অর্থহীন

একটি সূক্ষ্ম নিয়ম মনে রাখুন: R, W, X তিনটিই ০ হলে ঘরটি leaf নয় — এটি পরের স্তরের টেবিলের pointer. R বা X-এর যেকোনো একটি ১ হলে ঘরটি leaf, অর্থাৎ আসল অনুবাদ। আর W = 1 কিন্তু R = 0 সংরক্ষিত সমন্বয় — hardware এমন ঘর পেলে page fault তোলে। এক বিটের এই কৌশলে আলাদা “এটি leaf কি না” বিট লাগে না।

হাতে-কলমে: hex-এ একটি PTE decode করা

ধরা যাক একটি Sv32 leaf PTE = 0x200040D7. ধাপে ধাপে:

নিচের ৮ বিট: 0xD7 = 1101 0111. বিট ০ থেকে পড়ুন: V=1, R=1, W=1, X=0, U=1, G=0, A=1, D=1. অর্থাৎ বৈধ, পড়া-লেখা যায়, চালানো যায় না, user-এর page, আগে ছোঁয়া হয়েছে আর লেখা হয়েছে।
বিট ৯–৮ (RSW): 0x0D7-এর ওপরের দুটি বিট = ০।
PPN = PTE ডানে ১০ বিট সরিয়ে: 0x200040D7 >> 10 = 0x80010. ভাগ করলে PPN[1] = 0x200, PPN[0] = 0x010.
Page-এর physical ভিত্তি = PPN × 4096 = 0x80010000. VA-র offset যদি 0xABC হয়, PA = 0x80010ABC.

প্রচলিত ভুল: PPN পেতে PTE-কে ১২ বিট ডানে সরানো। PTE-তে PPN শুরু হয় বিট ১০ থেকে, ১২ থেকে নয় (নিচের ১০টি বিট flag আর RSW). তাই আগে ১০ বিট ডানে, তারপর ১২ বিট বাঁয়ে — অর্থাৎ PA-র ভিত্তি = (PTE >> 10) << 12. x86-এর PTE-তে frame-এর ঠিকানা বিট ১২ থেকে শুরু হয়, তাই দুই ISA গুলিয়ে ফেললে এই ভুল হয়।

`satp` — টেবিলের মূল কোথায়

MMU-কে root টেবিলের ঠিকানা জানায় একটি CSR: satp (supervisor address translation and protection). Sv32-এ এর বিন্যাস: বিট ৩১ MODE (১ = Sv32 চালু, ০ = অনুবাদ বন্ধ), বিট ৩০–২২ ASID (৯ বিট), বিট ২১–০ root টেবিলের PPN. Context switch-এ OS শুধু satp-এ নতুন process-এর root PPN আর ASID লেখে — পুরো ঠিকানা-জগৎ বদলে যায় একটি instruction-এ (x86-এ একই কাজের register CR3). অনুবাদ চলে S-mode আর U-mode-এ; M-mode-এ (পর্ব ৩৮-এর privilege স্তর) সাধারণত অনুবাদ থাকে না।

৪ · Sv39, Sv48 আর x86-64 — তিন, চার, পাঁচ স্তরের walk

৬৪-bit RV64-এ সবচেয়ে প্রচলিত বিন্যাস Sv39: VA-র নিচের ৩৯ বিট ব্যবহৃত, ভাগ 9 | 9 | 9 | 12. PTE এখন ৮ byte (PPN ৪৪ বিট, তাই PA ৫৬ বিট পর্যন্ত), তাই প্রতিটি টেবিলে 2⁹ = ৫১২টি ঘর × ৮ = আবার ঠিক ৪ KiB. একটি L0 টেবিল ৫১২ × ৪ KiB = ২ MiB ঢাকে, একটি L1 টেবিল ৫১২ × ২ MiB = ১ GiB, root ৫১২ × ১ GiB = ৫১২ GiB.

৬৪ বিটের বাকি ২৫টি ওপরের বিট (৬৩–৩৯) অবশ্যই বিট ৩৮-এর সমান হতে হবে — নাহলে page fault. এতে ঠিকানা-জগৎ দুই ভাগে: নিচের ২৫৬ GiB (সাধারণত user) আর একেবারে ওপরের ২৫৬ GiB (সাধারণত kernel), মাঝে বিশাল অবৈধ ফাঁক। x86-64-এর “canonical address”-এর নিয়মও একই ধারণার। satp RV64-এ ৬৪ বিট: MODE ৪ বিট (৮ = Sv39, ৯ = Sv48, ১০ = Sv57), ASID ১৬ বিট, PPN ৪৪ বিট। যেমন MODE 8, ASID 5, root PPN 0x80000 হলে satp = 0x8000500000080000.

বিন্যাস	VA বিট	VA-র ভাগ	স্তর = walk-এ PTE পড়া	ঠিকানা-জগৎ
RISC-V Sv32	32	10 \| 10 \| 12	২	৪ GiB
RISC-V Sv39	39	9 \| 9 \| 9 \| 12	৩	৫১২ GiB
RISC-V Sv48	48	9 \| 9 \| 9 \| 9 \| 12	৪	২৫৬ TiB
RISC-V Sv57	57	9 × ৫ \| 12	৫	১২৮ PiB
x86-64, ৪ স্তর (PML4)	48	9 \| 9 \| 9 \| 9 \| 12	৪	২৫৬ TiB
x86-64, ৫ স্তর (LA57)	57	9 × ৫ \| 12	৫	১২৮ PiB

x86-64-এর ৪ স্তরের নামগুলো ঐতিহাসিক: PML4 → PDPT → PD → PT. ঠিকানার ভাগ Sv48-এর হুবহু এক — দুটিই ৮ byte PTE আর ৫১২ ঘরের টেবিল বেছে নেওয়ায় অঙ্ক একই দাঁড়ায়। ৫ স্তরের paging (Intel-এর নাম LA57) এসেছে খুব বড় মেমরির server-এর জন্য; প্রকাশিত তথ্য অনুযায়ী মোটামুটি ২০১৯–২০২১ সাল থেকে কিছু নতুন CPU-তে এটি পাওয়া যায়, আর OS-কে আলাদাভাবে চালু করতে হয়। বেশিরভাগ ল্যাপটপ আর ডেস্কটপ এখনো ৪ স্তরেই চলে। ARMv8-A-ও ৪ KiB granule-এ মোটামুটি একই ধাঁচের ৪ স্তরের টেবিল ব্যবহার করে, তবে ১৬ KiB আর ৬৪ KiB granule-এর বিকল্পও দেয়।

Sv39 walk — একটি নির্দিষ্ট ঠিকানায়, ধাপে ধাপে

VA = 0x40403ABC, একটি store. ভাগ: VPN[2] = 1, VPN[1] = 2, VPN[0] = 3, offset = 0xABC. satp.PPN = 0x80000. নিচের stepper-এ page table walk-এর প্রতিটি মেমরি-পড়া। “পরে” চাপুন:

VA ভাগ1 | 2 | 3 | ABC9+9+9+12
L2 (root)0x80000008pointer
L10x80001010pointer
L0 (leaf)0x80002018PPN 0x80123
যাচাইW, U, A, Dstore চলবে
PA0x80123ABCTLB-তে রাখা

হিসাবVA-র ভাগ

VA      = 0x40403ABC
VPN[2]  = VA >> 30          & 0x1FF = 1
VPN[1]  = (VA >> 21)        & 0x1FF = 2
VPN[0]  = (VA >> 12)        & 0x1FF = 3
offset  = VA & 0xFFF                = 0xABC
বিট 63..39 সব ০ = বিট 38 ✓ (বৈধ ঠিকানা)

মেমরি-পড়া ১root টেবিল

ঠিকানা = satp.PPN × 4096 + VPN[2] × 8
       = 0x80000000 + 1 × 8 = 0x80000008
PTE    = 0x20000401   flag: V-------
R = W = X = 0  -> leaf নয়, পরের টেবিলের pointer
পরের টেবিল = PPN 0x80001 -> 0x80001000

মেমরি-পড়া ২L1 টেবিল

ঠিকানা = 0x80001000 + VPN[1] × 8
       = 0x80001000 + 2 × 8 = 0x80001010
PTE    = 0x20000801   flag: V-------
আবার pointer -> পরের টেবিল 0x80002000

মেমরি-পড়া ৩L0 টেবিল

ঠিকানা = 0x80002000 + VPN[0] × 8
       = 0x80002000 + 3 × 8 = 0x80002018
PTE    = 0x20048CD7   flag: VRW-U-AD
R = 1 -> leaf, PPN = 0x20048CD7 >> 10 = 0x80123

অনুমতিstore, user mode

V = 1 ✓   W = 1 ✓ (store)   U = 1 ✓ (user mode)
A = 1 ✓   D = 1 ✓ (আগে থেকেই dirty)
কোনো শর্ত ভাঙলে: store page fault (cause 15)

ফল৩টি PTE পড়ার পরে

PA = PPN × 4096 + offset
   = 0x80123000 + 0xABC = 0x80123ABC
TLB-তে নতুন ঘর: (ASID, VPN 0x40403) -> PPN 0x80123, VRW-U-AD

ধাপ ১ — ঠিকানা ভাগ। VA = 0x40403ABC-কে ৯ + ৯ + ৯ + ১২ বিটে ভাগ করলে VPN = [1, 2, 3], offset = 0xABC. ওপরের ২৫টি বিট শূন্য, বিট ৩৮-ও শূন্য — ঠিকানাটি বৈধ। TLB-তে এই VPN পাওয়া যায়নি ধরে নিয়ে walk শুরু।
ধাপ ২ — root টেবিল। satp.PPN = 0x80000, তাই root টেবিল 0x80000000-এ। ঘর ১-এর ঠিকানা = 0x80000000 + 1 × 8 = 0x80000008. সেখানে PTE = 0x20000401: V = 1, কিন্তু R, W, X সব ০ — তাই এটি pointer. পরের টেবিল PPN 0x80001-এ।
ধাপ ৩ — L1 টেবিল। ঘর ২: 0x80001000 + 2 × 8 = 0x80001010. PTE = 0x20000801, আবার pointer, পরের টেবিল 0x80002000-এ। এ পর্যন্ত দুটি মেমরি-পড়া, আর এখনো অনুবাদ পাওয়া যায়নি।
ধাপ ৪ — L0, leaf. ঘর ৩: 0x80002000 + 3 × 8 = 0x80002018. PTE = 0x20048CD7, নিচের byte 0xD7 মানে V, R, W, U, A, D সেট। R = 1, তাই এটি leaf. PPN = PTE >> 10 = 0x80123.
ধাপ ৫ — অনুমতি যাচাই। Store-এর জন্য W = 1 লাগে, user mode-এর জন্য U = 1. A আর D দুটিই ১, তাই হালনাগাদের দরকার নেই (অংশ ৫)। কোনোটি ভাঙলে walker কিছু লেখে না, store page fault ওঠে, আর ঠিক এই instruction-এ precise exception (পর্ব ৩৮)।
ধাপ ৬ — physical ঠিকানা। PA = 0x80123 × 4096 + 0xABC = 0x80123ABC. অনুবাদটি TLB-তে রাখা হয়, যাতে একই page-এর পরের প্রবেশে আর walk না লাগে। মোট খরচ: ৩টি নির্ভরশীল মেমরি-পড়া — একটির ফল না এলে পরেরটির ঠিকানাই জানা যায় না।

এবার একই walker চালানো যায় এমন রূপে। নিচের JS একটি ছোট simulated physical memory (ঠিকানা → PTE-র মান) নিয়ে Sv32 আর Sv39 দুটিই walk করে: প্রতিটি স্তরে PTE-র ঠিকানা, মান, flag আর পরের PPN ছাপে, আর শেষে physical ঠিকানা বা page fault-এর কারণ বলে। একটি ক্ষেত্রে leaf আছে L1-এ — ২ MiB-এর superpage.

// RISC-V Sv32 / Sv39 page-table walker on a tiny simulated physical memory (address -> PTE value).
const hex = x => "0x" + x.toString(16);
const flags = p => [..."VRWXUGAD"].map((c, i) => (p >> BigInt(i)) & 1n ? c : "-").join("");
function walk(mode, rootPPN, mem, va, acc) {           // acc: "r" load, "w" store, "x" fetch
  const [L, vb, sz] = mode === "Sv32" ? [2, 10n, 4n] : [3, 9n, 8n];
  const vpn = i => (va >> (12n + vb * BigInt(i))) & ((1n << vb) - 1n);
  const kind = { r: "load", w: "store", x: "instruction" }[acc];
  console.log(`${mode} ${acc} VA ${hex(va)}  VPN = [${[...Array(L).keys()].reverse().map(vpn).join(", ")}]`);
  let a = rootPPN << 12n;                                // satp.PPN -> root table address
  for (let i = L - 1; i >= 0; i--) {
    const pa = a + vpn(i) * sz, pte = mem.get(pa) ?? 0n, ppn = (pte >> 10n) & ((1n << 44n) - 1n);
    console.log(`  L${i}: PTE @${hex(pa)} = ${hex(pte)} ${flags(pte)} PPN=${hex(ppn)}`);
    if (!(pte & 1n) || (pte & 6n) === 4n) return console.log(`  => ${kind} page fault (V=0 or W without R)`);
    if (!(pte & 0xAn)) { a = ppn << 12n; continue; }    // R=0, X=0: pointer to next level
    const low = vb * BigInt(i);                          // leaf at level i covers 2^(12+low) bytes
    if (ppn & ((1n << low) - 1n)) return console.log(`  => ${kind} page fault (misaligned superpage)`);
    if (!(pte & { r: 2n, w: 4n, x: 8n }[acc])) return console.log(`  => ${kind} page fault (no ${acc} permission)`);
    const pa2 = ((ppn | ((va >> 12n) & ((1n << low) - 1n))) << 12n) | (va & 0xFFFn);
    return console.log(`  => leaf at L${i} (${4n << low} KiB page)  PA = ${hex(pa2)}  [${L - i} PTE reads]`);
  }
  console.log(`  => ${kind} page fault (no leaf at L0)`);
}
const m32 = new Map([[0x80000004n, 0x20000401n], [0x8000100Cn, 0x200040D7n]]);
walk("Sv32", 0x80000n, m32, 0x00403ABCn, "r");
const m39 = new Map([[0x80000008n, 0x20000401n], [0x80001010n, 0x20000801n],
  [0x80002018n, 0x20048CD7n], [0x80001028n, 0x2010005Bn]]);
walk("Sv39", 0x80000n, m39, 0x40403ABCn, "w");           // 3-level walk to a 4 KiB page
walk("Sv39", 0x80000n, m39, 0x40A1F123n, "x");           // leaf at L1: 2 MiB superpage
walk("Sv39", 0x80000n, m39, 0x40A1F123n, "w");           // same page, but W=0
walk("Sv39", 0x80000n, m39, 0x40404000n, "r");           // L0 entry empty

আউটপুট (নির্ধারিত — সব মান স্থির):

Sv32 r VA 0x403abc  VPN = [1, 3]
  L1: PTE @0x80000004 = 0x20000401 V------- PPN=0x80001
  L0: PTE @0x8000100c = 0x200040d7 VRW-U-AD PPN=0x80010
  => leaf at L0 (4 KiB page)  PA = 0x80010abc  [2 PTE reads]
Sv39 w VA 0x40403abc  VPN = [1, 2, 3]
  L2: PTE @0x80000008 = 0x20000401 V------- PPN=0x80001
  L1: PTE @0x80001010 = 0x20000801 V------- PPN=0x80002
  L0: PTE @0x80002018 = 0x20048cd7 VRW-U-AD PPN=0x80123
  => leaf at L0 (4 KiB page)  PA = 0x80123abc  [3 PTE reads]
Sv39 x VA 0x40a1f123  VPN = [1, 5, 31]
  L2: PTE @0x80000008 = 0x20000401 V------- PPN=0x80001
  L1: PTE @0x80001028 = 0x2010005b VR-XU-A- PPN=0x80400
  => leaf at L1 (2048 KiB page)  PA = 0x8041f123  [2 PTE reads]
Sv39 w VA 0x40a1f123  VPN = [1, 5, 31]
  L2: PTE @0x80000008 = 0x20000401 V------- PPN=0x80001
  L1: PTE @0x80001028 = 0x2010005b VR-XU-A- PPN=0x80400
  => store page fault (no w permission)
Sv39 r VA 0x40404000  VPN = [1, 2, 4]
  L2: PTE @0x80000008 = 0x20000401 V------- PPN=0x80001
  L1: PTE @0x80001010 = 0x20000801 V------- PPN=0x80002
  L0: PTE @0x80002020 = 0x0 -------- PPN=0x0
  => load page fault (V=0 or W without R)

প্রথম ব্লক অংশ ৩-এর হাতে-করা decode-এর সাথে মেলে: Sv32-এ দুটি PTE পড়ে PA = 0x80010abc. দ্বিতীয় ব্লক ওপরের stepper-এর তিনটি ধাপ হুবহু, আর store চলেছে কারণ W = 1. তৃতীয় ব্লকে L1-এর ঘর (0x80001028) নিজেই leaf (VR-XU-A-): walk থেমেছে দুটি পড়ায়, আর PA-র গঠন দেখুন — PPN 0x80400-এর ওপরের অংশ, কিন্তু VPN[0] = 31 (0x1f) সরাসরি VA থেকে, তাই PA = 0x80400000 + 0x1f000 + 0x123 = 0x8041f123. চতুর্থ ব্লকে একই page-এ store — W = 0, তাই store page fault. শেষ ব্লকে L0-এর ঘর 0x80002020 খালি (মান ০, V = 0) — load page fault; OS এখানে demand paging-এ page আনবে (OS কোর্সে page fault-এর ধাপ)।

৫ · Superpage, A/D বিট, অনুমতি আর page fault-এর পথ

Superpage — উঁচু স্তরে leaf

ওপরের simulator-এ দেখলেন, walk যেকোনো স্তরে leaf পেলে থেমে যায়। Sv39-এ L1-এ leaf মানে একটি ২ MiB page (৫১২টি ৪ KiB page-এর সমান), L2-তে leaf মানে ১ GiB page (২,৬২,১৪৪টি ৪ KiB page). Sv32-এ L1-এ leaf মানে ৪ MiB-এর “megapage”. সাধারণ ভাষায় এদের huge page-ও বলে (Linux-এর নাম)। লাভ দুটি: walk ছোট (২ MiB-এ ২টি, ১ GiB-এ ১টি PTE পড়া), আর অংশ ৬-এ দেখবেন — একটি TLB ঘর অনেক বেশি মেমরি ঢাকে।

শর্ত একটি: superpage-কে তার নিজের আকারে aligned হতে হবে। ২ MiB superpage-এর PPN-এর নিচের ৯টি বিট (PPN[0]) শূন্য হতে হবে, ১ GiB-এর ক্ষেত্রে নিচের ১৮টি। নাহলে hardware page fault তোলে (“misaligned superpage”). কারণ সহজ: PA-র নিচের অংশ VA থেকে সরাসরি আসে, তাই physical দিকেও সেই অংশ শূন্য থেকে শুরু হওয়া চাই। OS-এর দিক থেকে এর অর্থ — ২ MiB-এর একটানা, aligned physical জায়গা খুঁজে পাওয়া, যা মেমরি খণ্ডিত হলে কঠিন।

A আর D বিট — কে হালনাগাদ করে

A (accessed) বিট OS-কে বলে কোন page সম্প্রতি ব্যবহৃত (page replacement-এর জন্য, OS কোর্সে), আর D (dirty) বলে কোন page disk-এ লিখে ফেরত দিতে হবে। A = 0 অবস্থায় প্রবেশ, বা D = 0 অবস্থায় store হলে দুটি পথ আছে: hardware নিজে PTE-তে বিটটি বসায় (একটি atomic লেখা, x86 এভাবেই করে), অথবা page fault তুলে OS-কে করতে দেয়। RISC-V-এর privileged specification ঐতিহাসিকভাবে দুটিই অনুমোদন করত — কোনটি, তা বাস্তবায়নের ওপর। পরের সংস্করণে Svade (exception-এর পথ) আর Svadu (hardware হালনাগাদ) নামে extension এই আচরণ স্পষ্ট করেছে বলে জানা যায়; নির্দিষ্ট chip কোনটি করে, তার datasheet দেখা দরকার। দুই পথের দাম ভিন্ন: hardware-এর পথে walker-কে মেমরিতে লিখতেও হয়, exception-এর পথে প্রথম লেখায় কয়েকশো cycle-এর trap.

অনুমতির নিয়ম আর page fault

Load-এ R = 1, store-এ W = 1, fetch-এ X = 1 লাগে।
User mode শুধু U = 1 page ছুঁতে পারে। Supervisor mode সাধারণত U = 1 page পড়তে-লিখতে পারে না — sstatus-এর SUM বিট সেট করলে তবেই। এতে kernel-এর bug ভুল করে user-এর বিছানো ডেটা পড়ে ফেলতে পারে না। U = 1 page-এর কোড supervisor কখনো চালাতে পারে না।
MXR বিট সেট থাকলে X = 1 page-ও পড়া যায় (execute-only কোড পড়ার জন্য)।

কোনো নিয়ম ভাঙলে page fault — তিন রকম, RISC-V-এর scause-এ ভিন্ন কোড: instruction page fault (১২), load page fault (১৩), store/AMO page fault (১৫)। আর stval-এ থাকে দোষী virtual ঠিকানা, যাতে OS জানে কোন page. Pipeline-এ এটি কীভাবে precise রাখা হয় — দোষী instruction-এর আগের সব শেষ, পরের সব বাতিল, sepc-এ তার PC — তা পর্ব ৩৮-এ (Exception আর interrupt). Page fault-এর পর OS PTE ঠিক করে একই instruction আবার চালায়।

মূল ধারণা

Hardware নীতি চাপায়, OS নীতি ঠিক করে। কোন page কোথায়, কার অনুমতি কী — তা OS page table-এ লেখে। MMU প্রতিটি প্রবেশে সেই লেখা নির্ভুলভাবে প্রয়োগ করে, আর কিছু অমিল হলে নিজে সিদ্ধান্ত না নিয়ে exception দিয়ে OS-কে ডাকে।

৬ · TLB — অনুবাদের cache

Sv39-এ প্রতিটি মেমরি-প্রবেশের আগে ৩টি PTE পড়তে হলে প্রতিটি load আসলে ৪টি মেমরি-প্রবেশ — অসম্ভব ধীর। সমাধান TLB: সম্প্রতি ব্যবহৃত অনুবাদের একটি ছোট, দ্রুত cache. প্রতিটি ঘরে থাকে VPN (tag), PPN, অনুমতির বিট, ASID আর G বিট, আর superpage হলে তার আকার। Locality-র কারণে (পর্ব ৪৪, মেমরি হায়ারার্কি) একটি ৪ KiB page-এ সাধারণত বহুবার প্রবেশ হয়, তাই অল্প কিছু ঘরেই hit rate সাধারণত খুব উঁচু থাকে।

গঠন — cache-এর মতোই, ছোট আকারে

Associativity: ছোট L1 TLB প্রায়ই fully associative — যেকোনো অনুবাদ যেকোনো ঘরে, সব tag একসাথে তুলনা। বড় L2 TLB সাধারণত set-associative (যেমন ৪ বা ৮ way). Set, way আর replacement-এর ধারণা হুবহু পর্ব ৪৬-এর (Set-associative আর fully associative cache); replacement সাধারণত LRU বা তার সস্তা অনুকরণ।
আকার (মোটামুটি, chip-ভেদে ভিন্ন): L1-এ instruction আর data-র আলাদা TLB, প্রতিটি কয়েক ডজন ঘর (৩২ থেকে ১০০-র কাছাকাছি); তার পেছনে একটি ভাগ করা L2 TLB, প্রায় এক থেকে কয়েক হাজার ঘর। L1 TLB সাধারণত ১ cycle-এর মধ্যে, L2 TLB কয়েক cycle-এ উত্তর দেয়।
Superpage-এর ঘর: ভিন্ন আকারের page একই টেবিলে রাখা কঠিন (tag-এর কয়টি বিট তুলনা হবে?), তাই অনেক নকশায় ২ MiB বা ১ GiB-এর আলাদা ছোট TLB থাকে।

TLB reach — TLB কতটা মেমরি ঢাকে

TLB reach = TLB-র ঘর × page size

৬৪ ঘরের L1 TLB, ৪ KiB page: ৬৪ × ৪ KiB = ২৫৬ KiB. ১৫৩৬ ঘরের L2 TLB: ৬ MiB. কিন্তু আজকের L2/L3 cache-ই কয়েক MiB থেকে কয়েক ডজন MiB — অর্থাৎ ডেটা cache-এ আছে, অথচ তার অনুবাদ TLB-তে নেই, এমন অবস্থা খুবই সম্ভব। একই ১৫৩৬ ঘরে ২ MiB page হলে reach ৩ GiB. বড় database, virtual machine আর বৈজ্ঞানিক হিসাবে huge page তাই প্রায়ই চোখে পড়ার মতো গতি আনে।

TLB miss কে সামলায়

Hardware walker (x86, ARM, বেশিরভাগ RISC-V core): miss হলে একটি ছোট state machine নিজেই অংশ ৪-এর walk করে, ঘর ভরে, instruction চালিয়ে যায় — OS কিছু জানে না। Page table-এর বিন্যাস তাই ISA-তে বাঁধা। Software-managed TLB (ঐতিহাসিক MIPS-এর ধাঁচ, যেখানে TLB miss একটি exception): OS-এর একটি ছোট handler টেবিল খুঁজে বিশেষ instruction দিয়ে TLB-তে ঘর লেখে। OS যেকোনো টেবিল-বিন্যাস বেছে নিতে পারে, কিন্তু প্রতিটি miss-এ trap-এর খরচ, আর out-of-order core-এ pipeline flush. এই দুইয়ের তুলনা OS কোর্সের TLB miss কে সামলায় অংশেও আছে।

Walk-এর PTE-গুলো সাধারণ ডেটার মতো data cache দিয়ে পড়া হয়, তাই প্রায়ই L1 বা L2-তে hit করে। তার ওপর অনেক নকশায় page-walk cache থাকে — ওপরের স্তরের PTE (root, L1) মনে রাখার ছোট cache, যাতে walk শুরু হয় সরাসরি নিচের স্তর থেকে। Intel-এর নথিতে এর নাম “paging-structure cache”; অন্য নির্মাতারা ভিন্ন নামে একই ধারণা ব্যবহার করে বলে জানা যায়, যদিও খুঁটিনাটি প্রায়ই প্রকাশিত নয়। আধুনিক বড় core একসাথে একাধিক walk চালাতেও পারে।

ASID — context switch-এ TLB না মুছে

দুটি process-এর একই VPN সম্পূর্ণ ভিন্ন physical page দেখাতে পারে। TLB-তে শুধু VPN থাকলে context switch-এ পুরো TLB মুছতে (flush) হয়, আর নতুন process প্রথম কয়েক হাজার প্রবেশ miss-এ কাটায়। সমাধান: প্রতিটি ঘরে ASID (address space identifier) — RISC-V-এ satp-এর ASID, x86-এ PCID (১২ বিট)। মেলার শর্ত: VPN সমান এবং (ASID সমান অথবা G = 1). OS page table বদলালে RISC-V-এ sfence.vma instruction দিয়ে জানায় — নির্দিষ্ট VA, নির্দিষ্ট ASID, অথবা সব। নিচের stepper-এ hit, miss আর ASID-এর ভূমিকা:

1ASID 1: load  0x40403ABC2-- context switch: satp = (ASID 2, root B) --3ASID 2: load  0x40403ABC4ASID 2: load  0x40403F005-- context switch: satp = (ASID 1, root A) --6ASID 1: store 0x40403100

TLB-র অবস্থা (ASID, VPN → PPN)

চলতি ASID
ঘর ০
ঘর ১
ঘর ২
Walk মোট

প্রবেশ ১ — hit. Process A (ASID 1) VA 0x40403ABC পড়ে। VPN 0x40403 আর ASID 1 দুটিই ঘর ০-এর সাথে মেলে — hit. PA = 0x80123 × 4096 + 0xABC = 0x80123ABC, প্রায় ১ cycle-এ। ঘর ১ একটি global page (যেমন সব process-এ একই রকম map করা kernel-এর অংশ), G = 1, তাই যেকোনো ASID-এ মিলবে।
Context switch. OS satp-এ process B-এর root টেবিল আর ASID 2 লেখে। ASID আছে বলে TLB মোছা হয় না — A-র ঘর রয়ে যায়, কারণ সেগুলো ASID 1 দিয়ে চিহ্নিত, B ভুল করে সেগুলো ব্যবহার করতে পারবে না।
প্রবেশ ৩ — একই VPN, তবু miss. B-ও VA 0x40403ABC পড়ে। ঘর ০-এর VPN মেলে, কিন্তু ASID 1 ≠ 2 আর G = 0 — মেলে না। Walker B-এর টেবিল walk করে PPN 0x9A005 পায়, ঘর ২-এ রাখে। PA = 0x9A005ABC — A-র থেকে সম্পূর্ণ ভিন্ন physical page. বিচ্ছিন্নতা এখানেই।
প্রবেশ ৪ — একই page-এ hit. B এবার 0x40403F00 পড়ে — একই VPN 0x40403, ভিন্ন offset. ঘর ২ মেলে, hit, PA = 0x9A005F00. একটি walk-এর দাম একই page-এর পরের সব প্রবেশে ভাগ হয়ে যায়।
আবার context switch. OS A-তে ফেরে: satp = (ASID 1, root A). এবারও কোনো flush নেই। ASID না থাকলে এখানে পুরো TLB মুছে যেত, আর A-কে সব অনুবাদ আবার walk করে আনতে হতো।
প্রবেশ ৬ — ফেরার পর সরাসরি hit. A-র store 0x40403100: ঘর ০ এখনো আছে, hit. অনুমতি TLB-র ঘরেই রাখা, তাই W = 1 যাচাইও এখানে হয় — কোনো walk নয়। মোট ৪টি অনুবাদ-প্রয়োজনে walk মাত্র ১টি। OS পরে A-র এই map বদলালে sfence.vma (VA 0x40403100, ASID 1) দিয়ে শুধু ঘর ০ বাতিল করবে।

TLB shootdown — একাধিক core-এ

Multicore-এ প্রতিটি core-এর নিজস্ব TLB. OS যদি একটি page-এর map সরায় (যেমন memory ফেরত দেওয়া বা অনুমতি কমানো), তাহলে যে core-গুলো একই address space চালাচ্ছে, তাদের TLB-তেও পুরোনো অনুবাদ থাকতে পারে। TLB shootdown-এ OS অন্য core-গুলোতে inter-processor interrupt পাঠায়, প্রতিটি নিজের TLB থেকে ঘরটি বাতিল করে জানায়, আর তারপরই physical page পুনরায় ব্যবহার করা নিরাপদ। এটি দামি (কয়েক হাজার cycle পর্যন্ত হতে পারে), তাই OS কাজ জমিয়ে একবারে করে। কিছু ISA-তে (যেমন ARMv8) TLB বাতিলের instruction hardware নিজেই অন্য core-এ পাঠাতে পারে। Cache-এর জন্য একই ধরনের সমস্যার hardware সমাধান — coherence — পর্ব ৫৩-এ (Multicore আর cache coherence); TLB সাধারণত সেই coherence-এর বাইরে, তাই software-কে এটি করতে হয়।

নিচের simulator একটি fully associative, LRU TLB চালায় — দুটি process (A ৬টি page, B ৪টি page, একই VPN) চারটি time slice-এ পালা করে চলে। ASID ছাড়া (প্রতিটি switch-এ flush) আর ASID-সহ, আর দুটি ছোট আকারে। শেষে TLB reach-এর টেবিল:

// Fully associative LRU TLB, with or without ASID tags, on a 2-process address trace.
function simulate(entries, useASID, trace) {
  let tlb = [], hits = 0, walks = 0, cur = null;           // tlb: keys, most recent last
  for (const [asid, va] of trace) {
    if (asid !== cur && !useASID) tlb = [];                 // no ASID: flush on context switch
    cur = asid;
    const key = (useASID ? asid + ":" : "") + (va >>> 12).toString(16);   // VPN (+ ASID)
    const i = tlb.indexOf(key);
    if (i >= 0) { hits++; tlb.splice(i, 1); }
    else { walks++; if (tlb.length === entries) tlb.shift(); }           // evict LRU
    tlb.push(key);
  }
  return { hits, walks, rate: (100 * hits / trace.length).toFixed(1) + "%" };
}
const trace = [];                                           // A uses 6 pages, B uses 4 (same VPNs!)
const slice = (asid, pages) => { for (let r = 0; r < 3; r++)
  for (let p = 0; p < pages; p++) trace.push([asid, 0x10000 + p * 4096 + r * 8]); };
for (let s = 0; s < 4; s++) s % 2 ? slice(2, 4) : slice(1, 6);
console.log(`trace: ${trace.length} accesses, 4 time slices A B A B`);
console.log("entries  ASID   hits  walks  hit rate");
for (const [n, a] of [[16, false], [16, true], [8, true], [10, true]]) {
  const r = simulate(n, a, trace);
  console.log(String(n).padStart(7), (a ? "yes" : "no").padStart(5), String(r.hits).padStart(6),
              String(r.walks).padStart(6), r.rate.padStart(9));
}
console.log("\nTLB reach = entries x page size");
const fmt = b => b >= 2 ** 30 ? b / 2 ** 30 + " GiB" : b >= 2 ** 20 ? b / 2 ** 20 + " MiB" : b / 1024 + " KiB";
for (const n of [64, 1536]) console.log(String(n).padStart(5) + " entries:",
  [4096, 2 ** 21, 2 ** 30].map(p => `${fmt(p)} page -> ${fmt(n * p)}`).join(" | "));

আউটপুট (নির্ধারিত):

trace: 60 accesses, 4 time slices A B A B
entries  ASID   hits  walks  hit rate
     16    no     40     20     66.7%
     16   yes     50     10     83.3%
      8   yes     40     20     66.7%
     10   yes     50     10     83.3%

TLB reach = entries x page size
   64 entries: 4 KiB page -> 256 KiB | 2 MiB page -> 128 MiB | 1 GiB page -> 64 GiB
 1536 entries: 4 KiB page -> 6 MiB | 2 MiB page -> 3 GiB | 1 GiB page -> 1536 GiB

৬০টি প্রবেশে মোট ১০টি ভিন্ন (ASID, VPN). ASID ছাড়া প্রতিটি switch-এ সব মুছে যায়, তাই প্রতিটি slice-এ তার সব page আবার walk: ৬ + ৪ + ৬ + ৪ = ২০টি walk, hit rate ৬৬.৭%. ASID-সহ ১৬ ঘরে শুধু প্রথমবারের ১০টি (compulsory) miss — ৮৩.৩%. মজার সারি ৮ ঘরের: ঘর ১০টি অনুবাদের চেয়ে কম, আর LRU-তে চক্রাকারে প্রবেশ হলে ঠিক যে ঘরটি পরে লাগবে সেটিই বাদ পড়ে — ফল আবার ২০টি walk, যেন ASID নেই-ই। ১০ ঘর হলেই ৮৩.৩%-এ ফেরে। শিক্ষা: TLB reach যদি working set-এর চেয়ে সামান্যও কম হয়, LRU হঠাৎ খুব খারাপ হতে পারে। Reach টেবিলে দেখুন, ৬৪ ঘর ৪ KiB page-এ মাত্র ২৫৬ KiB, অথচ ১ GiB page-এ ৬৪ GiB.

নিজের হাতে TLB-র প্রভাব মাপা

এবার আসল hardware-এ। নিচের C প্রোগ্রাম nটি ভিন্ন cache line ছোঁয় দুই ভাবে: (ক) প্রতিটি line আলাদা ৪ KiB page-এ — nটি page, (খ) line-গুলো পাশাপাশি — মাত্র n/৬৪টি page. দুই ক্ষেত্রেই cache-এ সমান সংখ্যক line, তাই পার্থক্যের বড় অংশ আসে TLB থেকে। Page-এর ভেতরে line-টি একটু করে সরানো হয়েছে, যাতে সব line একই cache set-এ না পড়ে। madvise দিয়ে huge page না দিতে অনুরোধ করা হয়েছে।

// One byte per 4 KiB page vs one byte per 64 B line: n distinct lines either way (timings vary)
#define _GNU_SOURCE
#include <stdio.h>
#include <sys/mman.h>
#include <time.h>
#define PAGE 4096u
#define LINE 64u
#define MAXP 65536u                 /* up to 65536 pages = 256 MiB of virtual space */
#define TOTAL (1u << 22)            /* accesses per measurement */
static double now_ns(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec * 1e9 + t.tv_nsec; }
static unsigned sink;
static double run(const volatile unsigned char *a, unsigned n, size_t stride) {
    double best = 1e30;
    for (int k = 0; k < 3; k++) {           /* best of 3 runs: less noise */
        unsigned s = 0; double t0 = now_ns();
        for (unsigned r = 0; r < TOTAL / n; r++)
            for (unsigned i = 0; i < n; i++)    /* page case: stagger the line in each page */
                s += a[i * stride + (stride == PAGE ? (i % 64) * LINE : 0)];
        double t = (now_ns() - t0) / TOTAL; sink += s; if (t < best) best = t;
    }
    return best;
}
int main(void) {
    size_t bytes = (size_t)MAXP * PAGE;
    unsigned char *a = mmap(NULL, bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (a == MAP_FAILED) { puts("mmap failed"); return 0; }
    madvise(a, bytes, MADV_NOHUGEPAGE);                   /* ask for plain 4 KiB pages */
    for (size_t i = 0; i < bytes; i += PAGE) a[i] = 1;   /* touch every page once */
    printf("%7s %12s %12s %6s\n", "n", "1/page ns", "1/line ns", "ratio");
    for (unsigned n = 16; n <= MAXP; n *= 4) {
        double p = run(a, n, PAGE), l = run(a, n, LINE);
        printf("%7u %12.2f %12.2f %6.1f\n", n, p, l, p / l);
    }
    return (int)(sink & 0u);       /* uses sink so the loads are not optimised away */
}

একটি shared virtual machine-এ একবারের আউটপুট (প্রতিবার আর প্রতি যন্ত্রে ভিন্ন হবে):

      n    1/page ns    1/line ns  ratio
     16         4.21         4.12    1.0
     64         3.00         3.14    1.0
    256         3.07         3.77    0.8
   1024         3.38         2.91    1.2
   4096         9.57         2.10    4.6
  16384         9.45         2.75    3.4
  65536         9.74         3.43    2.8

১০২৪টি page পর্যন্ত দুই কলাম প্রায় সমান, প্রায় ৩ ns — অনুবাদ TLB-তে থাকছে (১০২৪ × ৪ KiB = ৪ MiB, যা এক-দুই হাজার ঘরের L2 TLB-র reach-এর মধ্যে)। ৪০৯৬টি page থেকে “1/page” কলাম লাফিয়ে প্রায় ৯–১০ ns-এ ওঠে, অথচ একই সংখ্যক line পাশাপাশি থাকলে সময় প্রায় বদলায় না — এই লাফই TLB reach পেরিয়ে যাওয়ার চিহ্ন: প্রায় প্রতিটি প্রবেশে এখন page walk. সতর্কতা তিনটি: (১) এটি একটি virtual machine, তাই TLB miss-এ সম্ভবত অংশ ৮-এর দ্বিমাত্রিক walk হচ্ছে — native যন্ত্রে লাফ ছোট হতে পারে; (২) cache-ও ভূমিকা রাখে — বড় n-এ line-গুলো L1 ছাড়িয়ে L2/L3-তে যায়, আর walk-এর PTE-ও cache-এ জায়গা নেয়; (৩) ছোট n-এ সময় loop-এর নিজের খরচেই প্রায় সীমিত, আর সংখ্যাগুলো প্রতিবার কিছুটা বদলায়। নিজের Linux যন্ত্রে চালালে লাফটি কোথায়, তা থেকে আপনার CPU-র TLB-র আকারের একটি মোটা আন্দাজ পাওয়া যায় (sysfs থেকে cache-এর আকার পড়ার একটি script আছে পর্ব ৪৬-এ — Set-associative আর fully associative cache দেখুন)।

৭ · Cache-এর সাথে TLB — PIPT, VIPT, VIVT আর synonym

পর্ব ৪৫-এ (Cache-এর মৌলিক কথা) ঠিকানাকে ভাগ করেছিলেন | tag | index | block offset |. প্রশ্ন: cache কোন ঠিকানা দিয়ে খোঁজা হবে — virtual না physical? তিনটি নকশা:

PIPT

Physically indexed, physically tagged: আগে TLB, তারপর PA দিয়ে cache. সবচেয়ে সরল আর নির্ভুল — কোনো alias সমস্যা নেই। কিন্তু TLB-র সময় cache-এর সময়ের সাথে যোগ হয়। L2, L3 প্রায় সবসময় PIPT, কারণ ততক্ষণে PA জানা।

নির্ভুল, ধীর L1-এর জন্য

VIPT

Virtually indexed, physically tagged: VA-র index অংশ দিয়ে set বাছা আর TLB lookup একসাথে; তারপর TLB-র PPN দিয়ে tag তুলনা। Index যদি পুরোপুরি page offset-এর ভেতরে থাকে, তাহলে VA আর PA-র index একই — নির্ভুল আর দ্রুত। আধুনিক L1 data cache-এর প্রচলিত নকশা।

L1-এর জন্য প্রচলিত

VIVT

Virtually indexed, virtually tagged: TLB লাগেই না hit-এর পথে। কিন্তু দুটি সমস্যা: ভিন্ন process-এর একই VA (homonym) — ASID দিয়ে tag না করলে context switch-এ cache মুছতে হয়; আর একই PA-র দুটি VA (synonym). পুরোনো কিছু ARM নকশায় ছিল; আজ মূলধারার data cache-এ বিরল।

দ্রুত, কিন্তু জটিল

Synonym সমস্যা আর VIPT-এর আকারের সীমা

Synonym (alias): দুটি ভিন্ন VA একই physical ঠিকানা দেখায় — যেমন shared memory, বা kernel একই page দুটি জায়গায় map করেছে। VIPT-এ index-এর কোনো বিট যদি page offset-এর বাইরে (VPN থেকে) আসে, তাহলে দুটি VA একই physical line-কে দুটি ভিন্ন set-এ বসাতে পারে। এক জায়গায় লেখা হলো, অন্য জায়গার কপি পুরোনো — ভুল ফল। তাই নিয়ম:

index + block offset বিট ≤ page offset বিট ⇔ cache-এর আকার ≤ way × page size

যুক্তি: cache-এর আকার C, way সংখ্যা W, line-এর আকার B হলে set = C / (W × B). Index আর block offset মিলে log₂(set × B) = log₂(C / W) বিট। এটি page offset-এর (log₂ P) মধ্যে থাকার শর্ত C / W ≤ P, অর্থাৎ প্রতিটি way-এর আকার ≤ page size. তখন index-এর সব বিট VA আর PA-তে একই, synonym-এর দুই VA একই set-এ পড়ে, আর physical tag তুলনা ঠিক line-টিকেই চেনে।

৩২ KiB, 8-way, ৬৪ B line, ৪ KiB page: প্রতি way = ৩২ / ৮ = ৪ KiB; set = ৩২৭৬৮ / (৮ × ৬৪) = ৬৪ → index ৬ বিট + offset ৬ বিট = ১২ বিট = ঠিক page offset ✓. বহু বছর ধরে x86 core-এর L1 data cache এই আকারের ছিল — কাকতালীয় নয়।
৬৪ KiB, 8-way: প্রতি way ৮ KiB → ১৩ বিট লাগে, একটি বিট VPN থেকে → একই physical line দুটি set-এ বসতে পারে। Hardware-কে বাড়তি ব্যবস্থা নিতে হয় (দুই set-এই খোঁজা, বা alias ধরা), অথবা OS-কে page colouring করতে হয়।
বড় L1 চাইলে: way বাড়ানো (৪৮ KiB 12-way-এ প্রতি way আবার ৪ KiB — সাম্প্রতিক কিছু x86 core-এ এমন L1 আছে বলে প্রকাশিত), অথবা বড় page. প্রকাশিত বিশ্লেষণ অনুযায়ী, কিছু ARM-ভিত্তিক নকশা ১৬ KiB page ব্যবহার করে, যেখানে 8-way-তে ১২৮ KiB পর্যন্ত VIPT সম্ভব।

নিচের stepper-এ একটি VIPT L1 lookup, TLB-র সাথে সমান্তরালে। Cache: ৩২ KiB, 8-way, ৬৪ B line. VA = 0x40403ABC (অংশ ৪-এর একই ঠিকানা):

VA = 0x40403ABCVPN 0x40403 │ offset 0xABC

offset → index 42, block offset 60বিট 11–6 আর 5–0

TLB: VPN 0x40403 খোঁজাএকই cycle-এ

Cache: set 42-এর ৮টি tag পড়াVA-র index দিয়েই

TLB hit: PPN 0x80123physical tag

৮টি tag-এর সাথে তুলনাway 5 মেলে

byte 60 ফেরতPA 0x80123ABC

ঠিকানা ভাগ। ৬৪ B line মানে block offset ৬ বিট, ৬৪টি set মানে index ৬ বিট — মোট ১২ বিট, পুরোটাই page offset 0xABC-এর ভেতরে। 0xABC = 2748; index = 2748 ÷ 64-এর ভাগফল = 42, block offset = ভাগশেষ 60. এই দুটি অনুবাদের আগেই জানা।
দুই কাজ একসাথে। একই cycle-এ TLB VPN 0x40403 খোঁজে, আর cache set 42-এর ৮টি way-এর tag (আর ডেটা) পড়ে ফেলে। Cache-কে অনুবাদের জন্য অপেক্ষা করতে হয় না — VIPT-এর পুরো সুবিধা এখানে।
TLB-র উত্তর। TLB hit, PPN = 0x80123. যেহেতু index আর block offset মিলে ঠিক ১২ বিট, physical tag = PA-র বাকি অংশ = PPN নিজেই, 0x80123.
Tag তুলনা। Set 42-এর ৮টি tag-এর সাথে 0x80123 একসাথে তুলনা হয় (৮টি comparator). ধরা যাক way 5-এর tag 0x80123 আর valid — cache hit. TLB miss হলে এখানে walk-এর জন্য অপেক্ষা করতে হতো।
ডেটা ফেরত। Way 5-এর line থেকে byte 60 বাছাই করে load-এর ফল। PA = 0x80123ABC — অংশ ৪-এর walk-এর ফলের সাথে মেলে। মোট সময় ≈ max(TLB, cache-এর set পড়া) + tag তুলনা — যোগফল নয়।

৮ · Effective access time আর virtualization-এর দ্বিমাত্রিক walk

Ns-ভিত্তিক textbook হিসাব OS কোর্সের Effective access time অংশে আছে। এখানে cycle-এ, hardware-এর দৃষ্টিতে: TLB আগে দেখা হয়, miss হলে walk-এর L টি PTE পড়া, তারপর ডেটা।

EAT = t_TLB + (1 − h) × L × t_PTE + t_mem

এখানে h = TLB hit rate, L = walk-এ PTE পড়ার সংখ্যা, t_PTE = প্রতিটি PTE পড়ার গড় সময় (PTE cache-এ থাকলে অনেক কম)। এটি textbook-এর h(t_TLB + m) + (1 − h)(t_TLB + (L + 1)m)-এর সমান, যখন t_PTE = t_mem = m — গুণ খুলে দেখুন।

উদাহরণ: h = ৯৮%, t_TLB = ১ cycle, Sv39 (L = ৩), প্রতিটি PTE DRAM থেকে ১০০ cycle, ডেটা ১০০ cycle. EAT = 1 + 0.02 × 3 × 100 + 100 = ১০৭ cycle; আদর্শ (সব hit) ১০১ cycle. সব access-এ TLB miss হলে (h = ০) প্রতিবার walk: 1 + 300 + 100 = ৪০১ — প্রায় ৪ গুণ।

Virtualization — দুই স্তরের অনুবাদ

Virtual machine-এ অতিথি OS নিজের page table বানায়, যা অতিথির virtual ঠিকানাকে “অতিথির physical” ঠিকানায় নেয়। কিন্তু অতিথির physical আসল RAM নয় — hypervisor আরেকটি টেবিল দিয়ে সেটিকে host-এর physical-এ নেয়। Hardware সহায়তার আগে hypervisor দুটি মিলিয়ে একটি “shadow page table” software-এ রক্ষা করত — প্রতিটি অতিথি-টেবিল বদলে trap, খুব দামি। Nested paging-এ (Intel-এর নাম EPT, AMD-র NPT; ২০০৭–০৮ সালের দিকে বাজারে আসে বলে জানা যায়) MMU নিজেই দুটি টেবিল walk করে। RISC-V-এর hypervisor extension-এও একই ধারণা আছে (“G-stage” অনুবাদ)।

দাম: অতিথির walk-এর প্রতিটি PTE-র ঠিকানাও অতিথি-physical, তাই সেটি পড়তে আগে host-এর পুরো walk! অতিথি n স্তর, host m স্তর হলে:

PTE পড়া = n × (m + 1) + m = (n + 1)(m + 1) − 1

যুক্তি: অতিথির প্রতিটি স্তরে (n টি) host-এর m টি পড়া দিয়ে PTE-র ঠিকানা অনুবাদ, তারপর ১টি পড়া অতিথির PTE নিজেই — n(m + 1). শেষে যে অতিথি-physical ঠিকানা পাওয়া গেল, তার host অনুবাদে আরও m টি। ৪ × ৪-এ: 4 × 5 + 4 = ২৪টি PTE পড়া — native-এর ৪টির ৬ গুণ (সবচেয়ে খারাপ ক্ষেত্র; page-walk cache আর TLB-র অংশবিশেষ এটি অনেক কমায়)। তাই virtual machine-এ host-এর huge page প্রায় অপরিহার্য বলে গণ্য।

নিচের calculator অনুমিত মান দিয়ে কয়েকটি ক্ষেত্র তুলনা করে:

// Effective access time (cycles) with a TLB. All latencies are ASSUMED teaching values.
// EAT = tTLB + (1 - h) * walkRefs * tPTE + tMem      (TLB looked up first, then the data access)
// nested (2D) walk: guest n levels, host m levels -> (n + 1) * (m + 1) - 1 PTE reads
const eat = (h, tTLB, refs, tPTE, tMem) => tTLB + (1 - h) * refs * tPTE + tMem;
const nested = (n, m) => (n + 1) * (m + 1) - 1;
const tTLB = 1, tMem = 100;                     // ideal = every access hits the TLB
const ideal = tTLB + tMem;
const cases = [
  ["h = 0: every access walks",    0,     3,             100],
  ["Sv39, PTEs in DRAM",            0.98,  3,             100],
  ["Sv39, PTEs hit in L2 (20 cy)",  0.98,  3,             20],
  ["x86-64 4-level, DRAM",          0.98,  4,             100],
  ["nested 4x4, DRAM",              0.98,  nested(4, 4),  100],
  ["nested 4x4, h = 99.5%",         0.995, nested(4, 4),  100],
];
console.log("case".padEnd(30) + "walk refs".padStart(10) + "EAT".padStart(8) + "  vs ideal");
for (const [name, h, refs, tPTE] of cases) {
  const e = eat(h, tTLB, refs, tPTE, tMem);
  console.log(name.padEnd(30) + String(refs).padStart(10) + e.toFixed(1).padStart(8) +
              ("x" + (e / ideal).toFixed(3)).padStart(10));
}
for (const [n, m] of [[3, 3], [4, 4], [5, 5]]) console.log(`nested ${n}x${m}: ${nested(n, m)} PTE reads per walk`);
// What hit rate keeps a nested 4x4 walk within 5% of ideal?  (1-h)*24*100 <= 0.05*ideal
const hNeed = 1 - 0.05 * ideal / (nested(4, 4) * 100);
console.log(`nested 4x4 within 5% of ideal needs h >= ${(100 * hNeed).toFixed(2)}%`);

আউটপুট (নির্ধারিত, সব latency অনুমিত):

case                           walk refs     EAT  vs ideal
h = 0: every access walks              3   401.0    x3.970
Sv39, PTEs in DRAM                     3   107.0    x1.059
Sv39, PTEs hit in L2 (20 cy)           3   102.2    x1.012
x86-64 4-level, DRAM                   4   109.0    x1.079
nested 4x4, DRAM                      24   149.0    x1.475
nested 4x4, h = 99.5%                 24   113.0    x1.119
nested 3x3: 15 PTE reads per walk
nested 4x4: 24 PTE reads per walk
nested 5x5: 35 PTE reads per walk
nested 4x4 within 5% of ideal needs h >= 99.79%

প্রথম সারিতে h = 0 — প্রতিটি প্রবেশে walk: ৪০১ cycle, আদর্শের প্রায় ৪ গুণ। ৯৮% hit-এ Sv39-এর খরচ মাত্র ৫.৯% বেশি (১০৭), আর PTE L2-তে পেলে ১.২% (১০২.২) — walk-এর PTE cache-এ থাকা কতটা জরুরি, তা দেখা যায়। x86-64-এর ৪ স্তরে ১০৯. Nested ৪ × ৪-এ একই ৯৮% hit-এ ১৪৯ cycle — প্রায় ৪৭.৫% বেশি; hit rate ৯৯.৫% হলে ১১৩. শেষ লাইন: nested walk-এ আদর্শের ৫%-এর মধ্যে থাকতে hit rate লাগে অন্তত ৯৯.৭৯% — বড় TLB আর huge page ছাড়া প্রায় অসম্ভব। বাস্তবে PTE-গুলোর বড় অংশ cache-এ পাওয়া যায়, তাই আসল খরচ সাধারণত এই সবচেয়ে খারাপ হিসাবের চেয়ে কম।

IOMMU — device-এর জন্য MMU

Network card বা disk controller DMA দিয়ে সরাসরি মেমরিতে লেখে (পর্ব ৫২, Interrupt আর DMA). IOMMU device-এর দেওয়া ঠিকানাকেও page table দিয়ে অনুবাদ আর যাচাই করে — যাতে একটি ভুল বা ক্ষতিকর device যেকোনো মেমরিতে লিখতে না পারে, আর virtual machine-কে সরাসরি একটি device দেওয়া যায়। Intel VT-d, AMD-Vi আর ARM-এর SMMU এর উদাহরণ; এদেরও নিজস্ব TLB (প্রায়ই IOTLB বলা হয়) থাকে।

আরও গভীরে: TLB miss-এর খরচ কমাতে গবেষণা আর শিল্প কয়েক দিকে এগিয়েছে — একটি TLB ঘরে কয়েকটি পাশাপাশি page একসাথে রাখা (coalescing; OS যদি পাশাপাশি VPN-কে পাশাপাশি PPN দেয়, তাহলে hardware তা চিনে নিতে পারে), পুরো বড় একটানা অংশের জন্য একটি “range” অনুবাদ, আর walk-এর পরের স্তর আগেভাগে আনা। Linux-এর transparent huge page সুবিধা OS-এর দিক থেকে ২ MiB page স্বয়ংক্রিয়ভাবে দেওয়ার চেষ্টা করে, তবে মেমরি খণ্ডিত হলে তা ব্যর্থ হতে পারে। কোন বাণিজ্যিক chip ঠিক কোন কৌশল নিয়েছে, তা প্রায়ই প্রকাশিত নয়; বাইরের পরিমাপ থেকে পাওয়া সংখ্যা আন্দাজ হিসেবে নেবেন।

৯ · AI-এর যুগে — virtual memory-র অঙ্কে AI, আর যাচাইয়ের অভ্যাস

AI টুল page table-এর ধারণা ব্যাখ্যায় ভালো, কিন্তু সংখ্যা আর বিটের খুঁটিনাটিতে প্রায়ই ভুল করে। এই বিষয়ে সবচেয়ে বেশি দেখা যায়:

AI-এর প্রচলিত ভুল	ঠিক কথা	কীভাবে যাচাই
RISC-V PTE থেকে PPN পেতে ১২ বিট সরানো	PPN শুরু বিট ১০ থেকে: (PTE >> 10) << 12	এই পর্বের walker-এ PTE বসিয়ে চালানো
Sv39-কে “৪ স্তর” বা Sv48-কে “৩৯ বিট” বলা	Sv39 = ৩ স্তর, 9+9+9+12; Sv48 = ৪ স্তর	RISC-V privileged specification-এর Sv39 অংশ
TLB reach-এ বিট আর byte গুলানো, বা KiB/KB মেশানো	Reach = entry × page size, ২-এর ঘাতে	হাতে গুণ, তারপর script দিয়ে মেলানো
Nested walk-কে “৪ + ৪ = ৮” বলা	(n + 1)(m + 1) − 1 = ২৪	অংশ ৮-এর যুক্তি ধাপে ধাপে গোনা
“VIPT যেকোনো আকারে নিরাপদ”	প্রতি way-এর আকার ≤ page size, নাহলে synonym	set × line = C/W হিসাব করে page size-এর সাথে তুলনা
নির্দিষ্ট CPU-র TLB-র ঘর আত্মবিশ্বাসের সাথে বানিয়ে বলা	নির্মাতার optimization manual বা নিজের পরিমাপ	অংশ ৬-এর benchmark চালিয়ে লাফটি খোঁজা

AI-কে প্রশ্ন করার সময় ISA, page size আর ধাপের হিসাব স্পষ্ট করে চান:

আমি RISC-V-এর virtual memory hardware শিখছি। ISA: RV64, Sv39, page size 4 KiB. ১. VA 0x40A1F123-কে VPN[2], VPN[1], VPN[0] আর offset-এ ভাগ করো, প্রতিটি shift আর mask দেখিয়ে। ২. Sv39 PTE 0x2010005B decode করো: প্রতিটি flag বিট (V R W X U G A D), PPN, আর এটি L1-এ leaf হলে কত বড় page এবং PA কত — বিট ধরে দেখাও। ৩. Guest 4-level আর host 4-level nested paging-এ একটি TLB miss-এ সবচেয়ে খারাপ ক্ষেত্রে কতটি মেমরি-পড়া হয়? সূত্রটি প্রমাণ করো। ৪. যে কথা কোনো নির্দিষ্ট chip-এর (TLB-র আকার, latency) ওপর নির্ভর করে, তা আলাদা করে চিহ্নিত করো, আর বলো কোন নথিতে মিলিয়ে দেখব। MIPS বা x86-এর নিয়ম RISC-V-এর সাথে মিশিও না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

VA-র ভাগ নিজে hex-এ বের করেছি (offset = নিচের ৩টি hex অঙ্ক) আর AI-এর সাথে মিলিয়েছি
PTE-র PPN বিট ১০ থেকে নেওয়া হয়েছে কি না দেখেছি, আর walker-এ মান বসিয়ে চালিয়েছি
Superpage-এর ক্ষেত্রে PA-র নিচের অংশ VA থেকে এসেছে আর alignment-এর শর্ত দেখা হয়েছে
TLB reach আর table size-এর একক (KiB, MiB, GiB) ২-এর ঘাতে হিসাব করেছি
EAT-এর সূত্রে TLB সময় আর walk-এর সংখ্যা ঠিক জায়গায় বসেছে কি না calculator দিয়ে মিলিয়েছি
নির্দিষ্ট chip-এর দাবি (TLB-র ঘর, L1-এর আকার) নির্মাতার নথিতে বা নিজের পরিমাপে খুঁজেছি

পরীক্ষা ও ইন্টারভিউতে এই বিষয়ে প্রায়ই যা জিজ্ঞেস করা হয়:

৩২-bit VA, ৪ KiB page, ৪ byte PTE — এক স্তরের page table কত বড়? — 2²⁰ × ৪ = ৪ MiB প্রতি process.
Multi-level page table কেন জায়গা বাঁচায়? — অব্যবহৃত অংশের নিচের টেবিল থাকেই না; ওপরের স্তরের একটি অবৈধ ঘর পুরো অংশ ঢাকে।
TLB reach কী, বাড়াবেন কীভাবে? — entry × page size; বেশি ঘর বা huge page.
VIPT cache-এর আকারের সীমা কেন? — index + offset page offset-এর মধ্যে না থাকলে synonym; তাই আকার ≤ way × page size.
ASID কেন দরকার? — ভিন্ন process-এর একই VPN আলাদা রাখতে, যাতে context switch-এ TLB মুছতে না হয়।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন।

প্র ০১৪ KiB page প্রায় চার দশক ধরে টিকে আছে, অথচ RAM হাজার গুণ বেড়েছে। বড় page সব জায়গায় কেন ব্যবহার হয় না?

Virtual memory-র ধারণা প্রথম বাস্তবে আসে ১৯৬০-এর দশকের শুরুতে Manchester বিশ্ববিদ্যালয়ের Atlas কম্পিউটারে, যেখানে ছোট core memory আর বড় drum-এর মধ্যে page স্বয়ংক্রিয়ভাবে আনা-নেওয়া হতো। পরের দশকগুলোতে page size যন্ত্রভেদে ভিন্ন ছিল — ১৯৭০-এর দশকের শেষে DEC-এর VAX ৫১২ byte-এর page ব্যবহার করত। ১৯৮৫ সালে Intel 80386 x86-এ paging আনে ৪ KiB page দিয়ে, আর x86-এর বিপুল software ভিত্তির কারণে সেই আকার কার্যত মান হয়ে যায়। RISC-V-ও ৪ KiB-কে মূল page হিসেবে বেছে নিয়েছে।

বড় page-এর দাম কয়েকটি। প্রথম, internal fragmentation: একটি ছোট প্রোগ্রাম বা প্রতিটি thread-এর stack-ও অন্তত একটি পুরো page নেয়; ২ MiB page-এ হাজারো ছোট process-এ অনেক RAM নষ্ট। দ্বিতীয়, copy-on-write আর disk-এ আনা-নেওয়া: একটি byte বদলালে পুরো page কপি করতে বা লিখতে হয় — page যত বড়, কাজ তত বেশি। তৃতীয়, বড় একটানা aligned physical জায়গা খুঁজে পাওয়া কঠিন, বিশেষত যন্ত্র অনেকক্ষণ চলার পর মেমরি খণ্ডিত হলে। চতুর্থ, পুরোনো software অনেক সময় ধরে নেয় page = ৪ KiB.

তাই শিল্প মাঝামাঝি পথ নিয়েছে: মূল page ছোট, আর দরকারি জায়গায় superpage — database-এর buffer, virtual machine-এর মেমরি, বড় বৈজ্ঞানিক array. Linux-এর transparent huge page এটি স্বয়ংক্রিয়ভাবে করার চেষ্টা করে। কিছু প্ল্যাটফর্ম মূল page-ই বাড়িয়েছে — প্রকাশিত তথ্য অনুযায়ী কিছু ARM-ভিত্তিক ল্যাপটপ আর ফোনের OS ১৬ KiB page ব্যবহার করে, যা TLB reach চার গুণ করে আর VIPT L1-কে বড় হতে দেয় (অংশ ৭)। কিন্তু এমন বদলে পুরোনো software-কে নতুন করে পরীক্ষা করতে হয়।

মূল উপলব্ধি: page size একটি দর-কষাকষি — ছোট page নমনীয়তা দেয়, বড় page TLB-র গতি দেয়। আধুনিক সমাধান একটি আকার বেছে নেওয়া নয়, বরং একই সিস্টেমে কয়েকটি আকার একসাথে চালানো।

প্র ০২MIPS-এর মতো কিছু RISC নকশা TLB miss software-এ সামলাত, অথচ x86 আর আজকের বেশিরভাগ RISC-V core hardware walker রাখে। এই দুই দর্শনের পার্থক্য কী, আর পাল্লা কেন hardware-এর দিকে ঝুঁকল?

১৯৮০-এর দশকের RISC আন্দোলনের মূলমন্ত্র ছিল: hardware-এ শুধু সেটুকু রাখা, যা প্রতিটি cycle-এ লাগে; বাকিটা software-এর দায়িত্ব। MIPS-এর প্রথম দিকের chip-এ একটি ছোট fully associative TLB ছিল বলে জানা যায়, আর miss হলে একটি বিশেষ exception — OS-এর কয়েক ডজন instruction-এর একটি handler টেবিল খুঁজে বিশেষ instruction দিয়ে ঘর লিখত। লাভ: chip সরল, আর OS যেকোনো টেবিল-কাঠামো (multi-level, hashed, inverted) বেছে নিতে পারে। ১৯৯০-এর দশকে DEC Alpha একই ধারণা নেয়, তবে handler রাখে PALcode নামের একটি বিশেষ firmware স্তরে।

কিন্তু সময়ের সাথে পাল্লা বদলাল। প্রথম, pipeline গভীর আর out-of-order হলো (পর্ব ৪০)। Exception মানে শত instruction-এর জানালা flush করা, তারপর handler চালানো, তারপর আবার ভরা — একটি miss-এর খরচ কয়েকশো cycle ছাড়িয়ে যায়। Hardware walker-এ miss হলে শুধু সেই load অপেক্ষা করে, বাকি স্বাধীন instruction চলতে থাকে, আর একাধিক walk একসাথে চলতে পারে। দ্বিতীয়, বড় মেমরির workload-এ TLB miss খুব ঘন হলো — প্রতিটির খরচ সরাসরি গতিতে প্রতিফলিত। তৃতীয়, transistor সস্তা হলো; একটি walker state machine chip-এর তুলনায় নগণ্য জায়গা নেয়।

Hardware walker-এর দাম হলো নমনীয়তা হারানো: page table-এর বিন্যাস ISA-তে চিরকালের জন্য বাঁধা, আর virtualization-এর মতো নতুন প্রয়োজনে (অংশ ৮) hardware-কেই নতুন walk শিখতে হয়। RISC-V মাঝামাঝি অবস্থান নিয়েছে: privileged specification টেবিলের বিন্যাস আর walk-এর algorithm নির্দিষ্ট করে, তবে বলা হয় খুব ছোট বাস্তবায়ন সেই algorithm M-mode firmware-এ trap দিয়েও চালাতে পারে — software-এর কাছে আচরণ একই থাকে।

মূল উপলব্ধি: কোনো কাজ hardware-এ না software-এ, তার উত্তর প্রযুক্তির সাথে বদলায়। যে কাজ যথেষ্ট ঘন আর যার দেরি pipeline আটকে দেয়, সেটি শেষ পর্যন্ত hardware-এ চলে আসে — আর নমনীয়তা রক্ষা করা হয় ISA-তে একটি পরিষ্কার চুক্তি লিখে।

প্র ০৩Virtual machine-এর জন্য hardware-এ nested paging আসার আগে hypervisor কীভাবে মেমরি অনুবাদ সামলাত, আর nested paging কোন নতুন সমস্যা তৈরি করল?

২০০০-এর দশকের শুরুতে x86-এ virtualization জনপ্রিয় হয়, কিন্তু MMU জানত শুধু একটি টেবিল। Hypervisor তাই একটি কৌশল নিত: অতিথি OS-এর টেবিলকে hardware-এ বসানো হতো না; তার বদলে hypervisor একটি “shadow page table” বানাত, যা অতিথির virtual ঠিকানাকে সরাসরি host-এর physical ঠিকানায় নেয়। অতিথির টেবিলের page গুলো write-protected রাখা হতো, যাতে অতিথি টেবিল বদলালে trap হয় আর hypervisor shadow টেবিল হালনাগাদ করে। TLB-র গতি native-এর মতো ছিল, কিন্তু অতিথির প্রতিটি page table বদল — process তৈরি, page fault, context switch — একটি দামি trap. Process-ভারী workload-এ এটি বড় বোঝা ছিল।

২০০৭–০৮ সালের দিকে AMD (NPT/RVI) আর Intel (EPT) hardware-এ দ্বিতীয় স্তরের অনুবাদ আনে বলে জানা যায়। এখন অতিথি নিজের টেবিল স্বাধীনভাবে বদলায়, কোনো trap ছাড়া; MMU দুটি টেবিল মিলিয়ে walk করে। কিন্তু অংশ ৮-এর হিসাব অনুযায়ী সবচেয়ে খারাপ ক্ষেত্রে একটি TLB miss-এ ২৪টি PTE পড়া — native-এর ৬ গুণ। সেই সময়ের প্রকাশিত গবেষণায় দেখানো হয়, এই দ্বিমাত্রিক walk-এর খরচ কমাতে page-walk cache-এর বিশেষ নকশা কতটা কাজে আসে।

বাস্তবে খরচ কমানো হয় কয়েক স্তরে: TLB-তে সরাসরি অতিথি-virtual → host-physical অনুবাদ রাখা (তাই hit-এর পথ native-এর মতোই), host-এর দিকে ২ MiB বা ১ GiB page (তাতে m কমে), অতিথির দিকে huge page (n কমে), আর বড় page-walk cache. আর কিছু ক্ষেত্রে, যেখানে অতিথি খুব ঘন ঘন টেবিল বদলায় না কিন্তু TLB miss অনেক, পুরোনো shadow পদ্ধতিই দ্রুত — কিছু hypervisor তাই দুই পদ্ধতির মধ্যে বদলানোর বিকল্প রেখেছিল বলে জানা যায়। RISC-V-এর hypervisor extension শুরু থেকেই দুই স্তরের অনুবাদ নকশায় রেখেছে।

মূল উপলব্ধি: একটি software-এর বোঝা (trap) hardware-এ সরালে প্রায়ই খরচ অন্য জায়গায় সরে যায় (দীর্ঘ walk). ভালো নকশা খরচটি চেনে আর সেখানেই আলাদা cache বা বড় page দিয়ে প্রতিকার করে।

প্র ০৪L1 data cache বহু বছর ৩২ KiB-এ আটকে ছিল, অথচ L2 আর L3 অনেক বেড়েছে। VIPT-এর নিয়ম এর পেছনে কতটা দায়ী, আর নকশাকারেরা কীভাবে এই সীমা পেরোন?

L1-এর নকশায় সবচেয়ে বড় শত্রু সময়: load-to-use latency সাধারণত মাত্র কয়েক cycle, আর প্রতিটি বাড়তি cycle প্রায় প্রতিটি নির্ভরশীল instruction-কে দেরি করায়। TLB আর cache পরপর খুঁজলে (PIPT) সময় যোগ হয়, তাই L1 প্রায় সবসময় VIPT. অংশ ৭-এর নিয়ম তখন সরাসরি আকার বেঁধে দেয়: ৪ KiB page-এ প্রতি way সর্বোচ্চ ৪ KiB. ৩২ KiB পেতে 8-way — আর way বাড়ানো সস্তা নয়: প্রতিটি way-এর জন্য একটি tag comparator, বেশি তার, বেশি শক্তি, আর ধীর বাছাই (mux). অনেক প্রজন্মের x86 core-এ ৩২ KiB 8-way L1 data cache এই ভারসাম্যের ফল বলে ব্যাপকভাবে ব্যাখ্যা করা হয়।

সীমা পেরোনোর পথ কয়েকটি। প্রথম, আরও way: প্রকাশিত তথ্য অনুযায়ী সাম্প্রতিক কিছু x86 core ৪৮ KiB 12-way L1 data cache ব্যবহার করে — প্রতি way আবার ঠিক ৪ KiB. দ্বিতীয়, বড় page: কিছু ARM-ভিত্তিক প্ল্যাটফর্মের ১৬ KiB page-এ 8-way VIPT ১২৮ KiB পর্যন্ত যেতে পারে, আর এমন বড় L1 data cache-এর কথা প্রকাশিত বিশ্লেষণে এসেছে। তৃতীয়, hardware-এ synonym ধরা: index-এর বাড়তি বিটের সম্ভাব্য সব মানের set খোঁজা, বা L2-তে প্রতিটি line-এর কোন VA-র রঙে L1-এ আছে তা মনে রাখা, যাতে দ্বিতীয় কপি তৈরি হলে আগেরটি সরানো যায়। চতুর্থ, software-এর সহায়তা — page colouring, যেখানে OS নিশ্চিত করে যে একই physical page-এর সব VA-র “রঙ” (index-এর VPN-বিট) এক।

Instruction cache-এ synonym-এর সমস্যা কম, কারণ কোড সাধারণত লেখা হয় না — তাই সেখানে নকশাকারেরা কিছুটা বেশি স্বাধীনতা নেন। আর অনেক নকশায় L1 ছোট রেখে তার পেছনে দ্রুত L2 দিয়ে AMAT কমানো হয় (পর্ব ৪৭-এর বহু-স্তরের সূত্র)।

মূল উপলব্ধি: একটি ছোট সংখ্যা — page size — cache-এর মতো সম্পূর্ণ ভিন্ন অংশের আকার নিয়ন্ত্রণ করতে পারে। আর্কিটেকচারে অংশগুলো আলাদা দেখালেও তাদের সীমা একে অপরের সাথে বাঁধা।

প্র ০৫Cache-এর জন্য hardware coherence আছে, কিন্তু TLB-র জন্য সাধারণত OS-কে shootdown করতে হয়। কেন এই পার্থক্য, আর বহু core-এর যুগে এর দাম কী?

Cache coherence (পর্ব ৫৩) নিশ্চিত করে যে একটি core মেমরিতে লিখলে অন্য core-এর cache-এ সেই line-এর পুরোনো কপি বাতিল হয়। Page table-ও মেমরিতে থাকে, তাই PTE-র লেখা অন্য core-এর data cache-এ ঠিকই পৌঁছায়। কিন্তু TLB হলো PTE-র একটি অনুবাদিত, প্রক্রিয়াজাত কপি — কোন physical ঠিকানার PTE থেকে কোন TLB ঘর এসেছে, তা TLB সাধারণত মনে রাখে না, আর walk-এর মাঝের স্তরগুলো page-walk cache-এ ছড়িয়ে থাকে। প্রতিটি TLB ঘরকে coherence-এর snoop-এ যুক্ত করা জায়গা আর শক্তিতে দামি, তাই বেশিরভাগ ISA দায়িত্ব দিয়েছে software-কে: PTE বদলে স্পষ্ট নির্দেশ দিয়ে TLB বাতিল করা — RISC-V-এ sfence.vma, x86-এ invlpg.

একটি core-এ এটি সস্তা। কিন্তু একটি process-এর thread যদি ৬৪টি core-এ চলে, আর একটি thread একটি মেমরি অংশ ফেরত দেয়, তাহলে বাকি ৬৩টি core-কে জানাতে হবে। x86-এ এর জন্য inter-processor interrupt: প্রতিটি core কাজ থামিয়ে handler চালায়, ঘর বাতিল করে, উত্তর দেয়, আর পাঠানো core সবার উত্তরের জন্য অপেক্ষা করে। Core যত বেশি, অপেক্ষা তত দীর্ঘ। ARMv8 এখানে ভিন্ন পথ নিয়েছে: TLB বাতিলের instruction-এর একটি রূপ hardware নিজেই একই “shareable” অঞ্চলের সব core-এ পাঠায়, interrupt ছাড়াই। RISC-V-এ প্রচলিত পথ হলো firmware-এর (SBI) মাধ্যমে অন্য hart-কে remote fence করতে বলা; ভবিষ্যতে hardware-সহায়তার প্রস্তাবও আলোচিত হয়েছে বলে জানা যায়।

OS-ও খরচ কমায়: কাজ জমিয়ে একবারে shootdown, শুধু যে core-গুলো সত্যিই সেই address space চালিয়েছে তাদের জানানো, আর কিছু ক্ষেত্রে অলসভাবে (lazy) — core যখন পরে সেই address space-এ ফেরে, তখনই মোছা। মেমরি বরাদ্দ-ফেরতের খুব ঘন workload-এ shootdown পরিমাপযোগ্য বোঝা হতে পারে বলে বিভিন্ন পরিমাপে দেখা গেছে।

মূল উপলব্ধি: প্রতিটি কপি — cache line হোক বা TLB ঘর — একটি সামঞ্জস্যের দায় তৈরি করে। কে সেই দায় নেবে, hardware না software, তা নির্ধারণ করে খরচ কোথায় পড়বে; বহু core-এর যুগে এই সিদ্ধান্ত গতির ওপর সরাসরি প্রভাব ফেলে।

অনুশীলন

পরীক্ষার ধাঁচে লেখা — আগে খাতায় সমাধান করুন, তারপর উত্তর মিলিয়ে নিন।

Page table-এর আকার আর ঠিকানার ভাগ: (ক) একটি যন্ত্রে VA ৩২ বিট, PA ৩৬ বিট, page ৮ KiB. Offset, VPN আর PPN কত বিট? এক স্তরের page table-এ কয়টি ঘর? প্রতিটি PTE-তে PPN আর ৪টি flag বিট থাকলে, আর PTE-কে পূর্ণ byte-এ গোল করে ৪ byte ধরলে, টেবিল কত বড়? (খ) একটি Sv39 process ঠিকানা 0 থেকে ৮ MiB একটানা (কোড আর ডেটা) আর 2³⁸-এর ঠিক নিচে ১ MiB stack ব্যবহার করে। Page table-এর কয়টি page লাগবে, মোট কত KiB? এক স্তরের টেবিলের সাথে তুলনা করুন।
- (ক) ৮ KiB = 2¹³, তাই offset = ১৩ বিট; VPN = ৩২ − ১৩ = ১৯ বিট; PPN = ৩৬ − ১৩ = ২৩ বিট. ঘর = 2¹⁹ = ৫,২৪,২৮৮টি। PTE = ২৩ + ৪ = ২৭ বিট → ৪ byte. টেবিল = 2¹⁹ × ৪ = ২ MiB.
- (খ) Root: ১টি. ০–৮ MiB অংশ VPN[2] = 0-এর ১ GiB-এর মধ্যে → ১টি L1 টেবিল; ৮ MiB ÷ ২ MiB = ৪টি L0 টেবিল। Stack: 2³⁸ − ১ MiB = 0x3FFFF00000 থেকে; VPN[2] = 0x3FFFF00000 >> 30 = ২৫৫ → আরেকটি L1 টেবিল; পুরো ১ MiB শেষ ২ MiB ব্লকের (0x3FFFE00000 থেকে) ভেতরে → ১টি L0 টেবিল।
- মোট = ১ + ২ + ৫ = ৮টি page = ৩২ KiB. এক স্তরের Sv39 টেবিল হতো ১ GiB — প্রায় ৩২,৭৬৮ গুণ বড়। দাম: প্রতিটি TLB miss-এ ১টির বদলে ৩টি PTE পড়া।
Sv32 PTE decode আর ফল আন্দাজ: (ক) Sv32 leaf PTE = 0x0C8A44CF. সব flag বিট, PPN, PPN[1] আর PPN[0] লিখুন। VA-র offset 0x7F0 হলে PA কত? (খ) এই page user mode থেকে পড়া যাবে? Supervisor mode থেকে চালানো যাবে? (গ) অংশ ৪-এর walker-এর শেষ লাইনের পরে walk("Sv39", 0x80000n, m39, 0x40A1F123n, "r"); যোগ করলে কী ছাপা হবে, আন্দাজ করুন।
- (ক) নিচের byte 0xCF = 1100 1111: V=1, R=1, W=1, X=1, U=0, G=0, A=1, D=1 (VRWX--AD). RSW = ০। PPN = 0x0C8A44CF >> 10 = 0x32291; PPN[1] = 0x32291 >> 10 = 0xC8, PPN[0] = 0x291. PA = 0x32291000 + 0x7F0 = 0x322917F0.
- (খ) U = 0, তাই user mode-এর যেকোনো প্রবেশে page fault (load-এ cause ১৩)। Supervisor mode-এ X = 1 আর U = 0, তাই চালানো যাবে — এটি একটি kernel-এর পড়া-লেখা-চালানো page (বাস্তবে নিরাপত্তার জন্য kernel সাধারণত W আর X একসাথে রাখে না)।
- (গ) একই superpage, এবার load. R = 1, তাই চলবে: Sv39 r VA 0x40a1f123 VPN = [1, 5, 31], তারপর একই দুটি L2 আর L1 লাইন, শেষে => leaf at L1 (2048 KiB page) PA = 0x8041f123 [2 PTE reads]. Fetch-এর ফলের সাথে হুবহু এক — অনুমতি বদলায় শুধু fault হবে কি না, ঠিকানা নয়।
TLB-সহ effective access time: TLB hit rate ৯৮%, TLB ১ cycle, Sv39 walk (৩টি PTE, প্রতিটি ১০০ cycle), ডেটা-প্রবেশ ১০০ cycle. (ক) EAT কত? (খ) EAT ১০৫ cycle-এর মধ্যে রাখতে hit rate অন্তত কত লাগবে? (গ) ২ MiB page ব্যবহারে walk ২টি PTE-তে নামে আর hit rate ৯৯.৫%-এ ওঠে — নতুন EAT? (ঘ) একই প্রোগ্রাম virtual machine-এ, অতিথি ও host দুই দিকেই ৪ স্তর, hit rate ৯৮% — সবচেয়ে খারাপ ক্ষেত্রে EAT?
- (ক) EAT = 1 + 0.02 × 3 × 100 + 100 = 1 + 6 + 100 = ১০৭ cycle.
- (খ) 1 + (1 − h) × 300 + 100 ≤ 105 → (1 − h) × 300 ≤ 4 → 1 − h ≤ 0.01333 → h ≥ ৯৮.৬৭% (প্রায়)।
- (গ) 1 + 0.005 × 2 × 100 + 100 = 1 + 1 + 100 = ১০২ cycle — huge page একসাথে দুই দিকে লাভ দেয়: কম miss, ছোট walk.
- (ঘ) Nested walk = (4 + 1)(4 + 1) − 1 = ২৪টি PTE. EAT = 1 + 0.02 × 24 × 100 + 100 = 1 + 48 + 100 = ১৪৯ cycle — native-এর ১০৭-এর তুলনায় প্রায় ৩৯% বেশি। অংশ ৮-এর calculator-এর সারির সাথে মেলান।
VIPT-এর আকারের সীমা: page size ৪ KiB, line ৬৪ B. (ক) ৩২ KiB, 8-way L1 কি synonym ছাড়া VIPT হতে পারে? set, index আর offset বিট দেখান। (খ) ৬৪ KiB L1 VIPT রাখতে, synonym ছাড়া, কমপক্ষে কত way লাগবে? (গ) কেউ ৬৪ KiB, 8-way VIPT বানাল। একটি physical line সম্ভাব্য কয়টি set-এ বসতে পারে, আর কেন?
- (ক) set = 32768 ÷ (8 × 64) = ৬৪ → index ৬ বিট, block offset ৬ বিট, মোট ১২ = page offset. প্রতি way ৪ KiB ≤ ৪ KiB — হ্যাঁ, ঠিক সীমায়.
- (খ) C / W ≤ P → W ≥ 65536 ÷ 4096 = ১৬-way.
- (গ) প্রতি way ৮ KiB → index + offset = ১৩ বিট, যার সবচেয়ে ওপরের বিট (বিট ১২) VPN থেকে আসে। একই physical page দুটি VA-তে map হলে সেই বিট ভিন্ন হতে পারে, তাই line টি ২টি ভিন্ন set-এ বসতে পারে (2^{13 − 12} = ২)। প্রতিকার: hardware-এ দুই set খোঁজা, OS-এর page colouring, বা 16-way.

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমSv39-এ একটি load-এর TLB miss হলো। Hardware walker-এর ঘটনাগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

VA-কে VPN[2], VPN[1], VPN[0] আর offset-এ ভাগ করা
satp.PPN × 4096 + VPN[2] × 8 ঠিকানা থেকে root PTE পড়া
Root PTE-র PPN দিয়ে L1 টেবিলে VPN[1]-এর ঘর পড়া
L0 টেবিলে VPN[0]-এর ঘর পড়ে leaf PTE পাওয়া
R বিট, U বিট আর A বিট যাচাই করা
PPN × 4096 + offset দিয়ে PA বানিয়ে TLB-তে অনুবাদ রাখা

৩২-bit virtual ঠিকানা, ৪ KiB page আর ৪ byte PTE-র একটি এক স্তরের page table-এর আকার প্রতি process-এ কত?

৪ KiB
৪ MiB
৪ GiB
১ MiB

RISC-V Sv32-এর একটি PTE-র মান 0x200040D7. এর PPN কত?

0x20004
0xD7
0x80010
0x80010000

Sv39-এ একটি leaf PTE L1 স্তরে (মাঝের স্তরে) পাওয়া গেল। এই অনুবাদ কত বড় মেমরি ঢাকে, আর walk-এ কয়টি PTE পড়া হলো?

৪ KiB, ৩টি
১ GiB, ১টি
৪ MiB, ২টি
২ MiB, ২টি

একটি L2 TLB-তে ১৫৩৬টি ঘর। সব ঘরে ২ MiB page থাকলে TLB reach কত?

৩ GiB
৬ MiB
১৫৩৬ GiB
৭৬৮ MiB

৪ KiB page আর ৬৪ B line-এর একটি যন্ত্রে, synonym সমস্যা ছাড়া VIPT L1 cache রাখতে চাইলে নিচের কোন নকশা চলবে না?

৩২ KiB, 8-way
৪৮ KiB, 12-way
৬৪ KiB, 8-way
১৬ KiB, 4-way

TLB hit rate ৯৮%, TLB lookup ১ cycle, TLB miss-এ ৩টি PTE পড়া (প্রতিটি ১০০ cycle), আর ডেটা-প্রবেশ ১০০ cycle. Effective access time কত?

১০১ cycle
১০৭ cycle
১০৩ cycle
৪০১ cycle

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

অনুবাদ: VA = VPN | offset → PA = PPN | offset; offset অপরিবর্তিত। MMU একই সাথে R/W/X/U অনুমতি যাচাই করে, ভাঙলে page fault (RISC-V-এ cause ১২, ১৩, ১৫)।
টেবিলের আকার: এক স্তর = 2^{VPN বিট} × PTE (৩২-bit-এ ৪ MiB). Multi-level-এ শুধু ব্যবহৃত অংশ: Sv32 10|10|12, Sv39 9|9|9|12, x86-64 ৪ বা ৫ স্তর; প্রতিটি টেবিল ঠিক একটি ৪ KiB page.
RISC-V PTE: নিচের ৮ বিট V R W X U G A D, PPN বিট ১০ থেকে; R = W = X = 0 মানে pointer. Root আসে satp থেকে (MODE, ASID, PPN). উঁচু স্তরে leaf = superpage (Sv39-এ ২ MiB, ১ GiB), aligned হতে হয়।
TLB: অনুবাদের cache; reach = entry × page size; miss-এ hardware walker (বা পুরোনো নকশায় software); ASID/PCID context switch-এ flush বাঁচায়; multicore-এ পরিবর্তনের পর shootdown.
Cache আর খরচ: VIPT L1-এ আকার ≤ way × page size; EAT = t_TLB + (1 − h) × L × t_PTE + t_mem; nested walk (n + 1)(m + 1) − 1 = ২৪ (৪ × ৪)।

পরের পর্বে: মডিউল ৯ শুরু — CPU কীভাবে keyboard, disk আর network card-এর সাথে কথা বলে। Memory-mapped I/O, port I/O, আর PCIe ও USB-এর মতো bus কীভাবে কাজ করে।

Virtual memory-র hardware — page table, TLB আর page walk

এই পর্বে যা শিখবেন

১ · কেন virtual memory, আর MMU-র কাজ কী

ঠিকানার দুই ভাগ — VPN আর offset

২ · এক স্তরের page table কেন অচল — আকারের হিসাব

৩ · RISC-V Sv32 — দুই স্তর, PTE-র বিট আর `satp`

PTE-র ভেতরে — বিট ধরে ধরে

হাতে-কলমে: hex-এ একটি PTE decode করা

`satp` — টেবিলের মূল কোথায়

৪ · Sv39, Sv48 আর x86-64 — তিন, চার, পাঁচ স্তরের walk

Sv39 walk — একটি নির্দিষ্ট ঠিকানায়, ধাপে ধাপে

৫ · Superpage, A/D বিট, অনুমতি আর page fault-এর পথ

Superpage — উঁচু স্তরে leaf

A আর D বিট — কে হালনাগাদ করে

অনুমতির নিয়ম আর page fault

৬ · TLB — অনুবাদের cache

গঠন — cache-এর মতোই, ছোট আকারে

TLB reach — TLB কতটা মেমরি ঢাকে

TLB miss কে সামলায়

ASID — context switch-এ TLB না মুছে

TLB shootdown — একাধিক core-এ

নিজের হাতে TLB-র প্রভাব মাপা

৭ · Cache-এর সাথে TLB — PIPT, VIPT, VIVT আর synonym

PIPT

VIPT

VIVT

Synonym সমস্যা আর VIPT-এর আকারের সীমা

৮ · Effective access time আর virtualization-এর দ্বিমাত্রিক walk

Virtualization — দুই স্তরের অনুবাদ

IOMMU — device-এর জন্য MMU

৯ · AI-এর যুগে — virtual memory-র অঙ্কে AI, আর যাচাইয়ের অভ্যাস

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

অনুশীলন

নিজেকে যাচাই করুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বে যা শিখবেন

১ · কেন virtual memory, আর MMU-র কাজ কী

ঠিকানার দুই ভাগ — VPN আর offset

২ · এক স্তরের page table কেন অচল — আকারের হিসাব

৩ · RISC-V Sv32 — দুই স্তর, PTE-র বিট আর satp

PTE-র ভেতরে — বিট ধরে ধরে

হাতে-কলমে: hex-এ একটি PTE decode করা

satp — টেবিলের মূল কোথায়

৪ · Sv39, Sv48 আর x86-64 — তিন, চার, পাঁচ স্তরের walk

Sv39 walk — একটি নির্দিষ্ট ঠিকানায়, ধাপে ধাপে

৫ · Superpage, A/D বিট, অনুমতি আর page fault-এর পথ

Superpage — উঁচু স্তরে leaf

A আর D বিট — কে হালনাগাদ করে

অনুমতির নিয়ম আর page fault

৬ · TLB — অনুবাদের cache

গঠন — cache-এর মতোই, ছোট আকারে

TLB reach — TLB কতটা মেমরি ঢাকে

TLB miss কে সামলায়

ASID — context switch-এ TLB না মুছে

TLB shootdown — একাধিক core-এ

নিজের হাতে TLB-র প্রভাব মাপা

৭ · Cache-এর সাথে TLB — PIPT, VIPT, VIVT আর synonym

PIPT

VIPT

VIVT

Synonym সমস্যা আর VIPT-এর আকারের সীমা

৮ · Effective access time আর virtualization-এর দ্বিমাত্রিক walk

Virtualization — দুই স্তরের অনুবাদ

IOMMU — device-এর জন্য MMU

৯ · AI-এর যুগে — virtual memory-র অঙ্কে AI, আর যাচাইয়ের অভ্যাস

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

অনুশীলন

নিজেকে যাচাই করুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

৩ · RISC-V Sv32 — দুই স্তর, PTE-র বিট আর `satp`

`satp` — টেবিলের মূল কোথায়