計(jì)算機(jī)操作系統(tǒng)課件(第四版)第二章

第二章

進(jìn)程管理2.1 前驅(qū)圖和程序執(zhí)行2.2進(jìn)程的描述2.3進(jìn)程控制2.4進(jìn)程同步2.5經(jīng)典進(jìn)程同步問題2.6進(jìn)程通信2.7線程的基本概念2.1前驅(qū)圖和程序執(zhí)行程序的順序執(zhí)行前趨圖與前趨關(guān)系程序的并發(fā)執(zhí)行1、程序順序執(zhí)行的特征(1)程序的順序執(zhí)行語句1語句2語句3語句4語句5I1C1P1I2C2P2程序1程序2(2)特征①順序性②封閉性③可再現(xiàn)性2、前趨圖與前趨關(guān)系前趨圖(PrecedenceGraph)一個(gè)有向無循環(huán)圖描述程序或程序段之間執(zhí)行的前后關(guān)系前趨關(guān)系“”如果：(Pi,Pj)∈，也可以寫成：PiPj則稱：Pi是Pj的直接前趨,Pj是Pi的直接后繼初始結(jié)點(diǎn)：沒有前趨終止結(jié)點(diǎn)：沒有后繼P1P2P3P8P6P5P7P4P9觀察下圖，初始結(jié)點(diǎn)是哪個(gè)？終止結(jié)點(diǎn)是哪個(gè)？有哪些前驅(qū)關(guān)系？思考：下圖是否為前趨圖？S1S2S33、程序的并發(fā)執(zhí)行I1C1P1I2C2P2I3C3P3I4C4P4輸入程序計(jì)算程序打印程序?qū)τ谙率鏊臈l語句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4并發(fā)執(zhí)行時(shí)的特征間斷性——“停停走走”失去封閉性——原因：多個(gè)程序共享資源不可再現(xiàn)性程序A{n=n+1;}程序B{print(n);n=0;}

例如:有兩個(gè)循環(huán)程序A和B，共享一個(gè)變量n。程序A和B以不同的速度運(yùn)行?？赡艹霈F(xiàn)的情況如下：1、A快B慢，得到的n值為：n+1,n+1,02、B快A慢，得到的n值為：n,0,13、n:=n+1在print(n)和n:=0之間，如圖，得到的n值為

n,n+1,02.2進(jìn)程的描述進(jìn)程的定義和特征進(jìn)程的基本狀態(tài)和轉(zhuǎn)換掛起操作和狀態(tài)轉(zhuǎn)換進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)2.2.1、進(jìn)程的定義和特征進(jìn)程的定義進(jìn)程的特征進(jìn)程的定義進(jìn)程：進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。進(jìn)程實(shí)體＝程序段＋相關(guān)的數(shù)據(jù)段＋PCB進(jìn)程組成系統(tǒng)數(shù)據(jù)段，PCB程序段數(shù)據(jù)段LinuxLinux的進(jìn)程實(shí)體組成Linux進(jìn)程是由三部分組成：正文段、用戶數(shù)據(jù)段和系統(tǒng)數(shù)據(jù)段。(1)正文段（text）——程序段正文段是只能讀不能修改的指令代碼，它允許系統(tǒng)中多個(gè)進(jìn)程共享這一代碼段。(2)用戶數(shù)據(jù)段（usersegment）——數(shù)據(jù)段用戶數(shù)據(jù)段是進(jìn)程執(zhí)行時(shí)直接操作的所有數(shù)據(jù)（包括全部變量在內(nèi)），這些信息是可以被修改的。(3)系統(tǒng)數(shù)據(jù)段（systemsegment）——PCB

