# OS chapter 5 Process Scheduling

### Basic Concepts
* the idea of multiprogramming: 很多個process存在記憶體中等待被執行，一個時間只能一人使用
* CPU-I/O burst cycle: 一段時間都在做同一件事(CPU burst or I/O burst)
* 有很多小的CPU burst跟很少大的CPU burst
* I/O-bound的program通常有很多小CPU burst(因為CPU的速度遠快於I/O)
* 反之CPU-bound有很少大CPU burst

### Preenptive vs. Non-preemptive
* 可以在某些地方要schedule CPU
1. 有個process從running變waiting
2. 有個process從running變ready
3. 有個process從waiting變ready
4. process結束
* Non-preemptive: 只在1跟4做切換，讓CPU burst不會被中斷
* preemptive: 任何時候都會

### Preemptive Issues
* Inconsistent state of shared data
* 效能比較好
* 需要process synchorization
* 需要特別處理shared data
* Affect the deign of OS kernel
* 在kernel裡面處理synchorization
* UNIX: 在run kernel process時會把interrupt diasabled，一來就不會被scheduler打斷

### Dispathcer
* 負責執行切換process
* context switch也是他負責的
* 跳到要執行的program的位置
* Dispath latency: 做切換所花的時間
* 做scheduling的時間
* 重新enable interrupt的時間
* 做context switch的時間

## Scuduling Algorithm

### Scheduling Criteria
* CPU utilization: 理論上0%~100%， 實際上通常介於40%~90%
* throughput:每單位時間完成的process數
* Turnaround time: submission到完成的時間
* Waiting Time: 整個執行過程中，在ready queue裡等待的時間
* Response time: submission到first response(第一個CPU burst cycle)的時間

### FCFS Scheduling
* 假設process放到ready queue裡的順序是Px(預計執行幾個cycle): P1(24), P2(3),P3(3)
* waiting time: P1=0,P2=24,P3=27
* AVG waiting time(AWT): (0+24+27)/3 = 17
* convoy effect: 短process在長 process後就會增加waiting time

### Shortest-Job-First(SJF) Scheduling
* 最短的process先執行，可以有最短的AWT
* preemptive SJF 會比non-preemptive有更短的AWT
* Wait time = completion time - arrival time - run time - (IO burst time)
* Difficulty: 不知道CPU的burst time
* Approximate SJF: 用過去的資訊的exponential average推測現在

### Priority Scheduling
* 每個process都有piority，根據priority決定CPU要給誰用
* 最general的作法
* SJF也是一種Priority Scheduling
* starvation:process低的很難被執行到
* aging:每過一段時間，還沒執行到的process priority就會增加
### Round-Robin Scheduling
* 每個process都有一段CPU時間可以使用(time quntent)
* 時間到就會被preempt，回到ready queue
* TQ太長就變成FIFO，太短則需要一直做context switch，overhead增加
* 因為要輪流，所以每個process容易都要到最後才能做完，因此具較高的平均turnaround time，但response time會比較好

### Multilevel Queue Scheduling
* 有好幾個獨立的小queue，每個queue可以有自己的排程方式
* queue之間也需要做排程
* 優先度固定:可能會有starvation的問題
* Time Slice:大家輪流做

### Multilevel Feedback Queue Scheduling
* process可以移動到別的queue上(需要設定怎麼升降)
* queue彼此的優先度固定，越高的就要先做

### Evaluation Methods
* Deterministic modeling:給input之後測是哪個方法最好，會因為Input不同有不一樣的結果
* Queueing model: 數學分析(機率)，但很難找到match的方式
* Simulation:給更general的input
* Implementation: 加入更多現實生活中的overhead做分析

## Hardware level Scheduling

### Multi Processor Scheduling
#### Asymmetric multiprocessing
* 系統事務統一由一個processor處理，其他人就執行user code
* 比較簡單，但主processor容易閒置
#### symmetric multiprocessing
* 所有process競爭同一個queue，有同步問題。

### Processor affinity
* affinity:一個程式被綁在CPU core上，可以跑比較快(能reuse cache)，如果那個core在做別的事就要等
* soft affinity:等太久可以換給別人做
* hard affinity:等再久都要他做

### NUMA
* 不同CPU要讀別人的資料比較慢，所以要盡可能的scedule到同一塊區域上

### Load-balancing
* 盡可能讓大家的工作量相同
* Push migration:從工作量重的往輕的給(整體loading低的時候呼叫push的次數低)
* Pull migration:從工作量輕的跟重的要(整體loading高的時候呼叫pull的次數低)
* 與affinity的優點可能會互斥

### Multi-core Processor Scheduling
* Multi-core比較快又有效率，但會有memory stall的問題，需要花很多時間等memory可以被存取
* 多thread能在同一顆core上，等memory的時候換另一個人做
* 如何換thread?
* coarse-grained:直接flush掉原本的pipeline, cost比較高
* fine-grained:保留住，

### Real-Time Scheduling
* 必須在deadline前完成
* Soft r.t requirements:即使miss deadline影響也不大
* Hard:一定要在deadline前完成，不然會出事

### Real-Time Scheduling Algorithms
* burst time表現形式:(Ready, Execution, Period(什麼時候下一個burst會出現))
* 必須重複出現有規律
* Rate-Monotonic: period越小的優先度越高，因此priority是fixed
* Earliest-Deadline-First:越靠近deadline的優先度越高，因此priority是Dynamic

## Problem Set
### 5.3
* Consider a system running ten I/O-bound task and one CPU-bound
task. Assume that the I/O-bound tasks issue an I/O operation once for
every millisecond of CPU computing and that each I/O operation takes 10
milliseconds to complete. Also assume that the context-switching
overhead is 0.1 millisecond and that all processes are long-running tasks.
Describe the CPU utilization for a round-robin scheduler when:
1. The time quantum is 1 millisecond
答: I/O-bound task 每1 ms就要做IO，並換人，輪10個task之後回到他的時IO就做好了，執行時間內不會浪費時間等IO，utilization是1/(1+0.1)，而CPU-bound task也是1/1.1，因此total就是1.1 = 91%
2. The time quantum is 10 milliseconds
答:在這個情況下，IO-bound task只有第一秒會做事，之後就會做context switch換人，10個task共花了1.1*10=11的時間，其中有10秒使用CPU。，而CPU-bound task則是10/10.1，總和為20/21.1=94.7%

### 5.4
* What advantage is there in having different time-quantum sizes at
different levels of a multilevel queueing system?
答: 可以客製化，需要real time interaction就適用於小tq，不需要的就適合大tq，如果全部都是小tq對不需要real time interaction的就會浪費很多時間在做不必要的context switch。

### 5.7
* Explain the differences in how much the following scheduling the
algorithms descriminate in favor of short processes:
a. FCFS:當長process先來時，FCFS就會讓短process等很久，比較不利;
b. RR: 大家都能輪流使用相同的時間，因此短process可以比較快做完;
c. Multilevel feedback queues:包含了RR的優點，並且可以將長Process放到low level的queue中，讓短process可以更快做完，
### 5.9
* Which of the following scheduling algorithms could result in
starvation? a. First-come, first-served b. Shortest job first c. Round robin d.
Priority.
答:B,短的一直進來長的永遠做不到

### 5.13
* The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
1. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority (a larger priority number implies a higher priority), and RR (quantum = 2)
2. What is the turnaround time of each process for each of the scheduling algorithms in part a?
3. What is the waiting time of each process for each of these scheduling algorithms?
4. Which of the algorithms results in the minimum average waiting time (over all processes)?