3.1处理机调度相关基本概念
处理机调度
1高级调度：又称作业调度或长程调度，接纳调度（主要在早期批处理阶段，处理在外存上的作业）
系统运行并不一定存在高级调度
2.低级调度：也称为进程调度、微观调度或短程调度
最基本的一种调度，在批处理系统、分时系统、实时系统中都有
3.中级调度
引入目的：提高内存利用率和系统吞吐量
5.选择调度方式和调度算法的若干准则
1）面向用户的准则：周转时间短、响应时间快、均衡性、截止时间的保证、优先权准则
2）面向系统的准则：系统吞吐量高、处理机利用率好、各类资源的平衡利用
二、调度算法
1.先来先服务调度算法FCFS（非抢占方式）
按照作业提交。或进程变为就绪状态的先后次序分派CPU，新作业只有当当前作业或进程执行完或阻塞才获得CPU运行
不利于段作业（进程）
不足：段作业C的带权周转时间高达100长作业D的带权周转时间仅为1.99；有利于CPU繁忙型的作业，而不利于I/o繁忙的作业
2.短作业（进程）有限调度算法SJF/SPF
此算法能有效的降低作业的平均等待时间，提高系统吞吐量
方式：分抢占和非抢占两种方式，上例为简单的非抢占式。
不足：1.对短作业有利，但同时造成了对长作业的不利。2.由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。3.未考虑作业的紧迫程度，因而不能保证紧迫性作业的及时处理。
3.高优先权优先调度算法HPF
1）分非抢占式和抢占式优先权算法（关键点：新作业产生时）
2）优先权的类型
静态优先权：创建进程时确定，整个运行期间保持不变
动态优先权：创建进程时赋予的优先权，可随进程的推进或随其等待时间的增加而改变
3）高响应比优先调度算法HRRN
HRRN为每个作业引入动态优先权，使作业的优先级随着等待时间的增加而以速率a提高
1.同时到达的作业优先权相同（若等待时间t相同，利于短作业；长作业的优先级随等待时间的增加而提高）
2.实行时间相同的作业，优先权的高低决定于其等待时间的长短，也就是先来先服务
什么时候计算各进程的响应比优先权？
调度选择时：作业完成时、新作业完成时（抢占、非抢占）、时间片完成时、进程阻塞时
3.基于时间片的轮转调度算法RR
（1）时间片轮转算法
时间片长度 过长：FCFS 过短：频繁切换
（2）多级反馈队列算法FB
1.设置多个就绪队列，各队列有不同的优先级，优先级从第一个队列依次降低
2.赋予各队列进程执行时间片大小不同，优先权越高，时间片越短
三、实时调度
1.系统能够在限定的响应时间内提供所需水平的服务
2.计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错
基本条件：
1）提供必要的信息
就绪时间、开始截止时间、完成截止时间、处理时间、资源要求、优先级
2）系统能力足够强
3）采用抢占式调度机制
4）具有快速切换机制
抢占式调度算法：1、基于时钟：某高优先级任务到达后并不立即抢占，，而等下一个时钟中断时抢占。2、立即抢占：一旦出现外部中断，只要当前任务未处于临界区，就立即抢占处理机。
最早截止时间优先EDF、最低松弛度优先LLF（主要用于抢占调度方式中）
四、产生死锁的原因和必要条件
多道程序系统借助并发执行改善资源利用率，提高系统吞吐量，但可能发生一种危险——死锁（指多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种状态时，若无外力作用，它们都将无法再向前推进）
饥饿：指一个进程无休止地等待
产生死锁的原因：1.竞争资源 2.进程间推进程序非法（请求和释放资源的顺序不当）
产生死锁的必要条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件
死锁避免属于动态策略
预防死锁：
①摒弃“请求和保持”条件：所有进程开始运行前，必须一次性的申请其在整个运行过程所需的全部资源（AND）。算法简单、易于实现且很安全。但缺点是资源浪费严重、或进程延迟运行。
②摒弃“不剥夺”条件：允许进程先运行，但当提出的新要求不被满足时必须释放它已保持的所有资源，待以后需要时再重新申请。实现比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和释放等情况。
③摒弃“环路等待”条件：将所有资源按类型进行线性排队，赋予不同序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样在所形成的资源分配图中，不可能会出现环路。
2.避免死锁
安全状态：没有死锁；不安全状态：可能会产生死锁
安全序列：只要系统按此进程列分配资源，就能使每个进程都顺利完成。
3.银行家算法避免死锁
死锁的解除：1.剥夺进程。2.撤销进程
网友评论