搜索
1部分高校操作系统硕士研究生入学试题参考答案北京大学2000操作系统硕士入学试参考答案一、回答下列问题（15分）1．对某系统进行检测后表明平均每个进程在I/O阻塞之前的运行时间为T，一次进程的切换时间为S，这里S实际上就是开销。对于时间为Q秒的轮转法进程调度，分别就下列条件给出CPU的利用率的计算公式。（1）Q=∞；（2）QT；（3）SQT。解：因为，CPU利用率=进程有效运行时间/CPU总时间=有效运行时间/(有效运行时间+系统开销)。由于Q＝∞或Q＞T，那么，时间片足够大，进程每次运行总能结束，故1)和2)两种情况下，在T+S时间中，有效运行了T。得到CPU利用率=T/（T+S）。1）Q=∞CPU利用率=T/（T+S）2）QTCPU利用率=T/（T+S）2．I/0软件一般分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。试说明以下各个工作是在哪一层完成的？（1）向设备寄存器写命令；（2）检查用户是否有权使用设备；（3）将二进制整数转化成ASCII码以便打印。解：(1)在设备驱动程序。(2)与设备无关的软件层。(3)用户层。二、文件系统（15分）1．在文件系统中，会出现文件系统不一致性的现象，请简要解释这种现象产生的原因以及问题的严重性。2．为了解决文件系统的不一致性问题，常采用一个实用程序检查文件系统。在进行了块的不一致性检查后，得到如表所示的结果：块号0123456789101112131415空闲块1110101110101112分配块0011010002000000请解释该文件系统中出现的每一种错误，并给出处理方法。解：如果管理空闲块及分配/回收程序出现故障，则会导致不一致性错，或丢失盘块(均为0的情况)，或破坏信息(如重复分配)。正常情况，空闲块计数与分配块计数应互补。但表中有不一致处，块2—重复出现，向系统报告出错。块9---分配块重复出现，盘块被分了二次，严重错误，立即报告。块11---两组计数中均未出现，报告给系统但影响不大，只是该块被隔离了。块15---空闲块出现两次，可删去一个块15号。2三、P，V操作题（5分）某银行有人民币储蓄业务，由n个储蓄员负责。每个顾客进入银行后先取一个号，并且等着叫号。当一个储蓄人员空闲下来，就叫下一个号。请用P，V操作正确编写储蓄人员和顾客进程的程序。解：varcustomer_count,mutex:semaphore;customer_count:=0;mutex:=1;cobeginprocesscustomerbeginL1:takeanumber;P(mutex0;进入队列;V(mutex);V(customer_count);GotoL1;End;Processserversi(I=1,2,3,…)BeginP(customer_count);P(mutex);从队列取号;V(mutex);为该号客人服务;end;coend.北京航空航天大学2002年硕士入学操作系统试题参考答案一、简答题（20分）1．操作系统的基本特征是什么？答：并发性（concurrence）是指两个或两个以上的事件或活动在同一时间间隔内发生。操作系统是一个并发系统，并发性是它的重要特征，操作系统的并发性指计算机系统中同时存在若干个运行着的程序，因此，它应该具有处理和调度多个程序同时执行的能力。共享性是指计算机系统中的资源（包括硬件资源和信息资源）可被多个并发执行的用户程序和系统程序共同使用，而不是被其中某一个程序所独占。又可分互斥访问和共享访问。异步性是指在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况下，进程的执行不是一贯到底，而是“走走停停”。异步性给系统带来了潜在的危险，有可能导致进程产生与时间有关的错误，操作系统必须保证多次运行进程，都会获得完全相同的结果。3虚拟性是指操作系统中的一种管理技术，它是把物理上的一个实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。例如，在多道程序系统中，物理CPU可以只有一个，每次也仅能执行一道程序，但通过多道程序和分时使用CPU技术，宏观上有多个程序在执行，就好像有多个CPU在为各道程序工作一样，物理上的一个CPU变成了逻辑上的多个CPU。虚拟存储器则是把物理上的多个存储器(主存和辅存)变成逻辑上的一个(虚存)的例子。2．什么是死锁？死锁的原因是什么？答：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。3．信号量的物理意义是什么？答：信号量S的值表示它代表的物理资源的使用状态：S0表示还有共享资源可供使用。S=0表示共享资源正被进程使用但没有进程等待使用资源。S0表示资源已被分配完，还有进程等待使用资源。4．什么是进程？进程的基本特征？答：进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。它具有结构性、共享性、动态性、独立性、制约性、并发性等特征。二、判断题（5分）1．当一个进程从等待态变成就绪态，就一定有一个进程从就绪态变成运行态。(错)2．在请求页式存储管理中，页面淘汰所花费的时间不属于系统开销。(错)3．在中断处理过程中，必须屏蔽中断。(对)5．在有虚拟存储器的系统中，可以运行比主存容量还大的程序。(对)6．打印机是一类典型的字符设备。(错)三、考虑一仅460B的程序的下述内存的访问序列（该序列的下标均从0开始）10，11，104，170，73，309，185，245，246，434，458，364，且页面大小为100B，则（1）写出页面的访问序列。（2）假设内存中仅有200B可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？（3）如果采用最近最久未使用算法（LRU），则又会发生多少次缺页中断?（10分）答：设逻辑地址为L，页面大小为M(=100B)，故虚页号P=[L/M]（1）页面的访问序列为：0、0、1、1、0、3、1、2、2、4、4、3。（2）6次4（3）7次四、在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车：售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用P，V操作实现司机与售票员之间的同步。（10分）答：vars1，s2：semaphore；s1=0；s2=0;cobegin{driver();busman();}coenddriver()beginwhile(1){P(s1)启动车辆；正常行车；到站停车；V(s2);}endbusman()beginwhile(1){关车门；，V(s1)售票；P(s2)开车门；上下乘客；}end五、下面是两个并发执行的进程。它们能正确运行吗？若不能请举例说明，并改正之。（5分）parbeginvarx：integer;5processP1processP2vary，z：integer：vart,u：integer；beginbeginx:=1；x:=0：y:=0：t=0；ifx≥ltheny:=y十1；ifx≤lthent:=t+2；z:=y；u:=t；end；end；parend.答：显然，由于有共享变量x，并发执行时会产生与时间有关的错误。例P1先运行，程序执行完后z=1，而u=2。但若P1执行x:=1后暂仃，进程P2执行，此时x的值又重新赋0。待进程P2执行结束后，P1再运行，结果z=0，u=2。从而，结果不唯一。改正后程序为：parbeginvarx：integer;mutex:semaphore;mutex:=1;processP1processP2vary，z：integer：vart,u：integer；beginbeginP(mutex);P(mutex);x:=1；x:=0：y:=0：t=0；ifx≥ltheny:=y十1；ifx≤lthent:=t+2；V(mutex);V(mutex);z:=y；u:=t；end；end；parend.北京理工大学2001年硕士入学操作系统试题参考答案一、选择填空题（10分）1.在单处理机系统中实现并发技术后，（(2)）。（1）各进程在某一时刻并行运行，CPU与外设间并行工作（2）各进程在一个时间段内并行运行，CPU与外设间并行工作（3）各进程在一个时间段内并行运行，CPU与外设间串行工作（4）各进程在某一时刻并行运行，CPU与外设间串行工作2.在进程的生命期内，进程与其执行的程序个数之间是（(2)）关系。（1）一对一（2）一对多（3）多对一（4）多对多3.文件系统中的路径名是由（(3)）组成。（1）磁盘符和目录名（2）文件名和目录名（3）磁盘符、目录结构的各个目录名、文件名（4）磁盘符、根目录名、文件名64.在内存管理模式中，内存利用率最高的是（(2)）模式：动态扩充实现得最好的是（(3)）模式；内存利用率最高且保护和共享容易的是（(4)）模式。（1）分区管理（2）分页管理（3）分段管理（4）段页式管理5.在SPOOLing系统中，用户进程实际分配到的是（(3)）。（1）用户所要求的外设（2）一块内存区，即虚拟设备（3）共享设备的一部分存储区（4）虚拟设备的一部分空间6.按照地址映射的时机不同，可以分为（(2)）和（(4)）。（1）静态分配（2）静态重定位（3）动态分配（4）动态重定位7.用户及其应用程序和应用系统是通过（(3)）提供的支持和服务来使用系统资源完成其操作的。（1）点击鼠标（2）键盘命令（3）系统调用（4）图形用户界面二、正误判断题（5分）1.原语可以被多个进程同时执行。(错)2.对文件进行检索时，检索的起点必须是根目录而不是其他目录。(错)3．并发性是指若干个事件在不同的时刻发生。(错)4．死锁是系统中的全部进程都处于阻塞状态。(错)5．在用P，V操作解决进程之间的同步与互斥时，一定要正确地安排P，V操作的顺序，否则会引起死锁。(对)三、简答题（15分）1．在设备管理中，何谓设备的独立性？如何实现设备的独立性？答：用户编程时，指定逻辑设备，使用户程序独立于物理设备，再通过适当途径建立逻辑设备与物理设备的对应关系，称设备的独立性。实现设备的独立性的主要方法是程序员利用逻辑设备I/O，而逻辑设备与物理设备的对应转换可由操作系统命令或语言实现。2.在UNIX系统中，每个i节点中分别含有10个直接地址的索引和一、二、三级间接索引。若每个盘块放128个盘块地址，则一个1MB的文件分别占用多少间接盘块？20MB的文件呢？设每个盘块有512B。答：直接块容量=10×512B/1024=5KB一次间接容量=128×512B/1024=64KB二次间接容量=128×128×512B/1024=64KB×128=8192KB三次间接容量=128×128×128×512B/1024=64KB×128=8192KB×128=1048576KB1MB为1024KB，1024KB-69KB=955KB，955×1024B/512B=1910块，1MB的文件分别占用1910个二次间接盘块。20×1024KB-69-8192=12219KB，12219×1024B/512=24438块，20MB的文件分别占用24438个三次间接盘块和8192个二次间接盘块。3.假定一个处理机正在执行两道作业，一道作业以计算为主，另一道以I/O为主，你将怎样为它们分配优先级？为什么？7答：优先级调度的基本原则是：照顾时间紧迫的作业使其得到及时处理、照顾会话型作业使其快速响应、照顾I/O繁忙型作业，使外设充分保持忙碌。故I/O为主的作业对应的进程优先级高，而以计算为主的作业对应的进程优先级低。4.列举出操作系统向用户提供的接口方式。答：操作系统通过程序接口和操作接口两种方式把它的服务和功能提供给用户。程序接口又称应用编程接口，由一组系统调用（systemcall）组成，用户在编写的程序中使