Multiprocessor আর real-time scheduling — affinity, RM আর EDF

১ · অনেক CPU, নতুন প্রশ্ন — একটি লাইন, নাকি প্রতি কাউন্টারে আলাদা লাইন

পর্ব ১৬ থেকে ১৯ পর্যন্ত আমরা একটি প্রশ্নের উত্তর খুঁজেছি: ready queue থেকে কাকে পরের পালা দেওয়া হবে — FCFS, SJF, Round Robin, MLFQ. সব হিসাব ছিল একটিমাত্র CPU ধরে, অথচ আজকের ফোনেও ৮টি, আর সার্ভারে শতাধিক logical CPU থাকে। তখন প্রশ্ন দাঁড়ায় দুটি: কাকে চালানো হবে, আর কোন CPU-তে চালানো হবে।

একটি ব্যাংকের শাখার কথা ভাবুন। একটি কাউন্টার থাকলে প্রশ্ন সহজ — টোকেন নম্বর ধরে ডাকা। পাঁচটি কাউন্টার হলে দুটি পথ খোলা। এক, সবার জন্য একটিই টোকেন-লাইন; যে কাউন্টার খালি হয়, সে লাইনের পরের জনকে ডাকে। দুই, প্রতিটি কাউন্টারের সামনে আলাদা লাইন। প্রথম পথে কেউ বৃথা বসে থাকে না, কিন্তু টোকেন-যন্ত্রটির সামনে সব কর্মকর্তার ভিড় লাগে। দ্বিতীয় পথে ভিড় নেই, কিন্তু কোনো লাইন লম্বা আর কোনোটি খালি হয়ে যেতে পারে।

Asymmetric বনাম symmetric multiprocessing

শুরুর দিকের অনেক multiprocessor সিস্টেম সবচেয়ে সরল পথ নিয়েছিল: asymmetric multiprocessing (AMP). একটি প্রধান CPU একাই kernel চালায় — scheduling-এর সিদ্ধান্ত, I/O, system call সব তার হাতে। বাকি CPU-গুলো শুধু তার দেওয়া user কোড চালায়। Kernel-এর ডেটা একজনই ছোঁয় বলে নকশা সরল, কিন্তু প্রধান CPU-টি বাধা (bottleneck) হয়ে দাঁড়ায়।

আজকের Linux, Windows, macOS, Android আর iOS সবই symmetric multiprocessing (SMP): প্রতিটি CPU নিজেই scheduler চালায়, নিজেই kernel-এ ঢুকতে পারে, নিজেই পরের task বাছে। দাম হলো kernel-এর ভাগের ডেটা সুরক্ষিত রাখতে lock আর সতর্ক নকশা (মডিউল ৪)। “Asymmetric” শব্দটি অবশ্য আজও অন্য অর্থে টিকে আছে — যেমন একটি চিপে কয়েকটি core-এ Linux আর একটি ছোট core-এ আলাদা real-time firmware চলা — আর ভিন্ন স্বভাবের core নিয়ে আমরা অংশ ৪-এ কথা বলব।

এক ভাগের run queue বনাম প্রতি CPU-র নিজের run queue

Linux-এর ইতিহাস এখানে শিক্ষণীয়। Linux 2.4-এর scheduler-এ পুরো সিস্টেমে একটিই runqueue ছিল, আর একটি lock. ২০০২-০৩ সালের দিকে Ingo Molnar-এর O(1) scheduler (Linux 2.6-এ মূলধারায়) প্রতিটি CPU-কে নিজের runqueue দেয়। পরের CFS (২০০৭) আর আজকের EEVDF (পর্ব ২১)-ও এই কাঠামো রেখেছে: Linux kernel-এর struct rq প্রতি CPU-তে একটি। Windows আর macOS-ও মূলত প্রতি processor (কিছু ক্ষেত্রে কাছাকাছি কয়েকটি processor-এর একটি দল) ধরে আলাদা ready queue রাখে।

২ · Processor affinity — যে CPU চেনে, তার কাছেই থাকা

একটি task কিছুক্ষণ CPU 0-তে চললে তার ব্যবহৃত ডেটা আর কোড CPU 0-এর L1 আর L2 cache-এ জমে (পর্ব ৪-এর memory hierarchy মনে করুন)। এই অবস্থাকে বলে warm cache. এখন যদি পরের পালায় তাকে CPU 1-এ পাঠানো হয়, সেখানকার cache-এ তার কিছুই নেই — প্রথম কিছুক্ষণ প্রায় প্রতিটি মেমরি-ছোঁয়া cache miss, আর CPU 0-এর cache-এ পড়ে থাকা পুরোনো কপিগুলো cache coherence-এর নিয়মে বাতিল করতে হয়। এই খরচ এড়াতে scheduler-এর একটি স্বাভাবিক ঝোঁক থাকে: task যে CPU-তে আগে চলেছে, পরেও সেখানেই চালানো। এই ঝোঁকের নাম processor affinity (বা CPU affinity).

Hard affinity কেন দরকার? কম-latency সার্ভারে thread-কে সেই core-এ রাখা, যেখানে নেটওয়ার্ক কার্ডের interrupt আসে; benchmark-এ মাপ স্থির রাখা; আর একটি real-time কাজকে এমন core দেওয়া, যেখানে আর কেউ চলে না। পর্ব ৯-এর ping-pong মাপার প্রোগ্রামেও দুটি প্রসেসকে এক CPU-তে বাঁধা হয়েছিল।

নিজে করে দেখা — একটি প্রোগ্রাম নিজেকে CPU 0-তে বাঁধে

Linux-এ affinity হলো একটি CPU-র সেট (cpu_set_t), যার প্রতিটি বিট একটি CPU. নিচের প্রোগ্রাম আগে দেখে নেয় সে কোন কোন CPU ব্যবহার করতে পারে আর এখন কোথায় চলছে (sched_getcpu()). তারপর CPU 0-তে নিজেকে বাঁধে — container বা cgroup কোনো কারণে CPU 0 না দিলে, অনুমোদিত প্রথম CPU-তে। শেষে কিছু হিসাব-ভারী কাজ করে পাঁচবার দেখে, সে কখনো অন্য CPU-তে গিয়েছিল কি না।

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <unistd.h>

