第三章并发进程

3.1并发进程

3.2临界区管理

3.3信号量与PV操作

3.4管程

3.5进程通信

3.7死锁

第3章并发进程

3.1.1顺序程序设计3.1.2并发程序设计3.1.3进程的交互：竞争和协作3.1并发进程

3.1.1顺序程序设计程序执行的顺序性程序在处理器上执行时严格有序的，即只有当一个操作结束后，才能开始后继操作，这称为程序内部的顺序性如果完成一个任务需要若干个不同的程序，这些不同程序在时间上按调用次序严格有序执行，这称为程序外部的顺序性传统的程序设计方法是顺序程序设计,即把一个程序设计成一个顺序执行的程序模块，不同程序也是按序执行的顺序程序设计的特点执行的顺序性环境的封闭性结果的确定性过程的可再现性3.1.2并发程序设计1.程序并发执行进程的并发性:一组进程的执行在时间上是重叠的所谓执行在时间上是重叠的，是指一个进程执行的第一条指令是在另一个进程执行的最后一条指令完成之前开始的例如：有两个进程A和B，进程A执行操作a1、a2、a3，进程B执行操作b1、b2、b3进程A和B顺序（串行）执行的情况：在单处理器上，进程A执行完，进程B才开始执行，它们的操作次序为：a1、a2、a3、b1、b2、b3进程A和B并发执行的一种情况：在单处理器上，进程A和B交替（交叉）执行，它们交替（交叉）执行的操作次序可能为：a1、b1、b2、a2、a3、b3进程的并发性从宏观上看，并发性反映一个时间段中几个进程都在同一处理器上处于运行还未运行结束的状态从微观上看，任一时刻仅有一个进程在处理器上运行并发的实质是一个处理器在几个进程之间的多路复用并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率在采用多道程序设计的系统中，利用了处理器与外围设备、外围设备与外围设备之间的并行工作能力，提高了计算机的工作效率。进程的并发性(续)例如：程序P=while(I<Count){input(data[I]，process

data[I]，output

data[I])}对一批数据（Count组）进行处理Input涉及对输入设备的操作process涉及处理器的计算工作output涉及对输出设备的操作程序的编制决定了程序的执行一次仅能操作一台物理设备，设备之间存在等待现象，循环迭代一次仅能处理一组数据程序P属于串行执行的程序进程的并发性(续)若对这个计算问题改用三个程序来实现：（I=J=K=1）输入程序PI：while(I<Count){input(data[I++])，send}计算程序PC：while(J<Count){receive， process(data[J++])，send}输出程序PO：while(K<Count){receive， output(data[K++])}send、receive为通信控制操作进程的并发性(续)输入程序PI

计算程序PC 输出程序POinput(data[1])input(data[2]) process(data[1])input(data[3]) process(data[2]) output(data[1])input(data[4]) process(data[3]) output(data[2])input(data[5]) process(data[4]) output(data[3]) process(data[5]) output(data[4]) output(data[5])t1t2t3t4t5t6t7进程的并发性(续)并发程序设计：使一个程序分成若干个可同时执行的程序模块的方法称为并发程序设计(如果这些模块都属于一个进程，在进程内部执行,则称为并发多线程程序设计;若模块属于不同进程,则称为并发多进程程序设计)2.并发进程的特性

并发进程之间的关系分为两类：无关的和交互的无关的并发进程：一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关，即一个并发进程不会改变另一个并发进程的变量值交互的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的执行结果。交互的并发进程之间具有制约关系，这种交互必须是有控制的，否则会出现不正确的结果进程的并发性(续)并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件Bernstein条件：设

R(pi)={a1,a2,…an}，程序pi在执行期间引用的变量集

W(pi)={b1,b2,…bm}，程序pi在执行期间改变的变量集若两个程序p1、p2的引用变量集与改变变量集交集之和为空集：

R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}则并发进程的执行与时间无关

进程的并发性(续)并发可以是程序内部语句之间或模块之间的并发，也可以是程序与程序之间的并发例如，一个程序PS有如下四条语句：S1:a=x+y；S2:b=z+1;S3:c=a–b；S4:w=c+1;这四条语句的书写次序定义了一个串行程序的执行流程，也定义了程序的逻辑意义，程序执行时将按S1、S2、S3、S4的次序执行。现在要将该程序PS进行变换，得到一个并发程序PC，而且PC与PS等价分析：该问题的核心是找出哪些语句能够同时执行，而这些语句同时执行时对变量的访问和修改合乎程序PS的原有逻辑与时间有关的错误对于一组交互的并发进程，若执行的相对速度无法相互控制，则各种与时间有关的错误就可能出现与时间有关的错误有两种表现形式：结果不唯一永远等待…a1=n//n表示剩余的票数if(a1>=1){a1=a1-1;//售出一张票

