第4章進(jìn)程及管理

第4章進(jìn)程及進(jìn)程管理進(jìn)程及進(jìn)程管理進(jìn)程的引入進(jìn)程概念進(jìn)程控制進(jìn)程之間的制約關(guān)系進(jìn)程互斥與同步的實(shí)現(xiàn)進(jìn)程間通信線程的概念和特點(diǎn)進(jìn)程及進(jìn)程管理——主要內(nèi)容進(jìn)程引入進(jìn)程及進(jìn)程管理——進(jìn)程的引入程序進(jìn)程及進(jìn)程管理——進(jìn)程的引入用來(lái)表示人們思維對(duì)象的抽象概念的物理表現(xiàn)叫做數(shù)據(jù)。數(shù)據(jù)處理的規(guī)則叫做操作（指令）。對(duì)某一有限數(shù)據(jù)的集合所施行的、目的在于解決某一問(wèn)題的一組有限的操作的集合，稱為一個(gè)計(jì)算。計(jì)算機(jī)就是用指令來(lái)處理數(shù)據(jù)。程序是數(shù)據(jù)和指令的集合（數(shù)據(jù)結(jié)構(gòu)+算法）。一個(gè)程序的執(zhí)行過(guò)程就是一次計(jì)算。程序的順序執(zhí)行和并發(fā)執(zhí)行

進(jìn)程及進(jìn)程管理——進(jìn)程的引入程序的執(zhí)行有兩種方式：順序執(zhí)行和并發(fā)執(zhí)行。順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式；現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是提高資源利用率。順序程序的特點(diǎn)進(jìn)程及進(jìn)程管理——進(jìn)程的引入1.什么是程序的順序執(zhí)行一個(gè)程序由若干個(gè)子程序段組成，每個(gè)程序段由若干條操作指令組成。子程序段的執(zhí)行必須嚴(yán)格按照先后次序順序執(zhí)行。子程序段中的指令也必須是順序執(zhí)行的。系統(tǒng)中存在的若干個(gè)程序也是一個(gè)一個(gè)按順序運(yùn)行，同時(shí)只能運(yùn)行一個(gè)程序，一個(gè)程序運(yùn)行完畢后才能運(yùn)行下一個(gè)程序。

順序程序的特點(diǎn)①單道系統(tǒng)的工作情況對(duì)用戶作業(yè)的處理——

首先輸入用戶的程序和數(shù)據(jù)；然后進(jìn)行計(jì)算；最后打印計(jì)算結(jié)果，即有三個(gè)順序執(zhí)行的操作。

I：輸入操作

C：計(jì)算操作

P：輸出操作單用戶系統(tǒng)中操作的先后次序圖進(jìn)程及進(jìn)程管理——進(jìn)程的引入P2C2I2P1C1I1P3C3

I3②

順序程序的特點(diǎn)順序性

——處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。封閉性

——程序一旦開(kāi)始執(zhí)行，其計(jì)算結(jié)果不受外界因素的影響?？稍佻F(xiàn)性

——程序執(zhí)行的結(jié)果與它的執(zhí)行速度無(wú)關(guān)(即與時(shí)間無(wú)關(guān))，而只與初始條件有關(guān)。

時(shí)間無(wú)關(guān)性-->可再現(xiàn)性

時(shí)間無(wú)關(guān)性的先決條件是：程序的封閉性缺點(diǎn)是計(jì)算機(jī)系統(tǒng)效率不高。

進(jìn)程及進(jìn)程管理——進(jìn)程的引入進(jìn)程及進(jìn)程管理——進(jìn)程的引入78輸入處理器打印130150228280300378430450時(shí)間處理器利用率：52/(78+52+20)≈35%2.并發(fā)執(zhí)行

(1)多道系統(tǒng)的工作情況

I1

I2

I3

I4C1C3C2P1P2

哪些程序段的執(zhí)行必須是順序的？為什么？哪些程序段的執(zhí)行可以是并行的？為什么？多道系統(tǒng)中操作的先后次序圖對(duì)n個(gè)用戶作業(yè)的處理——

作業(yè)1：I1C1P1

作業(yè)2：I2C2P2......

......

作業(yè)n：InCnPn進(jìn)程及進(jìn)程管理——進(jìn)程的引入進(jìn)程及進(jìn)程管理——進(jìn)程的引入78輸入處理器打印130150156234312384時(shí)間處理器利用率：52/78≈67%(2)為什么程序可以并發(fā)執(zhí)行由程序運(yùn)行時(shí)需要占用的資源決定的：一個(gè)資源本來(lái)就可以同時(shí)被多個(gè)程序使用；一個(gè)資源同時(shí)只能被一個(gè)程序使用，但是可以分時(shí)使用；一個(gè)程序在不同的時(shí)刻可能占用不同的資源，它釋放的資源可以讓其他程序使用；存在多個(gè)同類資源；并發(fā)執(zhí)行的優(yōu)點(diǎn)：發(fā)揮了硬件的并行能力，以提高資源利用率進(jìn)程及進(jìn)程管理——進(jìn)程的引入(3)什么是程序的并發(fā)執(zhí)行①

定義

若干個(gè)程序段同時(shí)在系統(tǒng)中運(yùn)行，這些程序段的執(zhí)行在時(shí)間上是重疊的，一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開(kāi)始，即使這種重疊是很小的一部分，也稱這幾個(gè)程序段是并發(fā)執(zhí)行的。②三個(gè)并發(fā)執(zhí)行的程序段PQR三個(gè)并發(fā)進(jìn)程進(jìn)程及進(jìn)程管理——進(jìn)程的引入(4)并發(fā)程序的描述進(jìn)程及進(jìn)程管理——進(jìn)程的引入把一個(gè)程序設(shè)計(jì)成若干個(gè)可同時(shí)執(zhí)行的程序模塊，用下面語(yǔ)句表示并發(fā)執(zhí)行這些程序段：

cobegin S1；S2；…；Sn coend

表示程序段（函數(shù)）S1，S2，…，Sn可以并發(fā)執(zhí)行。并發(fā)執(zhí)行意味著各個(gè)程序段以不可預(yù)知的次序運(yùn)行。甚至也可能是串行。并發(fā)程序的描述示例進(jìn)程及進(jìn)程管理——進(jìn)程的引入一個(gè)程序設(shè)計(jì)成若干個(gè)程序模塊Si，用下面語(yǔ)句表示執(zhí)行這些程序段：{

S0

cobegin S1；S2；…；Sn coend Sn+1}s0sns2s1sn+1…并發(fā)程序的例子(1)謄抄——用卡片輸入機(jī)將一個(gè)文本復(fù)寫(xiě)到行式打印機(jī)。

(1)循環(huán)順序執(zhí)行

