第二章進(jìn)程的描述與控制

1、第二章第二章 進(jìn)程的描述與控制進(jìn)程的描述與控制 軟件工程學(xué)院計算機(jī)應(yīng)用系目錄目錄1. 進(jìn)程的基本概念進(jìn)程的基本概念 2. 進(jìn)程控制進(jìn)程控制 3. 進(jìn)程同步進(jìn)程同步 4. 經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題 5. 進(jìn)程通信進(jìn)程通信 6. 線程的基本概念線程的基本概念 是一個是一個有向無循環(huán)圖有向無循環(huán)圖，圖中每個結(jié)點表示一個語句、一段，圖中每個結(jié)點表示一個語句、一段程序或一個進(jìn)程程序或一個進(jìn)程表示表示S1S3S7S6S4S2S5 順序性順序性 封閉性封閉性 可再現(xiàn)性可再現(xiàn)性 ：程序的運(yùn)行結(jié)果與其推進(jìn)速度無關(guān)程序的運(yùn)行結(jié)果與其推進(jìn)速度無關(guān) read(disk,&a,4); /*從磁盤讀從磁盤

2、讀a*/ c=a+2; printf(“c=%fn”,c);ICPI C P間斷間斷( (異步異步) )性：性：“運(yùn)行暫停運(yùn)行運(yùn)行暫停運(yùn)行”；失去封閉性失去封閉性不可再現(xiàn)性：不可再現(xiàn)性：進(jìn)程的運(yùn)行結(jié)果與其推進(jìn)速度有關(guān)。進(jìn)程的運(yùn)行結(jié)果與其推進(jìn)速度有關(guān)。 2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念4. 進(jìn)程的定義及特征進(jìn)程的定義及特征n簡單定義簡單定義：一個程序的一次運(yùn)行過程。一個程序的一次運(yùn)行過程。n 特征：特征： 動態(tài)性：動態(tài)性：進(jìn)程最基本的特征進(jìn)程最基本的特征 結(jié)構(gòu)特征結(jié)構(gòu)特征： 程序數(shù)據(jù)程序數(shù)據(jù)PCB 321該程序所需的相關(guān)該程序所需的相關(guān)數(shù)據(jù)數(shù)據(jù)(變量、工作變量、工作空間，緩沖區(qū)等空間

3、，緩沖區(qū)等)該程序的執(zhí)行上該程序的執(zhí)行上下文下文(Context)一個可執(zhí)行的程一個可執(zhí)行的程序序2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 獨(dú)立性：獨(dú)立性：是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位，是能獨(dú)是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位，是能獨(dú)立運(yùn)行的基本單位立運(yùn)行的基本單位 并發(fā)性：并發(fā)性：程序在建立進(jìn)程后并發(fā)運(yùn)行程序在建立進(jìn)程后并發(fā)運(yùn)行 異步性：異步性：進(jìn)程以不可預(yù)知的速度向前推進(jìn)進(jìn)程以不可預(yù)知的速度向前推進(jìn) n定義：定義：可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的一可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的一次運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)次運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨(dú)立單位。

4、立單位。2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 (1)從定義上看，進(jìn)程是程序處理數(shù)據(jù)的過程，而程序是從定義上看，進(jìn)程是程序處理數(shù)據(jù)的過程，而程序是一組指令的有序集合；一組指令的有序集合； (2)進(jìn)程具有動態(tài)性、并發(fā)性、獨(dú)立性和異步性等，而程進(jìn)程具有動態(tài)性、并發(fā)性、獨(dú)立性和異步性等，而程序不具有這些特性；序不具有這些特性； (3)從進(jìn)程結(jié)構(gòu)特性上看，它包含程序、數(shù)據(jù)和從進(jìn)程結(jié)構(gòu)特性上看，它包含程序、數(shù)據(jù)和PCB； (4)進(jìn)程和程序并非一一對應(yīng)：進(jìn)程和程序并非一一對應(yīng)：通過多次執(zhí)行，一個程序通過多次執(zhí)行，一個程序可對應(yīng)多個進(jìn)程；通過調(diào)用關(guān)系，一個進(jìn)程可執(zhí)行多個程可對應(yīng)多個進(jìn)程；通過調(diào)用關(guān)系，

5、一個進(jìn)程可執(zhí)行多個程序。序。2.1 進(jìn)程的基本概念進(jìn)程的基本概念 就緒狀態(tài)：就緒狀態(tài)：進(jìn)程分配到必要的資源，等待獲得進(jìn)程分配到必要的資源，等待獲得CPUCPU執(zhí)行的狀執(zhí)行的狀態(tài)。態(tài)。 組織成一個或多個就緒隊列。組織成一個或多個就緒隊列。 運(yùn)行狀態(tài)運(yùn)行狀態(tài)：進(jìn)程分配到必要的資源，在進(jìn)程分配到必要的資源，在CPUCPU上執(zhí)行時的狀態(tài)上執(zhí)行時的狀態(tài) 阻塞狀態(tài)（等待狀態(tài)）阻塞狀態(tài)（等待狀態(tài)）：正在執(zhí)行的進(jìn)程由于發(fā)生某事正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)。件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)。組織成一個或多個阻塞隊列。組織成一個或多個阻塞隊列。進(jìn)程

6、三種基本狀態(tài)的轉(zhuǎn)換進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換運(yùn)行運(yùn)行就緒就緒阻塞阻塞等待事件等待事件 (系統(tǒng)服務(wù)請求，系統(tǒng)服務(wù)請求，如請求如請求I/O) 被調(diào)度或分派被調(diào)度或分派 時間片時間片用完用完 事件發(fā)生事件發(fā)生進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換：進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換：思考問題：思考問題：1.在進(jìn)程狀態(tài)轉(zhuǎn)換時，下列哪一種狀態(tài)轉(zhuǎn)換是不可能發(fā)生的？在進(jìn)程狀態(tài)轉(zhuǎn)換時，下列哪一種狀態(tài)轉(zhuǎn)換是不可能發(fā)生的？ A)就緒態(tài)就緒態(tài)運(yùn)行態(tài)運(yùn)行態(tài) B)運(yùn)行態(tài)運(yùn)行態(tài)就緒態(tài)就緒態(tài) C)運(yùn)行態(tài)運(yùn)行態(tài)等待態(tài)等待態(tài) )阻塞態(tài)阻塞態(tài)運(yùn)行態(tài)運(yùn)行態(tài) 答案：答案：D2某進(jìn)程在運(yùn)行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時該進(jìn)某進(jìn)程在運(yùn)行過程中需要等待從磁盤上讀入

