苏州中车建设工程有限公司网站,分销网站,wordpress 本地化,小卖部做网站目录 处理机调度的层次
高级调度
作业
作业控制块 JCB
作业调度的主要任务
低级调度
中级调度
进程调度
进程调度时机
进程调度任务
进程调度机制
排队器
分派器
上下文切换器
进程调度方式
非抢占调度方式
抢占调度方式
调度算法
处理机调度算法的目标
处理…目录 处理机调度的层次
高级调度
作业
作业控制块 JCB
作业调度的主要任务
低级调度
中级调度
进程调度
进程调度时机
进程调度任务
进程调度机制
排队器
分派器
上下文切换器
进程调度方式
非抢占调度方式
抢占调度方式
调度算法
处理机调度算法的目标
处理机调度算法的共同目标
资源利用
公平性
平衡性
策略强制执行
批处理系统中处理机调度算法的目标
平均周转时间短
系统吞吐量高
处理机利用率高
分时系统中处理机调度算法的目标
保证响应时间快
保证均衡性
实时系统中处理机调度算法的目标
保证满足截止时间的要求
保证可预测性
先来先服务调度算法 FCFS
短作业优先调度算法 SJF
简介
优点
缺点
优先级调度算法
优先级调度算法的类型
非抢占式优先级调度算法
抢占式优先级调度算法
优先级的类型
静态优先级
动态优先级
高响应比优先调度算法 HRRN
轮转调度算法 RR
基本原理
进程切换时机
时间片大小的确定
多级队列调度算法
多级反馈队列调度算法
调度机制
性能
基于公平原则的调度算法
保证调度算法
公平分享调度算法
实时调度
实现实时调度的基本条件
提供必要的信息
系统处理能力强
采用抢占式调度机制
采用快速切换机制
实时调度算法分类
非抢占式调度算法
非抢占式轮转调度算法
非抢占式优先级调度算法
抢占式调度算法
基于时钟中断的抢占式优先级调度算法
立即抢占的优先级调度算法
最早截止时间优先算法 EDF
非抢占式调度方式用于非周期实时任务
抢占式调度方式用于周期实时任务
最低松弛度优先算法 LLF
优先级倒置
优先级倒置的形成
优先级倒置的解决方法
一种简单的解决方法
一种比较实用的解决方法 处理机调度的层次 要做什么 调度发生在…… 发生频率 对进程状态的影响 高级调度 长程调度、作业调度 按照某种规则从后备队列中选择合适的作业将其调入内存并为其创建进程 外存—内存 面向作业 最低 无—创建态—就绪态 中级调度 内存调度 按照某种规则从挂起队列中选择合适的进程将其数据调回内存 外存—内存 面向进程 中等 挂起态—就绪态 阻塞挂起态—阻塞态 低级调度 短程调度、进程调度 按照某种规则从就绪队列中选择一个进程为其分配处理机 内存—CPU 最高 就绪态—运行态
高级调度
别称长程调度、作业调度
调度对象作用
PS每个作用只调入一次调出一次
主要功能根据某种算法决定将外存上处于后备队列中的哪几个作业调入内存为其创建进程【作业调入时会建立 PCB调出时撤销 PCB】、分配必要的资源并将其放入就绪队列
应用主要用于多道批处理系统中在分时系统和实时系统中不设置高级调度 在多道批处理系统中作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入磁盘存储器并保存在一个后备作业队列中再由作业调度程序将其从外存调入内存
作业
定义一个具体的任务
作业是一个比程序更为广泛的概念不仅包含了的程序和数据而且配有一份作业说明书系统根据该说明书对程序的运行进行控制。在多道批处理中会将作业作为基本单位从外存调入内存
作业控制块 JCB
设置目的管理和调度作业
地位是作业在系统中存在的标准保存了系统对作业进行管理和调度所需的全部信息
包含的内容作业标志、用户名称、用户账号、作业类型CPU繁忙型、I/O繁忙型、批量型、终端型、作业状态、调度信息优先级、作业运行时间、资源需求情况预计运行时间、要求内存大小、资源使用情况……
执行过程每当一个作业进入系统时“作业注册”程序便会为该作业建立一个 JCB然后根据作业类型将其放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法调度它们被调度到的作业将被装入内存。在作业运行期内系统会按照 JCB 中的信息和作业说明书对作业进行控制。当一个作业执行结束并进入完成状态时系统便会收回已分配给它的资源并撤销其 JCB
作业调度的主要任务
作业调度的主要任务是根据 JCB 中的信息检查系统中的资源能否满足作业的需求以及按照一定的调度算法从外存的作业后备队列中选取某些作业调入内存并为其创建进程和分配必要的资源。然后将新创建的进程排在就绪队列上等待调度。故把作业调度称为接纳调度。在每次执行作业调度时都须做出的决定
接纳多少个作业在每次进行作业调度时应从后备队列中选取多少作业调入内存取决于多道程序度表示允许多少个作业同时在内存中运行。对系统而言希望装入内存较多的作业有利于提高资源利用率和系统吞吐量。但若内存中同时运行的作业太多进程在运行时因内存不足所发生的中断就会急剧增加会使进程的平均周转时间显著延长进而影响系统的服务质量。故多道程序度的确定方法综合考虑计算机系统规模、计算机运行速度、作业大小以及所能获得的系统性能好坏等情况后做出适当的抉择接纳哪些作业应选择后备队列中的哪些作业调入内存取决于所采用的调度算法
低级调度
别称短程调度运行频率最高在分时chi中通常仅10ms~100ms便进行一次低级调度、进程调度
调度对象进程或 LWP
主要功能根据某种算法决定就绪队列中的哪个进程应获得处理机并由分派程序将处理机分配给被选中的进程
地位最基本的一种调度
应用在多道批处理、分时和实时这 3 种系统中都必须配置这种调度
中级调度
别称内存调度
引入目的提高内存利用率和系统吞吐量
描述把暂时不能运行的进程调至外存等待此时进程的状态称为就绪驻外存状态或挂起状态。当其已具备运行条件且内存稍有空闲时由中级调度决定把外存上已具备运行条件的就绪进程重新调入内存并修改其状态为就绪状态挂在就绪队列上等待
PS一个进程可能会被多次调出、调入内存故中级调度发生的频率比高级调度更高
实质存储器管理中的对换功能
进程调度
地位进程调度是 OS 中必不可少的一种调度也是对系统性能影响最大的一种处理机调度
“狭义的进程调度”与“进程切换”的区别
狭义的进程调度指的是从就绪队列中选中一个要运行的进程此进程可以是刚被暂停执行的进程也可以是另一个进程后者需要进程切换进程切换指一个进程让出处理机由另一个进程占用处理机的过程
广义的进程调度包含选择一个进程和进程切换两个步骤
进程切换的过程主要完成了
对原来运行进程各种数据的保存对新的进程各种数据的恢复
PS进程切换是有代价的因此若过于频繁的进行进程调度、切换会使整个系统的效率降低使系统大部分时间都花在进程切换上而真正用于执行进程的时间减少
调度程序决定
让谁运行——调度算法运行多长时间——时间片大小
闲逛进程调度程序永远的备胎没有其他就绪进程时运行闲逛进程
闲逛进程的特性
优先级最低可以是零地址指令占一个完整的指令周期指令周期末尾例行检查中断能耗低
进程调度时机 PS有的系统中只允许进程主动放弃处理机有的系统中进程可以主动放弃处理机当有更紧急的任务需要处理时也会强行剥夺处理机被动放弃
真题
进程在操作系统内核程序程序临界区中不能进行调度与切换 √
进程处于临界区时不能进程处理机调度 ×
解析
临界资源一个时间段内只允许一个进程使用的资源各进程需要互斥地访问临界资源
临界区访问临界资源的代码
内核程序临界区一般是用来访问某种内核数据结构的比如进程的就绪队列
内核程序临界区访问的临界资源若不尽快释放极有可能影响操作系统内核的其他管理工作因此在访问内核程序临界区期内不能进行调度与切换
普通临界区访问的临界资源不会直接影响操作系统内核的管理工作因此在访问普通临界区时可以进行调度与切换
进程调度任务
保存 CPU 现场信息在进行进程调度时首先需要保存当前进程的 CPU 现场信息按某种算法选取进程调度程序须按某种算法从就绪队列中选取一个进程将其状态改为运行状态并准备把 CPU 分配给它把 CPU 分配给进程有分派程序把 CPU 分配给该进程此时需要将选中进程的 PCB 内有关 CPU 的现场信息装入 CPU 相应的各个寄存器内并把 CPU 的控制权交给该进程以使其能够从上次的断点处恢复运行
进程调度机制
为了实现进程调度在进程调度机制中应具有排队器、分派器、上下文切换器 3 个基本部分 排队器
为了提高进程调度的效率应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列以便调度程序能最快地找到它们。以后每当有一个进程转变为就绪状态时排队器便将其插入相应的就绪队列
分派器
将进程调度程序所选定的进程从就绪队列中取出然后进行从分派器到新选进程间的上下文切换将 CPU 分配给新选进程
上下文切换器
在对处理机进行切换时会发生两对上下文的切换操作
第一对上下文切换时OS 将保存当前进程的上下文即把当前进程的 CPU 寄存器内容保存到该进程的 PCB 内的相应单元而装入分派程序的上下文可以方便分派程序运行第二对上下文切换是移出分派程序的上下文把新选进程的 CPU 现场信息装入 CPU 的各个相应寄存器中以便新选进程运行
在进行上下文切换时需执行大量的 load 和 store 等操作指令已保存寄存器的内容。通过硬件实现减少上下文切换时间采用两组或多组寄存器其中一组寄存器供处理机在内核态时使用另一组寄存器供应用程序使用此时上下文切换只须改变指针使其指向当前寄存器组即可
进程调度方式
非抢占调度方式
描述采用非抢占调度方式时一旦把处理机分配给某进程就会一直让其运行下去决不会因为时钟中断或其他原因去抢占该进程的处理机直至该进程完成或发生某事件被阻塞时才会把分配给该进程的处理机分配给其他进程
引起进程调度的因素
正在执行的进程运行完毕或因发生某事件而使其无法继续运行正在执行的进程因提出 I/O 请求而暂停执行在进程通信或同步过程中执行了某种原语操作
优点实现简单、系统开销小
适用范围适用于大多数批处理系统但不能用于分时系统和大多数实时系统
抢占调度方式
描述抢占调度方式允许调度程序根据某种原则去暂停某个正在执行的进程并将已分配给该进程的处理机重新分配给另一进程
广泛使用的原因对于批处理机系统抢占调度方式可以防止一个长进程长时间占用处理机以确保处理机能为所有进程提供更为公平的服务
应用分时系统中采用抢占调度方式实现人机交互实时系统中抢占调度方式能满足实时任务的需求
缺点抢占调度方式比较复杂所须付出的开销较大
“抢占”原则
优先级原则允许优先级高的新到进程抢占当前进程的处理机短进程优先原则允许新到的短进程抢占当前长进程的处理机时间片原则各进程按时间片轮转运行时当正在执行的进程的一个时间片用完后便停止该进程的执行而重新进行调度
调度算法
处理机调度算法的目标
处理机调度算法的共同目标
资源利用
最重要的资源 —— CPU 的利用率 CPU 有效工作时间 / CPU 有效工作时间 CPU 空闲等待时间
公平性
含义各进程都获得合理的 CPU 时间以防止发生进程饥饿现象
相对公平
相同类型的进程应获得相同的服务不同类型的进程由于其紧急程度或重要性不同为其提供不同的服务
平衡性
系统中可能具有多种类型的作业有的属于 CPU 繁忙型作业有的属于 I/O 繁忙型作业。为使系统中的 CPU 和各种 I/O 设备都能经常属于忙碌状态调度算法应尽可能保证系统资源使用的平衡性
策略强制执行
对于所制定的策略包括安全策略只要有需要就必须予以准确的执行即使造成某些工作延迟也要执行
批处理系统中处理机调度算法的目标
以下目标的实现之间存在着一定的矛盾
平均周转时间短
周转时间作业周转时间指从作业被提交给系统开始到作业完成为止的这段时间间隔包括作业在外存后备队列上等待作业调度的时间进程在就绪队列上等待进程调度的时间进程在 CPU 上执行所耗费的时间以及进程等待 I/O 操作完成的时间后三项在一个作业的整个处理过程中可能会发生多次
作业周转时间 作业完成时间 - 作业提交时间
每个用户希望自己作业的周转时间最短
计算机系统的管理者希望作业的平均周转时间最短不仅可以有效提高系统资源的利用率还可以使大多数用户感到满意
平均周转时间 带权周转时间作业的周转时间 Ti 与系统为其提供服务的时间 Tsi之比Wi Ti / Tsi
平均带权周转时间 等待时间指进程/作业处于等待处理机状态时间之和等待时间越长用户满意度越低
进程等待时间指进程建立后等待被服务的时间之和在等待 I/O 完成的期间进程是被服务的故不计入等待时间作业不仅考虑建立进程后的等待时间还要加上作业在外存后备队列中等待的时间
系统吞吐量高
系统吞吐量指单位时间内系统所完成的作业数与批处理作业的平均长度有关
系统吞吐量 总共完成了多少道作业 / 总共花了多少时间
若仅为了获得高的系统吞吐量则应尽量多选择短作业运行
处理机利用率高
若仅为了使处理机的利用率高则应尽量多选择计算量大的作业运行
分时系统中处理机调度算法的目标
保证响应时间快
响应时间快是选择分时系统中进程调度算法的重要准则
响应时间指用户通过键盘提交一个请求开始到屏幕上显示出处理结果为止的这段时间间隔包括请求信息从键盘输入开始直至传送到处理机的时间处理机对请求信息进行处理的时间以及将所形成的响应信息回送到终端显示器的时间
保证均衡性
均衡性系统响应时间的快慢应与用户所请求服务的复杂性相适应
实时系统中处理机调度算法的目标
保证满足截止时间的要求
截止时间某任务必须开始执行的最迟时间或必须完成的最迟时间
对于实时系统而言调度算法的一个主要目标是保证实时任务满足截止时间的要求
保证可预测性
在实时系统中可预测性非常重要
先来先服务调度算法 FCFS
地位最简单的调度算法
使用既可用于作业调度也可用于进程调度
描述
作业调度当在作业调度中采用该算法时系统将按照作业到达的先后次序进行调度或者说会考虑在系统中等待时间最长的作业而不管该作业执行时间的长短。FCFS 调度算法会从后备作业队列中选择几个最先进入该队列的作用将其调入内存并为其分配资源和创建进程最后将其放入就绪队列进程调度当在进程调度中采用 FCFS 调度算法时每次调度都是从就绪的进程队列中选择一个最先进入该队列的进程并为之分配处理机使之投入运行。在该进程一直运行到完成或发生某事件而阻塞后进程调度程序才会将处理机分配给其他进程
调度方式非抢占式调度
周转时间 完成时间 - 到达时间
带权周转时间 周转时间 / 运行时间
等待时间 周转时间 - 运行时间
有 I/O 操作的进程等待时间 周转时间 - 运行时间 - I/O 操作时间
优点公平算法实现简单
缺点排在长作业进程后面的短作业需要等待很长的时间带权周转时间很大对短作业说用户体验不好即 FCFS 算法对长作业有利对短作业不利
饥饿现象某进程/作业长期得不到服务不会出现饥饿现象
短作业优先调度算法 SJF
简介
SJF 调度算法是以作业的长短计算优先级的作业越短其优先级越高
作业的长短以作业所要求的运行时间衡量
使用可分别用于作业调度和进程调度
描述
作业调度从外存的作业后备队列中选择估计运行时间最短的作业并优先将其调入内存运行进程调度短进程优先算法 SPF从就绪队列中选择估计运行时间最短的进程并为之分配 CPU 运行
调度方式非抢占式调度、抢占式调度
非抢占式短作业优先调度算法
周转时间 完成时间 - 到达时间带权周转是时间 周转时间 / 运行时间等待时间 周转时间 - 运行时间
抢占式短作业优先调度算法最短剩余时间优先算法 SRTN
描述每当有进程加入就绪队列改变时就需要调度若新到达的进程剩余时间比当前运行的进程剩余时间更短则由新进程抢占处理机当前运行进程重新回到就绪队列且当一个进程完成时也需要调度周转时间 完成时间 - 到达时间带权周转时间 周转时间 / 运行时间等待时间 周转时间 - 运行时间
饥饿现象某进程/作业长期得不到服务会出现饥饿现象
优点
“最短的”平均等待时间、平均周转时间 【不太严谨】
在所有进程同时可运行时采用 SJF 调度算法的平均等待时间、平均周转时间最少
在所有进程都几乎同时到达时采用 SJF 调度算法的平均等待时间、平均周转时间最少
抢占式的短作业/进程优先调度算法的平均等待时间、平均周转时间最短
缺点
必须预先知道作业的运行时间对长作业非常不利长作业的周转时间会明显增长当采用 FCFS 调度算法时无法实现人机交互SJF 调度算法完全没有考虑作业的紧迫程度故不能保证紧迫性作业得到及时处理
优先级调度算法
优先级调度算法基于进程的紧迫程度由外部赋予进程相应的优先级根据该优先级进行调度
使用可用于作业调度也可用于进程调度
描述
作业调度从后备队列中选择优先级最高的作业装入内存进程调度从就绪队列中选择具有最高优先级的进程在 CPU 上运行
饥饿现象某进程/作业长期得不到服务会出现饥饿现象
优先级调度算法的类型
非抢占式优先级调度算法
抢占式优先级调度算法
应用常用于对实时性要求较高的系统
优先级的类型
静态优先级
定义静态优先级在创建进程时确定在进程的整个运行期间保存不变
表示利用某一范围内的一个整数表示称为优先数
确定进程优先级大小的依据
进程类型通常系统进程如接收进程、对换进程……的优先级要高于一般用户进程的优先级进程对资源的需求对资源要求少的进程应被赋予较高的优先级用户要求根据进程的紧迫程度以及用户所付费用的多少确定优先级前台进程优先级高于后台进程OS 更偏好 I/O 型进程I/O 繁忙型进程
优点简单易行系统开销小
缺点不够精确可能出现优先级低的进程长期未被调用的情况
动态优先级
定义指在创建进程之初先赋予进程一个优先级然后优先级会随进程的推进或等待时间的增加而改变以便获得更好的调度性能
高响应比优先调度算法 HRRN
地位优先级调度算法的一个特例
使用通常用于作业调度
描述既考虑作业的等待时间又考虑作业的运行时间因此既照顾了短作业又不会致使长作业的等待时间过长从而改善了处理机调度的性能
优先级的变化规律优先级 等待时间 要求服务时间/ 要求服务时间 响应时间 / 要求服务时间 响应比 Rp
若作业的等待时间相同则要求服务时间越短优先级越高此时 HRRN 调度算法类似于 SJF 算法有利于短作业当作业的要求服务时间相同时其优先级取决于等待时间此时 HRRN 调度算法类似于 FCFS 调度算法对于长作业的优先级可随等待时间得到增加而提高当作业的等待时间足够长时可获得处理机
调度方式非抢占式调度
优点实现了较好的折中
缺点每次调度之前都需要先计算响应比增加系统开销
轮转调度算法 RR
描述采取非常公平的处理机分配方式即让就绪队列上的每个进程每次仅运行一个时间片若就绪队列上有 n 个进程则每个进程每次大约可获得 1/n 的处理机时间
地位分时系统中最简单、最常用的进程调度算法
饥饿现象某进程/作业长期得不到服务不会出现饥饿现象
基本原理
在 RR 调度算法中系统将所有的就绪进程按 FCFS 策略排成一个就绪队列。系统可设置每隔一定时间便产生一次中断去激活进程调度程序进行调度把处理机分配给队首进程并令其执行一个时间片。当其运行完后再把处理机分配给就绪队列中新的队首进程同时让其也执行一个时间片。保证就绪队列中的所有进程在确定的时间段内都能获得一个时间片的处理机时间
进程切换时机
若一个时间片尚未用完而正在运行的进程便已经完成则立即激活调度程序将已经运行完成的进程从就绪队列中删除再调度就绪队列中新的队首进程运行并启动一个新的时间片当一个时间片用完时计时器中断处理程序会被激活此时若进程尚未运行完毕调度程序就把它送往就绪队列的末尾
时间片大小的确定
一个较为可取的时间片大小是略大于一次典型的交互所需要的时间使大多数交互式进程能在一个时间片内完成从而可以获得很小的响应时间
时间片太大退化为先来先服务调度算法
时间片太小进程切换过于频繁系统花费大量的时间处理进程切换导致实际用于进程执行的时间比例减少 多级队列调度算法
描述多级队列调度算法将系统中的进程就绪队列从一个拆分为若干个将不同类型或性质的进程固定分配在不同的就绪队列不同的就绪队列采用不同的调度算法一个就绪队列中的进程可以设置不同的优先级不同的就绪队列本身也可以设置不同的优先级
优点在多处理机系统中多级队列调度算法由于安排了多个就绪队列因此可以很方便地为每个处理机设置一个单独的就绪队列。不仅对每个处理机的调度可以实施各自不同的调度策略而且对于一个含有多个线程的进程而言可以根据其要求将所有线程分配在一个就绪队列上并全部在一个处理机上运行再者对于一组需要相互合作的进程或线程而言可将其分配到一组处理机所对应的多个就绪队列上使其能同时获得处理机并行执行
多级反馈队列调度算法
饥饿现象某进程/作业长期得不到服务会出现饥饿现象
调度机制 设置多个就绪队列在系统中设置多个就绪队列为每个队列赋予不同的优先级。第一个队列的优先级最高第二个队列次之其余队列的优先级依次降低。为不同队列中的进程所赋予的执行时间片的大小不同优先级越高的队列的时间片越小每个队列都采用 FCFS 调度算法当新进程进入内存后首先将其放入第一个队列的末尾按 FCFS 策略等待调度。当轮到该进程执行时若其能在该时间片内完成则可撤离系统否则调度程序将其转入第二个队列的末尾等待调度若其在第二个队列中运行一个时间片后仍未完成则将其放入第三个队列依次类推。当进程最后被降到第 n 队列后在第 n 队列中便采取 RR 方式运行按队列优先级调度调度程序首先调度最高优先级队列中的各进程运行仅当第一队列空闲时才调度第二队列中的进程运行换而言之仅当第 1~i-1队列均空时才会调度第 i 队列中的进程运行。若处理机在第 i 队列中为某进程服务时又有新进程进入任一优先级较高的队列则必须把正在运行的进程放回到第 i 队列的末尾并把处理机分配给新到的高优先级进程
调度方式抢占式调度
性能
在多级反馈队列调度算法中若规定第一个队列的时间片略大于多数人机交互所需的处理时间则能较好地满足各类用户的需要
终端型用户由于终端型用户提交的作业多属于交互型作业通常较小系统只要能使这些作业在第一队列规定的时间片内完成便可使终端型用户感到满意短批处理作业用户对于这类作业若可在第一队列中执行完成则能获得与终端型作业一样的响应时间对于稍长的短作业也只须在第二和第三队列各执行一个时间片即可完成其周转时间仍然较短长批处理作业用户对于这类作业将其依次在第 12...n 个队列中运行然后再按 RR 方式运行用户不必担心其作业长期得不到处理
基于公平原则的调度算法
保证调度算法
向用户做出明确的性能保证可以做到调度的公平性
一种比较容易实现的性能保证措施公平分配处理机若在系统中有 n 个相同类型的进程同时运行则为了公平起见须保证每个进程都能获得相同的处理机时间
在实施公平调度算法时系统必须具备的功能
跟踪计算每个进程自创建以来已经执行的处理时间计算每个进程应获得的处理机时间即自创建以来的时间除以 n计算进程获得处理机时间的比率即进程实际执行的处理时间和应获得的处理机时间之比比较各进程获得处理机时间的比率调度程序应选择比率最小的进程将处理机分配给它并让它一直运行直到它的比率超过最接近它的进程的比率为止
公平分享调度算法
描述分配给每个进程相同的处理机时间
在公平分享调度算法中调度的公平性主要是针对用户的即所有用户能获得相同的处理机时间或所要求的时间比例。因为调度是以进程为基本单位的所以必须考虑每个用户所拥有的进程数目 实时调度
实现实时调度的基本条件
提供必要的信息
就绪时间指某任务的状态转换为就绪状态的起始时间在周期任务的情况下就绪时间是事先预知的一串时间序列开始截止时间和完成截止时间对于典型的实时应用只须知道开始截止时间或完成截止时间处理时间一个任务从开始执行直至完成所需的时间资源要求任务执行时所需的一组资源优先级若某任务的开始截止时间被错过了势必引起故障则应赋予任务“绝对”优先级若其开始截止时间的错过对任务的继续执行无重大影响则可赋予其“相对”优先级以供调度程序参考
系统处理能力强
假定系统中有 m 个周期性的 HRT 任务它们的处理时间表示为 Ci周期时间表示为 Pi则在单处理机情况下必须满足 的限制条件系统才可以调度。因该限制条件并未考虑任务切换所花费的时间故当利用该限制条件时应适当留有余地
提高处理机能力的途径
采用单处理机系统须增强其处理能力以显著减少对每个任务的处理时间采用多处理机系统假定系统中的处理机个数为 N则限制条件应为
采用抢占式调度机制
在含有 HRT 任务的实时系统中广泛采用抢占式调度机制可以满足 HRT 任务对截止时间的要求这种调度机制比较复杂
对于一些小的实时系统若能预知任务的开始截止时间则对实时任务的调度可采用非抢占式调度机制以简化调度程序和任务调度时所花费的系统开销
在设计这种调度机制时应使所有的实时任务都比较小并在执行完关键性程序和临界代码后能及时地将自己阻塞起来以便释放处理机并供调度程序去调度开始截止时间即将到达的任务
采用快速切换机制
为保证 HRT 任务能及时运行在系统中应采用快速切换机制使之能进行任务的快速切换该机制应具有以下两方面的能力
对中断的快速响应能力对紧迫的外部事件请求中断能及时响应要求系统具有快速硬件中断机构还应使禁止中断的时间间隔尽量短以免耽误时机影响其他紧迫任务的执行快速的任务分派能力为了提高分派程序的任务切换速度应使系统中的每个运行功能单位适当地小以减少任务切换的开销
实时调度算法分类 非抢占式调度算法
非抢占式轮转调度算法
描述由一台计算机控制若干个相同的或类似的对象为每个被控对象建立一个实时任务并将其排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后便把它挂在轮转队列的末尾进行等待调度程序再选择下一个队首任务运行
响应时间数秒至数十秒
应用可用于要求不太严格的实时控制系统
非抢占式优先级调度算法
描述若在系统中还含有少数具有一定要求的实时任务则可采用非抢占式优先级调度算法系统会为这些任务赋予较高的优先级。当这些实时任务到达时系统会把其安排在就绪队列的队首等待当前任务自我终止或运行完成后再通过调度执行队首的高优先级进程
响应时间数百毫秒至数秒
应用可用于有一定要求的实时控制系统
抢占式调度算法
根据抢占发生时间的不同将抢占式调度算法分为 基于时钟中断的抢占式优先级调度算法 和 立即抢占的优先级调度算法
基于时钟中断的抢占式优先级调度算法
描述在某实时任务到达后若其优先级高于当前任务的优先级则此时并不立即抢占当前任务的处理机而是等到时钟中断发生后调度程序才会剥夺当前任务的执行将处理机分配给新到的高优先级任务
调度时延几毫秒至几十毫秒
应用用于大多数的实时系统
立即抢占的优先级调度算法
描述此调度算法要求 OS 具有快速响应外部中断事件的能力。一旦出现外部中断只要当前任务未处于临界区便能立即剥夺当前任务的执行把处理机分配给请求中断的紧迫任务
调度时延几百微秒至几毫秒
最早截止时间优先算法 EDF
描述根据任务的截止时间确定任务的优先级任务的截止时间越早其优先级越高具有最早的截止时间的任务排在队列的前面。调度程序在选择任务时总是选择就绪队列中的第一个任务并为之分配处理机
使用即可用于抢占式调度方式中又可用于非抢占式调度方式中
非抢占式调度方式用于非周期实时任务 解析4 个非周期实时任务先后到达。系统先调度任务 1 执行在任务 1 执行期间任务 2、任务 3 又先后到达。由于任务 3 的开始截止时间早于任务 2 的故系统在执行完任务 1 后先调度任务 3 执行。在此期间任务 4 又到达了其开始截止时间仍早于任务 2 的故在任务 3 执行完后系统又会先调度任务 4 执行最后才调度任务 2 执行
抢占式调度方式用于周期实时任务 最低松弛度优先算法 LLF
描述最低松弛度优先算法在确定任务的优先级时根据的是任务的紧急程度或松弛度。任务紧急程度越高赋予该任务的优先级就越高使其可被优先执行
松弛度必须完成时间 - 其本身的运行时长 - 当前时间 解析任务 A 每 20ms 执行一次执行时长为 10ms任务 B 每 50ms 执行一次执行时长为 25ms任务 A 和任务 B 每次必须完成的子任务 A1、A2、A3、……和 B1、B2、B3、……的时间情况 优先级倒置
优先级倒置的形成
高优先级进程或线程被低优先级进程或线程延迟或阻塞
优先级倒置的解决方法
一种简单的解决方法
规定在进程进入临界区后其所占用的处理机就不允许被抢占
适用情况系统中的临界区都较短且不多时适用
一种比较实用的解决方法
建立在动态优先级基础的基础上
规定当高优先级进程要进入临界区去使用临界资源时若已有一个低优先级进程正在使用该资源则此时一方面高优先级进程会被阻塞另一方面会由低优先级进程继承高优先级进程的优先级并一直保持到低优先级进程推出临界区
目的不让比低优先级进程的优先级稍高但比高优先级进程的优先级稍低的进程插进来导致延缓低优先级进程退出临界区
