# Process Scheduling
###### tags: `OS Note Pro`

[TOC]
:::spoiler Definition of **Burst**
CPU burst 與 I/O burst 是指一段連續使用CPU/IO的時間
通常short cpu burst較多，long cpu burst較少。
:::
:::spoiler Definition of **Bound**
可以認為通常情況下，大部分程式針對某個特定的效能metric而言都可分為CPU bound 和I/O bound兩類。 CPU bound的程式一般而言CPU佔用率相當高。 這可能是因為任務本身不太需要訪問I/O裝置，也可能是因為程式是多執行緒實現因此遮蔽掉了等待I/O的時間。
CPU-Bound : Long CPU burst
I/O-Bound : Short CPU burst
:::

## Basic Concept
首先要先知道，排程是在排甚麼，為甚麼需要排程。因為要處理multiprograming，所以CPU對每個process的執行必須能夠達到最高效率，因此kernel必須要能夠排程。而要知道怎麼排，要先知道CPU是怎麼執行以及他的消耗是怎麼算。Process的執行可分為兩個部分，CPU burst和I/O burst，不是在做CPU的運算就是做I/O，因次我們希望能夠協調出不要完全是CPU-bound或I/O-bound。

:::success
CPU Scheduler的工作就是將ready queue中的process pick 進 CPU 執行。
:::

### Preemptive vs Non-preemptive
兩者差異在於 : Preemptive能在任何時刻直接中斷換下一個process，而Non-preemptive不行。而這些切換有以下4種情況:
1. Running to waiting
2. Running to ready
3. Ready to waiting
4. Terminated

Preemptive 4個都能執行，能中斷任何burst，去執行其他process。
而Non-preemptive只能執行1和4，只能等CPU burst完成才能執行下一個。
:::success
Preemptive的好處是更有效率，整體運行較快。但會遇到synchronization的問題，因為是在run time切換。(處理方法可以將kernel process執行時不接受interrupt，也就是變成non-preemptive)
Non-preemptive就寫顯得比較沒彈性，所以整體會較慢。
:::

### Dispatcher
排完程後真正執行指派process到CPU的人就是Dispatcher啦。

## Scheduler Algorithm
### Scheduling criteria
評斷效能的方法有以下5點:
整體 :
1. CPU utilization
2. Throughput : 單位時間完成的process數量
---
Process :
4. Turnaround: process提交後到完成的時間
5. Waiting time: 在CPU執行之後被插隊的總共等待時間，不包含I/O burst的時間
6. Response time : process arrive後到第一個執行cycle出現的時間

:::success
這裡的arrive或被插隊被迫等待的process應該都是待在ready queue裡的。..
所以scheduler會決定誰在queue裡誰在CPU中執行。
:::

### First-come-First-serve(FCFS)
Waiting time 不一，假如第一個進來的burst很大，那就會執行很久才輪到下一個。(而且一次執行就會執行完，屬於non-preemptive)
### Short job First(SJF)
最短的job先執行。有**preemptive**和**non-preemptive**兩種版本。當然preemptive是較有效率的。
:::info
但事實上我們在執行該process前是不知道它的burst，所以會透過一些math algorithm 來去預測下一個process的CPU-burst。
:::
### Priority scheduling
讓每個process有各自的權重值，權重大的就先執行，小的後執行。
同樣也有preemptive和non-preemptive的不同執行方法。
:::success
SJF也是一種priority scheduling的一種，只是是以burst的大小做權重(反比)。
:::
:::warning
Priority scheduling 會遇到的問題是 : 若有一個process的priority很低，然後一直有比他高的priority process要執行，那就有可能會一直執行不到。
所以後來的解決方案是每過一段時間就將queue中的priority增加，保證在一定時間內都會被執行到。
:::

### Round-Robin(RR)
就是輪流執行。
由**Time quantum**決定多久換下一個process執行，待執行的都留在ready queue中。一定是**preemptive**。
:::success
Response time會表現不錯，只要(QT)不要太長，但waiting time有可能就不好了。
:::

### Multilevel queue
將ready queue依照演算法分類，分成多個queue，讓process進到ready queue時選擇屬於自己的queue，且每個queue被選重的依據是由機率來決定，比較重要的queue就有較高的機率被選重，反之亦然。概念就像是priority用在queue上。
### Multilevel feedback queue
一樣有多個queue，但不再以process的重要性來區分，而是以QT做篩選，比如說第一層的queue的QT是8ms，若有個process經過第一個queue卻發現沒做完(CPU burst too long)，那他就會被搬到第2層queue(QT:16ms)，然後最後一層是FCFS。執行順序是第一層queue都做完了才會執行第二層queue，以此類推，這樣才能達到SJF。
:::info
**QT**完的process都是離開CPU到ready queue中的，所以若有一個process很快就執行到I/O burst，那他下一次還會回到第一層queue，這些狀態的紀錄都是由PCB來處理的。
:::