5.8 轮询调度模式

2024-01-30 12:12
文章标签 模式 调度 5.8 轮询

本文主要是介绍5.8 轮询调度模式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

5.8.1 Abstract

轮询调度模式(Round Robin Pattern)是一种公平的调度策略,适用于那些所有任务的进展比满足特定截止时间更重要的系统。与循环执行模式(Cyclic Executive Pattern)相似,但轮询模式会基于时间进行任务抢占。这种模式在实时系统的文献中经常被讨论,因为它适用于任务的紧急性比关键性更重要的情况。

紧急性(urgency)通常指任务的截止时间的临近程度,即任务需要在多快的时间内完成。

关键性(criticality)指的是任务完成截止时间的重要性,即如果任务不能在截止时间前完成,对系统的功能或正确性会产生多大的影响。

这两个概念虽然不同,但操作系统通常提供的是一个概念:优先级。操作系统使用任务的优先级来决定当多个任务都准备好运行时,哪些任务应该优先执行。也就是说,操作系统总是优先运行所有当前准备好运行的任务中优先级最高的任务。

在动态优先级模式(Dynamic Priority Pattern)中,最高优先级的任务是截止时间最近的任务。动态优先级模式明确强调紧急性高于关键性。

紧急性和关键性是调度可行性的两个最重要的概念,但操作系统通常提供的是单一的值:优先级。在静态优先级模式(Static Priority Pattern)中,优先级在设计时设置,通常反映了紧急性和关键性的结合。在动态优先级模式中,任务的优先级是在运行时根据任务的紧急性设置的。

简而言之,紧急性关注的是任务完成的时间限制,而关键性关注的是任务完成对系统整体的重要性。两者在任务调度中都是重要的考量因素,但它们影响任务优先级的方式不同。

5.8.2 Problem

轮询模式解决的问题是如何在一个调度周期内,以大致相同的速率推进整个任务集合,特别是那些在单个调度周期内无法完成的任务。

5.8.3 Pattern Structure

轮询模式是循环执行模式的一个简单变体。两者之间的区别在于,轮询模式中的调度器能够抢占正在运行的任务,并且会在收到其关联定时器的时钟中断信号时执行抢占。图 5-15 展示了轮询模式的两种形式。

  • 完整形式(图 5-15a)展示了任务控制块 (Task Control Block) 和栈等基础设施类。
  • 简化形式(图 5-15b)则省略了这些类,只保留了核心结构。

5.8.4 Collaboration Roles

轮询调度模式由多个协作角色共同实现,它们各有其独特的职责:

  • 抽象线程 (Abstract Thread): 抽象类,不可直接实例化,提供任务的基本接口,例如启动、停止、获取状态等。所有具体线程都继承自该抽象类,从而保证接口的一致性。
  • 具体线程 (Concrete Thread): 可实例化的具体任务,包含实际完成系统工作的代码。它封装了这些“语义”对象,并使其融入并发框架。
  • 调度器 (Scheduler): 系统初始化时,调度器首先加载所有任务,然后依次运行它们。任务可以主动交出控制权,也可以在调度器收到定时器信号时被抢占。
  • 栈 (Stack): 与标准编程语言类似,每个线程都需要一个栈来存储局部变量、函数返回值和返回地址。由于线程可能会在执行过程中被中断,因此需要独立的栈来保证恢复执行时的正确性。
  • 任务控制块 (Task Control Block): 该对象为每个任务存储信息,包括初始启动地址和抢占后的重新进入点。系统中每个具体线程都对应一个任务控制块。
  • 定时器 (Timer): 定期向调度器发送时钟中断信号,触发任务切换。通常,定时器与硬件时钟协作,由调度器在系统启动前配置好时钟周期。收到中断后,调度器会执行任务切换操作。

总结:

轮询调度模式通过抽象线程、具体线程、调度器、栈、任务控制块和定时器等角色的协作,实现公平高效的并发任务执行。

5.8.5 Consequences

优点:

  • 公平性: 与循环执行模式一样,轮询模式为所有任务提供了运行机会,保障了公平性。
  • 鲁棒性: 即使某个任务出现错误行为,也不会导致整个系统崩溃。定时器会在恰当的时机进行任务切换,避免单一任务卡死系统。
  • 可扩展性: 相比循环执行模式,轮询模式在处理更多任务时表现出更佳的扩展性。

缺点:

  • 实时性欠佳: 对突发事件的响应不如其他调度模式迅速。
  • 不稳定性: 无法预测哪个任务会在系统超载时率先崩溃。
  • 任务切换开销: 随着任务数量增多,每个任务获得的时间片会缩短,大量任务切换会导致性能损耗,甚至系统“折腾” (thrashing) 现象。
  • 数据共享限制: 该模式提供的的数据共享机制相对简单,实现复杂模型可能存在困难。

