Scheduling (ဘယ် process ကို CPU အချိန် ပေးမလဲ ဆုံးဖြတ်ခြင်း)

A1.3.3: Compare different approaches to scheduling
မြန်မာလို: Scheduling လုပ်တဲ့ မတူညီတဲ့ နည်းလမ်းတွေကို compare (အားလုံးကို တစ်လျှောက်လုံး ကိုးကားပြီး တူတဲ့ အချက်တွေကို ဖော်ပြ) လုပ်နိုင်ရပါမယ်။

အဓိက အယူအဆများ

Scheduling ဘာကြောင့် အရေးကြီးသလဲ

Core (ညွှန်ကြားချက်တွေကို သီးခြား run နိုင်တဲ့ processor ထဲက processing unit) တစ်ခုတည်း ရှိတဲ့ CPU (ကွန်ပျူတာရဲ့ အဓိက processor) က တစ်ကြိမ်မှာ process (run နေတဲ့ program) တစ်ခုကိုပဲ execute (run) လုပ်နိုင်ပါတယ်။ ဘယ်အချိန်မှာမဆို CPU အချိန်ကို လုယူနေတဲ့ process ဒါဇင်ချီ၊ ရာချီတောင် ရှိနိုင်ပါတယ်: သင့် web browser (ဝဘ်စာမျက်နှာ ဖွင့်တဲ့ software)၊ နောက်ကွယ်မှာ run နေတဲ့ update တွေ၊ antivirus scan (virus ရှာဖွေ စစ်ဆေးမှု) တစ်ခု၊ operating system (OS၊ ကွန်ပျူတာကို စီမံတဲ့ အဓိက software) ကိုယ်တိုင်။ Scheduler ဆိုတာ နောက် ဘယ် process က CPU ကို ရမလဲ ဆုံးဖြတ်ပေးတဲ့ OS ရဲ့ အစိတ်အပိုင်းပါ။

ကောင်းတဲ့ scheduling ရဲ့ ရည်မှန်းချက်တွေက:

Throughput (အချိန် တစ်ခုအတွင်း လုပ်ပြီးနိုင်တဲ့ အလုပ် ပမာဏ) ကို အများဆုံး ဖြစ်အောင် လုပ်ခြင်း: အချိန် ယူနစ် တစ်ခုမှာ process တွေကို ဖြစ်နိုင်သမျှ အများဆုံး ပြီးအောင် လုပ်ခြင်း
Waiting time (စောင့်ချိန်) ကို အနည်းဆုံး ဖြစ်အောင် လုပ်ခြင်း: process တွေ ready queue (run ဖို့ အဆင်သင့် ဖြစ်ပြီး CPU ကို စောင့်နေတဲ့ process တွေရဲ့ queue) ထဲမှာ စောင့်ရတဲ့ အချိန်ကို လျှော့ခြင်း
တရားမျှတမှု ရှိအောင် လုပ်ခြင်း: process တစ်ခုတည်းက CPU ကို လက်ဝါးကြီးအုပ် မထားအောင် တားခြင်း
Responsiveness (user လုပ်တာကို မြန်မြန် တုံ့ပြန်နိုင်မှု) ကို ထိန်းထားခြင်း: interactive (user နဲ့ အပြန်အလှန် တုံ့ပြန်ရတဲ့) application တွေ မြန်နေသလို ခံစားရအောင် ထားခြင်း

Process State (process ရဲ့ လက်ရှိ အခြေအနေ) များ

စနစ်ထဲက process တိုင်းက ဘယ်အချိန်မှာမဆို state ငါးမျိုးထဲက တစ်မျိုးမှာ ရှိနေပါတယ်:

State	ဖော်ပြချက်
New (အသစ်)	Process ကို ဖန်တီးပြီးပြီ၊ ဒါပေမယ့် ready queue ထဲ မဝင်ရသေးပါဘူး
Ready (အဆင်သင့်)	CPU အချိန်ကို ready queue ထဲမှာ စောင့်နေပါတယ်: run လို့ ရပေမယ့် CPU က အလုပ်များနေပါတယ်
Running (run နေ)	CPU ပေါ်မှာ လက်ရှိ execute လုပ်နေပါတယ်
Waiting (စောင့်နေ)	Block ဖြစ်နေပါတယ်: I/O (ဒေတာ အဝင်အထွက်) ပြီးတာ ဒါမှမဟုတ် ပြင်ပ event (ဖြစ်ရပ်) တစ်ခုကို စောင့်နေပါတယ်
Terminated (ပြီးဆုံး)	Run တာ ပြီးသွားပါပြီ၊ resource (သုံးလို့ရတဲ့ ကွန်ပျူတာ အရင်းအမြစ်) တွေကို ပြန်လွှတ်နေပါတယ်

flowchart LR
    N[New] -->|admitted| R[Ready]
    R -->|selected by the scheduler| X[Running]
    X -->|time slice ends| R
    X -->|requests I/O| W[Waiting]
    W -->|I/O completes| R
    X -->|finishes| T[Terminated]

ပုံထဲက မြှားတွေရဲ့ အဓိပ္ပာယ်: admitted (ready queue ထဲ လက်ခံလိုက်တယ်)၊ selected by the scheduler (scheduler က ရွေးလိုက်တယ်)၊ time slice ends (process ကို ပေးထားတဲ့ CPU အချိန် အပိုင်း ကုန်သွားတယ်)၊ requests I/O (I/O တောင်းတယ်)၊ I/O completes (I/O ပြီးသွားတယ်)၊ finishes (run တာ ပြီးသွားတယ်)။

