第 10章 部分高校考研操作系统试题与解答
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),是否能实施资源分配? 为什么?
表1 T0时刻系统状态进程
最大资源需求量
已分配资源数量
A B C
A B C
P1
P2
P3
P4
P5
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名学生选该课,规定:
①每两个学生组成一组,各占一台机器,协同完成上机实习;
②只有一组两个学生到齐,并且此时机房有空闲机器时,该组学生才能进入机房;
③上机实习由一名教师检查,检查完毕,一组学生同时离开机房。
试用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)访问磁盘次数减少的条件为
(五)(共10分)
①T0时刻是安全状态,因为可以找到一个安全的序列(P4,P5,Pl,P2,P3)。
②不能分配。因为所剩余的资源数量不够。
③可以分配。当分配完成后,系统剩余的资源向量为(0,3,2),这时仍可找到一个安全的序列队,(P4,P5,Pl,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
寻道时间为258×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的调度算法时,各任务在系统中的执行情况如下表所示:
执行次序
运行时间
优先数
等待时间
周转时间
A
10
3
0
10
B
6
5
10
16
C
2
2
16
18
D
4
1
18
22
E
8
4
22
30
所以,进程的平均周转时间为:
T=(10+16+18+22+3O)/5=19.2 min
(2)采用优先级调度算法时,各任务在系统中的执行情况如下表所示:
执行次序
运行时间
优先数
等待时间
周转时间
B
6
5
0
6
E
8
4
6
14
A
10
3
14
24
C
2
2
24
26
D
1
1
26
27
所以,进程的平均周转时间为:
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.25小时 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块,每块存放一个记录,安排如下表所示:
块号
1 2 3 4
记录号
A B C D
现在要顺序处理这些记录,如果磁盘旋转速度为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<CHAIRS)
{
waiting=waiting+I;
V(customers);
V(S);
P(barbers);
坐下等待:
}
else { V(S);
}
}
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.∑|(Rj,Pi)|≤Wj
B.|( Rj,Pi )| +||≤ Wj
C.|( R i,Pj )|+ ∑|( R j,Pk )|≤ Wj
D.∑|( R i,Pj )| ≤ Wj
E.∑|( R j,Pk ) |≤ Wj
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进程的调度过程。
优先级4(最高)
优先级3
优先级2
优先级1(最低)
高

图2.1
2.有5个待运行作业J1,J2,J3,J4,J5,各自预计运行时间分别是9,6,3,5和7。假定这些作业同时到达,并且在一台处理机上按单道方式执行。讨论采用哪种调度算法和哪种运行次序将使平均周转时间最短,平均周转时间为多少?
3.在一个只允许单向行驶的十字路口,分别有若干由东向西,由南向北的车辆在等待通过十字路口。为了安全,每次只允许一辆车通过(东→西或南→北)。当有车辆通过时其它车辆等待,当无车辆在路口行驶时则允许一辆车(东→西或南→北)进入。请用p、v操作实现能保证安全行驶的自动管理系统。
4.在UNIX系统中有卷资源表如下所示:
S_nfree=97
S_nfree[0]=120
S_nfree[0]=121

S_nfree[96]=145
(1)现有一个进程要释放四个物理块,其块号为150#,156#,172#,177#,画出卷资源表的变化。
(2)在(1)完成后,假定有一进程要求分配6个空闲块,画出分配后的卷资源表。
(1) (2)
(3)
(4)
(5)
图2.2
变化
(1)
(2)
(3)
(4)
(5)
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;
Cobegin
Process E->W
begin
p(s);
通过;
v(s)
end;
Process S->N
begin
p(s);
通过;
V(S);
END
Coend
4.
S_nfree=1
S_nfree[0]=177

S_nfree=100
S_nfree[0]=120

S_nfree[96]=145
S_nfree[97]=150
S_nfree[98]=156
S_nfree[99]=172
(1)
(2)
S_nfree=95
S_nfree[0]=120

