嵌入式多核操作系统负载均衡模型研究

何翔

摘要：近年来嵌入式系统大量采用多核架构处理器，然而传统的嵌人式软件架构并没有充分考虑并行计算的负载均衡，导致多核处理器性能无法充分发挥，本文提出了一种针对嵌入式领域多核应用特点的嵌入式多核操作系统负载均衡研究框架，以便进一步研究。

关键词：多核；负载均衡；模型；嵌入式

1引言

并行模型的使用是提高计算机系统性能的有效方法，通常我们采用加速系数来衡量并行系统性能提升幅度，其定义为：加速系数S（p）=串行模型执行时间/使用具有p个执行节点所需执行时间。其中加速系数的取值范围是O1说明并行模型提升了系统性能。影响加速系数的因素很多，其中系统负载均衡是关键因素。

负载均衡（load balancing）是一种计算机技术，用来解决多节点负载分配问题，实现系统的资源优化使用、吞吐率最大化、响应时间最小化的目的。给用户提供优质，可靠，稳定的服务。计算机系统的负载均衡模型由节点模型、负载模型以及均衡模型组成。

2多核系统负载均衡模型

多核系统指依托片上多处理芯片（CMP）而构成的计算机系统，可分为多核硬件、系统软件以及应用软件三部分。负载均衡是系统软件向用户提供的服务，确保系统内各CPU承担的负载大致相近的服务，保证系统不出现某些CPU的负载特别重而另一些CPU却处于空闲状态。多核系统中的CPU是并行系统的节点，节点上执行的任务是被均衡的负载，假设某多核系统中有m个CPU和n个任务，P代表CPU集合，则P={p1，p2，……pm}，其中pi代表系统内的某个CPU。T代表系统内所有任务执行体的集合，则T={t1，t2，……tn}，其中ti代表系统内某个任务。系统运行中的某个时刻t具有确定的处理器集合Pt以及任务集合Tt。当多核系统采用f（）为负载均衡算法，在t时刻任务和处理器之间的映射关系为Mt，则Mt=f（Pt，Tt），也可表示为：Mt=f（P，T，t）。多核系统的负载均衡模型：多核节点P、系统负载T以及均衡算法f（）三个方面。负载均衡算法f（）以节点模型P、负载模型T以及时间t为输入可计算出系统在t时刻的负载均衡映射关系Mt。

3节点模型

经过多年的发展，多核处理器已经出现了多个发展方向和分类，从负载均衡角度可划分为：同构、异构两种。

CPU节点完全相同被称为同构多核，也成为SMP处理器。同构处理器的节点集合P={p1，p2，……pm}中个元素是完全对等关系，所以各节点只包含自身的编号信息即pi={i}。为了进一步挖掘处理器性能，提高CPU计算部件的利用率，芯片设计者通过扩充CPU取指部件实现这一目的，这种技术被称为SMT（simultaneous multi-thread）。以外部视角观察，SMT技术提供了一个物理CPU虚拟两个逻辑CPU的能力。由于同物理CPU的两个虚拟CPU共用一个计算部件，共用一套私有缓存，导致两个逻辑CPU之间存在性能影响，而这种影响关系在传统SMP硬件中是不存在的。在支持SMT技术的同构多核节点集合中，节点pi={i，（Pj，Pk，……，P1）}其中，i为本CPU节点编号，（i，k，……，1）表示本节点所在物理CPU中所有的逻辑CPU。

此之节点模型中还可以加入CPU节点的缓存信息，均衡算法f（）运算中可以优先选择缓存中已经预载任务数据的CPU，可以减少任务读取内存时间，继而提高本次任务执行的效率。缓存预载的引入使节点模型复杂，导致均衡算法设计困难，并且很难达到最优算法，鉴于此预载信息简化为CPU节点最近运行任务信息，即有节点模型中：pi={i，ti}，其中i为本CPU节点编号，tj为最近运行任务信息。

CPU节点不完全相同的被称为异构多核。异构多核处理器的产生来自于应用需求，与同构多核处理器系统相比，异构多核处理器系统的优势是通過集成不同特点的计算内核来优化处理器内部结构，实现处理器性能组合的最佳化，同时可以有效地降低系统的功耗。

在嵌入式领域常用的多核处理器还包括GPU、DSP等，利用SOC技术将GPU或DSP与CPU封装成为一个芯片，形成多种复杂结构的多核处理器，这类处理器的负载均衡节点模型可以通过上述节点模型的相互融合形成。

4负载模型

多核系统中的负载可分为系统负载以及用户负载，系统负载，用户负载的吞吐量是负载均衡效果的关键指标。

1）负载

在使用操作系统的多核系统中，用户负载被称为任务，用户或操作系统将任务拆分为线程、进程、分区，并分配到各处理器核上执行。

2）模型

从负载封装形式的角度，可以将系统内负载分为系统开销和任务负载，其中任务负载包括用户任务和内核任务。多核系统处于满负荷运行状态时，用户负载与系统开销存在多个数量级的差别，建模时忽略系统开销。即有任务集合T={t1，t2，……tn}中，其中ti代表用户任务或者内核任务。ti包括负载均衡相关的任务信息。ti中至少包含任务ID、任务状态，采用优先级调度时还需要引入任务优先级信息，即ti={ID、state、priority}。

例如为满足特定的需求，负载模型还需引入特定信息。用户希望某些任务能够固定在某个CPU中执行，则需引入任务亲和性信息，即负载模型中ti={ID、state、prioriIv、affinityl，affinity指向任务所绑定的CPU，负载均衡算法f（）即可根据affinity分配任务到目标核。

5均衡算法

均衡算法f（）根据节点模型P以及负载模型T的动态变化形成动态的节点、任务之间的映射关系M，M在时刻t的映射关系为Mt。多核负载算法可分为架构和策略，均衡架构决定均衡算法的基本特征，均衡策略在架构的基础上实现多核的负载均衡。

5.1负载均衡架构

多核系统负载均衡架构有主从式架构和分布式架构两种。

主从式架构：多核系统的主从式负载均衡架构是指系统内所有CPU节点具有统一的负载均衡策略，为CPU节点分配负载。负载均衡策略可以固定在一个CPU上执行，也可以运行时动态执行在某个CPU上，但同一时刻只能有一个CPU节点执行负载均衡策略。在多核系统运行中执行负载均衡策略的CPU与其他CPU是主从关系。

分布式架构：多核系统的分布式负载均衡架构是指系统内的CPU节点具有独立的负载均衡策略。分布式负载均衡架构中，各CPU节点可并行处理负载均衡事物，可配置不同的负载均衡策略。CPU节点间相互对等，独立处理并维护与自己相关的负载，节点间通过通用协议实现负载迁移。

5.2负载均衡策略

多核处理器中，要很好地发挥出多个CPU的性能的话，必须保证负载能够均匀分配到各个CPU上。以负载均衡架构为基础，负载均衡策略根据节点集合P以及负载集合T将任务分配到CPU节点上。

在工程应用中存在许多不能由静态负载均衡解决的问题，比如系统中存在一个循环负责任务的创建消亡，循环的次数是由外部输入的，事先并不知道循环的次数，此时采用静态负载均衡划分策略就很难实现负载均衡。而采用动态负载可获得理想的负载均衡效果，程序的运行过程中根据均衡策略动态分配任务。

6结束语

嵌入式系统具有硬件多样化的特点，嵌入式多核计算机系统的负载均衡方法和策略的制定依赖于硬件以及应用程序特性，不存统一的解决方案。但是无论哪种架构都可以基于本文提出的P、T、F（）模型分析，并最终选择适合的解决方案。