系統(tǒng)數(shù)據(jù)段存放著進(jìn)程的控制信息，即進(jìn)程控制塊（PCB），它存放了程序的運(yùn)行環(huán)境。PCB程序段數(shù)據(jù)段進(jìn)程的結(jié)構(gòu)圖示：進(jìn)程控制塊動(dòng)態(tài)特征的集中反映描述要完成的功能操作對(duì)象及工作區(qū)進(jìn)程的其他定義：進(jìn)程是一個(gè)具有一定獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的一次動(dòng)態(tài)執(zhí)行過程。進(jìn)程是并發(fā)程序的一次執(zhí)行過程。是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位。進(jìn)程是可以和別的計(jì)算并發(fā)執(zhí)行的計(jì)算。進(jìn)程與程序的區(qū)別進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進(jìn)程是程序的執(zhí)行。進(jìn)程是暫時(shí)的，程序的永久的：進(jìn)程是一個(gè)狀態(tài)變化的過程，程序可長久保存。進(jìn)程與程序的組成不同：進(jìn)程的組成包括程序、數(shù)據(jù)和進(jìn)程控制塊（即進(jìn)程狀態(tài)信息）。進(jìn)程與程序的對(duì)應(yīng)關(guān)系：通過多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程；通過調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序。進(jìn)程的特征動(dòng)態(tài)性：“它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤銷而消亡”。進(jìn)程具有動(dòng)態(tài)的地址空間（數(shù)量和內(nèi)容），地址空間上包括：代碼（指令執(zhí)行和CPU狀態(tài)的改變）數(shù)據(jù)（變量的生成和賦值）系統(tǒng)控制信息（進(jìn)程控制塊PCB的生成和刪除）獨(dú)立性：進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立調(diào)度的基本單位。各進(jìn)程的地址空間相互獨(dú)立。并發(fā)性：引入進(jìn)程的目的正是為了使其程序能和其他進(jìn)程的程序并發(fā)執(zhí)行；異步性：進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)結(jié)構(gòu)性：進(jìn)程由程序段、數(shù)據(jù)段及PCB三部分組成，在Linux中稱為“進(jìn)程映像”2.2.2進(jìn)程的基本狀態(tài)及轉(zhuǎn)換就緒狀態(tài)（Ready）得到了除CPU以外的所有必要資源執(zhí)行狀態(tài)（Running）已獲得處理機(jī)，程序正在被執(zhí)行阻塞狀態(tài)（Blocked）因等待某事件發(fā)生而暫時(shí)無法繼續(xù)執(zhí)行，從而放棄處理機(jī)，使程序執(zhí)行處于暫停狀態(tài)1、進(jìn)程的三種基本狀態(tài)中斷接納完成進(jìn)程調(diào)度事件發(fā)生等待某事件創(chuàng)建終止就緒執(zhí)行阻塞進(jìn)程基本狀態(tài)轉(zhuǎn)換圖創(chuàng)建狀態(tài)為新進(jìn)程創(chuàng)建PCB，填寫信息，該進(jìn)程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊(duì)列中。引入創(chuàng)建狀態(tài)可保證進(jìn)程的調(diào)度在創(chuàng)建工作完成后，確保對(duì)PCB操作的完整性。終止?fàn)顟B(tài)等待OS進(jìn)行善后處理將PCB清零，將PCB空間返還系統(tǒng)。終止態(tài)的進(jìn)程不能再執(zhí)行，但需等待其它進(jìn)程完成對(duì)它的信息提取后，OS再將它刪除。進(jìn)程的掛起狀態(tài)（靜止?fàn)顟B(tài)）引入父進(jìn)程考查和修改、協(xié)調(diào)子進(jìn)程間的活動(dòng)操作系統(tǒng)協(xié)調(diào)資源使用或進(jìn)行記賬終端用戶的請(qǐng)求，希望自己的程序暫時(shí)靜止下來負(fù)荷調(diào)節(jié)的需要，如實(shí)時(shí)緊急任務(wù)，由系統(tǒng)把一些不重要的進(jìn)程掛起內(nèi)存外存活動(dòng)靜止進(jìn)程的掛起狀態(tài)掛起就緒掛起阻塞活動(dòng)就緒執(zhí)行活動(dòng)阻塞掛起I/O請(qǐng)求掛起激活掛起調(diào)度釋放激活釋放喚醒1、操作系統(tǒng)中用于管理控制的數(shù)據(jù)結(jié)構(gòu)資源信息表、進(jìn)程信息表：數(shù)據(jù)結(jié)構(gòu)表征其實(shí)體。包含了資源或進(jìn)程的標(biāo)識(shí)、描述、狀態(tài)等信息及一批指針。2.2.4、進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)內(nèi)存設(shè)備文件進(jìn)程內(nèi)存表設(shè)備表文件表進(jìn)程表1進(jìn)程表n進(jìn)程1進(jìn)程n...進(jìn)程實(shí)體及所用資源列表2、PCB(ProcessControlBlock)PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。OS是根據(jù)PCB來對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。是進(jìn)程存在的唯一標(biāo)志。PCB可被操作系統(tǒng)中的多個(gè)模塊讀或修改，如被調(diào)度程序、資源分配程序、中斷處理程序以及監(jiān)督和分析程序讀或修改。PCB經(jīng)常被系統(tǒng)訪問，故應(yīng)常駐內(nèi)存。2.2.4、進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)Linux的PCB結(jié)構(gòu)3、PCB中的信息進(jìn)程標(biāo)識(shí)符：唯一的標(biāo)識(shí)一個(gè)進(jìn)程內(nèi)部標(biāo)識(shí)（OS）外部標(biāo)識(shí)（由創(chuàng)建者提供，由字母數(shù)字組成）處理機(jī)狀態(tài)：由CPU的各種寄存器中的內(nèi)容組成。通用R指令計(jì)數(shù)器PC程序狀態(tài)字PSW用戶棧指針進(jìn)程調(diào)度信息：進(jìn)程狀態(tài)進(jìn)程優(yōu)先級(jí)其它信息等待事件（阻塞原因）進(jìn)程控制信息：程序和數(shù)據(jù)的地址同步和通信機(jī)制資源清單鏈接指針4、進(jìn)程控制塊的組織方式PCB數(shù)目一個(gè)系統(tǒng)中的PCB數(shù)目可為數(shù)十個(gè)、數(shù)百個(gè)甚至數(shù)千個(gè)線性方式把所有的PCB都組織在一張線性表中，將表的首地址放在內(nèi)存的專用區(qū)中。鏈接方式把具有同一狀態(tài)的PCB，用其鏈接字鏈接成一個(gè)隊(duì)列就緒隊(duì)列、若干個(gè)阻塞隊(duì)列、空隊(duì)列索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立相應(yīng)的索引表就緒索引表、阻塞索引表等，索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專用單元中。PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……PCB線性表示示意圖PCBn執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911……PCB鏈接隊(duì)列示意圖PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針按索引方式組織PCB第三節(jié)

進(jìn)程的控制系統(tǒng)內(nèi)核進(jìn)程創(chuàng)建進(jìn)程撤消進(jìn)程阻塞進(jìn)程喚醒進(jìn)程掛起與激活進(jìn)程管理中最基本功能是進(jìn)程控制。進(jìn)程控制的作用：創(chuàng)建新進(jìn)程，終止已完成進(jìn)程，并負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換。進(jìn)程控制是由OS內(nèi)核中的原語實(shí)現(xiàn)的。OS內(nèi)核：把一些與硬件緊密相關(guān)的模塊（如中斷）、各種常用設(shè)備的驅(qū)動(dòng)程序、運(yùn)行頻率較高的模塊（時(shí)鐘管理、進(jìn)程調(diào)度等）以及為許多模塊公用的一些基本操作，安排在靠近硬件的軟件層次中，以提高OS的運(yùn)行效率。OS內(nèi)核是常駐內(nèi)存的程序和數(shù)據(jù)。2.3.1操作系統(tǒng)內(nèi)核原語：是由若干條指令組成的，用于完成一定功能的一個(gè)過程。具有不可分割性。

具有原子性。即：原語的執(zhí)行必須是連續(xù)的，在執(zhí)行的過程中不允許被中斷。處理機(jī)的執(zhí)行狀態(tài)具有兩種狀態(tài)：核心態(tài)(系統(tǒng)態(tài)、管態(tài))：OS的管理程序執(zhí)行時(shí)處理機(jī)所處狀態(tài)。具有較高的特權(quán)，能執(zhí)行一切指令，訪問所有寄存器和存儲(chǔ)區(qū)。OS運(yùn)行在系統(tǒng)態(tài)。用戶態(tài)（目態(tài)）：用戶程序執(zhí)行時(shí)處理機(jī)所處狀態(tài)。具有較低特權(quán)的執(zhí)行狀態(tài)，僅能執(zhí)行規(guī)定的指令訪問制定的寄存器和存儲(chǔ)區(qū)。應(yīng)用程序一般運(yùn)行在用戶態(tài)。

