并发进程及死锁问题课件

第五章并发进程及死锁问题进程间的联系进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）第五章并发进程及死锁问题进程间的联系5.1进程间的制约关系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程5.1进程间的制约关系相交进程与无关进程直接作用和间接作用直接作用： 进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用： 进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间直接作用和间接作用相互感知程度

交互关系

一个进程对其他进程的影响

相互不感知(完全不了解其它进程的存在)竞争(competition)一个进程的操作对其他进程的结果无影响

间接感知(双方都与第三方交互，如共享资源)通过共享进行协作

一个进程的结果依赖于从其他进程获得的信息

直接感知(双方直接交互，如通信)通过通信进行协作

一个进程的结果依赖于从其他进程获得的信息

相互感知程度交互关系一个进程对其他进程的影响相互不感知进程的同步（直接作用）进程的同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态进程的同步（直接作用）进程的同步：synchronism例:

司机P1售票员P2

while(true)while(true)

{{

启动车辆；关门；

正常运行；售票；

到站停车；开门；

}}

例:

司机P1售票员P进程的互斥（间接作用）mutualexclusion

由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：criticalresource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量进程的互斥（间接作用）mutualexclusion临界区（互斥区）：criticalsection

一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区临界区（互斥区）：criticalsectiona:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥

进程的互斥（间接作用）a:=a-1a:=a+1P1互斥P2互斥If并发进程及死锁问题课件使用互斥区的原则：有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权使用互斥区的原则：有空让进：当无进程在互斥区时，任何有权使用使用互斥区的原则：前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）使用互斥区的原则：进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软件方法

其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志

其中的主要问题是设置什么标志和如何检查标志进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软软件解法(1)free:表示临界区标志

true:有进程在临界区

false:无进程在临界区(初值)

....

while(free);

free=true;

临界区free=false;软件解法(1)free:表示临界区标志

软件解法(2)turn:true P进入临界区false Q进入临界区....P:while(notturn);临界区turn=false;Q:while(turn);临界区turn=true;软件解法(2)turn:true P进入临界区软件解法的缺点：1.忙等待2.实现过于复杂，需要高的编程技巧

软件解法的缺点：硬件解法(1)

“测试并设置”指令booleanTS(boolean*lock){booleanold;old=*lock;*lock=true;}whileTS(&lock);临界区lock=false;硬件解法(1)

“测试并设置”指令boolean硬件解法(2)

“交换”指令voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);临界区lock:=false;硬件解法(2)

