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

軟件工程學(xué)院計算機應(yīng)用系目錄1.進(jìn)程的基本概念2.進(jìn)程控制

3.進(jìn)程同步4.經(jīng)典進(jìn)程同步問題5.進(jìn)程通信6.線程的基本概念

是一個有向無循環(huán)圖，圖中每個結(jié)點表示一個語句、一段程序或一個進(jìn)程1.前驅(qū)圖有向邊<Vi,Vj>表示Vj僅在

Vi執(zhí)行完后才能開始執(zhí)行

S1S3S7S6S4S2S52.1進(jìn)程的基本概念順序執(zhí)行的特征順序性封閉性可再現(xiàn)性：程序的運行結(jié)果與其推進(jìn)速度無關(guān)例：程序段

read(disk,&a,4);/*從磁盤讀a*/c=a+2;printf(“c=%f\n”,c);2.程序的順序執(zhí)行→I→C→PI→C→P3.程序的并發(fā)執(zhí)行（1）概念（2）特征間斷(異步)性：“運行－暫停－運行”；失去封閉性不可再現(xiàn)性：進(jìn)程的運行結(jié)果與其推進(jìn)速度有關(guān)。

2.1進(jìn)程的基本概念4.進(jìn)程的定義及特征簡單定義：一個程序的一次運行過程。特征：動態(tài)性：進(jìn)程最基本的特征結(jié)構(gòu)特征：＝程序＋數(shù)據(jù)＋PCB

321該程序所需的相關(guān)數(shù)據(jù)(變量、工作空間，緩沖區(qū)等)該程序的執(zhí)行上下文(Context)一個可執(zhí)行的程序2.1進(jìn)程的基本概念獨立性：是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨立單位，是能獨立運行的基本單位并發(fā)性：程序在建立進(jìn)程后并發(fā)運行異步性：進(jìn)程以不可預(yù)知的速度向前推進(jìn)

進(jìn)程特征定義：可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的一次運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。2.1進(jìn)程的基本概念(1)從定義上看，進(jìn)程是程序處理數(shù)據(jù)的過程，而程序是一組指令的有序集合；(2)進(jìn)程具有動態(tài)性、并發(fā)性、獨立性和異步性等，而程序不具有這些特性；(3)從進(jìn)程結(jié)構(gòu)特性上看，它包含程序、數(shù)據(jù)和PCB；(4)進(jìn)程和程序并非一一對應(yīng)：通過多次執(zhí)行，一個程序可對應(yīng)多個進(jìn)程；通過調(diào)用關(guān)系，一個進(jìn)程可執(zhí)行多個程序。進(jìn)程與程序的區(qū)別2.1進(jìn)程的基本概念就緒狀態(tài)：進(jìn)程分配到必要的資源，等待獲得CPU執(zhí)行的狀態(tài)。組織成一個或多個就緒隊列。運行狀態(tài)：進(jìn)程分配到必要的資源，在CPU上執(zhí)行時的狀態(tài)阻塞狀態(tài)（等待狀態(tài)）：正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)。組織成一個或多個阻塞隊列。5.進(jìn)程的狀態(tài)（1）三種基本狀態(tài)進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換運行就緒阻塞等待事件

(系統(tǒng)服務(wù)請求，如請求I/O)被調(diào)度或分派時間片用完事件發(fā)生進(jìn)程三種基本狀態(tài)的轉(zhuǎn)換：思考問題：1.在進(jìn)程狀態(tài)轉(zhuǎn)換時，下列哪一種狀態(tài)轉(zhuǎn)換是不可能發(fā)生的？

A)就緒態(tài)→運行態(tài)B)運行態(tài)→就緒態(tài)

C)運行態(tài)→等待態(tài)D)阻塞態(tài)→運行態(tài)答案：D2．某進(jìn)程在運行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時該進(jìn)程的狀態(tài)將（）。

A.從就緒變?yōu)檫\行B.從運行變?yōu)榫途w

C.從運行變?yōu)樽枞鸇.從阻塞變?yōu)榫途w答案：C2.1進(jìn)程的基本概念引人掛起狀態(tài)的原因：（1）操作系統(tǒng)的需要；（2）終端用戶的需要；（3）父進(jìn)程請求；（4）負(fù)荷調(diào)節(jié)的需要。進(jìn)程狀態(tài)的轉(zhuǎn)換：（2）掛起狀態(tài)：靜止?fàn)顟B(tài)靜止就緒靜止阻塞掛起掛起激活激活（1）活動就緒靜止就緒（2）活動阻塞靜止阻塞（3）靜止就緒活動就緒（4）靜止阻塞活動阻塞(5)運行狀態(tài)靜止就緒掛起具有掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換活動就緒運行活動阻塞靜止阻塞靜止就緒wakeup(喚醒)事件發(fā)生掛起suspend時間片完被調(diào)度scheduler激活

active掛起

suspend激活

active掛起

suspend等待事件