while(不空){INPUT;//卡片輸入機(jī)讀OUTPUT;//打印機(jī)打印}

缺點(diǎn)：未能利用卡片輸入機(jī)與行式打印機(jī)的并行操作能力，造成系統(tǒng)效率低。進(jìn)程及進(jìn)程管理——進(jìn)程的引入并發(fā)程序的例子(2)基于一個(gè)緩沖區(qū)的并發(fā)謄抄方案卡片輸入機(jī)-->緩沖區(qū)-->行式打印機(jī)

輸入程序I： 輸出程序O：

while(不空){ while(未結(jié)束){INPUT; RECEIVE;SEND; OUTPUT; } }

問(wèn)題：提高了謄抄效率，但是可能出現(xiàn)結(jié)果不正確（可能出現(xiàn)什么錯(cuò)誤？請(qǐng)考慮）。進(jìn)程及進(jìn)程管理——進(jìn)程的引入并發(fā)程序的例子(3)基于兩個(gè)緩沖區(qū)的并發(fā)謄抄方案，卡片輸入機(jī)-->緩沖區(qū)s-->緩沖區(qū)t->行式打印機(jī)進(jìn)程及進(jìn)程管理——進(jìn)程的引入卡片輸入-->緩沖區(qū)swhile(謄寫(xiě)未完成){

緩沖區(qū)s-->緩沖區(qū)t cobegin

緩沖區(qū)t-->行式打印機(jī) 卡片輸入-->緩沖區(qū)s coend}并發(fā)程序的特點(diǎn)①失去程序的封閉性若一個(gè)程序(段)的執(zhí)行可以改變另一個(gè)程序(段)的變量，那么后者的輸出就可能有賴于各程序(段)執(zhí)行的相對(duì)速度，即失去了程序的封閉性特點(diǎn)。

例子：

討論共享公共變量的兩個(gè)程序，執(zhí)行時(shí)可能產(chǎn)生的不同結(jié)果。程序A執(zhí)行時(shí)對(duì)n做加

1的操作；程序B打印出n值，并將它減1重新置為零。程序A...n:=n+1;......程序B...

print(n);

n:=n-1;

...共享變量的兩個(gè)程序進(jìn)程及進(jìn)程管理——進(jìn)程的引入與時(shí)間有關(guān)的錯(cuò)誤程序A的n:=n+1與程序B的兩個(gè)語(yǔ)句的關(guān)系n的初值打印的結(jié)果n的最終值

之前

10

11

0

之后

10

10

1

之間

10

10

0

程序A...n:=n+1;......程序B...

print(n);

n:=0;

...共享變量的兩個(gè)程序進(jìn)程及進(jìn)程管理——進(jìn)程的引入intX;//剩余的票數(shù)訂票的函數(shù)（）{ if(X>=1){ X=X-1; 輸出一張票 }else{ 輸出票已售完 }}機(jī)票問(wèn)題并發(fā)程序的特點(diǎn)失去封閉性，導(dǎo)致失去可再現(xiàn)性1即使輸入相同的初始條件，也可能得到不同的結(jié)果。2結(jié)果不可再現(xiàn)，不可預(yù)測(cè)。3程序的執(zhí)行結(jié)果與程序間的相對(duì)速度有關(guān)。

即：程序并發(fā)執(zhí)行時(shí)會(huì)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤。與時(shí)間有關(guān)的錯(cuò)誤進(jìn)程及進(jìn)程管理——進(jìn)程的引入

程序并發(fā)執(zhí)行時(shí)若共享了變量，其執(zhí)行結(jié)果將與并發(fā)程序執(zhí)行的相對(duì)速度有關(guān)，即使給定相同的初始條件，也可能會(huì)得到不同的結(jié)果，此為與時(shí)間有關(guān)的錯(cuò)誤。并發(fā)執(zhí)行不能保證程序的正確性，還有實(shí)用價(jià)值嗎？ 1并發(fā)程序之間如果沒(méi)有共享變量，那么他們之間還是封閉的，不會(huì)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤。 2如果有共享變量，必須慎重對(duì)待！??！ 怎樣才能保證程序的正確性呢？對(duì)共享變量的互斥訪問(wèn)②程序與計(jì)算不再一一對(duì)應(yīng)程序是靜態(tài)的概念，是指令的有序集合。計(jì)算是指令序列在處理機(jī)上的執(zhí)行過(guò)程，是動(dòng)態(tài)的概念。程序順序執(zhí)行時(shí)，程序和計(jì)算有一一對(duì)應(yīng)關(guān)系。并發(fā)執(zhí)行時(shí)，程序的一次運(yùn)行就可能是一次不同的計(jì)算。③程序并發(fā)執(zhí)行的相互制約（為了保證結(jié)果正確）并發(fā)進(jìn)程之間存在同步和互斥的約束。同步對(duì)應(yīng)協(xié)作；互斥對(duì)應(yīng)資源共享或公共變量；進(jìn)程及進(jìn)程管理——進(jìn)程的引入進(jìn)程概念進(jìn)程及進(jìn)程管理——進(jìn)程概念

進(jìn)程引入

a提高資源利用率-->程序并發(fā)執(zhí)行 b程序段的并發(fā)執(zhí)行可以有任意的組合情況，為了保證并發(fā)程序的正確性，避免時(shí)間有關(guān)的錯(cuò)誤，并發(fā)程序之間有同步和互斥的約束，這些運(yùn)行時(shí)的約束是通過(guò)阻塞/喚醒程序運(yùn)行來(lái)實(shí)現(xiàn)，這樣程序就不停的處于運(yùn)行/暫停/運(yùn)行....的狀態(tài)。

c 一個(gè)程序可以同時(shí)多次運(yùn)行，每次運(yùn)行的情況可能都不一樣

基于以上原因，程序的概念已經(jīng)不夠了。為了動(dòng)態(tài)反應(yīng)程序的活動(dòng)和狀態(tài)的變化，

運(yùn)行----->暫停------>運(yùn)行

引入了新的概念：進(jìn)程進(jìn)程及進(jìn)程管理——進(jìn)程概念

1.進(jìn)程定義

1進(jìn)程是這樣的計(jì)算部分，它是可以和其他計(jì)算并行的一個(gè)計(jì)算。 2進(jìn)程是一個(gè)程序與其數(shù)據(jù)一道通過(guò)處理機(jī)的執(zhí)行所發(fā)生的行為 3進(jìn)程是由一個(gè)程序以及與它相關(guān)的狀態(tài)信息（包括寄存器內(nèi)容，存儲(chǔ)區(qū)域和鏈接表）所組成。 4所謂進(jìn)程，就是一個(gè)程序在給定活動(dòng)空間和初始環(huán)境下，在一個(gè)處理機(jī)上的執(zhí)行過(guò)程。 5進(jìn)程是指一個(gè)具有一定獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。進(jìn)程及進(jìn)程管理——進(jìn)程概念進(jìn)程是支持并發(fā)作業(yè)的操作系統(tǒng)中最基本、最重要的概念?，F(xiàn)代操作系統(tǒng)的設(shè)計(jì)都是建立在進(jìn)程的基礎(chǔ)上。

1.進(jìn)程定義

進(jìn)程及進(jìn)程管理——進(jìn)程概念

(2)進(jìn)程與程序的區(qū)別①程序是指令的有序集合，是靜態(tài)的概念，進(jìn)程是程序的一次執(zhí)行過(guò)程，是動(dòng)態(tài)的概念；②進(jìn)程是一個(gè)獨(dú)立運(yùn)行的活動(dòng)單位；③進(jìn)程是競(jìng)爭(zhēng)系統(tǒng)資源的基本單位；④一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程；

一個(gè)進(jìn)程一定包含一個(gè)程序；2.進(jìn)程的狀態(tài)②等待狀態(tài)(wait)

進(jìn)程正等待著某一事件的發(fā)生而暫時(shí)停止執(zhí)行。這時(shí)，即使給它CPU控制權(quán)，它也無(wú)法執(zhí)行。③就緒狀態(tài)(ready)

進(jìn)程已獲得除CPU之外的運(yùn)行所必需的資源，一旦得到CPU控制權(quán)，立即可以運(yùn)行。(1)進(jìn)程的基本狀態(tài)（至少應(yīng)該具備的狀態(tài)）①運(yùn)行狀態(tài)(running)

該進(jìn)程已獲得運(yùn)行所必需的資源，它的程序正在處理機(jī)上執(zhí)行。進(jìn)程及進(jìn)程管理——進(jìn)程概念(2)進(jìn)程狀態(tài)的變遷①基本狀態(tài)的最少變遷圖運(yùn)行服務(wù)請(qǐng)求(請(qǐng)求I/O等)服務(wù)完成/事件來(lái)到進(jìn)程調(diào)度等待就緒進(jìn)程狀態(tài)變遷圖進(jìn)程及進(jìn)程管理——進(jìn)程概念(2)進(jìn)程狀態(tài)的變遷②分時(shí)系統(tǒng)的進(jìn)程變遷運(yùn)行1234等待就緒進(jìn)程狀態(tài)變遷圖進(jìn)程及進(jìn)程管理——進(jìn)程概念(2)進(jìn)程狀態(tài)的變遷③進(jìn)程狀態(tài)可能的變遷運(yùn)行服務(wù)請(qǐng)求(請(qǐng)求I/O等)服務(wù)完成/事件來(lái)到進(jìn)程調(diào)度時(shí)間片到等待就緒×進(jìn)程狀態(tài)變遷圖進(jìn)程及進(jìn)程管理——進(jìn)程概念×3.進(jìn)程描述

(1)進(jìn)程的組成代碼與數(shù)據(jù)進(jìn)程控制塊代碼段：描述進(jìn)程本身所應(yīng)完成的功能；數(shù)據(jù)段：進(jìn)程使用的數(shù)據(jù)堆：用于動(dòng)態(tài)分配的數(shù)據(jù)棧：用于函數(shù)調(diào)用和參數(shù)傳遞PCB：進(jìn)程控制塊（ProcessControlBock）進(jìn)程組成的示意圖進(jìn)程及進(jìn)程管理——進(jìn)程概念 (2)什么是進(jìn)程控制塊

描述進(jìn)程的動(dòng)態(tài)特征，進(jìn)程與其他進(jìn)程和系統(tǒng)資源的關(guān)系的數(shù)據(jù)結(jié)構(gòu)。是操作系統(tǒng)標(biāo)識(shí)一個(gè)進(jìn)程以及進(jìn)程存在的唯一標(biāo)識(shí)。(一一對(duì)應(yīng))(3)進(jìn)程控制塊的主要內(nèi)容

①

進(jìn)程標(biāo)識(shí)符

進(jìn)程名或內(nèi)部id號(hào)②

進(jìn)程當(dāng)前狀態(tài)本進(jìn)程目前處于何種狀態(tài)大量的進(jìn)程如何組織？wait_lpt_q_startPCB3PCB7next打印機(jī)等待隊(duì)列結(jié)構(gòu)runningPCB4next運(yùn)行指針ready_q_startPCB1PCB2PCB9就緒隊(duì)列結(jié)構(gòu)next進(jìn)程隊(duì)列結(jié)構(gòu)示例進(jìn)程及進(jìn)程管理——進(jìn)程概念③

當(dāng)前隊(duì)列指針next

該項(xiàng)登記了處于同一狀態(tài)的下一個(gè)進(jìn)程的PCB地址。④

進(jìn)程優(yōu)先級(jí)反映了進(jìn)程要求CPU的緊迫程度。⑤

CPU現(xiàn)場(chǎng)保護(hù)區(qū)當(dāng)進(jìn)程由于某種原因釋放處理機(jī)時(shí)，CPU現(xiàn)場(chǎng)信息被保存在PCB的該區(qū)域中。⑥通信信息進(jìn)程間進(jìn)行通信時(shí)所記錄的有關(guān)信息。⑦家族聯(lián)系指明本進(jìn)程與家族的聯(lián)系⑧占有資源清單

進(jìn)程及進(jìn)程管理——進(jìn)程概念進(jìn)程控制進(jìn)程及進(jìn)程管理——進(jìn)程控制1.進(jìn)程控制的概念

(1)進(jìn)程控制的職責(zé)

對(duì)系統(tǒng)中的進(jìn)程實(shí)施有效的管理，實(shí)現(xiàn)進(jìn)程狀態(tài)的改變。

①

進(jìn)程狀態(tài)變化進(jìn)程及進(jìn)程管理——進(jìn)程控制創(chuàng)建撤銷無(wú)有消亡阻塞運(yùn)行等待喚醒就緒等待

②常用的進(jìn)程控制原語(yǔ)

創(chuàng)建原語(yǔ)、撤消原語(yǔ)、阻塞原語(yǔ)、喚醒原語(yǔ)(2)進(jìn)程創(chuàng)建

進(jìn)程及進(jìn)程管理——進(jìn)程控制進(jìn)程創(chuàng)建的方式和時(shí)機(jī)：批處理系統(tǒng)中，提交一個(gè)作業(yè)；分時(shí)系統(tǒng)中，在一個(gè)終端登錄，交互；啟動(dòng)時(shí)，操作系統(tǒng)創(chuàng)建服務(wù)進(jìn)程；用戶程序自己也可以創(chuàng)建新的進(jìn)程；生成進(jìn)程稱父進(jìn)程(ParentProcess)，被生成進(jìn)程稱子進(jìn)程(ChildProcess)、即一個(gè)父進(jìn)程可以創(chuàng)建子進(jìn)程，從而形成樹(shù)形結(jié)構(gòu)。(2)進(jìn)程創(chuàng)建①進(jìn)程創(chuàng)建原語(yǔ)的形式

create(name，priority)name為被創(chuàng)建進(jìn)程的標(biāo)識(shí)符priority為進(jìn)程優(yōu)先級(jí)②進(jìn)程創(chuàng)建原語(yǔ)的功能創(chuàng)建一個(gè)具有指定標(biāo)識(shí)符的進(jìn)程，建立進(jìn)程的PCB結(jié)構(gòu)。進(jìn)程及進(jìn)程管理——進(jìn)程控制PCB池③進(jìn)程創(chuàng)建原語(yǔ)的實(shí)現(xiàn)

ab-1...進(jìn)程創(chuàng)建原語(yǔ)的實(shí)現(xiàn)框圖入口查PCB總鏈有同名?向系統(tǒng)申請(qǐng)一個(gè)空的PCB

結(jié)構(gòu)有空PCB?將入口信息填入PCB相應(yīng)項(xiàng)將PCB入就緒隊(duì)列將PCB入總鏈隊(duì)列返回進(jìn)程pid出錯(cuò)YN出錯(cuò)PCB池示意圖進(jìn)程創(chuàng)建原語(yǔ)流程圖進(jìn)程及進(jìn)程管理——進(jìn)程控制linux下創(chuàng)建進(jìn)程的實(shí)現(xiàn)： pid_tfork(void)+exec(...)系列函數(shù)進(jìn)程及進(jìn)程管理——進(jìn)程控制(3)進(jìn)程撤銷進(jìn)程及進(jìn)程管理——進(jìn)程控制進(jìn)程撤銷的原因：進(jìn)程正常運(yùn)行結(jié)束進(jìn)程運(yùn)行中出錯(cuò)，如執(zhí)行了非法指令、在常態(tài)下執(zhí)行了特權(quán)指令、運(yùn)行時(shí)間超越了分給的最大時(shí)間段、申請(qǐng)的內(nèi)存超過(guò)了系統(tǒng)能提供最大量、越界錯(cuò)誤等操作員或操作系統(tǒng)干預(yù)父進(jìn)程撤銷其子進(jìn)程

父進(jìn)程撤銷操作系統(tǒng)終止(3)進(jìn)程撤銷①

進(jìn)程撤銷原語(yǔ)的形式

當(dāng)進(jìn)程完成任務(wù)后希望終止自己時(shí)使用進(jìn)程撤消原語(yǔ)。

Kill(或exit)②進(jìn)程撤銷原語(yǔ)的功能

撤消當(dāng)前運(yùn)行的進(jìn)程。將該進(jìn)程的PCB結(jié)構(gòu)歸還到PCB資源池，所占用的資源歸還給父進(jìn)程，從總鏈隊(duì)列中摘除它，然后轉(zhuǎn)進(jìn)程調(diào)度程序。進(jìn)程及進(jìn)程管理——進(jìn)程控制③進(jìn)程撤銷原語(yǔ)的實(shí)現(xiàn)

入口由運(yùn)行指針得當(dāng)前進(jìn)程的pid釋放本進(jìn)程所占用的資源該進(jìn)程從總鏈隊(duì)列中摘下釋放PCB結(jié)構(gòu)轉(zhuǎn)進(jìn)程調(diào)度進(jìn)程撤銷原語(yǔ)流程圖進(jìn)程及進(jìn)程管理——進(jìn)程控制linux下進(jìn)程撤銷的實(shí)現(xiàn)1.進(jìn)程自己正常結(jié)束退出: main()函數(shù)返回 exit()2.其他進(jìn)程撤銷情況都是通過(guò)信號(hào)(signal)實(shí)現(xiàn): kill進(jìn)程及進(jìn)程管理——進(jìn)程控制(4)進(jìn)程等待①進(jìn)程等待原語(yǔ)的形式

當(dāng)進(jìn)程需要等待某一事件完成時(shí)，它可以調(diào)用等待原語(yǔ)掛起自己。

susp(chan)

入口參數(shù)chan：進(jìn)程等待的原因②進(jìn)程等待原語(yǔ)的功能

中止調(diào)用進(jìn)程的執(zhí)行，并加入到等待chan的等待隊(duì)列中；最后使控制轉(zhuǎn)向進(jìn)程調(diào)度。進(jìn)程及進(jìn)程管理——進(jìn)程控制③進(jìn)程等待原語(yǔ)的實(shí)現(xiàn)

入口保護(hù)進(jìn)程的CPU現(xiàn)場(chǎng)到PCB結(jié)構(gòu)中置該進(jìn)程為”等待”狀態(tài)將該進(jìn)程PCB結(jié)構(gòu)插入到等待隊(duì)列中轉(zhuǎn)進(jìn)程調(diào)度進(jìn)程等待原語(yǔ)流程圖進(jìn)程及進(jìn)程管理——進(jìn)程控制(5)進(jìn)程喚醒①進(jìn)程喚醒原語(yǔ)的形式

當(dāng)處于等待狀態(tài)的進(jìn)程所期待的事件來(lái)到時(shí)，由發(fā)現(xiàn)者進(jìn)程使用喚醒原語(yǔ)叫喚醒它。

wakeup(chan)

入口參數(shù)chan：進(jìn)程等待的原因。②

進(jìn)程喚醒原語(yǔ)的功能當(dāng)進(jìn)程等待的事件發(fā)生時(shí)，喚醒等待該事件的進(jìn)程。進(jìn)程及進(jìn)程管理——進(jìn)程控制③進(jìn)程喚醒原語(yǔ)的實(shí)現(xiàn)

入口找到該等待隊(duì)列將隊(duì)列首進(jìn)程移出此等待隊(duì)列將該進(jìn)程置為”就緒”狀態(tài)，并將PCB結(jié)構(gòu)插入到就緒隊(duì)列中返回進(jìn)程喚醒原語(yǔ)流程圖進(jìn)程及進(jìn)程管理——進(jìn)程控制linux下進(jìn)程等待/喚醒的情形比較多，每一種情況等待和喚醒的系統(tǒng)調(diào)用都不一樣，有：鎖，等待進(jìn)程或線程退出，sleep，文件讀，select，poll，epoll進(jìn)程及進(jìn)程管理——進(jìn)程控制進(jìn)程之間的相互制約關(guān)系進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系進(jìn)程之間的相互制約關(guān)系進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系

并發(fā)執(zhí)行的多個(gè)進(jìn)程以各自的速度向前推進(jìn)，但是相互協(xié)作的多個(gè)進(jìn)程之間不是孤立的，存在相互制約的關(guān)系。

例子:

多個(gè)終端訂票；

醫(yī)院看病、化驗(yàn)；

輸入、打印；

接力賽跑；

視頻播放；

圖像處理...進(jìn)程之間的相互制約關(guān)系分為兩種情況：進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系1、由于競(jìng)爭(zhēng)系統(tǒng)資源引起的間接相互制約關(guān)系.

比如：處理器的共享(分時(shí))，內(nèi)存，其他硬件資源2、進(jìn)程之間存在共享數(shù)據(jù)而引起的直接相互制約關(guān)系.

比如：共享文件，共享變量；相互協(xié)作 協(xié)調(diào)進(jìn)程之間的直接相互制約關(guān)系就是要協(xié)調(diào)各進(jìn)程前進(jìn)的步伐，即實(shí)現(xiàn)進(jìn)程的同步，而要實(shí)現(xiàn)進(jìn)程的同步，必須支持進(jìn)程之間的信息交換，這就是進(jìn)程間的通信。進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系并發(fā)進(jìn)程之間的直接相互制約關(guān)系分為兩種：

進(jìn)程互斥、進(jìn)程同步 操作A必須在操作B之前執(zhí)行； 操作C必須在操作A和B都完成之后才能執(zhí)行； 操作D和操作E不能在同一時(shí)刻執(zhí)行；1.進(jìn)程互斥的概念

(1)臨界資源

①例1：兩個(gè)進(jìn)程共享一個(gè)變量x

設(shè)：x代表某航班機(jī)座號(hào)，p1和p2兩個(gè)售票進(jìn)程，售票工作是對(duì)變量x加1。這兩個(gè)進(jìn)程在一個(gè)處理機(jī)C上并發(fā)執(zhí)行，分別具有內(nèi)部寄存器r1和r2。

進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系兩個(gè)進(jìn)程共享一個(gè)變量x時(shí)，兩種可能的執(zhí)行次序p1：r1:=x;r1:=r1+1;x:=r1;p2：r2:=x;r2:=r2+1;x:=r2;設(shè)x的初值為10，兩種情況下的執(zhí)行結(jié)果：

情況A：

x=10+2情況B：x=10+1

特點(diǎn)：當(dāng)兩個(gè)進(jìn)程公用一個(gè)變量時(shí)，它們必須順序地使用，一個(gè)進(jìn)程對(duì)公用變量操作完畢后，另一個(gè)進(jìn)程才能去訪問(wèn)和修改這一變量。

p1：r1:=x;

r1:=r1+1;x:=r1;

p2：r2:=x;r2:=r2+1;x:=r2;進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系A(chǔ)：B：臨界區(qū)是進(jìn)程中對(duì)公共變量(或存儲(chǔ)區(qū))進(jìn)行訪問(wèn)與修改的程序段，稱為相對(duì)于該公共變量的臨界區(qū)。

臨界資源的定義一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源。

硬件：如輸入機(jī)、打印機(jī)、磁帶機(jī)等軟件：如公用變量、數(shù)據(jù)、表格、隊(duì)列等(2)臨界區(qū)

x

:=x+1;csa{進(jìn)程A進(jìn)程B

x

:=x+1;csb{進(jìn)程臨界區(qū)示意圖進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系臨界區(qū)的調(diào)度原則一次至多允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)內(nèi)一個(gè)進(jìn)程不能無(wú)限地停留在臨界區(qū)內(nèi)一個(gè)進(jìn)程不能無(wú)限地等待進(jìn)入臨界區(qū)無(wú)空等待、有空讓進(jìn)、擇一而入、算法可行。(3)互斥

在操作系統(tǒng)中，當(dāng)某一進(jìn)程正在訪問(wèn)某一存儲(chǔ)區(qū)域時(shí)，就不允許其他進(jìn)程來(lái)讀出或者修改存儲(chǔ)區(qū)的內(nèi)容，否則，就會(huì)發(fā)生后果無(wú)法估計(jì)的錯(cuò)誤。進(jìn)程間的這種相互制約關(guān)系（排它性控制）稱為互斥。

x

:=x+1;csa{進(jìn)程A進(jìn)程B

x

:=x+1;csb{進(jìn)程臨界區(qū)示意圖進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系注意：同一臨界資源的臨界區(qū)才需要互斥進(jìn)入。進(jìn)程A正在執(zhí)行csa段時(shí)，進(jìn)程B就不能進(jìn)入csb段執(zhí)行。2.進(jìn)程同步的概念

(1)什么是進(jìn)程同步并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要互相等待與互通消息，這種相互制約的等待與互通消息稱為進(jìn)程同步。(2)進(jìn)程同步的例子

①

病員就診

同步約束條件：？看病活動(dòng)：看病

要病人去化驗(yàn)；

等化驗(yàn)結(jié)果；

繼續(xù)診??；化驗(yàn)活動(dòng)：

有化驗(yàn)單?

進(jìn)行化驗(yàn)；

開(kāi)出化驗(yàn)結(jié)果；

進(jìn)程同步活動(dòng)示意圖進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系②

共享緩沖區(qū)的計(jì)算進(jìn)程與打印進(jìn)程的同步計(jì)算進(jìn)程cp和打印進(jìn)程iop公用一個(gè)單緩沖

緩沖區(qū)bufiop

cp兩個(gè)進(jìn)程共享一個(gè)緩沖區(qū)示意圖進(jìn)程及進(jìn)程管理——進(jìn)程之間的相互制約關(guān)系同步約束條件？1：cp進(jìn)程把數(shù)據(jù)送入buf后，iop進(jìn)程才能取出數(shù)據(jù)去打印。2：iop進(jìn)程把數(shù)據(jù)取出后，cp進(jìn)程才能把下一個(gè)數(shù)據(jù)送入buf。進(jìn)程同步機(jī)構(gòu)進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)

操作系統(tǒng)提供的，實(shí)現(xiàn)進(jìn)程之間協(xié)作關(guān)系（同步和互斥）的措施和方法，稱為同步機(jī)構(gòu):

1鎖2信號(hào)燈(信號(hào)量)1.鎖和上鎖、開(kāi)鎖操作(1)什么是鎖

用一個(gè)變量w代表某種資源的占用狀態(tài)，w稱為“鎖”。(2)上鎖操作和開(kāi)鎖操作

進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)檢測(cè)w的值(是0還是1)；如果w的值為1，繼續(xù)檢測(cè)；如果w的值為0，將鎖位置1(表示占用資源)，進(jìn)入臨界區(qū)執(zhí)行。

(此為上鎖操作)臨界資源使用完畢，將鎖位置0。(此為開(kāi)鎖操作)

(3)上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)①

上鎖原語(yǔ)算法lock輸入：鎖變量w輸出：無(wú){test：if(w==1)gototest;∕*測(cè)試鎖位的值*∕

elsew=1;∕*上鎖*∕}②

開(kāi)鎖原語(yǔ)算法unlock輸入：鎖變量w輸出：無(wú){w=0；∕*開(kāi)鎖*∕}進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)（spinlock自旋鎖）(4)用上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥

上鎖原語(yǔ)w

進(jìn)入臨界區(qū)csb

開(kāi)鎖原語(yǔ)w進(jìn)程B

上鎖原語(yǔ)w

進(jìn)入臨界區(qū)csa

開(kāi)鎖原語(yǔ)w進(jìn)程Aspinlock中的鎖變量w本身也是一個(gè)共享變量，怎么保證w自己的互斥訪問(wèn)？進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)①

上鎖原語(yǔ)算法lock輸入：鎖變量w輸出：無(wú){test：if(w==1)gototest;∕*測(cè)試鎖位的值*∕

elsew=1;∕*上鎖*∕}1:mov%0,[w];cmp%0,#1;beq1b;mov[w],#1;[w]:變量w的內(nèi)存地址%0：表示某個(gè)寄存器#1：表示立即數(shù)1硬件可以保證的原子操作：1、單個(gè)硬件指令是原子操作，中斷只會(huì)發(fā)生在指令邊界。2、內(nèi)存總線一次地址對(duì)齊的讀或?qū)懖僮鳎?到N個(gè)字節(jié)）是原子操作。spinlock中的鎖變量w本身也是一個(gè)共享變量，怎么保證w自己的互斥訪問(wèn)？進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)必須擴(kuò)充新的指令，能同時(shí)完成內(nèi)存的讀寫(xiě)操作1、交換指令（arm:swpx86:xchg）雖然一個(gè)指令完成讀寫(xiě)，但是內(nèi)存操作不是原子性，如果有多核cpu，還是會(huì)打斷。必須要lock鎖住總線的功能。多核心處理器實(shí)現(xiàn)：加鎖：

