Paging — page, frame আর page table

১ · কেন paging — টুকরো জায়গার সমস্যার সমাধান

পর্ব ৩১-এ দেখেছেন, প্রতিটি প্রসেসকে যদি RAM-এর একটানা একটি অংশ দিতে হয় (contiguous allocation), তাহলে সময়ের সাথে মেমরিতে ছোট ছোট ফাঁকা জায়গা ছড়িয়ে পড়ে। মোট খালি জায়গা যথেষ্ট, কিন্তু কোনো একটি ফাঁকা অংশই নতুন প্রসেসের জন্য যথেষ্ট বড় নয় — এটিই external fragmentation. Compaction করে সব প্রসেস সরিয়ে ফাঁকা জায়গা জোড়া দেওয়া যায়, কিন্তু তা অনেক সময় নেয়, আর চলমান প্রসেসের ঠিকানা বদলানোর ঝামেলাও আছে।

Paging সমস্যাটিকে একেবারে গোড়া থেকে বদলে দেয়। প্রশ্নটি আর “এতটা একটানা জায়গা কোথায় পাব?” থাকে না। নিয়ম হয়: প্রসেসের ঠিকানা-জগৎকে (logical address-এর জগৎ) সমান মাপের টুকরোয় ভাগ করুন — প্রতিটি টুকরো একটি page. Physical RAM-কেও ঠিক একই মাপের ঘরে ভাগ করুন — প্রতিটি ঘর একটি frame. এবার যেকোনো page যেকোনো খালি frame-এ বসতে পারে; পাশাপাশি থাকার দরকার নেই। কোন page কোন frame-এ আছে, তার হিসাব রাখে প্রসেসের নিজস্ব একটি টেবিল — page table.

যেহেতু সব frame সমান মাপের, যেকোনো খালি frame যেকোনো page-এর জন্য সমান ভালো। “কোন ফাঁকে বসাব” — first fit, best fit-এর সেই প্রশ্নই আর ওঠে না; খালি frame-এর একটি তালিকা থাকলেই চলে। তবে paging বিনামূল্যে নয়। তিনটি দাম দিতে হয়, আর এই পর্বের বাকিটা সেই তিন দামেরই হিসাব: (১) প্রতিটি প্রসেসের জন্য একটি page table রাখার মেমরি, (২) প্রতিটি মেমরি-ব্যবহারে অনুবাদের সময়, আর (৩) শেষ page-এর ভেতরে অব্যবহৃত জায়গা — internal fragmentation.

২ · ঠিকানার দুই ভাগ — page number আর offset

Paging-এর পুরো হিসাব একটি সরল পর্যবেক্ষণের ওপর দাঁড়িয়ে: page size সবসময় ২-এর ঘাত (৫১২, ১০২৪, ৪০৯৬…)। ধরুন logical address-এর মোট বিট m, অর্থাৎ logical ঠিকানা-জগতের আকার ২^m বাইট। আর page size ২ⁿ বাইট। তাহলে প্রতিটি logical address দুই ভাগে ভাঙে:

কেন এমন? কারণ ২ⁿ দিয়ে ভাগ করা বাইনারিতে শুধু n ঘর ডানে সরানো। p = ঠিকানা ÷ ২ⁿ-এর ভাগফল, d = ভাগশেষ — আর ২-এর ঘাত হলে ভাগফল ঠিক উপরের বিটগুলো, ভাগশেষ ঠিক নিচের n বিট। Hardware-কে কোনো ভাগ করতে হয় না; তারগুলো দুই দলে ভাগ করে দিলেই হলো। মোট page-এর সংখ্যা ২^m−n, আর প্রতিটি page-এ ২ⁿটি বাইট।

৪ KiB page-এ offset ১২ বিট, আর ১২ বিট মানে ঠিক ৩টি hex অঙ্ক (প্রতিটি hex অঙ্ক ৪ বিট)। তাই 0x1ABC-এর মতো ঠিকানায় শেষ তিন অঙ্ক ABC হলো d, আর বাকি 1 হলো p — চোখে দেখেই ভাগ করা যায়। কিন্তু page size ১ KiB হলে offset ১০ বিট, যা hex অঙ্কের সীমায় পড়ে না; তখন বাইনারিতে লিখে ভাগ করতে হয়। নিচের stepper-এ ঠিক সেটাই দেখুন।

1 m = 16, page = 1024 = 2^10, n = 102 0x3A7F = 0011 1010 0111 11113 p = top 6 bits, d = low 10 bits4 p = 001110, d = 10 0111 11115 check: 14 x 1024 + 639 = 14975

