名校操作系统历年考研试题(含解答)

1、名校操作系统考研试题与解答10.1北京大学1997年考研操作系统试题(一)名词术语解释(每小题5分,共30分)1.进程状态 2.快表 3.目录项4.系统调用 5.设备驱动程序 6.微内核(二)填空(每小题1分,共10分)1.如果系统中有n个进程,则在等待队列中进程的个数最多为_个。2.在操作系统中,不可中断执行的操作称为_。3.如果系统中的所有作业是同时到达的,则使作业平均周转时间最短的作业调度是_。4.如果信号量的当前值为-4,则表示系统中在该信号量上有_个等待进程。5.在有m个进程的系统中出现死锁时,死锁进程的个数k应该满足的条件是_。6.不让死锁发生的策略可以分为静态和动态两种,死锁避免

2、属于_。7.在操作系统中,一种用空间换取时间的资源转换技术是_。8.为实现CPU与外部设备的并行工作,系统引入了_硬件机制。9.中断优先级是由硬件规定的,若要调整中断的响应次序可通过_。10.若使当前运行的进程总是优先级最高的进程,应选择_进程调度算法。(三)问答题(每小题15分,共30分)1.消息缓冲通信技术是一种高级通信机制,由Hansen首先提出。(1)试述高级通信机制与低级通信机制P、V原语操作的主要区别。(2)请给出消息缓冲机制(有界缓冲)的基本原理。(3)消息缓冲通信机制(有界缓冲)中提供发送原语Send(receiver,a),调用参数a表示发送消息的内存区首地址,试设计相应的数

3、据结构,并用P、V原语操作实现Send原语。2.在虚拟段式存储系统中,引入了段的动态链接。(1)试说明为什么引入段的动态链接。(2)请给出动态链接的一种实现方法。(四)(共10分)在实现文件系统时,为加快文件目录的检索速度,可利用"文件控制块分解法"。假设目录文件存放在磁盘上,每个盘块为512字节。文件控制块占64字节,其中文件名占8字节。通常将文件控制块分解成两个部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。(1)假设某一目录文件共有254个文件控制块,试分别给出采用分解法前和分解法后,查找该目录文件的某一个文

