名校操作系统考研试题与解答
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-1
2.原语
3.短作业优先算法
4.四
5.k≤m
6.动态策略
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进程,用于控制学生的进入和计算机分配。从题目本身来看,虽然没有明确写出这一进程,但实际上这一进程是存在的。因此,在解决这类问题时,需要对题目加以认真分析,找出其隐蔽的控制机制。
上机实习过程可描述如下:
BEGIN
student,computer,enter,finish,check:semaaphore;
studen:=0;
computer:=2m;
mter:=0;
finish :=O;
check :=0;
COBEGIN
Process Procedure Student:
begin
V(student); {表示有学生到达}
P(computer); {获取一台计算机}
P(enter); {等待允许进入}
DO it with partner;
V(finish); {表示实习完成}
P(check); {等待教师检查}
V(computer); {释放计算机资源}
end
Process Procedure Teacher:
begin
L1:P(finished); {等待学生实习完成}
P(finished); {等待另一学生实习完成}
check the work;
V(check); {表示检查完成}
V(check); {表示检查完成}
goto L1;
end
Process Procedure Monitor
begin
L2: P(student); {等待学生到达}
P(student); {等待另一学生到达}
V(enter); {允许学生进入}
V(enter); {允许学生进入}
end
Coend
END
10.2西安交通大学1999年考研操作系统试题
(一)名词解释(30分,每小题5分)
1.多道程序设计
2.工作目录
3.线程与进程
4.地址空间与存储空间
5.通道
6.系统调用
(二)判断、选择与填空题(每题1分,共15分)
1.程序的并发执行是指同一时刻有两个以上的程序,它们的指令在同一处理器上执行。()
2.对于请求分页式存储管理系统,若把页面的大小增加一倍,则缺页中断次数会减少一半。()
3.三个用户在同一系统上同时对他们的C语言源程序进行编译,此时系统应分别为各用户创建一个C编译进程及保留一份C编译程序副本。()
4.可顺序存取的文件不一定能随机存取,但是,凡可随机存取的文件都可以顺序存取。()
5.缓冲技术是借用外存储器的一部分区域作为缓冲池。()
6.在操作系统中,P、V操作是一种_______。
(A)机器指令 (B)系统调用命令
(C)作业控制命令 (D)低级进程通讯原语
7.最佳适应算法的空白区是_______。
(A)按大小递减顺序排列的 (B)按大小递增顺序排列的
(C)按地址由小到大排列的 (D)按地址由大到小排列的
8.把作业地址空间中使用的逻辑地址变成内存中的物理地址称为_______。
(A)加载 (B)重定位 (C)物理化 (D)逻辑化
9.文件系统用___组织文件。
(A)堆核 (B)指针 (C)目录 (D)路径
10.磁盘是设备,磁带是设备,显示器是________设备。
(A)输入 (B)输出 (C)输入输出 (D)虚拟
11.并发进程中涉及相同变量的程序段叫做_______,对这些程序段要执行_______。
12.分区存储管理方案不能实现虚拟的原因是___________。
13.目前认为逻辑文件有两种类型,即_________式文件与________式文件。
14.进程调度算法采用等时间片轮转法,时间片过大,就会使轮转法转化为_______调度算法。
15.采用交换技术获得的好处是以牺牲__________为代价的。
(三)简答题(每题10分,共50分)
1.试述分时系统与实时系统,并比较它们的区别。
2.何谓虚拟存储器?举一例说明操作系统是如何实现虚拟内存的。
3.什么是P、V操作? 试用P、V操作描述读者一写者问题。要求允许儿个阅读者可以同时读该数据集,而一个写者不能与其他进程(不管是写者还是读者)同时访问该数据集。
4.磁盘请求的柱面按10,22,20,2,40,6,38的次序到达磁盘的驱动器,寻道时每个柱面移动需要6ms。计算按以下算法调度时的寻道时间:
(1)先来先服务; (2)下一个最邻近的柱面; (3)电梯算法。
以上所有情况磁头臂均起始于柱面20。
5.对3种不同的保护机制,即权限,存取控制表以及UNIX操作系统的RWX位,简述下面的情况分别适用于哪些机制。
(1)甲用户希望除他的同事以外,任何人都能读取他的文件;
(2)乙用户和丙用户希望共享某些秘密文件;
(3)丁用户希望公开他的一些文件。
西安交通大学1999年考研操作系统试题解答
(一)名词解释(每小题5分,共30分)
1.多道程序设计是指在主存中同时存放多道用户作业,它们都处于执行的开始点和结束点之间。多道程序设计的特点如下:
(1)多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。
(2)宏观上并行。从宏观上看,它们在同时执行。
(3)微观上串行。从微观上看,它们在交替、穿插地执行。
采用多道程序设计后,减少了CPU时间的浪费。尤其对计算题的作业,由于I/O操作较少,CPIJ
浪费的时间很少。
2.文件系统如果采用多级树型目录,那么使用完整的路径名来查找文件会感到很不方便,因此引入了"工作目录"。考虑到通常一个进程在一段时间内所访问的文件具有局部性,即在某一范围之内,所以可在这一段时间内指定某一目录为工作目录或值班目录。以后的操作一般都是针对以工作目录(也称为当前目录)为根的子目录树进行的。
3.所谓线程(thread),从操作系统的管理角度看,就是指"进程的一个可调度实体",是处理机调度的基本单位:从编程逻辑看,线程是指"程序内部的一个单一的顺序控制流"。
线程是进程的一个组成部分,每个进程在创建时通常只有一个线程,由这个线程再创建其它进程。通常一个进程都有若干个线程,至少会有一个线程。
进程和线程是构造操作系统的两个基本元素,两者之间的主要区别是:
(1)调度方面: 线程作为调度分派的基本单位。
(2)并发性方面: 进程之间可以并发执行。
(3)拥有资源方面: 进程是拥有资源的基本单位,线程除少量必不可少的资源外,基本上不拥有资源,但它可以访问其隶属进程的资源。
(4)系统开销: 进程间切换时要涉及到进程环境的切换,开销比较大。而线程间的切换只需保存和设置少量的寄存器内容。因此进程问切换的系统开销远大于线程问切换的系统开销。4.程序经编译和连接以后转变为相对地址编址形式,它是以0为基址的。相对地址也叫逻辑地址或虚地址。地址空间是逻辑地址的集合。
计算机系统实际的内存地址是绝对地址。绝对地址又叫物理地址或实地址。存储空间是物理地址的集合。
5.通道又称I/O处理机,它使主机摆脱了管理I/O的工作,彻底实现了主机和外设的并行操作。具有通道结构的计算机系统,主存、通道、控制器和设备之间采用四级连接,实施三级控制。这样,I/O系统就由通道、控制器、设备三级构成。一个CPU可以连接多个通道,一个通道可以连接多个控制器,一个控制器可以连接同类型的多台设各。另一方面,也允许将一台设备连接到几个控制器上,或一个控制器连接到几个通道上。按信息交换方式和连接的设备类型不同,可以将通道分为三种类型:
(1)字节多路通道；(2)选择通道；(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.所谓分时系统,就是在一台计算机上,连接多个终端,用户通过各自的终端和终端命令把作业送入计算机,计算机又通过终端向各用户报告其作业的运行情况,这种计算机能分时轮流地为各终端用户服务并能及时对用户服务请求予以响应,这就构成了分时系统。分时系统设计的主要目标是使用户能与系统交互作用,对用户的请求及时响应,并在可能的条件下尽量提高系统资源的利用率。
实时系统是为了能对特定输入做出及时响应,并在规定的时间内完成对该事件的处理而引入的。实时系统分为两大类z实时控制系统和实时信息处理系统。
(1)实时控制系统: 在这类应用中要求计算机系统实时采集测量系统的数据,对被测量的数据及时进行加工处理及输出。它主要用于军事和生产过程中的自动控制领域。
(2)实时信息处理系统：在这类应用中要求计算机系统能对用户的服务请求及时作出回答,并能及时修改、处理系统中的数据。它主要用于像飞机票的预定、银行储蓄的财务管理等大量数据处理的实时系统中。
实时系统与分时系统的主要区别如下:
①系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统:而实时系统则大多数都是具有某种特殊用途的专用系统。
②响应时间的长短不同。分时系统的响应时间通常为秒级:而实时系统的响应时间通常为毫秒级甚至是微秒级。
③交互性的强弱不同。分时系统的交互性强,而实时系统的交互性相对较弱。
2.在操作系统中,通过一些硬件和软件的措施为用户提供了一个其容量比实际主存大得多的存储器,称为虚拟存储器。
操作系统要实现虚拟内存,必须把主存和辅存统一管理起来,即大作业程序在执行时,有一部分地址空间在主存,另一部分在辅存,当访问的信息不在主存时,由操作系统将其调入主存并实现自动覆盖功能,使用户在编写程序时不再受主存容量的限制。
例如在请求分页存储管理系统中,用户作业的所有页面并不一定都在实存,在作业运行过程中再请求调入所用的虚页。为了实现从逻辑地址空间到物理地址空间的变换,在硬件上必须提供一套地址变换机构,动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地址两部分,并利用页表将页号代之以块号,把块号和页内地址拼接就得到了内存的物理地址,从而实现了虚拟存储器。
3.读者一写者问题是经常出现的一种同步问题。计算机系统中的数据(文件、记录)常被多个进程共享,但其中某些进程可能只要求读数据(称为Reader):另一些进程则要求修改数据(称为Writer)。就共享数据而言,Reader和Writer是两种不同类型的进程。一般地,两个或两个以上的Reader进程同时访问共享数据时不会产生副作用,但若某个Writer和其它进程(Reader或Writer)同时访问共享数据时,则可能产生错误。为了避免错误,同时尽可能地让读者进程和写者进程并发运行,只要保证任何一个写者进程能与其它进程互斥访问共享数据即可。这个问题称为读者一写者问题。下面使用信号量机构来描述这一问题。
P、V操作是定义在信号量s上的两条原语,它是解决进程同步与互斥的有效手段。
定义下列信号量: 互斥信号量rmutex,初值为1,用于使读者互斥地访问读者计数器,共享变量rcount: 互斥信号量wmutex,初值为1,用于实现写者之间以及写者与读者之间互斥地访问共享数据集。则用信号量和P、V操作描述读者一写者问题如下:
Begin
rmutex wmutex:semaphore;
rcount:Integer;
rmutex=wmutex=1;
rcount=0;
Cobegin
Process procedure Reader
begin
repeat
…
P(rmutex);
rcount:=rcount+1
if rcount=l then P(rmutex);
V(rmutex);
perfonn read operations;
P(rmutex);
rcount:=rcount-1;
if rcount=O then V(rmutex);
V(rmutex);
…
until fa1se;
end
Process procedure Writer
begin
repeat
…
P(wmutex);
perform write operations;
V(wmutex);
…
until false;
end
Coend
End
4.该题的解题方法是先计算出每种算法的柱面移动总量。因为每个柱面移动需要6ms,所以,寻道时间=柱面移动总量×6ms。
(1)先到先服务算法的调度顺序为: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=348ms
5.第(1)种情况只适合用存取控制表实现保护机制。
第(2)种情况适合用权限或存取控制表实现保护机制。
第(3)种情况适合用存取控制表或RWX位或权限实现保护机制。
10.3西安交通大学2000年考研操作系统试题
(一)名词解释(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为最高优先级。对于下列每一种调度算法,计算其平均进程周转时间(进程切换开销可不考虑)。
(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.所谓线程(thread),从操作系统管理角度看线程是指"进程的一个可调度实体",是处理机调度的基本单位: 从编程逻辑看线程是指"程序内部的一个单一的顺序控制流"。线程是进程的一个组成部分。
2.所谓分时系统,就是指在一台计算机上,连接多个终端,用户通过各自的终端和终端命令把作业送入计算机,计算机又通过终端向各用户报告其作业的运行情况。这种计算机能分时轮流地为各终端用户服务并能及时对用户服务请求予以响应,这就构成了分时系统。分时系统设计的主要目标是使用户能与系统交互作用,对用户的请求及时响应,并在可能的条件下尽量提高系统资源的利用率。分时系统的主要特征是:
①同时性:若干个终端用户按照系统提供的各种服务,在各自终端进行操作,同时使用一台计算机资源。宏观上看是各用户在并行工作,微观上看是各用户轮流使用计算机。
②独立性:用户间可以相互独立地操作,互不干涉,系统保证各用户程序运行的完整性,不会发生相互混淆或破坏现象。
③及时性:系统可对用户的输入及时作出响应。分时系统性能的主要指标之一是响应时间,它是指从终端发出命令到系统予以应答所需的时间。
④交互性:用户可根据系统对请求的响应结果,进一步向系统提出新的请求,即能使用户和系统进行人一机对话的工作方式,所以分时系统也被称之为交互式系统。
3.系统调用是指用户在程序中能用"访管指令"调用的由操作系统提供的子功能的集合。每一个子功能称为一条系统调用命令(或广义指令)。系统调用是操作系统在程序级给用户提供的接口。
4.所谓地址再定位,就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程,即将地址空间给出的逻辑地址映射到内存的物理地址。地址重定位有静态重定位和动态重定位两种方式。
5.多道程序设计是指在主存中同时存放多道用户作业,它们都处于执行的开始点和结束点之间。多道程序设计的特点如下:
(1)多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。
(2)宏观上并行。从宏观上看,它们在同时执行。
(3)微观上串行。从微观上看,它们在交替、穿插地执行。
采用多道程序设计后,减少了CPU时间的浪费。尤其对计算题的作业,由于I/O操作较少,CPU 浪费的时间很少。
(二)简答题(32分)
1.覆盖技术与虚拟存储技术最本质的不同在于覆盖的程序段的最大长度要受到物理内存容量的限制,而虚拟存储器的最大长度不受物理内存容量的限制,只受计算机地址结构的限制。另外,使用覆盖技术要求程序员必须精心地设计程序及其数据结构,使得要覆盖的段具有相对独立性,不存在直接联系或相互交叉访问。而虚拟存储技术对用户的程序段之间没有此要求。
交换技术与虚存中使用的调入/调出技术的主要相同点是都要在内存与外存之间交换信息。交换技术与虚存中使用的调入/调出技术的主要区别在于:交换技术换进换出整个进程(proc结构和共享正文段除外〉,因此一个进程的大小受物理存储器的限制:而虚存中使用的调入/调出技术在内存和外存之间来回传递的是存储页或存储段,而不是整个进程,从而使得进程的地址映射具有了更大的灵活性,且允许进程的大小比可用的物理存储空间大得多。
2.顺序存取法就是严格按物理记录排列的顺序依次存取:随机存取法允许随意存取文件中的任何一个物理记录,而不管上次存取了哪一个记录。
顺序存取法对有结构文件的操作是设置一个访问指针ptr,令它总是指向"下一次"要访问的记录首址。每访问完一个记录后,对ptr住进行相应的修改。对于定长记录:ptr=ptr+L(L 为文件的物理记录长度):对于变长记录:Ptr=ptr+Li+1(其中1是存放记录长度Li的字节数)。顺序存取法对无结构文件的操作是按读写位移(offset)从当前位置开始读写,即每读写完一段信息后,读写位移自动力日上这段的长度,然后再根据该位移读写下面的信息。
随机存取法对有结构文件的操作也是设置一个访问指针pt,对于定长记录文件,欲访问第I个记录。(I=0,1,2,…)的首址为: ptr=offset+I*L(其中,offest是该文件的首址,L为记录长度):对于变长记录,随机存取法是十分低效的。随机存取法对无结构文件的操作必须事先用有关的命令把读写位移移到欲读写的信息开始处,然后再进行读写。
3.死锁是指多个进程因竞争资源而造成的一种僵局,若无外力的作用,这些进程都将永远不能再向前推进。所以,死锁是由于系统中多个进程所共享的资源不足以同时满足需要时,引起对资源的竞争而产生的。但竞争资源不→定都会产生死锁,因为只要进程推进顺序合法,就不会产生死锁。
4.所谓虚拟设备,是指利用SPOOLing系统把低速的独占设备改造成为共享的设备,或利用软件方法把共享的设备分割为若干台虚拟设备。
SPOOLing系统的核心思想是利用一台可共享的、高速大容量的块设备(磁盘)来模拟独占设各的操作,使一台独占设备变成多台可并行使用的虚拟设备。SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的特点是提高了I/O操作的速度:将独占设备改造为共享设备;实现了虚拟设备功能。
(三)(10分)
(1)采用FCFS的调度算法时,各任务在系统中的执行情况如下表所示:
所以,进程的平均周转时间为:
T=(10+16+18+22+3O)/5=19.2 min
(2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示:
所以,进程的平均周转时间为:
T=(6+14+24+26+27)/5=19.4 min
(3)采用时间片轮转算法时,假定时间片为2min,各任务的执行情况是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。设A～E五个进程的周转时间依次为T1～T5,显然,
T1=3Omin, T2=22min, T3=6min,T4=16min,T5=28min
所以,进程的平均周转时间为:
T=(30+22+6+16+28)/5=20.4min
(四)(10分)
1.因为虚拟页式存储系统中允许作业的一部分页面在内存,只有引入缺页中断,才能将不在内存的信息页从外存调入内存,中断恢复后可以继续执行。
2.缺页中断的实现由硬件和软件两部分组成。其实现方法如下:
每当CPU要执行一条指令时,首先形成操作数的有效地址,在计算页号和页内地址,检查页表看该页在实存吗。如在,则进行地址变换,按变换后的地址取出操作数,完成该指令的功能,然后继续进行下一条指令; 如不在,则引起缺页中断,进入缺页中断处理程序。
在中断处理程序中,首先利用存储器分块表(MBT)检查实存是否有空闲页面,如无,则选择某页淘汰。若该页被修改过还需写入辅存,并修改PMT和MBT,此时便出现了空闲实页。如有空闲实页,则根据辅助页表提供的磁盘地址调入所需的页面,修改PMT和MBT。最后再重新执行被中断的指令。
(五)(13分)
1.高级通信机制与低级通信机制P、V原语操作的主要区别是:
(1)交换信息量方面:利用p、v原语操作作为进程间的同步互斥工具是理想的,但进程间只能交换一些信息,基本上只能是控制信息,缺乏传输消息的能力。而高级通信不仅能较好地解决进程间的同步互斥问题,且能很好交换大量消息,是理想的进程通信工具。
(2)通信对用户透明方面:用户要用P、V原语进行进程间的通信必须在程序中增加p、V编程,这样做不但增加了编程的复杂性,不便对程序有直观的理解,同时由于编程不当,有可能出现死锁,难以查找其原因。而高级通信机制不但能高效传输大量信息,且操作系统隐藏了进程通信的实现细节,即通信过程对用户是透明的。这样就大大地简化了通信程序编制上的复杂性。
2.所谓消息(Message),是指一组信息,消息缓冲区是含有如下信息的缓冲区:
指向发送进程的指针:Sptr
指向下一信息缓冲区的指针:Nptr;
消息长度: Size;
消息正文: Text;
消息缓冲通信机制的基本工作原理是:把消息缓冲区作为进程通讯的一个基本单位,为了实现进程之间的通讯,系统提供了发送原语Send(A)和接收原语Receive(B)。每当发送进程欲发送消息时,发送进程用Send(A)原语把欲发送的消息从发送区复制到消息缓冲区,并将它挂在接收进程的消息队列末尾。如果该接收进程因等待消息而处于阻塞状态,则将其换醒。而每当接收进程欲读取消息时,就用接收原语Receive(B)从消息队列头取走一个消息放到自己的接收区。
3.消息缓冲通信机制中,消息队列属于临界资源,故在PCB中设置了一个用于互斥的信号量mutex,而每当有进程要进入消息队列时,应对信号量mutex施行P操作,退出消息队列后,应对信号量mutex施行V操作。由于接受进程可能会收到几个进程发来的消息,故应将所有的消息缓冲区链成一个队列,其队头由接收进程PCB中的队列头指针Hptr指出。
为了表示队列中的消息的数目,在PCB中设置了信号量旬,每当发送进程发来一个消息,并将它挂在接收进程的消息队列上时,便在Sn上执行V操作:而每当接收进程从消息队列上读取一个消息时,先对Sn执行P操作,再从队列上移出要读取的消息。
用P、V原语操作实现Send原语和Receive原语的处理流程如下:
Procedure Send(receiver,Ma) {发送原语}
begin
getbuf(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);
end
Procedure Receive(Mb) {接收原语}
begin
j:internal name; {接收进程内部标识符}
P(j.Sn);
P(j.mutex);
remove(j.Hptr,i); {从消息队列中移出第一个消息}
V(j.mutex);
Mb.Sender:=i.Sender; {将消息缓冲区中的信息复制到接收区}
Mb.Size:=i.Size:
Mb.text:=i.text:
End
10.4 西安电子科技大学2000年考研操作系统试题
(一)单项选择题(10分)
1.分页式虚拟存储管理系统中,一般来说页面的大小与可能产生缺页中断的次数_____。
A.成正比
B.成反比
C.无关
D.成固定比值
2.实时操作系统必须在_______内完成来自外部的事件。
A.响应时间
B.周转时间
C.规定时间
D.调度时间
3.早期UNIX操作系统的存储管理采用_______方案。
A.段式管理
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的叙述中,_______描述是不正确的。
A.SPOOLING系统中不需要独占设备
B.SPOOLING系统加快了作业执行的速度
C.SPOOLING系统使独占设备变成共享设备
D.SPOOLBNG系统利用了处理器与通道并行工作的能力。
9.页式虚拟存储管理的主要特点是_____。
A.不要求将作业装入到主存的连续区域
B.不要求将作业同时全部装入到主存的连续区域
C.不要求进行缺页中断处理
D.不要求进行页面置换
10.下列文件中属于逻辑结构的文件是
A.连续文件
B.系统文件
C.散列文件
D.流式文件
(二)改错题(对错误的命题,请说明原因)(10分)
1.采用多道程序设计的系统中,系统的程序道数越多,系统的效率就越高。
2.特权指令只能在管态下执行,而不能在算态下执行。
3.采用资源的静态分配算法可以预防死锁的发生。
4.一个虚拟的存储器,其地址空间的大小等于辅存的容量加上主存的容量。
5.一个作业由若干个作业步组成,在多道程序设计的系统中这些作业步可以并发执行。
6.作业调度是处理机的高级调度,进程调度是处理机的低级调度。
7.I/O交通管理程序的主要功能是管理主存、控制器和通道。
8.移臂调度的目标是使磁盘旋转周数最小。
9.进程是一个独立的运行单位,也是系统进行资源分配和调度的基本单位。
10.作业的联机控制方式适用于终端作业。
(三)、填空题(9分)
1.UNIX操作系统在结构上分为两个部分:_______和_______。
2.把作业装入内存中随即进行地址变换的方式称为_______,而在作业执行期间,当访问到指令或数据时才进行地址变换的方式称为________。
3.死锁产生的四个必要条件是:互斥控制、________、________、________。
4.多道程序设计的引入给存储管理提出了新的课题,应考虑的三个问题是________、________、________。
5.在存储管理方案中,可用上下限地址寄存器存储保护的是______。
6.在UNIX文件管理系统中,为了对磁盘空间的空闲块进行有效的管理,采用的方法____。
7.为了记录设备的分配情况,操作系统应设置一张______和三个控制块: 设备控制块、_______、_______。
8.I/O设备处理进程平时处于_______状态,当______和______出现时被唤醒。
(四)综合题(21分)
1.什么叫"可再入"程序? 它有什么特征?
2.简述UNIX的进程调度的公式和算法。
3.给出UNDE进程的调度状态,当子进程终止时,处于什么状态?
4.假设有4个记录A、B、C、D存放在磁盘的某个磁道上,该磁道划分为4块,每块存放一个记录
现在要顺序处理这些记录,如果磁盘旋转速度为2Oms转一周,处理程序每读出一个记录后花5ms的时间进行处理。试问处理完这4个记录的总时间是多少?为了缩短处理时间应进行优化分布,试问应如何安排这些记录?并计算处理的总时间。
5.有一个理发师,一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客,则理发师便在理发椅子上睡觉:当一个顾客到来时,必须唤醒理发师,进行理发；如果理发师正在理发时,又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和顾客各编一段程序描述他们的行为,要求不能带有竞争条件。
西安电子科技大学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.系统设备表控制器控制块通道控制块。
8.睡眠IIO中断I/O请求
(四)综合题(21分)
1.可再入程序是能够被多个进程共享的程序段,代码不因程序的执行而改变,又称为可再入码。纯代码的主要作用就是可被多个程序共享。其特点如下:
(1)可再入程序必须是纯代码的,在执行中不变化。
(2)一个可再入程序要求调用者提供工作区,以保证程序以同样的方式为用户服务。
(3)编译程序和操作系统程序通常是可再入程序,能同时被不同用户调用而形成不同进程。2.UNIX采用动态优先数调度算法,优先数的计算公式为:
p_pri=min{127,(p_cpu/16+PUSER+p_ice)} UNIX第6版
p_pri=(p_cpu/2+PUSER+NZERO) UNIX System
优先数越大,优先级越低。
3.在UNIX系统中,进程状态有: 运行状态、就绪状态、睡眠状态、创建状态、僵尸状态。当进程终止时处于僵尸状态。
4.优化前处理总时间=(5+5)+(5*3+5+5)+(5*3+5+5)+(5*3+5+5)=85ms
优化后记录顺序为: A,C,B,D
优化后处理总时间=(20/4+5)*4+5=45ms
5.
#define CHAIRS 6/ *为等候的顾客准备的椅子数*/
semphore customers=0;
semphore barbers=O;
semaphore S=1; /*用于互斥*/
int waiting=0;
void barber()
{ while (T)
{
P(customers);
P(S);
waiting =waiting -1;
V(bMbers);
V(S);
理发...
}
}
void customerO
{
P(S);
if (wait { waiting=waiting+I; V(customers); V(S); P(barbers); 坐下等待: } else { V(S); } } 2.4.3 睡着的理发师问题 (The Sleeping Barber Problem) 睡着的理发师问题又是一个有趣的 进程同步问题。 在理发馆中，有一个理发师，一张理发椅和 n 个为等待顾客所设的椅子。如果没有顾客来，理 发师就会坐在理发椅上睡觉，当一个顾客来到时，他必须唤醒睡着了的理发师。如果在理发 师理发时，又有别的顾客到达，他们要么坐下 ( 如果有空的椅子 )，要么离开 ( 如果所有的椅子都被坐满)。 解决方法是使用三个信号量： 1.customers , 用于记录等候的顾客的数 量。 2.barbers，用于记录空闲理发师的数量。 3.mutex, 用于进程之间的互斥。 另外还需使用一个变量 waiting，也是用于记录 等候的顾客的数量。 例程如下： #include "prototypes.h" #define CHAIRS 5/*chairs for waiting customers */ typedef int semaphore;/* use your imagination */ semaphore customers = 0 ;/* # of customers waiting for service */ semaphore barbers=0;/* # of barbers waiting for customers */ semaphore mutex=1;/* for mutual exclusion */ int waiting = 0;/* customers are waiting (not being cut) */ void Barber(void) {while (TRUE){ p(customers); p(mutex); waiting=waiting-1; v(barbers); v(mutex); cut_hair();/* go to sleep if # of customers is 0*/ /* acquire access to 'waiting' */ /* decrement count of waiting customers*/ /* one barber is now ready to cut hair */ /* release 'waiting' */ /* cut hair (outside critical region) */ }} V oid Customer(void) { p(mutex);/* enter critical region */ if (waiting < CHAIRS) {/* if there are no freee chairs, leave */ waiting = waiting + 1; v(customers); v(mutex); p(barbers); get_haircut();/* increment count of waiting customers */ /* wake up barber if necessary*/ /* release access to 'waiting'*/ /* go to sleep if # of free barbers 0 */ /* be seated and be served */ } else { v(mutex);/* shop is full, do not wait */ }} 10.5 西安电子科技大学2001年考研操作系统试题 (一)填空题(15分) 1.设有四个进程共享一程序段,而每次最多允许两个进程进入该程序段,则信号量的取值范围可能是_____。 2.特权指令能在______下执行,而不能在______下执行。 3.磁盘的驱动调度先进行______调度,再进行______调度。 4.采用资源有序分配算法可以_______死锁的发生。 5.一个虚拟的存储器,其地址空间的大小等于_______。 6.多道程序设计的特点是多道、_______和_______。 7._______调度是处理机的高级调度,__________调度是处理机的低级调度。 8.临界区是指_________________________________。 9.操作系统向用户提供了两类接口,一类是________,另一类是__________。 10.UNDE操作系统的存储管理采用______________方案。 (二)多项选择题(10分) 1.有关进程的描述中,_____是正确的。 A.进程执行的相对速度不能由进程自己来控制 B.P、V操作都是原语操作 C.利用信号量的P、V操作可以交换大量信息 D.同步是指并发进程之间存在的一种制约关系 E.并发进程在访问共享资源时,不可能出现与时间有关的错误 2.批处理操作系统的目的是____ A.提高系统与用户的交互性 B.提高系统资源的利用率 C.降低用户作业的周转时间 D.提高系统的吞吐率 E.减少用户作业的等待时间 3.用于解决进程间互斥的方法是_________。 A.信号量及P、V操作 B.加锁与开锁 C.信箱方式 D.消息缓冲方式 E.特权指令方式 4.支持程序放在不连续的内存中的存储管理方法有______。 A.可变式分区分配 B.多重分区分配 C.分页式分配 D.分段式分配 E.段页式分配 5.每一张合理的进程资源图必须满足_______。 A.∑|(R j ,P i)|≤W j B.|( R j ,P i )| +||≤ W j C.|( R i ,P j )|+ ∑|( R j,P k )|≤ W j D.∑|( R i ,P j )| ≤ W j E.∑|( R j,P k ) |≤ W j 6.文件的物理结构一般有______。 A.连续结构 B.流式结构 C.记录式结构 D.串联式结构 E.索引结构 7.连续结构的文件适合采用______的存取方法。 A.顺序存取 B.直接存取 C.按键存取 D.分区存取 E.以上都对 8.使用下面哪些方法可以实现虚存______? A.分区靠拢 B.覆盖 C.交换. D.联想寄存器 E.段靠拢 9.从设备分配的角度来看,设备分成________。 A.独享设备 B.系统设备 C.用户设备 D.共享设备 E.虚拟设各 10.UNIX文件采用多级保护,为每个文件规定了不同用户的使用权限,按_______划分给予不同的权限。 A.特权用户 B.文件的所布者 C.文件主的同组用户 D.普通用户 E.与文件主不同组的用户 (三)综合题(25分) 1.图 2.1中将一组进程分为4类,各类进程之间采用优先级调度,而各类进程内部采用时间片轮转调度,请简述P1,P2,P3,p4,P5,P6,p7,P8进程的调度过程。 高 底 图2.1 2.有5个待运行作业J1,J2,J3,J4,J5,各自预计运行时间分别是9,6,3,5和7。假定这些作业同时到达,并且在一台处理机上按单道方式执行。讨论采用哪种调度算法和哪种运行次序将使平均周转时间最短,平均周转时间为多少? 3.在一个只允许单向行驶的十字路口,分别有若干由东向西,由南向北的车辆在等待通过十字路口。为了安全,每次只允许一辆车通过(东→西或南→北)。当有车辆通过时其它车辆等待,当无车辆在路口行驶时则允许一辆车(东→西或南→北)进入。请用p、v操作实现能保证安全行驶的自动管理系统。 4.在 : (1)现有一个进程要释放四个物理块,其块号为150#,156#,172#,177#, 画出卷资源表的变化。 (2)在(1)完成后,假定有一进程要求分配6个空闲块,画出分配后的卷资源表。 6.磁盘请求以10、22、20、2、40、6、38柱面的次序到达磁盘驱动器。寻道时每个柱面移动需要6ms,计算以下寻道次序和寻道时间: (1)先到先服务； (2)电梯调度算法(起始移动向上)。 所有情况下磁头臂起始都位于柱面20。 西安电子科技大学2001年考研操作系统试题答案 (一)填空题(15分) 1.-2～2 6.宏观上并行微观上串行 2.管态算态 7.作业进程 3.移臂旋转 8.互斥执行的程序段 4.预防 9.命令级程序级 5. 2地址长度 10.最先适应算法 (二)多项选择题(10分) 1.A,B,D 2.C,D 3.B,C,D,E 4.A,B 5.A,D,E 6.A,B 7.B,C 8.B,C 9.A,D,E 10.B,c,E (三)综合题(25分) 1.各类进程之间采用优先级调度,而同类进程内部采用时间片轮转调度。先进行优先级4的进程调度,P1,P2,的按时间片进行轮转:等P1,P2,P3均执行完毕,执行优先级3的进程P4,P5。同理P4,P5按时间片轮转,运行完成后调度优先级1的进程P6,P7,P8。进程P6,",P8按时间片轮转直至完成。 2. (1)按小作业优先法: T=[3+(3+5)+(3+5+6)+(3+5+6+7)+(3+5+6+7+9)]/5=15.2 选择J3,J4,J5,J1。 (2)响应比R=1+作业的等候时间/作业的执行时间 R1=1.33,R2=1.5,R4=1.6,R5=1.428,选择J5,J4,J2,而,J3,J4,J5。 按响应比高者优先,则 T=[3+(3+5)+(3+5+6)+(3+5+6+7)+(3+5+6+7+9)]/5=152 所以应按刀,J4,J2,J5,J1的调度顺序运行作业,平均周转时间为152。 3.这是一个互斥问题,设信号量为S =1: S:samphore; S=1;
相关主题
文本预览