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）分布式调度
3.4 产生死锁的原因和必要条件
1、死锁（Deadlock）：指多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。
2、请求推进的次序与对非剥夺性资源的争用都是造成死锁的原因。
3、产生死锁的原因可归结为如下两点：
1）竞争资源。
2）进程间推进顺序非法。
4、产生死锁的必要条件
①互斥条件：进程对所分配到的资源进行排他性使用
②请求和保持条件：进程已经保持了至少一个资源，又提出新的资源请求，而新请求资源被其他进程占有只能造成自身进程阻塞，但对自己已获得的其他资源保持不放，必然影响其他进程。
③不剥夺条件：进程已获得的资源未使用完之前不能被剥夺，只能在使用完时由自己释放。
④环路等待条件
注：四个条件缺一不可！！！
5、处理死锁的基本方法
事先预防：
1）预防死锁
2）避免死锁
事后处理：
3）检测死锁
4）解除死锁
3.5预防死锁的方法
预防死锁：
1、摒弃“请求和保持”条件
2、摒弃“不剥夺”条件
3、摒弃“环路等待”条件：有序设置资源
避免死锁：
采用避免死锁的方法则是只施加较弱限制条件，从而获得令人满意的系统性能。
银行家算法：
1、过程：就是对各进程的Request向量及资源数量进行一系列判断及值操作。
进程Pi发出资源请求后，系统按下述步骤进行检查：
首先是两个基本判断：
（1）IF
Requesti[j]<= Need[i,j]
THEN转向步骤2；
ELSE 认为出错，所需资源数超过宣布的最大值（自我矛盾)
（2）IF
Requesti[j]<= Available[j]
THEN转向步骤3；
ELSE 表示尚无足够资源，Pi需等待（现实不满足）
3.6死锁的检测与解除
1、检测时机：
Ø当进程等待时检测死锁
Ø定时检测
Ø系统资源利用率下降时检测死锁
2、检测算法：
每个进程和资源指定唯一编号
* 设置一张资源分配表
记录各进程与其占用资源之间的关系
* 设置一张进程等待表
记录各进程与要申请资源之间的关系
3、死锁解除：
1）剥夺资源
2）撤销进程
4、
死锁处理方法比较
