2015-2016学年上学期期中

2015-2016学年上学期期中试卷（含答案）

说明

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

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

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

要互斥地进入临界区，必须采用基于硬件的解决办法。

答案：
错。可以用基于软件/算法的方法，例如Peterson算法。
单CPU环境下由于任何时刻只有一个进程（线程）能够运行，因此操作系统不需要实现同步与互斥控制。

答案：
错。单CPU环境下,并发执行的进程之间也需要实现同步与互斥。
对于内核支持的线程，当该线程执行系统调用被阻塞时，不仅该线程被阻塞，而且同一进程内的所有线程都会被阻塞。

答案：
错。只有当前线程被阻塞，其它线程可以继续执行。
多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业(进程)迅速完成。

答案：
对。
线程都保存有各自的栈信息、CPU状态（寄存器、指令计数器等）、堆信息，以及打开文件列表等。

答案：
错。线程保存栈信息、CPU状态；而堆信息，以及打开文件列表等是进程保存的。

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

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

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

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

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

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

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

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

A. CPU利用率增高

B. CPU利用率降低

C. 磁盘I/O增多

D. 磁盘I/O减少

答案：
D
关于线程，以下说法正确的是（）

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

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

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

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

答案：
A, B, C
多CPU共享内存环境下，以下哪种实现临界区的方法无效？（）

A. 使用test_and_set机器指令实现“忙等”（busy waiting）

B. Peterson算法

C. 关中断

D. 使用swap机器指令实现“忙等”

答案：
C
一个正在运行的进程，当所分配的时间片用完后，将其挂在（）。

A．等待队列

B．运行队列

C．就绪队列

D．任意一个队列

答案：
C

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

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

死锁（deadlock）与饥饿（starvation）

答案：
死锁：多个进程循环等待对方，都无法继续执行。
饥饿：某个或某些进程由于无法得到资源长时间无法执行。
死锁必然发生饥饿，但是饥饿不一定发生死锁。
对称多处理系统调度与非对称多处理系统调度

答案：
Symmetric Multiprocessing (SMP) – each processor makes its own scheduling decisions.
Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing.
进程的同步与互斥

答案：
同步：并发进程之间相互合作，完成一项工作，它们之间有一定的时序关系。互相约束，其表现为一个进程等待另一个进程的变量结果.
互斥：并发进程之间相互竞争临界资源的排他性关系
管程与进程

答案：
管程：是一种并发性的构造，它包括用于分配一个共享资源或一组共享资源的数据和过程。为了完成分配资源的功能，进程必须调用特定的管程入口。管程（Monitor）采用资源集中管理的方法，将系统中的资源用某种数据结构抽象地表示出来。由于临界区是访问共享资源的代码段，因而建立一个管程来管理进程提出的访问请求。采用这种方式对共享资源的管理就可以借助数据结构及其上实施操作的若干过程来进行；对共享资源的申请和释放可以通过管程在数据结构上的操作来实现。
进程：进程是计算机中的程序关于某数据集合的一次运行活动。在传统操作系统中，它是资源拥有的基本单元。进程之间同样可以并发执行。进程虽然拥有自己的系统资源，但也因此导致创建或撤销进程开销都十分的大，切换、通信、同步也会比线程之间的实现更加复杂。
微内核和模块化内核

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

四、综合题（40分，每题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)
（甘特图略）

桌上有一个空盘，最多可以容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘中放苹果，妈妈专向盘中放橘子。儿子专门等吃盘中橘子，女儿专门等吃盘中苹果，请用PV操作实现爸爸、妈妈、儿子、女儿之间的同步与互斥操作。

答案：

设置4个信号量：

empty:表示还可以向盘中放几个水果，初值为2；

apple:表示已放入盘中的水果，初值为0；

orange:表示已放入盘中的橘子，初值为0；

mutex: 对盘子互斥访问，初值为1.

提示

原参考答案将apple解释为“已放入盘中的水果”，结合题意和后续代码，此处应指“已放入盘中的苹果”。

Semaphore mutex=1,empty=2,apple = 0,orange=0;

Main()
{
    Conbegin
    father();
    mother();
    son();
    daughter();
    Coend
}

father()
{
    while (true)
    {
        P(empty）
        P(mutex)
        向盘中放水果；
        V(mutex);
        V(apple);
    }
}

mother()
{
    while (true)
    {
        P(empty）
        P(mutex)
        向盘中放水果；
        V(mutex);
        V(orange);
    }
}

son()
{
    while (true)
    {
        P(orange);
        P(mutex);
        从盘中取橘子
        V(mutex);
        V(empty);
        吃橘子；
    }
}

daughter()
{
    while (true)
    {
        P(apple）
        P(mutex)
        从盘中取苹果；
        V(mutex);
        V(empty);
        吃苹果；
    }
}

请详细描述一个用户态线程调用sleep()系统调用后，操作系统所执行的任务。

答案：
（1）系统调用过程：mode-switch, 查表（syscall handling）, 执行系统调用代码
（2）sleep() 将当前进程放入waiting队列（设置alarm）
（3）CPU调度（context switch）
（4）系统调用结束，返回，mode-switch
现有四个进程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

2015-2016学年上学期期中试卷（含答案）​

说明​

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

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

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

四、综合题（40分，每题10分）​

2015-2016学年上学期期中试卷（含答案）

说明

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

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

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

四、综合题（40分，每题10分）