基于Petri网的分布式实时嵌入式系统调度的建模

提出了一种基于资源的时间Petri网模型,以便建模分布式实时嵌入式系统中的静态调度,分析系统性能。该模型将处理器资源和通信资源,以及相应的优先级附着到变迁上,从而建模以下的分布式实时嵌入式系统：在单处理器上采用基于固定优先级的抢先式调度,处理器之间的通信采用基于固定优先级的不可抢先式调度。最后分析了该模型的语义、性质以及状态类图的构造方法。     

EPTS:一种实时动态电压调整的抢占阈值调度器

低功耗目前已成为嵌入式实时系统设计中非常重要的性能需求。动态电压调度DVS机制通过动态调整处理器电压进而有效降低系统功耗,正在逐渐得到广泛应用。抢占阈值调度策略实现双优先级系统,每个任务具有两个优先级,任务优先级被用于任务之间竞争处理器,而抢占阈值作为任务开始运行后实际使用的优先级,从而减少现场切换次数,降低系统功耗,同时也提高整个任务集合的可调度性。本文提出一种在线节能调度算法EPTS,拓展抢占阈值调度模型,在任务执行过程中动态调节处理器电压,力求在保证任务集合可调度性的前提下尽可能减少系统功耗,提高系统性能。而后在AMDAthlon4处理器和RT-Linux平台上实现了EPTS调度器,实验证明对于实际任务集合能够有效节能,提高了处理器的利用率,改善了RT-Linux的实时性能。     

高性能嵌入式处理器技术

介绍面向分布式集群计算机的高性能嵌入式处理器产业链,分析该产业链中CPU核提供商、处理器芯片开发商、系统软件提供商、嵌入式计算机制造商等各个环节的技术特点,并在高性能嵌入式处理器开发上做了有益的探索。提出要积极与系统软件、嵌入式计算机制造商协作,充分发挥软硬件协同设计能力,以开发出面向分布式集群计算机的高性能嵌入式处理器。进一步指出多核设计与高速总线电路是高性能嵌入式处理器发展的未来之路。     

基于组合优先级的自适应实时调度算法研究

在嵌入式实时操作系统中,由单个特征参数作为实时任务优先级的调度依据,并不能较好地描述系统中任务的关键性和紧迫性.提出一种基于组合优先级的自适应实时调度算法(SREDF),综合任务的截止期和CPU运行期设计任务的优先级,使截止期越早且CPU运行期越短的任务拥有最高优先级.处理器能有效地调度相同截止期的实时任务,并提前分析和预测任务能否完成.实验表明,该算法降低了任务调度的截止期错失率(MDP),并提高了任务调度的速度和效率.     

分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。     

嵌入式实时数据库ARTs-EDB事务调度实现技术

着重讨论了嵌入式实时数据库系统ARTs-EDB中事务调度实现技术。给出了ARTs-EDB中事务的执行模型、状态及状态变迁；设计了一个考虑事务类型和截止期的多层动态可调整优先级分派方法；给出了一个优先级驱动可抢占的实时事务调度策略，以保证更多事务满足截止期要求。     

虚系统防火墙中处理器资源分配方案

为了有效地解决虚系统防火墙中处理器资源分配问题,提出一个基于阈值触发的PQ与WRR队列结合的处理器资源分配方案.为每个虚系统设置一个软件队列,通过对各虚系统的软件队列调度来实现处理器资源在各虚系统中的按需分配.软件队列之间采用WRR算法实现了高效率的基于权重的调度,硬件队列和软件队列之间采用了动态优先级的调度算法,设置调度触发阁值,降低了调度方案引入的性能损失.测试数据表明,该方案引入的性能损失很低,且处理器资源在各虚系统中得到了按需调度.     

静态实时中间件的优先级映射问题

使用截止期单调(DM)调度算法和分布式优先级冲顶资源访问控制协议(DPCP)的实时CORBA系统中,当节点的本地优先级个数不足时,必须将多个全局优先级映射成一个本地优先级.这需要：①判定映射后任务可调度性的充分必要条件;②减少时间复杂度的映射算法.为此,推导出判定条件,确定了DGPM映射算法.该算法在保证系统可调度的前提下分配任务,或者证明映射后系统不可调度.证明了DGPM算法能调度其他直序列优先级映射算法可调度的任务和GCS集合.判定条件和算法在实际项目中得到了应用.     

