TLB আর বড় page table — multilevel, hashed আর inverted

১ · প্রতিটি ঠিকানায় দুবার মেমরি — সমস্যাটা কোথায়

পর্ব ৩২-এ দেখেছেন, paging-এ প্রসেসের virtual address দুই ভাগে ভাঙে — page number আর offset. Page number দিয়ে page table-এ খুঁজে পাওয়া যায় কোন frame-এ ডেটা আছে; তারপর frame number-এর পাশে offset বসালেই physical address. নিয়মটি সুন্দর, কিন্তু একটি বড় খরচ লুকিয়ে আছে: page table নিজেই মেমরিতে থাকে।

অর্থাৎ প্রোগ্রাম যখন একটি ভ্যারিয়েবল পড়ে, CPU-কে আসলে দুবার মেমরিতে যেতে হয় — প্রথমে page table থেকে সেই page-এর page table entry (PTE) পড়া, তারপর আসল ডেটা পড়া। মেমরি একবার পড়তে ১০০ ns লাগলে প্রতিটি ছোঁয়ায় ২০০ ns. প্রোগ্রাম রাতারাতি অর্ধেক গতির হয়ে গেল — শুধু সুরক্ষা আর নমনীয়তার জন্য। কেউ এই দাম দিতে রাজি হতো না।

কাজ করে কেন? কারণ প্রোগ্রাম মেমরির সব জায়গা সমানভাবে ছোঁয় না — পর্ব ৪-এর locality. একটি ৪ KiB page-এর মধ্যে সাধারণত অনেকগুলো পরপর ছোঁয়া পড়ে (একটি লুপ, একটি array, stack-এর ওপরের অংশ)। তাই অল্প কয়েকটি page-এর অনুবাদ মনে রাখলেই বেশিরভাগ ছোঁয়া মিটে যায়।

২ · TLB — page table-এর ছোট, দ্রুত cache

TLB থাকে MMU-এর ভেতরে, CPU-র একদম কাছে। এর প্রতিটি entry মোটামুটি এরকম: একটি tag (virtual page number), সংশ্লিষ্ট frame number, অনুমতির bit (পড়া/লেখা/চালানো, user না kernel), আর প্রায়ই একটি address-space নম্বর (ASID, x86-এ PCID), যাতে কোন প্রসেসের অনুবাদ তা আলাদা করা যায়। Process switch-এ TLB-র কী হয়, ASID/PCID কীভাবে মুছে ফেলার খরচ বাঁচায় — সেটি পর্ব ৯-এর খরচের অংশে বিস্তারিত দেখেছেন; এখানে আর পুনরাবৃত্তি করছি না।

TLB নিজেও স্তরে স্তরে সাজানো থাকে: instruction আর data-র জন্য আলাদা ছোট L1 TLB (খুব দ্রুত), তাদের পেছনে একটি বড় যৌথ L2 TLB. সংখ্যাগুলো প্রসেসর-প্রজন্মভেদে আলাদা, তাই এই পর্বে উদাহরণ হিসেবে ধরা হবে L1-এ ৬৪টি আর L2-তে ১৫৩৬টি entry — আধুনিক desktop প্রসেসরে এর কাছাকাছি সংখ্যা দেখা যায়, কিন্তু আপনার মেশিনে আলাদা হতে পারে।

নিচের stepper-এ একটি ৪-entry TLB দেখুন (page size ৪ KiB, তাই ঠিকানার শেষ ১২ bit = শেষ ৩টি hex অঙ্ক offset). প্রথমে একটি hit, তারপর একটি miss. TLB-র লাইনগুলো বাঁ থেকে ডানে “সবচেয়ে পুরোনো ব্যবহার” থেকে “সবচেয়ে সাম্প্রতিক”-এ সাজানো — জায়গা না থাকলে বাঁয়েরটি বাদ যায়, যাকে বলে LRU.

1 VA 0x40A10 -> VPN 0x40, offset 0xA102 compare 0x40 with ALL tags at once -> HIT3 PA = frame 0x07 + 0xA10 = 0x07A10, read data4 VA 0x99123 -> VPN 0x99: no tag matches -> MISS5 page walk: read PTE[0x99] from memory -> 0x2E6 evict LRU 0x12, insert 0x99->0x2E, read data

এখানে hit ratio (h) মানে মোট ছোঁয়ার কত ভাগ TLB-তে মিলল। বাস্তব প্রোগ্রামে এটি সাধারণত ৯৯%-এর আশেপাশে বা বেশি থাকে — কারণ একটি ৪ KiB page-এ ৬৪টি cache line, আর লুপ একই page বারবার ছোঁয়। কিন্তু বড় ডেটা এলোমেলোভাবে ছোঁয়া প্রোগ্রামে (বড় hash table, graph, database index) এটি অনেক কমে যেতে পারে — অংশ ৫-এ মেপে দেখবেন।

