《操作系统》试卷

2005-2006学年第一学期操作系统期末试卷

（计算机科学与技术专业2003级)

班级         学号              姓名               成绩            

I. 填空.(30分，每空1分) 

1. 在系统中，没有程序运行时，CPU做什么？      忙等         (从中选择一个答案： 暂停、忙等、等待中断、休眠  )。

2. 引入多道程序技术带来的主要好处是    提高了CPU利用率         ；但如果多道程序数目太多，则会造成一种称为    抖动     现象的问题。

3. 导致进程状态从 运行→就绪 转换的原因是    超时，进程的时间片到期       。

4. 进程调度算法（FCFS，SPN，SRT， RR, FB）中对各种类型的进程（如CPU密集型或I/O密集型进程）都能平等对待的是RR时间片轮转    和   FB 多级反馈队列     。

5. (用十进制表示)考虑以下段表：

段号	段基址	段长
0	330	124
1	876	211
2	111	99
3	498	302

请给出以下逻辑地址对应的物理地址，如果地址变换产生了缺段，请指明：

a. 0, 99           429    330+99         

b. 2, 78           1    111+78       

c. 1, 265          缺段   211<265           

6. 在一个物理空间为232字节的纯分页系统中，如果虚拟地址空间大小为212页，页的大小为512字节，那么：

    a. 一个虚拟地址有多少位？     21       

    b. 一个页框有多少字节？     512    

    c. 在一个物理地址中用多少位来指明对应的页框？    23   

    d. 页表的长度为多少（即页表中表项数目为多少）？   212 (4096)    

7. 目前常用的文件目录结构是   树型（多级）  目录结构。

8. 适合磁盘的外存分配模式是：   连续、链接、索引   。

9. 进程迁移是指 将一个进程的状态，从一台机器转移到另一台机器上，从而使该进程能在目标机上执行.

10. 分布式系统中的关键机制是进程间通信。中间件提供了标准的编程接口和协议，掩藏了不同网络协议和操作系统之间的复杂细节和差异，其实现基于消息传递和远程过程调用两种机制。

11. 操作系统安全里说的身份鉴别机制的作用是 识别请求存取的用户，并判断它的合法性 。

12. 根据美国国防部的划分，计算机系统的安全从低到高分为哪4等？ D，C，B，A （按从低到高的顺序）。

13. 正误判断题：

    a．在SPOOLing系统中，对用户进程的设备申请，系统将物理字符设备按时间片方式分配给用户进程使用。  ╳   。

b．SPOOLing系统是虚拟存储技术的体现  ╳   。

14. 判断题：系统调用与用户程序之间的调用不同之处是处理机状态的改变  √。

15. 虚拟设备是指通过某种虚拟计数，将一台物理设备变成若干台逻辑设备。逻辑设备实际上并不存在，只是给用户的一种感觉。在操作系统中引入虚拟设备的原因是 为了克服独占设备所具有的速度较慢、资源利用率较低的缺点，以提高设备利用率。

16. 已知某文件采用串联结构，它由10个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，都为1024字节，并依次存放在10, 61, 32, 75, 87, 98, 46, 37, 33, 11号磁盘块上。若要存取文件的第7654逻辑字节处的信息，要访问的磁盘块块号为      37   7654/1024=7    。

17. 在采用分页式存储管理的系统中，某作业对应的页表如下：

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

    已知页大小为4096字节，则逻辑地址 8862 对应的物理地址为   37534  。（十进制表示）

19. 对于硬盘上存放的信息，物理上读写的最小单位是一个   物理块    。（选择以下一个填空：二进位、字节、物理块、逻辑记录）

20.      处理中断        是操作系统必须提供的功能。（选择以下一个填空：GUI； 为进程提供系统调用命令； 处理中断； 编译源程序）

21. 操作系统具备处理同时性活动的能力，其最重要的硬件支持是 中断系统  。

II. 简答( 共32分，每题4分).

1. 假设系统由相同类型的m个资源组成，有n个进程，每个进程至少请求一个资源。证明：当n个进程最多需要的资源数之和小于m+n时，该系统无死锁。

证：假设第i个进程的最大资源需求量为Ri，( 1 <= i <= n )；

    则对于最差的情况而言，每个进程都必须得到其所需的全部资源才能完成运行。在每个进程都得到了部分资源，即对任一第i个进程而言，已经拥有 Ri-1个资源，还差一个资源即可满足其最大要求。此时，如果系统中还余一资源，即如有

∑（Ri-1）+ 1 = m    则系统不会产生死锁

∑Ri – n + 1 = m

∑Ri = m + n – 1

∑Ri < m + n

因此，当n个进程最多需要的资源数之和小于m+n时，该系统无死锁。

