一、課程內容概述

本節課程主要講解操作系統的CPU調度策略，聚焦于基本操作系統上的調度算法，探討其大致實現方式、需折中考慮的問題。CPU調度在不同場景下復雜程度不同，如衛星、導彈等實時性要求高的系統，需采用實時調度，而本次課程主要圍繞常見的基本調度策略展開，不求窮盡所有算法，旨在以點帶面，幫助學習者觸類旁通。

二、CPU調度的基本概念

1. 調度與切換的關系：在多進程圖像下，CPU調度和進程切換緊密相連。調度的目的是從就緒隊列中選取下一個要執行的進程（獲得next），并切換到該進程（switch to next），從而使操作系統能夠實際運轉。例如，當一個進程（如p1）在執行過程中因阻塞、時間片到期等原因無法繼續執行時，操作系統需從就緒隊列中選擇另一個進程（如p2或p3）來執行，此時就涉及到調度策略的選擇。

2. 調度的直觀想法：其直觀思路是從就緒隊列的眾多進程中選擇執行對象。生活中的銀行、食堂等場景也存在類似調度，最常見的方法是先來先服務（先入先出），這種方法簡單公平，但存在局限性。比如在銀行，對于簡單詢問業務的客戶，若采用先來先服務，可能導致其等待時間過長，不太合理，因此可考慮短作業適當優先。然而，若短作業的處理時間不斷延長，又需適當降低其優先級，這就引出了優先級調度的概念，且優先級在實際中會不斷變化 。
   

三、設計調度算法的指標

1. 進程滿意的關鍵因素：設計調度算法需要明確指標，而讓進程滿意的關鍵在于時間相關因素。對于進程而言，用戶希望程序執行速度快，這涉及到多種時間指標，如周轉時間和響應時間。
2. 周轉時間：周轉時間是指從任務進入系統到任務結束的時間，用戶希望該時間越短越好。例如，在編譯任務中，用戶期望編譯過程盡快完成。
3. 響應時間：響應時間是從操作發生到系統產生反應的時間，對于一些前臺任務（如word操作），用戶更關注響應時間。比如按下鍵盤后，希望字符能盡快顯示在屏幕上。
4. 其他指標：除了周轉時間和響應時間，系統內耗時間也應盡量少，否則會減少實際用于處理任務的時間，導致用戶不滿。同時，系統完成任務的數量（吞吐量）應盡量大 。

四、CPU調度的關鍵——折中和綜合

1. 系統任務的多樣性與矛盾：操作系統中存在多種任務，如前臺任務（如ppt操作）和后臺任務（如圖像壓縮），它們關注點不同，前臺任務更關注響應時間，后臺任務更關注周轉時間。而且這些任務之間相互影響，例如，若要滿足前臺任務響應時間短的要求，就需要增加進程切換次數，但這會導致系統內耗增大，進而使后臺任務的周轉時間變長，因此CPU調度需要在這些相互矛盾的需求之間進行折中、平衡與綜合 。
2. I/O約束性任務和CPU約束性任務：I/O約束性任務的特點是I/O操作較多，CPU執行區間短且頻率高，如銀行出納工作、word操作等；與之相對的是CPU約束性任務，這類任務長時間進行計算，幾乎沒有I/O操作，例如gcc編譯、matlab矩陣計算等。由于兩者特點不同，調度優先級也應有所區別，I/O約束性任務通常優先級更高，因為它優先執行可以使I/O和CPU并行工作，提高系統效率，且I/O約束性任務往往是前臺任務，為了給用戶及時反饋，也應賦予較高優先級 。

五、常見調度算法

1. 先來先服務（FCFS）：這是最簡單的調度算法，按照進程到達就緒隊列的先后順序進行調度。例如，進程p1先到達，p5后到達，調度順序就是p1執行完后p2，依次類推直到p5。但這種算法可能導致周轉時間較長，通過調整進程執行順序，將短作業提前執行，可降低周轉時間，提高系統整體滿意度，由此引出短作業優先（SJF）算法 。

2. 短作業優先（SJF）：該算法將短作業優先執行，可證明這種方法能使周轉時間最小。因為在計算周轉時間的公式中，先執行的作業被重復計算的次數更多，所以將短作業放在前面執行，最終得到的周轉時間總和更小。這種算法在實際中有重要價值，但也有局限性 。

3. 時間片輪轉調度（RR）：為保證響應時間，引入時間片輪轉調度算法。它將CPU時間劃分為固定大小的時間片，每個進程輪流執行一個時間片。例如，給進程p1、p2、p3各分配10個時間片，執行完后再為后續進程分配。通過這種方式，可保證最長響應時間在一定范圍內（為進程數量乘以時間片大小），從而確保響應時間。為提高響應速度，時間片應盡量小，但同時要限制系統中進程的數量 。

4. 優先級調度：由于不同任務對響應時間和周轉時間的需求不同，可采用優先級調度。直觀做法是設置前臺任務隊列和后臺任務隊列，前臺任務采用輪轉調度以保證響應時間，后臺任務采用短作業優先以減少周轉時間，然后通過優先級來決定執行順序，前臺任務優先級高于后臺任務。
   但如果采用絕對優先級調度，可能導致后臺任務饑餓，如1967年提交的一個進程，因前臺任務不斷出現，直到1973年都未執行。因此，任務優先級應動態調整，但這又會引發新的矛盾，如后臺長CPU任務執行時會影響前臺任務響應時間。所以，調度算法需要綜合考慮輪轉調度、優先級和短作業優先等因素，且應具備學習機制，能根據任務特點和變化自適應調整，以實現對各種任務的折中與綜合 。
   
   

六、課程總結與展望

本次課程介紹了CPU調度的含義，即從就緒隊列選取進程執行，強調調度算法需考慮周轉時間、響應時間、任務特點和優先級等因素，還講解了先來先服務、短作業優先、時間片輪轉調度三種基本算法。未來課程將在此基礎上，展示如何綜合這些基本算法，設計出簡單且能有效折中多種任務需求的實際調度程序，以應對操作系統中多任務的復雜情況 。