操作系统大题

1、 简述操作系统的基本特征。答：（1）并发。在单处理机、多道程序环境下并发是指一段时间内，宏观上多个程序同时运行、微观上交替运行的情形。OS中引入进程的概念就是为了实现并发；（2） 共享。是指系统中并发执行的多个进程共享系统资源。根据资源属性可以有互斥共享和同时访问两种方式；（3） 虚拟。OS会通过虚拟技术实现系统功能的扩充。（4） 异步性。并发执行的多个进程由于资源的限制会出现“走走停停”的运行模式。2、 试分析引起进程阻塞和唤醒的事件主要有哪些。答：（1）请求系统服务。当正在执行的进程请求系统提供服务而系统无法满足其请求时，进程阻塞等待；由释放服务的进程唤醒阻塞进程。（2） 启动某种操作。当进程启动某种I/O操作后阻塞以等待操作完成；由中断处理程序唤醒阻塞进程。（3） 新数据尚未到达。相互合作的进程中，消费者进程阻塞等待数据到达；生产者进程在数据到达后唤醒阻塞进程。（4） 无新工作可做。系统进程没有新工作可做时阻塞等待；当有进程发出请求时唤醒阻塞进程。3、 简述在操作系统中引入缓冲的主要原因。答：（1）缓和CPU与I/O设备间速度不匹配的矛盾。（2） 减少对CPU的中断频率，放宽对中断响应时间的限制。（3） 提高CPU和I/O设备之间的并行性。4、 以独占设备为例简述设备分配的过程。答：（1）设备的分配。根据物理设备名，查找SDT；找出该设备的DCT，得该设备的状态：忙则将进程的PCB排入设备队列中等待；闲则分配设备给进程。（2） 控制器的分配。根据设备的DCT找到与之相连的控制器的COCT，从中得到控制器的状态：忙则将进程的PCB排入控制器的等待队列中；闲则分配控制器给进程。（3） 通道的分配。如果系统有通道，则根据控制器的COCT找到与之相连的通道的CHCT，从中得到通道的状态：忙则将进程的PCB挂入通道的等待队列中；否则分配通道给进程。只有在三者都分配成功时，设备分配才算成功。五、综合分析题（每小题5分，共30分）1、假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上标志（进入时登记，离开时去掉登记项），而且每次只允许一人登记或去掉登记，问：（1） 用P、V操作管理并发进程时，应如何定义信号量？写出信号量的初值并说明其含义；（2） 根据所定义的信号量，把应执行的P、V操作填入以下程序中，以保证进程能够正确地并发执行。COBEGINPROCEDUREEnterBegin登记;进入阅览室；阅读；End；PROCEDURELeaveBegin去掉登记项;离开；End；COEND；【解析】（1）设置资源信号量Empty：=100,表示阅览室中最初有100个空位；设置互斥信号量Mutex：=1，表示登记表初始是可用的。（2）按顺序填入P（Empty）；P（Mutex）；V（Empty）；2、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的非抢占式调度算法。下表所列的作业优先数即为进程优先数，优先数越小优先级越高。作业名到达时间估计运行时间优先数A10:0030分5B10:2020分4C10:3040分3D10:5010分6（1） 列出所有作业进入内存时间及结束时间;（2） 计算平均周转时间。【解析】（1）（2）答案如下所示：作业名到达时间运行时间优先数进入内存时间结束时间周转时间A10:0030分510:0010:3030分B10:2020分410:2011:3070分C10:3040分310:3011:1040分D10:5010分611:1011:4050分平均周转时间=（30+70+40+50）/4=47.5分3、假如某个时刻的系统状态如图所示:请问：（1）对该RAG进行化简并说明是否存在死锁，要求给出化简步骤;（2）如果系统发生了死锁，常用的死锁解除策略有哪些？【解析】（1）OR2OR2R1OORAG可以完全化简，故不存在死锁。(2)如果发生了死锁，常用的死锁解除策略有：剥夺资源；撤消进程。4、给出某系统中的进程请求表和空闲分区表，系统采用可变分区存储管理策略。进程名大小A96KB20KC200K进程请求表分区号大小起始地址132K100K210K150K35K200K4218K220K596K530K空闲分区表请问：（1）若采用首次适应算法和最佳适应算法来处理这些进程序列，哪一种算法可以满足该进程序列的请求?（2）给出按照能满足进程序列请求的算法进行分区分配后的空闲分区表。【解析】（1）最佳适应算法可以满足所有进程的资源请求。（2）分区分配后的空闲分区表如下：分区号大小起始地址112K120K210K150K35K200K418K420K5、在某个请求分页存储系统中，已知页面大小为1024K。现有一进程，其页表如下:页号块号状态0311212413—04—0其中，状态位为1表示该页在内存，为0表示不在内存。请问：（1）若给定一逻辑地址为2148，其物理地址为多少？（2）若给定一逻辑地址为5000，给出其物理地址的计算过程。【解析】（1）逻辑地址LA=2148，则逻辑页号P=INT（2148/1024）=2，页内位移W=2148mod1024=100。查页表知：该页在内存，块号为4，由此得物理地址PA=1024*4+100=4196。（2）逻辑地址LA=5000，则逻辑页号P=INT（5000/1024=4，查页表知：该页不在内存，发生缺页中断。6、在一个请求分页存储系统中，一个进程的页面走向为4,3,2,1，4,3,5,3,2,1，设分配给该进程的内存块数M=3，采用FIFO页面置换算法（每调进一个新页认为发生一次缺页中断）。（1）试完成下表：时刻12345678910P4321435321M=3F（2）求缺页中断次数F=；缺页率f=【解析】（1）时刻12345678910P43214353214441115555M=333344442222233331F123456789（2）缺页中断次数为F=9次，缺页率为f=90%。1、 名词解释（1） 虚拟存储器；虚拟存储器：由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。也可解释为仅把作业的一部分装入内存便可运行作业的存储器系统；具体地说是指具有调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。（2） 死锁；死锁：指各并发进程彼此互相等待对方所拥有的资源，而且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想的到资源而又的不到资源，各并发进程不能继续向前推进的状态。2、 简答（1）段页式管理这种存储管理方式中为什么要设置高速联想寄存器？因为如果不采用高速联想寄存器，段页式的地址转换需要访问内存的次数将达三次以上，这将使cpu执行指令的速度大大降低，所以必须要设置高速联想寄存器，存放当前最常用的段号、页号和对应的内存页面与其它控制栏目，达到大大提高地址转换的目的。（2）进程和程序有什么区别和联系？a） 进程是一个动态概念，而程序是一个静态概念，程序是指令的有序集合，无执行含义，进程则强调执行的过程。b） 进程具有并行特征，程序没有。c） 进程是竞争计算机系统资源的基本单位。d） 不同的进程可以包含同一个程序，同一程序也可产生多个进程。（3） 什么是系统调用？简述系统调用的实现过程。系统调用是操作系统提供给编程人员的唯一接口。编程人员利用系统调用，在源程序一级动态请求和释放系统资源，调用系统中已有的系统功能来完成那些与机器硬件部分相关的工作以及控制程序的执行速度等。实现过程：用户在程序中使用系统调用，给出系统调用名和函数后，即产生一条相应的陷入指令，通过陷入处理机制调用服务，引起处理机中断，然后保护处理机现场，取系统调用功能号并寻找子程序入口，通过入口地址表来调用系统子程序，然后返回用户程序继续执行。五、综合题（每小题6分，共30分）1、假设有四个作业的单道系统，它们的提交、运行时间如下表所示（时间单位：小时，以十进制进行计算）。若采用基于优先权的非抢占式调度算法（优先数高者优先权低），试回答：（1）作业应以怎样的顺序调度？给出分析过程。（2）计算平均带权周转时间。作业号到达时间运行时间/IX Wr优先数A8.02.04B8.50.56C9.00.22D9.51.05

