LEVEL 4লেসন ১২/২৯অ্যাডভান্সড১ ঘণ্টা ৩০ মিনিট

Page Fault ও Demand Paging — OS-এর সবচেয়ে গুরুত্বপূর্ণ hook

Page Faults and Demand Paging

গত লেসনের শেষে একটা লাইন খোলা রেখে আসা হয়েছিল — page walk শেষে P=0 পাওয়া গেলে কী হয়? এই লেসনে সেই প্রশ্নের উত্তর: page fault handler-এর সিদ্ধান্ত-বৃক্ষ, minor বনাম major fault-এর নাটকীয় খরচ-পার্থক্য, demand paging আর copy-on-write PTE-স্তরে, আর Linux-এর page replacement কীভাবে LRU optimal-না-হওয়ার তাত্ত্বিক সীমা মেনেও কাজ চালায় — সব হাতে-কলমে perf, /usr/bin/time, cgroup আর নিজের-লেখা একটা SIGSEGV হ্যান্ডলার দিয়ে যাচাইযোগ্য।

এই লেসন শেষে আপনি পারবেন

Minor আর major page fault-এর মধ্যে খরচের পার্থক্য (~০.৫-৩ μs বনাম ~১০০ μs থেকে কয়েক ms) সংখ্যাসহ ব্যাখ্যা করতে পারবেন, আর কেন এই দুইটাকে একই 'page fault' নামে ডাকা সত্ত্বেও সম্পূর্ণ ভিন্ন ঘটনা হিসেবে বিবেচনা করা জরুরি
Linux-এর fault handler-এর সম্পূর্ণ সিদ্ধান্ত-বৃক্ষ (VMA বৈধ? অনুমতি আছে? copy-on-write? stack growth? swap থেকে আনতে হবে? নাকি SIGSEGV) ধাপে ধাপে বর্ণনা করতে পারবেন, আর একটা নির্দিষ্ট ঠিকানায় fault ঘটলে সেটা কোন শাখায় যাবে তা নির্ণয় করতে পারবেন
demand paging কীভাবে mmap()-কে lazy রাখে (গত লেসনের 'mmap মানেই allocation না' পর্যবেক্ষণের পূর্ণ ব্যাখ্যা) আর একটা প্রোগ্রামের প্রথম-touch খরচ কীভাবে হিসাব করতে হয় তা দেখাতে পারবেন
copy-on-write PTE-স্তরে ঠিক কীভাবে কাজ করে — fork()-এ কোনো data কপি হয় না, শুধু PTE read-only হয়, আর write fault-এই আসল কপি ঘটে (বা refcount=1 হলে কপিই লাগে না) — এই যুক্তি ব্যাখ্যা করতে পারবেন
Level 0-এর প্রমাণ অনুসরণ করে LRU কেন page replacement-এ optimal না তা বলতে পারবেন, আর Linux-এর active/inactive list আর swappiness কীভাবে এই তাত্ত্বিক সীমাবদ্ধতার সাথে বাস্তবে মানিয়ে চলে তা ব্যাখ্যা করতে পারবেন
perf আর /usr/bin/time -v দিয়ে সরাসরি minor/major fault গুনতে পারবেন, thrashing-এর 'cliff' নিজের মেশিনে পরিমাপ করতে পারবেন, আর একটা SIGSEGV-ভিত্তিক userspace demand-paging হ্যান্ডলার নিজে লিখে userfaultfd-র সাথে তার সম্পর্ক ব্যাখ্যা করতে পারবেন

আগে যা বোঝা থাকা দরকার

↑ TLB — Page Walk-এর খরচ থেকে বাঁচার ক্যাশ

আগে এটা বুঝি

গত লেসনে বারবার একটা লাইন এসেছিল, প্রতিবার একটু তাড়াহুড়ো করে পাশ কাটিয়ে — “walk শেষে দেখা যায় mapping-টাই অবৈধ (P=0)”। TLB miss-এর গল্পটা সহজ ছিল: hardware page walker কয়েক-দশ থেকে কয়েক-শ cycle-এ কাজ সেরে ফেলে, কোনো software-এর দরকারই পড়ে না। কিন্তু P=0 হলে গল্পটা সম্পূর্ণ বদলে যায় — walker হাল ছেড়ে দেয়, CPU একটা #PF exception (vector 14, x86-এ) ছোঁড়ে, আর নিয়ন্ত্রণ চলে যায় OS-এর কাছে।

এই মুহূর্তটাই — যাকে আমরা page fault বলি — আধুনিক অপারেটিং সিস্টেমের সবচেয়ে গুরুত্বপূর্ণ hook। এটা নিছক একটা error-condition না; এটা একটা extension point, যার উপর দাঁড়িয়ে আছে memory management-এর প্রায় প্রতিটা চতুর কৌশল। mmap() কীভাবে ১০০ MB ফাইল সাথে সাথে “খুলে ফেলে” কোনো I/O না করেই? demand paging। fork() কীভাবে একটা ৪ GB প্রসেসকে মিলিসেকেন্ডে কপি করে? copy-on-write। একটা প্রোগ্রাম কীভাবে RAM-এর চেয়ে বড় dataset নিয়ে কাজ করে (ধীরে হলেও)? swap। CRIU কীভাবে একটা running process-কে checkpoint করে অন্য মেশিনে migrate করায়? userfaultfd। Chrome কীভাবে একটা ট্যাব খোলার সময় পুরো renderer বাইনারি না পড়েই চালু হয়ে যায়? demand paging, আবার।

সবগুলোর ভিত্তি একই জায়গায় — একটা সাধারণ মেমরি অ্যাক্সেস, যা হঠাৎ একটা পূর্ণাঙ্গ trap হয়ে যায়, OS-কে সিদ্ধান্ত নেওয়ার সুযোগ দেয়: এই ঠিকানাটা আসলে কী চায়? এই লেসনে সেই সিদ্ধান্ত-বৃক্ষ, তার খরচ, আর তার উপর গড়ে ওঠা তিনটা প্রধান কৌশল (demand paging, COW, page replacement) — সব খুলে দেখব।

মূল ধারণা

Minor বনাম major fault — একই নাম, সম্পূর্ণ ভিন্ন খরচ

গত লেসনের misconception সেকশনে একটা পার্থক্য টানা হয়েছিল যেটা এখন পুরোপুরি খোলা দরকার। “Page fault” একটা ছাতা-শব্দ, তার নিচে দুইটা সম্পূর্ণ ভিন্ন ঘটনা:

	Minor fault (soft fault)	Major fault (hard fault)
Frame কোথায় পাওয়া যায়	ইতিমধ্যে RAM-এ — page cache-এ, অন্য কোনো mapping-এ, বা শুধু zero-fill দরকার	RAM-এ নেই — disk/swap থেকে পড়তে হবে
প্রয়োজনীয় কাজ	PTE বসানো, refcount বাড়ানো, TLB-তে entry — কোনো I/O না	সব minor fault-এর কাজ, প্লাস একটা block I/O request, process-কে blocked/sleep করানো, completion-এর জন্য অপেক্ষা
আনুমানিক খরচ	~০.৫-৩ μs (trap entry + handler logic, disk ছোঁয়াই না)	~১০০ μs (দ্রুত NVMe) থেকে ~১০ ms (ঘূর্ণায়মান HDD)
Kernel-এর counter	`min_flt` (`/proc/[pid]/stat`)	`maj_flt`

সংখ্যাটা লক্ষ করুন — major fault minor fault-এর চেয়ে ৫০ থেকে ২০,০০০ গুণ বেশি ব্যয়বহুল, storage-এর ধরনের উপর নির্ভর করে। এই একটা পার্থক্যই ব্যাখ্যা করে কেন page cache warm রাখা এত গুরুত্বপূর্ণ, আর কেন একটা প্রোগ্রাম প্রথমবার ধীরে চলে, দ্বিতীয়বার (একই ডেটা নিয়ে) হঠাৎ দ্রুত।

Fault handler-এর সিদ্ধান্ত-বৃক্ষ