7、數(shù)據(jù)，此時該進(jìn)程的狀態(tài)將（程的狀態(tài)將（ ）。）。 A.從就緒變?yōu)檫\(yùn)行從就緒變?yōu)檫\(yùn)行 B.從運(yùn)行變?yōu)榫途w從運(yùn)行變?yōu)榫途w .從運(yùn)行變?yōu)樽枞麖倪\(yùn)行變?yōu)樽枞?D.從阻塞變?yōu)榫途w從阻塞變?yōu)榫途w 答案：答案：C2.1 進(jìn)程的基本概念進(jìn)程的基本概念 引人掛起狀態(tài)的原因：引人掛起狀態(tài)的原因：（1 1）操作系統(tǒng)的需要；（）操作系統(tǒng)的需要；（2 2）終端用戶的需要；）終端用戶的需要；（3 3）父進(jìn)程請求；）父進(jìn)程請求； （4 4）負(fù)荷調(diào)節(jié)的需要。）負(fù)荷調(diào)節(jié)的需要。 進(jìn)程狀態(tài)的轉(zhuǎn)換：進(jìn)程狀態(tài)的轉(zhuǎn)換：靜止就緒靜止就緒靜止阻塞靜止阻塞掛起掛起掛起掛起激活激活激活激活（1 1）活動就緒）活動就緒 靜止就緒靜止就緒 （2

8、2）活動阻塞）活動阻塞 靜止阻塞靜止阻塞（3 3）靜止就緒）靜止就緒 活動就緒活動就緒 （4 4）靜止阻塞）靜止阻塞 活動阻塞活動阻塞 (5) (5) 運(yùn)行狀態(tài)運(yùn)行狀態(tài) 靜止就緒靜止就緒掛起掛起具有掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換具有掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換活動就緒活動就緒運(yùn)行運(yùn)行活動阻塞活動阻塞靜止阻塞靜止阻塞靜止就緒靜止就緒wakeup (喚醒喚醒)事件發(fā)生事件發(fā)生掛起掛起suspend時間片完時間片完被調(diào)度被調(diào)度scheduler激活激活active掛起掛起suspend激活激活active掛起掛起suspend等待事件等待事件sleep事件發(fā)生事件發(fā)生wakeup (喚醒喚醒)（1）NULL 創(chuàng)建

9、創(chuàng)建 （2）創(chuàng)建）創(chuàng)建 活動就緒活動就緒（3）創(chuàng)建）創(chuàng)建 靜止就緒靜止就緒（4）執(zhí)行）執(zhí)行 終止終止補(bǔ)充：進(jìn)程管理功能：補(bǔ)充：進(jìn)程管理功能：（1 1）進(jìn)程控制：）進(jìn)程控制：控制進(jìn)程狀態(tài)轉(zhuǎn)換；（2 2）進(jìn)程同步：）進(jìn)程同步：進(jìn)程間運(yùn)行順序的協(xié)調(diào)：互斥方式；互斥方式；同步方式：同步方式： （3 3）進(jìn)程通信：）進(jìn)程通信：進(jìn)程間的信息交換直接通信；直接通信；間接通信。間接通信。 （4 4）進(jìn)程調(diào)度：）進(jìn)程調(diào)度：進(jìn)程間競爭臨界資源進(jìn)程間相互合作2.1 進(jìn)程的基本概念進(jìn)程的基本概念 程序：程序：描述進(jìn)程要完成的功能描述進(jìn)程要完成的功能 數(shù)據(jù)集合：數(shù)據(jù)集合：包含程序運(yùn)行所需的數(shù)據(jù)和工包含程序運(yùn)行所需的數(shù)據(jù)

10、和工作區(qū)作區(qū) 進(jìn)程控制塊（進(jìn)程控制塊（PCBPCB）：）：包含進(jìn)程的描述信息包含進(jìn)程的描述信息和控制信息，是進(jìn)程動態(tài)特性的反映和控制信息，是進(jìn)程動態(tài)特性的反映程序和數(shù)據(jù)集合是進(jìn)程的實體程序和數(shù)據(jù)集合是進(jìn)程的實體進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志進(jìn)程控制塊是由進(jìn)程控制塊是由OSOS維護(hù)維護(hù)的用來記錄的用來記錄進(jìn)程相關(guān)進(jìn)程相關(guān)信息信息的一塊內(nèi)存。的一塊內(nèi)存。2.1 進(jìn)程的基本概念進(jìn)程的基本概念 進(jìn)程標(biāo)識符：進(jìn)程標(biāo)識符： 內(nèi)部標(biāo)識符、外部標(biāo)識符內(nèi)部標(biāo)識符、外部標(biāo)識符 處理機(jī)狀態(tài)信息：處理機(jī)狀態(tài)信息：（1 1）通用寄存器；）通用寄存器；（2 2）段寄存器；）段寄存器；（3 3

11、）指令計數(shù)器；）指令計數(shù)器；（4 4）程序狀態(tài)字）程序狀態(tài)字(PSW)(PSW)；3232位位CPUCPU有有8 8個個3232位的位的通用寄存器通用寄存器EAXEAX、EBXEBX、ECXECX、EDXEDX、ESIESI、EDIEDI、EBPEBP和和ESPESP 。EAXEAX：稱為累加器，可用于乘、除、輸入：稱為累加器，可用于乘、除、輸入/ /輸出等操作；輸出等操作；EBX:EBX:稱為基地址寄存器稱為基地址寄存器, , 可作為存儲器指針來使用；可作為存儲器指針來使用； ECX:ECX:稱為計數(shù)寄存器稱為計數(shù)寄存器, , 控制循環(huán)次數(shù)；控制循環(huán)次數(shù)；EDX:EDX:稱為數(shù)據(jù)寄存器稱為數(shù)

12、據(jù)寄存器, ,在進(jìn)行乘、除運(yùn)算時，作為默認(rèn)的操作在進(jìn)行乘、除運(yùn)算時，作為默認(rèn)的操作數(shù)參與運(yùn)算，也可用于存放數(shù)參與運(yùn)算，也可用于存放I/OI/O的端口地址。的端口地址。ESIESI：變址寄存器，是內(nèi)存移動和比較操作的源地址寄存器；：變址寄存器，是內(nèi)存移動和比較操作的源地址寄存器；EDIEDI：變址寄存器，是內(nèi)存移動和比較操作的目標(biāo)地址寄存器：變址寄存器，是內(nèi)存移動和比較操作的目標(biāo)地址寄存器EBPEBP：指針寄存器，存放堆棧幀的始址；：指針寄存器，存放堆棧幀的始址；ESP: ESP: 指針寄存器，當(dāng)前堆棧棧頂位置。指針寄存器，當(dāng)前堆棧棧頂位置。段寄存器是根據(jù)內(nèi)存分段的管理模式而設(shè)置的。內(nèi)存單元的段

13、寄存器是根據(jù)內(nèi)存分段的管理模式而設(shè)置的。內(nèi)存單元的物理地址由段寄存器的值和一個偏移量組合而成。物理地址由段寄存器的值和一個偏移量組合而成。3232位位CPUCPU有有6 6個，個，1616位位CPUCPU有有4 4個個 。CSCS：代碼段寄存器，其值為代碼段的段地址；：代碼段寄存器，其值為代碼段的段地址；DSDS：數(shù)據(jù)段寄存器，其值為數(shù)據(jù)段的地址；：數(shù)據(jù)段寄存器，其值為數(shù)據(jù)段的地址；ESES：附加段寄存器，其值為附加數(shù)據(jù)段的地址；：附加段寄存器，其值為附加數(shù)據(jù)段的地址；SSSS：堆棧段寄存器，其值為堆棧段的地址；：堆棧段寄存器，其值為堆棧段的地址；FSFS：附加段寄存器，其值為附加數(shù)據(jù)段的地址