2、输入进程不断地从磁盘读入记录存入缓冲区（假设该缓冲区的大小正好等于两条磁盘记录），计算进程不断地从缓冲区取数据进行计算，要求输入进程和计算进程之间的合作必须保持同步：即输入进程不能向满的缓冲区内存记录，计算进程不能从空的缓冲区内取数据。用P、V原语描述输入进程Input和计算进程Calculate之间的合作，并回答以下问题：（1）设置信号量empty，用于查看缓冲区是否有空间存储新记录，其初值应为多少？设置信号量full，用于查看缓冲区内是否放入数据，其初值应为多少？（2）根据定义的信号量，将适当的P、V原语填入以下程序使并发进程能够正确执行。COBEGINInput：RepeatBegin读磁盘记录 ① ；存入缓冲区；EndUntilFalse；Calculate：RepeatBegin ③ ；取出记录；④ ^ ；进行计算；EndUntilFalse；COEND已用3、设进程A（30K）、B（70K）和C（50K）依次请求内存分配，内存采用可变分区管理。现有两个空闲分区F1（120K）和F2（80K），如下图所示。若采用首次适应算法，画出内存分配情况示意图。已用1200KF1（120K）1500K已用1500KF2（80K）已用4、在一个分段存储管理系统中，其段表如下:段号内存始址段长0200500125008523009041006005500120计算与给定逻辑地址LA对应的物理地址PA，给出计算过程:（1）LA=（1，50）；

