淮海工学院操作系统期末试卷整理

淮 海 工 学 院

 11 - 12 学年 第 1 学期操作系统原理 试卷(B闭卷)

10 - 11 学年 第 1 学期操作系统原理 试卷(A闭卷)

一、单项选择题（本大题含20小题，每小题1分，共计20分）

1、操作系统是对（ C）进行管理的软件。      

A、软件     B、硬件    C、计算机资源     D、应用程序

2、在进程管理中，当（  B ）时，进程从运行状态变为就绪状态。      

A、进程被调度程序选中         B、时间片用完

C、等待某一事件发生           D、等待的事件发生

3、银行家算法在解决死锁问题中是用于（  A   ）的               

A、预防死锁     B、避免死锁       C、检测死锁      D、解除死锁

4、下列步骤中（  D ）不是创建进程所必须的。                        

A、建立一个进程控制块         B、为进程分配内存

C、将其控制块插入就绪队列中   D、为进程分配CPU

5、文件系统中用（　C）来管理文件。 

A、作业控制块     B、外页表     C、目录    D、软硬件结合的办法

6、( D  )算法是设备分配常用的一种算法。

A、短作业优先      B、最佳适应     C、首次适应        D、先来先服务 

7、多道程序环境下,操作系统分配资源以( C  )为基本单位。

A、程序     B、指令     C、进程     D、作业

8、在分时系统中，若当前运行的进程连续获得了两个时间片，原因可能是（ B）

A、该进程的优先级最高            B、就绪队列为空

C、该进程最早进入就绪队列        D、该进程是一个短进程

9、在操作系统中，用户程序申请使用I/O设备时，通常采用( B  )。        

A、物理设备名    B、逻辑设备名    C、虚拟设备名    D、独占设备名

10、设3个目标模块A、B、C，起始地址都是0，长度分别是L、M、N，这3个模块按A、B、C顺序采用静态链接方式链接在一起后，模块C的起始地址变换为（ A ）。                                                  

A、L+M　　　B、L＋M＋N        C、L+M-1         D、M+N

11、操作系统最重要的特征是（ A  ）。

A、并发性   B、共享性   C、虚拟性   D、异步性

12、以时间换空间的技术是（  B）。

A．分时技术       B．虚拟存储技术     C．并发技术        D．缓冲技术

13、某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（C  ）。

A、2       B、3     C、4     D、5

14、虚存指的是（  B ）。

A、提高运算速度的设备   B、进程的地址空间及其内存扩充方法

C、容量扩大了的内存     D、实际不存在的存储器

15、在页面置换算法中，可能引起Belady现象的是（ A ）。

A、FIFO       B、LRU      C、OPT      D、CLOCK

16、在一般大型计算机系统中，主机对外设的控制可通过通道、设备控制器和设备这三个层次来实现，下面的叙述中正确的是（ C）。

A、通道和控制器分别控制设备  B、控制器可控制通道，设备在通道的控制下工作

C、通道控制控制器，设备在控制器控制下工作   D、控制器控制通道和设备工作

17、（ B）是解决进程间同步与互斥的一对低级通信原语。

A、lock和unlock    B、P和V     C、W和S    D、send和receive

18、动态重定位技术依赖于(  B )。 

A、重定位装入程序   B、重定位寄存器   C、地址结构   D、目标程序

19、临界区是指并发进程享临界资源的（ C）

A、内存区 、数据区段 、程序区段 、管理信息

20、在SPOOLING系统中，用户进程实际分配得到的是（ B）。

A、用户所要求的外设             B、内存区，即虚拟设备    

C、设备的一部分存储区           D、设备的一部分空间

1．操作系统是一组（ C ）

A．应用程序      B．实用程序      C．资源管理程序       D．都对

2．利用P、V操作控制临界区的使用。当有N个进程希望进入临界区时，对应信号量的最大取值范围可能是（ C  ）。

A．1～-1       B．-1～1        C．1～1-N         D．-N～N-1

3．下列进程调度算法中，综合考虑了进程等待时间和执行时间的是（D）

A．FCFS        B．SPF          C．RR             D．HRN

4．在操作系统中，用户在使用I/O设备时，通常采用（ B）。

A．设备号    B．逻辑设备名    C．虚拟设备名   D．物理设备名

5．下列死锁预防策略中，破坏了“循环等待”条件的是（ D ）。

A．银行家算法    B．一次性分配    C．剥夺资源法    D．资源有序分配

6．将分区管理发展为分页管理的主要目的是（  C）。

A．提高系统的吞吐量                       B．提高程序的并发度

C．提高主存的利用率                       D．使系统能运行更大的程序

7．若分时系统的时间片一定，那么（  C），则响应时间越短。

A．内存越小       B．内存越大     C．用户数越少    D．用户数越多

