实时系统中的任务通常都联系着一个截止时间,实时调度的关键是保证满足实时任务 对截止时间的要求 为了保证满足实时任务对截止时间的要求,实时系统必须具备足够强的处理能力和快速 的切换机制。通常,在提交实时任务时,系统将该任务的截止时间、所需的处理时间、资源要 求和优先级等信息一起提交给调度程序。若系统能及时处理该任务,调度程序便将它接收下来, 否则,将拒绝接收该任务。 对不同的实时系统,其调度方式和算法的选择也各不相同。在一些小型实时系统或要求不 太严格的实时控制系统中,常采用简单易行的非抢占式轮转调度方式,它可获得数秒至数十秒 的响应时间:而在有一定要求的实时控制系统中,可采用非抢占式优先权调度算法,它可获得 仅为数秒至数百毫秒级的响应时间。在要求比较严格(响应时间为数十毫秒以下)的实时系统 中,应采用比较复杂的抢占调度方式,其中,基于时钟中断的抢占式优先权调度算法,可获得几 十毫秒至几毫秒的响应时间,适用于大多数的实时系统:丽立即抢占的优先权调度算法,可将 响应时间降到几毫秒至1∞微秒,甚至更低,适用于要求更严格的实时系统。下面将介绍两种 常用的高优先权优先的实时调度算法 (1)最早截止时间优先CEDE币算法:该算法根据任务的开始截止时间来确定任务的优先级, 即任务的开始截止时间愈早,其优先级愈高。在实现该算法时,要求系统中保持一个实时任务就 绪队列,该队列按各任务的截止时间的早晚排序。EDF算法即可采用非抢占调度方式,也可采 用抢占调度方式。在采用抢占调度方式时,如果新到达的任务的开始截止时间比正在执行的任 务早,则它将立即抢占CP (2)最低松弛度优先(LF)算法。LIF算法根据实时任务的松弛度(松弛度=任务必须完成的 时间一任务本身的运行时间一当前时间)来确定任务的优先权,即任务的松弛度愈低,其优先 权愈高。在实现该算法时,要求系统中有一个按松弛度排序的实时任务就绪队列。 该算法主要用于可抢占调度方式中,当一任务的最低松弛度减为0时,它便必须立即抢占 CPU,以保证按截止时间的要求完成任务。 5.多处理机系统中的调度 1.进程分配方式 在对称多处理器系统(SMPS)中,各处理器单元在功能和结构上都是相同的,因而可把所有 的处理器作为一个处理器池?并将进程分配到其中的任干处理器上运行。在进行进程分配时, 可采用静态和动态两种分配方式。采用静态分配方式时,一个进程从开始执行直至其完成,都 被固定分配到一个处理器上去执行,此时,需要为每个处理器维护一个专用的就绪队列。静态 分配方式的优点是调度的开销小,缺点是会使处理器的忙闲不均。采用动态分配方式时,系统 中设置有二个公用的就绪队列,所有的就绪进程都被放在该队列中,然后被随机地调度到任 空闲的处理器上去执行,因此,在一个进程生命周期的不同时刻,它可以在不同的处理器上执 行,对松散祸合的多处理器系统,此时需要进行进程现场信息的转移,会明显增加调度开销,但 动态分配方式能较好地消除处理器忙闲不均的现象。 在配置有多种类型处理器单元的非对称多处理器系统中,常采用主一从式结构,即操作系 统的核心驻留在某个特定的处理器(即主处理器)上,而其他的处理器(即从处理器)只用于执 行用户程序。进程调度由主处理器执行,从处理器空闲时,便向主处理器发一索求进程的信号 并由主处理器从自己的就绪队列中摘下一个进程分配给请求的从处理器。这种方式的优点是 系统处理简单,缺点是主处理器的故障会导致整个系统瘫痪,而且主处理器容易成为系统瓶 2.进程(线程)调度方式 在多处理机系统中,常用的进程(线程)调度方式主要有 (1)自调度方式。一它是指在系统中设置一个公用的进程(或线程)队列,所有的处理器在空实时系统中的任务通常都联系着一个截止时间,实时调度的关键是保证满足实时任务: 对截止时间的要求。 为了保证满足实时任务对截止时间的要求,实时系统必须具备足够强的处理能力和快速 的切换机制。通常,在提交实时任务时,系统将该任务的截止时间、所需的处理时间、资源要 求和优先级等信息一起提交给调度程序。若系统能及时处理该任务,调度程序便将它接收下来, 否则,将拒绝接收该任务。 对不同的实时系统,其调度方式和算法的选择也各不相同。在一些小型实时系统或要求不 太严格的实时控制系统中,常采用简单易行的非抢占式轮转调度方式,它可获得数秒至数十秒 的响应时间:而在有一定要求的实时控制系统中,可采用非抢占式优先权调度算法,它可获得 仅为数秒至数百毫秒级的响应时间。在要求比较严格(响应时间为数十毫秒以下)的实时系统 中,应采用比较复杂的抢占调度方式,其中,基于时钟中断的抢占式优先权调度算法,可获得几 十毫秒至几毫秒的响应时间,适用于大多数的实时系统:丽立即抢占的优先权调度算法,可将 响应时间降到几毫秒至 1∞微秒,甚至更低,适用于要求更严格的实时系统。下面将介绍两种 常用的高优先权优先的实时调度算法。 (1)最早截止时间优先 CEDE 币算法：该算法根据任务的开始截止时间来确定任务的优先级, 即任务的开始截止时间愈早,其优先级愈高。在实现该算法时,要求系统中保持-个实时任务就 绪队列,该队列按各任务的截止时间的早晚排序。EDF 算法即可采用非抢占调度方式,也可采 用抢占调度方式。在采用抢占调度方式时,如果新到达的任务的开始截止时间比正在执行的任 务早,则它将立即抢占 CPU。: (2)最低松弛度优先(LLF)算法。LIF 算法根据实时任务的松弛度(松弛度=任务必须完成的 时间一任务本身的运行时间一当前时间)来确定任务的优先权,即任务的松弛度愈低,其优先 权愈高。在实现该算法时,要求系统中有一个按松弛度排序的实时任务就绪队列。 该算法主要用于可抢占调度方式中,当一任务的最低松弛度减为 0 时,它便必须立即抢占 CPU,以保证按截止时间的要求完成任务。 5.多处理机系统中的调度 1.进程分配方式 在对称多处理器系统(SMPS)中,各处理器单元在功能和结构上都是相同的,因而可把所有 的处理器作为一个处理器池?并将进程分配到其中的任干处理器上运行。在进行进程分配时, 可采用静态和动态两种分配方式。采用静态分配方式时,一个进程从开始执行直至其完成,都 被固定分配到一个处理器上去执行,此时,需要为每个处理器维护一个专用的就绪队列。静态 分配方式的优点是调度的开销小,缺点是会使处理器的忙闲不均。采用动态分配方式时,系统 中设置有二个公用的就绪队列,所有的就绪进程都被放在该队列中,然后被随机地调度到任一 空闲的处理器上去执行,因此,在一个进程生命周期的不同时刻,它可以在不同的处理器上执 行,对松散祸合的多处理器系统,此时需要进行进程现场信息的转移,会明显增加调度开销,但 动态分配方式能较好地消除处理器忙闲不均的现象。 在配置有多种类型处理器单元的非对称多处理器系统中,常采用主一从式结构,即操作系 统的核心驻留在某个特定的处理器(即主处理器)上,而其他的处理器(即从处理器)只用于执 行用户程序。进程调度由主处理器执行,从处理器空闲时,便向主处理器发一索求进程的信号, 并由主处理器从自己的就绪队列中摘下一个进程分配给请求的从处理器。这种方式的优点是 系统处理简单,缺点是主处理器的故障会导致整个系统瘫痪,而且主处理器容易成为系统瓶 颈。 2.进程(线程)调度方式 在多处理机系统中,常用的进程(线程)调度方式主要有: (1)自调度方式。-它是指在系统中设置一个公用的进程(或线程)队列,所有的处理器在空