关于调度算法
【例1】下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）
作业号1
提交时间00
运行时间80
2
04
40
3
10
10
分析
解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。我们用
一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。
采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。然后按照“排队买票”的办法，依次选择作业。其作业执行时间图如下：
采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。其作业执行时间图如下：
由于作业1，2，3是依次到来的，所以当开始时系统中只有作业1，于是作业1先被选中。在80时刻，作业1运行完成，这时系统中有两道作业在等待调度，作业2和作业3，按照短作业优先调度算法，作业3只要运行1个时间单位，而作业2要运行4个时间单位，于是作业3被优先选中，所以作业3先运行。待作业3运行完毕，最后运行作业2。作业调度的次序是1，3，2。
f另外，要记住以下公式：
作业i的周转时间Ti＝作业完成时间－作业提交时间
系统中个作业的平均周转时间
，其中Ti为作业i的周转时间。
解：采用先来先服务调度策略，则调度次序为l、2、3。
作业号123
提交时间000410
运行时间804010
开始时间0080120
完成时间80120130
周转时间80116120
平均周转时间T＝（8＋116＋12）3＝1053
采用短作业优先调度策略，则调度次序为l、3、2。
作业号132
提交时间001004
运行时间801040
开始时间008090
完成时间8090130
周转时间8080126
平均周转时间T＝（8＋8＋126）3＝953
思考题1
请同学们判断这句话：作业一旦被作业调度程序选中，即占有了CPU。（）
提示：需要清楚作业调度和进程调度的区别。
【例2】考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6
当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少
答：缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。
f当内存块数量为3时：
发生缺页中断的次数为16。
在FIFO算法中，先进入内存的页面被先换出。当页6要调入时，内存的状态为4、1、5，考查页6之前调入的页面，分别为5r