“交换”指令voidSWAP(i硬件解法(3)

“开关中断”指令进入临界区前执行：执行“关中断”指令离开临界区后执行：执行“开中断”指令硬件解法(3)

“开关中断”指令进入临界区前执行：5.2进程的同步机制──

信号量及P.V操作（解决进程同步与互斥）

5.2.1概念同步机制：信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）

会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）5.2进程的同步机制──

信号量及P.V操作（解决进程同步信号量分类公用信号量私用信号量二元信号量一般信号量信号量分类公用信号量同步机制应满足的基本要求：*描述能力*可以实现*效率高*使用方便同步机制应满足的基本要求：信号量：semaphore是一个数据结构定义如下：strucsemaphore{ intvalue; pointer_PCBqueue;}信号量说明：semaphores;信号量：semaphore是一个数据结构P、V操作P(s){s.value=s.value--;if(s.value<0){ 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s.queue;}}P、V操作P(s)P、V操作V(s){s.value=s.value++;if(s.value<=0){唤醒相应等待队列s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列

}}P、V操作V(s)P、V操作为原语操作原语：primitiveoratomicaction是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性 即原语的执行必须是连续的，在执行过程中不允许被中断实现：开关中断P、V操作为原语操作信号量的使用：

必须置一次且只能置一次初值初值不能为负数

只能执行P、V操作信号量的使用：用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)用P、V操作解决进程间互斥问题P(mutex)V(mutex经典的生产者─消费者问题消费者生产者经典的生产者─消费者问题消费者生产者经典的生产者─消费者问题同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为S1Q进程不能从“空”的缓冲区中取产品，设置信号量S2经典的生产者─消费者问题同步问题：S1初值为1，S2初值为0P：Q：while(true){while(true){生产一个产品;P(s2);P(s1);从缓冲区取产品;送产品到缓冲区;V(s1);V(s2);消费产品;};};单缓冲区生产者-消费者问题S1初值为1，S2初值为0P：并发进程及死锁问题课件多个缓冲区的生产者和消费者P：

i=0;

while(true){

生产产品;

P(S1);

往Buffer[i]放产品;

V(S2);

i=(i+1)%n;};Q：j=0;while(true){P(S2);从Buffer[j]取产品;V(S1);消费产品;j=(j+1)%n;};多个缓冲区的生产者和消费者P：

i=0;

while(【思考题】要不要对缓冲区（临界资源）进行互斥操作？【思考题】要不要对缓冲区（临界资源）进行互斥操作？Q：j=0;while(true){P(S2);P(mutex);从Buffer[j]取产品;V(mutex);V(S1);消费产品;j=(j+1)%n;};n个缓冲区、m个生产者和k个消费者P：

i=0;

while(true){

生产产品;

P(S1);

P(mutex);往Buffer[i]放产品;V(mutex);

V(S2);

i=(i+1)%n;};有错误？若颠倒两个P操作的顺序？Q：n个缓冲区、m个生产者和k个消费者P：

i=0;

wQ：j=0;while(true){P(S2);P(mutex);从Buffer[j]取产品;j=(j+1)%n;V(mutex);V(S1);消费产品;};n个缓冲区、m个生产者和k个消费者P：

i=0;

while(true){

生产产品;

P(S1);

P(mutex);往Buffer[i]放产品;i=(i+1)%n;V(mutex);

V(S2);

};正确Q：n个缓冲区、m个生产者和k个消费者P：

i=0;

wP.V操作讨论1)信号量的物理含义：S>0表示有S个资源可用S=0表示无资源可用S<0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于0P.V操作讨论2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要2)P.V操作必须成对出现，有一个P操作就一定有一个V操作3）P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂3）P.V操作的优缺点当同时需要多种资源时怎么办?

单个信号量使用很不方便，容易产生混乱,且前面已经提到对多个信号量进行P操作时,如果顺序稍有差错会导致错误发生，因此可以采用信号量集的方法当同时需要多种资源时怎么办?单个信号量信号量集——AND型信号量集

AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作

AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal信号量集——AND型信号量集AND型信号量集是指同时需要多Swait(S1,S2,…,Sn) //P原语；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理；for(i=1;i<=n;++i)-–Si;//注：与P的处理不同，这里是在确信可满足//资源要求时，才进行减1操作；break;}else{ //某些资源不够时的处理；

调用进程进入第一个小于1信号量的等待队列Sj.queue;

阻塞调用进程;}}}Swait(S1,S2,…,Sn) //P原语；Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源；for(在Si.queue中等待的每一个进程P)//检查每种资源的等待队列的所有进程；{从等待队列Si.queue中取出进程P;

Ssignal(S1,S2,…,Sn)if(判断进程P是否通过Swait中的测试)//注：与signal不同，这里要进行重新判断；{//通过检查（资源够用）时的处理；

进程P进入就绪队列;}else{//未通过检查（资源不够用）时的处理；

进程P进入某等待队列；}}}}if(判断进程P是否通过Swait中的测试)一般“信号量集”一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理

一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请一般“信号量集”一般信号量集是指同时需要多种资源、每种占用的进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si>=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);进程对信号量Si的一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1)表示互斥信号量Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情【思考题】1.用P.V操作解决下图之同步问题:getcopyputfstg【思考题】1.用P.V操作解决下图之同步问题:getcopy用P.V操作解决司机与售票员的问题司机进程：while(true){启动车辆正常驾驶到站停车}…售票员进程：while(true){关门售票开门}…用P.V操作解决司机与售票员的问题司机进程：售票员进程：5.2.2IPC经典问题1.读者写者问题

