進程的描述及處理器調度

1、 了解進程的基本概念了解進程的基本概念 熟悉進程的幾種狀態(tài)及轉換原因熟悉進程的幾種狀態(tài)及轉換原因 掌握處理器調度的各種算法掌握處理器調度的各種算法1 1為初始結點，為初始結點，4 4為終止結點為終止結點例：例：1 1表示輸入進程，表示輸入進程，2 2、3 3分別表示乘法、分別表示乘法、 加法運算，加法運算，4 4表示輸出進程表示輸出進程1234 并發(fā)程序設計并發(fā)程序設計/ /順序程序設計順序程序設計 使一個程序分成若干個可同時執(zhí)行的程序模塊的使一個程序分成若干個可同時執(zhí)行的程序模塊的程序設計方法稱為并發(fā)程序設計；相應，串行運程序設計方法稱為并發(fā)程序設計；相應，串行運行程序方法稱為順序程序設計。

2、行程序方法稱為順序程序設計。 特點特點 間斷性：共享資源導致程序間斷性：共享資源導致程序“執(zhí)行執(zhí)行 暫停暫停 執(zhí)執(zhí)行行” 失去封閉性：并發(fā)執(zhí)行以及共享資源可能導致結失去封閉性：并發(fā)執(zhí)行以及共享資源可能導致結果變化果變化 不可再現(xiàn)性：不同次執(zhí)行結果可能不一致不可再現(xiàn)性：不同次執(zhí)行結果可能不一致 程序并發(fā)執(zhí)行的條件程序并發(fā)執(zhí)行的條件 兩段程序間無共享變量或對共享變量僅有讀兩段程序間無共享變量或對共享變量僅有讀 操作操作2.1.2 2.1.2 進程的描述與特點進程的描述與特點 進程的定義進程的定義 一個具有一定獨立功能的程序在一個數(shù)據(jù)集一個具有一定獨立功能的程序在一個數(shù)據(jù)集上的一次執(zhí)行上的一次執(zhí)行

3、一段程序和它執(zhí)行時處理的數(shù)據(jù)一段程序和它執(zhí)行時處理的數(shù)據(jù)1.可與其它程序并發(fā)執(zhí)行的程序的一次執(zhí)行可與其它程序并發(fā)執(zhí)行的程序的一次執(zhí)行例如，某一算題為將一千個字符輸入到緩沖區(qū)，處理后例如，某一算題為將一千個字符輸入到緩沖區(qū)，處理后 輸出到磁帶，按并發(fā)程序設計思路將該算題分成：輸出到磁帶，按并發(fā)程序設計思路將該算題分成： 模塊模塊1 1：循環(huán)執(zhí)行：讀入：循環(huán)執(zhí)行：讀入10001000個字符到輸入緩沖區(qū)；個字符到輸入緩沖區(qū)； 模塊模塊2 2：循環(huán)執(zhí)行：處理輸入緩沖區(qū)中：循環(huán)執(zhí)行：處理輸入緩沖區(qū)中10001000個字符，個字符， 然后將然后將10001000個字符送輸出緩沖區(qū)；個字符送輸出緩沖區(qū)； 模

4、塊模塊3 3：循環(huán)執(zhí)行：取出輸出緩沖區(qū)中：循環(huán)執(zhí)行：取出輸出緩沖區(qū)中10001000個字符寫個字符寫 到磁帶。讓這三個模塊同時并發(fā)進行。到磁帶。讓這三個模塊同時并發(fā)進行。2.2.進程的形成進程的形成 例如：例如：P P為一編譯程序，同時為甲、乙兩程序服為一編譯程序，同時為甲、乙兩程序服 務，假定編譯程序務，假定編譯程序P P從從a a點開始工作，現(xiàn)在正在編點開始工作，現(xiàn)在正在編 譯源程序甲，當工作到譯源程序甲，當工作到b b點時程序點時程序P P等待磁盤傳輸?shù)却疟P傳輸 信息；這時利用處理器讓編譯程序信息；這時利用處理器讓編譯程序P P為源程序乙進為源程序乙進 行編譯，編譯程序仍從行編譯，編譯

5、程序仍從a a點開始。點開始。 雖然編譯程序雖然編譯程序P P只有一個，但是加工對象有甲、只有一個，但是加工對象有甲、乙兩個源程序。如果把編譯程序乙兩個源程序。如果把編譯程序P P與服務對象聯(lián)與服務對象聯(lián)系起來，則程序系起來，則程序P P為甲服務就說構成了進程為甲服務就說構成了進程P P甲，甲，程序程序P P為乙服務就說構成了進程為乙服務就說構成了進程P P乙乙程程序序甲甲程程序序乙乙編譯程序編譯程序ab3.3.進程進程的屬性的屬性結構：結構：同一程序運行在不同數(shù)據(jù)集上時，構成不同的進同一程序運行在不同數(shù)據(jù)集上時，構成不同的進程。它包含了數(shù)據(jù)集和運行在其上的程序及進程控程。它包含了數(shù)據(jù)集和運行

6、在其上的程序及進程控制塊（制塊（PCB）；）；并發(fā)性：并發(fā)性：多個進程可以并發(fā)執(zhí)行，交替執(zhí)行，走走停停，多個進程可以并發(fā)執(zhí)行，交替執(zhí)行，走走停停，即一個進程已開始工作但尚未結束之前，另一個進即一個進程已開始工作但尚未結束之前，另一個進程可以開始工作；程可以開始工作；交往性：交往性： 若干個進程間可以相互交往制約，表現(xiàn)為內部若干個進程間可以相互交往制約，表現(xiàn)為內部 邏輯上協(xié)調關系及共享資源的間接關系；邏輯上協(xié)調關系及共享資源的間接關系；動態(tài)性：動態(tài)性： 進程是動態(tài)的，有個生命期，由創(chuàng)建而產進程是動態(tài)的，有個生命期，由創(chuàng)建而產 生，由調度而執(zhí)行，由撤銷而消亡。生，由調度而執(zhí)行，由撤銷而消亡。異步性

7、：異步性： 各進程按獨立，未知的速度發(fā)展，導致不可再各進程按獨立，未知的速度發(fā)展，導致不可再 現(xiàn)性?，F(xiàn)性。同一程序運行在不同數(shù)據(jù)集上時，構成不同同一程序運行在不同數(shù)據(jù)集上時，構成不同的進程。的進程。4.4.進程的進程的基本狀態(tài)基本狀態(tài)在單處理器系統(tǒng)中，并發(fā)進程輪流占用處在單處理器系統(tǒng)中，并發(fā)進程輪流占用處理器，理器，由于發(fā)生事件引起狀態(tài)變化。由于發(fā)生事件引起狀態(tài)變化。 進程的三種基本狀態(tài)：進程的三種基本狀態(tài)：等待等待/ /阻塞態(tài)：因某事件發(fā)生而暫停，等待該阻塞態(tài)：因某事件發(fā)生而暫停，等待該事件完成。事件完成。就緒態(tài)：所需資源均已備齊，等待系統(tǒng)分配中就緒態(tài)：所需資源均已備齊，等待系統(tǒng)分配中央處理

8、器，以便運行。央處理器，以便運行。運行態(tài)：占有中央處理器正在運行。運行態(tài)：占有中央處理器正在運行。 進程的狀態(tài)變化進程的狀態(tài)變化l 運行態(tài)運行態(tài)等待態(tài)等待態(tài)l 等待態(tài)等待態(tài)就緒態(tài)就緒態(tài)l 就緒態(tài)就緒態(tài)運行態(tài)運行態(tài) 注意：只有處于就緒態(tài)的進程，才有可能轉換為運行態(tài)；注意：只有處于就緒態(tài)的進程，才有可能轉換為運行態(tài)； 處于等待態(tài)的進程在等待結束后只能進入就緒態(tài)，處于等待態(tài)的進程在等待結束后只能進入就緒態(tài)， 不能直接進入運行態(tài)；不能直接進入運行態(tài)； 處于就緒態(tài)的進程只能轉處于就緒態(tài)的進程只能轉 換為運行態(tài)，而不能再進入等待態(tài)。換為運行態(tài)，而不能再進入等待態(tài)。 2.1.3 2.1.3 進程控制塊進程控

9、制塊PCB每一個進程都設置一個每一個進程都設置一個“進程控制塊進程控制塊”。操作系統(tǒng)。操作系統(tǒng)通過進程控制塊來描述各進程的運行情況，并以此通過進程控制塊來描述各進程的運行情況，并以此為依據(jù)決定如何管理和控制進程運行。為依據(jù)決定如何管理和控制進程運行。進程控制塊是一個進程存在的唯一標志。最基本的進程控制塊是一個進程存在的唯一標志。最基本的進程控制塊如圖所示。進程控制塊如圖所示。 PCB的組織方式的組織方式鏈接方式鏈接方式不同狀態(tài)不同狀態(tài)PCB組成相應隊列組成相應隊列,若鏈接字為若鏈接字為0，表示，表示鏈接結束，鏈接結束，就緒隊列按進程優(yōu)先權大小排列，等就緒隊列按進程優(yōu)先權大小排列，等待進程，還可

10、按原因再一次分成小隊列待進程，還可按原因再一次分成小隊列進程號進程號 下一個鏈接的進程號下一個鏈接的進程號PCB1 4PCB2PCB8PCB7PCB6PCB5PCB4PCB33010978PCB9運行態(tài)隊列運行態(tài)隊列等待態(tài)隊列等待態(tài)隊列就緒態(tài)隊列就緒態(tài)隊列空閑隊列空閑隊列索引方式索引方式各種狀態(tài)建立獨自的索引表，每個表目記錄相各種狀態(tài)建立獨自的索引表，每個表目記錄相應應PCB在在PCB表中地址表中地址PCB1PCB8PCB7PCB6PCB5PCB4PCB3PCB2運行指針運行指針就緒指針就緒指針等待指針等待指針就緒索引表就緒索引表等待索引表等待索引表2.1.4 進程的控制進程的控制進程的創(chuàng)建進

11、程的創(chuàng)建 每一個進程都有生命期，即從創(chuàng)建到消亡。每一個進程都有生命期，即從創(chuàng)建到消亡。當一個程序模塊獲得一個數(shù)據(jù)塊和一個進程控當一個程序模塊獲得一個數(shù)據(jù)塊和一個進程控 制塊后就說創(chuàng)建了一個進程。制塊后就說創(chuàng)建了一個進程。 進程的創(chuàng)建過程進程的創(chuàng)建過程申請申請PCB為新進程分配內存為新進程分配內存初始化初始化PCB將新進程插入就緒隊列將新進程插入就緒隊列 進程的終止進程的終止 當一個進程完成了特定的工作后，收回當一個進程完成了特定的工作后，收回 它所占的數(shù)據(jù)塊和一個進程控制塊，即它所占的數(shù)據(jù)塊和一個進程控制塊，即 撤銷了一個進程。撤銷了一個進程。 終止過程終止過程 選擇新進程占用處理機選擇新進程

12、占用處理機 將子孫進程終止將子孫進程終止 將所有占用資源歸還給父進程或系統(tǒng)將所有占用資源歸還給父進程或系統(tǒng) 將該進程從所在隊列移出將該進程從所在隊列移出 等待過程等待過程從運行態(tài)轉為等待態(tài)，加入等待隊列從運行態(tài)轉為等待態(tài)，加入等待隊列喚醒過程喚醒過程使用喚醒原語從等待隊列中移出，將使用喚醒原語從等待隊列中移出，將PCB中狀態(tài)改為就緒，插入就緒隊列中狀態(tài)改為就緒，插入就緒隊列進程的掛起與激活進程的掛起與激活 進程的掛起進程的掛起將進程靜止，運行態(tài)進程暫停，就緒態(tài)進程暫不將進程靜止，運行態(tài)進程暫停，就緒態(tài)進程暫不接收調度，阻塞態(tài)不急轉成就緒態(tài)接收調度，阻塞態(tài)不急轉成就緒態(tài)例如：阻塞態(tài)進程調至外存例

13、如：阻塞態(tài)進程調至外存系統(tǒng)負荷過重，將一些進程掛起系統(tǒng)負荷過重，將一些進程掛起操作系統(tǒng)或父進程掛起（子）進程，檢查操作系統(tǒng)或父進程掛起（子）進程，檢查資源使用或修改協(xié)調子進程資源使用或修改協(xié)調子進程終端用戶掛起進程對程序進行修改終端用戶掛起進程對程序進行修改進程的激活進程的激活從靜止阻塞態(tài)變?yōu)榛顒幼枞麘B(tài)，等待轉從靜止阻塞態(tài)變?yōu)榛顒幼枞麘B(tài)，等待轉為就緒態(tài)；為就緒態(tài)；從靜止就緒態(tài)轉為活動就緒態(tài)，等待從靜止就緒態(tài)轉為活動就緒態(tài)，等待CPU調度選中調度選中運行運行態(tài)態(tài)活動就活動就緒緒活動阻塞活動阻塞靜止靜止就緒就緒靜止阻塞靜止阻塞掛掛起起激激活活激激活活掛掛起起釋放釋放釋放釋放掛起掛起進程狀態(tài)轉換圖進

14、程狀態(tài)轉換圖3.1 處理機調度的基本概念處理機調度的基本概念3.1.1調度類型調度類型一、高級調度一、高級調度即作業(yè)調度或長程調度、接納調度，從外存調度即作業(yè)調度或長程調度、接納調度，從外存調度選中若干個作業(yè)進入內存，并建立進程，插入到選中若干個作業(yè)進入內存，并建立進程，插入到就緒隊列中就緒隊列中分時系統(tǒng)與實時系統(tǒng)無需作業(yè)調度分時系統(tǒng)與實時系統(tǒng)無需作業(yè)調度所做工作包括：所做工作包括：根據(jù)多道程度確定選中作業(yè)的道數(shù)根據(jù)多道程度確定選中作業(yè)的道數(shù)根據(jù)調度算法確定選中哪些作業(yè)根據(jù)調度算法確定選中哪些作業(yè)二、低級調度二、低級調度 即進程調度或短程調度、處理器調度即進程調度或短程調度、處理器調度 調度方

15、式有：調度方式有：搶占方式搶占方式搶占原則有搶占原則有非搶占方式非搶占方式時間片原則時間片原則短作業(yè)優(yōu)先短作業(yè)優(yōu)先優(yōu)先權原則優(yōu)先權原則三、中級調度三、中級調度又稱中程調度，即存儲管理中的對換又稱中程調度，即存儲管理中的對換將暫時不運行的進程先調至外存置為掛將暫時不運行的進程先調至外存置為掛 起，等內存空閑再把它們從外存調入改起，等內存空閑再把它們從外存調入改 為就緒態(tài)為就緒態(tài)3.1.2 選擇調度方式與調度算法的若干準則選擇調度方式與調度算法的若干準則一、面向用戶準則一、面向用戶準則1、周轉時間、周轉時間 帶權周轉時間帶權周轉時間W =周轉時間周轉時間T /系統(tǒng)服務時間系統(tǒng)服務時間Ts2、響應時

16、間、響應時間3、截止時間（最遲開始時間）、截止時間（最遲開始時間）4、優(yōu)先權、優(yōu)先權二、面向系統(tǒng)的準則二、面向系統(tǒng)的準則1、系統(tǒng)吞吐量、系統(tǒng)吞吐量2、處理機利用率、處理機利用率3、各類資源的平衡利用、各類資源的平衡利用3.2 調度算法調度算法一、先來先服務法一、先來先服務法(FCFS) 按照進程進入就緒隊列的先后次序來選擇進程按照進程進入就緒隊列的先后次序來選擇進程 從后備隊列選中作業(yè)進入內存從后備隊列選中作業(yè)進入內存 利于利于CPU繁忙的作業(yè)繁忙的作業(yè) 對長作業(yè)進程有利，對短作業(yè)不利對長作業(yè)進程有利，對短作業(yè)不利 周轉時間完成時間到達時間周轉時間完成時間到達時間 帶權周轉時間周轉時間帶權周轉

17、時間周轉時間/服務時間服務時間二、二、時間片輪轉法：時間片輪轉法： 規(guī)定一個時間片規(guī)定一個時間片(如如10毫秒毫秒)，每個進程輪流地，每個進程輪流地運行一個這樣的時間片。當這個時間片結束時，運行一個這樣的時間片。當這個時間片結束時，就強迫當前運行的進程退出處理器，讓其他進就強迫當前運行的進程退出處理器，讓其他進程運行。實現(xiàn)方法是使用內部間隔時鐘程運行。實現(xiàn)方法是使用內部間隔時鐘 保證所有進程均能獲得時間片保證所有進程均能獲得時間片 時間片的確定時間片的確定系統(tǒng)對時間的要求系統(tǒng)對時間的要求就緒進程的數(shù)目就緒進程的數(shù)目系統(tǒng)處理能力系統(tǒng)處理能力三、最高優(yōu)先權法三、最高優(yōu)先權法每一個進程給出一個優(yōu)先數(shù)，處理器調度每每一個進程給出一個優(yōu)先數(shù)，處理器調度每次選擇就緒進程中優(yōu)先數(shù)最小者，讓它占用次選擇就緒進程中優(yōu)先數(shù)最小者，讓它占用處理器運行。處理器運行。該調度算法又分兩種：該調度算法又分兩種：非搶占式非搶占式適用于批處理系統(tǒng)或要求不嚴的實時系統(tǒng)適用于批處理系統(tǒng)或要求不嚴的實時系統(tǒng)搶占式搶占式適合緊迫作業(yè)需求及要求較高的實時、分時系統(tǒng)適合緊迫作業(yè)需求及要求較高的實時、分時系統(tǒng) 優(yōu)先權的確定優(yōu)先權的確定靜態(tài)優(yōu)先數(shù)法靜態(tài)優(yōu)先數(shù)法進程創(chuàng)建時確定，在運行期間不變進程創(chuàng)建時確定，在運行期間不變例如例如:系統(tǒng)進程、運行時間短或內存需求