sleep事件發(fā)生wakeup(喚醒)2.1進(jìn)程的基本概念（3）創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)（1）NULL創(chuàng)建（2）創(chuàng)建活動就緒（3）創(chuàng)建靜止就緒（4）執(zhí)行終止補充：進(jìn)程管理功能：（1）進(jìn)程控制：控制進(jìn)程狀態(tài)轉(zhuǎn)換；（2）進(jìn)程同步：進(jìn)程間運行順序的協(xié)調(diào)：互斥方式；同步方式： （3）進(jìn)程通信：進(jìn)程間的信息交換直接通信；間接通信。

（4）進(jìn)程調(diào)度：進(jìn)程間競爭臨界資源進(jìn)程間相互合作2.1進(jìn)程的基本概念程序：描述進(jìn)程要完成的功能數(shù)據(jù)集合：包含程序運行所需的數(shù)據(jù)和工作區(qū)進(jìn)程控制塊（PCB）：包含進(jìn)程的描述信息和控制信息，是進(jìn)程動態(tài)特性的反映5.進(jìn)程控制塊PCB程序和數(shù)據(jù)集合是進(jìn)程的實體進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志進(jìn)程控制塊是由OS維護的用來記錄進(jìn)程相關(guān)信息的一塊內(nèi)存。2.1進(jìn)程的基本概念進(jìn)程標(biāo)識符：內(nèi)部標(biāo)識符、外部標(biāo)識符處理機狀態(tài)信息：（1）通用寄存器；（2）段寄存器；（3）指令計數(shù)器；（4）程序狀態(tài)字(PSW)；進(jìn)程控制塊（PCB)內(nèi)容32位CPU有8個32位的通用寄存器EAX、EBX、ECX、EDX、ESI、EDI、EBP和ESP

。EAX：稱為累加器，可用于乘、除、輸入/輸出等操作；EBX:稱為基地址寄存器,可作為存儲器指針來使用；ECX:稱為計數(shù)寄存器,控制循環(huán)次數(shù)；EDX:稱為數(shù)據(jù)寄存器,在進(jìn)行乘、除運算時，作為默認(rèn)的操作數(shù)參與運算，也可用于存放I/O的端口地址。ESI：變址寄存器，是內(nèi)存移動和比較操作的源地址寄存器；EDI：變址寄存器，是內(nèi)存移動和比較操作的目標(biāo)地址寄存器EBP：指針寄存器，存放堆棧幀的始址；ESP:指針寄存器，當(dāng)前堆棧棧頂位置。段寄存器是根據(jù)內(nèi)存分段的管理模式而設(shè)置的。內(nèi)存單元的物理地址由段寄存器的值和一個偏移量組合而成。32位CPU有6個，16位CPU有4個

。CS：代碼段寄存器，其值為代碼段的段地址；DS：數(shù)據(jù)段寄存器，其值為數(shù)據(jù)段的地址；ES：附加段寄存器，其值為附加數(shù)據(jù)段的地址；SS：堆棧段寄存器，其值為堆棧段的地址；FS：附加段寄存器，其值為附加數(shù)據(jù)段的地址；GS：附加段寄存器，其值為附加數(shù)據(jù)段的地址。

中斷允許位、陷入標(biāo)志、任務(wù)嵌套標(biāo)志、特權(quán)標(biāo)志、溢出標(biāo)志、符號標(biāo)志、零標(biāo)志、進(jìn)位標(biāo)志等2.1進(jìn)程的基本概念進(jìn)程控制信息：（1）程序和數(shù)據(jù)地址；（2）進(jìn)程同步和通信信息；（3）資源清單；（4）鏈接指針進(jìn)程控制塊內(nèi)容鏈接方式：索引方式進(jìn)程控制塊的組織方式（1）就緒鏈表；（2）執(zhí)行進(jìn)程；（3）阻塞鏈表；（4）空白鏈表。進(jìn)程調(diào)度信息：（1）進(jìn)程狀態(tài)；（2）進(jìn)程優(yōu)先級；（3）事件；（4）其他信息2.2進(jìn)程控制進(jìn)程控制的功能完成進(jìn)程狀態(tài)的轉(zhuǎn)換。原語(primitive)：由若干條指令構(gòu)成的“原子操作(atomicoperation)”過程，完成某種特定的功能，作為一個整體而不可分割－－要么全都完成，要么全都不做。OS的內(nèi)核

為了對進(jìn)程控制，系統(tǒng)中必須設(shè)置一個機構(gòu)，它具有創(chuàng)建撤消以及進(jìn)程通訊和資源管理等功能，這樣結(jié)構(gòu)稱為OS的內(nèi)核(kernel)。2.2進(jìn)程控制用于進(jìn)程控制的原語有：(1)創(chuàng)建進(jìn)程原語 (2)終止進(jìn)程原語

(3)掛起進(jìn)程原語 (4)激活進(jìn)程原語

