সরাসরি পর্বে যান
পর্ব ৬০ · ৬৪-এর মধ্যে · মডিউল ১০

Numerical সমস্যা — scheduling, page replacement, Banker's আর disk

Operating Systems Numericals — Fully Worked Problems on Scheduling, Synchronization, Deadlock, Memory, Paging, Disk, File Systems, RAID and Queueing

Taught in Bangla, this page collects fully worked operating systems numericals with answer-layout tips: CPU utilization, AMAT, context switch and fork counting, Amdahl's law, FCFS, SJF, SRTF, HRRN, priority, Round Robin, MLFQ and real-time scheduling, semaphore traces and Banker's algorithm, fits, buddy, paging, TLB and segmentation, page replacement and working sets, and disk, file system, RAID and queueing problems.

এই পর্বে যা পাবেন

  • প্রতিটি numerical-এর সূত্র, নিয়ম (convention) আর সাধারণ ফাঁদ এক পাতায়
  • Gantt chart, Need-Work টেবিল, frame টেবিল আর head-movement হিসাব এমনভাবে লেখার অভ্যাস, যাতে পরীক্ষক প্রতিটি ধাপ মেলাতে পারেন
  • FCFS থেকে MLFQ, RM/EDF, Banker's-এর request ও detection, FIFO/OPT/LRU/Clock আর ছয়টি disk অ্যালগরিদমের পূর্ণ সমাধান
  • উল্টো দিকের প্রশ্ন সামলানো: “ন্যূনতম hit ratio কত?”, “সর্বোচ্চ fault rate কত?”, “সর্বোচ্চ কতটি প্রসেস?”
  • ক্যালকুলেটর দিয়ে নিজের উত্তর মেলানো, আর AI-এর দেওয়া numerical সন্দেহের চোখে দেখা

১ · পাতার মানচিত্র আর খাতায় উত্তর সাজানোর কৌশল

মডিউল ১০-এ স্বাগতম। প্রথম ৫৯টি পর্বে আপনি অপারেটিং সিস্টেম শিখেছেন; এই পাঁচটি পর্বে সেই জ্ঞান পরীক্ষার খাতায়, MCQ-এর ঘড়ির সামনে আর ইন্টারভিউর টেবিলে কাজে লাগানোর অনুশীলন। শুরু করছি numerical দিয়ে, কারণ বিশ্ববিদ্যালয়ের OS কোর্সের লিখিত পরীক্ষা থেকে চাকরির লিখিত পরীক্ষা পর্যন্ত — এ ধরনের প্রশ্ন প্রায়ই আসে, আর এখানে নম্বর পুরোপুরি পাওয়া যায় যদি পদ্ধতি পরিষ্কার থাকে।

Numerical-এ ভুল সাধারণত সূত্রে হয় না, হয় নিয়মে। একই process table-এ দুজন ছাত্র দুটি ভিন্ন Gantt chart আঁকতে পারেন, আর দুজনেই “ঠিক” — যদি একজন ধরেন একই মুহূর্তে আসা নতুন প্রসেস আগে সারিতে ঢোকে আর অন্যজন উল্টোটা। তাই এই পাতার প্রতিটি প্রশ্নে নিয়ম লেখা আছে, আর আপনার খাতাতেও উত্তরের প্রথম লাইনে নিয়ম লেখা থাকা উচিত।

কোন ভাগে কী, কোন পর্ব ঝালাবেন

ভাগকী আছেমূল পর্ব
২1 − pⁿ, AMAT ও cache-এর EAT, q/(q + s), fork গোনা, Amdahl০২, ০৪, ০৯, ১০, ১৪
৩FCFS, SJF, SRTF, HRRN — idle ফাঁকসহ; scheduler ক্যালকুলেটর১৬, ১৭
৪Priority (দুই রূপ), Round Robin, MLFQ, RM আর EDF১৮, ১৯, ২০
৫Semaphore trace, n(k − 1) + 1, Banker's safety, request আর detection২৪, ২৭, ২৮
৬Fit কৌশল, buddy, address translation, page-table-এর আকার, TLB, segmentation৩১–৩৪
৭Demand paging-এর EAT, FIFO/OPT/LRU/Clock, Belady, frame ভাগ, working set৩৫–৩৭
৮Disk access time ও scheduling, buffering, inode, FAT, bitmap, RAID, M/M/1৩৯, ৪০, ৪৩, ৪৫, ৫৭

এই পাতার নিয়ম (convention) — প্রশ্নে অন্য কিছু না বললে

বিষয়নিয়ম
Scheduling-এর মাপTAT = CT − AT; WT = TAT − BT; RT = প্রথমবার CPU পাওয়া − AT; context switch-এর খরচ ০
TiePreemptive নীতিতে চলতি প্রসেস চলতে থাকে; তারপর আগে আসা; তারপর টেবিলের ক্রম (ছোট index)
Priorityছোট সংখ্যা = বেশি অগ্রাধিকার
Round Robinএকই মুহূর্তে নতুন আগমন আর quantum ফুরানো হলে নতুন প্রসেস আগে সারিতে, তারপর থামানো প্রসেস
MLFQনতুন প্রসেস সবচেয়ে ওপরের queue-তে; পুরো quantum খেলে এক স্তর নিচে; ওপরে কেউ এলে নিচের জন থামে আর নিজের queue-এর সামনে থাকে
Banker'sপ্রতিবার P0 থেকে খোঁজা শুরু, প্রথম যে চলতে পারে সে চলে (সবচেয়ে ছোট index আগে)
Page replacementখালি frame বাঁ থেকে ভরে; OPT-এ একাধিক page আর কখনো না লাগলে আগে আনা জন যায়; Clock-এ প্রতিটি ছোঁয়ায় বিট ১
DiskSSTF-এ সমান দূরত্বে ছোট cylinder আগে; C-SCAN/C-LOOK-এর মোট দুভাবে — ফেরার লাফ ধরে আর বাদে
এককKiB = 1024 byte, MiB = 220; ডিস্কের MB/s = 106 byte/s; সময় ms, µs, ns আলাদা করে লিখুন
পরীক্ষার কৌশল — খাতায় উত্তর সাজানোর সাত নিয়ম

১. নিয়ম ঘোষণা করুন। প্রথম লাইনে লিখুন: “ধরে নিলাম: tie-তে আগে আসা প্রসেস; RR-এ নতুন আগমন আগে; context switch ০.” প্রশ্নে না থাকলে এটাই আপনার রক্ষাকবচ।

২. সূত্র আগে, মান পরে। “EAT = h(t + m) + (1 − h)(t + 2m)” লিখে তারপর সংখ্যা বসান। মাঝপথে গণনায় ভুল হলেও সূত্রের নম্বর থাকে।

৩. Gantt chart পুরো আঁকুন। প্রতিটি খোপের নিচে শুরু আর শেষের সময়, idle ফাঁক আলাদা খোপে “idle” লিখে। Preemptive অ্যালগরিদমে প্রতিটি arrival-এ ready queue-র অবস্থা পাশে লিখুন।

৪. টেবিলে উত্তর দিন। কলাম: প্রসেস, AT, BT, CT, TAT, WT (চাইলে RT). শেষ সারিতে যোগফল আর গড় — ভগ্নাংশ আর দশমিক দুটোই (যেমন ১৩/৫ = ২.৬০)।

৫. একক লিখুন, রূপান্তর দেখান। “৬ ms = ৬,০০০,০০০ ns” এক লাইনে দেখালে ns আর ms মিশে যাওয়ার ভুল ধরা পড়ে। KiB আর KB, MiB আর MB আলাদা।

৬. একটি চেক-যোগফল দিন। ΣWT = ΣTAT − ΣBT; Banker's-এর শেষে Work = মোট resource; page replacement-এ hit + fault = string-এর দৈর্ঘ্য; Gantt-এর শেষ সময় = মোট burst + মোট idle.

৭. শেষ উত্তর আলাদা করুন আর এক লাইনের মন্তব্য দিন। “গড় WT = ২.০০ ms; SRTF সবচেয়ে কম, কিন্তু P1 দুবার থেমেছে” — তুলনার প্রশ্নে এই এক লাইনেই অনেক সময় পূর্ণ নম্বর।

সময়ের হিসাব: পাঁচ প্রসেসের একটি preemptive Gantt chart আর টেবিলে ১০–১২ মিনিট লাগতে পারে। পরীক্ষায় আগে টেবিলের কাঠামো (কলাম, প্রসেসের নাম, AT, BT) এঁকে নিন — সময় ফুরালেও কাঠামো আর প্রথম কয়েকটি সারিতে নম্বর থাকে। এই পাতার ড্রিল একবার ঘড়ি ধরে করুন।

২ · ভিত্তির হিসাব — CPU ব্যবহার, AMAT, context switch, fork আর Amdahl

ঝালিয়ে নিন: পর্ব ০২ · OS-এর ইতিহাস আর ধরন, পর্ব ০৪ · OS-এর চোখে হার্ডওয়্যার, পর্ব ০৯ · Context switch, পর্ব ১০ · fork, exec আর wait, পর্ব ১৪ · থ্রেড.

সূত্রের কার্ড

CPU ব্যবহার (multiprogramming): প্রতিটি কাজ সময়ের p অংশ I/O-র অপেক্ষায় থাকলে, মেমরিতে n টি কাজ রাখলে CPU ব্যস্ত ≈ 1 − pⁿ (কাজগুলো স্বাধীন ধরে নেওয়া আনুমানিক মডেল)।

AMAT: hit time + miss rate × miss penalty; দুই স্তরে H₁ + m₁(H₂ + m₂ · Tmem), যেখানে m₂ হলো L2-এর local miss rate. Cache-এর EAT-এর দুই রীতি: স্তর ধরে (hierarchical) h·tc + (1 − h)(tc + tm), একসাথে খোঁজা (simultaneous) h·tc + (1 − h)·tm.

Context switch-এর দক্ষতা: প্রতিটি প্রসেস পুরো quantum q চালালে আর প্রতি switch-এ s খরচ হলে efficiency = q/(q + s); burst T < q হলে T/(T + s).

fork গোনা: পরপর n টি fork → 2ⁿ টি প্রসেস, নতুন 2ⁿ − 1. && আর || থাকলে প্রতিটি fork-এর ফল (parent-এ ধনাত্মক, child-এ 0) ধরে গাছ আঁকুন।

Amdahl: speedup = 1 / ((1 − f) + f/N); N → ∞ হলে সীমা 1/(1 − f).

উদাহরণ ২.১ (সহজ) — 1 − pⁿ

প্রশ্ন: প্রতিটি কাজ সময়ের ৭০% I/O-র জন্য অপেক্ষা করে। মেমরিতে ১, ২ আর ৪টি কাজ থাকলে CPU কত শতাংশ সময় ব্যস্ত?

p = 0.7
n = 1 : 1 - 0.7   = 0.30   -> 30%
n = 2 : 1 - 0.49  = 0.51   -> 51%
n = 4 : 1 - 0.2401 = 0.7599 -> 76.0%

দুটি কাজে ব্যবহার ৩০% থেকে ৫১% — প্রায় দ্বিগুণ নয়, কারণ দুটি কাজ কখনো কখনো একসাথেই I/O-তে থাকে। বৃদ্ধি ক্রমশ কমে আসে।

উদাহরণ ২.২ (মাঝারি) — উল্টো প্রশ্ন: ন্যূনতম n

প্রশ্ন: একই p = ০.৭-এ CPU-কে অন্তত ৯০% ব্যস্ত রাখতে মেমরিতে ন্যূনতম কতটি কাজ লাগবে?

1 - 0.7^n >= 0.9   =>   0.7^n <= 0.1   =>   n >= ln 0.1 / ln 0.7 = 6.46
n = 6 : 1 - 0.7^6 = 0.8824  (not enough)
n = 7 : 1 - 0.7^7 = 0.9176  -> answer n = 7

log নেওয়ার সময় ln ০.৭ ঋণাত্মক, তাই অসমতার দিক উল্টে যায় — এখানেই অনেকে ভুল করেন। ৬.৪৬ পূর্ণসংখ্যা নয়, তাই ওপরের দিকে গোল করে ৭, আর দুটি পাশের মান বসিয়ে যাচাই দেখান।

উদাহরণ ২.৩ (কঠিন) — RAM দিয়ে n নির্ধারণ

প্রশ্ন: ১৬ GiB RAM-এর ২ GiB OS নেয়, প্রতিটি কাজ ১.৫ GiB চায়, I/O অপেক্ষা ৮০%. CPU ব্যবহার কত? RAM ৩২ GiB করলে কত?

jobs = floor((16 - 2) / 1.5) = floor(9.33) = 9    util = 1 - 0.8^9  = 0.8658 -> 86.6%
jobs = floor((32 - 2) / 1.5) = floor(20)   = 20   util = 1 - 0.8^20 = 0.9885 -> 98.8%

RAM দ্বিগুণে কাজের সংখ্যা দ্বিগুণের বেশি (৯ → ২০), কারণ OS-এর অংশ স্থির। তবু ব্যবহার বাড়ল মাত্র ১২ শতাংশ-বিন্দু — উঁচু ব্যবহারে বাড়তি মেমরির লাভ কম।

উদাহরণ ২.৪ (মাঝারি) — দুই স্তরের AMAT

প্রশ্ন: L1 hit = ২ cycle, L1 miss rate ৫%; L2 hit = ১২ cycle, L2-এর local miss rate ৩০%; RAM = ১৫০ cycle. AMAT কত? L2 না থাকলে কত? Global miss rate কত?

AMAT  = 2 + 0.05 x (12 + 0.30 x 150) = 2 + 0.05 x 57 = 4.85 cycles
no L2 = 2 + 0.05 x 150               = 9.5 cycles
global miss rate (reach RAM) = 0.05 x 0.30 = 0.015 = 1.5%

L2 যোগ করায় AMAT প্রায় অর্ধেক। ফাঁদ: প্রশ্নে L2-এর global miss rate (এখানে ১.৫%) দেওয়া থাকলে সেটিকে local ধরে ওপরের সূত্রে বসালে ভুল আসে; তখন সূত্র H₁ + m₁·H₂ + (global miss rate) × Tmem = ২ + ০.৬ + ২.২৫ = ৪.৮৫ — প্রশ্নে “local” না “global” লেখা, দেখে নিন।

উদাহরণ ২.৫ (মাঝারি) — cache-এর EAT, দুই রীতি

প্রশ্ন: Cache hit ratio ০.৯৫, cache access ৫ ns, মেমরি ৬০ ns. দুই রীতিতে effective access time কত?

hierarchical : 0.95 x 5 + 0.05 x (5 + 60) = 4.75 + 3.25 = 8.00 ns
simultaneous : 0.95 x 5 + 0.05 x 60       = 4.75 + 3.00 = 7.75 ns

পার্থক্য শুধু miss-এর পথে: স্তর ধরে খুঁজলে miss-এ cache দেখার ৫ ns-ও যায়। প্রশ্নে রীতি বলা না থাকলে hierarchical ধরে লিখে দিন।

উদাহরণ ২.৬ (সহজ → কঠিন) — q/(q + s)

প্রশ্ন: Context switch ০.৫ ms. (ক) q = ৪ ms আর q = ১ ms-এ efficiency? (খ) প্রসেসগুলো ৩ ms চলেই I/O-তে যায়, q = ৪ — efficiency? (গ) ৯৫% efficiency-র জন্য ন্যূনতম q? (ঘ) ৬টি প্রসেস, q = ৪: একটি প্রসেস সর্বোচ্চ কত অপেক্ষার পর আবার CPU পায়?