Scheduler က process ကို ရွေးလိုက်တဲ့အခါ process က Ready ကနေ Running ကို ပြောင်းပါတယ်။ Process ကို preempt (OS က အတင်း ရပ်ခိုင်း) လုပ်လိုက်ရင်၊ ဆိုလိုတာက time slice (process တစ်ခုကို ပေးတဲ့ CPU အချိန် အပိုင်းလေး) ကုန်သွားရင် Running ကနေ Ready ကို ပြန်ရွှေ့ပါတယ်။ I/O ကို တောင်းရင် Running ကနေ Waiting ကို ရွှေ့ပါတယ်။ I/O ပြီးသွားတဲ့အခါ Ready ကို ပြန်သွားပါတယ်။

Preemptive နဲ့ Non-Preemptive

Scheduling မှာ အခြေခံ နည်းလမ်း နှစ်မျိုး ရှိပါတယ်:

Non-preemptive scheduling (run နေတဲ့ process ကို အတင်း မရပ်ခိုင်းတဲ့ scheduling)

Process တစ်ခု run စပြီဆိုရင် ပြီးဆုံးတဲ့အထိ ဒါမှမဟုတ် ကိုယ်တိုင် ဆန္ဒအလျောက် ပြန်လွှတ်တဲ့အထိ (ဥပမာ I/O တောင်းဆိုချက် လုပ်တဲ့အခါ) CPU ကို ဆက်ယူထားပါတယ်
Implement (တကယ် အလုပ်လုပ်အောင် code ရေး) လုပ်ရ ပိုလွယ်ပါတယ်၊ အတင်း လုပ်ခိုင်းတဲ့ context switch (process တစ်ခုကနေ တစ်ခုကို CPU ပြောင်းခြင်း) တွေ မရှိပါဘူး
အန္တရာယ်: ကြာတဲ့ process တစ်ခုက တခြား process အားလုံးကို ပိတ်ဆို့ထားနိုင်ပါတယ်

Preemptive scheduling (run နေတဲ့ process ကို OS က အတင်း ရပ်ခိုင်းနိုင်တဲ့ scheduling)

OS က run နေတဲ့ process ကို CPU ပေါ်ကနေ အတင်း ဖယ်ထုတ်နိုင်ပါတယ် (ဥပမာ time slice ကုန်သွားတဲ့အခါ ဒါမှမဟုတ် priority (ဦးစားပေး အဆင့်) ပိုမြင့်တဲ့ process ရောက်လာတဲ့အခါ)
ပိုရှုပ်ပါတယ်: process state ကို save (သိမ်း) လုပ်ပြီး ပြန် load (ပြန်ထည့်) လုပ်ဖို့ လိုပါတယ် (context switch)
Responsiveness အရေးကြီးတဲ့ interactive စနစ်တွေအတွက် ပိုကောင်းပါတယ်

Algorithm (အယ်လ်ဂိုရီသမ်၊ ပြဿနာကို အဆင့်ဆင့် ဖြေရှင်းတဲ့ နည်းလမ်း) တစ်ခုစီကို preemptive လား non-preemptive လား ခွဲခြားနိုင်အောင် လုပ်ပါ။

Scheduling Algorithm များ

First-Come First-Served (FCFS) (အရင်ရောက် အရင်ရ scheduling)

FCFS က အရိုးရှင်းဆုံး scheduling algorithm ပါ။ ဆိုင်တစ်ဆိုင်မှာ တန်းစီသလိုပဲ process တွေကို ရောက်လာတဲ့ အစဉ်အတိုင်း ဝန်ဆောင်ပေးပါတယ်။

အမျိုးအစား: Non-preemptive
အလုပ်လုပ်ပုံ: Ready queue ရဲ့ ရှေ့ဆုံးက process က ပြီးဆုံးတဲ့အထိ ဒါမှမဟုတ် CPU ကို ကိုယ်တိုင် ဆန္ဒအလျောက် ပြန်လွှတ်တဲ့အထိ (ဥပမာ I/O တောင်းဆိုချက် လုပ်တဲ့အခါ) run ပါတယ်၊ ပြီးရင် queue ထဲက နောက် process က run ပါတယ်၊ ဒီလိုနဲ့ ဆက်သွားပါတယ်
အားသာချက်: Implement လုပ်ရ လွယ်ပြီး နားလည်ရလည်း လွယ်ပါတယ်၊ starvation (process တစ်ခုက CPU အချိန် ဒါမှမဟုတ် resource ကို အမြဲ မရဘဲ ငတ်နေခြင်း) မရှိပါဘူး
အားနည်းချက်: Convoy effect (ကြာတဲ့ process နောက်မှာ တိုတဲ့ process တွေ တန်းစီ ပိတ်မိနေခြင်း)။ ကြာတဲ့ process တစ်ခု နောက်မှာ ပိတ်မိနေတဲ့ တိုတဲ့ process တွေက အလွန်အကျွံ စောင့်ရပါတယ်
အသင့်တော်ဆုံး: အစဉ်က အရေးကြီးပြီး အလျင်စလို မလိုတဲ့ batch system (user နဲ့ တုံ့ပြန်ဖို့ မလိုဘဲ အလုပ်တွေကို စုပြီး တစ်ခုပြီး တစ်ခု run တဲ့ စနစ်) တွေ

Round Robin (RR) (အလှည့်ကျ အချိန်ပေးတဲ့ scheduling)