有两组并发进程:读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作5.2.2IPC经典问题1.读者写者问题第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第一类：读者优先如果读者来：第一类读者写者问题的解法读者：while(true){P(mutex);readcount++;if(readcount==1)P(w);V(mutex);读P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};写者：while(true){P(w);写V(w);};第一类读者写者问题的解法读者：写者：第一类读者写者问题的解法

（一般信号量集）读者：swait(wmutex,1,1;rcount,R,0);写；ssignal(wmutex,1);写者：swait(rcount,1,1;wmutex,1,0);写；ssignal(rcount,1);第一类读者写者问题的解法

（一般信号量集）读者：写者：2.哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子2.哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘#defineN5voidphilosopher(inti){while(true){

思考；取fork[i];取fork[(i+1)%5]；进食；放fork[i];放fork[(i+1)%5]；}}#defineN5

为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿 为防止死锁发生可采取的措施：哲学家就餐问题解法（1）#defineN5voidphilosopher(inti){while(true){

思考；取fork[i];取fork[(i+1)%5]；进食；放fork[i];放fork[(i+1)%5]；}}哲学家就餐问题解法（1）#defineN5哲学家就餐问题解法（2）#defineN5#defineTHINKING0#defineHUNGRY1#defineEATING2#typedefintsemaphore;intstate[N];semaphoremutex=1;semaphores[N];哲学家就餐问题解法（2）#defineN5voidtest(inti){if(state[i]==HUNGRY)&&(state[(i-1)%5]!=EATING)&&(state[(i+1)%5]!=EATING){state[i]=EATING;V(&s[i]);}}voidtest(inti)voidphilosopher(inti){while(true){思考;P(&mutex);state[i]=HUNGRY;test(i);V(&mutex);P(&s[i]);拿左筷子；拿右筷子；进食；

放左筷子；放右筷子；P(&mutex)state[i]=THINKING；test([i-1]%5);test([i+1]%5);V(&mutex);}}state[i]=THINKINGs[i]=0voidphilosopher(inti)【作业】1.推广例子中的消息缓冲问题。消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次若有m个发送进程呢？【作业】1.推广例子中的消息缓冲问题。2.第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）2.第二类读者写者问题：3.有一个系统，定义P、V操作如下：P(s):s:=s-1;ifs<0then

将本进程插入相应队列末尾等待；V(s)：s:=s+1;ifs<=0then从相应等待队列队尾唤醒一个进程，将其插入就绪队列；3.有一个系统，定义P、V操作如下：

问题：1）这样定义P、V操作是否有问题？2）用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。3）对于2）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？问题：4.理发师睡觉问题 理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先唤醒理发师 如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开4.理发师睡觉问题5.3进程通信概述消息缓冲通信方式5.3进程通信概述5.3.1概述 P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息

如果要在进程间传递大量信息则要用Send/Receive原语（高级通讯原语）5.3.1概述 P.V操作实现的是进程之间的低级通讯，所以进程通信的方式共享内存：相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换这种通信模式需要解决两个问题？进程通信的方式消息传递：系统为进程提供了两个高级通讯原语send和receivesend： 当要进行消息传递时执行sendreceive： 当接收者要接收消息时执行receive消息传递：共享文件模式：管道通信共享文件模式：管道通信消息传递模式消息缓冲在内存中开设缓冲区，发送进程将消息送入缓冲区，接收进程接收传递来的缓冲区信箱通信消息传递模式消息缓冲直接方式：发送进程发消息时要指定接收进程的名字，反过来，接收时要指明发送进程的名字Send(receiver,message)Receiver(sender,message)*对称形式：一对一*非对称形式：多对一（顾客/服务员）有缓冲（有界，无界），无缓冲直接方式：发送进程发消息时要指定接收进程的名字，间接方式：发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信

