1、第二章 處理器管理2.1 多道程序設計首先描述程序的順序和并發(fā)執(zhí)行方式2.1.1 程序的順序執(zhí)行 一個程序由假設干個程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。2.1.1 程序的順序執(zhí)行例：討論單道系統(tǒng)的工作情況 對用戶作業(yè)的處理 首先輸入用戶的程序和數據 然后進行計算 最后打印計算結果 即有三個順序執(zhí)行的操作 I：輸入操作 C：計算操作 P：輸出操作P2C2 I2P1C1 I1輸入機CPU打印機2.1 多道程序設計2.1.2 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行例： 在系統(tǒng)中有n個作業(yè)，每個作業(yè)都有三個處理步驟，輸入數據、處理、輸出，即Ii,Ci,Pi (i=

2、1,2,3,.,n)。 這些作業(yè)系統(tǒng)中執(zhí)行時是對時間的偏序，有些操作必須在其它操作之前執(zhí)行，這是有序的，但有些操作是可以同時執(zhí)行的。2.1.2 程序的并發(fā)執(zhí)行 I1 I2 I3 I4C1C3C2P1P2例如: I1、C1、P1的執(zhí)行必須嚴格按照I1，C1，P1的順序，而P1與I2，C1與I2，I3與P1是可以同時執(zhí)行的。.2.1.3 多道程序設計P152.2 進程的概念 操作系統(tǒng)的特性之一是并發(fā)與共享，即在系統(tǒng)中內存同時存在幾個相互獨立的程序，這些程序在系統(tǒng)中既交叉地運行，又要共享系統(tǒng)中的資源，這就會引起一系列的問題，包括：對資源的競爭、運行程序之間的通信、程序之間的合作與協(xié)同等符。 要解決這

3、些問題，用程序的概念已經不能描述程序在內存中運行的狀態(tài)，必須引入新的概念進程2.2.1 進程的定義行為的一個規(guī)那么叫做程序，程序在處理機上執(zhí)行時所發(fā)生的活動稱為進程Dijkstra)。進程是這樣的計算局部，它是可以和其它計算并行的一個計算。(Donovan)進程有時稱為任務是一個程序與其數據一道通過處理機的執(zhí)行所發(fā)生的活動。Alan.C. Shaw)進程是執(zhí)行中的程序。Ken Thompson and Dennis Ritchie )進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調度的一個獨立單位。 進程的定義：把一個程序在一個數據集上的一次執(zhí)行 稱為一個進程process)。2.2.2 為什

4、么要引入進程提高資源利用率正確描述程序的執(zhí)行情況2.2.3 進程的屬性1.進程是動態(tài)的，它包含了數據和運行在數據集上的程序2.多個進程可以含有相同的程序3.多個進程可以并發(fā)執(zhí)行4.進程有三種根本狀態(tài)2.2.3 進程的屬性4. 進程的三種根本狀態(tài)(1)就緒狀態(tài)(Ready) 進程已獲得除CPU之外的所有必需的資源，一旦得到CPU控制權，立即可以運行。(2)運行狀態(tài)(Running) 該進程已獲得運行所必需的資源，它的程序正在處理機上執(zhí)行。 (3)等待阻塞狀態(tài)(Waiting,Blocked) 正在執(zhí)行的進程由于發(fā)生某事件而暫時無法執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，那么稱該進程處于阻塞狀態(tài)或等待

5、狀態(tài)。就緒隊列與阻塞隊列2.2.3 進程的屬性執(zhí) 行阻 塞就 緒時間片完I/O請求進程調度I/O完成進程的三種根本狀態(tài)以及各狀態(tài)之間的轉換關系2.2.3 進程的屬性進程的特征進程的特征CPB據數段程序段進程實體動態(tài)性-最根本特征進程：進程實體的一次執(zhí)行過程，有生命周期。程序：程序是一組有序指令的集合，是靜態(tài)的概念。 并發(fā)性異步性多個進程實體同存于內存中，在一段時間內同時運行 程序不能并發(fā)執(zhí)行進程按各自獨立的、不可預知的速度向前推進2.3 進程控制塊1. 進程控制塊的作用 存放進程的管理和控制信息的數據結構稱為進程控制塊。它是進程管理和控制的最重要的數據結構，在創(chuàng)立時，建立PCB，并伴隨進程運行