static volatile unsigned long sink;   /* keeps the loop from being optimised away */

static int count_moves(int target) {     /* busy work; how often are we elsewhere? */
    int away = 0;
    for (int i = 0; i < 5; i++) {
        for (unsigned long k = 0; k < 20000000UL; k++) sink += k;
        if (sched_getcpu() != target) away++;
    }
    return away;
}

int main(void) {
    cpu_set_t allowed, one;
    if (sched_getaffinity(0, sizeof allowed, &allowed) != 0) { perror("sched_getaffinity"); return 1; }
    printf("online CPUs: %ld, CPUs I may use: %d\n", sysconf(_SC_NPROCESSORS_ONLN), CPU_COUNT(&allowed));
    printf("before: running on CPU %d\n", sched_getcpu());

    int target = 0;                       /* want CPU 0, else the first allowed one */
    while (target < CPU_SETSIZE - 1 && !CPU_ISSET(target, &allowed)) target++;
    CPU_ZERO(&one);
    CPU_SET(target, &one);
    if (sched_setaffinity(0, sizeof one, &one) != 0) { perror("sched_setaffinity"); return 1; }

    int away = count_moves(target);
    sched_getaffinity(0, sizeof allowed, &allowed);
    printf("pinned to CPU %d, CPUs I may use now: %d\n", target, CPU_COUNT(&allowed));
    printf("after: running on CPU %d, checks on another CPU: %d of 5\n", sched_getcpu(), away);
    return 0;
}

online CPUs: 2, CPUs I may use: 2
before: running on CPU 0
pinned to CPU 0, CPUs I may use now: 1
after: running on CPU 0, checks on another CPU: 0 of 5

একই তথ্য shell থেকে দেখা যায়। nproc দেখায় এই প্রসেস কতগুলো CPU ব্যবহার করতে পারে, taskset -p দেখায় affinity-র mask (hex-এ, প্রতিটি বিট একটি CPU), আর /proc/<pid>/status-এর Cpus_allowed_list একই কথা তালিকা আকারে বলে।

echo "nproc            : $(nproc)"
grep Cpus_allowed_list /proc/self/status          # grep's own allowed CPUs
taskset -p $$                                      # this shell's affinity mask (hex)
taskset -cp $$                                     # the same mask as a CPU list
taskset -c 0 grep Cpus_allowed_list /proc/self/status   # a child started pinned to CPU 0
ps -o pid,psr,comm -p $$                           # PSR = CPU it last ran on
chrt -p $$                                         # scheduling policy of this shell
chrt -f 10 true 2>&1 || echo "-> SCHED_FIFO refused (exit code $?)"

nproc            : 2
Cpus_allowed_list:	0-1
pid 2's current affinity mask: 3
pid 2's current affinity list: 0,1
Cpus_allowed_list:	0
    PID PSR COMMAND
      2   0 bash
pid 2's current scheduling policy: SCHED_OTHER
pid 2's current scheduling priority: 0
chrt: failed to set pid 0's policy: Operation not permitted
-> SCHED_FIFO refused (exit code 1)

PS> $p = Get-Process notepad
PS> $p.ProcessorAffinity          # bit mask, e.g. 255 = CPUs 0-7
255
PS> $p.ProcessorAffinity = 1      # hard affinity: CPU 0 only
PS> cmd /c start /affinity 3 notepad.exe   # start a new notepad on CPUs 0 and 1 (mask 0x3)

৩ · Load balancing — push, pull, work stealing আর NUMA

প্রতি CPU-র আলাদা run queue নিলে অসমতা আসবেই। কেউ নতুন প্রসেস চালু করল, কেউ ডিস্কের অপেক্ষায় ঘুমাল, কেউ শেষ হলো — কিছুক্ষণ পর দেখা যায় এক CPU-তে পাঁচজন অপেক্ষা করছে আর পাশের CPU কিছুই করছে না। Load balancing-এর কাজ এই অসমতা মেটানো। দুটি মৌলিক কৌশল:

• Push migration — নির্দিষ্ট সময় পরপর (যেমন timer tick-এর সাথে) একটি পরীক্ষা চলে; কোনো CPU বেশি ভারী হলে তার queue থেকে task ঠেলে হালকা CPU-তে পাঠানো হয়।
• Pull migration — যে CPU অলস হয়ে পড়ল, সে বসে না থেকে নিজেই সবচেয়ে ব্যস্ত CPU-র queue থেকে একটি task টেনে আনে।

দুটি একসাথেই চলে। Linux-এ নির্দিষ্ট সময় পরপর balance পরীক্ষা হয়, আর কোনো CPU-র queue খালি হওয়া মাত্র “newly idle” balance চেষ্টা করে কাজ টেনে আনতে। কোন task সরাবে, সেটিও হিসাবের ব্যাপার: যে task সবেমাত্র চলেছে (“cache-hot”), তাকে সরালে cache-এর ক্ষতি বেশি, তাই সম্ভব হলে অন্যকে বাছা হয়; আর যার hard affinity অন্য CPU নিষেধ করে, তাকে তো ছোঁয়াই যায় না। নিচের stepper-এ দুটি CPU-র পুরো ঘটনা দেখুন।

1start: CPU0 runs A, CPU1 runs E2E calls read() on disk -> blocks3CPU1 newly idle -> pull from busiest4D starts on CPU1 (cold cache)5disk done: E wakes -> back to CPU16periodic balance: 3 vs 2 -> no move

Work stealing — runtime-এর ভেতরের একই ধারণা

Pull migration-এর একটি জনপ্রিয় রূপ প্রোগ্রামের runtime-এ দেখা যায়: work stealing. প্রতিটি worker thread-এর নিজস্ব কাজের সারি (deque); সে নিজের সারির সামনের দিক থেকে কাজ নেয়, আর কারও সারি খালি হলে সে অন্য worker-এর সারির পেছন থেকে কাজ চুরি করে। পেছন থেকে নেওয়ায় দুজনের ঠোকাঠুকি কম হয়। ১৯৯০-এর দশকে MIT-র Cilk প্রকল্প এর তাত্ত্বিক ভিত্তি দেয়; আজ Go-র goroutine scheduler, Java-র ForkJoinPool আর Rust-এর Tokio এই কৌশলে চলে।