4、件控制块的平均访问磁盘次数。(2)一般地,若目录文件分解前占用n个盘块,分解后改用m个盘块存放文件名和文件内部号部分,请给出访问磁盘次数减少的条件。(五)(共10分设系统中有三种类型的资源(A、B、C)和五个进程(P1、P2、P3、P4、P5),A资源的数量为17,B资源的数量为5,C资源的数量为20。在T0时刻系统状态如表1和表2所示。系统采用银行家算法实施死锁避免策略。T0时刻是否为安全状态? 若是,请给出安全序列。在T0时刻若进程P2请求资源(0,3,4),是否能实施资源分配? 为什么? 在的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配? 为什么?在的基础上,若进程请求资

5、源(0,2,0),是否能实施资源分配? 为什么?表1 T0时刻系统状态进程最大资源需求量已分配资源数量 A B C A B CP1P2P3P4P5 5 5 9 5 3 6 4 0 11 4 2 5 4 2 4 2 1 2 4 0 2 4 0 5 2 0 4 3 1 4表2 T0时刻系统状态A B C剩余资源数 2 3 3(六)(共10分)某高校计算机系开设有网络课并安排了上机实习,假设机房共有2m台机器,有2n名学生选该课,规定:每两个学生组成一组,各占一台机器,协同完成上机实习；只有一组两个学生到齐,并且此时机房有空闲机器时,该组学生才能进入机房；上机实习由一名教师检查,检查完毕,一组学生同

6、时离开机房。试用P、V操作模拟上机实习过程。北京大学1997年级研操作系统试题解答(一)名词术语解释(每小题5分,共30分)1.进程在其存在过程中,由于各进程并发执行及相互制约,使得它们的状态不断发生变化。一般来说进程主要有三种基本状态,这三种基本状态是:就绪状态、运行状态和阻塞状态。2.在页式存储管理系统中的地址变换过程中,由于页表是存放在内存中的,CPU每访问一个数据(或一条指令)至少要访问内存两次,一次是访问页表,确定所取数据(或指令)的物理地址,第二次才根据该地址访问数据(或指令)。为了提高查表速度,在地址变换机构中加入了一个高速、小容量的联想寄存器,构成一张快表。如果快表被命中,只要

7、访问内存一次即可存取一个数据。3.在文件系统中,文件目录记录文件的管理信息,每个文件在目录表中都有一个目录项。文件目录项主要包含下列信息:(1)有关文件的标识信息,例如文件的名称符号。(2)有关文件结构的信息,例如文件长度、文件存放在外存中的物理地址等。(3)有关文件的存取控制信息,例如文件属性、文件主及共享用户的标识、存取权限等。(4)有关文件的管理信息,例如文件建立的时间、保留时间、最新修改时间等。4.系统调用是用户在程序中能用"访管指令"调用的由操作系统提供的子功能的集合。每一个子功能称为一条系统调用命令(或广义指令)。系统调用是操作系统在程序级给用户提供的接口。系统

8、调用与一般过程调用不同,其主要区别是:运行的状态不同:进入的方式不同:代码层次不同。5设备驱动程序也称为I/O处理程序,是一种低级的系统例程,它向上与高级I/0操作原语相对应,向下与I/0硬设备相对应,完成两者间的相互通信。它们一般是用汇编语言编写,针对具体的I/0设备控制器,进行控制编码或微程序操作。设备驱动程序早期是操作系统的一部分,后来将其中的公共部分作为高级I/O操作原语留在操作系统中,而把与物理设备有直接关系的部分脱离操作系统,交给设备厂商和软硬件开发商编制。因此,设备驱动程序己成为系统的选件,系统和用户可以根据需要选择配置设备,灵活地装载、卸载驱动程序,从而极大地增强了系统的开放性

9、和可扩展性。6.操作系统有两种内核组织形式:强内核(Monolithic kernel)和微内核(Micro kernel)。微内核结构是一种新的结构组织形式,它体现了操作系统结构设计的新思想。其设计目标是使操作系统的内核尽可能小,使其它所有操作系统服务都放在核外用户级完成。微内核仅仅提供以下四种服务:进程间通信机制:某些存储管理:有限的低级进程管理和调度:低级I/0。微内核的基本思想是良好的结构化、模块化,最小的公共服务。具有微内核的操作系统称为微内核操作系统。(二)填空(每小题1分,共10分)1.n-1 2.原语 3.短作业优先算法 4.四 5.km6.动态策略 7.缓冲区技术 8.中断和

10、通道 9.软件实现 10.剥夺式优先级(三)问答题(每小题15分,共30分)1.(见西安交大2000年考题中第五题的解答)2.(1)在作业装入内存运行前,应将各个目标程序定位后装入作业的地址空间,形成可执行程序的链接,称为静态链接。静态链接常常因为目标程序个数多而花费大量的CPU时间,而实际运行时又常常只用到其中的部分模块,因而也造成了存储空间的浪费。动态链接是作业运行时先装入主程序,运行过程中需要某模块时,再将该模块的目标程序调入内存并进行链接,它克服了静态链接的不足。(2)分段存储管理就是最典型的动态链接。分段管理允许用户将作业按逻辑关系进行自然分段,各段的大小可以不同。逻辑段内的地址是由

11、两部分组成的(s: 段号,d：段内位移量),即分段地址空间是用户定义的二维空间。内存分配以段为单位,段可以在作业运行过程中根据请求而动态链接和装入。(四)(共10分)利用"文件控制块分解法"加快文件目录的检索速度,其原理是减少因查找文件内部号而产生的访问磁盘次数。因为在进行查找文件内部号的过程中不需要把文件控制块的所用内容都读入内存,所以在查找过程中减少所需读入的存储块就有可自色减少访问磁盘的次数。但是,采用这种方法访问文件,当找到匹配的文件控制块后,还需要访问一次磁盘,才能读出全部的文件控制块信息。这就是为何采用这种方法在一定条件下并不能减少访问磁盘的次数的原因。(1)采

12、用分解法前,查找该目录文件的某一个文件控制块的平均访问磁盘次数为:64×(254/2)/512=16采用分解法后,查找该目录文件的某一个文件控制块的平均访问磁盘次数为:10×(254/2)/512+1=4(2)访问磁盘次数减少的条件为 64×(x/2)/512 > 10×(x/2)/512+1，解不等式得x>=19时访问磁盘的次数减少。(五)(共10分)T0时刻是安全状态,因为可以找到一个安全的序列(P4,P5,Pl,P2,P3)。不能分配。因为所剩余的资源数量不够。可以分配。当分配完成后,系统剩余的资源向量为(0,3,2),这时仍可找到一个

13、安全的序列队, (P4,P5,Pl,P2,P3)。不能分配。若分配完成后,系统剩余的资源向量为(0,3,匀,这时无法找到一个安全的序列。(六)(共10分)在本题中,为了保证系统的控制流程,增加了Monitor进程,用于控制学生的进入和计算机分配。从题目本身来看,虽然没有明确写出这一进程,但实际上这一进程是存在的。因此,在解决这类问题时,需要对题目加以认真分析,找出其隐蔽的控制机制。上机实习过程可描述如下: BEGINstudent,computer,enter,finish,check:semaaphore; studen:=0;computer:=2m; mter:=0;finish :=O

14、;check :=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); 表示

15、检查完成goto L1;endProcess Procedure MonitorbeginL2: P(student); 等待学生到达P(student); 等待另一学生到达V(enter); 允许学生进入V(enter); 允许学生进入endCoendEND10.2西安交通大学1999年考研操作系统试题(一)名词解释(30分,每小题5分)1.多道程序设计 2.工作目录3.线程与进程 4.地址空间与存储空间5.通道 6.系统调用(二)判断、选择与填空题(每题1分,共15分)1.程序的并发执行是指同一时刻有两个以上的程序,它们的指令在同一处理器上执行。()2.对于请求分页式存储管理系统,若把页面

16、的大小增加一倍,则缺页中断次数会减少一半。()3.三个用户在同一系统上同时对他们的C语言源程序进行编译,此时系统应分别为各用户创建一个C编译进程及保留一份C编译程序副本。()4.可顺序存取的文件不一定能随机存取,但是,凡可随机存取的文件都可以顺序存取。()5.缓冲技术是借用外存储器的一部分区域作为缓冲池。()6.在操作系统中,P、V操作是一种_。(A)机器指令 (B)系统调用命令(C)作业控制命令 (D)低级进程通讯原语7.最佳适应算法的空白区是_。(A)按大小递减顺序排列的 (B)按大小递增顺序排列的(C)按地址由小到大排列的 (D)按地址由大到小排列的8.把作业地址空间中使用的逻辑地址变成

17、内存中的物理地址称为_。(A)加载 (B)重定位 (C)物理化 (D)逻辑化9.文件系统用_组织文件。(A)堆核 (B)指针 (C)目录 (D)路径10.磁盘是设备,磁带是设备,显示器是_设备。(A)输入 (B)输出 (C)输入输出 (D)虚拟11.并发进程中涉及相同变量的程序段叫做_,对这些程序段要执行_。12.分区存储管理方案不能实现虚拟的原因是_。13.目前认为逻辑文件有两种类型,即_式文件与_式文件。14.进程调度算法采用等时间片轮转法,时间片过大,就会使轮转法转化为_调度算法。15.采用交换技术获得的好处是以牺牲_为代价的。(三)简答题(每题10分,共50分)1.试述分时系统与实时系

18、统,并比较它们的区别。2.何谓虚拟存储器?举一例说明操作系统是如何实现虚拟内存的。3.什么是P、V操作? 试用P、V操作描述读者一写者问题。要求允许儿个阅读者可以同时读该数据集,而一个写者不能与其他进程(不管是写者还是读者)同时访问该数据集。4.磁盘请求的柱面按10,22,20,2,40,6,38的次序到达磁盘的驱动器,寻道时每个柱面移动需要6ms。计算按以下算法调度时的寻道时间:(1)先来先服务; (2)下一个最邻近的柱面; (3)电梯算法。以上所有情况磁头臂均起始于柱面20。5.对3种不同的保护机制,即权限,存取控制表以及UNIX操作系统的RWX位,简述下面的情况分别适用于哪些机制。(1)

19、甲用户希望除他的同事以外,任何人都能读取他的文件;(2)乙用户和丙用户希望共享某些秘密文件;(3)丁用户希望公开他的一些文件。西安交通大学1999年考研操作系统试题解答(一)名词解释(每小题5分,共30分)1.多道程序设计是指在主存中同时存放多道用户作业,它们都处于执行的开始点和结束点之间。多道程序设计的特点如下:(1)多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。(2)宏观上并行。从宏观上看,它们在同时执行。(3)微观上串行。从微观上看,它们在交替、穿插地执行。采用多道程序设计后,减少了CPU时间的浪费。尤其对计算题的作业,由于I/O操作较少,CPIJ浪费的时间

20、很少。2.文件系统如果采用多级树型目录,那么使用完整的路径名来查找文件会感到很不方便,因此引入了"工作目录"。考虑到通常一个进程在一段时间内所访问的文件具有局部性,即在某一范围之内,所以可在这一段时间内指定某一目录为工作目录或值班目录。以后的操作一般都是针对以工作目录(也称为当前目录)为根的子目录树进行的。3.所谓线程(thread),从操作系统的管理角度看,就是指"进程的一个可调度实体",是处理机调度的基本单位:从编程逻辑看,线程是指"程序内部的一个单一的顺序控制流"。线程是进程的一个组成部分,每个进程在创建时通常只有一个线程,由这

21、个线程再创建其它进程。通常一个进程都有若干个线程,至少会有一个线程。进程和线程是构造操作系统的两个基本元素,两者之间的主要区别是:(1)调度方面: 线程作为调度分派的基本单位。(2)并发性方面: 进程之间可以并发执行。(3)拥有资源方面: 进程是拥有资源的基本单位,线程除少量必不可少的资源外,基本上不拥有资源,但它可以访问其隶属进程的资源。(4)系统开销: 进程间切换时要涉及到进程环境的切换,开销比较大。而线程间的切换只需保存和设置少量的寄存器内容。因此进程问切换的系统开销远大于线程问切换的系统开销。4.程序经编译和连接以后转变为相对地址编址形式,它是以0为基址的。相对地址也叫逻辑地址或虚地址

22、。地址空间是逻辑地址的集合。计算机系统实际的内存地址是绝对地址。绝对地址又叫物理地址或实地址。存储空间是物理地址的集合。5.通道又称I/O处理机,它使主机摆脱了管理I/O的工作,彻底实现了主机和外设的并行操作。具有通道结构的计算机系统,主存、通道、控制器和设备之间采用四级连接,实施三级控制。这样,I/O系统就由通道、控制器、设备三级构成。一个CPU可以连接多个通道,一个通道可以连接多个控制器,一个控制器可以连接同类型的多台设各。另一方面,也允许将一台设备连接到几个控制器上,或一个控制器连接到几个通道上。按信息交换方式和连接的设备类型不同,可以将通道分为三种类型:(1)字节多路通道；(2)选择通

23、道；(3)数组多路通道 6.系统调用是用户在程序中能用"访管指令"调用的由操作系统提供的子功能的集合。每一个子功能称为一条系统调用命令或广义指令。系统调用是操作系统在程序级给用户提供的接口。(二)判断、选择与填空题(每题1分,共15分)1.错 2.错 3.错 4.对 5.错 6.(D)7.(B) 8.(B) 9.(C) 10.(C)和(D),(C),(B)11.临界区 互斥 12.作业的地址空间不能超过存储空间 13.有结构的记录 无结构的流 14.先来先服务(FCFS)15.CPU时间(三)简答题(每题10分,共50分)1.所谓分时系统,就是在一台计算机上,连接多个终端,

24、用户通过各自的终端和终端命令把作业送入计算机,计算机又通过终端向各用户报告其作业的运行情况,这种计算机能分时轮流地为各终端用户服务并能及时对用户服务请求予以响应,这就构成了分时系统。分时系统设计的主要目标是使用户能与系统交互作用,对用户的请求及时响应,并在可能的条件下尽量提高系统资源的利用率。实时系统是为了能对特定输入做出及时响应,并在规定的时间内完成对该事件的处理而引入的。实时系统分为两大类z实时控制系统和实时信息处理系统。(1)实时控制系统: 在这类应用中要求计算机系统实时采集测量系统的数据,对被测量的数据及时进行加工处理及输出。它主要用于军事和生产过程中的自动控制领域。(2)实时信息处理

25、系统：在这类应用中要求计算机系统能对用户的服务请求及时作出回答,并能及时修改、处理系统中的数据。它主要用于像飞机票的预定、银行储蓄的财务管理等大量数据处理的实时系统中。实时系统与分时系统的主要区别如下:系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统:而实时系统则大多数都是具有某种特殊用途的专用系统。响应时间的长短不同。分时系统的响应时间通常为秒级:而实时系统的响应时间通常为毫秒级甚至是微秒级。交互性的强弱不同。分时系统的交互性强,而实时系统的交互性相对较弱。2.在操作系统中,通过一些硬件和软件的措施为用户提供了一个其容量比实际主存大得多的存储器,称为虚拟

26、存储器。操作系统要实现虚拟内存,必须把主存和辅存统一管理起来,即大作业程序在执行时,有一部分地址空间在主存,另一部分在辅存,当访问的信息不在主存时,由操作系统将其调入主存并实现自动覆盖功能,使用户在编写程序时不再受主存容量的限制。例如在请求分页存储管理系统中,用户作业的所有页面并不一定都在实存,在作业运行过程中再请求调入所用的虚页。为了实现从逻辑地址空间到物理地址空间的变换,在硬件上必须提供一套地址变换机构,动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地址两部分,并利用页表将页号代之以块号,把块号和页内地址拼接就得到了内存的物理地址,从而实现了虚拟存储器。3.读者一写者问题是经常出现

27、的一种同步问题。计算机系统中的数据(文件、记录)常被多个进程共享,但其中某些进程可能只要求读数据(称为Reader):另一些进程则要求修改数据(称为Writer)。就共享数据而言,Reader和Writer是两种不同类型的进程。一般地,两个或两个以上的Reader进程同时访问共享数据时不会产生副作用,但若某个Writer和其它进程(Reader或Writer)同时访问共享数据时,则可能产生错误。为了避免错误,同时尽可能地让读者进程和写者进程并发运行,只要保证任何一个写者进程能与其它进程互斥访问共享数据即可。这个问题称为读者一写者问题。下面使用信号量机构来描述这一问题。P、V操作是定义在信号量s

28、上的两条原语,它是解决进程同步与互斥的有效手段。定义下列信号量: 互斥信号量rmutex,初值为1,用于使读者互斥地访问读者计数器,共享变量rcount: 互斥信号量wmutex,初值为1,用于实现写者之间以及写者与读者之间互斥地访问共享数据集。则用信号量和P、V操作描述读者一写者问题如下:Beginrmutex wmutex:semaphore;rcount:Integer;rmutex=wmutex=1;rcount=0;CobeginProcess procedure Readerbeginrepeat P(rmutex);rcount:=rcount+1if rcount=l then

29、 P(rmutex);V(rmutex);perfonn read operations;P(rmutex);rcount:=rcount-1;if rcount=O then V(rmutex);V(rmutex);until fa1se;endProcess procedure Writerbeginrepeat P(wmutex);perform write operations;V(wmutex);until false;endCoendEnd4.该题的解题方法是先计算出每种算法的柱面移动总量。因为每个柱面移动需要6ms,所以,寻道时间=柱面移动总量×6ms。(1)先到先服务

30、算法的调度顺序为:10,22,20,2,40,6,38柱面移动总量为:146寻道时间为:146×6ms=876ms(2)下一个最邻近柱面算法调度顺序为:20,22,10,6,2,38,40柱面移动总量为:60寻道时间为:60×6ms=360ms(3)电梯算法调度顺序为:20,22,38,40,10,6,2柱面移动总量为:58寻道时间为58×6ms=348ms5.第(1)种情况只适合用存取控制表实现保护机制。第(2)种情况适合用权限或存取控制表实现保护机制。第(3)种情况适合用存取控制表或RWX位或权限实现保护机制。10.3西安交通大学2000年考研操作系统试题(一

31、)名词解释(15分)1.线程 2.分时系统 3.系统调用4.地址再定位 5.多道程序设计(二)简答题(32分) 1.覆盖技术与虚拟存储技术有何本质不同?交换技术与虚存中使用的调入/调出技术有何相同与不同之处?2.文件顺序存取与随机存取的主要区别是什么?它们对有结构文件与无结构文件的操作有何不同?3.死锁和竞争有何关系? 4.何请虚拟设备? 请说明SPOOLing系统是如何实现虚拟设备的。(三)(10分)有5个任务A,B,C,D,E,它们几乎同时到达,预计它们的运行时间为10,6,2,4,8mn。其优先级分别为3,5,2,1和4,这里5为最高优先级。对于下列每一种调度算法,计算其平均进程周转时间

32、(进程切换开销可不考虑)。(1)先来先服务(按A,B,c,D,E)算法。(2)优先级调度算法。(3)时间片轮转算法。(四)(10分)在虚拟页式存储系统中引入了缺页中断。1.试说明为什么引入缺页中断。2.缺页中断的实现由哪几部分组成?并分别给出其实现方法。(五)(13分)消息缓冲通信技术是一种高级通信机制,由HANSEN首先提出。1.试叙述高级通信机制与低级通信机制P、V原语操作的区别。2.请给出消息缓冲通信机制(有界缓冲)的基本工作原理。3.试设计相应的数据结构,并用P、V原语操作实现Send和Receive原语。西安交通大学2000年考研操作系统试题解答(一)名词解释(15分)1.所谓线程(

33、thread),从操作系统管理角度看线程是指"进程的一个可调度实体",是处理机调度的基本单位: 从编程逻辑看线程是指"程序内部的一个单一的顺序控制流"。线程是进程的一个组成部分。2.所谓分时系统,就是指在一台计算机上,连接多个终端,用户通过各自的终端和终端命令把作业送入计算机,计算机又通过终端向各用户报告其作业的运行情况。这种计算机能分时轮流地为各终端用户服务并能及时对用户服务请求予以响应,这就构成了分时系统。分时系统设计的主要目标是使用户能与系统交互作用,对用户的请求及时响应,并在可能的条件下尽量提高系统资源的利用率。分时系统的主要特征是:同时性:若干

34、个终端用户按照系统提供的各种服务,在各自终端进行操作,同时使用一台计算机资源。宏观上看是各用户在并行工作,微观上看是各用户轮流使用计算机。独立性:用户间可以相互独立地操作,互不干涉,系统保证各用户程序运行的完整性,不会发生相互混淆或破坏现象。及时性:系统可对用户的输入及时作出响应。分时系统性能的主要指标之一是响应时间,它是指从终端发出命令到系统予以应答所需的时间。交互性:用户可根据系统对请求的响应结果,进一步向系统提出新的请求,即能使用户和系统进行人一机对话的工作方式,所以分时系统也被称之为交互式系统。3.系统调用是指用户在程序中能用"访管指令"调用的由操作系统提供的子功能

35、的集合。每一个子功能称为一条系统调用命令(或广义指令)。系统调用是操作系统在程序级给用户提供的接口。4.所谓地址再定位,就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程,即将地址空间给出的逻辑地址映射到内存的物理地址。地址重定位有静态重定位和动态重定位两种方式。5.多道程序设计是指在主存中同时存放多道用户作业,它们都处于执行的开始点和结束点之间。多道程序设计的特点如下:(1)多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。(2)宏观上并行。从宏观上看,它们在同时执行。(3)微观上串行。从微观上看,它们在交替、穿插地执行。采用多道程序设计后,减少了

36、CPU时间的浪费。尤其对计算题的作业,由于I/O操作较少,CPU浪费的时间很少。(二)简答题(32分)1.覆盖技术与虚拟存储技术最本质的不同在于覆盖的程序段的最大长度要受到物理内存容量的限制,而虚拟存储器的最大长度不受物理内存容量的限制,只受计算机地址结构的限制。另外,使用覆盖技术要求程序员必须精心地设计程序及其数据结构,使得要覆盖的段具有相对独立性,不存在直接联系或相互交叉访问。而虚拟存储技术对用户的程序段之间没有此要求。交换技术与虚存中使用的调入/调出技术的主要相同点是都要在内存与外存之间交换信息。交换技术与虚存中使用的调入/调出技术的主要区别在于:交换技术换进换出整个进程(proc结构和

37、共享正文段除外,因此一个进程的大小受物理存储器的限制:而虚存中使用的调入/调出技术在内存和外存之间来回传递的是存储页或存储段,而不是整个进程,从而使得进程的地址映射具有了更大的灵活性,且允许进程的大小比可用的物理存储空间大得多。2.顺序存取法就是严格按物理记录排列的顺序依次存取:随机存取法允许随意存取文件中的任何一个物理记录,而不管上次存取了哪一个记录。顺序存取法对有结构文件的操作是设置一个访问指针ptr,令它总是指向"下一次"要访问的记录首址。每访问完一个记录后,对ptr住进行相应的修改。对于定长记录:ptr=ptr+L(L为文件的物理记录长度):对于变长记录:Ptr=p

38、tr+Li+1(其中1是存放记录长度Li的字节数)。顺序存取法对无结构文件的操作是按读写位移(offset)从当前位置开始读写,即每读写完一段信息后,读写位移自动力日上这段的长度,然后再根据该位移读写下面的信息。随机存取法对有结构文件的操作也是设置一个访问指针pt,对于定长记录文件,欲访问第I个记录。(I=0,1,2,)的首址为: ptr=offset+I*L(其中,offest是该文件的首址,L为记录长度):对于变长记录,随机存取法是十分低效的。随机存取法对无结构文件的操作必须事先用有关的命令把读写位移移到欲读写的信息开始处,然后再进行读写。3.死锁是指多个进程因竞争资源而造成的一种僵局,若

39、无外力的作用,这些进程都将永远不能再向前推进。所以,死锁是由于系统中多个进程所共享的资源不足以同时满足需要时,引起对资源的竞争而产生的。但竞争资源不定都会产生死锁,因为只要进程推进顺序合法,就不会产生死锁。4.所谓虚拟设备,是指利用SPOOLing系统把低速的独占设备改造成为共享的设备,或利用软件方法把共享的设备分割为若干台虚拟设备。SPOOLing系统的核心思想是利用一台可共享的、高速大容量的块设备(磁盘)来模拟独占设各的操作,使一台独占设备变成多台可并行使用的虚拟设备。SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的特点是提高了I/O操作

40、的速度:将独占设备改造为共享设备;实现了虚拟设备功能。(三)(10分)(1)采用FCFS的调度算法时,各任务在系统中的执行情况如下表所示:执行次序运行时间优先数等待时间周转时间A103010B651016C221618D411822E842230所以,进程的平均周转时间为:T=(10+16+18+22+3O)/5=19.2 min(2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示:执行次序运行时间优先数等待时间周转时间B6506E84614A1031424C222426D112627所以,进程的平均周转时间为:T=(6+14+24+26+27)/5=19.4 min(3)采用时间片

41、轮转算法时,假定时间片为2min,各任务的执行情况是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。设AE五个进程的周转时间依次为T1T5,显然,T1=3Omin, T2=22min, T3=6min,T4=16min,T5=28min所以,进程的平均周转时间为:T=(30+22+6+16+28)/5=20.4min(四)(10分)1.因为虚拟页式存储系统中允许作业的一部分页面在内存,只有引入缺页中断,才能将不在内存的信息页从外存调入内存,中断恢复后可以继续执行。2.缺页中断的实现由硬件和软件两部分组成。其实现方法如下:每当CPU要执行一条指令时,首先形成操作

42、数的有效地址,在计算页号和页内地址,检查页表看该页在实存吗。如在,则进行地址变换,按变换后的地址取出操作数,完成该指令的功能,然后继续进行下一条指令; 如不在,则引起缺页中断,进入缺页中断处理程序。在中断处理程序中,首先利用存储器分块表(MBT)检查实存是否有空闲页面,如无,则选择某页淘汰。若该页被修改过还需写入辅存,并修改PMT和MBT,此时便出现了空闲实页。如有空闲实页,则根据辅助页表提供的磁盘地址调入所需的页面,修改PMT和MBT。最后再重新执行被中断的指令。(五)(13分)1.高级通信机制与低级通信机制P、V原语操作的主要区别是:(1)交换信息量方面:利用p、v原语操作作为进程间的同步

43、互斥工具是理想的,但进程间只能交换一些信息,基本上只能是控制信息,缺乏传输消息的能力。而高级通信不仅能较好地解决进程间的同步互斥问题,且能很好交换大量消息,是理想的进程通信工具。(2)通信对用户透明方面:用户要用P、V原语进行进程间的通信必须在程序中增加p、V编程,这样做不但增加了编程的复杂性,不便对程序有直观的理解,同时由于编程不当,有可能出现死锁,难以查找其原因。而高级通信机制不但能高效传输大量信息,且操作系统隐藏了进程通信的实现细节,即通信过程对用户是透明的。这样就大大地简化了通信程序编制上的复杂性。2.所谓消息(Message),是指一组信息,消息缓冲区是含有如下信息的缓冲区:指向发送

44、进程的指针:Sptr指向下一信息缓冲区的指针:Nptr;消息长度: Size;消息正文: Text;消息缓冲通信机制的基本工作原理是:把消息缓冲区作为进程通讯的一个基本单位,为了实现进程之间的通讯,系统提供了发送原语Send(A)和接收原语Receive(B)。每当发送进程欲发送消息时,发送进程用Send(A)原语把欲发送的消息从发送区复制到消息缓冲区,并将它挂在接收进程的消息队列末尾。如果该接收进程因等待消息而处于阻塞状态,则将其换醒。而每当接收进程欲读取消息时,就用接收原语Receive(B)从消息队列头取走一个消息放到自己的接收区。3.消息缓冲通信机制中,消息队列属于临界资源,故在PCB

45、中设置了一个用于互斥的信号量mutex,而每当有进程要进入消息队列时,应对信号量mutex施行P操作,退出消息队列后,应对信号量mutex施行V操作。由于接受进程可能会收到几个进程发来的消息,故应将所有的消息缓冲区链成一个队列,其队头由接收进程PCB中的队列头指针Hptr指出。为了表示队列中的消息的数目,在PCB中设置了信号量旬,每当发送进程发来一个消息,并将它挂在接收进程的消息队列上时,便在Sn上执行V操作:而每当接收进程从消息队列上读取一个消息时,先对Sn执行P操作,再从队列上移出要读取的消息。用P、V原语操作实现Send原语和Receive原语的处理流程如下:Procedure Send

46、(receiver,Ma) 发送原语begingetbuf(Ma, size,i); 申请消息缓冲区i.sender:=Ma.Sender; 将发送区的信息发送到消息缓冲区i.size:=Ma.Size;i.text:=Ms.text;i.next:=0;getid(PCB set,receive,j); 获得接收进程的内部标识符P(j.mutex);insert(j.Hptr,i); 消息缓冲区插入到消息队列首V(j.Sn);V(j.mutex); endProcedure Receive(Mb) 接收原语 beginj:internal name; 接收进程内部标识符P(j.Sn);P(j

47、.mutex);remove(j.Hptr,i); 从消息队列中移出第一个消息V(j.mutex);Mb.Sender:=i.Sender; 将消息缓冲区中的信息复制到接收区Mb.Size:=i.Size:Mb.text:=i.text:End10.4 西安电子科技大学2000年考研操作系统试题(一)单项选择题(10分)1.分页式虚拟存储管理系统中,一般来说页面的大小与可能产生缺页中断的次数_。A.成正比 B.成反比 C.无关 D.成固定比值2.实时操作系统必须在_内完成来自外部的事件。A.响应时间 B.周转时间 C.规定时间 D.调度时间3.早期UNIX操作系统的存储管理采用_方案。A.段式

48、管理 B.请求分页C.可变式分区管理 D.固定式分区管理4.在下列语言中属于脱机作业控制语言的是_。A.作业控制语言 B.汇编语言C.会话式程序设计语言 D.解释BASIC语言5.MS-DOS中的文件物理结构采用_。A.连续结构 B.链接结构 C.索引结构 D.哈希表6.在请求分页存储管理方案中,如果所需的页面不在内存中,则产生缺页中断,它属于_中断。A.硬件故障 B.I/O C.外 D.程序中断7.设有四个作业同时到达,每个作业的执行时间均为2小时,它们在一台处理机上按单道方式运行,则平均周转时间为_。A.1小时 B.5小时 C.2.5小时 D.8小时8.在关于SPOOLING的叙述中,_描

49、述是不正确的。A.SPOOLING系统中不需要独占设备B.SPOOLING系统加快了作业执行的速度C.SPOOLING系统使独占设备变成共享设备D.SPOOLBNG系统利用了处理器与通道并行工作的能力。9.页式虚拟存储管理的主要特点是_。A.不要求将作业装入到主存的连续区域 B.不要求将作业同时全部装入到主存的连续区域C.不要求进行缺页中断处理D.不要求进行页面置换10.下列文件中属于逻辑结构的文件是A.连续文件 B.系统文件 C.散列文件 D.流式文件(二)改错题(对错误的命题,请说明原因)(10分)1.采用多道程序设计的系统中,系统的程序道数越多,系统的效率就越高。2.特权指令只能在管态下

50、执行,而不能在算态下执行。3.采用资源的静态分配算法可以预防死锁的发生。4.一个虚拟的存储器,其地址空间的大小等于辅存的容量加上主存的容量。5.一个作业由若干个作业步组成,在多道程序设计的系统中这些作业步可以并发执行。6.作业调度是处理机的高级调度,进程调度是处理机的低级调度。7.I/O交通管理程序的主要功能是管理主存、控制器和通道。8.移臂调度的目标是使磁盘旋转周数最小。9.进程是一个独立的运行单位,也是系统进行资源分配和调度的基本单位。10.作业的联机控制方式适用于终端作业。(三)、填空题(9分)1.UNIX操作系统在结构上分为两个部分:_和_。2.把作业装入内存中随即进行地址变换的方式称

51、为_,而在作业执行期间,当访问到指令或数据时才进行地址变换的方式称为_。3.死锁产生的四个必要条件是:互斥控制、_、_、_。4.多道程序设计的引入给存储管理提出了新的课题,应考虑的三个问题是_、_、_。5.在存储管理方案中,可用上下限地址寄存器存储保护的是_。6.在UNIX文件管理系统中,为了对磁盘空间的空闲块进行有效的管理,采用的方法_。7.为了记录设备的分配情况,操作系统应设置一张_和三个控制块: 设备控制块、_、_。8.I/O设备处理进程平时处于_状态,当_和_出现时被唤醒。(四)综合题(21分)1.什么叫"可再入"程序? 它有什么特征?2.简述UNIX的进程调度的公

52、式和算法。3.给出UNDE进程的调度状态,当子进程终止时,处于什么状态?4.假设有4个记录A、B、C、D存放在磁盘的某个磁道上,该磁道划分为4块,每块存放一个记录,安排如下表所示:块号 1 2 3 4记录号 A B C D现在要顺序处理这些记录,如果磁盘旋转速度为2Oms转一周,处理程序每读出一个记录后花5ms的时间进行处理。试问处理完这4个记录的总时间是多少?为了缩短处理时间应进行优化分布,试问应如何安排这些记录?并计算处理的总时间。5.有一个理发师,一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发椅子上睡觉:当一个顾客到来时,必须唤醒理发师,进行理发；如果理发师正在

53、理发时,又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和顾客各编一段程序描述他们的行为,要求不能带有竞争条件。西安电子科技大学2000考研操作系统试题答案(一)单项选择题(10分)1.B 2.C 3.C 4.A 5.B 6.D 7.B 8.C 9.B 10.D(二)改错题(对错误的命题,请说明原因)(10分)1.错,系统的程序道数越多,并不能说明效率就越高。2.对3.对4.错,虚存大小与地址总线的位数有关。5.错,作业之间并发执行。6.对 7.错,I/0交通管理程序管理设备、控制器、通道的全部状态信息等,但它不管理主存。8.错,移臂调度以减少移臂时间为目的。9.对10.对(三)填空题（9分)1.外壳 内核2.静态地址再定位 动态地址再定位3.非剥夺控制 零散请求 环路条件4.存储器分配 虚存管理 存储保护5.分区分配6.成组连接法7