名校操作系统考研试题与解答10.1北京大学1997年考研操作系统试题(一)名词术语解释(每小题5分,共30分)1.进程状态2.快表3.目录项4.系统调用5.设备驱动程序6.微内核(二)填空(每小题1分,共10分)1.如果系统中有n个进程,则在等待队列中进程的个数最多为________个。
2.在操作系统中,不可中断执行的操作称为_________。
3.如果系统中的所有作业是同时到达的,则使作业平均周转时间最短的作业调度是_________。
4.如果信号量的当前值为-4,则表示系统中在该信号量上有________个等待进程。
5.在有m个进程的系统中出现死锁时,死锁进程的个数k应该满足的条件是_________。
6.不让死锁发生的策略可以分为静态和动态两种,死锁避免属于_________。
7.在操作系统中,一种用空间换取时间的资源转换技术是_________。
8.为实现CPU与外部设备的并行工作,系统引入了__________硬件机制。
9.中断优先级是由硬件规定的,若要调整中断的响应次序可通过_________。
10.若使当前运行的进程总是优先级最高的进程,应选择________进程调度算法。
(三)问答题(每小题15分,共30分)1.消息缓冲通信技术是一种高级通信机制,由Hansen首先提出。
(1)试述高级通信机制与低级通信机制P、V原语操作的主要区别。
(2)请给出消息缓冲机制(有界缓冲)的基本原理。
(3)消息缓冲通信机制(有界缓冲)中提供发送原语Send(receiver,a),调用参数a表示发送消息的内存区首地址,试设计相应的数据结构,并用P、V原语操作实现Send原语。
2.在虚拟段式存储系统中,引入了段的动态链接。
(1)试说明为什么引入段的动态链接。
(2)请给出动态链接的一种实现方法。
(四)(共10分)在实现文件系统时,为加快文件目录的检索速度,可利用"文件控制块分解法"。
假设目录文件存放在磁盘上,每个盘块为512字节。
文件控制块占64字节,其中文件名占8字节。
通常将文件控制块分解成两个部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。
(1)假设某一目录文件共有254个文件控制块,试分别给出采用分解法前和分解法后,查找该目录文件的某一个文件控制块的平均访问磁盘次数。
(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),是否能实施资源分配? 为什么?④在③的基础上,若进程请求资源(0,2,0),是否能实施资源分配? 为什么?(六)(共10分)某高校计算机系开设有网络课并安排了上机实习,假设机房共有2m台机器,有2n名学生选该课,规定:①每两个学生组成一组,各占一台机器,协同完成上机实习；②只有一组两个学生到齐,并且此时机房有空闲机器时,该组学生才能进入机房；③上机实习由一名教师检查,检查完毕,一组学生同时离开机房。
试用P、V操作模拟上机实习过程。
北京大学1997年级研操作系统试题解答(一)名词术语解释(每小题5分,共30分)1.进程在其存在过程中,由于各进程并发执行及相互制约,使得它们的状态不断发生变化。
一般来说进程主要有三种基本状态,这三种基本状态是:就绪状态、运行状态和阻塞状态。
2.在页式存储管理系统中的地址变换过程中,由于页表是存放在内存中的,CPU每访问一个数据(或一条指令)至少要访问内存两次,一次是访问页表,确定所取数据(或指令)的物理地址,第二次才根据该地址访问数据(或指令)。
为了提高查表速度,在地址变换机构中加入了一个高速、小容量的联想寄存器,构成一张快表。
如果快表被命中,只要访问内存一次即可存取一个数据。
3.在文件系统中,文件目录记录文件的管理信息,每个文件在目录表中都有一个目录项。
文件目录项主要包含下列信息:(1)有关文件的标识信息,例如文件的名称符号。
(2)有关文件结构的信息,例如文件长度、文件存放在外存中的物理地址等。
(3)有关文件的存取控制信息,例如文件属性、文件主及共享用户的标识、存取权限等。
(4)有关文件的管理信息,例如文件建立的时间、保留时间、最新修改时间等。
4.系统调用是用户在程序中能用"访管指令"调用的由操作系统提供的子功能的集合。
每一个子功能称为一条系统调用命令(或广义指令)。
系统调用是操作系统在程序级给用户提供的接口。
系统调用与一般过程调用不同,其主要区别是:①运行的状态不同:②进入的方式不同:③代码层次不同。
5．设备驱动程序也称为I/O处理程序,是一种低级的系统例程,它向上与高级I/0操作原语相对应,向下与I/0硬设备相对应,完成两者间的相互通信。
它们一般是用汇编语言编写,针对具体的I/0设备控制器,进行控制编码或微程序操作。
设备驱动程序早期是操作系统的一部分,后来将其中的公共部分作为高级I/O操作原语留在操作系统中,而把与物理设备有直接关系的部分脱离操作系统,交给设备厂商和软硬件开发商编制。
因此,设备驱动程序己成为系统的选件,系统和用户可以根据需要选择配置设备,灵活地装载、卸载驱动程序,从而极大地增强了系统的开放性和可扩展性。
6.操作系统有两种内核组织形式:强内核(Monolithic kernel)和微内核(Micro kernel)。
微内核结构是一种新的结构组织形式,它体现了操作系统结构设计的新思想。
其设计目标是使操作系统的内核尽可能小,使其它所有操作系统服务都放在核外用户级完成。
微内核仅仅提供以下四种服务:①进程间通信机制:②某些存储管理:③有限的低级进程管理和调度:④低级I/0。
微内核的基本思想是良好的结构化、模块化,最小的公共服务。
具有微内核的操作系统称为微内核操作系统。
(二)填空(每小题1分,共10分)1.n-12.原语3.短作业优先算法4.四5.k≤m6.动态策略7.缓冲区技术8.中断和通道9.软件实现 10.剥夺式优先级(三)问答题(每小题15分,共30分)1.(见西安交大2000年考题中第五题的解答)2.(1)在作业装入内存运行前,应将各个目标程序定位后装入作业的地址空间,形成可执行程序的链接,称为静态链接。
静态链接常常因为目标程序个数多而花费大量的CPU时间,而实际运行时又常常只用到其中的部分模块,因而也造成了存储空间的浪费。
动态链接是作业运行时先装入主程序,运行过程中需要某模块时,再将该模块的目标程序调入内存并进行链接,它克服了静态链接的不足。
(2)分段存储管理就是最典型的动态链接。
分段管理允许用户将作业按逻辑关系进行自然分段,各段的大小可以不同。
逻辑段内的地址是由两部分组成的(s: 段号,d：段内位移量),即分段地址空间是用户定义的二维空间。
内存分配以段为单位,段可以在作业运行过程中根据请求而动态链接和装入。
(四)(共10分)利用"文件控制块分解法"加快文件目录的检索速度,其原理是减少因查找文件内部号而产生的访问磁盘次数。
因为在进行查找文件内部号的过程中不需要把文件控制块的所用内容都读入内存,所以在查找过程中减少所需读入的存储块就有可自色减少访问磁盘的次数。
但是,采用这种方法访问文件,当找到匹配的文件控制块后,还需要访问一次磁盘,才能读出全部的文件控制块信息。
这就是为何采用这种方法在一定条件下并不能减少访问磁盘的次数的原因。
(1)采用分解法前,查找该目录文件的某一个文件控制块的平均访问磁盘次数为: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,P l,P2,P3)。
②不能分配。
因为所剩余的资源数量不够。
③可以分配。
当分配完成后,系统剩余的资源向量为(0,3,2),这时仍可找到一个安全的序列队, (P4,P5,P l,P2,P3)。
④不能分配。
若分配完成后,系统剩余的资源向量为(0,3,匀,这时无法找到一个安全的序列。
(六)(共10分)在本题中,为了保证系统的控制流程,增加了Monitor进程,用于控制学生的进入和计算机分配。
从题目本身来看,虽然没有明确写出这一进程,但实际上这一进程是存在的。
因此,在解决这类问题时,需要对题目加以认真分析,找出其隐蔽的控制机制。
上机实习过程可描述如下:BEGINstudent,computer,enter,finish,check:semaaphore;studen:=0;computer:=2m;mter:=0;finish :=O;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); {表示检查完成}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.程序的并发执行是指同一时刻有两个以上的程序,它们的指令在同一处理器上执行。