File system-এর ভেতর — allocation, inode, FAT আর free space

১ · ডিস্ক শুধু block-এর সারি — বাকি সব file system-এর হিসাব

পর্ব ৪০-এ দেখেছেন, ডিস্ক (HDD হোক বা SSD) নিজে শুধু বোঝে নম্বর দেওয়া sector-এর লম্বা সারি: “sector ১১৭০৪ পড়ো” বা “sector ৫০০-তে এই ৫১২ byte লেখো”, ব্যস। ফাইলের নাম, ফোল্ডার, আকার, অনুমতি — এসবের কোনো ধারণা ডিস্কের নেই। পর্ব ৪১ আর ৪২-এ আপনি ব্যবহারকারীর চোখে ফাইল আর directory দেখেছেন। এই পর্বে প্রশ্ন উল্টো দিক থেকে: OS কীভাবে ওই সাদামাটা সারির ওপর ফাইলের পুরো জগৎ বানায়?

File system সাধারণত sector একটি একটি করে নয়, কয়েকটি sector মিলিয়ে একটি block (Windows-এর ভাষায় cluster) হিসেবে কাজ করে — আজকাল সাধারণত ৪ KiB, অর্থাৎ ৮টি ৫১২-byte sector. তারপর তাকে চারটি প্রশ্নের উত্তর রাখতে হয়:

1. কোন block কোন ফাইলের, কোন ক্রমে? — allocation (অংশ ৩–৬)।
2. কোন block এখনো খালি? — free-space management (অংশ ৭)।
3. ফাইলের নাম, আকার, মালিক, অনুমতি কোথায়? — inode বা FCB আর directory (অংশ ২; directory-র বিস্তার পর্ব ৪২-এ)।
4. এত কিছু করেও গতি কীভাবে রাখা যায়? — cache, read-ahead, block size (অংশ ৮)।

স্তরে স্তরে নকশা — layered file system

এত কাজ এক টুকরো কোডে লিখলে তা বোঝা, বদলানো আর নতুন ডিভাইসে চালানো কঠিন হতো। তাই পাঠ্যবই (Silberschatz) file system-কে কয়েকটি স্তরে ভাগ করে দেখায় — layered file system. প্রতিটি স্তর শুধু নিচের স্তরের সেবা ব্যবহার করে, আর ওপরের স্তরকে একটু বেশি বিমূর্ত সেবা দেয়:

লাভ: নিচের স্তরগুলো সব file system ভাগ করে নেয় — ext4, FAT বা NTFS যা-ই হোক, “block ১২০৭ পড়ো” একই পথে যায়। দাম: প্রতিটি স্তরে কিছু বাড়তি সময়। বাস্তব kernel এই ভাগ হুবহু মানে না, তবে ভাবনার কাঠামো হিসেবে এটি কাজের; পর্ব ৪২-এর VFS logical স্তরের ওপরে বসে সব file system-কে একই interface দেয়। নিচে একটি read() স্তরগুলো পেরিয়ে নামছে।

n = read(fd, buf, 4096);   /* fd = 3, file offset now 8192 */

/* no file name, no disk, no block number here */

fd 3 -> per-process table -> open-file entry
open-file entry: inode 1442, offset 8192, mode read
(permission was checked once, at open time)
logical block = 8192 / 4096 = 2

inode 1442 (already in memory):
  direct[0] = 1200   direct[1] = 1201
  direct[2] = 1207   <- logical block 2
physical block = 1207

buffer/page cache: (sda2, block 1207)?  -> miss
allocate a 4096-byte buffer
queue request: READ sda2 block 1207

1 block = 8 sectors of 512 B
sector in partition = 1207 x 8 = 9656
partition sda2 starts at LBA 2048
LBA = 2048 + 9656 = 11704, count = 8
-> command to the controller, DMA into buffer

controller reads LBA 11704..11711, DMA -> buffer
interrupt -> driver marks request done
cache keeps block 1207 for next time
copy 4096 bytes to buf, offset = 12288
read() returns 4096

ধাপ ৫-এর LBA, DMA আর interrupt পর্ব ৩৯-এর বিষয়; ধাপ ২-এর open-file table পর্ব ৪১-এর। এই পর্বের মূল জায়গা ধাপ ৩: ফাইলের block ২ ডিস্কের ঠিক কোথায় — সেই হিসাব কীভাবে রাখা হয়।

২ · ডিস্কের ওপর আর মেমরিতে — file system-এর কাঠামো

ডিস্কে যা থাকে (on-disk structures)

একটি volume (একটি partition-এ বানানো একটি file system) ফরম্যাট করার সময়, অর্থাৎ Linux-এ mkfs বা Windows-এ Format চালানোর সময়, ডিস্কে কয়েকটি স্থায়ী কাঠামো লেখা হয়। নাম file system-ভেদে আলাদা, কাজ প্রায় একই:

একটি কথা প্রায়ই অবাক করে: ফাইলের নাম inode-এ থাকে না। নাম থাকে directory-র ভেতরে, “নাম → inode নম্বর” জোড়া হিসেবে। তাই একই inode-এর দুটি নাম (hard link) থাকতে পারে — পর্ব ৪২-এর বিষয়। Inode-এ যা থাকে, তা stat কমান্ড দেখায় (অংশ ৯-এ চালাবেন)। Windows-এর NTFS-এ ব্যাপারটি একটু আলাদা — ফাইলের নাম MFT record-এর একটি attribute হিসেবেও রাখা হয়।