(5)阻塞進(jìn)程原語 (6)喚醒進(jìn)程原語

進(jìn)程圖概念：

描述系統(tǒng)中進(jìn)程的家族關(guān)系的有向圖。2.系統(tǒng)啟動過程：機器加電，系統(tǒng)復(fù)位：CPU初始化（CS=F000H，IP=FFF0H）Cpu執(zhí)行第一條指令：JMP（ROMBIOS中的啟動程序入口加電自檢POST初始化顯卡、顯示BIOS信息、檢測CPU的類型和工作頻率、測試主機所有的內(nèi)存；檢測系統(tǒng)中的標(biāo)準(zhǔn)硬件設(shè)備：硬盤、CD-ROM、軟驅(qū)、串行接口和并行接口等連接的設(shè)備；檢測和配置即插即用設(shè)備、更新擴展系統(tǒng)配置數(shù)據(jù))系統(tǒng)啟動過程：執(zhí)行19H中斷：BOIS帶的系統(tǒng)初始引導(dǎo)程序讀入引導(dǎo)盤的第一個扇區(qū)到內(nèi)存：若是硬盤：主引導(dǎo)程序+硬盤分區(qū)表讀入可引導(dǎo)分區(qū)第一個扇區(qū)Linux系統(tǒng)啟動過程：執(zhí)行bootsect.s程序：1）將自身從0x7C00處移動到0x90000處；2）調(diào)用BIOS13H中斷讀入setup.s程序到0x90200處；3）讀入磁盤驅(qū)動器參數(shù)4）加載system模塊到0x1000處5）跳轉(zhuǎn)到setup.s程序執(zhí)行。Linux系統(tǒng)啟動過程：執(zhí)行setup.s程序：1）從BIOS中讀取系統(tǒng)數(shù)據(jù)到0x90000處；2）將system模塊從0x10000移動到0x0000處；3）加載段描述符：中斷描述符表寄存器、全局描述符表寄存器；4）重新對中斷進(jìn)行編程；5）轉(zhuǎn)換到保護模式運行：將控制寄存器CR0的位0置1即可；6）跳轉(zhuǎn)到system模塊執(zhí)行；（該模塊包括head.s,main.c程序，內(nèi)核模塊等）系統(tǒng)啟動過程：執(zhí)行head.s程序：1）設(shè)置各個數(shù)據(jù)段寄存器；2）設(shè)置中斷描述符表；設(shè)置全局描述符表；3）設(shè)置頁目錄表；設(shè)置4張頁表；4）設(shè)置頁目錄基址寄存器CR3；5）啟動使用分頁處理：CR0的位31為1；6）跳轉(zhuǎn)到main.c執(zhí)行；head.s執(zhí)行后的內(nèi)存映像：系統(tǒng)啟動過程：執(zhí)行main.c利用setup.s程序取得的系統(tǒng)參數(shù)設(shè)置系統(tǒng)的根文件設(shè)備號及一些內(nèi)存全局變量建立可分頁主內(nèi)存區(qū)的內(nèi)存塊位示圖初始化設(shè)備：塊設(shè)備、字符設(shè)備、tty初始化調(diào)度程序相關(guān)的數(shù)據(jù)結(jié)構(gòu)：如任務(wù)數(shù)組、全局描述符表、時鐘中斷處理句柄等初始化緩沖管理：如建立空閑緩沖區(qū)鏈表等初始化硬盤、軟驅(qū)管理等，并開啟中斷系統(tǒng)啟動過程：執(zhí)行main.c轉(zhuǎn)移到用戶模式運行任務(wù)（進(jìn)程）0任務(wù)0調(diào)用fork()創(chuàng)建進(jìn)程1進(jìn)程1執(zhí)行init()程序Init()：1）調(diào)用setup()，讀取硬盤參數(shù)包括分區(qū)表信息，建立虛擬盤，安裝根文件系統(tǒng)設(shè)備；

2）用讀寫方式打開“/dev/tty00”（終端控制臺）

3）創(chuàng)建login進(jìn)程等待用戶登錄；

4）登錄成功后調(diào)用fork()創(chuàng)建shell進(jìn)程運行/bin/sh程序用戶登錄。作業(yè)調(diào)度。3.引起創(chuàng)建進(jìn)程的事件：

(3)提供服務(wù)。

(4)應(yīng)用請求。

4.創(chuàng)建進(jìn)程原語的工作大致描述為：

申請空白PCB；為新進(jìn)程分配資源；(3)初始化進(jìn)程控制塊PCB；

(4)將新進(jìn)程插入就緒隊列。

調(diào)用alloc_task_struct()分配兩個頁面存放task_struct及系統(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)程插入可運行進(jìn)程隊列3.終止進(jìn)程原語正常結(jié)束2)異常結(jié)束3)外界干預(yù)引起進(jìn)程終止的事件：

OS父進(jìn)程終止父進(jìn)程請求（1）根據(jù)被終止進(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)程終止的過程：

