第3章進(jìn)程和處理機(jī)管理

1、q清華大學(xué)出版社清華大學(xué)出版社 計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)Computer Operating System主主 編：編：劉騰紅劉騰紅 駱正華駱正華 主主 講：講： 潘林森潘林森 2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2 2重重 慶慶 師師 范范 大大 學(xué)學(xué)第第3章章 進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理q 3.1 進(jìn)程的基本概念進(jìn)程的基本概念q 3.2 進(jìn)程管理進(jìn)程管理q 3.3 線程的概念線程的概念q 3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥q 3.5進(jìn)程通信進(jìn)程通信q 3.6死鎖死鎖q 3.7處理機(jī)調(diào)度處理機(jī)調(diào)度q 3.8Windows XP的進(jìn)

2、程和線程管理的進(jìn)程和線程管理2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3 3重重 慶慶 師師 范范 大大 學(xué)學(xué)3.1.1 程序順序執(zhí)行程序順序執(zhí)行 1. 1. 程序順序執(zhí)行程序順序執(zhí)行 程序在處理機(jī)上的執(zhí)行是嚴(yán)格按序的，即前一個操程序在處理機(jī)上的執(zhí)行是嚴(yán)格按序的，即前一個操作結(jié)束后，才開始后繼操作。作結(jié)束后，才開始后繼操作。3.1 進(jìn)程的基本概念進(jìn)程的基本概念I(lǐng)1 作業(yè)作業(yè)1 作業(yè)作業(yè)2 .C1P1I2C2P22. 2. 程序順序執(zhí)行的特點(diǎn)程序順序執(zhí)行的特點(diǎn) (1)(1)順序性順序性 (2) (2)封閉性封閉性 (3) (3)可再現(xiàn)性可再現(xiàn)性2022年6月3

3、0日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:4 4重重 慶慶 師師 范范 大大 學(xué)學(xué)3.1.2 程序并發(fā)執(zhí)行程序并發(fā)執(zhí)行 1.1.程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 程序在處理機(jī)上的執(zhí)行時間程序在處理機(jī)上的執(zhí)行時間是交叉重疊的，是提高是交叉重疊的，是提高CPUCPU利用率而采取的一種同步利用率而采取的一種同步操作技術(shù)。操作技術(shù)。如圖： I3I3、C2C2、P1P1是并發(fā)執(zhí)行的是并發(fā)執(zhí)行的. . 多道程序系統(tǒng)中，程序在處多道程序系統(tǒng)中，程序在處理機(jī)上的執(zhí)行過程是動態(tài)理機(jī)上的執(zhí)行過程是動態(tài)的、隨機(jī)得、不可預(yù)測的。的、隨機(jī)得、不可預(yù)測的。3.1 進(jìn)程的基本概念進(jìn)程的基本概念I(lǐng)2C2P2I

4、3C3P3I4C4P4I1C1P1圖圖 程序段并發(fā)執(zhí)行程序段并發(fā)執(zhí)行2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:5 5重重 慶慶 師師 范范 大大 學(xué)學(xué)程序并發(fā)執(zhí)行程序并發(fā)執(zhí)行的描述：的描述： S S0 0 / /* * 并發(fā)執(zhí)行前的語句并發(fā)執(zhí)行前的語句 * */ / COBEGINCOBEGIN P P1 1 ;P ;P2 2 ; ;P Pn n; ; / /* *并發(fā)程序段并發(fā)程序段 * */ / COEND COEND S Sn n / /* *并發(fā)執(zhí)行后的語句并發(fā)執(zhí)行后的語句 * */ /例例 前面的并發(fā)執(zhí)行使用下面語句描述前面的并發(fā)執(zhí)行使用下面語句描

5、述 cobegincobegin I3; I3; C2; C2; P1; P1; coendcoend; ;3.1 進(jìn)程的基本概念進(jìn)程的基本概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:6 6重重 慶慶 師師 范范 大大 學(xué)學(xué)3.1 進(jìn)程的基本概念進(jìn)程的基本概念例例 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 設(shè)程序設(shè)程序A A 執(zhí)行執(zhí)行 a1,a2,a3; a1,a2,a3; 程序程序B B 執(zhí)行執(zhí)行 b1,b2,b3.b1,b2,b3. 若在若在CPUCPU上執(zhí)行是上執(zhí)行是 a a1 1 a a2 2 a a3 3 b b1 1 b b2 2 b b3 3 , ,則稱

6、則稱程序程序A A、B B是是順序執(zhí)行的順序執(zhí)行的； 若在若在CPUCPU上執(zhí)行是上執(zhí)行是 a a1 1 b b1 1 a a2 2 b b2 2 a a3 3 b b3 3 , ,則稱則稱程序程序A A、B B是是并發(fā)執(zhí)行的并發(fā)執(zhí)行的；2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7 7重重 慶慶 師師 范范 大大 學(xué)學(xué) 2. 2. 程序并發(fā)執(zhí)行的特點(diǎn)程序并發(fā)執(zhí)行的特點(diǎn) (1) (1)失去了程序的封閉性失去了程序的封閉性 程序之間的相互制約關(guān)系程序之間的相互制約關(guān)系( (間接關(guān)系和直接間接關(guān)系和直接關(guān)系關(guān)系) )導(dǎo)致程序?qū)е鲁绦颉皥?zhí)行執(zhí)行-暫停暫停-執(zhí)行執(zhí)行”

7、，即，即程序的執(zhí)行具有程序的執(zhí)行具有間斷性間斷性。如下頁例子如下頁例子 (2) (2) 通信性通信性: :如圖如圖3-33-3 (3) (3) 獨(dú)立性獨(dú)立性3.1 進(jìn)程的基本概念進(jìn)程的基本概念BCA圖3-3 并發(fā)進(jìn)程間的通信2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:8 8重重 慶慶 師師 范范 大大 學(xué)學(xué)飛機(jī)訂票系統(tǒng)例子 設(shè)某航班票數(shù)為設(shè)某航班票數(shù)為x,x,有兩個終端有兩個終端T1(x)T1(x)、T2(x)T2(x)同時售票。同時售票。 則則 COBEGINCOBEGIN Process T1(x); Process T1(x); Process T2(x

8、); Process T2(x); COENDCOEND2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:9 9重重 慶慶 師師 范范 大大 學(xué)學(xué) Process T1(x); Process T2(x);Process T1(x); Process T2(x); Read(x); Read(x); Read(x); Read(x); if x1 then x=x-1; if x1 then x=x-1; if x1 if x1 thenxthenx=x-1;=x-1; write(xwrite(x); ); write(xwrite(x);); 設(shè)某時刻設(shè)某時刻x

9、 x1 1，按按執(zhí)行執(zhí)行, ,則導(dǎo)致一張票售了兩次。則導(dǎo)致一張票售了兩次。 T1T1：read(x) x=x-1 write(x)read(x) x=x-1 write(x) X=1 x=0 x=0 X=1 x=0 x=0 t t T2T2： read(x) x=x-1 write(x) read(x) x=x-1 write(x) X=1 x=0 x=0 X=1 x=0 x=0飛機(jī)訂票系統(tǒng)例子2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1010 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.1.3 進(jìn)程描述進(jìn)程描述 1.1. 進(jìn)程定義進(jìn)程定義 最能反映進(jìn)程實(shí)質(zhì)的定義

10、有： 1 1）進(jìn)程是程序的一次執(zhí)行活動；）進(jìn)程是程序的一次執(zhí)行活動； 2 2）進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算；）進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算； 3 3）進(jìn)程是一個程序在對應(yīng)數(shù)據(jù)結(jié)構(gòu)上的進(jìn)行的操作；）進(jìn)程是一個程序在對應(yīng)數(shù)據(jù)結(jié)構(gòu)上的進(jìn)行的操作； 4 4）所謂進(jìn)程，就是一個程序在給定活動空間和初始環(huán)境下，在）所謂進(jìn)程，就是一個程序在給定活動空間和初始環(huán)境下，在一個處理機(jī)上的執(zhí)行過程；一個處理機(jī)上的執(zhí)行過程； 5 5）進(jìn)程是程序在一個數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)程資）進(jìn)程是程序在一個數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)程資源分配和調(diào)度的一個獨(dú)立單位。源分配和調(diào)度的一個獨(dú)立單位。 國內(nèi)的定義

11、：國內(nèi)的定義：進(jìn)程是一個具有一定獨(dú)立功能的程進(jìn)程是一個具有一定獨(dú)立功能的程序，是關(guān)于某個數(shù)據(jù)集合的一次運(yùn)行活動。序，是關(guān)于某個數(shù)據(jù)集合的一次運(yùn)行活動。3.1 進(jìn)程的基本概念進(jìn)程的基本概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1111 重重 慶慶 師師 范范 大大 學(xué)學(xué)進(jìn)程和程序的聯(lián)系和區(qū)別進(jìn)程和程序的聯(lián)系和區(qū)別: : 進(jìn)程是動態(tài)的；程序是靜態(tài)的；進(jìn)程是動態(tài)的；程序是靜態(tài)的； 進(jìn)程具有并發(fā)特征；程序不具有；進(jìn)程具有并發(fā)特征；程序不具有； 進(jìn)程是分配資源的單位；程序是功能實(shí)現(xiàn)的步驟；進(jìn)程是分配資源的單位；程序是功能實(shí)現(xiàn)的步驟； 不同進(jìn)程可包含同一程序。不同進(jìn)

12、程可包含同一程序。引入進(jìn)程的目的引入進(jìn)程的目的為了控制和協(xié)調(diào)并發(fā)程序執(zhí)行過程中對資源的共享和競爭。為了控制和協(xié)調(diào)并發(fā)程序執(zhí)行過程中對資源的共享和競爭。 為了有一個描述程序執(zhí)行過程和共享資源的基本單位。為了有一個描述程序執(zhí)行過程和共享資源的基本單位。 3.1 進(jìn)程的基本概念進(jìn)程的基本概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1212 重重 慶慶 師師 范范 大大 學(xué)學(xué)2.2. 進(jìn)程類型進(jìn)程類型 (1)系統(tǒng)進(jìn)程系統(tǒng)進(jìn)程和用戶進(jìn)程用戶進(jìn)程 (2)計(jì)算進(jìn)程計(jì)算進(jìn)程和I/OI/O進(jìn)程進(jìn)程系統(tǒng)進(jìn)程系統(tǒng)進(jìn)程和和用戶進(jìn)程兩者的區(qū)別用戶進(jìn)程兩者的區(qū)別: : 1)1)系統(tǒng)進(jìn)

13、程被分配一個初始的資源集合，其可以系統(tǒng)進(jìn)程被分配一個初始的資源集合，其可以獨(dú)占或按最高優(yōu)先權(quán)限優(yōu)先使用這些資源。但用獨(dú)占或按最高優(yōu)先權(quán)限優(yōu)先使用這些資源。但用戶進(jìn)程必須通過系統(tǒng)服務(wù)請求來申請資源，并競戶進(jìn)程必須通過系統(tǒng)服務(wù)請求來申請資源，并競爭資源爭資源 2 2）用戶進(jìn)程不能直接完成）用戶進(jìn)程不能直接完成I/OI/O操作，而系統(tǒng)進(jìn)程操作，而系統(tǒng)進(jìn)程可以做顯示的、直接的可以做顯示的、直接的I/OI/O操作操作 3 3）系統(tǒng)進(jìn)程在管態(tài)下運(yùn)行，而用戶進(jìn)程在目態(tài)下）系統(tǒng)進(jìn)程在管態(tài)下運(yùn)行，而用戶進(jìn)程在目態(tài)下運(yùn)行運(yùn)行3.1 進(jìn)程的基本概念進(jìn)程的基本概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和

14、處理機(jī)管理 NO:NO:1313 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.3. 進(jìn)程的特征和利弊進(jìn)程的特征和利弊 特征：特征： 1 1）動態(tài)性）動態(tài)性 2 2）并發(fā)性）并發(fā)性 3 3）獨(dú)立性）獨(dú)立性 4 4）異步性）異步性/ /間斷性間斷性 5 5）結(jié)構(gòu)特征）結(jié)構(gòu)特征 引入進(jìn)程增加開銷：引入進(jìn)程增加開銷： 1 1）空間開銷）空間開銷 2 2）時間開銷）時間開銷3.1 進(jìn)程的基本概念進(jìn)程的基本概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1414 重重 慶慶 師師 范范 大大 學(xué)學(xué)4.4. 進(jìn)程的狀態(tài)與變遷進(jìn)程的狀態(tài)與變遷 進(jìn)程的三種基本狀態(tài)及其狀態(tài)變遷如圖進(jìn)程

15、的三種基本狀態(tài)及其狀態(tài)變遷如圖3-43-4就緒就緒執(zhí)行執(zhí)行 因調(diào)度而執(zhí)行因調(diào)度而執(zhí)行執(zhí)行執(zhí)行就緒就緒 時間片用完而落選時間片用完而落選執(zhí)行執(zhí)行等待等待 因等待事件而阻塞因等待事件而阻塞等待等待就緒就緒 事件發(fā)生而喚醒事件發(fā)生而喚醒3.1 進(jìn)程的基本概念進(jìn)程的基本概念終止終止初始初始2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1515 重重 慶慶 師師 范范 大大 學(xué)學(xué)5.5. 進(jìn)程控制塊進(jìn)程控制塊PCBPCB 1) 1)PCBPCB的作用的作用 標(biāo)識進(jìn)程存在的唯一實(shí)體標(biāo)識進(jìn)程存在的唯一實(shí)體 2 2）進(jìn)程控制塊的內(nèi)容）進(jìn)程控制塊的內(nèi)容（如表（如表3-13-1）進(jìn)

16、程控制塊中主要包括進(jìn)程控制塊中主要包括: : 進(jìn)程的描述信息進(jìn)程的描述信息; ; 進(jìn)程的控制信息進(jìn)程的控制信息; ; 資源管理信息資源管理信息; ; CPUCPU現(xiàn)場保護(hù)信息?，F(xiàn)場保護(hù)信息。3 3）PCBPCB的組織方式的組織方式 a)a)鏈接方式如圖鏈接方式如圖3-53-5 b) b)索引方式如圖索引方式如圖3-63-63.1 進(jìn)程的基本概念進(jìn)程的基本概念進(jìn)程標(biāo)識符進(jìn)程標(biāo)識符進(jìn)程當(dāng)前狀態(tài)進(jìn)程當(dāng)前狀態(tài)現(xiàn)場保護(hù)區(qū)現(xiàn)場保護(hù)區(qū)程序和數(shù)據(jù)地址程序和數(shù)據(jù)地址進(jìn)程優(yōu)先級進(jìn)程優(yōu)先級資源清單資源清單進(jìn)程通信信息進(jìn)程通信信息互斥和同步機(jī)構(gòu)互斥和同步機(jī)構(gòu)家族聯(lián)系家族聯(lián)系鏈接字鏈接字總鏈指針總鏈指針 表3-1 PC

17、B信息 表3-1 PCB信息 2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1616 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.1 進(jìn)程的基本概念進(jìn)程的基本概念 表3-1 PCB信息 PCB1PCB12 2PCB2PCB23 3PCB3PCB34 4PCB4PCB41313PCB5PCB56 6PCB6PCB67 7PCB7PCB79 9PCB8PCB8PCB9PCB91010PCB10PCB10PCB11PCB111212PCB12PCB12i iPCB13PCB13就緒指針執(zhí)行指針等待指針空閑指針圖3-5 按鏈接方式組織PCB2022年6月30日星期四第3章進(jìn)程

18、和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1717 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.1 進(jìn)程的基本概念進(jìn)程的基本概念就緒指針等待指針空閑指針1 12 23 34 413135 56 67 79 9101011111212PCB1PCB1PCB2PCB2PCB3PCB3PCB4PCB4PCB5PCB5PCB6PCB6PCB7PCB7PCB8PCB8PCB9PCB9PCB10PCB10PCB11PCB11PCB12PCB12PCB13PCB13索 引 表圖3-6 按索引方式組織PCB2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1818 重重 慶慶 師師 范范

19、 大大 學(xué)學(xué)操作系統(tǒng)使用一組原語操作實(shí)現(xiàn)進(jìn)程管理。操作系統(tǒng)使用一組原語操作實(shí)現(xiàn)進(jìn)程管理。原語原語 具有特定功能的程序段或指令，執(zhí)行時不可中具有特定功能的程序段或指令，執(zhí)行時不可中斷，是不可分割的基本單位。斷，是不可分割的基本單位。操作系統(tǒng)使用的主要原語有：操作系統(tǒng)使用的主要原語有： 創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語。創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語。3.2 進(jìn)程管理進(jìn)程管理2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:1919 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.2.1 進(jìn)程創(chuàng)建原語進(jìn)程創(chuàng)建原語由系統(tǒng)程序或父進(jìn)程調(diào)用創(chuàng)建原語實(shí)現(xiàn)。分三步完成：由系統(tǒng)

20、程序或父進(jìn)程調(diào)用創(chuàng)建原語實(shí)現(xiàn)。分三步完成： 從從PCBPCB鏈表中取下一個空鏈表中取下一個空PCB;PCB; 填入有關(guān)參數(shù)，形成代表進(jìn)程的填入有關(guān)參數(shù)，形成代表進(jìn)程的PCBPCB結(jié)構(gòu)；結(jié)構(gòu)； 將其插入就緒進(jìn)程隊(duì)列。將其插入就緒進(jìn)程隊(duì)列。創(chuàng)建原語描述如下：創(chuàng)建原語描述如下：3.2 進(jìn)程管理進(jìn)程管理算法：算法：create輸入：新進(jìn)程的符號名，優(yōu)先級，開始執(zhí)行地址輸入：新進(jìn)程的符號名，優(yōu)先級，開始執(zhí)行地址輸出：新創(chuàng)建進(jìn)程的內(nèi)部標(biāo)識符輸出：新創(chuàng)建進(jìn)程的內(nèi)部標(biāo)識符PID在總鏈隊(duì)列上查找有無同名的進(jìn)程；在總鏈隊(duì)列上查找有無同名的進(jìn)程；if (有同名進(jìn)程有同名進(jìn)程) return （錯誤碼）（錯誤碼） /

21、*帶錯誤碼返回帶錯誤碼返回*/在空閑在空閑PCB隊(duì)列申請一個空閑的隊(duì)列申請一個空閑的PCB結(jié)構(gòu)；結(jié)構(gòu)；if (無空無空PCB結(jié)構(gòu)結(jié)構(gòu)) return （錯誤碼）；（錯誤碼）； /*帶錯誤碼返回帶錯誤碼返回*/用參數(shù)填充用參數(shù)填充PCB內(nèi)容；內(nèi)容；置進(jìn)程為就緒狀態(tài)；置進(jìn)程為就緒狀態(tài)；將新進(jìn)程的將新進(jìn)程的PCB插入到就緒隊(duì)列；插入到就緒隊(duì)列；將新進(jìn)程的將新進(jìn)程的PCB插入到總鏈隊(duì)列中；插入到總鏈隊(duì)列中；設(shè)置進(jìn)程的家族關(guān)系；設(shè)置進(jìn)程的家族關(guān)系；return （新進(jìn)程（新進(jìn)程PID）；）； /* create(name, priority, start-addr) */2022年6月30日星期四第3章

22、進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2020 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.2.2 進(jìn)程撤消原語進(jìn)程撤消原語 分三步完成：分三步完成： 從進(jìn)程鏈表中取下一個從進(jìn)程鏈表中取下一個PCB; 釋放進(jìn)程占有的資源；釋放進(jìn)程占有的資源； 釋放進(jìn)程的釋放進(jìn)程的PCB結(jié)構(gòu)。結(jié)構(gòu)。撤消原語撤消原語KillKill操作如下：操作如下：3.2 進(jìn)程管理進(jìn)程管理void kill輸入：進(jìn)程標(biāo)識符輸入：進(jìn)程標(biāo)識符PID輸出：無輸出：無 由參數(shù)由參數(shù)PID查找到當(dāng)前進(jìn)程的查找到當(dāng)前進(jìn)程的PCB； 釋放本進(jìn)程所占用的資源給父進(jìn)程；釋放本進(jìn)程所占用的資源給父進(jìn)程； 將該進(jìn)程從總鏈隊(duì)列中摘除；將該進(jìn)程從總鏈

23、隊(duì)列中摘除；釋放此釋放此PCB結(jié)構(gòu)；結(jié)構(gòu)；釋放所占用的資源；釋放所占用的資源；轉(zhuǎn)進(jìn)程調(diào)度程序；轉(zhuǎn)進(jìn)程調(diào)度程序； /* kill */2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2121 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.2.3 進(jìn)程等待原語進(jìn)程等待原語 將處于執(zhí)行態(tài)的進(jìn)程置入等待隊(duì)列。將處于執(zhí)行態(tài)的進(jìn)程置入等待隊(duì)列。 由執(zhí)行進(jìn)程自己或系統(tǒng)父進(jìn)程調(diào)用阻塞原語完成。由執(zhí)行進(jìn)程自己或系統(tǒng)父進(jìn)程調(diào)用阻塞原語完成。等待原語操作過程如下：等待原語操作過程如下：3.2 進(jìn)程管理進(jìn)程管理void void suspsusp( (chanchan) )輸入：輸入：chanc

24、han / /* *等待的事件（等待原因）等待的事件（等待原因）* */ / 保護(hù)現(xiàn)行進(jìn)程保護(hù)現(xiàn)行進(jìn)程CPUCPU現(xiàn)場到現(xiàn)場到PCBPCB結(jié)構(gòu)中；結(jié)構(gòu)中； 置該進(jìn)程為置該進(jìn)程為“等待等待/ /阻塞阻塞”態(tài)；態(tài)； 將該進(jìn)程將該進(jìn)程PCBPCB插入到等插入到等chanchan的等待隊(duì)列；的等待隊(duì)列； 轉(zhuǎn)進(jìn)程調(diào)度；轉(zhuǎn)進(jìn)程調(diào)度； / /* * suspsusp( (chanchan) ) * */ /2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2222 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.2.4 進(jìn)程喚醒原語進(jìn)程喚醒原語 從等待進(jìn)程隊(duì)列中摘下被喚醒的進(jìn)程置入就緒隊(duì)列

25、。從等待進(jìn)程隊(duì)列中摘下被喚醒的進(jìn)程置入就緒隊(duì)列。 由事件發(fā)生進(jìn)程或系統(tǒng)進(jìn)程調(diào)用喚醒原語完成。由事件發(fā)生進(jìn)程或系統(tǒng)進(jìn)程調(diào)用喚醒原語完成。喚醒原語操作過程如下：喚醒原語操作過程如下：3.2 進(jìn)程管理進(jìn)程管理void wakeup(chan) 輸入：輸入：chan /*等待的事件（等待原因）等待的事件（等待原因）*/輸出：無輸出：無 保護(hù)現(xiàn)行運(yùn)行進(jìn)程的保護(hù)現(xiàn)行運(yùn)行進(jìn)程的CPU現(xiàn)場到它的現(xiàn)場到它的PCB結(jié)構(gòu)中；結(jié)構(gòu)中； 置該進(jìn)程為就緒狀態(tài)；置該進(jìn)程為就緒狀態(tài)； 將該進(jìn)程插入就緒隊(duì)列；將該進(jìn)程插入就緒隊(duì)列； 找到該阻塞原因的隊(duì)列指針；找到該阻塞原因的隊(duì)列指針； for(該隊(duì)列上的每一個等待進(jìn)程該隊(duì)列上的

26、每一個等待進(jìn)程) 將進(jìn)程移出此等待隊(duì)列；將進(jìn)程移出此等待隊(duì)列；置進(jìn)程狀態(tài)為置進(jìn)程狀態(tài)為“就緒就緒”并將進(jìn)程放入就緒隊(duì)列；并將進(jìn)程放入就緒隊(duì)列； 轉(zhuǎn)進(jìn)程調(diào)度；轉(zhuǎn)進(jìn)程調(diào)度； /* wakeup(chan) */2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2323 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.2.5 其他原語其他原語1.進(jìn)程延遲原語和延遲喚醒原語 延遲原語的功能是：將需要延遲的進(jìn)程PCB結(jié)構(gòu)加入到延遲隊(duì)列，當(dāng)延遲時間到來時，由延遲喚醒進(jìn)程（系統(tǒng)進(jìn)程）把它喚醒2.進(jìn)程掛起原語和進(jìn)程激活原語 進(jìn)程的掛起狀態(tài)是一種靜止?fàn)顟B(tài)，它分為掛起就緒和掛起等待。3.2 進(jìn)程

27、管理進(jìn)程管理2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2424 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.3.1 線程的概念線程的概念 線程是比進(jìn)程更小的活動單位，它是進(jìn)程內(nèi)一段進(jìn)程內(nèi)一段程序的基本調(diào)度單位。程序的基本調(diào)度單位。 線程可以這樣描述：線程可以這樣描述： 1）線程是進(jìn)程中的一條執(zhí)行路徑； 2）它有自己的私用堆棧和處理機(jī)執(zhí)行環(huán)境（尤其是處理器寄存器）； 3）它與父進(jìn)程共享分配給父進(jìn)程的主存； 4）它是由單個進(jìn)程所創(chuàng)建的眾多線程中的一個線程；3.3 線程的概念線程的概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2525

28、 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.3.2 線程與進(jìn)程的比較線程與進(jìn)程的比較1.1.調(diào)度：調(diào)度：把線程作為調(diào)度和分派的基本單位，而把把線程作為調(diào)度和分派的基本單位，而把進(jìn)程作為資源擁有的基本單位；進(jìn)程作為資源擁有的基本單位；2.2.并發(fā)性：并發(fā)性：不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一不僅進(jìn)程之間可以并發(fā)執(zhí)行，而且在一個進(jìn)程中的多個線程之間也可并發(fā)執(zhí)行；個進(jìn)程中的多個線程之間也可并發(fā)執(zhí)行；3.3.擁有資源：擁有資源：進(jìn)程是擁有資源的一個獨(dú)立單位，線進(jìn)程是擁有資源的一個獨(dú)立單位，線程不擁有系統(tǒng)資源，但可訪問隸屬于進(jìn)程的全部程不擁有系統(tǒng)資源，但可訪問隸屬于進(jìn)程的全部資源；資源；4.4.系統(tǒng)開銷：系

29、統(tǒng)開銷：進(jìn)程大；線程小。進(jìn)程大；線程小。3.3 線程的概念線程的概念2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2626 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.3.3 線程的分類線程的分類 1. 線程的兩種類型 1）內(nèi)核支持線程 2）用戶級線程 2.兩種線程的分析3.3 線程的概念線程的概念比較角度比較角度內(nèi)核支持線程內(nèi)核支持線程用戶級線程用戶級線程線程的調(diào)度與線程的調(diào)度與切換速度切換速度與進(jìn)程的調(diào)度和切換十與進(jìn)程的調(diào)度和切換十分相似分相似切換無須通過中斷進(jìn)入操作系切換無須通過中斷進(jìn)入操作系統(tǒng)的內(nèi)核，切換規(guī)則簡單統(tǒng)的內(nèi)核，切換規(guī)則簡單系統(tǒng)調(diào)用系統(tǒng)調(diào)用把系統(tǒng)調(diào)用

30、只看作是該把系統(tǒng)調(diào)用只看作是該線程的行為線程的行為把系統(tǒng)調(diào)用看做是整個把系統(tǒng)調(diào)用看做是整個進(jìn)程的行為進(jìn)程的行為線程的執(zhí)行線程的執(zhí)行時間時間以進(jìn)程為單位進(jìn)行以進(jìn)程為單位進(jìn)行調(diào)度是以線程為單位進(jìn)行的調(diào)度是以線程為單位進(jìn)行的2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2727 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.1 進(jìn)程間的制約關(guān)系 并發(fā)并發(fā)執(zhí)行執(zhí)行進(jìn)程間存在進(jìn)程間存在2種制約關(guān)系種制約關(guān)系間接制約：間接制約：并發(fā)執(zhí)行程序共享公用資源而引起的執(zhí)并發(fā)執(zhí)行程序共享公用資源而引起的執(zhí)行速度上的制約。（導(dǎo)致進(jìn)程互斥）行速度上的制約。（導(dǎo)致進(jìn)程互斥）直接制約：直接制約：

31、并發(fā)執(zhí)行進(jìn)程共享對方私用資源而引起并發(fā)執(zhí)行進(jìn)程共享對方私用資源而引起的執(zhí)行速度上的制約。（導(dǎo)致進(jìn)程同步）的執(zhí)行速度上的制約。（導(dǎo)致進(jìn)程同步）1.資源共享互斥共享互斥共享同時訪問同時訪問 2.進(jìn)程合作 進(jìn)程相互合作和通信，共同完成一個任務(wù)進(jìn)程相互合作和通信，共同完成一個任務(wù)3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2828 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.2 進(jìn)程互斥進(jìn)程互斥 1. 1. 互斥的概念互斥的概念 不允許兩個或以上共享資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)。不允許兩個或以上共享資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)

32、?；コ夤蚕淼馁Y源互斥共享的資源：物理設(shè)備和軟件資源物理設(shè)備和軟件資源 臨界區(qū)：臨界區(qū)：不允許多個并發(fā)執(zhí)行進(jìn)程交叉執(zhí)行的代碼段。不允許多個并發(fā)執(zhí)行進(jìn)程交叉執(zhí)行的代碼段。臨界資源：臨界資源：一次只允許一個進(jìn)程訪問的資源。一次只允許一個進(jìn)程訪問的資源。 例：例：賦值語句賦值語句 x:=xx:=x1 1 用匯編語言表示：用匯編語言表示： Load Load A,xA,x AddiAddi A,1 A,1 Store Store A,xA,x 臨界區(qū)臨界區(qū)3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:2929 重重 慶慶 師師

33、范范 大大 學(xué)學(xué)3.4.2 進(jìn)程互斥進(jìn)程互斥2. 鎖及其操作置鎖信號W=1稱為上鎖原語（lock），置鎖信號W=0稱為開鎖原語(unlock)，代碼如下所示3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥上鎖原語上鎖原語開鎖原語開鎖原語 void lock(鎖變量鎖變量w) test: if(w為為1) goto test /*測試鎖位的值測試鎖位的值*/ else w=1; /*上鎖上鎖*/ /* lock(w) */ void unlock(鎖變量鎖變量w) w=0; /* 開鎖開鎖 */ /* unlock(w) */2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:N

34、O:3030 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.2 進(jìn)程互斥進(jìn)程互斥2. 2. 鎖及其操作鎖及其操作gotogoto語句使進(jìn)程一直占用處理機(jī)來循環(huán)測試鎖語句使進(jìn)程一直占用處理機(jī)來循環(huán)測試鎖狀態(tài)，故將上鎖原語和開鎖原語改進(jìn)如下狀態(tài)，故將上鎖原語和開鎖原語改進(jìn)如下3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥改進(jìn)后的上鎖原語改進(jìn)后的上鎖原語改進(jìn)后的開鎖原語改進(jìn)后的開鎖原語void lock(鎖變量鎖變量) while(w=1) 保護(hù)現(xiàn)行進(jìn)程保護(hù)現(xiàn)行進(jìn)程CPU現(xiàn)場；現(xiàn)場； 現(xiàn)行進(jìn)程入現(xiàn)行進(jìn)程入w的等待隊(duì)列；的等待隊(duì)列； 置進(jìn)程為置進(jìn)程為“等待等待”狀態(tài)；狀態(tài)； 轉(zhuǎn)進(jìn)程調(diào)度；轉(zhuǎn)進(jìn)程調(diào)度； w=1

35、; /* 上鎖上鎖 */ /* lock(w) */void lock(鎖變量鎖變量) while(w=1) 保護(hù)現(xiàn)行進(jìn)程保護(hù)現(xiàn)行進(jìn)程CPU現(xiàn)場；現(xiàn)場； 現(xiàn)行進(jìn)程入現(xiàn)行進(jìn)程入w的等待隊(duì)列；的等待隊(duì)列； 置進(jìn)程為置進(jìn)程為“等待等待”狀態(tài)；狀態(tài)； 轉(zhuǎn)進(jìn)程調(diào)度；轉(zhuǎn)進(jìn)程調(diào)度； w=1; /* 上鎖上鎖 */ /* lock(w) */2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3131 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.2 進(jìn)程互斥3. 使用鎖實(shí)現(xiàn)進(jìn)程互斥如圖3-7，說明了兩個進(jìn)程使用同一臨界資源時的操作。兩者都必須先執(zhí)行上鎖原語3.4 進(jìn)程間的同步與互斥進(jìn)程

36、間的同步與互斥進(jìn)程進(jìn)程A上鎖原語上鎖原語進(jìn)入進(jìn)入A的臨界區(qū)的臨界區(qū)CSa開鎖原語開鎖原語進(jìn)程進(jìn)程B上鎖原語上鎖原語進(jìn)入進(jìn)入B的臨界區(qū)的臨界區(qū)CSb開鎖原語開鎖原語圖3-7 進(jìn)程使用臨界資源時的操作2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3232 重重 慶慶 師師 范范 大大 學(xué)學(xué)與圖3-7相應(yīng)的進(jìn)程互斥代碼如下：3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥main() int w=0; /系統(tǒng)初啟時置鎖狀態(tài)系統(tǒng)初啟時置鎖狀態(tài) cobegin ppa(); /進(jìn)程進(jìn)程A ppb(); /進(jìn)程進(jìn)程B coend ppa() /進(jìn)程進(jìn)程A ; lock(w);

37、進(jìn)程進(jìn)程A的臨界區(qū)的臨界區(qū)CSa； unlock(w); ; ppb() /進(jìn)程進(jìn)程B ; lock(w); 進(jìn)程進(jìn)程B的臨界區(qū)的臨界區(qū)CSb； unlock(w); ; 2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3333 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.3 信號燈和信號燈和P、V操作操作 1. 1. 信號燈的概念信號燈的概念 1965 1965年荷蘭年荷蘭DijkstraDijkstra提出的進(jìn)程同步工具。提出的進(jìn)程同步工具。 信號燈表示信號燈表示: :二元組（二元組（s,qs,q） 其中：其中：s s具有非負(fù)初值的整型變量，代表資具有非負(fù)初值的

38、整型變量，代表資 源實(shí)體或并發(fā)進(jìn)程的狀態(tài)源實(shí)體或并發(fā)進(jìn)程的狀態(tài); ;q q是一個初始狀是一個初始狀 態(tài)為空的等待隊(duì)列態(tài)為空的等待隊(duì)列信號燈（信號燈（SemaphoreSemaphore） 表示系統(tǒng)中資源實(shí)體數(shù)目或資源使用情況的整型量，表示系統(tǒng)中資源實(shí)體數(shù)目或資源使用情況的整型量，其值只能由其值只能由PVPV原語操作改變。原語操作改變。 按用途信號燈可分為：按用途信號燈可分為： 公用信號燈公用信號燈 用于互斥的信號量。用于互斥的信號量。 私用信號燈私用信號燈 用于同步的信號量。用于同步的信號量。3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理

39、機(jī)管理 NO:NO:3434 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.3 信號燈和信號燈和P、V操作操作2. P2. P、V V操作原語操作原語系統(tǒng)一般提供系統(tǒng)一般提供P P、V V操作原語來修改信號燈的值操作原語來修改信號燈的值如果如果s s表示信號燈表示信號燈( (信號量信號量) )，則，則 1) P 1) P操作操作 P P（s s） 對信號燈進(jìn)行減對信號燈進(jìn)行減1 1操作，再根據(jù)信操作，再根據(jù)信號燈的值對調(diào)用號燈的值對調(diào)用P P操作的進(jìn)程進(jìn)行相應(yīng)處理操作的進(jìn)程進(jìn)行相應(yīng)處理 2) V 2) V操作操作 V V（s s） 對信號燈進(jìn)行加對信號燈進(jìn)行加1 1操作操作, ,再根據(jù)信再根據(jù)信號

40、燈的值進(jìn)行相應(yīng)處理號燈的值進(jìn)行相應(yīng)處理3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3535 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥 設(shè)設(shè)S S為信號量，為信號量，P P操作的動操作的動作定義如下：作定義如下： P(S) P(S) ： 將將S S減減1 1； 若若S S0 0 ，則將調(diào)用則將調(diào)用P(S)P(S)的的進(jìn)程置為等待狀態(tài)；進(jìn)程置為等待狀態(tài)； 若若S0 S0 ，則進(jìn)程繼續(xù)。則進(jìn)程繼續(xù)。 s=s-1 S0S0S0S03.4.3 信號燈和信號燈和P、V操作操作2022年6月3

41、0日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3636 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥 設(shè)設(shè)S S為信號量，為信號量，V V操作的動作定操作的動作定義如下：義如下：V(S) V(S) ： 將將S S加加1 1； 若若S0 S0 ，則喚醒一個等則喚醒一個等待待S S的進(jìn)程；的進(jìn)程； 若若S S0 0 ，則進(jìn)程繼續(xù)。則進(jìn)程繼續(xù)。S S 0 0s=s+1 3.4.3 信號燈和信號燈和P、V操作操作2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:3737 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.4.3 信號燈和

42、信號燈和P、V操作操作3.4 進(jìn)程間的同步與互斥進(jìn)程間的同步與互斥void p(變量變量s) /變量變量s為信號燈為信號燈 s-; if(s0) /進(jìn)程進(jìn)入相應(yīng)的等待隊(duì)列進(jìn)程進(jìn)入相應(yīng)的等待隊(duì)列保留調(diào)用進(jìn)程保留調(diào)用進(jìn)程CPU現(xiàn)場；現(xiàn)場； 將該進(jìn)程進(jìn)入將該進(jìn)程進(jìn)入s的等待隊(duì)列；的等待隊(duì)列； 置置“等待等待”狀態(tài)；狀態(tài)； 轉(zhuǎn)進(jìn)程調(diào)度；轉(zhuǎn)進(jìn)程調(diào)度； /* p(s) */ 1 1）P P操作過程操作過程void v(變量變量s) /變量變量s為信號燈為信號燈 s+; if(s 0 0，表示系統(tǒng)中同類臨，表示系統(tǒng)中同類臨界資源的數(shù)目有界資源的數(shù)目有mutexmutex個；個； 2 2）操作中）操作中mut

43、exmutex 0 0，表示可用的同類臨界資，表示可用的同類臨界資源的數(shù)目為源的數(shù)目為mutexmutex； 3 3）操作中）操作中mutexmutex 同時滿足同時滿足4條條 系統(tǒng)死鎖系統(tǒng)死鎖 同時滿足同時滿足4條條4.4.解決死鎖的基本方法解決死鎖的基本方法1 1）預(yù)防死鎖）預(yù)防死鎖 ； 2 2）避免死鎖）避免死鎖3 3）檢測死鎖；）檢測死鎖； 4 4）解除死鎖）解除死鎖3.6 死鎖死鎖2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:6666 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.6.2 預(yù)防死鎖預(yù)防死鎖1.1.否定條件二否定條件二-不剝奪條件不剝奪條件規(guī)定：

44、規(guī)定：一個已經(jīng)占有了某些資源的進(jìn)程，若申一個已經(jīng)占有了某些資源的進(jìn)程，若申請不到新的資源時，就釋放已經(jīng)占有的資源，請不到新的資源時，就釋放已經(jīng)占有的資源，以后再需要時重新申請。以后再需要時重新申請。 缺點(diǎn)：缺點(diǎn)：要付出很大代價，增加了系統(tǒng)開銷，降要付出很大代價，增加了系統(tǒng)開銷，降低系統(tǒng)吞吐量低系統(tǒng)吞吐量2.2.否定條件三否定條件三-部分分配部分分配在分配資源時，只要有一個資源要求得不到滿在分配資源時，只要有一個資源要求得不到滿足，則該進(jìn)程就不能得到任何資源足，則該進(jìn)程就不能得到任何資源3.6 死鎖死鎖2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:6767 重重

45、慶慶 師師 范范 大大 學(xué)學(xué)3.6.2 預(yù)防死鎖預(yù)防死鎖2.2.否定條件三否定條件三-部分分配部分分配缺點(diǎn)：缺點(diǎn)：方法簡單、容易實(shí)現(xiàn)；但資源嚴(yán)重浪費(fèi)方法簡單、容易實(shí)現(xiàn)；但資源嚴(yán)重浪費(fèi)3.3.否定條件四否定條件四-環(huán)路條件環(huán)路條件資源編號；所有進(jìn)程對資源的請求必須按照資資源編號；所有進(jìn)程對資源的請求必須按照資源序號遞增的次序提出源序號遞增的次序提出缺點(diǎn)：缺點(diǎn)：1 1）限制了新資源的增加；）限制了新資源的增加；2 2）會發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定的）會發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定的順序不同的情況，造成資源浪費(fèi)；順序不同的情況，造成資源浪費(fèi)；3 3）限制了用戶簡單、自由地編程。）限制了用戶

46、簡單、自由地編程。3.6 死鎖死鎖2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:6868 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.6.3 避免死鎖 通過判斷資源分配的安全性分配 安全狀態(tài)：只指系統(tǒng)按照某種進(jìn)程順序（如P1、P2、Pn）為每個進(jìn)程分配資源，直至最大需求，每個進(jìn)程都可以順利完成。若不存在這樣的安全序列，則稱系統(tǒng)處于不安全狀態(tài) 銀行算法是Dijkstra.E.W1968年提出的一種避免死鎖的方法，滿足資源的最大需求量 缺點(diǎn)：過于謹(jǐn)慎以及花費(fèi)開銷較大3.6 死鎖死鎖2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:6969 重重

47、 慶慶 師師 范范 大大 學(xué)學(xué)3.6.3 避免死鎖避免死鎖下面用例子說明系統(tǒng)的安全狀態(tài)和不安全狀態(tài)下面用例子說明系統(tǒng)的安全狀態(tài)和不安全狀態(tài)假如系統(tǒng)有假如系統(tǒng)有1212臺磁帶機(jī)。有三個進(jìn)程臺磁帶機(jī)。有三個進(jìn)程P1P1、P2P2和和P3P3，分別要求，分別要求1010臺、臺、4 4臺和臺和9 9臺磁帶機(jī)。設(shè)在時臺磁帶機(jī)。設(shè)在時刻刻T0T0進(jìn)程進(jìn)程P1P1、P2P2和和P3P3分別已經(jīng)獲得分別已經(jīng)獲得5 5臺、臺、2 2臺和臺和2 2臺磁帶機(jī)。臺磁帶機(jī)。 進(jìn)程進(jìn)程 最大需求最大需求 已分配已分配 可用可用 P1 P1 1010 5 53 3 P2 P2 4 4 2 2 P3 P3 9 9 2 23.

48、6 死鎖死鎖2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7070 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.6.4 死鎖的檢測與恢復(fù)死鎖的檢測與恢復(fù) 發(fā)現(xiàn)死鎖的原理：發(fā)現(xiàn)死鎖的原理：考查某一時刻系統(tǒng)狀態(tài)考查某一時刻系統(tǒng)狀態(tài)是否合理是否合理 檢測死鎖算法的基本思想檢測死鎖算法的基本思想 死鎖檢測的時機(jī)：死鎖檢測的時機(jī)： 1) 1) 每次分配后；每次分配后；2)2)定期檢查定期檢查 排除死鎖的實(shí)用方法：排除死鎖的實(shí)用方法： 1) 1)把陷于死鎖的全部進(jìn)程一律撤消；把陷于死鎖的全部進(jìn)程一律撤消； 2) 2)逐個作廢死鎖進(jìn)程至死鎖不再存在；逐個作廢死鎖進(jìn)程至死鎖不再存在；

49、 3) 3)逐個強(qiáng)迫搶占資源至死鎖不再存在逐個強(qiáng)迫搶占資源至死鎖不再存在3.6 死鎖死鎖2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7171 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.7.1 處理機(jī)的多級調(diào)度處理機(jī)的多級調(diào)度 1.處理機(jī)調(diào)度的功能 1）確定數(shù)據(jù)結(jié)構(gòu) 2）制訂調(diào)度策略（調(diào)度原則） 3）給出調(diào)度算法 4）具體的實(shí)施處理機(jī)分派 2.批處理系統(tǒng)中的處理機(jī)調(diào)度 處理機(jī)調(diào)度分類：作業(yè)調(diào)度和進(jìn)程調(diào)度 3. 多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度 4.多線程操作系統(tǒng)中的處理機(jī)調(diào)度3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 N

50、O:NO:7272 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.7.2 進(jìn)程調(diào)度進(jìn)程調(diào)度 進(jìn)程調(diào)度（也稱進(jìn)程調(diào)度（也稱CPUCPU調(diào)度）調(diào)度）: :按照某種調(diào)度按照某種調(diào)度算法從就緒隊(duì)列中選取進(jìn)程分配算法從就緒隊(duì)列中選取進(jìn)程分配CPUCPU 衡量各種調(diào)度算法性能優(yōu)劣的指標(biāo)衡量各種調(diào)度算法性能優(yōu)劣的指標(biāo): : 1 1）CPUCPU利用率利用率主要目標(biāo)主要目標(biāo)CPUCPU利用率利用率=CPU=CPU利用的時間利用的時間/ /開機(jī)運(yùn)行的總時間開機(jī)運(yùn)行的總時間 2 2）等待時間）等待時間 3 3）響應(yīng)時間）響應(yīng)時間 4 4）I/OI/O設(shè)備的利用率設(shè)備的利用率 5 5）“時空時空”代價代價3.7 處理機(jī)調(diào)度

51、處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7373 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.7.2 進(jìn)程調(diào)度進(jìn)程調(diào)度 進(jìn)程調(diào)度方式：進(jìn)程調(diào)度方式： 1 1）剝奪調(diào)度）剝奪調(diào)度 2 2）非剝奪調(diào)度）非剝奪調(diào)度常用進(jìn)程調(diào)度方法常用進(jìn)程調(diào)度方法 1. 1.先來先服務(wù)先來先服務(wù) 2. 2. 輪轉(zhuǎn)法（輪轉(zhuǎn)法（RRRR，Round RobinRound Robin） 將將CPUCPU的處理時間分成固定大小的時間片，進(jìn)程時的處理時間分成固定大小的時間片，進(jìn)程時間片內(nèi)輪轉(zhuǎn)執(zhí)行間片內(nèi)輪轉(zhuǎn)執(zhí)行 關(guān)鍵問題：關(guān)鍵問題：如何確定時間片的大小如何確定時間片的大小 時間片時間片q

52、 = RT/q = RT/NmaxNmax3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7474 重重 慶慶 師師 范范 大大 學(xué)學(xué)考慮下面考慮下面3 3個進(jìn)程，它們按個進(jìn)程，它們按1 1，2 2，3 3的順序處于就緒隊(duì)列中：的順序處于就緒隊(duì)列中： 進(jìn)程進(jìn)程 下一個下一個CPUCPU周期周期 P1 24P1 24 P2 3 P2 3 P3 3 P3 33.7 處理機(jī)調(diào)度處理機(jī)調(diào)度FCFSFCFS調(diào)度算法調(diào)度算法其他調(diào)度算法其他調(diào)度算法平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間ATT=（24+27+30）/3=27 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間ATT=（3+

53、6+30）/3=132022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7575 重重 慶慶 師師 范范 大大 學(xué)學(xué)2. 輪轉(zhuǎn)法設(shè)有如下4個就緒進(jìn)程： 進(jìn)程 下一個CPU周期 P1 6 P2 3 P3 1 P4 7 則如圖3-18所示3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度ATTATT0 1 2 3 4 5 6 7 q圖圖3-18 平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間ATT與時間片與時間片q之間的關(guān)系之間的關(guān)系2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7676 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.7.2 進(jìn)程調(diào)度進(jìn)程調(diào)度3.3. 多級反饋輪轉(zhuǎn)法多級反饋輪

54、轉(zhuǎn)法 思想：思想：不同級別的就緒隊(duì)列分配給不同時不同級別的就緒隊(duì)列分配給不同時間片，優(yōu)先級高的為第一級隊(duì)列，時間片最間片，優(yōu)先級高的為第一級隊(duì)列，時間片最小，隨著隊(duì)列級別降低，時間片加大小，隨著隊(duì)列級別降低，時間片加大 例如例如考慮由考慮由3 3個隊(duì)列組成的多級隊(duì)列調(diào)度。個隊(duì)列組成的多級隊(duì)列調(diào)度。3 3個隊(duì)列的編號分別為個隊(duì)列的編號分別為0, 1, 20, 1, 2，如圖，如圖3-193-193.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7777 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.7.2 進(jìn)程調(diào)度 4. 優(yōu)先數(shù)法（Priority

55、） 思想：按進(jìn)程的優(yōu)先級確定調(diào)度優(yōu)先權(quán) 優(yōu)先級確定方法：（1）靜態(tài)法：可按進(jìn)程類型、資源的要求、用戶要求指定（2）動態(tài)法：原則是合理地分配CPU時間、緊急的程序優(yōu)先3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7878 重重 慶慶 師師 范范 大大 學(xué)學(xué)實(shí)例解釋：實(shí)例解釋：假設(shè)就緒狀態(tài)有假設(shè)就緒狀態(tài)有4 4個進(jìn)程，每個進(jìn)程所需運(yùn)行個進(jìn)程，每個進(jìn)程所需運(yùn)行時間如下所示。時間如下所示。 進(jìn)程進(jìn)程 所需運(yùn)行時間所需運(yùn)行時間 1 1 6 6 2 2 3 3 3 1 3 1 4 7 4 7 進(jìn)程到達(dá)次序?yàn)檫M(jìn)程到達(dá)次序?yàn)? 1，2 2，3 3，4

56、 4。試分別按先來先服務(wù)調(diào)度。試分別按先來先服務(wù)調(diào)度算法、短進(jìn)程優(yōu)先調(diào)度算法和時間片輪轉(zhuǎn)法算法、短進(jìn)程優(yōu)先調(diào)度算法和時間片輪轉(zhuǎn)法( (時間片分時間片分1 1，3 3，5 5，6) 6) 給出進(jìn)程調(diào)度順序，并計(jì)算平均等待時間。給出進(jìn)程調(diào)度順序，并計(jì)算平均等待時間。3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:7979 重重 慶慶 師師 范范 大大 學(xué)學(xué)解：解：（1 1）先來先服務(wù)調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋海┫葋硐确?wù)調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋?平均等待時間：平均等待時間：T=1T=14 4(0+6+9+10)=6.25(0+6+9+10)=

57、6.25（2 2）短進(jìn)程優(yōu)先調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋海┒踢M(jìn)程優(yōu)先調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋?平均等待時間：平均等待時間： T=1T=14 4(4+1+0+10)=3.75(4+1+0+10)=3.75（3 3）時間片輪轉(zhuǎn)法）時間片輪轉(zhuǎn)法3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:8080 重重 慶慶 師師 范范 大大 學(xué)學(xué)解：解：時間片為時間片為1 1，進(jìn)程調(diào)度順序如下：，進(jìn)程調(diào)度順序如下： 平均等待時間：平均等待時間：T=1/4T=1/4(0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1)(0+3+2+2+1+

58、1)+(1+3+2)+2+(3+2+2+1+1+1) =1 =14 4(9+6+2+10)=6.75(9+6+2+10)=6.75時間片為時間片為3 3，進(jìn)程調(diào)度順序如下：，進(jìn)程調(diào)度順序如下： 平均等待時間：平均等待時間：T=1T=14 4(0+7)+3+6+(7+3)(0+7)+3+6+(7+3) =1 =14 4(7+3+6+10)=6.5(7+3+6+10)=6.53.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:8181 重重 慶慶 師師 范范 大大 學(xué)學(xué)解：解：時間片為時間片為5 5，進(jìn)程調(diào)度順序如下：，進(jìn)程調(diào)度順序如下： 平均

59、等待時間：平均等待時間： T=1T=14 4(0+9)+5+8+(9+1)(0+9)+5+8+(9+1) =1 =14 4(9+5+8+10)=8(9+5+8+10)=8 時間片為時間片為6 6，相當(dāng)于先來先服務(wù)調(diào)度算法。其進(jìn)程調(diào)度順序和平，相當(dāng)于先來先服務(wù)調(diào)度算法。其進(jìn)程調(diào)度順序和平均等待時間與先來先服務(wù)調(diào)度算法相同。均等待時間與先來先服務(wù)調(diào)度算法相同?？偨Y(jié)：總結(jié)：短進(jìn)程優(yōu)先調(diào)度算法使進(jìn)程平均等待時間最小。短進(jìn)程優(yōu)先調(diào)度算法使進(jìn)程平均等待時間最小。對于時間片輪轉(zhuǎn)法，進(jìn)程平均等待時間與時間片的大小對于時間片輪轉(zhuǎn)法，進(jìn)程平均等待時間與時間片的大小有關(guān)。有關(guān)。3.7 處理機(jī)調(diào)度處理機(jī)調(diào)度2022年

60、6月30日星期四第3章進(jìn)程和處理機(jī)管理進(jìn)程和處理機(jī)管理 NO:NO:8282 重重 慶慶 師師 范范 大大 學(xué)學(xué)3.8.1 Windows XP的進(jìn)程 1.Windows XP的進(jìn)程對象2.Windows XP的進(jìn)程TDB（任務(wù)數(shù)據(jù)庫）3.8 Windows XP的進(jìn)程和線程管理的進(jìn)程和線程管理圖3-20 Windows XP的進(jìn)程對象進(jìn)程進(jìn)程ID安全描述符基本優(yōu)先級默認(rèn)處理器集合定額限制執(zhí)行時間I/O計(jì)數(shù)器VM操作計(jì)數(shù)器異常/調(diào)試端口退出狀態(tài)創(chuàng)建進(jìn)程打開進(jìn)程查詢進(jìn)程信息設(shè)置進(jìn)程信息當(dāng)前進(jìn)程終止進(jìn)程對象類型對象體屬性服務(wù)圖3-21 Windows XP的進(jìn)程TDB私有堆棧 鏈接指針狀態(tài)標(biāo)志（事