总体:

轮询调度模式在公平性和鲁棒性方面表现出色,可扩展性也优于循环执行模式,但实时性和稳定性相对较弱。随着任务数量增加,性能可能恶化。该模式适用于任务间的紧急性差异不大,对响应速度要求不高的场景。

5.8.6 Implementation Strategies

轮询调度模式可以通过以下几步来实现:

  1. 创建抽象线程类,该类提供任务的基本接口,例如启动、停止、获取状态等。
  2. 创建具体线程类,该类继承自抽象线程类,并实现具体的任务逻辑。
  3. 创建调度器类,该类负责管理任务的调度。
  4. 创建定时器类,该类定期向调度器发送时钟中断信号,触发任务切换。

具体实现时,可以使用硬件定时器驱动的中断来实现定时器功能。此外,需要注意以下几点:

  • 具体线程可以通过临时禁用中断来防止在临界区内被抢占。但是,需要注意不要永久禁用中断,否则将导致任务切换无法正常进行。
  • 由于该模式并不假设任务是运行到完成,因此每个任务都需要一个独立的栈来存储局部变量、函数返回值和返回地址,以及一个任务控制块来存储被抢占任务的重新进入点。

总结:

轮询调度模式的实现相对简单,但需要注意一些细节,例如临界区内的中断处理和任务切换时的栈管理。

5.8.7 Related Patterns

轮询模式比循环执行模式稍微复杂一些,但没有静态优先级模式(Static Priority Pattern)和动态优先级模式(Dynamic Priority Pattern)这样的基于优先级的抢占模式复杂。

5.8.8 Sample Model

示例模型展示了一个简单的两任务模型,使用轮询模式实现。在这个简单的案例中,当调度器运行时,它会配置定时器以正确的周期运行,然后轮流执行每个任务。

系统的运行流程如下:

  1. 调度器启动: 首先,调度器配置定时器,设置适当的时间片长度。
  2. 执行第一个任务: 调度器调用第一个任务的默认 run() 操作,并在其栈上运行。
  3. 时间片到期: 定时器发出时钟中断信号,触发任务切换。
  4. 保存现场: 调度器保存当前任务的执行状态,包括栈指针等信息。
  5. 切换栈空间: 调度器激活第二个任务的栈,并设置栈指针为上次任务被中断的位置。
  6. 恢复执行: 调度器从中断处恢复第二个任务的运行。
  7. 反复切换: 时间片到期后,重复上述步骤,在两个任务之间轮流切换,直到所有任务完成。

关键细节:

  • 每个任务拥有独立的栈: 由于任务可能在任意时间点被抢占,独立栈用于保存任务的上下文信息,确保在恢复执行时能从正确的位置继续。
  • 调度器负责任务管理: 调度器负责配置定时器、启动任务、处理时钟中断、保存和恢复任务状态、切换栈空间。
  • 定时器触发抢占: 定时器是轮询模式的核心部件,它定期发出时钟中断信号,驱动调度器进行任务切换。

总结:

轮询模式通过调度器、定时器和独立栈的配合,实现了公平、高效的任务调度。图5-16清晰地展示了该模式的结构和运行流程。

这篇关于5.8 轮询调度模式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/660204

相关文章

RabbitMQ工作模式中的RPC通信模式详解

《RabbitMQ工作模式中的RPC通信模式详解》在RabbitMQ中,RPC模式通过消息队列实现远程调用功能,这篇文章给大家介绍RabbitMQ工作模式之RPC通信模式,感兴趣的朋友一起看看吧... 目录RPC通信模式概述工作流程代码案例引入依赖常量类编写客户端代码编写服务端代码RPC通信模式概述在R

SQL Server身份验证模式步骤和示例代码

《SQLServer身份验证模式步骤和示例代码》SQLServer是一个广泛使用的关系数据库管理系统,通常使用两种身份验证模式:Windows身份验证和SQLServer身份验证,本文将详细介绍身份... 目录身份验证方式的概念更改身份验证方式的步骤方法一:使用SQL Server Management S

Redis高可用-主从复制、哨兵模式与集群模式详解

《Redis高可用-主从复制、哨兵模式与集群模式详解》:本文主要介绍Redis高可用-主从复制、哨兵模式与集群模式的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录Redis高可用-主从复制、哨兵模式与集群模式概要一、主从复制(Master-Slave Repli

一文带你搞懂Redis Stream的6种消息处理模式

《一文带你搞懂RedisStream的6种消息处理模式》Redis5.0版本引入的Stream数据类型,为Redis生态带来了强大而灵活的消息队列功能,本文将为大家详细介绍RedisStream的6... 目录1. 简单消费模式(Simple Consumption)基本概念核心命令实现示例使用场景优缺点2

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3