基于FPGA的实时操作系统调度器硬件化设计与实现

关 沫，张晓宇

(沈阳工业大学 信息科学与工程学院，辽宁 沈阳 110870)

0 引言

面对嵌入式系统功能需求的复杂化和多样性，目前在复杂任务中多核系统已基本取代单核系统。随着异构多核系统的快速发展，其以芯片高利用率、低功耗、高并行化应用程序等诸多优势已成为处理器体系结构发展的一个重要方向[1]。但是多核处理器在体系结构和系统管理上有不同于单核处理器的固有特性，在多核平台上高效地设计和部署软件实时操作系统仍然面临着一些挑战。一般多核系统运行模式主要有三种：Asymmetric Multi-Processing(AMP)、Symmetric Multi-Processing(SMP)和Bound Multi-Processing(BMP)。SMP运行模式的实时操作系统无法部署在异构多核系统中，在该运行模式下的实时系统的实例存在于RAM中，并依附于同构处理器进行调度，管理所有可运行系统实例的处理器内核，而对于异构的处理器系统实例只存在于一种架构的处理器中而无法管理所有架构[2-3]。AMP运行模式可使多个系统实例存在于不同处理器系统中，但不能将多核系统统一管理起来。BMP运行模式允许共享同一个数据集的应用独立地运行在同一个内核上，但锁定于一个内核的应用无法利用其他内核，即使其他内核处于空闲状态，造成系统浪费。

在系统的实时性方面，对于基于软件实现的多核实时操作系统的任务调度产生的Non-deterministic Polynomial(NP)难题[4]，单纯依靠改进算法已不能使实时性得到更大的提高，仅依靠提升处理器的性能产生的效果也十分有限。要实现调度算法并行的物理操作，在现有的计算机处理器中很难达到，必须借助外部辅助设备进行[5]。而硬件电路独立于处理器运行，不占用处理器的处理时间，所节省的时间可用于执行任务程序，所以基于硬件实现的操作系统可以使其实时性和可靠性显著提高[6]。

本文工作是基于目前Field Programmable Gate Array(FPGA)具有功能强大、设计灵活、易于维护和升级等特点[7]，使用FPGA进行实时操作系统内核调度器的搭建，硬件化系统内核的任务调度算法，并设计了一种新的运行模式VMP，使系统不再是一段处理器的可执行程序，系统实例运行在处理器之外，不再依附与处理器本身进行调度，从而实现对所有异构处理器系统的管理。

1 硬件实时操作系统运行模式设计

硬件实时操作系统与软件实时操作系统虽然在设计与搭建上不太相同，但其主要功能基本一致。任务调度算法是软件实时操作系统的核心也是硬件操作系统的核心器件[8]。硬件系统调度器使用的调度算法与一般软件系统一样均为抢占式加轮询式。对于异构处理器的任务调度，本文设计一种新的运行模式VMP，该运行模式将SMP与BMP两种运行模式相结合，使之可以动态地相互转化或共存在一个系统之中，在SMP运行模式下可保证系统的整体运算能力，在BMP运行模式下可降低CACHE冲突。

在VMP运行模式下需将可执行任务进行分组，然后指定内核执行的任务分组形成可执行任务集合，每个内核的调度任务都将在任务集合中选取。在运行时可动态改变任务分组及集合内分组。图1所示有7个任务需在3种不同架构的处理器中运行，其中任务0、1为DSP任务，任务2为X86任务，任务3、4、5、6为ARM任务。图1中DSP和X86处理器运行在BMP运行模式下即所有任务固定在特定的处理器下，ARM处理器运行在SMP运行模式下。如果改变ARM的执行任务分组则其变为BMP运行模式，即SMP与BMP运行模式可以进行相互转化。这样VMP既保证了系统的实时性，又提高了系统的整体运算效率。

多核硬件调度器的调度规则如下：每个核心总是执行未被其他核心占用的优先级最高，且在最新一次轮询中未被执行过的任务。为了保证系统的实时性，当有突发任务(任务恢复，新任务创建)时，将替换核心中运行时间最长且优先级最低的任务。为了降低系统的功耗，核心如果没有可运行任务则关闭该核心，直到有可调用的任务或任务关闭处理器核心。

2 硬件实时操作系统调度器设计

根据实时操作系统硬件调度器性质及调度规则可将调度器分为6个基本模块电路，分别为任务状态电路、分组电路、事件管理电路、任务轮询电路、任务选择电路及地址映射电路。图2是以4核处理器为例的硬件调度器示意图。

图1 任务调度示意图

图2 硬件调度器示意图

2.1 任务状态电路

任务是否可运行由任务状态决定，而任务状态则由硬件系统内核调度器中任务状态标志决定。每个任务都有一个任务状态，并由任务状态电路提供。在硬件操作系统中由于存储空间固定，因此任务的数量固定。每个任务有两种状态属性，如图3所示，属性1为任务是否存在，属性2为任务是否挂起，M、N为优先级数和同优先级任务数，组成M×N位任务编码。

