计算机操作系统典型例题解析之三.doc

计算机操作系统典型例题解析之三【例1】分配到必要的资源并获得处理机时的进程状态是（B ）。A、就绪状态 B、执行状态 C、阻塞状态D、新状态分析：进程有三种基本状态：就绪状态、执行状态和阻塞状态。当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机便可立即执行，这时的状态称为就绪状态；处于就绪状态的进程如果获得了处理机，其状态转换为执行状态；进程因发生某种事件（如I/O请求、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种状态为阻塞状态；而新状态是指创建了进程但尚未把它插入到就绪队列前的状态。所以本题的答案是B。【例2】挂起的进程被激活，应该使用（C）原语。A、CreateB、Suspend C、ActiveD、Wakeup分析：在不少系统中，进程除了三种基本状态外，又增加了一些新的状态，其中最重要的是挂起状态。“挂起”的实质是使进程不能继续执行，即使挂起后的进程处于就绪状态，它也不能参加对CPU的竞争，进程的挂起调用Suspend（）原语。因此，被挂起的进程处于静止状态，相反，没有挂起的进程则处于活动状态。而且，处于静止状态的进程，只有通过“激活”动作，调用Active（）原语，才能转换成活动状态，调入内存。所以本题的答案是C。【例3】任何时刻总是让具有最高优先数的进程占用处理器，此时采用的进程调度算法是（ D）。A非抢占式的优先数调度算法 B、时间片轮转调度算法C、先来先服务调度算法 D、抢占式的优先数调度算法分析：“让具有最高优先数的进程占用处理器”，我们可以知道，采用的进程调度算法是优先数调度算法，但是我们还要进一步分析是抢占式的还是非抢占式的。“任何时刻总让”，通过这句话我们知道采用的是抢占式的，所以本题的答案是D。【例4】若P、V操作的信号量S初值为2，当前值为1，则表示有（ B）等待进程。A、0个 B、1个 C、2个 D、3个分析：信号量的初始值表示系统中资源的数目，每次的Wait操作意味着进程请求一个单位的资源，信号量进行减1的操作，当信号量小于0时，表示资源已分配完毕，进程自我阻塞。因此，如果信号量小于0，那么信号量的绝对值就代表当前阻塞进程的个数。所以本题的答案是B。【例5】发生死锁的必要条件有四个，要预防死锁的发生，可以破坏这四个必要条件，但破坏（ A）条件是不太实际的。A、互斥 B、请求和保 C、不剥夺 D、环路等待分析：预防死锁是指通过破坏死锁的某个必要条件来防止死锁的发生。四个必要条件中，后三个条件都可以被破坏，而第一个条件，即“互斥”条件，对某些像打印机这样的设备，可通过SPOOLing技术予以破坏，但其他资源，因受它们的固有特性的限制，该条件不仅不能被破坏，反而应加以保证。所以本题的答案是A。【例6】有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是1 至1m。分析：采用信号量机制实现m个进程对临界资源的互斥访问，信号量的初始值为1，也是该信号量的最大值。如果有进程要访问临界资源，那么执行Wait（）操作，信号量减1，考虑极端情况，m个进程都要求访问临界资源，信号量将执行m个减1操作，因此信号量的最小值为1m。所以本题的答案是1 至1m。【例7】在一个单处理机系统中，若有5个用户进程，且假设当前时刻为用户态，则处于就绪状态的用户进程最多有4、0个，最少有 个。分析：因为是单处理机系统，所以一个时刻只有一个进程处于执行状态，能占据处理机运行。所以，5个用户进程，处于就绪状态的进程最多有4个。最少时有0个就绪状态的进程，此时有两种情况：一、4个进程处于阻塞状态，1个处于执行状态，二、5个进程都处于阻塞状态。所以本题的答案是：4、0。【例8】在引入线程的操作系统中，独立调度和分派的基本单位是线程，资源分配的单位是进程。分析：引入线程的目的是为了进一步提高系统的并发程度，有效地提高系统的性能。在引入线程的操作系统中，线程是调度和分派的单位，而无论是否引入了线程，进程都是资源分配的单位。所以本题的答案是：线程、进程。【例9】试比较进程与程序的异同。答：进程和程序是紧密相关而又完全不同的概念。（1）每个进程实体中包含了程序段、数据段这两个部分，因此说进程和程序是紧密相关的。但从结构上看，进程实体中除了程序段和数据段外，还必须包含一个数据结构，即进程控制块PCB。（2）进程是程序的一次执行过程，因此是动态的；动态性还表现在进程由创建产生、由调度而执行、由撤销而消亡，即它具有一定的生命周期。而程序则只是一组指令的有序集合，并可永久地存放在某种介质上，其本身不具有动态的含义，因此是静态的。（3）多个进程实体可同时存放在内存中并发执行，其实这正是引入进程的目的。而程序的并发执行具有不可再现性，因此程序不能正确地并发执行。（4）进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而因程序不具有PCB，所以它是不可能在多道程序环境下独立运行的。（5）进程和程序不一一对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程；而一个进程也可以执行多个程序。【例10】什么是进程控制块？它有什么作用？答：进程控制块PCB是一个记录进程属性信息的数据结构，是进程实体的一部分，是操作系统中最重要的数据结构。当操作系统要调度某进程执行时，需要从该进程的PCB中查询其现行状态和优先级调度参数；在调度到某进程后，要根据其PCB中保存的处理机状态信息去设置和恢复进程运行的现场，并根据其PCB中的程序和数据的内存地址来找到其程序和数据；进程在执行过程中，当需要与其它进程通信时，也要访问其PCB；当进程因某种原因而暂停执行时，又需要将断点的现场信息保存在其PCB中。系统在建立进程的同时就建立了该进程的PCB，在撤销一个进程时也就撤销其PCB。由此可知，操作系统根据PCB来对并发执行的进程进行控制和管理，PCB是进程存在的惟一标志。【例11】什么是原语？答：原语是由若干条机器指令构成的一段程序，用以完成特定的功能。这段程序在执行期间不可分割。也就是说，原语的执行不能被中断，所以原语操作具有原子性。【例12】进程和线程的主要区别是什么？答：从调度、并发性、系统开销、拥有资源等方面来比较线程和进程：调度。在传统的操作系统中，独立调度、分派的基本单位是进程。而在引入线程的操作系统中，则把线程作为调度和分派的基本单位。并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。拥有资源。不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。一般地说，线程自己不拥有系统资源（也有一点必不可少的资源），但它可以访问其隶属进程的资源。系统开销。由于在创建、撤销或切换进程时，系统都要为之分配或回收资源，保存CPU现场。因此，操作系统所付出的开销将显著地大于在创建、撤销或切换线程时的开销。【例13】有4个进程P1，P2，P3，P4，它们进入就绪队列的先后次序为P1、P2、P3、P4，它们的优先数和需要的处理器时间如下表所示。假定这四个进程执行过程中不会发生等待事件，忽略进行调度等所花费的时间，从某个时刻开始进程调度，请回答下列问题：写出分别采用“先来先服务”调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及的平均等待时间；写出分别采用“非抢占式的优先数”（固定优先数）调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间；写出分别采用“时间片轮转”（时间片大小为5）调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间。进 程处理器时间优先数P183P261P3225P444分析：先来先服务算法是把处理机分配给最先进入就绪队列的进程，并且一个进程一旦分得了处理机，便一直执行下去，直到该进程完成或因发生某事件而阻塞时，才释放处理机；非抢占式优先数（优先级）调度算法将CPU分配给就绪队列中优先级最高的进程，就算进程在运行过程中，有更高优先数的进程进入，也要等待运行完毕或阻塞再释放处理机；时间片轮转算法中每个进程轮流运行一个时间片的时间，如果在一个时间片的时间内没有运行完毕，则进入就绪队列，等待下一个时间片继续运行。答：先来先服务算法选择进程的顺序依次为P1、P2、P3、P4。进程P1等待时间为0；进程P2等待时间为8；进程P3等待时间为8+6=14；进程P4等待时间为8+6+22=36。平均等待时间为（0+8+14+36）/4=14.5非抢占式的优先数算法选择进程的顺序依次为P3、P4、P1、P2。进程P1等待时间为4+22=26；进程P2等待时间为22+4+8=34；进程P3等待时间为0；进程P4等待时间为22。平均等待时间为（26+34+0+22）/4=20.5时间片轮转进程调度顺序为P1、P2、P3、P4、P1、P2、P3、P3、P3、P3。进程P1等待两次，时间为0+（5+5+4）=14；进程P2等待两次，时间为5+（5+4+3）=17；进程P3等待两次，时间为（5+5）+（4+3+1）=18；进程P4等待1次，时间为5+5+5=15。平均等待时间为（14+17+18+15）/4=16【例14】图3-3给出了四个进程合作完成某一任务的前驱图，试说明这四个进程的同步关系，并用信号量描述它。S1S2S3S4图3-3 四个合作进程的前驱图分析：图3-3说明任务启动后S1先执行，当S1结束后，S2、S3可以开始执行，S2、S3执行完成后，S4才可以开始执行。为了确保这一执行顺序，设4个同步信号量a、b、c、d分别表示S1S2、S1S3、S2S3、S2S4的前驱关系，初始值均为0。利用信号量的Wait（）和Signal（）操作来实现同步。答：。Main()Semaphore a=b=c=d=0;CobeginS1;signal(a);signal(b);wait(a);S2;signal(c);wait(b);S3;signal(d);wait(c);wait(d);S4;【例15】a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确管理以保证行驶安全。分析：此题是读者写着问题的变形。我们设置3个信号量S1、S2和Sab，分别用于从a点进入的车互斥访问共享变量ab（用于记录当前ab段上由a点进入的车辆的数量），从b点进入的车互斥访问共享变量ba（用于记录当前ab段上由b点进入的车辆的数量）和a、b点的车辆互斥进入ab段。3个信号量的初值分别为1、1和1，两个共享变量ab和ba的初值分别为0、0。答： Semaphore S1=1,S2=1,Sab=1;int ab=ba=0;void Pab ()while(1)wait(S1);if(ab=0)wait(Sab);ab=ab+1;signal(S1);车辆从a点驶向b点wait(S1);ab=ab-1;if(ab=0)signal(Sab);signal(S1);voidPb()while(1)wait(S2);if(ba=0)wait(Sab);ba=ba+1;signal(S2);车辆从b点驶向a点;wait(S2);ba=ba-1;if(ba=0)signal(Sab)signal(S2);main()cobeginPab ();Pba ();【例16】在公共汽车上，司机和售票员的工作流程如图3-4所示。为保证乘客的安全，司机和售票员应密切配合协调工作。请用信号量来实现司机与售票员之间的同步。司机启动车辆到站停车正常行车售票员关车门开车门售票图3-4 司机和售票员工作流程图分析：在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步。在本题中，设置两个信号量：S1、S2，S1表示是否允许司机启动汽车，其初值为0；S2表示是否允许售票员开门，其初值为0。答：则该问题描述如下：Semaphoere S1=S2=0;void Driver()while(1) wait(S1); 启动车辆； 正常行车；到站停车；signal(S2); void Busman()while(1) 关车门； signal（S1）； 售票； wait（S2）； 开车门； main() cobegin Driver(); Busman();【例17】用信号量集机制解决哲学家进餐问题。分析：哲学家进餐问题也是典型的同步问题，它由Dijkstra提出并解决。该问题的描述是，有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子继续思考。经分析可知，筷子是临界资源，在一段时间内只允许一个哲学家使用。因此，可以用一个信号量表示一支筷子，由五个信号量构成信号量数组。其描述如下：semaphore chopstick4=1,1,1,1,1;信号量集机制分为AND型信号量集机制和一般“信号量集”机制。AND同步机制的基本思想是，将进程在整个运行过程中所需要的所有临界资源一次性全部分配给进程，待该进程使用完后再一起释放。只要尚有一个资源未能分配给该进程，其他所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式，要么全部分配到进程，要么一个也不分配。避免死锁的发生。为此，在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait（Simultaneous Wait）。其定义如下：Swait(S1,S2,Sn)if (S11&Sn1) for (i=1;i=n;i+) Si-;elsePlace the process in the waiting queue associated with the Si found with Si1,and set the program count of this process to the beginning of Swait operation.Ssignal(S1,S2,Sn)for (i=1;i=n;i+)Si+;Remove all the process waiting in the queue associated with Si into the ready queue.在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1的操作，即每次只能获得或释放一个单位的临界资源。当一次需要n个某类资源时，便需要进行n次wait(s)操作，显然这是低效的。此外，在某些情况下，当资源数量低于某一下限值时便不予分配。因而，在每次分配之前都必须测试该资源的数量是否大于测试值t。基于上述两点可以对AND信号量机制进行扩充，形成一般化的“信号量集”机制。Swait操作可描述如下：Swait(S1,t1,d1,S2,t2,d2,Sn,tn,dn)if (S1t1&Sntn) for (i=1;i=n;i+) Si=Si-di;elsePlace the process in the waiting queue associated with the Si found with Siti,and set the program count of this process to the beginning of Swait operation.Ssignal(S1,t1,d1,S2,t2,d2,Sn,tn,dn) for (i=1;i=n;i+)Si=Si+di;Remove all the process waiting in the queue associated with Si into the ready queue. 答：用AND信号量机制可获得最简洁的解法：semaphore chopstick4=1,1,1,1,1;void process(int i)while (1) Swait(chopstick(i+1) mod 5, chopsticki);.eat;. Ssignal(chopstick(i+1) mod 5, chopsticki);.think;main()cobeginprocess(0); process(1);process(2);process(3);process(4);除此以外，还可以采用另外两种方法解决哲学家进餐问题：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。【例18】试用管程解决哲学家进餐问题。分析：我们认为哲学家可以处于这样三种状态之一：即进餐、饥饿和思考。相应地，引入数据结构： enum status thinking,hungry,eating enum status state5; 我们还为每一位哲学家设置一个条件变量self(i)，每当哲学家饥饿，但又不能获得进餐所需的筷子时，他可以执行self(i).wait操作来推迟自己进餐。条件变量可描述为：condition self5;答：则用于解决哲学家进餐问题的管程描述如下：monitor dining-philosophersenum status thinking,hungry,eating;enum status state5;condition self5; entry pickup(int i) statei=hungry; test(i); if (stateieating)self(i).waitentry putdown(int i) statei=thinking;test(i-1 mod 5);test(i+1 mod 5);test(int i); if (statei-1 mod 5eating & statek=hungry & statei+1 mod 5eating)statei=eating;selfi.signal;for(i=0;i=4;i+)statei=thinking;【例19】产生死锁的四个必要条件是什么？答：互斥条件。进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占有。请求和保持条件。当进程因请求资源而阻塞时，对已获得的资源保持不放。不剥夺条件。进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。环路等待条件。在发生死锁时，必然存在一个进程资源的环形链。【例20】为什么说采用有序资源分配法不会产生死锁？答：假设系统中有m类资源，n个进程，分别用R1，R2，Rm（1，2，m可看作资源编号）和P1，P2，Pn表示。根据有序资源分配法可知，进程申请资源时必须按照资源编号的升序申请，即任何进程在占有了Ri类资源后，再申请的资源Rj的编号j一定大于I。因此再任一时刻，系统中至少存在一个进程Pk，它占有了较高的编号的资源Rh，且它继续请求的资源必然是空闲的，因而Pk可以一直向前推进直至完成，当Pk运行完成后即会释放它占有的资源；在Pk完成后，剩下的进程集合中同样会存在一个进程，它占有了较高编号的资源，且它继续请求的资源必然是空闲的，因而它可以一直向前推进直至完成；以次类推，所有进程均可运行完成，故不会发生死锁。【例21】不安全状态是否必然导致系统进入死锁状态？答：不安全状态不一定导致系统进入死锁状态。因为，安全性检查中使用的向量Max是进程执行前提供的，而在实际运行过程中，一进程需要的最大资源量可能小于Max，如一进程对应的程序中有一段进行错误处理的代码，其中需要n个A种资源，若该进程在运行过程中没有碰到相应的错误而不需要调用该段错误处理代码，则它实际上将完全不会请求这n个A种资源。【例22】n个进程共享某种资源R，该资源共有m个，每个进程一次一个地申请或释放资源。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于mn，试证明在这个系统中不可能发生死锁。答：设max(i)表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：max(i)+max(n)=need(i)+need(n)+alloc(i)+alloc(n)m+n如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即alloc(1)+alloc(n)=m另一方面所有的进程将陷入无限等待状态，由上述两式可得：need(i)+need(n)就绪态 B、运行态-等态待C、就绪态-运行态 D、等待态-就绪态8已经获得了除( C)以外的所有运行所需资源的进程处于就绪状态。A、存储器 B、打印机 C、CPU D、磁盘空间9下列进程变化状态中，（C ）变化是不可能发生的。A、运行-就绪B、运行-阻塞C、阻塞-运行C、阻塞-就绪10时间片轮转调度算法经常用于（C ）。A、单用户操作系统 B、实时系统 C、分时操作系统 D、批处理系统 11抢占式的优先数调度算法在（ D）中很有用。A、网络操作系统 B、分布式系统C、批处理系统 D、实时系统12系统可把等待资源的进程组织成等待队列，这样的等待队列有（ D）。A、0个 B、1个 C、2个 D、1个或多个13进程调度的关键问题是（ B）A、时间片大小 B、进程调度算法C、CPU速度 D、内存空间利用率14一次中断后可能引起若干个进程状态的变化，因此中断处理后，由（A ）来决定哪个进程可占用处理器。A、进程调度 B、页面调度 C、移臂调度 D、作业调度15采用时间片轮转调度算法是为了（A ）A、多个终端用户能得到系统的及时响应B、先来先服务C、需CPU最短的进程先执行D、优先级高的进程能得到及时调度16下面的叙述中正确的是（D ）。A、操作系统的一个重要概念是进程，因此不同进程所执行的代码也一定不同B、为了避免发生进程死锁，各进程只能逐个申请资源C、操作系统用PCB管理进程，用户进程可以从PCB中读出与本身运行状况有关的信息D、进程同步是指某些进程之间在逻辑上的相互制约关系17在操作系统中，进程是一个具有独立运行功能的程序在某个数据集合上的一次（B ）。A、等待过程 B、运行过程 C、单独过程 D、关联过程18多道程序环境下，操作系统分配资源以（ D）为基本单位。A、程序 B、指令 C、作业 D、进程19两个进程合作完成一个任务。在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的（A ）。A、同步 B、执行 C、互斥 D、调度20为了进行进程协调，进程之间应当具有一定的联系，这种联系通常采用进程间交换数据的方式进行，这种方式称为（C ）。A、进程互斥B、进程同步C、进程通信D、进程制约21除了进程竞争资源，因为资源不足可能出现死锁以外，不适当的（C ）也可能产生死锁。A、进程优先权 B、资源的线性分配C、进程推进顺序 D、分配队列优先权22除了可以采用资源剥夺法解除死锁，还可以采用（ C）方法解除死锁。A、修改信号量B、拒绝分配新的资源C、撤销进程D、执行并行操作23资源的按序分配策略可以破坏（D ）条件。A、互斥B、请求和保持C、不剥夺D、环路等待24在（ C）的情况下，系统出现死锁。A、计算机系统发生了重大故障B、有多个阻塞的进程存在C、若干个进程因竞争资源而无休止地相互等待他方释放已占有的资源 D、资源数大大小于进程数或进程同时申请的资源数大大超过资源总数25某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是（B ）。A、9B、10 C、11D、1226银行家算法是一种（B ）算法。A、解除死锁 B、避免死锁 C、预防死锁 D、检测死锁27（A ）优先权是在创建进程的时候确定的，确定之后在整个进程运行期间不再改变。A、静态 B、短作业 C、动态 D、高响应比28在下列解决死锁的方法中，属于死锁预防策略的是（B ）。A、银行家算法B、资源有序分配法C、死锁检测法D、资源分配图化简法1DE 2.ABDE 3.DB 4.ABD 5.CE 6.BE 7.CD 8.ABD 9.BC 10.CD 11.ABCDE 12.BD 13.AB 14.AC 15.ACD二、多项选择题1关于先来先服务进程调度算法说法正确的是（DE ）。A、算法效率高 B、使进程等待分配处理器的平均时间缩短C、实现复杂 D、有时使进程等待分配处理器的平均时间较长E、系统效率低2优先数进程调度算法中优先数的确定是恰当得是（ ABDE）。A、系统进程优先数高于用户进程B、交互式用户进程优先数高于批处理进程C、使用中央处理器频繁的进程的优先数高D、重要算题的进程优先数高E、频繁输入输出的进程优先数高3属于优先数进程调度算法中动态优先数确定原则的是（