机载惯导系统的EDF算法优化研究

文章针对机载惯导系统软件的通信模块中出现多任务同时争夺处理机的过载情况,提出一种改进的最早截止时间优先算法（DPEDF）,以最大化完成任务的静态优先级之和为目标,引入动态规划的方法建立调度模型,计算近似最优阔度序列,实现了导致过载发生的各个任务优先级的动态划分。通过示例展示了如何化解过载,保证实时系统正常运行。     

多功能组网雷达可变参数任务规划方法

针对任意周期雷达任务(侦查、干扰、探测等)在多功能组网雷达中的规划问题,提出了一种可变参数的任务规划方法。首先,分析雷达任务特性,建立可变参数雷达任务模型。然后,设定组网雷达中各雷达任务规划时间窗宽度和开槽宽度,使组网雷达可执行任务的周期与现有任务周期最接近。接着,针对雷达任务任意周期的特点,以任务周期变化量最小为原则对任务周期进行调整,保证多个任务在同一部雷达中不重叠,并且具有周期性。最后,利用启发式算法,以任务驻留时间的平均隶属度最大为目标完成任务规划。仿真结果与实例证明了该方法的有效性。     

孔径分割多功能雷达的任务调度研究

针对孔径分割多功能雷达实时任务调度中资源利用不充分的问题,提出了一种基于扩展域的任务自适应调度方法。方法以时间指针为对象,对该时刻的任务分析范围从当前调度间隔扩展到整个调度时间轴,从整个调度时间轴上所有满足时间指针处执行条件的任务中,选择一个优先级最高的任务,可实现任务间的紧密安排,有效减少空闲资源的浪费,使得孔径分割雷达能够在有限的资源内调度执行更多的任务。最后,将该方法与传统多任务并行调度方法进行对比仿真,仿真结果证明了该方法的有效性和优越性。     

基于价值优化的相控阵雷达任务调度算法

针对相控阵雷达时间资源分配问题,该文提出一种基于价值优化的任务调度算法。首先建立任务调度属性参数,对跟踪任务队列进行可行性分析和筛选操作,确定跟踪任务调度属性。其次,根据任务最大价值及其变化斜率,建立关于实际执行时刻的动态任务价值函数,并基于此构建任务调度的价值优化模型,对跟踪任务执行时刻进行分配,以更好满足及时性原则。最后,利用执行跟踪任务间的空闲时间片对搜索任务进行调度。仿真结果表明,该文算法有效减小了时间偏移量,提升了实现价值率。     

军用网格环境下基于优先权的Min-Min任务调度算法

军用网格环境下的资源调度与一般网格环境下的资源调度相比较，一个明显的特点就是必须考虑一些特别任务的优先级。在给出网格独立任务调度模型基础上，提出了一种基于优先权的Min—Min资源调度算法，该算法首先调度优先级高的任务，其余任务则采用Min—Min算法调度。经过分析，该算法的时间复杂度是O（n^2m），与Min—Min相比，该算法的Makespan可能略大，但可以满足军用网格环境下特殊任务优先执行的需求。     

Online task interleaving scheduling for the digital array radar

Aiming at the task scheduling problem in the DAR (digital array radar), an online task interleaving scheduling algorithm is proposed. The full structure of the DAR task is explicitly considered in a way that the waiting duration can be utilized to transmit or receive subtasks, which is called the task interleaving, as well as the receiving durations of different tasks can be overlapped. The algorithm decomposes the task interleaving analysis into the time resource constraint analysis and the energy resource constraint analysis, and online schedules all kinds of tasks that can be interleaved. Thereby the waiting durations and receiving durations can be fully utilized. The simulation results demonstrate that the proposed algorithm improves the successfully scheduling ratio by 73%, the high value ratio by 86% and the time utilization ratio by 55% compared with the HPEDF (highest priority and earliest deadline first) algorithm.     

改进的Min-Min网格任务调度算法

在网格环境中,如何对任务进行高效调度是当前研究的热点问题。目前Min—Min调度算法是一个简单、快速、有效的算法。但它很难满足网格任务对服务质量的要求。在独立型的任务调度模型的基础上,提出了一种基于权值的改进Min—Min调度算法。改进后的算法通过量化网格任务的优先级和等待时间,解决了原有算法存在的高质量任务和大任务等待时间过长的问题。仿真实验结果表明,改进后的算法满足了网格任务对优先级和等待时间的服务质量要求．是一种网格环境下有效的任务调度算法。     

A Modelling of Context-Aware Elderly Healthcare Eco-System-(CA-EHS) Using Signal Analysis and Machine Learning Approach

