本文主要是介绍操作系统（Operating System）知识点复习——第九章 单处理器调度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
0.前言
1.调度的类型
2.调度算法Scheduling Algorithms
2.1 短程调度准则
②User-oriented(面向用户) && other
④System-oriented(面向系统) && other
2.2 The Use of Priorities
2.3 调度算法
①First-Come-First-Served(FCFS)先来先服务
②Round-Robin(RR轮转)
③Shortest Process Next(SPN)最短进程优先
④Shortest Remaining Time(SRT)最短剩余时间
⑤Highest Response Ratio Next(HRRN)最高响应比优先
⑥Feedback多级反馈列表
2.4 公平共享调度
0.前言
本系列文章旨在记录操作系统的知识点，可用于期末复习，笔者理解尚浅，文中不正之处静待批正。加粗高亮部分为重点。
1.调度的类型
目的：处理器分配
- Response time (响应时间)--弹窗速度
- Throughput (吞吐率)--单位时间完成工作量
- Processor efficiency (处理器效率)
调度的时机：
- Nonpreemptive非抢占式--主动放弃CPU
- 线程终止(正常终止，异常终止)
- 线程阻塞
- Preemptive抢占式
- 线程时间片用完了
- 中断服务完成
- 新线程到达
调度分类：
- 长程调度(Long-term scheduling)：决定哪些程序可以进入系统进行处理(控制并发度)，发生时机在进程终止或CPU空闲率超过某个值时会增加新进程
- 中程调度(Medium-term scheduling)：决定增加在内存中的进程数(管理并发度，降低抖动)
- 短程调度(Short-term scheduling)(dispatcher)：决定哪一个进程执行(执行最频繁)
- I/O调度(I/O scheduling)
调度与进程状态转换：
调度的层次：
2.调度算法Scheduling Algorithms
2.1 短程调度准则
①User-oriented(面向用户) && Performance-related(性能相关)
用户能感知到的系统行为
- Turnaround time周转时间：从作业提交给系统开始到作业完成为止
- Response Time响应时间：从提交到首次相应所用的时间
- Deadlines终止时间
②User-oriented(面向用户) && other
predictability可预测性
③System-oriented(面向系统) && Performance-related(性能相关)
- Processor utilization处理器的使用效率
- Throughput吞吐量：单位时间完成进程数
④System-oriented(面向系统) && other
- Fairness公平性：无进程饥饿
- Enforcing priorities强制优先级：倾向于高优先级进程
- Balancing resources(also for medium-term and long-term )： 保持资源繁忙
2.2 The Use of Priorities
往往选择高优先级进程，用多个就绪队列表示进程的等级，低级进程可能饥饿
2.3 调度算法
相关术语：
- Response time响应时间
- 服务时间Ts：进程单独执行需要的时间
- Throughput吞吐量
- Turnaround time(周转时间或驻留时间)Tr：Tr=完成时间-到达时间
- Normalized turnaround time(归一化周转时间)=Tr/Ts
- Selection function选择函数：确定在就绪进程中选择哪一个进程在下一次执行
- Decision mode决策模式：选择函数被执行瞬间的处理方式(抢占式与非抢占式)
①First-Come-First-Served(FCFS)先来先服务
原理：选择最先到达就绪队列中的进程
调度时机：进程结束时切换
决策模式：非抢占式
- 优点：公平，简单，不会产生饥饿，适合处理器密集型进程CPU-bound process(I/O要等CPU)
- 缺点：不宜处理短进程
②Round-Robin(RR轮转)
原理：按到达就绪队列的顺序，轮流执行一个时间片(选择下一个进程基于FCFS)，若未执行完，则剥夺，重新加入
调度时机：时间片用完了或进程结束
决策模式：抢占式
- 优点：公平，无饥饿
- 缺点：有开销，对I/O-bound process不友好
- 抢占时间片略大于一次典型交互时间最好
Virtual Round-Robin Scheduler(VRR，虚拟轮转法，添加虚拟辅助队列)
③Shortest Process Next(SPN)最短进程优先
原理：选择服务时间最短的进程(需预知服务时间)
调度时机：进程结束时
决策模式：非抢占式
- 优点：最短平均等待时间，最短平均周转时间
- 缺点：对长进程不利，会产生饥饿
④Shortest Remaining Time(SRT)最短剩余时间
原理：选择进程剩余时间最短的(需预知服务时间，若剩余时间相同，遵循FCFS)
调度时机：新进程到达时或进程结束时
决策模式：抢占式
- 优点：高吞吐量
- 缺点：可能发生饥饿
⑤Highest Response Ratio Next(HRRN)最高响应比优先
原理：选取响应比最高的(需预知服务时间)
调度时机：进程结束时
决策模型：非抢占式
- 优点：高吞吐量，无饥饿
⑥Feedback多级反馈列表
原理：有多个调度队列，运行一次降级一次(不需要知道服务时间)
调度时机：时间片用完或进程结束
决策模式：抢占式(采用时间片分配，优先级从高到底，时间片从小到大)
- 缺点：调度复杂，开销大，可能饥饿
(i表示第几个进程到达，从0开始)
总结：
2.4 公平共享调度
- 用户的应用程序以进程集(process sets)的形式运行
- 用户更关注应用程序的性能
- 需要根据进程集做出调度决策
这篇关于操作系统（Operating System）知识点复习——第九章 单处理器调度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
