共查询到20条相似文献,搜索用时 31 毫秒
1.
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: |
2.
Real-time embedded systems are often specified as a collection of independent tasks, each generating a sequence of event-triggered
code blocks. The goal of scheduling tasks in this domain is to find an execution order which satisfies all real-time constraints.
Within the context of recurring real-time tasks, all previous work either allowed preemptions, or only considered dynamic
scheduling, and generally had exponential complexity. However, for many embedded systems running on limited resources, preemptive
scheduling may be very costly due to high context switching and memory overheads, and dynamic scheduling can be less desirable
due to high CPU overhead. In this paper, we study static priority scheduling of recurring real-time tasks. We focus on and
obtain schedule-theoretic results for the non-preemptive uniprocessor case. To achieve this, we derive a sufficient (albeit
not necessary) condition for schedulability under static priority scheduling and show that this condition can be efficiently
tested in practice. The latter technique is demonstrated with examples, where in each case, an optimal solution for a given
problem specification is obtained within reasonable time, by first detecting good candidates using meta-heuristics, and then
by testing them for schedulability.
相似文献
Selin Cerav-ErbasEmail: |
3.
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: |
4.
It is well known that the performance of computer controlled systems is heavily affected by delays and jitter occurring in
the control loops, which are mainly caused by the interference introduced by other concurrent activities. A common approach
adopted to reduce delay and jitter in periodic task systems is to decrease relative deadlines as much as possible, but without
jeopardizing the schedulability of the task set.
In this paper, we formally characterize the region of admissible deadlines so that the system designer can appropriately select
the desired values to maximize a given performance index defined over the task set. Finally we also provide a sufficient region
of feasible deadlines which is proved to be convex.
相似文献
Giorgio ButtazzoEmail: |
5.
An analysis of global edf schedulability for arbitrary-deadline sporadic task systems 总被引:1,自引:1,他引:0
Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task’s relative
deadline parameter is constrained to be no larger than its minimum inter-arrival separation. This paper introduces new analysis
techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in
this manner. For tasks with deadlines greater than their minimum inter-arrival separation, two models are considered, with
and without an implicit intra-task job precedence constraint. The new analyses yield schedulability conditions that strictly
dominate some previously proposed tests that are generally accepted to represent the current state of the art in multiprocessor
edf schedulability analysis, and permits the derivation of an improved speed-up bound.
相似文献
Sanjoy K. BaruahEmail: |
6.
Chen Xu-Dong Zhu Qing-Xin Liao Yong Xiong Guang Ze 《The Journal of supercomputing》2008,43(3):225-240
A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The
key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end
deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback
control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution
times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation
to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete
QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically
provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving
the system throughput.
相似文献
Xiong Guang ZeEmail: |
7.
Feasibility and schedulability problems have received considerable attention from the real-time systems research community
in recent decades. Since the publication of the Liu and Layland bound, many researchers have tried to improve the schedulability
bound of the RM scheduling. The LL bound does not make any assumption on the relationship between any of the task periods.
In this paper we consider the relative period ratios in a system. By reducing the difference between the smallest and the
second largest virtual period values in a system, we can show that the RM schedulability bound can be improved significantly.
This research has also proposed a system design methodology to improve the schedulability of real time system with a fixed
system load.
相似文献
Wei-Kuan ShihEmail: |
8.
Schedulability analysis of global edf 总被引:1,自引:1,他引:0
The multiprocessor edf scheduling of sporadic task systems is studied. A new sufficient schedulability test is presented and proved correct. It
is shown that this test generalizes the previously-known exact uniprocessor edf-schedulability test, and that it offers non-trivial quantitative guarantees (including a resource augmentation bound) on
multiprocessors.
相似文献
Sanjoy BaruahEmail: |
9.
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: |
10.
Tardiness bounds under global EDF scheduling on a multiprocessor 总被引:2,自引:2,他引:0
We consider the scheduling of a sporadic real-time task system on an identical multiprocessor. Though Pfair algorithms are
theoretically optimal for such task systems, in practice, their runtime overheads can significantly reduce the amount of useful
work that is accomplished. On the other hand, if all deadlines need to be met, then every known non-Pfair algorithm requires restrictions on total system utilization that can
approach approximately 50% of the available processing capacity. This may be overkill for soft real-time systems, which can
tolerate occasional or bounded deadline misses (i.e. bounded tardiness). In this paper we derive tardiness bounds under preemptive and non-preemptive global
when the total system utilization is not restricted, except that it not exceed the available processing capacity. Hence, processor
utilization can be improved for soft real-time systems on multiprocessors. Our tardiness bounds depend on the total system
utilization and per-task utilizations and execution costs—the lower these values, the lower the tardiness bounds. As a final
remark, we note that global
may be superior to partitioned
for multiprocessor-based soft real-time systems in that the latter does not offer any scope to improve system utilization
even if bounded tardiness can be tolerated.
相似文献
UmaMaheswari C. DeviEmail: |
11.
Edward T.-H. Chu Tai-Yi Huang Cheng-Han Tsai Jian-Jia Chen Tei-Wei Kuo 《Real-Time Systems》2009,41(3):222-255
The I/O subsystem has become a major source of energy consumption in a hard real-time monitoring and control system. To reduce
its energy consumption without missing deadlines, a dynamic power management (DPM) policy must carefully consider the power
parameters of a device, such as its break-even time and wake-up latency, when switching off idle devices. This problem becomes
extremely complicated when dynamic voltage scaling (DVS) is applied to change the execution time of a task. In this paper,
we present COLORS, a composite low-power scheduling framework that includes DVS in a DPM policy to maximize the energy reduction
on the I/O subsystem. COLORS dynamically predicts the earliest-access time of a device and switches off idle devices. It makes
use of both static and dynamic slack time to extend the execution time of a task by DVS, in order to create additional switch-off
opportunities. Task workloads, processor profiles, and device characteristics all impact the performance of a low-power real-time
algorithm. We also identify a key metric that primarily determines its performance. The experimental results show that, compared
with previous work, COLORS achieves additional energy reduction up to 20%, due to the efficient utilization of slack time.
相似文献
Tei-Wei KuoEmail: |
12.
Classic task models for real-time systems focus on execution windows expressing earliest start times and deadlines of tasks
for feasibility. Only within these windows the execution of tasks is feasible, and it is considered of uniform utility.
Some tasks, however, have target demands in addition: a task should preferably execute at a specific target point within its execution window, but can execute around
this point, albeit at lower utility. Examples of such applications include control and media processing.
In this paper, we present a task model based on a gravitational analogy to address these issues. Tasks are considered as massive
bobs hanging on a pendulum: a single task, left to itself, will execute at the bottom, the target point. If a force, such
as the weight of other tasks, is applied, it can be shifted around this point. Thus, tasks’ importance and their utility around
target points can be expressed. Since the execution of a task cannot be mapped to a point in time, the model allows tasks
to express an arbitrary point with its execution to represent the whole execution. This point is called the anchor point.
Moreover, we show an example of a scheduling algorithm for this model which finds an approximation to the best compromise
of tasks’ interests based on the equilibrium state of a pendulum. Nonetheless, this task model is not restricted to a particular
scheduling algorithm.
Results from a simulation study show the effectiveness of the approach.
相似文献
Gerhard FohlerEmail: |
13.
Constructing deliberative real-time AI systems is challenging due to the high execution-time variance in AI algorithms and
the requirement of worst-case bounds for hard real-time guarantees, often resulting in poor use of system resources. Using
a motivating case study, the general problem of resource usage maximization is addressed. We approach the issues by employing
a hybrid task model for anytime algorithms, which is supported by recent advances in fixed priority scheduling for imprecise
computation. In particular, with a novel scheduling scheme based on Dual Priority Scheduling, hard tasks are guaranteed by
schedulability analysis and scheduled in favor of optional and anytime components which are executed whenever possible for
enhancing system utility. Simulation studies show satisfactory performance on the case study with the application of the scheduling
scheme. We also suggest how aperiodic tasks can be scheduled effectively within the framework and how tasks can be prioritized
based on their utilities by an efficient algorithm. These works form a comprehensive package of scheduling model, analysis,
and algorithms based on fixed priority scheduling, providing a versatile platform where real-time AI applications can be suitably
facilitated.
相似文献
Alan BurnsEmail: |
14.
Real-time scheduling for energy harvesting sensor nodes 总被引:1,自引:1,他引:0
Energy harvesting has recently emerged as a feasible option to increase the operating time of sensor networks. If each node
of the network, however, is powered by a fluctuating energy source, common power management solutions have to be reconceived.
This holds in particular if real-time responsiveness of a given application has to be guaranteed. Task scheduling at the single
nodes should account for the properties of the energy source, capacity of the energy storage as well as deadlines of the single
tasks. We show that conventional scheduling algorithms (like e.g. EDF) are not suitable for this scenario. Based on this motivation,
we have constructed optimal scheduling algorithms that jointly handle constraints from both energy and time domain. Further
we present an admittance test that decides for arbitrary task sets, whether they can be scheduled without deadline violations.
To this end, we introduce the concept of energy variability characterization curves (EVCC) which nicely captures the dynamics
of various energy sources. Simulation results show that our algorithms allow significant reductions of the battery size compared
to Earliest Deadline First scheduling.
相似文献
Clemens MoserEmail: |
15.
MPEG-4 video coding stream with Fine Granularity Scalability (FGS) can be flexibly dropped by very fine granularity so as
to adapt to the available network bandwidth. The MPEG-4 FGS model is similar to the imprecise computation model originally
proposed in the real-time scheduling field. In both models, it is required that all the mandatory tasks be completely scheduled
before their deadlines even in the worst case, which is called the feasible mandatory constraint. The problem is how to maximize
the number of the scheduled tasks based on the importance of tasks and to satisfy the feasible mandatory constraint. We adapt
the existing unit-time tasks scheduling algorithm to address the problem by using a weighted assignment scheme that adds constant
weights to mandatory tasks. Under the feasible mandatory constraint, we prove that the proposed algorithm maximizes the total
weights of the scheduled tasks, and all mandatory tasks are guaranteed to be completely scheduled before their deadlines.
The experimental results show the performance of the video quality for our scheduling algorithm by the measurements of Peak
Signal to Noise Ratio (PSNR).
相似文献
LihChyun Shu (Corresponding author)Email: |
16.
A probabilistic and adaptive scheduling algorithm using system-generated predictions for inter-grid resource sharing 总被引:1,自引:1,他引:0
Rapid advancement and more readily availability of Grid technologies have encouraged many businesses and researchers to establish
Virtual Organizations (VO) and make use of their available desktop resources to solve computing intensive problems. These
VOs, however, work as disjointed and independent communities with no resource sharing between them. We, in previous work,
have proposed a fully decentralized and reconfigurable Inter-Grid framework for resource sharing among such distributed and
autonomous Grid systems (Rao et al. in ICCSA, [2006]). The specific problem that underlies in such a collaborating Grids system is scheduling of resources as there is very little
knowledge about availability of the resources due to the distributed and autonomous nature of the underlying Grid entities.
In this paper, we propose a probabilistic and adaptive scheduling algorithm using system-generated predictions for Inter-Grid
resource sharing keeping collaborating Grid systems autonomous and independent. We first use system-generated job runtime
estimates without actually submitting jobs to the target Grid system. Then this job execution estimate is used to predict
the job scheduling feasibility on the target system. Furthermore, our proposed algorithm adapted itself to the actual resource
behavior and performance. Simulation results are presented to discuss the correctness and accuracy of our proposed algorithm.
相似文献
Eui-Nam Huh (Corresponding author)Email: |
17.
The Real-Time Specification for Java (RTSJ) provides an integrated approach to scheduling periodic real-time threads and monitoring
their CPU execution time. It defines a cost enforcement model whereby a periodic real-time thread is suspended when it consumes
more CPU time (budget) than it requested in a single release. However, compliant implementations need not support this model, as the underlying operating systems mechanisms are not widely
available. Consequently, experience with the model is limited (it is generally not provided in most implementations of the
RTSJ). In previous work we showed, using model checking techniques, that the current version of the cost enforcement model
can, under certain unlikely scenarios, allow a periodic thread more than its CPU budget in a single period. Such a behaviour can undermine any schedulability analysis that has been undertaken. In this paper, we present a revised
formal model, which corrects this anomalous behaviour, and evaluate its properties. We also extend the formal model, so it
allows support for real-time threads with sporadic and aperiodic releases, and show how our revised cost enforcement model
is valid for all types of threads.
相似文献
Andy WellingsEmail: |
18.
This paper addresses the search and track coordination problems of multiple shipboard radars. The proposed approach first
exploits the physical characteristics of a single phased array radar to improve its effective capacity. Its effective capacity
is abstracted by a closed-form equation called a schedulability envelope. Using the schedulability envelope for each radar, we deal with search and track coordination as a relative-load-balancing problem in a multi-resource environment. The simulation results show that the proposed approach significantly improves the
overall capacity of a multi-ship multi-radar system.
相似文献
Chang-Gun Lee (Corresponding author)Email: |
19.
In scheduling hard-real-time systems, the primary objective is to meet all deadlines. We study the scheduling of such systems
with the secondary objective of minimizing the duration of time for which the system locks each shared resource. We abstract
out this objective into the resource hold time (rht)—the largest length of time that may elapse between the instant that a system locks a resource and the instant that it subsequently
releases the resource, and study properties of the rht. We present an algorithm for computing resource hold times for every resource in a task system that is scheduled using Earliest
Deadline First scheduling, with resource access arbitrated using the Stack Resource Policy. We also present and prove the
correctness of algorithms for decreasing these rht’s without changing the semantics of the application or compromising application feasibility.
相似文献
Sanjoy Baruah (Corresponding author)Email: |
20.
Computational grids hold great promise in utilizing geographically separated heterogeneous resources to solve large-scale
complex problems. However, they suffer from a number of major technical hurdles, including distributed resource management
and effective job scheduling. The main focus of this work is devoted on online scheduling of real time applications in distributed
environments such as grids. Specifically, we are interested in applications with several independent tasks, each task with
a prespecified lifecycle called deadline. Here, our goal is to schedule applications within an optimum overall time considering
the specified deadlines. To achieve this, the resource performance prediction based on workload modeling and with the help
of queuing techniques is employed. Afterward, a mathematical neural model is used to schedule the subtasks of the application.
The main contributions of this work is to incorporate the impatiency factor as well as resource fault in performance modeling
of nondedicated distributed systems, and also presenting an efficient and fast parallel scheduling algorithm under time constraint
and heterogeneous resources. The proposed model is appropriate for implementation on parallel machines and in O(1) time. The new model was implemented on GridSim toolkit and under various conditions and with different parameters to evaluate
the performance of scheduling algorithm. Simulation outcomes have shown that approximately in 87.8% of cases, our model schedules
the tasks in such a way that all constraints are satisfied.
相似文献
Mohammad Kazem AkbariEmail: |