Contiguous allocation — fit কৌশল, fragmentation আর buddy system

১ · এক টুকরো টানা জায়গা — contiguous allocation কী

পর্ব ৩০-এ দেখেছেন, প্রতিটি প্রসেস logical address দিয়ে কাজ করে, আর MMU সেটিকে physical ঠিকানায় অনুবাদ করে। সবচেয়ে সরল অনুবাদ-ব্যবস্থায় MMU-তে থাকে মাত্র দুটি register: একটি base (বা relocation register), যা যোগ হয়, আর একটি limit, যার বাইরে গেলে trap. এই ব্যবস্থায় একটি শর্ত আপনা থেকেই চলে আসে — প্রসেসের পুরো মেমরি physical RAM-এ এক টুকরো, টানা হতে হবে, কারণ base + offset একটি সরল রেখায় চলে।

এভাবে মেমরি ভাগ করার নামই contiguous allocation. সাধারণত মেমরির এক প্রান্তে (অনেক সিস্টেমে নিচের দিকে, যেখানে interrupt vector থাকে) OS নিজে বসে, বাকিটা user প্রসেসদের। নতুন প্রসেস এলে OS খোঁজে: কোথায় এর পুরো আকারের একটি খালি টানা জায়গা আছে? প্রসেস শেষ হলে তার জায়গা খালি হয়, আর পাশের খালি জায়গার সাথে মিশে বড় খালি জায়গা হতে পারে।

আজকের Linux, Windows বা macOS সাধারণ প্রসেসকে এভাবে মেমরি দেয় না — তারা paging ব্যবহার করে (পর্ব ৩২), যেখানে প্রসেসের মেমরি RAM-এর যেকোনো জায়গায় ছড়ানো ছোট ছোট frame-এ থাকতে পারে। তাহলে এই পর্ব কেন? চারটি কারণে:

• Paging কেন এল, তা বোঝার জন্য। External fragmentation-এর যন্ত্রণাই paging-এর মূল প্রেরণা।
• একই সমস্যা সবখানে। একটি প্রোগ্রামের ভেতরে malloc তার heap-এ ঠিক এই কাজ করে; kernel physical page-গুলো ভাগ করে buddy system দিয়ে; file system ডিস্কে টানা block খোঁজে (পর্ব ৪৩)। প্রতিটিতে fit কৌশল আর fragmentation একই রূপে ফিরে আসে।
• MMU-হীন সিস্টেমে এখনো এটিই বাস্তব। অনেক ছোট microcontroller-এ MMU নেই; সেখানে RTOS-এর heap সরাসরি contiguous. যেমন FreeRTOS-এর heap_4 নামের allocator first fit ব্যবহার করে আর পাশাপাশি খালি ব্লক জোড়া লাগায়।
• পরীক্ষার প্রিয় অঙ্ক। First/best/worst fit-এর placement বের করা বিশ্ববিদ্যালয় আর চাকরির লিখিত পরীক্ষায় খুব পরিচিত numerical.

২ · Fixed partition আর internal fragmentation

সবচেয়ে পুরোনো আর সরল উপায়: সিস্টেম চালুর সময় মেমরিকে কয়েকটি নির্দিষ্ট আকারের partition-এ ভাগ করে রাখা। প্রতিটি partition-এ একবারে ঠিক একটি প্রসেস। একটি partition খালি হলে অপেক্ষার সারি থেকে একটি প্রসেস সেখানে বসে। এর নাম fixed partitioning.

একটি উদাহরণ দেখুন। ব্যবহারকারীদের মেমরি ১০০০K, চারটি partition — ১০০K, ২০০K, ৩০০K আর ৪০০K. চারটি কাজ এসেছে, প্রতিটি নিজের মাপের সবচেয়ে কাছের partition-এ বসেছে:

এই ১৫০K খালি, কিন্তু কেউ ব্যবহার করতে পারবে না — কারণ প্রতিটি টুকরো এমন একটি partition-এর ভেতরে, যা ইতিমধ্যে একজনকে দেওয়া। এটাই internal fragmentation: দেওয়া জায়গা চাওয়ার চেয়ে বড়, আর বাড়তি অংশটুকু ব্লকের ভেতরে আটকে থাকে। আরও দুটি সীমাবদ্ধতা চোখে পড়ে:

• সবচেয়ে বড় partition-এর চেয়ে বড় কাজ কখনো চলতে পারে না। ৪৫০K-এর একটি কাজ এখানে চিরকাল অপেক্ষা করবে, যদিও পুরো মেমরি ১০০০K.
• Degree of multiprogramming আগেই বাঁধা। চারটি partition মানে একসাথে সর্বোচ্চ চারটি কাজ, তারা যত ছোটই হোক।