৩ · TLB miss কে সামলায় — hardware না software

Miss হলে page table হাঁটার কাজটি কে করবে, তা নিয়ে ইতিহাসে দুটি স্কুল আছে।

Software-managed TLB-এর সবচেয়ে পরিচিত উদাহরণ MIPS: TLB miss হলে একটি নির্দিষ্ট “TLB refill” exception ঠিকানায় লাফ, সেখানে kernel-এর মাত্র কয়েক ডজন instruction-এর handler, আর TLB-তে লেখার জন্য tlbwr-জাতীয় instruction. পাঠ্যবইয়ের এই গল্পটি সরলীকৃত — পরের প্রজন্মের MIPS-এ hardware-সহায়তাও যোগ হয়েছিল, আর Alpha-র ক্ষেত্রে কাজটি করত firmware-এর একটি স্তর (PALcode). মূল শিক্ষা একটাই: software refill-এ OS যেকোনো ধরনের টেবিল (hashed, inverted, নিজের তৈরি) ব্যবহার করতে পারে, কিন্তু প্রতিটি miss বেশি দামি।

৪ · Effective access time — পরীক্ষার সবচেয়ে পরিচিত হিসাব

পর্ব ৪-এ cache-এর জন্য AMAT আর effective access time দেখেছেন। TLB-র ক্ষেত্রেও একই কাঠামো: hit হলে এক রকম সময়, miss হলে আরেক রকম, আর hit ratio দিয়ে ওজন করা গড়ই effective access time (EAT). ধরুন:

• m = একবার main memory পড়ার সময়
• t = একবার TLB খোঁজার সময়
• h = TLB hit ratio
• L = page table-এর স্তর (সাধারণ paging-এ L = ১)

Hit-এ: TLB খোঁজা + ডেটা পড়া = t + m. Miss-এ: TLB খোঁজা + L বার টেবিল পড়া + ডেটা = t + (L + 1)m. তাই:

সরল করলে এক স্তরে EAT = t + m + (1 − h)m, আর L স্তরে EAT = t + m + (1 − h)·L·m. অর্থাৎ প্রতিটি miss-এর বাড়তি খরচ L·m, আর সেটি ঘটে (1 − h) ভাগ সময়ে।

দুই রীতি — t গোনা হবে কি না

পরীক্ষায় সবচেয়ে বেশি গোলমাল হয় এখানে। বই আর প্রশ্নভেদে দুটি রীতি চলে:

• রীতি ক (t গোনা হয়): উপরের সূত্র। TLB খোঁজার পরেই মেমরিতে যাওয়া, তাই hit আর miss দুই পথেই t যোগ হয়। প্রশ্নে “TLB access time ২০ ns” দেওয়া থাকলে সাধারণত এটিই চাওয়া হয়।
• রীতি খ (t নগণ্য ধরা হয়): কিছু পাঠ্যবই (যেমন Silberschatz-এর পরিচিত বইয়ের নতুন সংস্করণগুলো) ধরে নেয় TLB খোঁজা মেমরি-পড়ার তুলনায় এত দ্রুত বা মেমরি-পড়ার সাথে এমনভাবে মিশে যায় যে আলাদা গোনার দরকার নেই: EAT = h·m + (1 − h)·2m. প্রশ্নে t না থাকলে এটিই।

আরও একটি মিশ্র রূপ কোথাও কোথাও দেখা যায় — hit-এ t + m, কিন্তু miss-এ 2m (TLB আর টেবিল খোঁজা একসাথে শুরু ধরে)। নিরাপদ নিয়ম: উত্তরের শুরুতে লিখে দিন কোন রীতি ধরছেন, তাহলে পরীক্ষক আপনার যুক্তি বুঝবেন।

নিচের calculator দুই রীতিতে এক, দুই, চার আর পাঁচ স্তরের EAT একসাথে ছাপে। পরীক্ষার আগে নিজের বইয়ের সংখ্যা বসিয়ে হাতের উত্তর মিলিয়ে নিতে পারেন — কিন্তু আগে হাতে করুন।

// Effective access time with a TLB. m = one memory access, t = one TLB lookup (ns).
const m = 100, t = 20;
// Convention A (t counted): hit = t + m, miss = t + (L + 1) m   (L = page-table levels)
const eatA = (h, L) => h * (t + m) + (1 - h) * (t + (L + 1) * m);
// Convention B (t ignored, "TLB time negligible"): hit = m, miss = (L + 1) m
const eatB = (h, L) => h * m + (1 - h) * (L + 1) * m;
const f = x => x.toFixed(1).padStart(7);

