进程同步与互斥

进程间的相互作用进程间的联系进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）进程间的联系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。进程的互斥（间接作用）mutualexclusion由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源（Criticalresource）：系统中某些资源一次只允许一个进程使用，这样的资源称为临界资源或互斥资源或共享变量。临界区（Criticalregion）：把不允许多个并发进程交叉执行的一段程序称为临界区或临界部分。临界区就是访问公用数据的那段程序。例如堆栈操作中的get(top)和rel(blk)程序。程序段1程序段2程序段n共享变量临界区（互斥区）：criticalsection一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作。在进程中涉及到临界资源的程序段叫临界区。多个进程的临界区称为相关临界区。在临界区前面增加一段用于进行检查的代码，称为进入区。在临界区后面加上一段代码，称为退出区。进程中除了进入区、临界区及退出区之外的其它部分的代码，称为剩余区。使用互斥区的原则：空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：不允许两个以上的进程同时进入互斥区有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权使用互斥区的原则：前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:•由竞争各方平等协商•引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）进程互斥的软件方法通过平等协商方式实现进程互斥的最初方法是软件方法。其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志。其中的主要问题是设置什么标志和如何检查标志。设有两个计算进程PA、PB共享内存MS。其中MS分为三个领域，即系统区、进程工作区和数据区。这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据。系统区主要是堆栈S，其中存放那些空数据块的地址。如图所示：getspace（）{intg;gstack[top];toptop-1;}执行getspace就是获取一个空数据release(ad){toptop+1；stack[top]ad；}release(ad)就是释放一个地址为ad的数据块信号量：semaphore是一个数据结构定义如下：structsemaphore{intvalue;pointer_PCBqueue;}信号量说明：semaphores;P、V操作P(s){s.value=s.value--;if(s.value0){该进程状态置为等待状态；将该进程的PCB插入相应的等待队列末尾s.queue;}}V操作V(s){s.value=s.value++;if(s.value=0){唤醒相应等待队列s.queue中等待的一个进程；改变其状态为就绪态并将其插入就绪队列；}}P、V操作为原语操作原语：primitiveoratomicaction是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性即原语的执行必须是连续的，在执行过程中不允许被中断实现：开关中断信号量的使用：必须置一次且只能置一次初值初值不能为负数只能执行P、V操作用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)三个进程共用两个I/O缓冲区。解：设用信号量S表示共享资源，S初始值为2互斥例子例：用信号量及P、V原语实现两个并发进程Pa和Pb互斥。两进程都想进入临界区S。解：1）设sem为互斥信号量，表示临界区是否可进入2）设sem的初始值为1，表示临界区可用3）描述：Pa：Pb:P(sem)P(sem)SSV(sem)V(sem)…………例：大学校门处要求来客登记，只有一张登记表，登记表同时只能由一个人使用，用P、V原语描述一个校外人员进入大学的过程。解：1）设互斥信号量mutex，表示登记表是否正在使用2）设mutex初始值为1，表示登记表没有人使用3）描述：Enter:P(mutex)//申请登记表登记V(mutex)//释放登记表有A、B两进程，A进程从卡片机读信息入缓冲区，B进程负责加工读进缓冲区的卡片解：设信号量S1：缓冲区中有否可供加工的信息，初始值为0；信号量S2：缓冲区是否为空，初始值为1。同步例子下列活动属于哪种制约关系(1)若干同学去图书馆借书(2)两队进行篮球比赛(3)流水线生产的各道工序(4)商品生产和社会消费习题某仓库有两名发货员，一名审核员。当顾客提货时，只要发货员空闲，允许顾客进入仓库提货，顾客离开时，审核员检验顾客提货是否正确。其工作流程如下图所示。为了利用PV操作正确地协调他们之间的工作，设置了两个信号量S1和S2，初值分别位2，1。图中的a，b，c，d应分别填（）。顾客进程（i=1，2，…，n）a在仓库提货bc检验d应用实例例1P1进程和P2进程共享一台打印机，用信号量和P、V操作实现它们的互斥。例2矩阵A+B=矩阵和，用信号量和P、V原语操作实现它们的同步。A用甲进程表示，B用乙进程表示。例3矩阵A+B=C，用信号量和P、V原语操作实现它们的同步。A用甲进程表示，B用乙进程表示，C用丙进程表示。例4设公共汽车上，司机和售票员的活动分别是司机活动：启动车辆；正常运行；到站停车售票员活动：关门；售票；开门用信号量和P、V操作实现它们的关系经典的生产者─消费者问题消费者生产者经典的生产者─消费者问题同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量为S1Q进程不能从“空”的缓冲区中取产品，设置信号量S2S1初值为1，S2初值为0P：Q：while(true){while(true){生产一个产品;P(s2);P(s1);从缓冲区取产品;送产品到缓冲区;V(s1);V(s2);消费产品;};};......PQ放消息取消息nn个缓冲区(Buffer)ij多个缓冲区的生产者和消费者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;};生产者-消费者问题共享缓冲区n生产指针消费指针Producer1Producer2...ProducerMConsumer1Consumer2...ConsumerK满空指针移动方向P1有界缓冲区Q1P2Q2P3Q3::Pm-1Qk-1PmQk………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操作的顺序？P：i=0;while(true){生产产品;P(mutex);P(S1);往Buffer[i]放产品;V(mutex);V(S2);i=(i+1)%n;};Q：j=0;while(true){P(mutex);P(S2);从Buffer[j]取产品;V(mutex);V(S1);消费产品;j=(j+1)%n;};错误Q：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);};正确P.V操作讨论1)信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于02)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现.如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要3）P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂课堂练习1.若进程信号量S的初值为2,当前值为-1,则表示有_________个等待进程.A0B1C2D32.用P、V操作管理临界区时，信号量的初值应定义为_______A-1B0C1D任意值3.对于两个并发进程，设互斥信号量为mutex，若mutex=0，则________A表示没有进程进入临界区B表示有一个进程进入临界区C表示有一个进程进入临界区，另一个进程等待进入D表示有两个进程进入临界区4.在多进程的系统中,为了保证公共变量的完整性,各进程应互斥进入临界区.所谓临界区是指_________A一个缓冲区B一段数据区C同步机制D一段程序5.如果信号量的当前值为-4，则表示系统中在该信号量上有______个等待进程。6.__________是一种只能进行P操作和V操作的特殊变量。A调度B进程C同步D信号量7.有m个进程共享同一临界资源，若使用信号量机制实现对资源的互斥访问，则信号量值的变化范围是________________。课堂练习课堂练习8.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。COBEGINPROCESSPI(I=1，2，……)begin；；进入售票厅；购票；退出；；end；COEND(3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。信号量集——AND型信号量集AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为SsignalSwait(S1,S2,…,Sn)//P原语；{while(TRUE){if(S1=1&&S2=1&&…&&Sn=1){//满足资源要求时的处理；for(i=1;i=n;++i)-–Si;//注：与P的处理不同，这里是