cli+禁止進(jìn)程調(diào)度；

1:mov%0,#1;

lockxchg%0,[lock];

cmp%0,#1;判斷是否已經(jīng)加鎖

beq1b;解鎖：

mov[w],#0；

sti+恢復(fù)進(jìn)程調(diào)度；單核心處理器實(shí)現(xiàn)：加鎖：

cli+禁止進(jìn)程調(diào)度；解鎖：

sti+恢復(fù)進(jìn)程調(diào)度；進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)交換指令違背了arm精簡(jiǎn)指令機(jī)的宗旨，并且lock總線導(dǎo)致自旋時(shí)整個(gè)系統(tǒng)總線效率很低，在armv6指令級(jí)之后引入了新的機(jī)制:獨(dú)占監(jiān)測(cè)（Exclusivemonitors）機(jī)制ldrex/strex:多核心處理器實(shí)現(xiàn)：加鎖1:ldrex%0,[lock];標(biāo)記cpu0獨(dú)占這個(gè)地址，并讀lock值到%0寄存器cmp%0,#1;假定是否已經(jīng)加鎖beq1b;等于1表示已經(jīng)加鎖，自旋mov%0,#1;strex%1,%0,[lock];檢查是否cpu0仍然獨(dú)占這個(gè)地址，如果是就存儲(chǔ)%0到lock(即lock為1),并賦值0-->%1寄存器，并清除獨(dú)占標(biāo)記;