8．磁盘高速缓存指的是（ B）。

A．CPU和内存间增设的高速缓存            B．内存中的一块空间

C．磁盘上的一个物理块                   D．以上都有可能

9．以空间换时间的技术是（ A ）。

A．SPOOLING技术    B．分时技术         C．并行技术        D．分页技术

10．（ B）是解决进程间同步与互斥的一对低级通信原语。

A．lock和unlock       B．P和V        C．W和S        D．send和receive

11．在分时系统中，一个运行的进程用完了分配给它的时间片但未结束，其状态变为（ A ）。

A．就绪      B．等待       C．运行       D．由用户自己确定

12．某系统中有3个并发进程，都需要同类资源4个，问该系统不会发生死锁的最少资源数是（ C ）。

A．11          B．9         C．10         D．12

13．在内存中的多个进程，若一段时间内都得到运行。这种性质称为进程的（ B ）。

A.动态性      B．并发性       C．调度性         D．异步性

14．在页面置换算法中，可能引起Belady现象的是（ A ）。

A．FIFO       B．LRU      C．OPT      D.CLOCK

15．下列进程状态的转换中，哪一个是不正确的（D ）。

A．活动就绪→运行                         B．运行→活动就绪

C．活动阻塞→静止阻塞                     D．活动就绪→静止阻塞

16．系统在（D  ）时，发生从用户态到核心态的转换。

A．发出P操作    B．发出V操作      C．执行系统调用  D．执行中断程序

17．在SPOOLING系统中，用户进程实际分配得到的是（ B ）。

A．用户所要求的外设             B．内存区，即虚拟设备    

C．设备的一部分存储区           D．设备的一部分空间

18．某系统使用两级页表，页的大小为212B，虚地址长度为32位，页目录表占8位，二级页表占（  C）位。

A．8         B．10        C．12          D．14

19．在以下文件的物理结构中，不利于文件长度动态增长的是（A）

A．连续结构     B．链接结构      C．索引结构     D．hash结构 

20．采用请求分页存储管理方法，一个已在内存被修改的置换页面，应置换到（D）

A．后备作业区     B．磁盘文件区     C．I/O缓冲区    D．磁盘交换区

二、填空题（本大题含9小题10空，每空2分，共计20分）

1．多道程序设计技术的实现是由于硬件技术中出现了通道和 _中断__ 才产生的。

2．操作系统的两个基本特征是 __并发性 和共享性   ，它们互为存在条件。

3．在一个单CPU系统中，若有N个用户进程（N＞1），且当前CPU为用户态，则处于就绪状态的用户进程数最多为_N-1个。

4．标识进程的唯一数据结构是 PCB  。

5．进程从就绪态到执行态的转换是由于_ 进程调度   引起的

6．进程进行了P操作后，若能继续运行，P操作前信号量的值应该___大于0___。

7. 一个计算机系统配置了3台激光印字机和1台绘图机。系统应该配置__2_个设备驱动程序。

8．在一个请求分页系统中,采用OPT页面置换算法时,假如一个的页面走向为5，4,3,2,1,4,3,5,4,3,2,1,5,当分配给该作业的物理页面数分别为3时,访问过程中所发生的缺页次数为_ 8次___。

9. 分页存储管理方式与分段存储管理方式比较，分段存储____方法对于实现程序共享更自然更有效。

简答题（本大题共4小题，共20分）

1、什么是设备性？实现此功能后，可带来哪些好处？（4分）

答：设备性的含义是：应用程序于具体使用的物理设备。

好处：（1）提高了设备分配时的灵活性。

（2）易于实现I/O重定向。

2、简要叙述基于位示图进行盘块分配和回收的过程。（5分）

答：基于位示图的盘块分配过程为

（1）顺序扫描位示图，从中找出一个或一组值为0的二进制位（0表示空闲）  

（2）将一个或一组二进制位转换成与之相应的盘块号。如第i行，第就j列，则相应的盘块号计算如下：

          B=n(i-1)+j  

 (3)修改位示图,map(i,j)=1

盘块的回收分两步：

（1）将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：

i=(b-1)DIV n +1   

j=(b-1) MOD n +1  

    （2）修改位示图。令map(i,j)=0

3、简述段页式管理的优缺点。（6分）

主要优点：a主存利用率高。

b便于信息共享和存取保护。

c作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。对于主存空间的管理仍然和页式管理一样，将其分成若干个和页面大小相同的存储块。作业的地址结构包含三部分：段号、页号及页内偏移。

缺点：1)增加系统开销成本。

2)存取时间较长。

4、什么是文件的物理结构，主要有哪几类。（5分）

文件的物理结构是指一个文件在文件存贮器上存贮方式。它与文件的存取方法有密切关系。为了适应用户的应用要求，文件的物理结构基本上分为连续、链接和索引三种。