1、進(jìn)程創(chuàng)建（Creat()）進(jìn)程之間的關(guān)系：父、子進(jìn)程與祖先進(jìn)程：PCB中標(biāo)識(shí)繼承歸還資源、“父”創(chuàng)建“子”、父撤子消引起創(chuàng)建進(jìn)程的事件用戶登錄、作業(yè)調(diào)度、提供服務(wù)、應(yīng)用請(qǐng)求進(jìn)程創(chuàng)建的過程申請(qǐng)空白PCB、為新進(jìn)程分配資源、初始化PCB、插入就緒進(jìn)程隊(duì)列PDPBPEPCPFPAPIPHPGPJPKPLPMPNHD就緒隊(duì)列指針PCB15PCB2PCB3PCB4PCB513PCB60PCB7PCB89PCB912PCB10PCB11PCB1225PCB136……空PCB隊(duì)列指針RAM程序+數(shù)據(jù)PCB80PCB682、進(jìn)程撤消（Terminat()）引起進(jìn)程終止（Termination）的事件正常結(jié)束：執(zhí)行到最后的結(jié)束指令、中斷異常結(jié)束：出現(xiàn)錯(cuò)誤或因故障而被迫終止外界干擾：進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行進(jìn)程撤消的過程檢索進(jìn)程狀態(tài)、結(jié)束并置調(diào)度標(biāo)志、撤銷其所有的子進(jìn)程、歸還資源、移出隊(duì)列一個(gè)進(jìn)程可以向其父進(jìn)程申請(qǐng)撤消自己；也可以因父進(jìn)程的被撤銷而被同時(shí)撤消。PDPBPEPCPFPAPIPHPGPJPKPLPMPN3、進(jìn)程阻塞（Block()）引起阻塞的事件請(qǐng)求系統(tǒng)服務(wù)、啟動(dòng)某種操作、數(shù)據(jù)尚未到達(dá)、無新工作可做進(jìn)程阻塞的過程發(fā)現(xiàn)上述事件，調(diào)用阻塞原語把自己阻塞停止進(jìn)程的執(zhí)行，修改PCB中的狀態(tài)信息，并將其插入相應(yīng)的阻塞隊(duì)列轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度4、進(jìn)程喚醒（Wakeup()）引起喚醒的事件與引起阻塞的事件相對(duì)應(yīng)進(jìn)程喚醒的過程阻塞進(jìn)程所期待的事件出現(xiàn)，有關(guān)的進(jìn)程調(diào)用喚醒原語，將等待該事件的進(jìn)程喚醒將PCB從阻塞隊(duì)列中移出，修改PCB中的狀態(tài)信息，再將其插入到就緒進(jìn)程隊(duì)列中阻塞與喚醒要匹配使用，以免造成“永久阻塞”5、進(jìn)程掛起與激活

（Suspend()、Active()）進(jìn)程掛起檢查被掛進(jìn)程的狀態(tài)，改為相應(yīng)的掛起狀態(tài)。把進(jìn)程的PCB復(fù)制到指定的區(qū)域。最后，轉(zhuǎn)向調(diào)度程序重新調(diào)度。進(jìn)程激活先將進(jìn)程從外存調(diào)入內(nèi)存。檢查該進(jìn)程的現(xiàn)行狀態(tài)，改為相應(yīng)的活動(dòng)狀態(tài)。根據(jù)優(yōu)先級(jí)確定是否需要重新調(diào)度。第四節(jié)

進(jìn)程同步

進(jìn)程同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程之間有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性?；靖拍钣布綑C(jī)制信號(hào)量機(jī)制信號(hào)量的應(yīng)用進(jìn)程互斥：一個(gè)進(jìn)程正在訪問臨界資源，另一個(gè)要訪問該資源的進(jìn)程必須等待。并發(fā)執(zhí)行可產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤2.4.1基本概念兩種形式的制約關(guān)系直接相互制約：源于進(jìn)程間的合作間接相互制約：源于進(jìn)程對(duì)資源的共享進(jìn)程同步：合作完成同一個(gè)任務(wù)的多個(gè)進(jìn)程，在執(zhí)行速度或某些時(shí)序點(diǎn)上必須相互協(xié)調(diào)的合作關(guān)系。進(jìn)程同步舉例：例1：接力賽例2：司機(jī)－售票員司機(jī)：P1while(true){

啟動(dòng)車輛；正常運(yùn)行；到站停車；

}售票員：P2while(true){

關(guān)門；售票；開門；

}互斥現(xiàn)象火車到站的調(diào)度

火車1火車2火車3…

站臺(tái)軌道例1：兩個(gè)同學(xué)做搶椅子的游戲。同學(xué)甲……if有空椅子then坐下……同學(xué)乙……if有空椅子then搬走……例2：民航售票系統(tǒng)主機(jī)A窗口B窗口C窗口D窗口每個(gè)進(jìn)程執(zhí)行的操作：設(shè)x表示某航班的票數(shù)。

……ifx>0thenx:=x-1;……在某時(shí)刻x=1，有a、b兩人分別去A窗口、B窗口買票，分析售票情況：時(shí)間片到a人b人例3：交通流量統(tǒng)計(jì)統(tǒng)計(jì)在一定的時(shí)間段之內(nèi)在路面上通過的車輛數(shù)量。利用計(jì)算機(jī)計(jì)數(shù)車輛數(shù)。S表示車輛數(shù)。S:=0;Delay(600);Write(S);中斷處理程序：S:=S+1;例4：存儲(chǔ)管理分配進(jìn)程（B）……ifx<Bthen等待elsex=x-B;……回收進(jìn)程（B）……x=x+B;喚醒；……(x為可用內(nèi)存空間)例5：哲學(xué)家就餐問題五個(gè)哲學(xué)家圍著桌子坐，工作方式：思考；

if餓了{(lán)拿左叉子；拿右叉子；吃飯；放左叉子；放右叉子；}//只能拿靠近自己左右兩邊的叉子臨界區(qū)（臨界段）臨界資源：一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源臨界區(qū)：每個(gè)進(jìn)程中訪問臨界資源的代碼段臨界區(qū)的使用原則：各進(jìn)程互斥地進(jìn)入臨界區(qū)，可實(shí)現(xiàn)互斥訪問臨界資源criticalsection;//臨界區(qū)repeatuntilfalse;entrysection//進(jìn)入?yún)^(qū)exitsection//退出區(qū)remaindersection;//剩余區(qū)同步應(yīng)遵循的規(guī)則空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待P1：

a:=a+1print(a)互斥P2：a:=a-1print(a)互斥P3：ifa<0thena:=a+1elsea:=a-1互斥程序中的臨界區(qū)?？疾熳兞縜2.4.2、硬件同步機(jī)制關(guān)中斷利用Test-and-Set指令實(shí)現(xiàn)互斥利用Swap指令實(shí)現(xiàn)進(jìn)程互斥