অপেক্ষার সারি হতে পারে partition-প্রতি আলাদা, অথবা একটি — partition খালি হলে সেখান থেকে মানানসই কাজ বেছে নেওয়া হয়। বিনিময়ে লাভ সরলতা: partition-এর সীমানা বদলায় না, তাই external fragmentation প্রায় নেই।

৩ · Variable partition, hole আর dynamic storage-allocation problem

Internal fragmentation কমানোর স্বাভাবিক চিন্তা: প্রতিটি প্রসেসকে ঠিক যতটা চায় ততটাই দেওয়া। এটাই variable partitioning (MVT-এর ভাবনা)। শুরুতে পুরো user মেমরি একটিমাত্র বড় খালি অংশ। প্রসেস আসে, প্রত্যেকে নিজের মাপের টুকরো কেটে নেয়; প্রসেস শেষ হয়, তার টুকরো খালি হয়। কিছুক্ষণ পর মেমরি দেখতে হয় এরকম: ব্যবহৃত ব্লক আর খালি অংশ পালা করে। প্রতিটি খালি টানা অংশকে বলে hole.

0K                                                                  1950K
│ hole 100 │ X │ hole 500 │ X │ hole 200 │ X │ hole 300 │ X │ hole 600 │ X │
             X = 50K used by some other process (holes cannot merge across it)

উপরের ছবিটিই এই পর্বের ক্লাসিক অঙ্কের শুরুর অবস্থা: পাঁচটি hole, ঠিকানার ক্রমে ১০০K, ৫০০K, ২০০K, ৩০০K আর ৬০০K, মাঝে মাঝে অন্য প্রসেসের ৫০K করে ব্লক (তাই hole গুলো জোড়া লাগতে পারে না)। OS এই hole-গুলোর একটি তালিকা রাখে — free list. এখন প্রশ্ন:

মুক্ত হলে জোড়া লাগানো — চারটি ঘটনা

একটি ব্লক মুক্ত হলে তার বাঁ আর ডান প্রতিবেশী দেখতে হয়। চারটি সম্ভাবনা, আর প্রতিটিতে hole-এর সংখ্যা কীভাবে বদলায় — অংশ ৫-এর প্রমাণে এটিই লাগবে:

এই জোড়া লাগানো দ্রুত করতে free list সাধারণত ঠিকানার ক্রমে সাজানো রাখা হয় (প্রতিবেশী পাশাপাশি থাকে), অথবা প্রতিটি ব্লকের দুই মাথায় তার আকার আর “ব্যবহৃত কি না” লেখা থাকে — boundary tag (অংশ ৮)। একটি সতর্কতা: পাশাপাশি দুটি hole কখনো আলাদা থাকা উচিত নয়; থাকলে বুঝবেন coalescing ঠিকমতো হয়নি — বড় অনুরোধ অকারণে ব্যর্থ হবে।

৪ · চার fit কৌশল — নিয়ম আর ক্লাসিক অঙ্ক

চারটিতেই কোনো hole যথেষ্ট বড় না হলে অনুরোধটি অপেক্ষা করে (বা ব্যর্থ হয়) — যদিও মোট খালি জায়গা হয়তো অনেক। এবার ক্লাসিক প্রশ্ন:

প্রশ্ন: ঠিকানার ক্রমে পাঁচটি hole — ১০০K, ৫০০K, ২০০K, ৩০০K আর ৬০০K. প্রসেসগুলো এই ক্রমে আসে: P1 = ২১২K, P2 = ৪১৭K, P3 = ১১২K, P4 = ৪২৬K. প্রতিটি কৌশলে কে কোথায় বসবে? কোন কৌশল মেমরি সবচেয়ে ভালো ব্যবহার করে?

একটি সূক্ষ্ম বিষয় আগে মেনে নিন (অনেক বইয়ে স্পষ্ট লেখা থাকে না): এগুলো variable partition — একটি hole থেকে কেটে নেওয়ার পর বাকি অংশ নতুন ছোট hole হয়ে তালিকায় থাকে, আর পরের অনুরোধ সেখানেও বসতে পারে। প্রশ্নে যদি fixed partition বলা থাকে (একটি partition-এ একটিই প্রসেস), উত্তর আলাদা হতে পারে। প্রথমে first fit আর best fit পাশাপাশি দেখুন:

1 holes: 100 500 200 300 6002 P1 asks 212K3 P2 asks 417K4 P3 asks 112K5 P4 asks 426K

চারটি কৌশলই একসাথে চালিয়ে দেখুন। Simulator ঠিকানার ক্রমে hole আর অন্যদের ৫০K ব্লক সাজায়, প্রতিটি অনুরোধে নিয়ম মেনে hole বেছে নেয়, তারপর একটি “free P2” ঘটনা ঘটায় — যাতে দেখা যায় মুক্ত হওয়া জায়গা জোড়া লাগার পর অপেক্ষায় থাকা P4 জায়গা পায় কি না।

