（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 3 2
10.40 10.20 12.80 13.80 2.40 3.60 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小时
作业五：存储管理
1、假定某页式虚拟系统中，页面大小为100个单元，某作业占有实页面数为M=3，它的访问地址（走向）序列为75，175，66，267，32，102，333，166，22，255，256（数字为虚存的逻辑地址）。（1）请指出这些单元对应的页面访问顺序序列；（2）按先来先服务（FIFO）页面淘汰算法求出缺页率f，并画出图表表示之；（3）按最近最久未使用（LRU）页面置换算法求出缺页率f，并画出图表表示之。 2、有系统其主存容量为1024K（字节），有6个作业同时到达，各作业要求主存量和运行时间如下表所示。假定系统初启时，将主存1024K按作业的编号顺序分给各道作业，并假定是多CPU下，分配到主存的作业都可以立即运行。请问： （1）1秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？ （2）2秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？ （3）在（2）后，此时有一个作业7要求进入主存，它需要主存量为30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况。
作业编号 1 2 3 4 5 6
需主存量（K） 200 120 100 50 80 320 运行时间（s） 2 1 3 1 3 2