14、；：附加段寄存器，其值為附加數(shù)據(jù)段的地址；GSGS：附加段寄存器，其值為附加數(shù)據(jù)段的地址。：附加段寄存器，其值為附加數(shù)據(jù)段的地址。中斷允許位、陷入標(biāo)志、中斷允許位、陷入標(biāo)志、任務(wù)嵌套標(biāo)志、特權(quán)標(biāo)任務(wù)嵌套標(biāo)志、特權(quán)標(biāo)志、溢出標(biāo)志、符號標(biāo)志、溢出標(biāo)志、符號標(biāo)志、零標(biāo)志、進(jìn)位標(biāo)志志、零標(biāo)志、進(jìn)位標(biāo)志等等2.1 進(jìn)程的基本概念進(jìn)程的基本概念 進(jìn)程控制信息：進(jìn)程控制信息：（1 1）程序和數(shù)據(jù)地址；）程序和數(shù)據(jù)地址；（2 2）進(jìn)程同步和通信信息；）進(jìn)程同步和通信信息；（3 3）資源清單；）資源清單；（4 4）鏈接指針）鏈接指針 鏈接方式：鏈接方式： 索引方式索引方式（1 1）就緒鏈表；）就緒鏈表；（2 2

15、）執(zhí)行進(jìn)程；）執(zhí)行進(jìn)程；（3 3）阻塞鏈表；）阻塞鏈表；（4 4）空白鏈表。）空白鏈表。 進(jìn)程調(diào)度信息：進(jìn)程調(diào)度信息：（1 1）進(jìn)程狀態(tài)；）進(jìn)程狀態(tài)；（2 2）進(jìn)程優(yōu)先級；）進(jìn)程優(yōu)先級；（3 3）事件；）事件；（4 4）其他信息）其他信息2.2 進(jìn)程控制進(jìn)程控制完成進(jìn)程狀態(tài)的轉(zhuǎn)換。完成進(jìn)程狀態(tài)的轉(zhuǎn)換。原語原語(primitive)(primitive)：由若干條指令構(gòu)成的由若干條指令構(gòu)成的“原子原子操作操作(atomic operation)”(atomic operation)”過程，完成某種特定過程，完成某種特定的功能，作為一個的功能，作為一個整體整體而而不可分割不可分割要么全都要么全都完

16、成，要么全都不做。完成，要么全都不做。 為了對進(jìn)程控制，系統(tǒng)中必須設(shè)置一個機(jī)構(gòu)，它為了對進(jìn)程控制，系統(tǒng)中必須設(shè)置一個機(jī)構(gòu)，它具有創(chuàng)建撤消以及進(jìn)程通訊和資源管理等功能，這樣具有創(chuàng)建撤消以及進(jìn)程通訊和資源管理等功能，這樣結(jié)構(gòu)稱為結(jié)構(gòu)稱為OS的內(nèi)核的內(nèi)核 (kernel)。2.2 進(jìn)程控制進(jìn)程控制用于進(jìn)程控制的原語有：用于進(jìn)程控制的原語有：(1) 創(chuàng)建進(jìn)程原語創(chuàng)建進(jìn)程原語 (2) 終止進(jìn)程原語終止進(jìn)程原語 (3) 掛起進(jìn)程原語掛起進(jìn)程原語 (4) 激活進(jìn)程原語激活進(jìn)程原語(5) 阻塞進(jìn)程原語阻塞進(jìn)程原語(6) 喚醒進(jìn)程原語喚醒進(jìn)程原語 進(jìn)程圖概念：進(jìn)程圖概念： 描述系統(tǒng)中進(jìn)程的家族關(guān)系的有向圖。描述

17、系統(tǒng)中進(jìn)程的家族關(guān)系的有向圖。2. 系統(tǒng)啟動過程：系統(tǒng)啟動過程：機(jī)器加電，系統(tǒng)復(fù)位：機(jī)器加電，系統(tǒng)復(fù)位：CPUCPU初始化（初始化（CS=F000HCS=F000H，IP=FFF0HIP=FFF0H）CpuCpu執(zhí)行第一條指令：執(zhí)行第一條指令：JMPJMP（ROMBIOSROMBIOS中的啟動程序入口中的啟動程序入口加電自檢加電自檢POSTPOST初始化顯卡、顯示初始化顯卡、顯示BIOS信息、檢測信息、檢測CPU的類型和工作的類型和工作頻率頻率 、測試主機(jī)所有的內(nèi)存、測試主機(jī)所有的內(nèi)存 ；檢測系統(tǒng)中的標(biāo)準(zhǔn)硬件設(shè)備：硬盤、檢測系統(tǒng)中的標(biāo)準(zhǔn)硬件設(shè)備：硬盤、CD-ROM、軟驅(qū)、軟驅(qū)、串行接口和并行接

18、口等連接的設(shè)備串行接口和并行接口等連接的設(shè)備 ；檢測和配置即插即用設(shè)備檢測和配置即插即用設(shè)備 、更新擴(kuò)展系統(tǒng)配置數(shù)據(jù)、更新擴(kuò)展系統(tǒng)配置數(shù)據(jù)) 系統(tǒng)啟動過程：系統(tǒng)啟動過程：執(zhí)行執(zhí)行19H中斷：中斷：BOIS帶的系統(tǒng)初始引導(dǎo)程序帶的系統(tǒng)初始引導(dǎo)程序讀入引導(dǎo)盤的第一個扇區(qū)到內(nèi)存：讀入引導(dǎo)盤的第一個扇區(qū)到內(nèi)存：若是硬盤：主引導(dǎo)程序若是硬盤：主引導(dǎo)程序+硬盤分區(qū)表硬盤分區(qū)表讀入可引導(dǎo)分區(qū)第一個扇區(qū)讀入可引導(dǎo)分區(qū)第一個扇區(qū)Linux系統(tǒng)啟動過程：系統(tǒng)啟動過程： 執(zhí)行執(zhí)行bootsect.s程序：程序：1）將自身從）將自身從0 x7C00處移動到處移動到0 x90000處；處；2）調(diào)用）調(diào)用BIOS 13H

19、中斷讀入中斷讀入setup.s程序到程序到0 x90200處；處；3）讀入磁盤驅(qū)動器參數(shù)）讀入磁盤驅(qū)動器參數(shù)4）加載）加載system模塊到模塊到0 x1000處處5）跳轉(zhuǎn)到）跳轉(zhuǎn)到setup.s程序執(zhí)行。程序執(zhí)行。Linux系統(tǒng)啟動過程：系統(tǒng)啟動過程： 執(zhí)行執(zhí)行setup.s程序：程序：1）從）從BIOS中讀取系統(tǒng)數(shù)據(jù)到中讀取系統(tǒng)數(shù)據(jù)到0 x90000處；處；2）將）將system模塊從模塊從0 x10000移動到移動到0 x0000處；處；3）加載段描述符：中斷描述符表寄存器、全局描述）加載段描述符：中斷描述符表寄存器、全局描述符表寄存器；符表寄存器；4）重新對中斷進(jìn)行編程；）重新對中斷進(jìn)