৩ · Page table দিয়ে অনুবাদ — পাঠ্যবইয়ের ৩২ বাইটের উদাহরণ

অনুবাদের নিয়ম এক লাইনের। p দিয়ে page table-এর p নম্বর ঘর দেখুন; সেখানে লেখা আছে frame number f. Physical address-এ offset বদলায় না — একটি page পুরোটাই একটি frame-এ বসে, তাই page-এর ভেতরের ৬৩৯ নম্বর বাইট frame-এর ভেতরেও ৬৩৯ নম্বর বাইট।

অপারেটিং সিস্টেমের প্রায় প্রতিটি পাঠ্যবইয়ে (যেমন Silberschatz, Galvin ও Gagne-এর Operating System Concepts) একটি ছোট উদাহরণ আছে, যা পরীক্ষায়ও প্রায়ই আসে। Physical মেমরি মাত্র ৩২ বাইট, page size ৪ বাইট — তাই ৩২ ÷ ৪ = ৮টি frame (০–৭)। একটি প্রসেসের logical মেমরি ১৬ বাইট (m = ৪), যেখানে a থেকে p পর্যন্ত ১৬টি অক্ষর রাখা — অর্থাৎ ৪টি page (০–৩), n = ২. Page table: page ০ → frame ৫, page ১ → frame ৬, page ২ → frame ১, page ৩ → frame ২.

এবার কয়েকটি ঠিকানা অনুবাদ করি (হিসাব নিচের simulator-এ আবার যাচাই হবে):

• Logical ০ (অক্ষর a): p = ০ ÷ ৪ = ০, d = ০. Page ০ → frame ৫, তাই physical = ৫ × ৪ + ০ = ২০.
• Logical ৩ (d): p = ০, d = ৩ → ৫ × ৪ + ৩ = ২৩.
• Logical ৪ (e): p = ১, d = ০ → ৬ × ৪ + ০ = ২৪.
• Logical ১৩ (n): p = ৩, d = ১ → ২ × ৪ + ১ = ৯. খেয়াল করুন, logical ঠিকানা বড়, physical ঠিকানা ছোট — ক্রম রাখার কোনো বাধ্যবাধকতা নেই।

বাইনারিতে দেখলে কাজটি আরও যান্ত্রিক। Logical ১৩ = 11 01 (৪ বিট: উপরের ২ বিট p = ৩, নিচের ২ বিট d = ১)। Frame ২ = 010 (physical ঠিকানা ৫ বিটের, কারণ ৩২ = ২^৫; তাই frame number ৩ বিট)। এখন frame-এর বিটের পাশে d জুড়ে দিন: 010 01 = ৯. এই “জুড়ে দেওয়া”-ই hardware করে — গুণ বা যোগের সার্কিট লাগে না।

৪ · Hex ঠিকানার অনুবাদ — পরীক্ষার ধাঁচে পূর্ণ সমাধান

বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় সবচেয়ে সাধারণ প্রশ্নটি এমন: “Page size ৪ KiB. একটি প্রসেসের page table দেওয়া আছে। নিচের logical address-গুলোর physical address বের করুন; কোনোটি অবৈধ হলে বলুন।” ধরুন টেবিলটি এই (৫টি entry, অর্থাৎ table length ৫):

৪ KiB = ২^১২, তাই d = শেষ ৩টি hex অঙ্ক, আর f × ৪০৯৬ মানে hex-এ f-এর পরে তিনটি শূন্য বসানো। ফলে hex-এ উত্তর হয় শুধু “f-এর hex, তারপর d-এর তিন অঙ্ক”:

দশমিক ঠিকানা দিলে (শেষ সারি) ভাগ করুন: ৪১০০ ÷ ৪০৯৬ = ১, ভাগশেষ ৪. দুটি অবৈধ ঠিকানার পার্থক্যও খেয়াল করুন: 0x2FFF-এর page টেবিলে আছে কিন্তু invalid চিহ্নিত, আর 0x5000-এর page নম্বর টেবিলের দৈর্ঘ্যই ছাড়িয়ে গেছে। দুই ক্ষেত্রেই MMU নিজে কিছু ঠিক করে না — CPU একটি exception তোলে, নিয়ন্ত্রণ যায় kernel-এর handler-এ, আর OS ঠিক করে কী হবে। ঠিকানাটি সত্যিই অবৈধ হলে Linux প্রসেসকে SIGSEGV পাঠায় — পরিচিত “Segmentation fault”. (Page বৈধ কিন্তু এখন ডিস্কে আছে — এমন page fault-এর গল্প পর্ব ৩৫-এ।)

নিচের stepper-এ MMU-র ভেতরে একেকটি ঠিকানা কীভাবে চলে, আর প্রতিটিতে কতবার মেমরিতে যেতে হয়, তা দেখুন:

