CPU排程 (CPU scheduling)：多個程序同時處于記憶體，當一個程序必須等待時，OS從該程序拿走CPU使用權交給其他程序。
程序執行從一個IO區間(I/O burst)開始，随後進入一個CPU區間(CPU burst)并反複，程序循環地在CPU執行和I/O等待兩個狀态間切換，直到通過系統請求終止最後一個CPU burst。
CPU burst的長度随程序和計算機的不同而變化，通常具有大量短CPU burst和少量長CPU burst。I/O限制程式通常具有很多短CPU burst，CPU限制程式可能有少量長CPU burst。
每當CPU空閑時，OS就使用短期排程程式(short-term scheduler) （或CPU scheduler）從就緒隊列中選擇一個能夠執行的程序并為它配置設定CPU。
就緒隊列不一定是FIFO隊列。就緒隊列中的記錄通常為PCB。
搶占&非搶占
CPU排程決策發生在4種情況下：
1) 程序從運作(running)狀态切換到等待(waiting)狀态；
2) 程序從運作(running)狀态切換到就緒(ready)狀态；
3) 程序從等待(waiting)狀态切換到就緒(ready)狀态；
4) 程序終止
非搶占(nonpreemptive)排程方案：a.k.a. 協作(cooperative)排程方案，一旦CPU配置設定給一個程序，該程序會一直使用CPU直到程序終止或切換到等待狀态，該方案中排程隻發生在1、4兩種情況下。
否則稱為搶占(preemptive)排程方案。
分派程式
分派程式(dispatcher)：每次程序切換時都要使用的一個子產品，用于将CPU控制交給由short-term scheduler 所選的程序。功能包括1)切換上下文；2)切換到使用者模式；3)跳轉使用者程式的合适位置來重新開機程式。
分派延遲(dispatch latency)：dispatcher停止一個程序并啟動另一個程序所用的時間。
排程準則
用于分析比較CPU排程算法的準則可包括
·CPU使用率(CPU utilization)：理論上為0%~100%，真實系統一般為40%~90%。
·吞吐量(Throughput)：一個時間機關内所完成程序的數量。
·周轉時間(Turnaround time)：一個程序從送出到完成的所用時間。
·等待時間(Waiting time)：程序在就緒隊列中等待所用時間之和。
·響應時間(response time)：從送出請求到産生第一響應的所用時間。
需要使CPU utilization和throughput最大化，turnaround time、waiting time和response time最小化。絕大多數情況下需要優化平均值，有些情況下需要優化最大值、最小值或response time方差等。
排程算法
FCFS （最簡單，但會讓短程序等待時間非常長）
先到先服務排程算法(first-come, first-served (FCFS) scheduling algorithm)：先請求CPU的程序先配置設定到CPU，通常用FIFO隊列實作。 [nonpreemptive]
FCFS政策平均等待時間通常較長，不适用于time-sharing系統。
護航效果(convoy effect)：所有其他程序都等待一個大程序釋放CPU，相比讓較短程序最先執行的情況，CPU和裝置的使用率更低。
SJF （提供最短平均等待時間）
最短作業有限排程算法(shortest-job-first (SJF) scheduling algorithm)：每個程序與其下一個CPU burst關聯。當CPU空閑時，将它配置設定給具有最短CPU burst的程序。[preemptive or nonpreemptive]
更适當的術語表示應該是 “the shortest-next-CPU-burst algorithm”，命名為SJF主要是因為慣例。
難點：如何知道下一CPU burst的長度。
1) 對于（batch system中的）long-term job scheduling，可将使用者送出job時所指定的process time limit作為長度。
2) 對于short-term CPU scheduling，下一CPU burst的長度無法知道。可對下一CPU burst長度進行預測，選擇具有最短預測CPU burst的程序。
下一CPU burst通常預測為以前CPU burst區間測量長度的指數平均(exponential average)。
τn+1 = αtn + (1-α) τn
tn – 第n個CPU burst的長度（記錄最近資訊）；
τn – 第n個CPU burst的預測值（記錄過去曆史）；
τn+1 – 下一CPU burst的預測值；
α – 控制最近和過去曆史在預測中的相對權重，0≤α≤1。
preemptive的SJF排程 – 最短剩餘時間優先排程(shortest-remaining-time-first scheduling)，如果到達就緒隊列的新程序有比目前運作程序更短的CPU burst，可搶占CPU。
Nonpreemptive的SJF排程 – 允許目前運作的程序先完成。
優先級排程
優先級排程算法(priority scheduling algorithm)：每個程序都與一個優先級(priority)關聯，CPU被配置設定給具有最高priority的程序，相同priority的程序按FCFS順序排程。[preemptive or nonpreemptive]
SJF是優先級排程的一個特例，其priority為下一CPU burst的倒數。
Priority通常為固定區間的數字，有的系統用小數字表示低priority，有的系統則用小數字表示高priority。
Priority可通過内部或外部定義。
内部priority通過對程序的測量資料（e.g. 時間極限、記憶體要求、打開檔案數量、平均I/O burst和平均CPU burst之比）計算來定義；
外部priority通過OS之外的準則（e.g. 程序重要性、使用計算機的費用類型和數量、贊助機關等因素）。
Preemptive的priority排程 – 如果到達就緒隊列的新程序有比目前運作程序更高的priority，可搶占CPU。
Nonpreemptive的priority排程 – 将新程序加到就緒隊列的頭部。
優先級排程和SJF排程會産生饑餓，可用老化技術解決。
Problem – 無窮阻塞（indefinite blocking）/饑餓（starvation）：某個低priority程序可能會無窮等待CPU。
Solution — 老化（aging）：逐漸增加在系統中等待很長時間的程序的priority，使得最終該程序擁有最高priority并能執行。
RR （适合分時/互動系統）
時間片(time quantum, a.k.a. time slice)：一個較小的時間單元，通常為10~100ms。
輪轉法排程算法(round-robin (RR) scheduling algorithm)：專門為time-sharing系統設計，CPU排程程式循環就緒隊列，為每個程序配置設定不超過一個time quantum的CPU。[preemptive]
實作
CPU排程程式每次從FIFO就緒隊列中選擇第一個程序，設定定時器在一個time quantum後終端，再dispatch該程序。
1) 如果目前運作程序的CPU burst短于time quantum，則CPU由程序自動釋放，排程程式再處理下一個程序；
2) 如果目前運作程序的CPU burst長于time quantum，則到點後定時器向OS發送中斷，執行上下文切換，程序被加入到就緒隊列尾部，CPU排程程式再處理下一個程序。（被搶占）
采用RR的平均waiting time通常較長。
主要問題：選擇時間片。RR算法的性能非常依賴于time quantum的大小。
如果time quantum太大，則與FCFS一樣；
如果time quantum很小，則因上下文切換而引起的排程開銷過大。
Time quantum應該比context switch時間長。
處理器共享(processor sharing)：如果time quantum很小，則RR可産生“n個程序都有它自己的處理器，各自速度都為真正處理器速度的1/n”的效果。
多級隊列排程（允許多個不同算法用于各種類型的程序）
多級隊列排程算法(multilevel queue scheduling algorithm)：将就緒隊列劃分成多個獨立隊列，每個隊列有自己的排程算法。程序根據自身屬性被永久配置設定到對應的一個隊列。
常用模型：前台互動隊列使用RR，和背景批處理隊列使用FCFS。
隊列之間必須有排程。可采用
1) 固定優先級搶占排程(fixed-priority preemptive scheduling) – 每個隊列相比更低層隊列有絕對的priority。對于一個隊列，隻有高層隊列都為空時該隊列内程序才可運作；如果有新程序進入高層隊列則CPU會被搶占。[通常采用]
2) 在隊列間劃分time-slice – 每個隊列有固定的CPU時間，在自己的CPU時間内可排程隊列内程序。
多級回報隊列排程
對比多級隊列排程 –允許程序在隊列之間移動，相比開銷更大，更靈活。
多級回報隊列排程算法(multilevel feedback queue scheduling algorithm)：根據CPU burst的特點區分程序。如果程序使用過多CPU時間則轉移到更低隊列，在低priority隊列中等待時間過長的程序可被轉移到高priority隊列（aging的一種形式）。
可由以下參數定義：
1) 隊列數量；
2) 每個隊列的排程算法；
3) 用于确定何時更新到更高priority隊列的方法；
4) 用于确定何時降級到更低priority隊列的方法；
5) 用于确定程序需要服務時應進入哪個隊列的方法。
e.g.
隊列0中，不能在8ms内完成的程序會被搶占，移到隊列1尾部；
隊列1中，不能在16ms内完成的程序會被搶占，移到隊列2尾部；
隻有隊列0和1為空時，隊列2内程序才可根據FCFS運作。
多處理器排程(multuiple-processor scheduling)
同構(homogeneous)：processor功能相同。同構系統中，可将任何processor用于運作隊列中的任何程序。
目前許多計算機都支援multiprocessing，并允許每個processor獨立排程自己。通常每個processor維護自己私有的程序或線程隊列。
多處理器排程的方法
1) 非對稱多處理(asymmetric multiprocessing)方法：讓單獨的一個processor (master server) 處理所有排程決策、I/O處理和其他系統活動，其它processor隻執行使用者代碼。（簡單，隻有一個processor通路系統資料結構，減輕資料共享的需要）
2) 對稱多處理(symmetric multiprocessing, SMP)方法：每個processor是self-scheduling的，每個processor檢查就緒隊列并選擇一個程序來執行。（所用程序可能處于一個共同的就緒隊列中，或每個processor都有私有的就緒隊列。）
在絕大多數支援SMP的當代作業系統中，每個processor都有私有的就緒隊列。
幾乎現代作業系統都支援SMP。
處理器親和性
處理器親和性(Processor affinity)：程序對其運作所在的processor的親和性，盡量使一個程序在同一個processor上運作，避免将程序在processors之間遷移。
由于在processors之間遷移程序的代價(1. 使原processor的cache無效 2. 重新建構新processor的cache)高，大多數SMP系統都具有processor affinity。
優點：程序可以利用它在原processor的cache中的資料。
Processor affinity通常有兩種形式：
軟親和性(soft affinity)：OS具有讓一個程序保持在同一個processor上的運作政策，但不能做任何保證，程序有可能移動。
硬親和性(hard affinity)：允許程序指定它不能遷移至其他processor上。E.g. Linux提供
負載平衡
負載平衡(Load balancing)：設法将工作負載平均配置設定到SMP系統的所有processor上。
對于“擁有自己私有的就緒隊列”的processor來說是必需的，“具有共同就緒隊列”的系統通常不需要。
Load balancing通常有兩種方法：
Push migration：一個特定的task周期性地檢查每個processor上的負載，如果發現不平衡就把程序從過載的processor push到空閑或不太忙的processor上。
Pull migration：空閑的processor從忙碌的processor上pull走一個waiting task。
Push migration和pull migration可以并行實作，不需要互斥。
e.g. Linux scheduler, ULE scheduler for FreeBSD.
Load balancing通常會抵消掉processor affinity的好處，關于何種方式更好并沒有絕對的規則。有些系統中隻有當不平衡達到一定額度後才會移動程序。
SMT
對稱多線程(Symmetric multithreading, SMT)：提供多個logical processors來實作多線程同時運作的政策。在intel processors中也稱為超線程(hyperthreading)技術。
SMT在同一physical processor上生成多個logical processor，向OS呈現一個“多個logical processors”的視圖。
每個logical processor都有自己的架構狀态(architecture state)，包括general-purpose和machine-state registers。
每個logical processor負責自己的中斷處理。
SMT是由硬體（而不是軟體）提供的。硬體應提供每個logical processor的架構狀态的表示以及中斷處理方法，OS不需要特殊設計。
線程排程(Thread Scheduling)
對于支援多線程的OS，OS排程的是核心線程，而不是程序。
競争範圍
使用者線程和核心線程所用排程方法的不同
程序競争範圍(Process-contention scope, PCS)：在實作多對一或多對多模型的系統中，線程庫排程使用者級線程到可用的LWP上。i.e. CPU競争發生在“屬于相同程序的線程”之間。
系統競争範圍(System-contention scope, SCS)：OS将核心線程排程到實體CPU上，該競争發生在OS的所有線程中。采用一對一模型的OS的線程排程隻采用SCS。
PCS通常根據priority來完成排程 [preemptive] ，但在具有相同priority的線程間并不保證有time slicing。
Pthread線程排程
POSIX Pthread API允許線上程生成中指定是PCS或SCS。競争範圍值PTHREAD_SCOPE_PROCESS表示“采用PCS排程”，PTHREAD_SCOPE_SYSTEM表示“采用SCS排程”。
函數pthread_attr_setscope(pthread attr_t *attr, int scope)、pthread_attr_getscope(pthread_attr_t *attr, int *scope) 用于擷取及設定競争範圍。
某些OS隻允許特定的競争範圍值。E.g. Linux, Mac OS X隻允許PTHREAD_SCOPE_SYSTEM。
OS執行個體
對于支援核心級線程的OS，必須排程線程（而不是程序）來執行。
以下3種OS通常偏愛互動程序而不是批處理程序或CPU-bound程序。
Solaris的核心線程排程（搶占、基于優先級、支援實時線程）
傳統Solaris使用多對多模型，Solaris 9使用一對一模型。
Solaris按照優先級排序有4種排程類型： 實時(real time)、系統(System)、分時(Time sharing)和互動(Interactive)，每種類型有不同的priority和排程算法。
Scheduler将特定類的priority轉換為全局priority，再選擇全局priority最高的線程來執行，直到該線程阻塞、用完time quantum或被更高priority的線程搶占。如果多個線程的priority相同，則采用循環隊列。
Solaris 9引入2種新的排程類型：
1) 固定優先級(fixed priority) – 線程的priority與time sharing類型範圍相同，但不能動态調節。
2) 公平共享(fair share) – 用CPU shares代替priority來做排程決策。
CPU shares：表明可用CPU資源的權利，并被配置設定到一個project(程序集)。
Time sharing類(預設排程類型)和Interactive類采用同樣的排程政策(多級回報隊列)，Priority和time quantum預設成反比。
通常Interactive程序的priority更高，CPU-bound程序的priority更低。
Interactive和time sharing類包括60個優先級，在其排程中：
時間片到期(Time quantum expired)（i.e. 用完其time-quantum而未堵塞）的線程将被認為是CPU-intensive的，并被降低優先級。
從睡眠中傳回(Return from sleep)（e.g. 從等待I/O中傳回）的線程優先級将被提高。
System類專門保留給核心使用，用于運作核心程序。System程序一旦建立，其priority就不再改變。（在核心模式下運作的使用者程序并不屬于system類。）
Real time類的程序具有最高priority，能在其他類型程序之前運作。通常隻有少數程序屬于real time類。
Windows XP的核心線程排程（基于優先級、搶占、支援實時線程）
Dispatcher：Windows XP核心中用于處理排程的部分。（應該與前面所介紹的分派程式dispatcher不同）
Dispatcher選擇priority最高的線程來執行，直到該程序被更高priority的程序搶占、終止、用完time quantum或調用了blocking system call。
Dispatcher使用32級priority方案，priority分為兩大類型：
Priority 0的線程用于記憶體管理
Priority 1~15的線程屬于可變類型(variable class)，此類線程的priority可以改變。
Priority 16~31的線程屬于實時類型(real-time class)
Dispatcher為每個priority使用一個隊列，并從高到低檢查隊列集，直到發現一個可以執行的線程。如果沒有找到，則執行一個稱為空閑線程(idle thread)的特别線程。
Win32 API定義了程序可能屬于的priority類型：
1) REALTIME_PRIORITY CLASS
2) HIGH_PRIORITY_CLASS
3) ABOVE_NORMAL_PRIORITY_CLASS
4) NORMAL_PRIORITY_CLASS
5) BELOW_NORMAL_PRIORITY_CLASS
6) IDLE_PRIORITY_CLASS
其中，REALTIME_PRIORITY_CLASS屬于real-time class，其它類型屬于variable class。
程序通常屬于NORMAL_PRIORITY_CLASS，除非其父程序為IDLE_PRIORITY_CLASS或在建立該程序時指定其他類型。
每個線程的priority都基于其所屬priority類型和它在該類型中的relative priority。Relative priority的值包括：
1) TIME_CRITICAL
2) HIGHEST
3) ABOVE_NORMAL
4) NORMAL
5) BELOW_NORMAL
6) LOWEST
7) IDLE
基礎優先級(base priority)：每個線程都有的一個（在其所屬類型範圍内的）priority值，預設為該類型中relative priority為NORMAL的值。
線程的priority初始值通常為所屬程序的base priority。
線程的time quantum用盡時将被中斷，如果該線程屬于variable class則其priority将降低，但絕不會低于其base priority。
當屬于variable class的線程被從等待操作中釋放時，其priority将提升（提升多少取決于該線程等待的是什麼）。
e.g. 等待I/O比等待磁盤操作得到的提升更大，縮短互動線程的響應時間。
為了給互動程式的程序提供優秀的性能，Windows XP對NORMAL_PRIORITY_CLASS的程序有一個特别排程規則 – 區分前台程序和背景程序，當程序進入前台時增加其time quantum的倍數（通常為3）。
Linux核心排程（基于優先級，搶占、提供實時支援）（Linux不區分程序和線程，使用task。）
2.5版本前運作傳統UNIX算法，存在問題：1) 對SMP系統沒有提供足夠支援 2) tasks數量增加時無法按比例調整。2.5版本提供了O(1)的排程算法和對SMP的支援。
Linux兩個獨立的priority range：
Real-time (0~99)：被配置設定靜态priority。
Nice (100~140)：具有動态priority，根據task的互動性決定+5還是-5。（互動性更強的任務通常-5，使priority更高）
這兩個ranges映射到global priority，數值越低priority越高。
Linux中配置設定給task的time quantum與priority成反比。（與Solaris、Windows XP相反）
runque：核心所維護的一個資料結構，記錄可運作tasks的清單。每個runque包括兩個priority arrays，每個priority array都有一個根據priority索引的tasks清單。
Active array包括所有在time quantum中還有剩餘的tasks；
Expired array包括所有已到期（耗盡time quantum）的tasks。
因為支援SMP，每個processor都需維護自己的runque并自行排程。排程時，從active array中選擇priority最高的task來在CPU上執行。Task到期被移至expired array後将重新計算動态優先級。當所有tasks都到期（I.e. active array為空）時，兩個array互換。
排程算法評估
分析評估法(analytic evaluation)：評估算法的一種主要方法，使用給定算法和系統負荷産生一個公式或數字來評估算法在該負荷下的性能。（使用數學分析）
确定模型
确定模型法(deterministic modeling)：analytic evaluation的一種。使用預先确定的特定負荷，計算每個算法在該負荷下的性能。主要用于描述排程算法和提供例子。
缺點：要求輸入精确數字，并且答案隻适用于給定情況。
排隊模型
對于許多系統，程序集合并不是靜态的但可以通過測量CPU burst分布和程序到達系統的時間分布來估計程序的到達率(arrival rates)和CPU的服務率(service rates)。
排隊網絡分析(queueing-network analysis)：CPU可看做具有一個等待程序隊列的伺服器，從程序的到達率和服務率可計算CPU使用率、平均隊列長度、平均等待時間等。主要用于比較排程算法。
缺點：隊列模型隻是現實系統的近似，難以處理複雜算法或分布。
Little formula: (可用于根據3個變量中的2個來計算另外1個)
n – 平均隊列長度； W – 隊列平均等待時間；