RTAI下动态集成的资源预留调度器的设计与实现

近年来基于双内核架构增强Linux操作系统实时性的RTAI(Real-Time Application Interface)在工业控制等硬实时领域得到广泛应用。RTAI通过抢占Linux的执行来保障硬实时性,Linux被抢占的时间依赖于硬实时应用的处理器要求而每次均会有较大不同,导致Linux的执行时间不可预测,从而无法保障软实时应用的服务质量。动态集成的资源预留调度器(Dynamic Integrated Resource Reserved Scheduler,DIRRS)通过增强RTAI调度器使其支持资源预留机制,在Linux实现可动态集成的、基于服务器的调度策略,不但可以保证Linux及其以上的软实时应用,即使在有硬实时任务并发时也能得到处理器资源,而且很容易通过更换不同的服务器内核模块来实现用户自定义的调度策略。     

权重队列实时调度系统的反馈控制

针对工作在不可预测环境下具有不确定性任务特征的实时调度系统的服务区分问题，利用队列理论对权重队列实时调度系统进行多变量控制建模，并结合模型预测控制方法将控制问题转化为受限多变量优化问题，进而基于标准的最小二乘求解器设计预测控制调度框架以及算法。通过调整任务类的权重因子来改变任务类的计算资源分配，以实现为调度任务类提供相对延迟时间比保证。仿真试验结果表明，所设计方法在任务到达速率和执行时间变化且不能预知的情况下，仍然能为系统提供良好的相对延迟时间比控制。     

基于LSTM的集群用户作业执行时间预测模型

为提升服务质量,数据中心需要确保在规定的截止时间前完成用户作业,因此必须根据实时的系统资源对作业进行有效的调度。提出了一种作业调度算法,根据预测的作业执行时间进行批作业调度,以最小化批作业的完成时间。作业执行时间预测模型基于长短期记忆LSTM网络,根据用户作业类型、作业量、作业需要的CPU核数和内存数量,以及作业需要的资源在系统总资源中的占比,对用户作业的执行时间进行预测。预测结果用于判断集群是否有能力按时完成用户作业,同时为合理安排各作业的执行顺序提供依据。通过实验确定了影响LSTM时间预测模型性能的各超参数取值,如迭代次数、学习率和网络层数等。实验表明,与SVR模型、ARIMA模型和BP模型相比,基于LSTM的作业执行时间预测模型的决定系数R2分别有2.97%,2.34%和5.66%的提升效果,且预测的平均误差仅为0.78%。     

面向多核处理器的实时优化技术:基于独立实时域的实时优化方法

多核处理器具有良好的性能功耗比,因此其在实时嵌入式系统中的应用是一种趋势.然而,现有的软件结构下,多核处理器的多核特性对实时性能的提高没有帮助;甚至,多核处理器核间的资源共享使影响程序执行时间的因素变得复杂,实时任务的最坏执行时间(Worst Case Execution Time,WCET)变得更为不可预测和难以控制.基于国产飞腾处理器研究了基于多核处理器的实时系统构建和实时性能优化,提出了“基于独立实时域的实时优化方法”;通过虚拟化技术把处理器分为“实时域”和“非实时域”,实时任务和非实时任务运行在不同的核心上,充分利用多核处理器各个核心,高效调度实时任务和非实时任务运行.     

基于异构Flink集群的节点优先级调度策略

Flink流处理系统默认的任务调度策略在一定程度上忽略了集群异构和节点可用资源,导致集群整体负载不均衡。研究分布式节点的实时性能和集群作业环境,根据实际作业环境的异构分布情况,设计结合异构Flink集群的节点优先级调整方法,以基于Ganglia可扩展分布式集群资源监控系统的集群信息为依据,动态调整适应当前作业环境的节点优先级指数。基于此提出Flink节点动态自适应调度策略,通过实时监测节点的异构状况,并在任务执行过程中根据实时作业环境更新节点优先级指数,为系统任务找到最佳的执行节点完成任务分配。实验结果表明,相比于Flink默认的任务调度策略,基于节点优先级调整方法的自适应调度策略在WorldCount基准测试中的运行时间约平均减少6%,可使异构Flink集群在保持集群低延迟的同时,节点资源利用率和任务执行效率更高。     

服务网格中资源可用性评估方法研究*