发送原语：send(MB,Message)接收原语：receive(MB,Message)间接方式：发送进程发消息时不指定接收进程的名字，而是指定5.3.2消息缓冲（有界缓冲区原理）：在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行5.3.2消息缓冲（有界缓冲区原理）：5.3.2消息缓冲（续1）（有界缓冲区原理）：在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行5.3.2消息缓冲（续1）（有界缓冲区原理）：PCB......Send(R,M)......SIZE:消息长度TEXT:消息正文......消息链指针............Receive(pid,N)......SIZE:消息长度TEXT:消息正文......M:N:接受进程R发送进程S消息消息消息......PCB..................M:N:接受进程消息缓冲区结构：消息长度消息正文发送者消息队列指针消息缓冲区结构：用P.V操作来实现Send原语:Send（R，M）P(m-mutex);Begin把缓冲区挂到接收进程根据R找接收进程，的消息链链尾;如果没找到出错返回;V(m-mutex);申请空缓冲区P（s-b）；V(s-m);P(b-mutex);END摘空缓冲区;V(b-mutex);把消息从M处copy到空缓冲区;其中s-b初值:n;s-m初值:0用P.V操作来实现Send原语:5.3.3信箱通信信箱组成信箱说明

与

信箱体可存放信件数，已存放信件数，指针信箱使用规则若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被释放若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放5.3.3信箱通信信箱组成5.3.3信箱通信（续1）Send实现send（N，M）：把信件M送到指定的信箱N中步骤：查找指定信箱N；若信箱未满，则把信件M送入信箱且释放“等信件”者；若信箱已满置发送信件进程为“等信箱”状态；5.3.3信箱通信（续1）Send实现5.3.3信箱通信（续2）Receive实现receive（N，X）：从指定信箱N中取出一封信，存放到指定的地址X中步骤：查找指定信箱N；若信箱中有信，则取出一封信存于X中且释放“等信箱”者；若信箱中无信件则置接收信件进程“等信件”状态；5.3.3信箱通信（续2）Receive实现5.3.3信箱通信（续3）应用实例磁盘管理进程：从信箱中收取信件，处理，启动磁盘工作其他进程：要求访问磁盘，向磁盘管理进程发一封信作业：

用进程通信的办法解决生产者消费者问题

5.3.3信箱通信（续3）应用实例5.3.4管道通信方式Pipe

也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质发送进程接收进程字符流方式写入读出先进先出顺序5.3.4管道通信方式Pipe发送进程接收进程字符流方式5.4线程的基本概念线程的引入线程与进程的对比线程的实现实例：Solaris5.4线程的基本概念线程的引入5.4.1线程的引入进程的两个基本属性：资源的拥有者：

给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度调度单位：

进程是一个执行轨迹

以上两个属性构成进程并发执行的基础5.4.1线程的引入进程的两个基本属性：5.4.1线程的引入（续1）系统必须完成的操作：创建进程撤消进程进程切换缺点：时间空间开销大，限制并发度的提高5.4.1线程的引入（续1）系统必须完成的操作：5.4.1线程的引入（续2）在操作系统中，进程的引入提高了计算机资源的利用效率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制线程的引入正是为了简化进程间的通信，以小的开销来提高进程内的并发程度5.4.1线程的引入（续2）在操作系统中，进程的引入提高了5.4.1线程的引入（续3）线程：有时称轻量级进程

进程中的一个运行实体是一个CPU调度单位资源的拥有者还是进程或称任务将原来进程的两个属性分开处理5.4.1线程的引入（续3）线程：有时称轻量级进程5.4.1线程的引入（续4）线程：有执行状态（状态转换）不运行时保存上下文有一个执行栈有一些局部变量的静态存储可存取所在进程的内存和其他资源可以创建、撤消另一个线程5.4.1线程的引入（续4）线程：线程和进程：单进程、单线程单进程、多线程多进程、一个进程一个线程多进程、一个进程多个线程线程和进程：PCB用户栈单线程进程模型用户地址空间核心栈线程控制块：包含了寄存器映像，线程优先数和线程状态信息PCB用单线程进程模型用户地址空间核线程控制块：PCB多线程进程模型用户地址空间用户栈核心栈线程控制块用户栈核心栈线程控制块用户栈核心栈线程控制块PCB多线程进程模型用户用核线程用核线程用核线程引入线程的好处：创建一个新线程花费时间少（结束亦如此）两个线程的切换花费时间少（如果机器设有“存储[恢复]所有寄存器”指令，则整个切换过程用几条指令即可完成）因为同一进程内的线程共享内存和文件，因此它们之间相互通信无须调用内核适合多处理机系统引入线程的好处：创建一个新线程花费时间少（结束亦如此）例子1：LAN中的一个文件服务器，在一段时间内需要处理几个文件请求因此有效的方法是：为每一个请求创建一个线程在一个SMP机器上：多个线程可以同时在不同的处理器上运行例子1：LAN中的一个文件服务器，在一段时间内需要处理几个文例子2：一个线程显示菜单，并读入用户输入；另一个线程执行用户命令考虑一个应用：由几个独立部分组成，这几个部分不需要顺序执行，则每个部分可以以线程方式实现当一个线程因I/O阻塞时，可以切换到同一应用的另一个线程例子2：一个线程显示菜单，并读入用户输入；5.4.2线程与进程的比较调度并发性拥有资源系统开销5.4.2线程与进程的比较调度5.4.3线程的实现机制用户级线程核心级线程两者结合方法5.4.3线程的实现机制用户级线程一、用户级线程（UserLevelThread）由应用程序完成所有线程的管理