In cloud computing, more often times cloud assets are underutilized because of poor allocation of task in virtual machine (VM). There exist inconsistent factors affecting the scheduling tasks to VMs. In this paper, an effective scheduling with multi-objective VM selection in cloud data centers is proposed. The proposed multi-objective VM selection and optimized scheduling is described as follows. Initially the input tasks are gathered in a task queue and tasks computational time and trust parameters are measured in the task manager. Then the tasks are prioritized based on the computed measures. Finally, the tasks are scheduled to the VMs in host manager. Here, multi-objectives are considered for VM selection. The objectives such as power usage, load volume, and resource wastage are evaluated for the VMs and the entropy is calculated for the measured objectives and based on the entropy value krill herd optimization algorithm prioritized tasks are scheduled to the VMs. The experimental results prove that the proposed entropy based krill herd optimization scheduling outperforms the existing general krill herd optimization, cuckoo search optimization, cloud list scheduling, minimum completion cloud, cloud task partitioning scheduling and round robin techniques.

     

硬实时系统中基于任务同步及节能的动态调度算法

提出基于任务同步及节能的动态实时调度算法HDSA(hybrid dynamic scheduling algorithm),以有效地解决任务同步及节能的难题.HDSA 结合RM及EDF算法,在满足任务实时可调度性及任务同步的限制条件下,采用DVFS节省能耗.HDSA包含静态算法及动态算法两部分.静态算法在静态条件下,求出任务的静态速度.动态调度算法在实际运行中,固定临界区的运行速度,并充分回收、利用任务运行时的空闲执行时间,调节处理器的速度,以有效降低能耗并满足实时可调度性.同时避免高优先权任务被阻塞时,临界区继承高优先权任务的速度时所造成的处理器电压开关的频繁切换,因而能有效地降低实时任务调度的成本.实验测试表明,HDSA在调度性能上明显优于目前所知的有效算法.     

嵌入式RTOS中任务优先级反转问题研究

针对嵌入式实时系统任务调度策略的特点，任务在运行的时候可能被更高优先级的任务中断。分析了嵌入式RTOS中的最高就绪任务的查找算法，指出该调度算法存在的不同优先级的反转问题，并且针对这一问题进行研究，给出了相应的优先级继承方案。较好地解决了RTOS中任务调度中的优先级的反转问题。     

A multiprocessor-oriented power-conscious scheduling algorithm for periodic tasks

With the rapid development of advanced technology in VLSI circuit designs, many processors could provide dynamic voltage scaling (DVS) to save power consumption when the supply voltage is allowed to be lower. In this paper, we propose a multiprocessor-oriented power-conscious scheduling algorithm for the real-time periodic tasks with task migration constrained scheme. We classify periodic tasks into fixed tasks and migration tasks, and limit the number of migration tasks and the number of destination processors which execute migration tasks. The proposed algorithm is made up of two steps. Firstly, choosing a processor to sort all of the periodic tasks in a non-increasing order according to task utilization, afterwards, allocating them to other processors. Secondly, scheduling the migration tasks with a virtual execution windows policy, and then scheduling the fixed tasks with EDF algorithm. The experiment results show that compared with arbitrary task migration policy and no task migration allowed policy, the power consumption in multiprocessor real-time periodic tasks scheduling is lowered significantly with the proposed algorithm.     

Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design

Hardware/software (HW/SW) partitioning and scheduling are the crucial steps during HW/SW co-design. It has been shown that they are classical combinatorial optimization problems. Due to the possible sequential or concurrent execution of the tasks, HW/SW partitioning and scheduling has become more difficult to solve optimally. In this paper more efficient heuristic algorithms are proposed for the HW/SW partitioning and scheduling. The proposed algorithm partitions a task graph by iteratively moving the task with highest benefit-to-area ratio in higher priority. The benefit-to-area ratio is updated in each iteration step to cater for the task concurrence. The proposed algorithm for task scheduling executes the task lying in hardware-only critical path in higher priority to enhance the task forecast. A large body of experimental results conclusively shows that the proposed heuristic algorithm for partitioning is superior to the latest efficient combinatorial algorithm (Tabu search) cited in this paper. Moreover, the Tabu search for partitioning has been further improved by utilizing the proposed heuristic solution as its initial solution. In addition, the proposed scheduling algorithm obtains the improvements over the most widely used approaches by up to 10% without large increase in running time. This work was presented in part at 2006 IEEE International Conference on Field Programmable Technology (ICFPT).     

RM算法的运行时开销研究与算法改进

RM算法是经典的固定优先级实时调度算法.而在嵌入式实时系统中,系统的工作负荷往往是由很多频率快、执行时间较短的任务组成.因此,直接使用RM算法进行任务调度会由于实时操作系统中任务的上下文切换开销而导致嵌入式系统资源利用率的降低.分析了基于RM算法调度的任务之间的抢占关系,并建立了以任务属性为参数的上下文切换开销模型.在该模型的基础上,通过优化任务的释放时间来降低RM算法导致的系统运行时任务切换开销.最后的实验结果验证了该策略的有效性.     

基于逆序层优先的柔性综合调度算法

