# 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 <font color=#ff0000>考</font>

* 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 (待補)

<font color=#ff0000>考</font>
:::info
<font color=#0000000>

$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)
</font>
:::

## 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 <font color=#ff0000>考</font>

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 <font color=#ff0000>絕對必考</font>

### First-Come, First-Served (FCFS)

Assume Arrival at 0 (k)

average waiting time (k)：$\frac{0+2+3+8+12}{5}=5$

<font color=#ff0000>考</font>
* **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):
<font color=#f98000>0</font> <font color=#cc0000>1</font> <font color=#00a000>3</font> <font color=#f04000>4</font> <font color=#0000aa>5</font>


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)

<font color=#ff0000>考</font>
:::info
<font color=#0000000>

$Q$ : What scheduling algorithms could result in starvation?
<font color=#ff0000> SJF、Priority (without aging)</font>

$Q$ : Explain the differences in the degree to which the following scheduling algorithms discriminate in favor of short processes:
a. FCFS: <font color=#ff0000>Convoy effect (against short process</font>
b. RR: <font color=#ff0000>treats all jobs equally, thus short jobs will be able to leave the system faster</font>
c. Multilevel feedback queues: <font color=#ff0000> similar to RR</font>

</font>
:::

### 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

<font color=#000000>
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.
</font>
:::

>[color=#00a000]
>
>所以process一直在不同Queue轉來轉去？
>[name=Omnom]

>[color=#FF00FF]會監控Process的執行狀況並根據某些依據(通常是執行時間)來調整(upgrade and demote)Process應該要放在哪一個優先度的Queue中。而跟MFQ相同的是每個Queue可以有不同的排程演算法。
>[name=Neko]
>
## Thread Scheduling
<font color=#ff0000>考</font>
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