NUMA — সব মেমরি সমান দূরে নয়

বড় সার্ভারে দুই বা ততোধিক processor socket থাকে, আর প্রতিটির সাথে আলাদা মেমরি-চ্যানেল। এমন কম্পিউটারকে বলে NUMA (non-uniform memory access): একটি CPU নিজের node-এর মেমরি দ্রুত পায়, অন্য socket-এর মেমরি পেতে আন্তঃসংযোগ (interconnect) পেরোতে হয় — সাধারণত লক্ষণীয়ভাবে ধীর, আর ব্যান্ডউইথও কম। তখন affinity-র প্রশ্ন শুধু cache-এর নয়, মেমরিরও: Linux-এর ডিফল্ট নিয়মে একটি page প্রথম যে CPU ছোঁয়, তার node-এই বরাদ্দ হয় (“first touch”). তাই একটি thread-কে অন্য socket-এ সরালে তার পুরো মেমরি দূরে পড়ে যায়।

এজন্য NUMA-সচেতন scheduler balance করার সময় আগে একই core-এর ভেতরে, তারপর একই socket-এ, আর একেবারে শেষে অন্য socket-এ task সরায় — Linux এই স্তরগুলোকে বলে scheduling domain. Linux-এর automatic NUMA balancing task আর তার page-কে কাছাকাছি আনতে চেষ্টা করে; হাতে নিয়ন্ত্রণের জন্য আছে numactl --cpunodebind=0 --membind=0 ./db.

$ numactl --hardware
available: 2 nodes (0-1)
node 0 cpus: 0 1 2 3 4 5 6 7 16 17 18 19 20 21 22 23
node 0 size: 64326 MB
node 1 cpus: 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31
node 1 size: 64507 MB
node distances:
node   0   1
  0:  10  21
  1:  21  10

node distances একটি আপেক্ষিক মাপ (নিজের node = ১০), ন্যানোসেকেন্ড নয়; এখানে অন্য node প্রায় দ্বিগুণ “দূরে”। সাধারণ ল্যাপটপে একটিই node থাকে।

৪ · Multicore, SMT আর ভিন্ন-স্বভাবের core

Memory stall আর hardware thread

একটি multicore চিপে প্রতিটি core একটি পূর্ণ CPU. কিন্তু core-গুলো তাদের সময়ের একটি বড় অংশ অপেক্ষায় কাটায়: ডেটা cache-এ না থাকলে মেমরি থেকে আসতে প্রায় ১০০ ন্যানোসেকেন্ড লাগতে পারে — আধুনিক CPU-র কয়েকশো clock cycle. এই অপেক্ষার নাম memory stall. মেমরি-ছড়ানো কাজে (ডেটাবেস, গ্রাফ, বড় hash table) core-এর বড় অংশ সময় এভাবে নষ্ট হয়।

সমাধান: একটি core-এ দুই (বা বেশি) সেট register রাখা — অর্থাৎ দুটি hardware thread. একটি thread মেমরির জন্য থেমে থাকলে core অন্যটির নির্দেশ চালায়। এর নাম SMT (simultaneous multithreading); Intel-এর বাজারি নাম Hyper-Threading, যা ২০০২ সালে সার্ভার প্রসেসরে আসে। OS প্রতিটি hardware thread-কে একটি আলাদা logical CPU দেখে — ৮-core, ১৬-thread চিপে nproc বলবে ১৬.

এক hardware thread:   T1 ███▒▒▒▒▒▒███▒▒▒▒▒▒███      (▒ = memory stall, core বসে আছে)
দুই hardware thread:  T1 ███▒▒▒▒▒▒███▒▒▒▒▒▒███
                      T2    ███▒▒▒▒▒▒███▒▒▒▒▒▒███   T1-এর stall-এর সময় core T2 চালায়

দুটি hardware thread মানে দুটি পূর্ণ core নয় — তারা execution unit, L1 আর L2 cache ভাগ করে। কাজের ধরনভেদে লাভ খুব বেশি থেকে প্রায় শূন্য, এমনকি ঋণাত্মকও হতে পারে (দুজনই একই unit চাইলে)। তাই scheduler-এর জন্য দুটি নিয়ম দাঁড়ায়: (১) হাতে যথেষ্ট খালি physical core থাকলে দুটি ব্যস্ত task-কে একই core-এর দুই sibling-এ না রেখে আলাদা core-এ রাখা; (২) একই core-এর sibling-এর মধ্যে task সরানো প্রায় বিনামূল্যে, কারণ cache ভাগের।

ভিন্ন-স্বভাবের core — big.LITTLE আর P/E core

ফোনের চিপে সব core সমান নয়। ARM ২০১১ সালে big.LITTLE ধারণা ঘোষণা করে: কয়েকটি বড়, দ্রুত, বিদ্যুৎ-খেকো core আর কয়েকটি ছোট, ধীর, সাশ্রয়ী core এক চিপে। এটিই heterogeneous multiprocessing. গান শোনা বা নোটিফিকেশন দেখার মতো হালকা কাজ ছোট core-এ চললে ব্যাটারি বাঁচে, আর গেম বা ক্যামেরার প্রসেসিং চায় বড় core. Intel ২০২১ সালের Alder Lake (১২তম প্রজন্ম Core) থেকে ডেস্কটপ আর ল্যাপটপেও একই পথ নেয়: Performance-core (P-core) আর Efficient-core (E-core). Apple-এর M আর A-সিরিজ চিপেও একই ভাগ।