請求系統(tǒng)服務(wù)2)啟動某種操作3)新數(shù)據(jù)尚未到達(dá)4)無新工作可做：服務(wù)進(jìn)程4.阻塞與喚醒原語引起進(jìn)程阻塞與喚醒的事件：

停止當(dāng)前進(jìn)程執(zhí)行，并修改進(jìn)程狀態(tài)：由“執(zhí)行”改為“阻塞”；2)將PCB插入阻塞隊列；

3)轉(zhuǎn)調(diào)度程序重新進(jìn)行調(diào)度。

進(jìn)程阻塞過程：

1)把被阻塞的進(jìn)程從等待該事件的阻塞隊列中移出修改PCB中的進(jìn)程狀態(tài)：由阻塞改為就緒3)將該PCB插入到就緒隊列中進(jìn)程喚醒過程：

5.掛起與激活原語用戶進(jìn)程請求將自己掛起(2)父進(jìn)程請求將自己的某個子進(jìn)程掛起(3)父進(jìn)程或用戶進(jìn)程請求激活指定進(jìn)程，內(nèi)存空間允許引起進(jìn)程掛起和激活的事件

：

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

：

便將其改為靜止就緒；便將其改為靜止阻塞；便將其改為靜止就緒；將進(jìn)程從外存調(diào)入內(nèi)存；修改進(jìn)程狀態(tài)：若是靜止就緒，便將之改為活動就緒；若為靜止阻塞，便將之改為活動阻塞。3）修改PCB中進(jìn)程的程序和數(shù)據(jù)的地址；4）將PCB插入相關(guān)隊列。進(jìn)程激活的過程

：

2.3進(jìn)程同步

臨界資源進(jìn)程間的制約關(guān)系（1）間接制約：相互競爭－－獨占分配到的部分或全部共享資源，“互斥”系統(tǒng)中一次僅允許一個進(jìn)程使用的一類資源。打印機，卡片輸入機，磁帶機、共享變量等?；コ猓褐傅氖菍δ硞€系統(tǒng)資源，一個進(jìn)程正在使用它，另外一個想用它的進(jìn)程就必須等待，而不能同時使用；

（2）直接制約：相互協(xié)作－－等待來自其他進(jìn)程的信息，“同步”,即保證進(jìn)程間的前驅(qū)后繼關(guān)系。共享變量的修改沖突例：民航售票系統(tǒng)，n個售票處

/*ProcessPi,i=1,2,...,n*/…../*按訂票要求找到數(shù)據(jù)庫中的共享數(shù)據(jù)x[k]*//*x[k]存放某月某日某次航班的現(xiàn)有票數(shù)*/R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

輸出一張機票；

}else

顯示“票已售完”；臨界區(qū)的互斥訪問過程：臨界區(qū)：進(jìn)程中訪問臨界資源的程序段。同類臨界區(qū)：對同一臨界資源進(jìn)行操作的程序段。entrysection進(jìn)入?yún)^(qū)exitsection退出區(qū)

criticalsection(臨界區(qū)）

remaindersection（剩余區(qū)）臨界區(qū)(criticalsection)：進(jìn)程中訪問臨界資源的一段代碼。進(jìn)入?yún)^(qū)(entrysection)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。退出區(qū)(exitsection)：釋放臨界資源的一段代碼剩余區(qū)(remaindersection)：代碼中的其余部分?？臻e讓進(jìn)：其他進(jìn)程均不處于臨界區(qū)；忙則等待：已有進(jìn)程處于其臨界區(qū)；有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能"死等"；讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）同步機制應(yīng)遵循的準(zhǔn)則有兩個進(jìn)程P0,P1：設(shè)立一個公用整型變量turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識，假設(shè)初始化turn=0，表示首先輪到P0訪問臨界資源。進(jìn)程互斥的軟件方法算法1：互斥算法while(turn!=0);criticalsectionturn=1;remaindersectionP0的代碼：while(turn!=1);criticalsectionturn=0;remaindersectionP1的代碼：缺點：強制輪流進(jìn)入臨界區(qū)，沒有考慮進(jìn)程的實際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；違背了空閑讓進(jìn)、讓權(quán)等待的原則。設(shè)立一個標(biāo)志數(shù)組flag[2]：描述進(jìn)程是否已在臨界區(qū)，初值均為0(FALSE)，表示進(jìn)程都不在臨界區(qū)。算法2：P0:while(flag[1]);

flag[0]=1;

臨界區(qū)

flag[0]=0;P1:while(flag[0]);

flag[1]=1;

臨界區(qū)

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

flag[0]=0;P1:flag[1]=1;while(flag[0]);臨界區(qū)

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

flag[0]=1;turn=1;

while(flag[1]&&turn==1);臨界區(qū)

flag[0]=0;P1:flag[1]=1;turn=0;

while(flag[0]&&turn==0);臨界區(qū)