20、行編程；5）轉(zhuǎn)換到保護(hù)模式運(yùn)行：將控制寄存器）轉(zhuǎn)換到保護(hù)模式運(yùn)行：將控制寄存器CR0的位的位0置置1即可；即可；6）跳轉(zhuǎn)到）跳轉(zhuǎn)到system模塊執(zhí)行；（該模塊包括模塊執(zhí)行；（該模塊包括head.s,main.c程序，內(nèi)核模塊等）程序，內(nèi)核模塊等）系統(tǒng)啟動過程：系統(tǒng)啟動過程： 執(zhí)行執(zhí)行head.s程序：程序：1）設(shè)置各個數(shù)據(jù)段寄存器；）設(shè)置各個數(shù)據(jù)段寄存器；2）設(shè)置中斷描述符表；設(shè)置全局描述符表；）設(shè)置中斷描述符表；設(shè)置全局描述符表；3）設(shè)置頁目錄表；設(shè)置）設(shè)置頁目錄表；設(shè)置4張頁表；張頁表；4）設(shè)置頁目錄基址寄存器）設(shè)置頁目錄基址寄存器CR3；5）啟動使用分頁處理：）啟動使用分頁處理：CR0

21、的位的位31為為1；6）跳轉(zhuǎn)到）跳轉(zhuǎn)到main.c執(zhí)行；執(zhí)行；head.s執(zhí)行后的內(nèi)存映像：執(zhí)行后的內(nèi)存映像：系統(tǒng)啟動過程：執(zhí)行系統(tǒng)啟動過程：執(zhí)行main.c利用利用setup.s程序取得的系統(tǒng)參數(shù)設(shè)置系統(tǒng)的根文件程序取得的系統(tǒng)參數(shù)設(shè)置系統(tǒng)的根文件設(shè)備號及一些內(nèi)存全局變量設(shè)備號及一些內(nèi)存全局變量建立可分頁主內(nèi)存區(qū)的內(nèi)存塊位示圖建立可分頁主內(nèi)存區(qū)的內(nèi)存塊位示圖初始化設(shè)備：塊設(shè)備、字符設(shè)備、初始化設(shè)備：塊設(shè)備、字符設(shè)備、tty初始化調(diào)度程序相關(guān)的數(shù)據(jù)結(jié)構(gòu)：如任務(wù)數(shù)組、全局描述初始化調(diào)度程序相關(guān)的數(shù)據(jù)結(jié)構(gòu)：如任務(wù)數(shù)組、全局描述符表、時鐘中斷處理句柄等符表、時鐘中斷處理句柄等初始化緩沖管理：如建立空閑

22、緩沖區(qū)鏈表等初始化緩沖管理：如建立空閑緩沖區(qū)鏈表等初始化硬盤、軟驅(qū)管理等，并開啟中斷初始化硬盤、軟驅(qū)管理等，并開啟中斷系統(tǒng)啟動過程：執(zhí)行系統(tǒng)啟動過程：執(zhí)行main.c轉(zhuǎn)移到用戶模式運(yùn)行任務(wù)（進(jìn)程）轉(zhuǎn)移到用戶模式運(yùn)行任務(wù)（進(jìn)程）0任務(wù)任務(wù)0調(diào)用調(diào)用fork()創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程1進(jìn)程進(jìn)程1執(zhí)行執(zhí)行init()程序程序Init()：1）調(diào)用）調(diào)用setup()，讀取硬盤參數(shù)包括分區(qū)表信息，讀取硬盤參數(shù)包括分區(qū)表信息，建立虛擬盤，安裝根文件系統(tǒng)設(shè)備；建立虛擬盤，安裝根文件系統(tǒng)設(shè)備； 2）用讀寫方式打開）用讀寫方式打開“/dev/tty00”（終端控制臺）（終端控制臺） 3）創(chuàng)建）創(chuàng)建login進(jìn)程等待

23、用戶登錄；進(jìn)程等待用戶登錄； 4）登錄成功后調(diào)用）登錄成功后調(diào)用fork() 創(chuàng)建創(chuàng)建shell進(jìn)程運(yùn)行進(jìn)程運(yùn)行/bin/sh程序程序用戶登錄。用戶登錄。作業(yè)調(diào)度。作業(yè)調(diào)度。 3. 引起創(chuàng)建進(jìn)程的事件：引起創(chuàng)建進(jìn)程的事件： (3) 提供服務(wù)。提供服務(wù)。 (4) 應(yīng)用請求。應(yīng)用請求。 4. 創(chuàng)建進(jìn)程原語創(chuàng)建進(jìn)程原語的工作大致描述為：的工作大致描述為： 申請空白申請空白PCB； 為新進(jìn)程分配資源；為新進(jìn)程分配資源； (3) 初始化進(jìn)程控制塊初始化進(jìn)程控制塊PCB； (4) 將新進(jìn)程插入就緒隊列。將新進(jìn)程插入就緒隊列。 調(diào)用 alloc _task _struct ()分配兩個頁面存放task_st

24、ruct 及 系統(tǒng)堆棧調(diào)用get _pid ()獲得新建子進(jìn)程PID1、調(diào)用copy_files()復(fù)制父進(jìn)程已經(jīng)打開的文件控制結(jié)構(gòu)；2、調(diào)用copy_fs()復(fù)制父進(jìn)程的根目錄、安裝點等；3、調(diào)用copy_sighand()復(fù)制父進(jìn)程信號處理函數(shù)；4、調(diào)用copy_mm()復(fù)制父進(jìn)程用戶地址空間調(diào)用 copy _ thread()復(fù)制系統(tǒng)堆棧調(diào)用wake _ up _ process () 將子進(jìn)程插入可運(yùn)行進(jìn)程隊列3. 終止進(jìn)程原語終止進(jìn)程原語 正常結(jié)束 2) 異常結(jié)束 3) 外界干預(yù) 引起進(jìn)程終止的事件：引起進(jìn)程終止的事件： OSOS父進(jìn)程終止父進(jìn)程終止父進(jìn)程請求父進(jìn)程請求（1）根據(jù)被終

25、止進(jìn)程的標(biāo)識符，從PCB集合中檢索出該進(jìn)程的PCB，獲得該進(jìn)程的狀態(tài)（2）若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真。（3）若該進(jìn)程還有子孫進(jìn)程，終止其所有子孫進(jìn)程。（4）回收資源（5）回收PCB 進(jìn)程終止的過程：進(jìn)程終止的過程： 請求系統(tǒng)服務(wù) 2) 啟動某種操作 3) 新數(shù)據(jù)尚未到達(dá)4) 無新工作可做：服務(wù)進(jìn)程4. 阻塞與喚醒原語阻塞與喚醒原語 引起進(jìn)程阻塞與喚醒的事件：引起進(jìn)程阻塞與喚醒的事件： 停止當(dāng)前進(jìn)程執(zhí)行，并修改進(jìn)程狀態(tài)： 由“執(zhí)行執(zhí)行”改為“阻塞阻塞”；2) 將PCB插入阻塞阻塞隊列； 3) 轉(zhuǎn)調(diào)度程序重新進(jìn)行調(diào)度。 進(jìn)程阻塞過程：進(jìn)程阻塞過程： 1)