如果不是就賦值1-->%1，不改變lock值;cmp%1,#0;bne1b;解鎖mov%0,#0；str%0,[lock];(3)上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)2進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)

上鎖原語(yǔ)lock

輸入：鎖變量w輸出：無(wú){while(w==1){保護(hù)當(dāng)前進(jìn)程的cpu現(xiàn)場(chǎng)；

設(shè)置當(dāng)前進(jìn)程的狀態(tài)為等待,并插入到w的等待隊(duì)列；轉(zhuǎn)進(jìn)程調(diào)度；

}w=1;}（mutex普通鎖）(3)上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)2進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)開(kāi)鎖原語(yǔ)

unlock輸入：鎖變量w輸出：無(wú){

if(w的等待隊(duì)列不為空)

{移出等待隊(duì)列首元素，插入到就緒隊(duì)列；置該進(jìn)程為就緒狀態(tài)；}

w=0;}(4)用上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥

上鎖原語(yǔ)w

進(jìn)入臨界區(qū)csb

開(kāi)鎖原語(yǔ)w進(jìn)程B

上鎖原語(yǔ)w

進(jìn)入臨界區(qū)csa

開(kāi)鎖原語(yǔ)w進(jìn)程A2、信號(hào)燈和P、V操作1965年，由荷蘭學(xué)者Dijkstra提出（所以P、V分別是荷蘭語(yǔ)的test(proberen)和increment(verhogen)），是一種卓有成效的進(jìn)程同步機(jī)制。