CPU trap ছোঁড়ার পর Linux-এর do_page_fault (আর তার ভেতরের handle_mm_fault) একটা নির্দিষ্ট ক্রমে প্রশ্ন করে:

Page fault হ্যান্ডলার — সিদ্ধান্ত ক্রম (do_page_fault → handle_mm_fault, সরলীকৃত)

১. ঠিকানা কোনো VMA-র ভেতরে? (find_vma)
   না  → SIGSEGV  "invalid address" (segmentation violation)

২. VMA-র permission (VM_READ/VM_WRITE/VM_EXEC) fault-এর ধরনকে অনুমতি দেয়?
   না, এবং COW-ও প্রযোজ্য না → SIGSEGV  "protection violation"

৩. এটা কি copy-on-write write-fault?
   (PTE-তে R/W=0, কিন্তু VMA নিজে writable, আর page-টা shared)
   হ্যাঁ → নতুন frame বরাদ্দ, পুরনো frame থেকে কপি,
           PTE-তে R/W=1 বসিয়ে resume  (hood সেকশনে বিস্তারিত)

৪. এটা কি stack growth?
   (fault ঠিকানা বর্তমান stack VMA-র নিচে, RLIMIT_STACK-এর ভেতরে)
   হ্যাঁ → stack VMA প্রসারিত করুন, নতুন frame zero-fill করে resume

৫. PTE-তে কি একটা swap entry আছে (page আগে RAM-এ ছিল, এখন swap-এ)?
   হ্যাঁ → swap থেকে পড়ুন, নতুন frame-এ বসান, resume   ← major fault

৬. অন্যথায় — এই page প্রথমবার touch হচ্ছে (demand paging)।
   Anonymous VMA হলে   → zero-fill করা নতুন frame          ← সাধারণত minor
   File-backed VMA হলে → page cache-এ আছে?
                          থাকলে সরাসরি map               ← minor
                          না থাকলে disk থেকে পড়ুন          ← major

Page fault handler-এর সিদ্ধান্ত-বৃক্ষ — সরলীকৃত, কিন্তু বাস্তব Linux ক্রম অনুসরণ করে।

লক্ষ করুন — SIGSEGV শুধু দুইটা জায়গায় আসে: ঠিকানাটা কোনো VMA-তেই নেই (classic “invalid pointer”), অথবা VMA আছে কিন্তু অনুমতি নেই (যেমন একটা read-only page-এ লেখা, বা একটা non-executable page থেকে instruction fetch করা — গত লেসনের NX বিটের প্রয়োগ)। বাকি সবগুলো শাখা — COW, stack growth, swap, demand paging — কোনোটাই error না, এগুলো স্বাভাবিক, ইচ্ছাকৃতভাবে-ব্যবহৃত mechanism।

Demand paging — mmap()-কে lazy রাখার আসল কারণ

গত লেসনের misconception সেকশনে দেখানো হয়েছিল mmap() কোনো physical frame বরাদ্দ করে না, শুধু একটা VMA নথিভুক্ত করে। এখন সেই আচরণের প্রক্রিয়াটা সম্পূর্ণ পাওয়া গেল — সিদ্ধান্ত-বৃক্ষের ধাপ ৬। প্রথমবার যখন কোনো instruction সেই ঠিকানায় touch করে, PTE-তে P=0 পাওয়া যায়, fault হয়, আর তখনই — শুধু তখনই — আসল frame বরাদ্দ হয়।

এর ব্যবহারিক ফল বিশাল। একটা ২০০ MB বাইনারি চালু করলে kernel পুরো ২০০ MB disk থেকে পড়ে না — execve() শুধু ELF-এর প্রতিটা segment-এর জন্য VMA বানায়, তারপর CPU যে instruction চালাতে চায় ঠিক সেই page-টাই fault করে আনা হয়। বেশিরভাগ প্রোগ্রামের বেশিরভাগ কোড (error-handling path, বিরল feature, dead code) কখনোই touch হয় না — সেই page-গুলো কখনো fault-ই করে না, কখনো disk থেকে পড়াই হয় না। এটাই lazy evaluation-এর একটা memory-স্তরের রূপ, ঠিক programming-languages মডিউলে যেমন lazy evaluation দেখবেন কম্পিউটেশনের স্তরে।

Copy-on-write — PTE-স্তরে

গত দুই লেসনে COW-র কথা এসেছে কিন্তু mechanism খোলা হয়নি। এখন সিদ্ধান্ত-বৃক্ষের ধাপ ৩-এর পূর্ণ ব্যাখ্যা:

fork() ডাকলে child-এর জন্য একটা নতুন page table তৈরি হয় — কিন্তু কোনো data কপি হয় না। বদলে, parent-এর প্রতিটা writable page-এর PTE-তে R/W বিট ০ করে দেওয়া হয়, parent আর child দুইটাতেই, আর সেই physical frame-এর reference count (page->_refcount) বাড়ানো হয় (এখন দুইটা PTE একই frame-কে নির্দেশ করছে)। এই পুরো কাজটা — PTE-গুলো iterate করে বিট বদলানো — কয়েক হাজার entry-র জন্যও মাইক্রোসেকেন্ডের ব্যাপার, page-এর সংখ্যা যত বড়ই হোক না কেন data-র আকার।

সমস্যা হয় যখন কেউ লেখে। R/W=0 একটা page-এ লেখার চেষ্টা একটা protection-violation fault তৈরি করে — কিন্তু handler সাথে সাথে SIGSEGV পাঠায় না। সে প্রথমে চেক করে: VMA নিজে কি writable (mprotect দিয়ে সত্যিই read-only করা হয়নি তো)? আর page-টা কি সত্যিই shared (refcount > ১)?

refcount > ১ হলে (আরেকজন এখনো এই frame ব্যবহার করছে) — একটা নতুন frame বরাদ্দ, পুরনো data কপি, নতুন frame-এ লেখা, এই process-এর PTE নতুন frame-কে নির্দেশ করানো, R/W=1, পুরনো frame-এর refcount কমানো। এখানেই আসল কপি ঘটে, আর শুধু এই একটা page-এর জন্য, পুরো address space-এর জন্য না।
refcount == ১ হলে (এই process-ই একমাত্র মালিক, অন্য কেউ আর ব্যবহার করছে না — হয়তো sibling process আগেই তার কপি করে ফেলেছে বা exit করেছে) — কোনো কপির দরকারই নেই, শুধু R/W বিট আবার ১ করে দেওয়া। একে বলে “breaking COW without copying”।

Page replacement — কেন LRU optimal না

RAM সসীম, তাই যখন নতুন frame দরকার আর কোনো ফাঁকা frame নেই, OS-কে কাউকে বাদ দিতে হয় (evict)। কোন page বাদ দেওয়া উচিত? গত মডিউলে (Level 0, mathematics) ঠিক এই প্রশ্নটাই একটা প্রমাণের বিষয় ছিল — mathematics/proof-techniques লেসনের একটা design-প্রশ্নে (n=3) দেখানো হয়েছিল একটা counterexample দিয়ে: cache আকার ২, access sequence A, B, C, A, B, C, ... — LRU প্রতিবার ঠিক সেই entry বাদ দেয় যেটা এক ধাপ পরেই লাগবে, ফলে ১০০% miss, যেখানে একটা ভিন্ন policy (A, B সবসময় রাখা, C কখনো cache না করা) দিত ৬৬% hit rate। উপসংহার ছিল $\text{LRU optimal না}\quad\blacksquare$ — সত্যিকারের optimal (Bélády’s OPT) দাবি করে ভবিষ্যৎ জানা, যা বাস্তবে অসম্ভব।

এই একই প্রমাণ page replacement-এ হুবহু প্রযোজ্য — page replacement আসলে cache eviction-এরই একটা বিশাল-স্কেল সংস্করণ (TLB replacement যেমন ছোট-স্কেল সংস্করণ ছিল, গত লেসনের hood সেকশনে দেখেছেন)। LRU সব sequence-এ optimal না, কিন্তু বাস্তব প্রোগ্রামে temporal locality থাকে বলে ভালো কাজ করে — একটা empirical দাবি, প্রমাণযোগ্য দাবি না।