- PTBR -> table, PTLR = 50 [0] frame 0x5   valid1 [1] frame 0x9   valid2 [2] ---         invalid3 [3] frame 0x1A  valid4 [4] frame 0x2   valid

নিজের বইয়ের অনুশীলনী যাচাই করতে নিচের translator-এ page size, page table আর ঠিকানার তালিকা বদলে নিন। ঠিকানা দশমিক সংখ্যা বা "0x…" আকারের hex লেখা — দুটোই চলে; টেবিলে null মানে invalid. প্রথম কলটি উপরের ৩২ বাইটের উদাহরণ, দ্বিতীয়টি এই অংশের hex প্রশ্ন।

// Paging address translator: logical address -> (p, d) -> frame -> physical
function translate(PAGE, table, addrs) {
  const n = Math.log2(PAGE);                          // offset bits
  const hex = x => "0x" + x.toString(16).toUpperCase();
  console.log("page size " + PAGE + " = 2^" + n + ", table length " + table.length);
  for (const a of addrs) {
    const la = typeof a === "number" ? a : parseInt(a, 16);
    const p = Math.floor(la / PAGE), d = la % PAGE;   // = la >> n, la & (PAGE - 1)
    let out = String(a).padEnd(7) + "-> p=" + p + " d=" + d + " (" + hex(d) + ")";
    if (p >= table.length) out += "  p >= length -> trap";
    else if (table[p] === null) out += "  invalid -> trap";
    else {
      const pa = table[p] * PAGE + d;
      out += "  frame " + table[p] + " -> " + pa + " (" + hex(pa) + ")";
    }
    console.log(out);
  }
}
// textbook: 32-byte memory, 4-byte pages, page table 0->5, 1->6, 2->1, 3->2
translate(4, [5, 6, 1, 2], [0, 3, 4, 13, 15]);
// exam style: 4 KiB pages, page 2 invalid, 5 entries (PTLR = 5)
translate(4096, [5, 9, null, 0x1A, 2],
          ["0x1ABC", "0x3004", "0x0123", "0x2FFF", "0x5000", 4100]);

page size 4 = 2^2, table length 4
0      -> p=0 d=0 (0x0)  frame 5 -> 20 (0x14)
3      -> p=0 d=3 (0x3)  frame 5 -> 23 (0x17)
4      -> p=1 d=0 (0x0)  frame 6 -> 24 (0x18)
13     -> p=3 d=1 (0x1)  frame 2 -> 9 (0x9)
15     -> p=3 d=3 (0x3)  frame 2 -> 11 (0xB)
page size 4096 = 2^12, table length 5
0x1ABC -> p=1 d=2748 (0xABC)  frame 9 -> 39612 (0x9ABC)
0x3004 -> p=3 d=4 (0x4)  frame 26 -> 106500 (0x1A004)
0x0123 -> p=0 d=291 (0x123)  frame 5 -> 20771 (0x5123)
0x2FFF -> p=2 d=4095 (0xFFF)  invalid -> trap
0x5000 -> p=5 d=0 (0x0)  p >= length -> trap
4100   -> p=1 d=4 (0x4)  frame 9 -> 36868 (0x9004)

৫ · Page table কত বড়, কোথায় থাকে, আর কত সময় নেয়

পূর্ণ সমাধান: ৩২-বিট ঠিকানা, ৪ KiB page

প্রশ্ন: “Logical address ৩২ বিট, page size ৪ KiB, প্রতিটি page table entry ৪ বাইট। (ক) কতগুলো page? (খ) Page table-এ কতগুলো entry? (গ) একটি প্রসেসের page table কত বড়?”

1. Page size ৪ KiB = ২^১২ বাইট → offset n = ১২ বিট।
2. Page number = ৩২ − ১২ = ২০ বিট → মোট page = ২^২০ = ১০,৪৮,৫৭৬ (প্রায় ১০ লাখ)।
3. একতলা (single-level) টেবিলে প্রতিটি সম্ভাব্য page-এর জন্য একটি entry, তাই entry = ২^২০টি।
4. আকার = ২^২০ × ৪ বাইট = ২^২২ বাইট = ৪ MiB, প্রতিটি প্রসেসের জন্য।