এখন scheduler-এর প্রশ্ন শুধু “কোন CPU খালি” নয়, “কোন ধরনের CPU এই task-এর উপযুক্ত”. Linux-এ এর উত্তরের বড় অংশ Energy Aware Scheduling (EAS), যা মূল kernel-এ এসেছে Linux 5.0 (২০১৯)-এ: প্রতিটি core-এর ক্ষমতা আর বিদ্যুৎ-খরচের মডেল দেখে task রাখা হয়। Intel হার্ডওয়্যারে Thread Director নামের একটি অংশ যোগ করেছে, যা চলমান thread-এর নির্দেশের ধরন দেখে OS-কে ইঙ্গিত দেয় কোন thread P-core-এ বেশি লাভবান হবে; Windows 11 এই ইঙ্গিত ব্যবহার করে, আর Linux-এ এর সমর্থন ধাপে ধাপে যুক্ত হচ্ছে — কোন kernel সংস্করণে কতটুকু, তা নিজের সিস্টেমে মিলিয়ে নেওয়াই নিরাপদ। macOS-এ অ্যাপ core বাছে না, কাজের QoS শ্রেণি জানায় (ভাবনার প্রশ্ন ৪)।

Gang scheduling — একসাথে চালানোর প্রয়োজন

কিছু প্রোগ্রামের thread-গুলো ঘন ঘন একে অপরের জন্য অপেক্ষা করে — যেমন একটি সমান্তরাল হিসাব, যেখানে প্রতিটি ধাপের শেষে সবাই একটি barrier-এ মিলিত হয়। সঙ্গী queue-তে অপেক্ষায় থাকলে চলমান thread barrier-এ বৃথা ঘোরে। Gang scheduling (co-scheduling) এই দলকে একই মুহূর্তে আলাদা আলাদা CPU-তে একসাথে চালায়, আর একসাথে থামায়। ধারণাটি ১৯৮২ সালে John Ousterhout-এর কাজে প্রস্তাবিত; আজ এটি বেশি দেখা যায় বড় সমান্তরাল (HPC) ক্লাস্টার আর কিছু hypervisor-এ, যেখানে একটি virtual machine-এর সব virtual CPU কাছাকাছি সময়ে চালানো দরকার।

৫ · Real-time scheduling-এর ভিত্তি — সময়মতো, গড়ে নয়

পর্ব ২-এ দেখেছেন, real-time সিস্টেম মানে “খুব দ্রুত” নয় — মানে নির্দিষ্ট সময়ের মধ্যে, নিশ্চিতভাবে। hard real-time-এ একটি deadline মিস করাও ব্যর্থতা (airbag, পেসমেকার, বিমানের নিয়ন্ত্রণ); soft real-time-এ মিস হলে মান কমে, কিন্তু সিস্টেম ভাঙে না (ভিডিও কল, গান বাজানো)। Real-time-এর মাপকাঠি গড় নয়, সবচেয়ে খারাপ ক্ষেত্রের সময়।

Latency — ঘটনা থেকে সাড়া পর্যন্ত

একটি সেন্সর সংকেত দিল (যেমন গাড়ির চাকা পিছলে যাচ্ছে)। সাড়া শুরু হওয়া পর্যন্ত মোট সময়কে বলে event latency. এর ভেতরে কয়েকটি টুকরো:

ঘটনা ──► interrupt latency ──► ISR চলে ──► dispatch latency ─────────────────► real-time task চলে
          (চলতি নির্দেশ শেষ,       (task-কে    │ conflict phase           │ dispatch │
           interrupt বন্ধ থাকলে    জাগায়)     │ kernel-এর চলতি কাজ       │ context  │
           তার অপেক্ষা)                        │ preempt; নিচু task-এর    │ switch   │
                                               │ ধরা resource ছাড়া       │          │

• Interrupt latency — interrupt CPU-তে পৌঁছানো থেকে তার ISR শুরু পর্যন্ত। Kernel লম্বা সময় interrupt বন্ধ রাখলে এটি বাড়ে।
• Dispatch latency — scheduler-এর এক task থামিয়ে real-time task চালু করার সময় (পর্ব ৯). এর দুটি অংশ: conflict phase — kernel-এর ভেতরে চলতে থাকা কাজকে preempt করা, আর নিচু অগ্রাধিকারের task-এর ধরে রাখা resource (যেমন একটি lock) ছেড়ে দেওয়ানো; তারপর dispatch phase — আসল context switch.

এখান থেকে দুটি নকশা-নিয়ম আসে: kernel-কে preemptible হতে হবে (নইলে একটি লম্বা system call শেষ না হওয়া পর্যন্ত জরুরি task অপেক্ষা করবে), আর lock-এর ক্ষেত্রে priority inversion ঠেকাতে হবে — নিচু task-এর ধরা lock-এর জন্য উঁচু task আটকে থাকা, যার প্রতিকার priority inheritance (পর্ব ২৯-এ বিস্তারিত)।

Periodic task model

Real-time-এর অনেক কাজ নির্দিষ্ট ছন্দে আসে: প্রতি ১০ ms-এ মোটরের গতি পড়া, প্রতি ২০ ms-এ একটি অডিও বাফার পূরণ। বাস টার্মিনালের সময়সূচির মতো — প্রতি আধা ঘণ্টায় একটি বাস ছাড়ে, আর প্রতিটি বাস পরের বাস ছাড়ার আগেই প্ল্যাটফর্ম খালি করতে হবে। এই ধরনের কাজকে বলে periodic task, আর পাঠ্যবইয়ের মডেলে প্রতিটি task-এর তিনটি সংখ্যা:

সব task-এর মোট utilisation U = Σ c_i/p_i. প্রথম, সবচেয়ে সরল সত্য: এক CPU-তে U > ১ হলে কোনো নীতিই সব deadline রাখতে পারবে না — সময়ের চেয়ে কাজ বেশি। আর আগমনের নকশা প্রতি hyperperiod-এ (সব period-এর লসাগু) হুবহু আবার শুরু হয়, তাই একটি hyperperiod ধরে schedule যাচাই করলেই চলে। কোনো task-গুচ্ছ একটি নীতিতে সব deadline রাখবে কি না, তা আগেই হিসাব করে বলার পদ্ধতিকে বলে schedulability test, আর real-time OS নতুন task নেওয়ার আগে এমন পরীক্ষা চালালে তাকে বলে admission control.

৬ · Rate Monotonic — ছোট period, উঁচু অগ্রাধিকার