资源可用性的预测与评估是动态网格环境下合理资源选择和保证服务质量的前提和基础。基于相关资源和任务的历史信息,利用概率论方法对资源可用性进行了预测与评估,提出了资源离线时间、本地任务执行时间、等待队列长度、等待时间等可用性尺度,证明并给出这些尺度的分布函数。实验表明,基于相关历史信息对资源可用性进行预测方法有效,并且根据资源可用性评估及提取的相关可用性尺度来确定任务调度的候选资源,可大大减少候选资源数目,从而降低调度的时间复杂度。     

多机多任务实时系统云调度策略

采用云方法对多要实时系统任务的重要性和任务处理的适时性进行分析,实时计算被激活任务的价值及其在不同资源条件下的作业执行时间,提出一种兼顾任务价值和作业执行时间两方面因素的新的调度策略－云调度策略,有效地解决了任务优先级的判定和任务处理适时性问题,提高了系统资源利用效率、运行质量和系统整体效能。仿真证明,此策略优于现在广泛采用的固定优先级和先到先处理调度策略。     

基于可延迟调度提升实时数据对象时序一致性服务质量算法

针对保证实时数据对象时序一致性调度算法在软实时数据库系统环境下的应用问题,提出了一种基于概率统计的可延迟优化(SDS-OPT)算法。首先,分析和比较了现有算法在可调度性、服务质量(QoS)以及工作负载方面的特征与不足,指出优化现有算法的必要性;然后,利用最速下降法提升作业的执行时间筛选基准值,进而增加实时更新事务可调度的作业数量,以确保实时数据对象的时序一致性服务质量(QoS)最大化;最后,从工作负载和服务质量两个方面对所提算法和现有算法的性能进行对比分析。仿真实验结果表明,相对于已有的针对固定优先级可延迟调度算法(DS-FP)和统计性的非确定性可延迟调度算法(DS-PS),所提算法能够保证实时数据对象的时序一致性,同时降低工作负载,服务质量提升明显。     

面向流媒体应用的实时可执行概率获取方法研究

为准确获取网络实时可执行概率,从而对网络实时任务进行接纳控制,是解决当前网络尽力服务与实时任务服务质量（QoS）要求间矛盾的重要手段。面向流媒体应用,针对网络资源余量的高度不确定性,分析和实时获取了变化中的网络资源余量的概率时效图,并对今后的时效曲线进行预测,得到流媒体应用的实时可执行概率。实验比较了资源余量的概率时效图的预测值和实测值,结果较符合,为共享资源网络上执行实时任务作出了有益的探索。     

云平台下基于截止时间的自适应调度策略

针对在共享集群中进行任务调度时,无法兼顾任务的响应速度与任务完成时间的问题,提出一种基于截止时间的自适应调度算法。该算法以用户提交的截止时间为依据,根据任务的执行进度自适应地分配适当的计算资源。不同于传统调度方式里由用户提交固定资源参数,该算法在资源约束的情况下会对优先级高的任务进行抢占式调度以保证服务质量（QoS）,并在抢占过程结束后额外分配资源补偿被抢占的任务。在Spark平台进行的任务调度实验结果显示,与另一种资源协调者（YARN）框架下的调度算法相比,所提算法能严格地控制短任务的响应速度,并使长作业的任务完成时间缩短35%。     

非周期软实时系统的动态最优控制方法

运用多优先级排队系统的分析方法,研究了到达时刻和执行时间均不确定的非周期软实时系统,提出了一种针对DM调度算法的动态最优控制方法。该方法能在统计意义上确保系统的实时性,同时又兼顾系统的QoS需求和提高系统吞吐率。实例表明，该方法能提高系统的实际利用率，降低系统的截止时间错过率,是一种有效的载荷管理方法。     

基于概率的实时任务调度分析

在某些软实时系统中，为了降低系统成本，允许系统过载，并且允许过载时少量任务能错失时限；对于这样的系统，常常能设法获得其任务的执行时间所服从的概率分布。针对这样的系统，提出了基于概率的可调度分析方法，对系统的性能作出概率上的估计，在概率意义上预测系统的可行性；并提出以数据挖掘技术估算任务执行时间的分类方法，这对预测系统的性能和提高系统利用率有重要的意义。     

一种面向随机性负载的计算网格资源预留定价策略