Hades高可信架构中固定延迟分区实时调度

为了增强不同安全等级的复杂嵌入式安全关键系统的高可信能力,Hades架构以"时空隔离"思想和分区机制为基础,各分区分时共享系统物理资源.针对Hades中分区的实时调度问题,提出一种固定延迟分区调度模型,并采用优先级位图算法设计了分区级和任务级两级调度机制;为了保障分区中所有实时任务的可调度性,对分区中任务组采用单调速率调度和最早截止时间优先2种调度策略,并分别给出任务可调度条件.最后,通过仿真实验进一步验证了该调度模型的有效性.     

一种优先级反转抑制的外设管理模型

已有优先级反转抑制方法的通用性较差,优先级天花板值难于选取.为此,提出一种改进的优先级反转抑制模型.分析现有解决优先级反转方法存在的缺陷,通过为各种稀缺资源单独建立服务队列,将其排除在优先级调度队列的排队模型之外,从而在单处理核的嵌入式系统中形成多服务员处理模型,以降低优先级反转的发生概率.仿真结果表明,该模型的优先级反转概率约为1‰.     

Dynamic task scheduling using online optimization

Algorithms for scheduling independent tasks on to the processors of a multiprocessor system must trade-off processor load balance, memory locality, and scheduling overhead. Most existing algorithms, however, do not adequately balance these conflicting factors. This paper introduces the self-adjusting dynamic scheduling (SADS) class of algorithms that use a unified cost model to explicitly account for these factors at runtime. A dedicated processor performs scheduling in phases by maintaining a tree of partial schedules and incrementally assigning tasks to the least-cost schedule. A scheduling phase terminates whenever any processor becomes idle, at which time partial schedules are distributed to the processors. An extension of the basic SADS algorithm, called DBSADS, controls the scheduling overhead by giving higher priority to partial schedules with more task-to-processor assignments. These algorithms are compared to two distributed scheduling algorithms within a database application on an Intel Paragon distributed memory multiprocessor system.     

基于PTIDES执行策略的调度算法

分析现有PTIDES执行策略调度算法,综合考虑事件的截止期和执行时间,改进传统最小空闲时间优先算法,将空闲时间作为事件调度优先权,提出零空闲时间优先PTIDES调度算法——ZSFPTIDES。实例分析表明,ZSFPTIDES调度算法能避免事件在处理过程中因得不到及时处理而夭折的现象,减小事件的抢占切换率,优化分布实时嵌入式系统的调度性能。     

容错实时任务调度的DSPN建模与分析

复杂系统的形式化描述对新系统的设计以及现有系统的改进与评价都具有十分重要的作用;针对处理机系统容错实时混合任务调度,提出采用确定与随机Petri网进行建模与性能分析;首先,根据任务执行的优先级、周期性、容错性和实时性,将任务分为四类;然后,采用DSPN对任务调度执行过程,不同优先级任务抢占式调度,处理机故障及故障恢复过程进行建模,由此构成处理机系统容错实时任务调度过程的DSPN模型;最后,仿真实验结果表明,在负载相同情况下,处理机利用率基本相同,且具有容错的实时任务调度算法可以有效地降低任务错失率;容错实时任务调度DSPN模型可以为复杂任务调度系统的Petri网建模与分析奠定了基础,并为实际工程应用提供了理论指导。     

一种基于强化学习的嵌入式系统抗拒绝服务攻击的缓存调度方案