flag[1]=0;每一類臨界資源設(shè)置一把鎖lock。lock表示資源的兩種狀態(tài)：TRUE表示正被占用（關(guān)鎖狀態(tài)）；FALSE表示空閑（開鎖狀態(tài)）進(jìn)程互斥的鎖操作方法加鎖操作開鎖操作執(zhí)行臨界區(qū)程序臨界區(qū)太長時，降低了中斷響應(yīng)速度；加鎖時CPU不斷測試，處于忙等待；不能實現(xiàn)多處理機系統(tǒng)中同類臨界區(qū)互斥；優(yōu)點：簡單、可靠鎖操作方法用開、關(guān)中斷實現(xiàn)鎖操作關(guān)中斷開中斷執(zhí)行臨界區(qū)程序缺點：信號量(semaphore)

1.整型信號量最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。又分別稱為P、V操作。

wait和signal操作可描述為：

wait(S)或P(S):whileS≤0dono-op；S∶=S-1;

signal(S)或V(S):S∶=S+1;

缺點：存在“忙等”現(xiàn)象。信號量(semaphore)信號量數(shù)據(jù)結(jié)構(gòu)：typedefstruct{intvalue;/*信號量的值*/PCB*L;/*進(jìn)程阻塞隊列隊首指針*/}semaphore;

2.記錄型信號量Value:初始化為一個非負(fù)整數(shù)值，表示空閑資源總數(shù)－－若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對值表示當(dāng)前等待臨界資源的進(jìn)程個數(shù)。L：初值為空P原語wait(S){S->value--;if(S->value<0)thenBlock(S->L);}semaphore*S;V原語signal(S){S->value++;if(S->value<=0)thenWakeup(S->L);}為臨界資源設(shè)置一個互斥信號量mutex(MUTualExclusion)，其初值為1；在每個進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間；必須成對使用P和V原語，P、V原語不能次序錯誤、重復(fù)或遺漏利用信號量實現(xiàn)互斥：Semaphore

mutex=1P（mutex）criticalsectionV（mutex）remaindersection信號量實現(xiàn)互斥模型：

semaphoremutex={1,NULL};

cobeginprogrampi{while(1){P(mutex)；

criticalsectionforpi;/*進(jìn)程pi臨界區(qū)*/V(mutex)；

remaindersectionforpi;}}

coend例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobeginprogrampi{………R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

輸出一張機票；

}

else{顯示“票已售完”；

}}coend例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobeginprogrampi{………P(mutex)；

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;x[k]=R;V(mutex)；輸出一張機票；

}

else{

顯示“票已售完”；

}}coend例：民航售票系統(tǒng)，n個售票處

semaphoremutex={1,NULL};

cobeginprogrampi{………P(mutex)；

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;x[k]=R;V(mutex)；輸出一張機票；

}

else{V(mutex)；

顯示“票已售完”；

}}coend設(shè)置一個同步信號量proceed1，其初值為0利用信號量實現(xiàn)同步

semaphoreproceed1={0,NULL};

cobegin

進(jìn)程p1………P(proceed1)；

………

進(jìn)程p2………V(proceed1)；

……….

coend

教材P54：圖2-12前驅(qū)圖：S1S2S3S4S5S6abcdefga,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0cobegins1:{s1;v(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ìn)程的同步

program司機{啟動車輛;正常行車；

到站停車；}program售票員{關(guān)閉車門;售票

打開車門;}

分析：同步關(guān)系：（1）售票員關(guān)閉車門→司機啟動車輛（2）司機到站停車→售票員打開車門例：一輛公共汽車上，司機和售票員進(jìn)程的同步

semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};到站停車→打開車門關(guān)閉車門→啟動車輛

program司機{啟動車輛;正常行車；

到站停車；}program售票員{關(guān)閉車門;售票

打開車門;}

例：一輛公共汽車上，司機和售票員進(jìn)程的同步

semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};

cobeginprogram司機{while(1){

P(drive_sem)；

/*等待關(guān)門*/startacar;driving;/*正常行車*/stopping;V(conductor_sem)；/*喚醒開門*/}}

到站停車→打開車門關(guān)閉車門→啟動車輛

program售票員{while(1){closethedoor;V(drive_sem)；

/*喚醒司機開車*/selltickets;/*售票*/

P(conductor_sem)；

/*等待停車*/openthedoor;}}coend（1）確定進(jìn)程：包括進(jìn)程的數(shù)量、進(jìn)程的工作內(nèi)容。（2）確定進(jìn)程同步互斥關(guān)系：根據(jù)進(jìn)程間是競爭臨界資源還是相互合作處理上的前后關(guān)系，來確定進(jìn)程間是互斥還是同步。（3）確定信號量：根據(jù)進(jìn)程間的同步互斥關(guān)系確定信號量個數(shù)、含義、初始值，各進(jìn)程需要對信號量進(jìn)行的PV操作。（4）用類程序語言描述算法。使用信號量解決進(jìn)程同步問題的步驟：