针对传统预留机制对本地任务服务质量造成的负面影响,提出了基于预留收益与损失均衡的资源预留机制。首先,基于本地任务相关统计特性利用概率论方法,给出并证明了一段时间内本地任务执行时间之和的概率分布函数。然后,在资源提供者的效用中考虑本地任务可能带来的损失,求解出了为保障本地任务服务质量的最低资源价格。实验结果表明,提出的预留机制能有效保障本地任务的服务质量,提高资源利用率、降低任务拒绝率。     

一种基于资源预分配的虚拟机软实时调度方法

虚拟机技术作为云计算的重要技术之一,近年来得到广泛关注,但是由于虚拟机管理层的存在,导致语义鸿沟,使得实时应用程序、并发程序等在虚拟机上的运行性能受到影响。分析和研究了Xen虚拟机管理器的Credit调度算法,针对其在并发调度和软实时调度方面存在的不足,提出了改进调度算法,实现了算法的调度器原型。新的调度算法对软实时虚拟机进行Credit比例预分配,采用动态调度时间片机制,以non-work-conserving方式实现软实时任务周期调度,保障调度周期满足运行周期要求。通过区分并发和非并发软实时虚拟机,采取不同的调度策略,在满足资源利用率的基础上,确保实时任务的顺利运行。测试结果表明,该调度算法在对并发和非并发软实时任务调度上,具有良好的表现,较好满足了软实时应用调度需求。     

A non-preemptive scheduling algorithm for soft real-time systems

Real-time systems are often designed using preemptive scheduling and worst-case execution time estimates to guarantee the execution of high priority tasks. There is, however, an interest in exploring non-preemptive scheduling models for real-time systems, particularly for soft real-time multimedia applications. In this paper, we propose a new algorithm that uses multiple scheduling strategies for efficient non-preemptive scheduling of tasks. Our goal is to improve the success ratio of the well-known Earliest Deadline First (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF) is based on dynamic grouping of tasks with deadlines that are very close to each other, and using Shortest Job First (SJF) technique to schedule tasks within the group. We will present results comparing gEDF with other real-time algorithms including, EDF, Best-effort, and Guarantee, by using randomly generated tasks with varying execution times, release times, deadlines and tolerance to missing deadlines, under varying workloads. We believe that grouping tasks dynamically with similar deadlines and utilizing a secondary criteria, such as minimizing the total execution time (or other metrics such as power or resource availability) for scheduling tasks within a group, can lead to new and more efficient real-time scheduling algorithms.     

一种严格按比例派发服务的混合实时调度算法

在混合实时系统中,调度器必须既保证所有硬实时任务严格按照其时间约束在截止期内完成,又要尽可能地提高软实时任务和非实时任务的服务质量.提出了一种严格按比例派发服务器算法(RPDS),并以此为基础构建了一种层次式调度框架.RPDS将处理器时间流分成连续的小段,并在每一小段中强制为非硬实时任务分配一个时间片.实验结果表明,RPDS可以合理地为各种类型应用分配处理器时间,并且降低了实时任务的截止期错失率.     

Quality of service estimation for soft handoff region ratio and call admission control in CDMA cellular systems

In the operational stage of code division multiple access (CDMA) systems, the soft handoff region ratio (SHRR) is among the important parameters that guarantee the quality of service (QoS) and resource allocation. This paper analytically investigates the effects of the SHRR on QoS. In doing so, we simultaneously take into account the capacity increasing factor and traffic load variation. For this purpose, we propose a new traffic load estimation model using a semi-Markov chain in order to consider the call arrivals influenced by the SHRR under general resident time condition. We also present the calculation algorithm of the QoS measures such as the new call blocking probability (NBP) and forced termination probability (FTP) by applying the proposed model to the prioritized call admission control (CAC). The numerical result illustrates the effects of various soft handoff system parameters. Likewise, it shows that the value of SHRR has a significant impact of the QoS under the normal propagation conditions. Sensitivity analysis is also performed to show the effect of exponential cell resident time assumption. The proposed modeling is expected to provide a practical guide to improve the QoS of CDMA soft handoff systems.     

一种基于改进遗传算法的网格资源调度策略

首先对网格资源调度的特点、现有遗传算法的局限性进行了分析,在此基础上对遗传算法进行改进;提出一种基于改进遗传算法的网格资源调度策略（GRSS_IGA）,该算法综合考虑资源任务分配量、任务截止时间、任务等待时间及资源利用率等QoS参数;并用马尔可夫理论证明了算法的正确性;最后通过仿真对改进前后两种算法的性能进行比较,实验结果表明改进后的算法降低了时间消耗,提高了资源利用率。