通过线程库(用户空间)一组管理线程的过程核心不知道线程的存在线程切换不需要核心态特权调度是应用特定的一、用户级线程（UserLevelThread）由应用程线程库创建、撤消线程在线程之间传递消息和数据调度线程执行保护和恢复线程上下文线程库创建、撤消线程对用户级线程的核心活动核心不知道线程的活动，但仍然管理线程的进程的活动当线程调用系统调用时，整个进程阻塞但对线程库来说，线程仍然是运行状态

即线程状态是与进程状态独立的对用户级线程的核心活动核心不知道线程的活动，但仍然管理线程的用户级线程的优点和缺点优点：线程切换不调用核心调度是应用程序特定的：可以选择最好的算法ULT可运行在任何操作系统上（只需要线程库）缺点：大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上用户级线程的优点和缺点优点：二、核心级线程（KLT）所有线程管理由核心完成没有线程库，但对核心线程工具提供API核心维护进程和线程的上下文线程之间的切换需要核心支持以线程为基础进行调度例子：WindowsNT，OS/2二、核心级线程（KLT）所有线程管理由核心完成核心级线程的优点和缺点优点：对多处理器，核心可以同时调度同一进程的多个线程阻塞是在线程一级完成核心例程是多线程的缺点：在同一进程内的线程切换调用内核，导致速度下降核心级线程的优点和缺点优点：三、两者分析针对不同的操作系统开销和性能（线程的调度和切换速度）系统调用（阻塞）线程执行时间灵活性可扩充性抢占CPU共享进程的资源三、两者分析针对不同的操作系统四、ULT和KLT结合方法线程创建在用户空间完成大量线程调度和同步在用户空间完成程序员可以调整KLT的数量可以取两者中最好的例子：Solaris四、ULT和KLT结合方法线程创建在用户空间完成5.4.4实例：Solaris进程：用户地址空间用户栈进程控制块5.4.4实例：Solaris进程：实例：Solaris（续1）用户级线程（线程库）：可在应用进程中建立多个ULT每个ULT需要：栈、程序计数器不受调度程序的调度，线程切换快对操作系统不可见提供应用程序并行性接口实例：Solaris（续1）用户级线程（线程库）：实例：Solaris（续2）核心级线程：设置了大量KLT有一个小的数据结构和栈完成内核的所有工作调度处理器的单位，其结构由核心维护实例：Solaris（续2）核心级线程：实例：Solaris（续3）轻型进程（LWP）：