n=a1;}…… …a2=n//n表示剩余的票数if(a2>=1){a2=a2-1;//售出一张票

n=a2;}…… 因为这种错误和相对执行速度有关，因此称为与时间有关的错误。服务器售票员A售票员B与时间有关的错误-结果不唯一与时间有关的错误-永远等待

例：内存管理问题：有2个并发进程borrow和return分别负责申请和归还主存资源，下面算法中，x表示现有空闲主存容量，B表示申请或归还的主存量。并发进程的算法及执行描述如下：voidborrow(intB){while（B>X） {进程进入等待队列等主存资源}

X=X-B;

修改主存分配表，进程获得主存资源;}voidreturn(intB){X=X+B;

修改主存分配表释放等主存资源的进程

}intX=memory;cobegin repeatborrow(B); repeatreturn(B);coend3.1.3进程的交互：竞争和协作1.并发进程之间的竞争关系系统中的多个进程之间彼此无关，相互并不知道其它进程的存在，相互之间并不交换信息。但是由于这些进程共用了一套计算机系统资源，因而必然产生竞争资源的问题，一个进程的执行可能影响到同其竞争资源的其它进程。操作系统必须协调好诸进程对资源的争用。一旦一个进程要使用已分配给另一个进程的资源，则该进程必须等待2.并发进程之间的协作关系某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当协作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后才被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步竞争（互斥）关系定义：当多个进程因为争夺临界资源而互斥执行称为进程的互斥。临界资源：也称独占资源，是指在一段时间内只允许一个进程访问的资源。例如打印机，磁带机，也可以是进程共享的数据、变量等。竞争关系

资源竞争产生两个问题：

一个是死锁(Deadlock)问题，就是一组进程如果都获得了部分资源，还想要得到其他进程所占用的资源，最终所有进程都将陷入死锁一个是饥饿(Starvation)问题，是指一个进程由于其它进程总是优先于它而被无限期拖延既要解决饥饿问题，又要解决死锁问题。协作（同步）关系data定义：进程之间这种相互合作、协同工作的关系称为进程的同步。简单说来就是：多个相关进程在执行次序上的协调。实例有2个进程P1、P2，其中P1是计算进程，P2是打印进程，每当P1计算出一个结果以后，将计算结果送到缓冲区，以便P2进程从中取出数据打印。假设缓冲区被划分为0、1、2…k-1共k个单元。还设置了两个指针：in指针用于计算进程存放数据，指向缓冲区下一个空闲的单元；out指针用于打印进程取数据，指向缓冲区下一个将要取走数据单元。…….0123456789k-1inout3.2.1互斥与临界区3.2.2临界区管理的尝试3.2.3实现临界区管理的软件方法3.2.4实现临界区管理的硬件设施

3.2临界区管理

…a1=n//n表示剩余的票数if(a1>=1){a1=a1-1;//售出两张票

n=a1;}…… …a2=n//n表示剩余的票数if(a2>=1){a2=a2-1;//售出一张票

n=a2;}…… 服务器售票员A售票员B临界资源临界区：与临界资源操作相关的程序段。3.2.1互斥与临界区与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知如果能保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误临界区的调度原则一次至多允许一个进程进入临界区内；如果已有进程在临界区中，试图进入此临界区的其他进程应等待；进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入临界区调度原则可总结成三句话：互斥使用、有空让进；忙则等待、有限等待；择一而入、让权等待、算法可行。算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁。3.2.2临界区管理的尝试下面的程序是采用标志方法实现互斥的一种尝试booleaninside1=false;/*P1不在其临界区内*/boolean

inside2=false;/*P2不在其临界区内*/cobeginprocessP1{… whileinside2do{}; inside1=true;

临界区;

inside1=false;…}coendprocessP2{… whileinside1do{}; inside2=true;

临界区;

inside2=false;…}临界区管理的尝试(续)下面是第二个尝试：booleaninside1=false;/*P1不在其临界区内*/booleaninside2=false;/*P2不在其临界区内*/cobeginprocessP1{… inside1:=true; whileinside2do{};

临界区;

inside1:=false;…}

coend

processP2{…inside2:=true;whileinside1do{};

临界区;inside2:=false;…};改进算法★初步设想◆进程交替进入临界区。当turn=0时，P1必须等待P0进入临界区执行，退出后，才能进入临界区；即使此时临界区空闲，不符合空闲让进◆任何进程在临界区内或外失败，其它进程将可能因为等待使用临界区而无法向前推进processP0{…inside[0]=true;turn=1;while(inside[1]&&turn==1) {donothing};

{临界区;}inside[0]=false;…}booleaninside[2];intturn=0or1;inside[0]=false;inside[1]=false;cobegin

