算法题二.xls

一. 简答题（共3题，100分）

1. (简答题, 33.3分)有一个盘子，盘中只能放一个水果，父亲随机向盘中放入一个苹果或橘子，儿子喜欢吃苹果，女儿喜欢吃橘子，他俩只会拿自己喜欢吃的水果。请定义适当的记录型信号量，并说明其含义和初值，用wait和signal操作来实现父亲、儿子、女儿三个进程的并发。

我的答案：

semaphore a,o,p;//分别代表苹果、橘子、盘子资源

/*
信号量p表示是否允许向盘子放入水果，初值为1表示允许放入，且只允许放入一个。
信号量a表示盘子中是否有苹果，初值为0表示盘子为空，不许取，a= 1表示可以取。
信号量o表示盘子中是否有橘子，初值为0表示盘子为空，不许取，o = 1表示可以取。
/
a=o=0,p=1; 定义信号量，赋初值，并说明含义

Dad( )//父亲进程
{
while(1)
{
wait(p);//盘子资源-1
Place a ramdom fruit in the plate;
if(The fruit is apple)
signal(a);//苹果+1
else
signal(o);//橘子+1

}

}

Son( )//儿子
{
while(1){
wait(a);//苹果-1
Get an apple from the plate;
signal(p);//盘子资源+1
}
}

Daughter( )//女儿
{
while(1){
wait(o);//橘子-1
Get an orange from the plate;
signal(p);//盘子资源+1
}
}

void main( )
{
cobegin
Dad( ); Son( ); Daughter( );
coend
}

正确答案：
semaphore a,o,p;//分别代表苹果、橘子、盘子资源
a=o=0,p=1; 定义信号量，赋初值，并说明含义
Dad( )
{ while(1)
{
wait(p);
Place a ramdom fruit in the plate;
if(The fruit is apple)
signal(a);
else
signal(o);
}
}
Son( )
{while(1){
wait(a);
Get an apple from the plate;
signal(p);
}
}
Daughter( )
{ while(1){
wait(o);
Get an orange from the plate;有同学给儿子女儿取水果加上了互斥
signal(p);
}
}
void main( )
{ cobegin
Dad( ); Son( ); Daughter( );
coend
}

2. (简答题, 33.3分)在单道批处理系统中，有下列三个作业用先来先服务调度算法和最短作业优先调度算法进行调度，请完成下表中未完成的内容。（单位：嘀嗒，以十进制进行计算，计算结果不能除尽的保留两位小数）先来先服务算法：短作业优先调度算法：

|

|

|

| | 2 | 10.20 | 0.60 |

|

|

|

| | 3 | 10.50 | 0.10 |

|

|

|

| | 4 | 11.30 | 0.30 |

|

|

|

| | 调度顺序：
平均周转时间 t=
平均带权周转时间 w= | | | | | | |

|

|

|

| | 2 | 10.20 | 0.60 |

|

|

|

| | 3 | 10.50 | 0.10 |

|

|

|

| | 4 | 11.30 | 0.30 |

|

|

|

| | 调度顺序：
平均周转时间 t=
平均带权周转时间 w= | | | | | | |

我的答案：

正确答案：
先来先服务算法：

短作业优先调度算法：

3. (简答题, 33.4分)系统中有五个进程P1、P2、P3、P4、P5，有三种类型的资源：A、B、和C。在T0时刻系统状态如下表所示。若采用银行家算法实施死锁避免策略，回答下列问题： （1）T0时刻是否为安全状态？为什么？（2）若这时P3请求资源（3，0，0），是否能实施资源分配？为什么？

|

|

| | P3 | 0 | 0 | 3 | 7 | 0 | 5 |

|

|

| | P4 | 1 | 1 | 5 | 4 | 3 | 5 |

|

|

| | P5 | 1 | 1 | 0 | 6 | 1 | 3 |

|

|

|

我的答案：

正确答案：
解：（1）安全，可以找到一个安全序列P4，P1，P5，P2，P3

（2）
Request（3 0 0）所以预分配，系统状态为

| | P3 | 303 | 705 | 302 |

| | P4 | 115 | 435 | 320 |

| | P5 | 110 | 613 | 503 |

|

此时找不到安全序列，故不能满足P3要求。