72/130

(1)什么是信號(hào)燈信號(hào)燈是一個(gè)確定的二元組(s，q)，s是一個(gè)具有非負(fù)初值的整型變量，q是一個(gè)初始狀態(tài)為空的隊(duì)列。操作系統(tǒng)利用信號(hào)燈的狀態(tài)對(duì)并發(fā)進(jìn)程和共享資源進(jìn)行控制和管理。

s是整型變量，代表可用資源實(shí)體的數(shù)量。

s>0時(shí)，表示有可用資源，進(jìn)程執(zhí)行(綠燈)；

s

<=

0時(shí)，表示沒(méi)有可用資源，進(jìn)程停止執(zhí)行(紅燈)；

注意：創(chuàng)建信號(hào)燈時(shí)，應(yīng)準(zhǔn)確說(shuō)明信號(hào)燈s的意義和初值

(這個(gè)初值絕不能為負(fù)值)。進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)(2)P操作①

P操作的定義

對(duì)信號(hào)燈s的p操作記為p(s)。p(s)是一個(gè)不可分割的原語(yǔ)操作，即取信號(hào)燈值減1，若相減結(jié)果為負(fù)，則調(diào)用p(s)的進(jìn)程被阻，并插入到該信號(hào)燈的等待隊(duì)列中，否則可以繼續(xù)執(zhí)行。②

P操作的實(shí)現(xiàn)

入口

S-1→S

S≥0?轉(zhuǎn)進(jìn)程調(diào)度返回入信號(hào)燈等待隊(duì)列置“等待狀態(tài)”≥0P操作原語(yǔ)流程圖進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)(3)V操作①

V操作的定義

對(duì)信號(hào)燈s的v操作記為v(s)。v(s)是一個(gè)不可分割的原語(yǔ)操作，即取信號(hào)燈值加1，若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行，否則，要幫助喚醒在信號(hào)燈等待隊(duì)列上的一個(gè)進(jìn)程。②V操作的實(shí)現(xiàn)

入口

S+1→S從信號(hào)燈的等待隊(duì)列中取出首元素入就緒隊(duì)列置“就緒狀態(tài)”返回

S≤0?>0V操作原語(yǔ)流程圖進(jìn)程及進(jìn)程管理——進(jìn)程同步機(jī)構(gòu)進(jìn)程互斥與同步的實(shí)現(xiàn)進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)1.用上鎖原語(yǔ)和開(kāi)鎖原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥

(1)框圖描述上鎖原語(yǔ)進(jìn)入臨界區(qū)csa進(jìn)程pa開(kāi)鎖原語(yǔ)上鎖原語(yǔ)進(jìn)入臨界區(qū)csb進(jìn)程pb開(kāi)鎖原語(yǔ)兩個(gè)進(jìn)程利用上鎖、開(kāi)鎖原語(yǔ)實(shí)現(xiàn)互斥進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)(2)程序描述程序task1main()pa()pb(){{{

intw=0；∕*互斥鎖,初值為0*∕

cobeginlock(w)；lock(w)；

pa()；csa

；csb

；

pb()；unlock(w)；unlock(w)；

coend

}}}

進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)2.用信號(hào)燈的P、V操作實(shí)現(xiàn)互斥

(1)框圖描述設(shè)：mutex為互斥信號(hào)燈，初值為1。p(mutex)進(jìn)入臨界區(qū)csa進(jìn)程pa

v(mutex)p(mutex)進(jìn)入臨界區(qū)csb進(jìn)程pb

v(mutex)兩個(gè)進(jìn)程利用信號(hào)燈的P、V操作實(shí)現(xiàn)互斥進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)(2)程序描述main(){intmutex=1；∕*互斥信號(hào)燈*∕

cobeginpa()；

pb()；

coend}pa()pb(){{p(mutex)；p(mutex)；

csa

；csb

；

v(mutex)；v(mutex)；

}}

(3)信號(hào)燈可能的取值兩個(gè)并發(fā)進(jìn)程，互斥信號(hào)燈的值僅取1、0和－1三個(gè)值。mutex=1

