Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is and hence certification, rest non safety critical does not need certified, or certified lower level assurance. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) described for scheduling such mixed-criticality task systems. Analyses significantly superior previously-known ones...

A model is considered for representing recurrent precedence-constrained tasks that are to execute on multiprocessor platforms. task specified as a directed cyclic graph (DAG), period, and relative deadline. Each vertex of the DAG represents sequential job, while edges represent precedence constraints between these jobs. All jobs released simultaneously need complete execution within deadline their release. The may release in this manner an unbounded number times, with successive releases...

Many safety-critical embedded systems are subject to certification requirements; some may be required meet multiple sets of requirements, from different authorities. Certification requirements in such "mixed-criticality" give rise interesting scheduling problems, that cannot satisfactorily addressed using techniques conventional theory. In this paper, we study a formal model for representing mixed-criticality workloads. We demonstrate first the intractability determining whether system...

A model has been proposed in [Baruah et al., Proceedings of the IEEE Real-Time Systems Symposium 2012] for representing recurrent precedence-constrained tasks to be executed on multiprocessor platforms, where each task is modeled by a directed acyclic graph (DAG), period, and relative deadline. Each vertex DAG represents sequential job, while edges represent precedence constraints between these jobs. All jobs are released simultaneously have completed within some specified The may release...

Different task models have been proposed to represent the parallel structure of real-time tasks executing on manycore platforms: fork/join, synchronous parallel, DAG-based, etc. Despite different schedulability tests and resource augmentation bounds are available for these systems, we experience difficulties in applying such results real application scenarios, where execution flow is characterized by multiple (and nested) conditional structures. When a branch drives number size sub-jobs...

The sporadic DAG task model exposes parallelism that may exist within individual tasks to the run-time scheduling mechanism, and is therefore considered a particularly suitable for representing recurrent real-time are be implemented upon multiprocessor platforms. This paper proposes evaluates an extension allow concurrent modeling of conditional execution pieces task, along with intra-task parallelism. Global Earliest Deadline First (GEDF) systems represented in this generalized studied,...

Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is and hence certification; rest non-safety-critical does not need certified, or certified lower levels assurance. The certification-cognizant runtime scheduling such mixed-criticality systems considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) presented: this can...

Several task models have been introduced in the literature to describe intrinsic parallelism of real-time activities, including fork/join, synchronous parallel, DAG-based, etc. Although schedulability tests and resource augmentation bounds derived for these context multicore systems, they are still too pessimistic execution flow parallel tasks characterized by multiple (and nested) conditional statements, where it is hard decide which path select modeling worst-case scenario. To overcome...

We investigate the impact of Stackelberg routing to reduce price anarchy in network games. In this setting, an α fraction entire demand is first routed centrally according a predefined strategy and remaining then selfishly by (nonatomic) players. Although several advances have been made recently proving that can, fact, significantly for certain topologies, central question whether holds true general still open. answer negatively constructing family single-commodity instances such every...

Physarum Polycephalum is a slime mold that apparently able to solve shortest path problems. A mathematical model has been proposed by biologists describe the feedback mechanism used adapt its tubular channels while foraging two food sources s0 and s1. We prove that, under this model, mass of will eventually converge s0-s1 network lies on, independently structure or initial distribution.This matches experimental observations can be seen as an example "natural algorithm", is, algorithm...

Recent results have demonstrated the existence of a sufficient global EDF schedulability test for sporadic task systems that makes following guarantee: any system is not determined to be schedulable on an m-processor platform by this guaranteed actually so in which each processor m/(2m - 1) times as fast. A new proposed here builds result. This shown less pessimistic and more widely applicable than earlier result was, while retaining strong theoretical properties particular, speedup bound

We study the preemptive scheduling of real-time sporadic tasks on a uniprocessor. consider both fixed priority (FP) as well dynamic by Earliest Deadline First (EDF) algorithm. investigate problems testing schedulability and computing response time tasks. Generally these are known to be computationally intractable for task systems with constrained deadlines. In this paper, we focus particular case harmonic period lengths, meaning that periods pair wise divide each other. This is special...