1.生產(chǎn)者－消費者問題(theproducer-consumerproblem)問題描述：若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進(jìn)程不斷寫入，而"消費者"進(jìn)程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。0123…4N-12.4經(jīng)典進(jìn)程同步問題

inout分析：確定進(jìn)程：進(jìn)程數(shù)量及工作內(nèi)容；確定進(jìn)程間的關(guān)系：

（1）互斥：多個進(jìn)程間互斥使用同一個緩沖池；

（2）同步：當(dāng)緩沖池空時，消費者必須阻塞等待；當(dāng)緩沖池滿時，生產(chǎn)者必須阻塞等待。設(shè)置信號量：Mutex：用于訪問緩沖池時的互斥，初值是1Full：“滿緩沖”數(shù)目，初值為0；Empty：“空緩沖"數(shù)目，初值為N。full+empty=N

＃defineN100

＃defineMAXLEN80typedefstruct{intnum;chararray[MAXLEN];}Message;semaphoremutex={1,NULL};semaphoreempty={N,NULL};

semaphorefull={0,NULL};Messagebuffers[N];

intin=0,out=0;

算法描述：cobeginprogramproduceri{Messagep_puf;while(1){produceamessageinp_buf;P(empty)；

P(mutex)；buffers[in]=p_bufin=(in+1)%N;V(mutex)；

V(full)；}}programconsumerj{Messagec_buf;while(1){P(full)；

P(mutex)；

c_buf=buffers[out]；out=(out+1)%N;V(mutex)；

V(empty)；

consumethemessageinc_buf;}}coend如果將消費者的兩個P操作對調(diào)？生產(chǎn)者i

消費者j生產(chǎn)出一產(chǎn)品；

P（mutex）；P（empty

）；

P（full）；P（mutex

）

；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（mutex）；V（mutex

）；

V（empty）；

V（full

）

；消費該產(chǎn)品；P（full）；P（mutex）；如果將消費者的兩個V操作對調(diào)？？生產(chǎn)者i

消費者j生產(chǎn)出一產(chǎn)品；

P（full）；P（empty

）；

P（mutex）；P（mutex

）

；從緩沖區(qū)取出一產(chǎn)品；將該產(chǎn)品放入緩沖區(qū)；

V（empty）；V（mutex

）；

V（mutex）；

V（full

）

；消費該產(chǎn)品；V（mutex）；V（empty）；2.哲學(xué)家進(jìn)餐問題問題描述：

有五個哲學(xué)家坐在一張圓桌旁，在圓桌上有五個盤子也五只筷子，他們的生活方式就是交替地進(jìn)行思考和進(jìn)餐。平時，一個哲學(xué)家進(jìn)行思考，饑餓時取其左右兩只筷子，只有拿到這兩只筷子是才能進(jìn)餐；進(jìn)餐完畢，放下筷子繼續(xù)思考。

semaphorechopstick[0…4]={1,NULL};cobegin

programphilosopher（i）{

P(chopstick[i])；P(chopstick[i+1]mod5);eating;V(chopstick[i])；

V(chopstick[i+1]mod5);}

coend

算法描述：

semaphorechopstick[0…4]={1,NULL};

semaphoresm={4,NULL};

cobegin

programphilosopher（i）{P(sm)；

P(chopstick[i])；P(chopstick[i+1]mod5);eating;V(chopstick[i])；

V(chopstick[i+1]mod5);

V（sm）；}

coend

算法描述：3.讀者－寫者問題(thereaders-writersproblem)問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個當(dāng)有寫者在寫數(shù)據(jù)時，其他寫者和讀者必須等待；

當(dāng)有讀者在讀數(shù)據(jù)時，其他寫者必須等待；但其他讀者可以同時讀數(shù)據(jù)。

3.讀者－寫者問題(thereaders-writersproblem)采用信號量機制：信號量wmutex表示“允許寫”，互斥使用數(shù)據(jù)，初值是1。公共整形變量Readcount表示“正在讀”的讀者數(shù)，初值是0；信號量Rmutex：實現(xiàn)多個讀者對Readcount的互斥操作，初值是1。

wmutex:semaphore=1//讀者與寫者之間、寫者與寫者之間互斥使用共享數(shù)據(jù)readcount:int=0;//當(dāng)前正在讀的讀者數(shù)量

rmutex:semaphore=1//多個讀者互斥使用//readcount算法：Cobegin:

Reader:beginRepeat

wait(rmutex)ifreadcount=0thenwait(wmutex);readcount++;signal(rmutex);

reading…wait(rmutex);readcount--;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;end;writer:beginrepeat:

wait(wmutex);writing…signal(wmutex);

untilfalseend;coend;3.寫者優(yōu)先的讀者－寫者問題問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個互斥寫、讀寫互斥

寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）

共享讀