6、的全過程，直到進程撤消而撤消。PCB就象我們的戶口。 進程控制塊是進程存在的唯一標志。 系統(tǒng)的所有PCB組織成鏈表或隊列，常駐內存的PCB區(qū)。2.3 進程控制塊2. 進程控制塊中的信息1) 進程標示符 每個進程都必須有一個唯一的標識符內部標示符外部標示符2) 處理機狀態(tài) 處理機狀態(tài)信息主要由處理機的各種存放器中的內容組成。處理機運行時的信息存放在存放器中，當被中斷時這些信息要存放在PCB中。唯一的數字標識符用戶（進程）訪問該進程使用通用存放器 指令計數器程序狀態(tài)字PSW 用戶棧指針2.3 進程控制塊3) 進程調度信息進程狀態(tài)進程優(yōu)先級進程調度所需的其他信息事件4) 進程控制信息程序和數據的地址

7、進程通信和同步機制資源清單鏈接指針進程控制P21 對系統(tǒng)中的全部進程實施有效的管理，負責進程狀態(tài)的改變。進程的創(chuàng)立1. 進程圖 描述進程的家族關系的有向樹 進程Pi創(chuàng)立了進程Pj，那么Pi是Pj的父進程， Pj是Pi的子進程，用一條由進程Pi指向進程Pj的有向邊來描述。 創(chuàng)立父進程的進程為祖進程，由此形成進程樹，樹根為進程家族的祖先。ABDKEFLMJIHGC內核完成進程控制2. 引起創(chuàng)立進程的事件3. 進程的創(chuàng)立用戶登錄提供服務作業(yè)調度應用請求在多道程序環(huán)境中，只有進程才能在系統(tǒng)中運行。操作系統(tǒng)發(fā)現要求創(chuàng)立新進程的事件后，調用進程創(chuàng)立原語Creat()創(chuàng)立新進程。創(chuàng)立過程(1) 申請空白PC

8、B(2) 為新進程分配資源(3) 初始化進程控制塊(4) 將新進程插入就緒隊列進程控制進程的撤銷1. 引起進程終止的事件正常結束異常結束外界干預越界錯誤、保護錯、非法指令、特權指令錯、運行超時、等待超時、算術運算錯、I/O故障操作員或操作系統(tǒng)干預父進程請求父進程中止2. 進程的終止過程(1) 根據被終止進程的標示符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態(tài)。(2) 假設被終止進程正處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行，置調度標志為真，用于指示該進程被終止后應重新進行調度。(3) 假設該進程有子孫進程，應將其所有子孫進程予以終止，以防他們成為不可控的進程。(4) 將被終止進程所擁

9、有的全部資源，或歸還其父進程，或歸還系統(tǒng)。(5) 將被終止進程的PCB從所在隊列或鏈表中移出，等待其他程序搜索信息。進程控制進程的阻塞與喚醒1. 引起進程阻塞和喚醒的事件1) 請求系統(tǒng)服務2) 啟動某種操作3) 新數據尚未到達4) 無新工作可做2. 進程阻塞過程調用阻塞原語BLOCK()阻塞自己中止調用進程的執(zhí)行，將PCB中的狀態(tài)改為阻塞，并參加到阻塞隊列中；最后轉進程調度。3. 進程喚醒過程阻塞進程等待的事件發(fā)生，有關進程調用喚醒原語WAKEUP()把等待該事件的進程喚醒。 喚醒原語的執(zhí)行：把阻塞進程從等待該事件的阻塞隊列中移出，將其PCB中的現行狀態(tài)改為就緒，將PCB插入到就緒隊列中阻塞原

10、語與喚醒原語作用相反，成對使用2.4 進程隊列進程控制塊的組織方式1) 鏈接方式把具有統(tǒng)一狀態(tài)的PCB用其中的鏈接字鏈接成一個隊列。就緒隊列 假設干個阻塞隊列 空白隊列 2) 索引方式系統(tǒng)根據所有進程的狀態(tài)建立幾張索引表，把各表的內存首地址記錄在內存的專用單元中。索引表的表目中記錄了相應狀態(tài)的某個PCB在PCB表中的地址。 1 PCB9 0 PCB8 9 PCB7 7 PCB6 PCB5 8 PCB4 0 PCB3 3 PCB2 4 PCB1就緒隊列指針阻塞隊列指針空閑隊列指針執(zhí)行指針鏈接方式：PCB7PCB6PCB5PCB4PCB3PCB2PCB1執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索