console.log("     h |   1L A   1L B |   2L A |   4L A   4L B |   5L A");
for (const h of [0.80, 0.90, 0.95, 0.98, 0.99, 0.999]) {
  console.log((h * 100).toFixed(1).padStart(5) + "% |" + f(eatA(h, 1)) + f(eatB(h, 1)) +
    " |" + f(eatA(h, 2)) + " |" + f(eatA(h, 4)) + f(eatB(h, 4)) + " |" + f(eatA(h, 5)));
}
console.log("No TLB: 1-level " + 2 * m + " ns, 4-level " + 5 * m + " ns");
// Reverse question: smallest h so that 1-level EAT (A) <= 130 ns
// t + m + (1 - h) m <= 130  ->  1 - h <= (130 - t - m) / m
const target = 130;
console.log("EAT <= " + target + " ns needs h >= " + (1 - (target - t - m) / m).toFixed(2));
// Slowdown compared with an ideal machine that needs only m per access
console.log("h = 98%, 4-level: " + eatA(0.98, 4).toFixed(1) + " ns = " +
  ((eatA(0.98, 4) / m - 1) * 100).toFixed(0) + "% slower than " + m + " ns");

     h |   1L A   1L B |   2L A |   4L A   4L B |   5L A
 80.0% |  140.0  120.0 |  160.0 |  200.0  180.0 |  220.0
 90.0% |  130.0  110.0 |  140.0 |  160.0  140.0 |  170.0
 95.0% |  125.0  105.0 |  130.0 |  140.0  120.0 |  145.0
 98.0% |  122.0  102.0 |  124.0 |  128.0  108.0 |  130.0
 99.0% |  121.0  101.0 |  122.0 |  124.0  104.0 |  125.0
 99.9% |  120.1  100.1 |  120.2 |  120.4  100.4 |  120.5
No TLB: 1-level 200 ns, 4-level 500 ns
EAT <= 130 ns needs h >= 0.90
h = 98%, 4-level: 128.0 ns = 28% slower than 100 ns

৫ · TLB reach আর huge page

TLB কত বড় মেমরির অনুবাদ একসাথে ধরে রাখতে পারে, তার মাপ TLB reach:

৬ MiB! অথচ আজকের একটি ব্রাউজার, database বা machine-learning প্রোগ্রাম কয়েক GB মেমরি নিয়ে কাজ করে। যদি প্রোগ্রাম সেই বড় অংশ এলোমেলোভাবে ছোঁয়, প্রায় প্রতিটি ছোঁয়াই TLB miss. সমাধান: বড় page. x86-64-এ ৪ KiB-এর পাশাপাশি ২ MiB আর ১ GiB page আছে; ARM64-এও granule অনুযায়ী বড় block আছে। একটি huge page-এর একটি TLB entry ৫১২টি সাধারণ page-এর কাজ করে, আর page walk-এও এক স্তর কম লাগে (অংশ ৭)।

দাম কী? Internal fragmentation — ২ MiB-এর page-এ ১০ KiB দরকার হলেও পুরো ২ MiB আটকে যায়; আর একটানা ২ MiB খালি physical মেমরি খুঁজে পাওয়াও কঠিন হতে পারে (fragmentation, পর্ব ৩১)। Linux-এ দুই পথ: আগে থেকে সংরক্ষিত hugetlbfs page (প্রোগ্রামকে বিশেষভাবে চাইতে হয়), আর transparent huge page (THP), যেখানে kernel নিজেই সুযোগ পেলে সাধারণ মেমরিকে ২ MiB-এ বসায়। Windows-এ এর নাম “large pages” (বিশেষ অনুমতি লাগে), আর Apple silicon-এ macOS-এর সাধারণ page-ই ১৬ KiB — যা reach চার গুণ বাড়ায়। বিস্তারিত পর্ব ৩৮-এ।

নিজের হাতে মাপা — একই ডেটা, দুই ক্রমে

নিচের প্রোগ্রাম ৬৪ MiB মেমরি নেয় (১৬৩৮৪টি ৪ KiB page), আর দুবারই প্রতিটি ৬৪-byte cache line ঠিক একবার পড়ে — মোট পড়া সমান। পার্থক্য শুধু ক্রমে: stride 64-এ একটি page-এর ৬৪টি line শেষ করে পরের page-এ যায়; stride 4096-এ প্রতিটি পড়াই নতুন page-এ — ১৬৩৮৪টি page ঘুরে তারপর পরের offset. madvise(MADV_NOHUGEPAGE) দিয়ে kernel-কে বলা হয়েছে huge page না দিতে, আর memset দিয়ে সব page আগেই ছুঁয়ে নেওয়া হয়েছে, যাতে সময়ের মধ্যে page fault না ঢোকে।

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <sys/mman.h>
#define SIZE (64UL << 20)   /* 64 MiB = 16384 pages of 4 KiB */
#define PAGE 4096UL
#define LINE 64UL
static unsigned long sink;
static double now_ns(void) {
    struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1e9 + ts.tv_nsec; }
