第3章處理機管理

學習目標和學習要點3.1作業調度

3.2進程調度3.3調度性能的評價3.4常用調度算法3.5Linux處理機管理

3.6Windows2000/XP處理機管理

本章小結第3章：處理機管理返回到目錄本章學習目標掌握：作業與進程的關系、作業調度策略與算法。

理解：進程調度策略與算法、幾種調度策略的評價。了解：Linux及WindowsXP實例，本章其他內容。

第3章：處理機管理本章學習要點應深入理解、掌握作業調度策略與算法，進程的調度策略、算法及幾種調度策略的評價。

返回到本章第3章：處理機管理3.1作業調度

3.1.1作業狀態

3.1.2調度級別

3.1.3作業調度

返回到本章第3章：處理機管理3.1.1作業狀態

作業在整個活動期間一共有四種狀態：（1）提交狀態——即用戶向系統提交一個作業時，該作業所處的狀態。（2）后備狀態——即用戶作業經輸入設備（如讀卡機）送入輸出設備（磁盤）中存放，等待進入內存時所處的狀況。此時，該作業的數據已轉換成內部的機器可讀的形式，并且作業請求資源等信息也交給了操作系統。（3）執行狀態——即作業分配到所需的資源，被調入內存，并且在處理機（CPU）上執行相應的程序時所處的狀況。此時該作業真正處于活動狀況。（4）完成狀態——即作業完成了計算任務，結果由打印機輸出，最后由系統回收分配給它的全部資源，準備退出系統時的作業狀況。

第3章：處理機管理3.1.1作業狀態作業的四種狀態的轉換以及與各進程狀態之間的關系如圖所示：返回到本節第3章：處理機管理圖3-1

作業的狀態及轉換

3.1.2調度級別

1．調度的層次所謂調度就是選出待分派的作業或進程。處理機調度的主要目的就是為了分配處理機。在不同的操作系統中所采用的調度方式并不完全相同。有的系統中僅采用一級調度，而有的系統采用兩級或三級，并且所用的調度算法也完全可能不同。一般說來，作業從進入系統到最后完成，可能要經歷三級調度：高級調度、中級調度和低級調度。

第3章：處理機管理3.1.2調度級別

（1）高級調度：又稱作業調度或宏觀調度。其主要功能是根據一定的算法，從輸入的一批作業中選出若干個作業，分配必要的資源，如內存、外設等，為它建立相應的用戶作業進程和為其服務的系統進程（如輸入、輸出進程），最后把它們的程序和數據調入內存，等待進程調度程序對其執行調度，并在作業完成后作善后處理工作，回收系統資源。

第3章：處理機管理3.1.2調度級別

（2）中級調度：又稱交換調度。為了使內存中同時存放的進程數目不至于太多，有時就需要把某些進程從內存中移到外存上，以減少多道程序的數目，為此設立了中級調度。特別在采用虛擬存儲技術的系統或分時系統中，往往增加中級調度這一級。所以中級調度的功能是在內存使用情況緊張時，將一些暫時不能運行的進程從內存對換到外存上等待。當以后內存有足夠的空閑空間時，再將合適的進程重新換入內存，等待進程調度。引入中級調度的主要目的是為了提高內存的利用率和系統吞吐量。它實際上就是存儲器管理中的對換功能。

第3章：處理機管理3.1.2調度級別

（3）低級調度：

又稱進程調度或微觀調度。其主要功能是根據一定的算法將CPU分派給就緒隊列中的一個進程。執行低級調度功能的程序稱作進程調度程序，由它實現CPU在進程間的切換。進程調度的運行頻率很高，在分時系統中往往幾十毫秒就要運行一次。進程調度是操作系統中最基本的一種調度。在一般類型的操作系統中都必須有進程調度，而且它的策略的優劣直接影響整個系統的計能。

第3章：處理機管理3.1.2調度級別

2．作業和進程的關系作業可被看作是用戶對象計算機提交任務的任務實體。例如一次計算、一個控制過程等。反過來，進程則是計算機為了完成用戶任務實體而設置的執行實體，是系統分配資源的基本單位。顯然，計算機要完成一個任務實體，必須要有一個以上的執行實體，也就是說，一個作業總是由一個以上的多個進程組成的。那么，作業怎樣分解為進程呢？首先，系統必須為一個作業創建一個根進程，然后，在執行作業控制語句時，根據任務要求，系統或根進程為其創建相應的子進程，然后，為各子進程分配資源和調度各子進程執行以完成作業要求的任務。