每个ULT利用LWP与内核通信每个LWP支持一个或多个用户级线程，并映射到一个核心级线程每个LWP对应用程序可见，内核看到的是多个LWP而看不到ULT实例：Solaris（续3）轻型进程（LWP）：Solaris：如果逻辑并行性不需要硬件并行性的支持，则可使用ULT例子：多个窗口，任一时刻只有一个窗口是活跃的如果内核级线程可能被阻塞，则可以指定两个或多个LWP，避免整个应用程序的阻塞Solaris：如果逻辑并行性不需要硬件并行性的支持，则可使分派唤醒继续抢占停止可运行睡眠睡眠停止停止停止用户级线程活跃连接在LWP上分派唤醒继续抢占停止可运行睡眠睡眠停止停止停止用户级线程活跃分派唤醒继续时间片或抢占停止运行阻塞系统调用停止停止轻型进程状态LWP状态独立于状态ULT（受限制ULT除外）可运行阻塞唤醒分派唤醒继续时间片停止运行阻塞停止停止轻型进程状态LWP状态进程1进程2进程3进程4进程5进程库用户内核硬件用户级线程内核级线程轻型线程处理器进程1进程2进程3进程4进程5进程库用户内核硬件用线程与进程的关系线程：进程特点例子1:1每一执行的线程是有自己的地址空间和资源的唯一进程.各种UNIX版本M:1进程定义了所拥有的地址空间和动态资源。在该进程中多个线程可被创建和执行.WindowsNT,Solaris,OS/2,OS/390,MACH线程与进程的关系线程：进程特点例子1:1每一执行的线程是各种第五章并发进程及死锁问题进程间的联系进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）第五章并发进程及死锁问题进程间的联系5.1进程间的制约关系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程5.1进程间的制约关系相交进程与无关进程直接作用和间接作用直接作用： 进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用： 进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间直接作用和间接作用相互感知程度

交互关系

一个进程对其他进程的影响

相互不感知(完全不了解其它进程的存在)竞争(competition)一个进程的操作对其他进程的结果无影响

间接感知(双方都与第三方交互，如共享资源)通过共享进行协作

一个进程的结果依赖于从其他进程获得的信息

直接感知(双方直接交互，如通信)通过通信进行协作

一个进程的结果依赖于从其他进程获得的信息

相互感知程度交互关系一个进程对其他进程的影响相互不感知进程的同步（直接作用）进程的同步：synchronism 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态进程的同步（直接作用）进程的同步：synchronism例:

司机P1售票员P2

while(true)while(true)

{{

启动车辆；关门；

正常运行；售票；

到站停车；开门；

}}

例:

司机P1售票员P进程的互斥（间接作用）mutualexclusion

由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：criticalresource 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量进程的互斥（间接作用）mutualexclusion临界区（互斥区）：criticalsection

一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区临界区（互斥区）：criticalsectiona:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥

进程的互斥（间接作用）a:=a-1a:=a+1P1互斥P2互斥If并发进程及死锁问题课件使用互斥区的原则：有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权使用互斥区的原则：有空让进：当无进程在互斥区时，任何有权使用使用互斥区的原则：前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）使用互斥区的原则：进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软件方法

其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志

其中的主要问题是设置什么标志和如何检查标志进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软软件解法(1)free:表示临界区标志

true:有进程在临界区

false:无进程在临界区(初值)

....

while(free);

free=true;

临界区free=false;软件解法(1)free:表示临界区标志

软件解法(2)turn:true P进入临界区false Q进入临界区....P:while(notturn);临界区turn=false;Q:while(turn);临界区turn=true;软件解法(2)turn:true P进入临界区软件解法的缺点：1.忙等待2.实现过于复杂，需要高的编程技巧

软件解法的缺点：硬件解法(1)

“测试并设置”指令booleanTS(boolean*lock){booleanold;old=*lock;*lock=true;}whileTS(&lock);临界区lock=false;硬件解法(1)

“测试并设置”指令boolean硬件解法(2)

“交换”指令voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);临界区lock:=false;硬件解法(2)