26、把被阻塞的進(jìn)程從等待該事件的阻塞隊列中移出修改PCB中的進(jìn)程狀態(tài)： 由阻塞阻塞改為就緒就緒3) 將該P(yáng)CB插入到就緒隊列中 進(jìn)程喚醒過程：進(jìn)程喚醒過程： 5. 掛起與激活原語掛起與激活原語用戶進(jìn)程請求將自己掛起用戶進(jìn)程請求將自己掛起(2) 父進(jìn)程請求將自己的某個子進(jìn)程掛起父進(jìn)程請求將自己的某個子進(jìn)程掛起(3) 父進(jìn)程或用戶進(jìn)程請求激活指定進(jìn)程，內(nèi)存空間允許父進(jìn)程或用戶進(jìn)程請求激活指定進(jìn)程，內(nèi)存空間允許 引起進(jìn)程掛起和激活的事件引起進(jìn)程掛起和激活的事件 ： 修改被掛起進(jìn)程的狀態(tài)：修改被掛起進(jìn)程的狀態(tài)： 若處于若處于活動就緒狀態(tài)活動就緒狀態(tài)， 若處于若處于活動阻塞狀態(tài)活動阻塞狀態(tài)， 若進(jìn)程處于若進(jìn)

27、程處于運(yùn)行狀態(tài)運(yùn)行狀態(tài)，將將該進(jìn)程的該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域復(fù)制到某指定的內(nèi)存區(qū)域可能會被換出到外存可能會被換出到外存4) 若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新調(diào)度若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)調(diào)度程序重新調(diào)度 進(jìn)程掛起過程進(jìn)程掛起過程 ： 便將其改為便將其改為靜止就緒靜止就緒；便將其改為便將其改為靜止阻塞靜止阻塞；便將其改為便將其改為靜止就緒靜止就緒；將進(jìn)程從外存調(diào)入內(nèi)存；將進(jìn)程從外存調(diào)入內(nèi)存；修改進(jìn)程狀態(tài)：若是修改進(jìn)程狀態(tài)：若是靜止就緒靜止就緒， 便將之改為便將之改為活動就緒活動就緒； 若為若為靜止阻塞靜止阻塞， 便將之改為便將之改為活動阻塞活動阻塞。 3）修改）修改PCB中

28、進(jìn)程的程序和數(shù)據(jù)的地址；中進(jìn)程的程序和數(shù)據(jù)的地址；4）將）將PCB插入相關(guān)隊列。插入相關(guān)隊列。 進(jìn)程激活的過程進(jìn)程激活的過程 ： 2.3 進(jìn)程同步進(jìn)程同步 進(jìn)程間的制約關(guān)系進(jìn)程間的制約關(guān)系（1 1）間接制約：）間接制約：相互競爭獨(dú)占分配到的部分或全部相互競爭獨(dú)占分配到的部分或全部共享資源，共享資源，“互斥互斥”系統(tǒng)中一次僅允許一個進(jìn)程使用的一類資源。系統(tǒng)中一次僅允許一個進(jìn)程使用的一類資源。 打印機(jī)，卡片輸入機(jī)，磁帶機(jī)、共享變量等。打印機(jī)，卡片輸入機(jī)，磁帶機(jī)、共享變量等。互斥：互斥：指的是對某個系統(tǒng)資源，一個進(jìn)程正在使用它，另指的是對某個系統(tǒng)資源，一個進(jìn)程正在使用它，另外一個想用它的進(jìn)程就必須等

29、待，而不能同時使用外一個想用它的進(jìn)程就必須等待，而不能同時使用 ； （2 2）直接制約）直接制約：相互協(xié)作等待來自其他進(jìn)程的信：相互協(xié)作等待來自其他進(jìn)程的信息，息，“同步同步”,即保證進(jìn)程間的前驅(qū)后繼關(guān)系。即保證進(jìn)程間的前驅(qū)后繼關(guān)系。共享變量的修改沖突共享變量的修改沖突例：民航售票系統(tǒng)，例：民航售票系統(tǒng)，n個售票處個售票處 /*Process Pi ,i=1,2,.,n*/ . /*按訂票要求找到數(shù)據(jù)庫中的共享數(shù)據(jù)按訂票要求找到數(shù)據(jù)庫中的共享數(shù)據(jù)xk*/ /*xk存放某月某日某次航班的現(xiàn)有票數(shù)存放某月某日某次航班的現(xiàn)有票數(shù)*/ R=xk; /*現(xiàn)有票數(shù)現(xiàn)有票數(shù)*/ if(R=1) R-; xk

30、=R; 輸出一張機(jī)票；輸出一張機(jī)票； else 顯示顯示“票已售完票已售完”；進(jìn)程中訪問臨界資源的程序段。進(jìn)程中訪問臨界資源的程序段。對同一臨界資源進(jìn)行操作的程序段。對同一臨界資源進(jìn)行操作的程序段。entry section 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)exit section 退出區(qū)退出區(qū) critical section(臨界區(qū)）臨界區(qū)） remainder section（剩余區(qū)）（剩余區(qū)） 臨界區(qū)臨界區(qū)(critical section)(critical section)：進(jìn)程中訪問進(jìn)程中訪問臨界資源的一段代碼。臨界資源的一段代碼。 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū)(entry section)(entry secti

31、on)：在進(jìn)入臨界區(qū)之在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。前，檢查可否進(jìn)入臨界區(qū)的一段代碼。 退出區(qū)退出區(qū)(exit section)(exit section)：釋放臨界資源的釋放臨界資源的一段代碼一段代碼 剩余區(qū)剩余區(qū)(remainder section)(remainder section)：代碼中的其代碼中的其余部分。余部分。 空閑讓進(jìn)：其他進(jìn)程均不處于臨界區(qū)；空閑讓進(jìn)：其他進(jìn)程均不處于臨界區(qū)； 忙則等待：已有進(jìn)程處于其臨界區(qū)；忙則等待：已有進(jìn)程處于其臨界區(qū)； 有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能死等死等； 讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)

32、釋放讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）（如轉(zhuǎn)換到阻塞狀態(tài)） 有兩個進(jìn)程有兩個進(jìn)程P0, P1P0, P1： 設(shè)立一個公用整型變量設(shè)立一個公用整型變量 turnturn：描述允許進(jìn)入臨界區(qū)的進(jìn)程：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識，假設(shè)初始化標(biāo)識，假設(shè)初始化turn=0turn=0，表示首先輪到，表示首先輪到P0P0訪問臨界資源。訪問臨界資源。while (turn != 0);while (turn != 0); critical section turn = 1; remainder sectionP0P0的代碼：的代碼：while (turn != 1);while