(a) 4 / 4.5 = 88.9%        1 / 1.5 = 66.7%
(b) burst 3 < q: 3 / 3.5 = 85.7%
(c) q / (q + 0.5) >= 0.95  =>  q >= 0.95 x 0.5 / 0.05 = 9.5 ms
(d) (n - 1)(q + s) = 5 x 4.5 = 22.5 ms

(খ)-তে q কোনো ভূমিকা রাখে না — প্রসেস নিজেই আগে ছেড়ে দেয়। (ঘ)-তে বাকি পাঁচজনের প্রত্যেকে পুরো quantum আর একটি switch নেয়; এটাই RR-এর response-এর সর্বোচ্চ সীমা।

উদাহরণ ২.৭ (মাঝারি → কঠিন) — fork গোনা

প্রশ্ন: প্রতিটি কোড শেষে মোট কতটি প্রসেস থাকে (মূলটিসহ)? (a) for (i = 0; i < 3; i++) fork(); (b) if (fork() == 0) fork(); (c) fork() || fork(); (d) fork() && (fork() || fork()); (e) for (i = 0; i < 4; i++) if (i % 2 == 0) fork();

(a) 2^3 = 8
(b) parent skips; child forks once           -> 1 + 1 + 1 = 3
(c) parent: fork1 > 0, || stops; child: 0 -> fork2 -> 3
(d) A>0 -> B>0 : stop (1 process)
         B=0   -> C : 2 processes
    A=0 : && stops  (1 process)              -> 1 + 2 + 1 = 4
(e) fork only at i = 0 and i = 2              -> 2^2 = 4

(d)-র পদ্ধতিই সাধারণ পদ্ধতি: প্রতিটি fork-এ দুটি শাখা, প্রতিটি শাখায় short-circuit কোথায় থামায় দেখুন, শেষে পাতা (leaf) গুনুন।

কঠিন ফাঁদ — buffer: for (i = 0; i < 3; i++) { fork(); printf("A"); } — প্রতিটি printf সঙ্গে সঙ্গে লেখা হলে A ছাপা হয় 2 + 4 + 8 = ১৪ বার। কিন্তু newline ছাড়া stdout buffer-এ জমে থাকে আর fork সেই buffer-ও কপি করে; তখন শেষের ৮টি প্রসেসের প্রত্যেকে নিজের buffer-এর “AAA” ছাপে — মোট ২৪. পরীক্ষায় দুটি সংখ্যাই কারণসহ লিখুন (পর্ব ১০)।

খাতার গাছ আসল সিস্টেমে মিলিয়ে দেখুন। নিচের C প্রোগ্রাম পাঁচটি ধাঁধার প্রতিটি একটি আলাদা child-এর ভেতরে চালায়; ধাঁধা শেষে প্রতিটি প্রসেস একটি pipe-এ ঠিক এক byte লেখে, আর মূল প্রসেস byte গুনে প্রসেসের সংখ্যা বলে। Pipe-এর শেষ (EOF) আসে কেবল তখন, যখন সব প্রসেস write-প্রান্ত বন্ধ করে বেরিয়ে যায় — তাই গোনা নির্ভরযোগ্য, প্রসেসগুলো যে ক্রমেই চলুক।

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

static void puzzle(int k) {                 /* the five fork puzzles of example 2.7 */
    if (k == 0) for (int i = 0; i < 3; i++) fork();
    if (k == 1) { if (fork() == 0) fork(); }
    if (k == 2) (void)(fork() || fork());
    if (k == 3) (void)(fork() && (fork() || fork()));
    if (k == 4) for (int i = 0; i < 4; i++) if (i % 2 == 0) fork();
}
int main(void) {
    const char *name[] = {"(a) for i<3: fork()", "(b) if (fork()==0) fork()", "(c) fork() || fork()",
                          "(d) fork() && (fork() || fork())", "(e) for i<4: if (i%2==0) fork()"};
    for (int k = 0; k < 5; k++) {
        int fd[2], n = 0; char c;
        if (pipe(fd) != 0) return 1;
        fflush(stdout);                     /* nothing buffered may be copied into children */
        pid_t leader = fork();
        if (leader == 0) {                  /* the puzzle runs inside this child */
            close(fd[0]);
            puzzle(k);
            if (write(fd[1], "x", 1) != 1) _exit(1);    /* every process reports once */
            _exit(0);
        }
        close(fd[1]);
        while (read(fd[0], &c, 1) == 1) n++;            /* EOF only after all have exited */
        close(fd[0]);
        waitpid(leader, NULL, 0);
        printf("%-34s -> %d processes\n", name[k], n);
    }
    return 0;
}

আউটপুট (প্রতিবার একই, কারণ শুধু মূল প্রসেস ছাপে):

(a) for i<3: fork()                -> 8 processes
(b) if (fork()==0) fork()          -> 3 processes
(c) fork() || fork()               -> 3 processes
(d) fork() && (fork() || fork())   -> 4 processes
(e) for i<4: if (i%2==0) fork()    -> 4 processes

পাঁচটি সংখ্যাই খাতার উত্তরের সাথে মেলে। দুটি খুঁটিনাটি লক্ষ করুন: প্রতিটি fork-এর আগে fflush(stdout) — নইলে আগের লাইনগুলো buffer-সহ child-এ কপি হয়ে দুবার ছাপা হতো (উপরের ২৪-এর ফাঁদ); আর child-রা _exit দিয়ে বেরোয়, যাতে stdio-র buffer আবার flush না হয়। এটি Linux/glibc-এ চালানো; Windows-এ fork নেই (সেখানে CreateProcess, পর্ব ১০)।

উদাহরণ ২.৮ (মাঝারি) — Amdahl

প্রশ্ন: একটি প্রোগ্রামের ৮০% সমান্তরালে চালানো যায়। (ক) ৪ core-এ speedup? (খ) ১৬ core-এ? (গ) অসীম core-এ সীমা? (ঘ) ৮ core-এ ৬ গুণ speedup পেতে সমান্তরাল অংশ কত হতে হবে?

(a) 1 / (0.2 + 0.8/4)  = 1 / 0.40 = 2.50   (efficiency 2.5/4 = 62.5%)
(b) 1 / (0.2 + 0.8/16) = 1 / 0.25 = 4.00
(c) 1 / 0.2 = 5
(d) (1 - f) + f/8 = 1/6  =>  1 - 7f/8 = 1/6  =>  f = (5/6)(8/7) = 0.952 -> 95.2%

core চার গুণ (৪ → ১৬) করে speedup মাত্র ১.৬ গুণ বাড়ল। ২০% ধারাবাহিক অংশ পুরো সীমা ঠিক করে দেয় — এটাই Amdahl-এর শিক্ষা।

নিজে করুন — ভাগ ২

নি ২.১(সহজ) I/O অপেক্ষা ৫০% হলে CPU-কে অন্তত ৯০% ব্যস্ত রাখতে ন্যূনতম কতটি কাজ লাগবে?

৪টি। 1 − 0.5³ = 0.875 (যথেষ্ট নয়), 1 − 0.5⁴ = 0.9375 ≥ 0.9.

নি ২.২(সহজ) L1 hit ১ ns, miss rate ১০%, RAM ১০০ ns, L2 নেই — AMAT কত? এরপর L2 (hit ৮ ns, local miss ৪০%) যোগ করলে?

L2 ছাড়া 1 + 0.1 × 100 = ১১ ns. L2-সহ 1 + 0.1 × (8 + 0.4 × 100) = 1 + 4.8 = ৫.৮ ns.

নি ২.৩(মাঝারি) Context switch ০.২ ms হলে ৯৮% efficiency-র জন্য ন্যূনতম quantum কত?

q/(q + 0.2) ≥ 0.98 ⟹ 0.02q ≥ 0.196 ⟹ q ≥ ৯.৮ ms. যাচাই: 9.8/10 = 0.98.

নি ২.৪(মাঝারি) for (i = 0; i < 5; i++) fork(); printf("X\n"); — কতটি প্রসেস, কতটি নতুন, কতটি লাইন? আর fork(); fork() && fork();-এ কতটি প্রসেস?

প্রথমটিতে ২৫ = ৩২টি প্রসেস, নতুন ৩১টি, প্রত্যেকে একবার ছাপে — ৩২ লাইন (printf লুপের পরে, তাই fork-এর সময় buffer খালি; আউটপুট টার্মিনালে বা pipe-এ, যেখানেই যাক)। দ্বিতীয়টিতে প্রথম fork-এর পর ২টি প্রসেস; প্রত্যেকের fork() && fork() থেকে ৩টি — মোট ৬টি.

নি ২.৫(মাঝারি) ৯০% সমান্তরাল প্রোগ্রাম ১০ core-এ কত speedup পায়? সর্বোচ্চ সীমা কত?

1/(0.1 + 0.09) = 1/0.19 ≈ ৫.২৬; সীমা 1/0.1 = ১০. দশটি core-এ সীমার অর্ধেকের সামান্য বেশি।

৩ · CPU scheduling ১ — FCFS, SJF, SRTF আর HRRN

ঝালিয়ে নিন: পর্ব ১৬ · CPU scheduling-এর ভিত্তি, পর্ব ১৭ · FCFS, SJF আর SRTF.

নিয়মের কার্ড

মাপ: AT (আগমন), BT (burst), CT (শেষ), TAT = CT − AT, WT = TAT − BT, RT = প্রথম শুরু − AT. Non-preemptive নীতিতে RT = WT.

বাছাই: FCFS — ছোট AT; SJF — এসে যাওয়াদের মধ্যে ছোট BT, শেষ না হওয়া পর্যন্ত চলে; SRTF — প্রতিটি arrival-এ বাকি সময় তুলনা, ছোট হলে preemption; HRRN — CPU খালি হলে সবচেয়ে বড় response ratio R = (W + S)/S, যেখানে W = এ পর্যন্ত অপেক্ষা, S = burst.

ফাঁদ: প্রথম প্রসেস t = ০-তে না এলে শুরুতে idle; মাঝে কেউ না থাকলে idle — দুটোই Gantt chart-এ দেখাতে হয়। চেক: ΣWT = ΣTAT − ΣBT.

এই ভাগের process table (সেট A): ৫টি প্রসেস, সময় ms-এ। শুরুতে ২ ms আর মাঝে ৩ ms CPU খালি থাকে — ইচ্ছা করে রাখা ফাঁদ। মোট BT = ১৫.

প্রসেসP1P2P3P4P5
AT234618
BT53142
উদাহরণ ৩.১ (সহজ) — FCFS 
│idle│P1   │P2 │P3│P4  │idle│P5│
0    2     7   10 11   15   18  20
প্রসেসATBTCTTATWT
P125750
P2331074
P3411176
P4641595
P51822020
যোগ / গড়1530 / 6.0015 / 3.00

চেক: ৩০ − ১৫ = ১৫ ✓; শেষ সময় ২০ = মোট burst ১৫ + idle (২ + ৩). RT = WT, গড় ৩.০০. সবচেয়ে ছোট কাজ P3 সবচেয়ে বেশি অপেক্ষা করল (৬) — convoy effect-এর ছোট রূপ।

উদাহরণ ৩.২ (মাঝারি) — SJF (non-preemptive) 
│idle│P1   │P3│P2 │P4  │idle│P5│
0    2     7  8   11   15   18  20

t = ২-এ শুধু P1, তাই সে পুরো ৫ ms চলে (non-preemptive — পরে ছোট কেউ এলেও থামে না)। t = ৭-এ অপেক্ষায় P2 (৩), P3 (১), P4 (৪) → P3; t = ৮-এ P2 (৩) বনাম P4 (৪) → P2; তারপর P4. CT = ৭, ১১, ৮, ১৫, ২০; TAT = ৫, ৮, ৪, ৯, ২ (যোগ ২৮); WT = ০, ৫, ৩, ৫, ০ (যোগ ১৩)। গড় TAT = ২৮/৫ = ৫.৬০, গড় WT = ১৩/৫ = ২.৬০. চেক: ২৮ − ১৫ = ১৩ ✓.

উদাহরণ ৩.৩ (কঠিন) — SRTF, ধাপে ধাপে

SRTF-এ প্রতিটি arrival আর প্রতিটি সমাপ্তি একটি সিদ্ধান্তের মুহূর্ত। খাতায় প্রতিটি মুহূর্তে লিখুন: কে এল, সবার বাকি সময় কত, কে চলবে। নিচের stepper ঠিক সেই ছক — প্রতিটি ধাপে Gantt chart এক খোপ করে বাড়ে।

1t=0   nobody here        idle2t=2   P1 arrives (5)     run P13t=3   P2 (3) < P1 (4)    PREEMPT -> P24t=4   P3 (1) < P2 (2)    PREEMPT -> P35t=5   P3 done            pick P2 (2)6t=6   P4 (4) > P2 (1)    keep P27t=7   P1 (4) = P4 (4)    tie -> P18t=11  P1 done            run P4, then idle9t=18  P5 arrives         run P5, all done
এই মুহূর্তে
CPU-তে
বাকি P1/P2/P3/P4/P5
অপেক্ষায়
শেষ হলো
  1. t = ০ থেকে ২: কেউ আসেনি। প্রথম খোপটি “idle”. এটি বাদ দিলে সব CT ২ করে ভুল হয় — সবচেয়ে সাধারণ ভুল।
  2. t = ২: P1 এল (৫)। একমাত্র প্রার্থী, তাই চলে। P1-এর RT = ২ − ২ = ০. এক ms পর বাকি ৪.
  3. t = ৩: P2 এল (৩)। তুলনা: P2-এর ৩ বনাম P1-এর বাকি ৪ — ৩ < ৪, তাই preemption. P1 বাকি ৪ নিয়ে অপেক্ষায়। P2-এর RT = ০.
  4. t = ৪: P3 এল (১)। ১ < P2-এর বাকি ২ — আবার preemption. P3 চলে ৪–৫ আর শেষ: CT ৫, TAT ১, WT ০.
  5. t = ৫: P3 শেষ। প্রার্থী P1 (৪) আর P2 (২) → P2 ফিরে আসে।
  6. t = ৬: P4 এল (৪)। P2-এর বাকি মাত্র ১ < ৪, তাই কোনো preemption নেই। P2 শেষ করে t = ৭-এ: CT ৭, TAT ৪, WT ১.
  7. t = ৭: tie. P1 আর P4 দুজনেরই বাকি ৪. নিয়ম: আগে আসা জন — P1 (AT ২)। P1 চলে ৭–১১: CT ১১, TAT ৯, WT ৪. এই tie-নিয়ম উল্টালে P4 আগে চলে, তখন P4-এর WT ১ আর P1-এর WT ৮ — আলাদা সংখ্যা বদলায়, গড় একই থাকে; তাই নিয়মটি লিখুন।
  8. t = ১১: P4 একা। P4 চলে ১১–১৫: CT ১৫, TAT ৯, WT ৫, RT = ১১ − ৬ = ৫. তারপর ১৫–১৮ আবার idle.
  9. t = ১৮: P5. চলে ১৮–২০, WT ০. ফল: TAT যোগ ৯ + ৪ + ১ + ৯ + ২ = ২৫, WT যোগ ১০, RT যোগ ৫. গড় TAT ৫.০০, গড় WT ২.০০, গড় RT ১.০০ — FCFS (৩.০০) আর SJF (২.৬০)-এর চেয়ে কম, দাম দুটি বাড়তি preemption.