Linux বাস্তবে কী করে — exact LRU না, active/inactive list

exact LRU রাখতে হলে প্রতিটা memory access-এ একটা list-এর মধ্যে সেই page-কে সামনে সরাতে হবে — কোটি কোটি access-এ এই bookkeeping অবাস্তব ব্যয়বহুল (ঠিক গত লেসনে দেখা TLB-র exact-LRU-vs-approximation trade-off-এর মতোই, কিন্তু এখানে স্কেল আরও বড়)। তাই Linux দুইটা list রাখে প্রতিটা memory zone-এ:

List	অর্থ
active list	সাম্প্রতিক-ব্যবহৃত page, evict-এর জন্য শেষ প্রার্থী
inactive list	reclaim-এর প্রথম প্রার্থী

একটা page inactive list-এ থাকা অবস্থায় আবার access হলে, active list-এ প্রমোট হয় (একটা accessed বিট চেক করে — ঠিক TLB-র pseudo-LRU-র মতোই সস্তা একটা approximation, exact LRU order না)। Memory চাপে পড়লে, kernel প্রথমে active list-এর একটা অংশ inactive-এ demote করে (second-chance দিয়ে — যদি সেই সময়ের মধ্যে আবার access হয়, আবার active-এ ফিরে যায়), তারপর inactive list-এর tail থেকে reclaim শুরু করে।

Swappiness — anonymous বনাম file-backed reclaim-এর ভারসাম্য

Reclaim করার সময় দুই ধরনের page পাওয়া যায়:

File-backed, clean (page cache — কোনো ফাইলের কন্টেন্ট, লেখা হয়নি): সরাসরি বাদ দেওয়া যায়, দরকার হলে আবার disk থেকে পড়া যাবে। সস্তা reclaim।
Anonymous (heap, stack — কোনো ফাইলের সাথে সম্পর্কিত না): বাদ দেওয়ার আগে swap-এ লিখতে হবে, নাহলে data হারিয়ে যাবে। ব্যয়বহুল reclaim — একটা write I/O লাগে।

/proc/sys/vm/swappiness (০-১০০, ডিফল্ট ৬০) এই দুইয়ের ভারসাম্য নিয়ন্ত্রণ করে — বেশি swappiness মানে kernel তুলনামূলক আগে anonymous page swap করতে রাজি, কম মানে page cache আগে বাদ দিয়ে anonymous page যতটা সম্ভব RAM-এ রাখার চেষ্টা।

Thrashing — যখন working set RAM ছাড়িয়ে যায়

Peter Denning-এর ১৯৬৮ সালের working set model একটা সহজ কিন্তু গভীর পর্যবেক্ষণ দেয়: একটা প্রসেসকে ভালোভাবে চালাতে হলে তার “working set” (একটা সময়-জানালায় সক্রিয়ভাবে ব্যবহৃত page-গুলোর সেট) RAM-এ ধরে রাখা দরকার। যদি একসাথে চলা সব প্রসেসের working set-এর যোগফল উপলব্ধ RAM ছাড়িয়ে যায়, একটা দুষ্টচক্র শুরু হয়:

page A আনতে হবে → কাউকে evict করতে হবে → evict-করা page B-ই একটু পরে আবার লাগবে → B আনতে major fault → এবার A-কে evict করতে হবে → …

প্রতিটা fault এখন একটা major fault (ধাপ ৫, উপরের সিদ্ধান্ত-বৃক্ষ), প্রতিটা ~১০০ μs-১০ ms। CPU প্রায় পুরো সময় I/O-এর জন্য অপেক্ষায় কাটায়, প্রকৃত কাজ প্রায় বন্ধ হয়ে যায় — একে বলে thrashing। এটা একটা cliff, gradual degradation না — RAM-এর সীমার ঠিক নিচে সিস্টেম স্বাভাবিক, সামান্য ছাড়ালেই throughput কয়েক ডজন গুণ কমে যায় (experiment সেকশনে এই cliff-টা সরাসরি মাপা হবে, ঠিক গত লেসনের TLB reach cliff-এর মতোই আকৃতিতে)।

ভেতরে কী ঘটছে

একটা fault-এর ভেতরের ধাপ — trap থেকে resume পর্যন্ত

x86-এ page fault exception (#PF, vector 14) একটা error code stack-এ push করে, যা fault-এর কারণ সম্পর্কে জানায়:

বিট	নাম	অর্থ
০	P	০ = non-present page (P=0-এর কারণে fault), ১ = protection violation
১	W/R	০ = read access, ১ = write access
২	U/S	০ = supervisor mode, ১ = user mode
৪	I/D	১ = instruction fetch (NX violation-এর সময় প্রাসঙ্গিক)

এই বিটগুলো দিয়েই handler প্রথম প্রশ্নগুলোর উত্তর পায় — P=0+W/R=1 মানে “not-present page-এ লেখার চেষ্টা”, অর্থাৎ হয়তো demand paging (ধাপ ৬) নয়তো swap (ধাপ ৫)। P=1+W/R=1 মানে “present কিন্তু write permission নেই” — এটাই COW-র সিগনেচার (ধাপ ৩)।

একটা anonymous heap page-এ প্রথম write — COW handler-এর ভেতর

একটা child process লিখছে একটা heap byte-এ, যা fork()-এর সময় R/W=0 করা হয়েছিলPTE: P=1 (frame আছে), R/W=0 — CPU write-এ protection violation ধরে
CPU #PF exception ছোঁড়ে, error code = P=1, W/R=1, U/S=1control চলে যায় kernel-এর page fault entry point-এ, একটা privilege-level পরিবর্তনসহ
do_page_fault → handle_mm_fault → find_vmaঠিকানাটা একটা বৈধ, writable anonymous VMA-র ভেতরে — ধাপ ১-২ পাস
COW চেক — refcount দেখা হলোএই frame-এর refcount = ২ (parent + child দুইজনেই ব্যবহার করছে) — সত্যিকারের copy দরকার
নতুন frame বরাদ্দ, পুরনো frame থেকে ৪ KB কপিএকটা physical memory-to-memory কপি — বেশ কিছু cycle, কিন্তু এখনো কোনো disk I/O না
child-এর PTE আপডেট — নতুন frame, R/W=1parent-এর PTE অপরিবর্তিত থাকে, এখনো পুরনো frame-কে নির্দেশ করছে, R/W=0-ই থাকে
পুরনো frame-এর refcount কমে ১ — এখন শুধু parent-এর দখলেপরের বার parent যদি এই page-এ লেখে, refcount==1 পাবে, কপি ছাড়াই শুধু R/W=1 হয়ে যাবে
instruction replay — এবার write সফলএই পুরো fault-টা একটা minor fault ছিল — কোনো disk touch হয়নি, শুধু memory copy

লক্ষ করুন — COW fault-টা minor, disk কখনো ছোঁয়া হয়নি, শুধু RAM-এ RAM-এ একটা কপি। এই পার্থক্যটাই এই লেসনের প্রথম টেবিলের ভিত্তি — “page fault” নাম শুনে ভয় পাওয়ার আগে, কোন ধরনের fault সেটা জিজ্ঞাসা করা জরুরি।

উদাহরণ

একটা ২০০ MB বাইনারি চালু হওয়া — demand paging-এর প্রকৃত খরচ

ধরুন একটা ২০০ MB executable চালু হচ্ছে। ৪ KB page-এ মোট page সংখ্যা:

$\frac{200\,\text{MB}}{4\,\text{KB}} = 51{,}200 \text{ page}$

বাস্তবে একটা typical প্রোগ্রাম রান-টাইমে তার কোডের একটা ছোট অংশই ছোঁয় — ধরি ১৫% (৭,৬৮০ page)। বাকি ৮৫% (error path, ব্যবহৃত না হওয়া feature) কখনো fault-ই করে না।

প্রথম রান, ঠান্ডা page cache (fresh boot, কেউ আগে এই ফাইল পড়েনি):

প্রতিটা touch একটা major fault (readahead কিছুটা batch করে, কিন্তু সরল হিসাবের জন্য প্রতি page একটা fault ধরি):

$7{,}680 \times 200\,\mu s \approx 1.54\,\text{সেকেন্ড}$

দ্বিতীয় রান, warm page cache (একই ফাইল, ইতিমধ্যে RAM-এ):

$7{,}680 \times 2\,\mu s \approx 15.4\,\text{ms}$

পার্থক্য ~১০০ গুণ — একই কোড, একই touched page সংখ্যা, শুধু page cache-এর অবস্থা ভিন্ন। এটাই ব্যাখ্যা করে কেন একটা অ্যাপ্লিকেশন প্রথমবার (বা reboot-এর পর প্রথমবার) ধীরে চালু হয়, তারপরের রানগুলোয় হঠাৎ দ্রুত — সাধারণত কোনো কোড বদলায়নি, শুধু disk I/O-এর জায়গায় RAM copy চলে এসেছে।

তুলনা — পুরোটা আগেভাগে load করলে কী হতো

যদি demand paging না থাকত আর পুরো ২০০ MB আগেভাগে (eager) load করতে হতো, প্রতিবারই ৫১,২০০ page পড়তে হতো, touch হোক বা না হোক — ঠান্ডা cache-এ প্রায় ১০ সেকেন্ড, যদিও প্রোগ্রামের মাত্র ১৫% আসলে দরকার। demand paging শুধু গতি বাড়ায় না, অপ্রয়োজনীয় I/O সম্পূর্ণ এড়িয়ে যায় — যা এই লেসনের পরের experiment-এ সরাসরি readahead-এর সংখ্যায় দেখা যাবে।

নিজে চালিয়ে দেখুন

EXPERIMENT

Minor বনাম major fault গুনুন — একটা বড় ফাইল mmap করে, ঠান্ডা বনাম গরম cache-এ

Linux, root দরকার (drop_caches-এর জন্য)· ২০ মিনিট

/* mmap_read.c — একটা mmap করা ফাইলের প্রতিটা page touch করে, byte-sum
 * করে (compiler-কে touch বাদ দিতে বাধা দিতে volatile ব্যবহার)।
 *
 * বানান: gcc -O2 -o mmap_read mmap_read.c
 * চালান: ./mmap_read <file>
 */
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

int main(int argc, char **argv) {
    int fd = open(argv[1], O_RDONLY);
    if (fd < 0) { perror("open"); return 1; }
    struct stat st;
    fstat(fd, &st);
    char *p = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }

    volatile unsigned long sum = 0;
    for (long i = 0; i < st.st_size; i += 4096) sum += (unsigned char)p[i];
    printf("sum = %lu\n", sum);
    return 0;
}

