操作系统原理第五章

清华大学出版社1/19第5章并发性:互斥、同步和通信并发执行的各个进程之间，既有独立性，又有制约性。独立性：各进程可独立地向前推进制约性：一个进程会受到其他进程的影响，这种影响关系可能有：互斥同步通信清华大学出版社2/19第5章并发性:互斥、同步和通信5.1并发的原理5.2信号量机制5.3管程机制5.4进程通信清华大学出版社3/195.1并发的原理5.1.1与时间有关的错误5.1.2互斥与同步的概念5.1.3临界区与进程互斥5.1.4硬件支持互斥的方法清华大学出版社4/195.1.1与时间有关的错误例：Pl，P2两并发进程共享变量count，如果按如下顺序运行：P1：R1=count；R1=R1+1；count=R1；P2:R2=count；R2=R2+1；count=R2；结果:count的值+2，正确清华大学出版社5/195.1.1与时间有关的错误如果Pl，P2按如下顺序运行：P1：R1=count；R1=R1+1；count=R1；P2:R2=count；R2=R2+1；count=R2；结果:count的值+1,错误！清华大学出版社6/195.1.1与时间有关的错误原因：1、共享了变量；2、“同时”使用了这个变量。解决办法：1、取消共享（×）2、允许共享，不允许同时使用（√）------进程互斥清华大学出版社7/195.1.2互斥与同步的概念1、进程间两种形式的制约关系间接制约关系：进程间要通过某种中介发生联系，是无意识安排的。直接制约关系：进程间的相互联系是有意识的安排的。清华大学出版社8/192、进程的同步（直接制约）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态5.1.2互斥与同步的概念清华大学出版社9/19例:司机P1售票员P2while(true）while(true){{启动车辆；关门；正常运行；售票；到站停车；开门；}}5.1.2互斥与同步的概念清华大学出版社10/193、进程的互斥（间接制约）mutualexclusion由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。5.1.2互斥与同步的概念清华大学出版社11/195.1.3临界区与进程互斥1、临界资源(criticalresource）系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。2、临界区（互斥区）：criticalsection在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区清华大学出版社12/19进程的互斥（间接作用）…a:=a+1print(a)…P1互斥…a:=a-1print(a)…P2互斥…Ifa0thena:=a+1elsea:=a-1…P3互斥临界区的例子清华大学出版社13/19程序段1共享变量程序段2程序段3临界区的例子清华大学出版社14/19While(1){进入区代码;临界区代码;退出区代码;其余代码;}3、实现各进程互斥进入临界区进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entrysection)。在临界区后面加上一段称为退出区(exitsection)的代码5.1.3临界区与进程互斥清华大学出版社15/19空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：不允许两个以上的进程同时进入互斥区有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权4、使用互斥区的原则：5.1.3临界区与进程互斥清华大学出版社16/195、进程互斥的解决主要有两种:硬件方法：分为中断禁用、专用机器指令两种（5.1.4节）软件方法：用编程解决，包括操作系统或程序设计语言中提供某种级别的支持，比如信号量机制和管程机制（5.2～5.3节），但常常忙等待5.1.3临界区与进程互斥清华大学出版社17/195.1.4硬件支持互斥的方法1．中断禁用为保证互斥，只需保证进程不被中断就可以了，通过系统内核为启用中断和禁用中断定义的原语实现。进程结构：While(true){禁用中断;临界区;启用中断;其余部分;}缺点：效率低，不能用于多处理器结构。清华大学出版社18/195.1.4硬件支持互斥的方法2．专用机器指令可用于多处理器机器，2条硬件指令：testset指令和exchange指令testset指令定义：booleantestset(inti){if(i==0){i=1;returntrue;}else{returnfalse;}}清华大学出版社19/195.1.4硬件支持互斥的方法testset指令实现进程的互斥访问设置—个共享变量bolt，其初值=0，代表资源空闲，其值为1代表资源被占用。实现互斥的各个进程为：while(true){while(!testset(bolt));/*当资源占用时等待*/临界区;bolt=0;其余部分;}清华大学出版社20/195.1.4硬件支持互斥的方法exchange指令定义：voidexchange(intregister,intmemory){inttemp;temp=memory;memory=register;register=temp;}该指令交换一个寄存器和一个存储单元的内容清华大学出版社21/195.1.4硬件支持互斥的方法exchange指令实现进程的互斥访问设置一个共享变量bolt,初值为0,各个并发的进程设置一个局部变量key,初值为1。实现互斥的各个进程描述为：while(true){key=1while(key!=0)exchange(key,bolt);临界区;exchange(key,bolt);其余部分;}清华大学出版社22/195.1.4硬件支持互斥的方法特点：唯一可以进入临界区的进程是发现bolt等于0的进程，它将bolt置1排斥其它进程进入临界区。当该进程离开临界区时将bolt重新置0，允许另一个进程进入临界区。缺点：不能满足“让权等待”的准则，造成处理机空等（忙等）。且只能解决互斥，不能用于同步。信号量机制能完满地解决上述问题。清华大学出版社23/195.2信号量机制5.2.1信号量的概念5.2.2信号量的应用5.2.3生产者—消费者问题5.2.4哲学家进餐问题5.2.5读者—写者问题清华大学出版社24/195.2.1信号量的概念信号量(semaphore，信号灯)定义信号量说明：semaphores;是一个记录型数据结构定义如下：strucsemaphore{intvalue;pointer_PCBqueue;}清华大学出版社25/195.2.1信号量的概念P、V操作除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被称为P、V操作。原子操作（atomicaction）或简称“原语”(primitive)：在执行上不可中断的操作。清华大学出版社26/195.2.1信号量的概念P、V操作定义P(s)/*=wait(s)）*/{s.value=s.value－－;if(s.value0)block(s.queue)}V(s)/*=signal(s)*/{s.value=s.value++;if(s.value=0)wakeup(s.queue)/*唤醒等待队列一个进程，使其变为就绪态*/}清华大学出版社27/195.2.1信号量的概念P、V操作含义1)信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数2)P、V操作的含义P(S):表示申请一个资源V(S)：表示释放一个资源。信号量的初值应≥0清华大学出版社28/195.2.2信号量的应用利用信号量实现进程互斥while(true){P(mutex);criticalsection;V(mutex);remaindersection;}while(true){P(mutex);criticalsection;V(mutex);remaindersection;}Process1:Process2:清华大学出版社29/195.2.2信号量的应用P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)清华大学出版社30/195.2.2信号量的应用利用信号量实现前驱关系（同步例子）P1P2设置一个信号量S，其初值为0,P1；V(S);P(S)；P2;如此即可实现先执行P1，再执行P2清华大学出版社31/195.2.2信号量的应用利用信号量实现前驱关系S1S2S3S4S5S6设5个信号量semaphorefl=f2=f3=f4=f5=O；含义：分别表示进程S1、S2、S3、S4、S5是否执行完成。清华大学出版社32/195.2.2信号量的应用各个进程的结构为：voidS1(){……V(f1);V(f1);}voidS2(){P(f1);……V(f2);V(f2);}voidS3(){P(f1);……V(f3);}voidS4(){P(f2);……V(f4);}voidS5(){P(f2);……V(f5);}voidS6(){P(f3);P(f4);P(f5);……}清华大学出版社33/195.2.3生产者—消费者问题单缓冲区：生产者进程P和消费者进程C共用一个缓冲区，P生产产品放入缓冲区，C从缓冲区取产品来消费。消费者生产者清华大学出版社34/195.2.3生产者—消费者问题单缓冲区的同步问题P进程不能往“满”的缓冲区中放产品，设置信号量为emptyC进程不能从“空”的缓冲区中取产品，设置信号量full单缓冲区的互斥问题P、C进程不能同时使用缓冲区清华大学出版社35/195.2.3生产者—消费者问题单缓冲区的生产者─消费者问题解P：C：while(true){while(true){生产一个产品;P(full);P(empty);从缓冲区取产品;送产品到缓冲区;V(empty);V(full);消费产品;};};empty初值为1，full初值为0清华大学出版社36/195.2.3生产者—消费者问题多个缓冲区：若干个生产者进程P1,P2,…,Pn，若干个消费者进程Cl，C2，…，Cm。它们通过一个有界缓冲池(k个)联系。....PC生产者消费者kk个Buffernm清华大学出版社37/195.2.3生产者—消费者问题多缓冲区的同步互斥问题同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：所有进程应互斥使用缓冲池这一临界资源。清华大学出版社38/195.2.3生产者—消费者问题多缓冲区的生产者─消费者问题解法设置三个信号量mutex，empty，full的初始值分别为1，n，0；思考：P操作的顺序可换吗？清华大学出版社39/195.2.3生产者—消费者问题注意：此解中，无论是生产者进程还是消费者进程，V操作的次序无关紧要，但P操作的次序不能随意交换，否则可能造成死锁。例如，若将生产者进程中的P(empty)与P(mutex)的次序交换，则在一定条件下就会出现死锁现象。清华大学出版社40/195.2.4哲学家进餐问题5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子，如图所示。为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。图5.3哲学家进餐问题清华大学出版社41/195.2.4哲学家进餐问题-解Semaphorechopstick[5]=1；//为每支筷子设置一个信号量哲学家i的活动为：voidphilosopher(inti){while(true){思考；P