2. 使用分段及分页地址转换的一个问题是要使用I/O。假设用户希望将某些数据由输入设备读入内存，为了保证数据传输过程中的有效性，通常将要放入数据处的实际内存地址提供给I/O设备，由于将实际地址传送给I/O，因此，在非常快速的数据传输过程中不再需要进行费时的地址转换。这一方法所带来的安全问题是什么？

答：正在等待I/O完成的进程，可能满足置换算法的要求，其对应I/O的进程页面被换出。从而导致输入的数据不在所需进程空间内，且对于换入进程而言，I/O破坏了新换入进程空间里的数据。

3. 二级目录和多级目录的好处是什么？

答：检索速度快、允许文件重名、便于共享。

4. 为什么打印机的输出文件在打印前通常都假脱机输出到磁盘上？

答：提高CPU和打印机的并行工作程序；加快进程打印输出速度，缩短进程周转时间，提高系统的吞吐量。

5. 死锁的产生有4个必要条件：互斥条件、请求与保持条件(逐步请求条件)、不剥夺条件、环路等待条件。死锁的预防就是破坏这4个必要条件中的一个或几个，来达到防止产生死锁的目的。请简要说明死锁预防的各种策略及其优劣。

答：

(1)    破坏“互斥条件”。由于资源特性所限，一般情况下这个条件是无法摒弃的，但对于某些互斥共享的设备，如打印机，则可以通过Spooling技术来摒弃互斥条件。

(2)    破坏“请求与保持条件”。可以采用资源静态分配法，即对资源采用一次性分配策略，但会导致资源利用率的下降。

(3)    破坏“不剥夺条件”。可以采用剥夺策略，但涉及到对资源现场的恢复问题，需付出高昂代价。因此，一般只适用于处理机和存储器资源，不适宜对其他资源使用该方法。

(4)    破坏“环路等待条件”。可以采用资源顺序分配法，但实际情况是：资源编号增加的顺序与实际使用资源的顺序不一致，从而可能导致提早分配资源而导致资源长期不用的现象，使资源利用率下降。

6. 为何段式管理有段内越界，而页式管理无页内越界问题？

答：页的划分是由操作系统完成的，每个地址由系统自动划分为页号和页内地址两部分，因此无页内越界问题。而段的划分是由编译程序完成的，逻辑地址由段号和段内偏移量组成，因此，存在段内越界问题。

7. 什么是进程？操作系统通过什么来感知进程的存在？

答：进程的概念，一般把它定义为可并发执行的程序在一个数据集合上的运行过程。操作系统需要通过一定的数据结构来描述进程的情况和控制进程的运行，这个数据结构就是进程控制块(PCB，Process Control Block)。PCB是进程存在的惟一标志，操作系统通过检测PCB的存在来感知进程的存在。

8. 简述分页式存储管理方案中地址变换过程，并说明系统为提高地址变换速度采取了什么措施。

答：访问页表得到内存块号，由内存块号和页内地址构成要访问的物理地址，访问物理地址得到所需的指令或数据。

为了存取指令或数据需访问两次内存，为此，引入联想寄存器（快表）来提高地址变换速度。

III. (9分) 有如表1所示的进程：

表 1

进程	就绪时间	处理时间
P1	0	3
P2	2	6
P3	4	4
P4	6	5
P5	8	2

1. 画一个图来说明它们的执行过程，分别按以下算法：

a. FCFS

b. SPN

c. RR ( 时间片长度为1 )

2. 计算各种算法下的平均周转时间。

答：FCFS：

进程	就绪时刻	结束时刻	服务时间	周转时间	带权周转时间
P1	0	3	3	3-0 = 3	3/3 = 1.0
P2	2	9	6	9-2 = 7	7/6 = 1.17
P3	4	13	4	13-4 = 9	9/4 = 2.25
P4	6	18	5	18-6 = 12	12/5 = 2.4
P5	8	20	2	20-8 = 12	12/2 = 6.0
平均				8.6	2.56

SPN：

进程	就绪时刻	结束时刻	服务时间	周转时间	带权周转时间
P1	0	3	3	3-0 = 3	3/3 = 1.0
P2	2	9	6	9-2 = 7	7/6 = 1.17
P3	4	15	4	15-4 = 11	11/4 = 2.75
P4	6	20	5	20-6 = 14	14/5 = 2.80
P5	8	11	2	11-8 = 3	3/2 = 1.5
平均				7.60	1.84

RR：

进  程	就绪时刻	结束时刻	服务时间	周转时间	带权周转时间
P1	0	4	3	4-0 = 4	4/3 = 1.33
P2	2	18	6	18-2 = 16	16/6 = 2.67
P3	4	17	4	17-4 = 13	13/4 =3.25
P4	6	20	5	20-6 = 14	14/5 = 2.80
P5	8	15	2	15-8 = 7	7/2 = 3.50
平均				10.8	2.71