উদাহরণ ৩.৪ (মাঝারি → কঠিন) — HRRN

(ক) সেট A-তে: t = ৭-এ (P1 শেষ) R হিসাব: P2 = (৪ + ৩)/৩ = ২.৩৩, P3 = (৩ + ১)/১ = ৪.০০, P4 = (১ + ৪)/৪ = ১.২৫ → P3. t = ৮-এ P2 = (৫ + ৩)/৩ = ২.৬৭, P4 = (২ + ৪)/৪ = ১.৫০ → P2. ফল এখানে SJF-এর হুবহু এক (গড় WT ২.৬০)।

(খ) নতুন সেট B, যেখানে লম্বা কাজের অপেক্ষা পার্থক্য গড়ে: P1 (AT ০, BT ৬), P2 (১, ২), P3 (২, ৮), P4 (৩, ৩), P5 (৪, ৪). Non-preemptive, R-এর tie-তে আগে আসা।

t=0  : P1 only                                   -> P1 0-6
t=6  : P2 (5+2)/2=3.50  P3 (4+8)/8=1.50  P4 (3+3)/3=2.00  P5 (2+4)/4=1.50 -> P2 6-8
t=8  : P3 (6+8)/8=1.75  P4 (5+3)/3=2.67  P5 (4+4)/4=2.00                  -> P4 8-11
t=11 : P3 (9+8)/8=2.125 P5 (7+4)/4=2.75                                   -> P5 11-15
t=15 : P3                                                                  -> P3 15-23
CT  = 6, 8, 23, 11, 15     TAT = 6, 7, 21, 8, 11 (sum 53)     WT = 0, 5, 13, 5, 7 (sum 30)
avg TAT = 10.60   avg WT = 6.00

লক্ষ করুন P3-এর R প্রতিটি সিদ্ধান্তে বাড়ছে (১.৫০ → ১.৭৫ → ২.১২৫) — অপেক্ষা বাড়লে লম্বা কাজও শেষে জেতে, তাই HRRN-এ starvation নেই। বড় সেটে এই aging-এর প্রভাব আরও স্পষ্ট।

Scheduler ক্যালকুলেটর — নিজের অঙ্ক মেলান

নিচের ক্যালকুলেটর এক ms করে সময় এগিয়ে যেকোনো নীতি চালায়: ALG-এ FCFS, SJF, SRTF, HRRN, NPP (non-preemptive priority), PP (preemptive priority) বা RR লিখুন, Q-তে quantum, টেবিলে নিজের প্রসেস। Tie আর RR-এর নিয়ম কোডের মাথায় লেখা — এই পাতার নিয়মই। প্রথমে খাতায় করুন, তারপর চালিয়ে মেলান।

// Universal CPU-scheduling calculator. Edit ALG, Q and the table, then press Run.
// ALG: FCFS SJF SRTF HRRN NPP (priority, non-preemptive) PP (priority, preemptive) RR
// Rules: smaller priority number = higher priority; ties -> running one stays (preemptive),
// then earlier arrival, then table order; RR: a new arrival joins before the preempted one.
const ALG = "SRTF", Q = 3;
const table = [["P1", 2, 5, 3], ["P2", 3, 3, 1], ["P3", 4, 1, 4],   // [name, arrival, burst, priority]
               ["P4", 6, 4, 2], ["P5", 18, 2, 1]];
const ps = table.map(([n, at, bt, pr], i) => ({ n, at, bt, pr, i, left: bt, start: -1 }));
const key = { FCFS: p => p.at, SJF: p => p.bt, SRTF: p => p.left, NPP: p => p.pr, PP: p => p.pr,
              HRRN: (p, t) => -(t - p.at + p.bt) / p.bt };
const g = [], rq = []; let t = 0, cur = null, used = 0, done = 0;
while (done < ps.length) {
  ps.filter(p => p.at === t).forEach(p => rq.push(p));            // arrivals first
  if (ALG === "RR") {
    if (cur && used === Q) { rq.push(cur); cur = null; }          // then the preempted one
    if (!cur && rq.length) { cur = rq.shift(); used = 0; }
  } else if (!cur || ["SRTF", "PP"].includes(ALG)) {
    const ready = ps.filter(p => p.at <= t && p.left > 0), k = p => key[ALG](p, t);
    ready.sort((a, b) => (Math.abs(k(a) - k(b)) < 1e-9 ? 0 : k(a) - k(b)) ||
                         (b === cur) - (a === cur) || a.at - b.at || a.i - b.i);
    cur = ready[0] || null;
  }
  const lab = cur ? cur.n : "idle", last = g[g.length - 1];
  if (last && last.lab === lab) last.e++; else g.push({ lab, s: t, e: t + 1 });
  if (cur) { if (cur.start < 0) cur.start = t; used++;
             if (--cur.left === 0) { cur.ct = t + 1; done++; cur = null; } }
  t++;
}
console.log(ALG + (ALG === "RR" ? " q=" + Q : "") + ": " + g.map(x => `${x.s}-${x.e} ${x.lab}`).join(" | "));
const s = [0, 0, 0];
for (const p of ps) { const v = [p.ct - p.at, p.ct - p.at - p.bt, p.start - p.at]; v.forEach((x, j) => s[j] += x);
  console.log(`  ${p.n}  CT=${p.ct}  TAT=${v[0]}  WT=${v[1]}  RT=${v[2]}`); }
const [a, w, r] = s.map(x => (x / ps.length).toFixed(2));
console.log(`  avg  TAT=${a}  WT=${w}  RT=${r}`);

আউটপুট (সেট A, SRTF):

SRTF: 0-2 idle | 2-3 P1 | 3-4 P2 | 4-5 P3 | 5-7 P2 | 7-11 P1 | 11-15 P4 | 15-18 idle | 18-20 P5
  P1  CT=11  TAT=9  WT=4  RT=0
  P2  CT=7  TAT=4  WT=1  RT=0
  P3  CT=5  TAT=1  WT=0  RT=0
  P4  CT=15  TAT=9  WT=5  RT=5
  P5  CT=20  TAT=2  WT=0  RT=0
  avg  TAT=5.00  WT=2.00  RT=1.00

প্রথম লাইনটিই stepper-এর শেষ Gantt chart, idle ফাঁকসহ; নিচের সারিগুলো উদাহরণ ৩.৩-এর টেবিল। ALG = "FCFS" বা "SJF" করলে উদাহরণ ৩.১ আর ৩.২-এর গড় (৩.০০, ২.৬০) পাবেন। টেবিলের চতুর্থ কলামের priority সংখ্যাগুলো শুধু NPP/PP-তে কাজে লাগে। মনে রাখবেন, ক্যালকুলেটর এই পাতার নিয়ম মানে; আপনার বইয়ের নিয়ম আলাদা হলে (যেমন RR-এ থামানো প্রসেস আগে) ফল আলাদা আসবে — সেটাই শেখার জায়গা।

নিজে করুন — ভাগ ৩

সেট E: P1 (AT ০, BT ৭), P2 (২, ৩), P3 (৩, ৬), P4 (৫, ১), P5 (২০, ২)। সময় ms-এ।

নি ৩.১(মাঝারি) সেট E-তে SJF (non-preemptive)-এর Gantt chart আর গড় WT কত?

│P1 0-7│P4 7-8│P2 8-11│P3 11-17│idle 17-20│P5 20-22│. WT = ০, ৬, ৮, ২, ০ → যোগ ১৬, গড় ৩.২০; গড় TAT ৭.০০. t = ১৭–২০-এর idle বাদ দিলে P5-এর হিসাব ভুল হয়।

নি ৩.২(কঠিন) সেট E-তে SRTF-এর Gantt chart, গড় WT আর গড় RT কত?

│P1 0-2│P2 2-5│P4 5-6│P1 6-11│P3 11-17│idle 17-20│P5 20-22│. t = ২-এ P2 (৩) < P1-এর বাকি ৫ → preemption; t = ৩-এ P3 (৬) বড়, কিছু হয় না; t = ৫-এ P2 শেষ, P4 (১) আসে → P4; তারপর P1 (৫) বনাম P3 (৬) → P1. WT = ৪, ০, ৮, ০, ০ → গড় ২.৪০; RT = ০, ০, ৮, ০, ০ → গড় ১.৬০; গড় TAT ৬.২০.

নি ৩.৩(মাঝারি) সেট E-তে HRRN চালালে t = ৭ আর t = ৮-এ প্রতিটি প্রার্থীর response ratio কত, আর কে জেতে?

t = ৭: P2 = (৫ + ৩)/৩ = ২.৬৭, P3 = (৪ + ৬)/৬ = ১.৬৭, P4 = (২ + ১)/১ = ৩.০০ → P4. t = ৮: P2 = (৬ + ৩)/৩ = ৩.০০, P3 = (৫ + ৬)/৬ = ১.৮৩ → P2. ফলে চার্ট SJF-এর মতোই, গড় WT ৩.২০.

নি ৩.৪(সহজ) P1 (AT ৩, BT ৪), P2 (৫, ২), P3 (৬, ১) — SJF-এ গড় TAT কত?

│idle 0-3│P1 3-7│P3 7-8│P2 8-10│. TAT = ৪, ৫, ২ → গড় ১১/৩ ≈ ৩.৬৭; WT = ০, ৩, ১ → গড় ১.৩৩. চার্ট ০ থেকেই শুরু করুন, ৩ থেকে নয়।

৪ · CPU scheduling ২ — priority, Round Robin, MLFQ আর real-time

ঝালিয়ে নিন: পর্ব ১৮ · Priority scheduling আর Round Robin, পর্ব ১৯ · Multilevel feedback queue, পর্ব ২০ · Multiprocessor আর real-time scheduling.

নিয়মের কার্ড

Priority: ছোট সংখ্যা = বেশি জরুরি। Non-preemptive-এ CPU খালি হলেই বাছাই; preemptive-এ প্রতিটি arrival-এ তুলনা, সমান priority-তে চলতি প্রসেস থামে না।

Round Robin: ready queue একটি FIFO; প্রত্যেকে সর্বোচ্চ q চলে। একই মুহূর্তে আগমন আর quantum ফুরালে নতুনটি আগে। খাতায় প্রতিটি quantum-সীমায় সারির অবস্থা লিখুন।

MLFQ: স্তরগুলোর মধ্যে fixed priority; পুরো quantum খেলে এক স্তর নিচে; নিচের জন থামলে নিজের queue-এর সামনে থাকে আর বাকি quantum নিয়ে ফেরে।

Real-time: U = Σ Ci/Ti. RM: U ≤ n(21/n − 1) হলে নিশ্চিত schedulable (Liu–Layland সীমা; n = ২-এ ০.৮২৮, n = ৩-এ ০.৭৮০); সীমার ওপরে হলে সিদ্ধান্ত দেয় না — তখন response-time analysis: R = Ci + Σj উঁচু ⌈R/Tj⌉·Cj, স্থির হওয়া পর্যন্ত। EDF (deadline = period): U ≤ ১ হলেই schedulable.

Priority-র process table (সেট C):

প্রসেসP1P2P3P4P5
AT01235
BT43252
Priority31421
উদাহরণ ৪.১ (সহজ) — non-preemptive priority 
│P1  │P2 │P5│P4   │P3│
0    4   7  9     14 16

t = ৪-এ অপেক্ষায় P2 (১), P3 (৪), P4 (২) → P2. t = ৭-এ P3 (৪), P4 (২), P5 (১) → P5 (পরে এলেও priority বেশি)। তারপর P4, শেষে P3. CT = ৪, ৭, ১৬, ১৪, ৯; WT = ০, ৩, ১২, ৬, ২ → যোগ ২৩, গড় WT ৪.৬০; গড় TAT ৭.৮০.

উদাহরণ ৪.২ (মাঝারি) — preemptive priority 
│P1│P2 │P4│P5│P4  │P1 │P3│
0  1   4  5  7    11  14 16

t = ১-এ P2 (১) এসে P1 (৩)-কে থামায়। t = ৪-এ P2 শেষ: প্রার্থী P1 (৩), P3 (৪), P4 (২) → P4. t = ৫-এ P5 (১) এসে P4 (২)-কে থামায়। t = ৭-এ P4 ফেরে (বাকি ৪), ১১-এ P1 (বাকি ৩), ১৪-এ P3.

প্রসেসCTTATWTRT
P11414100
P24300
P316141212
P411831
P57200
গড়8.205.002.60

গড় WT non-preemptive-এর চেয়ে বেশি (৫.০০ বনাম ৪.৬০), কিন্তু জরুরি P2 আর P5-এর অপেক্ষা শূন্য — priority-র লক্ষ্য গড় নয়, জরুরি কাজের দ্রুত সাড়া। P3 দুই রূপেই ১২ অপেক্ষা করে; ক্রমাগত উঁচু কাজ এলে সে starvation-এ পড়ত (প্রতিকার aging, পর্ব ১৮)।

উদাহরণ ৪.৩ (মাঝারি → কঠিন) — Round Robin, tie আর idle ফাঁকসহ

প্রশ্ন: q = ৩. P1 (AT ০, BT ৫), P2 (১, ৪), P3 (৩, ২), P4 (১৪, ৪), P5 (১৫, ৩)। Gantt chart, প্রতিটি quantum-সীমায় সারি, আর গড় TAT, WT, RT.

t=0  P1 runs 0-3            (P2 joins at 1)
t=3  P3 arrives AND P1 is preempted -> new first: queue [P2 P3 P1]
t=3  P2 runs 3-6 (left 1)   queue [P3 P1 P2]
t=6  P3 runs 6-8 done       queue [P1 P2]
t=8  P1 runs 8-10 done      queue [P2]
t=10 P2 runs 10-11 done     queue []
t=11 idle until 14
t=14 P4 runs 14-17          (P5 joins at 15)  -> at 17: queue [P5 P4]
t=17 P5 runs 17-20 done; P4 runs 20-21 done

│P1 │P2 │P3│P1│P2│idle│P4 │P5 │P4│
0   3   6  8  10 11   14  17  20  21

CT = ১০, ১১, ৮, ২১, ২০; TAT = ১০, ১০, ৫, ৭, ৫ (যোগ ৩৭); WT = ৫, ৬, ৩, ৩, ২ (যোগ ১৯); RT = ০, ২, ৩, ০, ২ (যোগ ৭)। গড় TAT ৭.৪০, WT ৩.৮০, RT ১.৪০. একই ডেটায় q = ২-এ গড় TAT আর WT কাকতালীয়ভাবে একই থাকে (৭.৪০, ৩.৮০) কিন্তু গড় RT কমে ১.০০ হয় — ক্যালকুলেটরে ALG = "RR", Q = 2 দিয়ে দেখুন। t = ৩-এর tie-নিয়ম উল্টালে সারি হতো [P2 P1 P3] — প্রতিটি প্রসেসের সংখ্যা বদলাত।

উদাহরণ ৪.৪ (কঠিন) — MLFQ

প্রশ্ন: Q0: RR q = ৪ → Q1: RR q = ৮ → Q2: FCFS. P1 (AT ০, BT ২০), P2 (২, ৬), P3 (৬, ৩), P4 (২৪, ৫)। প্রতিটির CT, TAT, WT.

0-4   P1@Q0  full quantum -> Q1 (left 16)
4-8   P2@Q0  full quantum -> Q1 (left 2)      P3 joined Q0 at 6
8-11  P3@Q0  done
11-19 P1@Q1  full 8 -> Q2 (left 8)
19-21 P2@Q1  done
21-24 P1@Q2  P4 arrives at 24 -> P1 preempted, stays at the front of Q2 (left 5)
24-28 P4@Q0  full quantum -> Q1 (left 1)
28-29 P4@Q1  done
29-34 P1@Q2  done

