2010-2011学年下学期期中

2010-2011学年下学期期中试卷

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

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

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

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

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

d) 等待 ==> 休眠 (4')

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

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

资源请求矩阵如下：

可用资源向量为：

A	B	C
0	2	0

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

假设有一个科学计算进程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只能在队列为空时执行，队列的大小没有限制。要求：

b) 使用信号量，并修改以上scicomp和taskassign代码，使得程序能够满足以上条件 (8');

c) 说明为什么你的程序是对的 (4')

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

a) 请简述采用TLB和2级页表时，内存访问的步骤 (10')；

b) 请比较反向页表（inverted page table）和散列页表（hashed page table）的优缺点 (10')。