基本概念

1、物理CPU、邏輯CPU、CPU核數

(1)一個物理CPU上有多個CPU核，如果采用了intel的超線程技術(HT), 就會再多出一倍的cpu核出來

(2)一般情況下，邏輯cpu數=物理CPU*cpu核數

(3)如果采用了超線程技術，則正常邏輯cpu數=物理CPU*cpu核數*2

top看到的cpu個數以及java中的Runtime.getRuntime().availableProcessors()獲得到的都是邏輯cpu數。

2、 隊列中的記錄通常是進程的進程控制塊。

3、CPU調度決策可在如下四種環境下發生

(1)當一個進程從運行狀態切換到等待狀態 例如，I/O請求或調用wait以等待一個子進程的終止

(2) 當一個進程從運行狀態切換到就需狀態 例如，當出現中斷

(3)當一個進程從等待狀態切換到就需狀態 例如，I/O完成

(4)當一個進程終止

當調度只能發生在第一和第四種種情況時，稱調度方案是非搶占的，否則調度方案是可搶占的。采用非搶占調度，一旦CPU被分配給一個進程，那麼該進程會一直使用CPU直到進程終止或切換到等待狀態時釋放CPU

 

查看Android設備CPU信息

查看物理CPU的個數

#cat /proc/cpuinfo |grep "physical id"|sort |uniq|wc -l

查看邏輯CPU的個數

#cat /proc/cpuinfo |grep "processor"|wc -l

查看CPU是幾核

#cat /proc/cpuinfo |grep "cores"|uniq

如果邏輯cpu數不是物理CPU數*CPU核數，而是其2倍，則代表采用超線程技術，cat /proc/cpuinfo |grep "core id"，相同的core id即代表是同一個核超級程。

 

CPU調度

用於多道程序，先討論對於單CPU的調度問題。

回顧多道程序，同時把多個進程導入內存，使得一個進程在CPU中執行I/O時，一個進程用來填補CPU的時間。通常進程都是在CPU區間和I/O區間之間轉換。CPU調度程序稱為短期調度程序，從內存調度到CPU。

在內存中等待的就緒隊列的節點是PCB。有許多不同的隊列實現方法。

搶占調度和非搶占調度(協作)：前者為一個進程還沒結束之前就被奪取CPU的擁有權，而後者則要一個進程結束或等待I/O才給予其他進程CPU的擁有權。

雖然現代操作系統都是用搶占調度，但是對於同時訪問一個數據來說就會有風險，比如一個進程在試圖更新一個數據，但是另一個進程搶占，並且讀取這個數據，使得數據不一致。這時就要用到進程同步的內容。lock對於中斷隨時可能發生的情況，我們可以在執行某個代碼段時，禁止中斷。分派程序用來把CPU的擁有權交給短期調度程序選定的進程。每次切換進程時都要使用。

分派延遲：分派程序所花的時間。

 

CPU調度需要考慮的因素：

1.CPU使用率。

2.吞吐量：單位時間完成進程的數量。

3.周轉時間：進程提交到進程完成。即從磁盤等待進入內存+就緒隊列等待時間+CPU執行時間+I/O執行時間。但是CPU調度算法只是裡面的一塊。

4.等待時間：在就緒隊列等待的時間之和。

5.響應時間：用於交互系統。

 

調度准則

CPU使用率： 40%到90%

吞吐量：一個時間單元內所完成進程的數量。

周轉時間：從進程提交到進程完成的時間間隔稱為周轉時間。周轉時間是所有時間段之和，包括等待進入內存、在就緒隊列中等待，在cpu上執行和I/O執行

等待時間：CPU調度算法並不影響進程運行和執行I/O的時間量。它只影響進程在就需隊列中等待所花費的時間。

響應時間：從提交請求到產生第一響應的時間。是開始響應所需要的時間，而不是輸出該響應所需要的時間。

CPU使用率和吞吐量最大化，周轉時間、等待時間和相應時間最小化

 

CPU調度算法：

1.FCFS 先到先服務

一旦選定進程，那麼在結束之前就不能再切換到另一個進程。

2.SJF 最短優先 精確的講是最短下一個CPU區間的算法

前面提到，一個進程是由CPU區間和I/O區間交替組成的。而SJF是看哪個進程的CPU區間最短。

（1）SRTF搶占式：又稱最短剩余優先，當新進來的進程的CPU區間比當前執行的進程所剩的CPU區間短，則搶占。

（2）非搶占：稱為下一個最短優先，因為在就緒隊列中選擇最短CPU區間的進程放在隊頭。

SJF用於長期調度而不能用短期調度，因為進程是一個整體，CPU沒法知道進程中第一個CPU區間長度。

SJF需要確定下一個CPU區間的時間長度，可以通過近似估算出下一個CPU區間的長度，比如tn+1=atn+(1-a)rn tn為最近最近一次的CPU時間，rn為歷史記錄。a是給定的權重。