5.引入缓冲的主要原因是什么？（6分）

答：缓和CPU与I/O设备间速度不匹配的矛盾；

减少对CPU 的中断频率，放宽对CPU 中断响应时间的；

提高CPU 与I/O 设备之间的并行性。

6．多级文件目录结构有哪些优点？（4分）

答：实现“按名存取”；提高对目录的检索速度；

实现了文件共享；允许文件重名。

三、基础理论与应用题（本大题含6道小题，每题10分，共计60分）

1、三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用put()将一个正整数送入缓冲区的一个单元中，P2每次用getodd()从缓冲区中取出一个奇数，P3每次用geteven()从缓冲区中取出一个偶数。试用信号量机制实现这三个进程的互斥与同步活动，用伪代码实现。

Semaphore empty=N,mutex=1,s1=s2=0;

p1(){    p(empty);

           p(mutex);

           put(); 

            if(是奇数) then v(s1); else v(s2) ;

     v(mutex); }

p2(){

           p(s1);

           p(mutex);

            getodd();

           v(mutex);

           v(empty); }

p3(){     p(s2);

           p(mutex);

          geteven();

           v(mutex);

           v(empty); }

2、假如5个就绪进程其到达系统和所需CPU运行时间如下表所示（单位：毫秒），如果分别采用FCFS和非抢占式SPF（短进程优先调度）调度算法进行CPU调度和运行，请在表中按要求栏目给出各进程在调度和执行完成时产生的各种时间数据。

进程	到达时刻	运行时间	开始时间		完成时刻		周转时间		带权周转时间
			FCFS	SPF	FCFS	SPF	FCFS	SPF	FCFS	SPF
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2
平均周转时间(FCFS)=
平均带权周转时间(FCFS)=
平均周转时间(SPF)=
平均带权周转时间(SPF)=

答：

进程	到达时刻	运行时间	开始时间		完成时刻		周转时间		带权周转时间
			FCFS	SPF	FCFS	SPF	FCFS	SPF	FCFS	SPF
A	0	3	0	0	3	3	3	3	3/3	3/3
B	2	6	3	3	9	9	7	7	7/6	7/6
C	4	4	9	11	13	15	9	11	9/4	11/4
D	6	5	13	15	18	20	12	14	12/5	14/5
E	8	2	18	9	20	11	12	3	12/2	3/2
平均周转时间(FCFS)=（3+7+9+12+12）/5=8.6
平均带权周转时间(FCFS)= 2.56
平均周转时间(SPF)= （3+7+11+14+3）/5=7.6
平均带权周转时间(SPF)=1.84

2、假如5个就绪进程其到达系统和所需CPU运行时间如下表所示（单位：毫秒），如果分别采用FCFS和抢占式SPF（短进程优先调度）调度算法进行CPU调度和运行，请在表中按要求栏目给出各进程在调度和执行完成时产生的各种时间数据。

进程	到达时刻	运行时间	开始时间		完成时刻		周转时间		带权周转时间
			FCFS	SPF	FCFS	SPF	FCFS	SPF	FCFS	SPF
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2
平均周转时间(FCFS)=
平均带权周转时间(FCFS)=
平均周转时间(SPF)=
平均带权周转时间(SPF)=

进程	到达时刻	运行时间	开始时间		完成时刻		周转时间		带权周转时间
			FCFS	SPF	FCFS	SPF	FCFS	SPF	FCFS	SPF
A	0	3	0	0	3	3	3	3	3/3	3/3
B	2	6	3	3	9	15	7	13	7/6	13/6
C	4	4	9	4	13	8	9	4	9/4	4/4
D	6	5	13	8	18	10	12	4	12/5	4/5
E	8	2	18	15	20	20	12	12	12/2	12/2
平均周转时间(FCFS)=（3+7+9+12+12）/5=8.6
平均带权周转时间(FCFS)= 2.56
平均周转时间(SPF)= （3+13+4+4+12）/5=7.2
平均带权周转时间(SPF)=1.59

3、假设移动头磁盘有200个磁道(从0号到199号)。目前正在处理125号磁道上的请求，而刚刚处理结束的请求是43号，如果下面给出的顺序是按FIFO排成的等待服务队列顺序：86，147，91，167，94，150，192，175，130。 若移臂调度分别用最短寻道时间优先SSTF和电梯算法SCAN，给出各种情况下的磁柱访问序列及磁头臂移动距离。

SSTF移动顺序：125→130→147→150→167→175→192→94→91→86

移动距离=173

SCAN: 125→130→147→150→167→175→192→94→91→86

移动距离=173