৪ MiB ছোট শোনায়, কিন্তু তিনটি সমস্যা আছে। প্রথমত, টেবিলটি নিজেই একটানা ৪ MiB জায়গা চায় — যে সমস্যা দূর করতে paging এসেছিল, সেটিই টেবিলের জন্য ফিরে এলো। দ্বিতীয়ত, ১০০০টি প্রসেস চললে শুধু টেবিলেই প্রায় ৪০০০ MiB. তৃতীয়ত, বেশিরভাগ প্রসেস তার ৪ GiB ঠিকানা-জগতের সামান্য অংশই ব্যবহার করে, তাই টেবিলের বেশিরভাগ entry invalid — খালি ঘরের জন্য মেমরি খরচ। ৬৪-বিট সিস্টেমে ছবিটি আরও ভয়ংকর: ৪৮-বিট virtual ঠিকানা আর ৪ KiB page-এ ২^৩৬টি entry, প্রতিটি ৮ বাইট হলে একতলা টেবিল হতো ৫১২ GiB. এই কারণেই বাস্তব সিস্টেম multilevel page table ব্যবহার করে, যেখানে অব্যবহৃত অংশের টেবিল তৈরিই হয় না — বিস্তারিত পর্ব ৩৩-এ। এখানে শুধু মূল চিন্তাটি মনে রাখুন: টেবিলকেও page-এ ভাগ করা, আর ঠিকানা-জগতের খালি অংশের জন্য কোনো টেবিল না রাখা।

PTBR আর context switch

প্রতিটি প্রসেসের নিজস্ব page table, তাই একই logical ঠিকানা 0x1000 দুই প্রসেসে দুই আলাদা frame-এ যায় — এভাবেই একটি প্রসেস আরেকটির মেমরি দেখতে পায় না। চলতি প্রসেসের টেবিল কোথায়, তা MMU জানে PTBR থেকে। x86-এ এই register-এর নাম CR3; ARM64-এ TTBR0_EL1 (user অংশের জন্য) আর TTBR1_EL1 (kernel অংশের জন্য); RISC-V-তে satp. প্রসেসের PCB-তে টেবিলের ঠিকানা লেখা থাকে, আর context switch-এ (পর্ব ৯) kernel নতুন প্রসেসের মানটি এই register-এ বসায়। পুরো টেবিল কপি করতে হয় না — একটি register বদলালেই পুরো ঠিকানা-জগৎ বদলে যায়। PTBR বদলানো একটি privileged নির্দেশ; শুধু kernel mode-এ চলে, নইলে যেকোনো প্রোগ্রাম অন্যের মেমরিতে ঢুকে পড়ত।

দুইবার মেমরি, আর TLB-র প্রবেশ

Stepper-এ দেখেছেন, প্রতিটি লোড বা স্টোরে আগে PTE, তারপর ডেটা — দুইবার মেমরি। মেমরি-access ১০০ ns ধরলে প্রতিটি ব্যবহার ২০০ ns — অর্থাৎ paging একাই প্রোগ্রামকে দ্বিগুণ ধীর করত। কেউ এটি মেনে নিত না। সমাধান হলো CPU-র ভেতরে একটি ছোট, খুব দ্রুত cache, যা সাম্প্রতিক অনুবাদগুলো (p → f) মনে রাখে: TLB. অনুবাদ TLB-তে পাওয়া গেলে (TLB hit) PTE পড়তে মেমরিতে যেতে হয় না। Locality-র কারণে প্রোগ্রাম একই কয়েকটি page বারবার ছোঁয়, তাই hit ratio সাধারণত খুব বেশি।

TLB hit ratio α, মেমরি-access সময় t_m, আর TLB খোঁজার সময় t_TLB হলে effective access time:

শুধু একটি স্বাদ: t_TLB নগণ্য ধরে, t_m = ১০০ ns আর α = ০.৮০ হলে EAT = ০.৮০ × ১০০ + ০.২০ × ২০০ = ১২০ ns (২০% ধীর); α = ০.৯৯ হলে ১০১ ns — প্রায় paging ছাড়া যতটা। TLB-র গঠন, ASID আর এই সূত্রের পূর্ণ numerical সমস্যা পর্ব ৩৩-এ।

OS-এর খাতা: frame table আর খালি frame-এর তালিকা

Page table প্রসেসের দিক থেকে হিসাব (“আমার page কোথায়?”)। OS-এর দরকার উল্টো দিকের হিসাবও (“RAM-এর কোন frame কার, কোনটি খালি?”)। এই কাজে OS রাখে একটি frame table — প্রতিটি physical frame-এর জন্য একটি ঘর: খালি নাকি বরাদ্দ, বরাদ্দ হলে কোন প্রসেসের কোন page. আর দ্রুত বরাদ্দের জন্য একটি free-frame list.