計(jì)算機(jī)提供一些特殊的硬件指令，允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行檢測和修正，或者是對(duì)兩個(gè)字的內(nèi)容進(jìn)行交換。利用這些特殊指令解決臨界區(qū)問題。臨界區(qū)的標(biāo)志可以看做一個(gè)鎖。鎖開、鎖關(guān)兩種狀態(tài)關(guān)中斷關(guān)中斷是實(shí)現(xiàn)互斥的最簡單的方法之一。進(jìn)入鎖測試之前關(guān)閉中斷，直至完成鎖測試，并上鎖之后才能打開中斷。進(jìn)程在臨界區(qū)中執(zhí)行期間，計(jì)算機(jī)系統(tǒng)不響應(yīng)中斷，也不會(huì)引發(fā)進(jìn)程調(diào)度。缺點(diǎn)：濫用關(guān)中斷權(quán)利關(guān)中斷時(shí)間過長，會(huì)影響系統(tǒng)效率不適用于多CPU系統(tǒng)利用Test-and-Set指令實(shí)現(xiàn)互斥是一種借助TS（測試建立）硬件指令實(shí)現(xiàn)互斥TS指令的一般性描述：booleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}do{...whileTS(&lock)；criticalsection;lock=False;remaindersection;}while(TRUE)利用Swap指令實(shí)現(xiàn)進(jìn)程互斥對(duì)換指令(用于交換兩個(gè)字的內(nèi)容)：booleanswap(boolean*a,*b){booleantemp;temp=*a;*a=*b;*b=temp;}do{key=TRUE；do{swap(&lock,&key);}while(key!=FALSE);criticalsection;lock=False;remaindersection;}while(TRUE)3、信號(hào)量（燈）機(jī)制1965年，荷蘭人Dijkstra首先提出信號(hào)量機(jī)制信號(hào)量（Semaphores）用于表示資源數(shù)目或請(qǐng)求使用某一資源的進(jìn)程個(gè)數(shù)的數(shù)據(jù)結(jié)構(gòu)。信號(hào)量是一個(gè)被保護(hù)的變量，它的值只能通過初始化和兩個(gè)wait、signal原語來操作——作為OS核心代碼執(zhí)行。wait操作（P原語）——進(jìn)程申請(qǐng)使用資源的操作（或申請(qǐng)進(jìn)入臨界區(qū)的操作），類似于進(jìn)入?yún)^(qū)的功能。P是荷蘭語的test(proberen)signal操作（V原語）——進(jìn)程用此釋放臨界資源，類似于退出區(qū)的功能。V是荷蘭語的increment(verhogen)Dijkstra（迪杰斯特拉）信號(hào)量的類型：整型：S為初值非負(fù)的整型變量，通常描述資源的狀態(tài)或可用資源的數(shù)量。記錄型：二元組(S,Q)，Q初始狀態(tài)為空的隊(duì)列。AND型：一次需要多個(gè)共享資源，改進(jìn)wait-signal操作。信號(hào)量集：一次需要N個(gè)多類資源，改進(jìn)wait-signal操作。整型信號(hào)量

intS;//Semaphore wait(S){whileS≦0dono-op；

S--;} signal(S) {S++;} wait(s)和signal(s)是原子操作只要信號(hào)量S≦0就不斷測試，不滿足讓權(quán)等待是一個(gè)記錄型的數(shù)據(jù)結(jié)構(gòu)，包含兩個(gè)數(shù)據(jù)項(xiàng)，一是記數(shù)值域，另一是等待該信號(hào)量的進(jìn)程隊(duì)列首指針域。描述如下：記錄型信號(hào)量：typedefStructSemaphore{intvalue;//整型變量

List_of_processL;//進(jìn)程等待隊(duì)列

}S;SvalueLwait(S){S.value--;ifS.value<0thenblock（S.L）;//將該進(jìn)程狀態(tài)置為等待狀態(tài)；并將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列S.L末尾}wait(S)原語描述如下：執(zhí)行一次wait操作意味著請(qǐng)求分配一個(gè)單位的資源，因此描述為:s.value=s.value-1。減1后：若s.value≥0，則進(jìn)程繼續(xù)進(jìn)行；若s.value＜0，表示已無資源可用，因此請(qǐng)求該資源的進(jìn)程將被阻塞，要把它排在信號(hào)量s的等待隊(duì)列中，此時(shí)，s.value的絕對(duì)值等于該信號(hào)量等待隊(duì)列上的進(jìn)程數(shù)目。s.value的物理含義：信號(hào)量的物理意義：S>0：S表示可用資源的個(gè)數(shù)

S=0：S表示無資源，無等待進(jìn)程

S<0：|S|表示等待隊(duì)列中進(jìn)程的個(gè)數(shù)signal(S){S.value++;ifS.value≤0thenwakeup（S.L）;//喚醒相應(yīng)等待隊(duì)列中等待的第一個(gè)進(jìn)程：改變其狀態(tài)為就緒態(tài)；并將其插入到就緒隊(duì)列。}signal(S)原語描述如下：

執(zhí)行一次signal操作意味著釋放一個(gè)單位的資源，故s.value=s.value+1。加1后：若s.value＞0，則進(jìn)程繼續(xù)；若s.value≤0，表示信號(hào)量請(qǐng)求隊(duì)列中仍有因請(qǐng)求該資源而被阻塞的進(jìn)程，因此應(yīng)把隊(duì)列中的一個(gè)或幾個(gè)進(jìn)程喚醒，使之轉(zhuǎn)至就緒隊(duì)列中。舉例：已知系統(tǒng)中有兩臺(tái)打印機(jī)，又有A、B、C、D四個(gè)進(jìn)程都要使用打印機(jī)，分析其wait、signal操作和信號(hào)量變化。設(shè)打印機(jī)資源信號(hào)量為s，初值為2。A：{wait(s);

使用打印機(jī)；

signal(s);}B：{wait(s);

使用打印機(jī)；

signal(s);}C：{wait(s);

使用打印機(jī)；

signal(s);}D：{wait(s);

使用打印機(jī)；

signal(s);}s=1s=0s=-1s=-2s=-1s=0s=1s=24、信號(hào)量的應(yīng)用實(shí)現(xiàn)進(jìn)程互斥例如：兩個(gè)進(jìn)程都使用一臺(tái)打印機(jī)實(shí)現(xiàn)進(jìn)程同步例如：矩陣運(yùn)算A＋B利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系(1)實(shí)現(xiàn)進(jìn)程互斥mutex=1；

…wait(mutex))

臨界區(qū)代碼

signal(mutex)

…

SAVE：

{m1=amountm1=m1+10amount=m1}TAKE：

{m2=amountm2=m2-10amount=m2}如何用wait、signal操作實(shí)現(xiàn)兩并發(fā)進(jìn)程的互斥執(zhí)行？例2

兄弟倆共用一個(gè)賬號(hào)，每次僅限存取十元錢，存錢和取錢的進(jìn)程分別如下所示：

amount=0parbeginSAVE;TAKEparend解決方法：設(shè)信號(hào)量mutex（初值為1）控制進(jìn)程對(duì)變量amount的互斥使用。amount=0parbeginSAVE;TAKEparendSAVE：

{wait(mutex)m1=amountm1=m1+10amount=m1signal(mutex)}

TAKE：

{

wait(mutex)m2=amountm2=m2-10amount=m2signal(mutex)}

(2)實(shí)現(xiàn)進(jìn)程同步例3：矩陣A+B運(yùn)算(3)實(shí)現(xiàn)前趨關(guān)系前趨關(guān)系：并發(fā)執(zhí)行的進(jìn)程P1和P2中，分別有代碼C1和C2，要求C1在C2開始前完成。為該前趨關(guān)系設(shè)置一個(gè)同步信號(hào)量S12，其初值為0。{…C1

Signal（S12）

…}P1：{…

Wait（S12）

C2…}P2：C1C2s12S1S3S2S4S5S6S7S8例4：利用信號(hào)量來描述前趨圖關(guān)系

該前趨圖具有8個(gè)結(jié)點(diǎn)，共有有向邊10條，可設(shè)10個(gè)信號(hào)量，初值均為0；有8個(gè)結(jié)點(diǎn)，可設(shè)計(jì)成8個(gè)并發(fā)進(jìn)程，具體描述如下：S1S3S2S4S5S6S7S8agefbcdhijsmaphorea，b，c，d，e，f，g，h，I，j=0,0,0,0,0,0,0,0,0,0；parbegin {S1;signal（a）；signal（b）；signal（c）；}{wait（a）；S2；signal（d）；}{wait（b）；S3；signal（e）；signal（f）；}{wait（c）；S4；signal（g）；}{wait（d）；wait（e）；S5；signal（h）；}{wait（f）；wait（g）；S6；signal（i）；}{wait（h）；wait（i）；S7；signal（j）；}{wait（j）；S8；}parendS1S3S2S4S5S6S7S8agefbcdhij用信號(hào)量解題的關(guān)鍵步驟：

信號(hào)量的設(shè)置；

給信號(hào)量賦初值（常用的互斥和同步信號(hào)量值的大小）；

wait、signal操作安排適當(dāng)?shù)奈恢米⒁猓?）互斥信號(hào)量：互斥時(shí)使用的信號(hào)量（二元信號(hào)量）：其初值為1或n，表示臨界資源的數(shù)目，用作互斥。它wait、signal操作在同一個(gè)進(jìn)程中。