dd if=/dev/urandom of=bigfile.bin bs=1M count=500
gcc -O2 -o mmap_read mmap_read.c

# ঠান্ডা রান — page cache খালি করে দিন
sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
/usr/bin/time -v ./mmap_read bigfile.bin 2>&1 | grep -E "Major|Minor|Elapsed"

# গরম রান — একই ফাইল, এবার page cache-এ আছে
/usr/bin/time -v ./mmap_read bigfile.bin 2>&1 | grep -E "Major|Minor|Elapsed"

ঠান্ডা রানের typical আউটপুট:

Major (requiring I/O) page faults: 3912
Minor (reclaiming a frame) page faults: 51
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.38

গরম রানের typical আউটপুট:

Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 128002
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.04

লক্ষ করুন major fault সংখ্যা (৩৯১২) মোট page সংখ্যার (৫০০ MB ÷ ৪ KB = ১২৮,০০০) চেয়ে অনেক কম — কারণ kernel-এর readahead একটা fault-এ শুধু একটা page না, আশেপাশের একটা বড় window (সাধারণত ১২৮ KB, অর্থাৎ ৩২ page) একসাথে পড়ে নেয়। তাই readahead window-এর প্রথম page-ই শুধু সত্যিকারের major fault, বাকি ৩১টা পরে touch হলে ইতিমধ্যে RAM-এ পাওয়া যায় — minor। গরম রানে সব ১,২৮,০০২টা fault-ই minor (প্রতিটা page-এর জন্য একটা PTE বসাতে হয়, যদিও data আগে থেকেই RAM-এ), আর সময় প্রায় ১০ গুণ কম।

এটা কী প্রমাণ করে

একই কোড, একই touched page সংখ্যা — কিন্তু page cache-এর অবস্থা ভিন্ন হলে fault-এর ধরন (minor বনাম major) আর তার ফলে wall-clock সময় নাটকীয়ভাবে বদলে যায়।

EXPERIMENT

Thrashing cliff — cgroup দিয়ে memory সীমাবদ্ধ করে working-set sweep

Linux, cgroup v2 (systemd-ভিত্তিক ডিস্ট্রোয় ডিফল্ট), root দরকার· ২৫ মিনিট

/* thrash_sweep.c — বাড়তে থাকা working-set আকারে random byte-write,
 * ops/sec মাপুন। cgroup memory.max দিয়ে সীমাবদ্ধ করে চালালে সীমা
 * ছাড়ানোর পর thrashing দেখা যায়।
 *
 * বানান: gcc -O2 -o thrash_sweep thrash_sweep.c
 * চালান: ./thrash_sweep <size_mb>
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/mman.h>

int main(int argc, char **argv) {
    size_t mb = atol(argv[1]);
    size_t total = mb * 1024 * 1024;
    char *buf = mmap(NULL, total, PROT_READ | PROT_WRITE,
                      MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (buf == MAP_FAILED) { perror("mmap"); return 1; }
    size_t page = 4096, npages = total / page;

    struct timespec t0, t1;
    long ops = 20 * 1000 * 1000;
    srand(1);
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (long i = 0; i < ops; i++)
        buf[((size_t)rand() % npages) * page] = (char)i;
    clock_gettime(CLOCK_MONOTONIC, &t1);

    double sec = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("%-6zu MB   ops/sec = %.0f\n", mb, ops / sec);
    return 0;
}

sudo mkdir -p /sys/fs/cgroup/pgfault_demo
echo 200M | sudo tee /sys/fs/cgroup/pgfault_demo/memory.max
echo $$   | sudo tee /sys/fs/cgroup/pgfault_demo/cgroup.procs   # বর্তমান shell-কে cgroup-এ ঢোকান

for mb in 50 100 150 200 250 300 400; do
    ./thrash_sweep $mb
done
grep pgmajfault /sys/fs/cgroup/pgfault_demo/memory.stat

Typical আউটপুট:

50 MB    ops/sec = 8420000
100 MB   ops/sec = 8110000
150 MB   ops/sec = 7760000
200 MB   ops/sec = 6900000     ← memory.max (200M)-এর ঠিক কাছে
250 MB   ops/sec = 210000      ← cliff — ৩০+ গুণ কম, thrashing শুরু
300 MB   ops/sec = 90000
400 MB   ops/sec = 41000

pgmajfault 1284213

৫০ থেকে ২০০ MB পর্যন্ত throughput প্রায় স্থিতিশীল (working set cgroup সীমার ভেতরে, সব anonymous page RAM-এ থাকতে পারছে)। ২৫০ MB-তে সীমা ছাড়ানোর সাথে সাথে throughput এক ধাক্কায় ৩০ গুণেরও বেশি কমে যায় — প্রতিটা random write এখন সম্ভাব্যভাবে একটা page evict করছে যেটা কিছুক্ষণ পরেই আবার দরকার হবে, দুষ্টচক্র শুরু। pgmajfault কাউন্টার নিশ্চিত করে — লক্ষ লক্ষ major fault, যেখানে ২০০ MB-র নিচে এই সংখ্যা প্রায় শূন্যের কাছাকাছি থাকত।

এটা কী প্রমাণ করে

working set RAM সীমার নিচে থাকলে throughput স্থিতিশীল থাকে; সীমা সামান্য পার হলেই thrashing শুরু হয় — একটা gradual degradation না, একটা cliff, ঠিক গত লেসনের TLB reach cliff-এর মতোই আকৃতিতে।

নিজে বানান

BUILD IT

একটা userspace demand-paging হ্যান্ডলার — SIGSEGV দিয়ে

C · ●●●●○

একটা region PROT_NONE দিয়ে mmap করুন — কোনো access-ই এখনো অনুমোদিত না
SA_SIGINFO সহ একটা SIGSEGV handler বসান — si_addr থেকে ঠিক কোন page-এ fault হলো বের করুন
handler-এর ভেতরে mprotect দিয়ে সেই একটা page-কে PROT_READ | PROT_WRITE করুন, ডেটা বসান
handler থেকে normal return করুন — kernel একই faulting instruction আবার চালাবে, এবার সফল হবে
একটা elelog রাখুন কোন page কতবার fault করল, নিশ্চিত করুন প্রতিটা distinct page ঠিক একবারই fault করছে

/* userfault_demo.c — একটা userspace demand-paging সিস্টেম। region-টা
 * PROT_NONE দিয়ে mmap করা; প্রথম touch একটা SIGSEGV তৈরি করে, handler
 * ঠিক সেই page-টাকে writable করে, data বসায়, আর ফিরে যায় — kernel
 * নিজে থেকেই একই instruction আবার চালায়। এটাই kernel-এর নিজের
 * demand-paging mechanism-এর একটা userspace অনুকরণ।
 *
 * বানান: gcc -O0 -o userfault_demo userfault_demo.c
 */
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <unistd.h>
#include <stdint.h>
#include <sys/mman.h>

