2008-2009学年下学期期中

2008-2009学年下学期期中试卷（含答案）

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

以下对于虚存调页（page replacement）策略，错误的是：

A. LRU不会发生Belady异常

B. 最优策略不会发生Belady异常

C. Belady异常就是随着页框（frame）个数增多，缺页率（page fault rate）必然增加

D. 调页必须在内核态（kernel mode）下进行

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

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

答案：
A, C, 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

二、（10'）

请说明：

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

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

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

三、（10'）

现有四个进程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

请问：目前是否存在死锁？如果不存在死锁，请给出一个能够让所有进程执行完的序列。（4'）

答案：
不存在死锁
进程 A B C
P0 0 3 0
P2 3 3 3
P1 5 3 3
P3 7 5 5
假设此时又来一个进程P4，申请资源（2, 2, 0），请问如果把2个资源B的实例分配给P4，假设除已经获得和正在请求的资源外，所有进程不再请求其它资源，是否处于安全状态（为什么）？（6'）

答案：
安全
此时可用资源向量为：0 0 0
进程 A B C
P2 3 0 3
P1 5 0 3
P4 5 2 3
P0 5 3 3
P3 7 5 5
仍然都能执行完

进程	A	B	C
P0	0	3	0
P2	3	3	3
P1	5	3	3
P3	7	5	5

进程	A	B	C
P2	3	0	3
P1	5	0	3
P4	5	2	3
P0	5	3	3
P3	7	5	5

四、（15'）

使用段页式内存管理，段表和页表都存放在主存中，所有要访问的页面都在主存中。页表项可以缓存在快表（或称旁路转换缓存，TLB）中。一次内存访问的代价为 $200\ \text{ns}$ ，一次TLB访问代价为 $10\ \text{ns}$ 。

请写出以上段页式内存访问的处理流程（也可以用图示表示）。（5'）

答案：
a. 访问段表，检查是否违法，获取页表地址
b. 访问快表，如果miss goto c，否则goto d
c. 访问内存页表
d. 访问内存
假设TLB的命中率为50%，请计算进程对内存的有效访问时间（effective access time）。（5'）

答案：
$200 + 50\% \times 10 + (1-50\%) \times 210 + 200$
$= 510\text{ns}$
如果要求进程对内存的有效访问时间不大于500ns，请问TLB的命中率必须提高到多少？（5'）

答案：
$200 + x \times 10 + (1-x) \times 210 + 200$
$=610-200x\le 500$
$x\ge 110/200=55\%$

五、（20'）

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

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

答案：
A，B，C
平均等待时间：(0+1000+2000)/3=1000
平均完成时间：(1000+2000+3000)/3=2000
请计算使用100毫秒为时间片长度，使用轮询（round-robin）调度时，三个进程的平均等待时间和平均完成时间。（4'）

答案：
A100, B100, C10, A100C90, B100, C10, A100C90, … B100, C10, C90
平均等待时间：(990+1090+1190)/3=1090
A: 110*9=990
B: 100+110*9=1090
C: 200+110*9=1190
平均完成时间：(1990+2090+2190)/3=1790
A: 210*9+100=1990
B: 210*9+200=2090
C: 210*10+90=2190
请计算使用10毫秒为时间片长度，使用轮询（round-robin）调度时，三个进程的平均等待时间和平均完成时间。（4'）

答案：
A10, B10, C10, A10C10, B10C10, A10C10, B10C10...
平均等待时间：(1080+1090+1190)/3=1120
A: 2099-1090=1980-900=1080
B: 10+2099-1090=1990-900=1090
C: 1190
平均完成时间：1790
A: 1990
B: 2090
C: 2190
请计算使用最短剩余时间优先（shortest remaining time first）调度时，三个进程的平均等待时间和平均完成时间。（4'）

答案：
C10, A90C90, C10, A90C90, …, A, …, B, …
平均等待时间：(100+1100+0)/3=400
A: 10*10=100
B: 10*10+1000=1100
C: 0
平均完成时间：(1100+2100+1000)/3=1400
A: 1000+100=1100
B: 1100+1000=2100
C: 1000
假设每次上下文切换需要1毫秒，请从CPU利用率、I/O利用率、进程响应时间三个角度分析以上四种调度策略哪种最适合A、B、C三个进程。（4'）

答案：
CPU利用率：SRTF最高，其次是RR的两种
I/O利用率：SRTF最高，其次是RR的两种
进程响应时间：RR最高，其次是SRTF

六、（15'）

假设有一个科学计算进程scicomp，它每次从任务队列中获得一个计算任务，然后进行计算：

void scicomp ()
{
    while (true)
    {
        get_task ();
        comp ();
    }
}

任务队列中的任务数存放在全局变量m中：

int m;

当任务队列为空时，它唤醒另一个进程taskassign，分配一些计算任务，放在队列中：

void taskassign ()
{
    while (true)
    {
        m = put_task ();
    }
}

其中，put_task ()返回的是放入队列的任务个数。

假设scicomp在队列为空时不能执行get_task()，而taskassign只能在队列为空时执行，队列的大小没有限制。要求：

使用信号量，并修改以上scicomp和taskassign代码，使得程序能够满足以上条件（10'）;
说明为什么你的程序是对的（5'）

答案：

信号量：

semaphore free=0;
semaphore busy=0;
semaphore mutex=1;
int servings=0;

int m;

程序：

void scicomp ()
{
    while (true)
    {
        mutex.wait();
        if(servings==0)
        {
            free.signal();
            busy.wait();
            servings=m;
        }
        servings -= 1;
        get_task ();
        mutex.signal();
        comp ();
    }
}

void taskassign ()
{
    while (true)
    {
        free.wait();
        m = put_task ();
        busy.signal();
    }
}

说明：

对队列、servings的访问不会冲突
逻辑正确
不会死锁或饥饿

附加题（实验班做）

请使用二元信号量（binary semaphore，即值只能为0或1的信号量）实现计数信号量（counting semaphore，取值可为任意整数）。