軟件設(shè)計師培訓(xùn)(OS)

1、軟件設(shè)計師培訓(xùn)軟件設(shè)計師培訓(xùn)軟件設(shè)計師軟件設(shè)計師3.3.操作系統(tǒng)知識操作系統(tǒng)知識大綱要求：大綱要求：l 操作系統(tǒng)的內(nèi)核（中斷控制）、進(jìn)程、線程概念操作系統(tǒng)的內(nèi)核（中斷控制）、進(jìn)程、線程概念l 處理機(jī)管理（狀態(tài)轉(zhuǎn)換、共享與互斥、分時輪轉(zhuǎn)、搶占、死鎖）處理機(jī)管理（狀態(tài)轉(zhuǎn)換、共享與互斥、分時輪轉(zhuǎn)、搶占、死鎖）l 存儲管理（主存保護(hù)、動態(tài)連接分配、分段、分頁、虛存）存儲管理（主存保護(hù)、動態(tài)連接分配、分段、分頁、虛存）l 設(shè)備管理（設(shè)備管理（I/OI/O控制、假脫機(jī)）控制、假脫機(jī)）l 文件管理（文件目錄、文件組織、存取方法、存取控制、恢復(fù)處理）文件管理（文件目錄、文件組織、存取方法、存取控制、恢復(fù)處理）

2、l 作業(yè)管理（作業(yè)調(diào)度、作業(yè)控制語言（作業(yè)管理（作業(yè)調(diào)度、作業(yè)控制語言（JCLJCL）、多道程序設(shè)計）、多道程序設(shè)計）l 漢字處理，多媒體處理，人機(jī)界面漢字處理，多媒體處理，人機(jī)界面l 網(wǎng)絡(luò)操作系統(tǒng)和嵌入式操作系統(tǒng)基礎(chǔ)知識網(wǎng)絡(luò)操作系統(tǒng)和嵌入式操作系統(tǒng)基礎(chǔ)知識l 操作系統(tǒng)的配置操作系統(tǒng)的配置軟件設(shè)計師軟件設(shè)計師3.1 3.1 操作系統(tǒng)的基本概念操作系統(tǒng)的基本概念l 操作系統(tǒng)的定義操作系統(tǒng)的定義 能有效地組織和管理系統(tǒng)中的各種軟、硬件資源，合理地能有效地組織和管理系統(tǒng)中的各種軟、硬件資源，合理地組織計算機(jī)系統(tǒng)工作流程，控制程序的執(zhí)行，并且向用戶提組織計算機(jī)系統(tǒng)工作流程，控制程序的執(zhí)行，并且向用戶提

3、供一個良好的工作環(huán)境和友好的接口。供一個良好的工作環(huán)境和友好的接口。硬件資源：包括硬件資源：包括CPUCPU，存儲器，輸入，存儲器，輸入/ /輸出資源等物理設(shè)備。輸出資源等物理設(shè)備。軟件資源：以文件形式保存在存儲器上的程序和數(shù)據(jù)等信息。軟件資源：以文件形式保存在存儲器上的程序和數(shù)據(jù)等信息。軟件設(shè)計師軟件設(shè)計師l 操作系統(tǒng)的操作系統(tǒng)的2 2個重要作用個重要作用: :(1) (1) 通過資源管理提高計算機(jī)系統(tǒng)的效率通過資源管理提高計算機(jī)系統(tǒng)的效率(2) (2) 改善人機(jī)界面，向用戶提供友好的工作環(huán)境改善人機(jī)界面，向用戶提供友好的工作環(huán)境軟件設(shè)計師軟件設(shè)計師l 操作系統(tǒng)的操作系統(tǒng)的4 4個特征個特征

4、(1)(1)并發(fā)性：計算機(jī)系統(tǒng)存在著許多并發(fā)執(zhí)行的活動并發(fā)性：計算機(jī)系統(tǒng)存在著許多并發(fā)執(zhí)行的活動P1C1I1I2C2P2I1I2I3I4C1C2C3C4P1P2P3P4軟件設(shè)計師軟件設(shè)計師(2)(2)共享性：系統(tǒng)中各個并發(fā)活動要共享計算機(jī)系統(tǒng)中的各共享性：系統(tǒng)中各個并發(fā)活動要共享計算機(jī)系統(tǒng)中的各 種軟，硬件資源。種軟，硬件資源。(3)(3)虛擬性：虛擬是操作系統(tǒng)中的重要特征，所謂虛擬就是虛擬性：虛擬是操作系統(tǒng)中的重要特征，所謂虛擬就是 把物理上的一臺設(shè)備變成邏輯上的多臺設(shè)備。把物理上的一臺設(shè)備變成邏輯上的多臺設(shè)備。(4)(4)不確定性不確定性( (異步性異步性) )：指進(jìn)程的執(zhí)行順序和執(zhí)行時間

5、及執(zhí)：指進(jìn)程的執(zhí)行順序和執(zhí)行時間及執(zhí) 行結(jié)果的不確定性。行結(jié)果的不確定性。軟件設(shè)計師軟件設(shè)計師l 操作系統(tǒng)的操作系統(tǒng)的5 5大管理功能大管理功能 (1) (1) 進(jìn)程管理進(jìn)程管理 (2) (2) 存儲管理存儲管理 (3) (3) 設(shè)備管理設(shè)備管理 (4) (4) 文件管理文件管理 (5) (5) 作業(yè)管理作業(yè)管理軟件設(shè)計師軟件設(shè)計師l基本概念基本概念 多道程序設(shè)計原理多道程序設(shè)計原理：在計算機(jī)內(nèi)存中同時存放幾道相互：在計算機(jī)內(nèi)存中同時存放幾道相互 獨(dú)立的程序，它們在管理程序的控制下相互穿插地運(yùn)獨(dú)立的程序，它們在管理程序的控制下相互穿插地運(yùn) 行，共享行，共享CPUCPU和外設(shè)等資源。和外設(shè)等資源