在多核嵌入式操作系统中,中央处理器对共享最后一级缓存(Last Level Cache,LLC)的资源调度决定了各用户进程的指令周期数(Instructions Per Cycle,IPC),以及对拒绝服务(Denial-of-Service,DoS)攻击的鲁棒性。但是,现有缓存调度方案依赖于具体的LLC调度模型和DoS攻击模型,使中央处理器难以在不同调度环境中的每个调度周期及时获得用户进程的运行信息。因此,文中提出一种基于强化学习的嵌入式系统LLC调度技术,以抵御拒绝服务攻击。该技术根据用户进程的LLC占用起始位置和终止位置,结合反馈的指令周期数、载入未命中率和存储未命中率等信息,优化LLC的占用位置和占用空间。在动态LLC调度环境下,中央处理器不需要预知DoS攻击模型,即可提高指令周期数并同时降低恶意进程的DoS攻击成功率。在多租户虚拟机共同参与的多核嵌入式操作系统中的仿真结果表明,所提技术可以显著提高指令周期数并降低DoS攻击的成功率。     

面向分布式实时系统的安全驱动调度算法研究

针对现有实时调度算法无法适应动态安全需求的问题,构建了一种安全驱动调度模型,该模型从系统安全级别、系统安全服务和任务安全策略三个方面描述了实时系统的动态安全需求,并设计了一种基于安全驱动的实时任务调度器框架。以该模型和框架为基础,提出了一种安全驱动调度算法(Security Driven Scheduling Algorithm,SDSA)。从全局角度对新到达任务进行可调度性检查,并将可调度任务分配到合适的处理机上运行。按照系统安全级别来动态调整已分配到各处理机上实时任务的安全策略,使其达到安全性和可调度性的最优平衡。采用优先级抢占式策略对各实时任务进行调度。仿真结果表明,SDSA算法与其他同类算法相比,在系统动态安全需求的适应性、关键任务的可调度性以及安全防危能力等方面具有较好的表现。     

基于模拟退火算法的改进主/副版本调度算法

针对异构分布式系统中面向任务优先级约束的调度问题,提出一种基于模拟退火算法的改进主/副版本调度算法SAPB。任务模型以有向无环图DAG表示,该算法共计调度主、副2个版本的任务。在任务优先级排序阶段,采取HEFT的任务排序方法,避免了eFRD等主/副版本调度算法中任务模型描述的局限性问题;在任务处理器分配阶段,采取模拟退火算法搜索满足截止时限条件下具有更高可靠性的调度结果,并且采取多一重备份策略以解决处理器数量相对较少时任务优先级约束带来的副版本调度易失败问题。最后,通过随机生成的DAG图进行仿真实验,结果表明,相比eFRD等算法SAPB具有更优的副版本可调度性和更高的系统可靠性。     

嵌入式并行系统中基于任务优化的调度算法

在嵌入式并行计算系统中,任务调度是决定系统性能的关键。多任务调度中,启发式调度法是一种设计简单且性能良好的调度方法。目前的调度算法大多是基于任务复制的,没有充分考虑前驱任务与其后继任务间的相关性。该文提出了一种基于相关任务优化(DTO)的调度算法,通过分析已用处理机的负载和空闲时间,尽量减少系统的调度长度和处理机数目。算法分析结果表明,DTO算法在性能上优于其他算法,对嵌入式并行计算系统中的多任务调度是一个较好的选择。     

System level fixed priority energy management algorithm for embedded real time application

Dynamic power management (DPM) and dynamic voltage scaling (DVS) are crucial techniques to reduce the energy consumption in embedded real-time systems. Many previous studies have focused on the energy consumption of the processor or I/O devices. In this paper, we focus on the problem of energy management integrating DVS and DPM techniques for periodic embedded real-time applications with rate monotonic (RM) policy and present a system level fixed priority energy-efficient scheduling (SLFPEES) algorithm. The SLFPEES algorithm consists of I/O device scheduling and job scheduling. I/O device scheduling is based on the dynamic power management with rate monotonic (DPM-RM) policy which puts devices into the sleep state when the idle interval is larger than devices break even time. Job scheduling is based on the RM policy and uses stack resource protocol (SRP) to guarantee exclusive access to the shared resources. For energy efficiency, the SLFPEES algorithm schedules the task with a lower speed and a higher speed. The experimental result shows that the SLFPEES algorithm can yield significantly energy savings with respect to the existing techniques.