// Variable partitions: first, next, best and worst fit on the same request/free sequence.
const HOLES = [100, 500, 200, 300, 600];          // free holes in address order, in K
const SEQ = [["P1", 212], ["P2", 417], ["P3", 112], ["P4", 426], ["free", "P2"]];
function run(rule) {
  const mem = []; let at = 0, rover = 0, waiting = [];
  for (const h of HOLES) {                        // a hole, then a 50K block someone else uses
    mem.push({ at, size: h, who: null }, { at: at + h, size: 50, who: "X" }); at += h + 50;
  }
  const place = (p, k) => {
    let c = mem.filter(b => !b.who && b.size >= k);          // holes big enough, address order
    if (rule === "next") c = [...c.filter(b => b.at >= rover), ...c.filter(b => b.at < rover)];
    if (rule === "best") c.sort((a, b) => a.size - b.size);  // stable sort: ties -> lower address
    if (rule === "worst") c.sort((a, b) => b.size - a.size);
    if (!c.length) { console.log(`  ${p} ${k}K: no hole >= ${k}K -> WAIT`); return false; }
    const h = c[0], old = h.size, rest = old - k;
    mem.splice(mem.indexOf(h), 1, { at: h.at, size: k, who: p },
               ...(rest ? [{ at: h.at + k, size: rest, who: null }] : []));
    rover = h.at + k;                                         // next fit resumes here
    console.log(`  ${p} ${k}K -> hole ${old}K at ${h.at}K, ${rest}K left`); return true;
  };
  console.log(rule.toUpperCase() + " FIT");
  for (const [p, k] of SEQ) {
    if (p !== "free") { if (!place(p, k)) waiting.push([p, k]); }
    else {
      mem.find(b => b.who === k).who = null; console.log(`  free ${k}`);
      for (let i = mem.length - 1; i > 0; i--)                // merge neighbouring holes
        if (!mem[i].who && !mem[i - 1].who) { mem[i - 1].size += mem[i].size; mem.splice(i, 1); }
      waiting = waiting.filter(([q, s]) => !place(q, s));    // retry whoever is waiting
    }
    console.log("    holes: " + mem.filter(b => !b.who).map(b => b.size).join(" "));
  }
  const free = mem.filter(b => !b.who).map(b => b.size), total = free.reduce((a, b) => a + b);
  console.log(`  free ${total}K in ${free.length} holes, largest ${Math.max(...free)}K\n`);
}
["first", "next", "best", "worst"].forEach(run);

FIRST FIT
  P1 212K -> hole 500K at 150K, 288K left
    holes: 100 288 200 300 600
  P2 417K -> hole 600K at 1300K, 183K left
    holes: 100 288 200 300 183
  P3 112K -> hole 288K at 362K, 176K left
    holes: 100 176 200 300 183
  P4 426K: no hole >= 426K -> WAIT
    holes: 100 176 200 300 183
  free P2
  P4 426K -> hole 600K at 1300K, 174K left
    holes: 100 176 200 300 174
  free 950K in 5 holes, largest 300K

NEXT FIT
  P1 212K -> hole 500K at 150K, 288K left
    holes: 100 288 200 300 600
  P2 417K -> hole 600K at 1300K, 183K left
    holes: 100 288 200 300 183
  P3 112K -> hole 183K at 1717K, 71K left
    holes: 100 288 200 300 71
  P4 426K: no hole >= 426K -> WAIT
    holes: 100 288 200 300 71
  free P2
  P4 426K: no hole >= 426K -> WAIT
    holes: 100 288 200 300 417 71
  free 1376K in 6 holes, largest 417K

BEST FIT
  P1 212K -> hole 300K at 950K, 88K left
    holes: 100 500 200 88 600
  P2 417K -> hole 500K at 150K, 83K left
    holes: 100 83 200 88 600
  P3 112K -> hole 200K at 700K, 88K left
    holes: 100 83 88 88 600
  P4 426K -> hole 600K at 1300K, 174K left
    holes: 100 83 88 88 174
  free P2
    holes: 100 500 88 88 174
  free 950K in 5 holes, largest 500K

WORST FIT
  P1 212K -> hole 600K at 1300K, 388K left
    holes: 100 500 200 300 388
  P2 417K -> hole 500K at 150K, 83K left
    holes: 100 83 200 300 388
  P3 112K -> hole 388K at 1512K, 276K left
    holes: 100 83 200 300 276
  P4 426K: no hole >= 426K -> WAIT
    holes: 100 83 200 300 276
  free P2
  P4 426K -> hole 500K at 150K, 74K left
    holes: 100 74 200 300 276
  free 950K in 5 holes, largest 300K

তুলনা — গতি আর fragmentation