IV. (7分)一个磁盘有200个柱面，编号从0 到 199，假设磁头当前位于柱面53。按FIFO顺序请求的柱面号如下：98，183，37，122，14，124，65，67。为了满足磁盘请求队列中的所有请求，请按以下要求完成图示和计算。

1）分别按照FCFS、SSTF算法，画出示意图并计算磁头移过的柱面数目。

2）假设当前磁头正朝柱面0移动，画出示意图说明SCAN算法，并计算磁头移过的柱面数目。

3）假设磁头单向移动方向为柱面0到柱面199，画出示意图说明CSCAN算法。

解：

FCFS：

(98-53)+(183-98)+(183-37)+(122-37)+(122-14)+(124-14)+(124-65)+(67-65) = 600

SSTF：

(65-53)+(67-65)+(67-37)+(37-14)+(98-14)+(122-98)+(124-122)+(183-124) = 236

SCAN：

(53-37)+(37-14)+(14-0)+(65-0)+(67-65)+(98-67) + (122-98) + (124-122)+(183-124) = 236

CSCAN：

V. (6 分) 程序对页面的引用序列如下：

    1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6

如果为程序分配4个内存块，分别使用以下淘汰算法，计算各自的缺页次数：

a. FIFO算法

b. LRU算法

c. OPT算法

解：

FIFO：14次

页面 引用	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
序列	1	2	3	4	4	4	5	6	2	1	1	3	7	6	6	2	1	1	3	3
		1	2	3	3	3	4	5	6	2	2	1	3	7	7	6	2	2	1	2
			1	2	2	2	3	4	5	6	6	2	1	3	3	7	6	6	2	2
				1	1	1	2	3	4	5	5	6	2	1	1	3	7	7	6	6
缺页	+	+	+	+			+	+	+	+		+	+	+		+	+		+

LRU：10次

页面 引用	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
序列	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
		1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3
			1	2	3	4	2	1	5	6	6	2	2	3	7	6	3	3	2	2
				1	1	3	4	2	1	5	5	6	1	2	2	7	6	6	6	1
缺页	+	+	+	+			+	+				+	+	+			+

OPT：8次

页面 引用	1	2	3	4	2	1	5	6	2	1	2	3	7	6	3	2	1	2	3	6
序列	1	2	3	4	4	4	5	6	6	6	6	6	6	6	6	6	6	6	6	6
		1	2	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3	3
			1	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2
				1	1	1	1	1	1	1	1	1	7	7	7	7	1	1	1	1
缺页	+	+	+	+			+	+					+				+

VI.（6分) 

1）如何理解“现代操作系统是以多道程序设计为基础的操作系统”？你认为是否在所有的操作系统中都有必要引入多道程序设计技术？为什么？

2）在所学过的课程中，你感到哪些课程能促进对操作系统的学习？操作系统能否帮助理解其他课程的内容？

VII. (10分) 假设有三个并发进程P，Q，R。其中P负责从输入设备上读入信息并传送给Q；Q将信息加工后传送给R；R则负责将信息打印输出。进程P、Q共享一个由m个缓冲区组成的缓冲池；进程Q、R共享另一个由n个缓冲区组成的缓冲池（假设缓冲区足够大，进程间每次传输信息的单位均小于等于缓冲区长度）。利用信号量机制写出满足上述条件的并发程序。

【分析】

本例主要考查操作系统中信号量的应用。3个进程P、Q和R之间的关系如图3.13所示：

进程P和Q之间存在着同步关系，进程Q和R之间也存在着同步关系；其次，进程P和Q需要访问公有的缓冲池资源，因此P和Q对缓冲池的使用应该互斥进行；

Q和R需要访问公有的缓冲池资源，因此Q和R对缓冲池的使用也应该互斥进行；

设有两个信号量mutex1，mutex2分别用来实施对缓冲区的互斥访问，则其初值都为1；

设置私有信号量Sip、Siq用于进程P和Q之间的同步；

设置私有信号量Soq、Sor用于进程Q和R之间的同步。

【解答】

满足上述条件的并发程序可如下描述：

mutex1, mutex2, Sip, Siq, Soq, Sor: Semapahore = 1,1,m,0,n,0;

Process P

Begin

Loop:

    <读入信息>;

    P(Sip);

    P(mutex1);

    <数据放入缓冲区>;

    V(Siq);

    V(mutext1);

    Goto loop;

End;

Process Q

Begin

Loop:

    P(Siq);

    P(mutex1);

    <从缓冲区中取出数据>;

    V(mutex1);

    V(Sip);

    <数据处理>;

    P(Soq);

    P(mutex2);

<处理后的数据放入缓冲区>;

    V(Sor);

    V(mutex2);

Goto Loop;

End;

Process R

Begin

Loop:

    P(Sor);

    P(mutex2);

    <把数据送入打印机完成打印>.

    V(mutex2);

    V(Soq);

Goto Loop;

End;