ধরুন একটি নতুন প্রসেসের ৪টি page লাগবে, আর খালি তালিকায় আছে frame ১৪, ১৩, ১৮, ২০, ১৫. OS তালিকা থেকে একে একে নেয়: page ০ → ১৪, page ১ → ১৩, page ২ → ১৮, page ৩ → ২০; প্রতিটি বসানোর সাথে সাথে প্রসেসের page table-এ entry লেখে আর frame table-এ মালিকানা চিহ্নিত করে। তালিকায় থাকে শুধু ১৫. লক্ষ করুন, “কোন ফাঁকে বসাব” নিয়ে কোনো খোঁজাখুঁজি নেই — তালিকার মাথা থেকে নিলেই হয়। n page-এর প্রসেসের জন্য শুধু n টি খালি frame থাকলেই যথেষ্ট, পাশাপাশি হোক বা না হোক।

OS-কে প্রসেসের টেবিলও মনে রাখতে হয়। একটি system call-এ প্রসেস যখন একটি buffer-এর logical ঠিকানা দেয় (যেমন read(fd, buf, n)), kernel-কে জানতে হয় সেই ঠিকানা কোন frame-এ পড়েছে আর আদৌ বৈধ কি না। আর dispatcher প্রতিটি context switch-এ পরের প্রসেসের টেবিল hardware-এ বসায়। তাই পাঠ্যবইয়ের ভাষায় OS প্রতিটি প্রসেসের page table-এর একটি কপি (বাস্তবে তার ঠিকানা, PCB-তে) রাখে — আর এই বাড়তি কাজ context switch-এর সময় কিছুটা বাড়ায়।

৬ · Page table entry-র ভেতরে — বিট ধরে ধরে

একটি page table entry (PTE) শুধু frame number নয়। Frame number-এর পাশে কয়েকটি ছোট বিট থাকে, যা hardware প্রতিটি access-এ পড়ে বা লেখে। পাঠ্যবইয়ের সাধারণ নামগুলো আর x86-64-এর আসল নাম পাশাপাশি:

x86-64-এ আরও কয়েকটি বিট আছে — cache নিয়ন্ত্রণের (PWT, PCD, PAT) আর G (global: context switch-এও TLB থেকে মুছবে না, kernel-এর page-এর জন্য)। ARM64-এ নাম ও বিন্যাস ভিন্ন — যেমন access flag (AF), user আর privileged অংশের জন্য আলাদা execute-never বিট (UXN, PXN), access permission (AP) — কিন্তু ধারণাগুলো একই। Frame number-এর জন্য ১২ বিট ছেড়ে শুরু কেন? কারণ frame-এর শুরুর ঠিকানা সবসময় ৪০৯৬-এর গুণিতক, তাই তার নিচের ১২ বিট সবসময় শূন্য — সেগুলো সংরক্ষণ করার দরকার নেই, ঐ জায়গাতেই flag-বিটগুলো রাখা হয়।

Valid বিট দিয়ে সুরক্ষা — পাঠ্যবইয়ের ১৪-বিট উদাহরণ

একটি সিস্টেমে ঠিকানা ১৪ বিট (০ থেকে ১৬,৩৮৩), page size ২ KiB (২০৪৮), তাই মোট ১৬,৩৮৪ ÷ ২০৪৮ = ৮টি page (০–৭)। একটি প্রোগ্রাম ব্যবহার করে শুধু ঠিকানা ০ থেকে ১০,৪৬৮. ১০,৪৬৮ ÷ ২০৪৮ = ৫ (ভাগশেষসহ), তাই page ০–৫ valid, page ৬ আর ৭ invalid. প্রোগ্রাম ১৪,০০০ ঠিকানায় গেলে (page ৬) trap — ভালো। কিন্তু ১১,০০০ ঠিকানায় গেলে? সেটি page ৫-এর ভেতরে (১০,২৪০–১২,২৮৭), যা valid — তাই hardware বাধা দেবে না, যদিও প্রোগ্রামের আসল সীমা ১০,৪৬৮. সুরক্ষা page-এর মাপে কাজ করে, বাইটের মাপে নয়। ১০,৪৬৯ থেকে ১২,২৮৭ পর্যন্ত জায়গাটি একই সাথে সুরক্ষার ফাঁক আর internal fragmentation.

এই page-মাপের সুরক্ষা নিজের চোখে দেখা যায়। নিচের C প্রোগ্রাম mmap দিয়ে দুটি page নেয়, দুটিতেই লেখে, তারপর mprotect দিয়ে শুধু প্রথম page-কে read-only করে — অর্থাৎ kernel সেই page-এর PTE-তে R/W বিট মুছে দেয়। এরপর প্রথম page-এ লেখার চেষ্টা MMU আটকায়, kernel প্রসেসকে SIGSEGV পাঠায়। প্রোগ্রামটি নিজের signal handler দিয়ে সেটি ধরে, sigsetjmp/siglongjmp দিয়ে লেখার জায়গা থেকে বেরিয়ে আসে, আর ফল ছাপে:

#define _GNU_SOURCE
#include <stdio.h>
#include <setjmp.h>
#include <signal.h>
#include <unistd.h>
#include <sys/mman.h>

static sigjmp_buf back;
static void *volatile fault_at;
static void on_segv(int sig, siginfo_t *info, void *ctx) {
    (void)sig; (void)ctx;
    fault_at = info->si_addr;                  /* address that faulted */
    siglongjmp(back, 1);                       /* leave the bad write */
}

int main(void) {
    long ps = sysconf(_SC_PAGESIZE);
    volatile char *mem = mmap(NULL, 2 * ps, PROT_READ | PROT_WRITE,
                              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (mem == MAP_FAILED) { perror("mmap"); return 1; }
    struct sigaction sa = {0};
    sa.sa_sigaction = on_segv;  sa.sa_flags = SA_SIGINFO;
    sigaction(SIGSEGV, &sa, NULL);
    printf("page size %ld, start page-aligned: %s\n", ps,
           (unsigned long)mem % ps ? "no" : "yes");
    mem[0] = 'A'; mem[ps] = 'B';                  /* both pages writable */
    mprotect((void *)mem, ps, PROT_READ);         /* page 0: read-only */
    printf("read page 0: %c\n", mem[0]);
    if (sigsetjmp(back, 1) == 0) { mem[10] = 'X'; puts("write succeeded?!"); }
    else printf("write blocked: SIGSEGV at offset %ld\n",
                (long)((char *)fault_at - (char *)mem));
    mem[ps + 10] = 'Y';                           /* page 1 unaffected */
    printf("page 1: %c%c, page 0 mem[10] = %d\n", mem[ps], mem[ps + 10], mem[10]);
    return 0;
}

page size 4096, start page-aligned: yes
read page 0: A
write blocked: SIGSEGV at offset 10
page 1: BY, page 0 mem[10] = 0

৭ · Internal fragmentation আর page size-এর দর-কষাকষি

Paging external fragmentation দূর করে, কিন্তু internal fragmentation আনে: প্রসেসের আকার page size-এর ঠিক গুণিতক না হলে শেষ frame-এর একটি অংশ অব্যবহৃত থাকে। পাঠ্যবইয়ের পরিচিত হিসাব:

1. Page size ২,০৪৮ বাইট, প্রসেস ৭২,৭৬৬ বাইট।
2. ৭২,৭৬৬ ÷ ২,০৪৮ = ৩৫, ভাগশেষ ১,০৮৬ → ৩৫টি পূর্ণ page আর একটি page-এ ১,০৮৬ বাইট।
3. মোট frame লাগবে ৩৬টি। শেষ frame-এ অব্যবহৃত ২,০৪৮ − ১,০৮৬ = ৯৬২ বাইট.
4. সবচেয়ে খারাপ ক্ষেত্র: প্রসেস n page আর ১ বাইট — তখন প্রায় পুরো একটি frame (২,০৪৭ বাইট) নষ্ট।

প্রসেসের আকার এলোমেলো হলে শেষ page-এর ব্যবহৃত অংশ ০ থেকে পুরো page-এর মধ্যে সমানভাবে ছড়ানো ধরে নেওয়া যায়, তাই গড়ে প্রতি প্রসেসে (বা প্রতি মেমরি-এলাকায়) আধা page নষ্ট. এটি ছোট page-এর পক্ষে যুক্তি। কিন্তু ছোট page মানে বেশি page, বড় টেবিল, আর TLB-তে কম জায়গা ধরা। নিচের টেবিল (৩২-বিট ঠিকানা, ৪ বাইটের entry, একতলা টেবিল) দর-কষাকষিটি দেখায়:

শেষ কলামটির নাম TLB reach — TLB-র entry-সংখ্যা × page size. বড় page-এ একই TLB অনেক বেশি মেমরি ঢেকে রাখে, তাই বড় ডেটা নিয়ে কাজ করা প্রোগ্রামে TLB miss কমে। আরেকটি দিক I/O: ডিস্ক থেকে page আনার সময় (পর্ব ৩৫) প্রতিটি পড়ার একটি নির্দিষ্ট খরচ (HDD-তে seek আর rotation, SSD-তেও প্রতিটি অনুরোধের নিজস্ব খরচ) আছে; বড় page-এ সেই খরচ বেশি ডেটায় ভাগ হয়, তাই প্রতি বাইটে I/O সস্তা। কিন্তু উল্টো দিকও আছে: বড় page-এ এমন ডেটাও আসে যা প্রোগ্রাম চায়নি, আর মেমরিতে “কাজের” অংশ কম সূক্ষ্মভাবে ধরা যায়। ছোট page প্রোগ্রামের locality আরও নিখুঁতভাবে অনুসরণ করে।

ঐতিহাসিকভাবে page size বেড়েছে: Atlas-এ ৫১২ word, VAX-এ ৫১২ বাইট, তারপর ৪ KiB প্রায় সার্বজনীন, আর এখন কিছু প্ল্যাটফর্ম ১৬ KiB-এ যাচ্ছে। কারণ RAM প্রতি দশকে বহুগুণ বেড়েছে, কিন্তু TLB-র আকার সেই হারে বাড়েনি, আর আধা page নষ্ট হওয়া বড় RAM-এ তুচ্ছ। সমাধান হিসেবে আধুনিক CPU একসাথে একাধিক page size দেয়: x86-64-এ ৪ KiB-এর পাশাপাশি huge page — ২ MiB আর ১ GiB. Database আর virtual machine-এর মতো বড় মেমরির কাজে huge page ব্যবহার হয়; Linux-এ hugetlbfs আর transparent huge page (THP) এর দুই পথ, যার বিস্তারিত পর্ব ৩৮-এ।

৮ · Shared page — এক frame, অনেক প্রসেস

Paging-এর একটি বড় উপহার হলো শেয়ার করা সহজ। দুই প্রসেসের page table-এ দুটি entry যদি একই frame number রাখে, তাহলে দুই প্রসেস একই physical মেমরি দেখে — যদিও তাদের logical ঠিকানা আলাদা হতে পারে। কপি করতে হয় না, শুধু টেবিলে একই নম্বর লিখলেই হয়।

সবচেয়ে বড় প্রয়োগ প্রোগ্রামের কোড। একটি অফিসের ৪০ জন কর্মী একসাথে একই text editor চালাচ্ছেন, editor-এর কোড ১৫০ KiB আর প্রত্যেকের নিজস্ব ডেটা ৫০ KiB. শেয়ার না করলে মোট ৪০ × (১৫০ + ৫০) = ৮,০০০ KiB. কোড শেয়ার করলে কোডের একটিই কপি: ১৫০ + ৪০ × ৫০ = ২,১৫০ KiB — প্রায় চার ভাগের এক ভাগ। আজকের Linux-এ প্রতিটি প্রোগ্রাম C library (glibc-এর libc.so.6) ব্যবহার করে; কয়েকশো প্রসেস চললেও libc-এর কোডের page-গুলো RAM-এ সাধারণত একবারই থাকে, প্রতিটি প্রসেসের টেবিল সেই একই frame-এ নির্দেশ করে।

শর্ত একটাই: শেয়ার করা কোড হতে হবে reentrant (pure code) — চলার সময় নিজেকে কখনো বদলায় না। প্রতিটি প্রসেসের নিজস্ব অবস্থা (ভ্যারিয়েবল, stack) থাকে তার নিজের ডেটা page-এ। OS এটি নিশ্চিত করে protection বিট দিয়ে: শেয়ার করা কোডের page read-only আর executable, তাই কোনো প্রসেস ভুল করে লিখতে গেলে trap. নিচের stepper-এ দুই প্রসেস একই editor চালাচ্ছে:

শেয়ারিং শুধু কোডে সীমিত নয়। দুই প্রসেস ইচ্ছা করে একই ডেটা page ভাগ করে নিতে পারে — shared memory দিয়ে IPC (পর্ব ১২) ঠিক এভাবেই কাজ করে। আর fork()-এর পর parent আর child প্রথমে সব page শেয়ার করে, শুধু-পড়ার অনুমতিতে; কেউ লিখলে তখনই কপি হয় — copy-on-write, যার পূর্ণ গল্প পর্ব ৩৫-এ। Windows-এও DLL-এর কোড এভাবে প্রসেসগুলোর মধ্যে শেয়ার হয়, আর macOS-এ সিস্টেমের library-গুলো একটি বড় “shared cache” হিসেবে সব প্রসেসে ভাগ হয়।

৯ · বাস্তব সিস্টেমে paging — page size দেখুন নিজের চোখে

ARM64 আর্কিটেকচার নিজেই তিনটি page size (granule) সমর্থন করে — ৪, ১৬ আর ৬৪ KiB — আর কোনটি ব্যবহার হবে, তা ঠিক করে OS. তাই একই CPU-তে ভিন্ন OS ভিন্ন page size নিতে পারে। Google Android 15 থেকে ১৬ KiB page-এর ডিভাইস সমর্থন শুরু করেছে এবং app-নির্মাতাদের ১৬ KiB-এর সাথে মানিয়ে নিতে বলেছে; কোন ফোন কোনটি ব্যবহার করে তা নির্মাতা আর মডেলভেদে আলাদা। শিক্ষা হলো: কোডে কখনো ৪০৯৬ লিখে রাখবেন না — চলার সময় জিজ্ঞেস করুন। C-তে sysconf(_SC_PAGESIZE) (উপরের প্রোগ্রামের মতো), shell-এ getconf PAGESIZE.

নিচের script page size দেখায়, তারপর /proc-এর /proc/self/maps পড়ে — এখানে self মানে যে প্রসেস ফাইলটি পড়ছে, অর্থাৎ awk নিজে। প্রতিটি লাইন একটি মেমরি-এলাকা (শুরু-শেষ ঠিকানা hex-এ, অনুমতি, ফাইল)। Script প্রতিটি এলাকার শুরু আর শেষ page size দিয়ে ভাগ যায় কি না (% ps == 0) যাচাই করে, আর মোট কত page তা যোগ করে। শেষে /proc/self/smaps থেকে প্রতিটি এলাকার kernel page size গোনে:

echo "page size: $(getconf PAGESIZE) bytes"
awk -v ps="$(getconf PAGESIZE)" '
function hex(s,   i, n) {                  # hex string -> number, any awk
  n = 0; s = tolower(s)
  for (i = 1; i <= length(s); i++) n = n * 16 + index("0123456789abcdef", substr(s, i, 1)) - 1
  return n
}
{ split($1, r, "-"); a = hex(r[1]); b = hex(r[2]); pages = (b - a) / ps
  total += pages; n++
  if (a % ps == 0 && b % ps == 0) ok++
  if (n == 1 || $6 == "[heap]" || $6 == "[stack]")
    printf "%s  %s  %5d pages  %s\n", r[1], $2, pages, $6
}
END { printf "regions: %d, page-aligned: %d, total %d pages = %d KiB\n", n, ok, total, total * ps / 1024 }
' /proc/self/maps
echo "KernelPageSize in grep's own smaps:"
grep KernelPageSize /proc/self/smaps | sort | uniq -c

page size: 4096 bytes
5a606eebb000  r--p      2 pages  /usr/bin/mawk
5a607eb55000  rw-p     33 pages  [heap]
7ffe6c517000  rw-p     33 pages  [stack]
regions: 29, page-aligned: 29, total 1025 pages = 4100 KiB
KernelPageSize in grep's own smaps:
     29 KernelPageSize:        4 kB

অন্য OS-এ একই প্রশ্নের উত্তর অন্য পথে — /proc শুধু Linux-এর জিনিস:

getconf PAGESIZE                    # 4096 on x86-64; 16384 on a 16 KiB-page kernel
grep -i huge /proc/meminfo          # HugePages_Total, Hugepagesize: 2048 kB ...
cat /sys/kernel/mm/transparent_hugepage/enabled   # e.g. always [madvise] never

$ getconf PAGESIZE
16384
$ sysctl hw.pagesize
hw.pagesize: 16384

PS> [Environment]::SystemPageSize
4096

১০ · AI-এর যুগে paging-এর অঙ্ক আর কোড

Paging-এর অঙ্ক দেখতে সহজ, তাই AI-কে দিলে দ্রুত উত্তর আসে। কিন্তু কয়েকটি ভুল বারবার দেখা যায় — বেশিরভাগই একক আর বিটের গোলমাল:

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

• p-এর বিট + d-এর বিট = logical address-এর মোট বিট, নিজে মিলিয়েছি
• অন্তত একটি ঠিকানা হাতে বাইনারিতে ভেঙে, আর ভাগ-ভাগশেষ দিয়ে দুইভাবে যাচাই করেছি
• উপরের translator-এ একই টেবিল আর ঠিকানা বসিয়ে ফল মিলিয়েছি
• KiB/MiB-এর একক আর “বিট নাকি বাইট” প্রতিটি ধাপে দেখেছি
• AI-এর দেওয়া কোডে page size hard-code করা নেই; sysconf বা getconf ব্যবহার হয়েছে, আর কমান্ডটি আমার OS আর distro-র জন্যই কি না man page-এ দেখেছি
• sudo বা chmod 777-এর মতো পরামর্শ পেলে কেন লাগবে তা বুঝে, আগে নিরাপদ পরিবেশে পরীক্ষা করেছি; মেমরি-সংক্রান্ত দাবি (যেমন huge page-এ দ্রুত হবে) নিজের workload-এ মেপে দেখেছি