2014-2015学年下学期期中

2014-2015学年下学期期中试卷（含答案）

说明

原卷标题：华东师范大学软件学院期中考试卷（2014—2015学年第二学期）

一、判断题（30分，每小题3分）

判断下列每句话是否正确，如错误请说明理由。

银行家算法只能保证系统处在安全状态，但不能保证死锁不发生。

答案：
错。银行家算法只能检测是否处于安全状态，并不能保证系统处于安全状态；此外，安全状态一定无死锁。
提示
原参考答案中“只能检测是否处于安全状态，并不能保证系统处于安全状态”的表述疑似不准确。银行家算法会在分配前进行安全性检查，并拒绝会使系统进入不安全状态的资源分配。
要实现临界区，必须采用基于硬件的解决办法。

答案：
错。可以用基于软件/算法的方法，例如Peterson算法、信号量、管程等。
不安全状态未必会导致死锁的发生；始终处于安全状态也不能保证死锁一定不会发生。

答案：
错。安全一定无死锁。
单CPU环境下由于任何时刻只有一个进程（线程）能够运行，因此操作系统不需要实现同步与互斥支持。

答案：
错。单CPU环境下可能不需要互斥，因为不会同时有两个进程要求进入临界区；但是当多个进程需要顺序执行时，需要同步机制保证多个进程顺序执行。
提示
原参考答案关于互斥的解释疑似有误。单CPU环境仍可能因抢占或中断发生交错访问，因此访问共享临界资源时仍需要互斥机制。
在抢占式（preemptive）操作系统中，进程不会因为申请、使用资源发生死锁。

答案：
对。抢占式操作系统违反了死锁发生的充分条件之一。
提示
原参考答案将本题判为“对”，疑似混淆了CPU抢占与资源抢占。抢占式调度允许操作系统抢占CPU，但不代表进程持有的资源可以被抢占，因此仍可能发生资源死锁。
将“二值”或者“布尔”信号量的初值设为1作为互斥信号量，采用P、V原语操作可解决互斥问题。

答案：
对。信号量的P原语相当于获得排他性的资源访问锁，而V原语则释放这个锁。
由于资源数少于进程对资源的需求数，因而产生资源的竞争，所以这种资源的竞争必然会引起死锁。

答案：
错。资源竞争是引起死锁的根本原因，但是并非必然引起死锁，而是在操作不当的情况可能引起死锁。
一个用户进程在执行过程中，遇到硬件中断，中断处理程序运行在核心态、用户上下文中。

答案：
错。中断处理程序运行在系统上下文中。
死锁是指因相互竞争资源使得系统中有多个阻塞进程的情况。

答案：
错。根据银行家算法，在当前时刻，无论有多少进程处于阻塞状态，只要找到一个安全序列说明整个系统处于安全状态，系统就不会出现死锁。
进程所请求的一次打印输出结束后，将使进程状态从运行态变为就绪态。

答案：
错。等待态变为就绪态。

二、多项选择题（15分，每小题3分）

每题有一个或多个答案，答错、少选、多选均不给分。

以下哪种情况仍然可能会发生死锁？（）

A. 资源都是可共享的；

B. 每一种资源的数量都超过单个进程所需这类资源的最大值；

C. 空闲资源能够满足任意一个进程还需要的资源需求；

D. 每个进程必须一次申请、获得所需的所有资源

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

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．等待队列

B．运行队列

C．就绪队列

D．任意一个队列

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

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

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

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

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

答案：
C

三、辨析题（30分，每小题6分）

分别解释以下每组的两个名词，并列举他们的区别。

死锁（deadlock）与饥饿（starvation）

答案：
死锁：多个进程循环等待对方，都无法继续执行
饥饿：某个或某些进程由于无法得到资源长时间无法执行
死锁必然发生饥饿，但是饥饿不一定发生死锁
同步和互斥

答案：
同步：并发进程之间相互合作，完成一项工作，它们之间有一定的时序关系。互相约束，其表现为一个进程等待另一个进程的变量结果.
互斥：并发进程之间相互竞争临界资源的排他性关系
区别：基于信号量的实现中，同步中的P，V原语在不同的临界区中出现，而在互斥中它们被临界区所分割；此外，它们的初值不同，同步中信号量的初值为0，而互斥中初值为1。
线程和进程