CT : P1 34, P2 21, P3 11, P4 29
TAT: 34, 19, 5, 5   (avg 15.75)     WT: 14, 13, 2, 0   (avg 7.25)

দুটি সূক্ষ্ম বিন্দু: t = ৮-এ P3 (Q0) চলে, যদিও Q1-এ P1 আগে থেকে অপেক্ষায় — ওপরের স্তর সবসময় আগে। আর t = ২৪-এ নতুন P4 সর্বোচ্চ স্তরে ঢুকে Q2-এর P1-কে থামায়; ছোট কাজ (P4, P3) দ্রুত শেষ হয়, লম্বা P1 নিচে নেমে অপেক্ষা করে — MLFQ-এর নকশাই এই।

উদাহরণ ৪.৫ (মাঝারি → কঠিন) — RM আর EDF

(ক) তিনটি periodic task (C, T): (১, ৪), (২, ৬), (৩, ১২); deadline = period. RM-এ schedulable?

U = 1/4 + 2/6 + 3/12 = 0.250 + 0.333 + 0.250 = 0.833
LL bound (n = 3) = 3(2^(1/3) - 1) = 0.780   -> U > bound: test says nothing
RTA: R1 = 1 <= 4
     R2 = 2 + ceil(R/4)*1      : 3 -> 3            = 3 <= 6
     R3 = 3 + ceil(R/4)*1 + ceil(R/6)*2 : 6 -> 7 -> 9 -> 10 -> 10   = 10 <= 12
=> schedulable under RM

(খ) (১, ৩), (২, ৫), (২, ৮) — RM-এ? EDF-এ?

U = 1/3 + 2/5 + 2/8 = 0.333 + 0.400 + 0.250 = 0.983   (> 0.780)
RTA for task 3: 5 -> 6 -> 8 -> 9   9 > 8  => misses its deadline under RM
EDF: U = 0.983 <= 1  => schedulable

সবচেয়ে বড় ভুল: “U > সীমা, তাই schedulable নয়” — Liu–Layland শর্তটি পর্যাপ্ত, আবশ্যক নয়। (ক) সীমার ওপরে থেকেও schedulable; (খ)-তে সত্যিই ব্যর্থ, সেটা RTA দেখায় (আর simulation-এ t = ৮-এ task 3-এর deadline ফসকায়)।

নিজে করুন — ভাগ ৪

নি ৪.১(মাঝারি) সেট E (P1 ০/৭, P2 ২/৩, P3 ৩/৬, P4 ৫/১, P5 ২০/২) — RR, q = ৪: Gantt chart আর গড় WT কত?

│P1 0-4│P2 4-7│P3 7-11│P1 11-14│P4 14-15│P3 15-17│idle 17-20│P5 20-22│. t = ৪-এ সারি [P2 P3 P1]; t = ৭-এ [P3 P1 P4]; t = ১১-এ [P1 P4 P3]. WT = ৭, ২, ৮, ৯, ০ → গড় ৫.২০; গড় TAT ৯.০০. এক ms-এর P4 সারিতে ৯ ms অপেক্ষা করল — RR ছোট কাজকে আলাদা সুবিধা দেয় না।

নি ৪.২(মাঝারি) P1 (AT ০, BT ৫, pr ২), P2 (১, ২, ১), P3 (২, ৪, ৩), P4 (৪, ১, ১) — preemptive আর non-preemptive priority-তে গড় WT কত?

Preemptive: │P1 0-1│P2 1-3│P1 3-4│P4 4-5│P1 5-8│P3 8-12│ → WT ৩, ০, ৬, ০ → গড় ২.২৫. Non-preemptive: │P1 0-5│P2 5-7│P4 7-8│P3 8-12│ → WT ০, ৪, ৬, ৩ → গড় ৩.২৫.

নি ৪.৩(কঠিন) দুই স্তরের MLFQ: Q0 RR q = ২, Q1 FCFS. P1 (০, ৫), P2 (১, ৩), P3 (৪, ২) — CT আর গড় TAT কত?

│P1@Q0 0-2│P2@Q0 2-4│P3@Q0 4-6│P1@Q1 6-9│P2@Q1 9-10│. CT = ৯, ১০, ৬; TAT = ৯, ৯, ২ → গড় ৬.৬৭. t = ৪-এ P3 Q0-তে আসে, আর Q1-এর P1, P2 অপেক্ষা করে।

নি ৪.৪(মাঝারি) Task (C, T): (৩, ৬) আর (৩, ৮) — RM-এ schedulable? Liu–Layland কী বলে?

U = ০.৫০০ + ০.৩৭৫ = ০.৮৭৫ > ০.৮২৮ — সীমা সিদ্ধান্ত দেয় না। RTA: R₂ = 3 + ⌈R/6⌉·3: ৬ → ৬, আর ৬ ≤ ৮ — schedulable.

নি ৪.৫(সহজ) Task (২, ৬) আর (৩, ৯) — RM-এ schedulable কি না, সবচেয়ে কম হিসাবে বলুন।

U = ০.৩৩৩ + ০.৩৩৩ = ০.৬৬৭ ≤ ০.৮২৮ — Liu–Layland সীমার ভেতরে, তাই নিশ্চিত schedulable; RTA লাগে না (করলে R₂ = ৫ ≤ ৯)।

৫ · Semaphore আর deadlock — trace, ন্যূনতম resource আর Banker's

ঝালিয়ে নিন: পর্ব ২৪ · Mutex আর semaphore, পর্ব ২৭ · Deadlock, পর্ব ২৮ · Banker's algorithm.

নিয়মের কার্ড

Semaphore (পাঠ্যবই-রীতি): wait (P) মান ১ কমায়, মান ঋণাত্মক হলে ডাকা প্রসেস ঘুমায়; signal (V) মান ১ বাড়ায়, মান ≤ ০ হলে সারির প্রথমজনকে জাগায়। ঋণাত্মক মান = −(অপেক্ষারত প্রসেসের সংখ্যা)। শেষ মান = শুরু − P-এর সংখ্যা + V-এর সংখ্যা।

ন্যূনতম resource: n টি প্রসেস, প্রত্যেকের সর্বোচ্চ চাহিদা k (একই ধরনের resource) হলে deadlock অসম্ভব করতে লাগে n(k − 1) + 1; চাহিদা আলাদা হলে Σ(ki − 1) + 1. যুক্তি: সবাই k − 1 ধরে থাকলেই সবচেয়ে খারাপ অবস্থা, তখন একটি বাড়তি unit কাউকে শেষ করায়।

Banker's: Need = Max − Allocation. Safety: Work = Available; Needi ≤ Work এমন প্রথম i চলে, Work += Allocationi; সবাই শেষ হলে safe. Request: (১) Request ≤ Need না হলে error, (২) ≤ Available না হলে অপেক্ষা, (৩) ধরে নিয়ে safety চালানো — safe হলে মঞ্জুর, না হলে প্রত্যাখ্যান। Detection: Need-এর জায়গায় বর্তমান Request, আর কিছু না ধরে থাকা প্রসেস শুরুতেই finished.

উদাহরণ ৫.১ (মাঝারি) — semaphore-এর মান আর সারি

প্রশ্ন: S = ২. ক্রমে ঘটে: P1 wait, P2 wait, P3 wait, P4 wait, P1 signal, P5 wait, P2 signal, P3 signal, P4 signal, P5 signal. প্রতিটির পর S আর অপেক্ষার সারি?

ঘটনাSসারিফল
P1 wait1—P1 ঢোকে
P2 wait0—P2 ঢোকে
P3 wait−1P3P3 ঘুমায়
P4 wait−2P3, P4P4 ঘুমায়
P1 signal−1P4P3 জাগে, ঢোকে
P5 wait−2P4, P5P5 ঘুমায়
P2 signal−1P5P4 জাগে
P3 signal0—P5 জাগে
P4 signal1—কেউ অপেক্ষায় নেই
P5 signal2—শুরুর মানে ফেরা

যেকোনো মুহূর্তে ভেতরে সর্বোচ্চ দুজন — counting semaphore-এর কাজ ঠিক এটাই। চেক: ২ − ৫ + ৫ = ২ ✓. যে বইয়ে মান কখনো ঋণাত্মক হয় না (busy-wait রূপ), সেখানে কলামটি ০-তে আটকে থাকবে — রীতি লিখে দিন।

উদাহরণ ৫.২ (সহজ) — শেষ মান

প্রশ্ন: (ক) S = ৫-এ ১২টি wait আর ৯টি signal (যেকোনো ক্রমে) হলে শেষ মান? (খ) S = ৩-এ ৮টি wait আর ৪টি signal?

(ক) ৫ − ১২ + ৯ = ২, কেউ অপেক্ষায় নেই। (খ) ৩ − ৮ + ৪ = −১: একটি প্রসেস এখনো ঘুমিয়ে। পাঠ্যবই-রীতিতে ক্রম শেষ মান বদলায় না, শুধু মাঝের অবস্থা বদলায়।

উদাহরণ ৫.৩ (সহজ → কঠিন) — n(k − 1) + 1 
(a) 4 processes, each needs 3        -> 4 x 2 + 1 = 9
(b) R = 11 units, each needs 4: largest n with 3n + 1 <= 11 -> n = 3   (n = 4 needs 13)
(c) needs 2, 3, 4, 5                 -> 1 + 2 + 3 + 4 + 1 = 11
(d) R = 13, n = 4 equal needs: largest k with 4(k - 1) + 1 <= 13 -> k = 4

(খ)-তে ৪টি প্রসেস নিলে তিনজন ৩টি করে আর একজন ২টি ধরে ১১টিই শেষ করে ফেলতে পারে, অথচ প্রত্যেকের আরও লাগে — তাই সবাই আটকে যেতে পারে। “পারে” শব্দটি জরুরি: deadlock-এর সম্ভাবনা দূর করতেই সূত্র।

Banker's-এর অবস্থা (৫টি প্রসেস, তিন ধরনের resource A, B, C):

প্রসেসAllocation (A B C)Max (A B C)Need = Max − Alloc
P01 2 04 4 23 2 2
P12 0 13 2 21 2 1
P20 1 15 3 35 2 2
P33 1 03 3 10 2 1
P41 0 22 2 41 2 2
Available = (2, 2, 1); মোট = Allocation-এর যোগ (7, 4, 4) + Available = (9, 6, 5)
Work আর Finish
এই ধাপের খোঁজ
Work
Finish (P0…P4)
Safe sequence
  1. শুরু। Work = Available = (২, ২, ১), কেউ শেষ হয়নি। আগে Need টেবিল লিখে নিন — Max সরাসরি তুলনা করা একটি সাধারণ ভুল।
  2. প্রথম খোঁজ। P0-এর Need (৩, ২, ২): A-তে ৩ > ২, চলবে না। P1 (১, ২, ১) ≤ (২, ২, ১) — চলে, শেষে নিজের Allocation (২, ০, ১) ফেরত দেয়: Work = (৪, ২, ২)।
  3. আবার P0 থেকে। এবার P0 (৩, ২, ২) ≤ (৪, ২, ২) — চলে, ফেরত (১, ২, ০): Work = (৫, ৪, ২)। “ছোট index আগে” নিয়মে প্রতিবার শুরু থেকে খুঁজতে হয়।
  4. P2. (৫, ২, ২) ≤ (৫, ৪, ২) — A ঠিক সমান, চলে। ফেরত (০, ১, ১): Work = (৫, ৫, ৩)।
  5. P3. (০, ২, ১) ≤ (৫, ৫, ৩) — চলে, ফেরত (৩, ১, ০): Work = (৮, ৬, ৩)।
  6. P4, সবাই শেষ। (১, ২, ২) ≤ (৮, ৬, ৩)। Work = (৯, ৬, ৫) = মোট resource — হিসাব ঠিক থাকার চেক। Safe, sequence <P1, P0, P2, P3, P4>. অন্য বাছাই-নিয়মে sequence বদলাতে পারে, “safe” সিদ্ধান্ত বদলায় না।
উদাহরণ ৫.৫ (কঠিন) — চারটি request, চার রকম ফল

প্রতিটি request আলাদাভাবে শুরুর অবস্থা থেকে বিচার করুন।

P3 (0,2,0): <= Need (0,2,1), <= Avail (2,2,1). Pretend: Avail (2,0,1), P3 Need (0,0,1)
            P3 -> (5,3,1)  P1 -> (7,3,2)  P0 -> (8,5,2)  P2 -> (8,6,3)  P4 -> (9,6,5)
            SAFE <P3, P1, P0, P2, P4>  => GRANT
P4 (1,0,1): <= Need, <= Avail. Pretend: Avail (1,2,0), P4 Need (0,2,1)
            every Need has C >= 1 while Work C = 0  => nobody can run
            UNSAFE => DENY (P4 waits)
P1 (0,3,0): Need of P1 is (1,2,1); 3 > 2  => ERROR (exceeds its declared maximum)
P2 (3,0,0): <= Need (5,2,2) but 3 > Avail A = 2  => WAIT (resources not available)

P4-এর ঘটনাটি মনোযোগ দিয়ে দেখুন: resource খালি থাকা সত্ত্বেও মঞ্জুর হলো না, কারণ দিলে এমন অবস্থায় পৌঁছানো যায় যেখান থেকে কেউ শেষ করতে পারে না। Unsafe মানেই deadlock নয় — deadlock হতে পারে; Banker's সেই সম্ভাবনাই এড়ায়।

উদাহরণ ৫.৬ (কঠিন) — deadlock detection আর recovery

অবস্থা: Allocation P0 (১, ০, ১), P1 (২, ১, ০), P2 (০, ১, ১), P3 (১, ০, ০), P4 (০, ০, ১); Available (০, ১, ০); মোট (৪, ৩, ৩)। (ক) Request: P0 (০, ০, ০), P1 (১, ০, ১), P2 (২, ০, ০), P3 (০, ১, ১), P4 (১, ১, ০)। (খ) একই Allocation, কিন্তু Request: P0 (০, ০, ০), P1 (১, ০, ১), P2 (০, ০, ২), P3 (১, ০, ২), P4 (০, ১, ২)।

(a) Work (0,1,0): P0 -> (1,1,1)  P1 -> (3,2,1)  P2 -> (3,3,2)  P3 -> (4,3,2)  P4 -> (4,3,3)
    everyone finishes  => NO deadlock
(b) Work (0,1,0): P0 -> (1,1,1)  P1 -> (3,2,1)
    P2 wants C=2, P3 wants C=2, P4 wants C=2, but Work C = 1   => DEADLOCK {P2, P3, P4}
recovery, abort one victim:
    abort P3 (frees 1,0,0) : C still 1 -> P2, P4 remain stuck
    abort P2 (frees 0,1,1) or P4 (frees 0,0,1) : C becomes 2 -> all others finish

শিক্ষা: শুধু “একজনকে মারো” নয় — কাকে মারলে আটকে থাকা resource (এখানে C) মুক্ত হয়, সেটাই দেখতে হয়। P3 ছোট দেখালেও তার কাছে C নেই।

Banker's ক্যালকুলেটর

অবস্থা আর request তালিকা বদলে নিজের অঙ্ক যাচাই করুন। প্রতিটি request শুরুর অবস্থা থেকে আলাদাভাবে বিচার হয় (একটির পর আরেকটি জমা হয় না)।

