Springer Science and Business Media LLC

Fieldbus networks aim at the interconnection of field devices such as sensors, actuators and small controllers. Therefore, they are an effective technology upon which distributed computer-controlled systems (DCCS) can be built. DCCS impose strict timeliness requirements to the communication network. In essence, by timeliness requirements we mean that traffic must be sent and received within a bounded interval, otherwise a timing fault is said to occur. P-NET is a multi-master fieldbus standard based on a virtual token passing scheme. In P-NET each master is allowed to transmit only one message per token visit, which means that in the worst-case the communication response time could be derived considering that the token is fully utilized by all stations. However, such analysis can be proved to be quite pessimistic. In this paper, we propose a more sophisticated P-NET timing analysis model, which considers the actual token utilization by different masters. The major contribution of this model is to provide a less pessimistic, and thus more accurate, analysis for the evaluation of the worst-case communication response time in P-NET fieldbus networks.

To meet consistency requirements found in concurrent applications, a process must be guaranteed that it will be able to use all resources in a set ofpassive resources (such as shared data structures). To provide predictable execution time required in real-time systems, a process also needs guaranteed access to at least one of a set ofactive resources (such as processors) associated with each passive resource. As such, a concurrent real-time-process has AND-OR resource requirements. If locking is used to provide exclusive access to resources, deadlock is possible since processes can request additional resources while holding other resources. Deadlock detection and recovery techniques and deadlock avoidance techniques typically involve preempting resources or terminating processes, and are therefore inappropriate for real-time systems that require the execution time of processes to be predictable. This paper describes a general resource request condition that we proveprevents deadlock in AND-OR systems. It also describes how we use this AND-OR deadlock prevention technique in a concurrent real-time system.

Synchronous reactive models are widely used in the development of embedded software and systems. The schedulability analysis of tasks obtained as the code implementation of synchronous finite state machines (FSMs) can be performed in several ways. One possible option is to leverage the correspondence between the execution of actions in an FSM and the execution of jobs in a digraph task model, thereby applying all the analysis methods developed for these digraph task systems. Another option is to directly leverage the state information and use dynamic programming methods to compute the worst possible sequence of (state dependent) reactions for a given FSM model. In this paper we compare these analysis methods in terms of accuracy and runtime.

In the high-tech and automotive industry, bandwidth considerations and widely accepted standardization are two important reasons why Ethernet is currently being considered as an alternative solution for real-time communication (compared to traditional fieldbusses). Although Ethernet was originally not intended for this purpose, the development of the Ethernet AVB standard enables its use for transporting high-volume data (e.g. from cameras and entertainment applications) with low-latency guarantees. In complex industrial systems, the network is shared by many applications, developed by different parties. To face this complexity, the development of these applications must be kept as independent as possible. In particular, from a network point of view, progress of all communication streams must be guaranteed, and the performance for individual streams should be predictable using only information regarding the stream under study and the general parameters of the communication standard used by the network. Initial methods to guarantee latency for Ethernet AVB networks rely on the traditional busy-period analysis. Typically, these methods are based on knowledge of the inter-arrival patterns of both the stream under study and the interfering streams that also traverse the network. The desired independence is therefore not achieved. In this paper, we present an independent real-time analysis based on so-called eligible intervals, which does not rely on any assumptions on interfering priority classes other than those enforced in the Ethernet AVB standard. We prove this analysis is tight in case there is only a single higher-priority stream, and no additional information on interference is known. In case there are multiple higher-priority streams, we give conditions under which the analysis is still tight. Furthermore, we compare the results of our approach to the two most recent busy-period analyses, point out sources of pessimism in these earlier works, and argue that assuming more information on the sources of interference (e.g. a minimal inter-arrival time between interfering frames) has only limited advantages.

The synchronous dataflow graph (SDFG) model is widely used today for modeling real-time applications in safety-critical application domains. Schedulability analysis techniques that are well understood within the real-time scheduling community are applied to the analysis of recurrent real-time workloads that are represented using this model. An enhancement to the standard SDFG model is proposed, which supports the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A polynomial-time algorithm is derived for representing the computational requirement of each such enhanced SDFG task in terms of the notion of the demand bound function (dbf), which is widely used in real-time scheduling theory for characterizing computational requirements of recurrent processes represented by, e.g., the sporadic task model. By so doing, the extensive dbf-centered machinery that has been developed in real-time scheduling theory for the hard-real-time schedulability analysis of systems of recurrent tasks may be applied to the analysis of systems represented using the SDFG model as well. The applicability of this approach is illustrated by applying prior results from real-time scheduling theory to construct an exact preemptive uniprocessor schedulability test for collections of independent recurrent processes that are each represented using the enhanced SDFG model.