Round Robin က process တစ်ခုစီကို ပုံသေ time quantum (time slice လို့လည်း ခေါ်ပြီး process တစ်ခုကို ပေးတဲ့ CPU အချိန် အပိုင်းလေး) တစ်ခုစီ ပေးပါတယ်၊ ပုံမှန်အားဖြင့် millisecond (တစ်စက္ကန့်ရဲ့ တစ်ထောင်ပုံ တစ်ပုံ) အနည်းငယ်ပါ။ Quantum ကုန်သွားရင် run နေတဲ့ process ကို ready queue ရဲ့ နောက်ဆုံးကို ရွှေ့ပြီး နောက် process က အလှည့် ရပါတယ်။

အမျိုးအစား: Preemptive
အလုပ်လုပ်ပုံ: Process တစ်ခုစီက time quantum တစ်ခုစာ အများဆုံး run ပြီးရင် CPU ကို လွှဲပေးပါတယ်
အားသာချက်: တရားမျှတပါတယ်။ Process တိုင်း time slice တူတူ အလှည့်ကျ ရပါတယ်၊ responsiveness ကောင်းပါတယ်
အားနည်းချက်: Context switch overhead (context switch ကြောင့် အပို ကုန်ကျတဲ့ အချိန်နဲ့ အလုပ်): process state ကို save လုပ်ပြီး ပြန် load လုပ်ရတာ အချိန် ကုန်ပါတယ်၊ quantum အရမ်း သေးရင် CPU က execute လုပ်တာထက် ပြောင်းရတာမှာ အချိန် ပိုကုန်ပါတယ်
Quantum အရွယ်အစားရဲ့ trade-off (တစ်ခု ရဖို့ တစ်ခု အလျှော့ပေးရတာ):
- Quantum သေးရင် = ပိုမြန်မြန် တုံ့ပြန်ပေမယ့် overhead ပိုများပါတယ်
- Quantum ကြီးရင် = overhead နည်းပေမယ့် FCFS ရဲ့ ပုံစံနဲ့ ပိုတူလာပါတယ်
အသင့်တော်ဆုံး: Interactive စနစ်တွေနဲ့ time-sharing (CPU အချိန်ကို အလှည့်ကျ ခွဲဝေ မျှသုံးခြင်း) စနစ်တွေ

Round Robin ကို ပြောသူ တစ်ယောက်စီ 2 မိနစ် အတိအကျ ရတဲ့ အုပ်စု presentation (တင်ပြချက်) တစ်ခုလို မြင်ကြည့်ပါ။ 2 မိနစ် ပြည့်ရင် အရင်ပြောသူ ပြီးသည်ဖြစ်စေ မပြီးသည်ဖြစ်စေ နောက်လူက ပြောပါတယ်။ ပြောစရာ ကျန်သေးတဲ့သူတွေက တန်းရဲ့ နောက်ဆုံးကို သွားရပါတယ်။

Priority Scheduling (ဦးစားပေး အဆင့်အလိုက် scheduling)

Process တစ်ခုစီကို priority နံပါတ် တစ်ခုစီ သတ်မှတ်ပေးပါတယ်။ Priority အမြင့်ဆုံး process က အရင် run ပါတယ်။ ဒီသင်တန်းမှာ နံပါတ် ငယ်လေ priority မြင့်လေ ဖြစ်ပါတယ် (priority 1 က priority 5 ထက် အရင် run ပါတယ်)။

အမျိုးအစား: Preemptive ဒါမှမဟုတ် non-preemptive ဖြစ်နိုင်ပါတယ်
အလုပ်လုပ်ပုံ: Scheduler က ready queue ထဲက priority အမြင့်ဆုံး process ကို အမြဲ ရွေးပါတယ်
အားသာချက်: အရေးကြီးတဲ့ process တွေ (ဥပမာ system အလုပ်တွေ၊ real-time (ချက်ချင်း ဆက်တိုက်) စောင့်ကြည့်မှု) က အမြဲ အရင် run ပါတယ်
အားနည်းချက်: Starvation။ Priority မြင့်တဲ့ process တွေ ဆက်တိုက် ရောက်လာနေရင် priority နိမ့်တဲ့ process တွေက ဘယ်တော့မှ execute မလုပ်ရဘဲ ဖြစ်နိုင်ပါတယ်
ဖြေရှင်းနည်း: Ageing (စောင့်ချိန်အလိုက် priority တိုးပေးခြင်း)။ အချိန် ကြာကြာ စောင့်နေရတဲ့ process တွေရဲ့ priority ကို တဖြည်းဖြည်း တိုးပေးလို့ နောက်ဆုံးမှာ CPU အချိန် ရလာအောင် သေချာစေပါတယ်
အသင့်တော်ဆုံး: Real-time system တွေ (ဥပမာ ဆေးရုံ လူနာ စောင့်ကြည့်ရေး၊ လေယာဉ် ပျံသန်းမှု ထိန်းချုပ်ရေး)

Priority scheduling ရဲ့ အားနည်းချက်တွေကို ဆွေးနွေးတဲ့အခါ starvation ကို နာမည် တပ်ပြောပြီး ageing ကို ဖြေရှင်းနည်းအဖြစ် ပေးပါ။

Multilevel Queue (MLQ) (အဆင့် အများပါတဲ့ queue)

MLQ မှာ operating system က ready queue တစ်ခုတည်းအစား ready queue အများ ထားပါတယ်။ Process အမျိုးအစား တစ်ခုစီက ရောက်လာတဲ့အခါ ကိုယ့် queue ထဲ ဝင်ပြီး အဲဒီ queue ထဲမှာပဲ ဆက်နေပါတယ်။ Queue တစ်ခုစီက သူ့ထဲက process တွေနဲ့ ကိုက်ညီအောင် ရွေးထားတဲ့ မတူတဲ့ scheduling algorithm ကို သုံးနိုင်ပါတယ်။