// Banker's calculator: Need, safety check (lowest index first), then each request in turn.
const AVAIL = [2, 2, 1];
const ALLOC = [[1, 2, 0], [2, 0, 1], [0, 1, 1], [3, 1, 0], [1, 0, 2]];
const MAX   = [[4, 4, 2], [3, 2, 2], [5, 3, 3], [3, 3, 1], [2, 2, 4]];
const REQUESTS = [[3, [0, 2, 0]], [4, [1, 0, 1]], [1, [0, 3, 0]], [2, [3, 0, 0]]];   // [process, vector]
const le = (a, b) => a.every((x, j) => x <= b[j]);
function safe(avail, alloc, need, show) {
  let work = [...avail]; const fin = alloc.map(() => false), seq = [];
  for (;;) {
    const i = fin.findIndex((f, p) => !f && le(need[p], work));     // restart from P0 every time
    if (i < 0) break;
    work = work.map((x, j) => x + alloc[i][j]); fin[i] = true; seq.push("P" + i);
    if (show) console.log(`  P${i} runs, Work = (${work})`);
  }
  return fin.every(Boolean) ? "SAFE <" + seq.join(", ") + ">" : "UNSAFE (stuck: " +
    fin.map((f, p) => f ? "" : "P" + p).filter(Boolean).join(", ") + ")";
}
const NEED = MAX.map((r, i) => r.map((x, j) => x - ALLOC[i][j]));
console.log("Need: " + NEED.map((r, i) => `P${i}(${r})`).join(" "));
console.log("Initial state: " + safe(AVAIL, ALLOC, NEED, true));
for (const [p, req] of REQUESTS) {
  let verdict;
  if (!le(req, NEED[p])) verdict = "ERROR: request exceeds Need";
  else if (!le(req, AVAIL)) verdict = "WAIT: not enough available";
  else {
    const al = ALLOC.map((r, i) => i === p ? r.map((x, j) => x + req[j]) : [...r]);
    const nd = NEED.map((r, i) => i === p ? r.map((x, j) => x - req[j]) : [...r]);
    const s = safe(AVAIL.map((x, j) => x - req[j]), al, nd, false);
    verdict = (s.startsWith("SAFE") ? "GRANT, " : "DENY, ") + s;
  }
  console.log(`P${p} requests (${req}) from the initial state: ${verdict}`);
}

আউটপুট:

Need: P0(3,2,2) P1(1,2,1) P2(5,2,2) P3(0,2,1) P4(1,2,2)
  P1 runs, Work = (4,2,2)
  P0 runs, Work = (5,4,2)
  P2 runs, Work = (5,5,3)
  P3 runs, Work = (8,6,3)
  P4 runs, Work = (9,6,5)
Initial state: SAFE <P1, P0, P2, P3, P4>
P3 requests (0,2,0) from the initial state: GRANT, SAFE <P3, P1, P0, P2, P4>
P4 requests (1,0,1) from the initial state: DENY, UNSAFE (stuck: P0, P1, P2, P3, P4)
P1 requests (0,3,0) from the initial state: ERROR: request exceeds Need
P2 requests (3,0,0) from the initial state: WAIT: not enough available

প্রথম ছয় লাইন উপরের stepper-এর প্রতিটি ধাপ, শেষ চার লাইন উদাহরণ ৫.৫-এর চার রায়। findIndex প্রতিবার ০ থেকে খোঁজে — এই পাতার “ছোট index আগে” নিয়ম। Unsafe হলে কারা আটকে আছে, তাও ছাপে; detection-এর জন্য NEED-এর জায়গায় বর্তমান Request বসিয়ে একই safe() চালানো যায়।

নিজে করুন — ভাগ ৫

নি ৫.১(সহজ) S = ৪-এ প্রথমে ১০টি wait, তারপর ৭টি signal হলে শেষ মান কত, আর মাঝপথে সবচেয়ে বেশি কতজন ঘুমিয়ে ছিল?

শেষ মান ৪ − ১০ + ৭ = ১. দশটি wait-এর পর মান −৬ — তখন ৬ জন অপেক্ষায়, এটাই সর্বোচ্চ।

নি ৫.২(সহজ) ৫টি প্রসেসের প্রত্যেকের একই ধরনের ৪টি unit লাগে। Deadlock অসম্ভব করতে ন্যূনতম কত unit? ১৫টি থাকলে কোন অবস্থায় আটকে যায়?

৫ × ৩ + ১ = ১৬. ১৫টি থাকলে পাঁচজনই ৩টি করে ধরে চতুর্থটির অপেক্ষা করতে পারে — খালি unit শূন্য, কেউ এগোতে পারে না।

নি ৫.৩(মাঝারি) উপরের Banker's অবস্থায় P0 (১, ০, ১) চাইলে মঞ্জুর হবে? আর P1 (১, ১, ০)?

P0 (১, ০, ১): প্রত্যাখ্যান। ধরে নিলে Available (১, ২, ০), আর সবার Need-এ C ≥ ১ (P0-এর নতুন Need (২, ২, ১)) — কেউ চলতে পারে না, unsafe. P1 (১, ১, ০): মঞ্জুর। Available (১, ১, ১), P1-এর Need (০, ১, ১), Allocation (৩, ১, ১) → P1 চলে (৪, ২, ২), তারপর P0 (৫, ৪, ২), P2 (৫, ৫, ৩), P3 (৮, ৬, ৩), P4 (৯, ৬, ৫) — safe, <P1, P0, P2, P3, P4>.

নি ৫.৪(মাঝারি) উপরের অবস্থায় Available যদি (১, ২, ১) হতো, অবস্থা safe কি না, আর sequence কী?

Safe, <P1, P0, P3, P2, P4>: P1 → (৩, ২, ২), P0 → (৪, ৪, ২); P2-এর A ৫ > ৪ বলে আগে P3 → (৭, ৫, ২), তারপর P2 → (৭, ৬, ৩), P4 → (৮, ৬, ৫) = নতুন মোট।

৬ · মেমরি ১ — fit, buddy, paging, TLB আর segmentation

ঝালিয়ে নিন: পর্ব ৩১ · Contiguous allocation, পর্ব ৩২ · Paging, পর্ব ৩৩ · TLB আর বড় page table, পর্ব ৩৪ · Segmentation.

সূত্র ও নিয়মের কার্ড

Fit: first fit — প্রথম যথেষ্ট বড় ফাঁকা অংশ (hole); best fit — যথেষ্ট বড়দের মধ্যে সবচেয়ে ছোট; worst fit — সবচেয়ে বড়; next fit — শেষ বরাদ্দের hole থেকে খোঁজা শুরু, শেষে গিয়ে আবার শুরুতে। বরাদ্দের পর hole-টি ছোট হয়ে একই জায়গায় থাকে।

Buddy: অনুরোধকে ২-এর পরের ঘাতে গোল করুন; বড় block অর্ধেক অর্ধেক করে ভাঙুন, নিচের অর্ধেক ব্যবহার, ওপরের অর্ধেক free list-এ। মুক্ত হলে buddy (ঠিকানা XOR আকার) খালি থাকলে জোড়া লাগে, ওপরে উঠতে থাকে। অপচয় = internal fragmentation.

Paging: page number p = ⌊ঠিকানা / page size⌋, offset d = ঠিকানা mod page size; physical = frame × page size + d. Hex-এ শুধু ওপরের bit বদলায়। Page table-এর আকার = ২(VA bit − offset bit) × PTE-র আকার।

TLB-এর EAT, L স্তরের টেবিল: রীতি ক (TLB-র সময় t গোনা): h(t + m) + (1 − h)(t + (L + 1)m); রীতি খ (t নগণ্য): h·m + (1 − h)(L + 1)m.

Segmentation: (s, d) — d < limit হলে physical = base + d, নইলে trap. Limit মানে দৈর্ঘ্য, তাই বৈধ offset ০ থেকে limit − ১.

উদাহরণ ৬.১ (মাঝারি) — চার fit পাশাপাশি

প্রশ্ন: মেমরিতে ক্রমে পাঁচটি hole (KiB): H1 ১৫০, H2 ৪০০, H3 ২২০, H4 ৫০০, H5 ৩০০. অনুরোধ ক্রমে: ২১০, ৩৮০, ১৬০, ২৯০, ১২০. প্রতিটি কৌশলে কোন অনুরোধ কোথায় বসে?

request :  210    380    160    290    120     holes left (H1..H5)
first   :  H2     H4     H2     H5     H1      30  30 220 120  10
best    :  H3     H2     H5     H4     H5     150  20  10 210  20
worst   :  H4     H2     H5     H4     H3     150  20 100   0 140
next    :  H2     H4     H5     FAIL   H5     150 190 220 120  20

Next fit-এ ২৯০ বসে না: খোঁজা H5 (১৪০) থেকে শুরু, ঘুরে H1 (১৫০), H2 (১৯০), H3 (২২০), H4 (১২০) — কেউ যথেষ্ট বড় নয়, অথচ মোট ফাঁকা ৮২০ KiB. এটাই external fragmentation: জায়গা আছে, কিন্তু টুকরো টুকরো। Worst fit-এ ২৯০ বসে H4-এর ঠিক ২৯০-এর অবশিষ্টে — hole শূন্য হয়ে যায়।

উদাহরণ ৬.২ (কঠিন) — buddy system

প্রশ্ন: ১০২৪ KiB-এর একটি block. ক্রমে: A = ৯০ চাই, B = ২০০, C = ৪০, D = ১২০, A মুক্ত, C মুক্ত, E = ২৫০, B মুক্ত, D মুক্ত. প্রতিটি ধাপের পর free block (আকার@শুরু, KiB)?

A 90  -> 128@0    (1024 -> 512+512 -> 256+256 -> 128+128)   free: 128@128 256@256 512@512
B 200 -> 256@256                                           free: 128@128 512@512
C 40  -> 64@128   (split 128@128)                          free: 64@192 512@512
D 120 -> 128@512  (split 512@512 -> 256 -> 128)            free: 64@192 128@640 256@768
free A -> 128@0, buddy 128@128 is split -> no merge        free: 64@192 128@0 128@640 256@768
free C -> 64@128 + 64@192 = 128@128, + 128@0 = 256@0       free: 128@640 256@0 256@768
E 250 -> 256@0                                             free: 128@640 256@768
free B -> 256@256, buddy 256@0 is used (E) -> no merge     free: 128@640 256@256 256@768
free D -> 128@512 + 128@640 = 256@512, + 256@768 = 512@512 free: 256@256 512@512
internal fragmentation: A 38, B 56, C 24, D 8, E 6 KiB

Buddy-র ঠিকানা বের করার কৌশল: শুরু XOR আকার। ১২৮@০-এর buddy ১২৮@১২৮, ২৫৬@২৫৬-এর buddy ২৫৬@০. শেষে ২৫৬@২৫৬ আর ৫১২@৫১২ পাশাপাশি হলেও জোড়া লাগে না — তারা buddy নয় (আকার আলাদা)।

উদাহরণ ৬.৩ (সহজ) — address translation

প্রশ্ন: Page ৪ KiB; page table: ০ → ৬, ১ → ১১, ২ → ৩, ৩ → ৮, ৪ → ১. Logical ৯০০০, ১৭০০০ আর ১৬-bit hex 0x3C9E-এর physical ঠিকানা?

9000  : p = 9000 div 4096 = 2, d = 9000 - 8192 = 808  -> frame 3 -> 3 x 4096 + 808 = 13096
17000 : p = 4, d = 17000 - 16384 = 616                 -> frame 1 -> 4096 + 616     = 4712
0x3C9E: 4 KiB = 12 offset bits = 3 hex digits -> p = 0x3, d = 0xC9E -> frame 8 -> 0x8C9E

Hex-এ ভাগ করতে হয় না: শেষের তিনটি hex অঙ্ক offset, সামনেরটি page — শুধু সেটি frame নম্বরে বদলান।

উদাহরণ ৬.৪ (মাঝারি) — page table-এর আকার আর multilevel 
(a) 32-bit VA, 4 KiB page, 4 B PTE : 2^(32-12) = 2^20 entries x 4 B = 4 MiB per process
(b) 48-bit VA, 4 KiB page, 8 B PTE : 2^36 x 8 B = 2^39 B = 512 GiB  (flat table impossible)
(c) 30-bit VA, 2 KiB page, 4 B PTE : 2^19 entries, 2 MiB; physical 256 MiB / 2 KiB = 2^17 frames
    -> frame number needs 17 bits
(d) 32-bit, two-level 10 | 10 | 12 : each inner table = 1024 x 4 B = one 4 KiB page, maps 4 MiB
    a process with 8 MiB code (bottom) + 4 MiB stack (top) needs 2 + 1 inner + 1 outer
    = 4 pages = 16 KiB   (versus 4 MiB flat)

(ঘ) দেখায় multilevel page table কেন: ব্যবহার না হওয়া অংশের জন্য ভেতরের টেবিলই তৈরি হয় না। দাম — প্রতিটি TLB miss-এ বাড়তি মেমরি-পড়া, পরের উদাহরণ।

উদাহরণ ৬.৫ (মাঝারি → কঠিন) — TLB-র EAT

প্রশ্ন: মেমরি m = ৮০ ns, TLB t = ১০ ns. (ক) এক স্তর, h = ০.৯০. (খ) তিন স্তর, h = ০.৯৫. (গ) তিন স্তরে TLB না থাকলে? (ঘ) এক স্তর, রীতি ক-তে EAT ≤ ৯৫ ns রাখতে ন্যূনতম h?

(a) A: 0.90 x (10 + 80) + 0.10 x (10 + 160) = 81 + 17   = 98 ns
    B: 0.90 x 80 + 0.10 x 160              = 72 + 16   = 88 ns
(b) A: 0.95 x 90 + 0.05 x (10 + 4 x 80)    = 85.5 + 16.5 = 102 ns
    B: 0.95 x 80 + 0.05 x 320              = 76 + 16     = 92 ns
(c) 4 x 80 = 320 ns every access
(d) 90 + (1 - h) x 80 <= 95  =>  1 - h <= 0.0625  =>  h >= 0.9375
    check: 0.9375 x 90 + 0.0625 x 170 = 84.375 + 10.625 = 95 ns

তিন স্তরের টেবিলে miss-এ চারবার মেমরি (তিনটি টেবিল + ডেটা)। TLB না থাকলে ৩২০ ns, TLB-সহ ১০২ — চার স্তরের x86-64 টেবিল বাস্তবে চলে শুধু উঁচু hit ratio-র জোরে।

উদাহরণ ৬.৬ (সহজ) — segmentation

প্রশ্ন: Segment table (base, limit): ০ → (২০০০, ৫০০), ১ → (৫২০০, ৩০০), ২ → (৮০০, ১০০০), ৩ → (৭০০০, ১২০০)। (০, ৪৩০), (১, ৩০০), (২, ৯৯৯), (৩, ১২৫০), (১, ১২)-এর physical ঠিকানা?

(0, 430) : 430 < 500   -> 2000 + 430 = 2430
(1, 300) : 300 < 300 ? no -> TRAP (valid offsets 0..299)
(2, 999) : 999 < 1000  -> 800 + 999  = 1799
(3, 1250): 1250 < 1200 ? no -> TRAP
(1, 12)  : 12 < 300    -> 5200 + 12  = 5212

(১, ৩০০)-ই আসল ফাঁদ: offset limit-এর সমান হলে বৈধ নয়, কারণ limit হলো দৈর্ঘ্য। Segment-গুলো মেমরিতে ক্রমে না থাকলেও (segment ২ সবার নিচে) কিছু যায় আসে না।