6、。 程序程序：具有特定功能的一組指令集合，它指出了處理器：具有特定功能的一組指令集合，它指出了處理器 執(zhí)行操作的步驟。執(zhí)行操作的步驟。 進(jìn)程進(jìn)程：進(jìn)程是一個程序在一個數(shù)據(jù)集合上的一次執(zhí)行。：進(jìn)程是一個程序在一個數(shù)據(jù)集合上的一次執(zhí)行。3.2 3.2 進(jìn)程管理進(jìn)程管理軟件設(shè)計師軟件設(shè)計師程序和進(jìn)程區(qū)別程序和進(jìn)程區(qū)別：(1)(1)程序是動態(tài)的，進(jìn)程是動態(tài)的。程序是動態(tài)的，進(jìn)程是動態(tài)的。(2)(2)進(jìn)程與程序的對應(yīng)關(guān)系：通過多次執(zhí)行，一個程序可進(jìn)程與程序的對應(yīng)關(guān)系：通過多次執(zhí)行，一個程序可 對應(yīng)多個進(jìn)程；通過調(diào)用關(guān)系，一個進(jìn)程可包括多個對應(yīng)多個進(jìn)程；通過調(diào)用關(guān)系，一個進(jìn)程可包括多個 程序。程序。(3)

7、(3)進(jìn)程是暫時的，程序的永久的：進(jìn)程是一個狀態(tài)變化進(jìn)程是暫時的，程序的永久的：進(jìn)程是一個狀態(tài)變化 的過程，程序可長久保存。的過程，程序可長久保存。(4)(4)進(jìn)程與程序的組成不同：進(jìn)程的組成包括程序、數(shù)據(jù)進(jìn)程與程序的組成不同：進(jìn)程的組成包括程序、數(shù)據(jù) 進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）。進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）。軟件設(shè)計師軟件設(shè)計師 進(jìn)程通常由三部分組成：進(jìn)程通常由三部分組成： (1)(1)程序：描述了進(jìn)程所要完成的功能，是進(jìn)程執(zhí)行時不可程序：描述了進(jìn)程所要完成的功能，是進(jìn)程執(zhí)行時不可 修改的部分。修改的部分。 (2)(2)數(shù)據(jù)集合：程序執(zhí)行時所需要的數(shù)據(jù)和工作區(qū)，為一個數(shù)據(jù)集合：程序執(zhí)行時所

8、需要的數(shù)據(jù)和工作區(qū)，為一個 進(jìn)程專用，可修改。進(jìn)程專用，可修改。 (3)(3)進(jìn)程控制塊進(jìn)程控制塊PCB (Process Control Block)PCB (Process Control Block)：包含了：包含了 進(jìn)進(jìn) 程的描述信息和控制信息，是進(jìn)程的動態(tài)特性的集中反程的描述信息和控制信息，是進(jìn)程的動態(tài)特性的集中反 映。映。PCBPCB包含以下幾類信息：進(jìn)程描述信息、進(jìn)程控制包含以下幾類信息：進(jìn)程描述信息、進(jìn)程控制 信息、資源占用信息、信息、資源占用信息、CPUCPU現(xiàn)場保護(hù)結(jié)構(gòu)：現(xiàn)場保護(hù)結(jié)構(gòu)：軟件設(shè)計師軟件設(shè)計師l 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換：進(jìn)程的基本狀態(tài)及轉(zhuǎn)換： 進(jìn)程在生命期內(nèi)處于且

9、僅處于三種基本狀態(tài)之一：進(jìn)程在生命期內(nèi)處于且僅處于三種基本狀態(tài)之一： 運(yùn)行態(tài)運(yùn)行態(tài): :當(dāng)一個進(jìn)程在處理機(jī)上運(yùn)行時，則稱該進(jìn)程處于當(dāng)一個進(jìn)程在處理機(jī)上運(yùn)行時，則稱該進(jìn)程處于運(yùn)行狀態(tài)。運(yùn)行狀態(tài)。 就緒態(tài)就緒態(tài): :一個進(jìn)程獲得了除處理機(jī)外的一切所需資源，一一個進(jìn)程獲得了除處理機(jī)外的一切所需資源，一旦得到處理機(jī)即可運(yùn)行，則稱此進(jìn)程處于就緒狀態(tài)。旦得到處理機(jī)即可運(yùn)行，則稱此進(jìn)程處于就緒狀態(tài)。 阻塞態(tài)阻塞態(tài): :當(dāng)一個進(jìn)程正在等待某一事件發(fā)生（例如請求當(dāng)一個進(jìn)程正在等待某一事件發(fā)生（例如請求I IO O而等待而等待I IO O完成等）而暫時停止運(yùn)行，這時即使把處理完成等）而暫時停止運(yùn)行，這時即使把處理

10、機(jī)分配給進(jìn)程也無法運(yùn)行，故稱該進(jìn)程處于阻塞狀態(tài)。注機(jī)分配給進(jìn)程也無法運(yùn)行，故稱該進(jìn)程處于阻塞狀態(tài)。注意與就緒狀態(tài)的不同在于即使處理機(jī)處于空閑狀態(tài)也無法意與就緒狀態(tài)的不同在于即使處理機(jī)處于空閑狀態(tài)也無法運(yùn)行。運(yùn)行。 軟件設(shè)計師軟件設(shè)計師運(yùn)行運(yùn)行就緒就緒阻塞阻塞調(diào)度調(diào)度I/OI/O完成完成時間片到時間片到I/OI/O請求請求 就緒就緒運(yùn)行：運(yùn)行：調(diào)度程序選擇一個新的進(jìn)程運(yùn)行調(diào)度程序選擇一個新的進(jìn)程運(yùn)行. . 運(yùn)行運(yùn)行就緒：就緒：運(yùn)行進(jìn)程用完時間片被中斷或在搶占調(diào)度運(yùn)行進(jìn)程用完時間片被中斷或在搶占調(diào)度 方式中方式中, , 因為一高優(yōu)先級進(jìn)程進(jìn)入就緒狀態(tài)因為一高優(yōu)先級進(jìn)程進(jìn)入就緒狀態(tài) 運(yùn)行運(yùn)行阻塞：阻