মেমরিতে যা থাকে (in-memory structures)

প্রতিবার ডিস্ক থেকে এসব পড়লে সিস্টেম খুব ধীর হতো, তাই kernel মেমরিতে কয়েকটি কাঠামো রাখে; mount-এর সময় তৈরি হয়, unmount-এ মুছে যায়:

• Mount table: কোন volume কোন directory-তে বসানো (mount), কোন file system-এর ধরন — Linux-এ /proc/mounts এর একটি জানালা।
• Directory-structure cache: সম্প্রতি খোঁজা path-এর অংশ → inode; Linux-এ dentry cache. প্রতিবার /home/rahim/notes.txt খুলতে চারটি directory ডিস্ক থেকে পড়তে হয় না।
• System-wide open-file table: প্রতিটি খোলা ফাইলের জন্য একটি entry — মেমরিতে আনা inode-এর কপি, file offset ইত্যাদি (Linux-এ inode cache আর struct file).
• Per-process open-file table: প্রতিটি প্রসেসের fd → ওপরের table-এর entry. পর্ব ৪১-এ এর পুরো ছবি।
• Buffer cache: সম্প্রতি পড়া বা লেখা block-এর কপি — stepper-এর ধাপ ৪-এ যেখানে প্রথমে খোঁজা হয়েছিল।

নতুন ফাইল তৈরি তাহলে মোটামুটি এই: একটি খালি inode বরাদ্দ, directory-তে “নতুন নাম → এই inode” যোগ, তারপর দুটিই ডিস্কে লেখা। মাঝপথে বিদ্যুৎ গেলে কী হয় — সেই প্রশ্ন পর্ব ৪৪-এর।

৩ · Contiguous allocation — পাশাপাশি সিট

প্রথম আর সবচেয়ে সরল পদ্ধতি: contiguous allocation — প্রতিটি ফাইল ডিস্কের পরপর block-এ থাকে। Directory entry-তে শুধু দুটি সংখ্যা লাগে: শুরুর block আর দৈর্ঘ্য। ধরুন mail ফাইলের শুরু ১৯, দৈর্ঘ্য ৬ — তাহলে সে block ১৯ থেকে ২৪ জুড়ে।

সুবিধা: random access-এ একটি হিসাব আর একটি disk access; sequential পড়াও সবচেয়ে দ্রুত, কারণ হার্ড ডিস্কের মাথা প্রায় নড়ে না। তাই CD/DVD-র ISO 9660-এ ফাইল পরপর sector-এ থাকে — একবার লেখা মাধ্যম, ফাইল আর বাড়বে না।

ঠিক এই দুটি সমস্যা:

• External fragmentation: পর্ব ৩১-এর মেমরির variable partition-এর মতোই। ফাইল তৈরি-মোছার পর খালি জায়গা ছোট ছোট hole-এ ভাগ হয়ে যায়; মোট খালি অনেক হলেও বড় ফাইলের জায়গা হয় না। Hole বাছার নিয়মও একই — first fit, best fit, worst fit. প্রতিকার compaction — ডিস্কে যাকে defragmentation বলে, বড় ডিস্কে ঘণ্টার পর ঘণ্টা লাগতে পারে।
• আকার আগে জানতে হয়: জায়গা কম দিলে পরে বাড়ানো যায় না, বেশি দিলে অপচয়। একটি log ফাইল কত বড় হবে, কে জানে?

Extent — contiguous-এর আধুনিক রূপ

সমাধান হিসেবে অনেক file system একটি মিশ্র নকশা নেয়: ফাইল পুরোটা এক টানা জায়গায় না হয়ে কয়েকটি টানা অংশে থাকতে পারে। প্রতিটি টানা অংশের নাম extent, আর তার বর্ণনা তিনটি সংখ্যা — (ফাইলের কোন block থেকে, ডিস্কের কোন block-এ, কতগুলো)। ফাইল বাড়লে নতুন একটি extent যোগ হয়। ext4, XFS, NTFS (সেখানে নাম “data run”), Btrfs, APFS — আধুনিক প্রায় সব file system extent ব্যবহার করে (অংশ ৫-এর শেষে ext4). Fragmentation পুরো যায় না — extent যত বেশি, ফাইল তত ছড়ানো — তবে অনেক কমে।

৪ · Linked allocation আর FAT — block-এ block-এ চিরকুট

Contiguous-এর দুই সমস্যা — fragmentation আর আগে থেকে আকার জানা — একসাথে মুছে দেয় linked allocation: ফাইলের block ডিস্কের যেকোনো জায়গায় থাকতে পারে, আর প্রতিটি block-এর শেষ কয়েকটি byte-এ লেখা থাকে পরের block-এর নম্বর — একটি linked list. Directory entry-তে শুধু প্রথম (আর সুবিধার জন্য শেষ) block-এর নম্বর। ফাইল বাড়াতে যেকোনো খালি block নিয়ে শেষ block-এর pointer-এ জুড়ে দিলেই হলো; কোনো খালি block কখনো অব্যবহৃত থাকে না, তাই external fragmentation নেই।

দাম তিনটি:

• Random access ধীর: block i-তে পৌঁছাতে আগে block ০ থেকে i−১ পড়ে pointer দেখতে হয় — block i পড়তে i + ১টি disk access (০ থেকে গুনলে)। Sequential পড়ায় এটি সমস্যা নয়।
• Pointer-এর জায়গা: ৫১২-byte block-এ ৪-byte pointer মানে প্রায় ০.৭৮% অপচয়। প্রতিকার: কয়েকটি block মিলিয়ে একটি cluster, প্রতি cluster-এ একটি pointer — ৪ block-এর cluster-এ প্রায় ০.২০%. দাম: বেশি internal fragmentation.
• নির্ভরযোগ্যতা: একটি pointer নষ্ট হলে chain-এর বাকি অংশ হারায়, বা chain অন্য ফাইলের block-এ ঢুকে পড়ে। আংশিক প্রতিকার: doubly linked list, বা প্রতিটি block-এ ফাইলের পরিচয় আর ক্রমিক নম্বর রাখা।

FAT — চিরকুটগুলো এক খাতায় জড়ো করা

১৯৭০-এর দশকের শেষ দিকে Microsoft-এর একটি BASIC-এর জন্য তৈরি আর পরে MS-DOS-এর মাধ্যমে জনপ্রিয় হওয়া FAT (File Allocation Table) linked allocation-এর একটি চতুর রূপ: pointer-গুলো data block-এর ভেতরে না রেখে volume-এর শুরুতে একটি আলাদা টেবিলে রাখা হয়। টেবিলে প্রতিটি cluster-এর জন্য একটি entry; entry i-এর মান = “cluster i-এর পরের cluster কোনটি”. বিশেষ মান: ০ = খালি cluster, একটি “end of chain” (EOC) চিহ্ন = ফাইলের শেষ cluster, আরেকটি চিহ্ন = নষ্ট (bad) cluster. Directory entry-তে থাকে ফাইলের নাম, আকার আর প্রথম cluster-এর নম্বর।

লাভ: FAT ছোট, তাই তার ব্যস্ত অংশ মেমরিতে (cache) রাখা যায়। তখন chain ধরে হাঁটা হয় মেমরিতে, আর ডিস্কে যেতে হয় একবার — আসল data cluster পড়তে। Cache-এ না থাকলে প্রতিটি ধাপে ডিস্কের মাথাকে volume-এর শুরুতে ফিরতে হয়। নির্ভরযোগ্যতার জন্য FAT সাধারণত দুটি কপিতে থাকে। নিচে একটি ১৬ entry-র FAT; cluster ৪ KiB.

Directory-তে দুটি ফাইল: notes.txt (প্রথম cluster ২, আকার ১৩,০০০ byte) আর photo.jpg (প্রথম cluster ৪, আকার ১৫,০০০ byte). FAT-এর প্রথম দুটি entry (০ আর ১) data cluster নয়, তাই নম্বর ২ থেকে শুরু — আসল FAT-এও তা-ই। নিচের stepper-এ notes.txt-এর chain ধরে হাঁটা হচ্ছে।

1 c = dir["notes.txt"].start2 while c != EOC:3     visit(c); c = FAT[c]4 k = 9000 / 4096; hop k times5 f = first FREE; FAT[last] = f

একই কাজ নিচের ছোট প্রোগ্রাম করে — দুটি ফাইলের chain, random access আর append:

// A tiny FAT: entry i says which cluster comes after cluster i.
const FREE = 0, EOC = -1, BAD = -7;   // free, end of chain, bad cluster
const FAT = [null, null, 5, 9, 7, 3, FREE, 8, 12, EOC, FREE, BAD, EOC, FREE, FREE, FREE];
const CLUSTER = 4096;
const dir = [{ name: "notes.txt", start: 2, size: 13000 },   // directory entries
             { name: "photo.jpg", start: 4, size: 15000 }];

function chain(start) {               // follow the FAT from the first cluster
  const out = [];
  for (let c = start; c !== EOC; c = FAT[c]) out.push(c);
  return out;
}
for (const f of dir) {
  const c = chain(f.start);
  console.log(f.name.padEnd(10) + " start " + f.start + ": " + c.join(" -> ") + " -> EOC" +
              "  (" + c.length + " clusters, need " + Math.ceil(f.size / CLUSTER) + ")");
}
// Random access: which cluster holds byte 9000 of notes.txt?
const k = Math.floor(9000 / CLUSTER);
let c = dir[0].start;
for (let i = 0; i < k; i++) c = FAT[c];
console.log("notes.txt byte 9000 -> cluster #" + k + " of the file = cluster " + c + " (" + k + " FAT lookups)");
// Append one cluster to notes.txt: take the first free entry, link it at the end.
const free = FAT.indexOf(FREE), last = chain(dir[0].start).pop();
FAT[last] = free; FAT[free] = EOC;
console.log("append: FAT[" + last + "] = " + free + ", FAT[" + free + "] = EOC");
console.log("notes.txt now: " + chain(dir[0].start).join(" -> ") + " -> EOC");
console.log("free clusters left: " + FAT.filter((v) => v === FREE).length + ", bad: " + FAT.indexOf(BAD));

notes.txt  start 2: 2 -> 5 -> 3 -> 9 -> EOC  (4 clusters, need 4)
photo.jpg  start 4: 4 -> 7 -> 8 -> 12 -> EOC  (4 clusters, need 4)
notes.txt byte 9000 -> cluster #2 of the file = cluster 3 (2 FAT lookups)
append: FAT[9] = 6, FAT[6] = EOC
notes.txt now: 2 -> 5 -> 3 -> 9 -> 6 -> EOC
free clusters left: 4, bad: 11

