Intro

  • Multiprogramming : 為了獲得最大CPU使用率
  • CPU burst先，接著才是I/O burst
  • 主要考慮CPU

Scheduler

排程器在以下期間發揮作用 :

  • Switches from running to waiting state
  • Swithces from running to ready state
  • Switches from wating to ready
  • Terminate

Preemptive & Non-Preemptive

  1. Preemptive :
  • 排程器可以依據時間片/優先級搶佔CPU
  • 主流，fast-responsive且資源共享
  • 有race condition風險
  1. Non-Preemptive :
  • 排程只發生在指定情況(Terminate, Switch to waiting…)
  • 只在Process釋放CPU時重新分配
  • 設計上更簡單，但是poor-responsive

Dispatcher

  • Switch context
  • Switch to user mode
  • Jump to location in order to restart program

Dispatch Latency

Scheduling Criteria

  • CPU utilization
  • Throughput
  • Turnaround time
  • Waiting time
  • Response time

排程演算法

FCFS

First-come, first-served

可能產生Convoy effect

SJF

Shortest Job Fist

Preeptive版本 : Shortest Remaining Time First

如何預測CPU Burst?

  • 第N個CPU burst : $t_{n}$
  • 下一個CPU burst預估長度 : $\tau_{n+1}$
  • $\alpha$, $0 \leq \alpha \leq 1$

公式則可以被定義如下，通常令 $\alpha=\frac{1}{2}$ :

$$ \tau_{n+1} = \alpha \times t_{n} + (1 - \alpha) \times \tau_{n} $$

SRT

  • SJF的可搶占版本
  • 每當Process進入Ready Queue就使用SJN排程

Round-Robin

  • 把CPU time切分成time quantum
    • Q通常介於10ms-100ms
  • 保證每個Process都不會等超過 (n-1)xq 個時間單位
  • 當Q增加時會趨近於FCFS
  • 反之則趨近RR，但是考慮context swtich的overhead不應太小

Priority Scheduling

  • Priority number : int
  • CPU會優先處理最高優先級(數字最小)
  • 可能導致Starvation的問題

img

Multilevel Queue

  • Ready Queue由許多queue組成
  • 由以下參數定義排程器 :
    1. 佇列數量
    2. 每個佇列對應的算法
    3. Process進入queue的方法
    4. 佇列之間的排程

Multilevel Feedback Queue

example

  • Q1 : Round-Robin, q=10ms
  • Q2 : Round-Robin, q=20ms
  • Q3 : FCFS

CPU之間排程(多CPU系統)

CPU親和力

以下情境皆會使用到 :

  1. Multi-core
  2. Multi-thread
  3. NUMA
  4. Heterogeneous multi-processing

Multiple-processor Scheduling

  • Symmetric Multi-Processing(SMP) : 每個CPU獨自排程
  • 反之則是有Master-Slave關係存在

Multi-thread Multi-core

  • 每個core擁有 >1個 thread
  • 遇到momory stall則切換thread
  • NUMA : 為Process分配離CPU最近的Memory

POSIX Real-Time Scheduling

API

pthread_attr_getscope(&attr, &scope); //int scope
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM); //PTHREAD_SCOPE_PROCESS
pthread_create(&tid, &attr, runner, NULL); //runner is a function
pthread_join(tid, NULL);
pthread_exit(EXIT_SUCCESS);

Operation Examples

Linux : CFS

  • 取代原有O(1)排程器
  • Fair Scheduling
  • 使用紅黑樹平衡vruntime，對最小者分配最高優先(aging)
  • 解決Starvation, 且紅黑樹僅需 $O(log(n))$ 時間插入