coendprocessP1{…inside[1]=true;turn=0;while(inside[0]&&turn==0)

{donothing};

{临界区;}inside[1]=false;…}3.2.3实现临界区管理的软件方法Peterson算法

实现临界区管理的软件方法(续)当一个进程没有意图进入临界区时，另一个进程可以立即进入临界区。当两个进程都想进入临界区时，如果turn=i，则只有第i个进程可以进入临界区。一次只有一个进程可以进入临界区，因为在该进程退出之前turn的值是不会改变的该算法虽然能解决互斥问题但是算法复杂难以理解忙等3.2.4实现临界区管理的硬件设施

使用软件方法实现进程互斥使用临界资源是很困难的，他们通常能实现两个进程之间的互斥，很难控制多个进程的互斥程序设计时应该非常注意，否则就会产生死锁和不能解决互斥软件方法始终不能解决忙等，系统效率不高用来实现互斥的硬件设施主要有：关中断、测试并建立指令、对换指令实现临界区管理的硬件设施(续)1.关中断

关中断是实现互斥的最简单方法之一进程在测试标志之前，首先关中断，直到测试完并设置标志之后才开中断进程在临界区执行期间，计算机系统不响应中断因此，不会转向调度，也就不会引起进程或线程切换，正在执行标志测试和设置的进程或线程不会被打断，从而保证了互斥实现临界区管理的硬件设施(续)关中断方法的缺点：关中断时间过长会影响系统效率，限制处理器交叉执行程序的能力关中断方法也不适用于多CPU系统，因为，在一个处理器上关中断，并不能防止进程在其他处理器上执行相同临界区代码实现临界区管理的硬件设施(续)2.测试并建立指令（专用的机器指令）硬件提供的测试并建立指令的执行过程如下：TS(x):若x=true，则x=false；returntrue；否则returnfalse；TS指令管理临界区时，可把一个临界区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁

实现临界区管理的硬件设施(续)用TS指令实现临界区管理（互斥）的算法如下：booleans=true; //没有进程在临界区内processPi()/*i=1,2,…,n*/{ while(!TS(s))；//上锁

临界区;

s=true；//开锁}

实现临界区管理的硬件设施(续)3.对换指令

对换（Swap）指令的功能是交换两个字的内容，处理过程如下：

voidSwap(boolean&a,boolean&b)temp=a;a=b;b=temp;在Intel80x86中，对换指令称为XCHG指令实现临界区管理的硬件设施(续)用对换指令实现进程互斥的程序如下：

booleanlock;lock=false; //无进程在临界区processPi()/*i=1,2,…,n*/{ boolean

keyi=true;do{

Swap(keyi,lock);//上锁 }while(keyi);临界区；

Swap(keyi,lock);//开锁}实现临界区管理的硬件设施(续)导致饥饿：临界区空闲时，执行循环检测的若干进程能进入临界区的几率是相等的，有的进程可能运气很不好，很难有机会进入临界区，因而饥饿软件方法和硬件方法都存在忙等问题，浪费了处理器的时间不会成为一种通用的方法3.3.1同步与同步机制3.3.2信号量与PV操作3.3.3信号量实现互斥3.3.4信号量解决5位哲学家吃通心面问题3.3.5信号量解决生产者-消费者问题3.3.6信号量解决读者-写者问题3.3.7信号量解决理发师问题3.3信号量及其操作

3.3.1同步与同步机制著名的生产者--消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者--消费者问题就解决好了一类并发进程的同步问题生产者--消费者问题表述：有一环形缓冲池，包含k个缓冲区（0~k-1）。有两类进程：一组生产者进程和一组消费者进程，生产者进程向空的缓冲区中放产品，消费者进程从满的缓冲区中取走产品生产者-消费者必须同步…….0123456789k-1inout…….0123456789k-1inout生产者不能向满缓冲区写数据，消费者不能从空缓冲区取数据，即生产者与消费者必须同步。同步与同步机制(续)

生产者进程和消费者进程共享下面的变量intk;typedef

anyitemitem;itembuffer[k];//所有生产者进程和消费者进程共享bufferintin,out,counter;//所有生产者进程共享变量in//所有消费者进程共享变量out//所有生产者进程和消费者进程共享counter生产者进程：processproducer(void){

while(true){produceaniteminnextp;if(counter==k)sleep(producer);buffer[in]=nextp;in=（in+1）%k；counter=counter+1;if(counter==1)wakeup(consumer);}}消费者进程：processconsumer(void){While(true){if(counter==0)sleep(consumer);nextc=buffer[out];out=（out+1）%k；counter=counter-1;if(counter==k-1)wakeup(producer)consumetheiteminnextc;}}同步与同步机制(续)出现错误结果的原因在于各个进程访问缓冲区的速率不同，要得到正确结果，需要调整并发进程的速度，这需要通过在进程间交换信号或消息来调整相互速率，达到进程协调运行的目的。这种协调过程称为进程同步操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成常用的同步机制有：信号量与PV操作管程消息传递3.3.2信号量与PV操作1.前面种种方法解决临界区调度问题的缺点1)对不能进入临界区的进程，采用忙等测试法，浪费CPU时间2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担2.信号量同步机制的提出1965年荷兰计算机科学家E.W.Dijkstra提出了新的同步工具--信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过特殊变量展开交互。一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(Semaphore)。进程可以使用P、V两个特殊操作来发送和接收信号信号量与PV操作（续）起信号灯作用的变量称为信号量操作系统中，信号量是用来表示物理资源的实体,信号量是一种软资源除赋初值外，信号量仅能由同步原语P、V操作对其进行操作。P、V操作的不可分割性确保执行时的原子性及信号量值的完整性。利用信号量和P、V操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题一般信号量——结构型信号量

