2011计算机考研操作系统资料.doc

（清华大学1998年试题）（判断题）判断对与错：进程由进程控制块和数据集以及对该数据集进行操作的程序组成。进程上下文是进程执行活动全过程的静态描述。并发是并行的不同描述，其原理相同。提示： 本题考核的是进程的结构、进程上下文，及进程的特征。涉及的内容有： 进程的结构由PCB、数据集和程序代码组成。 进程上下文是进程执行活动全过程的描述，主要包括系统中与执行该进程有关的各种寄存器的值，比如数据寄存器、地址寄存器和程序状态字（PSW），还有程序段经编译后形成的机器指令集、数据集及各种堆栈值和PCB结构等。 程序的并发执行是指，一组在逻辑上互相独立的程序或程序段在执行时间上相互重叠，即一个程序段尚未结束，另一个程序段的执行已经开始。应当注意，并发性和并行性是决然不同的。程序的并行执行是指一组程序同时按独立的、异步的速度执行；而并发性是指程序执行时间上的重叠，不等于程序同时运行。【第四题】（南京大学1997年试题）（论述题）操作系统中为什么要引入进程的概念？为了实现并发进程间的合作和协调工作，以及保证系统的安全，操作系统在进程管理方面应做哪些工作？提示： 本题考核进程的一般概念。涉及的内容有： 让程序并发方式执行，能够充分利用系统资源，提高系统的处理能力。但由于系统资源是有限的，诸多并发执行的程序在共享资源的同时，必将引起资源的竞争。此时如果不制定特定的规则和方法，必将使这种共享和竞争呈现无序状态。程序的执行结果也将不可避免地失去封闭性和可再现性，从而得不出正确的、预期的结果。正因为如此，多道程序设计中需要引入一个能描述程序执行过程，且能用来共享资源的基本单位那就是“进程”。因此，进程可以被定义为“可并发执行的程序在一个数据集合的执行过程”。 操作系统对进程管理方面应做如下工作： 进程控制。包括进程创建与撤消，进程在运行过程中的状态转换，以及实现对进程控制块的维护等操作。 进程调度。操作系统必须按一定算法在就绪进程中选择一个进程，把处理机分配给它，使它顺利地投入运行。为此，进程调度应具有CPU现场信息的保护和恢复功能。 进程同步。对于一组合作的进程，它们的推进速度应当受到某种约束，以便协调一致地向前推进。因此系统必须设立同步控制机制，对所有进程的运行进行协调。协调方式包括进程互斥方式和进程同步方式。 进程通信。在多道程序环境下，进程之间往往要互相发送一些信息。操作系统应提供有关的通信调用和通信规范，保证实现这些进程之间的信息交换。进程之间的通信种类是很多的，控制机制也有很多。（西安电子科技大学2001年试题）1 运行就绪队列等待IO传输队列某系统中进程有如下的状态变化图：请回答下列问题：（1）该系统采用了怎样的进程调度算法？说明理由。（2）把图中发生-的状态变化原因填入下表中。变化变化原因【参考答案】（1）该系统采用的是“时间片轮转调度算法”。该调度算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占用处理器，但规定只能使用一个“时间片”。如果一个时间片用完，进程工作尚未结束，则它也必须让出处理器而被重新排到就绪队列的末尾，等待再次运行，当再次轮到运行时，重新开始使用一个新的时间片。这样，就绪队列中的进程就依次轮流地占用处理器运行。（2）变化变化原因进程到达就绪队列头，从就绪状态变为运行状态。运行的时间片到，从运行状态变为就绪状态，进入就绪队列末尾排队，等待调度。运行过程中，进程申请IO，从运行状态变为等待状态，进入等待队列等待IO完成。进程所申请的IO完成，进入就绪队列末尾排队，等待调度。（南京大学2001年试题）_可能会引起处理机从一个进程转到另一个进程。（A）一个进程从运行状态变为等待状态（B）一个进程从运行状态变为就绪状态（C）一个就绪状态进程的优先级降低 （D）一个进程运行完成而撤离系统（E）一个就绪状态进程的优先级升高【答案】ABDE【第一题】（青岛大学2002年试题） 青岛崂山有一处景点称作上清宫，游客在宫内游玩之后可以在宫门口免费搭乘轿车游览崂山的风景区，游览完毕再返回宫门口（如下图所示）。已知风景区内的轿车总量为M辆，游客总数为N，约定：（1）每辆轿车限乘一位游客；（2）如果有空闲的轿车，应当允许想游览的游客乘坐；（3）无空闲轿车时，游客只能排队等待；（4）若没有想游览的游客，空闲的轿车也要等待。试利用P、V操作实现N个游客进程与M辆轿车进程的同步操作过程。注意提示：本题中游客乘坐轿车游览风景区是免费的，因此程序设计中不需要考虑付费环节。分析： 本题考核的要点是进程同步问题。我们定义了3个信号量car_avail，car_taken和take_off，实现游客进程与轿车进程的同步操作。Begin Semaphore：car_avail，car_taken，take_off；car_avail:=0; car_taken:=0; take_off:=0;cobeginprocess passenger()begin逛上清宫；P(car_avail);Take_in_car();/ 游客上车V(car_taken);P(finished);Take_off_car();/ 游客下车V(that_off);endprocess car()beginrepeat V(car_avail);P(car_taken);Take_a_visit();/ 游览崂山风景区；V(finished);P(that_off);Until false;endcoendend.【第二题】（西安电子科技大学2000年试题） 有一个理发师，一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅子上睡觉；当一个顾客到来时，唤醒理发师进行理发。如果理发师正在理发时又有新顾客到来，有空椅子可坐，他就坐下来等，如果没有空椅子，就立即离开。为理发师和顾客各编一段程序描述他们的行为，要求不能带有竞争条件。分析： 这是一个比较复杂的进程同步问题。需要设计两个进程： 顾客进程Customer（） 理发师进程Barber（） 特定义两个信号量customers和barbers实现进程的同步，并定义信号量S实现进程的互斥。程序代码如下：Begin/ 定义信号量并初始化int CHAIRS:= n /为等候的顾客准备的椅子数semaphore： customers=0;semaphore： barbers=0;semaphore： cut=0;semaphore： finish=0;semaphore： mutex=1; /用于互斥的信号量int waiting=0;Cobegin/定义并发进程Process Customer()P(mutex);if(waitingCHAIRS) then V(mutex)/没有空椅子，离开else waiting=waiting+1;V(mutex);V(customers);/ 唤醒理发师SIT_ON_chair();/ 坐在椅子上等候P(barbers);/ 等待理发召唤Stand_up();/ 从椅子上起身 P(mutex);waiiting=waiting-1;V(mutex);SIT_ON_cut_chair();/ 坐在理发椅上V(cut);/ 告诉理发师可以开始理发P(finish);/ 等待理发完成void barber() while(T) P(customers);/ 等待顾客到来Clear_cut_chair();/ 整理一下理发椅子V(barbers);/ 召唤一个顾客P(cut);/ 等待顾客就座CUT_hair();/ 理发V(finish);/ 告诉顾客已结束Coend/ 并发进程的定义结束End.讨论：注意 代码中带阴影的部分可以从顾客进程移到理发师进程中处理。 该算法中没有涉及顾客理发后的付款过程。【第三题】（中国科学技术大学1998年试题） （程序阅读）何谓临界区？下面给出的实现两个进程互斥的算法是安全的吗？为什么？#define TRUE;#define FALSE;int flag2;flag0=flag1=FALSE;enter-crtsec(i)int i; WHILE(flag1-i); flagi=TRUE;leave-crtsec(i)int i; flagi=FLASE;process I:/*i=0 OR I=1*/ enter-crtsec (i);/*进入临界区*/ IN CRTICAL SECTION Leave-crtsec(i);/*离开临界区*/ 提示： 本题的考核要点是临界资源访问。 临界资源指的是一次仅允许一个进程使用的资源。在进程中用于访问临界资源的程序段称为临界区（CRTICAL SECTION）。 由于系统中的各进程在逻辑上是独立的，因此它们各自以独立的速度向前推进。然而它们又都需要系统中的资源，当这些资源为临界资源时，就产生了互斥访问的问题。临界区的概念由此产生。 本题给出的算法是不安全的。因为，在进入临界区前执行的过程enter-crtsec（）和退出临界区后执行的过程Leave-crtsec（）都不是原子操作。因而不能避免两个或更多进程进入临界区。【第四题】（南京大学2000年试题） 为了让用户进程互斥地进入临界区，可以把整个临界区实现成不可中断的过程，即让用户具有屏蔽所有中断的能力。每当用户程序进入临界区的时候，屏蔽所有中断。当出了临界区的时候，再开放所有中断。你认为这种方法有什么缺点。提示： 本题考核的要点是临界资源的使用。为了达到互斥使用临界资源的目的，将访问临界资源的程序放在中断被屏蔽的状态下运行。这样做虽然可以达到互斥访问的目的，但并不可取。因为，一般情况下，进程对临界资源的访问时间都比较长，比如访问内存中的一个缓冲区环，就需要判断环内是否已满或为空，然后对当前缓冲区进行访问，最后再移动环上的指针。 如果让中断屏蔽时间拖的太长，有可能错过对某些特别紧迫的中断信号的响应，以致丧失了最佳处理时机。【第五题】（中国科学院计算技术研究所1996年试题） Dijkstra提出的银行家算法的主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？提示： 本题的考核要点是银行家（Banker）算法。涉及的内容有： 银行家算法是一种解决死锁问题的方法。该算法模拟了银行在经营中的贷款策略。当用户提出资源请求时，先计算该次分配后是否会导致系统不安全，即是否存在一种顺序，使得所有的进程都能执行结束。若安全则将资源分配给用户，否则拒绝分配。 从理论上说，该算法有是很有意义的，但在实际实施中却有一定难度。因为算法所假设的一些条件太多，诸如，让用户提交作业需求资源的最大数目并不容易，算法本身涉及的数据结构太复杂等。 银行家算法比较耗时，而每当一个用户提出资源请求时，都需要调用银行家算法测算一遍，无形中使系统的开销加大，降低了处理机的利用率。注意 注意：银行家算法用于资源分配之前，检测系统是否安全。该算法能够解决实际中的死锁问题，但系统开销较大。【第六题】（西安理工大学2000年试题） （程序设计题）设有6个进程P1、P2、P3、P4、P5、P6，它们有如图所示的并发关系。试用P、V操作实现这些进程间的同步。提示： 本题考核的是用P、V操作实现进程间同步的问题。下面设计了4个信号量分别用于进程之间的同步，它们的初始值为0。当进程P1尚未得到运行的话，其他进程只能被阻塞等待。算法可描述如下：BEGINSemaphore：s1,s2,s3.s4;s1:=s2:=s3:=s4:=0COBEGINProcess P1:Begindo all work;V(s1);V(s1);EndProcess P2:BeginP(s1)do all work;V(s2);EndProcess P3:BeginP(s1);do all work;V(s3);EndProcess P4:BeginP(s2);do all work;V(s4);EndProcess P5:BeginP(s3);do all work;V(s4);EndProcess P6:BeginP(s4);P(s4);do all work;EndCOENDEND【第七题】（清华大学1995年试题） （问答题）使用P、V原语和加锁法都可以实现并发进程间的互斥，问： （1）P、V原语和加锁法实现互斥时有何导同？ （2）使用加锁法实现互斥时，有可能在进程使用临界区时造成不公平现象，即某个进程一直占用临界区，其他进程永远无法使用。找出一个不公平现象的例子，并分析产生不公平现象的原因。提示： 本题的考核要点是P、V原语和加锁法的原理。 P、V操作与加锁法都是实现进程互斥的方法。它们都是根据一个变量的值来判断当前是否可以进入临界区。它们的不同点如下： P、V操作是用原语来实现的，即P、V操作在屏蔽中断的环境中执行。而加锁法不具备这个特点。 加锁法对系统的运行性能有较大影响。比如，对锁定位的循环测试将损耗大量的CPU时间。 用P、V操作实现进程互斥时，未进入临界区的进程只能被阻塞等待，而加锁法则相反。 以下进程会产生不公平的现象。Process P1()begin L1: lock(keys)；“访问临界资源”；unlock(keys)；Goto L1；End.ProcessP2()Begin L2: lock(keys)；“访问临界资源”；unlock(keys)；Goto L2 ；End. 假设进程P1首先进入临界区。那么在进程P1执行unlock（keys）过程之前，keys的值为0，进程P2没有进入临界区的机会。然而，当进程P1执行完unlock（keys）过程后keys的值变为1，紧接着是一条转向语句，又将再次进入临界区。 这样一来，只有当进程P1执行完unlock（keys）过程之后的一瞬间内发生了进程调度，进程P2才可能获得处理机。因此说，进程P2获得执行的机会是相当小的。故进程P2将处于长期“饥饿”状态。【第八题】（北京大学1997年试题） 某高校计算机系开设有网络课并安排了上机实习，假设机房共有2m台机器，有2n 名学生选该课，规定： 每两个学生组成一组，各占一台机器，协同完成上机实习； 只有一组的两个学生到齐，并且此时机房有空闲机器时，该组学生才能进入机房； 上机实习由一名教师检查，检查完毕，一组学生同时离开机房。 试用P、V操作模拟上机实习过程。提示： 本题中考核的主要内容是进程互斥与同步问题。为了保证系统的控制流程，专门设一个Monitor进程，用于控制学生进入机房及计算机的分配使用。从题目本身来看，虽然没有明确指出这一进程，但实际上这一进程应当是存在的。 上机实习过程可描述如下：BEGINSemaphore： student, computer ,enter, finish, check;studen:=0;computer:=2m;enter:=0;finish:=0:chech:=0;COBEGINProcess Procedure Student()beginV(student):/ 表示有学生到达P(computer):/ 等待获取一台计算机P(enter);/ 等待进入许可DO it with partner();V(finish);/ 实习完成P(check);/ 等待老师检查V(computer):/ 释放计算机资源endProcess Procedure Teacher()beginL1:P(finished);/ 等待学生实习完成P(finished);/ 等待另一学生实习完成check the work();V(check);/ 表示检查完成V(check);/ 表示检查完成goto L1;endProcess Procedure Monitor()beginL2:P(student);/ 等待学生到达P(student);/ 等待另一学生到达V(enter);/ 允许学生进入V(enter);/ 允许学生进入endCoendEND【第九题】（西北工业大学2000年试题） （设计题）从读卡机上读进N张卡片，然后复制一份，要求复制出来的卡片与读进来的卡片完全一致。这一工作由三个进程get，copy和put以及两个缓冲区buffer1和 buffer2 完成。进程get的功能是把一张卡片上的信息从读卡机上读进buffer1；进程copy的功能是把buffer1中的信息复制到buffer2；进程put的功能是取出buffer2中的信息并从行式打印机上打印输出。 试用P、V操作完成这三个进程间的尽可能并发正确运行的关系（用程序或框图表示），并指明信号量的作用及初值。提示： 设计6个信号量S1，S2，Sn1，Sn2，Sm1，Sm2。其中： S1和S2为互斥信号量，初值为1，分别用于对buffer1和buffer2的互斥访问； Sn1和Sn2为同步信号量，初值为1，分别表示buffer1和buffer2为空闲，可以存放一张卡片的信息； Sm1和Sm2为同步信号量，初值为0，分别表示buffer1和buffer2中的信息还没有被取用（或已被取用了）。 用P、V操作完成这三个并发进程间能正确运行的程序如下：BEGINsemaphore: S1,S2, Sn1，Sn2, Sm1，Sm2;S1=S2=1;/ buffer1和buffer2的互斥信号量Sn1=Sn2=1;/ 同步信号量Sm1=Sm2=0;CobeginProcess produce get()BeginL1: 从读卡机读进一张卡片信息；P(Sn1);P(S1);将信息放入buffer1;V(Sm1);V(S1);Goto L1EndProcess produce copy()