পাঠ্যবইয়ের simulation-ভিত্তিক সিদ্ধান্ত: first fit আর best fit সময় আর মেমরি দুই দিকেই worst fit-এর চেয়ে ভালো; মেমরি ব্যবহারে first আর best প্রায় সমান, কিন্তু first fit সাধারণত দ্রুত। একটি অঙ্কের ফল দিয়ে এই সিদ্ধান্ত টানবেন না — উপরের অঙ্কে best fit জিতেছে, কিন্তু অনুশীলনের অঙ্কে দেখবেন অন্য চিত্র। বাস্তব workload-এ কোনটি ভালো, তা নির্ভর করে অনুরোধের আকার আর আয়ুর ধরনের ওপর।

৫ · Internal বনাম external fragmentation, আর ৫০-শতাংশ নিয়ম

External fragmentation কতটা খারাপ, তা মাপার একটি প্রচলিত উপায়: 1 − (সবচেয়ে বড় hole ÷ মোট খালি). শূন্য মানে সব খালি একটি টুকরোয়; ১-এর কাছে মানে খালি জায়গা গুঁড়ো হয়ে গেছে। Simulator-এর শেষ অবস্থায় first fit-এ ১ − ৩০০/৯৫০ ≈ ০.৬৮, আর best fit-এ ১ − ৫০০/৯৫০ ≈ ০.৪৭।

৫০-শতাংশ নিয়ম (fifty-percent rule)

Donald Knuth তাঁর The Art of Computer Programming-এর প্রথম খণ্ডে (dynamic storage allocation অংশে) একটি চমৎকার ফল দেখান। পাঠ্যবই এটিকে এভাবে বলে: first fit-এ, কিছু উন্নতির পরেও, N টি বরাদ্দ ব্লক থাকলে আরও প্রায় ০.৫N টি ব্লক fragmentation-এ হারিয়ে যায় — অর্থাৎ মেমরির প্রায় এক-তৃতীয়াংশ অব্যবহারযোগ্য হতে পারে। কথাটি সাবধানে পড়ুন, কারণ এতে দুটি আলাদা দাবি আছে:

1. Knuth-এর আসল বক্তব্য hole-এর সংখ্যা নিয়ে: সিস্টেম যদি একটি স্থিত অবস্থায় (equilibrium) পৌঁছায়, যেখানে গড়ে N টি ব্লক বরাদ্দ থাকে, প্রতিটি ব্লকের পরের মুক্ত হওয়ার সম্ভাবনা সমান, আর একটি বরাদ্দ ঠিক মাপের hole পায় না (hole ভাগ হয়) সম্ভাবনা p নিয়ে — তাহলে hole-এর গড় সংখ্যা ≈ pN/2. Exact fit বিরল হলে p ≈ ১, তাই hole ≈ N/2.
2. “এক-তৃতীয়াংশ” একটি বাড়তি অনুমান থেকে আসে: যদি hole-এর গড় আকার ব্লকের গড় আকারের সমান ধরা হয়, তাহলে মোট জায়গার N + N/2 ভাগের N/2 ভাগ hole — অর্থাৎ ১/৩. বাস্তবে hole-গুলো সাধারণত ব্লকের চেয়ে ছোট বা বড় হতে পারে, তাই “এক-তৃতীয়াংশ” একটি মোটা দাগের অনুমান, নিয়ম নয়।

শিক্ষাটা গুরুত্বপূর্ণ: variable partition-এ fragmentation কোনো দুর্ঘটনা নয়, স্থিত অবস্থার স্বাভাবিক ফল। ভালো fit নিয়ম hole-এর আকার ভালো রাখতে পারে, কিন্তু hole থাকবেই। দুটি পথ খোলা থাকে — জায়গা সরিয়ে hole এক করা (compaction), অথবা “এক টুকরো টানা” শর্তটিই তুলে দেওয়া (paging, পর্ব ৩২)।

৬ · Compaction — জায়গা সরিয়ে hole এক করা

Compaction মানে ব্যবহৃত ব্লকগুলোকে সরিয়ে এক পাশে জড়ো করা, যাতে সব hole মিলে একটি বড় hole হয়। কমিউনিটি সেন্টারের উদাহরণে: বসে থাকা অতিথিদের অনুরোধ করে এক দিকে সরিয়ে দেওয়া, যাতে আটজনের পরিবার একসাথে বসতে পারে। কিন্তু তার আগে দুটি প্রশ্ন।