নিজে করুন — ভাগ ৬

নি ৬.১(মাঝারি) Hole (KiB): ৩০০, ৬০০, ৩৫০, ২০০, ৭৫০, ১২৫; অনুরোধ ১১৫, ৫০০, ৩৫৮, ২০০, ৩৭৫. চার fit-এ কোনটি ব্যর্থ হয়?

First fit: H1, H2, H5, H3, H5 — সব বসে। Best fit: H6, H2, H5, H4, H5 — সব বসে। Worst fit: H5, H5, H2, H3, তারপর ৩৭৫ ব্যর্থ (বাকি ৩০০, ২৪২, ১৫০, ২০০, ১৩৫, ১২৫)। Next fit: H1, H2, H5, H5, তারপর ৩৭৫ ব্যর্থ (বাকি ১৮৫, ১০০, ৩৫০, ২০০, ১৯২, ১২৫)।

নি ৬.২(মাঝারি) ২৫৬ KiB buddy-তে ক্রমে ২০, ৩৫, ৬৪, ১০ KiB চাইলে কে কোথায় বসে, মোট internal fragmentation কত?

২০ → ৩২@০; ৩৫ → ৬৪@৬৪; ৬৪ → ৬৪@১২৮; ১০ → ১৬@৩২. অপচয় ১২ + ২৯ + ০ + ৬ = ৪৭ KiB. খালি থাকে ১৬@৪৮ আর ৬৪@১৯২.

নি ৬.৩(সহজ) উদাহরণ ৬.৩-এর টেবিলে logical ১২৩৪৫ আর ২০৫০০-এর কী হয়?

১২৩৪৫: p = ৩, d = ৫৭ → frame ৮ → ৮ × ৪০৯৬ + ৫৭ = ৩২৮২৫. ২০৫০০: p = ৫ — টেবিলে নেই (অবৈধ) → trap (বা valid bit ০ হলে page fault).

নি ৬.৪(মাঝারি) ৩৬-bit virtual address, ৮ KiB page, ৪ byte PTE — সমতল page table কত বড়?

Offset ১৩ bit, page নম্বর ২৩ bit: ২২৩ × ৪ = ৩২ MiB প্রতি প্রসেসে।

নি ৬.৫(কঠিন) m = ৮০, t = ১০ ns, দুই স্তরের টেবিল, রীতি ক. EAT ≤ ১১০ ns রাখতে ন্যূনতম hit ratio?

Hit-এ ৯০, miss-এ ১০ + ৩ × ৮০ = ২৫০: 90 + (1 − h) × 160 ≤ 110 ⟹ 1 − h ≤ 0.125 ⟹ h ≥ ০.৮৭৫.

নি ৬.৬(সহজ) উদাহরণ ৬.৬-এর টেবিলে (২, ১০০০) আর (৩, ০)?

(২, ১০০০): ১০০০ = limit → trap. (৩, ০): ৭০০০.

৭ · মেমরি ২ — demand paging, page replacement আর working set

ঝালিয়ে নিন: পর্ব ৩৫ · Virtual memory, পর্ব ৩৬ · Page replacement, পর্ব ৩৭ · Frame allocation, thrashing আর working set.

সূত্র ও নিয়মের কার্ড

Demand paging-এর EAT: (1 − p) × ma + p × fault service time; সব একই এককে (ns) বসান। Victim dirty হলে service time-এ লেখার সময়ও যোগ হয়।

Replacement: FIFO — সবচেয়ে আগে আনা; OPT — যাকে সবচেয়ে দেরিতে আবার লাগবে; LRU — যাকে সবচেয়ে আগে শেষবার ছোঁয়া হয়েছে; Clock — hand ঘোরে, reference bit ১ হলে ০ করে এগোয়, ০ পেলে সেখানে বসায়। শুরুতে খালি frame ভরার fault-গুলোও গোনা হয়।

Belady: FIFO-তে frame বাড়ালে fault বাড়তে পারে; LRU আর OPT stack algorithm, তাদের হয় না।

Frame ভাগ: proportional ai = ⌊si/S × m⌋. Working set WS(t, Δ) = শেষ Δটি reference-এ (t-সহ) ছোঁয়া আলাদা page; D = ΣWSSi > m হলে thrashing-এর ঝুঁকি — একটি প্রসেস স্থগিত করুন।

উদাহরণ ৭.১ (সহজ) — EAT

ma = ১৫০ ns, fault service ৬ ms, p = ০.০০১:

6 ms = 6,000,000 ns
EAT = 0.999 x 150 + 0.001 x 6,000,000 = 149.85 + 6000 = 6149.85 ns   (about 41 x slower)

হাজারে একটি fault-এই মেমরি ৪১ গুণ ধীর — একক রূপান্তর ভুললে (৬ লিখে ফেললে) উত্তর আসে প্রায় ১৫০ ns, যা অর্থহীন।

উদাহরণ ৭.২ (মাঝারি) — সর্বোচ্চ fault rate

একই ma আর service-এ ধীরগতি ১০%-এর মধ্যে রাখতে (EAT ≤ ১৬৫ ns) সর্বোচ্চ p?

150 + p x (6,000,000 - 150) <= 165
p <= 15 / 5,999,850 = 2.5 x 10^-6   ->  at most one fault in about 399,990 accesses
উদাহরণ ৭.৩ (কঠিন) — dirty victim

Victim clean হলে service ৬ ms, dirty হলে (আগে ডিস্কে লিখতে হয়) ১৪ ms; victim-দের ৪০% dirty. ma = ১৫০ ns, p = ০.০০০৫. EAT?

service = 0.6 x 6 + 0.4 x 14 = 3.6 + 5.6 = 9.2 ms = 9,200,000 ns
EAT = 0.9995 x 150 + 0.0005 x 9,200,000 = 149.925 + 4600 = 4749.925 ns

Fault rate অর্ধেক হলেও dirty page-এর জন্য EAT ৬১৫০-এর বদলে ৪৭৫০ — অর্ধেকের চেয়ে বেশি। তাই OS ফাঁকা সময়ে dirty page আগেভাগে লিখে রাখে।

উদাহরণ ৭.৪ (মাঝারি) — চার অ্যালগরিদম, ৩টি frame

Reference string: 2 4 3 0 4 1 2 4 5 4 4 2 2 0 2 3 (১৬টি)। খাতায় প্রতিটি কলাম একটি reference, নিচে frame-গুলোর অবস্থা, শেষ সারিতে F (fault) বা H (hit):

ref    2 4 3 0 4 1 2 4 5 4 4 2 2 0 2 3
FIFO f1 2 2 2 0 0 0 0 4 4 4 4 4 4 4 2 2
     f2 . 4 4 4 4 1 1 1 5 5 5 5 5 5 5 3
     f3 . . 3 3 3 3 2 2 2 2 2 2 2 0 0 0
        F F F F H F F F F H H H H F F F   = 11 faults
OPT  f1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3
     f2 . 4 4 4 4 4 4 4 4 4 4 4 4 0 0 0
     f3 . . 3 0 0 1 1 1 5 5 5 5 5 5 5 5
        F F F F H F H H F H H H H F H F   =  8 faults
LRU  f1 2 2 2 0 0 0 2 2 2 2 2 2 2 2 2 2
     f2 . 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3
     f3 . . 3 3 3 1 1 1 5 5 5 5 5 0 0 0
        F F F F H F F H F H H H H F H F   =  9 faults
CLOCK                                     = 10 faults

OPT-এর fault সংখ্যা সবসময় সবচেয়ে কম (বা সমান) — OPT-এর মান দিয়ে নিজের অন্য উত্তর যাচাই করুন: কোনো অ্যালগরিদম OPT-এর চেয়ে কম fault দিলে কোথাও ভুল। Clock এখানে FIFO আর LRU-র মাঝামাঝি (১০); পুরো ছক ক্যালকুলেটরে SHOW = "CLOCK" দিয়ে দেখুন। ৪টি frame-এ: FIFO ১০, OPT ৭, LRU ৯, Clock ১০.

উদাহরণ ৭.৫ (কঠিন) — Belady's anomaly

String: 4 3 5 1 4 3 2 4 3 5 1 5 2. FIFO-তে ৩ আর ৪ frame?

FIFO, 3 frames : 9 faults
FIFO, 4 frames : 10 faults     <- more frames, more faults
LRU,  3 frames : 10 faults
LRU,  4 frames : 8 faults      <- stack algorithm: never worse with more frames

কারণ: LRU-তে n frame-এ মেমরিতে থাকা page-এর সেট সবসময় n + ১ frame-এর সেটের উপসেট (inclusion property) — তাই n + ১-এ hit কখনো কমে না। FIFO-র সেট নির্ভর করে কে কবে এসেছে তার ওপর; ৪টি frame-এ ধাপ ৭-এ 4 বের হয় আর ঠিক পরেই লাগে, যা ৩টি frame-এ ঘটেনি।

উদাহরণ ৭.৬ (মাঝারি) — proportional allocation আর working set

(ক) ৬৪টি frame, তিনটি প্রসেসের আকার ১৫, ৪৫, ১২০ page (S = ১৮০)।

15/180 x 64 = 5.33 -> 5     45/180 x 64 = 16.00 -> 16     120/180 x 64 = 42.67 -> 42
total 63, one frame left over (give it to the free pool, or to the largest remainder: P3)

(খ) String (১-ভিত্তিক সময়): 1 3 3 2 5 1 1 4 2 2 2 6 4 4 6.

t = 6,  Delta = 4 : refs 3..6  = 3 2 5 1      -> WS {1, 2, 3, 5}  WSS 4
t = 10, Delta = 4 : refs 7..10 = 1 4 2 2      -> WS {1, 2, 4}     WSS 3
t = 15, Delta = 4 : refs 12..15 = 6 4 4 6     -> WS {4, 6}        WSS 2
t = 15, Delta = 6 : refs 10..15 = 2 2 6 4 4 6 -> WS {2, 4, 6}     WSS 3

(গ) তিনটি প্রসেসের WSS ৪, ৩, ৫ আর frame ১০: D = ১২ > ১০ — thrashing-এর ঝুঁকি, একটি প্রসেস স্থগিত করে তার frame অন্যদের দিন।

Page replacement ক্যালকুলেটর

REFS, FRAMES বদলান; SHOW-এ যে অ্যালগরিদম দেবেন, তার পুরো ছক ছাপা হবে (frame, hit/fault, কে বের হলো)।

// Page-replacement calculator: FIFO, OPT, LRU, CLOCK. Edit REFS, FRAMES and ALGS, then Run.
// Rules: free frames fill left to right; OPT tie (never used again) -> the one loaded earliest;
// CLOCK: every access sets R = 1; the hand clears R = 1 bits and stops at the first R = 0.
const REFS = "2 4 3 0 4 1 2 4 5 4 4 2 2 0 2 3".split(" ").map(Number);
const FRAMES = 3, ALGS = ["FIFO", "OPT", "LRU", "CLOCK"], SHOW = "LRU";   // SHOW: full table
for (const alg of ALGS) {
  const fr = Array(FRAMES).fill(null), R = Array(FRAMES).fill(0), last = {}, loaded = {};
  let hand = 0, faults = 0;
  REFS.forEach((p, t) => {
    let i = fr.indexOf(p), out = "";
    const hit = i >= 0;
    if (!hit) {
      faults++; i = fr.indexOf(null);
      if (i < 0) {
        if (alg === "CLOCK") { while (R[hand]) { R[hand] = 0; hand = (hand + 1) % FRAMES; }
                               i = hand; hand = (hand + 1) % FRAMES; }
        else {
          const nxt = k => { const j = REFS.indexOf(fr[k], t + 1); return j < 0 ? Infinity : j; };
          const cost = k => alg === "FIFO" ? loaded[fr[k]] : alg === "LRU" ? last[fr[k]] : -nxt(k);
          i = [...fr.keys()].sort((a, b) => cost(a) - cost(b) || loaded[fr[a]] - loaded[fr[b]])[0];
        }
        out = " out " + fr[i];
      }
      fr[i] = p; loaded[p] = t;
    }
    R[i] = 1; last[p] = t;
    if (alg === SHOW) console.log(`${String(t + 1).padStart(2)}  ref ${p}  ${hit ? "hit  " : "FAULT"}  ` +
      fr.map(x => x === null ? "." : x).join(" ") + out);
  });
  console.log(`${alg}: ${faults} faults, ${REFS.length - faults} hits (${FRAMES} frames)`);
}

আউটপুট (LRU-র পূর্ণ ছক):

FIFO: 11 faults, 5 hits (3 frames)
OPT: 8 faults, 8 hits (3 frames)
 1  ref 2  FAULT  2 . .
 2  ref 4  FAULT  2 4 .
 3  ref 3  FAULT  2 4 3
 4  ref 0  FAULT  0 4 3 out 2
 5  ref 4  hit    0 4 3
 6  ref 1  FAULT  0 4 1 out 3
 7  ref 2  FAULT  2 4 1 out 0
 8  ref 4  hit    2 4 1
 9  ref 5  FAULT  2 4 5 out 1
10  ref 4  hit    2 4 5
11  ref 4  hit    2 4 5
12  ref 2  hit    2 4 5
13  ref 2  hit    2 4 5
14  ref 0  FAULT  2 4 0 out 5
15  ref 2  hit    2 4 0
16  ref 3  FAULT  2 3 0 out 4
LRU: 9 faults, 7 hits (3 frames)
CLOCK: 10 faults, 6 hits (3 frames)

LRU-র ছকটি উদাহরণ ৭.৪-এর LRU সারির সাথে কলাম ধরে মেলান — frame-এর ক্রম একই (খালি frame বাঁ থেকে ভরে)। ছকের প্রতিটি “out” কে বের হলো দেখায়; যেমন ধাপ ৭-এ 2 এসে 0-কে সরায়, কারণ 0 সবচেয়ে আগে (ধাপ ৪) ছোঁয়া হয়েছিল। FRAMES = 4 আর উদাহরণ ৭.৫-এর string দিয়ে Belady নিজে দেখুন।

নিজে করুন — ভাগ ৭

নি ৭.১(মাঝারি) String 1 2 3 2 4 1 3 2 4 1, ৩টি frame — FIFO, LRU, OPT আর Clock-এ fault কত? কোন ফলটি অবাক করে?

FIFO ৬, LRU ৯, OPT ৫, Clock ৬. এখানে LRU FIFO-র চেয়ে খারাপ — string-টি ১, ৩, ২, ৪ ঘুরে ঘুরে ছোঁয়, আর LRU ঠিক যাকে পরে লাগবে তাকেই সরায়। “LRU সবসময় FIFO-র চেয়ে ভালো” ভুল; শুধু OPT সবসময় সেরা।

নি ৭.২(মাঝারি) ma = ১০০ ns, fault service ৫ ms. EAT ≤ ২০০ ns রাখতে সর্বোচ্চ fault rate?

100 + p(5,000,000 − 100) ≤ 200 ⟹ p ≤ 100/4,999,900 ≈ ২.০ × ১০−৫ — প্রায় ৫০,০০০ অ্যাক্সেসে একটি।

নি ৭.৩(সহজ) ৫০টি frame, প্রসেসের আকার ১২, ৪০, ৯৮ page — proportional ভাগ?

S = ১৫০: ৪.০০ → ৪, ১৩.৩৩ → ১৩, ৩২.৬৭ → ৩২; মোট ৪৯, একটি বাকি।