/* Both orders read every 64-byte line exactly once; only the ORDER differs. */
static double run(const volatile unsigned char *b, unsigned long stride) {
    unsigned long s = 0; double t0 = now_ns();
    if (stride == LINE)                              /* 64 reads per page, then next page */
        for (unsigned long i = 0; i < SIZE; i += LINE) s += b[i];
    else                                             /* every read lands on a new page */
        for (unsigned long off = 0; off < PAGE; off += LINE)
            for (unsigned long p = 0; p < SIZE; p += PAGE) s += b[p + off];
    sink += s;
    return (now_ns() - t0) / (SIZE / LINE);
}
int main(void) {
    unsigned char *b = mmap(NULL, SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (b == MAP_FAILED) { perror("mmap"); return 1; }
    madvise(b, SIZE, MADV_NOHUGEPAGE);              /* ask for plain 4 KiB pages */
    memset(b, 1, SIZE);                             /* take all page faults BEFORE timing */
    for (int r = 1; r <= 3; r++) {
        double a = run(b, LINE), c = run(b, PAGE);
        printf("run %d: stride 64 = %.2f ns/read, stride 4096 = %.2f ns/read (%.1fx)\n", r, a, c, c / a);
    }
    printf("reads per run %lu, checksum %lu\n", SIZE / LINE, sink);
    return munmap(b, SIZE);
}

run 1: stride 64 = 6.14 ns/read, stride 4096 = 20.69 ns/read (3.4x)
run 2: stride 64 = 4.63 ns/read, stride 4096 = 21.20 ns/read (4.6x)
run 3: stride 64 = 5.30 ns/read, stride 4096 = 20.59 ns/read (3.9x)
reads per run 1048576, checksum 6291456

আপনার Linux-এ page size আর huge page-এর অবস্থা দেখতে root লাগে না:

# Page size and huge-page settings of this Linux machine (read-only, no root needed)
echo "base page size: $(getconf PAGESIZE) bytes"
grep -i huge /proc/meminfo
echo "THP mode: $(cat /sys/kernel/mm/transparent_hugepage/enabled 2>/dev/null || echo 'not available')"
# This shell's own memory: how much of it sits in transparent huge pages?
grep -E '^(Rss|AnonHugePages):' /proc/self/smaps_rollup 2>/dev/null || echo "smaps_rollup not available"

base page size: 4096 bytes
AnonHugePages:         0 kB
ShmemHugePages:        0 kB
FileHugePages:         0 kB
HugePages_Total:       0
HugePages_Free:        0
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       2048 kB
Hugetlb:               0 kB
THP mode: always [madvise] never
Rss:                1844 kB
AnonHugePages:         0 kB

৬ · Page table কত বড় — ৩২ আর ৬৪ bit-এর হিসাব

এবার অন্য সমস্যা। TLB গতির সমস্যা মেটায়, কিন্তু page table নিজে কত মেমরি খায়? সাধারণ (সমতল, এক স্তরের) টেবিলে প্রতিটি সম্ভাব্য virtual page-এর জন্য একটি entry রাখতে হয় — প্রসেস সেটি ব্যবহার করুক বা না করুক, কারণ page number দিয়ে সরাসরি index করতে হবে।

৩২-bit-এ ৪ MiB হয়তো সহ্য করা যায় — কিন্তু ১০০টি প্রসেস মানে ৪০০ MiB শুধু টেবিলে, আর তাও একটানা physical মেমরিতে। ৬৪-bit-এ সমতল টেবিল অসম্ভব: পৃথিবীর কোনো কম্পিউটারে একটি প্রসেসের জন্য ৫১২ GiB RAM শুধু টেবিলের জন্য নেই।

অথচ বাস্তব প্রসেস তার address space-এর খুব সামান্য অংশ ব্যবহার করে: নিচে code আর data, তার ওপরে heap, অনেক ওপরে stack, মাঝে কিছু shared library — মাঝখানে বিশাল ফাঁকা জায়গা। একে বলে sparse address space. সমতল টেবিলের প্রায় সব entry তাই “invalid” — অপচয়। পরের তিনটি অংশের তিনটি কৌশল এই অপচয় এড়ানোর তিন উপায়।

৭ · Multilevel page table — টেবিলেরও page table

মূল চিন্তা: বড় টেবিলটিকে page-আকারের টুকরোয় ভাগ করুন, আর একটি ছোট “ওপরের” টেবিলে লিখে রাখুন কোন টুকরো কোথায় আছে। যে টুকরোর সব entry invalid, সেটি বানানোই হয় না — ওপরের টেবিলে তার entry-তে শুধু “নেই” লেখা থাকে। এটিই hierarchical বা multilevel page table.

৩২-bit-এর two-level: ১০/১০/১২

৪ KiB page আর ৪ byte PTE হলে একটি page-এ ৪০৯৬ ÷ ৪ = ১০২৪টি entry ধরে — ঠিক ১০ bit. তাই ২০ bit-এর page number দুই ভাগে: ওপরের ১০ bit (p₁) দিয়ে outer page table-এ index, পরের ১০ bit (p₂) দিয়ে ভেতরের টেবিলে index, আর শেষ ১২ bit offset. Classic ৩২-bit x86-এ ঠিক এই গঠন — ওপরেরটির নাম page directory.

 31          22 21          12 11              0
┌──────────────┬──────────────┬─────────────────┐
│ p1 (10 bit)  │ p2 (10 bit)  │ offset (12 bit) │
└──────────────┴──────────────┴─────────────────┘
  outer index    inner index    byte in page

আকারের হিসাব: outer table = ১০২৪ × ৪ byte = ৪ KiB, প্রতিটি inner table-ও ৪ KiB, আর একটি inner table ১০২৪ × ৪ KiB = ৪ MiB virtual মেমরি ঢাকে। ধরুন একটি ছোট প্রসেসের code 0x00400000-এ, heap 0x00800000-এ, আর stack ৩ GiB-এর ঠিক নিচে (0xBFFF0000–0xBFFFFFFF). এই তিন অংশ পড়ে outer index ১, ২ আর ৭৬৭-এ। দরকার মাত্র ১টি outer + ৩টি inner = ৪টি page = ১৬ KiB, সমতল টেবিলের ৪ MiB-এর বদলে। পুরো ৪ GiB ব্যবহার করলে অবশ্য ১ + ১০২৪টি page = ৪ MiB + ৪ KiB — সমতলের চেয়ে সামান্য বেশি। Multilevel-এর লাভ পুরোটাই sparse-তার ওপর।

এবার একটি ঠিকানা হাতে হাতে অনুবাদ করুন: 0x00403A7C. ধরুন outer table আছে frame 0x010-এ, তার entry ১ বলছে inner table frame 0x2B-তে, আর সেই inner table-এর entry ৩ বলছে frame 0x1F5. TLB শুরুতে খালি।

1 VA 0x00403A7C -> p1 = 1, p2 = 3, d = 0xA7C2 TLB lookup VPN 0x00403 -> MISS3 read outer[1] at PTBR (frame 0x010) -> 0x2B4 read inner[3] in frame 0x2B -> frame 0x1F55 PA = 0x1F5 << 12 | 0xA7C = 0x001F5A7C6 next: VA 0x00403A80 -> TLB HIT

এবার এই একই টেবিল একটি ছোট simulator-এ — ৪-entry LRU TLB, ১৬টি ঠিকানা, আর প্রতিটির জন্য কত মেমরি-পড়া লাগল তার হিসাব। টেবিলে outer index ১ (code), ২ (heap) আর ৭৬৭ (stack) ছাড়া কিছু নেই — sparse.

// Two-level page table (10/10/12) + a 4-entry LRU TLB. Frame numbers in hex.
const outer = { 1: 0x2B, 2: 0x2C, 767: 0x2D };          // outer index -> frame of inner table
const inner = { 0x2B: { 0: 0x1A0, 1: 0x1A1, 3: 0x1F5 }, // inner index -> data frame
                0x2C: { 0: 0x0C3, 1: 0x0C4 }, 0x2D: { 1023: 0x07E } };
const tlb = new Map();                                   // vpn -> frame, oldest first
const hex = (x, w) => x.toString(16).toUpperCase().padStart(w, "0");
let hits = 0, misses = 0, faults = 0, memReads = 0;
const trace = [0x00400010, 0x00403A7C, 0x00400020, 0xBFFFFFF0, 0x00800100,
  0x00400030, 0x00801008, 0x00403A80, 0xBFFFFFE8, 0x00400040, 0x00801010,
  0x00403A84, 0x00C00000, 0xBFFFFFE0, 0x00400050, 0x00800200];
for (const va of trace) {
  const p1 = va >>> 22, p2 = (va >>> 12) & 0x3FF, off = va & 0xFFF, vpn = va >>> 12;
  let frame, how;
  if (tlb.has(vpn)) {                                    // TLB hit: no table reads
    frame = tlb.get(vpn); tlb.delete(vpn); tlb.set(vpn, frame); hits++; how = "hit ";
  } else {
    misses++; memReads++;                                // read the outer entry
    const t2 = outer[p1];
    if (t2 !== undefined) { memReads++; frame = inner[t2][p2]; } // read the inner entry
    if (frame === undefined) { faults++; console.log(hex(va, 8) + " " + p1 + "/" + p2 + " miss -> PAGE FAULT"); continue; }
    if (tlb.size === 4) tlb.delete(tlb.keys().next().value); // evict least recently used
    tlb.set(vpn, frame); how = "miss";
  }
  memReads++;                                            // the data access itself
  console.log(hex(va, 8) + " " + p1 + "/" + p2 + "/" + hex(off, 3) + " " + how + " -> PA " + hex(frame * 4096 + off, 8));
}
const n = trace.length;
console.log("accesses " + n + ", TLB hits " + hits + ", misses " + misses + " (faults " + faults + ")");
console.log("hit ratio " + (100 * hits / n).toFixed(1) + "%, memory reads " + memReads +
  " (" + (memReads / n).toFixed(2) + " per access; without a TLB " + (3 * (n - faults) + faults) + ")");

00400010 1/0/010 miss -> PA 001A0010
00403A7C 1/3/A7C miss -> PA 001F5A7C
00400020 1/0/020 hit  -> PA 001A0020
BFFFFFF0 767/1023/FF0 miss -> PA 0007EFF0
00800100 2/0/100 miss -> PA 000C3100
00400030 1/0/030 hit  -> PA 001A0030
00801008 2/1/008 miss -> PA 000C4008
00403A80 1/3/A80 miss -> PA 001F5A80
BFFFFFE8 767/1023/FE8 miss -> PA 0007EFE8
00400040 1/0/040 hit  -> PA 001A0040
00801010 2/1/010 hit  -> PA 000C4010
00403A84 1/3/A84 hit  -> PA 001F5A84
00C00000 3/0 miss -> PAGE FAULT
BFFFFFE0 767/1023/FE0 hit  -> PA 0007EFE0
00400050 1/0/050 hit  -> PA 001A0050
00800200 2/0/200 miss -> PA 000C3200
accesses 16, TLB hits 7, misses 9 (faults 1)
hit ratio 43.8%, memory reads 32 (2.00 per access; without a TLB 46)

x86-64: চার স্তর, ৯/৯/৯/৯/১২

৬৪-bit-এ PTE ৮ byte, তাই একটি ৪ KiB page-এ ৫১২টি entry = ৯ bit. x86-64 ৬৪ bit-এর মধ্যে ৪৮ bit ব্যবহার করে: ৪ স্তর × ৯ bit + ১২ bit offset = ৪৮. বাকি ওপরের ১৬ bit-কে bit ৪৭-এর কপি হতে হয় (canonical address) — ফলে নিচের ১২৮ TiB user-এর, ওপরের ১২৮ TiB সাধারণত kernel-এর, মাঝে বিশাল নিষিদ্ধ ফাঁক। স্তরগুলোর নাম (Intel-এর পরিভাষায়) ওপর থেকে PML4 → PDPT → PD → PT.

প্রতিটি টেবিল ঠিক ৪ KiB, একটি page-এ আঁটে — এটাই নকশার সৌন্দর্য। একটি ছোট প্রসেস (code 0x400000-এ ১৬ KiB, heap 0x1000000-এ ১৩২ KiB, stack 0x7ffffffde000-এ ১৩২ KiB) গুনে দেখা যায়: ১টি PML4, ২টি PDPT (code-heap একটিতে, stack আরেকটিতে), ২টি PD, ৩টি PT = ৮টি page = ৩২ KiB. ৫১২ GiB-এর তুলনায় প্রায় শূন্য।

1 48-bit VA -> 254 / 232 / 145 / 325 / 0x6782 CR3 -> PML4[254] -> PDPT frame 0x2A3F13 PDPT[232] -> PD frame 0x0B7714 PD[145] -> PT frame 0x13C02 (PS = 0)5 PT[325] -> data frame 0x4D2E96 PA = 0x4D2E9 << 12 | 0x678 = 0x4D2E9678

পাঁচ স্তর (LA57) আর ARM64

৪৮ bit = ২৫৬ TiB virtual মেমরি। কয়েক TB RAM-ওয়ালা বড় server আর বিশাল memory-mapped ডেটার যুগে এটিও ছোট হয়ে আসছিল। তাই Intel একটি পঞ্চম স্তর (PML5) যোগ করে — five-level paging, CPU-র বৈশিষ্ট্যের নাম LA57: ৫ × ৯ + ১২ = ৫৭ bit, অর্থাৎ ১২৮ PiB. Linux-এ এর সমর্থন ২০১৭ সালের দিকে (4.14 সংস্করণের আশেপাশে) এসেছে, আর এটি শুধু সেসব CPU-তে চালু হয় যেগুলো LA57 দেয় — মূলত নতুন প্রজন্মের কিছু server প্রসেসর। দাম: TLB miss-এ এক স্তর বেশি হাঁটা। তাই Linux-এ সাধারণ প্রোগ্রাম ডিফল্টভাবে ৪৭-bit-এর নিচের ঠিকানাই পায়; বড় ঠিকানা চাইলে প্রোগ্রামকে স্পষ্টভাবে mmap-এ উঁচু ঠিকানার ইঙ্গিত দিতে হয়।

ARM64 (AArch64)-এ ৪ KiB granule-এর সাধারণ কনফিগারেশন প্রায় একই রকম: ৪৮-bit virtual address, চার স্তর (ARM-এর নামে level 0–3), প্রতিটিতে ৯ bit. পার্থক্য: ARM-এ user আর kernel-এর জন্য আলাদা দুটি টেবিল-register (TTBR0 আর TTBR1), আর ১৬ KiB ও ৬৪ KiB granule-ও আছে — বড় granule-এ স্তর কম লাগে আর TLB reach বেশি। Apple silicon-এ macOS আর iOS ১৬ KiB page ব্যবহার করে।

৮ · Hashed page table — যত page ব্যবহার, তত entry

৬৪-bit-এ চার-পাঁচ স্তর হাঁটা দামি। বিকল্প চিন্তা: page number-কে একটি hash table-এ রাখা, যেখানে entry থাকে শুধু ব্যবহৃত page-এর জন্য। প্রতিটি bucket-এ একটি linked list (chaining), আর প্রতিটি element-এ তিনটি জিনিস: virtual page number, frame number, আর পরের element-এর pointer. Hash table-এর মৌলিক ধারণা DSA কোর্সের hash table পর্বে আছে।

translate(vpn, offset):
    bucket = hash(vpn) mod TABLE_SIZE
    for e in chain[bucket]:          // usually 1 or 2 elements
        if e.vpn == vpn:
            return e.frame * PAGE_SIZE + offset
    page_fault(vpn)                   // not in the table: not mapped / not in memory

সুবিধা: টেবিলের আকার address space-এর আকারের ওপর নির্ভর করে না — ৪৮ bit হোক বা ৬৪ bit, ব্যবহৃত page-এর সংখ্যার সমানুপাতিক। ভালো hash function আর যথেষ্ট বড় table হলে গড়ে এক-দুটি তুলনাতেই পাওয়া যায়। অসুবিধা: chain লম্বা হলে খোঁজা ধীর; প্রতিটি element-এ vpn আর pointer রাখতে হয় বলে entry বড়; আর পাশাপাশি page-এর entry মেমরিতে ছড়িয়ে থাকে, cache-বান্ধব নয়।

Clustered page table এই শেষ সমস্যার উত্তর: প্রতিটি hash element একটির বদলে পরপর কয়েকটি page-এর (যেমন ১৬টি) অনুবাদ রাখে। প্রোগ্রাম সাধারণত পাশাপাশি page একসাথে ব্যবহার করে, তাই একটি খোঁজায় অনেকটা ঢাকা যায়, আর vpn-tag ও pointer-এর খরচ ১৬ ভাগে ভাগ হয়। ১৯৯০-এর দশকের মাঝামাঝি ৬৪-bit address space-এর জন্য এটি গবেষণায় প্রস্তাবিত হয়েছিল। এটি বিশেষত sparse অথচ গুচ্ছবদ্ধ (clustered) ব্যবহারে ভালো।

৯ · Inverted page table — প্রতিটি frame-এ একটি entry

এখন পর্যন্ত সব টেবিল ছিল প্রতি প্রসেসে একটি, আর virtual page দিয়ে সাজানো। Inverted page table উল্টো দিক থেকে ভাবে: পুরো সিস্টেমে একটিই টেবিল, physical মেমরির প্রতিটি frame-এর জন্য একটি entry. Entry i বলে “frame i-তে এখন কোন প্রসেসের কোন page আছে”: <pid, vpn>. টেবিলের আকার তাই RAM-এর আকারের সমানুপাতিক — প্রসেস যতই হোক, address space যত বড়ই হোক। ৮ GiB RAM আর ৪ KiB frame-এ ২০,৯৭,১৫২টি entry; প্রতিটি ৮ byte হলে মোট ১৬ MiB, পুরো সিস্টেমের জন্য।

সমস্যা: অনুবাদ করতে হয় <pid, vpn> থেকে frame-এ, অথচ টেবিল সাজানো frame দিয়ে। সরলভাবে পুরো টেবিল খুঁজতে হতো — ২০ লাখ entry, প্রতিটি মেমরি-ছোঁয়ায়! তাই বাস্তবে সঙ্গে থাকে একটি hash: <pid, vpn>-কে hash করে একটি ছোট hash anchor table-এ যাওয়া, যা বলে কোন frame-এর entry থেকে খোঁজা শুরু করতে হবে; তারপর একই hash-এর entry-গুলো একটি chain-এ জোড়া। আর অবশ্যই TLB প্রথমে দেখা হয়; inverted table-এ যাওয়া কেবল TLB miss-এ।

1 pid 2, VA 0x5ABC -> vpn 5, offset 0xABC2 h = (pid + vpn) mod 8 = 7 -> HAT[7] = frame 33 IPT[3] = <3, 4> no match -> next = 24 IPT[2] = <1, 6> no match -> next = 15 IPT[1] = <2, 5> MATCH -> frame = index 16 pid 2, vpn 9: h = 3 -> IPT[0] <1,0x12>, end -> FAULT

Sharing-এর দাম। দুটি প্রসেস একটি library বা shared memory একই frame-এ ভাগ করতে চাইলে সাধারণ টেবিলে কোনো সমস্যা নেই — দুজনের টেবিলে একই frame number. কিন্তু inverted table-এ প্রতিটি frame-এর একটিই entry, তাতে একটিই <pid, vpn> ধরে। সমাধানগুলো জোড়াতালির: এক সময়ে শুধু একজনের mapping রেখে অন্যজন ছুঁলে fault নিয়ে বদলে দেওয়া, entry-তে একাধিক mapping-এর chain রাখা, বা pid-এর বদলে একটি যৌথ “segment” পরিচয় ব্যবহার করা (IBM-এর নকশাগুলোতে এমন কিছু দেখা যায়)। ফলে shared memory ভারী কাজে inverted table অসুবিধাজনক।

বাস্তবে কোথায়? IBM-এর RT PC আর পরের POWER/PowerPC পরিবার hashed/inverted ধাঁচের টেবিলের জন্য পরিচিত (PowerPC-র “hashed page table”); Intel-এর IA-64 (Itanium)-এ OS-এর পছন্দে একটি hash-ভিত্তিক টেবিল (VHPT) ছিল, আর HP-র PA-RISC-ও inverted ধাঁচ ব্যবহার করত। বিস্তারিত প্রজন্মভেদে আলাদা, তাই এগুলোকে “ধাঁচ” হিসেবেই মনে রাখুন। আজকের x86-64 আর ARM64 দুটোই multilevel (radix) টেবিল ব্যবহার করে।

তুলনা — কোনটি কখন

১০ · AI-এর যুগে TLB আর page table

এই বিষয়ের numerical আর “আমার প্রোগ্রাম ধীর কেন” — দুই ধরনের প্রশ্নই মানুষ AI-কে করে। কয়েকটি ভুল বারবার দেখা যায়:

AI-এর উত্তর মানার আগে — চেকলিস্ট

• কোন EAT রীতি (t গোনা কি না) ব্যবহার হয়েছে দেখেছি, আর hit ও miss দুই পথে একই রীতি মানা হয়েছে কি না মিলিয়েছি
• Miss-এ (L + 1) বার মেমরি পড়া ধরা হয়েছে কি না, নিজে stepper-এর মতো গুনে দেখেছি
• Page table-এর আকারের হিসাবে bit-সংখ্যা, page size আর PTE-র আকার আলাদা করে লিখে ২-এর ঘাতে মিলিয়েছি
• CPU বা OS-এর দাবি (কত স্তর, hardware না software walker, কোন page size) নির্দিষ্ট architecture আর OS-এর জন্য কি না দেখেছি — Linux, Windows আর macOS আলাদা
• sudo বা /sys-এ লেখার কোনো কমান্ড চালানোর আগে man page আর kernel ডকুমেন্টেশন পড়েছি, আগে-পরে মেপে দেখেছি
• Benchmark-এর সংখ্যা একবারের রানে বিশ্বাস করিনি — কয়েকবার, লোডসহ চালিয়ে, অন্য কারণ (cache, prefetcher) বাদ দিতে পেরেছি কি না ভেবেছি