针对以往柔性综合调度算法均考虑正向调度，导致需要考虑目标工序的多紧前工序约束条件，难以合理安排相关工序进而影响产品完工时间的问题，该文提出一种基于逆序层优先的柔性综合调度算法。首先，提出逆序层优先策略，将各工序分配至逆序层待调度工序集；其次，提出动态拟长路径策略，确定各逆序层待调度工序集中工序的调度顺序；然后，分别提出设备选择策略和设备抢占策略以确定目标工序的加工设备以及加工时间；最后，提出基于完工时间翻转的调度方案转换策略，将逆序调度方案转换为正序调度方案。实例表明，和已有主流算法相比，该算法在不提高算法复杂度的前提下能够缩短产品完工时间。     

基于遗传算法的片上多处理器任务调度策略研究

针对在片上多处理器上任务调度的特征,提出了一种基于立体编码的遗传算法。采用适合片上多处理器结构的三维立体编码,使计算节点之间的距离得到了描述,结合提出的个体适应度函数计算公式,使通信代价较小的调度策略优先得到选择,从而通过减少因结点间距离产生的通信开销降低了总的任务完成时间。此外,对算法结构、遗传算子进行了改进提出了内部二维交叉算子,加速了算法的收敛。仿真实验结果表明立体编码的遗传算法能够有效地对任务进行分配和调度,较之传统遗传算法具有较好的性能。     

云计算环境下任务调度算法的研究

在云计算环境中存在庞大的任务数,为了能更加高效地完成任务请求,如何进行有效地任务调度是云计算环境下实现按需分配资源的关键。针对调度问题提出了一种基于蚁群优化的任务调度算法,该算法能适应云计算环境下的动态特性,且集成了蚁群算法在处理NP-Hard问题时的优点。该算法旨在减少任务调度完成时间。通过在CloudSim平台进行仿真实验,实验结果表明,改进后的算法能减少任务平均完成时间、并能在云计算环境下有效提高调度效率。     

针对弱硬实时系统的DRM调度算法

本文在定义支持多级QoS的弱硬实时系统周期任务模型的基础上,提出基于RM调度策略的弱硬实时调度算法DRM,它具备可调度判定不等式,不限定任务的QoS参数模式,并通过在调度的过程中动态调整任务的优先级来反映其紧迫程度.在系统过载时,DRM调度算法可以采用QoS退化机制,在保证紧要任务以及其所要求的最低QoS执行的同时,适当降低某些任务的服务等级,使得更多的任务可以有效运行,以此来提高系统对负载的适应性.最后,本文通过仿真实验,验证了DRM以及QoS退化机制的有效性.     

An Optimized Collaborative Scheduling Algorithm for Prioritized Tasks with Shared Resources in Mobile-Edge and Cloud Computing Systems

Mobile edge computing (MEC) is a promising technology that has the potential to meet the latency requirements of next-generation mobile networks. Since MEC servers have limited resources, an orchestrator utilizes a scheduling algorithm to decide where and when each task should execute so that the quality of service (QoS) of each task is achieved. The scheduling algorithm should use the least possible resources required to meet the service demands. In this paper, we develop a two-level cooperative scheduling algorithm with a centralized orchestrator layer. The first scheduling level is used to schedule tasks locally on MEC servers. In contrast, the second level resides at the orchestrator and assigns tasks to a neighboring base station or the cloud. The tasks serve in accordance with their priority, which is determined by the latency and required throughput. We also present a resource optimization algorithm for determining resource distribution in the system in order to ensure satisfactory service availability at the minimum cost. The resource optimization algorithm contains two variations that can be employed depending on the traffic model. One variant is used when the traffic is uniformly distributed, and the other is used when the traffic load is unbalanced among base stations. Numerical results show that the cooperative model of task scheduling outperforms the non-cooperative model. Furthermore, the results show that the suggested scheduling algorithm performs better than other well-known scheduling algorithms, such as shortest job first scheduling and earliest deadline first scheduling.

     

面向密集多波束组网的卫星通信系统资源调度算法

研究了高动态、资源受限条件下的卫星通信系统资源调度问题。以时间窗口、卫星功耗、信道数量、用户优先级以及任务突发性为约束,建立了卫星资源调度模型。考虑到传统的蚁群优化算法存在初期搜索速度过慢、局部搜索能力较弱以及易陷入局部最优等缺点,提出了以初始解集构造、额外信息素沉积为核心的改进蚁群优化算法,来求解资源调度问题。仿真实验评估了所提资源调度算法在完成任务的数量、优先级和调度完成时间方面的性能。实验结果表明,所提算法具有较快的收敛速度,且与同类型优化算法相比具有更高的调度效率,适用于调度面向密集多波束组网需求的卫星通信系统资源。     

树形网格自适应调度模型研究

提出一种基于树形计算网格的自适应调度模型,实现对小粒度独立任务和用户大作业的自适应最优调度.通过对网格环境的实时检测,给出了基于节点负载状况、节点任务执行时间和任务特性的自适应调度算法.实验证明该任务调度模型在负载平衡和容错方面具有良好的性能.