返回到本節第3章：處理機管理3.1.3作業調度

1．作業控制塊（JCB）每個作業進入系統時由系統為其建立JCB（JobControlBlock，作業控制塊）。作業存在的整個過程中，相應的JCB也存在，只有當作業退出系統時，JCB才被撤銷。因此，JCB是一個作業存在的標志。每個JCB記錄了與該作業有關的信息，而具體的內容根據作業調度的要求而定。對于不同的系統，其JCB內容也有所不同。表3-1列出了JCB的主要內容，包括作業名字、作業類型、作業狀態、該作業對系統資源的要求、該作業對已分配給它的資源的使用情況以及作業的優先級別等。第3章：處理機管理3.1.3作業調度第3章：處理機管理3.1.3作業調度第3章：處理機管理

2．作業調度的功能

作業調度的主要任務是完成作業從后備狀態到執行狀態和從執行狀態到完成狀態的轉換。具體來說，通常作業調度程序要完成以下工作（這就是作業調度的功能）。3.1.3作業調度第3章：處理機管理（1）確定數據結構系統為每一個已進入系統的作業分配一個作業控制塊JCB。作業控制塊記錄了每個作業在各階段的情況（包括分配的資源和狀態等），作業調度程序就是憑據各個作業的JCB提供的信息對作業進行調度和管理的。

3.1.3作業調度第3章：處理機管理（2）確定調度算法

按一定的調度算法，從磁盤中存放的大量作業（后備作業隊列）中挑選一個或幾個作業投入運行。即讓這些作業由后備狀態轉變為執行狀態。這一工作由作業調度程序完成，該程序在適當的時候按一定的調度原則從后備作業中挑選出若干個作業投入運行。作業調度程序的調度原則和調度時機通常與系統的設計目標有關，并由許多因素決定。為此，在設計作業調度程序時，必須綜合平衡各種因素，確定出合理的調度算法。

3.1.3作業調度第3章：處理機管理（3）分配資源

為被選中的作業分配運行時所需要的系統資源，如主存和外部設備等。作業調度程序在調度一個作業進入主存時，必須為該作業建立相應的進程，并且為這些進程提供所需的資源。至于處理機這一資源，作業調度程序只保證被選中的作業獲得使用處理機的資格，而對處理機的分配工作則由進程調度程序來完成。

3.1.3作業調度第3章：處理機管理（4）善后處理

在一個作業執行結束時，作業調度程序輸出一些必要的信息（例如執行時間、作業執行情況）等，然后收回該作業所占用的全部資源，撤銷與該作業有關的全部進程和該作業的作業控制塊。

返回到本節3.2進程調度

1．進程調度的功能和時機

2．調度方式

返回到本章第3章：處理機管理1．進程調度的功能和時機在多道程序系統中，用戶進程數往往多于處理機數，這將使它們相互爭奪處理機。此外，系統進程同樣需要使用處理機。這樣，就需要按一定的策略，動態地把處理機分配給就緒隊列中某一進程，以便使之執行。該任務是由進程調度來完成的。進程調度的具體功能如下述.

第3章：處理機管理1．進程調度的功能和時機（1）記錄和保持系統中所有進程的有關情況和狀態特征記錄和保持系統中所有進程的有關情況和狀態特征是通過對進程控制塊(PCB)的內容作相應的登記、修改，以及將PCB在不同的隊列中轉接而實現的，并由進程管理模塊（如進程創建、進程撤銷、進程通信等功能模塊）來實施。進程在活動期間其狀態是可以改變的，如由運行→等待，由等待→就緒，由就緒→運行。相應地，該進程的PCB就在運行指針、各種等待隊列和就緒隊列之間轉換。進程進入就緒隊列的排序原則體現了調度思想。

第3章：處理機管理1．進程調度的功能和時機

（2）決定分配策略

在處理機空閑時，根據一定的原則選擇一個進程去運行，同時確定獲得處理機的時間。分配策略實際上是由隊列排序原則體現的。若按優先調度原則，則進程就緒隊列按優先級高低排序；若按先來先服務原則，則按進程來到的先后次序排序。當處理機空閑時，只要選擇隊首元素就一定滿足確定的調度原則。

