---
# System prepended metadata
title: Chp 5 CPU Scheduling
tags: [作業系統]
---
# Chp 5 CPU Scheduling
###### tags: `作業系統`
[參照Chp 3](https://hackmd.io/Stbjgv5LSyipNPz0V-9onA#Scheduling)
[可參考的網站](https://mropengate.blogspot.com/2015/01/operating-system-ch5-cpu-scheduling.html)
## CPU Schedule 考
* a.k.a **Short-term scheduler** selects from among the processes in **ready queue**, and allocates the CPU to one of them
* CPU scheduling decisions:
## Preemptive v.s. Non-Preemptive (待補)
考
:::info
$Q$: Please explain what is the non-preemptive and preemptive scheduling? And also describe both scenarios of preemptive and non-preemptive scheduling.
* Ans.
+ non-preemptive: Process cannot be preempted until completes its CPU burst(執行中的process不能被其他process中斷)
+ preemptive: new process arrives with CPU burst length less than remaining time of current executing process, preempt(process可以執行到一半換成執行其他CPU burst 較短的 process)
:::
## Dispatcher
* Gives control to the process selected by the short term scheduler
e.g.
1. context switch
2. switch to user mode
3. restart user program
* **Dispatch latency**: **time** it takes for the dispatcher to stop the process and start another (the shorter, the better)
## Criteria 考
1. **CPU utilization** : keep CPU busy(max)
2. **Throughput** : $\frac{completed ~ processes} { time}$(max)
3. **Turnaround time** : $t_{finish}-t_{start}$, waiting time + executing time (min)
4. **Waiting time** : wait in the ready queue (min)
5. **Response time** : amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)(min) ($t_{response}-t_{request}$)
6. **Time slice (time quantum)**: max. time a thread can run before being preempted
>[color=#00a000]
>
>4相對於3是不定的？
>[name=Omnom]
>[color=#FF00FF]總覺得這Response time寫的文謅謅的。
>Response time是指Process 從Arrive之後到第一次取得CPU資源的這段待在ready queue的時間，這聽起來跟waiting time很像，但是response time是專指第一次，有可能process開始run了以後因為排程(RR)或是中斷之類的原因再次回到ready queue，這時候waiting time會繼續增加，但是response time就跟這裡沒關係了。
>[name=Neko]
## Schedule Algorithm 絕對必考
### First-Come, First-Served (FCFS)
Assume Arrival at 0 (k)
average waiting time (k)：$\frac{0+2+3+8+12}{5}=5$
考
* **Convoy effect**: 很多process 均在等待一個需要很長CPU Time 來完成工作process，造成Average waiting time大幅增加的不良現象
>[color=#00a000]
>
>有點naive
>所謂「FCFS比較公平」應該是指「先到先處理」
>[name=Omnom]
### Shortest-Job-First(SJF)
1. nonpreemptive
Assume Arrival at 0 (k)
average waiting time (k)：$\frac{0+1+3+6+10}{5}=4$
2. preemptive
**Shortest-remaining-time-first (SRTF)**
Assume Arrival (k):
0 1 3 4 5
average waiting time (k)：$\frac{0+(1-1)+(2-1)+(3-3)+(4-4)+(5-5)+(8-5)+(11-4)}{5}=2.2$
* Pro
Gives minimum average waiting time
* Con
1. need to predict next CPU burst
2. starvation issue
* Determine length of next CPU burst: exponential average waiting
- $t_n$: actual length of $n^{th}$ burst
- $\tau_{n+1}$:predicted value
- $\alpha,\ 0 \leq\alpha\leq 1$
- $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$
### Priority Scheduling
* General type: determine the prioritized criteria.
* Issue:
**Starvation** – low priority processes may never execute
Sol: **Aging** – as time progresses increase the priority of the process
>[color=#00a000]
>
>priority的High和Low好像和平常我們認知的顛倒？
>[name=Omnom]
>[color=#FF00FF]等待越久的Process其執行的優先度越高，避免資源都被其他high priority的process占用
>[name=Neko]
### Round Robin (RR)
* Description: Small unit of CPU time (time quantum), if there are $n$ threads in ready state and time quantum is $q$, split the time slot into $n$ chunks and distribute them equally of at most $q$ time units at once.
* Issue:
* context switch 不能太頻繁
* 耗費的時間不能太多
* quantum time取捨很重要
* Pro:
1. wait time 不會太大
2. 有multitasking的可能
* time quantum q
- Large:
+ 太大會退化成 FCFS
+ turnaround time 小
- Small:
+ q 必須比 context switch 所花的時間大 (如Issue所述)
+ Better response (multitasking)
考
:::info
$Q$ : What scheduling algorithms could result in starvation?
SJF、Priority (without aging)
$Q$ : Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:
a. FCFS: Convoy effect (against short process
b. RR: treats all jobs equally, thus short jobs will be able to leave the system faster
c. Multilevel feedback queues: similar to RR
:::
### Multilevel Queue Scheduling
* Ready queue partition: separate queues:
* foreground (interactive)
* background (batch)
* Concept:
將ready queue分層，每層使用特定的algorithm
e.g.
- foreground – RR
- background – FCFS
- Scheduling between queues
- Fixed priority scheduling: server from foreground to background queue (may lead to **starvation**)
- Time slice: each queue gets certain amount of CPU time
>[color=#FF00FF]此外，如果各個Queue裡面都有Process怎麼辦?因此queue之間也要做scheduling，就像講義25頁的圖，Queue也有優先度的區別。
>[name=Neko]
### Multilevel Feedback Queue Scheduling
* Concept:
- A process can move between the various queues (改良上述方式)
* higher priority time quantum 要越小
>Example
>Three jobs $Q_0,\ Q_1,\ Q_2$
>If $Q_0$ gets the process, it gets 8 ms, if not done, shift to $Q_1$ and so on.
:::info
Which of the following statements are true about multilevel feedback queue scheduling algorithm?
**(A)** A process can move between the various queue depending on the CPU time it uses.
**(B)** If a process waits too long in a lower-priority queue, it may be moved to higher-priority queue to prevent starvation.
(C ) Generally, the time quantum increases from lower-priority queue to higher-priority queue.
**(D)** If the time quantum is set as a very large value, the queue may result in convoy effect as FCFS scheduling.
(E) The time quantum is the smaller the better.
:::
>[color=#00a000]
>
>所以process一直在不同Queue轉來轉去？
>[name=Omnom]
>[color=#FF00FF]會監控Process的執行狀況並根據某些依據(通常是執行時間)來調整(upgrade and demote)Process應該要放在哪一個優先度的Queue中。而跟MFQ相同的是每個Queue可以有不同的排程演算法。
>[name=Neko]
>
## Thread Scheduling
考
1. **process-contention scope (PCS)**
thread library schedules user-level threads to run on LWP
>[color=#FF00FF]這個只有在Many-to-1跟many-to-many的模型才成立
>[name=Neko]
2. **system-contention scope (SCS)**
Kernel thread scheduled onto available CPU
## Multiple-Processor Scheduling (全篇待修)
### Approaches to Multiple-Processor Scheduling
### Multicore Processors
## Real-Time CPU Scheduling
* Start time: a task must start in response to some events
* Deadline: time at which the task must completes
* **Soft** real-time systems – no guarantee as to when critical real-time process will be scheduled
* **Hard** real-time systems – task must be serviced by its deadline, elsewise the result may be meaningless
* Real-time operating system usually use priority schedulers
>[color=#00a000]
>
>'critical real-time process' ?
>[name=Omnom]
>[color=#FF00FF]就是即時性很重要的Process，因為soft real-time沒有對process的時間有很嚴格的限制，所以才會這麼說。
>[name=Neko]
### Latency
- If T = period, D = deadline, C = compute time
- $C \leq D \leq T$
* Event lataency ($t_{occur}-t_{response}$)
1. Interrupt latency
- arrival of an interrupt at the CPU to the start of the routine
2. Dispatch latency
- dispatcher to stop one process and start another
- Conflict phase
1. Preemption of any process running in kernel mode
2. Release by low- priority process of resources needed by high- priority processes
### Priority-Based Scheduling
### Rate-Monotonic Scheduling
* Assign static property to periodic processes according to their periods
* Highest frequency process gets the highest priority
* Every RT process must have known period
* Same priority: round robin
* Missing deadlines
+ 用period設定priority可能造成問題(有可能在deadline前做不完)
### Earliest Deadline First Scheduling (EDF)
- always run the one that has closest deadline (may be preempted)
### Lseat Slack First (LSF) Scheduling
- Consider both remaining compute time and deadline
- Look how much a process can be deferred
- slack = (time to deadline) - (amount of remaining computation)
### EDF vs. LSF
* earlist deadline in EDF alaways finish before others
* LSF can get balanced result
* Difference when there is not enough time
* EDF: some early deadline processes may finish
* LSF: all deadline may be missed but roughly by the same amount
### Proportional Share Scheduling
e.g. $A:50 ~~B:15 ~~C:20 ~~Share:100$
$D:30$ is denied since 50+15+20+**30**=115>100
## Static & Dynamic Linker
## CPU Memory Access
- CPU executes process by reading instruction, which resides in memory and requires processor to read and write in new location
- Addresses amy be absolute or relative
- absolute address: actual memory location
- relative address: offset to the content of a register
- commin relative addressing mode: PC-relative
### Bind of Instruction and Data
- Adrdress binding in three stages
- Compile time: memory location priori: absolute code
- Load time: Must generate relocatable code if not known at compile time
- Execution time: Binding delayed until run time if process can be moved during execution from one segment to another
- Hardware support for address maps
### Multistep
### Memory access specification
- Absolute code: know where the program loaded
- Position independent code: all addresses are relative (fPIC)
- Dynamic relocatable code: relocated at load time
- Logical addresses: absolute code traslated at RT (Need special meory translation hardware MMU)
### Logical vs. Physical Address Space
- Logical address: generated by CPU (virtual address)
- Physical Address: seen by the memory unit
## Operating-System Examples(待修)
## Algorithm Evaluation
### Deterministic Modeling
* analytic evaluation
- given algorithm and the system workload to produce a formula or number to evaluate the performance of the algorithm for that workload.
* Deterministic modeling
1. type of analytic evaluation
### Queueing Models
### Simulations