距离上次更新已经 1030 天了,文章内容可能已经过时。
这里回顾第7章,本章介绍了进程调度:介绍。
书籍介绍:
学习资料:
参考资料:
参考资料:
第7 章 进程调度:介绍
内容回顾
关键概念
调度策略(sheduling policy)
调度指标
分为性能指标和公平指标
周转时间(性能指标)
响应时间(公平指标)
调度算法
- 先进先出调度(First In First Out或FIFO,First Come First Served或FCFS)
- 可能会产生护航效应(convoy effect):一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后
- 最短任务优先(Shortest Job First或SJF)
- 优化周转时间
- 最短任务优先是非抢占式调度程序:会将每项工作做完,再考虑是否运行新工作。
- 最短完成时间优先(Shortest Time-to-Completion First,STCF)/ 或抢占式最短作业优先(Preemptive Shortest Job First ,PSJF)
- 优化周转时间
- 每当新工作进入系统时,它就会确定剩余工作和新工作中,谁的剩余时间最少,然后调度该工作。
- 轮转(Round-Robin,RR)调度
- 响应时间
- RR在一个时间片(time slice,称为调度量子,scheduling quantum)内运行一个工作,然后切换到运行队列中的下一个任务,而不是运行一个任务直到结束。反复执行,直到所有任务完成。
- 时间片长度必须是时钟中断周期的倍数。
结合I/O
- 保证交互式作业正在执行I/O时,其他CPU密集型作业在运行。
作业
1
FIFO:
验证:
SJF:
因为时长一样,所以和FIFO相同:
验证:
2
FIFO:
验证:
SJF:
没变化,因为完成时长递增:
验证:
3
- 对于Job 0,响应时间为,完成时间为,等待时间为;
- 对于Job 1,响应时间为,完成时间为,等待时间为;
- 对于Job 2,响应时间为,完成时间为,等待时间为;
4
JOB时长单调递增。
5
量子长度大于最大工作长度。
6
假设个工作时分别为,按照升序排列得到:
SJF的平均响应时间为:
随着,平局响应时间
7
假设个工作时分别为,假设量子长度为,当增加时,最终会有
此时退化为FIFO,平均响应时间为