১৯৭৩ সালে C. L. Liu আর James W. Layland-এর একটি প্রবন্ধ (Journal of the ACM-এ) real-time scheduling-এর ভিত্তি স্থাপন করে। প্রথম নীতিটি হলো Rate Monotonic (RM): প্রতিটি task পায় একটি স্থির অগ্রাধিকার — যার period যত ছোট (অর্থাৎ rate বা আগমনের হার যত বেশি), তার অগ্রাধিকার তত উঁচু। চলার সময় সবচেয়ে উঁচু অগ্রাধিকারের ready job চলে, আর উঁচু কেউ এলে নিচুকে preempt করে। অগ্রাধিকার কখনো বদলায় না — তাই এটি fixed-priority scheduling.

ছোট period-এর task-এর deadline সবসময় কাছে, তাই সে আগে। Liu আর Layland প্রমাণ করেন, deadline = period হলে সব fixed-priority নীতির মধ্যে RM অনুকূলতম: কোনো task-গুচ্ছ কোনো স্থির অগ্রাধিকার-ক্রমে schedule করা গেলে RM ক্রমেও করা যাবে।

Liu–Layland সীমা

এই Liu–Layland bound সম্পর্কে দুটি কথা পরীক্ষায় বারবার আসে। এক, এটি যথেষ্ট শর্ত, আবশ্যক নয়: U সীমার নিচে হলে নিশ্চিত নিরাপদ; সীমার উপরে হলে উত্তর “জানি না” — সেখানে আরও সূক্ষ্ম পরীক্ষা লাগে। দুই, সীমাটি কখনো ln ২-এর নিচে নামে না, তাই যেকোনো সংখ্যক task-এর মোট U ≤ ০.৬৯৩ হলে RM-এ নিরাপদ।

প্রমাণের রূপরেখা — দুটি task-এর ক্ষেত্রে ০.৮২৮ কোথা থেকে

পুরো প্রমাণ লম্বা, কিন্তু n = ২-এর ক্ষেত্রটি এক অনুচ্ছেদে বোঝা যায়। দুটি ধাপ লাগে।

ধাপ ১ — critical instant: Fixed-priority-তে একটি task-এর সবচেয়ে খারাপ response time হয় তখন, যখন সে আর তার চেয়ে উঁচু সব task একই মুহূর্তে আসে। কারণ উঁচু কারও আগমন পিছিয়ে দিলে আমাদের task-এর সামনে বাধা কেবল কমতে পারে, বাড়তে পারে না। তাই t = ০-তে সবাই একসাথে এলে প্রতিটি task-এর প্রথম job-টি deadline রাখলেই যথেষ্ট।

ধাপ ২ — সবচেয়ে কম U-তে “পুরো ঠাসা” গুচ্ছ খোঁজা: T1-এর period p₁ ছোট, T2-এর p₂, আর ধরুন p₁ < p₂ ≤ ২p₁. Critical instant থেকে p₂ সময়ের মধ্যে T1 আসে দুবার (০ আর p₁-এ)। এমন c বাছি যাতে CPU ঠিক p₂-তে গিয়ে পুরো ঠাসা হয় — অর্থাৎ c একটুও বাড়ালে T2 deadline হারাবে: c₁ = p₂ − p₁ (T1-এর দ্বিতীয় job ঠিক p₂-তে শেষ), আর c₂ = p₂ − ২c₁ = ২p₁ − p₂. এখন r = p₂/p₁ (১ < r ≤ ২) লিখলে

এর সর্বনিম্ন মান খুঁজতে অবকলন শূন্য করি: ১ − ২/r² = ০ ⇒ r = √২. তখন U = √২ + √২ − ২ = ২(√২ − ১) ≈ ০.৮২৮. অর্থাৎ পুরো ঠাসা দুই-task গুচ্ছের মধ্যে সবচেয়ে কম U ০.৮২৮; এর চেয়ে কম U-র কোনো গুচ্ছ পুরো ঠাসা হতে পারে না, তাই deadline-ও হারায় না। Liu আর Layland একই যুক্তি n টি task-এ বাড়িয়ে n(২^১/n − ১) পান (period-অনুপাতগুলো সব ২^১/n হলে সবচেয়ে খারাপ)। p₂ > ২p₁-এর ক্ষেত্রও একই সীমায় নামিয়ে আনা যায় — বিস্তারিত তাঁদের প্রবন্ধে।

সীমা পেরোলে — response-time analysis

সীমার উপরের গুচ্ছের জন্য একটি সঠিক (আবশ্যক ও যথেষ্ট) পরীক্ষা আছে: response-time analysis (RTA). Critical instant থেকে task i-এর response time R_i হলো তার নিজের c_i, আর ওই সময়ের মধ্যে উঁচু অগ্রাধিকারের প্রতিটি task j যতবার আসে, ততবার তার c_j:

এবার তিনটি সমাধান করা উদাহরণ — একটি সীমার নিচে, একটি সীমার উপরে কিন্তু নিরাপদ, আর একটি যেখানে সত্যিই deadline মিস হয়।

সমাধান করা উদাহরণ ১ — সীমার নিচে, তাই নিশ্চিত

প্রশ্ন: A (c = ১, p = ৪), B (c = ১, p = ৫), C (c = ২, p = ১০). RM-এ সব deadline রক্ষা হবে কি?

সমাধান: U = ১/৪ + ১/৫ + ২/১০ = ০.২৫ + ০.২০ + ০.২০ = ০.৬৫. n = ৩-এর সীমা ০.৭৮০. ০.৬৫ ≤ ০.৭৮০, তাই হ্যাঁ, নিশ্চিত — আর কোনো হিসাব লাগে না।

সমাধান করা উদাহরণ ২ — সীমা পেরিয়েছে, তবু নিরাপদ

প্রশ্ন: A (c = ১, p = ৪), B (c = ২, p = ৬), C (c = ৩, p = ১২). RM-এ সব deadline রক্ষা হবে কি?

সমাধান: U = ০.২৫০ + ০.৩৩৩ + ০.২৫০ = ০.৮৩৩ > ০.৭৮০ — সীমার পরীক্ষা কিছুই বলতে পারছে না। RM অগ্রাধিকার: A (p ৪) > B (p ৬) > C (p ১২). এবার RTA:

• A: R_A = ১ ≤ ৪ ✔ (কেউ উঁচু নেই)
• B: শুরু ৩ → ২ + ⌈৩/৪⌉·১ = ৩ → স্থির। R_B = ৩ ≤ ৬ ✔
• C: নিচের stepper-এ ধাপে ধাপে — ফল R_C = ১০ ≤ ১২ ✔

1R0 = 1 + 2 + 3              = 62R1 = 3 + ceil(6/4)*1 + ceil(6/6)*2 = 73R2 = 3 + ceil(7/4)*1 + ceil(7/6)*2 = 94R3 = 3 + ceil(9/4)*1 + ceil(9/6)*2 = 105R4 = 3 + ceil(10/4)*1 + ceil(10/6)*2 = 10

সমাধান করা উদাহরণ ৩ — RM সত্যিই deadline হারায়

প্রশ্ন: P1 (c = ২৫, p = ৫০), P2 (c = ৩৫, p = ৮০). RM-এ কী হবে?

সমাধান: U = ২৫/৫০ + ৩৫/৮০ = ০.৫০০ + ০.৪৩৭৫ = ০.৯৩৭৫ > ০.৮২৮ — সীমা কিছু বলে না। P1-এর period ছোট, তাই P1 উঁচু। RTA: R₂ শুরু ৬০ → ৩৫ + ⌈৬০/৫০⌉·২৫ = ৩৫ + ৫০ = ৮৫ → ৩৫ + ⌈৮৫/৫০⌉·২৫ = ৮৫, স্থির। R₂ = ৮৫ > ৮০ — P2 deadline হারাবে। উল্টো অগ্রাধিকার দিলে (P2 উঁচু) কী হয়? তখন R₁ = ২৫ + ⌈R/৮০⌉·৩৫: শুরু ৬০ → ২৫ + ৩৫ = ৬০ > ৫০ — এবার P1 হারায়। অর্থাৎ কোনো স্থির অগ্রাধিকারেই এই গুচ্ছ চলে না, যদিও U < ১. টাইমলাইনে দেখুন:

1t=0 : P1#1, P2#1 arrive -> P1 (p 50) first2t=25: P1#1 done -> P2#1 runs3t=50: P1#2 arrives -> preempts P2#14t=75: P1#2 done -> P2#1 resumes5t=80: P2#1 deadline, 5 ms still left

৭ · EDF — যার deadline সবচেয়ে কাছে, সে আগে

RM-এর দুর্বলতা উদাহরণ ৩-এ স্পষ্ট: t = ৫০-এ P2#1-এর deadline ছিল ৮০, P1#2-এর ১০০ — তবু স্থির অগ্রাধিকারের কারণে P1 আগে গেল। ঈদের আগের রাতে দর্জি যে অর্ডার কাল সকালে দিতে হবে, সেটি আগে সেলাই করেন, পরের সপ্তাহেরটি পরে। এই নীতির নাম Earliest Deadline First (EDF): প্রতি মুহূর্তে, ready job-গুলোর মধ্যে যার absolute deadline সবচেয়ে কাছে, সে চলে। নতুন job এলে তুলনা আবার হয়, আর দরকার হলে preempt.

একটি task-এর অগ্রাধিকার এখানে স্থির নয় — একই P1 কখনো P2-এর আগে, কখনো পরে, নির্ভর করে তাদের এই মুহূর্তের job-এর deadline-এর ওপর। তাই EDF হলো dynamic-priority scheduling. একই P1/P2 গুচ্ছ এবার EDF-এ দেখুন:

1t=0  : P1#1 d=50, P2#1 d=80 -> P12t=25 : P1#1 done -> P2#13t=50 : P1#2 d=100 vs P2#1 d=80 -> P2 stays4t=60 : P2#1 done (d=80 ok) -> P1#25t=80 : P2#2 d=160 vs P1#2 d=100 -> P1 stays6t=85 : P1#2 done (d=100 ok) -> P2#27t=100: P1#3 d=150 vs P2#2 d=160 -> P1 preempts8t=125: P1#3 done -> P2#2, done at 145

কেন EDF অনুকূলতম — exchange argument

উপপাদ্য: এক CPU-তে, preemption চালু থাকলে, কোনো job-গুচ্ছের জন্য যদি কোনো একটি schedule থাকে যেখানে সব deadline রক্ষা হয়, তাহলে EDF-ও সব deadline রক্ষা করবে। (এই ফল সাধারণত Dertouzos-এর ১৯৭৪ সালের কাজের সাথে যুক্ত; periodic task-এর জন্য Liu আর Layland ১৯৭৩-এ EDF-এর সীমা দেখান।)

প্রমাণের রূপরেখা: ধরুন S একটি সফল schedule, কিন্তু EDF নয়। সময়রেখা ধরে এগোলে প্রথম একটি মুহূর্ত t পাওয়া যাবে, যেখানে S চালাচ্ছে job J_b, অথচ তখন ready আছে আরেকটি job J_a, যার deadline আগে: d_a < d_b. S সফল, তাই J_a কোথাও না কোথাও t-এর পরে কিন্তু d_a-এর আগে চলে শেষ হয়। এখন অদলবদল করি: t-তে J_b-এর পাওয়া এক টুকরো সময় (δ) দিই J_a-কে, আর J_a-এর পরের কোনো এক টুকরো (যা d_a-এর আগে) দিই J_b-কে। ফল: J_a আগের চেয়ে দেরিতে শেষ হয় না; J_b-এর কাজ সরে গেল এমন সময়ে, যা d_a-এর আগে, আর d_a < d_b — তাই J_b-ও নিরাপদ। বাকি কারও কিছু বদলায়নি। এভাবে প্রতিটি “ভুল-ক্রমের” মুহূর্ত সামনে থেকে একে একে সারালে S বদলে EDF schedule হয়, আর কোনো ধাপে কোনো deadline ভাঙে না। ∎