2）同步信號(hào)量：它聯(lián)系著一組并行進(jìn)程，但其初值為０或?yàn)槟硞€(gè)正整數(shù)ｎ，主要用于進(jìn)程同步，wait、signal操作在兩個(gè)進(jìn)程中配對(duì)出現(xiàn)。信號(hào)量小結(jié)信號(hào)量必須置初值，且只能置一次初值。初值可為非負(fù)整數(shù)信號(hào)量分類：互斥的信號(hào)量：它的P、V在同一個(gè)進(jìn)程中同步的信號(hào)量：它的P、V在不同的進(jìn)程中信號(hào)量的物理意義：S>0：S表示可用資源的個(gè)數(shù)S=0：S表示無資源，無等待進(jìn)程

S<0：|S|表示等待隊(duì)列中進(jìn)程的個(gè)數(shù)第五節(jié)

經(jīng)典進(jìn)程同步問題生產(chǎn)者-消費(fèi)者問題生產(chǎn)者與消費(fèi)者互斥訪問公用數(shù)據(jù)緩沖區(qū)生產(chǎn)“數(shù)據(jù)”，消費(fèi)“數(shù)據(jù)”讀者-寫者問題數(shù)據(jù)文件或記錄被多個(gè)進(jìn)程共享并互斥訪問的問題允許多個(gè)Reader同時(shí)訪問，但不允許一個(gè)Writer和其它Reader或任何兩個(gè)以上的Writer同時(shí)訪問哲學(xué)家就餐問題多資源共享及互斥訪問五個(gè)哲學(xué)家的思考與互斥共享五根筷子就餐的問題生產(chǎn)者-消費(fèi)者問題倉庫放取生產(chǎn)者——消費(fèi)者問題分類：第一類：一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，單一資源第二類：一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，多個(gè)資源第三類：多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，多個(gè)資源情況一：單一資源的Producer-Consumer問題（同步問題）BufPC①分析進(jìn)程間的同步關(guān)系：②設(shè)置信號(hào)量：

設(shè)進(jìn)程P的同步信號(hào)量：buffer(empty)，初值為1，表示緩沖區(qū)個(gè)數(shù)（空緩沖區(qū)的個(gè)數(shù)）。設(shè)進(jìn)程C的同步信號(hào)量：product(full)

，初值為0，表示產(chǎn)品個(gè)數(shù)(滿緩沖區(qū)的個(gè)數(shù))。P：

while(true){

生產(chǎn)一產(chǎn)品；

P(buffer);

送產(chǎn)品到緩沖區(qū)；}；C：

while(true){P(product);

從緩沖區(qū)取一產(chǎn)品；消費(fèi)產(chǎn)品；}；V(product);V(buffer);初值buffer=1;product=0情況二：多個(gè)資源的P—C問題（有限資源）…...n1PCBuffer（n個(gè)緩沖區(qū)）1、設(shè)置信號(hào)量

①buffer————進(jìn)程P的私用信號(hào)量,初始值為n。（緩沖區(qū)的個(gè)數(shù)）

②product

————進(jìn)程C的私用信號(hào)量,初始值為0。2、算法描述

Main（）

{smaphorebuffer=n,product=0；

intin=0,out=0;parbegin

P;C;parend}P：

while(true){

生產(chǎn)一產(chǎn)品；

P(buffer);

往Buffer[i]放產(chǎn)品；

V(product);in=(in+1)%n;//環(huán)形緩沖區(qū)

}；C：

while(true){P(product);

從Buffer[j]取產(chǎn)品；

V(buffer);

消費(fèi)產(chǎn)品；

out=(out+1)%n;}；初值buffer=n；product=0情況三：n個(gè)緩沖區(qū)，m個(gè)生產(chǎn)者，k個(gè)消費(fèi)者123…….……nP1P2…Pm.C1C2…Ck要求：任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖池進(jìn)行操作。1)分析進(jìn)程的同步關(guān)系2)設(shè)置信號(hào)量

a.互斥信號(hào)量mutex，表示緩沖池是否可用，初值為1。

b.生產(chǎn)者的同步信號(hào)量buffer(empty)，表示緩沖區(qū)個(gè)數(shù)（空單元數(shù)），初值為n。

c.消費(fèi)者的同步信號(hào)量product(full)，表示產(chǎn)品個(gè)數(shù)（滿單元個(gè)數(shù)），初值為0。Producer：

while(true){

生產(chǎn)一產(chǎn)品；

wait(buffer);

往Buffer[in]放產(chǎn)品；

in=(in+1)%n;signal(product);}；Consumer：

while(true){wait（product）；

從Buffer[out]取產(chǎn)品；

out=(out+1)%n;signal（buffer）;

消費(fèi)一產(chǎn)品；}；wait（mutex）;signal（mutex）;wait(mutex);signal(mutex);初值buffer=n；product=0；mutex=1

該問題中的兩個(gè)wait操作的順序不能顛倒，否則容易導(dǎo)致死鎖。例如，消費(fèi)者進(jìn)程的兩個(gè)wait操作順序如下：

Consumer：

while(true){wait(mutex);wait（product）；從Buffer[out]取產(chǎn)品；

out=(out+1)%n;signal(mutex);signal（buffer）;

消費(fèi)一產(chǎn)品；}；Producer：

while(true){

生產(chǎn)一產(chǎn)品；

wait(buffer);wait(mutex);

往Buffer[in]放產(chǎn)品；

in=(in+1)%n;signal(mutex);signal(product);}；問題：其實(shí)生產(chǎn)者和消費(fèi)者間是不用互斥的，為了提高效率，為生產(chǎn)者和消費(fèi)者分別設(shè)置互斥信號(hào)量。解決方法：為所有生產(chǎn)者設(shè)置一互斥信號(hào)量：mutex1;為所有消費(fèi)者設(shè)置一互斥信號(hào)量：mutex2；初值均為1。代碼如下：Producer：