(2)LA=(5,350)。5、在一个请求分页存储管理系统中，某进程的页面走向为2、3、2、1、5、2、4、5、3、2,当分配给该进程的物理块数为3时（假设开始执行时内存中没有页面），试回答以下问题：（1） 计算采用最近最久未用LRU置换算法的缺页率；（2） LRU置换算法选择什么样的页面淘汰？1、作业号到达时间运行时间ZJX+心r优先数开始时间完成时间周转时间带权时间A8.02.048.010.02.01.0B8.50.5611.211.73.26.4C9.00.2210.010.21.26.0D9.51.0510.211.21.71.7（1） 8.0时，只有A到达，调度运行，10.0完成，此时B、C、D均到达；C具有最高优先权，调度运行，10.2完成；D的优先权较B高，调度D运行，11.2完成；11.2时调度B运行，11.7完成；故进程调度顺序为：ACDB。（2） 作业A的周转时间：10.0-8.0=2.0；带权周转时间：2.0/2.0=1.0；作业B的周转时间：11.7-8.5=3.2；带权周转时间：3.2/0.5=6.4；作业C的周转时间：10.2-9.0=1.2；带权周转时间：3.2/0.5=6.0；作业D的周转时间：11.2-9.5=1.7；带权周转时间：1.7/1.0=1.7；故平均带权周转时间为：5.275。2、（1）资源信号量empty：=2；同步信号量full：=0；（2）①P（empty）； ②；V（full） ③P（full）； ④V（empty）；3、4、 （1）LA=（1，50），PA=2500+50=2550；（2）LA=（5，350），因350>120发生地址越界。5、页面走向2 3 2152453 2LRU2 2 2 22222333 3 3555555n=31114442缺页XX XXXXX（1） 缺页率：7/10=70%；（2） LRU置换算法选择离当前时间最近的一段时间内最久没有使用过的页面淘汰。四，简答题从资源管理的角度说明操作系统的主要功能.答：进程管理（或处理器管理），存储管理，文件管理，作业管理和设备管理.什么是操作系统？它的主要功能是什么？答：操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合，是用户与计算机之间的接口——它们能有效地组织和管理计算机系统中的硬件及软件资源，合理地组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使得用户能够灵活、方便、有效地使用计算机，并使整个计算机系统能高效地运行。操作系统的主要功能包括：存储器管理、处理机管理、设备管理、文件管理以及用户接口管理。为什么说批处理多道系统能极大地提高计算机系统的工作效率？答：①多道作业并行工作，减少了处理器的空闲时间。作业调度可以合理选择装入主存储器中的作业，充分利用计算机系统的资源。作业执行过程中不再访问低速设备，而直接访问高速的磁盘设备，缩短执行时间。作业成批输入，减少了从操作到作业的交接时间。简述进程的几种状态和引起状态转换的典型原因，以及相关的操作原语。试描绘出进程状态转换图。答：进程的基本状态有：新建、就绪，阻塞，执行、挂起和终止六种。新建到就绪：交换，系统完成了进程创建操作，且当前系统的性能和内存的容量均允许。创建原语就绪到执行：进程调度，调度程序选择一个新的进程运行执行到阻塞：I/O请求，阻塞原语阻塞到就绪：I/O完成，唤醒原语执行到就绪：时间片完；运行进程被中断，因为一高优先级进程处于就绪状态阻塞到挂起：挂起原语挂起到就绪：激活原语执行到终止：进程执行完毕或被终止撤消原语。什么是临界区进程进入临界区的调度原则是什么答:在每个进程中访问临界资源的那段程序叫临界区进程进入临界区的调度原则是：如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入.任何时候,处于临界区内的进程不可多于一个.如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待.进入临界区的进程要在有限时间内退出，以便其它进程能及时进入自己的临界区.如果进程不能进入自己的临界区，则应让出CPU,避免进程出现〃忙等〃现象.怎样理解“计算机上由于装有操作系统，从而扩展了原计算机功能'？答：原来的计算机功能很小，只能进行一些基本而又非常简单的数据运算，而自从有了操作系统之后，计算机功能大大增加。DOS使计算机具有了命令处理、存储器管理、文件管理和设备管理等功能，而后，出现的WINDOWS各种系统使得计算机不但功能更加齐全，而且系统的工作效率大大提高，更让用户建立了网络，共享网络通信资源！一个具有分时兼批处理功能的操作系统应怎样调度和管理作业答：1)优先接纳终端作业，仅当终端作业数小于系统可以允许同时工作的作业数时，可以调度批处理作业.允许终端作业和批处理作业混合同时执行.把终端作业的就绪进程排成一个就绪队列，把批处理作业的就绪进程排入另外的就绪队列中.有终端作业进程就绪时，优先让其按〃时间片轮转〃法先运行.没有终端作业时再按确定算法选批处理作业就绪进程运行.在信号量S上作P、V操作时，S的值发生变化，当S>0、S=0、S<0时，它们的物理意义是什么？答：S的值表示它代表的物理资源的使用状态：S>0表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。S<0表示资源已被分配完，还有进程等待使用资源。处理机调度分为哪三级？各自的主要任务是什么？答：作业调度：从一批后备作业中选择一个或几个作业，给它们分配资源，建立进程，挂入就绪队列。执行完后，回收资源。进程调度：从就绪进程队列中根据某个策略选取一个进程，使之占用CPU。交换调度：按照给定的原则和策略，将外存交换区中的进程调入内存，把内存中的非执行进程交换到外存交换区。试比较进程调度与作业调度的不同点.答：(1)作业调度是宏观调度，它决定了哪一个作业能进入主存.进程调度是微观调度,它决定各作业中的哪一个进程占有中央处理机.(或)作业调度是高级调度，它位于操作系统的作业管理层次.进程调度是低级调度，它位于操作系统分层结构的最内层.(2)作业调度是选符合条件的收容态作业装入内存.进程调度是从就绪态进程中选一个占用处理机.进程与程序是两个完全不同的概念，但又有密切的联系，试写出两者的区别。答：两者的主要区别有：进程是动态，程序是静态的；进程是独立运行的单位，程序不能作为运行单位；各进程间在并发执行过程中会产生相互制约关系，而程序由于是静态的，所以不存在异步特征。单道批处理系统中，下列三个作业采用先来先服务调试算法和最高响应比优先算法进行调试，哪一种算法性能较好？请完成下表。作业提交时间运行时间开始时间完成时间周转时间带权周转时间110：002：00210：101：00310：250：25平均作业周转时间=平均作业带权周转时间W=FIFO作业提交时间运行时间开始时间完成时间周转时间带权周转时间110：002：0010:0012:002120/120210：101：0012:0013:002:50170/60310：250：2513:0013:253180/25平均作业周转时间=2.61平均作业带权周转时间W=3.34HRN作业提交时间运行时间开始时间完成时间周转时间带权周转时间110：002：0010:0012:002120/120210：101：0012:2513:253:15195/60310：250：2512:0012:252120/25平均作业周转时间=2.4167平均作业带权周转时间W=3.02可见HRRF比FIFO要好。简述死锁的防止与死锁的避免的区别.答:死锁的防止是系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生.而死锁的避免是当进程提出资源申请时系统测试资源分配，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁.试说明资源的静态分配策略能防止死锁的原因.答：资源静态分配策略要求每个进程在开始执行前申请所需的全部资源仅在系统为之分配了所需的全部资源后，该进程才开始执行.这样，进程在执行过程中不再申请资源，从而破坏了死锁的四个必要条件之一〃占有并等待条件〃，从而防止死锁的发生.计算机系统中产生死锁的根本原因是什么一般解决死锁的方法有哪三种答:计算机系统中产生死锁的根本原因是:资源有限且操作不当.一般解决死锁的方法有:死锁的预防，死锁的避免，死锁的检测与恢复等三种.什么是死锁？产生死锁的四个必要条件是什么？死锁：当某进程提出资源申请后，使得系统中一些进程处于无休止的阻塞状态，在无外力作用下，永远不能再继续前进。产生死锁的必要条件：互斥条件：某段时间内某资源只能由一个进程使用。不剥夺条件：资源在未使用完前，不能被剥夺，由使用进程释放。部分分配（请求和保持）：进程因请求资源而阻塞时，对已分配给它的资源保持不放。环路条件：发生死锁时，有向图必构成一环路。进程调度中〃可抢占〃和〃非抢占〃两种方式，哪一种系统的开销更大?为什么答：可抢占式会引起系统的开销更大.可抢占式调度是严格保证任何时刻，让具有最高优先数（权）的进程占有处理机运行，因此增加了处理机调度的时机,引起为退出处理机的进程保留现场，为占有处理机的进程恢复现场等时间（和空间）开销增大.存储管理的主要功能是什么答:存储管理的主要功能包括：（1）主存空间的分配和回收；（2）将用户的逻辑地址转换成主存的物理地址，完成重定位；（3）主存空间的共享和保护；（4）使用〃虚拟存储器〃，扩充主存空间.试述分区管理方案的优缺点.答:优点:算法较简单,实现较容易，内存开销较少，存储保护措施简单.缺点：内存使用不充分,存在较严重的碎片问题.虚拟存储器的基本特征是什么？虚拟存储器的容量主要受到哪两方面的限制？答:虚拟存储器的基本特征是：虚拟扩充，即不是物理上而是逻辑上扩充了内存容量；部分装入，即每个作业不是全部一次性地装入内存，而是只装入一部分；离散分配,即不必占用连续的内存空间，而是〃见缝插针〃；多次对换，即所需的全部程序和数据要分成多次调入内存.虚拟存储器的容量主要受到指令中表示地址的字长和外存的容量的限制1什么是虚拟存储器，它有什么特点？答：虚拟存储器是一种存储管理技术，用以完成用小的内存实现在大的虚空间中程序的运行工作。它是由操作系统提供的一个假想的特大存储器。但是虚拟存储器的容量并不是无限的，它由计算机的地址结构长度所确定，另外虚存容量的扩大是以牺牲CPU工作时间以及内、外存交换时间为代价的。什么是动态重定位？如何实现？动态重定位是指在程序执行期间，随着每条指令和数据的访问，自动的、连续的进行映射。具体实现过程为：当某个进程取得CPU控制权时，OS应负责把该作业程序在主存中的起始地址送入重定位寄存器中之后，每次访问存储器时，重定位寄存区的内容将被自动加到逻辑地址中区，经这样变换后，执行结果是正确的。试简述页式存储管理的优缺点。答：优点：有效地解决了碎片问题；缺点：程序的最后一页会有浪费空间的现象并且不能应用在分段编写的、非连续存放的大型程序中。影响缺页中断率的因素有哪些？答：4个因素，分别是：（1）分配给程序的主存块数；（2）页面的大小；（3）程序编制方法；（4）页面调度算法。什么是快表？它在地址转换中起什么作用？快表是一个高速、具有并行查询能力的联想存储器，用于存放正运行的进程的当前页号和块号，或者段号和段起始地址。加入快表后，在地址转换时，首先在快表中查找，若找到就直接进行地址转换；未找到，则在主存页表继续查找，并把查到的页号和块号放入联想存储器中。快表的命中率很高，有效地提高了地址转换的速度。主存空间信息保护有哪些措施？程序执行时访问属于自己主存区域的信息，允许它既可读，又可写；对共享区域中的信息只可读，不可修改；对非共享区域或非自己的主存区域中的信息既不可读，也不可写。操作系统为用户提供哪些接口？答：操作系统为用户提供两种类型的使用接口：一是操作员级的，它为用户提供控制作业执行的途径；二是程序员级的，它为用户程序提供服务功能。系统调用的执行过程分可分为哪几步？答：系统调用的执行过程分成以下几步：（1）设置系统调用号和参数；（2）系统调用命令的一般性处理；（3）系统调用命令处理程序做具体处理。目前操作系统采用的目录结构是什么？它具有什么优点？为了给用户提供对文件的存取控制及保护功能，而按一定规则对系统中的文件名，（亦可包含文件属性）进行组织所形成的表，称为目录表或文件目录。目前操作系统采用的目录结构是树型目录结构，它的优点有：有效地提高对目录的检索速度；允许文件重名；便于实现文件共享。试说明和比较几种文件共享的方法绕弯路法：利用基本文件目录实现文件共享：基于索引节点的共享方法：利用符号链实现文件共享：文件系统要解决哪些问题答:一般说来，文件系统应具备以下功能:文件管理（如创建/删除文件，对文件的各种操作等），目录管理（创建/删除目录项，权限验证等），文件存储空间的管理（如外存空间的分配与回收），文件的共享和保护，提供方便的接口（如实现按名存取,文件系统调用等）.常用的文件存取控制方式有哪些答:主要有存取控制矩阵，用户权限表，使用口令，使用密码.UNIX/Linux文件系统的主要特点是什么答:UNIX/Linux文件系统的主要特点有：（1）UNIX或Linux文件系统的目录组织是一个树形结构;（2）文件本身是无结构的字符流；（3）UNIX或Linux文件系统把外部设备做成特殊文件，与普通文件一并进行管理.请说明在生产者一消费者问题的描述中，P操作颠倒会产生死锁吗？为什么？答：如果将生产者执行的两个P操作顺序颠倒，会产生死锁。因为，在这种情况下，当缓冲区都为满时，生产者仍可顺利执行P（mutex）操作，于是它获得了对缓冲区的存取控制权。然后，当它执行P（mutex）操作时，由于没有空缓冲区它被挂起。能够将这个生产者进程释放的唯一途径是消费者从缓冲区取出了一个产品，并执行V（mutex）操作。但在此时，由于缓冲区已被挂起的生产者所占有，所以没有一个消费者能够取得对缓冲区的存取控制权。因此，出现了生产者和消费者的互相死等的局面。什么是设备独立性，它是如何实现的？答：设备独立性即应用程序独立于使用的物理设备，在应用程序中使用逻辑设备名称来请求使用某类设备。系统在执行时，是使用物理设备名称。要实现设备独立性必须由设备独立性软件完成，包括执行所有设备的公有操作软件提供统一的接口，其中逻辑设备到物理设备的映射是由逻辑设备表LUT完成的。在设备管理中，按照设备共享特性分成哪几种类型比较合理，并分别举例说明。答：按照是否可共享，可以分成独占设备和共享设备两类，独占设备不能让多个程序同时使用，共享设备可以同时让多个程序使用。打印机属于独占设备，如果多个程序同时使用打印机，则打印出来的数据就可能会随机混合交叉在一起，所以打印机只能让一个程序独占。而磁盘属于共享设备，多个程序同时在磁盘上打开文件是可以的。实现虚拟设备的硬件条件是什么操作系统应设计哪些功能程序答：硬件条件是:配置大容量的磁盘,要有中断装置和通道操作系统应设计好〃预输入〃程序,"井管理〃程序，〃缓输出〃程序.五，应用题假定系统有三个并发进程read,move和print共享缓冲器B1和B2.进程read负责从输入设备上读信息，每