• সরানো কি আদৌ সম্ভব? একটি প্রসেসকে নতুন ঠিকানায় সরালে তার ভেতরের সব ঠিকানাও বদলাতে হয়। ঠিকানা যদি compile বা load-এর সময় বেঁধে ফেলা হয় (পর্ব ৩০), তাহলে প্রোগ্রামের ভেতরে physical ঠিকানা লেখা আছে — সরালেই সব ভাঙবে। Compaction তখনই সম্ভব, যখন execution-time binding: প্রোগ্রাম শুধু logical ঠিকানা জানে, আর MMU-র relocation register যোগ হয় প্রতিটি মেমরি-ব্যবহারে। তাহলে ব্লক কপি করে শুধু register-এর মান বদলালেই চলে।
• কোনো I/O চলছে কি? কোনো device যদি DMA দিয়ে প্রসেসের একটি buffer-এ physical ঠিকানায় লিখছে, তখন সেই ব্লক সরানো যাবে না — হয় I/O শেষ হওয়া পর্যন্ত ব্লকটি আটকে রাখা (pin), নয়তো I/O শুধু OS-এর নিজের buffer-এ করা।

নিচের stepper-এ first fit-এর শেষ অবস্থা থেকে (P4 = ৪২৬K অপেক্ষায়, মোট খালি ৯৫৯K) compaction দেখুন। ঠিকানা K-তে, X1…X5 অন্য প্রসেসের ৫০K করে ব্লক।

1 state after first fit, P4 426K waits2 move X1 100->0, P1 150->503 move P3 362->262, X2 650->3744 move X3 ->424, X4 ->474, P2 ->5245 one hole of 959K: place P4 at 9416 cheaper: from step 1, move only X2

দাম কত? Compaction মূলত মেমরি কপি। ধরুন একটি মেশিন সেকেন্ডে প্রায় ১০ GB কপি করতে পারে (একটি কল্পিত সংখ্যা, মেশিনভেদে আলাদা); তাহলে ৮ GB সরাতে প্রায় ০.৮ সেকেন্ড, আর সেই সময় সরানো প্রসেসগুলো থেমে থাকে। তাই compaction সাধারণত মাঝে মাঝে, দরকার হলে করা হয় — প্রতিটি free-তে নয়।

আজ compaction কোথায়? সাধারণ প্রসেসের জন্য নয় — paging থাকায় দরকার পড়ে না। কিন্তু Linux kernel physical মেমরিতে compaction করে, যাতে বড় টানা জায়গা (যেমন huge page, পর্ব ৩৮) পাওয়া যায়; এটি সম্ভব কারণ page সরিয়ে শুধু page table বদলালেই প্রসেস টের পায় না। Java বা .NET-এর মতো runtime-এর garbage collector-ও heap compact করে, কারণ তারা প্রতিটি reference খুঁজে বদলাতে পারে। C-এর malloc পারে না — প্রোগ্রামের হাতে কাঁচা pointer, কোনটি কোথায় লেখা আছে allocator জানে না।

৭ · Buddy system — ২-এর ঘাতে ভাগ আর জোড়া

Variable partition-এ coalescing-এর জন্য প্রতিবেশী খুঁজতে হয়, আর hole যেকোনো মাপের হতে পারে। Buddy system দুটিকেই সরল করে: সব ব্লকের আকার ২-এর ঘাত (power of two), আর প্রতিটি ব্লকের জোড়া লাগার সঙ্গী — তার buddy — ঠিকানা থেকেই হিসাব করে বের করা যায়।

নিয়ম

1. বরাদ্দ: n চাইলে আকার বাড়িয়ে নিকটতম ২-এর ঘাত s ≥ n ধরুন (১০০K → ১২৮K). s মাপের free list-এ ব্লক থাকলে সেটি দিন। না থাকলে তার চেয়ে বড় সবচেয়ে ছোট খালি ব্লক নিন, আর বারবার অর্ধেক করুন — প্রতিবার এক অর্ধেক রাখুন, অন্য অর্ধেক (সেটিই buddy) উপযুক্ত free list-এ দিন — যতক্ষণ না আকার s হয়।
2. মুক্তি: ব্লকের buddy খালি আর একই মাপের হলে দুটি জোড়া লাগিয়ে দ্বিগুণ মাপের ব্লক করুন; নতুন ব্লকের buddy-ও খালি হলে আবার জোড়া — যতক্ষণ সম্ভব। এরপর ফলের ব্লকটি free list-এ দিন।
3. প্রতিটি মাপের আলাদা free list: ৬৪K, ১২৮K, ২৫৬K… প্রতিটির নিজস্ব তালিকা — যেটি একধরনের segregated free list.

এবার পাঠ্যবইয়ের পরিচিত উদাহরণ: ১ MB (১০২৪K) pool; অনুরোধ A = ১০০K, B = ২৪০K, C = ৬৪K, D = ২৫৬K; তারপর একে একে free B, free A, free C, free D.

1 pool: 1024K free at 02 A = 100K  -> 128K3 B = 240K  -> 256K4 C = 64K   -> 64K5 D = 256K  -> 256K6 free B7 free A8 free C9 free D

