1.中断与程序并发之间的关系是什么？解析：本题考查中断的作用。答案：中断是程序并发的前提条件。如果没有中断，操作系统不能获得系统控制权，无法按调度算法对处理机进行重新分配，一个程序将一直运行到结束而不会被打断。2.在信号量S上执行P、V操作时，S的值发生变化，当S>0，S=0，S<0时，它们的物理意义是什么？P（S）、V（S）的物理意义又是什么？解析：对于信号量的操作只能通过PV操作来进行，用来改变资源的可用情况。答案：S>0表示有S个资源可用；S=0表示无资源可用；S<0则|S| 表示S等待队列中的进程个数。信号量的初值应该大于或等于0。P(S):表示申请一个资源，若申请后s<0,表示已无资源可用，需要将自己阻塞起来。V(S):表示释放一个资源，若释放后s<=0,表示等待队列上有等待进程，需要将第一个等待进程唤醒。PV原语小结PV原语通过操作信号量来处理进程间的同步与互斥的问题。其核心就是一段不可分割不可中断的程序。信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语（P、V原语）来访问。初始化可指定一个非负整数，即空闲资源总数。P原语：P是荷兰语Proberen（测试）的首字母。为阻塞原语，负责把当前进程由运行状态转换为阻塞状态，直到另外一个进程唤醒它。操作为：申请一个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞；V原语：V是荷兰语Verhogen（增加）的首字母。为唤醒原语，负责把一个被阻塞的进程唤醒，它有一个参数表，存放着等待被唤醒的进程信息。操作为：释放一个被占用的资源（把信号量加1），如果发现有被阻塞的进程，则选择一个唤醒之。具体PV原语对信号量的操作可以分为三种情况：1）把信号量视为一个加锁标志位，实现对一个共享变量的互斥访问。实现过程：P(mutex); // mutex的初始值为1访问该共享数据V(mutex);非临界区2）把信号量视为是某种类型的共享资源的剩余个数，实现对一类共享资源的访问。实现过程：P(resource); // resource的初始值为该资源的个数N使用该资源；V(resource);非临界区3）把信号量作为进程间的同步工具实现过程：临界区C1；P(S);V(S); 临界区C2；利用PV操作实现互斥互斥信号量是根据临界资源的类型设置的。有几种类型的临界资源就设置几个互斥信号量。它代表该类临界资源的数量，或表示是否可用，其初值一般为“1”。
3.在一个只允许单向行驶的十字路口，分别有若干由东向西，由南向北的车辆在等待通过十字路口。为了安全，每次只允许一辆车通过。当有车辆通过时其它车辆必须等候，当无车辆在路口行驶时则允许一辆车通过。请用PV操作实现保证十字路口安全行驶的自动管理系统。解析：设置信号量s：表示临界资源十字路口，s初值为1 。答案：int s=1;main(){ pew(); psn();}pew() psn(){ {p(s); p(s);由东向西通过十字路口；由南向北通过十字路口；v(s); v(s);}}利用PV操作实现同步同步信号量是根据进程的数量设置的。一般情况下，有几个进程就设置几个同步信号量，表示该进程是否可以执行，或表示该进程是否执行结束。其初值一般为“0”。4.桌上有一个空盘子，只允许放一个水果。爸爸可以向盘中放苹果，也可以向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时，一次只能放一只水果，请用PV操作实现爸爸、儿子、女儿3个并发进程的同步。解析：设置信号量sp：表示盘子是否为空，sp初值为1；设置信号量sa：表示盘子里是否有苹果供女儿吃，sa初值为0；设置信号量so：表示盘子里是否有桔子供儿子吃，so初值为0。答案：int sp=1，sa=0，so=0; main(){father(); son();daughter();}father() son()daughter（）{ while(1) {while(1){while(1){p(sp); {p(so); {p(sa);将水果放入盘中；从盘中取出桔子；从盘中取出苹果；if (放入的是桔子) v(sp); v(sp);v(so); 吃桔子；吃苹果；else v(sa); }}} }}同步与互斥的解题思路①分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。②对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。③对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程
是否已经结束。④在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒，必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作，但V操作的顺序没有严格要求。5.对于下述处理机调度算法分别画出进程状态转换图。(1) 时间片轮转算法;(2) 可抢占处理机的优先数调度算法;(3) 不可抢占处理机的优先数调度算法。解析：首先要了解进程状态转换关系，接下来按照不同的处理机调度算法画出各自的进程状态转换图。答案：如图2.1所示。(1) 时间片轮转算法(2) 可抢占处理机的优先数调度算法(3) 不可抢占处理机的优先数调度算法7.在一个两道的批处理操作系统中，有6个作业进入系统，它们的进入时刻、估计运行时间和优先级如下表所示:表2-3作业号进入时刻估计运行时间优先级JOB18：0090分钟5JOB28：1030分钟6JOB38：3020分钟3JOB48：5025分钟8JOB59：2010分钟2JOB69：405分钟4系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出内存,但当有新的作业投入运行时，系统是可以按照优先级（优先级越大表示优先级越高）进行进程调度。（1）试给出各个作业的运行时间序列。（例如：JOB1：8：00-8：30，9：10-9：20，...）（2）试计算出作业的平均周转时间。解析：首先经过分析，系统同时只能容纳两道作业，采用短作业优先作业调度算法，抢占调度方式，优先权进程调度算法，接下来分析运行序列及计算平均周转时间。
答案：（1）各个作业的运行时间序列为：JOB1 8：00-8：10（JOB2抢占），8：40-10：00（此时系统中只有JOB1和JOB3）JOB2 8：10-8：40（运行完毕后JOB3进入内存）JOB3 10：05-10：25（JOB3比JOB5的优先级高，所以先运行）JOB4 10：25-10：50（JOB3运行完毕之后，JOB4进入内存，优先级比JOB5高，所以先运行）JOB5 10：50-11：00（JOB6运行完毕后，选择JOB4，JOB5种运行时间最短的JOB5进入内存）JOB6 10：00-10：05（JOB1运行完毕之后由于JOB6的运行时间在处于后备队列中的JOB4，JOB5，JOB6中最短，所以先进入内存，与JOB3同处于内存，并且JOB6的优先级高，先运行）（2）根据公式计算：周转时间=完成时间-进入时间平均周转时间=周转时间之和/nJOB1周转时间=10：00-8：00=120minJOB2周转时间=8：40-8：10=30minJOB3周转时间=10：25-8：30=115minJOB4周转时间=10：50-8：50=120minJOB5周转时间=11：00-9：20=100minJOB6周转时间=10：05-9：40=25min平均周转时间=（120+30+115+120+100+25）m/6=510m/6=85min8.假定某系统有同类资源m个，可被n个进程共享，请问每个进程最多可以申请多少个资源能保证系统一定不会发生死锁？解析：本题要求限制进程申请的资源数来确保系统的安全，若要使系统不发生死锁则应保证系统处于“安全状态”，即要保证所有的进程能在有限的时间里得到所需的资源。我们可以假设允许每个进程最多可以申请x个资源（1=＜x=＜m）那么，最坏的情况是每个进程都已得到了（x—1）个资源，现均要申请最后一个资源。因而，只要系统至少还有一个资源就可使其中一个或几个进程得到所需的全部资源，在它们执行结束后归还的资源又可供其它进程使用，故不可能发生死锁。也就是说，只要不等式n（x—1）＋1=＜m成立，则系统一定不会发生死锁。扩展：在实际的系统中每个进程需要多少个资源是由进程自己决定的，不能人为地去限制它。但是，如果在设计系统时能预计到并发进程申请资源量的情况，则可用上述方法来预测系统的安全性。只要系统拥有的资源数、可能并发执行的进程数、每个进程所需资源量之间的关系符合上述关系，则不必受资源分配策略的限制，只要有空闲资源就可分配给申请者，系统不会出现死锁现象。答案：假设每个进程最多可以申请X个资源，为保证系统不发生死锁，应该使下列不等式成立：n（x-1）＋1=＜m解上述不等式nx=＜n＋m-1x=＜1＋(m-1)/n于是可得到：当m=＜n时x=1当m＞n时x=1+(m-1)/n9设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共有3个，每个进程至少请求一个资源，它们所需资源最大量的总和为X，则发生死锁的必要条件是什么？
解析：本题主要考察操作系统中死锁的概念。根据死锁的定义，若一个进程集合中的每一个进程都在等待只能有本集合中的另一个进程才能引发的事件，则视这种情况为死锁。因此要发生死锁的必要条件就是这三个进程都因申请不到资源而发生死锁。现在，我们假设3个进程需要该类资源数分别为x，y，z个，因此有x+y+z=X。假设没有发生死锁，即当每个进程都申请了部分资源，还需最后一个资源，而此时系统总已经没有剩余资源了，即满足为（x-1）+(y-1)+(z-1)>=3X=x+y+z>=6因此，如果发生死锁，则X>=6,这就是死锁发生的必要条件。答案：X>=6是死锁发生的必要条件。10.有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答：(1)若对资源分配不加限制，会发生什么情况?为什么?(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么?解析：此题考查死锁的概念，以及如何可以预防死锁。答案：(1)可能会发生死锁例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待，这是循环等待。(或进程在等待新源时均不释放已占资源)(2)可有几种答案：A.采用静态分配。由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。或B.采用按序分配。不会出现循环等待资源现象。或C.采用银行家算法。因为在分配时，保证了系统处于安全状态。11.在分页存储管理系统中，逻辑地址的长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块10、12、14中，则相应的物理地址是多少？解析：在分页存储管理系统中进行地址转换时，地址变换机构将自动将逻辑地址转化为页号和页内地址，如果页号大于页表长度，则产生越界中断；否则便以页号为索引检索页表，从中得到对应的页号，并将块号和页内位移分别送入物理地址寄存器的块号和块内位移字段中，形成物理地址。答案：将题目所给的逻辑地址转换成二进制表示为：0010111101101010。因为逻辑地址长度为16位，页面大小为4096字节，因此在16位的逻辑地址中，前4位表示页号，后12位表示页内地址。即：0010 111101101010页号页内位移由此可知逻辑地址2F6AH的页号为2，小于页表长度3，没有越界，由题意知，该页存放在第14个物理块中，用十六进制表示块号为E，故物理地址为EF6A。12.假定某操作系统存储器采用页式存储管理．页的大小为64字节，假定某个进程的代码段长度为702个字节，页表如表2-8左表所示，该进程在联想存储器中的页表如表2-8右表所示。
表2-8页表及联想寄存器中的页表若该进程有如下的访问序列：其逻辑地址为八进制的105、217、567、1120、2500。试问给定的这些地址能否进行转换？若能，请说明地址转换过程及相应的物理地址。若不能，则说明理由。解答：页面大小64，页内位移是6位，该进程所需页数720／64=11页，编导为0~10。逻辑地址为八进制，因此地址数的右边两位即为页内位移d，其余左边高位为页号p。(105)八进制：P=1，d=5，得内存块号为F1，页内位移为5；(217)八进制：P=2，d=17，得内存块号为F2，页内位移为17；以上两地址均在联想寄存器中可找到，无需到内存中查找页表。(567)八进制；P=5，d；67，该页号不在联想寄存器中，需到主存页表项寻找块号，查找页表得内存块号为F5，页内位移为67；(1120)八进制：p=11；(2500)八进制：P=25；以上两地址页号均越界，进程代码段所占页号最大为10，不可转换。13.有一个请求分页存储系统，测得CPU和磁盘的利用率如下，试指出每种情况下存在的问题及可采取的措施：（1）CPU利用率为13%，磁盘利用率为97%；（2）CPU利用率为87%，磁盘利用率为3%；（3）CPU利用率为13%，磁盘利用率为3%。解析：CPU的利用率是指整个运行时间里，CPU有多少时间是真正处理用户的数据运算。答案：（1）这种情况表示系统在进行频繁的置换，以致大部分时间被花在页面置换上，系统可能出现抖动，可暂停部分进程运行；（2）这种情况下，系统运行正常，CPU利用率已相当高，但对换盘的利用率却相当低，这表明运行进程的缺页率很低，可增加运行进程数以进一步提高资源利用率；（3）这种情况下，处理器和设备利用率均很低，表示内存中可运行的程序数不足，可增加并发运行的进程数来提高CPU的利用率。14.设某作业占有5个页面，如果在主存中只允许装入4个工作页面，作业运行时，实际访问页面的顺序是4，3，2，1，4，3，5，4，3，2，1，5。试用FIFO与LRU页面置换算法，求出缺页中断次数和缺页率。(假设开始时所有的页面均不在主存) 解析：FIFO算法基本思想：当发生缺页中断需要置换时，总是淘汰那些驻留在主存时间最长的页面，即先进入主存的页面先被淘汰。LRU算法基本思想：当发生缺页中断需要置换时，选择在一段时间最久未用的页予以淘汰。答案：页号块号0F01F12F23F34F45F56F67F78F89F910F10页号块号0F01F12F23F34F4
FIFO算法页面淘汰序列如表2-10。表2-10FIFO算法页面淘汰序列页面走向432143543215M4+3+42+341+2341234123④5+12③4+51②3+45①2+34⑤1+23④5+123F++++++++++上表中，M行表示在主存中的页面号，其中标有“+”的表示新调入主存的页面，在M行总行按调入的顺序排列，加圆圈的数字表示在下一时刻被淘汰，F行表示是否引起缺页中断。缺页次数F=10，缺页率f=10/12≈83%LRU算法页面淘汰序列如表2-11。表2-11LRU算法页面淘汰序列页面走向432143543215M4+3+42+341+2344123341②5+341453134512+34⑤1+23④5+123F++++++++缺页次数F=8，缺页率f=8/12≈67%15.一进程已分配到4个页块。如表2-12所示（所有数宇都为10进制数，且以0开始）。表2-12进程的页表页号页块装入时间最近访问时间访问位修改位2060161011113016000022616210332016311当进程访问第4页时，产生缺页中断，请分别用FIFO（先进先出）、LRU（最近最少使用）、NRU（最近不用）算法，决定缺页中断服务程序选择换出的页面。解析：FIFO算法：选择最先进入主存的页面被置换。最近最久未使用算法LRU：选择内存中最久未使用的页面被置换。最不经常使用算法LFU：选择到当前时间为止被访问次数最少的页面被置换。最近没有使用页面置换算法NUR：从那些最近一个时期内未被访问的页中任选一页淘汰。答案：FIFO算法：根据算法规则，访问第4页时，缺页中断程序选择的是3号页帧。该页帧的修改位为1，在换出主存后应进行回写，即重新保存。LRU算法：根据算法规则，最近的一次访问时间离当前时间最远的页帧应当被选择换出；因此缺页中断程序选择的是1号页帧。NRU算法：根据算法规则，应当选择访问位为0的页帧换出主存，因此缺页中断程序选择0号页帧换出。16.使为什么要引入SPOOLing系统？实现SPOOLing技术系统需付出哪些代价？使用SPOOLing技术有什么好处？答案：所有字符设备都要独占设备并且是慢速设备，本质上属于顺序存取设备，并且在数据交换完成之前，其他进程不能同时访问这台设备。当一个进程正在使用这类设备进行一次大
量的数据交换时，其他需要同时访问该设备的进程就要等待较长的时间，系统正是针对从而降低了整个系统的并发能力。SPOOLing系统正是针对这一问题引入的一种设备管理技术，它的意思是外部设备联机并行操作。其核心思想是利用一台可共享的、高速大容量的块设备（磁盘）来模拟独占设备的操作，使一台独台设备变为多台可并行使用的虚拟设备，即把独占设备变成逻辑上的共享设备。实现SPOOLing技术系统需付出的代价有：（1）占用大量内存作为外设间传送用的缓冲区，系统所用的表格页占用不少内存空间；（2）占用大量磁盘空间用作输入和输出；（3）增加了系统的复杂性。使用SPOOLing技术的好处有：（1）字符设备和各虚拟设备之间的数据交换由SPOOLing进程统一调度实施，而且这种数据交换以并行方式进行，系统呈现出高度的并行性。（2）用户使用的是虚拟设备，可以减少用户进程的等待时间。17.当前磁盘读写位于20号柱面，此时有多个磁盘请求，以下列柱面号顺序送至磁盘驱动器：10，22，20，2，40，6，38。寻道（Track）时，移动一个柱面需要花费6ms，按下列算法计算所需寻道时间（柱面移动顺序及所需时间，总寻道时间;忽略到达指定柱面后所需寻道时间）。（1）先来先服务。（2）最短寻道时间优先。（3）电梯算法（当前状态为向上）。18.假定磁盘的存取臂当前处于6号柱面上，如表2-16所示。有6个请求者等待访问磁盘，试列出最省时间的响应顺序。表2-16序号柱面号磁道号块号1763255631520647445209565152解析：本题主要考查移臂调度和旋转调度的相关内容。题目只要求给出最省时间的相应序列，因此对具体算法没有限定。解题时要注意分清移臂调度和旋转调度的顺序（磁道号无需考虑）。由于移臂时间在磁盘的整个访问时间中占主要地位，因此应首先予以考虑。由题意，当前磁盘的存储臂在6号柱面，根据访问顺序，可以看出，采用6→5→7→15→20顺序，移臂时间最少。由于在第5和第7柱面均有若干访问动作，所以要考虑旋转优化。在第5柱面，访问的块号为6和2，可以考虑访问顺序为2→6；第7柱面，访问块号为4和3，可以考虑访问顺序为3→4。答案：最省时间的响应序列为（按请求序号）：6→2→4→1→3→5。19. 假定磁盘的存取臂当前处于6号柱面上，如表2-16所示。有6个请求者等待访问磁盘，试列出最省时间的响应顺序。表2-16序号柱面号磁道号块号17632556315206
47445209565152解析：本题主要考查移臂调度和旋转调度的相关内容。题目只要求给出最省时间的相应序列，因此对具体算法没有限定。解题时要注意分清移臂调度和旋转调度的顺序（磁道号无需考虑）。由于移臂时间在磁盘的整个访问时间中占主要地位，因此应首先予以考虑。由题意，当前磁盘的存储臂在6号柱面，根据访问顺序，可以看出，采用6→5→7→15→20顺序，移臂时间最少。由于在第5和第7柱面均有若干访问动作，所以要考虑旋转优化。在第5柱面，访问的块号为6和2，可以考虑访问顺序为2→6；第7柱面，访问块号为4和3，可以考虑访问顺序为3→4。答案：最省时间的响应序列为（按请求序号）：6→2→4→1→3→5。20.假定盘块的大小为1KB，磁盘的大小为500MB，采用显示链接分配方式时，其FAT需要占用多少存储空间？解析：FAT的每个表项对应磁盘的一个盘块，用来存放分配给文件的下一个盘块的快号，因此FAT的表项数目由物理盘块数决定，而表项的长度则由磁盘系统的最大盘块号决定（即它必须能存放最大的盘块号）。为了地址转换的方便，FAT表项的长度通常取半个字节的整数倍，因此必要时还必须由最大盘块号获得的FAT表项长度做一些调整。答案：由题意知，该硬盘共有500K个盘块（500MB/1KB=500K盘块），因此FAT共有500K个表项。若盘块从1开始编号，为了能保存最大的盘块号500K，该FAT表项最少需要19位（500K<512K=219），将它扩展为半个字节的整数倍后，可知每个FAT表项需要20位，即2.5个字节。所以，FAT需要占用存储空间的大小为：2.5B×500K=1250KB。21. 一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，程序B后开始运行。程序A的运行轨迹为：计算50ms、打印100ms、再计算50ms、打印100ms，结束。程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms，结束。试说明(1)两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？(2)程序A、B有无等待CPU的情况？若有，指出发生等待的时刻。画出两道程序并发执行图如下：