進(jìn)程的描述及處理器調(diào)度

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

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

3、一段程序和它執(zhí)行時處理的數(shù)據(jù)一段程序和它執(zhí)行時處理的數(shù)據(jù)1.可與其它程序并發(fā)執(zhí)行的程序的一次執(zhí)行可與其它程序并發(fā)執(zhí)行的程序的一次執(zhí)行例如，某一算題為將一千個字符輸入到緩沖區(qū)，處理后例如，某一算題為將一千個字符輸入到緩沖區(qū)，處理后 輸出到磁帶，按并發(fā)程序設(shè)計思路將該算題分成：輸出到磁帶，按并發(fā)程序設(shè)計思路將該算題分成： 模塊模塊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ā)進(jìn)行。到磁帶。讓這三個模塊同時并發(fā)進(jìn)行。2.2.進(jìn)程的形成進(jìn)程的形成 例如：例如：P P為一編譯程序，同時為甲、乙兩程序服為一編譯程序，同時為甲、乙兩程序服 務(wù)，假定編譯程序務(wù)，假定編譯程序P P從從a a點開始工作，現(xiàn)在正在編點開始工作，現(xiàn)在正在編 譯源程序甲，當(dāng)工作到譯源程序甲，當(dāng)工作到b b點時程序點時程序P P等待磁盤傳輸?shù)却疟P傳輸 信息；這時利用處理器讓編譯程序信息；這時利用處理器讓編譯程序P P為源程序乙進(jìn)為源程序乙進(jìn) 行編譯，編譯程序仍從行編譯，編譯

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

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

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

8、器，以便運行。央處理器，以便運行。運行態(tài)：占有中央處理器正在運行。運行態(tài)：占有中央處理器正在運行。 進(jìn)程的狀態(tài)變化進(jìn)程的狀態(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)的進(jìn)程，才有可能轉(zhuǎn)換為運行態(tài)；注意：只有處于就緒態(tài)的進(jìn)程，才有可能轉(zhuǎn)換為運行態(tài)； 處于等待態(tài)的進(jìn)程在等待結(jié)束后只能進(jìn)入就緒態(tài)，處于等待態(tài)的進(jìn)程在等待結(jié)束后只能進(jìn)入就緒態(tài)， 不能直接進(jìn)入運行態(tài)；不能直接進(jìn)入運行態(tài)； 處于就緒態(tài)的進(jìn)程只能轉(zhuǎn)處于就緒態(tài)的進(jìn)程只能轉(zhuǎn) 換為運行態(tài)，而不能再進(jìn)入等待態(tài)。換為運行態(tài)，而不能再進(jìn)入等待態(tài)。 2.1.3 2.1.3 進(jìn)程控制塊進(jìn)程控

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

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

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

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

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

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

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

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

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