作业三解答过程：

1、（1）何时会发生死锁？

北

（2）请提出一种可预防死锁发生的简单方法

方向②北

方向①

路口 S1 路口 S2

路口 S3 路口 S4

方向③

方向④

设4个路口为4个资源，其信号量分别设为S1，S2，S3和S4，初值均为1，代表资源空闲可用，下面用P，V操作预防死锁问题： 方向①进程： P（S1，S2） <通过S1、S2路口> V（S1，S2）

方向②进程： P（S2，S4） <通过S2、S4路口> V（S2，S4） 方向③进程： P（S3，S4） <通过S3、S4路口> V（S3，S4） 方向④进程： P（S1，S3） <通过S1、S3路口> V（S1，S3） 信号量S1，S2，S3和S4 的变化范围均为[-m ,…,-1,0,1]（m为正整数）。

2、（1）1个出入口，且一次只允许1人通过：

设超市容量信号量为S，初值为100；购物进程为Pi，购物信号量为mutex，初值为1。

购物进程Pi同步描述： P（S） P（mutex）

<进入超市并取1只篮子> V（mutex） <选购商品> P（mutex）

<结账并归还篮子> V（mutex） V（S） 信号量S的变化范围为[-m ,…,-1,0,1 ,…,100]（m为正整数）；信号量mutex的变化范围为[-99 ,…,-1,0,1 ]。

（2）1个入口，n个出口（n≥1且为整数） 设购物进程为Pi,；超市容量信号量为S，初值为100；入口互斥信号量为mutex1，初值为1；出口互斥信号量为mutex2，初值为1。

购物进程Pi同步描述： P（S） P（mutex1）

<进入超市并取1只篮子> V（mutex1） <选购商品> P（mutex2）

<结账并归还篮子> V（mutex2） V（S） 信号量S的变化范围为[-m ,…,-1,0,1 ,…,100]（m为正整数）；信号量mutex1和mutex2的变化范围均为[-99 ,…,-1,0,1 ]。 3、（1）两个进程间的制约关系：乙进程不能先于甲进程执行，而甲进程不受乙进程约束。 （2）设置1个信号量S，S表示甲进程写满的缓冲区的个数，S初值为0，表示缓冲区为空，则甲、乙两进程的同步算法描述为

甲进程： 乙进程： i=0 j=0 i=i+1 j=j+1 <写入第i个缓冲区> P（S） V（S） <读出第j个缓冲区>

（3）信号量S的变化范围为[-1,+∞]中的整数，当S=-1时表示缓冲区从未被写入信息或缓冲区信息被乙进程读空，且乙进程要求进一步读缓冲区中的信息，即乙进程超前甲进程欲读取缓冲区的信息而受阻。

作业四：作业、进程调度

1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？

（1）先来先服务（2）轮转法（3）短作业优先（4）优先级高者优先（5）长作业优先 2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率。下表给出了3种简单的作业调度算法：

调度算法 先来先服务 最短作业优先 最高相应比优先 吞吐量大 公平合理 发挥资源利用率 （1）请指出每种算法主要是体现了上述哪种原则。（在对应的行列上打上记号√）

（2）如果在实际系统中只采用上述3种简单算法的任一种，都只能体现其中一种原则而其它原则得不到反映。为此，给出下列能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：

R(优先数)=(作业等待时间)2+1/(作业要求运行时间)

请问这种算法反映了上述原则中的哪些原则？并简述理由。 3、假设有4道作业，它们的提交时刻及运行时间由下表给出： 作业号 1 2 3 4 提交时刻/小时 10.00 10.20 10.40 10.50 执行时间/小时 2 1 0.5 0.3 计算在单道程序环境下，采用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。

作业四解答过程：

1、适用于作业调度用的算法：（1）（3）（4）（5），适用于进程调度用的算法：（1）（2）（4）。 2、（1）

调度算法 先来先服务 最短作业优先 最高相应比优先 吞吐量大 √ 公平合理 √ 发挥资源利用率 √ （2）该算法体现了先来先服务原则和最短作业优先原则。理由如下： 体现先来先服务原则：假若两作业运行时间相同，但到达时间不同，早到达的作业等待时间长，根据公式计算，它的优先数大，则优先调度。

体现最短作业优先原则：假若两道作业同时到达，但运行时间不等，根据公式计算，运行时间短的作业其优先数高，因而优先调度。 3、（1）先来先服务（FCFS）调度：调度顺序为1→2→3→4。 作业号 1 2 3 4

到达时间 10.00 10.20 10.40 10.50 结束时间 12.00 13.00 13.50 13.80 周转时间 2 2.8 3.1 3.3 带权周转时间 1.00 2.80 6.20 11.00 平均周转时间T=(2+2.8+3.1+3.3)/4=2.8小时

平均带权周转时间W=(1+2.8+6.2+11)/4=5.25小时

（2）最短作业优先（SJF）调度：调度顺序为1→4→3→2。 作业号 1 4 3 2 到达时间 10.00 10.50 10.40 10.20 结束时间 12.00 12.30 12.80 13.80 周转时间 2 1.80 2.40 3.60 带权周转时间 1 6 4.8 3.6 平均周转时间T=(2+1.8+2.4+3.6)/4=2.45小时 平均带权周转时间W=(1+6+4.8+3.6)/4=3.85小时

（3）最高响应比优先（HRN）调度：调度顺序为1→4→3→2。

响应比=(作业执行时间+作业等待时间)/作业执行时间

从下表可见，在作业1完成时刻（12.00），作业2、3、4的响应比最高的为4；在作业4完成时刻（12.30），作业2、3的响应比最高的为3。 作业号 2 3 4 2 3

作业号 1 4 到达时间 10.00 10.50 结束时间 12.00 12.30 周转时间 2 1.80 带权周转时间 1 6 等待时间 1.80 1.60 1.50 2.1 1.9 执行时间 1 0.5 0.3 1 0.5 响应比 2.8 4.2 6 3.1 4.8