wmutex:semaphore=1//讀者與寫者之間、寫者與寫者之間互斥使用共享數(shù)據(jù)S：semaphore=1//當(dāng)至少有一個寫者準(zhǔn)備訪問共享數(shù)據(jù)時，它可使后續(xù)的讀者等待寫完成S2：semaphore＝1//阻塞第二個以后的等待讀者Readcount,writecount:int=0,0;//當(dāng)前讀者數(shù)量、

寫者數(shù)量mutex1:semaphore=1//多個讀者互斥使用readcountmutex2:semaphore=1//多個寫者互斥使用writecount算法：Cobegin:Reader:beginRepeatwait(S2);

wait(S);wait(mutex1)ifreadcount=0thenwait(wmutex);readcount++;signal(mutex1);signal(S);signal(S2);

reading…wait(mutex1);readcount--;ifreadcount=0thensignal(wmutex);signal(mutex1);untilfalse;begin;writer:beginrepeat;wait(mutex2);ifwritecount=0thenwait(S);writecount++;signal（mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);writecount--;ifwritecount=0thensignal(S);signal（mutex2）;untilfalse;end;coend;＝》例1某小型超級市場，可容納50人同時購物。入口處有足夠的籃子，每個購物者可拿一只籃子入內(nèi)購物。出口處結(jié)帳，并歸還籃子（出、入口禁止多人同時通過）。試用信號量和P、V操作寫出購物者的同步算法。這是個典型的進(jìn)程互斥問題解答:①所用信號量設(shè)置如下：Ⅰ）資源信號量S，初值為50，用以保證最多可以有50個購物者同時進(jìn)入超市。Ⅱ）互斥信號量mutex，初值為1，用以保證同時只能有一個購物者進(jìn)程進(jìn)入出入口拿起籃子或者結(jié)帳后放下籃子。②用信號量機制給出的每個購物者購物過程的算法描述如下：購物者i（解法一）購物者i（解法二）：

P（S）；

P（S）；P（mutex）；

P（mutex1）；從入口處進(jìn)超市，并取一只籃子；同左；V（mutex）；

V（mutex1）；

進(jìn)超市內(nèi)選購商品；同左；

P（mutex）；

P（mutex2）；

到出口結(jié)帳，并歸還籃子；同左

；

V（mutex）；

V（mutex2）；

從出口離開超市；同左；

V（S）；

V（S）；↓↓結(jié)束.結(jié)束.

出入口在一起：出入口不在一起：＝》例2：桌上有個只能盛得下一個水果的空盤子。爸爸可向盤中放蘋果或桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定：當(dāng)盤子空時，一次只能放入一個水果供吃者取用。試用信號量和P、V操作實現(xiàn)爸爸、兒子和女兒這三個循環(huán)進(jìn)程之間的同步。

本題屬于生產(chǎn)者——消費者問題的變形，相當(dāng)于一個能生產(chǎn)兩種產(chǎn)品的生產(chǎn)者（爸爸）向兩個消費者（兒子和女兒）提供產(chǎn)品的同步問題。因此，可參考生產(chǎn)者與消費者問題的解法。

解答：①所用信號量設(shè)置如下：Ⅰ）同步信號量empty，初值為1，表示盤子是空的，即兒子或女兒已把盤中的水果取走。

Ⅱ）同步信號量orange，初值為0，表示爸爸尚未把桔子放入盤中。Ⅲ）同步信號量apple，初值為0，表示爸爸尚未把蘋果放入盤中。

②使用信號量機制的三個進(jìn)程的同步描述如下：

爸爸進(jìn)程（P）：

兒子進(jìn)程（C1）：

女兒進(jìn)程（C2）：P（empty）；

P（orange）；

P（apple）；將水果放入盤中；

從盤中取出桔子；

從盤中取出蘋果；若放入的是桔子，

V（empty）；

V（empty）；則V（orange）；吃桔子；

吃蘋果；否則，V（apple）；1.管程的引人：2.管程的基本概念：

管程的定義：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。管程的組成：局部于管程的共享變量的說明；對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程；初始化局部變量的語句。

2.5管程機制

2.管程的基本概念：

管程的特性：模塊化；信息隱蔽性；規(guī)定進(jìn)程互斥進(jìn)入管程。3.條件變量：每個獨立的條件變量是和進(jìn)程需要等待的某種原因（或說條件）相聯(lián)系的，當(dāng)定義一個條件變量時，系統(tǒng)就建立一個相應(yīng)的等待隊列。關(guān)于條件變量的兩個操作：C.wait:

阻塞調(diào)用進(jìn)程，并使管程可用；C.signal:

喚醒相應(yīng)條件變量上的等待進(jìn)程。4.利用管程解決生產(chǎn)者--消費者問題：管程定義：

typePC=monitor in,out,count:int;

buffer[n]:item;