答案：
答题要点：从定义、调度、并发性、系统开销和拥有资源角度说明即可。
微内核和模块化内核

答案：
微内核：操作系统内核只包含最基本的功能（进程调度和进程间通讯）
模块化内核：操作系统内核的一些功能可以作为模块挂载
区别：微内核中内核和其它操作系统的功能模块（如虚存管理）在不同的地址空间运行，模块化内核中它们在一个地址空间。
管程与进程

答案：
管程：是一种并发性的构造，它包括用于分配一个共享资源或一组共享资源的数据和过程。为了完成分配资源的功能，进程必须调用特定的管程入口。管程（Monitor）采用资源集中管理的方法，将系统中的资源用某种数据结构抽象地表示出来。由于临界区是访问共享资源的代码段，因而建立一个管程来管理进程提出的访问请求。采用这种方式对共享资源的管理就可以借助数据结构及其上实施操作的若干过程来进行；对共享资源的申请和释放可以通过管程在数据结构上的操作来实现。
进程：略
区别：管程是进程间通信的一种实现方式，与进程有质的不同。

四、综合题（25分）

（5分）

已知生产者、消费者问题的代码如下：

生产者：

Producer () {
    while (true) {
        /* produce an item and
           put in nextProduced */
        while (count == BUF_SIZE)
            ; // do nothing
        buffer [in] = nextProduced;
        in = (in + 1) % BUF_SIZE;
        count++;
    }
}

消费者：

Consumer () {
    while (true) {
        while (count == 0)
            ; // do nothing
        nextConsumed = buffer[out];
        out = (out + 1) % BUF_SIZE;
        count--;
        /* consume the item in
           nextConsumed */
    }
}

请使用信号量（semaphore），修改现有代码，实现生产者和消费者可能会引起资源竞争的代码的互斥，并分析该实现是否正确、是否会发生死锁。

答案：

答：

Semaphore full = 0;
Semaphore empty = BUF_SIZE;
Semaphore mutex = 1; // 初始化1分

生产者：
Producer () {
    while (true) {
        /* produce an item and
           put in nextProduced */
        Wait (empty);
        Wait (mutex);
        buffer [in] = nextProduced;
        in = (in + 1) % BUF_SIZE;
        count++;
        Signal (mutex);
        Signal (full);
    }
}

消费者：
Consumer () {
    while (true) {
        Wait (full);
        Wait (mutex);
        nextConsumed = buffer[out];
        out = (out + 1) % BUF_SIZE;
        count--;
        Signal (mutex);
        Signal (empty);
        /* consume the item in
           nextConsumed */
    }
}

（10分）

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

a) 请计算采用FIFO调度，计算三个进程的平均等待时间和平均完成时间，画出甘特图（4分）

答案：
答：（甘特图略）
A，B，C
平均等待时间： $(0+200+400)/3=200$
平均完成时间： $(200+400+600)/3=400$

b) 请列出使用100毫秒为时间片长度，使用轮询（round-robin）调度时，画出甘特图求取三个进程的执行次序，并计算每次执行的时间（6分）

答案：
答：A100, B100, C10, A100(f)C40, B100(f), C10, C40, C10, C40, C10, C40(f)
（甘特图略）
（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 B C
P0 0 0 0
P1 2 0 2
P2 0 0 0
P3 1 0 0

可用资源向量为：

A B C
0 2 0

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

答案：
答：不存在死锁
进程 A B C
P0 0 3 0
P2 3 3 3
P1 5 3 3
P3 7 5 5

b) 假设此时又来一个进程P4，申请资源（2, 2, 0），请问如果把2个资源B的实例分配给P4，假设除已经获得和正在请求的资源外，所有进程不再请求其它资源，是否处于安全状态（为什么）？（5分）

答案：
答：安全
此时可用资源向量为：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

2014-2015学年下学期期中试卷（含答案）​

说明​

一、判断题（30分，每小题3分）​

二、多项选择题（15分，每小题3分）​

三、辨析题（30分，每小题6分）​

四、综合题（25分）​

2014-2015学年下学期期中试卷（含答案）

说明

一、判断题（30分，每小题3分）

二、多项选择题（15分，每小题3分）

三、辨析题（30分，每小题6分）

四、综合题（25分）