第3章：處理機管理1．進程調度的功能和時機

（3）實施處理機的分配和回收

當正在運行的進程由于某種原因要讓出處理機時，應將該進程的狀態該為“等待”，并插入到相應隊列中，還必須保留該進程的處理現場。

第3章：處理機管理1．進程調度的功能和時機調度時機：①進程完成其任務時。②在一次管理程序調用之后，該調用使現行程序暫時不能繼續運行時。③在一次出錯陷入之后，該陷入使現行進程在出錯處理時被掛起時。④在分時系統中，當進程使用完規定的時間片，時鐘中斷使該進程讓出處理機時。⑤在采用可剝奪調度方式的系統中，當具有更高優先級的進程要求處理機時。

返回到本節第3章：處理機管理2．調度方式通常有兩種進程調度方式：一種是仍然讓正在執行的進程繼續執行，直到該進程完成或發生某事件（如提出I/O請求）而進入“完成”或“等待”狀態時，才把處理機分配給“重要而緊迫”的進程，以使之執行。這種進程調度方式稱為非剝奪方式。另一種方式則是“重要而緊迫”的進程一到，便暫停正在執行的進程，立即把處理機分配給它。這種方式稱為剝奪調度方式。

返回到本節第3章：處理機管理3.3調度性能的評價

1．選擇調度算法時應考慮的因素

2．調度性能評價準則

返回到本章第3章：處理機管理1．選擇調度算法時應考慮的因素（1）所用算法應保證實現系統的設計目標。（2）對所有作業或進程應公平對待，使每個進程能公平地共享CPU。（3）均衡使用資源，盡量使系統中各種資源都同時得到利用，提高資源的利用率。（4）兼顧響應時間和資源利用率。各用戶由鍵盤輸入命令后，應在很短的時間內得到響應。這一點對分時系統尤為重要。（5）基于相對優先級，但避免無限延期。隨著等待時間的延長，低優先級進程的優先級應得到提升。（6）系統開銷不應太大。

返回到本節第3章：處理機管理2．調度性能評價準則（1）CPU利用率

當CPU的價格非常昂貴的時候，我們希望盡可能使它得到充分利用。CPU的利用率可從0％到100％。在實際的系統中，一般

CPU的利用率從40％（輕負荷系統）至90％（重負荷系統）。通常，在一定的I/O等待時間的百分比之下，運行程序道數越多，CPU空閑時間的百分比越低。

第3章：處理機管理2．調度性能評價準則（2）吞吐量

它表示單位時間內CPU完成作業的數量。對長作業來說，吞吐量可能是每小時一個作業；而對于短作業處理，它可以達到每秒10個作業。

第3章：處理機管理2．調度性能評價準則（3）周轉時間作業調度的功能是以一定的策略從后備作業隊列中選擇作業進入主存，使其投入運行。其關鍵是要確定作業調度算法。通常，采用平均周轉時間和平均周轉時間和平均帶權周轉時間來衡量作業調度算法性能的好壞。第3章：處理機管理2．調度性能評價準則（4）就緒等待時間

CPU調度算法并不真正影響作業執行或I/O操作的時間數量。各種CPU調度算法影響作業（進程）在就緒隊列中所花費的時間數量。

第3章：處理機管理2．調度性能評價準則（5）響應時間在交互系統中，周轉時間不可能是最好的評價準則。一個進程往往可以很早地就產生某些輸出，當前面的結果在終端上輸出時它可以繼續計算新的結果。于是，有另一個評價準則，就是從提交第一個請求到產生第一個響應所用的時間——響應時間。它是剛開始響應的時間，而不是用于輸出響應的時間。

第3章：處理機管理返回到本節3.4常用調度算法

3.4.1先來先服務法

3.4.2時間片輪轉法

3.4.3優先級法3.4.4其他算法簡介

返回到本章第3章：處理機管理3.4.1先來先服務法