11、引表索引方式：2.5 中斷和中斷處理2.5.1 中斷2.5.2 中斷類型中斷響應中斷處理2.5.1 中斷由于某些事件的出現，中止現行進程的運行，而由操作系統(tǒng)去處理出現的事件，待適當的時候讓被中止的進程繼續(xù)運行，這個過程稱為中斷。引起中斷的事件稱為中斷源。對出現的事件進行處理的程序稱為中斷處理程序。2.5.2 中斷類型1硬件故障中斷2程序中斷3外部中斷4輸入/輸出中斷5訪管中斷強迫性中斷事件自愿性中斷事件中斷響應P24硬件故障中斷程序中斷外部事件輸入/輸出事件訪管中斷事件當前PSW舊 PSW硬件故障中斷程序中斷外部事件輸入/輸出事件訪管中斷事件新 PSW中斷處理P251硬件故障中斷事件的處理-?

12、人工干預，輸出故障信息。2程序中斷事件的處理-?轉交用戶自行處理3外部中斷事件的處理-?例行程序4輸入/輸出中斷事件的處理-?IO正常結束、IO異常結束5訪管中斷事件的處理-?系統(tǒng)功能調用2.6 處理器調度P26在多道程序環(huán)境下，進程數目往往多于處理機數目。這就要求系統(tǒng)能夠按某種算法，動態(tài)的把處理機分配給就緒隊列中的一個進程，使之執(zhí)行。分配處理機的任務是由處理機調度程序完成的。由于處理機是最重要的計算機資源，提高處理機的利用率及改善系統(tǒng)性能，在很大程度上取決于處理機調度的性能。因此，處理機調度便成為OS設計的中心問題之一。高級、中級和低級調度 一個批處理型作業(yè)，從進入系統(tǒng)并駐留在外存的后備隊列

13、上開始，直至作業(yè)運行完畢，可能要經歷下述三級調度。高級調度High Scheduling 又稱為作業(yè)調度或長程調度Long-Term Scheduling，用于決定把外存上處于后備隊列中的哪些作業(yè)調入內存，并為它們創(chuàng)立進程、分配必要的資源，然后，再將新創(chuàng)立的進程排在就緒隊列上，準備執(zhí)行。因此有時也稱作業(yè)調度為接納調度Admission Scheduling。高級調度High Scheduling作業(yè)作業(yè)步典型的作業(yè)可分成三個作業(yè)步：編譯-鏈接裝配-運行作業(yè)流后備隊列作業(yè)控制塊JCB(job control block)高級調度High Scheduling 在批處理系統(tǒng)中，因作業(yè)進入系統(tǒng)后先駐

14、留在外存，故需要有作業(yè)調度。在分時系統(tǒng)中為做到及時響應，作業(yè)被直接送入內存，故不需作業(yè)調度。在實時系統(tǒng)中，通常也不需作業(yè)調度。高級調度作業(yè)調度在每次執(zhí)行作業(yè)調度時，都須作出兩個決定：接納多少作業(yè)每次接納多少作業(yè)進入內存，取決于多道程序度，即允許多少個作業(yè)同時在內存中運行。多道程序度確實定應根據系統(tǒng)的規(guī)模和運行速度等情況綜合考慮。接納哪些作業(yè)應接納哪些作業(yè)從外存調入內存，取決于所采用的調度算法。如先來先效勞，短作業(yè)優(yōu)先等。低級調度Low Level Scheduling 通常也稱為進程調度或短程調度Short-Term Scheduling，用來決定就緒隊列中的哪個進程應獲得處理機，然后再由分派