while(true){

生產(chǎn)一產(chǎn)品；

wait（buffer）;

往Buffer[in]放產(chǎn)品；

in=(in+1)%n;

signal(product);}；Consumer：

while(true){wait（product）;

從Buffer[out]取產(chǎn)品；

out=(out+1)%n;signal（buffer）;

消費(fèi)一產(chǎn)品；}；初值buffer=n；product=0；mutex1=1；mutex2=1wait（mutex1）;signal（mutex1）;wait（mutex2）;signal（mutex2）;小結(jié)P(S)表示申請(qǐng)（請(qǐng)求、使用）一個(gè)資源V(S)表示釋放（歸還）一個(gè)資源信號(hào)量的初值應(yīng)該>=0P、V必須成對(duì)出現(xiàn)，但不一定一一對(duì)應(yīng)。當(dāng)互斥操作時(shí)，處于同一進(jìn)程當(dāng)同步操作時(shí)，則在不同進(jìn)程如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要。一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)，同步P操作應(yīng)在互斥P操作前，而兩個(gè)V操作無關(guān)緊要。思考：有一個(gè)充分大的池子，兩個(gè)人分別向池中扔球。甲扔紅球，乙扔蘭球，一次扔一個(gè)。開始時(shí)池中有紅球、蘭球各一個(gè)，要求池中球滿足條件：1<=紅球數(shù)/蘭球數(shù)<=2試用P、V描述兩個(gè)過程。AND型信號(hào)量集AND型信號(hào)量集是指同時(shí)需要多種資源，且每種占用一個(gè)時(shí)的信號(hào)量操作?；舅枷耄涸谝粋€(gè)原語中申請(qǐng)整段代碼需要的多個(gè)臨界資源，要么全分配給它要么一個(gè)都不分配。AND型信號(hào)量集P原語：Swait(SimultaneousWait)AND型信號(hào)量集V原語：SsignalSwait(S1,S2,…,Sn)//P操作{while(true){if(S1>=1&&S2>=1&&…&&Sn>=1){for(i=1;i<=n;++i)--Si;break;}else{

調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列Sj.L;

阻塞調(diào)用進(jìn)程；

}}}

Ssignal(S1,S2,…,Sn)//V操作{for(i=1;i<=n;++i){++Si//釋放占用的資源；

for(在Si.L中等待的每個(gè)進(jìn)程P)//檢查每種資源的等待隊(duì)列的所有進(jìn)程

{從等待隊(duì)列Si.L中取出進(jìn)程P；

if(判斷進(jìn)程P是否通過Swait中的測試){進(jìn)程P進(jìn)入就緒隊(duì)列；}//通過檢查時(shí)的處理

else{進(jìn)程P進(jìn)入某等待隊(duì)列；}//未通過檢查時(shí)的處理

}}}哲學(xué)家就餐問題……………0101223344信號(hào)量定義：varchopstick[0,…,4]ofsemaphore;所有信號(hào)均量初始化為1第i位哲學(xué)家的活動(dòng)描述：

while(true){ P(chopstick[i]); P(chopstick[(i+1)%5]); …… eating; …… V(chopstick[i]); V(chopstick[(i+1)%5]); …… thinking; }Swait(chopstick[i],chopstick[(i+1)%5]);Ssignal(chopstick[i],chopstick[(i+1)%5]);1、至多只允許四位哲學(xué)家同時(shí)坐在桌旁；2、僅當(dāng)哲學(xué)家左右兩邊的筷子均可用時(shí)才允許他拿起筷子；3、規(guī)定奇數(shù)號(hào)哲學(xué)家先拿起他左邊的筷子，再拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家先拿起他右邊的筷子再拿左邊的筷子。死鎖的解決辦法如下：第1種解決解決方法：Semaphorechopstick[5]={1，1，1，1，1};Semaphoresm=4;while(true){wait（sm）；

wait（chopstick[i]）; wait（chopstick[(i+1)%5]）; …… eating; …… signal（chopstick[i]）; signal（chopstick[(i+1)%5]）;signal（sm）；

…… thinking;}第2種解決解決方法：用AND型信號(hào)量解決信號(hào)量定義：semaphorechopstick[5];所有信號(hào)均量初始化為1第i位哲學(xué)家的活動(dòng)描述：

while(true){ wait(chopstick[i]); wait(chopstick[(i+1)%5]); …… eating; …… signal(chopstick[i]); signal(chopstick[(i+1)%5]); …… thinking; }Swait(chopstick[i],chopstick[(i+1)%5]);Ssignal(chopstick[i],chopstick[(i+1)%5]);while(true){ifi%2==0then{wait(chopstick[i]);wait(chopstick[(i+1)%5]);……eating;……signal(chopstick[i]);signal(chopstick[(i+1)%5]);……thinking;}else{wait(chopstick[(i+1)%5]);wait(chopstick[i]);……eating;……signal(chopstick[(i+1)%5]);signal(chopstick[i]);……thinking;}}

第3種解決解決方法：則第i位哲學(xué)家的活動(dòng)描述：Semaphorechopstick[5]={1，1，1，1，1};一般信號(hào)量集一般信號(hào)量集是指同時(shí)需要多種資源，每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理?；舅悸罚涸贏ND型信號(hào)量集的基礎(chǔ)上進(jìn)程擴(kuò)充，在一次原語操作中完成所有的資源申請(qǐng)。對(duì)應(yīng)的PV原語格式為：

Swait(S1,t1,d1;…;Sn,tn,dn)Ssignal(S1,d1;…;Sn,dn)進(jìn)程對(duì)信號(hào)量Si的

下限值（測試值）為ti（表示信號(hào)量的判斷條件，要求Si>=ti;即當(dāng)資源數(shù)量低于ti時(shí)，便不予分配）需求值（占用值）為di（表示資源的申請(qǐng)量，即Si=Si-di）Swait(S,d,d)Swait(S,1,1)Swait(S,1,0)

//只測試，不占用（可控開關(guān)）一般信號(hào)量集的幾種情況：讀者—寫者問題有兩組并發(fā)進(jìn)程：讀者、寫者，共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作（讀寫互斥）不允許多個(gè)寫者同時(shí)操作（只能一人寫）第一類：讀者優(yōu)先

如果讀者來：無讀者、寫者，新讀者可以讀有寫者在等待，但有其他讀者在讀，則新讀者也可以讀有寫者在寫，新讀者等待

如果寫者來：無讀者，新寫者可以寫有讀者，新寫者等待有其他寫者，新寫者等待例如：教室——共享文件上自習(xí)——讀者（多個(gè)人使用教室）練歌——寫者（1個(gè)人使用教室）策略：1、唱歌的人進(jìn)來后，把門關(guān)上，其他任何人等待2、自習(xí)的人進(jìn)來后，把前門關(guān)上，后門開。其他自習(xí)的人從后門進(jìn)，唱歌的人等待。關(guān)鍵：1、第一個(gè)讀者進(jìn)入后把前門關(guān)，后門開2、最戶一個(gè)讀者離開時(shí)，把后門關(guān)，從前門出讀者：

