Describes how the scheduling algorithms and schedulability analysis methods developed for periodic tasks can be extended to provide performance guarantees semi-periodic tasks. Like tasks, requests in a task are released regularly. However, their computation times vary widely. We focus on systems where total maximum utilization of each processor is larger than one. Hence, according existing conditions we cannot guarantee that schedulable, even though average very small. describe two providing...

In many distributed real-time systems, the workload can be modeled as a set of periodic tasks, each which consists chain subtasks executing on different processors. Synchronization protocols are used to govern release so that precedence constraints among satisfied and schedulability resultant system is analyzable. Tasks have worst-case average end-to-end response times when used. this paper, we consider systems with independent, tasks fixed-priority scheduling algorithms. We propose three...

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Although similar to the DAG task model, systems are significantly more difficult analyze due constraints posed by specification. An important feature in tied tasks, which must execute same thread during whole life cycle. tasks enjoy benefits simplicity and efficiency, it was considered be not suitable its complex behavior. In this paper, we study realtime scheduling analysis of with tasks. First, show...

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types workload, and usually offer higher performance energy efficiency. In this paper, we study worst-case response time (WCRT) analysis typed scheduling parallel DAG tasks on heterogeneous multi-cores, where workload each vertex in is only allowed to execute a type cores. The known WCRT bound problem grossly pessimistic suffers non-self-sustainability problem. propose two new bounds. first...

Real-time systems are shifting from single-core to multi-core processors. Software must be parallelized fully utilize the computation power of architecture. OpenMP is a popular parallel programming framework in general and high-performance computing, recently has drawn lot interests embedded real-time computing. Much recent work been done on scheduling OpenMP-based workload. However, these studies conduct evaluations with randomly generated task systems, which cannot well represent structure...

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both quantifying the performance of algorithms and as efficient schedulability tests. However, parallel real time task graphs depends on not only utilization, but also another parameter tensity, ratio between longest path length period. In this paper, we use utilization-tensity bounds to better characterize tasks. particular, derive DAG tasks under global EDF scheduling,...

OpenMP is a promising framework to develop parallel real-time software on multi-cores. Although similar the DAG task model, systems are significantly more difficult analyze due constraints posed by specifications. One of most interesting features in support for nested parallelism, enjoying benefits enhancing performance transparency libraries and promoting reuse black-box code. Previous researches scheduling mainly restrict only one level parallelism. The problem whether tasks with multiple...

In the formal analysis of real-time systems, modeling branching codes and intratask parallelism structures are two most important research topics. These properties combined, resulting in fork-join task (FJRT) model, which extends digraph-based model with forking joining semantics. We prove that EDF schedulability problem on a preemptive uniprocessor for FJRT is coNP-hard strong sense, even if utilization system bounded by constant strictly less than 1. Then, we show becomes tractable some...

Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality scheduling algorithms, but also serves as simple linear-time test. Earlier on capacity bounds sporadic DAG task model were either restricted to single or set tasks with implicit deadlines. In this paper, we consider constrained deadlines under global earliest deadline first...

Existing DAG-based task models in real-time scheduling research assume well-nested structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP systems general have more flexible that do not comply with this assumption. In paper, we model the behaviors of non-well-nested branching study problem how to bound their worst-case response times (WCRT). A naive solution is apply established WCRT for DAG tasks without branches...

The conditional directed acyclic graph (DAG) task model can represent the execution flows that commonly exist in many real-time parallel applications. Previous work has shown by properly assigning priority among vertices inside a nonconditional DAG task, we reduce response time and achieve better system schedulability. This article studies how to apply intra-task assignment tasks. We develop bound theoretically dominates state-of-the-art present novel algorithm compute polynomial time....

The workload of many real time systems can be characterized as a set preemptable jobs with linear precedence constraints. Typically their execution times are only known to lie within range values. In addition, share resources and access the must synchronized ensure integrity system. paper is concerned schedulability such when scheduled on priority driven basis. It describes three algorithms for computing upper bounds completion that have arbitrary release priorities. first two simple but do...

Synchronous parallel tasks are widely used in HPC for purchasing high average performance, but merely consider how to guarantee good timing predictabilities. OpenMP is a promising framework multi-core real-time embedded systems. The synchronous significantly more difficult schedule and analyze due constraints posed by specifications. An important feature tied task, which must execute on the same thread during whole life cycle. This paper designs novel method, called group scheduling, tasks,...

In the autonomous driving (AD) system, complex data dependencies exist between tasks with different activation rates, making it very hard to analyze systems' real-time behaviors. This paper formulates AD system as a multi-rate DAG and proposes an integrated framework co-analyze schedulability of individual end-to-end latency task chains in DAG. Integer linear programming (ILP) techniques are developed guide how drop redundant workload increase chance that timing requirements can be met....

There are many uncertain factors in job shop scheduling problems. However, those uncertainties critical for the procedures. The imprecise processing times modeled as triangular fuzzy numbers (TFNs) and due dates trapezium this paper. A multi-objective genetic algorithm is proposed to solve problems, which objective functions conflicting. Agreement index (AI) used show satisfaction of client defined value area time membership function intersection divided by date function. composed maximize...

The Chinese postman problem is a famous and classical in graph theory. This paper introduces new variant of this problem, namely, the time-dependent rural which motivated by applications, involving scheduling with processing time. We present an arc-path formulation for constraint set that divided into two parts. first part linear has strong combinatorial structure, defines polytope alternation sequence (APAS), while second nonlinear closely related to travel First, we investigate facial...

Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may very pessimistic. No one precisely knows the gap between WCRT bound and actual WCRT. In this paper, we aim to derive exact of DAG task under list scheduling upon multi-core platforms. We encode analysis problem into satisfaction modular theoretical (SMT) formulation based on insights algorithm, prove...

OpenMP is a promising framework for developing parallel real-time software on multi-cores. Recently, many graph-based task models representing realistic features of systems have been proposed and analyzed. However, all previous studies did not model the loop structures, which common in systems. In this paper, we formulate workload with structures as cyclic graph study how to compute safe upper bounds worstcase response time (WCRT). The combined creation tasks conditional branches result...

Directed acyclic graph (DAG) becomes a popular model for modern real-time embedded software. It is really challenge to bound the worst-case response time (WCRT) of DAG task. Parallelism, dependencies and mutual exclusion become three most critical properties parallel tasks. Recent work applied prioritizing techniques reduce task's WCRT bound, which has well studied first two properties, i.e., parallelism dependencies, but leaves mutually exclusive property as an open problem. This paper...

Autonomous machines are commonly subject to real-time constraints. ROS 2, a widely-used robotics framework, considers capabilities as critical factor and is constantly evolving address these challenges, e.g., the end-to-end timing guarantee data fusion, etc. This paper studies message synchronizer, an integral component for multi-sensor provides potential direction synchronizer's evolution in future versions of 2. For effective input from different sensors must be sampled at time points that...