共查询到18条相似文献,搜索用时 218 毫秒
1.
2.
3.
4.
针对无线传感器网络的特点,分析了无线传感器网络对于任务调度的特殊需求,提出了一种基于反馈控制的动态集成调度算法。该算法将简单反馈控制与任务准入/回归控制、可达/夭折等策略相结合,设计了新的动态调度框架。该框架适用于对任务的多种特征参数的综合。最后从截止期错失率、对关键任务的优先执行能力和CPU有效利用率三个方面分析了算法的性能。实验结果表明,该算法在无线传感器网络环境下与最早截止期优先和固定优先级算法相比具有更好的性能。 相似文献
5.
6.
7.
基于最早截止期优先调度的实时系统,针对有新任务插入(与/或)现行任务加速但系统带宽不足的问题,提出一种最晚截止期优先(LDF)算法,用于系统在运行时选择现行任务转让带宽。采用从最晚作业截止期任务开始判断的方法,经过尽可能少的比较次数,找到合适的受压任务,平滑地完成带宽转让。算法需要的最多比较次数为2n。仿真结果表明,该算法在大多情况下只需要比较1~2次即可完成压缩任务。 相似文献
8.
现代导航与通信等实时系统经常面临着复杂的实时数字信号处理及信息交互需求,处理器处于高利用率状态.对于此类高利用率实时系统,传统的时间冗余容错通常会引发多个任务连续错失截止期的灾难性后果.针对高利用率情况,提出一种截止期错失率可预测的容错调度方法,截止期错失次数不大于出现错误的次数,消除了多个任务截止期连续错失的多米诺效应.进一步地在该方法中融合时间冗余方法的优点,提出了求解检测点上界位置的离线快速算法,有效地降低了截止期错失率.仿真实验表明,与目前已知的同类方法相比,该方法具有更低的截止期错失率. 相似文献
9.
提出了一种基于优先级表设计的调度算法.将任务的相对截止期和空闲时间这两个特征参数结合起来,综合设计任务的优先级表,使得截止期越早或空闲时间越短,任务的优先级越高,而且任务的优先级由相对截止期和空闲时间惟一确定.对于任意一个任务,可通过对设计的优先级表进行二元多点插值获得相应任务的惟一优先级.与传统的EDF和LSF算法进行仿真比较,仿真结果表明,通过优先级表设计方法来确定任务的优先级,提高了任务调度的成功率,降低了任务截止期的错失率.该方法可应用于实时系统中实时任务的动态调度中. 相似文献
10.
基于综合优先级的并行测试调度算法设计及实现 总被引:1,自引:0,他引:1
根据并行测试实际运行环境对多测试调度策略效率的要求,借鉴实时系统调度算法研究的相关成果,提出基于综合优先级的并行测试调度算法;算法结合并行测试,尤其是导弹测试特点,综合考虑测试任务的相对截止期和空闲时间两个特征参数,讨论了测试任务综合优先级的设计方法,给出了算法实现,并对算法的性能进行了分析;该算法无须预先确定测试任务参数的典型值,可以弥补TestStand的局限性. 相似文献
11.
提出一种面向异构云计算环境的截止时间约束的MapReduce作业调度方法。使用加权偶图建模MapReduce作业调度问题,将Map任务及Reduce任务与资源槽分为2个节点集合,连接2个节点集合的边的权重为任务在资源槽上的执行时间。进而,使用整数线性规划求解最小加权偶图匹配,从而得到任务到资源槽的调度方案。本文考虑了云计算环境下异构节点任务处理时间的差异性,在线动态评估和调整任务的截止时间,从而提升了MapReduce作业处理的性能。实验结果表明,所提出的方法缩短了作业数据访问的时间,最小化了截止时间冲突的作业数量。 相似文献
12.
13.
A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling 总被引:1,自引:0,他引:1
Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling. 相似文献
14.
讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliest deadline value)与VED(value earliest deadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliest deadline first)算法与HVF(highest value first)算法都有很大的性能改进. 相似文献
15.
To provide timely results for big data analytics, it is crucial to satisfy deadline requirements for MapReduce jobs in today’s production environments. Much effort has been devoted to the problem of meeting deadlines, and typically there exist two kinds of solutions. The first is to allocate appropriate resources to complete the entire job before the specified time limit, where missed deadlines result because of tight deadline constraints or lack of resources; the second is to run a pre-constructed sample based on deadline constraints, which can satisfy the time requirement but fail to maximize the volumes of processed data. In this paper, we propose a deadline-oriented task scheduling approach, named ‘Dart’, to address the above problem. Given a specified deadline and restricted resources, Dart uses an iterative estimation method, which is based on both historical data and job running status to precisely estimate the real-time job completion time. Based on the estimated time, Dart uses an approach–revise algorithm to make dynamic scheduling decisions for meeting deadlines while maximizing the amount of processed data and mitigating stragglers. Dart also efficiently handles task failures and data skew, protecting its performance from being harmed. We have validated our approach using workloads from OpenCloud and Facebook on a cluster of 64 virtual machines. The results show that Dart can not only effectively meet the deadline but also process near-maximum volumes of data even with tight deadlines and limited resources. 相似文献
16.
17.
An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules 下载免费PDF全文
Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline. 相似文献
18.
针对平均分区的EDF算法在CAN总线中的应用出现的问题,提出了一种改进的基于指数分区的EDF算法;并通过引入量化误差的概念,推导证明当CAN网络中各节点相对截至期分布时间过大时,平均分区的EDF算法会导致CAN总线中信息传输任务可调度性的下降,而基于指数分区的EDF算法保证了信息传输任务的实时性,仿真试验验证了算法的有效性。 相似文献