while(true){if(readcount==0)P(wmutex);readcount++;

讀；

readcount--;if(readcount==0)V(wmutex)

};P(rmutex);V(rmutex);P(rmutex);V(rmutex);寫者：

while(true){P(wmutex);

寫

V(wmutex);};初值

wmutex:=1rmutex:=1用一般信號(hào)量集表示：

(只允許至多RN個(gè)人同時(shí)讀)寫者：

Swait(mx,1,1;rcount,RN,0);//既無寫者也無讀者才可“寫”操作寫

Ssignal(mx,1);讀者：

Swait(rcount,1,1;mx,1,0);

讀；

Ssignal(rcount,1);

初值mx:=1rcount:=RN控制讀者人數(shù)管程機(jī)制

管程的基本概念管程應(yīng)用分析1、管程的基本概念管程的提出：

采用P、V同步機(jī)制來編寫并發(fā)程序，對(duì)于共享變變量及信號(hào)量變量的操作將被分散于各個(gè)進(jìn)程中。缺點(diǎn)：易讀性差、不利于修改和維護(hù)、正確性難以保證管程的產(chǎn)生：Dijkstra（1971）：”秘書”進(jìn)程

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

typemonitor-name=monitorvariabledeclarationsprocedureentryp1(…);begin….end;…prcedureentryPn(…);begin…end;begininitializationcode;end管程的特點(diǎn)：1、封裝性—管程內(nèi)的共享變量在管程外不可見。2、管程必須互斥進(jìn)入3、管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)列以及相應(yīng)的等待和喚醒操作。問題：多個(gè)進(jìn)程出現(xiàn)在管程中

當(dāng)一個(gè)進(jìn)入管程的進(jìn)程Q執(zhí)行等待操作時(shí)，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)另一個(gè)進(jìn)入管程的進(jìn)程P執(zhí)行喚醒操作時(shí)，(如P喚醒Q)，管程中便存在兩個(gè)同時(shí)處于活動(dòng)狀態(tài)的進(jìn)程。(這是管程所不允許的)處理方法有三種：（前提：P喚醒Q）1、P等待、Q繼續(xù)，直到Q退出或等待 2、Q等待、P繼續(xù)，直到P退出或等待3、規(guī)定喚醒操作為管程中最后一個(gè)可執(zhí)行的操作入口等待隊(duì)列：等待進(jìn)入管程緊急等待隊(duì)列：在管程內(nèi)部由于執(zhí)行喚醒操作，可能會(huì)出現(xiàn)多個(gè)等待進(jìn)程注：緊急等待隊(duì)列優(yōu)先級(jí)高于入口等待隊(duì)列。條件變量condition：

當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí)要使其等待，為此在管程內(nèi)部可以說明和使用一種特殊類型的變量，稱為條件變量：

Varcconditon；

對(duì)于條件變量可以執(zhí)行wait和signal操作。c.wait：如果緊急等待隊(duì)列非空，則喚醒第一個(gè)等待者；否則，釋放管程的互斥權(quán)，執(zhí)行此操作的進(jìn)程的PCB入C鏈尾部。c.signal：如果C鏈為空，則相當(dāng)于空操作，執(zhí)行此操作的進(jìn)程繼續(xù)；否則，喚醒第一個(gè)等待者，執(zhí)行此操作的進(jìn)程的PCB入緊急等待隊(duì)列的尾部。2、管程應(yīng)用分析生產(chǎn)者-消費(fèi)者問題put(item)，產(chǎn)品放入緩沖區(qū)中g(shù)et(item)，從緩沖區(qū)中取出一產(chǎn)品producer－consumer，簡稱p_ctypep_c=monitorVarin,out,count:integer;buffer:array[0,…n-1]ofitem;

notfull,notempty:condition;

procedureentryput(Varpro:item)begin

ifcount>=nthennotfull.wait;buffer[in]:=pro;in:=(in+1)modn;count:=count+1;ifnotempty.queue**notempty.signal;end

procedureentryget(Varpro:item)begin

ifcount<=0thennotempty.wait;pro:=buffer[out];out:=(out+1)modn;count:=count-1;

ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;endProducer:beginrepeatproduceaniteminnextp;

p_c.put(nextp);untilfalse;endConsumer:beginrepeat

p_c.get(nextc);consumetheiteminnextc;untilfalse;end第六節(jié)

進(jìn)程通信進(jìn)程通信的概念進(jìn)程通信的類型消息傳遞通信的實(shí)現(xiàn)方法消息傳遞系統(tǒng)實(shí)現(xiàn)中的若干問題消息緩沖隊(duì)列通信機(jī)制1、進(jìn)程通信的概念進(jìn)程通信，是指進(jìn)程之間的信息交換。低級(jí)通信（互斥、同步）利用信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程間的數(shù)據(jù)傳遞。缺點(diǎn)：效率低；對(duì)用戶不透明。高級(jí)通信（進(jìn)程通信）進(jìn)程之間利用OS提供的一組通信命令，高效地傳送大量數(shù)據(jù)的信息交換方式。優(yōu)點(diǎn)：高效，方便，簡化了通信程序的設(shè)計(jì)。2、進(jìn)程通信的類型高級(jí)通信機(jī)制可分為：共享存儲(chǔ)器系統(tǒng)、消息傳遞系統(tǒng)、管道通信系統(tǒng)三種。共享存儲(chǔ)器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享存儲(chǔ)區(qū)的通信方式消息傳遞系統(tǒng)進(jìn)程之間的數(shù)據(jù)交換，是以格式化的消息為單位消息（Message報(bào)文）及相關(guān)的一組命令直接通信方式和間接通信方式管道通信系統(tǒng)（首創(chuàng)于UNIX系統(tǒng)）管道（Pipe文件）：用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件。管道通信：發(fā)送進(jìn)程和接收進(jìn)程利用管道進(jìn)程通信。雙方進(jìn)程的協(xié)調(diào)：互斥、同步、確定對(duì)方存在。3、消息傳遞通信的實(shí)現(xiàn)方法直接通信方式發(fā)送進(jìn)程利用OS提供的發(fā)送命令原語，直接把消息發(fā)送給目標(biāo)進(jìn)程。Send(Receiver,message)、Receive(Sender,message)利用直接通信原語，解決生產(chǎn)者－消費(fèi)者問題：生產(chǎn)者消費(fèi)者

repeat……produceaniteminnextp;……send(consumer,nextp);untilfalse;