“交换”指令voidSWAP(i硬件解法(3)

“开关中断”指令进入临界区前执行：执行“关中断”指令离开临界区后执行：执行“开中断”指令硬件解法(3)

“开关中断”指令进入临界区前执行：5.2进程的同步机制──

信号量及P.V操作（解决进程同步与互斥）

5.2.1概念同步机制：信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）

会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）5.2进程的同步机制──

信号量及P.V操作（解决进程同步信号量分类公用信号量私用信号量二元信号量一般信号量信号量分类公用信号量同步机制应满足的基本要求：*描述能力*可以实现*效率高*使用方便同步机制应满足的基本要求：信号量：semaphore是一个数据结构定义如下：strucsemaphore{ intvalue; pointer_PCBqueue;}信号量说明：semaphores;信号量：semaphore是一个数据结构P、V操作P(s){s.value=s.value--;if(s.value<0){ 该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s.queue;}}P、V操作P(s)P、V操作V(s){s.value=s.value++;if(s.value<=0){唤醒相应等待队列s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列

}}P、V操作V(s)P、V操作为原语操作原语：primitiveoratomicaction是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性 即原语的执行必须是连续的，在执行过程中不允许被中断实现：开关中断P、V操作为原语操作信号量的使用：

必须置一次且只能置一次初值初值不能为负数

只能执行P、V操作信号量的使用：用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)用P、V操作解决进程间互斥问题P(mutex)V(mutex经典的生产者─消费者问题消费者生产者经典的生产者─消费者问题消费者生产者经典的生产者─消费者问题同步问题： P进程不能往“满”的缓冲区中放产品，设置信号量为S1Q进程不能从“空”的缓冲区中取产品，设置信号量S2经典的生产者─消费者问题同步问题：S1初值为1，S2初值为0P：Q：while(true){while(true){生产一个产品;P(s2);P(s1);从缓冲区取产品;送产品到缓冲区;V(s1);V(s2);消费产品;};};单缓冲区生产者-消费者问题S1初值为1，S2初值为0P：并发进程及死锁问题课件多个缓冲区的生产者和消费者P：

i=0;

while(true){

生产产品;

P(S1);

往Buffer[i]放产品;

V(S2);

i=(i+1)%n;};Q：j=0;while(true){P(S2);从Buffer[j]取产品;V(S1);消费产品;j=(j+1)%n;};多个缓冲区的生产者和消费者P：

i=0;

while(【思考题】要不要对缓冲区（临界资源）进行互斥操作？【思考题】要不要对缓冲区（临界资源）进行互斥操作？Q：j=0;while(true){P(S2);P(mutex);从Buffer[j]取产品;V(mutex);V(S1);消费产品;j=(j+1)%n;};n个缓冲区、m个生产者和k个消费者P：

i=0;

while(true){

生产产品;

P(S1);

P(mutex);往Buffer[i]放产品;V(mutex);

V(S2);

i=(i+1)%n;};有错误？若颠倒两个P操作的顺序？Q：n个缓冲区、m个生产者和k个消费者P：

i=0;

wQ：j=0;while(true){P(S2);P(mutex);从Buffer[j]取产品;j=(j+1)%n;V(mutex);V(S1);消费产品;};n个缓冲区、m个生产者和k个消费者P：

i=0;

while(true){

生产产品;

P(S1);

P(mutex);往Buffer[i]放产品;i=(i+1)%n;V(mutex);

V(S2);

};正确Q：n个缓冲区、m个生产者和k个消费者P：

i=0;

wP.V操作讨论1)信号量的物理含义：S>0表示有S个资源可用S=0表示无资源可用S<0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于0P.V操作讨论2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要2)P.V操作必须成对出现，有一个P操作就一定有一个V操作3）P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂3）P.V操作的优缺点当同时需要多种资源时怎么办?

单个信号量使用很不方便，容易产生混乱,且前面已经提到对多个信号量进行P操作时,如果顺序稍有差错会导致错误发生，因此可以采用信号量集的方法当同时需要多种资源时怎么办?单个信号量信号量集——AND型信号量集

AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作

AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal信号量集——AND型信号量集AND型信号量集是指同时需要多Swait(S1,S2,…,Sn) //P原语；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理；for(i=1;i<=n;++i)-–Si;//注：与P的处理不同，这里是在确信可满足//资源要求时，才进行减1操作；break;}else{ //某些资源不够时的处理；

调用进程进入第一个小于1信号量的等待队列Sj.queue;

阻塞调用进程;}}}Swait(S1,S2,…,Sn) //P原语；Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源；for(在Si.queue中等待的每一个进程P)//检查每种资源的等待队列的所有进程；{从等待队列Si.queue中取出进程P;