Probabilistic hard real-time systems, based on hardware architectures that use a random replacement cache, provide a potential means of reducing the hardware over-provision required to accommodate pathological scenarios and the associated extremely rare, but excessively long, worst-case execution times that can occur in deterministic systems. Timing analysis for probabilistic hard real-time systems requires the provision of probabilistic worst-case execution time (pWCET) estimates. The pWCET distribution can be described as an exceedance function which gives an upper bound on the probability that the execution time of a task will exceed any given execution time budget on any particular run. This paper introduces a more effective static probabilistic timing analysis (SPTA) for multi-path programs. The analysis estimates the temporal contribution of an evict-on-miss, random replacement cache to the pWCET distribution of multi-path programs. The analysis uses a conservative join function that provides a proper over-approximation of the possible cache contents and the pWCET distribution on path convergence, irrespective of the actual path followed during execution. Simple program transformations are introduced that reduce the impact of path indeterminism while ensuring sound pWCET estimates. Evaluation shows that the proposed method is efficient at capturing locality in the cache, and substantially outperforms the only prior approach to SPTA for multi-path programs based on path merging. The evaluation results show incomparability with analysis for an equivalent deterministic system using an LRU cache. For some benchmarks the performance of LRU is better, while for others, the new analysis techniques show that random replacement has provably better performance.

Bài báo này giải quyết vấn đề phân bổ tài nguyên cho các nhiệm vụ thời gian thực định kỳ phân tán, hoạt động trong các môi trường có sự thay đổi không dự đoán được và không phù hợp với việc chỉ định thời gian thực thi tồi tệ nhất có nghĩa. Các nhiệm vụ này được cung cấp bởi dữ liệu đầu vào xuất phát từ nhiều nguồn tải công việc môi trường khác nhau. Thay vì sử dụng thời gian thực thi tồi tệ nhất (WCETs) để mô tả mức sử dụng CPU của các nhiệm vụ, chúng tôi giả định rằng các hồ sơ thực thi được cung cấp để mô tả thời gian chạy của các nhiệm vụ dựa trên kích thước dữ liệu đầu vào của mỗi nguồn tải công việc. Mục tiêu của việc phân bổ tài nguyên là tạo ra một phân bổ ban đầu mạnh mẽ chống lại các biến động trong các tham số môi trường. Chúng tôi cố gắng tối đa hóa kích thước đầu vào (tải công việc) mà hệ thống có thể xử lý, và do đó trì hoãn các phân bổ lại (tốn kém) càng lâu càng tốt. Chúng tôi trình bày một thuật toán xấp xỉ dựa trên đầu tiên - phù hợp và tìm kiếm nhị phân mà chúng tôi gọi là FFBS. Như chúng tôi đã chỉ ra ở đây, thuật toán đầu tiên - phù hợp sản xuất các giải pháp thường gần với tối ưu. Cụ thể, chúng tôi cho thấy phân tích rằng FFBS được đảm bảo cung cấp một giải pháp ít nhất là 41% so với tối ưu, asymptotically, trong một số giới hạn hợp lý về thời gian chạy của các nhiệm vụ trong hệ thống. Hơn nữa, chúng tôi cho thấy rằng nếu ít nhất 12% sử dụng của hệ thống bị tiêu tốn bởi các nhiệm vụ độc lập đầu vào (ví dụ, các nhiệm vụ thời gian cố định), thì FFBS được đảm bảo cung cấp một giải pháp ít nhất là 33% so với tối ưu, asymptotically. Hơn nữa, chúng tôi trình bày các mô phỏng để so sánh thuật toán xấp xỉ FFBS với một tập hợp các heuristics chuẩn (tìm kiếm địa phương) như leo núi, làm mát giả lập và tìm kiếm ngẫu nhiên. Các kết quả cho thấy rằng FFBS, kết hợp với các chiến lược cải thiện địa phương khác, có thể là một phương pháp hợp lý cho việc phân bổ tài nguyên trong các hệ thống thời gian thực động.

In real-time software, not only computation errors but also timing errors can cause system failures, which eventually result in significant physical damages or threats to human life. To efficiently guarantee the timely execution of expected functions, it is necessary to clearly specify and formally verify timing requirements before performing detailed system design. With the expected benefit of reusability and extensibility, component technology has been gradually applied to developing industrial applications including real-time systems. However, most of component-based approaches applied to real-time systems lack in a systematic and rigorous approach to specifying and verifying timing requirements at an earlier development stage. This paper proposes a component-based approach to specifying and verifying timing requirements for real-time systems in a systematic and compositional manner. We first describe behaviors of the constituent components including timing requirements in UML diagrams, and then translate the UML diagrams into MTER nets, an extension of TER nets, to perform timing analysis in a compositional way. The merit of the proposed approach is that the specification and analysis results can be reused and independently maintained.

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.