第3章 进程的同步与通信

Chap.3进程的同步与通信1、如何控制和协调并发进程异步执行的时序？进程的同步机制2、进程之间如何互相联系，传递信息？进程的通信本章讨论的主要问题3.1进程间的相互作用进程间的联系进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）1.进程间的联系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态同步问题1Aracebetweentwoormoreteams,inwhicheachteammemberrunsonlyasetpartoftheraceandisthenrelievedbyanothermemberoftheteam.运动员1运动员2运动员3运动员4S1S2S3缓冲区键盘计算缓冲区缓冲区B进程A进程A进程只有当缓冲区为空时，才能将数据输入缓冲区，B进程只有当缓冲区有数据时，才能从缓冲区取数进行计算。进程的同步与互斥虽然是两个既有区别又有联系的概念，但从本质上看并发进程的异步执行都必须按一定的相互约束的时序进行，因此统称为“进程同步”。显然，必须解决好进程的同步问题，才能保证并发进程的正常执行。同步问题2进程的互斥（间接作用）由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：criticalresource系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量临界区（互斥区）：criticalsection一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区每个进程互斥访问临界资源的那段代码称为临界区。代码构成如下：repeatentrysection进入区—申请进入临界区criticalsection临界区—访问临界资源exitsection退出区—退出对临界资源的访问remaindersection剩留区—进程的其他代码untilfalse1。什么是临界资源凡是以互斥方式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性。2。临界区（criticalsection）使用互斥区的原则有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件软件使用互斥区的原则（续）软件解法(1)free:表示临界区标志true:有进程在临界区false:无进程在临界区(初值)....while(free);free=true;临界区free=false;空循环软件解法(2)turn:trueP进入临界区falseQ进入临界区....P:while(notturn);临界区turn=true;Q:while(turn);临界区turn=false;软件解法的缺点：1.忙等待2.实现过于复杂，需要高的编程技巧硬件解法：提供专门的硬件指令，允许对一个字的内容进行检测和修正，或交换两个字的内容目的：解决共享变量的完整性和正确性简单、有效，特别适用于多处理机缺点：忙等待硬件解法(1)“测试并设置”指令TS指令执行过程不可分割。为临界资源设置一个布尔量LOCK：实现的基本思想是：对临界资源“加锁”进程的同步机制可以用软件实现，也可以用硬件实现。（1）用Test—and—Set指令实现互斥LOCK={false没有进程在临界区true有进程进入临界区TS指令的形式：functionts（varlock：boolean）：boolean；begints：=lock；lock：=true；end；以两进程P1、P2并发执行为例，如果P1先执行：若P1先进入临界区，则P2循环执行TS指令，直到P1退出临界区。调用TS指令p1TS=true进入P1临界区Lock：=false进入剩余区调用TS指令p2TS=true进入P2临界区Lock：=false进入剩余区调用TS指令TS=trueNY进入P1临界区调用TS指令TS=trueYN调用TS指令调用TS指令TS=trueTS=trueLock：=false进入P2临界区进入剩余区如果P2先执行：若P2先进入临界区，则P1循环执行TS指令，直到P2退出临界区。结论：①TS指令有效实现互斥（空闲让进、忙则等待）②循环测试，处于“忙等待”（未让权等待）调用TS指令p2TS=true进入P1临界区Lock：=false进入剩余区调用TS指令TS=trueNY进入P2临界区Lock：=false进入剩余区调用TS指令p1TS=true进入P2临界区Lock：=false进入剩余区调用TS指令TS=trueYN调用TS指令调用TS指令TS=trueTS=true进入P1临界区Lock：=false进入剩余区2.进程的同步机制──信号量及P.V操作以上介绍的各种算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题操作系统可从进程管理者的角度来处理互斥的问题，信号量就是操作系统提供的管理公有资源的有效手段进程的同步机制（续）同步机制：信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）同步机制应满足的基本要求：*描述能力*可以实现*效率高*使用方便1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）一种卓有成效的进程同步机制最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）广泛应用于存在临界资源和临界区控制的场合信号量及P、V操作Semaphores(proposedbyDijkstrain1965)WhataSemaphoreis?AnintegervariableRepresentthenumberofresourcesavailable(whenitisgreaterthanorequalsto0)Representthenumberofprocesseswaitingfortheresources(whenitislessthan0)OperationsonasemaphoreInitializationPoperation-------totestVoperation-------toincrement信号量：semaphore是一个数据结构定义如下：strucsemaphore{intvalue;pointer_PCBqueue;}信号量说明：semaphores;①S.value：=S.Value+1；②若S.Value0进程继续执行。若S.Value≤0则释放S等待队列中的一个进程，使之转为就绪状态。P、V操作原语定义：VARS：Semaphore；1。P操作（wait原语）每作一次P操作，申请分配一个单位的资源。P（S）—对信号量S进行P操作。2。V操作（Signal原语）V（S）—对信号量S进行V操作，释放一个单位的资源。①S.value：=S.Value-1；②若S.Value≥0进程继续执行。若S.Value0进程阻塞，并进入等待队（L）。P操作ProcedureP（s）；Vars：semaphore；begins.value：=s.value-1ifs.value0thenblock（s.L）end；V操作ProcedureV（s）；Vars：semaphore；begins.value：=s.value+1ifs.value≤0thenwakeup（s.L）end；P、V操作的算法描述说明：①S.Value0时，其值表示某类资源可用数量。S.Value≤0时，其绝对值表示在信号量队列中等待该资源的进程数。②P、V操作有严格的不可分割性；执行过程不允许中断；③P、V操作成对出现。（根据同步机制的原则，分析P、V操作的特点，）？问题？如何使用P、V操作实现同步机制？考虑：如何控制互斥地使用临界资源？如何控制进程并发执行的时序？实现同步机制基本思想是：加锁、解锁AnotherMeaningfromSemaphoreP——torequestresourcesV——toreleaseresources1、利用信号量实现进程互斥共享某个公有资源定义一个互斥信号量，初值为1P(S)V(S)临界区MutualExclusionAchievedbyUsingSemaphoresharedsemaphoreS=1;//…P(S);//CriticalSectionV(S);TheBounded-BufferProblem1PAPBbuf设mutex—公共互斥信号量初值：mutex.Value=1利用P、V操作实现互斥的模型实现进程互斥—以两个进程并发执行为例进程P1...P（mutex）；进入P1临界区；V（mutex）；...值0①进程P2...P（mutex）；进入P2临界区；V（mutex）；...值0③值-1②进程P1先执行P（mutex）；进程P1进入临界区；进程P2开始执行P（mutex）；进程P2阻塞，插入阻塞队列。若进程P1再次执行V（mutex）；mutex.Value=0释放资源。2、实现进程间的同步PA：需要空缓冲区资源，该资源由PB取数后产生，空缓冲区资源用信号量Sempty表示PB：需要满缓冲区资源，该资源由PA送数后产生，满缓冲区资源用信号量Sfull表示PAPBbuf实现进程间的同步PA:P(Sempty);送数据V(Sfull);GotoPA;PB:P(Sfull);取数据V(Sempty);GotoPB;SharedSemaphoreSempty:=1SharedSemaphoreSfull:=0分析：打印进程与计算进程之间有两个约束：1）计算进程只有当缓冲区为空时，才能放入计算结果。2）打印进程只有当缓冲区有结果时，才能从缓冲区取计算结果打印。定义两个信号量：Sempty、Sfull，用于控制这两个约束：Sfull—控制打印进程从缓冲区取计算结果打印。Sempty—控制计算进程向缓冲区送计算结果。2、实现进程同步实例：打印进程与计算进程的同步问题。缓冲区计算打印机缓冲区缓冲区打印进程计算进程SfullSempty设：Sempty初值为1Sfull初值为0—表示缓冲区为空。当Sfull0表示可以打印当Sempty0表示可以放入计算结果。信号量机制的基本原理两个或多个进程可以通过简单的信号进行合作，一个进程被迫在某个指定位置停止，直到它收到一个特定的信号才继续。通过合适的信号结构可以满足任何复杂的协作要求。为了发信号，使用特殊的变量——信号量。进程执行原语signal(S)/V(S)发出信号，通过执行wait(S)/P(S)接收信号；如果没有相应的信号到达，该进程将被挂起直到所需信号到达。AnotherMeaningfromSemaphor