Ssignal(S1,S2,…,Sn)if(判断进程P是否通过Swait中的测试)//注：与signal不同，这里要进行重新判断；{//通过检查（资源够用）时的处理；

进程P进入就绪队列;}else{//未通过检查（资源不够用）时的处理；

进程P进入某等待队列；}}}}if(判断进程P是否通过Swait中的测试)一般“信号量集”一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理

一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请一般“信号量集”一般信号量集是指同时需要多种资源、每种占用的进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si>=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);进程对信号量Si的一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1)表示互斥信号量Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情【思考题】1.用P.V操作解决下图之同步问题:getcopyputfstg【思考题】1.用P.V操作解决下图之同步问题:getcopy用P.V操作解决司机与售票员的问题司机进程：while(true){启动车辆正常驾驶到站停车}…售票员进程：while(true){关门售票开门}…用P.V操作解决司机与售票员的问题司机进程：售票员进程：5.2.2IPC经典问题1.读者写者问题

有两组并发进程:读者和写者,共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作5.2.2IPC经典问题1.读者写者问题第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第一类：读者优先如果读者来：第一类读者写者问题的解法读者：while(true){P(mutex);readcount++;if(readcount==1)P(w);V(mutex);读P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};写者：while(true){P(w);写V(w);};第一类读者写者问题的解法读者：写者：第一类读者写者问题的解法

（一般信号量集）读者：swait(wmutex,1,1;rcount,R,0);写；ssignal(wmutex,1);写者：swait(rcount,1,1;wmutex,1,0);写；ssignal(rcount,1);第一类读者写者问题的解法

（一般信号量集）读者：写者：2.哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子2.哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘#defineN5voidphilosopher(inti){while(true){

思考；取fork[i];取fork[(i+1)%5]；进食；放fork[i];放fork[(i+1)%5]；}}#defineN5

为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿 为防止死锁发生可采取的措施：哲学家就餐问题解法（1）#defineN5voidphilosopher(inti){while(true){

思考；取fork[i];取fork[(i+1)%5]；进食；放fork[i];放fork[(i+1)%5]；}}哲学家就餐问题解法（1）#defineN5哲学家就餐问题解法（2）#defineN5#defineTHINKING0#defineHUNGRY1#defineEATING2#typedefintsemaphore;intstate[N];semaphoremutex=1;semaphores[N];哲学家就餐问题解法（2）#defineN5voidtest(inti){if(state[i]==HUNGRY)&&(state[(i-1)%5]!=EATING)&&(state[(i+1)%5]!=EATING){state[i]=EATING;V(&s[i]);}}voidtest(inti)voidphilosopher(inti){while(true){思考;P(&mutex);state[i]=HUNGRY;test(i);V(&mutex);P(&s[i]);拿左筷子；拿右筷子；进食；

放左筷子；放右筷子；P(&mutex)state[i]=THINKING；test([i-1]%5);test([i+1]%5);V(&mutex);}}state[i]=THINKINGs[i]=0voidphilosopher(inti)【作业】1.推广例子中的消息缓冲问题。消息缓冲区为k个，有1个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次若有m个发送进程呢？【作业】1.推广例子中的消息缓冲问题。2.第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）2.第二类读者写者问题：3.有一个系统，定义P、V操作如下：P(s):s:=s-1;ifs<0then

将本进程插入相应队列末尾等待；V(s)：s:=s+1;ifs<=0then从相应等待队列队尾唤醒一个进程，将其插入就绪队列；3.有一个系统，定义P、V操作如下：

问题：1）这样定义P、V操作是否有问题？2）用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。3）对于2）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？问题：4.理发师睡觉问题 理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子如果没有顾客,则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先唤醒理发师 如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来等；否则离开4.理发师睡觉问题5.3进程通信概述消息缓冲通信方式5.3进程通信概述5.3.1概述 P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息

如果要在进程间传递大量信息则要用Send/Receive原语（高级通讯原语）5.3.1概述 P.V操作实现的是进程之间的低级通讯，所以进程通信的方式共享内存：相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换这种通信模式需要解决两个问题？进程通信的方式消息传递：系统为进程提供