表示沒(méi)有進(jìn)程進(jìn)入臨界區(qū);mutex=0

表示有一個(gè)進(jìn)程進(jìn)入臨界區(qū);mutex=－1表示一個(gè)進(jìn)程進(jìn)入臨界區(qū)，另一個(gè)進(jìn)程等待進(jìn)入。進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)習(xí)題4-12:n個(gè)并發(fā)進(jìn)程共用一個(gè)公共變量，寫(xiě)出用信號(hào)燈實(shí)現(xiàn)n個(gè)進(jìn)程互斥的程序描述，給出信號(hào)燈的取值范圍，并說(shuō)明取值含義main(){intmutex=1；∕*互斥信號(hào)燈*∕

cobegin

p1()；p2()；…pn()；

coend}pi(){p(mutex)；訪問(wèn)變量Q；

v(mutex)；

}n個(gè)并發(fā)進(jìn)程，互斥信號(hào)燈的取值可能為 1,0,-1,…,-(n-1)進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)(4)推論推論1：若信號(hào)燈s為正值，則該值等于在掛起進(jìn)程之前對(duì)信號(hào)燈s可施行的P操作數(shù)、亦等于s所代表的實(shí)際還可以使用的物理資源數(shù)。推論2：若信號(hào)燈s為負(fù)值，則其絕對(duì)值等于登記排列在該信號(hào)燈s隊(duì)列之中等待的進(jìn)程個(gè)數(shù)，亦即恰好等于對(duì)信號(hào)燈s實(shí)施P操作而被掛起并進(jìn)入信號(hào)燈s隊(duì)列的進(jìn)程數(shù)。推論3：通常，P操作意味著請(qǐng)求一個(gè)資源，V操作意味著釋放一個(gè)資源。在一定條件下，P操作代表掛起進(jìn)程操作，而V操作代表喚醒被掛起進(jìn)程的操作。82/130

(5)共享變量的例子（互斥）

x代表某航班機(jī)座號(hào)，pa和pb兩個(gè)售票進(jìn)程，售票工作是對(duì)變量x加1。試用信號(hào)燈的P、V操作實(shí)現(xiàn)這兩個(gè)進(jìn)程的互斥。

設(shè)：mutex為互斥信號(hào)燈，初值為1。main()pa()pb(){{{

x=0;mutex=1;

cobeginp(mutex)；p(mutex);

Pa()

x:=x+1；x:=x+1；

Pb()

v(mutex)；v(mutex)；

coend

}}}進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)

(6)看病化驗(yàn)的例子（同步）

醫(yī)生的看病活動(dòng)和化驗(yàn)室的化驗(yàn)活動(dòng)的同步約束關(guān)系：

1、看病進(jìn)程開(kāi)出化驗(yàn)單，并發(fā)送給化驗(yàn)進(jìn)程，化驗(yàn)進(jìn)程才能開(kāi)始工作，否則化驗(yàn)進(jìn)程必須等待；

2、化驗(yàn)進(jìn)程化驗(yàn)完畢后得到化驗(yàn)結(jié)果，并發(fā)送給看病進(jìn)程，看病進(jìn)程才能根據(jù)化驗(yàn)結(jié)果確定醫(yī)療方案，否則看病進(jìn)程必須等待。進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)main(){ints1=0；∕*表示有無(wú)化驗(yàn)單，即化驗(yàn)單資源的個(gè)數(shù)*∕

ints2=0；∕*表示有無(wú)化驗(yàn)結(jié)果，即化驗(yàn)結(jié)果資源的個(gè)數(shù)*∕

cobegin

化驗(yàn)()；看病()；

coend}看病()化驗(yàn)(){{while(沒(méi)下班){while(沒(méi)下班){

看病

p(s1)；

v(s1)；化驗(yàn)；

p(s2)；

v(s2)

;診斷}

}}}

進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)3.兩類同步問(wèn)題的解法

(1)合作進(jìn)程的執(zhí)行次序①進(jìn)程流圖

p2p3p1

f

sp1p2p3

s

f進(jìn)程流圖示例進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)p3

s

fp5p1p2p4p6p7p8②

例：pa、pb、pc為一組合作進(jìn)程，其進(jìn)程流圖如圖所示，試用信號(hào)燈的p、v操作實(shí)現(xiàn)這三個(gè)進(jìn)程的同步。pbpcpa

f

s

ⅰ分析任務(wù)的同步關(guān)系任務(wù)啟動(dòng)后pa先執(zhí)行，當(dāng)它結(jié)束后，pb、pc可以開(kāi)始執(zhí)行，pb、pc

都執(zhí)行完畢后，任務(wù)終止。ⅱ信號(hào)燈設(shè)置設(shè)兩個(gè)同步信號(hào)燈sb、sc分別表示進(jìn)程pb和pc能否開(kāi)始執(zhí)行，其初值均為0。ⅲ同步描述

papbpcp(sb)；p(sc)；

v(sb)；

v(sc)；3個(gè)合作進(jìn)程的進(jìn)程流圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)pbpcpa

f

s程序task4main(){intsb=0；∕*表示pb進(jìn)程能否開(kāi)始執(zhí)行*∕

intsc=0；∕*表示pc進(jìn)程能否開(kāi)始執(zhí)行*∕

cobeginpa()；

pb()；

pc()；

coend}pa()pb()pc(){{{

p(sb)；p(sc)；

v(sb)；

v(sc)；

}}}

3個(gè)合作進(jìn)程的進(jìn)程流圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)習(xí)題4-13：用信號(hào)燈實(shí)現(xiàn)下面兩組進(jìn)程之間的同步，寫(xiě)出程序描述。進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)p2p3p1

f

sp4p1p3p2

f

s(a)(b)進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)p2p3p1

f

sp4(a)習(xí)題4-13(a)main(){ints2=0；∕*表示p2進(jìn)程能否開(kāi)始執(zhí)行*∕

ints3=0；∕*表示p3進(jìn)程能否開(kāi)始執(zhí)行*∕

ints4=0；∕*表示p4進(jìn)程能否開(kāi)始執(zhí)行*∕

cobeginp1()；p2()；p3()；p4()；

coend}p1()p2()p3()p4(){{{{...

p(s2)；p(s3)；p(s4)；

v(s2)；...

...

...

v(s3)；}}}

v(s4)；}

進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)習(xí)題4-13(b)main(){ints1=0；∕*表示p1進(jìn)程能否執(zhí)行完*∕

ints2=0；∕*表示p2進(jìn)程能否執(zhí)行完*∕

cobeginp1()；p2()；p3()；

coend}p1()p2()p3(){{{......

p(s1);

v(s1);

v(s2);

p(s2);}

}...}p1p3p2

f

s(b)進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)作業(yè)：

習(xí)題4-14p1p5

f

sp2p3p4

fp1p2

sp3p4p5(2)共享緩沖區(qū)的合作進(jìn)程的同步的解法

計(jì)算進(jìn)程cp和打印進(jìn)程iop公用一個(gè)單緩沖，為了完成正確的計(jì)算與打印，試用信號(hào)燈的p、v操作實(shí)現(xiàn)這兩個(gè)進(jìn)程的同步。