S_nfree[94]=143
5.
变化
原因
(1)
时间片到
(2)
因等待数据资源而阻塞
(3)
因UO而阻塞
(4)
数据资源到被唤醒
(5)
I/O完成被唤醒
6.
(1)寻道次序:10,22,20,2,40,6,38柱面寻道时间=[(20-10)+(22-10)+(22-20)+(20-2)+(40-2)+(40一6)+(38-6)]×6
=146×6
=876ms
(2)寻道次序,22,38,40,刻,10,6,2柱面寻道时间=[(22-20)+(38-22)+(40-38)+(40-20)+(20-10)+(10-6)+(6-2)]×6
=58×6
=348ms
10.6 西安电子科技大学2002年考研操作系统试题(50分)
(一)单项选择题(每小题1分,共10分)
1.多道程序设计是指。
A.在实时系统中并发运行多个程序
B.在分布系统中同一时刻运行多个程序
C.在一台处理机上同一时刻运行多个程序
D.在一台处理机上并发运行多个程序
2.位示图方法可用于。
A.盘空间的管理 B.盘的驱动调度
C.文件目录的查找 D.页式虚拟存贮管理中的页面调度
3.下列算法中用于磁盘移臂调度的是。
A时间片轮转法 B.LRU算法
C.最短寻找时间优先算法D.优先级高者优先算法
4.在以下存贮管理方案中,不适用于多道程序设计系统的是
A.单用户连续分配 B.固定式分区分配
C.可变式分区分配 D.页式存贮管理
5.现有三个同时到达的作业J1,J2和J3,它们的执行时间分别是T1,T2和T3,且T2<T2<13。系统按单道方式运行且采用短作业优先算法,则平均周转时间是_____。
A.T1+T2+T3 B.(T1+T2+T3)/3
C.(3T1+2T2+T3)/3 D.(T1+2T2+3T3)/3
6.进程从运行状态进入就绪状态的原因可能是_____。
A.被选中占有处理机 B.等待某一事件
C.等待的事件已发生 D.时间片用完
7.用磁带作为文件存贮介质时,文件只能组织成_______。
A.顺序文件 B.链接文件 C.索引文件 D.目录文件
8.一作业8:00到达系统,估计运行时间为1小时。若10:00开始执行该作业,其响应比是_____
A.2 B.1 C.3 D.0.5
9.文件系统采用多级目录结构后,对于不同用户的文件,其文件名_____。
A.应该相同 B.应该不同
C.可以相同,也可以不同 D.受系统约束
10.在可变式分区分配方案中,某一作业完成后,系统收回其主存空间,并与相邻空闲区合并,为此需修改空闲区表,造成空闲区数减1的情况是_______。
A.无上邻空闲区,也无下邻空闲区 B.有上邻空闲区,但无下邻空闲区
C.有下邻空闲区,但无上邻空闲区 D.有上邻空闲区,也有下邻空闲区
(二)多项选择题(每小题2分,共10分)
1.能影响中断响应次序的技术是________和_________。
A.时间片 B.中断 C.中断优先级
D.中断屏蔽 E.特权指令
2.文件的二级目录结构由______和______组成。
A.根目录 B.子目录 C.主文件目录
D.用户文件目录 E.当前目录
3.驱动调度算法中算法中______可能会随时改变移动臂的运动方向。
A.电梯调度 B.先来先服务 C.扫描
D.单向扫描 E.最短寻找时间优先
4.有关设备管理概念的下列叙述中,_______是不正确的。
A.通道是处理输入、输出的软件
B.所有外围设备的启动工作都由系统统一来做
C.来自通道的I/0中断事件由设备管理负责处理
D.编制好的通道程序是存放在主存贮器中的
E.由用户给出的设备编号是设备的绝对号
5.一进程刚获得三个主存块的使用权,若该进程访问页面的次序是{1321215123},当采用先进先出调度算法时,发生缺页次数是次,而采用LRU算法时,缺页数是_________次。
A.1 B.3 C.4 D.5 E.6
(三)填空题(10分)
1.在UNIX中,一个进程采用_____来创建新进程,创建和被创建的进程间形成父子关系。父子间可以__________执行,子进程继承父进程的proc、_______、________、_____。
进程终止可以使用________,而父进程可以使用________等待其子进程的终止。
2.存贮管理应实现的功能是:主存空间的分配与保护,_______,主存空间的共享和_______。
3.每个索引文件都至少有一张索引表,其中的每一个表项应包括能标识该记录的________和该记录的__________。
4.SPOOLing系统中,作业执行时,从磁盘上的________中读取信息,并把作业的执行结果暂时存放在磁盘上的_________中。
(四)简答题(每小题3分,共9分)
1.比较段式管理和页式管理的特点。
2.什么是记录的成组和分解?
3.为实现分页式虚拟存贮,页表中至少应含有哪些内容?
(五)(4分〉文件系统采用多重索引结构搜索文件内容。设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,分别求二级索引和三级索引时可寻址的文件最大长度。
(六)综合题(7分)
有三个进程P1、P2和P3并发工作。进程P1需用资源S3和S1:进程P2需用资源S1和SL进程的需用资源S2和S3。回答:
(1)若对资源分配不加限制,会发生什么情况? 为什么?
(2)为保证进程正确地工作,应采用怎样的资源分配策略? 为什么?
西安电子科技大学2002年考研操作系统试解答
(一)单项选择题(每小题1分,共10分)
1.D 2.A 3.C 4.A 5.C 6.D 7.A 8.C 9.C 10.D
(二)多项选择题(每小题1分,共10分)
1.C,D 2.C D 3.B,E
4.A,E 5.E,D (次序不可交换)
(三)填空题(10分)
1.管理软件软 硬件资源
2.地址再定位 存储扩充问题
3.主存空间的重定位 主存的扩充
4.关键字(或记录号) 存放地址(或存放位置)
5.操作控制命令 交互(或联机)
6.输入# 输出#
(四)简答题(每小题3分,共9分)
1.分页和分段都采用不连续的分配方式,它们的特点如下:
(1)页式管理中源程序进行编译连接时是将主程序、子程序、数据区等按照线形空间的一维地址排列起来。段式管理则是将程序按照内容或过程(函数)关系分成段,每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间,也就是一个二维虚拟存储器。
(2)同动态页式管理一样,段式管理也提供了内外存统一管理的虚存实现。与页式管理不同的是:段式虚存每次交换的是一段有意义的信息,而不是像页式虚存管理那样只交换固定大小的页,从而需要多次的缺页中断才能把所需要的信息完整地调入内存。
(3)在段式管理中,段长可根据需要动态地增长。这对那些需要不断增加或改变新数据或子程序的段来说,将是非常有好处的。
(4)段式管理便于对具有完整逻辑功能的信息段进行共享。
阶段式管理便于进行动态链接,而页式管理进行动态链接的过程比较复杂。
2.(1)把若干逻辑记录合并成一组,存入一个物理块的工作称为记录的成组。
(2)从一组中把一个逻辑记录分离出来的工作称为记录的分解。
3.页表中应含下列内容:
页号标志主存块号磁盘上的位置
(五)分析,二级索引文件结构以及三级索引文件结构如图23所示。
170
170 170
第一级 第二级 物理块
(a)二级索引

170
…
第一级 第二级
第三级 物理块
(b)三级索引图2.3
二级索引文件最大长度:[512/3]×[512/3]=170×170=28900(块〉
三级索引文件最大长度:[512/3]×[512/3]×[512/3]=170×170×170=491300(块)
(六)综合题(7分)
(1)可能会发生死锁例如:进程P1、P2和P3分别获得资源S3、S1和S2后再继续申请资源时都要等待,这是循环等待。
(或答进程在等待新源时均不释放已占资源。)
(2)可有几种答案:
A.采用静态分配由于执行前己获得所需的全部资源,故不会出现占有资源又等待别的资源的现象(或不l会出现循环等待资源现象)。
或B.采用按序分配不会出现循环等待资源现象。
或C.采用银行家算法因为在分配时,保证了系统处于安全状态。
10.7 西北工业大学1999年考研操作系统试题
(一)选择题
1.在采用SPOOLING技术的系统中,用户的打印数据首先被送到________。
A.磁盘固定区域 B.内存固定区域 C.终端 D.打印机
2.当CPU执行操作系统代码时,称CPU处于________。
A.执行态 B.目态 C.管态 D.就绪态
3.如果I/O所花费的时间比CPU的处理时间短得多,则缓冲区________。
A.最有效 B.几乎无效 C.均衡 D.以上都不是
4.操作系统提供给程序员的接口是________。
A.进程 B.系统调用 C.库函数 D.B和C
5.在下列性质中,不是分时系统的特征。
A.多路性 B.交互性 C.独占性 D.成批性
6.在UNIX操作系统中,文件的索引结构存放在________中。
A.超级块 B.I节点 C.目录项 D.空闲块
7.若信号S的初值为2,当前值为-1,则表示有_________等待进程。
A.0个 B.1个 C.2个 D.3个
8.UNIX操作系统的进程控制块中常驻内存的是________。
A.proc结构 B.proc结构和核心梭
C.proc区 D.proc结构和user结构
9.当________时,进程从执行状态转变为就绪状态。
A.进程被调度程序选中 B.时间片到
C.等待某一事件 D.等待的事件发生
10.文件系统的主要目的是________。
A.实现对文件的按名存取 B.实现虚拟存储
C.提高外存的读写速度 D.用于存储系统文件
(二)简答题
1.进程和线程的主要区别是什么?
2.一般从哪些方面对操作系统进行性能评价?
3.什么是文件的物理结构和逻辑结构?
4.何为纯代码,它有什么用途?
(三)试论述磁盘调度的电梯算法的基本思想和算法。
(四)产生死锁的必要条件是什么? UNIX操作系统在其管道通信中是如何避免死锁的?
(五)UNIX操作系统是如何在其打开文件结构中实现文件共享的?
(六)计算题:
有一矩阵Var A:array[1..100,1..100] of integer,以行为先进行存储。有一个虚存系统,物理内存共有三页,其中一页用来存放程序,其余两页用于存放数据。假设程序已在内存中占一页,其余两页空闲。
程序A:
for i:=1 to 100 do
for j:=1 to 100 do
A[i,j]:=0;
程序B:
for j:=1 to 100 do
for i:=1 to 100 do
A[i,j]:=0;
若每页可存放200个整数,程序A和程序B的执行过程各会发生多少次缺页? 试问:
若每页只能存放100个整数呢? 以上说明了什么问题?
2.假设某系统中有五个进程,每个进程的执行时间(单位:ms)和优先数如下(优先数越小,其优先级越高):
进程
执行时间
优先数
P1
10
3
P2
1
1
P3
2
5
P4
1
4
P5
5
2
如果在0时刻,各进程按P1,P2,P3,P4,P5的顺序同时到达,试说明:当系统分别采用先来先服务的调度算法、可剥夺的优先级调度算法、时间片轮转法(时间片为1ms)时,各进程在系统中的执行情况,并计算在上述每种情况下进程的平均周转时间。
西北工业大学1999年考研操作系统试题解答
(一)选择题
1.A 2.C 3.B 4.B 5.D 6.B 7.B 8.A 9.B l0.A
(二)简答题
1.进程和线程是构造操作系统的两个基本元素,两者之间的主要区别是:
(1)调度方面,线程作为调度分派的基本单位。
(2)并发性方面,进程之间可以并发执行。
(3)拥有资源方面,进程是拥有资源的基本单位,线程除少量必不可少的资源外,基本上不拥有资源,但它可以访问其隶属进程的资源。
(4)系统开销,进程间切换时要涉及到进程环境的切换,开销比较大:而线程间切换只需保存和设置少量的寄存器内容,因此进程间切换的系统开销远大于线程间切换的系统开销。
2.一般从下列四个方面对操作系统进行性能评价:
(1)系统效率。体现系统效率方面的指标是系统处理能力(吞吐量)、资源的利用率以及响应时间等。系统效率是评价操作系统的一个重要性能指标。
(2)系统的可靠性、可用性和可维护性。系统的可靠性@、可用性(A)和可维护性(S)用系统的平均故障时间(M四日和平均故障修复时间(MTTR)来衡量,其公式如下:
R=MTBF
S=MTTR
A=MIBF/(MTBF+MTTR)=R/(R+S)
(3)方便性。方便性即指操作系统是否操作简单,容易掌握。
(4)可移植性。可移植性是指操作系统能很好地适应不同机器系列,即在硬件发生变化时,操作系统只需做少量的改变,就能在新的机器上运行。
3.文件的逻辑结构,是指文件在用户"思维"中的结构,是从用户的观点出发所观察到的文件组织形式,是用户可以直接处理的数据及其结构。它的目标是为用户提供一种结构清晰、使用方便的逻辑文件形式,用户按照这种组织形式可以去存取、检索和加工有关文件信息。文件的逻辑结构主要有两种:有结构的记录式文件和无结构的流式文件。
文件的物理结构是指文件在存储设备上的存储组织形式,又称为文件的存储结构。其主要目标是工作性能良好、设备利用率高,系统按照这种形式去和外部设备打交道,控制信息的传输。常用的文件物理结构有:连续结构、链接结构、索引结构和hash结构。
4.纯代码(Pure Cord)也就是可再入码(Reentry Cord),是指进程执行时不可修改的、为多个进程所共享的那部分程序代码。纯代码的主要用途是能被多个进程同时共享执行。
(三)电梯调度算法同时考虑两个条件作为优先的准则:既考虑申请者要求磁头移动的方向,又考虑要求磁头移动的距离,而且首先是方向一致,其次才是距离最短。该算法所选择的下一个访问对象应是其欲访问的磁道在当前磁道之外,又是距离最近的。这样由里向外地访问,直至再无当前磁道之外的磁道需要访问,才将磁头臂换向,由外向里访问。这时,选择在当前磁道之内、距离最近的磁道访问,磁头逐步向里移动,直至再无当前磁道之内的磁道需要访问,从而避免了饥饿现象。该算法中磁头的移动规律与电梯类似,故称为电梯算法。
(四)产生死锁有四个必要条件:
(1)互斥控制。进程对所要求的资源进行排它控制,在一段时间内一个资源仅能被一个进程使用。
(2)不可剥夺控制。进程所获得的资源在未释放前,不能被其它进程剥夺。即使该进程处于阻塞态,它所占资源也不能被其它进程使用,只有等待占有该资源的进程释放后才能给别的进程使用。
(3)请求和保持。为了提高资源利用率,进程在运行过程中可随时提出对各种资源的请求,当进程因请求资源而阻塞时,对已获得的资源保持不放。
(4)环路等待条件。在发生死锁时,进程的资源状态图必构成环路,即前一进程保存着后一进程所要求的资源。
UNIX操作系统在其管道通信中避免死锁的方法是:当发生读/写等待时,在等待前先检查对方是否已关闭。如果发现对方己关闭,则读/写进程不必等待而直接返回。另外,进程在关闭管道文件时,也要检查对方是否正在等待。如果发现对方正在等待,则应先唤醒等待进程。
(五)UNIX操作系统的文件共享包括两个方面,即磁盘文件的共享和打开文件的共享。UNIX操作系统实现磁盘文件共享非常方便,不同目录中的文件指向同一个i节点,就可以实现共享。文件在目录结构中的共享是一种静态的共享。而当多个用户同时打开某一文件对其访问时,将在内存中建立打开文件结构,这时的共享称为打开文件结构中的共享,这是一种动态的共享。
UNDIX的文件系统中打开文件结构由三部分组成:
(1)进程打开文件表。每个进程都有一个进程打开文件表,其中每一项是一个指针,指向系统打开文件表。
(2)系统打开文件表。系统打开文件表也叫打开文件控制块。一个进程每打开一个文件都有一个系统打开文件表,其中主要包含:
f-count 指向该系统打开文件表的进程数
f-inode 指向一个打开文件的内存I节点
(3)内存I节点。其中主要包括:
i-addr[ ] 文件在盘上的物理位置信息
i-count 与此内存I节点相连的系统打开文件表的个数不同用户对打开文件的共享只需将系统打开文件表中的指针f-inode指向同一个内存I节点即可。在这种共享方式中,共享文件的各个进程拥有各自独立的文件读、写指针。但子进程共享父进程的文件却是同一个读写指针。
(六)计算题
1.考虑本题所给条件,每个主存块的大小为可以存放200个数组元素,有两个内存块可以用来存放数组信息,数组中的元素按行编址。
对于程序A,数组访问顺序是:
A[1,1],A[1,2],A[1,3],……,A[1,100]
A[2,1],A[2,2],A[2,3],……,A[2,100]
A[100,1],A[100,2],A[100,3],……,A[100,100]
显然,数组的存储顺序与访问顺序一致,每访问两行数组遇到一次缺页中断。如果采用LRU页面调度算法,会产生50次缺页中断。
对于程序B,数组访问顺序是:
A[1,1],A[2,1],A[3,1],……,A[100,1]
A[1,2],A[2,2],A[3,2],……,A{100,2]
A[1,100],A[2,100],A[3,100],……,A[100,100]
显然,数组的存储顺序(按行的顺序)与访问顺序(按列的顺序)不一致,每访问两个数组元素遇到一次缺页中断。如果采用LRU页面调度算法,会产生5000次缺页中断。
若每页只能存放100个整数,对于程序A,数组的存储顺序与访问顺序一致,每访问一行数组遇到一次缺页中断。如果采用LRU页面调度算法,会产生100次缺页中断。对于程序B,数组的存储顺序(按行的顺序)与访问顺序(按列的顺序)不一致,每访问一个数组元素遇到一次缺页中断。如果采用LRU页面调度算法,会产生10000次缺页中断。
以上结果说明,页面越大,缺页中断次数越少;页面越小,缺页中断次数越多。
2.(1)采用FCFS的调度算法时,各进程在系统中的执行情况如下表所示:
进程执行次序
执行时间
优先数
等待时间
周转时间/ms
P1
10
3
0
1
P2
1
2
10
6
P3
2
5
11
16
P4
1
4
13
17
P5
5
2
14
19
系统中进程的平均周转时间为:
T=(10+11+13+14+19)/5=13.4ms
(2)采用可剥夺的优先级调度算法时,各进程在系统中的执行情况如下表所示:
进程执行次序
执行时间
优先数
等待时间
周转时间/ms
P2
1
1
0
1
P5
5
2
1
6
P1
10
3
6
16
P4
1
4
16
17
P3
2
5
17
19
系统中进程的平均周转时间为:
T=(1+6+16+17+19)/5=11.8ms
(3)采用时间片轮转法(时间片为1ms)时,各进程在系统中的执行情况为:
(P1,P2,P3,P4,P5),(P1,P3,P5),(P1,P5,P1,P5,PL P5),(P1,P1,P1,P1,P1)
假设,进程P1~P5的周转时间分别为T1~T5,显然,
T1=19ms,T2=2ms,T3=7ms,T4=4ms,T5=14ms
系统中进程的平均周转时间为:
T=(19+2+7+4+14)/5=9.2ms
10.8西北工业大学2000军弩研操件系统试题
(一)填空、选择题(本题共12分,每空1分)
1.操作系统提供给程序员的接口是________。
A.进程 B.系统调用 C.库函数 D.B和C
2.设有8页的逻辑空间,每页有1024字节,它们被映射到32块的物理存储区中。那么,逻辑地址的有效位是_______位,物理地址至少是_______位。
3.文件系统中若文件的物理结构采用连续结构,则文件控制块中关于文件的物理位置应包括________和________。
4.考虑一个存于磁盘上的文件系统,其中的文件由大小为512B的块组成。假定每一个文件有一个文件目录像,该目录像包含此文件的名字、文件长度以及第一块(或第一索引块)和最后一块的位置,而且该目录项位于内存。对于索引结构文件,该目录项指明第一索引块,该索引块又依次指向511个文件块且有一个指向下一个索引块的指针。针对连续、链接、索引结构的每一种,如果当前位于逻辑块10(即最后一次访问的块是逻辑块10)且希望访问逻辑块4,那么,必须分别从盘上读_______,______,________个物理块。
5.在UNIX操作系统中,把输入输出设备看作是________。
A.普通文件 B.目录文件 C.索引文件 D.特殊文件
6.CPU执行操作系统代码时,称CPU处于________。
A.自由态 B.目态 C.管态 D.就绪态
7.设一段表为段号
基地址
段长
0
1
2
3
4
219
2300
90
1327
1952
600
14
100
5800
96
那么,逻辑地址(2,88)对应的物理地址是_________。
逻辑地址(4,100)对应的物理地址是_____________________。
(二)简要回答下列问题(本题共30分,每小题5分)
1.什么是多道程序设计技术? 多道程序设计的优点是什么? 为什么说直到出现中断和通道技术后,多道程序概念才变为有用的?
2.分时系统和实时系统有什么区别?设计适用于实时环境的操作系统的主要困难是什么?
3.在UNIX操作系统中,为什么PROC结构常驻内存?为什么ppda可以不常驻内存?ppda和其他数据结构合在一起有什么好处?
4.什么叫重定位? 采用内存分区管理时,如何实现程序运行时的动态重定位?
5.为什么要引入SPOOLing系统? SPOOLing系统可带来哪些好处?
6.文件目录和目录文件各起什么作用? 目前广泛采用的目录结构形式是哪种?它有什么优点?
(三)(本题10分)假定要在一台处理机上执行下列作业:
作 业
执行时间
优先级
1
2
3
4
5
10
1
2
1
5
3
1
3
4
2
且假定这些作业在时刻0以1,2,3,4,5的顺序到达。
1.说明分别使用FCFS,RR(时间片=1),SJF以及非剥夺式优先级调度算法时,这些作业的执行情况。
2.针对上述每种调度算法,给出平均周转时间和平均带权周转时间。
(四)(本题10分)
考虑下面的页访问串:
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
假定有4,5,6个页块,应用下面的页面替换算法,计算各会出现多少次缺页中断。注意,所给定的页块初始均为空,因此,首次访问一页时就会发生缺页中断。
(1)LRU; (2)FEO; (3)Optimal。
(五)(本题10分)为什么要引入缓冲区? UNIX操作系统如何管理缓冲区?
(六)(本题10分)试述UNIX操作系统如何实现文件的共享。
(七)(本题10分)从读卡机上读进N张卡片,然后复制一份,要求复制出来的卡片与读进来的卡片完全一致。这一工作由三个进程get,copy和put以及两个缓冲区buffer1和buffer2完成。进程get的功能是把一张卡片上的信息从读卡机上读进buffer1:进程copy的功能是把buffer1中的信息复制到buffer2:进程put的功能是取出buffer2中的信息并从行式打印机上打印输出。
试用P、V操作完成这三个进程间的尽可能并发正确运行的关系(用程序或框图表示),并指明信号量的作用及初值。
(八)(本题8分)考虑由n个进程共享的具有m个同类资源的系统,证明:如果对I=1,2,……,n,有Need>O而且所有最大需求量之和小于m+n,那么该系统是死锁无关的。
西北工业大学2000年考研操作系统试题解答
(一)填空、选择题(本题共12分,每空1分)
1.B 2.13 15 3.起始块号总块数 4.1 4 1
5.D 6.C
7.90+88=178 由于段内地址100超过段长96,所以产生越界中断
(二)简要回答下列问题(本题共30分,每小题5分)
1.现代计算机系统一般都采用基于多道程序设计的技术。通常多道程序设计是指在主存中同时存放多道用户作业,使它们都处于执行的开始点和结束点之间。多道程序设计的特点如下:
(1)多道。主存中有多道程序,它们在任一时刻必须处于就绪、运行、阻塞三种状态之一。
(2)宏观上并行。从宏观上看,它们在同时执行。
(3)微观上串行。从微观上看,它们在交替、穿插地执行。
因为中断是激活操作系统的手段,只有通过中断技术才能使CPU从一个作业的处理转到另一个作业的处理,而通道使得主机与外设可以并行工作,所以直到出现中断和通道技术后,多道程序概念才变为有用。
2.实时系统与分时系统的主要区别是:
(1)系统的设计目标不同。分时系统的设计目标是提供一种随时可供多个用户使用的通用性很强的系统,而实时系统则大多数都是具有某种特殊用途的专用系统。
(2)响应时间的长短不同。分时系统的响应时间通常为秒级,而实时系统的响应时间通常为毫秒级甚至微秒级。
(3)交互性的强弱不同。分时系统的交互性强,而实时系统的交互性弱。
设计适用于实时环境的操作系统的主要困难是:
①需要高精度的实时时钟管理。
②需要高可靠性和安全性做保证。
③需要连续的人机对话功能及快速的中断响应、中断处理能力。
④过载的防护等问题。
3.为了节省内存,UNIX系统把进程控制块分成两部分。一部分为进程的基本控制块,简称proc结构,它存放着进程最常用的一些信息,所以proc结构一般常驻内存。另一部分称为进程扩充控制块,简称user结构,它存放着进程的一些必要但不常使用的信息。ppda(进程系统数据区)包含user结构和系统枝,ppda可以不常驻内存是为了减少内存的开销。把ppda和其它数据结构(指用户校区和用户数据区)合起来形成进程的数据段,其好处是方便于一起调入调出内存。
4.所谓地址重定位,就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程,即将地址空间给出的逻辑地址映射到内存的物理地址上。地址重定位有静态重定位和动态重定位两种方式。
采用内存分区管理时,在硬件上设置一个"重定位寄存器"可以实现程序运行时的动态重定位。这种情况下地址重定位是在程序执行期间由地址变换机构动态实现的,主要的计算依据是:
物理地址=逻辑地址+重定位寄存器的内容
5.所有字符设备都是独享设备并属于慢速设备,本质上属于顺序存取设备。因此,一个进程在某台字符设各上进行数据交换时,往往要等待较长时间,并且在该数据交换完成之前,其他进程不能同时访问这台设备。而且动态分配也不能真正提高这类设备的利用率,当一个进程正在使用这类设备进行一次较大量的数据交换时,其他需要同时访问该设备的进程就要等待较长的时间,从而降低了整个系统的并发能力。SPOOLing技术正是针对上述问题提出的一种设备管理技术。
SPOOLing系统可带来的好处如下:
(1)字符设备和各虚拟设备之间的数据交换由SPOOLing进程统一调度实施,而切这种数据交换以并行方式进行,系统呈现出高度的并行性:
(2)用户使用的是虚拟设备,可以减少用户进程的等待时间。
在多道程序系统中,用程序模拟脱机输入/输出时外围控制机的功能,这样便可在主机的直接控制下实现脱机输入/输出功能。此时的外围操作与CPU对数据的处理同时进行,这种在联机情况下实现的外围设备同时操作称为SPOOLing,也称伪脱机。
SPOOLing系统的核心思想是利用一台可共享、高速、大容量的块设备(磁盘)来模拟独占设备的操作,使一台独占设备变成多台可并行使用的虚拟设备。SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的好处是提高了I/O操作的速度,将独占设备改造为共享设备,实现了虚拟设备的功能。
6.在文件系统中,文件目录记录文件的管理信息,又称为文件控制块,或文件说明信息。文件系统把同一卷上的若干文件的文件目录组成一个独立的文件,这个文件全部由文件目录组成,称为目录文件。
文件目录用于对单个文件的控制,它记录文件的名字、文件长度、文件存放在外存上的物理地址,以及文件属性和文件建立时间、日期等信息。目录文件是全部文件目录组成的文件,用于整个文件系统的管理。
文件的目录结构一般有三种形式z一级目录,二级目录,多级树型目录。一级目录简单方便,但不允许文件重名。二级目录由主目录和用户文件目录两级目录组成,可以解决文件的重名和别名问题。多级树型目录是二级目录的扩充。
目前广泛采用的目录结构形式是树型目录结构。它的主要优点是:①检索效率高:②允许文件重名:③确切反映了信息的层次结构,并且可以利用层次结构实现文件共享和保护。
三、(本题10分)
(1)采用FCFS的调度算法时,各作业在系统中的执行情况如下表所示:
作业执行次序
执行时间
优先数
等待时间
周转时间
带权周转时间
1
10
3
0
10
1
2
1
1
10
11
11
3
2
3
11
13
6.5
4
1
4
13
14
14
5
5
2
14
19
3.8
系统中作业的平均周转时间为:
T=(10+11+13+14+19)/5=13.4
系统中作业的平均带权周转时间为:
W=(1+11+6.5+14+3.8)/5=7.26
(2)采用RR(时间片=1)时,各作业在系统中的执行情况为:
(1,2,3,4,5),(1,3,5),(1,5,1,5,1,5),(1,1,1,1,1)
假设作业1~5的周转时间分别为T1~T5,显然,T1=19,T2=2,T3=7,T4=4,T5=14。系统中作业的平均周转时间为:
T=(19+2+7+4+14)/5=9.2
假设作业1~5的带权周转时间分别为W1~W5,那么:W1=19/10=1.9,W2=2/1=2,W3=7/2=3.5,W4=4/1=4,W5=14/5=2.84。系统中作业的带权平均周转时间为:
W=(1.9+2+3.5+4+2.8)/5=2.84
(3)采用SJF算法时,各作业在系统中的执行情况如下表所示:
作业执行次序
执行时间
优先数
等待时间
周转时间
带权周转时间
2
1
1
0
1
1
4
1
4
1
2
2
3
2
3
2
4
2
5
5
2
4
9
1.8
1
10
3
9
19
1.9
系统中作业的平均周转时间为:
T=(1+2+4+9+19)/5=7.0
系统中作业的平均带权周转时间为:
W=(1+2+2+1.8+1.9)/5=1.74
(4)采用非剥夺的优先级调度算法时,各作业在系统中的执行情况如下表所示:(假设优先数越小优先级越高)
作业执行次序
执行时间
优先数
等待时间
周转时间
带权周转时间
2
1
1
0
1
1
5
5
2
1
6
1.2
1
10
3
6
16
1.6
3
2
3
16
18
9
4
1
4
18
19
19
系统中作业的平均周转时间为,
T=(1+6+16+18+19)/5=12.0
系统中作业的带权平均周转时间为:
W=(1+1.2+1.6+9+19)/5=6.36
(四)(本题10分)
(请参考西北大学1998年试题第(九)题第2题的解答。〉
(五)(本题10分〉
引入缓冲区的主要原因如下:
①缓和CPU与I/O设备间速度不匹配的矛盾;
②减少对CPU的中断频率,放宽对中断响应时间的限制;
③提高CPU与I/0设备之间的并行操作程度。
UNIX操作系统将设备分为字符设备和块设备分别进行管理。块设备是指磁盘、磁鼓、磁带等高速设备,它们传送信息的单位是块(512字节)。字符设备是指打印机、键盘、卡片机等低速设备,它们传送信息的单位是字节。UNIX操作系统分别为字符设备和块设备设置了缓冲区。字符设各缓冲区的大小以字节为单位,块设备的缓冲区则以盘块大小(一般为512字节)为单位。
(1)字符设备缓冲区的管理,UNIX在系统中设置了一组字符缓冲区,供各种字符设备使用。其中,每个缓冲区的大小为70个字节,包括4项,第一个字符位置,最后一个字符位置,指向下一个缓冲区的指针和余下的用于存放64个字符的缓冲区。所有的空闲缓冲区链接成一个队列。缓冲区的分配和释放均可在链首处进行。
(2)块设备缓冲区的管理,UNIX操作系统的块设备缓冲区管理采用类似缓冲池管理的方法。每个缓冲区由两部分组成; 第一部分是缓冲区首部,用于存放缓冲区的管理和控制信息;第二部分是真正的缓冲区,用于存放数据。两者一一对应,但物理上并不相连,而是独立存储。缓冲区动态地组织成空闲缓冲区队列、设备缓冲区队列和设备I/0请求队列。空闲缓冲区队列是由空闲缓冲区构成的,设备缓冲区队列是按占用缓冲区的设备块号构成的多个散列队列,设备缓冲区队列中正在进行读写的缓冲区构成设备I/O请求队列。缓冲区的分配有两个过程:getblk()和getblk(dev,blkno),缓冲区的回收由brelse(bufno)完成。
(六)(本题10分)
UNIX操作系统实现文件共享的方式有两种:
(1)i节点法:不同目录中的文件指向同一个i节点,就可以实现共享。
(2)符号链法z利用符号链也可以实现文件共享。
共享i节点方式只能共享同一文件系统的文件,而符号链法可以跨文件系统共享。
(七)(本题10分)
设互斥信号量S1,S2初值为1,分别用于对buffer1和buffer2的互斥访问; 同步信号量SI11,SIG初值为1,分别表示bufferl和buffer2初始状态为空闲,可以放一张卡片信息; 同步信号量Sm1,Sm2初值为0,分别表示buffer1和buffer2中的信息还没有被取用(或已被取用了)。用P、V操作完成这三个并发进程间能正确运行的程序如下:
BEGIN
S1,S2,Sn1,Sn2,Sm1,Sm2,semaphore;
Sl=S2=1;
Snl=Sn2=1;
Sm1=Sm2=0;
Cobegin
Process produce get
Begin
L1,从读卡机读进一张卡片信息:
P(Sn1);
P(S1);
将信息放入buffer1;
V(Sm1);
V(Sl);
Goto L1
End
Process produce copy
Begin
L2,P(Sm1);
P(S1);
从buffer1复制信息;
V(Sn1);
V(Sl);
P(Sn2);
P(S2);
将复制的信息放入buffer2;
V(Sm2);
V(S2);
Goto L2
End
Process produce put
Begin
L3,P(Sm2);
P(S2);
从buffer2取信息;
V(Sn2);
V(S2);
把信息从打印机输出;
Goto L3
End
Coend;
END
(八)(本题8分)
设每个进程对共享资源的最大需求量为x(O<x≤m)时,由于每个进程最多申请使用x个资源,在最坏的情况下,每个进程都得到了(x-1)个资源i并且都需申请最后一个资源。这时系统剩余资源数为:m-n(x-1)。只要系统还有一个资源可用,就可使其中的一个进程获得所需的全部资源。该进程运行结束后释放出它所占用的资源,其它进程的资源需求也可得到全部满足。因此,当m-n(x-1)≥1时,即x≤(m+n-1)/n时系统不会发生死锁。进而可得系统中所有进程的最大需求量之和n×x≤(m+n-1)时系统不会发生死锁。该题中,所有进程最大需求量之和小于m+n,所以,该系统是死锁无关的。
10.9 西北大学1998年考研操作系统试题
(一)(15分)简述下列概念的区别与联系:
1.进程与程序 2.作业调度与进程调度
3.段式与页式存储管理 4.静态优先数与动态优先数
5.命令接口与程序接口
(二)(10分)设有一个具有N个信息元素的环形缓冲区,A进程顺序地把信息写入缓冲区,B进程依次地从缓冲区中读出信息。回答下列问题:
1.叙述A、B两个进程的相互制约关系。
2.用P、V操作表示A、B进程的同步算法
(三)(10分)在UNIX操作系统中,试述:
1.为创建一个进程,系统需做哪些准备工作。
2.进程树如何形成。
3.用流程图描述"创建进程(fork)"系统调用。
(四)(10分)消息缓冲通信机制有什么好处?试述:
1.消息缓冲通信的过程。
2.画出有关通信原语的逻辑框图。
(五)(10分)在请求分页存储管理系统中,试问:
1.局部与全局页面淘汰算法有何区别? 为什么在多道系统中常用局部页面淘汰算法?
2.试设计一个LRU淘汰算法的近似算法(指出所需的硬件支持、数据结构及软件处理流程或类Pascal描述)。
(六)(15分)设备分配时为什么应考虑安全性以及与设备的无关性?试给出一个检查系统安全性的算法。
(七)(10分〉在文件系统中,试问:
1.将一个文件目录分为基本目录项和名号目录项有什么好处?
2.试描述在UNIX系统中实现"打开文件"系统调用的处理过程。
(八)(10分)试问:
1.文件存储器的管理与内存管理有何异同点?
2.在UNIX系统中,当一个文件的规模分别为
(a)不超过10块; (b)在11~256块之间; (c)超过256块时,其物理文件如何组织?(可画图表示〉
(九)(15分)计算题:
1.在一个单道批处理系统中,一组作业的提交时刻和运行时间如下表所示:
作业
提交时间
运行时间
1
8:00
1.0
2
8:50
0.50
3
9:00
0.20
4
9:10
0.10
试计算以下三种作业调度算法的平均周转时间T和平均带权周转时间W:
(1)先来先服务;(2)短作业优先;(3)响应比高者优先。
2.在请求分页存储管理系统中,设一个作业访问页面的序列为4,3,2,1,4,3,5,4,3,2,1,5:设分配给该作业的存储空间有4块,且最初未装入任何页。试计算FIFO和LRU算法的失页率。
3.设某磁盘有200个柱面,编号为0,1,2,...,199,磁头刚从140道移到143道完成了读写。若某时刻有9个磁盘请求分别对如下各道进行读写:
86,147,91,177,94,150,102,175,130
试分别求FCFS,SSTF及SCAN磁盘调度算法响应请求的次序及磁头移动的总距离。
西北大学1998年考研操作系统试题解答
(一)简述下列概念的区别与联系(15分)
1.进程由程序、数据和PCB三部分构成。程序是进程的实体。进程与程序的主要区别有:
(1)进程是程序的一次执行,属于一种动态的概念:而程序是一组有序的指令,是一种静态的概念。但是进程离开了程序也就失去了存在的意义。因此,进程是程序执行的动态过程,而程序是进程运行的静态文本。
(2)程序可以作为一种软件资料长期保存,而进程是程序的一次执行过程,是暂时的。进程具有生命期,它由创建而产生,由调度而运行,因得不到资源而阻塞,因撤消而死亡。
(3)一个进程可以执行一个或几个程序:反之,同一个程序也可能由多个进程同时执行。
(4)进程具有并发性,它能与其它进程并发运行:而一般的程序不具有这种明显的特性。
(5)在没有线程的情况下,进程是一个独立的运行单位,也是系统进行资源分配和调度的基本单位。因此,进程具有独立性,但并发的进程之间还具有相互制约性。
2.作业调度属于高级调度,而进程调度属于低级调度。
作业调度是根据系统内资源的使用情况,从后备作业队列中选择一道作业进入系统,并创建相应的进程,分配必要的系统资源,使其处于"就绪"状态。
进程调度是根据CPU的使用情况及时地把CPU分配给一个"就绪"的进程,使其从"就绪"状态变为"运行"状态。
3.在页式存储管理系统中,把每个作业的地址空间划分成大小相等的页,把内存的存储空间分成与页大小相同的物理块。存储分配以块为单位,一个作业的地址空间可以分配到内存不连续的物理块中。系统为每个作业建立一张页面变换表(简写为PMT,简称为页表),记录相应页在内存中对应的物理块号。页表(PMT)是用来完成逻辑地址到物理地址变换的一个重要数据结构。当进程访问逻辑地址时,地址变换机构自动地将逻辑地址分为页号和页内地址两部分,再以页号为索引去检索页表,得到该页的物理块号。把该物理块号与页内地址拼接便得到了物理地址。请求分页是指作业的所有页面并不一定都在实存,在作业运行过程中再请求调入所用的虚页。分页管理系统根据请求装入页面的方法,称为请求分页存储管理。
段式管理允许用户将作业的逻辑关系进行自然分段,段数不限且各段的大小可不同。逻辑段内的地址是由两部分(S:段号,dz段内位移量)组成的,即分段地址空间是用户定义的三维空间。内存分配以段为单位,整个作业的地址空间可装配在若干个互不连续的内存区域。在分段存储管理系统中,可以用类似于分页管理用过的地址变换机构,实现分段管理的地址变换,只不过使用的是段变换表SMT。段也可以根据请求而动态地调入内存。
段式与页式存储管理的主要区别为:
(1)分页的作业地址空间是单一的线性地址空间,而分段的作业地址空间是二维的。
(2)页是信息的物理单位,页的大小固定。而段是信息的逻辑单位,其长度不定。
(3)分页的活动是看不见的,分段是用户可见的活动。
(4)请求分页管理实现单段式虚存,而分段管理实现多段式虚存。
4.系统在创建进程时就确定了它的优先数,该优先数在进程的整个生存期内不再改变,这种优先数属于静态优先数。
系统在创建进程时确定了它的优先数,但该优先数在进程的整个生存期内可以随着情况的变化而发生改变,这种优先数属于动态优先数。
5.命令接口与程序接口是操作系统为用户提供的两类接口。
按命令接口对作业控制方式的不同,可将命令接口分为两种:
(1)联机命令接口:不同的系统提供的联机用户命令不同,但一般可提供一种或几种方式:命令驱动方式、菜单驱动方式和命令文件方式。
(2)脱机命令接口:把批处理系统中的接口称为脱机命令接口。
程序接口是操作系统专门为用户程序设计的,也是用户程序取得操作系统服务的唯一途径。程序接口通常由一组系统调用组成。用户通过在程序中使用系统调用命令来请求操作系统服务。不同的操作系统其系统调用的表现形式也不相同,但其所提供的主要功能大致相同。
(二)(10分)
1.A和B两个进程的相互制约关系是既有互斥又有同步:对缓冲区的访问必须互斥,并且,当缓冲区满时,A进程不可以写,必须等待:当缓冲区空时,B进程不可以读,必须等待。
2.用P、V操作表示A、B进程的同步算法如下:
BEGIN
Buffer,ARRAY [0..N-1] of interger;
m,out,Interger;
S0,S1i S21Semaphore;
SO:=1; S1:=0; S2:=N;
in,=out:=0;
Cobegin
Process PROCEDURE A:
BEGIN
L1,生产数据m;
P(S2);
P(SO);
Buffer(in):=m;
in,=(in+1)MOD N;
V(S1)
V(SO);
Goto L1
END
Process PROCEDURE B:
BEGIN
L2,P(S1);
P(SO);
m:=buffer(out);
out,=(out+1)MOD N;
V(S2);
V(SO);
消费m;
goto L2
END
Coend
END
(三)(10分〉
1.为创建一个进程,首先需要启动UNIX操作系统。系统初启时,会自动建立0#进程,0#进程又创建1#进程,此后0#进程就变为对换进程,而1#进程就变为系统的始祖进程。
2.UNIX利用fork为每个终端创建一个子进程为用户服务,如等待用户登录、执行shell命令解释程序等。此后,每个终端子进程又可利用fork来创建它的子进程,从而可形成一棵进程树。
3.Fork()的主要工作流程如图2.4所示,
fork()

=1 =0
图2.4 fork()的主要工作流程
(四)(10分)
消息缓冲通信机制不仅能较好地解决进程间的同步互斥问题,还能交换大量消息,是理想的进程通信工具。而且操作系统隐藏了进程通信的实现细节,即通信过程对用户是透明的。这样就大大地简化了通信程序编制上的复杂性。
1.消息缓冲通信的过程如下:
当某个进程需要向另一个进程发送消息时,便向系统申请一个消息缓冲区,并把要发送的数据送到消息缓冲区,然后把该消息缓冲区插入到接受进程的消息队列中。接受进程在接受消息时,只要从本进程的消息队列中摘下该消息缓冲区,即可从中取下所需的信息,
2.高级通讯原语SEND相RECEIVE的逻辑框图如图2.5所示。
图 2.5
(五)(10分)
1.局部页面置换只在当前进程分配的页面中选择一个被置换的页面:全局页面置换从整个存储器用户区的所有页面中选择一个被置换的页面。
在多道程序系统中,采用局部页面置换策略进行页面置换,即使某个进程出现了抖动现象,不致引起其他进程也产生抖动,-可以将抖动局限在较小的范围内。
2.可以在MBT表中增设一个"引用位",当MBT表中的页被访问时"引用位"置1,在MBT表中再增设一个指针域,用于记录进入内存的页面顺序,另设一个替换指针指向最近刚刚进入内存的页面。可以根据引用位的状态来判别各页面最近的使用情况,当需要置换一页时,选择其引用位为0的页淘汰。该算法的程序流程图如图2.6所示:
N
Y
图2.6 LUR近似算法的流程图i
(六)(15分)
为了提高系统的适应性和均衡性,避免死锁的产生,设备分配必须考虑安全性问题。设备无关性使得用户的应用程序独立于实际的物理设备,不仅方便了用户,而且设备分配比较灵活,也便于实现I/O重定向。
所谓安全状态是指,当多个进程动态地申请资源时,系统按某种顺序逐次地为每个进程分配所需的资源,使每个进程都可以在最终得到最大需求量后,依次顺利地完成。反之,如果不存在这样一种分配顺序使进程都能顺利完成,则称系统处于不安全状态。
当然,在系统处于不安全状态下时未必一定发生死锁,但是处于安全状态下的系统是一定不会发生死锁的。所以,避免死锁的关键就是:让系统在动态分配资源的过程中,不要进入不安全状态。银行家算法就是实现上述思想的一个典型算法。
银行家算法的基本思想是把操作系统比作银行家,操作系统管理的各种资源比为周转资金,申请资源的进程比作借款的主顾(即借款人)。银行家占杳有限的资金,他不可能满足所有借款人的请求,但可以满足一部分人的借款请求,等这些人归还后,又可把这笔资金借给他人,其原则是不能使银行家的钱被借完,使资金无法周转。
(七)(10分)
1.将一个文件目录分为基本目录项和名号目录项的好处是可以加快文件目录的检索速度。其原理是减少因查找文件内部号而产生的访问磁盘次数。因为在进行查找文件内部号的过程中不需要把文件控制块(即目录项)的所有内容都读入内存,所以在查找过程中减少所需读入的存储块就有可能减少访问磁盘的次数。但是,采用这种方法访问文件,当找到匹配的文件控制块后,还需要访问一次磁盘,才能读出全部的文件控制块信息。这就是为何采用这种方法在一定条件下并不能减少访问磁盘的次数的原因。
2.UNIX操作系统的打开文件系统调用open的处理过程可以分成以下四步:
(1)检索目录,从根目录或当前目录开始,沿目录树查找指定文件名的文件的i节点。若未找到或不允许访问,则转出错处理,否则执行第(2)步。
(2)分配内存i节点,如果该文件己被其他用户打开,则引用计数加1,否则分配内存i节点,并将磁盘i节点内容拷贝到内存i节点,引用计数置为1。
(3)分配文件表项,在系统打开文件表中,分配一个文件表项,指向内存i节点,并置其他初值。
(4)分配用户文件描述表项:在用户文件描述符表(即用户打开文件表)中分配一个表项,指向第(3)步中分配的表项,返回。
(八)(10分)
1.可以从以下几个方面来比较文件存储器(即外存)与内存的管理:
(1)主要任务,内存管理的主要任务是为多道程序的运行提供良好的环境:而外存管理的主要任务是为文件系统提供存储空间。
(2)基本功能,内存管理的基本功能包括内存空间的分配、回收,内存保护,内存扩充等,而外存管理的基本功能则只是对外存空间的管理。
(3)分配方式,内存和外存管理中,都可采用连续分配方式,且都以离散分配方式为主。
(4)分配算法和机制,对于连续分配方式,内存与外存管理中的分配和回收算法类似,主要有最先适应算法和最佳适应算法等。在离散分配方式中,两者所采用的机制不同,内存管理主要是利用页(段)表:而在外存管理中,则主要利用文件分配表FAT等。
(5)分配单位,内存以字节为单位,外存则以盘块为单位。
2.在UNIX系统中文件的物理结构采用混合索引结构。它是将文件所占用的物理块号直接或间接地存放在该文件索引节点的13个地址项中。系统把常规文件分成小型、中型、大型和巨型四类。
(1)当一个文件的规模为不超过10块时(属于小型文件),可以用该文件索引节点的13个地址项中的前10个直接记录该文件的物理块号,即直接索引。
(2)当一个文件的规模在11~256块之间时(属于中型文件),该文件索引节点的前10个地址为直接索引,第11个地址为一次间接索引。
(3)当一个文件的规模为超过256块时(属于大型文件),该文件索引节点的前10个地址为直接索引,第11个地址为一次间接索引,第12个地址为二次间接索引。
(对于巨型文件,该文件索引节点的前10个地址为直接索引,第11个地址为一次间接索引,第12个地址为二次间接索引,第13个地址为三次间接索引。)
UNIX系统文件的物理结构如图2.7所示。
直接0
直接1
直接2
直接9
一次间接
二次间接
三次间接
…
…
…
…
…
…
图2.7 UNIX文件的混合索引结构示意图
(九)(15分)计算题
1.(1)采用先来先服务作业调度算法时,作业的运行情况如下表所示:
作业执行次序
提交时间
运行时间
开始时刻
完成时刻
周转时间
带权周转时间
1
8:00
1.0
8:00
9:00
1.0
1.0
2
8:50
0.05
9:00
9:50
1.0
2.0
3
9:00
0.20
9:50
9:70
0.7
3.5
4
9:10
0.10
9:70
9:80
0.7
7.0
所以,平均周转时间为:
T=(1.O+1.O+0.7+0.7)/4=0.85
平均带权周转时间为:
W=(1.O+2.O+3.5+7.O)/4=3.375
(2)采用短作业优先调度算法时,作业的运行情况如下表所示:
作业执行次序
提交时间
运行时间
开始时刻
完成时刻
周转时间
带权周转时间
1
8:00
1.0
8:00
9:00
1.0
1.0
3
9:50
0.20
9:00
9:20
0.2
1.0
4
9:10
0.10
9:20
9:30
0.2
2.0
2
8:50
0.50
9:30
9:80
1.3
2.6
所以,平均周转时间为:
T=(1.O+0.2+0.2+1.3)/4=0.675
平均带权周转时间为:
W=(1.0+1.O+2.O+2.6)/4=1.65
(3)采用响应比高者优先作业调度算法时,作业的运行情况如下表所示:
作业执行次序
提交时间
运行时间
开始时刻
完成时刻
周转时间
带权周转时间
1
8:00
1.0
8:00
9:00
1.0
1.0
3
9:00
0.20
9:00
9:20
0.2
1.0
2
8:50
0.50
9:20
9:70
1.2
2.4
4
9:10
0.10
9:70
9:80
0.7
7.0
所以,平均周转时间为:
T=(1.O+0.2+1.2+0.7)/4=0.775
平均带权周转时间为:
W=(1.O+1.O+2.4+7.O)/4=2.85
2.(1)采用FIFO页面置换算法时,该作业运行时缺页情况如下表所示:
时刻
1
2
3
4
5
6
7
8
9
10
11
12
P
4
3
2
1
4
3
5
4
3
2
1
5
M
4
3
4
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
F
+
+
+
+
+
+
+
+
+
+
缺页中断次数为F=10; 失页率为f=10/12=83%。
(2)采用LRU页面置换算法时,该作业运行时缺页情况如下表所示:
时刻
1
2
3
4
5
6
7
8
9
10
11
12
P
4
3
2
1
4
3
5
4
3
2
1
5
M
4
3
4
2
3
4
1
2
3
4
4
1
2
3
3
4
1
2
5
3
4
1
4
5
3
1
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
F
+
+
+
+
+
+
+
+
缺页中断次数为F=8; 失页率为f=8/12=67%。
3.FCFS算法的调度顺序与请求顺序一致。SSTF算法总是先完成距当前存取臂最近的柱面上的输入输出请求。SCAN算法是存取臂从磁盘的一端出发,向另一端移动,遇到需要访问的柱面就完成访问请求,直至到达磁盘的另一端。到达磁盘的另一端后,存取臂的移动方向就倒转过来,继续完成这一方向的访问请求。
(1)采用FCFS算法调度时,磁头移动顺序为:
143→86→147→91→177→94→150→102→175→130
磁头移动总距离为:
(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)
+(175-102)+(175-130)=565
(2)采用Sstf算法调度时,磁头移动顺序为
143→147→150→130→102→94→91→86→175→177
磁头移动总距离是162(柱面)
(3)采用SCAN算法调度时,磁头移动顺序为:
143→147→150→175→177→(199)→130→102→94→91→86
磁头移动总距离是255(柱面)。
10.10西北大学2000年考研操伟系统试题
(二)(每小题3分,共15分)简述下列概念的联系与区别
1.并发与并行 2.对换与切换 3.管道与通道
4.直接通信与间接通信 5.死锁与"饿死"
(二)(10分)关于处理机调度,试问:
1.什么是处理机三级调度?
2.处理机三级调度分别在什么情况下发生?
3.各级调度分别完成什么工作?
(三)(10分)
在一个飞机订票系统中,多个用户共享一个数据库。多用户同时查询是可以接收的,指但若一个用户要订票需更新数据库时,其余所有用户都不可以访问数据库。请画出用户查询与订票的逻辑框图。要求:当一个用户订票而需要更新数据库时,不能因不断有查询者的到来而使他长期等待。
(四)(10分)有5个待运行作业为A,B,c,D,E,各自估计运行时间为9,6,3,5,x。试问采用哪种运行次序可以使得平均响应时间最短?(答案依赖于x)
(五)(10分)关于存储管理,试问:
1.在分页、分段和段页式存储管理中,当访问一条指令或数据时,需要访问内存几次? 各做什么处理?
2.假设一个分页存储系统具有快表,多数活动页表项都可以存在其中。如果页表放在内存中,内存访问时间是1",若快表的命中率是85%,则有效存取时间为多少?若快表的命中率为50%,那么有效存取时间为多少?
(六)(10分)
在现代计算机系统中,存储器是十分重要的资源,能否合理有效地使用存储器,在很大程度上反映了操作系统的性能,并直接影响到整个计算机系统作用的发挥。请问:
1.主存利用率不高主要表现为哪几种形式?
2.可以通过哪些途径来提高主存利用率?
(七)(10分)关于设备管理:
1.试给出两种I/O调度算法,并说明为什么I/0调度中不能采用时间片轮转法。
2.I/O缓冲区是I/O系统中重要的数据结构。请给出山区操作系统中块设备缓冲区分配的处理流程。
(八)(10分)关于文件系统:
1.请介绍在文件存储空间的管理中几种常用的技术。
2.在UNIX操作系统中,文件存储空间的管理采用什么方法?简述其分配与释放过程。
(九)(10分)在UNIX操作系统中,试问:
1.有哪几种类型的文件?
2.试描述“关闭文件close”系统调用的实现过程。
3.若盘块为1KB,每块可放256个地址,如何将下列文件的字节偏移量转换为物理地址?
9000; 18000; 420000
(十)(5分)什么是分布式操作系统? 它与网络操作系统有何不同?试说明分布式操作系统或网络操作系统在传统的操作系统管理模式上需要做哪些改进。
西北大学2000年考研操作系统试题解答
(一)简述下列概念的联系与区别(每小题3分,共15分)
1.若干个事件在同一时刻发生称为并行;若干个事件在同一时间间隔内发生称为并发。并行是并发的特例,并发是并行的拓展。
2.对换是指把内存中暂时不能运行的进程或暂时不用的程序和数据,换出到外存上,以腾出足够的内存空间,把己具备运行条件的进程或进程所需的程序和数据换入内存。切换是指将CPU的使用权从一个进程转到另一个进程。在某些系统中,进程切换往往伴随着信息的对换。
3.管道(Pipe)是连接两个进程的一个共享文件,进程通过对该文件的读、写实现进程间的通信。管道文件实际上是一个临时文件,它以磁盘为中介实现进程间的通信,与内存相比,其通信速度较慢。通道(I/O处理机)是实现I/O操作的硬件装置。通道对管道的实现提供了硬件支持。
4.消息系统有直接通信和间接通信之分。
(1)直接通信。直接通信方式有一个基本原则; 进程在发送和接收消息时,必须指明接收者或发送者的名字。这种通信方式中Send和Receive原语定义如下:
send(P,message),将消息发送给进程P
Receive(Q,message),接收来自进程Q的消息这种通信方式中通信链路具有如下特征,每一对欲通信的进程间自动建立了一条双向通信链,只需知道对方的标识信息便可进行通信:每条通信链路严格地对应两个进程; 相互通信的一对进程之间存在一条通信链路。
(2)间接通信。进程间通过信箱进行消息传递的通信方式称为间接通信,又称为"信箱通信"。信箱(Mailbox)可以抽象地看成是一个虚设备,进程可以把消息(也称信件)放入信箱,也可以从中取出一条消息。信箱必须有唯一的标识符。在这种通信方式中,某个进程可以通过一组不同的信箱同时与其它多个进程通信。两个进程之间只有当它们有一个可共享的信箱时才可进行通信。
间接通信方式中的通信链路具有如下特征,只有当两个进程有了一个可共享的信箱时,通信链路才在两者之间建立; 一条通信链路可以连接两个以上的进程; 每一对通信进程之间可以有多条不同的通信链路,每一条链路对应一个信箱; 通信链路可以是单向的,也可以是双向的。
5.死锁是因竞争资源而引起的一种具有普遍性的现象,在多道程序系统中,由于多个并发进程共享系统的资源,如使用不当有可能造成一种僵局,即系统中两个或多个进程无限期地等待永远不会发生的条件,在无外力的干预下,这些进程都不能向前推进,我们称之为死锁。死锁不仅在两个进程之间发生,也可能在多个进程之间,甚至在系统全部进程之间发生。当死锁发生时,一定布一个资源被无限期地占用而得不到释放。
"饿死"是指系统中的每个资源占用者都在有限的时间内释放它所占用的资源,但是仍然存在申请者永远得不到资源的现象。因此,在操作系统中,不仅要考虑如何防止"死锁",还要考虑如何避免"饿死"。
(二)(10分)
1.操作系统中有三级调度:高级调度(作业调度)、中级调度(交换调度)和低级调度(进程调度)。它们构成系统内的多级调度。不同类型的操作系统不一定完全都实现上述三种调度。
2.处理机三级调度发生的情况是:
①高级调度。高级调度是根据系统内所有资源的使用情况,一旦可能便从后备作业中选择一道作业进入系统,并创建相应的进程,分配必要的系统资源,然后将进程"就绪"。
②低级调度。低级调度即为CPU调度,它是根据CPU资源的使用情况及时分配CPU,即从"就绪"的进程中选择一个进程在CPU上"运行"。这种调度不仅要求调度算法本身的时间复杂度小,而且要求策略精良,因为低级调度直接影响着系统的整体效率。在多道程序系统中必须提供低级调度。
③中级调度。在内存中常常有许多进程处于某种等待状态,这些进程在"等待"期间无谓地占用着内存资源。如将它们暂时换至外存,则所节省出来的内存空间可用以接纳新的进程,一旦换出外存的进程,具备运行条件时再将其重新换入内存。为此,在逻辑上将主存延伸,用一部分外存空间(称为交换区)替代主存,并且实施交换调度(中级调度)。在各种类型的操作系统中可以根据内存的配置、系统能承受的最大负载,有选择地进行中级调度,或者不实施中级调度。
3.高级调度完成作业调度,使"后备"状态的作业变为"执行"状态:中级调度完成内存和外存信息的交换调度:低级调度完成进程调度,使"就绪"的进程在CPU上"运行"。
(三)(10分)
本题是典型的读者一写者问题。查询操作是读者,订票操作是写者,而且要求写者优先。
为了达到这一控制效果,可以引入一个变量rc,用于记录当前正在运行的读者进程数。每个读者进程进入系统后需对rc值加1。当rc值由O变为1时,说明是第一个读者进程进入,因此需要该读者进程对控制写者进程的信号量Srw进行P操作,以便与写者进程互斥运行:当rc值由非0值增加时,说明不是第一个读者进程,此时控制写者进程的信号量已经过P操作控制禁止写者进程进入,因此不需要再次对该信号量进行P操作。当读者进程退出时,需对rc做减1操作。如发现减1后m值变为0,说明是最后一个读者进程退出,因此需要该读者进程对控制写者进程的信号量Srw进行V操作,以便使写者进程能够进入。资源计数变量rc也是一个临界资源,需要用信号量Src对它进行互斥访问控制。为了提高写者的优先级,我们还增加了一个信号量S,用以在写进程到达时封锁其后续的读者进程。用户查询与订票的逻辑框图如图2.8所示。
查询者 定票者
N
Y
N
Y
如图2.8 用户查询与订票的逻辑框图
(四)(10分)
由于短作业优先算法会使系统平均响应时间最短,所以:
当0<x<3时,应该采用的运算顺序为,x,3,5,6,9。
当3≤x≤5时,应该采用的运算顺序为,3,x,5,6,9。
当5≤x≤6时,应该采用的运算顺序为,3,5,x,6,9。
当6≤x≤9时,应该采用的运算顺序为,3,5,6,x,9。
当X>9时,应该采用的运算顺序为,3,5,6,9,x。
(五)(10分)
1.在分页存储管理中,当访问一条指令或数据时需要访问内存至少两次。一次是访问存放在内存中的页表PMT,实现地址变换; 另一次是访问所需的数据。
在分段存储管理中,当访问一条指令或数据时,也需要访问内存至少两次。一次是访问存放在内存中的段表SMT,实现地址变换;另一次是访问所需的数据。
在段页式存储管理中,当访问一条指令或数据时,需要访问内存至少三次。一次是访问存放在内存中的段表SMT,查找段号所对应的页表; 再一次是访问存放在内存中的页表PMT,实现地址变换; 第三次是访问所需的数据。
2.若快表的命中率是85%,则有效存取时间为:
0.85×1+(1-0.85)×(1+1)=1.15μs
若快表的命中率为50%,则有效存取时间为:
0.5×1+(1-0.5)×(1+1)=1.5μs
(六) (10分)
1.内存利用率不高主要表现为以下几个方面:
(1)内存中存在着大量的、分散的、难以利用的碎片;
(2)暂时或长期不能运行的程序和数据,占据了大量的内存空间:
(3)当作业较大时内存只能装入少量的作业,当它们被阻塞时将使CPU空闲,从而也降低了内存的利用率。
(4)内存中存在着重复的拷贝。
2.可以采用下列方法和途径来提高内存的利用率:
(1)改连续分配方式为离散分配方式,以减少内存的碎片;
(2)增加对换机制,将那些暂时不用的程序和数据从内存换到外存;
(3)采用虚拟存储管理技术,使更多的作业能装入内存,使CPU更加忙碌;
(4)引入动态装入和连接机制,尽量避免装入本次运行中不用的程序;
(5)引入存储器共享机制,允许一个正文段或数据段被若干个进程共享,以减少内存中的重复拷贝。
(七)(10分)
1.两种常用的I/O调度算法是:
(1)先请求先服务。当有多个进程对同一设备提出I/O请求时,该算法把所有I/O请求进程按请求顺序排成一个等待队列。I/O调度程序把该I/0设备分配给队列中的第一个进程。
(2)优先权高者优先。该算法把所有I/O请求进程按优先权由高到低的顺序排成一个等待队列。I/0调度程序把该I/O设备分配给队列中的第一个进程(其优先权最高)。
在I/O调度中不能采用时间片轮转法。因为在I/O操作中,有些设备的固有属性是独占性,一经某进程占用,便一直到使用完该设备才能释放。而且在由通道控制的I/0系统中,通道程序一经启动便一直进行下去,直到最后完成。在它完成之前不会产生中断。
2.UNIX操作系统中调用getblk过程分配缓冲区。当要读磁盘数据时,核心首先检查要读入的盘块内容是否已在某个缓冲区中,若发现已在某个缓冲区中,便不必再从磁盘上读入。仅当数据未在任何缓冲区中时,核心才需从磁盘上将数据读入,这时才需为其分配一个空闲缓冲区。类似地,当要把数据写入一个特定盘块时,核心应先检查该块内容是否己在某缓冲区中,仅当该块内容不在缓冲区中时,才需分配一个空闲缓冲区。获取空闲缓冲区时应提供的输入参数是文件系统号和磁盘块号。getblk过程分配缓冲区时,可分为如下两种情况:
(1)缓冲区在散列队列上。进入geblk过程后,首先根据文件系统号和盘块号去查找散列队列,若找到与文件系统号和块号相匹配的缓冲区,便叫.进一步检查该缓冲区是否空闲。若空闲,则应先上锁,以防止其他进程对它进行访问,然后把它从空闲链上摘下;若忙,则表明缓冲区已被其它进程上锁,因此,暂时不能对它进行访问而进入睡眠,直到该缓冲区变为空闲时再将它唤醒。
(2)缓冲区不在散列队列上。若在散列队列中找不到与文件系统号及块号相匹配的缓冲区,便只有从空闲链表中找一个缓冲区。若空闲链表己空,则无法进行分配,进程睡眠,直到空闲链表中出现缓冲区为止; 若空闲链表不空,这时可从链首摘下一缓冲区,若此缓冲区标记有"延迟写",此时应将该缓冲区内容异步地写到磁盘上,再从空闲链表中摘下一个缓冲区,并调整该缓冲区所在的散列队列,即将该散列队列从原来的散列队列调整到新的散列队列中。因为当该缓冲区重新分配后,缓冲区对应的盘块号发生了变化,从而也相应地改变了其所在的散列队列。
(八)(10分)
由于文件存储设备是分成若干个大小相等的物理块,并以块为单位来交换信息的,因此,文件存储空间的管理实质上是空闲块的组织和管理问题,它包括空闲块的组织、空闲块的分配与回收等。下面是三种在文件存储空间的管理中常用的技术:
(1)空闲文件目录。一个空闲文件是由文件存储器上连续的空闲块组成的。系统为所有的空闲文件建立一个单独的目录表。每个表目对应一个空闲文件,记录该空闲文件的起始块号和块数。
空闲文件的分配与回收算法与内存管理中的可变式分区管理的方法相似,同样可以采用最先适应算法、最佳适应算法、最坏适应算法等。
(2)空闲块链。空闲块链把文件存储设备上的所有空闲块链接在一起。当申请者需要空闲块时,分配程序从链首取下所需的空闲块,然后调整链首指针。反之,当回收空闲块时,把释放的空闲块逐个插入空闲链上。这种方法的优点是分配和回收一个空闲块的过程都非常简单,缺点是空闲块链可能很长。改进的办法是采用空闲盘区链接法或成组链接法。
(3)位示图。位示图利用一个二进制位来记载一个物理块的使用情况。系统为每个文件存储设备建立一张位示图,反映文件存储设备所有物理块的使用情况。每个物理块对应位示图上的一位,如果该位为0,则表示所对应的块是空闲的:反之,则表示所对应的块已被分配。利用位图来进行空闲块分配时,只需查找图中为0的位,并将其置1;反之,回收时只需把相应的位由1改为0。由于位示图很小,可以将它保存在内存中。
2.在UNIX操作系统中的文件存储介质可采用磁盘或磁带。通常把每个磁盘或磁带看作是一个文件卷,在每个文件卷上可以存放一个具有独立目录结构的文件系统。一个文件卷包含许多物理块。O#块一般用于系统引导或空闲;1#块称为超级块,用于存放文件卷的资源管理信息;从2#块起开始的若干块用于存放磁盘索引节点(具体块数由文件系统的大小决定),以后各块存放文件数据。
UNIX操作系统采用成组链接法对空闲盘块加以组织。该方法首先把文件存储设备中的所有空闲块按50块(或100块,下同)划分为一组,组的划分按从后往前的顺序进行,每组的第一块用来存放前一组中各块的块号和总块数。由于第一组的前面再也没有其他组存在,因此第一组的块数为49块。最后一组可能不足50块,而且由于该组后再也没有其他组,所以,该组的物理块号与总块数只能存放在管理文件存储设各用的文件资源表(超级块的一部分)中。系统在初启时把文件资源表复制到内存? 从而使文件资源表中存放有最后一组空闲块号和总块数的堆校进入内存,空闲块的分配与回收可在内存中进行。
当申请者提出申请空闲块要求时,盘块分配程序从找顶取出一空闲盘块号,将其对应的盘块分配,然后找顶指针下移一格,总空闲块数减1。若该盘块是找底,则将该块中存放的下一组的块号和总块数读入内存,然后才将该盘块分配,并重置校顶指针。
在系统回收空闲盘块时,找顶指针加1,把回收的空闲块号填入钱顶位置,空闲块数加1。如果找顶指针等于50,表示该组己满,需把当前战所帘的50个块号与块数写入新回收的空闲块中,重置找顶指针。
(九)(10分)
1.在UNIX操作系统中,有下列三种类型的文件:
(1)目录文件。目录文件是文件系统中树型结构的分支节点,它可以包含普通文件和次一级目录文件。目录文件也同普通文件一样存储在外存的文件系统存储区中。
(2)普通文件。普通文件是指系统程序或用户程序以及可执行的目标程序等。在详细列出文件内容时,在行首用"~"符号表示是普通文件。普通文件按拥有的信息量大小,又可分为小型文件、中型文件、大型文件和巨型文件四种。
(3)特别文件。特别文件是与硬件有关的文件。在UNIX中每个I/O设备都被看成是一个特别文件,为了检索和处理方便,系统把所有I/O设备都放在/dep/lp目录文件中,例如打印机是一个特别文件,可以写成/dep/lp。特别文件不包含信息,他们是操作系统标准I/O设备的通道,是用户与硬件设备连接的桥梁。当用户将数据写到文件"/dev/lp"中时,操作系统核心截取了这些数据,并把它们输出到打印机上打印出来。对用户来说,对特别文件的操作与对普通文件的操作是一样的。用户不需要启动设备驱动程序。有关硬件设备的操作均由操作系统完成。在目录表中,特别文件在行首用字母"b"表示。
2.当用户不再使用一个己打开的文件时,应调用close过程将该文件关闭,即断开用户程序与该文件之间已建立的通路。在UNIX系统中,由于允许一个文件被多个进程所共享,故只有在没有进程需要此文件时,即文件索引节点中的引用计数减1后为0时,才能真正关闭该文件。其语法格式如下:
int close(fd); int fd;
其中,fd是文件打开操作返回的文件描述符。
在执行close过程时,核心首先根据用户文件描述符M从相应的用户文件描述符表中获得指向文件表项的指针,再对该文件表项的引用计数做减1操作。
close的处理过程如下:
(1)若其结果值不为0,表示仍有其他进程在使用该文件表项,不能回收该文件表项。此时,仅将"所在的用户文件描述符表项置为空。
(2)若其结果值为0,表示无用户使用该文件表项,核心便可将对应的文件表项置为空,并进一步对其内存索引节点的引用计数做减1操作。若结果不为0,表明仍有进程在访问该文件,故不能回收其内存索引节点。
(3)仅当内存索引节点的引用计数为0时,才能回收该内存索引节点,即将指定文件关闭。
3.UNIX系统的文件逻辑结构采用流式文件。根据逻辑文件的字节偏移量可计算出该字节所在的物理块号。计算过程分两步:第一步,将逻辑文件的字节偏移量转换为文件的逻辑块号和块内偏移量。其转换方法是:将逻辑文件的字节偏移量整除以盘块大小的字节数,所得的商即为文件的逻辑块号,余数就是块内偏移量。第二步,将文件的逻辑块号转换为物理块号。其转换方法是:使用多重索引结构,在索引节点中根据逻辑块号通过直接索引或间接索引找到相应的物理块号。
因为Ll=INT(9000,1024)=8 B1=MOD (9000,1024) =808
L2=INT(18000,1024)=17 B1=MOD(18000,1024)=592
L3=INT(420000,1024)=410 B1=MOD(420000,1024)=160
所以,当文件的字节偏移量为9000时,其逻辑块号为8,只需在该文件的索引节点中直接索引(I-addr[7])即可找到相应的物理块号。当文件的字节偏移量为18000时,其逻辑块号为17,只需在该文件的索引节点中通过一次间接索引(I-addr[10])即可找到逻辑块号相应的物理块号。当文件的字节偏移量为420000时,其逻辑块号为410,需要在该文件的索引节点中通过(I-addr[11])二次间接索引即可找到逻辑块号对应的物理块号。
(十)(5分)
分布式操作系统是以实现并行任务分配、并行进程通信和分布控制的机构和实现分散资源管理等功能为目的的系统程序。网络操作系统是以资源共享和信息交换为目的的操作系统。
分布式系统和网络操作系统都是多机系统的支撑软件,都基于I/0或网络互联,但在很多情况下,网络操作系统是在本机局部操作系统之上建立的,形成了两个层次,而分布式操作系统则是一个独立的整体。
分布式操作系统与传统的集中式操作系统的主要区别表现在通信、资源管理和系统结构三个方面。因此分布式操作系统在传统的操作系统管理模式上还应增加网络管理模块,即通讯软件和网络控制软件。
10.11 西安理工大学2001年考研操件系统试题
(一)名词解释(每小题2分,共10分)
1.特权指令 2.地址再定位 3.联想存储器 4.死锁 5.文件目录
(二)单项选择题(每题2分,共20分)
1.在下列存储管理方案中,不适应于多道程序设计的是________。
A.单一连续分配 B.固定式分区分配
C.可变式分区分配 D.段页式存储管理
2.在可变式分区分配方案中,将空白区在空白区表中按地址递增次序排列是要________。
A.最佳适应算法 B.最差适应算法
C.最先适应算法 D.最迟适应算法
3.设有四个作业同时到达系统,每个作业的执行时间均为1小时,它们在一台处理机上按单道方式运行,则平均周转时间为________。
A.1小时 B.5小时 C.2小时 D.25小时
4.原语的主要特点是________。
A.不可分割性 B.不可再现性 C.不可屏蔽性 D.不可访问性
5.在进程一资源图中,资源Rj分配给进程Pi应表示为________。
A.(Pi,Rj) B.(Rj,Pi) C.|(Rj,Pi)| D.|(Pi,Rj)|
6.联想存储器在计算机系统中是用于________的。
A.存储文件信息且 B.与主存交换信息
C.地址变换 D.存储通道程序
7.设备控制块是________。
A.UCB B.JCB C.PCB D.CCB
8.在下列文件中,不便于文件增、删操作的是________。
A.索引文件 B.连续文件 C.Hash文件 D.串联文件
9.UNIX文件的目录结构采用________。
A.简单目录 B.二级目录
C.系统目录 D.带交叉勾链的树型目录
10.PC-DOS中盘空间的分配单位是________。
A.扇区 B.簇 C.页 D.物理块
(三)填空题(每空1分,共10分)
1.进程通常由______、_________和___________三部分组成。
2.实时系统按应用的不同分为__________和___________两种。
3.采用直接存取法存取文件时,对__________文件效率最高,对__________文件效率最低。
4.用户编程时使用_________地址,处理机执行程序时使用__________地址。
5.为了记录系统中所有的I/0设备,操作系统专门设置了一张___________表。
(四)判断题(每题1分,共10分〉
1.应用软件是加在裸机上的第一层软件。
2.原语的执行是屏蔽中断的。
3.时间片轮转法一般用于分时系统中。
4.PCB是进程存在的唯一标识。
5.每个作业都有自己的地址空间,地址空间中的地址都是相对于起始地址"0"单元开始的,因此逻辑地址就是相对地址。
6.文件的物理结构密切依赖于文件存储器的特性和存取方法。
7.移臂调度的目标是使磁盘的旋转周数最小。
8.最短查找时间优先算法(SSTF)的调度原则,就是要求磁头的移动距离最小。该算法有产生"饿死"的可能。
9.按最先适应算法分配的分区,一定与作业要求的容量大小最接近。
10.页表(SMT)的作用是实现逻辑地址到物理地址的映射。
(五)简答题(每题5分,共25分)
1.什么叫响应时间?影响分时系统响应时间的因素有哪些?
2.在设计进程调度算法时,应着重考虑哪儿个问题?
3.试述段页式存储管理方案的基本思想。
4.在文件系统中,采用多级树型文件目录结构有何优点?
5.什么是逻辑设各? 什么是物理设各?如何实现从逻辑设备到物理设备的转换?
(六)综合题(每题5分,共25分)
1.单道批处理系统中,有四个作业,其有关情况如下表所示。在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。
作业
J1
J2
J3
J4
提交时间/h
8.0
8.6
8.8
9.0
运行时间/h
2.0
0.6
0.2
0.5
2.在一个分页存储管理系统中,页面大小为4KB,系统中的地址占24位,给定页面变换表如下表所示。
(1)计算逻辑地址(页号为3,页内地址为100)的物理地址:
(2)说明地址变换过程。
页号P
块号B
0
3
1
4
2
9
3
7
3.在一个请求分页管理中,一个程序的页面走向为4,3,2,1,4,3,5,4,3,2,1,5。利用LRU页面置换算法。
(1)当分配给程序4个存储块时,求出缺页中断的次数。
(勾当分配给程序5个存储块时,求出缺页中断的次数。
(3)以上结果说明了什么?
4.设某系统磁盘共有500块,块号从0~499,若用位示图法管理这500块的盘空间,当字长为32位时:
(1)位示图需要多少个字?
(2)第i字第j位对应的块号是多少?
5.假设磁盘共有200个柱面,编号从O~199.当前存取臂在120号柱面上服务,并刚刚完成了105号柱面的请求。如果现有进程P1、P2、P3和P4分别请求的柱面号为:186,l58,115,90。按下列三种算法调度时,试问:①系统调度的次序是什么? ②存取臂移动总量为多少?
(1)先来先服务 (2)最短查找时间优先 (3)电梯调度算法
西安理工大学2001年考研操作系统试题解答
(一)名词解释
1.我们把只允许管态下使用而不允许在算态下使用的指令称为特权指令。常见的特权指令有关于对外设使用的指令,关于访问程序状态的指令和存取特殊寄存器指令等。
2.将用户程序中的逻辑地址变换成计算机主存的物理地址的过程称之为地址再定位。
地址再定位有两种方式:静态再定位和动态再定位。
3.在页式或段式存储管理系统中,为了提高查表速度,在地址变换机构中加入了一个高速、小容量的存储器,专门存放当前作业最常用的页表(或段表)信息,称为联想存储器。联想存储器又叫快表。联想存储器的主要作用是快速完成动态地址变换。
4.死锁是因竞争资源而引起的一种具有普遍性的现象,在多道程序系统中,由于多个并发进程共享系统的资源,如使用不当有可能造成一种僵局,即系统中两个或多个进程无限期地等待永远不会发生的条件,在无外力的干预下,这些进程都不能向前推进,我们称之为死锁。
5.文件目录是文件系统的关键数据结构。文件目录的作用如同图书馆的书籍目录一样,用来将许许多多的文件有条不紊地组织起来,以便能够迅速而准确地查找文件。通常,文件目录应包含下列信息:
(1)有关文件的标识信息:例如文件的名称符号。
(2)有关文件结构的信息:例如文件长度、文件存放在外存中的物理地址等。
(3)有关文件存取控制信息:例如文件属性、文件主及共享用户的标识、存取权限等。
(4)有关文件的管理信息:例如文件建立的时间、保留时间、最新修改时间等。
(二)单项选择题
1.A 2.C 3.D 4.A 5.B 6.C 7.A 8.B 9.D 10.B
(三)填空题
1.程序 数据集合 进程控制块PCB 2.过程控制系统 数据处理系统
3.索引 串联 4.逻辑 物理 5.系统设备表SDT
(四)判断题
1.错 2.对 3.对 4.对 5.对 6.对 7.错 8.对 9.错 10.对
(五)简答题
1.响应时间是指从终端发出命令到系统予以应答所需的时间。
影响分时系统响应时间的几个因素是:对换速度、用户数目、时间片以及对换信息量。
2.在设计进程调度算法时,应着重考虑以下四个问题:
(1)引起进程调度的时机; (2)进程调度的方式;
(3)进程队列的组织; (4)进程调度算法的选择。
3.段页式存储管理技术结合分段管理在逻辑上的优点以及分页管理在物理上的优点。
用分段方法来分配和管理虚存,用分页方法来分配和管理实存。即把作业分段,段内分成虚页,实存分成实页。
在段页式管理系统中,每一段不再占有连续的实存,而是被分为若干个页面,所以段页式存储管理实际上是对页面进行分配和管理。因此,有关段的靠拢、辅存管理以及段长限制等问题都得到很好的解决。而分段的优点,如动态扩大段长、动态链接装入、段的共享、段的保护措施等都被保留了下来。
4.树型目录结构是目前最常用的目录结构,因为它具有如下优点:
(1)解决了文件的重名问题;
(2)有利于文件的分类;
(3)提高了文件的检索速度;
(4)能进行存取权限的控制。
5.用户编程使用的设备是逻辑设备,计算机系统实际配置的设备是物理设备。通过系统设置的逻辑设备与物理设备的映射关系实现从逻辑设备到物理设备的转换。
(六)综合题分析响应比高者优先调度算法是指在每次调度作业运行时,先计算后备作业队列中每个作业的响应比,然后挑选响应比最高的投入运行。
在8.0小时,因为只有作业J1到达,系统先将作业J1投入运行。作业J1运行两个小时后完成。这时三个作业都已到达,要计算三个作业的响应比,然后使响应比最高的投入运行。三个作业的响应比为:
作业J2的响应比=1+(10.0-86)/0.6=333
作业J3的响应比=1+(10.0-8.8)/0.2=7
作业J4的响应比=1+(10.0-9.O)/0.5=3
从计算的结果来看,作业J3的响应比最高,所以让作业J3先执行。作业J3执行0.2小时后完成,此时作业J2和作业J4的响应比为:
作业J2的响应比=1+(10.2-8.6)/0.6=3.67
作业J4的响应比=1+(10.2-9.0)/0.5=3.4
从计算的结果来看,作业J2的响应比最高,所以再让作业J2执行。
可见,四个作业的执行次序为:作业J1,作业J3,作业J2,作业J4。
计算结果如下表:
作业号
到达时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
1
8.0
2.0
8.0
10.0
2.0
1.0
2
8.6
0.6
10.2
10.8
2.0
3.33
3
8.8
0.2
10.0
10.2
1.4
7
4
9.0
0.5
10.8
11.3
2.3
4.6
平均周转时间为:
T=(2.O+2.O+1.4+2.3)/4=1.93
平均带权周转时间为:
W=(1.0+3.33+7+4.6)/4=3.98
(1)逻辑地址(页号为3,页内地址为100)的物理地址为:
7×4KB+100=28KB+100=28772
(2)在请求分页存储管理方案中,系统是通过页面变换表来进行地址转换的。先将逻辑地址分解成页号P和页内地址W两部分,然后查页面变换表,可得页号P对应的物理块号为B,从而变换出对应的物理地址为:
物理地址=块号×页面大小+页内地址
3.(1)当分配给程序4个存储块时,利用LRU页面置换算法,缺页中断情况如下表所示:
T
1
2
3
4
5
6
7
8
9
10
11
12
P
4
3
2
1
4
3
5
4
3
2
1
5
M
4
3
4
2
3
4
1
2
3
4
4
1
2
3
3
4
1
2
5
3
4
1
4
5
3
1
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
F
+
+
+
+
+
+
+
+
当分配给程序4个存储块时,缺页中断的次数为8次。
(2)当分配给程序5个存储块时,利用LRU页面置换算法缺页中断情况如下表所示:
T
1
2
3
4
5
6
7
8
9
10
11
12
P
4
3
2
1
4
3
5
4
3
2
1
5
M
4
3
4
2
3
4
1
2
3
4
4
1
2
3
3
4
1
2
5
3
4
1
2
4
5
3
1
2
3
4
5
1
2
2
3
4
5
1
1
2
3
4
5
5
1
2
3
4
F
+
+
+
+
+
当分配给程序5个存储块时,缺页中断的次数为5次。
(3)以上结果说明:利用LRU页面置换算法,当增加主存容量时,不会增加缺页中断的次数。
4.(1)位示图需要,500/32=16个字。
(2)第i字第j位对应的块号是:32×i+j。
5.(1)用先来先服务算法,
系统调度的次序是P1,P2,P3,P4。
存取臂移动总量是(186-120)+(186-158)+(158-115)+(115-90)=162。
(2)最短查找时间优先算法:
系统调度的次序是P3,P4,P2,P1。
存取臂移动总量是(120-115)+(11590)+(158-90)+(186-158)=126。
(3)电梯调度算法:
系统调度的次序是P2,P1,P3,P4。
存取臂移动总量是(158-120)+(186-158)+(186-115)+(115-90)=159。
10.12西安理工大学2000年考研操作系统试题
(一)名词解释(每题2分,共10分)
1.系统调用 2.多道程序设计 3.周转时间 4.碎片 5.系统抖动
(二)单项选择题(每题2分,共20分)
1.配置了操作系统的计算机是一台比原来的物理计算机功能更强的计算机,这样的计算机只是一台逻辑上的计算机,称为_______计算机。
A.并行 B.真实 C.虚拟 D.共享
2.采用SPOOLing技术后,使得系统资源利用率________。
A.提高了 B.降低了
C.有时提高有时降低 D.出错的机会增加了________。
3.设有三个作业J1、J2、J3,其运行时间分别为1、2、3小时,假定这些作业同时到达,并在一台处理机上按单道运行,那么按序列执行时其平均周转时间最小。
A.J1; J2; J3 B.J2; J3; J1 C.J2; J1; J3 D.J1; J3; J2
4.分时系统的响应时间与下列哪一个因素无关? ________。
A.时间片长短 B.系统时钟的频率
C.终端用户数 D.主存和后援存储器之间的信息对换量
5.设有五个进程共享一个互斥段,如果最多允许两个进程同时进入互斥段,则所采用的互斥信号量初值应该是________。
A.5 B.2 C.1 D.0
6.通道又称I/O处理机,它用于实现_________之间的信息传输。
A.主存与外设 B.CPU与外设 C.主存与外存 D.CPU与外存
7.进程从运行状态到阻塞状态可能是由于________。
A.进程调度程序的调度 B.现运行进程的时间片用完
C.现运行进程执行了P操作 D.现运行进程执行了V操作
8.并发进程之间
A.彼此无关 B.必须同步
C.必须互斥 D.可能需要同步或互斥
9.银行家算法在解决死锁问题中是用于的。
A.预防死锁 B.避免死锁 C.检测死锁 D.解除死锁
10.当CPU处于管态时,它可以执行的指令应该是
A.仅限于特权指令 B.仅限于非特权指令
C.仅限于访管指令 D.计算机系统的全部指令
(三)填空题(每空1分,共10分)
1.进程控制块PCB是进程存在的_________________; 程序和数据集合是进程的________。
2._________是一种典型的顺序存取存储设各,而______________是一种典型的直接存取存储设备。
3.在通道进行I/O操作期间,要访问两个内存固定的单元:___________和___________。
4.在二级文件目录结构中,一级目录是,二级目录是____________。
5.可以预防死锁的方法是_____________法和________________法。
(四)判断题(每题1分,共10分)
1.按最差适应算法(WF)分配的分区,一定与作业要求的容量大小最接近。
2.访管指令不是特权指令,它能在管态下运行,也能在算态下运行。
3.多道程序设计可以缩短系统中作业的执行时间。
4.作业调度是高级调度,而进程调度是低级调度。
5.时间片越小,系统的响应时间就越小,系统的效率就越高。
6.CPU和通道之间的关系是主从关系,CPU是主设备,通道是从设各。
7.在分页存储管理中,减少页面大小,可以减少内存的浪费。所以,页面越小越好。
8.虚拟设各技术是在一类物理设备上模拟另一类物理设备的技术,它可以将独占设备改造成为共享设备。
9.进程A与进程B共享变量S1,需要互斥:进程B与进程C共享变量S2,需要互斥。从而,进程A与进程C也必须互斥。
10.虚拟存储器的基本思想是把作业地址空间和主存空间视为两个不同的地址空间,前者称为虚存,后者称为实存。
(五)简答题(每题5分,共25分)
1.为保证文件系统的安全性,可以采取哪些措施?
2.什么叫寻道? 访问磁盘时间由哪几部分组成? 其中哪一个是磁盘调度的主要目标? 为什么?
3.为建立虚拟存储系统需要哪些条件?
4.作业和进程有什么区别和联系?
5.给同存储保护方法,并说明各适时场合?
(六)综合题(每题5分,共25分)
1.设作业A(30K)、B(7OK)和C(5OK)依次请求内存分配,内存现有F1(100K)、F2(50K)两个空闲区,如图2.11(a)所示。分别采用最佳适应算法和最差适应算法,画出内存分配情况示意图。
2.某系统有同类资源m个,供n个进程共享。如果每个进程最多申请x个资源(其中1≤x≤m)。
请证明:当n(x-1)+1≤m时,系统不会发生死锁。
3.设有六个进程P1、P2、P3、P4、P5、P6,它们有如图2.9所示的并发关系。试用P、V操作实现这些进程间的同步。
P1
P2 P3
P4 P5
P6
图 2.9
4.设作业的虚拟地址为24位,其中高8位为段号,低16位为段内相对地址。试问:
(1)一个作业最多可以有多少段?
(2)每段的最大长度为多少字节?
(3)某段式存储管理采用如下段表,试计算[0,430]、[1,50]、[2,30]、[3,70]的主存地址。其中方括号内的前一元素为段号,后一元素为段内地址。当无法进行地址变换时,应说明产生何种中断。
段号
段长
主存起始地址
是否在主存
0
600
2100
是
1
40
2800
是
2
100
否
3
80
4000
是
5.在PC-DOS中,某磁盘文件A与B,它们所占用的磁盘空间如图2.10所示。试问:
A、B文件在磁盘上各占几簇? 依次写出各文件的簇号。
FDT FAT
……
A
002
B
003
簇号
FAT值
000
FFD
001
FFF
002
004
003
008
004
009
005
007
006
FFF
007
FFF
008
006
009
005
……
……
图 2.10
西安理工大学2000年考研操作系统试题解答
(一)名词解释(每题2分,共10分)
1.系统调用是用户在程序中能用"访管指令"调用的由操作系统提供的子功能的集合。每一个子功能称为一条系统调用命令(或广义指令)。系统调用是操作系统在程序级给用户提供的接口。
2.多道程序设计是指在主存中同时存放多道用户作业,它们都处于执行的开始点和结束点之间。
3.所谓周转时间,是指作业从进入到处理完成所经历的时间。
4.所谓碎片,是指存储器上不能利用的空闲区。
5.在分页存储系统中,将某一页从实存移到辅存为"出页",从辅存调入主存为"入页"。刚"出页"的页又要"入页",或刚"入页"的页又要"出页",这种反复出入页的现象称为"抖动"现象或者称为"系统颠簸"。
(二)单项选择题(每题2分,共20分)
1.C 2.A 3.A 4.B 5.B 6.A 7.C 8.D 9.B 10.D
(三)填空题(每题1分,共10分)
1.标志 实体
2.磁带 磁盘
3.CAW(通道地址字) CSW(通道状态字)
4.主目录(MFD) 用户文件目录(UFD)
5.资源静态分 配资源顺序分配
(四)判断题(每题1分,共10分)
1.错 2.对 3.错 4.对 5.错
6.对 7.错 8.对 9.错 10.对
(五)简答题(每题5分,共25分)
1.为保证文件系统的安全性,可以采取对文件的保护和保密等措施。
实现文件保护措施的一般情况可以从两个方面考虑,即防止系统故障包括软件、硬件故障造成的破坏和防止用户共享文件可能造成的破坏。前者可以采用建立副本和定时转储的方法,后者可以采用树形文件目录、存取控制表、规定文件使用权限等方法。另外,实现文件保密的措施包括隐藏文件目录、设置口令和使用密码等。
2.把磁头从当前位置移动到指定的磁头位置的操作过程叫寻道。访问磁盘时间是由寻道时间、旋转等待时间(即延迟时间)和传送时间组成的。其中传送时间是硬件设计时就固定、的,而寻道时间、延迟时间则与信息在磁盘上的位置有关。其中寻道时间是磁盘调度的主要目标,因为磁头臂是机械移动,所以寻道时间比其它两个时间长得多,是影响磁盘调度的主要因素。
3.为建立虚拟存储系统需要的条件有下列四个方面:
(1)要有一定容量的主存储器:
(2)要有大容量的辅助存储器:
(3)要有动态地址变换机构:
(4)要采用虚拟存储管理方案。
4.作业和进程之间的区别和联系是:
(1)作业是用户向计算机提交任务的任务实体,而进程则是完成用户任务的执行实体,是向系统申请分配资源的基本单位。
(2)一个作业可以由多个进程组成,且必须至少由一个进程组成。
(3)作业的概念主要用在批处理系统中,而进程的概念则用在所有的多道系统中。
5.常用的三种存储保护方法是:
(1)界地址寄存器法,适用于分区存储管理:
(2)锁钥相配法,适用于分页和分区存储管理:
(3)设置存取权限法,适用于分段存储管理。
(六)综合题(每题5分,共25分)
1.分析,最佳适应算法的基本思想是空闲区按容量递增顺序排列,即X1≤X2≤X3≤…≤Xn。当要求分配一个空闲区时,由小到大进行查找。如果要求分配一个容量为S的分区,则从Xl开始顺序比较,直至S≤Xi; 然后从Xi中分配S,如有剩余部分,作为一个空闲区插入适当位置; 如果比较到Xi仍不能满足要求,则分配失败。
该题中按BF算法,作业A(3OK)分配到F2空闲区后,F2变为2OK; 作业B(7OK)分配到F1空闲区后,F1变为3OK; 作业C(5OK)分配失败。
最佳适应算法的基本思想是空闲区按容量递减顺序排列,即X1≥X2≥X3≥…≥Xn。如果要求分配一个容量为S的分区,并且S≤X1;则从X1中分配S,如有剩余部分,作为一个空闲区插入适当位置;如果S >X1,则分配失败。
该题中若按WF算法,作业A(3OK)分配到F1后,F1变为70K; 作业B(7OK)也分配到F1空闲区:作业C(5OK)分配到F2空闲区。
答案,按BF算法内存分配情况如图2.11(b)所示。
按WF算法内存分配情况如图2.11(c)所示
A(30K)
B(70K)
C(50K)
F1(100K)
F2(50K)
B(70K)
F1(30K)
A(30K)
F2(50K)
(a) (b) (c)
图 2.11
2.由于每个进程最多申请使用x个资源,在最坏的情况下,每一个进程都得到了(x-1)个资源,并且现在均需申请最后一个资源。这时系统剩余资源数为,m-n(x-1)。如果系统剩余资源数大于1,即系统还有一个资源可以使用,就可以使这几个进程中的一个进程获得所需的全部资源。该进程可以运行结束,释放出所占有的资源。供其它进程使用,从而每一个进程都可以执行结束。
因而,当m-n(x-1)≥1时,即n(x-1)+1≤m时,系统不会发生死锁。
3.用P、V操作实现这些进程间的同步的算法如下:
BEGIN
s1,s2,s3,s4,semaphore;
s1:=s2:=s3:=s4:=O
COBEGIN
Process P1:
Begin
do all work;
V(s1);
V(sl);
End
Process P2:
Begin
P(s1)
do all work;
V(s2);
End
Process P3:
Begin
P(s1);
do all work;
V(s3);
End
Process P4:
Begin
P(s2);
do all work;
V(s4);
End
prorcess P5:
Begin
P(s3);
do all work;
V(s4);
End
prorcess P6:
Begin
P(s4);
P(s4);
do all work;
End
COEND
END
4.
(1)一个作业最多可以有28=254个段。
(2)每段的最大长度为216=64KB=65536字节。
(3)逻辑地址[0,430]的主存地址为,2100+430=2530;
逻辑地址[1,50]无法进行地址变换,因为产生了越界中断;
逻辑地址[2,30]无法进行地址变换,因为产生了缺段中断;
逻辑地址[3,70]的主存地址为,4000+70=4070。
5.分析,DOS磁盘空间的分配采用文件分配表FAT,磁盘空间的分配单位是簇(相当于块)。簇的大小因盘的类型而异。每个簇在FAT表中占用一项。FAT表的头两项用来标记盘的类型,其余的每个项包含三个十六进制的字符,若为000,表示该簇是空闲的; 若为FFF,表示该簇是一个文件的最后一簇; 若为其它任何十六进制字符,则表示该簇是某一文件的下一簇号。
一个文件占用了磁盘上的哪些簇,可用FAT表中形成的链表结构来说明。首先在文件目录表FDT中找到该文件的目录项,目录项中登记有文件的首簇号,再到FDT表中依次找到其余的簇号。
答案,文件A在磁盘上占用5簇,簇号依次是002,004,009,005,007。
文件B在磁盘上占用3簇,簇号依次是003,008,006。
10.13河南大学2002年考研操作系统试题(一)(共50分)
一、判断题(每小题1分,共5分)
你认为正确的在题后括号内划“√”,反之划“×”。
1.在使用已存在的文件之前,应首先打开文件。 ( )
2.在页式存储管理系统中当发生缺页中断时应淘汰掉内存中一页。 ( )
3.作业可被看作是用户向计算机提交任务的任务实体。 ( )
4.在UNIX系统中把一个程序看作是一个可执行文件。 ( )
5.在单处理机系统中任何时候只可能有一个进程处于执行状态。 ( )
二.填空(每空1分,共5分)
1.在操作系统中,信号量表示资源的实体,是一个与队列有关的______型变量,其值仅能由___________来改变。
2.便于实现动态连接的存储管理方案是________________。
3.文件的符号名与物理地址的转换是通过_______实现的。
4.分时系统中_________是衡量一个分时系统性能的一项重要指标。
三、单项选择(每题1分,共5分)
在每小题的四个备选答案中选出一个正确答案,并将其代码写在括号内。不选、错选或多选者,该题无分。
一个计算机系统可以认为由以下四个层次构成,而我们所说的裸机是指( )。
A.硬件层 B.操作系统层
C.语言处理程序层 D.应用程序层
2.外部设备完成了预定的操作或在操作过程中出现错误所引起的中断是( )。
A.程序中断 B.I/O中断
C.外中断 D.硬件故障中断
3.在一个计算机系统中,特权指令( )下执行。
A.只能在管态 B.只能在算态
C.可在管态,也可在算态 D.不能在管态,也不能在算态
4、在段页式存储系统中,一个作业对应( )。
A、多个段表 B、一个段表,一个页表
C、一个段表,多个页表 D、多个段表,多个页表
5.UNIX系统中把设备分为( )
A.输入设备和输出设备 B.字符设备和块设备
C.系统设备和用户设备 D.共享设备和虚拟设备四.问答题(每题5分,共15分)。
1.操作系统在计算机系统中处于何种地位?操作系统的作用是什么?
2.什么叫进程?为什么要引人“进程”这一概念?
3.访管指令、特权指令和系统调用之间有什么区别和联系?
五.下面是两个并发执行的进程。它们能正确执行吗?若不能,试举例说明,并修改之(12分)。
Cobegin
Var x,integer;
Process P1
Var y,z,integer;
Begin
x:=1;
y:=0;
If x>=1 then y:=y+1;
z:=y;
End
Process P2
Var t,u,integer;
Begin
x:=0;
t:=0;
If x<1 then t:=t+2;
u:=t;
End
Coend
六.在一请求分页存储管理系统中,主存容量为1MB,被划分为256块,每块为4KB,现有一作业,其页表如下表所示。
页 号
块 号
状 态
0
24
0
1
26
0
2
32
0
3
—
1
4
—
1
试问:
若给定一逻辑地址为9016(十进制),求其物理地址。(4分)
(2)若给定一逻辑地址为12300(十进制),其物理地址如何得到?(4分)
河南大学2002年考研操作系统试题(一)答案判断题
1,√ 2,× 3,√ 4,√ 5,√
二.填空题
1.整 P、V操作
2.段式存储管理
3.文件目录
4.相应时间单项选择
1.A 2.B 3.A 4.C 5.B
问答题操作系统在计算机系统中处于硬件层之上,是对硬件层的第一次扩充。在这一层上实现了操作系统的全部功能,并提供了相应的接口。(2分)
操作系统的作用是:
提高计算机系统的效率(1分)
提高计算机系统资源的利用率(1分)
方便用户使用计算机(1分)
进程是程序的一次执行,该程序可与其他程序并发执行。(2分)
在进程这一概念出现以前,人们已习惯于使用程序的概念。那么为什么要引入“进程”的概念呢?
为了提高系统资源的利用率,出现了多道程序设计技术,但多道程序的并发执行和资源共享带来了新的问题,破坏了程序的封闭性和可再现性,程序和机器执行程序的活动不在一一对应,并发程序之间有可能存在相互制约关系。并发程序的这些特性:独立性、并发性、动态性和相互制约,反应了并发程序的本质,程序的概念已不能反映程序并发执行的实质,因此,人们引入了进程的概念来描述并发程序的执行过程。(3分)
访管指令、特权指令和系统调用三者既有区别又有联系。(1分)
访管指令是一类机器指令,执行访管指令可以引起访管中断,访管指令不是特权指令,它可在算态下执行,也可在管特下执行。(1分)
特权指令也是一类机器指令,特权指令只能在管态下执行,不能在算态下执行。(1分)
系统调用不是机器指令,每个系统调用命令相当与一个函数,实现操作系统提供的一种子功能。用户在编程序时也可以使用这些系统调用命令,是操作系统和用户的编程接口。1(分)
在系统调用命令中,总是包含一条访管指令,当系统调用执行到访管指令时,就引起访管中断,在进入中断处理程序后便由算态转入管态,在管态下可以执行特权指令完成操作系统提供的功能。当中断处理结束后又返回算态。(1分)
P1和P2是两个并发进程不能正确执行,可能导致结果的不确定性,如:
进程P1 进程P2
(1) x:=1 (a) x:=0
(2) y:=0 (b) t:=0
(3) if x>=1 then y:=y+1 (c ) if x<1 then t:=t+2
(4) z:=y (d) u:=t
如果P1和P2按顺序执行,即(1)(4)(a)(d)
则结果为:y=1,z=1,t=2,u=2
如果执行顺序是:(1)(2)(a)(b)(3)(4)(c)(d)
则结果为:y=0,z=0,t=2,u=2
结果不确定性的原因在于使用了公共变量,要求P1和P2必须互斥执行,程序修改如下:
Cobegin
Var x,integer; S,semaphore;
S:=1
Process P1
Var y,z,integer;
Begin
P(S);
x:=1;
y:=0;
if x>=1 then y:=y+1; V(s);
z:=y;
V(S)
End
Process P2
Var t,u,integer;
Begin
P(S);
x:=0;
t:=0;
if x<1 then t:=t+2 ; V(S);
u:=t;
V(S);
End
Coend
六.(1)对给定的逻辑地址
页号为2,页内地址为824.
又有页表可知,该页被装入主存的第32块中,所以,其物理地址为,128K+824
(2)若给定逻辑地址为12300,,其页号为3,查页表,该页的状态位为1可知未装入主存,因而产生缺页中断。中断后由中断处理程序将该页装入主存,然后进行地址变换。
10.14 河南大学2002年考研操作系统试题(二)(共50分)
一、判断题(每小题1分,共5分)
你认为正确的在题后括号内划“√”,反之划“×”。
1,作业A的进程B处于阻塞状态,作业A也一定处于阻塞状态。 ( )
2,一次仅允许一个进程使用的资源称为临界资源。 ( )
3.文件名与物理地址之间的转换是通过文件目录实现的。 ( )
4.在设备管理中,对缓冲区或缓冲队列的操作必须互斥。 ( )
5.在UNIX系统中所有进程都是利用系统调用fork创建的。 ( )
二.填空(每空1分,共5分)
1.设备管理的主要任务是__________和CPU之间进行__________。
2.批处理系统的基本特征是“批量”,它把提高________作为主要设计目标。
3.便于实现动态连接的存储管理方案是________________。
4..缓冲的引入可以缓和CPU和I/O设备间____________的矛盾。
三、单项选择(每题1分,共5分)
在每小题的四个备选答案中选出一个正确答案,并将其代码写在括号内。不选、错选或多选者,该题无分。
1.当正在运行的程序要求数据传输时,CPU向通道发( ),命令通道开始工作。
A.通道命令 B.I/O指令
C.程序状态字 D.中断信号
2.采用直接存取法来读写盘上的物理记录时,效率最高的是( )。
A.连续结构文件 B.索引结构文件
C.串连结构文件 D.其他结构文件
3、在UNIX系统中使用的目录结构是( )。
A.单级 B.二级
C.树型 D.三级
4、在单处理机系统中,操作的“原子”性可以通过( )来实现。
A.特权指令 B.访管指令
C.屏蔽中断 D.系统调用
5、对简单分页系统,作业的信息要求在作业运行前( )。
A.必须全部装入主存 B.可以部分装入主存
C.不必装入主存 D.需要时再装四.问答题(每题5分,共15分)。
1.为什么要引人虚存的概念?虚存的最大容量由什么决定?
2.实现多道程序设计要解决哪些问题?
3.设备管理的目标是什么?设备管理包括哪些基本功能?
五.有一阅览室,读者进入时必须先在一张登记表上进行登记,该表为每一个座位列出一个表目,包括座位号、姓名,读者离开时要撤消登记信息。阅览室有180个座位,试问:
为描述读者的动作,应编写几个程序?应设置几个进程?进程和程序之间的对应关系如何?(5分)
试用P、V操作描述这些进程间的同步关系。(5分)
六.在一个请求分页存储系统中,一个程序的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,设分配给该程序的存储块数为4,试分别求出采用FCFS和LRU页面置换算法发生缺页中断的次数和缺页中断率(要求给出页面置换的过程)。(10分)
河南大学2002年考研操作系统试题(二)答案断题
1,√ 2,√ 3,√ 4,× 5、√
二.填空题
1.低级 高级 2.效率 3.运行 4.速度不匹配三.单项选择题
1.B 2.B 3.C 4.C 5.A
四、问答题在计算机系统中,主存的容量有一定的限制,不可能太大以满足各种用户的需要,而在技术上外存容量可以相当大。为了给大作业用户提供方便,使他们不在承担对主存和外存的具体分配和管理工作,而有操作系统把主存和外存统一管理起来。
虚存实际上就是作业的地址空间,作业地址空间的大小取决于计算机系统的地址结构。因此,虚存的最大容量取决于地址寄存器的位数。例如地址寄存器的位数为32位时,其虚存的最大容量可达4GB。
为了实现多道程序设计,必须解决以下三个问题:
存储保护和地址重定位。
处理机的管理和调度。
资源的管理和调度。
3.设备管理的目标是:
方便性,使用户在使用各种设备时感到方便;
并行性,提高系统中各种设备工作的并行性;
均衡性,使系统中各种设备的分配具有均衡性;
独立性,用户在编程序时不使用物理设备名而使用逻辑设备名,使得用户所要求的输入和输出与物理设备无关。
设备管理的基本功能:
动态地记录设备的状态,在有通道的系统中,还应该掌握通道、控制器的工作状态。
为满足进程的I/O请求,按某种调度算法将一设备分配给要求设备的进程。
完成实际的I/O操作。
五.(1)每个读者都可视为一个进程,有多少个读者就有多少个进程,这些进程称为读者进程,设为Pi(I=0,1,2,…)。读者进程Pi执行的程序包括:登记、阅览、撤消。每个读者的活动都相同,所以其程序也相同。进程与程序之间的关系是:各读者进程共享同一个程序。
(2)在读者进程执行的程序中,对登记与撤消都需要互斥执行,其信号量S1的初值为1;而对进入阅览室需互斥执行,信号量s2的初值为180。
读者进程Pi
P(S2)
P(S1)
登记
V(S1)
阅览
P(S1)
撤消
V(S1)
V(S2)
六.(1)FCFS算法的页面置换如下:
时刻
1
2
3
4
5
6
7
8
9
10
11
12
页面走向
4
3
2
1
4
3
5
4
3
2
1
5
M=4
4+
3+
4
2+
3
4
1+
2
3
4
1
2
3
4
1
2
3④
5+
1
2

4+
5
1

3+
4
5

2+
3
4

1+
2
3

5+
1
2
3
标志
+
+
+
+
+
+
+
+
+
+
缺页次数F=10,缺页中断率 10/12=83%
(2)LRU算法的页面置换如下:
时刻
1
2
3
4
5
6
7
8
9
10
11
12
页面走向
4
3
2
1
4
3
5
4
3
2
1
5
M=4
4+
3+
4
2+
3
4
1+
2
3
4
4
1
2
3
3
4
1②
5+
3
4
1
4
5
1
1
3
4
5
1
2+
3
4

1+
2
3

5+
1
2
3
标志
+
+
+
+
+
+
+
+
缺页次数F=8,缺页中断率8/12=67%
10.5 河南大学2003年考研操作系统试题(共50分)
一、判断题(每小题1分,共5分)
你认为正确的在题后括号内划“√”,反之划“×”。
1.作业A的进程B处于阻塞状态,作业A也一定处于阻塞状态。 ( )
2.一次仅允许一个进程使用的资源称为临界资源。 ( )
3.文件名与物理地址之间的转换是通过文件目录实现的。 ( )
4.在设备管理中,对缓冲区或缓冲队列的操作必须互斥。 ( )
5.在UNIX系统中所有进程都是利用系统调用fork创建的。 ( )
二.填空(每空1分,共5分)
1.设备管理的主要任务是控制设备和CPU之间进行__________。
2.对于一个进程来说,其运行的正确性不仅取决于程序的正确性,而且也与进程在执行中与其他相关进程正确的实施____________有关。
3.便于实现动态连接的存储管理方案是________________。
4.缓冲的引入可以缓和CPU和I/O设备间____________的矛盾。
5.UNIX系统采用________结构存放文件物理块的地址。
三、单项选择(每题1分,共5分)
在每小题的四个备选答案中选出一个正确答案,并将其代码写在括号内。不选、错选或多选者,该题无分。
1.在进程的组成成分中,进程在运行中不可修改的部分是( )。
A.私用程序段 B.共享程序段 C.数据集合 D.进程控制块
2.采用直接存取法来读写盘上的物理记录时,效率最高的是( )。
A.连续结构文件 B.索引结构文件 C.串连结构文件 D.其他结构文件
3、在UNIX系统中使用的文件目录结构是( )。
A.单级 B.二级 C.树型 D.三级
4、在单处理机系统中,操作的“原子”性可以通过( )来实现。
A.特权指令 B.访管指令 C.屏蔽中断 D.系统调用
5、最适合分时系统的进程调度算法是( ) 。
A.FCFS B.SSJF C.优先数法 D.轮转法四.问答题(每题5分,共15分)。
1.设备管理的目标和功能是什么?
2.实现多道程序设计要解决哪些问题?
3.请求页式管理与静态页面管理有什么区别?当访问的页不在内存应如何处理?
五.公路上有一座桥,该桥一次只允许一辆汽车在桥上行驶。当桥上有汽车时,其它汽车不能上桥。试问:
这是一个同步问题还是互斥问题?(2分)
(4)用信号量和P、V操作描述并发过程的活动。(8分)
六.在一个请求分页存储管理系统中,一个程序的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,设分配给该程序的存储块数为4,试分别求出采用FCFS和LRU页面置换算法时,发生缺页中断的次数和缺页中断率(要求给出页面置换的过程)。(10分)
河南大学2003年考研操作系统试题答案一、判断题
1,× 2,√ 3,√ 4,√ 5、×
二、填空题
1,I/O操作 2.互斥和同步 3.段式管理 4.速度不匹配 5.索引三.单项选择题
1.B 2.A 3.C 4.C 5.D
四、问答题
1,设备管理的目标是:
选择和分配I/O设备以便进行数据传输操作;控制I/O设备和CPU(或内存)之间交换数据;为用户提供一个友好的透明接口;提高设备和设备之间、CPU和设备之间,以及进程和进程之间的并行操作,以便操作系统获得最佳效率。
设备管理的基本功能:
提供和进程管理系统的接口;进行设备分配;实现设备和设备、设备和CPU等之间的并行操作;进行缓冲区管理。
2.为了实现多道程序设计,必须解决以下三个问题:
存储保护和地址重定位。
处理机的管理和调度。
资源的管理和调度。
3.请求页式管理是在静态页面管理的基础上实现的。它们之间的根本区别在于是否要将一个作业的全部地址空间同时装入主存。请求页式管理不要求将作业的全部地址空间同时装入主存。基于这一点,请求分页存储管理可以提供虚存,而分页存储管理确不能提供。
由于一个作业的地址空间不同时全部装入主存,在作业执行过程中,当所需页面不在主存时,便引起缺页中断。中断发生后,转中断处理程序。中断处理程序的主要工作是将所需的页面调入主存。当主存无空闲块时,按系统采用的页面置换算法将某页淘汰,然后将所需页面装入主存,修改页表。
五.(1)这一问题是互斥问题。桥是汽车进程互斥使用的资源。
(2)每了辆汽车对应一个进程,进程数量不确定。用Pi(i=0,1,2,…)表示汽车进程;设互斥信号量s,其初值为”1”。
汽车进程Pi的过程可描述如下:
汽车进程Pi (i=1,2,3…)
P(S)
汽车上桥
在桥上行驶
汽车下桥
V(S)
六.(1)FCFS算法的页面置换如下:
时刻
1
2
3
4
5
6
7
8
9
10
11
12
页面走向
4
3
2
1
4
3
5
4
3
2
1
5
M=4
4+
3+
4
2+
3
4
1+
2
3
4
1
2
3
4
1
2
3④
5+
1
2

4+
5
1

3+
4
5

2+
3
4

1+
2
3

5+
1
2
3
标志
+
+
+
+
+
+
+
+
+
+
缺页次数F=10,缺页中断率 10/12=83%
(2)LRU算法的页面置换如下:
时刻
1
2
3
4
5
6
7
8
9
10
11
12
页面走向
4
3
2
1
4
3
5
4
3
2
1
5
M=4
4+
3+
4
2+
3
4
1+
2
3
4
4
1
2
3
3
4
1②
5+
3
4
1
4
5
1
1
3
4
5
1
2+
3
4

1+
2
3

5+
1
2
3
标志
+
+
+
+
+
+
+
+
缺页次数F=8,缺页中断率8/12=67%