15、程序把處理機分配給該進程。進程調度是最根本的一種調度，在三種OS中都有。低級調度的功能1保存處理機的現場信息。2按某種算法選取進程3把處理器分配給進程進程調度的三個根本機制1排隊器2分派器分派程序3上下文切換機制低級調度Low Level Scheduling搶占方式Preemptive Mode 這種調度方式允許調度程序根據某種原那么，去暫停某個正在執(zhí)行的進程，將以分配給該進程的處理機重新分配給另一進程。搶占的原那么有：優(yōu)先權原那么。優(yōu)先權高的可以搶占優(yōu)先級低的進程的處理機。短作業(yè)進程優(yōu)先原那么。短作業(yè)進程可以搶占長作業(yè)進程的處理機。時間片原那么。各進程按時間片運行，一個時間片用完時，停止該

16、進程執(zhí)行重新進行調度。中級調度Intermediate-Level Scheduling 中級調度又稱中程調度Medium-Term Scheduling引入中級調度的目的，是為了提高內存利用率和系統(tǒng)吞吐量。為此，應使那些暫時不能運行的進程不再占用珍貴的內存資源，而將它們調之外存去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件、且內存又稍有空閑時，由中級調度來決定把外存上的哪些又具備運行條件的就緒進程，重新調入內存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調度。中級調度實際上就是存儲器管理中的對換功能。具有高級和低級調度的調度隊列模型 在批處理系統(tǒng)中，不僅

17、需要進程調度，而且還需要作業(yè)調度，由后者按一定的作業(yè)調度算法，從外存的后備隊列中選擇一批作業(yè)調入內存，并為它們建立進程，送入就緒隊列，然后才由進程調度算法按照一定的進程調度算法，選擇一個進程，把處理機分配給該進程。以下圖示出具有高、低兩級調度的調度隊列模型。具有高級和低級調度的調度隊列模型CPU就 緒 隊 列時間片完進程調度等待事件1進程完成后備隊列等待事件2等待事件n事件1出現事件2出現事件n出現作業(yè)調度具有高級和低級調度的調度隊列模型 具有上下兩級調度的調度模型與僅有進程調度的調度模型的主要區(qū)別在于：就緒隊列的形式。在批處理系統(tǒng)中，最常用的是最高優(yōu)先權優(yōu)先調度算法，因此最常用的就緒隊列形式

18、是優(yōu)先權隊列。設置多個阻塞隊列。對于小型系統(tǒng)可只設置一個，但對于較大系統(tǒng)要設置多個阻塞隊列以保證效率。每個隊列對應于某一種進程阻塞事件。2.6.1 處理器的兩級調度P26作業(yè)調度進程調度2.6.2 作業(yè)調度算法設計調度算法的原那么：公平性平衡資源使用極大地流量選擇調度方式和調度算法的假設干準那么 在一個OS的設計中，應如何選擇調度方式和算法，很大程度上取決于OS的類型和目標。如在批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)中，通常都采用不同的調度方式和算法。選擇的準那么，有的是面向用戶的，有的是面向系統(tǒng)的。面向用戶的準那么周轉時間短 周轉時間 平均周轉時間 帶權周轉時間 平均帶權周轉時間響應時間快 響應時間

19、截止時間的保證 截止時間優(yōu)先權準那么評價批處理系統(tǒng)的性能、選擇作業(yè)調度方式與算法的重要準那么之一。從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。作業(yè)的周轉時間與系統(tǒng)為他提供效勞的時間之比評價分時系統(tǒng)的性能、選擇進程調度算法的重要準那么之一。提交請求到顯示結果評價實時系統(tǒng)的性能、選擇實時調度算法的重要準那么。面向系統(tǒng)的準那么系統(tǒng)吞吐量高處理機利用率好各類資源的平衡利用評價批處理系統(tǒng)的性能的另一個重要指標、選擇批處理作業(yè)調度的重要準那么。單位時間內系統(tǒng)所完成的作業(yè)數衡量系統(tǒng)性能的十分重要的指標1、先來先效勞算法 FCFS是一種最簡單的調度算法。當在作業(yè)調度中采用該算法時，每次調度都是從后備