typedefstructsemaphore{ intvalue;//可用资源数

structpcb*list;//阻塞队列}voidP(semaphore&s){ s.value--;//信号量值减一 if(s.value<0)sleep(s.list);//若信号量值小于0，}阻塞当前进程。voidV(semaphore&s){ s.value++;//信号量值加一if(s.value≤0)wakeup(s.list);//若信号量值小于等于0，}

//唤醒s.list中一个进程。P、V操作的应用用P操作和V操作实现同步与互斥。s.value初值表示系统中某类资源的数目。进程进入临界区之前，首先执行P操作原语，若s.value<0,则进程调用sleep()内核函数，将自己阻塞，并插入到s.list队列排队。所以如果s.value<0，|s.value|表该信号量链表中已阻塞进程的数目。当其它进程执行了V操作原语，若s.value<=0，说明阻塞队列中还有被阻塞的进程，则调用wakeup()内核函数，把s.list中第一进程修改为就绪状态，送到就绪队列，准备执行临界区代码。propgrammutualexclusion;intn=...;/*进程数*/semaphoremutex=1;/*定义信号量mutex，mutex.value初始化为1*/cobeginprocessPi()//i=1,2,…,n{P(mutex);<临界区>;V(mutex);<其余程序>};coendvoidP(semaphore&s){ s.value--; if(s.value<0)sleep(s.list);}voidV(semaphore&s){ s.value++; if（s.value≤0)wakeup(s.list);}记录型信号量与PV操作（续）P(s)和V(s)中的s为两个过程的共享变量s的取值：信号量s的初值在初始化时，根据其用途进行设置推论1：s.value>=0时，s.value值表示还可以执行P而不会被阻塞的进程数，每执行一次P就意味着一次分配一个单位的资源推论2：当s.value<0，表示没有可用资源，请求该资源的进程被阻塞。s.value的绝对值表示被阻塞的进程数，执行一次V就意味着释放一个资源。若s.value<0表示还有被阻塞的进程，需要唤醒一个被阻塞的进程，使他到就绪队列中排队推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源；特定条件下P操作代表阻塞进程的操作，V操作代表唤醒被进程的操作。信号量的分类

信号量按其用途分为两种：公用信号量：初值常常为1，用来实现进程间的互斥。相关进程均可对其执行P、V操作私有信号量：初值常常为可用资源数，多用来实现进程同步。拥有该信号量的一类进程可以对其执行P操作，而另一类进程可以对其执行V操作信号量按其取值分为两种：二元信号量：仅取0和1，主要用于解决进程互斥问题一般信号量：允许取值为非负整数，主要用于解决进程同步问题信号量的应用我们将分析这样几个经典进程的同步问题：（1）哲学家进餐问题（2）读者--写者问题（3）生产者--消费者问题（4）理发师问题3.3.4哲学家进餐问题五位哲学家围坐一张圆桌，桌上放五根筷子，每位哲学家只能拿起与他相邻的两根筷子吃饭哲学家的生活方式是交替地进行思考和进餐哲学家筷子0011223344哲学家进餐问题（续）1.利用结构型信号量解决哲学家进餐问题数据结构：每根筷子都是一个临界资源，都应定义一个信号量，为五根筷子定义一个信号量数组，每个信号量的初值为1算法分析：若每个哲学家都各自拿起他左边的一根筷子，然后再去拿他右边的筷子时，将都拿不到右边的筷子，大家又都不会放下手中的筷子，大家在相互等待别人释放筷子，系统于是进入死锁状态操作描述：第i位哲学家的活动如下：

Semaphorefork[5];for(inti=0;i<5;i++)fork[i].value=1;

cobeginProcessphilosopher_i(){

while(true){think();

P(fork[i]);

P(fork[(i+1)mod5]); eating;

V(fork[i]);

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

coend哲学家筷子0011223344哲学家进餐问题（续）死锁问题解决方案：1）至多允许有四位哲学家同时去拿左边的筷子，最终保证至少有一位哲学家能够进餐，（至多可以有两位哲学家能够进餐）2）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家先拿他右边的筷子，然后再去拿左边的筷子3)每个哲学家取到手边的两把筷子才开始进餐，否则一根也不要3.3.5多缓冲区生产者-消费者问题对于m个生产者和n个消费者，它们共享可存放k件产品的缓冲区操作要求：多个生产者进程之间、多个消费者进程之间、生产者进程与消费者进程之间均能正确同步生产者/消费者必须同步…….0123456789k-1inout…….0123456789k-1inout生产者不能向满缓冲区写数据，消费者不能从空缓冲区取数据，即生产者与消费者必须同步。生产者/消费者必须互斥…….0123456789k-1inout生产者和消费者必须互斥进入缓冲区，即，某时刻只允许一个进程（生产者或消费者）访问缓冲区，生产者必须互斥消费者和其它任何生产者。P1将计算出来的数据放入in指针指向的6号单元，然后将in指向下个空闲单元-7号单元。P2将计算出来的数据放入in指针指向的7号单元，P2被中断。P1将计算出来的数据放入in指针指向的7号单元，覆盖了P2存放的数据，出错！生产一条数据是否有空存储单元是否可用存入一条数据归还使用权数据单元加1，唤醒一个消费者等待资源，阻塞被唤醒等待使用权，阻塞被唤醒无否有是生产者消费者空单元加1，唤醒一个生产者是否有数据单元是否可用取走一条数据归还使用权消费数据等待资源，阻塞被唤醒等待使用权，阻塞被唤醒无否有是生产者-消费者问题1.利用记录型信号量解决生产者--消费者问题

数据结构：1）含有k个缓冲区的公用缓冲池2）互斥信号量mutex：实现诸进程对缓冲池的互斥使用，一次仅允许一个进程读或写公用缓冲池，初值为13）资源信号量empty：记录空缓冲区个数，初值为k4）资源信号量full：记录满缓冲区个数，初值为0操作要求：多个生产者进程之间、多个消费者进程之间、生产者进程与消费者进程之间均能正确同步itemB[k];Semaphoreempty,full,mutex;empty=k;full=0;mutex=1;Intin=0;out=0;cobeginprocessproducer_i(){ while(true){produce();

P(empty);

P(mutex);appendtoB[in];in=(in+1)%k;

V(mutex);

V(full);}}processconsumer_j(){while(true){

P(full);

P(mutex);take()fromB[out];out=(out+1)%k;

V(mutex);

V(empty);consume();}}coend生产者-消费者问题（续）注意：1）在每个程序中用于互斥的P(mutex)和V(mutex)必须成对出现2）对资源信号量empty和full的操作也同样必须成对出现，但它们在不同的程序中3）在每个程序中的多个P操作顺序不能颠倒，否则容易引起死锁3.3.6读者写者问题该问题为多个进程访问一个共享数据区，如数据库、文件、内存区、寄存器等数据问题建立了一个通用模型，其中读进程只能读数据，写进程只能写数据。多个Reader进程同时读一条数据可以的，但如果一个Writer进程正在更新数据时，则所有其他进程都不能访问（读或写）该记录。data读者读者写者写者读者优先当一个读者正在读数据时，另一个读者也需要读数据，应该允许第二个读者进入，同理第三个及随后更多的读者都被允许进入。现在假设一个写者到来，由于写操作时排他的，所以它不能访问数据，需要阻塞等待。如果一直都有新的读者陆续到来，写者的写操作将被严重推迟。该方法称为“读者优先”。即，一旦有读者正在读数据，允许多个读者同时进入读数据，只有当全部读者退出，才允许写者进入写数据。读者写者问题（续）1.利用记录型信号量解决读者-----写者问题数据结构：1）互斥信号量writeblock：用于Reader与Writer、Writer与Writer之间的互斥，初值为1；2）ReadCount：正在读的进程数目，初值为03）互斥信号量mutex：用于Reader与Reader互斥访问整型量ReadCount，初值为1

semaphoremutex=1,writeblock=1; intReadCount=0;

cobegin processreader_i{

P(mutex);ifReadCount==0thenP(writeblock); ReadCount:=ReadCount+1;

V(mutex); {读文件};

P(mutex); ReadCount:=ReadCount-1; ifReadCount==0thenV(writeblock);

V(mutex); }

coendprocesswriter_j(){

P(writeblock);{写文件};

V(writeblock);}3.3.7信号量解决理发师问题理发店有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉。当一个顾客到来时，它必须叫醒理发师。如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等待，否则就离开。记录型信号量解决理发师问题intwaiting=0;//等候理发的顾客数

intCHAIRS=N;//为顾客准备的椅子数

semaphore

customers=0,barbers=0，mutex=1;procedurebarber(){While(true)

{P(cutomers);

P(mutex);

waiting:=waiting–1;

V(barbers);

V(mutex);

cut-hair();}}procedurecustomer(){P(mutex);

if(waiting<CHAIRS){waiting:=waiting+1;

V(customers);

V(mutex);

P(barbers);

get_haircut();}elseV(mutex);}3.4.1管程和条件变量3.4.2管程的实现3.4.3使用管程解决进程同步问题3.4 管程

3.4.1管程和条件变量1.为什么要引入管程信号量机制的缺点：进程自备同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁管程特点：管程集中封装了同步操作，对进程隐蔽了同步细节，简化了同步功能的调用界面。用户编写并发程序如同编写串行程序引入管程机制的目的：把分散在各进程中的临界区集中起来进行管理防止进程有意或无意的违反同步操作便于用高级语言来书写程序，也便于程序正确性验证管程和条件变量（续）管程基本思想：把分散在各个进程中的临界区集中起来管理，并把共享资源用数据结构抽象地表示出来建立一个“秘书”程序管理到来的访问“秘书”每次只让一个进程来访，后“秘书”更名为管程对共享资源的管理可以借助数据结构及其上所实施操作单若干进程来进行对共享资源的申请和释放通过进程在数据结构上的操作来实现代表共享资源的数据结构及并发进程在其上执行的一组过程构成了管程管程和条件变量（续）2.什么是管程一个管程定义了一个数据结构和能为并发进程所执行的在该数据结构上的一组操作，这组操作能同步进程和改变管程中的数据。3.管程的三个组成部分1）局部于管程的共享变量2）对数据结构进行操作的一组过程3）对局部于管程的数据进行初始化的语句管程和条件变量（续）说明：管程内的数据结构是私有的，只能在管程内使用，管程内的过程也只能使用管程内的数据结构进程通过调用管程的过程使用临界资源。任一时刻，管程中只能有一个活跃进程。也就是说对管程的使用是互斥的conditionc1wait(c1)…conditioncnwait(cn)urgentqueuesignal局部数据条件变量过程1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域…管程的结构

3.5.1信号通信机制3.5.2管道通信机制3.5.3共享存储区通信机制3.5.4消息通信机制

3.5进程通信

什么是进程通信？简单来说就是在进程间传输数据(交换信息)。进程通信的方式根据交换信息量的多少和效率的高低，分为：低级通信：只能传递状态和整数值（控制信息）进程1进程2P、V操作缺点：传送信息量小，效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。编程复杂：用户直接实现通信的细节，容易出错。高级通信：提高信号通信的效率，传递大量数据，减轻程序编制的复杂度。进程1进程2data提供三种方式：1、管道通信2、共享存储区方式3、消息传递方式3.5.1信号通信机制信号通信机制信号机制又称软中断，是一种进程之间进行通信的简单通信机制，通过发送一个指定的信号来通知进程某个异常时间发生，并进行适当处理软中断例子：软中断键与硬中断的差别：软中断运行在用户态，往往延时较长硬中断运行在核心态，能及时发现信号的发送：可以由内核发给用户进程也可以由用户进程发送给其他的进程。在unix系统中使用kill函数可以发送信号到某个进程或某组进程。在unix系统中定义了几十种系统信号3.5.2管道通信机制管道：是连接读写进程实现他们之间通信的一个特殊文件。属于一种共享文件通信机制管道：是一个共享文件，连接读写进程实现通信。写进程往管道一端写入信息，读进程从管道另一端读信息。管道可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质发送进程接收进程以字符流方式写入读出，按先进先出方式传送数据管道通信机制

(续)管道机制应具备的三个协调功能：1)互斥。一次仅由一个进程读写。（通过测试i_node节点的特征位来保证，改特征位就是一个读写互斥标志）2)确定对方是否存在3)同步。睡眠和唤醒功能。（管道文件只使用了i_node节点中的直接地址项，长度一般限制在几kb）4)进程在关闭管道的读出或写入时，应唤醒等待写或读此管道的进程3.5.3共享存储区通信机制内存需要交换信息的两个进程，通过对同一共享数据区的操作实现互相通信。原理进程1进程2申请申请datadata这种通信方式不要求数据移动，一般用于本地通信。对于远程通信来说，不宜实现共享存储区的访问。共享区3.5.4消息传递通信机制这里的消息是指进程之间传递的大量的、具有格式的信息。消息的格式与消息传递的机制及消息的范围有关。消息体消息格式消息头消息类型目的端地址源端地址消息长度控制信息消息传递通信机制(续)采用消息传递机制后，进程间通过消息来交换信息一个正在执行的进程可在任何时刻向另一个正在执行的进程发送消息一个正在执行的进程也可在任何时刻向正在执行的另一个进程请求消息如果进程在某一时刻的执行依赖于另一进程的消息或等待其他进程对所发消息的应答，则消息机制与进程的阻塞和释放相联系消息传递不仅具有进程通信的能力，还提供进程同步的能力消息传递通信机制(续)消息传递通信方式分两类：直接通信(消息缓冲区)方式间接通信(信箱)方式消息传递工作原理进程A进程B原语Send(B,m)消息原语Receive(m)消息缓冲区进程B的消息队列进程C的消息队列进程A的消息队列消息不阻塞发送，阻塞接收Send()和Receive()通信原语ProcedureSend(receiver,

Ma)begingetbuf(Ma，size，i)；

