Chp 5 CPU Scheduling

tags: 作業系統

參照Chp 3

可參考的網站

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

考

$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{completedprocesses}{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

4相對於3是不定的？
Omnom

總覺得這Response time寫的文謅謅的。
Response time是指Process 從Arrive之後到第一次取得CPU資源的這段待在ready queue的時間，這聽起來跟waiting time很像，但是response time是專指第一次，有可能process開始run了以後因為排程(RR)或是中斷之類的原因再次回到ready queue，這時候waiting time會繼續增加，但是response time就跟這裡沒關係了。
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大幅增加的不良現象

有點naive
所謂「FCFS比較公平」應該是指「先到先處理」
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\le \alpha \le 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

priority的High和Low好像和平常我們認知的顛倒？
Omnom

等待越久的Process其執行的優先度越高，避免資源都被其他high priority的process占用
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)

考

$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

此外，如果各個Queue裡面都有Process怎麼辦?因此queue之間也要做scheduling，就像講義25頁的圖，Queue也有優先度的區別。
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.

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.

所以process一直在不同Queue轉來轉去？
Omnom

會監控Process的執行狀況並根據某些依據(通常是執行時間)來調整(upgrade and demote)Process應該要放在哪一個優先度的Queue中。而跟MFQ相同的是每個Queue可以有不同的排程演算法。
Neko

Thread Scheduling

考

1. process-contention scope (PCS)
   thread library schedules user-level threads to run on LWP

這個只有在Many-to-1跟many-to-many的模型才成立
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

'critical real-time process' ?
Omnom

就是即時性很重要的Process，因為soft real-time沒有對process的時間有很嚴格的限制，所以才會這麼說。
Neko

Latency

• If T = period, D = deadline, C = compute time
  • $C\le D\le 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:50B:15C:20Share: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