20、作業(yè)隊列中，選擇一個或多個最先進入該隊列的作業(yè)，將它們調入內存，為它們分配資源、創(chuàng)立進程，然后放入就緒隊列。先來先效勞算法例題P28作業(yè)名進入輸入井時間需計算時間主存量要求A10.1時42分鐘15KB10.3時30分鐘60KC10.5時24分鐘50KD10.6時24分鐘10KE10.7時12分鐘20K主存空間為100K作業(yè)名裝入主存時間開始執(zhí)行時間執(zhí)行結束時間周轉時間A10.1時10.1時10.8時0.7小時B10.3時10.8時11.3時1.0小時C11.3時11.7時12.1時1.6小時D10.6時11.3時11.7時1.1小時E11.3時12.1時12.3時1.6小時先來先效勞算法平均周

21、轉時間=1.2作業(yè)名進入輸入井時間需計算時間主存量要求A10.1時42分鐘15KB10.3時30分鐘60KC10.5時24分鐘50KD10.6時24分鐘10KE10.7時12分鐘20K2、計算時間短的作業(yè)優(yōu)先算法短作業(yè)優(yōu)先SJF的調度算法，是從后備隊列中選擇一個或假設干個估計運行時間最短的作業(yè)，將它們調入內存運行。進程調度仍按裝入的次序讓它們依次占用處理器。作業(yè)名裝入主存時間開始執(zhí)行時間執(zhí)行結束時間周轉時間A10.1時10.1時10.8時0.7小時B10.3時10.8時11.3時1.0小時C11.3時11.9時12.3時1.8小時D10.6時11.3時11.7時1.1小時E11.3時11.7時

22、11.9時1.2小時計算時間短作業(yè)優(yōu)先算法平均周轉時間=1.16作業(yè)名進入輸入井時間需計算時間主存量要求A10.1時42分鐘15KB10.3時30分鐘60KC10.5時24分鐘50KD10.6時24分鐘10KE10.7時12分鐘20KP30SJF調度算法的優(yōu)缺點：優(yōu)點：有效降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。缺點：1.對長作業(yè)不利。2.該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)進程會被及時處理。3.由于作業(yè)進程的長短含主觀因素，不一定能真正做到短作業(yè)優(yōu)先。3、響應比高者優(yōu)先算法響應比=等待時間、計算時間調度在全部作業(yè)到達輸入井之后開始作業(yè)名進入輸入井時間需計算時間A8：501.

23、5小時B9：000.4小時C9：301.0小時時間A響應比B響應比C響應比9:3040/9030/240/609：5464/9024/604、 優(yōu)先級調度算法確定進程優(yōu)先權的依據有如下三個方面：進程類型：一般來說系統(tǒng)進程高于用戶進程。進程對資源的需求：如進程的估計時間及內存需要量的多少，對要求少的進程賦予較高優(yōu)先權。用戶要求：由用戶進程的緊迫程度及用戶所付費用的多少來確定優(yōu)先權的。5、均衡調度算法P31)2.6 進程調度算法P31)引起進程切換的原因：1一個進程從運行狀態(tài)變成等待狀態(tài)2一個進程從運行狀態(tài)變成就緒狀態(tài)3一個進程從等待狀態(tài)變成就緒狀態(tài)4一個進程完成工作后撤銷調度算法： P31-32

24、1 先來先效勞調度算法2 最高優(yōu)先級優(yōu)先調度算法3 時間片輪轉調度算法調度算法例題在單CPU和兩臺輸入/輸出設備I1,I2)的多道程序設計環(huán)境下，同時投入3個作業(yè)JOB1,JOB2,JOB3運行。這3個作業(yè)對CPU和輸入/輸出設備的使用順序和時間如下所示：JOB1:I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms)JOB2:I1(20ms);CPU(20ms);I2(40ms)JOB3:CPU(30ms);I1(20ms);CPU(10ms);I1(10ms)假定CPU，I1，I2都能并行工作，JOB1優(yōu)先級最高，JOB2次之，JOB3優(yōu)先級最低，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU但不搶占I1和I2。試求：13個作業(yè)從投入到完成分別需要的時間；2從投入到完成的CPU的利用率；3I/O設備利用率。調度算法例題JOB1從投入到運行完成需要110ms, JOB2從投入到運行完成需要90ms, JOB3從投入到運行完成需要110ms.Cpu利用率： 110-30/110=72.7%I1的利用率： 110-30/110=72.7%I2的利用率： 110-20/110=81