Scheduler Simulator

কেন এই প্রজেক্ট

Scheduling policy নিয়ে পড়া আর সেগুলো চালিয়ে দেখা — সম্পূর্ণ আলাদা অভিজ্ঞতা। “SJF optimal” পড়লে মনে হয় তাহলে সবাই SJF ব্যবহার করে না কেন? Simulator চালালে সাথে সাথে উত্তর পাওয়া যায়: একটা লম্বা job অনন্তকাল অপেক্ষা করে।

এই প্রজেক্টের আসল মূল্য হলো trade-off গুলো সংখ্যায় দেখা। Quantum ছোট করলে response time ভালো হয় কিন্তু context switch overhead বাড়ে — কোথায় ভারসাম্য? আপনার simulator সেটা বলে দেবে।

আর একটা বাড়তি সুবিধা: এটা Level 0-এর probability আর asymptotics-এর সরাসরি প্রয়োগ। Workload generate করতে distribution লাগবে, আর metric তুলনা করতে পরিসংখ্যান।

Model

from dataclasses import dataclass, field

@dataclass
class Job:
    jid: int
    arrival: int
    burst: int
    nice: int = 0
    # simulator যা ভরবে
    start: int | None = None
    finish: int | None = None
    remaining: int = field(init=False)
    first_run: int | None = None
    def __post_init__(self):
        self.remaining = self.burst

    @property
    def turnaround(self):  return self.finish - self.arrival
    @property
    def response(self):    return self.first_run - self.arrival
    @property
    def waiting(self):     return self.turnaround - self.burst

Metric — আর তারা কেন পরস্পরবিরোধী

Metric	সংজ্ঞা	কে চায়
Turnaround	`finish − arrival`	batch job
Response	`first_run − arrival`	interactive user
Waiting	`turnaround − burst`	fairness
Throughput	সময়প্রতি সম্পন্ন job	system operator

SJF turnaround-এ optimal — কিন্তু response time-এ ভয়ানক হতে পারে লম্বা job-এর জন্য। RR response-এ ভালো কিন্তু turnaround-এ খারাপ। কোনো একটা policy সব metric-এ জিততে পারে না, আর সেটা প্রমাণযোগ্য।

Policy গুলো

FIFO — convoy effect দেখান

def fifo(jobs):
    t, done = 0, []
    for j in sorted(jobs, key=lambda j: j.arrival):
        t = max(t, j.arrival)
        j.first_run = t
        t += j.burst
        j.finish = t
        done.append(j)
    return done

এই workload দিয়ে চালান:

jobs = [Job(0, 0, 100), Job(1, 1, 2), Job(2, 2, 2)]

ছোট দুইটা job ১০০ tick অপেক্ষা করবে। গড় turnaround ~৭০। এটাই convoy effect — আর এটাই supermarket-এ একজন ভরা ট্রলি নিয়ে দাঁড়ালে যা হয়।

SJF — optimal, কিন্তু…

একই workload-এ গড় turnaround নাটকীয়ভাবে কমবে। তারপর একটা লম্বা job যোগ করে ক্রমাগত ছোট job আসতে দিন — লম্বাটা কখনো চলবে না। Starvation।

Round Robin — quantum-এর curve

for q in [1, 2, 4, 8, 16, 32, 64]:
    result = round_robin(jobs, quantum=q, switch_cost=1)
    print(f"q={q:3d}  response={avg_response(result):6.2f}  "
          f"turnaround={avg_turnaround(result):6.2f}  "
          f"overhead={switches(result) * 1}")

একটা U-আকৃতির curve পাবেন — quantum খুব ছোটে overhead গিলে ফেলে, খুব বড়ে RR কার্যত FIFO হয়ে যায়। সেই সর্বনিম্ন বিন্দুটাই বাস্তব OS-এর quantum নির্বাচনের যুক্তি।

MLFQ — gaming আর boost

MLFQ-র নিয়ম:

উঁচু priority আগে চলে
একই priority-তে RR
পুরো quantum ব্যবহার করলে priority কমে
আগে ছেড়ে দিলে (I/O) priority একই থাকে
পর্যায়ক্রমে সবাইকে সর্বোচ্চ priority-তে boost

নিয়ম ৪-এর ফাঁক: একটা job যদি quantum শেষ হওয়ার ঠিক আগে একটা অর্থহীন I/O করে, সে চিরকাল উঁচু priority-তে থাকবে। এটা simulate করুন — তারপর নিয়ম ৫ (boost) চালু করে দেখুন সেটা কীভাবে ঠিক হয়।

CFS — vruntime

def cfs_pick(runnable):
    return min(runnable, key=lambda j: j.vruntime)

def advance(job, delta):
    weight = NICE_TO_WEIGHT[job.nice]
    job.vruntime += delta * (NICE_TO_WEIGHT[0] / weight)

Nice ০ আর nice ৫ -এর দুইটা busy job চালিয়ে CPU share মাপুন — অনুপাত 1.25^5 ≈ 3.05 হওয়া উচিত। এটা Linux-এ সরাসরি যাচাই করা যায়, আর আপনার simulator একই সংখ্যা দেওয়া উচিত।

Gantt chart

FIFO
  0    10   20   30   40   50
  |....|....|....|....|....|
  AAAAAAAAAABBBCCCCC
  
RR (q=2)
  ABABABABCBCBCACACA

Text-এ আঁকা যথেষ্ট — উদ্দেশ্য দৃশ্যমান করা, সুন্দর করা নয়।

চূড়ান্ত তুলনা

workload: 20 jobs, burst ~ exponential(mean=10), arrival ~ poisson

policy       avg_turn   avg_resp   max_wait   switches
──────────────────────────────────────────────────────
FIFO           88.4       78.2       201          19
SJF            52.1       42.0       178          19
SRTF           48.7       12.3       182          47
RR(q=4)        94.2        6.1        38         112
MLFQ           61.5        7.8        55          73
CFS            63.2        9.4        41          68

এই টেবিলটাই প্রজেক্টের চূড়ান্ত ফল — আর এখান থেকেই বোঝা যায় কেন বাস্তব OS MLFQ/CFS বেছে নেয়: কোনো একটা কলামে সেরা নয়, কিন্তু কোনোটাতেই ভয়াবহ নয়।

নিজেকে চ্যালেঞ্জ করুন

I/O-bound job যোগ করুন (burst-এর মাঝে block হয়) — এখানেই MLFQ-র আসল সুবিধা দেখা যায়
Multi-core — n টা CPU, per-CPU runqueue, আর load balancing
Priority inversion simulate করুন, তারপর priority inheritance দিয়ে ঠিক করুন (Mars Pathfinder-এর গল্পটা পুনর্নির্মাণ)
আপনার simulator-এর ফল বাস্তব Linux-এর সাথে মেলান — একই nice value দিয়ে দুইটা busy loop চালিয়ে /proc/<pid>/stat থেকে utime পড়ুন
EEVDF যোগ করুন আর CFS-এর সাথে latency তুলনা করুন

মাইলস্টোন

আগে যা পড়া দরকার