處理機調度

1.處理機調度的功能

一般情況下，當佔用處理機的進程因為某種請求得不到滿足而不得不放棄CPU進入等待狀態時，或者當時間片到，系統不得不將CPU分配給就緒隊列中另一進程的時候，都要引起處理機調度。除此之外，進程正常結束、中斷處理等也可能引起處理機的調度。因此，處理機調度是操作系統核心的重要組成部分，它的主要功能如下：

（1）記住進程的狀態，如進程名稱、指令計數器、程序狀態寄存器以及所有通用寄存器等現場信息，將這些信息記錄在相應的進程式控制制塊中。

（2）根據一定的演演算法，決定哪個進程能獲得處理機，以及佔用多長時間。

（3）收回處理機，即正在執行的進程因為時間片用完或因為某種原因不能再執行的時候，保存該進程的現場，並收回處理機。

處理機調度的功能中，很重要的一項就是根據一定演演算法，從就緒隊列中選出一個進程佔用CPU運行。可見，演演算法是處理機調度的關鍵。

2.處理機調度的性能準則

處理機調度，有許多不問的調度演演算法，不同的調度演演算法具有不同的特性。因此，在介紹演演算法之前，先介紹衡量一個演演算法的基本準則。

衡量和比較調度演演算法性能優劣主要有一下幾個因素：

（1）CPU利用率。CPU是計算機系統中最重要的資源，所以應儘可能使CPU保持忙，使這一資源利用率最高。

（2）吞吐量。CPU運行時表示系統正處於工作狀態，工作量的大小是以每單位時間所完成的作業數目來描述的，這就叫吞吐量。

（3）周轉時間。指從作業提交到作業完成所經過的時間，包括作業等待，在就緒隊列中排隊，在處理機上運行以及進行輸入/輸出操作所花時間的總和。

（4）等待時間。處理機調度演演算法實際上並不影響作業執行或輸入/輸出操作的時間，隻影響作業在就緒隊列中等待所花的時間。因此，衡量一個調度演演算法優劣常常簡單的考察等待時間。

（5）響應時間。指從作業提交到系統作出相應所經過的時間。在互動式系統中，作業的周轉時間並不一定是最好的衡量準則，因此，常常使用另一種度量準則，即響應時間。從用戶觀點看，響應時間應該快一點好，但這常常要犧牲系統資源利用率為代價。

3.處理機調度演演算法

1）先來先服調度演演算法（FIFO）

這是最簡單的處理機調度演演算法，其基本思想是按照進程進入就緒隊列的先後順序調度並分配處理機執行。先來先服務調度演演算法是一種不可搶佔的演演算法，先進入就緒隊列的進程，先分配處理機運行。一旦一個進程佔有了處理機，它就一直運行下去，直到該進程完成工作或者因為等待某事件發生而不能繼續運行時才釋放處理機。

從表面上看，FIFO演演算法對所有作業都是公平的，並且一個作業的等待時間是可能預先估計的。但實際上這種演演算法是不利於小作業的，因為當一個大作業先進入就緒隊列時，就會使其後的許多小作業等待很長的時間。這對小作業來說，等待時間可能要遠遠超出它運行的時間。

先來先服演演算法簡單，易於程序實現，但它性能較差，在實際運行的操作系統中，很少單獨使用，它常常配合其他調度演演算法一起使用。

2）時間片輪轉調度演演算法（RR）

時間片輪轉調度演演算法的基本思想是：對就緒隊列中的每一進程分配一個時間片，時間片的長度q一般從10ms-1100ms不等。把就緒隊列看成是一個環狀結構，調度程序按時間片長度q輪流調度就緒隊列中的每一進程，使每一進程都有機會獲得相同長度的時間佔用處理機運行。

時間片輪轉調度演演算法在分時系統中，是一種既簡單又有效的調度策略。一個分時系統有許多終端。終端用戶在各自的終端設備上同時使用計算機。如果某個終端用戶的程序長時間地佔用處理機，那麼其他終端用戶的請求就不能得到即時相應。一般說來，終端用戶提出請求后，能在幾秒鐘內得到響應也就感到滿意了。採用時間片輪轉演演算法，可以使系統即時地相應各終端用戶的請求。

時間片輪轉調度演演算法的性能極大的依賴於時間片長度q的取值，如果時間片過大。則RR演演算法就退化為FIFO演演算法了；反之，如果時間片過小，那麼，處理機在各進程之間頻繁轉接，處理機時間開銷變得很大，而提供給用戶程序的時間將大大減少。

3）優先數法

優先數法的基本思想是：對就緒隊列中的每個進程，首先按某種原則定義一個優先數來表示它，處理機調度時，每次選擇就緒隊列中優先數最大者（也可規定優先數愈小，其優先權愈高），讓它佔用處理機運行。

確定優先數一般可以有以下幾種考慮：

（1）頻繁使用外部輸入、輸出設備的進程優先數大。這樣有利於提高CPU使用效率。

（2）重要程序的進程優先數大，怎樣有利於用戶靈活操作。

（3）進入計算機系統時間長的進程優先數大，這樣有利於縮短作業的完成時間。

（4）互動式用戶作業進程優先數大，這樣有利於提高中斷響應時間。

優先數的設置可以採用靜態和動態兩種方式。靜態設置方式就是指系統在建立一個進程時，就按照某種原則為進程制定一個優先數，這個優先數在進程存在期間一直保持不變。而動態設置方式是指系統在進程存在期間經常改變進程的優先數，如何動態的改變進程的優先數，依賴於具體操作系統的設計目標。