计算机期末考试《操作系统》试题带答案

计算机学院第2学期期末考试《操作系统》试题（闭卷 B卷）

一、填空题（共8题，每空1分，共15分）

1．并发进程中涉及到（访问临界资源 ）的程序段称为临界区，为保证进程（ 互斥 ）使用临界区，应在进程的临界区前设置（ 进入区 ），在临界区后设置（退出区 ）。

2. 在多用户环境下，由多个程序共享一台计算机，机内资源的状态将由多个程序来改变，因此使程序失去了在顺序执行时具有的( 封闭性 )和(可再现性 )特性。

3. 进程通信的类型有( 共享存储器系统 )、( 消息传递系统 )和管道通信三类。

4. 假定一个操作系统的进程调度采用剥夺式进程 到达就绪队列时刻 执行时间

短进程优先调度算法（单处理机系统），系1 0 8

统中各进程到达就绪队列的时刻以及执行2 1 4

时间如右表所示：则各进程的调度次序为3 2 9

（ P1->P2->P4->P1->P3 ），平均周转4 3 5

时间是（ 13 ）。

5、分区管理中采用“首次适应”分配算法时，应将空闲区按（地址递增）次序登记在空闲分区表中。

6、在虚拟段式存储管理中，若逻辑地址的段内地址大于段表中该段的段长，则发生（越界中断）。

7. 设备无关性是指用户程序与（ 物理设备 ）无关。

8. 文件的结构就是文件的组织形式，从用户观点出发所看到的文件组织形式为文件的（逻辑结构 ）,从实现观点出发，文件在外存上的存放组织形式称为文件的（ 物理结构 ）。

二、单项选择题（共10题，每题2分，共20分）

1. 在存储管理中，采用覆盖与交换技术的目的是（ A ）。

A.节省主存空间 B.物理上扩充主存容量 C. 实现外存共享 D. 提高CPU效率

2. 采用段式存储管理的系统中，若地址用32位表示，其中12位表示段号，则允许段的最大长度是（ D ）。A.232 B. 212 C. 28 D. 220

3. 系统“抖动”现象的发生是由（ A ）引起的。

A. 置换算法选择不当 B. 交换的信息量过大 C. 内存容量不足 D.请求页式管理方案

4. 相同名字的文件应允许在一个系统中同时存在，解决这个问题的办法是（ B ）。

A. 通过文件共享 B. 多级目录管理 C. 采用索引文件 D. 文件安全管理

5. 在分时操作系统中,进程调度经常采用( C )算法。

A.先来先服务 B.最高优先权 C.时间片轮转 D.随机

6. 采用资源剥夺法可解除死锁，还可以采用（ B ）方法解除死锁

A.执行并行操作 B.撤消进程 C.拒绝分配新资源 D.修改信号量

7. 对磁盘进行移臂调度其目的是缩短( C )时间。

A.启动 B.数据传送 C.寻找定位 D.搜索延迟

8. V原语对信号量做加1运算后，( C )。

A．当S<0时进程继续执行 B. 当S<0时要唤醒一个就绪进

C. 当S≤0时要唤醒一个等待进程 D．当S≤0时要唤醒一个就绪进程

9. 某进程所要求的一次打印输出结束，该进程被( C )。A.阻塞B．执行 C．唤醒 D．挂起

10. 作业在系统中存在与否的唯一标志是( C ) 。

A.源程序 B.作业说明书 C.作业控制块 D．目的程序

三、简答题（共4题，每题5分，共20分）

1. 在多道操作系统控制下，一个作业反复执行多次，它的运行时间都相同吗？为什么？

一个作业反复执行多次，它每次的运行时间可能并不相同。

由于在多道操作系统控制下，一个作业需要和其他作业创建的进程并发执行，使其在执行过程中呈现异步性，时走时停，其开始、暂停及再次获得调度的时间都是无法预知的，因此其运行时间无法确定。

2. 有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3.回答：

（1）若对资源分配不加限制，可能会发生什么情况？

可能会发生死锁

例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待,这是循环等待。（或进程在等待新源时均不释放已占资源）

（2）为保证进程正确工作，应采用怎样的资源分配策略？为什么？

可有几种答案：

A.采用静态分配

由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象（或不会出现循环等待资源现象）。

或B.采用按序分配 不会出现循环等待资源现象。

或C.采用银行家算法 因为在分配时，保证了系统处于安全状态。

3. 有哪些基本的作业调度算法？在什么情况下调用作业调度程序？

答：基本的作业调度算法有： 先来先服务、短作业优先法、最高响应比优先法、时间片轮转法、优先数法等。

当完成作业从后备状态到运行状态和从运行状态到完成状态的转变时要使用作业调度算法。

4. SPOOLing技术如何使一台打印机虚拟成多台打印机？

将 一 台独享打印机改造为可供多个用户共享的打印机，是应用SPOOLing技术的典型实例。具体做法是:

（1）系统对于用户的打印输出，但并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送人其中; （2分）

（2）然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。（2分）

（3）若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。（1分）

四、计算题（共4题，共35分）

1. （10分）假设某程序的页面访问序列为1、2、3、4、5、2、3、1、2、3、4、5、1、2、3、4且开始执行时主存中没有页面，分配给该程序的物理块数是3，使用下列替换算法，求出现置换的次数及缺页率。（1）FIFO替换算法（2）LRU替换算法。

解：（1）FIFO算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：

1 2 3 4 5 2 3 1 2 3 4 5 1 2 3 4

1 2 3 4 5 2 3 1

1 2 3 4 5 2 3

1 2 3 4 5 2

4 5

1 4

3 1

2 3 4

5 2 3

4 5 2

置换次数：13次， 缺页率=13/16=81.25%

（2）LRU算法是最近最久未使用的页面予以淘汰。算法如图所示：

1 2 3 4 5 2 3 1 2 3 4 5 1 2 3 4

1 2 3 3 3 2 2 2

1 2 2 5 5 5 1

1 4 4 4 3 3

2 5 5 5 3 3

4 4 4 2 2 2

3 3 1 1 1 4

置换次数：14次（1分），缺页率=14/16=87.5%

2. （8分）假定在某移动臂磁盘上，刚刚处理了访问115号柱面的请求，目前正在100号柱面读信息，并且有下述请求序列等待访问磁盘: 190、10、160、80、90、105、30、20、125、25。试用：

（1）电梯调度算法

答：（1）电梯调度算法的处理次序为： 100-90-80-30-25-20-10-105-125-160-190

（2）最短寻找时间优先算法分别列出实际处理上述请求的次序。

最短寻找时间优先算法的处理次序为： 100-105-90-80-125-160-190-30-25-20-10

3.（9分）在页式存储管理系统中，假设进程逻辑地址空间占64页，每页为1024字节，系统物理内存为2M字节。进程的页表及所有逻辑页面都已在内存中。系统有快表（TLB），其平均命中率为85%。一次内存访问需要100ns，对TLB的查找时间忽略不计，则：

(1)进程的页表项共几项？页表项中物理页帧(frame)号占几位？

(2)进程访问一个逻辑页面的平均时间是多少？

(3)如果物理内存再增加一倍，再回答问题（1）。

解：（1） 页表项64项，frame号占11位

（2） 平均时间： 0.85 * 100 + 0.15 * ( 100 + 100) = 85 + 30 = 115ns

（3）页表项数不变，frame号占12位

4.（8分）设系统中资源类集合为{A，B，C}，资源类A中共有8个实例，资源类B中共有6个实例，资源类C中共有5个实例．又设系统中进程集合为{p1,p2,p3,p4,p5,p6}, 某时刻系统状态如下：

Allocation Need Available

A B C A B C A B C

p1: 1 0 0 0 0 0 2 2 1

p2: 3 2 1 3 1 2

p3: 0 1 2 2 0 2

p4: 0 0 0 0 0 0

p5: 2 1 0 0 3 1

p6: 0 0 1 0 0 1

问：(1)该时刻系统是否处于安全状态？

（2）在上述状态下系统接收到进程P6的请求：Request1(0,0,1)，请问系统能否进行资源分配，为什么？

答：（1）系统在该时刻处于安全状态。，安全序列为P6-P3 -P5-P2.

（2）在上述状态下系统接收到进程P6的请求时，不能进行资源分配。如果将P6请求的资源分配给它，则剩余的资源已经不能满足任意一个进程的资源需求，无法找到一个安全序列使全部进程执行完成。-

五、算法设计题（共1题，共10分）

假定有三个进程R、W1、W2共享一个缓冲区Buffer。进程R读入数据放到缓冲区Buffer中；若缓冲区中的数为奇数，则进程W1将其取出显示；若缓冲区中的数为偶数，则进程W2将其取出显示。对它们有如下的限制条件：

（1）缓冲区中每次只能存放一个数；

（2）只有当缓冲区中没有数，或W1或W2将数取走后，进程R才可以将新读入的数放到缓冲区中。

（3）进程W1或W2对每次存入缓冲区中的数只能显示一次，且W1和W2都不能从空缓冲区中取数。

假定开始缓冲区为空，利用记录型信号量及wait、signal操作写出三个并发进程的正确工作程序。

解：P、V操作如下： PW1:begin

var s,s1,s2:semaphore:=1,0,0； repeat

begin wait(s1);

parbegin x:=B;

PR:begin signal(s);

repeat 打印x；

从输入设备读到一个数B; until false;

wait(s); end; （2分）

放入; PW2:begin

if B=奇数 then signal(s1); repeat

else signal(s2); wait(s2);

until false; y:=B;

end; （4分） signal(s);

打印y；

until false;

end; （2分）

parend