নি ৭.৪(সহজ) উদাহরণ ৭.৬(খ)-এর string-এ t = ৮, Δ = ৩-এ working set?

Reference ৬–৮ = 1 1 4 → {1, 4}, WSS ২.

৮ · ডিস্ক, I/O, ফাইল সিস্টেম, RAID আর queueing

ঝালিয়ে নিন: পর্ব ৩৯ · I/O system, পর্ব ৪০ · ডিস্ক আর disk scheduling, পর্ব ৪৩ · File system-এর ভেতর, পর্ব ৪৫ · RAID, পর্ব ৫৭ · পারফরম্যান্স আর observability.

সূত্র ও নিয়মের কার্ড

Access time = seek + rotational latency (গড়ে অর্ধেক ঘূর্ণন = ৩০,০০০/RPM ms) + transfer (byte ÷ হার, বা sector ÷ প্রতি track-এর sector × এক ঘূর্ণন) + controller overhead.

Scheduling: FCFS আসার ক্রমে; SSTF সবচেয়ে কাছের (tie-তে ছোট cylinder); SCAN এক দিকে প্রান্ত পর্যন্ত, তারপর উল্টো; LOOK শেষ অনুরোধ পর্যন্ত; C-SCAN প্রান্তে গিয়ে অন্য প্রান্তে লাফ, একই দিকে আবার; C-LOOK শেষ অনুরোধ থেকে অপর দিকের শেষ অনুরোধে লাফ। লাফসহ আর লাফ ছাড়া দুটি মোটই লিখুন।

Buffering (n টি block, ডিভাইসে ভরতে T, কাজে C, কপিতে M): buffer ছাড়া n(T + C); single = T + M + C + (n − 1)(max(C, T) + M); double = T + C + (n − 1)·max(C, T).

Inode: প্রতি block-এ k = B/pointer-আকার pointer; সর্বোচ্চ ফাইল = (direct + k + k² + k³) × B. FAT: cluster-এর সংখ্যা × entry-র আকার। Bitmap: প্রতি block-এ ১ bit.

RAID (N টি ডিস্ক, প্রতিটি D): 0 → ND; 1/10 → ND/2; 5 → (N − 1)D; 6 → (N − 2)D. MTTDL (স্বাধীন ব্যর্থতা ধরে): mirror জোড়া MTTF²/(2 × MTTR); RAID 5: MTTF²/(N(N − 1) × MTTR).

M/M/1: ρ = λ/μ (< ১ হতে হবে); গড় response R = 1/(μ − λ); সিস্টেমে গড় সংখ্যা L = ρ/(1 − ρ); সারিতে অপেক্ষা Wq = R − 1/μ; Little: L = λR.

উদাহরণ ৮.১ (সহজ) — access time

৭২০০ RPM, গড় seek ৬ ms, transfer ১৫০ MB/s, ৪ KiB block, controller ০.২ ms.

one rotation = 60000 / 7200 = 8.333 ms   -> average latency 4.167 ms
transfer = 4096 B / 150,000,000 B/s = 0.0273 ms
total = 6 + 4.167 + 0.0273 + 0.2 = 10.394 ms

মোট সময়ের প্রায় ৯৮% যায় arm সরানো আর ঘূর্ণনের অপেক্ষায়; ডেটা পড়ায় যায় ০.৩%-এরও কম — এ কারণেই disk scheduling আর ক্রমিক (sequential) পড়া এত জরুরি।

উদাহরণ ৮.২ (মাঝারি) — sector দিয়ে transfer, আর random বনাম sequential

(ক) ১০,০০০ RPM, প্রতি track-এ ৫০০ sector, গড় seek ৪ ms, পরপর ৮টি sector পড়তে কত? (খ) উদাহরণ ৮.১-এর ডিস্কে ১ MiB ফাইল ২৫৬টি ছড়ানো ৪ KiB block হিসেবে বনাম একটানা পড়লে (controller বাদ)?

(a) rotation 6 ms, latency 3 ms, transfer = 8/500 x 6 = 0.096 ms -> 4 + 3 + 0.096 = 7.096 ms
(b) random    : 256 x (6 + 4.167 + 0.0273) = 256 x 10.194 = 2609.7 ms
    sequential: 6 + 4.167 + 1,048,576 / 150,000,000 s (6.99 ms) = 17.16 ms   -> about 152 x faster
উদাহরণ ৮.৩ (মাঝারি → কঠিন) — ছয়টি disk scheduling

প্রশ্ন: Cylinder ০–১৯৯, head ৮৫-এ, প্রথমে বড় cylinder-এর দিকে যাচ্ছে। অনুরোধ (আসার ক্রমে): 140, 30, 175, 60, 92, 12, 110, 160. প্রতিটির মোট head movement?

FCFS  : 85-140-30-175-60-92-12-110-160
        55 + 110 + 145 + 115 + 32 + 80 + 98 + 50                    = 685
SSTF  : 85-92-110-140-160-175-60-30-12
        7 + 18 + 30 + 20 + 15 + 115 + 30 + 18                       = 253
SCAN  : 85-92-110-140-160-175-199-60-30-12   (85->199) 114 + (199->12) 187 = 301
LOOK  : 85-...-175-60-30-12                   (85->175)  90 + (175->12) 163 = 253
C-SCAN: 85-...-175-199 ~> 0-12-30-60          114 + [199] + 60 = 373  (without jump 174)
C-LOOK: 85-...-175 ~> 12-30-60                 90 + [163] + 48 = 301  (without jump 138)

SSTF-এ ৮৫ থেকে কাছের ৯২ (৭ দূরে), ৬০ নয় (২৫)। এই সারিতে SSTF আর LOOK কাকতালীয়ভাবে একই পথ নেয়; SCAN প্রান্তে (১৯৯) গিয়ে ৪৮ বাড়তি চলে। SSTF-এর tie-নিয়মের ছোট উদাহরণ: head ৫০, সারি 60, 40, 90 — 40 আর 60 দুটিই ১০ দূরে, ছোট cylinder 40 আগে: ১০ + ২০ + ৩০ = ৬০.

উদাহরণ ৮.৪ (মাঝারি) — buffering

১২টি block; ডিভাইস একটি block buffer-এ আনে T = ৪ ms-এ, process একটি block-এ C = ৬ ms কাজ করে, buffer থেকে কপি M = ১ ms.

no buffer : 12 x (4 + 6)                 = 120 ms
single    : 4 + 1 + 6 + 11 x (max(6,4) + 1) = 11 + 77 = 88 ms
double    : 4 + 6 + 11 x max(6,4)          = 10 + 66 = 76 ms

Double buffering-এ ডিভাইস আর CPU পুরোপুরি সমান্তরালে চলে, তাই ধীরতর পক্ষ (এখানে C = ৬) গতি ঠিক করে। C < T হলে ডিভাইসই সীমা হতো।

উদাহরণ ৮.৫ (মাঝারি → কঠিন) — inode-এর সর্বোচ্চ ফাইল আর byte খোঁজা

Block ২ KiB, pointer ৮ byte, inode-এ ১০টি direct, একটি করে single, double আর triple indirect.

k = 2048 / 8 = 256 pointers per block
direct 10 x 2 KiB = 20 KiB
single 256 x 2 KiB = 512 KiB
double 256^2 x 2 KiB = 128 MiB
triple 256^3 x 2 KiB = 32 GiB
max = (10 + 256 + 65,536 + 16,777,216) x 2048 = 34,494,500,864 B  ~ 32.13 GiB

byte 300,000   -> block 300000 div 2048 = 146 ; 146 - 10 = 136 -> single indirect, entry 136
byte 5,000,000 -> block 2441 ; 2441 - 266 = 2175 -> double: outer 2175 div 256 = 8, inner 127

Inode মেমরিতে আছে ধরে ৩০০,০০০ byte পড়তে ২টি disk read (indirect block + data), ৫০ লাখ byte-এ ৩টি (outer, inner, data). ৮ byte pointer ৪ byte-এর তুলনায় প্রতি block-এ অর্ধেক pointer ধরে — সর্বোচ্চ আকার অনেক কমে যায়।

উদাহরণ ৮.৬ (সহজ) — FAT আর bitmap 
FAT32, 32 GiB volume, 8 KiB clusters: 2^35 / 2^13 = 2^22 = 4,194,304 clusters
   x 4 B per entry = 16 MiB per FAT copy (FAT32 usually keeps 2 copies -> 32 MiB)
bitmap, 2 TiB disk, 4 KiB blocks: 2^41 / 2^12 = 2^29 blocks -> 2^29 bits = 2^26 B = 64 MiB
উদাহরণ ৮.৭ (মাঝারি) — RAID-এর ধারণক্ষমতা আর MTTDL 
6 disks x 4 TB : RAID 0 = 24 TB   RAID 10 = 12 TB   RAID 5 = 20 TB   RAID 6 = 16 TB
mirror pair, MTTF 500,000 h, MTTR 20 h : 500,000^2 / (2 x 20) = 6.25 x 10^9 h ~ 713,470 years
RAID 5, N = 5, MTTF 200,000 h, MTTR 24 h : 4 x 10^10 / (5 x 4 x 24) = 8.33 x 10^7 h ~ 9,513 years
first failure among 50 disks of MTTF 1,000,000 h : 1,000,000 / 50 = 20,000 h ~ 833 days

শেষ লাইনটি সতর্কবার্তা: একটি ডিস্কের MTTF ১১৪ বছর শোনালেও ৫০টির মধ্যে প্রথম ব্যর্থতা গড়ে আড়াই বছরের কম সময়ে। আর MTTDL-এর সূত্র স্বাধীন ব্যর্থতা ধরে — একই ব্যাচের ডিস্ক বা rebuild-এর চাপে বাস্তবে অনেক কম (পর্ব ৪৫)।

উদাহরণ ৮.৮ (মাঝারি) — M/M/1

একটি ডিস্কে সেকেন্ডে গড়ে ৪০টি অনুরোধ আসে, গড় সেবা ২০ ms (μ = ৫০/s).

rho = 40/50 = 0.8 (80% utilization)
R  = 1 / (50 - 40) = 0.1 s = 100 ms      L  = 0.8 / 0.2 = 4 requests
Wq = 100 - 20 = 80 ms                    Lq = rho^2 / (1 - rho) = 3.2
check Little: L = lambda x R = 40 x 0.1 = 4
lambda = 45 /s  -> R = 1 / 5 = 200 ms    (12.5% more load, response doubles)
R <= 50 ms      -> 1/(50 - lambda) <= 0.05 -> lambda <= 30 /s

৮০% utilization-এ সেবার ২০ ms-এর বদলে মোট ১০০ ms; ৯০%-এ ২০০ ms. শেষ ১০% চাপ যোগ করার দাম সবচেয়ে বেশি — ক্যাপাসিটি পরিকল্পনার মূল শিক্ষা।

Disk scheduling ক্যালকুলেটর

HEAD, DIR, QUEUE আর cylinder-সীমা বদলান; ছয়টি অ্যালগরিদমের পথ আর মোট, C-SCAN/C-LOOK-এ ফেরার লাফসহ ও বাদে। “~” চিহ্ন মানে লাফ — এই পথে কোনো অনুরোধ সারা হয় না।

// Disk-scheduling calculator: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK. Edit and Run.
// SSTF tie -> smaller cylinder. SCAN/C-SCAN touch the disk edge; "~x" = return jump (no service).
const LO = 0, HI = 199, HEAD = 85, DIR = "up";               // DIR: "up" (toward HI) or "down"
const QUEUE = [140, 30, 175, 60, 92, 12, 110, 160];
function order(alg) {
  const up = QUEUE.filter(x => x >= HEAD).sort((a, b) => a - b);
  const dn = QUEUE.filter(x => x < HEAD).sort((a, b) => b - a);
  const [first, second, edge, far] = DIR === "up" ? [up, dn, HI, LO] : [dn, up, LO, HI];
  if (alg === "FCFS") return [...QUEUE];
  if (alg === "SSTF") {
    const left = [...QUEUE], out = []; let cur = HEAD;
    while (left.length) {
      left.sort((a, b) => Math.abs(a - cur) - Math.abs(b - cur) || a - b);
      cur = left.shift(); out.push(cur);
    }
    return out;
  }
  if (alg === "SCAN") return [...first, edge, ...second];
  if (alg === "LOOK") return [...first, ...second];
  if (!second.length) return [...first];                        // nothing left behind the head
  const back = [...second].reverse();                           // circular: restart from the far side
  if (alg === "C-SCAN") return [...first, edge, "~" + far, ...back];
  return [...first, "~" + back[0], ...back.slice(1)];           // C-LOOK
}
for (const alg of ["FCFS", "SSTF", "SCAN", "C-SCAN", "LOOK", "C-LOOK"]) {
  let cur = HEAD, move = 0, jump = 0;
  const seq = order(alg);
  for (const x of seq) {
    const c = Number(String(x).replace("~", ""));
    if (String(x)[0] === "~") jump += Math.abs(c - cur); else move += Math.abs(c - cur);
    cur = c;
  }
  console.log(`${alg.padEnd(6)} ${HEAD} -> ${seq.join(" -> ")}`);
  console.log(`       total = ${move + jump}` + (jump ? ` (without the return jump: ${move})` : ""));
}

আউটপুট:

FCFS   85 -> 140 -> 30 -> 175 -> 60 -> 92 -> 12 -> 110 -> 160
       total = 685
SSTF   85 -> 92 -> 110 -> 140 -> 160 -> 175 -> 60 -> 30 -> 12
       total = 253
SCAN   85 -> 92 -> 110 -> 140 -> 160 -> 175 -> 199 -> 60 -> 30 -> 12
       total = 301
C-SCAN 85 -> 92 -> 110 -> 140 -> 160 -> 175 -> 199 -> ~0 -> 12 -> 30 -> 60
       total = 373 (without the return jump: 174)
LOOK   85 -> 92 -> 110 -> 140 -> 160 -> 175 -> 60 -> 30 -> 12
       total = 253
C-LOOK 85 -> 92 -> 110 -> 140 -> 160 -> 175 -> ~12 -> 30 -> 60
       total = 301 (without the return jump: 138)

প্রতিটি মোট উদাহরণ ৮.৩-এর সাথে মেলে। DIR = "down" করলে নিচের “নিজে করুন ৮.১”-এর উত্তর পাবেন। SSTF-এর tie-নিয়ম || a - b অংশে — ছোট cylinder আগে।

সব সূত্র এক জায়গায় — দ্রুত যাচাই

এই প্রোগ্রাম পাতার বাকি সূত্রগুলো এক লাইনে একটি করে হিসাব করে — ভাগ ২, ৬, ৭ আর ৮-এর উদাহরণের মান দিয়ে। নিজের অঙ্কের সংখ্যা বসিয়ে মিলিয়ে নিন।