图3 任务状态转换图

由这两种属性可以组合出3种状态：睡眠态任务(未使用{运行挂起})、就绪态任务(使用运行)、挂起态任务(使用挂起)。任务的属性状态标志在寄存器组中由两个寄存器保存。寄存器组的输出相当于软件操作系统里任务就绪表的标志位。每个寄存器组中有2个状态寄存器，第一个寄存器为0表示任务未载入，为1表示任务已载入。第二个寄存器为0表示任务挂起，为1表示任务运行。输入创建、删除、恢复、挂起任务编码可改变任务状态。

2.2 任务轮询电路

对于一个可同优先级轮询的硬件调度器，不仅要有任务状态这个条件，还要有一个标志，即任务轮询标志。在任务轮询电路中用寄存器组成的一维向量表示。在软件操作系统里，任务轮询基本使用循环链表。而在硬件系统中则无法使用链表，需要一种模拟循环链表的电路完成操作。图4是使用一维向量表示在最新的一轮调度中还剩下可调度的任务编码。

图4 轮询电路示意图

轮询电路规则是进行一次调度时，本次轮询输出的可用任务编码等于就绪态任务编码按位与当前一维向量。一维向量值则是上一个状态值按位与当前调度的任务编码的按位取反，且当无可用任务编码输出且有就绪任务编码输入时，将一维向量值重新置为1。

按照以上规则可以保证在一次轮询中每一个就绪态任务都会被调度并支持同优先级任意数量的长度扩展。

2.3 任务选择电路

当前调度的任务编码是本次轮询输出的可用任务编码经过任务选择电路的输出编码。任务选择电路的功能有两个，一是将输入的睡眠态任务编码进行选择输出创建任务编码，二是通过输入的次轮询所输出的可用任务编码及突发任务编码进行任务调度。无论是创建还是调度都需要对输入任务编码进行选择。选择规则总是从最低位起第一个可用任务开始选择。

为了增加系统的扩展性，加入了控制信号，表1为选择电路真值表，PRD为控制信号输入，OQ为控制信号输出，任务编码输入输出长度可随配置变化。表1所示为3编码输入选择器。

表1 选择电路真值表

当创建任务时将选择电路并联，每个选择电路的任务输入宽度为同优先级任务数，选择电路个数为优先级数，睡眠态任务编码为任务输入，要创建优先级为所有PRD端口的输入。在创建任务时只需输入要创建的优先级就可得到相应的任务输出。对于多核系统只需将输入的睡眠态任务编码去除掉，当前选择任务编码输出作为下一个核心的选择电路的任务编码输入。以此类推可完成任意数量核心的任务创建。将每一个核心的任务编码输出作为任务状态电路的创建任务编码输入。

与创建任务类似，任务调度也是通过选择电路进行调度输出，将创建任务时并联的选择电路改为串联，并将任务编码输入由睡眠态任务编码改为编码总线上从低到高的突发任务编码、本次轮询输出的可用任务编码及下次轮询输出的可用任务编码。图5所示为一个优先级的调度电路，其数量与优先级数相同。在多优先级中，将PRD与OQ串联起来形如调度控制->(0优先级)PRD、(0优先级)OQ->(1优先级)PRD、(1优先级)OQ->(2优先级)PRD等，以此类推。

图5 调度电路示意图

从图5串行链接可知，最先调度的为0优先级任务。在同优先级中最先调度突发任务，未有突发任务则调度本轮询可用任务，未有可用任务则调度次轮询可用任务，在多核调度中，可能出现本轮可调度任务数少于请求调度的核心数，这时会从次轮询中提前调度任务作为本轮询的补充。如果在次轮询可用任务中未有可用调度任务，则进行下一优先级搜索。即从优先级最高的开始调度，如果0优先级未有可调度任务，其后从1优先级开始调度，以此类推。如果所有优先级未有可用任务调度则关闭处理器内核，等待可用任务。

在多核系统中，将前一个内核的任务输入编码去掉前一个内核的当前调度编码作为本内核的任务编码输入，以此类推可完成多核任务调度电路的搭建。

2.4 任务分组电路

任务分组功能则是通过分组电路中由寄存器组成的二维向量实现，如图6所示。在任务分组向量中，由0与1标记分组且分别互斥。通过任务状态控制该行任务分组向量的输出。通过任务分组功能将任务分组信息进行保存，选择哪些分组的选择信息则是保存在选择电路中。通过选择信息将每个选择分组的一维向量分别按位与调度电路的输入，保证输入的任务都是本处理器下调度的任务，则可实现任务分组功能。

图6 任务分组电路示意图

2.5 事件管理电路

为保证系统实时性，必须对一些系统事件进行及时处理[9]。事件是所有可改变任务状态的操作，包括任务的创建、删除、挂起、恢复和改变内核可调度任务集合的操作(如改变任务分组信息和选择信息)。系统会对改变任务状态的任务通过事件管理电路通知任务选择电路进行优先调度。对所有内核进行搜索，优先切换空闲状态下的内核，其次为运行优先级最低且运行时间最长的内核，以此保障系统的实时性。