ဖွဲ့စည်းပုံ ဥပမာ:
- Queue 1 (priority အမြင့်ဆုံး): System process တွေ။ Round Robin နဲ့ schedule လုပ်ပါတယ်
- Queue 2 (priority အလယ်အလတ်): User နဲ့ အပြန်အလှန် တုံ့ပြန်ရတဲ့ interactive process တွေ။ Round Robin နဲ့ schedule လုပ်ပါတယ်
- Queue 3 (priority အနိမ့်ဆုံး): Batch process တွေ။ FCFS နဲ့ schedule လုပ်ပါတယ်
Queue တွေကြား scheduling: ပုံမှန်အားဖြင့် priority ပုံသေပါ။ Queue 2 run ဖို့ Queue 1 က အလွတ် ဖြစ်နေရပါမယ်
အားနည်းချက်: Priority မြင့်တဲ့ queue တွေ အမြဲ အလုပ်များနေရင် priority နိမ့်တဲ့ queue တွေ starve (ငတ်) ဖြစ်နိုင်ပါတယ်

Multilevel Feedback Queue (MLFQ) (process တွေ queue အချင်းချင်း ရွှေ့နိုင်တဲ့ MLQ) က MLQ ရဲ့ ပုံစံကွဲ တစ်ခုပါ။ အဲဒီမှာ process တွေက သူတို့ အလုပ်လုပ်ပုံပေါ် မူတည်ပြီး queue တွေကြား ရွှေ့နိုင်ပါတယ်။ CPU ကို အများကြီး သုံးတဲ့ process ကို အောက်က queue ကို နှိမ့်ချနိုင်ပြီး I/O ကို မကြာခဏ လုပ်တဲ့ process ကို အထက် queue ကို မြှင့်တင်နိုင်ပါတယ်။ ဒါက ရိုးရိုး MLQ မှာ မရှိတဲ့ အခြေအနေနဲ့ လိုက်လျောညီထွေ ပြောင်းနိုင်မှုကို ပေးပါတယ်။

နှိုင်းယှဉ်ချက် ဇယား

Algorithm	အမျိုးအစား	Throughput	တရားမျှတမှု	Starvation ဖြစ်နိုင်ခြေ	Overhead (အပို ကုန်ကျတဲ့ အချိန်နဲ့ အလုပ်)	အသင့်တော်ဆုံး
FCFS	Non-preemptive	နိမ့်ကနေ အလယ်အလတ်	ရောက်တဲ့ အစဉ်အလိုက်	မရှိ	အလွန် နည်း	Batch system တွေ
Round Robin	Preemptive	အလယ်အလတ်	မြင့် (time slice တူတူ)	မရှိ	အလယ်အလတ် (context switch တွေကြောင့်)	Interactive စနစ်တွေ
Priority	နှစ်မျိုးလုံး ဖြစ်နိုင်	မြင့်	နိမ့်	ရှိ (ageing မပါရင်)	နည်း	Real-time system တွေ
MLQ	ရောစပ်	မြင့်	Queue အလိုက်	ရှိ (အောက်က queue တွေမှာ)	အလယ်အလတ်	ရှုပ်ထွေးတဲ့ စနစ်တွေ

IB syllabus ရဲ့ A1.3.3 က scheduling algorithm တွေကို compare လုပ်ဖို့ တောင်းပါတယ်။ Algorithm တစ်ခုစီကို ဖော်ပြနိုင်ရမယ်၊ Gantt chart (အလုပ်တစ်ခုစီကို အချိန်ဘားတွေနဲ့ ပြတဲ့ ဇယား) တွေ ဆွဲနိုင်ရမယ်၊ အားသာချက်/အားနည်းချက်တွေကို အကဲဖြတ်နိုင်ရပါမယ်။

ကြည့်ရန်: ဗီဒီယို အရင်းအမြစ်များ

The Fancy Algorithms That Make Your Computer Feel Smoother - Core Dumped

OS ရဲ့ scheduling algorithm တွေ (FCFS၊ Round Robin၊ Priority) နဲ့ အဲဒါတွေက system ရဲ့ responsiveness (ဘယ်လောက် မြန်မြန် တုံ့ပြန်လဲ) ကို ဘယ်လို အကျိုးသက်ရောက်လဲ ဆိုတာ ပြပါတယ်။

YouTube မှာ ကြည့်ရန်

Operating Systems 3 - Process Manager Part 2

Process scheduling၊ context switching နဲ့ OS က process အများကြီးကို ဘယ်လို အလှည့်ကျ ကိုင်တွယ်လဲ ဆိုတာကို ပိုနက်နက်ရှိုင်းရှိုင်း ကြည့်ပါတယ်။

YouTube မှာ ကြည့်ရန်

Process Scheduling

CPU scheduling algorithm တွေကို ဥပမာတွေ၊ နှိုင်းယှဉ်ချက်တွေနဲ့ ရှင်းရှင်းလင်းလင်း အဆင့်ဆင့် ရှင်းပြထားပါတယ်။

YouTube မှာ ကြည့်ရန်

အဓိက တိုင်းတာချက်များ

Algorithm တွေကို နှိုင်းယှဉ်တဲ့အခါ ဒါတွေကို တွက်ရပါမယ်:

Turnaround time = completion time (ပြီးဆုံးချိန်) - arrival time (ရောက်ရှိချိန်)၊ ဆိုလိုတာက ရောက်ချိန်ကနေ ပြီးချိန်အထိ စုစုပေါင်း ကြာချိန်ပါ
Waiting time = turnaround time - burst time (process run ဖို့ လိုတဲ့ CPU အချိန်)၊ ဆိုလိုတာက ready queue ထဲမှာ စောင့်နေရတဲ့ အချိန်ပါ
Average waiting time (ပျမ်းမျှ စောင့်ချိန်) = waiting time အားလုံးရဲ့ ပေါင်းလဒ် / process အရေအတွက်

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ 1: FCFS Gantt Chart

Process သုံးခု ရောက်လာပါတယ်:

Process	Burst Time	Arrival Time
P1	6	0
P2	3	1
P3	2	2

FCFS က non-preemptive ဖြစ်ပြီး process တွေကို ရောက်တဲ့ အစဉ်အတိုင်း ဝန်ဆောင်ပေးလို့:

| P1          | P2     | P3  |
0             6        9    11

Gantt chart ထဲက အကွက် တစ်ကွက်စီက process တစ်ခု run တဲ့ ကာလကို ပြပြီး အောက်က ဂဏန်းတွေက အဲဒီ ကာလတွေ စတဲ့ အချိန်နဲ့ ပြီးတဲ့ အချိန်တွေပါ။

အဆင့်ဆင့်:

t=0: P1 ရောက်လာပြီး run စပါတယ် (တခြား process မရှိသေးပါ)
t=1: P2 ရောက်လာပေမယ့် P1 က run နေဆဲ ဖြစ်လို့ P2 က ready queue ထဲ ဝင်ပါတယ်
t=2: P3 ရောက်လာပေမယ့် P1 က run နေဆဲ ဖြစ်လို့ P3 က ready queue ထဲ ဝင်ပါတယ်
t=6: P1 ပြီးသွားပါတယ်။ P2 စ run ပါတယ် (P3 ထက် အရင် ရောက်ခဲ့လို့ပါ)
t=9: P2 ပြီးသွားပါတယ်။ P3 စ run ပါတယ်
t=11: P3 ပြီးသွားပါတယ်

တွက်ချက်မှုများ:

Process	Completion	Turnaround (completion - arrival)	Waiting (turnaround - burst)
P1	6	6 - 0 = 6	6 - 6 = 0
P2	9	9 - 1 = 8	8 - 3 = 5
P3	11	11 - 2 = 9	9 - 2 = 7

Average waiting time: (0 + 5 + 7) / 3 = 4.0

Convoy effect ကို သတိထားကြည့်ပါ: P3 က CPU အချိန် 2ms ပဲ လိုပေမယ့် ပိုကြာတဲ့ process နှစ်ခုရဲ့ နောက်မှာ ရောက်လာလို့ 7ms စောင့်ရပါတယ်။

ဥပမာ 2: Round Robin Gantt Chart (Quantum = 3)

အရင် ဥပမာက process သုံးခုကိုပဲ သုံးပါမယ်:

Process	Burst Time	Arrival Time
P1	6	0
P2	3	1
P3	2	2

အဆင့်ဆင့် trace (တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်ခြင်း):

t=0: Queue ထဲမှာ P1 ပဲ ရှိပါတယ်။ P1 က quantum=3 စာ run ပါတယ်။ ဒီအချိန်အတွင်း P2 (t=1) နဲ့ P3 (t=2) ရောက်လာပြီး queue ထဲ ဝင်ပါတယ်။ P1 ရဲ့ quantum ပြီးနောက်: queue = [P2, P3, P1(ကျန် 3)]
t=3: P2 က 3ms (သူ့ burst time အပြည့်) run ပါတယ်။ P2 က t=6 မှာ ပြီးပါတယ်။ Queue = [P3, P1(3)]
t=6: P3 က 2ms (သူ့ burst time အပြည့်၊ quantum ထက် နည်းပါတယ်) run ပါတယ်။ P3 က t=8 မှာ ပြီးပါတယ်။ Queue = [P1(3)]
t=8: P1 က ကျန်တဲ့ 3ms ကို run ပါတယ်။ P1 က t=11 မှာ ပြီးပါတယ်။

| P1   | P2   | P3 | P1   |
0      3      6    8     11

တွက်ချက်မှုများ:

Process	Completion	Turnaround (completion - arrival)	Waiting (turnaround - burst)
P1	11	11 - 0 = 11	11 - 6 = 5
P2	6	6 - 1 = 5	5 - 3 = 2
P3	8	8 - 2 = 6	6 - 2 = 4

Average waiting time: (5 + 2 + 4) / 3 = 3.67

ဒီဥပမာမှာ Round Robin က FCFS ထက် average waiting time နည်းနည်း ပိုနည်းပါတယ် (3.67 နဲ့ 4.0)။ ပိုတိုတဲ့ process တွေ (P2 နဲ့ P3) က P1 ရဲ့ burst time တစ်ခုလုံး ပြီးတဲ့အထိ P1 နောက်မှာ ပိတ်မိမနေရလို့ အကျိုးရှိပါတယ်။

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. ဘယ် scheduling algorithm က convoy effect ကို ဖြစ်စေသလဲ။

Q2. Round Robin scheduling မှာ time quantum ဆိုတာ ဘာလဲ။

Q3. Priority scheduling မှာ ageing က ဘယ်ပြဿနာကို ဖြေရှင်းပေးသလဲ။

Q4. ဘယ် algorithm က process တိုင်းကို time slice တူတူ အလှည့်ကျ ပေးသလဲ။