對于作業調度來說，按照先來先服務法，是每次調度從后備作業隊列（按進入時間先后為序）中選擇隊列一個或幾個作業，把它們調入內存，分配相應的資源，創建進程，然后把進程放入就緒隊列。對于進程調度算法來說，采用先來先服務法，就是每次調度從就緒隊列中選擇一個最先進入該隊列的進程，把CPU分給它，令其投入運行。該進程一直運行下去，直至完成或者由于某些原因而阻塞，才放棄CPU。

第3章：處理機管理3.4.1先來先服務法

返回到本節第3章：處理機管理FCFS調度算法容易實現，但它的效率較低。

3.4.2時間片輪轉法常用于分時系統中，系統把所有就緒進程按先進先出的規則排成一個隊列，并選取隊列中的第一個進程投入運行，系統同時規定—個固定的時間單位（即時間片，如100ms），當進程運行完—個時間片時，調度程序便將其送至就緒隊列末尾，重新把CPU分配給隊列的下一個進程，如此重復，使就緒隊列中的所有進程，依次輪流獲得一個時間片的運行時間。第3章：處理機管理3.4.2時間片輪轉法對于時間片輪轉法，需要解決的主要問題：一是解決進程運行時間片的計時，系統中通常設計一個計時器，用于自動計算進程的運行時間；二是如何確定時間片的長度，時間片太長，輪轉法則退化成先來先服務（FCFS）算法了，時間片太短，則增加了進程調度的開銷。第3章：處理機管理3.4.2時間片輪轉法下面舉一個例子予以說明。例如：假設就緒狀態有四個進程，每個進程所需運行時間分別是：6、3、1、7。進程到達次序為1，2，3，4。試分析按FCFS法和時間片輪轉法（時間片分別為1，3）給出進程調度順序，并計算平均等待時間。第3章：處理機管理3.4.2時間片輪轉法①FCFS進程調度順序為圖3-2所示。這里Pi（i＝1，2，3，4）表示進程，以下同。圖3-2 FCFS法平均等待時間：T＝(1/4)*(0+6+9+10)＝6.25第3章：處理機管理3.4.2時間片輪轉法②時間片輪轉法時間片為1進程調度順序為圖3-3所示。圖3-3 時間片為1的輪轉法進程調度順序示意圖平均等待時間：T=(1/4)*((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1))＝(l/4)*(9+6+2+10)＝6.75第3章：處理機管理返回到本節3.4.3優先級法第3章：處理機管理利用優先級調度算法進行進程調度時，是從就緒隊列中選出優先級最高的進程，把CPU分給它使用。

有兩種不同的處理方式：（1）非搶占式優先級法。這種辦法就是“你打完電話，他再打電話”。也就是說，當前占用CPU的進程一直運行下去，直到完成任務或者因等待某事件而主動讓出CPU時，系統才讓另一個優先級高的進程占用CPU。（2）搶占式優先級法。這種辦法就是“不等你說完，接過話筒就打電話”。也就是說，當前進程在運行過程中，一旦有另一個優先級更高的進程出現在就緒隊列中，進程調度程序就停止當前進程的運行，強行將CPU分給那個進程。

3.4.3優先級法第3章：處理機管理返回到本節

進程的優先級是“一定終身”，還是“隨機應變”？這涉及兩種確定進程優先級的方式：靜態方式和動態方式。（1）靜態優先級是在創建進程時就確定下來的，而且在進程的整個運行期間保證不變。往往利用上述的內部定義或外部指定的辦法規定進程的靜態優先級。

（2）動態優先級是隨著進程的推進而不斷改變的。

3.4.4其他算法簡介第3章：處理機管理返回到本節1．短作業優先法

2．多級隊列法

3．多級反饋隊列調度算法

3-5多級反饋隊列

3.5Linux處理機管理

3.5.1Linux進程調度機制

3.5.2Linux進程調度的實現

3.5.3作業級用戶接口

返回到本章第3章：處理機管理3.5.1Linux進程調度機制第3章：處理機管理

1．Linux調度方式

Linux內核的調度方式基本上采用“搶占式優先級”方式，即當進程在用戶態運行時，不管是否自愿，在一定條件下（如時間片用完或等待I/O），核心就可以暫時剝奪其運行狀態而調度其他進程進入運行。但是，一旦進程切換到核心態運行，就不受以上限制而一直運行下去，直至又回到用戶態前才會發生進程調度。

Linux系統中的調度策略基本上是以優先級為基礎的調度策略

