操作系统2014年期中考试试题

操作系统 2014年期中考试试题

一、是非题（请判断以下论述是否正确。正确的标T；错误的标F，指出错误所在并修正）（2'*4=8'）

1.页表由各个进程自己管理，进程可在用户态对页表进行更新。

2.单CPU环境下由于任何时刻只有一个进程（线程）能够运行，因此操作系统不

需要实现同步与互斥支持。

3.在微内核结构的操作系统中，CPU调度必然在微内核内。

4.在抢占式（preemptive）操作系统中，进程不会因为申请、使用资源发生死锁。

二、（32'）问答题

1.（5'）请详细描述一个用户态线程调用sleep()系统调用后，操作系统所执行的任务。并分析其中每一个步骤的代价大小。

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

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

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

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

3.（15'）请简述计算机系统启动，直到运行第一个用户应用程序，然后派生出第二个线程的整个过程中的可能的步骤，并分析每一个步骤的代价（大／中／小），说明理由。

三、（43'）计算题

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

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

b) 假设TLB的命中率为50%，请计算进程对内存的有效访问时间（effective access time）（5'）

c) 如果要求进程对内存的有效访问时间不大于500ns，请问TLB的命中率必须提高到多少？（5'）

2.（16'）已知就绪队列中已有4个进程，所需要的CPU时间按到达次序分别为28，5，43，35个毫秒；在第10毫秒到达第五个进程，它所需要的CPU时间为8个毫秒。请写出在先来先服务（First-Come-First-Serve，FCFS）、以5毫秒和20毫秒为单位的轮询（Round-Robin）、最短作业优先（Shortest Job First）这四种不同的CPU 调度下，这些进程的调度序列（可用甘特图（Gantt Chart）表示）（3'x 4），并分别计算四种不同情况下的平均响应时间（1'x 4）。

3.（12'）现有5个进程（P0-P4），3类资源（A:9, B:5, C:5），当前的系统状态如下：

系统剩余的资源为：Available: (2, 3, 0)

请问：

a) 如果系统不允许资源抢占，系统当前是否处于安全状态？如果不处于安全状态，请写出可能发生死锁的进程，并画出它们之间的等待图（wait-for graph）；如果处于安全状态，请写出进程执行的序列。（8'）

b) 请问系统是否一定发生死锁？为什么？（4'）

四、（17'）设计题

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

2.（12'）有A、B两个线程，需要协同工作。A和B的程序逻辑分别如下：

1. A ()

2. {

3. A的自身处理代码;

4. // A和B的同步点，即双方都要执行完自身代码;

5. A的协同代码;

6. }

1. B ()

2. {

3. B的自身处理代码;

4. // A和B的同步点，即双方都要执行完自身代码;

5. B的协同代码;

6. }

a)（8'）请使用信号量，实现A和B的第4行同步点；

b)（4'）请说明为什么你的实现是正确的；你的实现是否会导致死锁。