Q5. ရိုးရိုး Multilevel Queue (MLQ) မှာ process တွေက queue တွေကြား ရွှေ့နိုင်သလား။

Gantt Chart ကို ပြည့်စုံအောင် ဖြည့်ပါ

Quantum = 2 ရှိတဲ့ Round Robin schedule အတွက် Gantt chart ကို ပြည့်စုံအောင် ဖြည့်ပါ။

Process သုံးခု ရောက်လာပါတယ်:

Process	Burst Time	Arrival Time
P1	5	0
P2	3	1
P3	4	2

ပထမ အချိန်အပိုင်း (0 ကနေ 2 အထိ) ကို ဖြည့်ပေးထားပြီးပါပြီ။ ကျန်တဲ့ အချိန်အပိုင်း တစ်ခုစီမှာ run တဲ့ process ကို ရိုက်ထည့်ပြီး completion time၊ turnaround time နဲ့ waiting time တွေကို တွက်ပါ။ Process နာမည်တွေကို P1၊ P2၊ P3 လို English စာလုံးနဲ့ ရိုက်ထည့်ပါ။ ဇယားရဲ့ ခေါင်းစဉ် အကွက်တွေက အချိန်ကာလတွေပါ: ဥပမာ ပထမ အကွက်က အချိန် 0 ကနေ 2 အထိကို ဆိုလိုပါတယ်။

သေချာ trace လုပ်ပါ: quantum တစ်ခု ပြီးတိုင်း run နေတဲ့ process က ready queue ရဲ့ နောက်ဆုံး ကို သွားပါတယ်။ အသစ် ရောက်လာတဲ့ process တွေက ရောက်တဲ့ အစဉ်အတိုင်း queue ထဲ ဝင်ပါတယ်။ Process တစ်ခုမှာ ကျန်တဲ့ အချိန်က quantum ထက် နည်းရင် စောစော ပြီးသွားပြီး နောက် process က ချက်ချင်း စပါတယ်။

Round Robin Scheduling (Quantum = 2)

အချိန်	0--2	2--4	4--6	6--8	8--9	9--11	11--12
Process	P1

အခု process တစ်ခုစီရဲ့ completion time၊ turnaround time နဲ့ waiting time တွေကို ဖြည့်ပါ:

Process	Completion Time	Turnaround Time	Waiting Time
P1
P2
P3

Trace လုပ်ပုံ အဆင့်ဆင့် (သင့်အဖြေတွေကို စစ်ကြည့်ပါ):

t=0 ကနေ 2: P1 run ပါတယ် (ကျန် 3)။ t=1 မှာ P2 ရောက်လာပြီး t=2 မှာ P3 ရောက်လာပါတယ်။ Queue: [P2, P3, P1(3)]
t=2 ကနေ 4: P2 run ပါတယ် (ကျန် 1)။ Queue: [P3, P1(3), P2(1)]
t=4 ကနေ 6: P3 run ပါတယ် (ကျန် 2)။ Queue: [P1(3), P2(1), P3(2)]
t=6 ကနေ 8: P1 run ပါတယ် (ကျန် 1)။ Queue: [P2(1), P3(2), P1(1)]
t=8 ကနေ 9: P2 က 1ms run ပြီး ပြီးသွားပါတယ်။ Queue: [P3(2), P1(1)]
t=9 ကနေ 11: P3 က 2ms run ပြီး ပြီးသွားပါတယ်။ Queue: [P1(1)]
t=11 ကနေ 12: P1 က 1ms run ပြီး ပြီးသွားပါတယ်။

Spot the Error (အမှား ရှာခြင်း)

ကျောင်းသား တစ်ယောက်က Round Robin scheduling algorithm ကို ဒီလို ဖော်ပြ ရေးထားပါတယ်။ Time quantum ကုန်သွားတဲ့အခါ ဘာဖြစ်လဲဆိုတာနဲ့ ပတ်သက်ပြီး line တစ်ကြောင်းမှာ အရေးကြီးတဲ့ အမှား ပါပါတယ်။ အမှားပါတဲ့ line ကို ရွေးပါ၊ ပြီးရင် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ။

1Round Robin is a preemptive scheduling algorithm. 2Each process is assigned a fixed time quantum. 3The scheduler picks the first process from the ready queue. 4When the time quantum expires, the process is terminated. 5This ensures every process gets a fair share of CPU time.

Line တွေရဲ့ အဓိပ္ပာယ်: (1) Round Robin က preemptive scheduling algorithm တစ်ခုပါ။ (2) Process တစ်ခုစီကို ပုံသေ time quantum တစ်ခုစီ သတ်မှတ်ပေးပါတယ်။ (3) Scheduler က ready queue ထဲက ပထမ process ကို ရွေးပါတယ်။ (4) Time quantum ကုန်သွားရင် process ကို terminate လုပ်ပါတယ်။ (5) ဒါက process တိုင်း CPU အချိန်ကို တရားမျှတစွာ ရအောင် လုပ်ပေးပါတယ်။

Line 4 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Fill in the Blanks (ကွက်လပ် ဖြည့်ခြင်း)

မှန်ကန်တဲ့ ဝေါဟာရတွေကို ဖြည့်ပြီး CPU scheduling အကြောင်း အောက်က ဖော်ပြချက်တွေကို ပြည့်စုံအောင် လုပ်ပါ။

ကွက်လပ် တစ်ခုစီကို မှန်ကန်တဲ့ scheduling ဝေါဟာရ ဒါမှမဟုတ် အယူအဆနဲ့ ဖြည့်ပါ။ စာကြောင်းတွေက English လို ဖြစ်လို့ ကွက်လပ်တွေကို English စကားလုံးနဲ့ ရိုက်ထည့်ပါ:

 processes jobs in the order they arrive.