FAT12, FAT16, FAT32 — নামের সংখ্যা আর হিসাব

নামের সংখ্যাটি FAT-এর প্রতিটি entry-র বিট-সংখ্যা: FAT12-এ ১২ বিট (ফ্লপি ডিস্কের যুগ), FAT16-এ ১৬, FAT32-এ ৩২ বিট — যার মধ্যে আসলে নিচের ২৮টি বিট cluster নম্বর, ওপরের ৪টি সংরক্ষিত। দুটি হিসাব পরীক্ষায় প্রায়ই আসে।

Volume-এর সীমাও আছে: ৫১২-byte sector-এ FAT32 volume তত্ত্বে প্রায় ২ TiB পর্যন্ত হতে পারে, তবে Windows-এর নিজস্ব format টুল দীর্ঘদিন ৩২ GB-এর বড় FAT32 volume বানাত না (সাম্প্রতিক কিছু সংস্করণে তা শিথিল হয়েছে বলে জানা যায়)। এই সীমাগুলোই অংশ ৯-এর exFAT-এর জন্মের কারণ।

৫ · Indexed allocation আর Unix-এর inode

Linked allocation-এ pointer ছড়ানো block-এ block-এ; FAT সব ফাইলের pointer এক টেবিলে রাখে। Indexed allocation মাঝামাঝি পথ নেয়: প্রতিটি ফাইলের নিজের একটি index block, যার i-তম entry = ফাইলের i-তম block-এর ডিস্ক-ঠিকানা। বইয়ের সূচিপত্রের মতো — “অধ্যায় ৩: পৃষ্ঠা ৫৭”। Directory entry-তে শুধু index block-এর ঠিকানা।

• সুবিধা: random access সরাসরি — index[i] দেখে এক read; external fragmentation নেই।
• অসুবিধা: ২০০ byte-এর ফাইলেও একটি পুরো index block. আর বড় ফাইলে এক index block যথেষ্ট নয়: ৪ KiB block-এ ৪-byte pointer ধরে ১০২৪টি entry, অর্থাৎ মাত্র ৪ MiB.

বড় ফাইলের জন্য তিনটি উপায়:

1. Linked scheme: index block-এর শেষ entry পরের index block-এর ঠিকানা — index block-এর linked list.
2. Multilevel index: প্রথম স্তরের index block-এর entry দেখায় দ্বিতীয় স্তরের index block, সেগুলো দেখায় data block — পর্ব ৩৩-এর multilevel page table-এর মতোই। দুই স্তরে ১০২৪ × ১০২৪ = ১০,৪৮,৫৭৬টি data block = ৪ GiB.
3. Combined scheme (Unix inode): ছোট ফাইল দ্রুত, বড় ফাইলও সম্ভব — দুটোই একসাথে।

Unix-এর combined scheme — ১২ + ৩

BSD-র UFS/FFS আর Linux-এর ext2/ext3-এর inode-এ ১৫টি block pointer (সংখ্যাটি নকশাভেদে আলাদা — যেমন পুরোনো Version 7 Unix-এ direct ছিল ১০টি):

• প্রথম ১২টি direct pointer: সরাসরি data block. ৪ KiB block-এ ১২ × ৪ KiB = ৪৮ KiB পর্যন্ত ফাইলের জন্য কোনো বাড়তি block-ই লাগে না — আর বেশিরভাগ ফাইল ছোট।
• ১৩তম: single indirect: একটি index block-এর ঠিকানা, যাতে ১০২৪টি data block-এর ঠিকানা।
• ১৪তম: double indirect: index block-এর index block — ১০২৪ × ১০২৪টি data block.
• ১৫তম: triple indirect: আরও এক স্তর — ১০২৪^৩টি data block.

নিচের calculator প্রতিটি স্তরের অবদান ছাপে, তারপর কয়েকটি offset-এর জন্য বলে কোন স্তর, কোন entry আর কতগুলো disk read (inode মেমরিতে ধরে)। B আর P বদলে নিজের অঙ্ক যাচাই করুন।

// Unix-style inode: 12 direct + single, double, triple indirect pointers.
const B = 4096;                 // block size in bytes
const P = 4;                    // pointer (block number) size in bytes
const n = B / P;                // pointers that fit in one index block
const fmt = (x) => x.toLocaleString("en-US");
const levels = [["direct (12)", 12], ["single", n], ["double", n ** 2], ["triple", n ** 3]];
console.log("block " + B + " B, pointer " + P + " B -> " + n + " pointers per index block");
let total = 0;
for (const [name, blocks] of levels) {
  total += blocks * B;
  console.log("  " + name.padEnd(11) + fmt(blocks).padStart(14) + " blocks = " + fmt(blocks * B).padStart(18) + " B");
}
console.log("  max file size = " + fmt(total) + " B (" + (total / 2 ** 40).toFixed(4) + " TiB)");

function locate(X) {              // which pointer level serves byte offset X?
  let r = Math.floor(X / B);      // logical block number inside the file
  const lb = r;
  for (let lv = 0; lv < 4; lv++) {
    const span = lv === 0 ? 12 : n ** lv;
    if (r < span) {
      const idx = [];             // index used inside each index block, top to bottom
      for (let k = lv - 1; k >= 0; k--) idx.push(Math.floor(r / n ** k) % n);
      const where = lv === 0 ? "direct[" + r + "]" : levels[lv][0] + " [" + idx.join("][") + "]";
      return "offset " + fmt(X) + " -> block " + fmt(lb) + ", " + where + ", disk reads = " + (lv + 1);
    }
    r -= span;
  }
  return "offset " + fmt(X) + " is beyond the maximum file size";
}
for (const X of [20000, 49152, 2000000, 10000000, 5000000000]) console.log(locate(X));