11、塞：進(jìn)程發(fā)生進(jìn)程發(fā)生I/OI/O請求或等待某事件時請求或等待某事件時 阻塞阻塞就緒：就緒：當(dāng)當(dāng)I/OI/O完成或所等待的事件發(fā)生時完成或所等待的事件發(fā)生時軟件設(shè)計師軟件設(shè)計師l 進(jìn)程調(diào)度進(jìn)程調(diào)度 在多道程序環(huán)境下，系統(tǒng)中有多個進(jìn)程同時運(yùn)行。多在多道程序環(huán)境下，系統(tǒng)中有多個進(jìn)程同時運(yùn)行。多個的進(jìn)程競爭處理機(jī)，就要求系統(tǒng)提供進(jìn)程調(diào)度功能，個的進(jìn)程競爭處理機(jī)，就要求系統(tǒng)提供進(jìn)程調(diào)度功能，將處理機(jī)動態(tài)地分配給系統(tǒng)中的各個進(jìn)程，使之能夠協(xié)將處理機(jī)動態(tài)地分配給系統(tǒng)中的各個進(jìn)程，使之能夠協(xié)調(diào)一致的運(yùn)行。調(diào)一致的運(yùn)行。進(jìn)程調(diào)度程序進(jìn)程調(diào)度程序：主要任務(wù)是按照一定的調(diào)度算法從就緒：主要任務(wù)是按照一定的調(diào)度算法從

12、就緒隊列中選取一個進(jìn)程，把處理機(jī)分配給此進(jìn)程使用。隊列中選取一個進(jìn)程，把處理機(jī)分配給此進(jìn)程使用。軟件設(shè)計師軟件設(shè)計師 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式(1) (1) 非搶占方式：在非搶占方式下，調(diào)度程序一旦把非搶占方式：在非搶占方式下，調(diào)度程序一旦把 CPUCPU分分配給某一進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)配給某一進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而不能運(yùn)行時，才將生某事件而不能運(yùn)行時，才將CPUCPU分給其它進(jìn)程。分給其它進(jìn)程。 這種調(diào)度方式通常用在批處理系統(tǒng)中。它的主要優(yōu)點(diǎn)這種調(diào)度方式通常用在批處理系統(tǒng)中。它的主要優(yōu)點(diǎn)是簡單、系統(tǒng)開銷小。是簡單、系統(tǒng)開銷小。(2) (2)

13、 搶占方式：當(dāng)一個進(jìn)程正在執(zhí)行時，系統(tǒng)可以基于某種搶占方式：當(dāng)一個進(jìn)程正在執(zhí)行時，系統(tǒng)可以基于某種策略剝奪策略剝奪CPUCPU給其它進(jìn)程。剝奪的原則有：給其它進(jìn)程。剝奪的原則有：優(yōu)先權(quán)原則、優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則和時間片原則。短進(jìn)程優(yōu)先原則和時間片原則。 這種調(diào)度方式多用在分時系統(tǒng)和實(shí)時系統(tǒng)中，以便及這種調(diào)度方式多用在分時系統(tǒng)和實(shí)時系統(tǒng)中，以便及時響應(yīng)各進(jìn)程的請求。時響應(yīng)各進(jìn)程的請求。軟件設(shè)計師軟件設(shè)計師進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法(1)(1)先來先服務(wù)先來先服務(wù)FCFS(FCFS(先進(jìn)先出調(diào)度算法，先進(jìn)先出調(diào)度算法，F(xiàn)IFO)FIFO)【算法思想【算法思想】: :最簡單的算法最簡單的算法按照

14、進(jìn)程進(jìn)入就緒隊列的按照進(jìn)程進(jìn)入就緒隊列的先后次序先后次序，分派，分派CPUCPU；當(dāng)前進(jìn)程占用當(dāng)前進(jìn)程占用CPUCPU，直到執(zhí)行完或阻塞直到執(zhí)行完或阻塞，才出讓，才出讓CPUCPU（非搶占方式）。（非搶占方式）。在進(jìn)程在進(jìn)程喚醒后喚醒后（如（如I/OI/O完成），并不立即恢復(fù)執(zhí)行，完成），并不立即恢復(fù)執(zhí)行，通常等到當(dāng)前進(jìn)程出讓通常等到當(dāng)前進(jìn)程出讓CPUCPU。【特點(diǎn)】：【特點(diǎn)】：比較有利于長作業(yè)，而不利于短作業(yè)。比較有利于長作業(yè)，而不利于短作業(yè)。有利于有利于CPUCPU繁忙的作業(yè)，而不利于繁忙的作業(yè)，而不利于I/OI/O繁忙的作業(yè)。繁忙的作業(yè)。軟件設(shè)計師軟件設(shè)計師(2)(2)短進(jìn)程優(yōu)先調(diào)度算法

15、短進(jìn)程優(yōu)先調(diào)度算法(SJF,SPF)(SJF,SPF)【算法思想【算法思想】：選擇就緒隊列中估計運(yùn)行時間最短的進(jìn)程選擇就緒隊列中估計運(yùn)行時間最短的進(jìn)程投入運(yùn)行。通常后來的短作業(yè)投入運(yùn)行。通常后來的短作業(yè)不搶先不搶先正在執(zhí)行的作業(yè)。正在執(zhí)行的作業(yè)。【優(yōu)點(diǎn)【優(yōu)點(diǎn)】：比比FCFSFCFS改善改善平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間和和平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間，縮，縮短作業(yè)的等待時間；短作業(yè)的等待時間；提高系統(tǒng)的提高系統(tǒng)的吞吐量吞吐量； 【缺點(diǎn)【缺點(diǎn)】：對長作業(yè)非常不利對長作業(yè)非常不利，可能長時間得不到執(zhí)行；，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的未能依據(jù)作業(yè)的緊迫程度緊迫程度來劃分執(zhí)行的優(yōu)先級；來劃分執(zhí)行

16、的優(yōu)先級；難以準(zhǔn)確估計作業(yè)（進(jìn)程）的執(zhí)行時間難以準(zhǔn)確估計作業(yè)（進(jìn)程）的執(zhí)行時間，從而影響，從而影響調(diào)度性能。調(diào)度性能。軟件設(shè)計師軟件設(shè)計師(3)(3)優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法(HPF(HPFHighest Priority First)Highest Priority First)【算法思想【算法思想】：優(yōu)先選擇就緒隊列中優(yōu)先級最高的進(jìn)程投：優(yōu)先選擇就緒隊列中優(yōu)先級最高的進(jìn)程投入運(yùn)行。分為：入運(yùn)行。分為：非搶占式優(yōu)先級算法非搶占式優(yōu)先級算法：僅發(fā)生在進(jìn)程放棄：僅發(fā)生在進(jìn)程放棄CPUCPU。搶占式優(yōu)先級算法搶占式優(yōu)先級算法：可剝奪當(dāng)前運(yùn)行進(jìn)程：可剝奪當(dāng)前運(yùn)行進(jìn)程CPUCPU?！?優(yōu)先權(quán)的類型

17、優(yōu)先權(quán)的類型】靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級：在進(jìn)程創(chuàng)建時指定優(yōu)先級：在進(jìn)程創(chuàng)建時指定優(yōu)先級, , 在進(jìn)程運(yùn)在進(jìn)程運(yùn)行時優(yōu)先數(shù)不變。行時優(yōu)先數(shù)不變。動態(tài)優(yōu)先級動態(tài)優(yōu)先級：在進(jìn)程創(chuàng)建時創(chuàng)立一個優(yōu)先級，但在：在進(jìn)程創(chuàng)建時創(chuàng)立一個優(yōu)先級，但在其生命周期內(nèi)優(yōu)先數(shù)可以動態(tài)變化。如等待時間長其生命周期內(nèi)優(yōu)先數(shù)可以動態(tài)變化。如等待時間長優(yōu)先數(shù)可改變。優(yōu)先數(shù)可改變。【確定優(yōu)先級的依據(jù)【確定優(yōu)先級的依據(jù)】 進(jìn)程類型、對資源的需求、根據(jù)用戶要求。進(jìn)程類型、對資源的需求、根據(jù)用戶要求。軟件設(shè)計師軟件設(shè)計師(4)(4)高響應(yīng)比優(yōu)先高響應(yīng)比優(yōu)先 (HRRN, Highest Response Ratio Next )： HRRN

18、是是FCFS和和SJF的折衷算法，響應(yīng)比的折衷算法，響應(yīng)比R用下式動態(tài)計用下式動態(tài)計算：算： 響應(yīng)比響應(yīng)比R =【特點(diǎn)】：【特點(diǎn)】： 等待時間相同要求服務(wù)的時間越短優(yōu)先權(quán)越高等待時間相同要求服務(wù)的時間越短優(yōu)先權(quán)越高, 有利于有利于短作業(yè)。短作業(yè)。 要求服務(wù)時間相同要求服務(wù)時間相同,等待時間越長優(yōu)先權(quán)越高等待時間越長優(yōu)先權(quán)越高,近似于先近似于先來先服務(wù)。來先服務(wù)。 長作業(yè)的優(yōu)先權(quán)會隨等待時間加長而升高長作業(yè)的優(yōu)先權(quán)會隨等待時間加長而升高,長作業(yè)也會得長作業(yè)也會得到執(zhí)行。到執(zhí)行。等待時間等待時間+要求服務(wù)時間要求服務(wù)時間 要求服務(wù)時間要求服務(wù)時間軟件設(shè)計師軟件設(shè)計師(5)(5)時間片輪轉(zhuǎn)調(diào)度算法時

19、間片輪轉(zhuǎn)調(diào)度算法【算法思想】：【算法思想】：通過時間片輪轉(zhuǎn)，提高進(jìn)程通過時間片輪轉(zhuǎn)，提高進(jìn)程并發(fā)性并發(fā)性和和響應(yīng)時響應(yīng)時間間特性，從而提高特性，從而提高資源利用率資源利用率。將系統(tǒng)中所有的就緒進(jìn)程按照將系統(tǒng)中所有的就緒進(jìn)程按照FCFSFCFS原則，排成一個原則，排成一個隊列隊列。 每次調(diào)度時將每次調(diào)度時將CPUCPU分派給分派給隊首進(jìn)程隊首進(jìn)程，讓其，讓其執(zhí)行一個時間執(zhí)行一個時間 片片。時間片的。時間片的長度長度從幾個從幾個msms到幾百到幾百msms。在一個時間片結(jié)束時，發(fā)生在一個時間片結(jié)束時，發(fā)生時鐘中斷時鐘中斷。調(diào)度程序據(jù)此調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到，將其

20、送到就緒隊列就緒隊列 的末尾的末尾，并通過，并通過CPUCPU現(xiàn)場切換現(xiàn)場切換執(zhí)行當(dāng)前的隊首進(jìn)程執(zhí)行當(dāng)前的隊首進(jìn)程。進(jìn)程可以進(jìn)程可以未使用完一個時間片未使用完一個時間片，就，就出讓出讓CPUCPU（如阻塞）。（如阻塞）。 軟件設(shè)計師軟件設(shè)計師(6)(6)多級反饋隊列算法多級反饋隊列算法( (多隊列輪轉(zhuǎn)法多隊列輪轉(zhuǎn)法) )【算法思想】：【算法思想】： 設(shè)置設(shè)置多個就緒隊列多個就緒隊列，分別賦予，分別賦予不同的優(yōu)先級不同的優(yōu)先級，隊列，隊列1 1的的優(yōu)先級最高，其他逐級降低。每隊列分配優(yōu)先級最高，其他逐級降低。每隊列分配不同的時間片不同的時間片，規(guī)定優(yōu)先級越低則時間片越長。規(guī)定優(yōu)先級越低則時間片越

21、長。 新進(jìn)程就緒后，新進(jìn)程就緒后，先投入隊列先投入隊列1 1的末尾的末尾，按，按FCFSFCFS算法調(diào)度。算法調(diào)度。若一個時間片未能執(zhí)行完，則若一個時間片未能執(zhí)行完，則降低降低投入到隊列投入到隊列2 2的末尾；的末尾；依此類推，依此類推，降低到最后的隊列降低到最后的隊列，則按，則按“時間片輪轉(zhuǎn)時間片輪轉(zhuǎn)”算法算法調(diào)度直到完成。調(diào)度直到完成。軟件設(shè)計師軟件設(shè)計師 進(jìn)程由于等待事件而放棄進(jìn)程由于等待事件而放棄CPUCPU后后, , 進(jìn)入等待隊列進(jìn)入等待隊列, , 一一旦等待的事件發(fā)生旦等待的事件發(fā)生, , 則回到原來的就緒隊列。則回到原來的就緒隊列。僅當(dāng)僅當(dāng)較高優(yōu)先級的隊列為空較高優(yōu)先級的隊列為空

22、，才調(diào)度較低優(yōu)先級的隊，才調(diào)度較低優(yōu)先級的隊列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時有新進(jìn)程進(jìn)入較高列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時有新進(jìn)程進(jìn)入較高優(yōu)先級的隊列，則優(yōu)先級的隊列，則搶先搶先執(zhí)行新進(jìn)程，并把執(zhí)行新進(jìn)程，并把被搶先的進(jìn)被搶先的進(jìn)程投入原隊列的末尾程投入原隊列的末尾。軟件設(shè)計師軟件設(shè)計師l 進(jìn)程同步和互斥進(jìn)程同步和互斥 在計算機(jī)系統(tǒng)中，多個進(jìn)程可以并發(fā)執(zhí)行，因在計算機(jī)系統(tǒng)中，多個進(jìn)程可以并發(fā)執(zhí)行，因此進(jìn)程間必然存在資源共享和相互合作的問題。此進(jìn)程間必然存在資源共享和相互合作的問題。軟件設(shè)計師軟件設(shè)計師例：例：共享數(shù)據(jù)變量資源造成的錯誤共享數(shù)據(jù)變量資源造成的錯誤終端售票處理進(jìn)程：終端售票處理進(jìn)程：

23、PROCESS Pi(i=1,2,3,n) /* Pi為顧客服務(wù)的處理進(jìn)程為顧客服務(wù)的處理進(jìn)程*/Begin 按旅客訂票要求找到按旅客訂票要求找到Aj; /* Aj為公共數(shù)據(jù)區(qū)為公共數(shù)據(jù)區(qū)*/ Ri:=Aj; /* Ri為各進(jìn)程執(zhí)行時所用的工作單元為各進(jìn)程執(zhí)行時所用的工作單元*/ if Ri1 then begin Ri:=Ri-1; Aj:=Ri; 輸出一張票輸出一張票； end else輸出輸出“票已售完票已售完”;end軟件設(shè)計師軟件設(shè)計師進(jìn)程互斥進(jìn)程互斥是指當(dāng)有若干進(jìn)程都要使用某一資源是指當(dāng)有若干進(jìn)程都要使用某一資源時，任何時刻最多只允許一個進(jìn)程去使用，其他時，任何時刻最多只允許一個進(jìn)

24、程去使用，其他要使用該資源的進(jìn)程必須等待，直到占用資源者要使用該資源的進(jìn)程必須等待，直到占用資源者釋放了該資源。釋放了該資源。 這樣的資源稱為稱為互斥資源這樣的資源稱為稱為互斥資源打印機(jī)，打印機(jī)，共享變量等。共享變量等。軟件設(shè)計師軟件設(shè)計師 共享資源的互斥的使用就是限定并發(fā)進(jìn)程互共享資源的互斥的使用就是限定并發(fā)進(jìn)程互斥的進(jìn)入相關(guān)臨界區(qū)。斥的進(jìn)入相關(guān)臨界區(qū)。 臨界區(qū)臨界區(qū) 并發(fā)進(jìn)程中與共享變量有關(guān)的程序段。并發(fā)進(jìn)程中與共享變量有關(guān)的程序段。 如例題中的臨界區(qū)：如例題中的臨界區(qū)： Ri:=Aj; if Ri1 then begin Ri:=Ri-1; Aj:=Ri; PV操作操作 就是一種實(shí)現(xiàn)相關(guān)

25、臨界區(qū)的管理，實(shí)就是一種實(shí)現(xiàn)相關(guān)臨界區(qū)的管理，實(shí)現(xiàn)進(jìn)程互斥的方法。現(xiàn)進(jìn)程互斥的方法。 軟件設(shè)計師軟件設(shè)計師 PVPV操作操作進(jìn)程的互斥進(jìn)程的互斥 PVPV操作由操作由P P操作操作和和V V操作操作組成，組成，P P操作和操作和V V操是兩個在操是兩個在信號量信號量S S上進(jìn)行的操作。定義如下：上進(jìn)行的操作。定義如下： Procedure P(S)Procedure P(S) begin S:=S-1; begin S:=S-1; if S0 then if S0 then 則該進(jìn)程進(jìn)入等待隊列；則該進(jìn)程進(jìn)入等待隊列； end;Pend;P Procedure V(S) Procedure V

26、(S) begin S:=S+1; begin S:=S+1; if S if S0 then 0 then 喚醒一個等待隊列中的進(jìn)程進(jìn)入就緒；喚醒一個等待隊列中的進(jìn)程進(jìn)入就緒； end;Vend;V 軟件設(shè)計師軟件設(shè)計師begin S：semaphore S：=1cobegin PROCESS Pi(i=1,2,3,n) 按旅客訂票要求找到按旅客訂票要求找到Aj; P（S） Ri:=Aj; if Ri1 then begin Ri:=Ri-1; Aj:=Ri; V（S） 輸出一張票輸出一張票； end else begin V（S） 輸出輸出“票已售完票已售完”; coendend軟件設(shè)計師

27、軟件設(shè)計師例：共享緩存器資源造成的錯誤例：共享緩存器資源造成的錯誤A進(jìn)程進(jìn)程B進(jìn)程進(jìn)程記錄記錄緩存器緩存器讀讀寫寫取取處理處理(1)A(1)A的執(zhí)行速度操作的執(zhí)行速度操作B B的執(zhí)行速度，造成緩存器中的數(shù)的執(zhí)行速度，造成緩存器中的數(shù)據(jù)還沒拿走，據(jù)還沒拿走，A A又讀入新數(shù)據(jù)覆蓋了原有數(shù)據(jù)。又讀入新數(shù)據(jù)覆蓋了原有數(shù)據(jù)。(2)B(2)B的執(zhí)行速度操作的執(zhí)行速度操作A A的執(zhí)行速度，的執(zhí)行速度，B B從緩存器取出一個從緩存器取出一個記錄并加工后，記錄并加工后，A A還沒有讀入新數(shù)據(jù)，造成還沒有讀入新數(shù)據(jù)，造成B B在緩存器中在緩存器中重復(fù)取同一個記錄加工。重復(fù)取同一個記錄加工。軟件設(shè)計師軟件設(shè)計師進(jìn)

28、程同步進(jìn)程同步是指并發(fā)進(jìn)程之間存在一種制約關(guān)系，是指并發(fā)進(jìn)程之間存在一種制約關(guān)系，一個進(jìn)程的執(zhí)行依賴另一個進(jìn)程的消息，當(dāng)一個進(jìn)一個進(jìn)程的執(zhí)行依賴另一個進(jìn)程的消息，當(dāng)一個進(jìn)程沒有得到另一個進(jìn)程的消息時應(yīng)等待，直到消息程沒有得到另一個進(jìn)程的消息時應(yīng)等待，直到消息到達(dá)才被喚醒。到達(dá)才被喚醒。軟件設(shè)計師軟件設(shè)計師 PVPV操作操作進(jìn)程的互斥進(jìn)程的互斥1.1.調(diào)用調(diào)用P P操作測試消息是否到達(dá)。若消息尚未到達(dá)則操作測試消息是否到達(dá)。若消息尚未到達(dá)則S=0S=0，調(diào)，調(diào)用用P(S)P(S)后，讓調(diào)用者稱為等待信號量后，讓調(diào)用者稱為等待信號量S S的狀態(tài)；若消息已的狀態(tài)；若消息已經(jīng)存在則經(jīng)存在則S0S0，調(diào)

29、用，調(diào)用P(S)P(S)后進(jìn)程不會成為等待狀態(tài)而可繼后進(jìn)程不會成為等待狀態(tài)而可繼續(xù)執(zhí)行。續(xù)執(zhí)行。2.2.調(diào)用調(diào)用V V操作發(fā)送消息。任何進(jìn)程要向進(jìn)程發(fā)送消息時可調(diào)操作發(fā)送消息。任何進(jìn)程要向進(jìn)程發(fā)送消息時可調(diào)用用V V操作。若調(diào)用操作。若調(diào)用V V操作之前操作之前S=0S=0，表示消息產(chǎn)生且無等待，表示消息產(chǎn)生且無等待消息進(jìn)程，這是調(diào)用消息進(jìn)程，這是調(diào)用V(S),V(S),執(zhí)行執(zhí)行S:=S+1S:=S+1使使S0S0，意味著消，意味著消息已存在。若調(diào)用息已存在。若調(diào)用V V操作之前操作之前S S0 0，表示消息未產(chǎn)生前已，表示消息未產(chǎn)生前已有進(jìn)程在等待消息，這是調(diào)用有進(jìn)程在等待消息，這是調(diào)用V(

30、S)V(S)后釋放一個等待消息者，后釋放一個等待消息者，即表示該進(jìn)程等待的消息已經(jīng)到達(dá)可以繼續(xù)執(zhí)行。即表示該進(jìn)程等待的消息已經(jīng)到達(dá)可以繼續(xù)執(zhí)行。軟件設(shè)計師軟件設(shè)計師beginbeginBufferBuffer：integerinteger；SP,SG:semaphoreSP,SG:semaphore；SP:=1; SG:=0;SP:=1; SG:=0;CobeginCobegin PROCESS Producer PROCESS Producerbeginbegin L1 L1：produce a productproduce a product P P（SPSP）；）； BufferBuff

31、er：=product=product； V V（SGSG）；）； gotogoto L1 L1EndEnd；PROCESS ConsumerPROCESS Consumerbeginbegin L2 L2： P P（SGSG）；）； take a product from buffertake a product from buffer； V V（SPSP）；）； consumeconsume goto goto L2 L2EndEnd；CoendCoend；EndEnd；軟件設(shè)計師軟件設(shè)計師【軟件設(shè)計師考試【軟件設(shè)計師考試20042004年年5 5月上午試題月上午試題23-2423-24】

32、 若有一個倉庫，可以存放若有一個倉庫，可以存放P1P1、P2P2兩種產(chǎn)品，但是每次只能兩種產(chǎn)品，但是每次只能存放一種產(chǎn)品要求：存放一種產(chǎn)品要求： w=P1 w=P1的數(shù)量的數(shù)量-P2-P2的數(shù)量的數(shù)量 -iwk (i -iwk (i、k k為正整數(shù)為正整數(shù)) )若用若用PVPV操作實(shí)現(xiàn)操作實(shí)現(xiàn)P1P1和和P2P2產(chǎn)品的入庫過程，至少需產(chǎn)品的入庫過程，至少需(23) (23) 個同個同步信號量及步信號量及 (24) (24) 個互斥信號量，其中，同步信號量的初個互斥信號量，其中，同步信號量的初值分別為值分別為 (25) (25) ，互斥信號量的初值分別為，互斥信號量的初值分別為 (26) (26

33、) 。(23)A(23)A0 0B B1 1C C2 2 D D3 3(24)A(24)A0 0B B1 1C C2 2 D D3 3(25)A(25)A0 0B Bi,k,0i,k,0C Ci,ki,k D Di-1,k-1 i-1,k-1 (26)A(26)A1 1B B1,11,1C C1,1,1 1,1,1 D Di,ki,k 軟件設(shè)計師軟件設(shè)計師【軟件設(shè)計師考試【軟件設(shè)計師考試20042004年年5 5月上午試題月上午試題23-2423-24】 在某超市里有一個收銀員，且同時最多允許有在某超市里有一個收銀員，且同時最多允許有n n個顧客個顧客購物，我們可以將顧客和收銀員看成是兩類不同

34、的進(jìn)程，且購物，我們可以將顧客和收銀員看成是兩類不同的進(jìn)程，且工作流程如下圖所示。為了利用工作流程如下圖所示。為了利用PVPV操作正確地協(xié)調(diào)這兩類進(jìn)操作正確地協(xié)調(diào)這兩類進(jìn)程之間的工作，設(shè)置了三個信號量程之間的工作，設(shè)置了三個信號量S1S1、S2S2和和SnSn，且初值分別，且初值分別為為0 0、0 0和和n n。這樣圖中的。這樣圖中的a a應(yīng)填寫應(yīng)填寫_(24)_(24)_，圖中的，圖中的b1b1、b2b2應(yīng)應(yīng)分別填寫分別填寫_(25)_(25)_，圖中的，圖中的c1c1、c2c2應(yīng)分別填寫應(yīng)分別填寫_(26)_(26)_。 軟件設(shè)計師軟件設(shè)計師軟件設(shè)計師軟件設(shè)計師(24)A. P(S1) (

35、24)A. P(S1) B BP(S2)P(S2) C CP(SnP(Sn) ) D DP(SnP(Sn) )、 P(S1)P(S1)(25)A(25)AP(SnP(Sn) )、V(S2) V(S2) B BP(SnP(Sn) )、 V(S1)V(S1) C CP(S2)P(S2)、 V(S1) V(S1) D DV(S1)V(S1)、 P(S2)P(S2)(26)A(26)AP(S1)P(S1)、V(S2) V(S2) B BP(SnP(Sn) )、 V(S1) V(S1) C CP(S2)P(S2)、 V(S1) V(S1) D DV(S1)V(S1)、 P(S2)P(S2)軟件設(shè)計師軟件

36、設(shè)計師l死鎖死鎖 死鎖的概念死鎖的概念 死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因 死鎖的必要條件死鎖的必要條件 處理死鎖的基本方法處理死鎖的基本方法軟件設(shè)計師軟件設(shè)計師進(jìn)程P2掃描儀打印機(jī)進(jìn)程P1 T1 request( T1 request(打印機(jī)打印機(jī)) )； request(request(掃描儀掃描儀) )； T2 holding T2 holding 打印機(jī)；打印機(jī)； holding holding 掃描儀掃描儀時刻時刻 進(jìn)程進(jìn)程P P1 1 進(jìn)程進(jìn)程P P2 2 T3 request(T3 request(掃描儀掃描儀) )； T4 T4 request ( request (打印機(jī)打印機(jī))

37、)；軟件設(shè)計師軟件設(shè)計師 死鎖的概念：死鎖的概念： 指多個進(jìn)程因指多個進(jìn)程因競爭資源競爭資源而造成的一種僵而造成的一種僵局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能局，若無外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)再向前推進(jìn)。死鎖的基本概念 軟件設(shè)計師軟件設(shè)計師 死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因 (1)(1)競爭資源競爭資源 當(dāng)系統(tǒng)中供多個進(jìn)程所共享的資源當(dāng)系統(tǒng)中供多個進(jìn)程所共享的資源, ,不足以同時滿足不足以同時滿足它們的需要時它們的需要時, ,引起它們對資源的競爭而產(chǎn)生死鎖。引起它們對資源的競爭而產(chǎn)生死鎖。 (2) (2) 進(jìn)程推進(jìn)順序不當(dāng)進(jìn)程推進(jìn)順序不當(dāng) 進(jìn)程在運(yùn)行過程中進(jìn)程在運(yùn)行過程中, ,請求和

38、釋放資源的順序不當(dāng)請求和釋放資源的順序不當(dāng), ,導(dǎo)致導(dǎo)致了進(jìn)程的死鎖。了進(jìn)程的死鎖。軟件設(shè)計師軟件設(shè)計師掃描儀進(jìn)程P1打印機(jī)進(jìn)程P2軟件設(shè)計師軟件設(shè)計師 死鎖產(chǎn)生的必要條件死鎖產(chǎn)生的必要條件 (1)(1)互斥使用資源互斥使用資源 (2)(2)占有并等待資源占有并等待資源 (3)(3)不可剝奪資源不可剝奪資源 (4)(4)循環(huán)等待資源循環(huán)等待資源進(jìn)程P2掃描儀打印機(jī)進(jìn)程P1死死 鎖鎖軟件設(shè)計師軟件設(shè)計師l 處理死鎖的基本方法處理死鎖的基本方法 預(yù)防死鎖預(yù)防死鎖 避免死鎖避免死鎖 銀行家算法銀行家算法 檢測死鎖檢測死鎖 解除死鎖解除死鎖軟件設(shè)計師軟件設(shè)計師 避免死鎖避免死鎖 銀行家算法銀行家算法

39、【基本步驟【基本步驟】 (1)(1)進(jìn)程首次申請時，測試該進(jìn)程對資源的最大需求量，進(jìn)程首次申請時，測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配，否則推遲。申請量分配，否則推遲。 (2)(2)當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程已占當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量，若超過了則拒絕。資源的最大需求量，若超過了則拒絕。軟件設(shè)計師軟件設(shè)計師(3)(3)若沒有超過則再測試系統(tǒng)

40、現(xiàn)存的資源能否滿足該進(jìn)程若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足按當(dāng)前的申請量分配資源，尚需的最大資源量，若能滿足按當(dāng)前的申請量分配資源，否則也要推遲分配。否則也要推遲分配。(4)(4)這樣，能保證在任何時刻至少有一個進(jìn)程可以得到所這樣，能保證在任何時刻至少有一個進(jìn)程可以得到所需要的全部資源而執(zhí)行到結(jié)束，執(zhí)行結(jié)束后歸還的資源加需要的全部資源而執(zhí)行到結(jié)束，執(zhí)行結(jié)束后歸還的資源加入到系統(tǒng)的剩余資源中，這些資源又至少可以滿足一個進(jìn)入到系統(tǒng)的剩余資源中，這些資源又至少可以滿足一個進(jìn)程的最大需求，最終保證了所有進(jìn)程都能在有限的時間內(nèi)程的最大需求，最終保證了所有進(jìn)程都能在有

41、限的時間內(nèi)得到需要的全部資源。得到需要的全部資源。軟件設(shè)計師軟件設(shè)計師【基本思想【基本思想】 銀行家算法是通過動態(tài)地檢測系統(tǒng)中資源分配情況銀行家算法是通過動態(tài)地檢測系統(tǒng)中資源分配情況和進(jìn)程對資源的需求情況來決定如何分配資源的，在和進(jìn)程對資源的需求情況來決定如何分配資源的，在能確保系統(tǒng)處于安全狀態(tài)時才能把資源分配給申請者，能確保系統(tǒng)處于安全狀態(tài)時才能把資源分配給申請者，從而避免系統(tǒng)發(fā)生死鎖。從而避免系統(tǒng)發(fā)生死鎖。軟件設(shè)計師軟件設(shè)計師【軟件設(shè)計師考試【軟件設(shè)計師考試20072007年年1111月上午試題月上午試題】 某系統(tǒng)中有四種互斥資源某系統(tǒng)中有四種互斥資源R1R1、R2R2、R3R3和和R4R

42、4，可用資源數(shù)，可用資源數(shù)分別為分別為3 3、5 5、6 6和和8 8。假設(shè)在。假設(shè)在T0T0時刻有時刻有P1P1、P2P2、P3P3和和P4 P4 四個四個進(jìn)程，并且這些進(jìn)程對資源的最大需求量和已分配資源數(shù)如進(jìn)程，并且這些進(jìn)程對資源的最大需求量和已分配資源數(shù)如下表所示，那么在下表所示，那么在T0T0時刻系統(tǒng)中時刻系統(tǒng)中R1R1、R2R2、R3R3和和R4R4的剩余資源的剩余資源數(shù)分別為數(shù)分別為 （2525） 。如果從。如果從T0T0時刻開始進(jìn)程按時刻開始進(jìn)程按 （2626） 順序順序逐個調(diào)度執(zhí)行，那么系統(tǒng)狀態(tài)是安全的。逐個調(diào)度執(zhí)行，那么系統(tǒng)狀態(tài)是安全的。軟件設(shè)計師軟件設(shè)計師最大需求量最大需求

43、量 已分配資源數(shù)已分配資源數(shù)R1R1R2R2R4R4R3R3R1R1R2R2R3R3R4R4P1P11 12 23 36 61 11 12 24 4P2P21 11 12 22 20 01 12 22 2P3P31 12 21 11 11 11 11 10 0P4P41 11 12 23 31 11 11 11 1資源資源請求請求 系統(tǒng)可用資源數(shù)為系統(tǒng)可用資源數(shù)為: : 3 5 6 8 已分配資源數(shù)為：已分配資源數(shù)為： 3 4 6 7 系統(tǒng)剩余資源數(shù)為：系統(tǒng)剩余資源數(shù)為：0 1 0 1軟件設(shè)計師軟件設(shè)計師尚需資源尚需資源 已分配資源數(shù)已分配資源數(shù)R1R1R2R2R4R4R3R3R1R1R2R2R3R3R4R4P1P10 01 11 12 21 11 12 24 4P2P21 10 00 00 00 01 12 22 2P3P30 01 10 01 11 11 11 10 0P4P40 00 01 12 21 11 11 11 1資源資源請求請求系統(tǒng)剩余資源數(shù)為：系統(tǒng)剩余資源數(shù)為：0 1 0 1P3P