In Round Robin, each process gets a fixed .

 occurs when low-priority processes never get CPU time.

 gradually increases the priority of waiting processes.

The  algorithm uses multiple ready queues with different scheduling policies.

စာကြောင်းတွေရဲ့ အဓိပ္ပာယ် (____ က ကွက်လပ်ပါ):
____ က job (အလုပ်) တွေကို ရောက်တဲ့ အစဉ်အတိုင်း လုပ်ဆောင်ပါတယ်။
Round Robin မှာ process တစ်ခုစီက ပုံသေ ____ တစ်ခုစီ ရပါတယ်။
Priority နိမ့်တဲ့ process တွေ CPU အချိန် ဘယ်တော့မှ မရတဲ့အခါ ____ ဖြစ်ပါတယ်။
____ က စောင့်နေတဲ့ process တွေရဲ့ priority ကို တဖြည်းဖြည်း မြှင့်ပေးပါတယ်။
____ algorithm က မတူတဲ့ scheduling စည်းမျဉ်းတွေ ရှိတဲ့ ready queue အများကို သုံးပါတယ်။

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

တွက်ချက်မှု 1: FCFS Average Waiting Time

Process သုံးခုက တစ်ချိန်တည်း (t=0) မှာ ရောက်လာပြီး FCFS နဲ့ schedule လုပ်ပါတယ်။ Average waiting time က ဘယ်လောက်လဲ။

Process   Burst Time   Arrival Time
  P1          4             0
  P2          2             0
  P3          1             0

Gantt chart:
| P1       | P2  | P3|
0          4     6   7

Average waiting time (ဒသမ 2 နေရာအထိ round လုပ်ပြီး ရေးပါ):

တွက်ချက်မှု 2: Round Robin Completion Time

Process နှစ်ခုကို quantum 3 ရှိတဲ့ Round Robin နဲ့ schedule လုပ်ပါတယ်။ P2 က ဘယ်အချိန်မှာ ပြီးသလဲ။

Process   Burst Time   Arrival Time
  P1          7             0
  P2          4             0

Trace the Gantt chart:
| P1   | P2   | P1   | P2|
0      3      6      9   ?

P2 ပြီးတဲ့ အချိန်:

Practice Exercises (လေ့ကျင့်ခန်းများ)

Core (အခြေခံ အဆင့်)

FCFS Gantt chart: Process လေးခု ရောက်လာပါတယ်: P1 (burst=3, arrival=0)၊ P2 (burst=5, arrival=1)၊ P3 (burst=2, arrival=2)၊ P4 (burst=4, arrival=3)။ FCFS Gantt chart ကို Draw (label တွေ ပါတဲ့ ပုံကို တိတိကျကျ ဆွဲပါ) လုပ်ပြီး process တစ်ခုစီရဲ့ turnaround time နဲ့ waiting time ကို calculate (တွက်တဲ့ အဆင့်တွေကို ပြပြီး ဂဏန်း အဖြေ ရှာပါ) လုပ်ပါ။ Average waiting time က ဘယ်လောက်လဲ။
Round Robin ရဲ့ အားသာချက်နဲ့ အားနည်းချက်များ: Round Robin scheduling ရဲ့ အားသာချက် နှစ်ခုနဲ့ အားနည်းချက် နှစ်ခုကို Explain (ရှင်းပြပါ) လုပ်ပါ။ Time quantum ရဲ့ အရွယ်အစားက စွမ်းဆောင်ရည်ကို ဘယ်လို သက်ရောက်လဲဆိုတာ Discuss (အမြင် အမျိုးမျိုးကို ချိန်ဆပြီး ဆွေးနွေးပါ) လုပ်ပါ: quantum အရမ်း သေးရင် ဘာဖြစ်မလဲ။ အရမ်း ကြီးရင်ကော။
Scheduling ရည်မှန်းချက်များ: CPU scheduling algorithm တစ်ခု ရောက်အောင် လုပ်သင့်တဲ့ ရည်မှန်းချက် သုံးခုကို Describe (ဖော်ပြရှင်းပြပါ) လုပ်ပါ။ ရည်မှန်းချက် တစ်ခုစီအတွက် ကောင်းကောင်း လုပ်ဆောင်နိုင်တဲ့ algorithm တစ်ခုနဲ့ ညံ့တဲ့ algorithm တစ်ခုကို name (နာမည် ဖော်ပြပါ) လုပ်ပါ။

Extension (တိုးချဲ့ အဆင့်)

ဆေးရုံ အခြေအနေ နှိုင်းယှဉ်ချက်: ဆေးရုံ ကွန်ပျူတာ စနစ် တစ်ခုက process အမျိုးအစား သုံးမျိုးကို run ပါတယ်: လူနာ စောင့်ကြည့်ရေး သတိပေးချက်တွေ (millisecond အတွင်း တုံ့ပြန်ရမယ်)၊ ဆရာဝန်တွေ မှတ်တမ်း ရှာကြည့်တာ (interactive ဖြစ်ပြီး မြန်မြန် တုံ့ပြန်သလို ခံစားရသင့်တယ်)၊ တစ်နေ့တာ ပြီးဆုံးချိန် အစီရင်ခံစာ ထုတ်တာ (ညဘက်မှာ run လို့ရတယ်)။ ဒီအခြေအနေအတွက် FCFS၊ Round Robin နဲ့ Priority scheduling ကို Compare and contrast (အားလုံးကို တစ်လျှောက်လုံး ကိုးကားပြီး တူတာနဲ့ ကွာတာကို ဖော်ပြပါ) လုပ်ပါ။ ဘယ် algorithm (ဒါမှမဟုတ် ဘယ်လို ပေါင်းစပ်မှု) ကို အကြံပြုမလဲ၊ ဘာကြောင့်လဲ။
Starvation နဲ့ ageing: Priority မတူတဲ့ process သုံးခု ပါတဲ့ တိကျတဲ့ ဥပမာ တစ်ခုနဲ့ starvation ရဲ့ အယူအဆကို Explain လုပ်ပါ။ ပြီးရင် ဒီပြဿနာကို ကာကွယ်ဖို့ ageing က ဘယ်လို အလုပ်လုပ်လဲဆိုတာ အဆင့်ဆင့် describe လုပ်ပါ။ Priority ပြောင်းလဲပုံကို ပြတဲ့ အချိန်ဇယား (timeline) တစ်ခု ထည့်ပါ။

