1. 第三章 進程調度的幾種方式
進程調度概念：操作系統必須為多個，嗎進程可能有競爭的請求分配計算機資源。對處理器而言，可分配的資源是在處理器上的執行時間，分配途徑是調度。調度功能必須設計成可以滿足多個目標，包括公平、任何進程都不會餓死、有效地使用處理器時間和低開銷。此外，調度功能可能需要為某些進程的啟動或結束考慮不同的優先順序和實時最後期限。
這些年以來，調度已經成為深入研究的焦點，並且已經實現了許多不同的演算法。如今，調度研究的重點是開發多處理系統，特別是用於多線程的。
下面簡介幾種調度演算法。
一、先來先服務和短作業(進程)優先調度演算法
1．先來先服務調度演算法
先來先服務(FCFS)調度演算法是一種最簡單的調度演算法，該演算法既可用於作業調度，也可用於進程調度。當在作業調度中採用該演算法時，每次調度都是從後備作業隊列中選擇一個或多個最先進入該隊列的作業，將它們調入內存，為它們分配資源、創建進程，然後放入就緒隊列。在進程調度中採用FCFS演算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞後才放棄處理機。
2．短作業(進程)優先調度演算法
短作業(進程)優先調度演算法SJ(P)F，是指對短作業或短進程優先調度的演算法。它們可以分別用於作業調度和進程調度。短作業優先(SJF)的調度演算法是從後備隊列中選擇一個或若干個估計運行時間最短的作業，將它們調入內存運行。而短進程優先(SPF)調度演算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執行並一直執行到完成，或發生某事件而被阻塞放棄處理機時再重新調度。
二、高優先權優先調度演算法
1．優先權調度演算法的類型
為了照顧緊迫型作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先(FPF)調度演算法。此演算法常被用於批處理系統中，作為作業調度演算法，也作為多種操作系統中的進程調度演算法，還可用於實時系統中。當把該演算法用於作業調度時，系統將從後備隊列中選擇若干個優先權最高的作業裝入內存。當用於進程調度時，該演算法是把處理機分配給就緒隊列中優先權最高的進程，這時，又可進一步把該演算法分成如下兩種。
1) 非搶占式優先權演算法
在這種方式下，系統一旦把處理機分配給就緒隊列中優先權最高的進程後，該進程便一直執行下去，直至完成；或因發生某事件使該進程放棄處理機時，系統方可再將處理機重新分配給另一優先權最高的進程。這種調度演算法主要用於批處理系統中；也可用於某些對實時性要求不嚴的實時系統中。
2) 搶占式優先權調度演算法
在這種方式下，系統同樣是把處理機分配給優先權最高的進程，使之執行。但在其執行期間，只要又出現了另一個其優先權更高的進程，進程調度程序就立即停止當前進程(原優先權最高的進程)的執行，重新將處理機分配給新到的優先權最高的進程。因此，在採用這種調度演算法時，是每當系統中出現一個新的就緒進程i 時，就將其優先權Pi與正在執行的進程j 的優先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續執行；但如果是Pi>Pj，則立即停止Pj的執行，做進程切換，使i 進程投入執行。顯然，這種搶占式的優先權調度演算法能更好地滿足緊迫作業的要求，故而常用於要求比較嚴格的實時系統中，以及對性能要求較高的批處理和分時系統中。
2．高響應比優先調度演算法
在批處理系統中，短作業優先演算法是一種比較好的演算法，其主要的不足之處是長作業的運行得不到保證。如果我們能為每個作業引入前面所述的動態優先權，並使作業的優先順序隨著等待時間的增加而以速率a 提高，則長作業在等待一定的時間後，必然有機會分配到處理機。該優先權的變化規律可描述為：
由於等待時間與服務時間之和就是系統對該作業的響應時間，故該優先權又相當於響應比RP。據此，又可表示為：
由上式可以看出：
(1) 如果作業的等待時間相同，則要求服務的時間愈短，其優先權愈高，因而該演算法有利於短作業。
(2) 當要求服務的時間相同時，作業的優先權決定於其等待時間，等待時間愈長，其優先權愈高，因而它實現的是先來先服務。
(3) 對於長作業，作業的優先順序可以隨等待時間的增加而提高，當其等待時間足夠長時，其優先順序便可升到很高，從而也可獲得處理機。簡言之，該演算法既照顧了短作業，又考慮了作業到達的先後次序，不會使長作業長期得不到服務。因此，該演算法實現了一種較好的折衷。當然，在利用該演算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統開銷。
三、基於時間片的輪轉調度演算法
1．時間片輪轉法
1) 基本原理
在早期的時間片輪轉法中，系統將所有的就緒進程按先來先服務的原則排成一個隊列，每次調度時，把CPU 分配給隊首進程，並令其執行一個時間片。時間片的大小從幾ms 到幾百ms。當執行的時間片用完時，由一個計時器發出時鍾中斷請求，調度程序便據此信號來停止該進程的執行，並將它送往就緒隊列的末尾；然後，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程在一給定的時間內均能獲得一時間片的處理機執行時間。換言之，系統能在給定的時間內響應所有用戶的請求。
2．多級反饋隊列調度演算法
前面介紹的各種用作進程調度的演算法都有一定的局限性。如短進程優先的調度演算法，僅照顧了短進程而忽略了長進程，而且如果並未指明進程的長度，則短進程優先和基於進程長度的搶占式調度演算法都將無法使用。而多級反饋隊列調度演算法則不必事先知道各種進程所需的執行時間，而且還可以滿足各種類型進程的需要，因而它是目前被公認的一種較好的進程調度演算法。在採用多級反饋隊列調度演算法的系統中，調度演算法的實施過程如下所述。
(1) 應設置多個就緒隊列，並為各個隊列賦予不同的優先順序。第一個隊列的優先順序最高，第二個隊列次之，其餘各隊列的優先權逐個降低。該演算法賦予各個隊列中進程執行時間片的大小也各不相同，在優先權愈高的隊列中，為每個進程所規定的執行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。
(2) 當一個新進程進入內存後，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度。當輪到該進程執行時，如它能在該時間片內完成，便可准備撤離系統；如果它在一個時間片結束時尚未完成，調度程序便將該進程轉入第二隊列的末尾，再同樣地按FCFS原則等待調度執行；如果它在第二隊列中運行一個時間片後仍未完成，再依次將它放入第三隊列，……，如此下去，當一個長作業(進程)從第一隊列依次降到第n隊列後，在第n 隊列便採取按時間片輪轉的方式運行。
(3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1～(i-1)隊列均空時，才會調度第i隊列中的進程運行。如果處理機正在第i隊列中為某進程服務時，又有新進程進入優先權較高的隊列(第1～(i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第i隊列的末尾，把處理機分配給新到的高優先權進程。
2. 進程調度方案設計 實現一個基本動態優先順序的調度演算法
前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類：批處理系統中的調度演算法，代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。互動式系統中的調度演算法，代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。實時系統中的調度演算法，代表調度演算法有：速率單調調度、最早最終時限優先調度。下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。速率單調調度速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。最早最終時限優先調度最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。
3. 挑戰408——操作系統（8）——典型的調度演算法
調度演算法是操作系統中用於合理分配處理機資源的關鍵技術。在面對如何提高CPU利用率的問題時，不同的系統依據其設計目標選擇不同的調度方式。常見的調度演算法包括先來先服務（FCFS）、短作業優先（SJF或SPF）、高響應比優先（HRRN）、優先順序調度（Priority）、時間片輪轉（RR）以及多級反饋隊列（MFQ）。
先來先服務（FCFS）
FCFS演算法簡單明了，其核心思想是按照程序到達的先後順序進行調度，類似於隊列的先進先出原則。它適合作業調度與進程調度，每次從就緒隊列中選擇最先進入隊列的進程分配處理機。該演算法雖然表面上看起來公平，但長作業的突然到來會導致短作業長期等待，不利於I/O繁忙作業的處理，常作為其他調度策略的輔助手段。
短作業優先（SJF或SPF）
SJF演算法通過選擇預計運行時間最短的進程進行調度，以減少作業或進程的平均周轉時間。同樣適用於作業調度和進程調度。然而，這種方法可能不利於長作業，容易導致飢餓現象，並未考慮作業的緊迫程度。
高響應比優先（HRRN）
HRRN演算法綜合了FCFS和SJF的特性，考慮每個作業的等待時間和估計運行時間。通過響應比（周轉時間/運行時間）來衡量作業的優先順序，實現對作業調度的動態平衡。
優先順序調度（Priority）
優先順序調度演算法旨在滿足緊急進程的及時處理，支持作業調度和進程調度。靜態優先順序在進程創建時確定，保持不變；動態優先順序隨進程執行情況動態調整，以優化系統性能。
時間片輪轉（RR）
RR演算法主要用於進程調度，常用於分時系統。通過將就緒進程按FCFS原則排序，每次分配固定時間片的處理機資源。時間片過長導致退化為FCFS，過短則增加用戶響應時間，特別不利於I/O頻繁的進程。
多級反饋隊列（MFQ）
MFQ演算法設置多個優先順序不同的就緒隊列，優先順序越高，時間片越短。進程按FCFS原則加入最高優先順序隊列，若未完成，則依次移至較低優先順序隊列。此演算法結合了前幾種演算法的優點，但需注意避免前隊列長期阻塞導致後續隊列飢餓。
調度演算法比較
通過綜合對比各類調度演算法，可以清晰地看到它們在公平性、響應時間、資源利用率等方面的差異。選擇合適的調度演算法取決於系統的目標、資源狀況和應用需求。
4. 進程調度
當計算機中有多個process處於ready狀態，將CPU分配給哪個進程呢？操作系統中做出這個決策的組件就是調度器，決策的演算法叫調度演算法，決策過程就是進程調度的過程。
進程調度一般發生在一下幾種情況下：
在非搶占式調度中，進程開始執行以後，除非它主動放棄CPU或被block, 否則就能一直執行。
搶占式調度中，如果在進程執行過程中來了一個優先順序更高的進程，CPU使用權就會被搶走，尤其在時間片調度中即使時間片沒用完也可以被搶占。但搶占也不是隨時可以發生的，如果設計不好可能會發生優先順序逆轉或者死鎖問題。
在不同的場景下，為了實現不同的目標，評價調度演算法的標准不盡相同。這里我們介紹一些常用的標准：
Fairness : 給每個進程公平的CPU使用機會
Balance : 讓系統的各個組件都能得到最大程度的利用率
Throughput 吞吐量 ：單位時間內完成的任務數量
Turnaround Time ：一般在批處理系統中，一個批任務從提交到結束的間隔時間
CPU Utilization ：CPU的利用率
Waiting Time ：進程在ready隊列里等待的時間
Response Time ：一般在互動式系統中，從用戶提交任務到第一次得到響應（任務不一定完成）的間隔時間
Meeting Deadline ：一般在實時系統中及時處理數據，避免丟失或失效
接下來我們看看在三種不同類型系統中常用的調度演算法。
1. FCFS : First Come, First Served
這是一種非搶占式的先來先服務演算法。ready process隊列只有一個。如果進程執行中被block，進入block隊列，ready之後作為新的進程排到ready隊列的尾部。
優點：容易理解，容易實現
缺點：平均等待時間往往很長，不好平衡CPU密集和IO密集型進程
2. SJF: Shortest Job First
SJF也是非搶占式調度，每次都選擇最短的任務來執行。
3. Shortest Remaining Time Next
是SJF的搶占式版本，只要有新任務到達就重新調度選擇剩餘時間最短的任務執行。
SJF和Shortest Remaining Time Next的問題在於一般情況下很難判斷進程的剩餘執行時間是多少。除非這是經常要執行的task，根據對歷史的統計分析能確定一個執行時間的大致范圍。
1. Round-Robin Scheling
輪詢調度。 給每個進程相同的時間片，輪流執行。一般時間片選擇在20-50msec比較合適，太短會導致進程切換浪費時間，太長會導致響應時間延長。
優點：比SJF響應快
缺點：turnaround時間長
2. Priority Scheling
優先順序調度為每個進程分配優先順序，高優先順序先執行，這也是時間片調度演算法。優先順序可以靜態分配也可以動態分配，為了避免高優先順序的進程一直佔用CPU不放，可以在依次執行結束後降低其優先順序。相同優先順序的進程之間可以使用其他的調度演算法如round-robin，不同隊列可以使用不同的調度演算法。
優點：引入了優先順序
3. Multiple Queues
為了避免執行時間長的進程頻繁進程切換，可以在不同的優先順序隊列之間分配不等長度的時間片。進程執行一次之後被分配其他擁有更長執行時間的優先順序。比如一個進程需要100個quanta, 第一次執行時分配1個，下一次執行分配2個，再下次分配4，8，16，32，64. 比每次都只分配1的純輪詢演算法減少了進程調度的次數。
4. Guaranteed Scheling
前面提到的演算法都不保證進程能夠得到的CPU時間，但有些情況下我們需要確保進程使用CPU的機會和時間，比如n個用戶同時登錄，一般要保證每個用戶都能獲得1/n的CPU，或者我們購買VPN服務，根據不同的用戶級別需要獲得一定的帶寬保證。這種演算法就叫Guaranteed 調度。在實現中，需要追蹤給每個進程分配的CPU，與承諾分配量比較，比值最小的進程會獲得下一次使用權。
5. Lottery Scheling
彩票調度演算法引入了隨機性，為每個進程發一張彩票，調度時就像開獎，誰中獎誰獲得資源。優先順序更高的進程可以獲得多張彩票以提高中獎機會。
彩票調度有趣的地方在於進程之間可以互贈彩票，比如process 1 pending在process 2上，它可以把自己的彩票都給process2提高它被調度的機會。process2結束以後再把彩票還給process1.
6. Fair-Share Scheling
下面考慮一種情況，所有進程並不屬於一個用戶，這在Linux 系統中非常常見。如果user1有99個process，user2隻有1個process，按照前面的演算法可能user1能得到99%的CPU，而user2隻有1%。為了實現用戶層面的公平性，調度時需要考慮進程屬於哪個user.
實時系統分兩種：
實時系統中，一般任務時間都比較短，調度器需要使所有進程都在deadline前完成。對於周期性發生的事件，如果事件發生的周期為 , 事件處理時間(需要佔用CPU的時間)為 , 只有 時，才是可調度的。
調度演算法只能由操作系統實現嗎，關於使用哪種調度演算法進程是否有話語權呢？答案是可以的。將機制與策略分離，由操作系統提供多種實現機制，並提供system call由process傳參數給OS指定具體使用哪一種調度策略。
如果線程是在用戶態實現的，那麼需要兩級調度，OS負責調度process，process負責調度thread。如果線程是在內核態實現的，OS直接調度thread，而不關心它屬於哪個process。