4、假设移动头磁盘系统有256个磁道(从0号到255号)。目前正在处理100号磁道上的请求，而此前处理结束的请求是143号磁道。现有以FIFO排成的当前各进程申请访问磁盘磁道号序列为：86，147，91，177，94，150，102，175，130。若分别用最短寻道时间优先和SCAN调度算法（电梯调度算法）进行磁盘访问调度，请列表描述这两种调度算法对申请访问序列的调度过程和寻道距离，并比较平均寻道距离的优劣。

SSTF移动顺序：100→102→94→91→86→130→147→150→175→177

寻道总距离=109   

平均寻道距离=12.1

SCAN移动顺序：100→94→91→86→102→130→147→150→175→177

寻道总距离=105   

平均寻道距离=11.7

综上可见SCAN较SSTF算法平均寻道距离短。

4、有一操作系统采用基本分页存储管理方式，若一进程的程序大小是10KB，页面大小为2KB，依次装入内存的第10、5、1、7、9块，试画出该进程的页表，并将虚地址7145转换成内存地址，分析执行虚地址12412所指指令时会产生什么结果。 

页号	块号
0	10
1	5
2	1
3	7
4	9

虚地址7145

P＝7145 ％ 2048 ＝3

W＝7145 mod 2048＝1001

MR=7*2048+1001=15337

虚地址7145的内存地址是：15337

虚地址12412

P＝12412 ％ 2048 ＝6

产生越界，进行异常中断处理

5、设系统有五个进程和A、B、C三类资源，且资源总数分别有10、5、7。在T0时刻进程资源的分配情况如下表，按照下列各小题目提问分别探讨系统的安全性（要求画出银行家算法资源分配安全检查表，并依此求得安全进程序列）。

     资源

分配

进程	MAX	ALLOCATION	NEED	AVAILABLE
	A   B   C	A   B   C	A   B   C	A   B  C
P0	7   5    3	0    1   0	7   4    3	3   3   2
P1	3   2    2	2    0   0	1   2    2
P2	9   0    2	3    0   2	6   0    0
P3	2   2    2	2    1   1	0    1   1
P4	4   3    3	0    0   2	4    3   1

1）讨论系统在T0时刻的安全性（6分）

2）在T0时刻P4进程发出资源请求向量为Requst4（3，3，0），请用银行家算法讨论其资源分配及系统安全性。（4分）

答：

1）T0时刻的安全性检查如下表，存在安全序列{P1，P3，P4，P2，P0}，故系统是安全的

     资源

分配

进程	Work	Need	Allocation	Work + Allocation	Finish
	A  B  C	A  B  C	A  B  C	A   B  C
P1	3   3   2	1   2  2	2   0  0	5   3   2	True
P3	5   3   2	0   1  1	2   1  1	7   4   3	True
P4	7   4   3	4   3  1	0   0  2	7   4   5	True
P2	7   4   5	6   0  0	3   0  2	10  4   7	True
P0	10  3   7	7   4  3	0   1  0	10  5   7	true

2) 当P4进程发出资源请求向量为Requst4（3，3，0）时，用银行家算法讨论起资源分配及其系统安全性如下：

① Request4(3，3，0)≤Need4(4，3，1)；

② Request4(3，3，0)>Available(2，3，0)，则系统资源现在不足，让P4阻塞等待。

5、假设系统分配给某进程3个内存块，且进程开始运行时，这3个内存块是空的，按下列页号访问：2，3， 2， 1，5，2，4，5，3，2，5，2。缺页时采用局部置换方式，分别画出利用OPT和LRU页面置换算法时的置换图（或表），并计算其缺页率。

采用OPT页面置换算法，其页面置换表如下表所示：

OPT	2	3	2	1	5	2	4	5	3	2	5	2
块1 块2 块3 缺页	2 Y	2 3 Y	2 3	2 3 1  Y	2 3 5 Y	2 3 5	4 3 5 Y	4 3 5	4 3 5	2 3 5 Y	2 3 5	2 3 5

OPT :发生  6次缺页.  f=6/12=50%

采用LRU页面置换算法，其页面置换表如下表所示：

LRU	2	3	2	1	5	2	4	5	3	2	5	2
块1 块2 块3 缺页	" 2 Y	" 3 2 Y	" 2 3	1 2 3  Y	5 1 2 Y	2 5 1	4 2 5 Y	5 4 2	3 5 4 Y	2 3 5 Y	5 2 3	2 5 3

LRU : 发生 次缺页.f=7/12=58.3%

6、某系统有R1、R2、R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见下表，此时系统的可用资源向量为（2，1，2）。

     资源

分配

进程	MAX	ALLOCATION
	R1、R2、R3	R1、R2、R3
P1	3   2    2	1    0   0
P2	6   1    3	4    1   1
P3	3   1    4	2    1   1
P4	4   2    2	0    0   2

试问：1）将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来。

2）若此时进程P1发出资源请求Request(1,0,1)，请用银行家算法讨论其资源分配及系统安全性。