33、 (turn != 1); critical section turn = 0; remainder sectionP1P1的代碼：的代碼： 缺點：缺點：強(qiáng)制輪流強(qiáng)制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實際需要。容易造成進(jìn)程的實際需要。容易造成資源利用不資源利用不充分充分：在：在PiPi出讓臨界區(qū)之后，出讓臨界區(qū)之后，PjPj使用臨使用臨界區(qū)之前，界區(qū)之前，PiPi不可能再次使用臨界區(qū)；不可能再次使用臨界區(qū)； 違背了空閑讓進(jìn)、讓權(quán)等待的原則。違背了空閑讓進(jìn)、讓權(quán)等待的原則。 設(shè)立一個標(biāo)志數(shù)組設(shè)立一個標(biāo)志數(shù)組flag2flag2：描述進(jìn)程是否已在臨界區(qū)描述進(jìn)程是否已在臨界區(qū)，初值均

34、為，初值均為0(FALSE)0(FALSE)，表示進(jìn)程都不在臨界區(qū)。，表示進(jìn)程都不在臨界區(qū)。 P0: while (flag1); flag0=1; 臨界區(qū)臨界區(qū) flag0=0; P1: while (flag0); flag1=1; 臨界區(qū)臨界區(qū) flag1=0; 違背了忙則等待原則；違背了讓權(quán)等待原則違背了忙則等待原則；違背了讓權(quán)等待原則 設(shè)立一個標(biāo)志數(shù)組設(shè)立一個標(biāo)志數(shù)組flag2flag2：描述進(jìn)程是否希望進(jìn)入臨描述進(jìn)程是否希望進(jìn)入臨界區(qū)，初值均為界區(qū)，初值均為0(FALSE)0(FALSE)，表示進(jìn)程都不希望進(jìn)入臨界區(qū)，表示進(jìn)程都不希望進(jìn)入臨界區(qū) P0: flag0=1; while

35、 (flag1); 臨界區(qū)臨界區(qū) flag0=0; P1: flag1=1; while (flag0); 臨界區(qū)臨界區(qū) flag1=0; 違背了空閑讓進(jìn)、有限等待、讓權(quán)等待原則違背了空閑讓進(jìn)、有限等待、讓權(quán)等待原則 設(shè)立一個標(biāo)志數(shù)組設(shè)立一個標(biāo)志數(shù)組flag2flag2：描述進(jìn)程是否希望進(jìn)入：描述進(jìn)程是否希望進(jìn)入臨界區(qū)，初值均為臨界區(qū)，初值均為0(FALSE)0(FALSE)，表示進(jìn)程都不希望進(jìn)入，表示進(jìn)程都不希望進(jìn)入臨界區(qū)。臨界區(qū)。int turn=0,int turn=0,表示首先輪到表示首先輪到P0P0進(jìn)入臨界區(qū)。進(jìn)入臨界區(qū)。 P0: flag0=1; turn=1; while (fl

36、ag1 &turn=1); 臨界區(qū)臨界區(qū) flag0=0; P1: flag1=1; turn=0; while (flag0 & turn=0); 臨界區(qū)臨界區(qū) flag1=0; 每一類臨界資源設(shè)置一把鎖每一類臨界資源設(shè)置一把鎖lock。 lock表示資源的兩種狀態(tài)：表示資源的兩種狀態(tài)：TRUE表示正被占用（表示正被占用（關(guān)鎖狀態(tài)）；關(guān)鎖狀態(tài)）；FALSE表示空閑（開鎖狀態(tài)）表示空閑（開鎖狀態(tài)）加鎖操作加鎖操作開鎖操作開鎖操作執(zhí)行臨界區(qū)程序執(zhí)行臨界區(qū)程序 臨界區(qū)太長時，降低了中斷響應(yīng)速度；臨界區(qū)太長時，降低了中斷響應(yīng)速度； 加鎖時加鎖時CPU不斷測試，處于忙等待；不斷測試，處

37、于忙等待； 不能實現(xiàn)多處理機(jī)系統(tǒng)中同類臨界區(qū)互斥；不能實現(xiàn)多處理機(jī)系統(tǒng)中同類臨界區(qū)互斥；關(guān)中斷關(guān)中斷開中斷開中斷執(zhí)行臨界區(qū)程序執(zhí)行臨界區(qū)程序 1. 整型信號量整型信號量 最初由Dijkstra把整型信號量定義為一個整型量，除初除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作(Atomic Operation) wait(S)和和signal(S)來訪問。來訪問。又分別稱為P P、V V操作。 wait和和signal操作可描述為：操作可描述為： wait(S)或或P(S): while S0 do no-op； S =S-1; signal(S)或或V(S): S =S

38、+1; 缺點：存在缺點：存在“忙等忙等”現(xiàn)象?，F(xiàn)象。信號量數(shù)據(jù)結(jié)構(gòu)：信號量數(shù)據(jù)結(jié)構(gòu)：typedef struct int value; /*信號量的值信號量的值*/ PCB * L; /*進(jìn)程阻塞隊列隊首指針進(jìn)程阻塞隊列隊首指針*/ semaphore ; 2. 記錄型信號量記錄型信號量 Value:初始化為一個非負(fù)整數(shù)值，表示空閑資源總初始化為一個非負(fù)整數(shù)值，表示空閑資源總數(shù)若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)數(shù)若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對值表示當(dāng)前等待臨界資源的進(jìn)程個數(shù)。值其絕對值表示當(dāng)前等待臨界資源的進(jìn)程個數(shù)。 L：初值為空初值為空 S-value-; if(S-va

39、lueL); semaphore *S; S-value+; if(S-valueL); 為臨界資源設(shè)置一個為臨界資源設(shè)置一個互斥信號量互斥信號量mutex(MUTual mutex(MUTual Exclusion)Exclusion)，其，其初值為初值為1 1；在每個進(jìn)程中將臨界區(qū)；在每個進(jìn)程中將臨界區(qū)代碼置于代碼置于P(mutex)P(mutex)和和V(mutex)V(mutex)原語之間；原語之間； 必須必須成對使用成對使用P P和和V V原語，原語，P P、V V原語原語不能次序錯誤不能次序錯誤、重復(fù)或遺漏、重復(fù)或遺漏 P（mutex）critical sectionV（mutex

40、）remainder section semaphore mutex=1,NULL; cobegin program pi while(1) P(mutex)； critical section for pi; /*進(jìn)程進(jìn)程pi臨界區(qū)臨界區(qū)*/ V(mutex)； remainder section for pi; coend例：民航售票系統(tǒng)，例：民航售票系統(tǒng)，n個售票處個售票處 semaphore mutex=1,NULL; cobegin program pi R=xk; /*現(xiàn)有票數(shù)現(xiàn)有票數(shù)*/ if(R=1) R-; xk=R; 輸出一張機(jī)票；輸出一張機(jī)票； else 顯示顯示“票已售

41、完票已售完”； coend 例：民航售票系統(tǒng)，例：民航售票系統(tǒng)，n個售票處個售票處 semaphore mutex=1,NULL; cobegin program pi P(mutex)； R=xk; /*現(xiàn)有票數(shù)現(xiàn)有票數(shù)*/ if(R=1) R-; xk=R; V(mutex)； 輸出一張機(jī)票；輸出一張機(jī)票； else 顯示顯示“票已售完票已售完”； coend 例：民航售票系統(tǒng)，例：民航售票系統(tǒng)，n個售票處個售票處 semaphore mutex=1,NULL; cobegin program pi P(mutex)； R=xk; /*現(xiàn)有票數(shù)現(xiàn)有票數(shù)*/ if(R=1) R-; xk=R