2.6 地址映射电路

在软件实时系统中切换任务需要这个任务的TCB任务控制块，以得到各种信息。而在硬件调度中任务信息存储在地址映射电路中。由于切换任务编码总线中的任务信息只有任务编码，需要将任务编码转换为任务信息，以任务编码为数据地址通过由寄存器组成的多个RAM输出任务信息，如图7所示。

在任务创建时输入任务数据和任务号，这时任务数据存入上方任务信息RAM中，与任务号对应的任务编码存入下方任务编码RAM中。任务切换时输入调度任务输出，也就是切换任务中的当前切换任务编码，输出切换任务对应的任务信息。在进行任务状态操作时，通过输入对应的任务号及相应操作的控制码，可将任务编码送入对应的任务编码总线完成操作。

(1)创建任务

处理器发送任务创建命令，输入创建任务信号，从睡眠态任务编码中选出一个任务编码，输出到任务创建编码总线上。同时输入任务数据和任务号，任务数据可以是PCB在内存中的指针，或是线程的堆栈指针，或是任务轮询时间片大小等，这时输入任务数据存入任务信息RAM中，创建任务编码存入任务编码RAM中。创建任务编码所对应的寄存器组的状态，由睡眠态变为就绪态或挂起态，这取决于在创建任务时输入的命令。在输入创建任务信号的同时完成以上步骤，在时钟上升沿输入信号，在下降沿存储数据。

(2)删除任务

处理器发送任务删除命令，输入任务号，任务号为读地址，存储器输出相应的任务编码。输入控制代码，输出到删除任务编码总线。任务状态电路将对应的任务变为睡眠态。同时删除分组电路里面的任务。在输入删除任务信号的同时完成以上步骤，在时钟上升沿输入信号，在下降沿存储数据。

图7 地址映射电路

(3)挂起与恢复任务

与删除任务一样，处理器发送挂起、恢复任务命令或外部电路发送挂起、恢复任务编码。当为处理器命令时，输入任务号，任务号为读地址，存储器输出相应的任务编码。输入控制代码，输出到相应的编码总线。如外部电路发送任务编码则直接送到相应的任务编码总线。任务状态电路将对应的任务变为对应的状态。在输入挂起、恢复任务信号的同时以上步骤同步完成，在时钟上升沿输入信号，在下降沿存储数据。

3 测试结果与分析

本文调度器电路的实现采用VHDL硬件描述语言，使用Altera公司的Quartus软件进行开发，用ModelSim进行功能仿真。

为了方便仿真及查看测试结果，将调度器配置核心数为2，优先级为2，同优先级任务数为5，分组数为2。共创建5个任务分别为1～5号任务，均为0优先级任务。分为2组，1、2号任务为0组，3、4和5号任务为1组。分别对任务调度、挂起任务、恢复任务及改变分组的功能进行了仿真测试。

如图8所示，CPU_CURTASK分别为CPU0和CPU1的调度任务的信息输出，将任务信息存储为任务号，RE_X为任务的切换信号，两个内核的可执行任务集合分别指向0组和1组，从图8可知调度器执行命令从时钟上升沿开始到下一个上升沿结束，且都是半个时钟完成调度。从调度输出可看出系统运行模式为BMP运行模式。

图8 任务调度测试

如图9所示，在200 ns输入任务挂起控制代码110，输入控制的5号任务。可见在半个时钟之后挂起任务5，且切换到任务3，在以后的任务调度中未见任务5。

图9 挂起任务测试

如图10所示，在270 ns输入任务恢复控制代码111，输入控制的5号任务。可见在半个时钟之后恢复任务5，且切换到任务5，在以后的任务调度中可见任务5。

图10 恢复任务测试

如图11所示，在450 ns输入改变分组命令，将两个内核的任务集合同时指向0、1分组。可见在任务调度时两个内核同时调度一个任务集合，运行模式改变为SMP运行模式。

图11 改变分组测试

测试结果表明基于硬件的多核调度器可以在半个时钟之后到一个时钟之内完成每一个内核发出的各种任务控制命令，与软件调度器相比极大地降低了系统任务调度的时间。

4 结论

本文使用VHDL语言设计了实时操作系统硬件多核调度器，基于FPGA完成了内核调度器的搭建。该调度器采用新的VMP运行模式，基于优先级使用抢占加轮询的方式进行任务调度，可根据系统配置进行硬件裁剪。系统测试结果表明该调度器可在一个系统时钟之内完成多核处理器发出的各种任务控制命令，实现了对异构多核处理器系统的统一调度和管理。同时调度器的硬件实现可以加快多核处理器系统任务调度的速度，降低处理器的系统开销，使处理器的时间基本用来执行用户任务，提高了处理器的利用率。