读出一个记录后把它存放到缓冲器B1中.进程move从缓冲器B1中取出一记录，加工后存入缓冲器B2.进程print将B2中的记录取出打印输出.缓冲器B1和B2每次只能存放一个记录.要求三个进程协调完成任务，使打印出来的与读入的记录的个数，次序完全一样.请用PV操作，写出它们的并发程序.semaphoreread()move()print()SR,SM1,SM2,SP;{{{recordB1,B2;recordX;recordY;recordZ;main()while(1)while(1)while(1){{{{SR=1;接收来自输入设备上一个记录P(SM1);P(SP);SM1=0;X=接收的一个记录；Y=B1;Z=B2;SM2=1;P(SR);V(SR)V(SM2);SP=0B1=X;加工Y打印Z;cobeginV(SM1);P(SM2);}read;}B2=Y;move;V(SP);print}coend}}有两个用户进程A和B,在运行过程中都要使用系统中的一台打印机输出计算结果.（1） 试说明A,B两进程之间存在什么样的制约关系（2） 为保证这两个进程能正确地打印出各自的结果，请用信号量和P,V操作写出各自的有关申请，使用打印机的代码.要求给出信号量的含义和初值.答：（1）A,B两进程之间存在互斥制约关系.因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用.（2）mutex:用于互斥的信号量,因为只有一台打印机，所以初值为1.进程A进程BP(mutex);P(mutex);使用打印机；使用打印机；V(mutex); V(mutex); 设input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：（1） 这两个进程有何相互制约关系？（2） 试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。答：（1）这两个进程的相互制约关系为同步关系；（2）设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q中是否有信息，初值为0，表示Q中无信息。两进程的代码段如下：

input进程{ output进程{ while信息未处理完毕while信息未处理完毕{{加工一个信息；P（S2）；P（S1）；从Q中读出一个信息；将信息放入Q中；V（S1）；V（S2）； }}4.两个并发执行的进程A和B的程序如下:进程Awhile(true){N=N+5;}进程Bwhile(true){打印N的值；N=0；}其中N为整数，初值为4。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理，使进程A和B并发执行时不会出现与时间有关的错误。答：因为N初值为4,若进程A先执行了三个循环，此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序，即进程A先执行一次循环，然后再进程B执行一次循环，此时打印的是正确值24,执行后N中的值为0。但若进程B先执行一次循环，然后再进程A执行一次循环，则打印的值是19,执行后N中的值是5。这是错误的，即发生了与时间有关的错误。用P、V操作进行管理，使进程A和B并发时不会出现与时间有关的错误的程序如下：（S为互斥信号量，初值为1），进程A进程Bwhile(true)while(true){{P(S);P(S);N=N+5;打印N的值；V(S);N=0；}V(S);}设在公共汽车上，司机和售票员的活动分别如下：司机的活动：启动车辆；正常行车；到站停车。售票员的活动：关车门；售票；开车门。（1）在汽车不停地到站、停车以及行驶的过程中，司机和售票员之间的活动有什么同步关系？（6分）答：（1）售票员关车门后，向司机发开车信号，司机接到开车信号后起动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。定义两个信号量：run:表示是否允许司机起动车辆stop：表示是否允许售票员开门。初值为0。请将以下描述这两个活动的P、V操作补充完整(4分):run=0;stop=0;main()｛parbegindriver();conductor();parend;}driver()conductor(){while(1){while(1)1 ;｛关车门；启动车辆；3 ；正常行车；售票.；到站停车；4 ;2 ；开车门；}上下乘客；}}}run:表示是否允许司机起动车辆，stop:表示是否允许售票员开门stop=0;run=0;main(){parbegindriver();conductor();parend;}driver()conductor(){while(1){while(1){wait(run);｛关车门；启动车辆；signal(run)；正常行车；售票.；到站停车；wait(stop);signal(stop)；开车门；}上下乘客；}}}6.假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：

