操作系统原理 第四章 进程通信.ppt

第四章进程通信,一、进程的同步和互斥1、进程的间的相互作用相关进程：逻辑上具有某种联系的进程无关进程：逻辑上没有任何联系的进程,2、相关进程间的关系1）直接作用(相互合作）同步关系：合作进程之间再执行次序上的协调关系2）间接作用（资源共享）互斥关系：一个进程正在访问共享资源，另一个要访问该资源的进程必须等待。,3、与时间有关的错误例4-2,4、临界资源和临界区临界资源：一次仅允许一个进程所使用的资源。如物理设备。（CR:criticalresource）临界区：每个进程中访问临界资源的那段程序代码。(CS:criticalsection)进程的互斥关系：当一个进程进入临界区使用临界资源时，另外的进程必须等待；当占有临界资源的进程推出临界区后，另一个进程才被允许进入其临界区。,entrysectioncriticalsectionexitsectionremaindersection临界区(criticalsection)：进程中访问临界资源的一段代码进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exitsection)：用于将“正在访问临界区”标志清除剩余区(remaindersection)：代码中的其余部分。,同步机构设计准则1、空闲让进2、忙则等待3、多中则一4、有限等待5、让权等待原则2反映了互斥的基本含义，即使用临界区资源的排他性，原则1表示要有效利用临界资源；原则3是原则1和2的一个特殊情况；原则4和5是为了避免进程间发生等待或死锁。,三、硬件指令体制1、测试与设置技术利用TS指令实现的进程互斥算法是：每个临界资源设置一个公共布尔变量lock，True表示正被占用，False表示空闲，初值为False.进程使用临界资源时，应该按照如下三步：1）测试lock值，如果为真，表示资源已经被占用，则不断等待测试；如果为假，则表示资源可用，这时候把lock设置为真，用来排斥其他进程使用资源，我们可以把这个过程叫做关锁。2）进程进入临界区，访问临界资源3）使用完毕，推出临界区，再把lock设置为假，以释放资源，让其他进程使用。这个过程可以叫做开锁。,2、TS指令FunctionTS（Varlock:boolean）:BooleanBeginTS:=lock;Lock:=true;EndTS指令的执行是不可分割的，它实际上是一条原语。利用TS指令可以简单有效的实现互斥，以上指令是TS指令的功能描述，并非软件实现，事实上，TS指令的实现是由硬件直接完成的，并由硬件保证其原子操作性能。,3、利用TS指令完成进程互斥每个临界资源设置一个公共布尔变量lock，初值为FALSE。在进入区利用TS进行检查：有进程在临界区时，TS为TURE,则重复检查；直到其它进程退出时,TS为FALSE,检查通过；whileTS(lock);entrysectioncriticalsection;lock:=false;exitsectionremaindersection;例4-5,硬件方法的优点1）适用于任意数目的进程，在单处理器或多处理器上2）简单，容易验证其正确性3）可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点1）等待要耗费CPU时间，不能实现让权等待2）可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上3）可能死锁,四、信号量机制一个进程强制的被停在一个特定的地方直到收到一个专门的信号，这个信号就是信号量，其工作方式类似于铁路交通管理中的信号灯。信号量是一种特殊的变量，它表面形式是一个整型变量或者一个整型变量附加一个队列，它只能被特定的原语操作来执行。,1、整型信号量将信号量定义为一个整型变量s信号量s=0表示可用的临界资源实体数信号量s0表示等待使用该资源的进程数,可执行的两个标准原子操作为wait（s）和signal（s）Wait（s）：Whiles0，表示还有临界资源，可以被使用，则将临界资源数减1Signal(s):s:=s+1临界资源数加一,整型信号量的不足之处在于，若s=0，则进程必须不断循环测试，陷入忙等状态。因此用整型信号量作为同步机制的实现技术不符合“让权等待”的原则。,2、记录型信号量用一个整型变量value表示资源数量，用一个进程链表L表示所有等待该信号量的进程的PCB。初始化指定一个非负整数值value，表示空闲资源总数（又称为“资源信号量”）若为非负值表示当前的空闲临界资源数；若为负值其绝对值表示当前等待临界资源的进程数。,wait(s)s.value=s.value-1;if(s.value0)该进程状态置为等待状态将该进程的PCB插入相应的等待队列s.list末尾,signal(s)s.value=s.value+1;if(s.value=0，该值表示此时资源的空闲数量s.value0，则|s.value|表示因为得不到资源而被阻塞的进程数量2）每执行一次wait操作，意味着要求分配一次资源；因此把s.value-1,如果s.value0，进程由于得不到资源而自行阻塞，此时需要重新调度进程。3)每执行一次signal操作，意味着释放一个资源；因此把s.value+1,如果s.value=0,则表示链表中有因为请求资源而阻塞的进程，因此要把队列中的第一个进程唤醒放到就绪队列中。4)注意要保证wait和singal操作的原子性，如果不能保证，会引起与时间有关的错误。,利用信号量实现互斥设置互斥信号量mutex，并赋初值为1，表示任何时刻只能有一个进程获得临界资源。mutex=1,资源未被占用；mutex=0,资源被占用；mutex0,资源被占用，且有等待进程。wait(mutex)；进入区临界区signal(mutex)；退出区剩余区,必须成对使用wait和signal原语：遗漏wait原语则不能保证互斥访问，遗漏signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）；wait、signal原语不能次序错误、重复或遗漏。,用信号量实现同步例：设有计算和打印两个进程Pc和Pp,共同使用同一缓冲区Buffer，Pc向Buffer中存放计算结果，Pp从Buffer取计算结果送打印机输出。这两个进程的执行是相互制约的。即Pc的执行结果是Pp的执行条件；而Pp的执行结果也是Pc的执行条件，它们是相互制约的。我们把一组在异步环境中由于以各自的执行结果而限制其它进程的执行速度的现象称为并发进程的直接制约，解决这种直接制约的方法称为同步。,具体分析本问题中的同步问题：1、pc进程不能向满的缓冲区放置数据2、pp进程不能从空的缓冲区取计算结果因此，需要两个信号量，分别用来记录pc和pp进程,进程互斥引入了信号量的概念，它是与所有并发进程都相关的，因此我们称其为公有信号量。那么在进程同步中，我们同样也引入信号量的概念，但它只是与制约进程和被制约进程有关，并不涉及所有的并发进程，因此我们称其为私有信号量。,a.为并发进程设置私有信号量b.为私有信号量赋初值；c.用wait、signal原语和私有信号量实现同步。,a.设Bufferempty为Pc进程的私有信号量，Bufferfull为Pp进程的私有信号量，b.赋初值；Bufferempty=n,Bufferfull=0;c.实现：pc：beginP(Bufferempty)DatatoBufferI;V(Bufferfull);end;pp：BeginP(Bufferfull);BufferItoData;V(Bufferempty);end;,wait和signal操作必须成对出现，有一个wait操作就有一个signal操作，当为互斥操作时，他们处于同一个进程，当为同步操作时，则不在一个进程出现。,3、AND信号量集机制信号量集用于同时需要多个资源时的信号量操作AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；一段处理代码需要同时获取两个或多个临界资源可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，各不相让,假定有两个进程A和B，都要求访问共享数据D和E，这两个数据都为临界资源，为此，可为这两个数据设置用于互斥的信号量Dmutex和Emutex，并另他们的初值都为1。相应的，在这两个进程中都要包含对Dmutex和Emutex的操作。也就是：ProcessA:ProcessB:wait（Dmutex）；wait（Emutex）；wait（Emutex）；wait（Dmutex）；,如果进程A和B交替执行Wait操作：ProcessA:wait(Dmutex);则Dmutex0ProcessB:wait(Emutex);则Emutex0ProcessA:wait(Emutex);则Emutex1A阻塞ProcessB:wait(Dmutex);则Dmutex1B阻塞最后，进程A和B都进入僵持状态，在无外力作用下，两者都将无法从僵持的状态中解脱出来，我们称此刻的进程A和B已经进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能也愈大。,AND信号量基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。p49定义,5、经典进程同步问题（1）生产者-消费者问题问题描述：设有一组生产者Producer和一组消费者Consumer通过一个容量为n的有界缓冲区Buffer共同完成“生产和消费”任务。每个缓冲区可以存放一个产品，生产者负责向其中投放产品Product，而消费者负责消费其中的产品。,互斥问题：同时只能有一个进程访问某个缓冲区，即缓冲区资源是临界资源。同步问题：1）生产者进程生产产品的速度不能超过缓冲区的有效容量，即生产进程不能往“满”的缓冲区放产品。2）消费者进程消费的速度不能快于生产者的速度，即消费者进程不能从“空”的缓冲区消费产品。,由此得到生产者和消费者进程应该满足以下同步规则：1）若生产者企图把产品放入满的缓冲区，则必须阻塞等待，直到消费者从缓冲区中取走一个产品后将他唤醒。2）若消费者企图从空的缓冲区取走商品，则必须阻塞等待，直到生产者放入一个产品后将其唤醒。,为了让缓冲区得到循环利用，将缓冲区做成环形的，以方便每个区域都可以循环利用,采用信号量机制：full是满缓冲区数目，初值为0，empty是空缓冲区数目，初值为N。记为同步信号量。实际上，full和empty是同一个含义：full+empty=Nmutex用于访问缓冲区时的互斥，初值是1另外设置整形变量in，out，分别用于指示空缓冲区和满缓冲区的位置,对环状缓冲区，放数据和取数据都有一个模操作In：（In1）modnOut：（out1）modn,每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？)分析：生产者进程：P（mutex）消费者进程：P（mutex）P（empty）P（full）当进行了n次生产之后，缓冲区占满，empty=0。这时再执行生产者进程，p（mutex），mutex=0，可以执行，再执行p（empty），则empty=-1，生产者进程因为没有空的缓冲区而进入等待状态。如果此时有一个消费者进程来，首先执行p（mutex），则mutex=-1，消费者进程也进入等待，彼此都等待对方来唤醒自己，处于循环等待的状态，形成了死锁。,如果进程中wait（s1）和wait（s2）两个操作在一起，那么wait操作的顺序至关重要，尤其是一个同步wait操作与一个互斥wait操作在一起时，同步wait操作应该出现在互斥wait操作之前，而两个signal操作的顺序无关紧要。,（2）哲学家就餐问题问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支叉子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支叉子，思考时则同时将两支叉子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到叉子；,解决方法：为每个叉子单独设置一个信号量，取叉子的时候执行wait操作，放叉子时执行signal操作。算法：p51问题：可能会出现每个哲学家都拿左边的叉子，会因为得不到右边的叉子而死锁。,解决死锁的方法1）至多只允许四个哲学家同时就餐，保证至少有一个哲学家可以进餐2）规定奇数号的哲学家先拿左边的叉子，再拿右边的叉子，偶数号哲学家则相反，这样的话，0，1号哲学家竞争1号叉子，2，3号哲学家竞争3号叉子。最后总有一个哲学家可以获得两把叉子。3）仅当一哲学家左右两边的筷子都可以用时，才允许他抓起叉子。,利用AND信号量解决问题Varforkarray0.4ofsemaphore:=(1,1,1,1,1)repeatSwait(forki,forki+1mod5);eat;Ssingal(forki,forkI+1mod5);think;untilfalse;,（3）读者-写者问题问题描述：有一个共享文件L，允许多个进程同时读（reader）L中的消息，但任何时刻只能由一个进程写或者修改（writer）L中的消息；当有进程读的时候不允许任何进程写，当有进程写的时候不允许其他进程读或写。,对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，读读允许另外，因为允许多个进程同时读，系统应记录读进程的个数，而每个读进程去读文或读文件结束后都要修改读者个数，因此，读者个数又是若干读进程的共享变量，即软件临界资源，它们也必须互斥地修改这个变量。,综上所述，我们定义两个互斥信号量和一个公共变量：Wmutex用于“读-写”和“写-写”互斥，初值为1；公共变量ReadCount用于记录当前正在读文件的读者数目；Rmutex用于若干读进程对读者个数ReadCount修改的互斥。P52,6、进程通信,进程之间的通讯也就是进程之间进行信息、数据的交换。这种信息、数据的交换一般有两种：控制信息和大批量信息或数据。进程之间控制信息的交换称为低级通讯；大批量信息、数据的交换称为高级通讯。,信号量机制可以归结为进程通信的一种方式，是卓有成效的同步机制，但却不是理想的通信工具。主要问题：通信效率低；通信过程对用户不透明。因此需要新的通信机制，需要具有高效性和透明性两大特点。,1）共享存储区系统在内存中开辟一快共享存储区作为进程通信区。共享存储区通信分为建立、附接、读写和断接几个步骤优点：效率高，常用于对通信速度由比较高要求的场合。这种模式需要解决两个问题：一是怎样提供共享内存，另一个是共享内存的读写互斥问题。操作系统一般只提供共享的内存空间，处理进程间的互斥关系则由程序开发人员的责任。,2）管道通信系统管道是指用于连接多个读写进程，实现他们之间通信的共享文件。这个通信方式中，管道文件的建立、打开、读写以及关闭等操作可借用文件系统的原有机制实现，但通信进程在通信过程中的相互协调紧靠文件系统无法解决，因此需要在文件系统基础上引入通信协调机制来解决。,通信协调机制：1、同步2、互斥3、对方是否存在优点：开销小，交换的信息量大且保存时间长，对用户透明缺点：io操作次数多，同步和控制比较复杂，实质是利用外存来进行数据通信，因此传送数据量大，但是通信速度慢。,3）消息传递系统a直接通信方式发送和接收进程都必须以显式方式提供目标进程标识符，以表明向谁发送或者从谁那里接收消息。系统提供的通信原语：Send（receiver，message）Receive（sender，message）,某些情况下，接收进程可与多个发送进程通信，因此，不可能事先指定发送进程。譬如打印进程，可以接收来自任何一个进程的打印请求。对于这样的应用，在接收进程接受消息的原语中的源进程参数，是完成通信后的返回值，可以表示为Receive（id，message）,消息缓冲通信内存中开辟了若干个消息缓冲区，用以存放消息。每当一个发送进程向另一个接受进程发送消息时，便申请一个消息缓冲区，并把已经准备好的消息送到缓冲区，然后把这个缓冲区插入到接受进程的消息队列中，最后通知接受进程。接受进程收到发送进程发来的通知后，从本进程的消息队列中摘下消息缓冲区，取出需要的信息，然后把缓冲区还给系统。,系统