http://en.wikipedia.org/wiki/CPU_Scheduling
Process execution consists of a "cycle" of CPU bursts and I/O bursts.
CPU-burst distribution follow a (hyper)exponential pattern.
=> I/O bound programs: many short CPU bursts(左半邊)
CPU bound programs: a few long CPU bursts(右半邊)
Recall process states:
new, waiting, ready, running, terminated
CPU scheduling decisions may take place when a process:
1. running -> waiting [I/O or event wait]
2. running -> ready [interrupt]
3. waiting -> ready [I/O or event completion]
4. running -> terminates
Scheduling under 1 and 4 is nonpreemptive.
Scheduling under 2 and 3 is preemptive.
Dispatcher transfers control of CPU to selected process, involving:
1. Context switching
2. Switching to user mode
3. Jumping to proper location in user program to 'restart' that program
Scheduling performance criteria/objectives:
[max]1. CPU utilization - CPU用在process執行的時間比率
[max]2. Throughput(產能) - 單位時間內完成的工作數量
[min]3. Turn around Time - submission ~ completion
[min]4. ★Waiting Time - total/average waiting time in "ready queue"
[min]5. Response Time - submission ~ 1st response
在time-sharing system及user-interactive system中特別強調
# Fair(排班時儘量要求公平)
# No Starvation(避免飢餓)
# Support "priority" scheduling
# Resource Utilization ↑
Scheduling algorithms: [建議study guide整段全看]
1. First-come, first-served (FCFS):
Long average waiting time
Convoy effect(護衛效應) -- lower CPU and I/O utilization
2. Shortest-job-first (SJF): [證明是optimum]
Actually "shortest next CPU burst"
Difficulty: next CPU burst難以估計 -> used in long-term scheduling
[變種1] Approximate SJF:
Exponentially Weighted Moving Average (EWMA)
τn+1 = (α)tn + (1-α)τn
= (α)tn + (1-α)(α)tn-1 + ... + (1-α)^n(α)t0 + (1-α)^(n+1)*τ0
{α=1/2} = 1/2tn + 1/4tn-1 + ... + 1/2^(n+1)t0 + 1/2^(n+1)τ0
Non-preemptive SJF -- SJF (Shortest Job First)
[變種2] Preemptive SJF -- SRTF (Shortest Remaining Time First)
若其剩餘的CPU burst time大於新到達的process之CPU burst time，
則此process會被迫放棄CPU，交由新process執行。
3. Priority:
也可分為non-preemptive和preemptive
關鍵在於priority value的定義方式: internal vs external
SJF是一種priority scheduling -- Priority is the "next CPU burst"
FCFS是一種priority scheduling -- Priority is the "arrival time"
Problem: Starvation -- Low priority processes may never execute.
(易發生在unfair，甚至加上preemptive的環境)
=> Solution: Aging -- 隨著時間經過逐漸提高該process的priority
4. Round-robin (RR):
Time quantum: q
若未能在q內完成工作，則此process會被preempt掉，排到ready queue的尾端。
Time-sharing system使用RR
q too large => 趨近FCFS
q too small => overhead of context switching
Typically, higher turnaround than SJF, but better response. (fair)
Time quantum愈多 => context switch愈多，但與turnaround time並無明顯相關。
5. Multi-level queue:
將單一ready queue分成許多不同優先權等級的ready queues
每個Queue中可有自己的排班法則，如：foreground:RR, background: FCFS。
不允許process在各個queue中移動(沒有feedback)
Queue與queue之間的scheduling: fixed priority, priority time slice.
Preemptive, possibility of starvation
6. Multi-level feedback scheduling
基本同[5]，但Process可以在queue之間移動。
Still unfair, but prevent starvation
Design issues:
a. # of queues
b. Scheduling algorithms for each queue
c. 新Process進來該插到哪個queue
d. When to upgrade a process. e.g. Aging
e. When to downgrade a process. e.g. 在quantum內無法做完
設計上最為複雜
分類：
# Fair：
1. FCFS
2. RR
# No starvation：
1. FCFS
2. RR
3. Multilevel Feedback Queue
# Non-preemptive：
1. FCFS
2. SJF
3. Non-preemptive priority
# Preemptive:
1. SRTF
2. Preemptive priority
3. RR
4. Multi-level queue
5. Multi-level feedback queue
Multiple-processor scheduling: (assuming homogeneous systems)
1. Asymmetric multiprocessing: 有master-slave processors
2. Symmetric multiprocessing(SMP): self-scheduling
a. common ready queue; b. separate ready queues.
Process affinity -- attempt to keep running on the same processor
Load sharing: push migration -- process觀察後自主換排
pull migration -- idle processor拉waiting process
Symmetric multithreading[SMT] or Intel's hyper-threading[HT] --
One physical processor[PP], multiple logical processors[LP]
Real-time scheduling:
Hard real-time -- within a guaranteed amount of time
=> Resource reservation is needed
Soft real-time -- only receive higher priority
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
Algorithm evaluation methods:
1. Deterministic modeling
Input: a given algorithm, a predetermined workload
Output: Corresponding performance
優：simple and fast
缺：too specific
使用：舉例說明時；同樣程式可以一直跑；觀察趨勢再證明
2. Queuing models -- 排隊理論
Input: distribution of service time, process arrival time, etc.
Output: utilization, average queue, average waiting time, etc.
Little's formula:
n = λ * W
n:queue length; λ:arrival rate; W:waiting time (都是average)
優：compare algorithms
缺：只是理論估計，unrealistic，independent assumptions
3. Simulations -- Programming a model of the system
優：more accurate
缺：跑模擬費時，large storage，coding
4. Implementations -- Construct a read system
優：the most accurate way
缺：too costly, environment may change
沒有留言:
張貼留言