notfull,notempty:condition; procedureput(item)procedureget(item){{ifcount>=nthenifcount<=0then

notfull.wait;notempty.wait;

buffer(in)=item;nextc=buffer(out);in=(in+1)modn;out=(out+1)modn;count=count+1;count=count-1;

notempty.signal;notfull.signal;}}Beginin=out=count=0;end4.利用管程解決生產(chǎn)者--消費者問題：生產(chǎn)者和消費者的算法描述：

procedureproducerprocedureconsumer{{

while(true)while(true){{produceranitem;PC.get(item);

PC.put(item);consumetheitem;}}}}

P(PCmutex);PC.put(item);V(PCmutex);管程結(jié)構(gòu)示意圖：

進(jìn)程等待隊列局部數(shù)據(jù)定義條件C1隊列

條件變量

初始化語句C1.wait

過程1

過程2條件Cn隊列…

過程nCn.wait

入管程出管程C1.signalCn.signal

管程

管程等待區(qū)

2.6進(jìn)程通信

低級通信：高級通信：一、進(jìn)程間通信的類型：是指進(jìn)程間的信息交換。效率低；通信對用戶不透明。用戶直接利用操作系統(tǒng)所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。二、高級通信類型1共享存儲器系統(tǒng)通信(Shared-MemorySystem)2管道(pipe)通信3消息傳遞系統(tǒng)通信(MessagepassingSystem)

1共享存儲器系統(tǒng)通信通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲器實現(xiàn)進(jìn)程之間的信息交換?？煞殖蓛煞N類型：基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式：低級通信基于共享存儲區(qū)的通信方式：高級通信通信過程：linux中相應(yīng)系統(tǒng)調(diào)用（1）申請共享存儲分區(qū)；shmget（）（2）將共享存儲分區(qū)映射到shmat（）本進(jìn)程地址空間中；（3）進(jìn)行數(shù)據(jù)讀寫；（4）釋放共享存儲分區(qū)；shmdt（）共享存儲器系統(tǒng)通信方式的特點：

最大的特點是沒有中間環(huán)節(jié)，直接把共享內(nèi)存映射到不同進(jìn)程的虛擬地址空間中，進(jìn)程可直接進(jìn)行訪問，通信直接快速。該通信機制沒有提供進(jìn)程同步機制。管道：用于連接一個讀進(jìn)程和一個寫進(jìn)程，以實現(xiàn)它們之間通信的共享文件（pipe文件，又稱為FIFO文件）

無名管道：int

pipe(intfd[2]),用于父子或兄弟進(jìn)程間通信有名管道：

int

mkfifo(constchar*pathname,mode_tmode)用于任意進(jìn)程間通信（又稱FIFO通信）2管道（pipe）通信兩種實現(xiàn)機制：FIFO文件的讀出和寫入：嚴(yán)格遵循先進(jìn)先出，不支持文件定位操作。管道通信應(yīng)注意的問題：2.管道通信機制：無名管道的使用：舉例：Linux中利用無名管道實現(xiàn)進(jìn)程間的通信。父進(jìn)程創(chuàng)建子進(jìn)程，子進(jìn)程向管道中寫一條消息，而父進(jìn)程從管道中讀出該信息： #include<stdio.h> #include<unistd.h> #include<signal.h> main() { intpid1,fd[2]; charbuf[50]; pipe(fd);2.管道通信機制：if((pid1=fork())<0){ printf("forkerror.\n"); exit(1);} if(pid1==0){ lockf(fd[0],1,0); write(fd[1],"Iamchild.\n",15); lockf(fd[0],0,0); exit(0);}else{ wait(0); lockf(fd[1],1,0); read(fd[0],buf,15);lockf(fd[0],0,0); printf("%s",buf); exit(0); }}3消息傳遞系統(tǒng)在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換是以消息(message，在計算機網(wǎng)絡(luò)中又稱報文)為單位。程序員直接利用系統(tǒng)提供的一組通訊命令（原語）來實現(xiàn)通訊。（1）消息格式：消息頭消息正文消息頭：存放消息傳輸時所需的控制信息。消息類型：定長消息；變長消息。直接通信方式（消息緩沖隊列機制）：發(fā)送進(jìn)程直接將消息發(fā)送給接收進(jìn)程，并將它掛在接收進(jìn)程的消息緩沖隊列上。接收進(jìn)程從消息緩沖隊列中取得消息。故稱為消息緩沖機制。（2）消息傳遞系統(tǒng)實現(xiàn)類型：發(fā)送進(jìn)程發(fā)送區(qū)設(shè)置公用緩沖區(qū)復(fù)制消息接收隊列掛入取消息消息緩沖區(qū)復(fù)制接收進(jìn)程接收區(qū)消息緩沖機制（直接通信）兩通信進(jìn)程必須滿足下列條件：互斥：在發(fā)送進(jìn)程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消息隊列時，應(yīng)禁止其他進(jìn)程對緩沖區(qū)消息隊列的訪問。同理，接收進(jìn)程取消息時也禁止其他進(jìn)程訪問緩沖區(qū)消息隊列。同步：