第三章作业2

10.是说明同步和互斥这两个概念有什么区别？进程同步：进程同步也是进程之间直接的制约关系，是为完成某种任务而建立的两个或多个线程，在运行过程中,某进程可能要在某些同步点上等待另一伙伴(协作进程)为它提供消息,在未获得消息之前,该进程处于等待状态,获得消息后被唤醒进入就绪态,此后,才能继续运行。这种关系可用“进程-进程”来描述。进程互斥：进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。这种关系可以用“进程-资源-进程”来描述。11.什么是临界资源和临界区？对临界区管理的基本要求是什么？临界资源(互斥资源)：系统中一次只允许一个进程访问的资源。这些资源既包括I/O设备,如打印机等资源,也包括软件资源,如共享变量、共享文件等。临界区(互斥区):并发执行的进程中,访问临界资源的必须互斥执行的程序段叫临界区。对临界区管理的基本要求：A．当有若干进程要求进入它们的临界区时，应在有限时间内使一进程临界区。B．每次最多有一个进程处于临界区内。C．进程在临界区内逗留应在有限时间范围内。13.试给出P、V操作的定义。如何用P、V操作实现进程间的互斥，并说明信号量的物理意义？P操作原语的定义：P（S）：顺序执行下述两个动作：1.信号量的值减1，即S=S-1；2.如果S≥0，则该进程继续执行；3.如果S0，则把该进程的状态设置为阻塞态，把它相应的PCB放入相应队列中，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）ProcedureP(VarS:Semaphore)beginS:=S-1;ifS0thenW(S)end;V操作原语的定义：V（S）顺序执行下述两个动作：1.S值加1，即S=S+12.如果S0，则该进程继续运行；3.如果S≤0，则唤醒等待信号量S阻塞队列中的头一个进程（把阻塞态改为就绪态），执行V操作的进程继续运行。ProcedureS(VarS:Semaphore)beginS:=S+1;ifS=0thenR(S)end;用P、V操作实现进程间的互斥设S为两进程互斥的公用信号量，初值为1，表明该临界资源未被占用。只需要把临界区的程序设置于P(S)和V(S)之间，即可实现两进程的互斥。进程P1进程P2P(S)P(S)S1S2V（S)V(S)其中的S1、S2是两互斥的程序段，即P1、P2的临界区信号量的物理意义在操作系统中，信号量是表示资源的实体，是一个与队列有关的整型变量，其值仅能由P、V操作来改变。14.如何用P、V操作实现进程间的同步？在同步和互斥中，信号量初值的设置有何不同？用P、V操作实现进程间的同步信号量初值为0，两个进程之间的同步模型如下：进程P1进程P2L1：P（S）L2：V(S)在这种同步操作中，进程p1受到进程P2的制约，而进程P2却不受进程P1的制约，所以是非对称的。在同步中，信号量初值的设置为0；在互斥中，信号量的初值设置为1。15.试分析生产者—消费者问题的同步过程，并写出相应程序？设三个信号量：1、信号量S，初值为1，表示没有产品进入临界区，用于互斥；2、信号量n1，表示可用缓冲区个数，初值为k3、信号量n2，表示产品个数，初值为0生产者—消费者进程描述如下：问题分析：当生产者生产出一个产品，对信号量n1进行p操作，n1减1，表示申请占用一个缓冲区。只有n1大于等于0则继续执行，当n1小于0是进程阻塞。若n1大于等于0，再对S进行p操作，此时S=0，该进程继续执行，产品放入缓冲区，再对S进行v操作，此时S=1，继续执行，对产品个数n2进行v操作，即产品个数加1.当有消费者消费产品时，对产品个数n2进行p操作，即产品个数减1，只有n2大于等于0则继续执行，当n2小于0是进程阻塞。若n,2大于等于0，继续对S进行p操作，此时S=0，产品从缓冲区取出，再对S进行v操作，S=1，继续执行，对缓冲区个数进行v操作，即缓冲区个数加1.相应程序：beginB:array[0..n-1]ofinteger;P,R:integer;S,Sn,So:semaphore;p:=R:=0S:=1;Sn:=n;So:=0;cobeginprocessproduceri(i=1,2,……,m)beginL1:produceaproduct;P（Sn）;P（S）;B[P]:=product;P:=(P+1)modn;V(So);V(S);gotoL1end;processconsumerj(j=1,2,…k)beginL2:P(So);P（S）；takeaproductfromB[R];R:=(R+1)modn;V(Sn);V(S);consumegotoL2endcoend;end;16．高级通讯原语何有优点？在消息缓冲中通讯方式中，发送原语和接收原语的功能是什么？P、V操作实现的是进程之间的低级通讯，所以P、V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。高级通信原语优点便是：能够实现在进程之间传递大量的信息。发送原语的功能：将欲发送的消息从发送区复制到消息缓冲区，并把它挂起在接收进程的消息缓冲队列末尾。如果该接收进程因等待消息而处于阻塞状态，则将其唤醒。接收原语的功能：把发送者发来的消息从消息缓冲区复制到接收区，然后将消息缓冲区从消息队列中消去，如果没有消息可以接收，则进入阻塞状态。17.何谓死锁？产生死锁的原因和必要条件是什么？为什么说死锁是与时间有关的一种错误？死锁：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁。产生死锁的原因1.竞争资源引起永久性资源:可以被多个进程多次使用(可再用资源)•剥夺性资源(CPU、内存）•非剥夺性资源(磁带机、打印机)•竞争非剥夺性资源会引起死锁临时性资源:只可使用一次的资源；如信号量,中断信号,同步信号等(可消耗性资源)竞争临时性资源也会引起死锁2.进程推进顺序不当引起对资源采用“申请--分配--使用--释放”模式,由于推进顺序不当两进程都要申请对方已占有的资源产生死锁的必要条件1)互斥条件（资源独占）：一个资源每次只能给一个进程使用2)不可剥夺条件（不可强占）：资源申请者不能强行的从资源占有者手中夺取资源,资源只能由占有者自愿释放3)请求和保持条件:(部分分配,占有申请)在申请新的资源的同时保持对原有资源的占有。4)循环等待条件：存在一个进程-等待资源环形链{P1,P2,…,Pn},其中P1等待P2占有的资源,P2等待P3占有的资源,…,Pn等待P1占有的资源。当进程争夺资源时，有可能产生死锁，但不一定就会死锁。这取决于各进程推进的速度和对资源请求的顺序，从而说明死锁是一种与时间有关的错误。18.对死锁问题的处理，有哪几种策略？A鸵鸟策略采取不理睬的策略B预防策略破坏死锁的四个必要条件C避免策略精心地分配资源，动态地回避死锁D检测和解除一旦发生死锁，及时检测出来，并采取措施解除死锁。19.怎么预防死锁发生？常用的方法有哪些？系统设计时确定资源分配算法,保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。1.破坏“不可剥夺”条件在允许进程动态申请资源前提下规定,一个进程在申请新的资源不能立即满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请。2.破坏“请求和保持”条件要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。3.破坏“循环等待”条件采用资源有序分配法:把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。4、破坏“互斥性”条件允许一个资源可由多个进程同时使用（缺点：对有的资源行不通，例如打印机）23.设有n个进程共享一个互斥段，如果1）每次只允许一个进程进入互斥段；2）每次最多允许m个进程（mn）同时进入互斥段。试问，所采用的信号量初值是否相同？信号量值的变化范围如何？（1）所采用的初值是不相同的，其中的初值是1，变化范围是[-1,1],（2)中的初值是n，变化范围是[-(n-m),m]24.有一阅览室，读者进入时必须先在一张登记表上进行登记。该表为每一座位列出一个表目，包括座位、姓名。读者离开要撤离登记信息。阅览室有100个座位。（1）读者的动作有两个，一是填表进入阅览室，这时要考虑阅览室里是否有座位；一是读者阅读完毕，离开阅览室，这时的操作要考虑阅览室里是否有读者。读者在阅览室读书时，由于没有引起资源的变动，不算动作变化。故应编写1个程序，设置2个进程。进程是程序的一部分，程序运行的时候会产生进程。（2）设算法的信号量：seats——表示阅览室是否有座位（初值为100，代表阅览室的空座位数）；readers——表示阅览室里的读者数，初值为0；用于互斥的mutex，初值为1。读者进入阅览室的动作描述getin：while(TRUE){P(seats);/*没有座位则离开*/P（mutex）/*进入临界区*/填写登记表;进入阅览室读书;V（mutex）/*离开临界区*/V（readers）}读者离开阅览室的动作描述getout：while(TRUE){P（readers）/*阅览室是否有人读书*/P（mutex）/*进入临界区*/消掉登记；离开阅览室；V（mutex）/*离开临界区*/V（seats）/*释放一个座位资源*/}25.设有两个优先级相同的进程P1、P2。令信号量S1、S1的初值为0，试问P1、P2并发运行结束后x=？y=？z=？(图见书)因为P1、P1是两个并发进程，所以进程调度程序调度P1和P2的顺序是不确定的。假设P1先执行，进程P1执行到语句P(S2)时S2=-1，进程P1阻塞。此时y=3，z=4,。当进程调度程序调度到P2时，由于进程P1已执行了V(S1)，进程P2在执行P(S1)时未阻塞而继续执行，当执行到V(S2)时将P1唤醒，分以下两种情况：A．执行P2最后一个语句，此时x=5，z=9，当进程P1再次被调度时，继续执行P1的最后一条语句，此时y=12，最终结果为x=5，y=12，z=9B．如果当P2进程执行到V(S2)时，将P1唤醒，然后P2进程被中断，此时x=5，y=3，z=4.P1进程开始执行然后执行最后一个语句，此时x=5，y=7，z=4，然后P2被调度，执行z:=x+z，此时x=5，y=7，z=9.26.设有三个并发进程R、M、P,它们共享一个缓冲区。进程R负责从输入设备读入信息，每读一个记录后就把它存入缓冲区中；M负责对缓冲区中的纪录进行加工；P把加工后的纪录打印输出。读入的纪录加工输出后，缓冲区中又可存放下一记录。试写出能正确执行的程序。三个进程共用一个缓冲区，他们必须同步工作，可定义三个信号量：S1：表示是否可把读人的记录放到缓冲区，初始值为1.S2：表示是否可对缓冲区中的记录加工，初始值为0.S3：表示记录是否加工好，可以输出，初始值也为0.三个进程可如下设计：beginS1，S2，S3：semaphore；S1：＝l；S2：＝S3：＝0；cobeginprocessRbeginL1：读记录；P（S1）；记录存入缓冲区；V（S2）；gotoL1；end；processMbeginL2：P（S2）；加工记录；V（S3）；gotoL2；end；processPbeginL3：P（S3）；输出加工后的记录；V（S1）；gotoL3；end；coend；end28.桌上有一只盘子，每次只能放入一个水果。爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。用PV操作实现四人正确活动的程序。解：四人之间的关系：1爸爸，妈妈要互斥使用盘子，所以两者之间是互斥关系；2爸爸放的苹果，女儿吃，所以两者是同步关系；3妈妈放的桔子，儿子吃，所以两者也是同步关系。Structsemaphores=1,so=0,sa=0;//s表示盘空，so表示橘子，sa表示苹果。CobeginVoidfather(voi