#define PAGE_SIZE     4096
#define REGION_PAGES  16

static char *region;
static int   faulted[REGION_PAGES];
static long  fault_count = 0;

static void segv_handler(int sig, siginfo_t *si, void *uctx) {
    (void)sig; (void)uctx;
    char *addr = (char *)((uintptr_t)si->si_addr & ~(uintptr_t)(PAGE_SIZE - 1));

    if (addr < region || addr >= region + REGION_PAGES * PAGE_SIZE) {
        fprintf(stderr, "সত্যিকারের segfault, ঠিকানা %p — abort\n", si->si_addr);
        _exit(1);
    }

    int idx = (int)((addr - region) / PAGE_SIZE);
    if (faulted[idx]) {
        fprintf(stderr, "একই page-এ দ্বিতীয়বার fault — bug\n");
        _exit(1);
    }

    /* "demand paging" — বাস্তব সিস্টেমে এখানে disk/network থেকে data
     * আনা হতো; demo-র জন্য zero-fill আর একটা marker */
    if (mprotect(addr, PAGE_SIZE, PROT_READ | PROT_WRITE) != 0) {
        perror("mprotect");
        _exit(1);
    }
    memset(addr, 0, PAGE_SIZE);
    snprintf(addr, 32, "page %d faulted-in\n", idx);

    faulted[idx] = 1;
    fault_count++;
    /* এখানেই handler শেষ — normal return, kernel একই instruction
     * আবার চালাবে, এবার mapping writable, তাই সফল হবে */
}