// Binary buddy system on 1 MB (1024K). Sizes in K; addresses are offsets from the pool start.
const TOTAL = 1024, free = { [TOTAL]: [0] }, used = {};    // free[size] = list of addresses
const take = (s, a) => free[s].splice(free[s].indexOf(a), 1);
function alloc(name, k) {
  let need = 1; while (need < k) need *= 2;               // round up to a power of two
  let s = need; while (s <= TOTAL && !(free[s] || []).length) s *= 2;
  if (s > TOTAL) return console.log(`${name} ${k}K: no block -> WAIT`);
  const a = Math.min(...free[s]); take(s, a);
  while (s > need) { s /= 2; (free[s] = free[s] || []).push(a + s); }   // split, keep low half
  used[a] = { name, size: need, k };
  show(`${name} ${k}K -> ${need}K block at ${a}K (waste ${need - k}K)`);
}
function release(name) {
  let a = +Object.keys(used).find(x => used[x].name === name), s = used[a].size;
  delete used[a];
  let log = `free ${name}: ${s}K at ${a}K`;
  while (s < TOTAL && (free[s] || []).includes(a ^ s)) {  // buddy = address XOR size
    take(s, a ^ s); log += `, merge with buddy ${a ^ s}K`;
    a = Math.min(a, a ^ s); s *= 2;
  }
  (free[s] = free[s] || []).push(a);
  show(log + ` -> ${s}K free at ${a}K`);
}
function show(msg) {
  const blocks = [];
  for (const s in free) for (const a of free[s]) blocks.push([a, `${s}`]);
  for (const a in used) blocks.push([+a, `${used[a].name}${used[a].size}`]);
  const waste = Object.values(used).reduce((t, u) => t + u.size - u.k, 0);
  console.log(msg + "\n   map: " + blocks.sort((x, y) => x[0] - y[0]).map(b => b[1]).join(" | ")
              + `   (internal waste ${waste}K)\n   free lists: ` + Object.keys(free).map(Number)
              .sort((x, y) => x - y).filter(s => free[s].length).map(s => `${s}K:[${free[s]}]`).join(" "));
}
alloc("A", 100); alloc("B", 240); alloc("C", 64); alloc("D", 256);
release("B"); release("A"); release("C"); release("D");

A 100K -> 128K block at 0K (waste 28K)
   map: A128 | 128 | 256 | 512   (internal waste 28K)
   free lists: 128K:[128] 256K:[256] 512K:[512]
B 240K -> 256K block at 256K (waste 16K)
   map: A128 | 128 | B256 | 512   (internal waste 44K)
   free lists: 128K:[128] 512K:[512]
C 64K -> 64K block at 128K (waste 0K)
   map: A128 | C64 | 64 | B256 | 512   (internal waste 44K)
   free lists: 64K:[192] 512K:[512]
D 256K -> 256K block at 512K (waste 0K)
   map: A128 | C64 | 64 | B256 | D256 | 256   (internal waste 44K)
   free lists: 64K:[192] 256K:[768]
free B: 256K at 256K -> 256K free at 256K
   map: A128 | C64 | 64 | 256 | D256 | 256   (internal waste 28K)
   free lists: 64K:[192] 256K:[768,256]
free A: 128K at 0K -> 128K free at 0K
   map: 128 | C64 | 64 | 256 | D256 | 256   (internal waste 0K)
   free lists: 64K:[192] 128K:[0] 256K:[768,256]
free C: 64K at 128K, merge with buddy 192K, merge with buddy 0K, merge with buddy 256K -> 512K free at 0K
   map: 512 | D256 | 256   (internal waste 0K)
   free lists: 256K:[768] 512K:[0]
free D: 256K at 512K, merge with buddy 768K, merge with buddy 0K -> 1024K free at 0K
   map: 1024   (internal waste 0K)
   free lists: 1024K:[0]

লাভ-ক্ষতির হিসাব

• দ্রুত coalescing: প্রতিবেশী খুঁজতে কোনো তালিকা ঘাঁটতে হয় না — একটি XOR আর “ওই ঠিকানার ব্লক কি খালি?” প্রশ্ন। মোট ২^k মাপের pool-এ বরাদ্দ বা মুক্তি সর্বোচ্চ k ধাপের ভাগ বা জোড়া।
• Internal fragmentation: আকার ২-এর ঘাতে গোল করতে হয়, তাই অপচয় ০ থেকে প্রায় ৫০% পর্যন্ত; গড় কত, তা অনুরোধের আকারের বণ্টনের ওপর নির্ভর করে।
• External fragmentation পুরো যায় না: শুধু buddy-র সাথেই জোড়া হয়। পাশাপাশি দুটি খালি ব্লক buddy না হলে (যেমন ৬৪@১৯২ আর ২৫৬@২৫৬) কখনো মিশবে না।

