共查询到18条相似文献,搜索用时 156 毫秒
1.
2.
3.
4.
针对于CAN总线的调度问题,因现有的平均分区EDF调度算法在对于优先级反转问题上收效甚微,从而导致消息缺乏一定的可调度性,故提出一种改进的基于幂函数分区的EDF算法;同时借助量化误差的概念,对该调度算法进行可调度性分析,充分论证了在该调度算法下,消息可调度的判定条件;采用CANoe平台进行实验仿真,对比平均分区EDF调度算法和双幂函数分区EDF调度算法,经试验测试验证了双幂函数分区EDF调度算法的可行性和优越性,改善了消息的最坏响应时间,提高了CAN网络通讯的实时性。 相似文献
5.
端到端实时任务调度模型可用于描述许多分布式实时系统.提出一种基于EDF调度策略的端到端实时任务调度模型,给出了端到端实时系统的可调度性判定条件,并提出其可调度性分析算法,该可调度性判定条件及可调度性分析算法适用于采用非连续工作型同步协议和连续工作型同步协议控制下的端到端实时系统.与固定优先级的端到端实时任务调度模型及其算法相比,基于EDF调度策略的端到端实时任务调度模型和算法更加简单和易于实现,仿真结果也表明具有较高的性能. 相似文献
6.
7.
本文详细论述了应用于静态优先级实时系统的抢占阈值调度算法。描述了算法实现和任务集合可调度性判定公式的推导,分析了算法的性能特点,阐述了抢占阈值调度是静态优先级嵌入式实时系统开发中调度算法的合适选择。 相似文献
8.
在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment, PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数. 相似文献
9.
实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。 相似文献
10.
针对多处理器实时调度中的固定优先级(FP)调度算法,提出了一种改进的可调度性判定方法。引入Baruah的最早截止期优先(EDF)窗口分析框架,将高优先级任务带入作业的最大数量限定为m-1(m为处理器个数),进而对任务的干涉上界进行重新界定,并由此得到一个更加紧密的可调度性判定充分条件。仿真实验结果表明,该方法增加了通过判定任务集的数量,体现出更优的可调度判定性能。 相似文献
11.
12.
Bertogna M. Cirinei M. Lipari G. 《Parallel and Distributed Systems, IEEE Transactions on》2009,20(4):553-566
This paper addresses the schedulability problem of periodic and sporadic real-time task sets with constrained deadlines preemptively scheduled on a multiprocessor platform composed by identical processors. We assume that a global work-conserving scheduler is used and migration from one processor to another is allowed during a task lifetime. First, a general method to derive schedulability conditions for multiprocessor real-time systems will be presented. The analysis will be applied to two typical scheduling algorithms: earliest deadline first (EDF) and fixed priority (FP). Then, the derived schedulability conditions will be tightened, refining the analysis with a simple and effective technique that significantly improves the percentage of accepted task sets. The effectiveness of the proposed test is shown through an extensive set of synthetic experiments. 相似文献
13.
The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first scheduling algorithm (EDF) upon a given multiprocessor platform. A new priority-driven algorithm is proposed for scheduling periodic task systems upon multiprocessor platforms: this algorithm is shown to successfully schedule some task systems for which EDF may fail to meet all deadlines. 相似文献
14.
In a parallelizable task model, a task can be parallelized and the component tasks can be executed concurrently on multiple processors. We use this parallelism in tasks to meet their deadlines and also obtain better processor utilisation compared to non-parallelized tasks. Non-preemptive parallelizable task scheduling combines the advantages of higher schedulability and lower scheduling overhead offered by the preemptive and non-preemptive task scheduling models, respectively. We propose a new approach to maximize the benefits from task parallelization. It involves checking the schedulability of periodic tasks (if necessary, by parallelizing them) off-line and run-time scheduling of the schedulable periodic tasks together with dynamically arriving aperiodic tasks. To avoid the run-time anomaly that may occur when the actual computation time of a task is less than its worst case computation time, we propose efficient run-time mechanisms.We have carried out extensive simulation to study the effectiveness of the proposed approach by comparing the schedulability offered by it with that of dynamic scheduling using Earliest Deadline First (EDF), and by comparing its storage efficiency with that of the static table-driven approach. We found that the schedulability offered by parallelizable task scheduling is always higher than that of the EDF algorithm for a wide variety of task parameters and the storage overhead incurred by it is less than 3.6% of the static table-driven approach even under heavy task loads. 相似文献
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.
Strict periodicity constraint is of great importance since it concerns some hard real-time systems where missing deadlines leads to catastrophic situations. However, the problem of schedulability analysis for non-preemptive strictly periodic tasks on a multiprocessor platform is even more intractable than the one with the common periodicity. In order to implement such systems, designers need effective tools based on fast and near-optimal solutions.This paper presents a schedulability analysis which results mainly in a, two versions, task assignment and start-time calculation algorithm. The first one targets the harmonic task periods case while the second one targets the non-harmonic task periods case. Each version is based on a sufficient uniprocessor schedulability test. In addition, for the non-harmonic case which is the most intractable, the uniprocessor sufficient schedulability test uses the strictly periodic task utilization factor. This factor stands for the fraction of time spent to execute a task while its strict periodicity and the ones of the already scheduled tasks are met. As a result, an efficient and easily implementable scheduling algorithm is proposed which begins by assigning tasks to processors then attributes a start-time to every task in such a way that strict periodicity and deadline constraints are met. The effectiveness of the proposed scheduling algorithm, in both versions, has been shown by a performance evaluation and comparisons with an optimal and a similar suboptimal solution. 相似文献
17.
一种改进的RM可调度性判定算法 总被引:6,自引:1,他引:5
固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高. 相似文献
18.
EDZL scheduling analysis 总被引:2,自引:1,他引:1
A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with
multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic
tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm.
Global EDZL is known to be at least as effective as global Earliest-Deadline-First (EDF) in scheduling task sets to meet deadlines.
It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new
schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF
schedulability tests.
In the second part of the paper, an improved version of the EDZL-schedulability test is presented. This new algorithm is able
to efficiently exploit information on the slack values of interfering tasks, to iteratively refine the estimation of the interference
a task can be subjected to. This iterative algorithm is shown to have better performance than the initial test, in terms of
schedulable task sets detected.
相似文献
Marko BertognaEmail: |