Periodic task-এ (d = p) এর সরাসরি ফল: U ≤ ১ হলেই EDF সব deadline রাখে, আর U > ১ হলে কেউই পারে না (একটি hyperperiod H-এ কাজ U·H > H). অর্থাৎ EDF-এর schedulability test নিখুঁত — আবশ্যক এবং যথেষ্ট। RM-এর ক্ষেত্রে সীমা ০.৬৯৩ থেকে ১-এর মধ্যে, আর মাঝের এলাকায় RTA লাগে।

নিজে চালিয়ে দেখুন — RM আর EDF simulator

নিচের simulator প্রতিটি ms-এ সিদ্ধান্ত নেয়: RM-এ অগ্রাধিকার = period, EDF-এ অগ্রাধিকার = job-এর deadline (ছোট মানে উঁচু; সমান হলে তালিকার আগের task). পুরো hyperperiod চালিয়ে টাইমলাইন আর deadline মিসের তালিকা ছাপে, সঙ্গে Liu–Layland সীমার পরীক্ষা। Deadline-এ শেষ না হওয়া job-কে বাদ দেওয়া হয় (hard real-time-এ দেরির ফল কাজে লাগে না)। শেষ লাইনে নিজের task-গুচ্ছ বসিয়ে দেখুন।

// Periodic tasks: c = execution time, p = period, deadline = end of period (ms)
function analyse(tasks) {
  const gcd = (a, b) => (b ? gcd(b, a % b) : a);
  const H = tasks.reduce((h, t) => (h * t.p) / gcd(h, t.p), 1);      // hyperperiod
  const n = tasks.length, U = tasks.reduce((s, t) => s + t.c / t.p, 0);
  const bound = n * (Math.pow(2, 1 / n) - 1);
  console.log(tasks.map(t => `${t.name}(c=${t.c},p=${t.p})`).join(" ") + `  hyperperiod=${H}`);
  console.log(`U=${U.toFixed(3)}  RM bound=${bound.toFixed(3)} -> ` +
    (U <= bound ? "RM surely OK" : "bound test inconclusive") + `;  EDF needs U<=1: ${U <= 1}`);
  for (const policy of ["RM", "EDF"]) {
    const jobs = [], segs = [], misses = [];
    for (let t = 0; t <= H; t++) {
      for (const j of jobs) if (j.left > 0 && j.dl === t) { misses.push(`${j.id} at t=${t}`); j.left = 0; }
      if (t === H) break;
      tasks.forEach((k, i) => { if (t % k.p === 0) jobs.push({ i, id: `${k.name}#${t / k.p + 1}`, left: k.c, dl: t + k.p }); });
      const key = j => (policy === "RM" ? tasks[j.i].p : j.dl);   // smaller = higher priority
      const ready = jobs.filter(j => j.left > 0).sort((a, b) => key(a) - key(b) || a.i - b.i);
      const who = ready.length ? (ready[0].left--, ready[0].id) : "idle";
      const last = segs[segs.length - 1];
      if (last && last.who === who) last.end = t + 1; else segs.push({ who, start: t, end: t + 1 });
    }
    console.log(`${policy}: ` + segs.map(s => `${s.start}-${s.end} ${s.who}`).join(" | "));
    console.log(`  deadline misses: ${misses.length ? misses.join(", ") : "none"}`);
  }
}
analyse([{ name: "P1", c: 25, p: 50 }, { name: "P2", c: 35, p: 80 }]);
analyse([{ name: "A", c: 1, p: 4 }, { name: "B", c: 2, p: 6 }, { name: "C", c: 3, p: 12 }]);

P1(c=25,p=50) P2(c=35,p=80)  hyperperiod=400
U=0.938  RM bound=0.828 -> bound test inconclusive;  EDF needs U<=1: true
RM: 0-25 P1#1 | 25-50 P2#1 | 50-75 P1#2 | 75-80 P2#1 | 80-100 P2#2 | 100-125 P1#3 | 125-140 P2#2 | 140-150 idle | 150-175 P1#4 | 175-200 P2#3 | 200-225 P1#5 | 225-235 P2#3 | 235-240 idle | 240-250 P2#4 | 250-275 P1#6 | 275-300 P2#4 | 300-325 P1#7 | 325-350 P2#5 | 350-375 P1#8 | 375-385 P2#5 | 385-400 idle
  deadline misses: P2#1 at t=80
EDF: 0-25 P1#1 | 25-60 P2#1 | 60-85 P1#2 | 85-100 P2#2 | 100-125 P1#3 | 125-145 P2#2 | 145-150 idle | 150-175 P1#4 | 175-210 P2#3 | 210-235 P1#5 | 235-240 idle | 240-250 P2#4 | 250-275 P1#6 | 275-300 P2#4 | 300-325 P1#7 | 325-350 P2#5 | 350-375 P1#8 | 375-385 P2#5 | 385-400 idle
  deadline misses: none
A(c=1,p=4) B(c=2,p=6) C(c=3,p=12)  hyperperiod=12
U=0.833  RM bound=0.780 -> bound test inconclusive;  EDF needs U<=1: true
RM: 0-1 A#1 | 1-3 B#1 | 3-4 C#1 | 4-5 A#2 | 5-6 C#1 | 6-8 B#2 | 8-9 A#3 | 9-10 C#1 | 10-12 idle
  deadline misses: none
EDF: 0-1 A#1 | 1-3 B#1 | 3-4 C#1 | 4-5 A#2 | 5-6 C#1 | 6-8 B#2 | 8-9 A#3 | 9-10 C#1 | 10-12 idle
  deadline misses: none

তাহলে সবাই EDF ব্যবহার করে না কেন?

শিল্পে fixed-priority এখনো বেশি প্রচলিত (ভাবনার প্রশ্ন ৩); তবে EDF-ও আছে — Linux-এর SCHED_DEADLINE, আর Zephyr-এর মতো কিছু RTOS-এ ঐচ্ছিকভাবে।

Proportional-share scheduling — এক নজরে