緩沖區(qū)bufiop

cp①兩個(gè)進(jìn)程的任務(wù)計(jì)算進(jìn)程cp經(jīng)過(guò)計(jì)算，將計(jì)算結(jié)果送入buf；打印進(jìn)程iop把buf中的數(shù)據(jù)取出打印。共享緩沖區(qū)的合作進(jìn)程的同步示意圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)②分析任務(wù)的同步關(guān)系

當(dāng)cp進(jìn)程把計(jì)算結(jié)果送入buf后，iop進(jìn)程才能從buf中取出結(jié)果去打印，否則必須等待。當(dāng)iop進(jìn)程把buf中的數(shù)據(jù)取出后，cp進(jìn)程才能把下一個(gè)計(jì)算結(jié)果數(shù)據(jù)送入buf中，否則必須等待。

緩沖區(qū)bufiop

cp共享緩沖區(qū)的合作進(jìn)程的同步示意圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)③信號(hào)燈設(shè)置

sa：表示緩沖區(qū)中是否有可供打印的計(jì)算結(jié)果，其初值為0。

sb：表示緩沖區(qū)有無(wú)空位置存放新的信息，其初值為1。

緩沖區(qū)bufiop

cp共享緩沖區(qū)的合作進(jìn)程的同步示意圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)②分析任務(wù)的同步關(guān)系

當(dāng)cp進(jìn)程把計(jì)算結(jié)果送入buf后，iop進(jìn)程才能從buf中取出結(jié)果去打印，否則必須等待。當(dāng)iop進(jìn)程把buf中的數(shù)據(jù)取出后，cp進(jìn)程才能把下一個(gè)計(jì)算結(jié)果數(shù)據(jù)送入buf中，否則必須等待。程序描述main(){intsa=0；∕*表示buf中有無(wú)信息*∕

intsb=1；∕*表示buf中有無(wú)空位置*∕

cobegincp()；iop()；

coend}cp()iop(){{while(計(jì)算未完成)while(打印工作未完成){{

得到一個(gè)計(jì)算結(jié)果；p(sa)；

p(sb)；從緩沖區(qū)中取一數(shù)；將數(shù)送到緩沖區(qū)中；v(sb)；

v(sa)；從打印機(jī)上輸出；

}}}}

緩沖區(qū)bufiop

cp共享緩沖區(qū)的合作進(jìn)程的同步示意圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)習(xí)題4-15：

get，copy，put三個(gè)進(jìn)程共用兩個(gè)緩沖區(qū)s，t（其大小為每次存放一個(gè)記錄）。get進(jìn)程負(fù)責(zé)不斷的把輸入記錄送入緩沖區(qū)s中；copy進(jìn)程負(fù)責(zé)從緩沖區(qū)s中取出記錄復(fù)制到緩沖區(qū)t中；put進(jìn)程負(fù)責(zé)把記錄從緩沖區(qū)t中取出打印。試用P、V操作實(shí)現(xiàn)這三個(gè)進(jìn)程之間的同步。進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)

緩沖區(qū)s

緩沖區(qū)tgetcopyput習(xí)題4-18：（1）3個(gè)進(jìn)程并發(fā)活動(dòng)的流程圖如圖所示，其同步算法描述如下：main(){ints=-1;cobeginp1();p2();p3();coend}p1()p2()p3(){{{......p(s);v(s);v(s);...}}}進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)p1p3p2

f

s(b)習(xí)題4-18：（2）設(shè)a，b兩進(jìn)程共用一緩沖區(qū)t，a向t寫(xiě)入信息，b從t讀出信息，算法框圖如下所示，判斷是否有錯(cuò)，指出錯(cuò)誤原因并改正。

a進(jìn)程b進(jìn)程

while(1)while(1){{......向t寫(xiě)入信息P(s)

......

V(s)從t讀信息......}}

注：信號(hào)燈s的初值為0進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)習(xí)題4-18：（3）設(shè)a，b兩進(jìn)程為并發(fā)進(jìn)程，它們共享一臨界資源。其執(zhí)行臨界區(qū)的算法框圖如下所示，判斷是否有錯(cuò)，指出錯(cuò)誤原因并改正。

a進(jìn)程b進(jìn)程

while(1)while(1){{......

CSa

P(s1)

V(s1)

CSb

P(s2)V(s2)......}}

注：信號(hào)燈s1，s2的初值為0進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)4.生產(chǎn)者——消費(fèi)者問(wèn)題

(1)生產(chǎn)者——消費(fèi)者問(wèn)題的例子

①

計(jì)算進(jìn)程和打印進(jìn)程 多個(gè)計(jì)算進(jìn)程cp不斷產(chǎn)生數(shù)據(jù)，是生產(chǎn)者；

多個(gè)打印進(jìn)程iop不斷打印數(shù)據(jù)，是消費(fèi)者； 有多個(gè)緩沖區(qū)；

②通信問(wèn)題發(fā)消息進(jìn)程send不斷產(chǎn)生消息，是生產(chǎn)者；收消息進(jìn)程receive不斷接收消息，是消費(fèi)者。進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)(2)生產(chǎn)者——消費(fèi)者問(wèn)題的一般解答

①生產(chǎn)者——消費(fèi)者問(wèn)題圖示

②生產(chǎn)者與消費(fèi)者的同步關(guān)系生產(chǎn)者：當(dāng)有界緩沖區(qū)中無(wú)空位置時(shí)，要等待；向有界緩沖區(qū)放入物品后，要發(fā)消息。消費(fèi)者：當(dāng)有界緩沖區(qū)中無(wú)物品時(shí)，要等待；從有界緩沖區(qū)取出物品后，要發(fā)消息。c1p1.........c2c3ck...p2p3pm生產(chǎn)者——消費(fèi)者問(wèn)題示意圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)③信號(hào)燈設(shè)置

ⅰ兩個(gè)同步信號(hào)燈——sb

：表示空緩沖區(qū)的數(shù)目，初值=nsa

：表示滿緩沖區(qū)(即信息)的數(shù)目，初值=0

ⅱ一個(gè)互斥信號(hào)燈——

mutex：表示有界緩沖區(qū)是否被占用，初值=1c1p1.........c2c3ck...p2p3pm生產(chǎn)者——消費(fèi)者問(wèn)題示意圖進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)④同步描述

生產(chǎn)者:消費(fèi)者:生產(chǎn)；p(sa)；p(sb)；p(mutex)；p(mutex)；從有界緩沖區(qū)中取數(shù)據(jù)；將數(shù)據(jù)放入有界緩沖區(qū)；v(mutex)；v(mutex)；v(sb)；v(sa)；消費(fèi);進(jìn)程及進(jìn)程管理——進(jìn)程互斥與同步的實(shí)現(xiàn)⑤程序描述main(){intsa=0；∕*滿緩沖區(qū)的數(shù)目*∕

intsb=n；∕*空緩沖區(qū)的數(shù)目*∕

intmutex=1；∕*對(duì)有界緩沖區(qū)進(jìn)行操作的互斥信號(hào)燈*∕

cobeginp1()；p2()；…pm(