Linux kernel physical page-গুলো এভাবেই রাখে: “order” k-এর তালিকায় ২^k টি পাশাপাশি page-এর ব্লক। /proc/buddyinfo ফাইলে প্রতিটি order-এ এখন কতগুলো খালি ব্লক আছে, দেখা যায় — নিচের কমান্ড চালালে আপনার সামনের সিস্টেমের (এখানে একটি container-এর ভেতর থেকে দেখা host kernel-এর) সংখ্যা আসবে।

# Linux keeps one free list per "order": order k holds blocks of 2^k pages.
echo "page size: $(getconf PAGESIZE) bytes"
echo "columns after the zone name = free blocks of order 0 1 2 ... 10"
cat /proc/buddyinfo 2>/dev/null || echo "/proc/buddyinfo is not readable here"

page size: 4096 bytes
columns after the zone name = free blocks of order 0 1 2 ... 10
Node 0, zone      DMA     56     54     39     33     27      9      1      3      1      0      1
Node 0, zone    DMA32   1335   3968   2656   1852    799    161     29      0      0      0      0

Slab আর segregated free list — ছোট object-এর জন্য

Kernel-কে প্রতি সেকেন্ডে হাজার হাজার ছোট object লাগে — একটি process descriptor, একটি inode, একটি network buffer-এর header — প্রত্যেকটি কয়েকশো বাইট। এগুলোর জন্য buddy থেকে গোটা একটি page (৪ KiB) নিলে বিশাল internal fragmentation. সমাধান হলো slab allocator-এর ভাবনা (Jeff Bonwick, Sun-এর Solaris-এর জন্য, ১৯৯৪ সালের প্রবন্ধ): buddy থেকে কয়েকটি page নিয়ে সেগুলোকে একই মাপের অনেক ঘরে ভাগ করা, আর প্রতিটি object-ধরনের জন্য আলাদা cache রাখা। একই মাপের ঘর বলে ভেতরে fragmentation প্রায় নেই, আর মুক্ত ঘর আবার একই ধরনের object-এর জন্য তৈরি থাকে। মূল নীতি — আকার অনুযায়ী আলাদা তালিকা (segregated free list) — user-space malloc-এরও ভিত্তি। Linux-এ slab-এর বর্তমান রূপ (SLUB), /proc/slabinfo আর বাস্তব খুঁটিনাটি পর্ব ৩৮-এ।

৮ · প্রোগ্রামের ভেতরে — malloc-ও একই সমস্যা সমাধান করে

OS প্রসেসকে মেমরি দেয় বড় টুকরোয় — brk দিয়ে heap বাড়িয়ে, বা mmap দিয়ে। কিন্তু প্রোগ্রাম চায় ২৪ বাইট, ১০০ বাইট, ৪ KB — লাখ লাখ বার। সেই বড় টুকরোর ভেতরে ছোট ছোট অংশ কেটে দেওয়া আর ফেরত নেওয়ার কাজ করে C library-র memory allocator — malloc আর free. এটি ঠিক এই পর্বের dynamic storage-allocation problem, শুধু একটি প্রসেসের virtual মেমরির ভেতরে। মূল কৌশলগুলো:

• Free list: খালি অংশগুলোর linked list — প্রতিটি খালি অংশের ভেতরেই পরের খালি অংশের pointer রাখা হয়, তাই আলাদা মেমরি লাগে না (DSA-র linked list পর্ব)।
• Boundary tag: প্রতিটি অংশের শুরুতে (header) আর দরকারে শেষে (footer) তার আকার আর “ব্যবহৃত কি না” লেখা — Knuth-এর বর্ণিত কৌশল। মুক্ত করার সময় header দেখে ডানের প্রতিবেশী, footer দেখে বাঁয়ের প্রতিবেশী O(1)-এ পাওয়া যায়, coalescing-এর জন্য তালিকা ঘাঁটতে হয় না।
• Size class আর bin: অনুরোধের আকার কয়েকটি নির্দিষ্ট মাপে গোল করা (যেমন ১৬, ৩২, ৪৮… বাইট), আর প্রতিটি মাপের আলাদা তালিকা — slab-এর মতোই segregated free list. ছোট অনুরোধ প্রায় O(1), বিনিময়ে কিছু internal fragmentation.
• বড় অনুরোধ সরাসরি OS থেকে: খুব বড় অংশ (glibc-তে ডিফল্ট সীমা প্রায় ১২৮ KiB, যা চলার সময় বদলাতে পারে) আলাদা mmap দিয়ে আনা হয়, free করলে সরাসরি OS-কে ফেরত — heap-এর fragmentation থেকে আলাদা থাকে।
• থ্রেডপ্রতি বা CPU-প্রতি cache আর arena: অনেক থ্রেড একই free list-এ lock নিয়ে লড়লে ধীর হয়, তাই আধুনিক allocator থ্রেডপ্রতি ছোট cache আর একাধিক আলাদা heap (arena) রাখে।