// One-line formula checker. Change any number, press Run, compare with your hand answer.
const r = (x, d = 3) => +x.toFixed(d);
const util = (p, n) => 1 - p ** n;                                 // CPU busy with n jobs, I/O wait p
const amat = (h1, m1, h2, m2, mem) => h1 + m1 * (h2 + m2 * mem);   // two-level cache
const eff = (q, s) => q / (q + s);                                 // RR: useful share of CPU time
const amdahl = (f, n) => 1 / ((1 - f) + f / n);                    // f = parallel fraction
const tlbA = (h, t, m, L) => h * (t + m) + (1 - h) * (t + (L + 1) * m);   // TLB time counted
const tlbB = (h, m, L) => h * m + (1 - h) * (L + 1) * m;                  // TLB time ignored
const dpEAT = (p, ma, svc) => (1 - p) * ma + p * svc;             // demand paging, all in ns
const disk = (seek, rpm, bytes, MBps, ctrl) => seek + 30000 / rpm + bytes / (MBps * 1e3) + ctrl; // ms
const inode = (B, ptr, nd) => { const k = B / ptr; return (nd + k + k ** 2 + k ** 3) * B; };   // bytes
const mm1 = (lam, mu) => ({ rho: lam / mu, R: 1 / (mu - lam), L: lam / (mu - lam) });
console.log("1-p^n   p=0.7, n=1,2,4,7 :", [1, 2, 4, 7].map(n => r(util(0.7, n), 4)).join(", "));
console.log("AMAT    2 + 0.05(12 + 0.3*150)   =", r(amat(2, 0.05, 12, 0.3, 150)), "cycles");
console.log("q/(q+s) q=4, s=0.5              =", r(eff(4, 0.5) * 100, 1) + "%");
console.log("Amdahl  f=0.8, n=4 / n=16        =", r(amdahl(0.8, 4), 2), "/", r(amdahl(0.8, 16), 2));
console.log("TLB     h=0.9, t=10, m=80, 1 lvl =", r(tlbA(0.9, 10, 80, 1), 1), "ns (A),", r(tlbB(0.9, 80, 1), 1), "ns (B)");
console.log("TLB     h=0.95, 3 levels         =", r(tlbA(0.95, 10, 80, 3), 1), "ns (A),", r(tlbB(0.95, 80, 3), 1), "ns (B)");
console.log("Paging  p=0.001, 150 ns, 6 ms    =", r(dpEAT(0.001, 150, 6e6), 2), "ns");
console.log("Disk    6 ms, 7200 rpm, 4 KiB    =", r(disk(6, 7200, 4096, 150, 0.2), 3), "ms");
console.log("Inode   2 KiB block, 8 B ptr, 10 =", inode(2048, 8, 10), "bytes =", r(inode(2048, 8, 10) / 2 ** 30, 3), "GiB");
const q = mm1(40, 50);
console.log("M/M/1   lam=40, mu=50 /s         = rho", q.rho, ", R", r(q.R * 1000, 1), "ms, L", r(q.L, 2));

আউটপুট:

1-p^n   p=0.7, n=1,2,4,7 : 0.3, 0.51, 0.7599, 0.9176
AMAT    2 + 0.05(12 + 0.3*150)   = 4.85 cycles
q/(q+s) q=4, s=0.5              = 88.9%
Amdahl  f=0.8, n=4 / n=16        = 2.5 / 4
TLB     h=0.9, t=10, m=80, 1 lvl = 98 ns (A), 88 ns (B)
TLB     h=0.95, 3 levels         = 102 ns (A), 92 ns (B)
Paging  p=0.001, 150 ns, 6 ms    = 6149.85 ns
Disk    6 ms, 7200 rpm, 4 KiB    = 10.394 ms
Inode   2 KiB block, 8 B ptr, 10 = 34494500864 bytes = 32.126 GiB
M/M/1   lam=40, mu=50 /s         = rho 0.8 , R 100 ms, L 4

প্রতিটি লাইন একটি উদাহরণের উত্তর: ২.১ (০.৩, ০.৫১, ০.৭৫৯৯, আর ২.২-এর ০.৯১৭৬), ২.৪ (৪.৮৫), ২.৬ (৮৮.৯%), ২.৮ (২.৫ আর ৪), ৬.৫ (৯৮/৮৮ আর ১০২/৯২), ৭.১ (৬১৪৯.৮৫), ৮.১ (১০.৩৯৪), ৮.৫ (৩৪,৪৯৪,৫০০,৮৬৪ byte) আর ৮.৮ (১০০ ms, L = ৪)। disk()-এ গড় latency সরাসরি ৩০,০০০/RPM ms, আর MB/s-কে ১০৬ ধরা — অন্য রীতিতে (MiB/s) transfer সামান্য বদলাবে।

নিজে করুন — ভাগ ৮

নি ৮.১(মাঝারি) উদাহরণ ৮.৩-এর সারিতে head প্রথমে ছোট cylinder-এর দিকে গেলে SCAN, LOOK, C-SCAN আর C-LOOK-এর মোট কত?

SCAN 85-60-30-12-0-92-…-175: ৮৫ + ১৭৫ = ২৬০. LOOK: ৭৩ + ১৬৩ = ২৩৬. C-SCAN: ৮৫ + [১৯৯] + ১০৭ = ৩৯১ (লাফ বাদে ১৯২)। C-LOOK: ৭৩ + [১৬৩] + ৮৩ = ৩১৯ (লাফ বাদে ১৫৬)।

নি ৮.২(মাঝারি) ৪ KiB block, ৪ byte pointer, ১২টি direct + single + double + triple — সর্বোচ্চ ফাইল?

k = ১০২৪: ৪৮ KiB + ৪ MiB + ৪ GiB + ৪ TiB ≈ ৪.০০৪ TiB. এটি শুধু pointer-কাঠামোর তাত্ত্বিক সীমা; আসল file system-এ অন্য field-এর সীমার কারণে সর্বোচ্চ ফাইল এর চেয়ে ছোট হতে পারে।

নি ৮.৩(সহজ) ৮টি ২ TB ডিস্কে RAID 5, RAID 6 আর RAID 10-এর ব্যবহারযোগ্য জায়গা?

RAID 5 = ৭ × ২ = ১৪ TB, RAID 6 = ১২ TB, RAID 10 = ৮ TB.

নি ৮.৪(মাঝারি) উদাহরণ ৮.৮-এর ডিস্কে λ = ৪৫/s হলে ρ, R আর L কত?

ρ = ০.৯, R = 1/(50 − 45) = ২০০ ms, L = 0.9/0.1 = ৯ (Little: ৪৫ × ০.২ = ৯ ✓)।

নি ৮.৫(কঠিন) ১৫,০০০ RPM ডিস্ক, গড় seek ৩.৫ ms, ২০০ MB/s, ৬৪ KiB পড়তে কত সময় (controller বাদ)?

Latency ৩০,০০০/১৫,০০০ = ২ ms; transfer ৬৫,৫৩৬/২০০,০০০,০০০ s = ০.৩২৮ ms; মোট ≈ ৫.৮২৮ ms.

৯ · AI-এর যুগে — numerical-এর উত্তর যাচাই

AI-কে একটি scheduling বা page replacement-এর অঙ্ক দিলে উত্তর আসে পরিষ্কার টেবিলে, আত্মবিশ্বাসী গলায় — আর বেশ প্রায়ই ভুল। ভুলের ধরনও চেনা: AI নিঃশব্দে একটি নিয়ম ধরে নেয় যা আপনার প্রশ্নের নিয়ম নয়, মাঝপথে একটি সংখ্যা ভুল করে আর বাকি সব সেই ভুলের ওপর দাঁড়ায়, বা একক মিশিয়ে ফেলে। টেবিল দেখতে নিখুঁত হলেও যোগফল মেলে না। এই পাতার ক্যালকুলেটর আর চেক-যোগফল ঠিক এই কাজের জন্য।

AI সাধারণত যেখানে ভুল করে

AI-এর ভুলপরিণামকীভাবে ধরবেন
শুরুর বা মাঝের idle ফাঁক বাদ দিয়ে Gantt chartসব CT, TAT ভুলশেষ সময় = মোট burst + idle — মিলিয়ে দেখুন
RR-এ নতুন আগমন আর থামানো প্রসেসের ক্রম নিজের মতোপ্রতিটি প্রসেসের সংখ্যা বদলায়প্রতিটি quantum-সীমায় সারির তালিকা চেয়ে নিন
“বড় সংখ্যা = বেশি priority” ধরে নেওয়াপুরো চার্ট উল্টে যায়প্রম্পটে নিয়ম লিখুন; প্রথম সিদ্ধান্ত হাতে মেলান
Banker's-এ Need-এর বদলে Max তুলনাsafe অবস্থাকে unsafe বলাশেষে Work = মোট resource কি না দেখুন
Request বিচারে Need ও Available যাচাই বাদ দিয়ে সরাসরি safety“error” বা “wait”-কে “deny” বলাতিন ধাপ আলাদা লিখতে বলুন
ms আর ns মিশিয়ে demand-paging EATহাজার গুণ ভুলসব একক এক লাইনে রূপান্তর চেয়ে নিন
“U > Liu–Layland সীমা, তাই schedulable নয়”ভুল সিদ্ধান্তRTA চালাতে বলুন; শর্তটি শুধু পর্যাপ্ত
C-SCAN/C-LOOK-এ লাফ কখনো গোনা, কখনো নয়বইয়ের উত্তরের সাথে অমিলদুটি মোটই চেয়ে নিন
Inode-এর হিসাবে direct pointer বা একটি স্তর বাদসর্বোচ্চ আকার কম আসেপ্রতিটি স্তর আলাদা লাইনে লিখে যোগ করুন

AI-কে উত্তরদাতা নয়, যাচাইকারী আর প্রশ্ন-বানানোর সহকারী হিসেবে ব্যবহার করুন:

আমি অপারেটিং সিস্টেমের numerical অনুশীলন করছি। নিচে প্রশ্ন, নিয়ম আর আমার হাতে করা সমাধান দিলাম। প্রশ্ন: [process table / reference string / disk queue / Banker's অবস্থা] নিয়ম: tie-তে চলতি প্রসেস থাকবে, তারপর আগে আসা; RR-এ একই মুহূর্তে নতুন প্রসেস আগে সারিতে; ছোট priority সংখ্যা = বেশি জরুরি; C-SCAN-এ ফেরার লাফসহ আর বাদে দুই মোটই; একক ms. আমার সমাধান: [Gantt chart + টেবিল পেস্ট করুন] ১. পুরো উত্তর আগে দিও না। আমার সমাধানের প্রথম যে ধাপে ভুল আছে, শুধু সেই ধাপটি বলো। ২. তুমি নিজে হিসাব করলে প্রতিটি সিদ্ধান্তের মুহূর্তে (arrival, quantum শেষ, সমাপ্তি) ready queue লিখে দেখাও। ৩. শেষে একটি চেক দাও: ΣWT = ΣTAT − ΣBT, বা Work = মোট resource, বা hit + fault = দৈর্ঘ্য। ৪. একই নিয়মে একটি নতুন, ফাঁদওয়ালা প্রশ্ন দাও (idle ফাঁক, tie, বা সীমার মান) — উত্তর লুকিয়ে রাখো।

যাচাইয়ের চেকলিস্ট

নিজেকে যাচাই করুন

প্রতিটি প্রশ্নে খাতায় হিসাব করে তবে উত্তর বাছুন। ভুল হলে কারণসহ ব্যাখ্যা পাবেন।

ক্রমএকটি preemptive scheduling numerical খাতায় সমাধানের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. নিয়ম লেখা — tie, preemption, context switch-এর খরচ
  2. t = ০ থেকে প্রতিটি arrival আর সমাপ্তিতে সিদ্ধান্ত নিয়ে Gantt chart আঁকা, idle সহ
  3. চার্ট থেকে প্রতিটি প্রসেসের CT আর প্রথম শুরুর সময় পড়া
  4. TAT = CT − AT, WT = TAT − BT, RT = শুরু − AT হিসাব করে টেবিলে লেখা
  5. গড় বের করে ΣWT = ΣTAT − ΣBT দিয়ে যাচাই করা

(সহজ) প্রতিটি কাজ সময়ের ৫০% I/O-র অপেক্ষায় থাকে। মেমরিতে ৩টি কাজ থাকলে 1 − pⁿ মডেলে CPU ব্যবহার কত?

  • ৮৭.৫%
  • ১২.৫%
  • ৫০%
  • ১৫০% (অর্থাৎ পূর্ণ ব্যস্ত)

(মাঝারি) SRTF: P1 (AT 0, BT 6), P2 (AT 1, BT 2), P3 (AT 2, BT 1). নিয়ম: বাকি সময় সমান হলে চলতি প্রসেস চলতে থাকে। P2-এর completion time কত?

  • 4
  • 3
  • 9
  • 2

(মাঝারি) fork(); fork() && fork(); চালানোর পর মূল প্রসেসসহ মোট কতটি প্রসেস থাকে?

  • 8
  • 4
  • 6
  • 5

(মাঝারি) Reference string 3 1 2 1 4 3 1 5 2 1, ৩টি frame (শুরুতে খালি)। LRU-তে কতটি page fault?

  • 8
  • 6
  • 10
  • 7

(মাঝারি) এক স্তরের page table, TLB hit ratio 0.85, TLB খোঁজা 15 ns, মেমরি 90 ns. TLB-র সময় গুনে (hit-এ t + m, miss-এ t + 2m) EAT কত?

  • 103.5 ns
  • 118.5 ns
  • 105 ns
  • 195 ns

(সহজ) ৬টি প্রসেসের প্রত্যেকের একই ধরনের resource-এর সর্বোচ্চ ৩টি unit লাগে। Deadlock কখনো না হওয়ার জন্য ন্যূনতম কতটি unit দরকার?

  • 18
  • 12
  • 13
  • 7

(কঠিন) Cylinder 0–199, head 50, বড় cylinder-এর দিকে। অনুরোধ: 20, 80, 30, 95, 60. C-LOOK-এ ফেরার লাফসহ মোট head movement কত?

  • 55
  • 120
  • 328
  • 130

(কঠিন) Block 1 KiB, pointer 4 byte, inode-এ 10টি direct, একটি single আর একটি double indirect (triple নেই)। সর্বোচ্চ ফাইল কত?

  • ≈ 64.26 MiB
  • ঠিক 64 MiB
  • 266 KiB
  • ≈ 16 GiB

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বে আসা শব্দগুলো এখানে একসাথে:

মনে রাখুন

  1. নিয়ম আগে: tie, RR-এর ক্রম, priority-র দিক, লাফ গোনা, TLB-র রীতি — উত্তরের প্রথম লাইনে লিখুন; নিয়ম বদলালে উত্তর বদলায়।
  2. Scheduling: idle সহ পুরো Gantt chart, তারপর CT → TAT → WT → RT; চেক ΣWT = ΣTAT − ΣBT. SRTF গড়ে সেরা, RR ন্যায্য, priority জরুরি কাজের জন্য, MLFQ ছোট কাজকে ওপরে রাখে।
  3. Deadlock: n(k − 1) + 1; Banker's-এ আগে Need, প্রতিবার P0 থেকে খোঁজা, শেষে Work = মোট; request-এ error → wait → safety, এই তিন ধাপ।
  4. মেমরি: page/offset ভাগ, PTE গুণ করে টেবিলের আকার, দুই রীতির EAT; demand paging-এ ns-এ রূপান্তর; OPT সর্বনিম্ন, LRU stack algorithm, FIFO-তে Belady.
  5. ডিস্ক ও বাকি: seek + latency + transfer; C-SCAN/C-LOOK দুই মোট; inode-এ স্তর ধরে যোগ; RAID-এর জায়গা আর MTTDL; M/M/1-এ R = 1/(μ − λ). শেষে ক্যালকুলেটরে মিলিয়ে নিন।

পরের পর্বে: পুরো কোর্সের MCQ প্রশ্নব্যাংক — মডিউল ধরে সাজানো, প্রতিটি অপশনের ব্যাখ্যাসহ। এই পাতার হিসাবগুলো সেখানে দ্রুত সিদ্ধান্তে কাজে লাগবে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান