操作系统复习总.doc

操作系统复习总
操作系统2018-2019学年第1学期考试试题（B）卷
一、单项选择题（每小题2分，共20分）
1．在一个计算机系统中，特权指令（ ）下执行。
A.只能在管态 B.只能在用户态
C.可在管态，也可在用户态 D.不能在管态，也不能在用户态
2.实时操作系统必须在_______内完成来自外部的事件。
A.响应时间 B.周转时间 C.规定时间 D.调度时间
3、最适合分时系统的进程调度算法是( ) 。
A.FCFS B.SSJF C.优先数法 D.轮转法
4.进程从运行状态进入就绪状态的原因可能是_____。
A.被选中占有处理机 B.等待某一事件
C.等待的事件已发生 D.时间片用完
5.设有五个进程共享一个互斥段,在同一时间最多允许一个进程进入互斥段,则所采用的互斥信号量初值应该是________。
A.5 B.2 C.1 D.0
6.银行家算法在解决死锁问题中是用于的。
A.预防死锁 B.避免死锁 C.检测死锁 D.解除死锁
7.在下列存储管理方案中,不适应于多道程序设计的是________。
A.单一连续分配 B.固定式分区分配
C.可变式分区分配 D.段页式存储管理
8.UNIX文件的目录结构采用________。
A.简单目录 B.二级目录
C.系统目录 D.带交叉勾链的树型目录
9.文件系统的主要目的是________。
A.实现对文件的按名存取 B.实现虚拟存储
C.提高外存的读写速度 D.用于存储系统文件
10.下列算法中用于磁盘移臂调度的是。
A时间片轮转法 B.LRU算法
C.最短寻找时间优先算法D.优先级高者优先算法
二、判断题（每小题2分，共10分）
1.采用多道程序设计的系统中,系统的程序道数越多,系统的效率就越高。
2.作业的联机控制方式适用于终端作业。
3.时间片越小,系统的响应时间就越小,系统的效率就越高。
4.程序的并发执行是指同一时刻有两个以上的程序,它们的指令在同一处理器上执行。
5.按最先适应算法分配的分区,一定与作业要求的容量大小最接近。
三、填空题（每小题2分，共10分）
1.为实现CPU与外部设备的并行工作,系统引入了__________硬件机制。
2.UNIX系统采用________结构存放文件物理块的地址。
3.文件的符号名与物理地址的转换是通过_______实现的。
4.用户编程时使用_________地址,处理机执行程序时使用__________地址。
5.采用资源有序分配算法可以_______死锁的发生。
四、简答题(每小题5分，共20分)
1.请介绍在文件存储空间的管理中几种常用的技术。
2.为什么要引入SPOOLing系统? SPOOLing系统可带来哪些好处?
3.进程和线程的主要区别是什么?
4产生死锁有四个必要条件?
五、计算题（40分）
1．在一个飞机订票系统中,多个用户共享一个数据库。多用户同时查询是可以接收的,指但若一个用户要订票需更新数据库时,其余所有用户都不可以访问数据库。请画出用户查询与订票的逻辑框图。要求:当一个用户订票而需要更新数据库时,不能因不断有查询者的到来而使他长期等待。（15分）
2．在一个请求分页存储管理系统中，一个程序的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,设分配给该程序的存储块数为4,试分别求出采用FCFS和LRU页面置换算法时，发生缺页中断的次数和缺页中断率（要求给出页面置换的过程）。 （15分）
3．磁盘请求的柱面按10,22,20,2,40,6,38的次序到达磁盘的驱动器,寻道时每个柱面移动需要6ms。计算按以下算法调度时的寻道时间:
(1)先来先服务; (2)下一个最邻近的柱面; (3)电梯算法。
假设以上所有情况磁头臂均起始于柱面20,并刚刚完成了19号柱面的请求。（10分）
操作系统试卷2018-2019-1-B答案
一、单项选择题(每空2分，共20分)
1
2
3
4
5
6
7
8
9
10
A
C
D
D
C
B
A
D
A
C
二、判断题（5*2分）
1.错
2.对
3.错
4.错
5.错
三、填空题（5*2分）
1.中断和通道
2.索引
3.文件目录
4.逻辑 物理
5.预防
四、简答题（4*5分）
1.
由于文件存储设备是分成若干个大小相等的物理块,并以块为单位来交换信息的,因此,文件存储空间的管理实质上是空闲块的组织和管理问题,它包括空闲块的组织、空闲块的分配与回收等。下面是三种在文件存储空间的管理中常用的技术:
(1)空闲文件目录。一个空闲文件是由文件存储器上连续的空闲块组成的。系统为所有的空闲文件建立一个单独的目录表。每个表目对应一个空闲文件,记录该空闲文件的起始块号和块数。空闲文件的分配与回收算法与内存管理中的可变式分区管理的方法相似,同样可以采用最先适应算法、最佳适应算法、最坏适应算法等。
(2)空闲块链。空闲块链把文件存储设备上的所有空闲块链接在一起。当申请者需要空闲块时,分配程序从链首取下所需的空闲块,然后调整链首指针。反之,当回收空闲块时,把释放的空闲块逐个插入空闲链上。这种方法的优点是分配和回收一个空闲块的过程都非常简单,缺点是空闲块链可能很长。改进的办法是采用空闲盘区链接法或成组链接法。
(3)位示图。位示图利用一个二进制位来记载一个物理块的使用情况。系统为每个文件存储设备建立一张位示图,反映文件存储设备所有物理块的使用情况。每个物理块对应位示图上的一位,如果该位为0,则表示所对应的块是空闲的:反之,则表示所对应的块已被分配。利用位图来进行空闲块分配时,只需查找图中为0的位,并将其置1；反之,回收时只需把相应的位由1改为0。由于位示图很小,可以将它保存在内存中。
2.
所有字符设备都是独享设备并属于慢速设备,本质上属于顺序存取设备。因此,一个进程在某台字符设各上进行数据交换时,往往要等待较长时间,并且在该数据交换完成之前,其他进程不能同时访问这台设备。而且动态分配也不能真正提高这类设备的利用率,当一个进程正在使用这类设备进行一次较大量的数据交换时,其他需要同时访问该设备的进程就要等待较长的时间,从而降低了整个系统的并发能力。SPOOLing技术正是针对上述问题提出的一种设备管理技术。
SPOOLing系统可带来的好处如下:
(1)字符设备和各虚拟设备之间的数据交换由SPOOLing进程统一调度实施,而切这种数据交换以并行方式进行,系统呈现出高度的并行性:
(2)用户使用的是虚拟设备,可以减少用户进程的等待时间。
在多道程序系统中,用程序模拟脱机输入/输出时外围控制机的功能,这样便可在主机的直接控制下实现脱机输入/输出功能。此时的外围操作与CPU对数据的处理同时进行,这种在联机情况下实现的外围设备同时操作称为SPOOLing,也称伪脱机。
SPOOLing系统的核心思想是利用一台可共享、高速、大容量的块设备(磁盘)来模拟独占设备的操作,使一台独占设备变成多台可并行使用的虚拟设备。SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的好处是提高了I/O操作的速度,将独占设备改造为共享设备,实现了虚拟设备的功能。
3.
进程和线程是构造操作系统的两个基本元素,两者之间的主要区别是:
(1)调度方面: 线程作为调度分派的基本单位。
(2)并发性方面: 进程之间可以并发执行。
(3)拥有资源方面: 进程是拥有资源的基本单位,线程除少量必不可少的资源外,基本上不拥有资源,但它可以访问其隶属进程的资源。
(4)系统开销: 进程间切换时要涉及到进程环境的切换,开销比较大:而线程间切换只需保存和设置少量的寄存器内容,因此进程间切换的系统开销远大于线程间切换的系统开销。
4.
(1)互斥控制。进程对所要求的资源进行排它控制,在一段时间内一个资源仅能被一个进程使用。
(2)不可剥夺控制。进程所获得的资源在未释放前,不能被其它进程剥夺。即使该进程处于阻塞态,它所占资源也不能被其它进程使用,只有等待占有该资源的进程释放后才能给别的进程使用。
(3)请求和保持。为了提高资源利用率,进程在运行过程中可随时提出对各种资源的请求,当进程因请求资源而阻塞时,对已获得的资源保持不放。
(4)环路等待条件。在发生死锁时,进程的资源状态图必构成环路,即前一进程保存着后一进程所要求的资源。
五、计算（40分）
1.(15分)
本题是典型的读者一写者问题。查询操作是读者,订票操作是写者,而且要求写者优先。
为了达到这一控制效果,可以引入一个变量rc,用于记录当前正在运行的读者进程数。每个读者进程进入系统后需对rc值加1。当rc值由O变为1时,说明是第一个读者进程进入,因此需要该读者进程对控制写者进程的信号量Srw进行P操作,以便与写者进程互斥运行:当rc值由非0值增加时,说明不是第一个读者进程,此时控制写者进程的信号量已经过P操作控制禁止写者进程进入,因此不需要再次对该信号量进行P操作。当读者进程退出时,需对rc做减1操作。如发现减1后m值变为0,说明是最后一个读者进程退出,因此需要该读者进程对控制写者进程的信号量Srw进行V操作,以便使写者进程能够进入。资源计数变量rc也是一个临界资源,需要用信号量Src对它进行互斥访问控制。为了提高写者的优先级,我们还增加了一个信号量S,用以在写进程到达时封锁其后续的读者进程。用户查询与订票的逻辑框图如图所示。
查询者 定票者
P(S)
P(S)

P(Srw)
P(Src)

rc=rc+1

更新数据库中的数据

rc=1?
N
V(Srw)

Y
V(S)
P(Srw)

P(Src)

P(S)

在数据库中查询所需的信息

P(Src)

Rc=rc-1

Rc=0?
N

Y
V(Srw)

V(Src)

用户查询与订票的逻辑框图
2．（15分）
（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
3
1
3
4
5
1
2+
3
4
⑤
1+
2
3
④
5+
1
2
3
标志
+
＋
＋
＋

＋

＋
＋
＋
缺页次数F=8,缺页中断率8/12=67%
3．（10分）
该题的解题方法是先计算出每种算法的柱面移动总量。因为每个柱面移动需要6ms,所以,寻道时间=柱面移动总量×6ms。
(1)先到先服务算法的调度顺序为:10,22,20,2,40,6,38
柱面移动总量为:10+12+2+18+38+34+32=146
寻道时间为:146×6ms=876ms
(2)下一个最邻近柱面算法调度顺序为:20,22,10,6,2,38,40
柱面移动总量为:0+2+12+4+4+36+2=60
寻道时间为:60×6ms=360ms
(3)电梯算法调度顺序为:20,22,38,40,10,6,2
柱面移动总量为:0+2+16+2+30+4+4=58
寻道时间为58×6ms=348ms
一． 判断题（正确划“√”，错误划“×”，10分）
1． 在分时系统中，由于采用了分时技术，用户可以独占计算机的资源。（ ）
2． 操作系统的一个重要概念是进程，因此不同进程所执行的代码也一定不同。（ ）
3．计算机系统采用多道程序设计技术后，缩短了每个程序的执行时间。（ ）
4． 操作系统用PCB管理进程，用户进程可以从PCB中读出与本身运行状态有关的信息。（ ）
5．存储管理中，固定分区比可变分区的存储器利用率高，因为它不产生碎片。（ ）
二． 填空题（10分）
1、程序的 执行是现代操作系统的基本特征之一，为了更好地描述这一特征而引入了 这一概念。
2、进程存在的标志是 。
3、如果系统中有n个进程，则在就绪队列中进程的个数最多为 。
4、每执行一次P操作，信号量的数值S减1。若S＝30，则该进程 ；若S<0，则该进程 。
5、计算机系统一般都设计有两种运行状态， 和 。
6、在段页式存储管理系统中，面向 的地址空间是段式划分，面向 的地址空间是页式划分。
三． 简答题（40分）
1．简述操作系统的5个基本功能。
2．什么是特权指令？如果允许用户进程执行特权指令，会带来什么结果？
3． 指出如下的每一个进程状态间的转换是否可能发生。如果可能发生，试举一个可以引起这种转换的例子。
（a）从运行态到就绪态
（b）从运行态到阻塞态
（c）从阻塞态到运行态
（d）从运行态到终止态
4． 什么是临界区？
5． 并行与并发有哪些区别？
6． 进程通信有哪几种主要方式？
7．什么是原语？
8．你认为学习操作系统的意义何在？
四． 系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机。设每个用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P,V操作写出这些进程使用打印机的算法。（20分）
五． 阅读下列程序，写出运行结果并对结果进行分析。（20分）
# include <unistd.h>
# include <signal.h>
# include <stdio.h>
int pid1,pid2;
main()
{
int fd[2];
char outpipe[100],inpipe[100];
pipe(fd);
while ((pid1=fork())==-1);
if (pid1==0)
{
lockf(fd[1],1,0);
sprintf(outpipe,"child 1 process is sending message!");
write(fd[1],outpipe,50);
sleep(5);
lockf(fd[1],0,0);
exit(0);
}
else
{
while ((pid2=fork())==-1);
if (pid2==0)
{
lockf(fd[1],1,0);
sprintf(outpipe,"child 2 process is sending message!");
write(fd[1],outpipe,50);
sleep(5);
lockf(fd[1],0,0);
exit(0);
}
else
{
wait(0);
read(fd[0],inpipe,50);
printf("%s\n",inpipe);
wait(0);
read(fd[0],inpipe,50);
printf("%s\n",inpipe);
exit(0);
}
}
}