i.sender:=Ma.sender；

i.size:=Ma.size；

i.text:=Ms.text；

i.next:=0；

getid(PCBset,receiver,j)；

P(j.mutex)；

insert(j.Hptr,i)；

V(j.Sn)；

V(j.mutex)；

endProcedureReceive(Mb)beginj：internalname；

P(j.Sn)；

P(j.mutex)；

remove(j.Hptr，i)；

V(j.mutex)；

Mb.Sender:=i.Sender；

Mb.Size:=i.Size；

Mb.text:=i.text；

end消息传递中的寻址直接寻址(直接通信)方式：点到点的发送

Send(destination,message)；

Receive(source,message)；间接寻址(间接通信)方式：以信箱为媒介进行传递

Send(mailbox,message)；

Receive(mailbox,message)；进程A进程B原语Send(…)原语Receive(…)Mailbox利用消息传递实现互斥采用“不阻塞发送，阻塞接收”方式。多个并发执行的发送进程和接收进程共享一个邮箱box，它被初始化为一个无内容的“空”消息。如果一个进程希望进入临界区，首先必须申请从box邮箱中接收一条消息。若邮箱为“空”，则该进程阻塞（接收）；若进程收到邮箱中的一条消息，则进入临界区，执行完毕以后，退出临界区，并将该消息发送回邮箱box中。constn=…;/*进程数*/voidPi(){ messagemsg; while(true){ receive(box,msg);/*从邮箱接收一条消息*/ <临界区>; send(box,msg);/*将消息发回邮箱*/ <其余部分>} begin/*主程序*/ create_mailbox(box);/*创建邮箱*/ send(box,null);/*初始化，向邮箱发送一条空消息*/

cobegin

P(1);P(2);…P(n)

coend end利用消息传递解决生产者/消费者问题供使用了capacity条消息，类似于共享内存缓冲区中capacity个存储单元。首先将capacity条“空”消息发送给生产者。当生产者向消费者传递一个数据项时，它取走一条“空”消息，并发送回一条填充了内容的消息。通过这种方式进行数据传递，系统中的总消息数保持不变，所以，消息可以存放在预知数量的内存中。如果生产者产生数据的速度比消费者消费数据的速度快，则所有的“空”消息最终都将被填满，于是生产者将因为接收不到“空”消息而阻塞，等待消费者取走带有数据的消息，然后返回一条“空”消息。如果消费者消费数据的速度快，则消费者因为接收不到“数据”消息而阻塞，直到生产者生产并发送一条“数据”消息。propgrammutualexclusion;intcapacity=...;/*消息缓冲区大小*/null=...;/*空消息*/voidproducer(){while(true){receive(mayproduce,null);pmsg:=produce;send(mayconsume,pmsg);}}

begin/*主程序*/create_mailbox(mayproduce);create_mailbox(mayconsume);fori=1tocapacitydosend(mayproduce,null);cobeginproducer;consumer;coendendvoidconsumer(){while(true){receive(mayconsume,cmsg);consume(cmsg);send(mayproduce,null);}}

3.6.1死锁产生3.6.2死锁防止3.6.3死锁避免3.6.4死锁的检测和解除3.6死锁

3.6.1死锁的产生和定义例1：两个同学同时进入只有一张书桌和一把凳子的房间学习，假设必需拥有书桌和凳子，方可学习。如果在某个时刻，A同学申请得到书桌，而B同学申请到凳子，A和B都希望得到对方的资源，而又不肯放手已经占有的资源，这时就发生了僵持局面。例2：在哲学家进餐问题中，5个哲学家，每人各执一个筷子，任何人都没有两个筷子进餐。例3：在生产者—消费者问题中，将生产者或消费者进程的两个P操作颠倒时也会发生死锁。死锁的产生和定义(续)死锁——多个进程运行过程中因争夺资源而造成的一种僵局，无外力作用，它们都无法向前推进。有关死锁的结论：参与死锁的进程最少是两个（两个以上进程才会出现死锁）参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃产生死锁的条件1.互斥：竞争的资源一次只能被一个进程使用。2.占有且等待：当一个进程占有一些资源，同时又申请新的资源，如果新资源申请失败，进程将占有资源且阻塞等待。3.不剥夺：进程已占有的资源不能被其它进程强行剥夺。4.循环等待：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有一些资源，同时又申请环形请求链中下一个进程所占有的资源。前3个条件为必要条件，第4个条件为前3个条件可能导致的结果，为死锁的充分条件，4个条件共同组成了死锁的充分必要条件。解决死锁的方法1.死锁防止：破坏4个条件之一；有效，使资源利用率低。2.死锁避免：防止进入不安全态。3.死锁检测与恢复：检测到死锁再清除。死锁防止是通过限制死锁产生的4个充要条件之一，以预防死锁的发生。1.互斥条件是临界资源固有属性，不能避免。2.禁止“占有且等待”条件:全分配，全释放(AND）缺点：（1）延迟进程运行 （2）资源严重浪费3.禁止“不剥夺”条件 增加系统开销，且进程前段工作可能失效。3.6.2死锁防止4.禁止“环路等待”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增新设备类型不便，（原序号已排定）（2）资源与进程使用顺序不同造成浪费（3）增加了程序设计难度例：系统中有四类资源编号为：1.输入机4.打印机 7.磁带机 9.磁盘机现有两个进程P1、P2都要使用打印机和磁盘机，P1先使用打印机后使用磁盘机，P2先使用磁盘机后使用打印机。如果P2先提出资源请求，则P2只能先申请打印机（编号小），然后申请磁盘机（编号大）。P2在使用磁盘机的时候，打印机空闲着不能被P1申请使用3.6.3死锁的避免避免死锁的方法通过资源分配之前预测是否会导致死锁，决定是否进行此次资源分配。系统的两种状态：安全状态和不安全状态

按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。若系统找不到这个安全序列则处于不安全状态。安全状态实例系统有三个进程P1、P2和P3，共有14台打印机；进程P1、P2和P3要求12台、4台和9台打印机。假设T0时刻，进程P1、P2和P3已经获得5台、2台和4台打印机。进程最大需求已分配还需要可用P112573P2422P3945安全序列：P2P3P1安全状态向不安全状态上例中，若P1再申请一台，则变为不安全状态。进程最大需求已分配还需要可用P112662P2422P3945利用银行家算法避免死锁1．数据结构Resource[j]=k:系统Rj类资源一共有k个；Available[j]=k:系统现有Rj类资源k个；Claim[i,j]=k:进程i需要Rj的最大数k个；Alloction[i,j]=k:进程i已得到Rj类资源k个；Need[i,j]=k: 进程i需要Rj类资源k个有：Need[i,j]=Claim[i,j]－Alloction[i,j]设Requesti是进程i请求资源数worki：进程i执行完后系统应有资源数（也即可用数）Finish[i]：布尔量，表进程i能否顺序完成。银行家算法Requesti≤Needi出错Requesti≤Availablei阻塞Available=Available-RequestiAlloctioni=Alloctioni+RequestiNeedi=Needi-RequestiFinish[j]=.F.Needj<=WorkWork=Work+AlloctionjFinish[j]=.T.否否是是举例

ClaimR1R2R3AllocationR1R2R3

NeedR1R2R3

AvailableR1R2R3P1322100

P2613612P3314211P4422002假定系统中有四个进程P1，P2，P3，P4和三类资源R1，R2，R3，每一种资源的数量分别为9、3、6，T0时刻的资源分配情况如下表。22

2001103420011T0时刻的安全序列<P2,P1,P4,P