3.1处理机调度相关基本概念
1、处理机调度：多道程序环境下，动态的把处理机分配给就绪队列中的一个进程使之执行。
2、三级调度：
•高级调度（High Scheduling）
•中级调度（Intermediate-Level Scheduling）
•低级调度（Low Level Scheduling）
3、高级调度
1）决定外存后备队列中的哪些作业调入内存;
2）为它们创建进程、分配必要的资源;
3）将新创建的进程排在就绪队列上，准备执行。
4）系统运行并不一定存在高级调度
4、低级调度
1）是最基本的一种调度，在三种基本OS中都有。
2）进程调度方式（重点）
（1）非抢占方式（Non-preemptive Mode）
一旦处理机分配给某进程，该进程一直执行。决不允许其他进程抢占已分配运行进程的处理机。
（2）抢占方式（PreemptiveMode）
允许调度程序根据某种原则，暂停某个正在执行的进程，将处理机重新分配给另一进程。
5、中级调度
1）引入目的：提高内存利用率和系统吞吐量。根据条件将一些进程调出或再调入内存。
2）三种调度的频率和复杂度
进程调度：运行频率最高，算法不能太复杂，以免占用太多的CPU时间。分时系统通常10~100ms便进行一次。
作业调度：一个作业运行完毕退出系统时即触发重新调度一个新作业入内存，周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。
中级调度：运行频率基本上介于上述两种调度之间。
6、调度队列模型
①仅有进程调度的调度队列模型
②具有高级和低级调度的调度队列模型
③同时具有三级调度的调度队列模型
7、选择调度方式和调度算法的若干准则
1)面向用户的准则
（1）周转时间短：
�总的等待时间Tw = 在后备队列中等待 + 就绪队列上等待+阻塞队列中等待（等待I/O操作用时）
�周转时间T=Ts+Tw
�带权周转时间W= T/Ts
�平均周转时间、平均带权周转时间（n个作业求平均）
（2）响应时间快
（3）均衡性
（4）截止时间的保证
（5）优先权准则
2)面向系统的准则
系统吞吐量高：批处理系统的重要指标。
单位时间内所完成的作业数，跟作业本身（与作业平均长度密切相关）和调度算法都有关系；
处理机利用率好(主要针对大中型主机)
各类资源的平衡利用(主要针对大中型主机)
3.2常用调度算法
1、调度的实质就是一种资源分配。
2、先来先服务调度算法FCFS
1）一种最简单的调度算法，按先后顺序进行调度。既可用于作业调度，也可用于进程调度。
2）按照作业提交，或进程变为就绪状态的先后次序分派CPU；
3）新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
3、 短作业（进程）优先调度算法SJF/SPF
1）优点：
通过上表可见采用SJF/SPF算法，平均周转时间、平均带权周转时间都有明显改善。SJF/SPF调度算法能有效的降低作业的平均等待时间，提高系统吞吐量。
2）方式：
分抢占和非抢占两种方式，上例为简单的非抢占式。
4、高优先权优先调度算法HPF
1)分两种方式：
非抢占式优先权算法
抢占式优先权算法 关键点：新作业产生时
2)优先权的类型
静态优先权
动态优先权
3）高响应比优先调度算法HRRN
优先权 =（等待时间+要求服务时间)/要求服务时间
= 响应时间 / 要求服务时间
5、基于时间片的轮转调度算法RR
1）分时系统新需求：及时响应用户的请求；采用基于时间片的轮转式进程调度算法。
2）时间片轮转算法
（1.将系统中所有的就绪进程按照FCFS原则，排成一个队列。
（2.每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
（3.在一个时间片结束时，发生时钟中断。
（4.调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。
（5.进程阻塞情况发生时，未用完时间片也要出让CPU
3）多级反馈队列算法FB
（1）特点：多个就绪队列，循环反馈 动态优先级、时间片轮转
6、总结1：
7、总结2
3.3实时调度
一、实现实时调度的基本条件
1、提供必要的信息
2、系统处理能力足够强
3、采用抢占式调度机制
4、具有快速切换机制
二、实时调度算法的分类
1、根据实时任务的性质
1）硬实时调度算法
2）软实时调度算法
2、按调度方式
1）非抢占调度算法
2）抢占调度算法
3、根据调度时间不同
1）静态调度算法
2）动态调度算法
4、多处理机环境下
1）集中式调度
2）分布式调度
