排序方式: 共有56条查询结果,搜索用时 31 毫秒
1.
针对综合模块化航空电子系统(Integrated Modular Avionics,IMA)存在周期任务和非周期任务,以及任务间依赖关系,传统方法不能准确验证其实时任务可调度性的问题,本文提出了一种基于Stopwatch时间自动机的ARINC653实时任务可调度性验证方法,利用模型检验工具UPPAAL对IMA系统进行建模仿真,并结合统计模型检验(Statistical Model Checking,SMC)与符号模型检验(Symbolic Model Checking,MC)来验证其可调度性。实验结果表明,该方法不仅快速验证了IMA系统的可调度性,而且能够准确定位不可调度任务。 相似文献
2.
In this paper, we re-analyse the rate monotonic scheduler. Traditionally, the schedulability condition was obtained from the greatest lower bound of utilisation factors over all the task sets that (are schedulable and) fully utilise the processor. We argue that full utilisation is not very appropriate for this purpose. We re-establish Liu and Layland's classic schedulability theorem by finding the greatest lower bound of utilisation factors over all the unschedulable task sets instead. The merits of our approach include: Firstly, the fact that the bound is both sound and tight for schedulability follows directly from definition; Secondly, our proof is simpler technically. 相似文献
3.
A heterogeneous system or distributed system typically contains different types of processors. Some jobs can execute on certain types of processors but not other types. Processors of different types may have different speeds. We present several worst-case upper bounds and efficient algorithms for determining the completion times of independent jobs that have arbitrary timing constraints and variable execution times and are scheduled on available processors dynamically in a priority-driven manner. Bounds and algorithms take into account the effects of nonmigratability, nonpreemptability and different levels of migratability. 相似文献
4.
强实时系统静态优先级调度的可调度性分析 总被引:5,自引:1,他引:4
文章在系统阐述和借鉴经典的强实时系统静态优先级调度理论的基础上,通过引入忙周期的概念,分析了任务时限超过任务周期的实时系统任务集的可调度特性,拓宽了该理论的应用范围,更有利于实时系统的设计者对任务的运行时间行为进行事前分析与预测。 相似文献
5.
EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number of context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3m/4=0.75m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m(1−1/e)≈0.6321m, where e≈2.718 is the Euler's number. 相似文献
6.
Minimal schedulability interval for real-time systems of periodic tasks with offsets 总被引:1,自引:0,他引:1
We consider real-time systems in highly safety context where tasks have to meet strict deadlines. Tasks are periodic, may have offsets, share critical resources and be precedence constrained. Off-line scheduling should be of great help for such systems, but methods proposed in the literature cannot deal with them. Our aim is to extend and improve the well-known cyclicity result of Leung and Merill to every scheduling algorithm and to systems of interacting tasks with offsets. One of the main benefit of our result is to enable the use of off-line scheduling methods for those real-time critical systems. 相似文献
7.
Assume that a real-time programP
T consisting of a number of parallel processes is executed on a system having a setPr of processors which are shared between the processes by a real-time schedulerS
T. Assume that PT must meet some timing deadlines. We show that such an implementation ofP
T can be represented as a transformationL(P
T) and that the deadlines ofP
T will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The schedulerS
T can be specifiedgenerically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details. 相似文献
8.
Uniprocessor schedulability theory made great strides, in part, due to the simplicity of composing the delay of a job from
the execution times of higher-priority jobs that preempt it. In this paper, we bound the end-to-end delay of a job in a multistage
pipeline as a function of job execution times on different stages under preemptive as well as non-preemptive scheduling. We
show that the end-to-end delay is bounded by that of a single virtual “bottleneck” stage plus a small additive component. This contribution effectively transforms the pipeline into a
single stage system. The wealth of schedulability analysis techniques derived for uniprocessors can then be applied to decide
the schedulability of the pipeline. The transformation does not require imposing artificial per-stage deadlines, but rather
models the pipeline as a whole and uses the end-to-end deadlines directly in the single-stage analysis. It also does not make
assumptions on job arrival patterns or periodicity and thus can be applied to periodic and aperiodic tasks alike. We show
through simulations that this approach outperforms previous pipeline schedulability tests except for very short pipelines
or when deadlines are sufficiently large. The reason lies in the way we account for execution overlap among stages. We discuss
how previous approaches account for overlap and point out interesting differences that lead to different performance advantages
in different cases. Further, we also show that in certain cases non-preemptive scheduling can result in higher system utilization
than preemptive scheduling in pipelined systems. We hope that the pipeline delay composition rule, derived in this paper,
may be a step towards a general schedulability analysis foundation for large distributed systems.
相似文献
Tarek AbdelzaherEmail: |
9.
The feasibility of general task systems with precedence constraints on multiprocessor platforms 总被引:1,自引:1,他引:0
Feasibility analysis determines (prior to system execution-time) whether a specified collection of hard-real-time jobs executed
on a processing platform can meet all deadlines. In this paper, we derive near-optimal sufficient tests for determining whether
a given collection of jobs can feasibly meet all deadlines upon a specified multiprocessor platform assuming job migration
is permitted. The collection of jobs may contain precedence constraints upon the order of execution of these jobs. The derived
tests are general enough to be applied even when the collection of jobs is incompletely specified. We discuss the applicability
of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks. We also
show that our feasibility conditions may be used to obtain global-EDF schedulability conditions.
相似文献
Sanjoy BaruahEmail: |
10.
Lionel C. Briand Yvan Labiche Marwa Shousha 《Genetic Programming and Evolvable Machines》2006,7(2):145-170
Reactive real-time systems have to react to external events within time constraints: Triggered tasks must execute within deadlines. It is therefore important for the designers of such systems to analyze the schedulability of tasks during the design process, as well as to test the system's response time to events in an effective manner once it is implemented. This article explores the use of genetic algorithms to provide automated support for both tasks. Our main objective is then to automate, based on the system task architecture, the derivation of test cases that maximize the chances of critical deadline misses within the system; we refer to this testing activity as stress testing. A second objective is to enable an early but realistic analysis of tasks' schedulability at design time. We have developed a specific solution based on genetic algorithms and implemented it in a tool. Case studies were run and results show that the tool (1) is effective at identifying test cases that will likely stress the system to such an extent that some tasks may miss deadlines, (2) can identify situations that were deemed to be schedulable based on standard schedulability analysis but that, nevertheless, exhibit deadline misses.
相似文献
Marwa ShoushaEmail: |