Challenge (စိန်ခေါ်မှု အဆင့်)

MLQ စနစ် တစ်ခု ဒီဇိုင်းဆွဲခြင်း: တက္ကသိုလ် ကွန်ပျူတာ lab (လက်တွေ့ခန်း) တစ်ခုက process အမျိုးအစား သုံးမျိုးကို ကိုင်တွယ်ရပါမယ်: (a) real-time lab ပစ္စည်း စောင့်ကြည့်ရေး (priority အမြင့်ဆုံး)၊ (b) programming အတွက် ကျောင်းသားတွေ သုံးတဲ့ interactive terminal (စာသားပဲ ပြတဲ့ window) တွေ (priority အလယ်အလတ်)၊ (c) ညဘက်မှာ run တဲ့ batch အမှတ် တွက်ချက်မှု (priority အနိမ့်ဆုံး)။ Multilevel Queue စနစ် တစ်ခုကို Design (အစီအစဉ် ဒါမှမဟုတ် model တစ်ခု ရေးဆွဲပါ) လုပ်ပါ: queue အရေအတွက်၊ queue တစ်ခုစီအတွက် scheduling algorithm နဲ့ queue တွေကြား scheduling စည်းမျဉ်းကို သတ်မှတ်ပြီး batch process တွေရဲ့ starvation ကို ဘယ်လို ကာကွယ်မလဲဆိုတာ explain လုပ်ပါ။
Web server ရဲ့ တုံ့ပြန်ချိန်: Web server (ဝဘ်စာမျက်နှာတွေ ပို့ပေးတဲ့ server) တစ်ခုက quantum 50ms ရှိတဲ့ Round Robin scheduling ကို သုံးပါတယ်။ User 100 ယောက်က တစ်ပြိုင်နက် ချိတ်ဆက်ကြပြီး တစ်ယောက်စီက CPU အချိန် 200ms လိုပါတယ်။ Context switch overhead သုည လို့ ယူဆပြီး ဒါတွေကို calculate လုပ်ပါ: (a) user တစ်ယောက်က သူ့ ပထမ quantum ကို မရခင် အများဆုံး စောင့်ရမယ့် အချိန်၊ (b) user အားလုံး ပြီးဖို့ စုစုပေါင်း အချိန်၊ (c) context switch တစ်ကြိမ်ကို 5ms ကြာရင် အဖြေ ဘယ်လို ပြောင်းမလဲ။

ဆက်စပ် ခေါင်းစဉ်များ

အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: OS Fundamentals: scheduling က OS ရဲ့ အဓိက လုပ်ဆောင်ချက်တွေထဲက တစ်ခု (process management: process တွေကို စီမံခန့်ခွဲခြင်း) ပါ၊ OS က CPU အချိန်ကို ဘယ်လို ခွဲဝေလဲ မလေ့လာခင် OS ရဲ့ အခန်းကဏ္ဍကို နားလည်ထားဖို့ လိုပါတယ်
ဆက်စပ် ခေါင်းစဉ်: CPU Architecture: scheduler က process တစ်ခုကို ရွေးပြီးတာနဲ့ CPU က အဲဒီ process ရဲ့ instruction (processor လုပ်ဆောင်ရမယ့် ညွှန်ကြားချက်) တွေကို FDE cycle (ညွှန်ကြားချက်ကို ယူ၊ နားလည်၊ လုပ်ဆောင်တဲ့ စက်ဝန်း) နဲ့ run ပါတယ်၊ multi-core processor (core အများကြီး ပါတဲ့ CPU) တွေက core တွေပေါ်မှာ တစ်ပြိုင်နက် scheduling လုပ်နိုင်စေပါတယ်
နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Polling and Interrupts: interrupt (CPU ကို ခဏ ရပ်ခိုင်းတဲ့ signal) တွေက context switch တွေနဲ့ ပြန် schedule လုပ်တာတွေကို စတင်စေနိုင်ပါတယ်၊ preemptive scheduling ကို ဖြစ်နိုင်စေတာ timer interrupt ပါ
နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Multitasking (HL: Higher Level၊ IB သင်တန်းမှာ ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အဆင့်): scheduling က multitasking (အလုပ် အများကို တစ်ပြိုင်နက်လို လုပ်ခြင်း) ကို ဖြစ်နိုင်စေပါတယ်၊ scheduling နဲ့ resource allocation (process တွေကို CPU အချိန်၊ memory စတဲ့ resource တွေ ခွဲဝေပေးခြင်း) မအောင်မြင်တဲ့အခါ deadlock နဲ့ starvation တွေ ဖြစ်ပါတယ်