42、; V(mutex)； 輸出一張機(jī)票；輸出一張機(jī)票； else V(mutex)； 顯示顯示“票已售完票已售完”； coend 設(shè)置一個同步信號量設(shè)置一個同步信號量proceed1proceed1，其初值為，其初值為0 0 semaphore proceed1=0,NULL; cobegin 進(jìn)程進(jìn)程p1 P( proceed1)； 進(jìn)程進(jìn)程p2 V( proceed1)； . coend 教材教材P54P54：圖：圖2-122-12前驅(qū)圖：前驅(qū)圖：S1S2S3S4S5S6abcdefga,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0cobegin s1: s1; v

43、(a); v(b); s2: p(a); s2; v(c); v(d); s3: p(b); s3; v(e); s4: p(c); s4; v(f); s5: p(d); s5; v(g); s6: p(e); p(f); p(g); s6; coend 例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的同步例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的同步 program 司機(jī)司機(jī) 啟動車輛啟動車輛; 正常行車；正常行車； 到站停車；到站停車； program 售票員售票員 關(guān)閉車門關(guān)閉車門; 售票售票 打開車門打開車門; 分析：同步關(guān)系：分析：同步關(guān)系：（1 1）售票員關(guān)閉車門）售票員關(guān)閉車門 司機(jī)啟動車輛

44、司機(jī)啟動車輛（2 2）司機(jī)到站停車）司機(jī)到站停車 售票員打開車門售票員打開車門例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的同步例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的同步 semaphore drive_sem=0,NULL; semaphore conductor_sem=0,NULL; 到站停車到站停車打開車門打開車門關(guān)閉車門關(guān)閉車門啟動車輛啟動車輛 program 司機(jī)司機(jī) 啟動車輛啟動車輛; 正常行車；正常行車； 到站停車；到站停車； program 售票員售票員 關(guān)閉車門關(guān)閉車門; 售票售票 打開車門打開車門; 例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的同步例：一輛公共汽車上，司機(jī)和售票員進(jìn)程的

45、同步 semaphore drive_sem=0,NULL; semaphore conductor_sem=0,NULL; cobegin program 司機(jī)司機(jī) while(1) P(drive_sem)； /*等待關(guān)門等待關(guān)門*/ start a car; driving; /*正常行車正常行車*/ stopping; V(conductor_sem)； / /* *喚醒開門喚醒開門* */ / 到站停車到站停車打開車門打開車門關(guān)閉車門關(guān)閉車門啟動車輛啟動車輛 program 售票員售票員 while(1) close the door; V(drive_sem)； /*喚醒司機(jī)開車喚

46、醒司機(jī)開車*/ sell tickets; /*售票售票*/ P(conductor_sem)； /*等待停車等待停車*/ open the door; coend （1）確定進(jìn)程：確定進(jìn)程： 包括進(jìn)程的數(shù)量、進(jìn)程的工作內(nèi)容。包括進(jìn)程的數(shù)量、進(jìn)程的工作內(nèi)容。（2 2）確定進(jìn)程同步互斥關(guān)系：）確定進(jìn)程同步互斥關(guān)系： 根據(jù)進(jìn)程間是競爭臨界資源還是相互合作處理上的前后根據(jù)進(jìn)程間是競爭臨界資源還是相互合作處理上的前后關(guān)關(guān) 系，來確定進(jìn)程間是互斥還是同步。系，來確定進(jìn)程間是互斥還是同步。（3 3）確定信號量：）確定信號量： 根據(jù)進(jìn)程間的同步互斥關(guān)系確定信號量個數(shù)、含義、初根據(jù)進(jìn)程間的同步互斥關(guān)系確定信號

47、量個數(shù)、含義、初始值，各進(jìn)程需要對信號量進(jìn)行的始值，各進(jìn)程需要對信號量進(jìn)行的PVPV操作。操作。（4 4）用類程序語言描述算法。）用類程序語言描述算法。使用信號量解決進(jìn)程同步問題的步驟：使用信號量解決進(jìn)程同步問題的步驟： 1. . 生產(chǎn)者消費(fèi)者問題生產(chǎn)者消費(fèi)者問題(the producer-consumer problem)問題描述：問題描述：若干進(jìn)程通過若干進(jìn)程通過有限的共享緩沖區(qū)有限的共享緩沖區(qū)交換數(shù)據(jù)。交換數(shù)據(jù)。其中，其中， 生產(chǎn)者生產(chǎn)者 進(jìn)程不斷寫入，而進(jìn)程不斷寫入，而 消費(fèi)者消費(fèi)者 進(jìn)程不斷進(jìn)程不斷讀出；共享緩沖區(qū)共有讀出；共享緩沖區(qū)共有N N個；任何時刻只能有一個進(jìn)程個；任何時刻只

48、能有一個進(jìn)程可對共享緩沖區(qū)進(jìn)行操作?？蓪蚕砭彌_區(qū)進(jìn)行操作。共享緩沖區(qū)生產(chǎn)指針消費(fèi)指針Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer N滿空指針移動方向01234N-12.4經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題 inout 分析分析： 確定進(jìn)程：進(jìn)程數(shù)量及工作內(nèi)容；確定進(jìn)程：進(jìn)程數(shù)量及工作內(nèi)容； 確定進(jìn)程間的關(guān)系：確定進(jìn)程間的關(guān)系： （1 1）互斥：）互斥：多個進(jìn)程間互斥使用同一個緩沖池；多個進(jìn)程間互斥使用同一個緩沖池； （2 2）同步：）同步：當(dāng)緩沖池空時，消費(fèi)者必須阻塞等待；當(dāng)緩沖池空時，消費(fèi)者必須阻塞等待； 當(dāng)緩沖池滿

49、時，生產(chǎn)者必須阻塞等待。當(dāng)緩沖池滿時，生產(chǎn)者必須阻塞等待。 設(shè)置信號量：設(shè)置信號量： MutexMutex：用于訪問緩沖池時的互斥，初值是：用于訪問緩沖池時的互斥，初值是1 1 FullFull：“滿緩沖滿緩沖”數(shù)目，初值為數(shù)目，初值為0 0； EmptyEmpty：“空緩沖空緩沖 數(shù)目，初值為數(shù)目，初值為N N。full+empty=Nfull+empty=N defineN 100 define MAXLEN 80 typedef struct int num; char arrayMAXLEN; Message ; semaphore mutex=1,NULL; semaphore em

50、pty=N,NULL; semaphore full=0,NULL; Message buffersN; int in =0, out=0; 算法描述：算法描述：cobegin program produceri Message p_puf; while(1) produce a message in p_buf; P(empty)； P(mutex)； buffersin = p_buf in =( in +1)%N; V(mutex)； V(full)； program consumerj Message c_buf; while(1) P(full)； P(mutex)； c_buf =