Windows-এর নিজস্ব heap (HeapAlloc, Low-Fragmentation Heap, নতুন সংস্করণে segment heap) আর macOS-এর libmalloc আলাদা নকশা, কিন্তু একই হাতিয়ার — size class, cache আর coalescing — নানা মিশ্রণে ব্যবহার করে। নিজে একটি ছোট malloc বানাতে চাইলে C কোর্সের “নিজের malloc বানানো” পর্ব দেখুন।

নিচের C প্রোগ্রাম glibc-র malloc থেকে বিভিন্ন মাপের অংশ চেয়ে দেখে: আসলে কত বাইট ব্যবহার করা যায় (malloc_usable_size, একটি glibc extension — standard C নয়), ঠিকানা ১৬-এর গুণিতক কি না, আর পাশাপাশি দুটি malloc(100)-এর মাঝে কত বাইটের দূরত্ব।

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <malloc.h>      /* malloc_usable_size: a glibc extension, not standard C */

int main(void) {
    size_t sizes[] = {1, 24, 25, 40, 100, 1000, 4000, 200000};
    int n = sizeof sizes / sizeof sizes[0];
    void *p[8];
    printf("%8s %8s %6s %8s\n", "asked", "usable", "extra", "addr%16");
    for (int i = 0; i < n; i++) {
        p[i] = malloc(sizes[i]);
        if (!p[i]) return 1;
        size_t u = malloc_usable_size(p[i]);
        printf("%8zu %8zu %6zu %8u\n", sizes[i], u, u - sizes[i],
               (unsigned)((uintptr_t)p[i] % 16));
    }
    char *a = malloc(100), *b = malloc(100);   /* two neighbours on the heap */
    printf("gap between two malloc(100): %ld bytes\n",
           (long)((uintptr_t)b - (uintptr_t)a));
    for (int i = 0; i < n; i++) free(p[i]);
    free(a); free(b);
    return 0;
}

   asked   usable  extra  addr%16
       1       24     23        0
      24       24      0        0
      25       40     15        0
      40       40      0        0
     100      104      4        0
    1000     1000      0        0
    4000     4008      8        0
  200000   200688    688        0
gap between two malloc(100): 112 bytes

দীর্ঘদিন চলা সার্ভারে fragmentation

একটি ওয়েব সার্ভার বা cache সপ্তাহের পর সপ্তাহ চলে। নানা মাপের অনুরোধ আসে-যায়; কিছু অংশ অনেকদিন বেঁচে থাকে, মাঝের অংশগুলো মুক্ত হয়। ধীরে ধীরে heap-এ hole জমে — ৫০-শতাংশ নিয়মের বাস্তব রূপ। লক্ষণ: প্রোগ্রামের আসল ব্যবহৃত ডেটা স্থির, কিন্তু OS-এর চোখে প্রসেসের RSS বাড়তেই থাকে — কারণ allocator এমন page ফেরত দিতে পারে না, যেখানে একটিও জীবিত অংশ আছে। এটি memory leak নয়, কিন্তু বাইরে থেকে দেখতে একই রকম।

• মাপা: allocator-এর নিজের হিসাব (জীবিত বাইট) আর OS-এর RSS তুলনা করুন। যেমন Redis-এর INFO memory-তে mem_fragmentation_ratio ঠিক এই অনুপাত দেখায়।
• উপায়: allocator বদলানো বা tune করা, একই আয়ুর object একসাথে রাখা, কিছু সিস্টেমে চলন্ত defragmentation — বিস্তারিত ভাবনার প্রশ্ন ৫-এ। যেটিই করুন, নিজের workload-এ মেপে দেখুন।

৯ · AI-এর যুগে মেমরি allocation

Fit কৌশলের অঙ্ক আর allocator নিয়ে AI-কে প্রশ্ন করলে উত্তর দ্রুত আসে, কিন্তু কয়েকটি ভুল বারবার দেখা যায়:

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

• প্রতিটি ধাপে hole তালিকা নিজে লিখে মিলিয়েছি, অবশিষ্ট অংশ বাদ পড়েনি
• মোট খালি জায়গার হিসাব প্রতিটি ধাপে মিলেছে
• প্রশ্ন fixed নাকি variable partition — সেই অনুযায়ী সমাধান হয়েছে কি না দেখেছি
• উপরের simulator-এ একই সংখ্যা বসিয়ে ফল মিলিয়েছি
• Allocator বা kernel নিয়ে দাবি (glibc-র সীমা, Linux-এর আচরণ) man page বা অফিসিয়াল ডকুমেন্টেশনে দেখেছি — অন্য OS বা পুরোনো সংস্করণের তথ্য কি না যাচাই করেছি
• AI-এর লেখা allocator কোড “আমার মেশিনে চলে” বলে মেনে নিইনি — একাধিক থ্রেড আর লোড দিয়ে, AddressSanitizer বা Valgrind চালিয়ে পরীক্ষা করেছি