block 4096 B, pointer 4 B -> 1024 pointers per index block
  direct (12)            12 blocks =             49,152 B
  single              1,024 blocks =          4,194,304 B
  double          1,048,576 blocks =      4,294,967,296 B
  triple      1,073,741,824 blocks =  4,398,046,511,104 B
  max file size = 4,402,345,721,856 B (4.0039 TiB)
offset 20,000 -> block 4, direct[4], disk reads = 1
offset 49,152 -> block 12, single [0], disk reads = 2
offset 2,000,000 -> block 488, single [476], disk reads = 2
offset 10,000,000 -> block 2,441, double [1][381], disk reads = 3
offset 5,000,000,000 -> block 1,220,703, triple [0][167][83], disk reads = 4

নিচের stepper তিনটি আলাদা offset-এর জন্য পথটি দেখায় — direct, single indirect আর double indirect. Physical block নম্বরগুলো (১২০৭, ৩৩০০…) উদাহরণের জন্য বানানো; index-এর হিসাব calculator-এর সাথে মেলে।

1 lb = offset / 40962 if lb < 12: read direct[lb]3 lb = lb - 124 if lb < 1024: S = read(single); read S[lb]5 lb = lb - 10246 D = read(double); L = read(D[lb/1024])
     read L[lb % 1024]

বাস্তবে একবার পড়া index block buffer cache-এ থেকে যায়, তাই পরপর block পড়তে সাধারণত শুধু data block-এর read. নকশার শিক্ষা: ছোট ফাইলের খরচ সবচেয়ে কম, বড় ফাইলের বাড়তি খরচ ধীরে (লগারিদমিক হারে) বাড়ে।

ext4-এর extent — pointer-এর বদলে টানা অংশ

১ GiB-এর একটি ফাইল ext3-এ মানে প্রায় ২,৬২,১৪৪টি আলাদা block pointer, আর সেগুলো রাখার আড়াইশোর বেশি index block — যদিও ফাইলটি হয়তো ডিস্কে প্রায় টানা পড়ে আছে। ext4 (Linux ২.৬.২৮, ২০০৮ থেকে স্থিতিশীল) তাই ডিফল্টে extent ব্যবহার করে: inode-এর ৬০ byte-এর pointer-জায়গায় একটি ১২-byte header আর ৪টি extent, প্রতিটি ১২ byte — (ফাইলের শুরুর block, দৈর্ঘ্য, ডিস্কের শুরুর block). একটি সাধারণ extent সর্বোচ্চ ৩২,৭৬৮টি block, ৪ KiB block-এ ১২৮ MiB ঢাকে। চারটির বেশি লাগলে inode-এর জায়গাটি একটি extent tree-র মূল হয়ে যায়, যার নিচের স্তরগুলো আলাদা block-এ — B-tree-র মতো (DSA কোর্সের B-tree পর্ব)। ext4-এ logical block নম্বর ৩২ বিট, তাই ৪ KiB block-এ সর্বোচ্চ ফাইল ২^৩২ × ৪ KiB = ১৬ TiB.

সূক্ষ্ম কথা: ext2/ext3-এর pointer-গণিত ৪ KiB block-এ ৪ TiB দিলেও বাস্তব সীমা সাধারণত ২ TiB বলা হয় — inode-এর আরেকটি ৩২-বিট field (৫১২-byte এককে ব্যবহৃত block) সীমা টানে। পরীক্ষায় প্রশ্নের মডেলেই উত্তর দিন।

৬ · তিন পদ্ধতি পাশাপাশি — একই ফাইল, একই ডিস্ক

একটি ১৬ block-এর ছোট ডিস্ক; block ০, ১, ৩, ৪, ৮ আর ১১ অন্য ফাইলের দখলে। a.txt-এর জন্য ৪টি block দরকার, পরে আরও একটি। নিচের stepper তিন পদ্ধতিতে একই কাজ করে। চিহ্ন: # = অন্যের block, . = খালি, A = a.txt-এর data, I = a.txt-এর index block.

৭ · Free-space management — কোন block খালি?

ফাইল তৈরি বা বড় হলে file system-কে খালি block খুঁজতে হয়, আর মুছলে সেগুলো ফেরত নিতে হয়। এই হিসাব রাখার কাজ free-space management. পাঁচটি পরিচিত পদ্ধতি আছে; প্রথমটি দিয়ে শুরু।

Bit vector (bitmap)

প্রতিটি block-এর জন্য একটি বিট — সব মিলিয়ে একটি লম্বা বিটের সারি, bit vector বা bitmap. এই পর্বে (আর ext4-এ) ১ = ব্যবহৃত, ০ = খালি; Silberschatz-এর পাঠ্যবই উল্টো নিয়ম নেয় (১ = খালি) — প্রশ্নে কোনটি দেওয়া, আগে দেখে নিন।