作业进入系统时间估计运行时间/分钟18:004028:203038:301249:001859:105（1）如果应用先来先服务的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:004028:203038:301249:001859:105作业平均周转时间T=（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:004028:203038:301249:001859:105作业平均周转时间T=答：（1）应用先来先服务的作业调度算法，表格填写如下:作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408:008:404028:20308:409:105038:30129:109:225249:00189:229:404059:1059:409:4535作业平均周转时间T=43.4217（2）应用最短作业优先的作业调度算法，表格填写如下:作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408:008:404028:20308:529:226238:30128:408:522249:00189:279:454559:1059:229:2717作业平均周转时间T=37.2186

系统中有五个进程P、P、P、P、P，有三种类型的资源：R1、R2、和R3。在T时刻系统状态如表所示。若采1 2 3 4 5 0用银行家算法实施死锁避免策略，回答下列问题：T0时刻是否为安全状态？为什么？（2分）若这时P"请求资源（1,2,0）,是否能实施资源分配？为什么？（4分）在上面的基础上，若进程P"请求资源（0,1,0）,是否能实施资源分配？为什么？（4分）T0时刻系统状态已分配资源数量最大资源需求量R1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065R1R2R3剩余资源数330解：（共9分，每小题3分）1）T0时刻是安全的，安全序列为：P1,P4,P5,P2,P32）P4请求资源（1,2,0）,根据银行家算法，预分配后系统是安全的，安全序列为：P1,P4,P5,P2,P33）P3请求资源（1,1,0）,根据银行家算法，预分配后系统不安全，所以不能实施资源分配。1011,2148,4000,5012转化为相应的物理地址.查页表第0页在第2块，所以物理地址为3059.查页表第2页在第1块，所以物理地址为1011,2148,4000,5012转化为相应的物理地址.查页表第0页在第2块，所以物理地址为3059.查页表第2页在第1块，所以物理地址为1124.查页表第3页在第6块，所以物理地址为7072.因页号超过页表长度，该逻辑地址非法.对于逻辑地址2148,P=INT(2148/1024)=2,D=2148mod1024=100,对于逻辑地址4000,P=INT(4000/1024)=3,D=4000mod1024=928,对于逻辑地址5012,P=INT(5012/1024)=4,D=5012mod1024=916,5.根据如下段表:段号基地址长度合法（0）/非法（1）03002001750054023000101032000100（1） 求出逻辑地址为［0,100］的物理地址并将其的合法性填入段上表适当位置;（2） 求出逻辑地址为［3,100］的物理地址并将其的合法性填入上表适当位置；答：（1）物理地址为：300+100=400，合法性如下表所示。（2）物理地址为：2000+100=2100，合法性如下表所示。段号基地址长度合法（0）/非法（1）0300200017500540230001010320001001在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115,228,120,88,446,102,321,432,260,167,若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：（1） 按FIFO调度算法将产生次缺页中断，依次淘汰的页号为，缺页中断率为.（2） 按LRU调度算法将产生次缺页中断，依次淘汰的页号为，缺页中断率为.答：（1）按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为:0,1,2;缺页中断率为：5/10=50%（2）按LRU调度算法将产生6次缺页中断;依次淘汰的页号为:2,0,1,3;缺页中断率为：6/10=60%某系统的进程状态图如下（1） 说明一个进程发生变迁1、3、4的原因是什么？（2） 下述因果变迁是否会发生?如果有可能的话,在什么情况下发生？A）1->3 B）2->4 C）4->1 D）5->1 E）3->2解：（1）发生变迁1的原因是：当CPU空闲且高优先就绪队列中有进程，则从高优先就绪队列调一个进程到CPU上去执行。发生变迁3的原因是：当一个在CPU上运行的进程用完它的时间片时，立即退出CPU而进入低优先就绪队列。发生变迁4的原因是：一个正在CPU上运行的进程需要输入或者输出数据时，退出CPU而进入等待队列。（2）A）和B）的因果变迁不可能发生。C）、D）和E）有可能发生，其原因是：C） 4->1：一个正在CPU上运行的进程需要输入或者输出数据时，退出CPU而进入等待队列，CPU空闲，这时若高优先就绪队列中有进程，则发生调度1。D） 5->1：当高优先就绪队列和CPU都处于空闲状态时，一个处于等待状态的进程被唤醒进入高优先就绪队列后立即被调度到CPU上去执行。

3->2：当一个在CPU上运行的进程用完它的时间片退出CPU而进入低优先就绪队列时，若高优先就绪队