51、 buffersout； out =(out+1)%N; V(mutex)； V(empty)； consume the message in c_buf; coend 如果將消費(fèi)者的兩個如果將消費(fèi)者的兩個P P操作對調(diào)？操作對調(diào)？生產(chǎn)出一產(chǎn)品；生產(chǎn)出一產(chǎn)品； P（ mutex）；）；P（ empty ） ； P（ full）；）；P（ mutex ） ； 從緩沖區(qū)取出一產(chǎn)品；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)將該產(chǎn)品放入緩沖區(qū)； V（mutex）；）；V（ mutex ） ； V（empty）；）； V（ full ） ； 消費(fèi)該產(chǎn)品；消費(fèi)該產(chǎn)品；P（ full）；）；P（ mutex

52、） ；如果將消費(fèi)者的兩個如果將消費(fèi)者的兩個V V操作對調(diào)？操作對調(diào)？生產(chǎn)出一產(chǎn)品；生產(chǎn)出一產(chǎn)品； P（ full）；）；P（ empty ） ； P（ mutex）；）；P（ mutex ） ； 從緩沖區(qū)取出一產(chǎn)品；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)將該產(chǎn)品放入緩沖區(qū)； V（empty）；）；V（ mutex ） ； V（mutex）；）； V（ full ） ； 消費(fèi)該產(chǎn)品；消費(fèi)該產(chǎn)品；V（ mutex）；）；V（ empty ） ；2. 哲學(xué)家進(jìn)餐問題 問題描述：問題描述： 有五個哲學(xué)家有五個哲學(xué)家 坐在一張圓桌旁，在圓桌上有五坐在一張圓桌旁，在圓桌上有五個盤子也五只筷子，他們的生活方

53、式就是交替地進(jìn)個盤子也五只筷子，他們的生活方式就是交替地進(jìn)行思考和進(jìn)餐。平時，一個哲學(xué)家進(jìn)行思考，饑餓行思考和進(jìn)餐。平時，一個哲學(xué)家進(jìn)行思考，饑餓時取其左右兩只筷子，只有拿到這兩只筷子是才能時取其左右兩只筷子，只有拿到這兩只筷子是才能進(jìn)餐；進(jìn)餐完畢，放下筷子繼續(xù)思考。進(jìn)餐；進(jìn)餐完畢，放下筷子繼續(xù)思考。 semaphore chopstick04=1,NULL;cobegin program philosopher（i） P(chopsticki)； P(chopsticki+1 mod 5); eating; V(chopsticki)； V (chopsticki+1 mod 5); coe

54、nd 算法描述：算法描述： semaphore chopstick04=1,NULL; semaphore sm=4,NULL; cobegin program philosopher（i） P(sm)； P(chopsticki)； P(chopsticki+1 mod 5); eating; V(chopsticki)； V (chopsticki+1 mod 5); V（sm）；）； coend 算法描述：算法描述：3. 3. 讀者寫者問題讀者寫者問題(the readers-writers problem) 問題描述：問題描述：對共享資源的讀寫操作，任一時刻對共享資源的讀寫操作，任一時

55、刻“寫者寫者”最多只允許一個，而最多只允許一個，而“讀者讀者”則允許多個則允許多個 當(dāng)有寫者在寫數(shù)據(jù)時，其他寫者和讀者必須等待；當(dāng)有寫者在寫數(shù)據(jù)時，其他寫者和讀者必須等待； 當(dāng)有讀者在讀數(shù)據(jù)時，其他寫者必須等待；但其他當(dāng)有讀者在讀數(shù)據(jù)時，其他寫者必須等待；但其他讀者可以同時讀數(shù)據(jù)。讀者可以同時讀數(shù)據(jù)。 3. 3. 讀者寫者問題讀者寫者問題(the readers-writers problem) 采用信號量機(jī)制：采用信號量機(jī)制： 信號量信號量wmutexwmutex表示表示“允許寫允許寫”，互斥使用數(shù)據(jù)，互斥使用數(shù)據(jù)，初值是，初值是1 1。 公共整形變量公共整形變量ReadcountReadc

56、ount表示表示“正在讀正在讀”的讀的讀者數(shù)，初值是者數(shù)，初值是0 0； 信號量信號量RmutexRmutex：實現(xiàn)多個讀者對：實現(xiàn)多個讀者對ReadcountReadcount的的互斥操作，初值是互斥操作，初值是1 1。 wmutex:semaphore=1 /讀者與寫者之間、寫者與讀者與寫者之間、寫者與 寫者之間互斥使用共享數(shù)據(jù)寫者之間互斥使用共享數(shù)據(jù) readcount: int = 0; /當(dāng)前正在讀的讀者數(shù)量當(dāng)前正在讀的讀者數(shù)量 rmutex :semaphore = 1 /多個讀者互斥使用多個讀者互斥使用 /readcount算法：算法：Cobegin: Reader: begin

57、 Repeat wait(rmutex) if readcount=0 then wait(wmutex); readcount+; signal (rmutex); reading wait(rmutex); readcount-; if readcount=0 then signal(wmutex); signal(rmutex); until false; end;writer: begin repeat: wait(wmutex); writing signal(wmutex); until false end;coend; 3. 3. 寫者優(yōu)先的讀者寫者問題寫者優(yōu)先的讀者寫者問題 問

58、題描述：問題描述：對共享資源的讀寫操作，任一時刻對共享資源的讀寫操作，任一時刻“寫者寫者”最多只允許一個，而最多只允許一個，而“讀者讀者”則允許多個則允許多個 互斥寫、讀寫互斥互斥寫、讀寫互斥 寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）須等待，喚醒時優(yōu)先考慮寫者） 共享讀共享讀 wmutex:semaphore=1 /讀者與寫者之間、寫者與讀者與寫者之間、寫者與 寫者之間互斥使用共享數(shù)據(jù)寫者之間互斥使用共享數(shù)據(jù)S：semaphore=1 /當(dāng)至少有一個寫者準(zhǔn)備訪問共當(dāng)至少有一個寫者準(zhǔn)備訪問共 享數(shù)據(jù)時，它可使后續(xù)的讀者享數(shù)據(jù)時，

59、它可使后續(xù)的讀者 等待寫完成等待寫完成S2：semaphore1 /阻塞第二個以后的等待讀者阻塞第二個以后的等待讀者Readcount,writecount: int = 0,0; /當(dāng)前讀者數(shù)量、當(dāng)前讀者數(shù)量、 寫者數(shù)量寫者數(shù)量mutex1 :semaphore = 1 /多個讀者互斥使用多個讀者互斥使用 readcountmutex2 :semaphore = 1 /多個寫者互斥使用多個寫者互斥使用 writecount算法：算法：Cobegin: Reader: begin Repeat wait(S2); wait(S); wait(mutex1) if readcount=0 the

60、n wait(wmutex); readcount+; signal (mutex1); signal(S); signal(S2); reading wait(mutex1); readcount-; if readcount=0 then signal(wmutex); signal(mutex1); until false; begin;writer: begin repeat; wait(mutex2); if writecount=0 then wait(S); writecount+; signal （mutex2）; wait(wmutex); writing signal(wmutex); wait