Real-time-এর আরেকটি দৃষ্টিভঙ্গি deadline নয়, ভাগ নিয়ে ভাবে। Proportional-share scheduling-এ মোট T টি share থাকে, আর একটি কাজ N টি share পেলে সে CPU-র N/T অংশ সময়ের নিশ্চয়তা পায়। ধরুন T = ১০০; A, B, C পেল ৫০, ১৫ আর ২০ — অর্থাৎ ৫০%, ১৫% আর ২০%. এখন D ৩০ share চাইলে মোট ১১৫ হয় — তাই admission control D-কে ফিরিয়ে দেয়। বিখ্যাত বাস্তবায়ন lottery scheduling (Waldspurger ও Weihl, ১৯৯৪): share-এর অনুপাতে টিকিট, প্রতি quantum-এ একটি টিকিট টানা। Linux-এর সাধারণ scheduler-এর nice-ভিত্তিক “weight”-ও আসলে একধরনের proportional share (পর্ব ২১)।

৮ · বাস্তব OS-এ — SCHED_FIFO, SCHED_RR আর SCHED_DEADLINE

POSIX মানদণ্ড দুটি real-time নীতি ঠিক করেছে, আর Linux একটি যোগ করেছে। সব real-time নীতিই সাধারণ (SCHED_OTHER, Linux-এর fair scheduler) task-এর আগে চলে — অর্থাৎ একটি runnable real-time task থাকলে সাধারণ কেউ সেই CPU পায় না।

$ chrt -m                                  # priority range of every policy
SCHED_OTHER min/max priority	: 0/0
SCHED_FIFO min/max priority	: 1/99
SCHED_RR min/max priority	: 1/99
SCHED_BATCH min/max priority	: 0/0
SCHED_IDLE min/max priority	: 0/0
SCHED_DEADLINE min/max priority	: 0/0

$ sudo chrt -f 50 ./motor_ctl              # start with SCHED_FIFO, priority 50
$ sudo chrt -r -p 20 4242                  # switch running PID 4242 to SCHED_RR, priority 20
$ chrt -p 4242
pid 4242's current scheduling policy: SCHED_RR
pid 4242's current scheduling priority: 20

# SCHED_DEADLINE: 2 ms of CPU every 10 ms, finished within 10 ms (all values in ns)
$ sudo chrt -d --sched-runtime 2000000 --sched-deadline 10000000 \
               --sched-period 10000000 0 ./control_loop

$ cat /proc/sys/kernel/sched_rt_runtime_us /proc/sys/kernel/sched_rt_period_us
950000
1000000

কয়েকটি বিষয় খেয়াল করুন। এক, অনুমতি: real-time নীতি নিতে root, CAP_SYS_NICE, বা RLIMIT_RTPRIO-এ অনুমোদিত সীমা লাগে — তাই অংশ ২-এ Operation not permitted. দুই, SCHED_DEADLINE-এর জন্য অগ্রাধিকার সবসময় 0, আর runtime ≤ deadline ≤ period হতে হয়; নতুন task নিলে মোট ব্যান্ডউইথ সীমা ছাড়ালে kernel admission control-এ অনুরোধ ফিরিয়ে দেয় (Device or resource busy). তিন, শেষ দুটি সংখ্যা RT throttling: ডিফল্টে প্রতি ১ সেকেন্ডে real-time task-গুলো সর্বোচ্চ ০.৯৫ সেকেন্ড পায়, যাতে একটি ভুল SCHED_FIFO লুপ পুরো সিস্টেম আটকে না দেয়; বাকি ৫% সময়ে অন্তত shell খুলে তাকে থামানো যায়।

প্রোগ্রামের ভেতর থেকে একই কাজ sched_setscheduler() দিয়ে হয় (POSIX), আর SCHED_DEADLINE-এর জন্য Linux-এর নিজস্ব sched_setattr():

struct sched_param sp = { .sched_priority = 50 };
if (sched_setscheduler(0, SCHED_FIFO, &sp) != 0)
    perror("sched_setscheduler");        /* EPERM for normal users */
/* real-time loops should also lock memory: page faults add latency */
mlockall(MCL_CURRENT | MCL_FUTURE);

Windows-এ ধারণা কাছাকাছি, নাম আলাদা। Thread-এর অগ্রাধিকার ০–৩১; ১৬–৩১ হলো “real-time” স্তর, যা পাওয়া যায় প্রসেসকে REALTIME_PRIORITY_CLASS দিলে (প্রশাসকের অধিকার লাগে)। তবে Windows hard real-time OS নয় — driver-এর interrupt আর DPC-এর সময়ের কঠোর ঊর্ধ্বসীমা নেই। আর সত্যিকারের hard real-time-এর জন্য আলাদা RTOS — FreeRTOS, Zephyr, VxWorks, QNX — যেখানে সাধারণত fixed-priority preemptive scheduling, আর সবচেয়ে খারাপ ক্ষেত্রের latency মাপা ও নথিভুক্ত (পর্ব ৫৪)।

৯ · AI-এর যুগে multiprocessor আর real-time scheduling

“কোন core-এ pin করব?” বা “এই task-গুচ্ছ RM-এ চলবে কি?” — AI দ্রুত উত্তর দেয়, ভুলও করে আত্মবিশ্বাসী সুরে। সাধারণ ভুল আর যাচাইয়ের পথ:

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

• U আর Liu–Layland সীমা নিজে হিসাব করেছি, আর “সীমা পেরোলেই অচল” ধরনের দাবি বাদ দিয়েছি
• RTA-র প্রতিটি পুনরাবৃত্তি হাতে মিলিয়েছি, আর Gantt chart একটি simulator-এ চালিয়ে দেখেছি
• কমান্ডগুলো আমার OS-এর (Linux বনাম Windows বনাম macOS) কি না, man taskset / man chrt দেখে নিশ্চিত হয়েছি
• Pinning বা real-time অগ্রাধিকারের আগে-পরে একই লোডে latency আর throughput মেপেছি; “আমার মেশিনে চলে” যথেষ্ট মনে করিনি
• sudo chrt -f 99, RT throttling বন্ধ, বা সব কিছু এক core-এ বাঁধার মতো ঝুঁকিপূর্ণ পরামর্শ মানিনি
• Kernel-সংস্করণ-নির্ভর দাবি (যেমন EEVDF, Thread Director-এর সমর্থন) kernel-এর ডকুমেন্টেশনে মিলিয়েছি