3.優先級調度算法 pintos的優先級是0-63 0為最低優先級，63為最高優先級

SJF是特殊的優先級調度算法，以CPU區間長度的倒數為優先級。

（1）內部優先級：通過內部數據比如內存要求等。

（2）外部優先級：用戶自己設定。set_priority

分為搶占式和非搶占式，前者為如果進來的進程優先級高於運行的進程，則替換；後者只是在就緒隊列中按優先級排隊。

缺點：無線阻塞或饑餓。前者為一個優先級高且運行時間長的進程一直阻塞，後者為優先級低的進程永遠都得不到執行。

解決饑餓的方法是老化。通過每個時間間隔後將等待的進程優先級降低。

4.轉輪法 RR算法 搶占式

用於分時系統。每個進程都占用一個時間片的時間。就緒隊列為FIFO循環隊列。如果一個進程的CPU區間長度小於時間片，則繼續下面的進程；如果大於時間片，則中斷切換到下一個進程執行。通常時間片長度為10ms-100ms，由此需要確定時間片大小使得上下文切換次數適當少。

5.多級隊列調度

根據某種性質將一個就緒隊列分成不同的獨立隊列，如系統進程，交互進程（前台進程），交互編輯進程，批處理進程，學生進程。

每個隊列都有不同的調度算法。

每個隊列都有優先級，比如前台隊列就比後台隊列要有絕對的優先級，因此隊列間的分配方法：

（1）只有優先級高的隊列為空，才能執行低優先級隊列。

（2）為隊列分配不同權重的CPU時間，優先級高的分配時間多。

6.多級反饋隊列 搶占式

動態調整進程，進程在不同隊列之間移動，雖然在隊列間移動需要耗費資源，但是更合理。按照CPU區間的大小分隊列。進程之間的劃分是按照所花CPU時間劃分，比如隊列0是就緒隊列，且規定一個時間上界，如果一個進程沒能規定時間完成，則被放入隊列1中。CPU區間越大的進程就被放入低優先中。每個進程一開始都進入就緒隊列。

多級反饋隊列的參數：

(1)隊列的數量。

(2)每個隊列的調度算法。

(3)怎樣升級到優先級更高的隊列。

(4)確定怎樣降級到優先級更低的隊列。

(5)進程需要確定進入哪個隊列。

 

多個CPU的負載均衡問題。

假設多個CPU是同構的，但是可能也會有特殊的限制比如只有某個CPU與I/O設備連接。

（1）非對稱多處理：一個處理器專門用於CPU調度決定等，其他用於執行用戶代碼。

（2）對稱多處理（SMP）：為每個處理器自我調度，可能會造成多個處理器同時訪問同一個數據結構則會造成沖突。

處理器親和性：一個進程只需要在一個處理器上執行即可，不會轉到另一個處理器上執行，因為如果轉移的話，處理器緩存的資源全部無效，浪費。緩存存儲的是進程的連續訪問的數據。

軟親和性：占時的不會轉移。

硬親和性：操作系統不允許進程在多處理器間游走。

負載平衡條件：每個處理器都有私有的就緒隊列。

負載平衡方法：push和pull。即從負載高的處理器push到低負載的處理上，從負載低的處理器pull到負載高的處理器，但是這樣就缺失了處理器親和性。

一個物理處理器可以劃分為邏輯處理器，SMT（對稱多線程）使得在一個物理處理器上同時運行多個線程。邏輯處理器對於物理處理器就像線程對進程。多個邏輯處理器共享物理處理器的資源，如緩存和總線。

舉個例子，就像分區一樣，硬盤分為C盤，D盤等，但事實上不是真的分硬盤。更理論的講,像數據庫的邏輯和物理關系。系統調度的是內核線程，用戶線程由線程庫管理。如果線程要在CPU上運行，需要與某個內核線程相連。

用戶線程需要連接到LWP（進程競爭范圍PCS）。

內核線程連接到物理CPU（系統競爭范圍SCS）。

linux采用搶占、優先級的調度算法，較高優先級的進程被分配較多的CPU時間片。每個處理器都維護一個運行隊列。運行隊列分為活動和到期的，前者是進程所耗時間小於時間片的，後者是所花時間大於時間片的任務。

當活動隊列為空，則互換兩隊列。

 

調度算法的評估：

1.分析評估法。事先確定負荷和算法，即一些本來可以自己設定的數據，比如確定特定算法FCFS，確定進程到來的時間和數量；根據不同的模型來比較性能。缺點是只適用於特定的情況。

2.排隊模型。數學公式以分析CPU和I/O的區間分布，給定進程到達系統的時間分布，排隊網絡分析。LITTLE公式：進入隊列的進程和離開隊列的進程要相等。

3.模擬。建模計算機系統，模擬程序，根據概率分布隨機生成數據，不能對於前後事件進行預測。但是通過跟蹤磁帶來記錄真實系統的運作，再來按照這種順序來模擬即可。

4.實現。編程後放入操作系統，觀測。