3.5.1Linux進程調度機制第3章：處理機管理

2．調度時機

Linux系統中沒有設置專門的調度進程，在需要調度的時候，調用一個特定的調度函數來完成調度功能。一般來講，Linux系統中進程調度發生的時機有下面幾種：（1）用戶利用系統提供的函數調用創建一個新的進程時；。（2）進程等待某個事件發生時；

（3）對于分時系統，每個進程執行完自己的時間片時；。（4）進程進行系統調用時，由用戶態轉為核心態，當系統調用完畢，進程從核心態回到用戶態時，將會調用調度函數，發生進程調度。

3.5.1Linux進程調度機制第3章：處理機管理返回到本節

3．調度策略

Linux針對不同類別的進程提供了三種不同的調度策略，即基于動態優先級的輪轉法（SCHED-RR）、先進先出算法（SCHED-FIFO）、基于動態優先級的輪轉法（SCHED-OTHER）。

3.5.2Linux進程調度的實現第3章：處理機管理

1．Run_queue隊列

Linux進程調度的任務是在run_queue隊列中選出一個就緒進程在處理機上運行。Linux的run_queue隊列包含了系統中所有處于可運行狀態的進程，它是通過task_struct結構的兩個指針next_run和prev_run連接形成雙向循環隊列，見圖3-6。

圖3-6

run_queue隊列

3.5.2Linux進程調度的實現第3章：處理機管理返回到本節

2．Schedule()函數

Schedule()函數在系統中被頻繁調用，該函數被調用的時機有：（1）進程狀態轉換的時刻；（2）可運行進程隊列中新增加一個進程時；（3）當前進程的時間片用完時；（4）進程從系統調用返回到用戶態時；（5）內核處理完中斷后，進程返回到用戶態時。

3.5.3作業級用戶接口第3章：處理機管理1．命令行用戶界面

3.5.3作業級用戶接口第3章：處理機管理

2．shell程序設計

shell除了作為命令行解釋程序外，還是一種高級程序設計語言。可以把多個shell命令放在一個文件中，然后利用標準輸入重定向讓shell從這個文件中讀人命令行依次執行。包含shell命令的文件被稱為shell腳本。shell腳本中可以有變量、關鍵字和if、case、while、for控制語句等。利用shell程序設計語言可以編寫出功能很強但代碼簡單的程序。3.5.3作業級用戶接口第3章：處理機管理

3．圖形用戶界面

Linux除提供命令行界面外，還有圖形用戶界面，如圖3-8所示。

3.5.3作業級用戶接口第3章：處理機管理返回到本節

4．系統調用

Linux的編程接口是系統調用。Linux系統調用符合POSIX的標準，也是一套C語言函數名的集合，因而可實現Linux和UNIX應用程序源代碼的相互移植。在Linux系統中，系統調用像普通C函數調用那樣出現在C程序中。但是，一般的函數調用并不能使進程的狀態從用戶態變為核心態，而系統調用卻可以做到。

3.6Windows2000/XP處理機管理

3.6.1Windows2000/XP任務管理器3.6.2系統性能監視器返回到本章第3章：處理機管理3.6.1Windows2000/XP任務管理器第3章：處理機管理有兩種方法啟動任務管理器：（1）“Ctrl”+“Alt”+“Delete”組合鍵啟動。（2）“Ctrl”+“Shift”+“Esc”組合鍵啟動。啟動后的窗口界面如圖所示。

3.6.1Windows2000/XP任務管理器第3章：處理機管理

1．應用程序在該選項卡內，顯示了當前用戶正在前臺運行的應用程序，以及該應用程序的狀態，一般為正在運行或無反應。通過這里可以查看當前的應用程序，并加以簡單的管理。用鼠標單擊一個應用程序，即可將其選項中，單擊下方的“結束任務”按鈕可以將其關閉。該方法通常在某個應用程序運行出現無反應的情況下強行關閉該應用程序。“切換至”按鈕可轉向被選項中的應用程序，相當于“Alt”+“Tab”組合鍵。而新任務按鈕則是打開一個新的程序。

3.6.1Windows2000/XP任務管理器第3章：處理機管理

2．進程它顯示了當前系統運行的進程，包括用戶進程和系統進程，以及