int main(void) {
    struct sigaction sa = {0};
    sa.sa_sigaction = segv_handler;
    sa.sa_flags = SA_SIGINFO;
    sigemptyset(&sa.sa_mask);
    if (sigaction(SIGSEGV, &sa, NULL) != 0) { perror("sigaction"); return 1; }

    size_t total = REGION_PAGES * PAGE_SIZE;
    region = mmap(NULL, total, PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (region == MAP_FAILED) { perror("mmap"); return 1; }

    printf("region mmap হলো PROT_NONE দিয়ে — কোনো page এখনো touch করা যায় না\n");

    int order[] = {3, 7, 3, 1, 15, 7, 0};
    for (size_t i = 0; i < sizeof(order) / sizeof(*order); i++) {
        char *p = region + order[i] * PAGE_SIZE;
        printf("touching page %d: %s", order[i], p);
    }

    printf("মোট %ld distinct page fault হ্যান্ডল হলো\n", fault_count);

    munmap(region, total);
    return 0;
}

চালালে দেখবেন:

region mmap হলো PROT_NONE দিয়ে — কোনো page এখনো touch করা যায় না
touching page 3: page 3 faulted-in
touching page 7: page 7 faulted-in
touching page 3: page 3 faulted-in
touching page 1: page 1 faulted-in
touching page 15: page 15 faulted-in
touching page 7: page 7 faulted-in
touching page 0: page 0 faulted-in
মোট 5 distinct page fault হ্যান্ডল হলো

page 3 আর 7 দুইবার touch হলেও fault_count মাত্র ৫ বাড়ে — দ্বিতীয়বার touch-এ কোনো fault-ই হয় না, কারণ প্রথমবারের mprotect ইতিমধ্যে সেই page-কে writable করে রেখেছে। এটাই ঠিক kernel-এর demand paging-এর আচরণ — প্রতিটা page ঠিক একবার fault করে, তারপর “শেখা হয়ে গেছে”।

এটা একটা teaching toy, production-এ ব্যবহারযোগ্য না

SIGSEGV-ভিত্তিক এই কৌশলের গুরুতর সীমাবদ্ধতা আছে — signal handler async-signal-safe function-এর বাইরে কিছু ডাকতে পারে না (এখানে printf/snprintf কড়াভাবে নিরাপদ না, শুধু demo-র সরলতার জন্য ব্যবহার করা হয়েছে), আর multi-threaded প্রোগ্রামে একই সাথে দুইটা thread fault করলে race condition তৈরি হতে পারে (faulted[] array-তে কোনো lock নেই)। উৎপাদন-মানের সিস্টেম (QEMU-র post-copy live migration, CRIU, Firecracker-এর lazy page loading) তাই userfaultfd ব্যবহার করে — একটা file descriptor-ভিত্তিক API যেখানে fault-এর তথ্য একটা আলাদা, সাধারণ (non-signal-handler) thread-এ পড়া যায়, read()/poll() দিয়ে, কোনো async-signal-safety সীমাবদ্ধতা ছাড়াই। মূল ধারণা একই — “একটা fault ধরো, তারপর তাকে সন্তুষ্ট করো” — শুধু mechanism নিরাপদ আর multi-threaded-friendly।

নিজে বাড়ান

userfaultfd-এ পুনর্লিখুন। userfaultfd() সিসকল দিয়ে একটা fd খুলুন, UFFDIO_REGISTER দিয়ে region রেজিস্টার করুন, একটা আলাদা thread-এ সেই fd read() করে fault event ধরুন, UFFDIO_COPY দিয়ে data বসান। SIGSEGV পদ্ধতির সাথে কোড কতটা বদলায় তুলনা করুন।
সত্যিকারের ফাইল থেকে data আনুন। zero-fill-এর বদলে handler-এ একটা ফাইল pread() করে সেই page-এর জন্য প্রকৃত content বসান — এটাই আসল demand paging।
Multi-threaded চালান। একাধিক thread একসাথে ভিন্ন page touch করলে কী হয় দেখুন — faulted[] array-তে race আছে কিনা যাচাই করুন, তারপর একটা atomic বা lock দিয়ে ঠিক করুন।
খরচ মাপুন। প্রতিটা fault-এর চারপাশে clock_gettime বসিয়ে userspace handler-এর overhead মাপুন, আর একটা সাধারণ heap write (কোনো signal ছাড়া)-এর সাথে তুলনা করুন — কত গুণ ধীর?
একটা “swap file” simulate করুন। যখন কোনো page অনেকক্ষণ touch হয়নি, সেটা আবার PROT_NONE করে দিন (একটা ছোট background thread দিয়ে) — এবার পরের touch আবার fault করবে, ঠিক real swap-out/swap-in-এর মতো একটা userspace অনুকরণ।

বাস্তব সিস্টেমে

Redis BGSAVE — COW-র সবচেয়ে পরিচিত ব্যবহার। fork() করার পর child process পুরো dataset snapshot করে ডিস্কে লেখে, আর parent স্বাভাবিকভাবে client request সার্ভ করতে থাকে। যতক্ষণ parent কোনো key লেখে না, কোনো copy ঘটে না — শুধু যেসব page লেখা হয় সেগুলোই COW fault করে, ছড়িয়ে ছড়িয়ে। ভারী write workload-এ এই ছড়ানো COW fault-গুলোই RSS-কে হঠাৎ বাড়িয়ে দিতে পারে (“COW spike”), আর transparent huge pages চালু থাকলে (গত লেসনের realworld অংশে দেখা misconception) একটা ২ MB page-এ একটা byte লেখাই পুরো ২ MB কপি ঘটায়।

CRIU আর QEMU post-copy live migration — userfaultfd-র উৎপাদন-মানের ব্যবহার। একটা running VM-কে নতুন হোস্টে migrate করার সময় পুরো memory আগে কপি করা সময়সাপেক্ষ। Post-copy পদ্ধতিতে VM নতুন হোস্টে সাথে সাথে চালু হয়ে যায়, আর যখনই কোনো page touch হয় যা এখনো transfer হয়নি, একটা userfaultfd fault ট্রিগার হয়, যা নেটওয়ার্কের ওপারে পুরনো হোস্ট থেকে সেই page আনায় — ঠিক এই লেসনের BuildIt-এর demo, শুধু “backing store” এখন একটা নেটওয়ার্ক সংযোগ।

Firecracker microVM — লক্ষ লক্ষ VM দ্রুত বুট করানো। AWS Lambda-র ভিত্তি Firecracker snapshot থেকে VM restore করার সময় পুরো memory eager-load না করে userfaultfd দিয়ে lazily fault-in করে — একটা VM মিলিসেকেন্ডে “চালু” দেখায়, বাস্তবে তার memory ধীরে ধীরে touch হওয়ার সাথে সাথে আসে, ঠিক এই লেসনের ২০০ MB বাইনারি উদাহরণের মতোই যুক্তি, শুধু scale আরও বড়।

JVM-এর -XX:+AlwaysPreTouch — বিপরীত কৌশল। গত লেসনের realworld অংশে দেখা এই flag ইচ্ছাকৃতভাবে demand paging-এর সুবিধা বাদ দেয় — startup-এই পুরো heap touch করে সব page fault-in করায়, যাতে চলার সময় (latency-সংবেদনশীল মুহূর্তে) কোনো অপ্রত্যাশিত fault না ঘটে। Startup সময় বাড়ে, কিন্তু runtime latency predictable হয় — একটা স্পষ্ট trade-off যা এই লেসনের যুক্তি দিয়েই ব্যাখ্যা করা যায়।

cgroup v2 memory.max আর OOM killer — thrashing এড়ানোর দুইটা ভিন্ন কৌশল। এই লেসনের thrashing experiment-এ ব্যবহৃত memory.max সীমা ছাড়ালে কী হবে সেটা নির্ভর করে configure-এর উপর — সীমা ছাড়ালে কার্নেল আগে reclaim/swap চেষ্টা করে (thrashing), কিন্তু সম্পূর্ণ অক্ষম হলে (কোনো swap নেই, বা memory.swap.max=0) কার্নেল বরং সেই cgroup-এর একটা প্রসেসকে OOM kill করে দেয় — thrashing-এর ধীর যন্ত্রণার চেয়ে একটা দ্রুত, নির্ধারক ব্যর্থতা প্রায়ই কাম্য, বিশেষত Kubernetes-এর মতো orchestration সিস্টেমে যেখানে একটা killed pod সহজে restart করা যায়।

যে ভুলগুলো সবাই করে

“Page fault মানেই কিছু একটা ভুল হয়েছে — যত কম fault, তত ভালো প্রোগ্রাম।”

সম্পূর্ণ ভুল একটা সাধারণীকরণ। Minor fault demand paging আর COW-র স্বাভাবিক, ইচ্ছাকৃত অংশ — একটা প্রোগ্রাম চালু হওয়ার সময় শত শত minor fault ঘটা সম্পূর্ণ প্রত্যাশিত, আর সেগুলো এড়ানোর চেষ্টা করাই বরং ক্ষতিকর (যেমন পুরো বাইনারি আগেভাগে touch করে ফেলা, যা এই লেসনের উদাহরণে ~১০ গুণ বেশি সময় নিত)। যেটা আসলেই সমস্যা, সেটা major fault — কারণ সেখানেই disk I/O লুকানো, আর সেটাও পরিমিত হলে স্বাভাবিক (প্রথমবার একটা ফাইল পড়া)। min_flt/maj_flt আলাদা করে না দেখলে “fault সংখ্যা বেশি” একটা অর্থহীন সংকেত।

“vm.swappiness=0 করলে swap সম্পূর্ণ বন্ধ হয়ে যায়।”

প্রায়-সত্যি, কিন্তু নির্ভরযোগ্য গ্যারান্টি না। Linux 3.5 (২০১২)-এর আগে swappiness=0 মানে সত্যিই ছিল “কখনো anonymous page swap করবে না”। তারপর থেকে আচরণ বদলেছে — swappiness=0 মানে kernel normal reclaim চাপে anonymous page swap এড়িয়ে চলবে (file-backed page আগে reclaim করবে), কিন্তু যদি সিস্টেম সত্যিকারের memory চাপে পড়ে আর file-backed page যথেষ্ট না হয়, kernel তবুও anonymous page swap করতে পারে, সম্পূর্ণ OOM-kill এড়াতে। সম্পূর্ণভাবে swap বন্ধ করতে হলে swapoff -a বা কোনো swap device-ই কনফিগার না করা দরকার — swappiness শুধু একটা প্রাধান্য, একটা নিশ্চয়তা না।

“fork() ধীর, কারণ পুরো process address space কপি করতে হয়।”

এই লেসনের hood সেকশন ঠিক এই ভুলটাই ভাঙে। fork() কোনো page data কপি করে না — শুধু page table entry-গুলো iterate করে R/W বিট শূন্য করা আর refcount বাড়ানো, যা page-এর সংখ্যার সমানুপাতিক (হাজার হাজার entry-র জন্যও মাইক্রোসেকেন্ডের ব্যাপার), data-র আকারের সমানুপাতিক না। আসল কপি — যদি আদৌ ঘটে — ঘটে পরে, ছড়িয়ে ছড়িয়ে, শুধু সেসব page-এর জন্য যেগুলো সত্যিই লেখা হয়। একটা ৮ GB heap-ওয়ালা process যদি fork()-এর পর মাত্র ১০০টা page লেখে, মোট কপি হবে ৪০০ KB, ৮ GB না।

“LRU-জাতীয় page replacement সবসময় optimal, কারণ 'সাম্প্রতিক ব্যবহার ভবিষ্যতের ভালো ইঙ্গিত' যুক্তিটা স্বতঃসিদ্ধ শোনায়।”

mathematics/proof-techniques লেসনের counterexample (cache আকার ২, sequence A,B,C,A,B,C,...) এই দাবি সরাসরি খণ্ডন করে — LRU সেখানে ১০০% miss দেয়, যেখানে একটা ভিন্ন, non-LRU policy দিত ৬৬% hit। LRU optimal না — এটা একটা প্রমাণিত মিথ্যা দাবি, “বাস্তব workload-এ LRU সাধারণত ভালো কাজ করে” একটা সম্পূর্ণ ভিন্ন, অভিজ্ঞতালব্ধ দাবি। Linux নিজেও exact LRU রাখে না (active/inactive list একটা approximation) — কারণ exact LRU maintain করার খরচও উল্লেখযোগ্য, শুধু তাত্ত্বিক optimality-র অভাবই একমাত্র সীমাবদ্ধতা না।

বুঝেছেন কি না দেখুন

একটা প্রোগ্রাম একটা ঠিকানায় write access করে যেখানে PTE বলছে P=1 (frame আছে) কিন্তু R/W=0, আর সেই VMA-র permission VM_WRITE সেট করা (অর্থাৎ VMA নিজে writable)। এই fault কোন শাখায় যাবে, আর সেটা minor না major হবে তা কিসের উপর নির্ভর করে?

প্রয়োগ

এই সিগনেচার — P=1 (page RAM-এ আছে) কিন্তু R/W=0, অথচ VMA writable — ঠিক copy-on-write-এর প্যাটার্ন (concept সেকশনের সিদ্ধান্ত-বৃক্ষের ধাপ ৩)। যদি এটা শুধু “না, permission নেই” হতো (VMA নিজেই non-writable), সেটা সরাসরি SIGSEGV হতো (ধাপ ২)। কিন্তু VMA writable হওয়ায় handler সন্দেহ করে এটা COW, আর refcount চেক করে:

Refcount	কাজ	Fault-এর ধরন
> ১ (page shared, অন্তত আরেকজন এখনো ব্যবহার করছে)	নতুন frame বরাদ্দ, পুরনো থেকে কপি, PTE আপডেট	minor — কোনো disk I/O না, শুধু RAM-এ RAM-এ কপি
== ১ (শুধু এই process-এর দখলে)	শুধু R/W=1 করে দেওয়া, কোনো কপি না	minor, আরও সস্তা — এমনকি copy-ও লাগে না

দুইটা ক্ষেত্রেই এটা minor fault — disk কখনো ছোঁয়া হয় না, কারণ frame ইতিমধ্যে RAM-এ আছে (P=1)। “COW fault” আর “swap fault” গুলিয়ে ফেলা একটা সাধারণ ভুল — swap fault-এ PTE-তে P=0 আর একটা swap entry থাকে (ধাপ ৫), সেটাই সত্যিকারের major fault-প্রার্থী।

fork()-এর পর copy-on-write-কে “একটা লাজি (lazy) evaluation কৌশল” বলা হয়। এই তুলনাটা ঠিক কোন অর্থে সত্যি, আর কোথায় এই তুলনার সীমা?

যুক্তি

তুলনাটা যেভাবে সত্যি: Lazy evaluation-এর কেন্দ্রীয় ধারণা — একটা কাজ (এখানে: memory copy) তার প্রয়োজন নিশ্চিত না হওয়া পর্যন্ত পিছিয়ে দেওয়া। fork() জানে না child বা parent আদৌ কোনো page লিখবে কিনা, বা লিখলেও কোনগুলো। তাই সে কোনো page কপি করে না সাথে সাথে — শুধু একটা “প্রতিশ্রুতি” রেখে দেয় (R/W=0 + COW ফ্ল্যাগ), আর প্রকৃত কাজটা (copy) পিছিয়ে দেয় ঠিক সেই মুহূর্ত পর্যন্ত যখন write-এর মাধ্যমে প্রমাণিত হয় এটা সত্যিই দরকার। যেসব page কখনো লেখা হয় না, তাদের জন্য কপি কখনোই ঘটে না — অব্যবহৃত কাজ সম্পূর্ণ এড়ানো, lazy evaluation-এর ঠিক এই সুবিধাটাই।

সীমা কোথায়: Programming-languages-এর lazy evaluation (যেমন Haskell-এর thunk) সাধারণত একটা single-threaded, deterministic মূল্যায়ন-ক্রম নিয়ে কাজ করে — একটা thunk একবারই force হয়, ফলাফল cache হয়ে যায়। COW-তে “force”-টা হার্ডওয়্যার ট্রিগার করা একটা asynchronous event (একটা page fault, যেকোনো সময় ঘটতে পারে, যেকোনো thread-এ), আর এর সাথে সরাসরি concurrency-র জটিলতা জড়িত — দুইটা thread একসাথে একই COW page-এ লিখলে race তৈরি হতে পারে, যা kernel-কে PTE-level লকিং দিয়ে সামলাতে হয় (এই লেসনের BuildIt-এর naive demo-তে ঠিক এই ধরনের race অনুপস্থিত, কারণ সেটা single-threaded)।

Level 5-এর সংযোগ: compilers module-এ lazy evaluation-এর thunk-ভিত্তিক বাস্তবায়ন বিস্তারিত দেখবেন — সেখানে “memory-তে deferred computation” ধারণাটা ভাষার স্তরে, এখানে হার্ডওয়্যার/OS-এর স্তরে, কিন্তু মূল trade-off (deferred cost বনাম bookkeeping overhead) অভিন্ন।

আপনি একটা database সার্ভার চালাচ্ছেন যেখানে buffer pool (RAM-এ cached table data, anonymous-এর মতোই আচরণ করে কারণ dirty page-গুলো নিজস্ব write-back logic ব্যবহার করে) আর OS-এর file-system page cache — দুইটাই একই RAM-এর জন্য প্রতিযোগিতা করছে। vm.swappiness কোন দিকে সেট করবেন, আর কেন?

ডিজাইন

এখানে মূল প্রশ্ন — memory চাপে পড়লে kernel কাকে আগে বাদ দেবে: database-এর নিজের buffer pool page (anonymous, কারণ database engine সাধারণত নিজের memory malloc/anonymous mmap দিয়ে ব্যবস্থাপনা করে), না কি OS-এর file page cache (file-backed)?

স্বল্প swappiness (যেমন ১-১০) বেছে নেওয়া উচিত, কারণ:

১. Database engine-এর নিজের buffer pool-এ ইতিমধ্যে একটা সুচিন্তিত eviction policy আছে (প্রায়ই LRU-K বা clock-sweep-এর একটা variant, database-এর query pattern জেনেই ডিজাইন করা) — kernel-এর generic active/inactive approximation তার চেয়ে খারাপ সিদ্ধান্ত নেবে, কারণ সে query pattern জানে না।

২. যদি kernel buffer pool page swap করে বের করে দেয়, database-এর কাছে সেই fact অদৃশ্য থাকে — সে ভাবে page এখনো RAM-এ আছে, কিন্তু পরের access-এ একটা অপ্রত্যাশিত major fault হয়। এই latency spike database-এর নিজের query planner-এর হিসাবের বাইরে, তাই debug করা কঠিন।

৩. File-backed page cache (যেমন WAL/log ফাইলের সাম্প্রতিক অংশ, বা কম-ব্যবহৃত auxiliary ফাইল) বাদ দেওয়া সস্তা এবং নিরাপদ — দরকার হলে আবার disk থেকে পড়া যায়, আর সেই read-টাও কম গুরুত্বপূর্ণ path-এ ঘটে।

বিকল্প	ঝুঁকি
উচ্চ swappiness	buffer pool page swap হয়ে যায়, database-এর নিজের eviction logic-এর সিদ্ধান্ত OS উল্টে দেয় — অপ্রত্যাশিত latency spike
নিম্ন swappiness	file cache আগে বাদ যায়, buffer pool RAM-এ যতটা সম্ভব থাকে — database নিজে ভবিষ্যদ্বাণীযোগ্যভাবে নিয়ন্ত্রণ রাখে

বাস্তব উদাহরণ: PostgreSQL আর MySQL-এর documentation উভয়েই production ডিপ্লয়মেন্টে vm.swappiness=1 (বা কাছাকাছি) সুপারিশ করে, ঠিক এই যুক্তিতে। কিছু ডিপ্লয়মেন্ট আরও এক ধাপ এগিয়ে mlock()/mlockall() দিয়ে buffer pool-কে সম্পূর্ণভাবে swap-অযোগ্য করে দেয়, যদি latency predictability সবচেয়ে গুরুত্বপূর্ণ হয়। Level 11-এর performance module এই ধরনের “OS আর application-এর মধ্যে caching সিদ্ধান্তের দ্বন্দ্ব” আরও সাধারণভাবে (double caching, buffer bloat) দেখাবে।

একটা প্রোগ্রাম রান-টাইমে ৫০,০০০টা page fault ঘটায়, তার মধ্যে ৪৮,০০০টা minor (গড় ১.৫ μs) আর ২,০০০টা major (গড় ৩০০ μs, দ্রুত NVMe SSD)। মোট fault-জনিত সময় কত? আর যদি সেই সিস্টেমে বদলে একটা ঘূর্ণায়মান HDD থাকত (major fault গড়ে ৮ ms), মোট সময় কেমন বদলে যেত?

প্রয়োগ

NVMe-তে:

$T_{\text{minor}} = 48{,}000 \times 1.5\,\mu s = 72{,}000\,\mu s = 72\,\text{ms}$ $T_{\text{major}} = 2{,}000 \times 300\,\mu s = 600{,}000\,\mu s = 600\,\text{ms}$ $T_{\text{মোট}} = 72 + 600 = 672\,\text{ms}$

মাত্র ৪% fault (২,০০০/৫০,০০০) হওয়া সত্ত্বেও major fault মোট সময়ের প্রায় ৮৯% দখল করে নেয় (৬০০ ÷ ৬৭২)।

HDD-তে (major fault ৮ ms):

$T_{\text{major, HDD}} = 2{,}000 \times 8\,\text{ms} = 16{,}000\,\text{ms} = 16\,\text{সেকেন্ড}$ $T_{\text{মোট, HDD}} = 0.072 + 16 = 16.07\,\text{সেকেন্ড}$

Storage	Major fault-এর মোট সময়	Total	Major-র অংশ
NVMe SSD	৬০০ ms	৬৭২ ms	৮৯%
ঘূর্ণায়মান HDD	১৬,০০০ ms	১৬,০৭২ ms	৯৯.৬%

পার্যবেক্ষণ: NVMe থেকে HDD-তে গেলে মোট সময় প্রায় ২৪ গুণ বেড়ে যায় — অথচ minor fault সংখ্যা, program logic, সব অপরিবর্তিত। শুধু storage-এর ধরন বদলে গেছে। এটাই সেই একই “miss rate নগণ্য কিন্তু miss-এর খরচ প্রবল” প্যাটার্ন যা গত লেসনের AMAT হিসাবে দেখা গিয়েছিল — শুধু এবার স্কেল μs-cycle-এর বদলে ms-সেকেন্ড।

ব্যবহারিক next step: major fault-প্রধান একটা workload-এ প্রথম প্রশ্ন হওয়া উচিত — এই ২,০০০ major fault কি এড়ানো যেত (readahead, prefetching, MAP_POPULATE, বড় RAM দিয়ে working set পুরোপুরি cache-এ রাখা)? Level 11-এর performance module এই ধরনের I/O-bound bottleneck শনাক্তকরণ (iostat, blktrace) হাতে-কলমে দেখাবে।

একটা Kubernetes cluster-এ একটা pod ধীরে ধীরে তার memory request-এর কাছাকাছি চলে যাচ্ছে, আর node-টা thrashing শুরু করেছে (এই লেসনের experiment-এর cliff-এর মতো)। আপনি cluster-অপারেটর — কী কী সিগনাল দেখে thrashing শনাক্ত করবেন, আর দুইটা সম্ভাব্য প্রতিক্রিয়া (OOM kill দেওয়া বনাম আরও RAM দেওয়া) — কোনটা কখন উপযুক্ত?

ডিজাইন

শনাক্তকরণ সিগনাল:

১. pgmajfault/সেকেন্ড হঠাৎ বেড়ে যাওয়া (এই লেসনের experiment-এর cgroup memory.stat-এর মতো) — সবচেয়ে সরাসরি সংকেত, কারণ থ্র্যাশিং মানেই বারবার major fault।

২. CPU utilization কমে যাওয়া অথচ latency/response-time বেড়ে যাওয়া — পাল্টা-স্বজ্ঞাত মনে হতে পারে, কিন্তু thrashing-এ CPU বেশিরভাগ সময় I/O wait-এ কাটায় (iowait metric বাড়ে), প্রকৃত কাজ কম হয়।

৩. vmstat-এর si/so (swap in/out) কলাম ক্রমাগত non-zero, বিশেষত so (swap-out) উচ্চ — মানে RAM চাপে ক্রমাগত anonymous page swap হচ্ছে।

দুইটা প্রতিক্রিয়ার তুলনা:

	OOM kill (বা cgroup memory.max দিয়ে হার্ড সীমা)	আরও RAM দেওয়া (vertical scale)
গতি	তাৎক্ষণিক — pod মারা যায়, restart হয়	ধীর — নতুন node/resize লাগতে পারে
ফলাফলের নির্ধারকতা	নির্ধারক ব্যর্থতা — orchestrator জানে ঠিক কী ঘটল	সমস্যা resolve হয় যদি অনুমান সঠিক হয়, নাহলে শুধু cliff পিছিয়ে যায়
কখন উপযুক্ত	working set সত্যিই RAM-এর সীমার বাইরে চলে গেছে (memory leak, বা প্রত্যাশার চেয়ে বড় dataset) — thrashing চালিয়ে যাওয়া শুধু latency নষ্ট করে, কোনো লাভ নেই	সাময়িক spike (batch job, cache warm-up) যেখানে working set প্রকৃতপক্ষে সহনীয় সীমার কাছাকাছি এবং সাময়িক

মূল সিদ্ধান্ত-নীতি: thrashing অবস্থায় সিস্টেম প্রায় কোনো কাজই করছে না (এই লেসনের experiment-এ throughput ৩০+ গুণ কমেছিল) — তাই “থ্র্যাশিং চলতে দেওয়া” প্রায় কখনোই সঠিক উত্তর না। দ্রুত, নির্ধারক ব্যর্থতা (OOM kill, pod restart) সাধারণত অনির্ধারিত ধীরগতির চেয়ে ভালো, বিশেষত যখন orchestrator (Kubernetes) স্বয়ংক্রিয়ভাবে restart/reschedule করতে পারে। memory.max (hard limit) তাই প্রায়ই ইচ্ছাকৃতভাবে thrashing-কে অসম্ভব করে দিতে ব্যবহৃত হয় — সীমা ছাড়ালেই সাথে সাথে OOM kill, ধীরে ধীরে thrashing-এ পতিত হওয়ার বদলে।

Level 9 আর 12-এর সংযোগ: এই “fail fast বনাম degrade gracefully” সিদ্ধান্তটা distributed-systems-এর একটা কেন্দ্রীয় থিম (circuit breaker, load shedding) — thrashing আসলে single-machine memory-র একটা মিনি-সংস্করণ সেই একই সমস্যার। Level 12-এর cloud module autoscaling policy-তে ঠিক এই trade-off (reactive scale-up বনাম hard limit + fast restart) আরও বিস্তারিত দেখাবে।

এরপর কী

পরের লেসন — malloc আসলে কী করে

এই লেসনে আমরা দেখেছি কীভাবে একটা fault OS-কে সিদ্ধান্ত নেওয়ার সুযোগ দেয় — নতুন frame বরাদ্দ, COW কপি, swap থেকে আনা। কিন্তু userspace-এ, একটা প্রোগ্রামার malloc(100) ডাকলে ঠিক কী ঘটে? সেই ১০০ byte কোথা থেকে আসে? একটা char *p = malloc(100)-এর নিচে আসলে কি একটা mmap() কল লুকিয়ে আছে, নাকি brk(), নাকি কিছুই না (শুধু আগে থেকে বরাদ্দ করা একটা বড় অঞ্চলের একটা অংশ)?

পরের লেসনে আমরা এই প্রশ্নের উত্তর খুঁজব — brk/sbrk বনাম mmap (আর glibc-র বিখ্যাত ১২৮ KB MMAP_THRESHOLD), ptmalloc2-র ভেতরের গঠন (chunk, bin, coalescing, arena), আর কেন একটা দীর্ঘ-চলা প্রসেসের RSS free() করার পরেও প্রায় কখনো কমে না — এই লেসনের demand paging-এর গল্পের ঠিক উল্টো দিক, “memory ফেরত দেওয়া” কেন কঠিন। আর একটা ছোট (~৪০ লাইনের) bump allocator লিখব যা brk আর mmap দুইটা পথই সরাসরি দেখায় — সম্পূর্ণ, উৎপাদন-মানের allocator লেখার পূর্ণ প্রজেক্ট আলাদাভাবে অপেক্ষা করছে।