2012-2013学年下学期期中

2012-2013学年下学期期中试卷（含答案）

说明

原卷标题：操作系统 2013年期中考试试题

一、多项选择题（5‘x5=25'，每题有一个或多个答案，答错不给分，少答按比例给分）

当系统中的进程增多时，以下哪些（个）情况不可能出现（不考虑死锁）：

A. CPU利用率增高

B. CPU利用率降低

C. 磁盘I/O增多

D. 磁盘I/O减少

答案：
D
以下那些（个）操作会使得一个进程从运行（running）状态转换为就绪（ready）状态：

A. 在可占先（preemptive）系统中，高优先级进程被创建

B. 分时系统中，时间片到

C. 当前运行进程发生缺页中断

D. 当前运行进程调用yield()，主动放弃使用CPU

答案：
A, B, D
对于死锁，以下哪些（个）描述是正确的：

A. 死锁避免（deadlock avoidance）中，不安全的状态必然发生死锁

B. 死锁避免（deadlock avoidance）中，发生死锁必然处于不安全状态

C. 资源分配图中有环（以资源类型和进程为节点），必然发生死锁

D. 如果要求每个进程必须一次申请所有需要的资源，如果不能满足其要求，则不分配任何资源，那么死锁不可能发生

答案：
B, D
以下描述正确的是：

A. 中断处理程序（interrupt handler）是进程的一部分，在进程的地址空间运行

B. 中断处理程序（interrupt handler）必须运行在内核态

C. 微内核体系结构下，进程间通讯（inter-processing communication）必须在微内核内

D. 分时（time sharing）的目的是提高CPU和I/O的并行度

答案：
B, C
关于线程，以下说法正确的是：

A. 用户态线程（无核心态线程或LWP）阻塞，可能会阻塞线程

B. 多处理器环境下，线程间同步不能使用关中断实现

C. 线程控制块中包含CPU寄存器状态

D. 在支持核心态线程的系统中，CPU调度的单位仍然是进程

答案：
A, B, C

二、（21'）

假设线程有运行（running）、就绪（ready）、等待（waiting）四种状态。请分别说明什么时候会发生以下状态转换：

a) 运行 ==> 等待 (4')

b) 就绪 ==> 运行 (4')

c) 等待 ==> 就绪 (4')

d) 请证明SJF调度策略在非抢占（non-preemptive）情况下是最优的 (9')。

三、（8'）

现有四个进程P0, P1, P2, P3，三类资源A, B, C，各有7、5、5个。资源分配矩阵如下：

	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	3
P3	2	2	2

资源请求矩阵如下：

	A	C
P0	0	0
P1	2	2
P2	0	0
P3	1	0

可用资源向量为：

A	B	C
0	2	0

请问：目前是否存在死锁？如果不存在死锁，请给出一个能够让所有进程执行完的序列；如果存在死锁请画出进程的等待图 (8')

四、（12'）

请说明：

进程创建时（如在类UNIX操作系统中，连续执行fork()和exec()系统调用），操作系统所需要进行那些工作，它们的代价如何（大，中，小）。（8'）

答案：
a. 构造PCB，代价小
b. 设置地址空间映射，代价中
c. 复制父进程地址空间内容，代价大
d. 复制I/O状态，代价中
为什么线程创建比进程快，它主要节省了以上哪个步骤的代价？（4'）

答案：
同一进程的不同线程共享资源，因此以上b, c, d三项代价几乎都可节省

五、（10'）

假设有三个进程A，B和C，A和B只使用CPU，各需要200毫秒，进程C使用10毫秒CPU然后进行40毫秒I/O，然后再使用10毫秒CPU接着40毫秒I/O，依此重复，总共也是200毫秒。假设三个进程的到达次序是ABC。

请计算使用FIFO调度，三个进程的平均等待时间和平均完成时间（4'）

答案：
A，B，C
平均等待时间：(0+200+400)/3=200
平均完成时间：(200+400+600)/3=400
请列出使用100毫秒为时间片长度，使用轮询（round-robin）调度时，三个进程的执行次序以及每次执行的时间（6'）

答案：
A100, B100, C10, A100(f)C40, B100(f), C10, C40, C10, C40, C10, C40(f)

六、（24'）

有家理发店，店里有一个理发师、一把理发椅和n把等候理发的顾客椅子。

（1）. 如果没有顾客则理发师便在理发椅上看报纸；

（2）. 当有一个顾客到达时，首先查看理发师在干什么，如果在看报纸则告诉理发师理发，然后坐到理发椅上开始理发；如果理发师正在理发，则查看是否有空的椅子可坐：如果有，他就坐下等待；如果没有，则离开；

（3）. 理发师为一位顾客理完发后，查看是否有人等待，如有则唤醒一位为其理发，如没有则在理发椅上看报纸；

（4）. 顾客不分优先级

请使用信号量实现多线程情况下的Barber()和Customer()两个函数（请自行定义信号量，并进行初始化）（12’），并详细说明实现的正确性（逐条说明是否能够满足以上四条规则，如何保证竞争条件的互斥，是否会发生死锁，是否会发生饥饿，是否公平）（12‘）。