repeat……receive(producer,nextc);……consumeraniteminnextc;untilfalse;間接通信方式進(jìn)程之間通過一個(gè)作為共享數(shù)據(jù)結(jié)構(gòu)的中間實(shí)體—信箱，以消息暫存方式實(shí)現(xiàn)的通信。操作原語：信箱的創(chuàng)建、撤消；消息的發(fā)送接收Send(mailbox,message)Receive(mailbox,message)信箱的創(chuàng)建和擁有者：OS或用戶（通信）進(jìn)程。信箱的種類：私用信箱、公用信箱、共享信箱利用信箱通信時(shí)，發(fā)送和接收進(jìn)程之間的關(guān)系：一對(duì)一、多對(duì)一、一對(duì)多、多對(duì)多4、消息傳遞系統(tǒng)實(shí)現(xiàn)中的問題通信鏈路網(wǎng)絡(luò)中：顯式調(diào)用“建立/拆除連結(jié)原語”單機(jī)中：系統(tǒng)自動(dòng)建立/拆除連結(jié)，只需調(diào)用發(fā)送原語消息格式消息頭（單機(jī)簡單）+消息正文定長、變長消息格式。通常系統(tǒng)同時(shí)支持兩種格式。進(jìn)程同步發(fā)送進(jìn)程阻塞、接收進(jìn)程阻塞發(fā)送進(jìn)程不阻塞、接收進(jìn)程阻塞發(fā)送進(jìn)程和接收進(jìn)程均不阻塞選講5、消息緩沖隊(duì)列通信機(jī)制Hansen教授首先提出的消息緩沖隊(duì)列通信機(jī)制是通過內(nèi)存中公用的消息緩沖區(qū)進(jìn)行進(jìn)程通信，屬直接通信方式。發(fā)送原語send(receiver,a)a：發(fā)送區(qū)的地址接收原語receive(b)b：接收區(qū)的地址數(shù)據(jù)結(jié)構(gòu)消息緩沖區(qū)PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)通信過程：構(gòu)成消息：發(fā)送進(jìn)程在工作區(qū)設(shè)置發(fā)送區(qū)a，將消息正文和有關(guān)控制信息填入其中。發(fā)送消息：將消息從發(fā)送區(qū)a復(fù)制到消息緩沖區(qū)，并把它插入到目標(biāo)進(jìn)程的消息隊(duì)列中。接收消息：由目標(biāo)進(jìn)程從自己的消息隊(duì)列中找到第一個(gè)消息緩沖區(qū)，并將其中的消息復(fù)制到自己的接收區(qū)b中。（1）消息緩沖區(qū)：typemessagebuffer=recordsender；發(fā)送區(qū)進(jìn)程標(biāo)識(shí)符

size；消息長度

text；消息正文

next；指向下一個(gè)消息緩沖區(qū)的指針

end（2）PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)：typeprocesscontrolblock=record…mq；消息隊(duì)列首指針

mutex；消息隊(duì)列互斥信號(hào)量

sm；消息隊(duì)列資源信號(hào)量end發(fā)送原語：proceduresend(receiver,a)begingetbuf(a,size,i)//根據(jù)a.size申請(qǐng)緩沖區(qū)

i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCBset,receiver,j);//獲得接收進(jìn)程內(nèi)部標(biāo)識(shí)符

wait(j.mutex);insert(j.mq,i);//將消息緩沖區(qū)插入消息隊(duì)列

signal(j.mutex);signal(j.sm);end//將發(fā)送區(qū)a的信息復(fù)制到消息緩沖區(qū)中接收原語：procedurereceive(b)beginj:=internalname;//j為接收進(jìn)程的內(nèi)部標(biāo)識(shí)符

wait(j.sm);wait(j.mutex);remove(j.mq,i);//將消息隊(duì)列中第一個(gè)消息移出

signal(j.mutex);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;

releasei;//將消息緩沖區(qū)i歸還系統(tǒng)end//將消息緩沖區(qū)i的信息復(fù)制到接收區(qū)b

進(jìn)程A PCB(B) 進(jìn)程B

Send(B,a)Sender:ASize:6Text:Hello!Receive(b)Sender:ASize:6Text:Hello!Sender:ASize:6Text:Hello!Next:0……首指針：mq互斥：mutex隊(duì)列資源：sm……a發(fā)送區(qū)ab接收區(qū)b消息緩沖通信第七節(jié)

線程的基本概念線程的引入線程和進(jìn)程的比較線程的屬性線程的狀態(tài)多線程OS中的進(jìn)程1、線程的引入進(jìn)程（60年代）目的：使多個(gè)程序并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量定義：在OS中能擁有資源和獨(dú)立運(yùn)行的基本單位進(jìn)程的創(chuàng)建、撤消與切換存在較大的時(shí)空開銷，限制了并發(fā)程度的提高。線程（80年代）目的：減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷。思想：“輕裝上陣”——將進(jìn)程的兩個(gè)屬性分離。定義：線程是系統(tǒng)獨(dú)立調(diào)度和分派（即可獨(dú)立運(yùn)行）的基本單位。進(jìn)程——擁有資源的單位調(diào)度線程是調(diào)度和分派的基本單位，進(jìn)程是擁有資源的基本單位并發(fā)性同族、非同族線程均可并發(fā)。擁有資源線程幾乎不占資源系統(tǒng)開銷線程的切換、同步、通信無須內(nèi)核干預(yù)。開銷小2、線程和進(jìn)程的特點(diǎn)輕型實(shí)體：線程幾乎不占資源（TCB、程序計(jì)數(shù)器、寄存器、堆棧）獨(dú)立運(yùn)行的基本單位：切換迅速且開銷小可并發(fā)執(zhí)行：同族、非同族的線程皆可并發(fā)共享進(jìn)程的資源：同族的線程共享進(jìn)程的資源可以創(chuàng)建、撤銷另一個(gè)線程3、線程的屬性

每個(gè)線程都利用TCB和一組狀態(tài)參數(shù)進(jìn)行描述(1)狀態(tài)參數(shù)：寄存器狀態(tài)、堆棧、運(yùn)行狀態(tài)、優(yōu)先級(jí)、專用存儲(chǔ)器、信號(hào)屏蔽(2)運(yùn)行狀態(tài)：就緒態(tài)、執(zhí)行態(tài)、阻塞態(tài)4、線程的狀態(tài)進(jìn)程作為系統(tǒng)資源分配的單位進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體進(jìn)程可包括一個(gè)或多個(gè)線程單進(jìn)程單線程（各種UNIX版本）單進(jìn)程多線程（WindowsNT/Solaris/OS/2）5、多線程OS中的進(jìn)程地址空間和其他資源（如打開文件）：同一進(jìn)程的各線程間共享資源－－進(jìn)程間相互獨(dú)立通信進(jìn)程間通信IPC－－線程間可以直接讀寫進(jìn)程數(shù)據(jù)段（如全局變量）來進(jìn)行通信，需要線程間同步和通信手段的輔助，以保證數(shù)據(jù)的一致性調(diào)度

不論是系統(tǒng)進(jìn)程還是用戶進(jìn)程，進(jìn)程的創(chuàng)建