共查询到18条相似文献,搜索用时 359 毫秒
1.
不可抢占式EDF调度算法的可调度性分析 总被引:4,自引:1,他引:4
沈卓炜 《计算机工程与应用》2006,42(9):10-12,29
现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。 相似文献
2.
在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率. 相似文献
3.
4.
单调速率及其扩展算法的可调度性判定 总被引:34,自引:6,他引:28
任务可调度性判定是实时系统调度理论研究的核心问题.单调速率(RM)算法是实时调度的重要算法,自其提出以来已被广泛研究.然而到目前为止,尚缺乏专题性的文章来系统而深入地探讨RM及其扩展算法的可调度性判定,以及各种现实条件和实现方式(包括任务调度的时间开销和任务同步问题等)对可调度性的影响.围绕RM算法下的可调度性判定问题,由浅入深,系统性地讨论各种不同假设和实现方式对可调度性的影响,具体为下述3大类问题:(1)理想的RM算法下的可调度性判定的CPU利用率最小上界最小及可调度的充分必要条件;(2)考虑调度时间开销情况下的可调度性判定条件;(3)优先级反转协议及其对可调度性的影响.给除了具体实例来叙述上述问题,并从算法复杂度和可检测率两方面比较各种算法的优劣。 相似文献
5.
端到端实时CORBA系统调度模型及其可调度性研究 总被引:6,自引:0,他引:6
实时CORBA系统中的基本问题是如何合理分配有限的计算资源和通信资源以保证各个实时任务的时间需求。该文以固定优先级方式调度的、周期性任务的硬实时系统为研究对象,提出了端到端实时CORBA系统调度模型,该模型综合考虑了客户端系统的处理、服务对象处理、网络传输等几大主要因素,而且可以描述服务对象间的嵌套调用关系,因而能全面描述实时CORBA系统中客户调用过程。在此基础上,该文基于非连续工作型同步协议,应用时间需求分析方法,研究并提出了该模型的可调度性分析算法。 相似文献
6.
针对于CAN总线的调度问题,因现有的平均分区EDF调度算法在对于优先级反转问题上收效甚微,从而导致消息缺乏一定的可调度性,故提出一种改进的基于幂函数分区的EDF算法;同时借助量化误差的概念,对该调度算法进行可调度性分析,充分论证了在该调度算法下,消息可调度的判定条件;采用CANoe平台进行实验仿真,对比平均分区EDF调度算法和双幂函数分区EDF调度算法,经试验测试验证了双幂函数分区EDF调度算法的可行性和优越性,改善了消息的最坏响应时间,提高了CAN网络通讯的实时性。 相似文献
7.
8.
9.
RM及其扩展可调度性判定算法性能分析 总被引:4,自引:0,他引:4
可调度性判定是实时调度算法的关键问题.单调速率算法RM(rate monotonic)及其扩展是应用广泛的实时调度算法,大量文献讨论了实时任务在这些算法下的可调度性判定,给出了相应的判定算法.但迄今为止,对这些判定算法的性能分析都是理论上的定性分析或者只是少数几种判定算法之间的简单比较,这不利于实时系统的开发.归纳了RM及其扩展的可调度性判定算法,通过测试平台,系统地测试和分析了各算法的性能和适用场合,讨论了各种条件和实现方式对算法性能和可调度性的影响. 相似文献
10.
本文基于随机模型研究了软实时系统中任务的可调度性特征,提出了期望可调度性的概念. 期望可调度性是与实时任务到达时间t相关的, 因此, 提出的方法能研究任务子集在任意给定时间间隔的可调度性特征. 本文给出了期望可调度性的条件, 如果任务的持续时间满足该条件, 则实时任务具有期望可调度性. 基于理论结果的数值分析与模拟结果是一致的,这表明当软实时系统的负载率小于69%(某些确定性模型提供的)时, 实时任务总是期望可
调度的. 这一结果也表明基于随机模型的期望可调度性方法能为软实时系统的任务可调度性分析提供一个更大的阈值和更好的适应性. 相似文献
11.
基于软件容错模型,提出了允许容错优先级提升的抢占阈值容错调度算法(extended fault-tolerantfixed-priority with preemption threshold,简称FT-FPPT*).该算法能够在抢占式容错调度算法(fault-tolerantfixed-priority preemptive,简称FT-FPP)和抢占阈值容错调度算法(fault-tolerant fixed-priority with preemptionthreshold,简称FT-FPPT)无法提高系统容错能力的情况下,进一步提高系统的容错能力.为了获得系统中任务优先级分配的最佳策略,基于任务最坏响应时间的可调度性分析,提出了一种最优的优先级配置搜索算法(priorityassignment search algorithm,简称PASA).经过深入分析和实验证明,与FT-FPPT算法相比,FT-FPPT*算法能够有效地提高硬实时系统的容错能力. 相似文献
12.
针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。 相似文献
13.
The objective of this paper is two-fold: give a survey of response time analysis (RTA), and contribute to schedulability analysis
for the real-time transaction model. The RTA is studied under fixed priority policies (FPP), while schedulability analysis
assumes an optimal scheduling algorithm (like the deadline driven scheduling algorithm EDF) in a preemptive context on uniprocessor
systems. We compare the transaction model to the family of multiframe models, then present the exact, and approximated methods,
as well as a tunable method to compute the RTA. Finally we present a new schedulability analysis method and an efficient algorithm
to speed up this test. 相似文献
14.
在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment, PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数. 相似文献
15.
Improved multiprocessor global schedulability analysis 总被引:1,自引:0,他引:1
Sanjoy Baruah Vincenzo Bonifaci Alberto Marchetti-Spaccamela Sebastian Stiller 《Real-Time Systems》2010,46(1):3-24
A new technique was recently introduced by Bonifaci et al. for the analysis of real-time systems scheduled on multiprocessor
platforms by the global Earliest Deadline First (EDF) scheduling algorithm. In this paper, this technique is generalized so
that it is applicable to the schedulability analysis of real-time systems scheduled on multiprocessor platforms by any work-conserving
algorithm. The resulting analysis technique is applied to obtain a new sufficient global Deadline Monotonic (DM) schedulability
test. It is shown that this new test is quantitatively superior to pre-existing DM schedulability analysis tests; in addition,
the degree of its deviation from any hypothetical optimal scheduler (that may be clairvoyant) is quantitatively bounded. A new
global EDF schedulability test is also proposed here that builds on the results of Bonifaci et al. This new test is shown
to be less pessimistic and more widely applicable than the earlier result was, while retaining the strong theoretical properties
of the earlier result. 相似文献
16.
In real-time systems, schedulability analysis has been widely studied to provide offline guarantees on temporal correctness, producing many analysis methods. The demand-based schedulability analysis method has a great potential for high schedulability performance and broad applicability. However, such a potential is not yet fully realized for real-time multi-core scheduling mainly due to (i) the difficulty of calculating the resource demand under dynamic priority scheduling algorithms that are favorable to multi-cores, and (ii) the lack of understanding how to combine the analysis framework with deadline-miss conditions specialized for those scheduling algorithms. Addressing those two issues, to the best of our knowledge, this paper presents the first demand-based schedulability analysis for dynamic job-priority scheduling algorithms: EDZL (Earliest Deadline first until Zero-Laxity) and LLF (Least Laxity First), which are known to be effective for real-time multi-core scheduling. To this end, we first derive demand bound functions that compute the maximum possible amount of resource demand of jobs of each task while the priority of each job can change dynamically under EDZL and LLF. Then, we develop demand-based schedulability analyses for EDZL and LLF, by incorporating those new demand bound functions into the existing demand-based analysis framework. Finally, we combine the framework with additional deadline-miss conditions specialized for those two laxity-based dynamic job-priority scheduling algorithms, yielding tighter schedulability analyses. Via simulations, we demonstrate that the proposed schedulability analyses outperform the existing schedulability analyses for EDZL and LLF. 相似文献
17.
Low-Power Design for Real-Time Systems 总被引:1,自引:0,他引:1
Real-time Systems often are located in the special environments where the power consumption is a big concern. Upon presence of timing constraints, the low power design on the real-time systems has significant impact on the performance as well as the schedulability of the systems. The system developers are facing the challenges for reducing the power consumption and meeting the timing constraints in the real-time systems.This paper represents one of few attempts to address the issue of the low power design on real-time systems. We present two power reduction methods: one is at the software compilation level and the other at the operating system level. Given a real-time program, an inter-instruction power reduction technique is proposed to transform the program to another one with lower power consumption. In addition, a scheduling algorithm for real-time operating systems is proposed to reschedule real-time programs when the execution time of the programs is changed. Therefore, the proposed scheduling algorithm works together with the proposed power reduction technique to make sure all programs meet their deadlines and to improve the system schedulability. We also evaluate the performance of the proposed inter-instruction reduction method by comparing it with the cold scheduling algorithm and show that the proposed method outperforms the cold scheduling algorithm and reduces more energy power. 相似文献
18.
Rolling-horizon scheduling for energy constrained distributed real-time embedded systems 总被引:1,自引:0,他引:1
Chuan He Xiaomin Zhu Hui Guo Dishan Qiu Jianqing Jiang 《Journal of Systems and Software》2012,85(4):780-794
Energy-efficient scheduling approaches are critical to battery driven real-time embedded systems. Traditional energy-aware scheduling schemes are mainly based on the individual task scheduling. Consequently, the scheduling space for each task is small, and the schedulability and energy saving are very limited, especially when the system is heavily loaded. To remedy this problem, we propose a novel rolling-horizon (RH) strategy that can be applied to any scheduling algorithm to improve schedulability. In addition, we develop a new energy-efficient adaptive scheduling algorithm (EASA) that can adaptively adjust supply voltages according to the system workload for energy efficiency. Both the RH strategy and EASA algorithm are combined to form our scheduling approach, RH-EASA. Experimental results show that in comparison with some typical traditional scheduling schemes, RH-EASA can achieve significant energy savings while meeting most task deadlines (namely, high schedulability) for distributed real-time embedded systems with dynamic workloads. 相似文献