প্রথম খালি block খোঁজা: CPU একবারে একটি পুরো word (৩২ বা ৬৪ বিট) তুলনা করতে পারে। তাই word ধরে ধরে এগোনো: যে word-এর সব বিট ১ (পুরো ভরা), এক তুলনাতেই বাদ। প্রথম যে word পুরো ভরা নয়, তার ভেতরে প্রথম ০ বিট খোঁজা — অনেক CPU-তে এর জন্য একটি instruction-ই আছে (x86-এর BSF/TZCNT-এর মতো bit-scan). সূত্র:

নিচের allocator একটি ৩২ block-এর bitmap চারটি ৮-বিটের word-এ রাখে (ছোট করে দেখার জন্য), প্রথম খালি block খোঁজে, তারপর first fit-এ কয়েকটি টানা অংশ বরাদ্দ করে আর একটি ফাইল মোছে। প্রতিটি কাজের পর পুরো bitmap ছাপে — বাঁ থেকে block ০।

// Free-space bitmap for 32 blocks, stored as four 8-bit words. Bit 1 = in use, 0 = free.
const words = [0b11111111, 0b11100011, 0b11000011, 0b00011111];
const bit = (b) => (words[b >> 3] >> (7 - (b & 7))) & 1;   // block b: word b/8, bit b%8
const set = (b, v) => { const m = 1 << (7 - (b & 7));
  words[b >> 3] = v ? words[b >> 3] | m : words[b >> 3] & ~m; };
const show = (label) => console.log(label.padEnd(15) +
  words.map((w) => w.toString(2).padStart(8, "0")).join(" "));

function firstFree() {               // skip full words with one compare each
  for (let w = 0; w < words.length; w++) {
    if (words[w] === 0xFF) continue;
    for (let i = 0; i < 8; i++) if (!bit(w * 8 + i)) return [w * 8 + i, w];
  }
  return [-1, -1];
}
function allocContig(len) {          // first run of len free blocks (first fit)
  for (let s = 0, run = 0; s < 32; s++) {
    run = bit(s) ? 0 : run + 1;
    if (run === len) { for (let b = s - len + 1; b <= s; b++) set(b, 1); return s - len + 1; }
  }
  return -1;
}
show("start");
const [b, full] = firstFree();
console.log("first free = " + b + " = 8 x " + full + " full words + bit " + (b % 8));
set(b, 1); show("alloc 1 -> " + b);
for (const len of [3, 3, 2]) show("alloc " + len + " -> " + allocContig(len));
set(9, 0); set(10, 0); show("free 9,10");
show("alloc 3 -> " + allocContig(3));
const freeList = [];
for (let k = 0; k < 32; k++) if (!bit(k)) freeList.push(k);
console.log("free blocks: " + freeList.join(",") + " (" + freeList.length + " free, none 3 in a row)");

start          11111111 11100011 11000011 00011111
first free = 11 = 8 x 1 full words + bit 3
alloc 1 -> 11  11111111 11110011 11000011 00011111
alloc 3 -> 18  11111111 11110011 11111011 00011111
alloc 3 -> 24  11111111 11110011 11111011 11111111
alloc 2 -> 12  11111111 11111111 11111011 11111111
free 9,10      11111111 10011111 11111011 11111111
alloc 3 -> -1  11111111 10011111 11111011 11111111
free blocks: 9,10,21 (3 free, none 3 in a row)

Bitmap সরল, আর পাশাপাশি খালি block খোঁজা সহজ; শর্ত হলো দ্রুততার জন্য এটি মেমরিতে রাখতে হয় — বড় storage array-তে কয়েক GB. তাই ext4 bitmap block group ধরে ধরে আনে (অংশ ৯)।

বাকি চারটি পদ্ধতি

TRIM — SSD-কে জানানো যে block খালি

ফাইল মুছলে file system শুধু bitmap-এ বিট ০ করে; পুরোনো ডেটা ডিস্কে পড়ে থাকে। হার্ড ডিস্কে তাতে ক্ষতি নেই। কিন্তু SSD-র flash-এ ওপরে লেখা যায় না, আগে বড় erase block মুছতে হয় (পর্ব ৪০); SSD না জানলে garbage collection-এর সময় মৃত ডেটাকেও “জীবিত” ভেবে কপি করে — ধীর হয়, flash দ্রুত ক্ষয় হয়। TRIM (SATA-র কমান্ড; NVMe-তে Deallocate, SCSI-তে UNMAP) দিয়ে file system SSD-কে জানায়, “এই block-গুলো খালি”. Linux-এ fstrim কমান্ড বা discard mount option (অনেক distro সপ্তাহে একবার fstrim.timer চালায়); Windows-এ “Optimize Drives” নিয়মিত retrim করে।

৮ · দক্ষতা আর গতি — block size, cache আর লেখার নীতি

Block size-এর আপস — একটি হিসাব

বড় block মানে প্রতিটি disk access-এ বেশি ডেটা — হার্ড ডিস্কে seek আর ঘোরার অপেক্ষা (ধরুন ১২ ms) প্রায় একই থাকে, তাই throughput বাড়ে। কিন্তু প্রতিটি ফাইলের শেষ block গড়ে অর্ধেক খালি থাকে — internal fragmentation. ধরুন একটি ডিস্ক: positioning ১২ ms, transfer ১০০ MB/s (১ MB = ১০^৬ byte), আর প্রতিটি block আলাদা জায়গায় (সবচেয়ে খারাপ ক্ষেত্র)। আর আটটি ফাইল, আকার ৩০০; ১,৫০০; ২,৫০০; ৫,০০০; ৯,০০০; ৪০,০০০; ৭০,০০০ আর ১০,০০,০০০ byte (মোট ১১,২৮,৩০০ byte). একটি scratch script-এ হিসাব:

হিসাবের ধাপ: এক block-এর সময় = ১২ ms + block size ÷ ১০০ MB/s; যেমন ৪ KiB-এ ১২ + ৪০৯৬ ÷ ১০^৮ s = ১২ + ০.০৪১ = ১২.০৪১ ms; কার্যকর গতি = ৪০৯৬ byte ÷ ১২.০৪১ ms ≈ ০.৩৪০ MB/s. অপচয় = (প্রতিটি ফাইলের ⌈আকার ÷ block⌉ × block) − আসল আকার, সবগুলোর যোগফল; শতাংশটি মোট বরাদ্দ জায়গার। ছোট block জায়গা বাঁচায়, বড় block সময় বাঁচায়। আজকের ৪ KiB ডিফল্ট এই আপসের ফল, আর page-এর আকারের (পর্ব ৩২) সাথে মেলে। SSD-তে positioning প্রায় নেই, তাই ছোট block-এর শাস্তি কম।

Unified buffer cache বনাম double caching

পুরোনো অনেক Unix-এ দুটি আলাদা cache ছিল: read()/write()-এর জন্য block-ভিত্তিক buffer cache, আর mmap (পর্ব ৩৫) করা ফাইলের জন্য virtual memory-র page cache. একটি ফাইল দুই পথেই ব্যবহৃত হলে একই ডেটা RAM-এ দুবার — double caching: RAM-এর অপচয়, CPU-র কপির খরচ, আর দুই কপির মধ্যে অমিলের ঝুঁকি। সমাধান unified buffer cache: দুই পথই একই page cache ব্যবহার করে। Solaris, Linux (২.৪-এর সময় থেকে মোটামুটি) আর Windows এমন একীভূত নকশা নেয়। Linux-এ free কমান্ডের “buff/cache” কলাম এর আকার দেখায় (পর্ব ৩৮)।

Read-ahead আর free-behind

বেশিরভাগ ফাইল শুরু থেকে শেষ পর্যন্ত পড়া হয় (sequential). File system তা টের পেলে দুটি কৌশল নেয়:

• Read-ahead: অনুরোধ করা block-এর সাথে পরের কয়েকটিও এক অনুরোধে পড়ে রাখা — হার্ড ডিস্কে seek একবার, বাকিটা টানা transfer. পর্ব ৪-এর prefetching-এর file system রূপ; Linux পড়ার ধরন দেখে জানালা বড়-ছোট করে।
• Free-behind: পরের page চাওয়া হলেই আগের page-কে cache থেকে সরানোর প্রার্থী করা — sequential পড়ায় সেটি আর লাগবে না, অথচ LRU (পর্ব ৩৬) তাকেই সবচেয়ে মূল্যবান ভাবে।

Synchronous বনাম asynchronous লেখা

write() সাধারণত asynchronous: ডেটা page cache-এ কপি হয়, page dirty চিহ্নিত হয়, আর system call সঙ্গে সঙ্গে ফেরে; ডিস্কে আসল লেখা পরে writeback-এ, দলবেঁধে আর ভালো ক্রমে। দাম: বিদ্যুৎ চলে গেলে শেষ কয়েক সেকেন্ডের লেখা হারাতে পারে। Synchronous লেখা — O_SYNC/O_DSYNC দিয়ে খোলা ফাইল, বা লেখার পর fsync(fd) — ডেটা ডিস্কে (ডিভাইসের নিজের cache পেরিয়ে) না পৌঁছানো পর্যন্ত ফেরে না। Database-এর commit আর পর্ব ৪৪-এর journal-এর জন্য এটি দরকার।

৯ · বাস্তবের file system — ext4, FAT32, NTFS আর exFAT

ext4 — block group, bitmap আর extent

Linux-এর সবচেয়ে প্রচলিত file system ext4 পুরো volume-কে সমান আকারের block group-এ ভাগ করে। ৪ KiB block-এ একটি block bitmap (একটিমাত্র block) ৪০৯৬ × ৮ = ৩২,৭৬৮টি block-এর হিসাব রাখতে পারে, তাই প্রতিটি group সাধারণত ৩২,৭৬৮ block = ১২৮ MiB. প্রতিটি group-এ:

• কিছু group-এ superblock আর group descriptor-এর ব্যাকআপ কপি;
• একটি block bitmap আর একটি inode bitmap — কোন data block আর কোন inode খালি;
• ওই group-এর inode table (ডিফল্টে প্রতিটি inode ২৫৬ byte);
• বাকি জায়গায় data block.

লক্ষ্য locality: ফাইলের inode আর data একই group-এ, যাতে হার্ড ডিস্কের মাথা কম নড়ে — BSD-র Fast File System (১৯৮৪)-এর cylinder group-এর উত্তরসূরি; “flex_bg” কয়েকটি group-এর metadata একসাথে রাখে। Inode-এর মোট সংখ্যা mkfs-এর সময় ঠিক হয়, তাই জায়গা থাকতেও inode ফুরিয়ে “No space left on device” আসতে পারে। নিচের কমান্ডগুলো এই container-এর file system দেখায়:

echo "== the file system that holds this directory"
stat -f .
echo
echo "== inode usage (df -i)"
df -i .
echo
printf 'hi\n' > tiny.txt                         # 3 bytes
head -c 10000 /dev/zero > ten_k.bin              # 10,000 bytes
truncate -s 1M sparse.bin                        # size 1 MiB, nothing written yet
printf 'x' | dd of=sparse.bin bs=1 seek=900000 conv=notrunc status=none
echo "== per-file: size vs. blocks really used (%b counts 512-byte units)"
stat -c '%n: size=%s B, %b blocks of %B B' tiny.txt ten_k.bin sparse.bin

== the file system that holds this directory
  File: "."
    ID: b9552bbea56a87eb Namelen: 255     Type: ext2/ext3
Block size: 4096       Fundamental block size: 4096
Blocks: Total: 14599048   Free: 3472925    Available: 2831092
Inodes: Total: 15551872   Free: 15220960

== inode usage (df -i)
Filesystem       Inodes  IUsed    IFree IUse% Mounted on
/dev/vda2      15551872 330912 15220960    3% /home/wandbox

== per-file: size vs. blocks really used (%b counts 512-byte units)
tiny.txt: size=3 B, 8 blocks of 512 B
ten_k.bin: size=10000 B, 24 blocks of 512 B
sparse.bin: size=1048576 B, 8 blocks of 512 B

FAT32 — সরল, সর্বজনীন, কিন্তু পুরোনো

অংশ ৪-এর পুরো ছবিটিই FAT32: সামনে reserved অংশ (boot sector, FSInfo), তারপর FAT-এর দুটি কপি, তারপর data অংশ, যেখানে root directory-ও একটি সাধারণ cluster chain. কোনো অনুমতি (owner, rwx) নেই, journaling নেই, ফাইল সর্বোচ্চ ৪ GiB − ১ byte. তবু প্রায় সব OS আর যন্ত্র এটি পড়তে পারে; UEFI-র EFI system partition (পর্ব ৭) এ কারণেই FAT32-এ।

NTFS — সবকিছুই একটি ফাইল

Windows NT ৩.১ (১৯৯৩)-এর সাথে আসা NTFS-এর কেন্দ্র MFT (Master File Table) — নিজেও একটি ফাইল, যার প্রতিটি record (সাধারণত ১ KiB) একটি ফাইল বা directory-র বর্ণনা: নাম, সময়, নিরাপত্তা, আর ডেটা — সব “attribute” হিসেবে। ছোট ফাইলের ডেটা এত ছোট যে MFT record-এর ভেতরেই ধরে যায় — একে resident ডেটা বলে, তখন আলাদা কোনো cluster লাগে না (কয়েকশো byte পর্যন্ত; সঠিক সীমা record-এর বাকি attribute-এর ওপর নির্ভর করে)। বড় ফাইলে ডেটা non-resident: record-এ থাকে “data run”-এর তালিকা — অর্থাৎ extent. Free space একটি bitmap-এ, যেটিও একটি ফাইল ($Bitmap); journal থাকে $LogFile-এ (পর্ব ৪৪)।

exFAT — flash-এর জন্য বড় FAT

বড় SD card আর pen drive-এ FAT32-এর ৪ GiB সীমা অসহনীয় হয়ে উঠছিল, অথচ NTFS ছোট যন্ত্রের জন্য ভারী। Microsoft ২০০৬ সালে আনে exFAT: ফাইলের আকার ৬৪-বিট (৪ GiB সীমা নেই), খালি জায়গার জন্য FAT-এর বদলে একটি আলাদা allocation bitmap, আর একটি চতুর বিকল্প — ফাইল পুরো টানা থাকলে directory entry-তে একটি flag দিয়ে বলা যায় “FAT chain দেখার দরকার নেই”, তখন ফাইলটি কার্যত contiguous allocation. SD Association বড় (SDXC) card-এর জন্য exFAT-কে মানদণ্ড করেছে। Microsoft ২০১৯ সালে এর specification প্রকাশ করার পর Linux kernel-এ (৫.৪-এ staging-এ, ৫.৭ থেকে মূল অংশে) exFAT driver এসেছে।

১০ · AI-এর যুগে file system-এর হিসাব

AI এই অঙ্কগুলো মুহূর্তে করে দেয়, আর প্রায়ই সূক্ষ্মভাবে ভুল করে:

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

• n = B ÷ p নিজে বের করেছি, আর প্রতিটি স্তরের অবদান আলাদা করে মিলিয়েছি
• Disk read গোনায় প্রশ্নের অনুমান (inode, index block cache-এ কি না) মেনেছি
• একক (KB বনাম KiB) উত্তরে স্পষ্ট লিখেছি
• AI-এর দেওয়া প্রোগ্রামকে আগে জানা উত্তর দিয়ে পরীক্ষা করেছি (৪ KiB, ৪ byte → 4,402,345,721,856 byte; offset ৪৯,১৫২ → single [0])
• কমান্ড কোন OS-এর (Linux, macOS, Windows) মিলিয়েছি; sudo, chmod 777, fsck, mkfs-এর মতো কমান্ড না বুঝে বা mount করা volume-এ চালাইনি
• বাস্তব file system-এর সীমা (ext4, NTFS, exFAT) ডকুমেন্টেশনে মিলিয়েছি — পাঠ্যবইয়ের মডেলের সংখ্যা বাস্তবের সাথে না-ও মিলতে পারে