تجزیه و تحلیل مبتنی بر اندازه گیری رفتار زمانی به عنوان پشتیبانی برای مشکلات برنامه ریزی در سیستم های موازی و توزیع شده زمان واقعی

Static analysis, based on scheduling techniques, provides the most typical approach for validation of real-time systems. However, in the case of complex real-time systems such as parallel and distributed systems, many simplifications are made in order to make analysis tractable. This means that even if the system can be statically validated, the real behaviour of the system in execution may be different enough from its theoretical behaviour to make it invalid. In these cases, an analysis based on measurement of the system in execution constitutes an invaluable aid to the static analysis. This article describes a methodology for the analysis of the temporal behaviour of parallel and distributed real-time systems with end-to-end constraints. The analysis is based on the measurement of a prototype of the system in execution and is supported by a behavioural model. The main components of the model are the sequences of activities throughout the system tasks (transactions), which are carried out in response to input events, causing the corresponding output events. Thus, the temporal behaviour of the system is viewed as a set of real-time transactions competing for the available resources. This article also includes experimental results of applying the methodology to the analysis of a well-known case study.

Timing analysis and validation have been highlighted as key areas of research for real-time and embedded computing [16]. Static analysis, based on formal methods and scheduling theory, and dynamic analysis, based on simulation and run-time measurement, are the two approaches most commonly used for timing analysis and validation. In complex industrial real-time systems, commonly implemented as parallel or distributed systems, timing constraints must be derived and imposed based on the end-to-end requirements between the input events (usually from the external environment of the system), and the output events (generated by the system in response to the input events). This end-to-end approach has been followed by several authors in the real-time computing area, working with mono-processor systems [3], parallel systems [18] and distributed systems [6] and [13]. Real-time scheduling, the most common approach in the related literature, produces low degrees of success with systems whose end-to-end tasks may have complex synchronization patterns (i.e. not only pipeline patterns, but fork-join patterns as well) and widely varying releases, execution times and resource requirements. The problem with scheduling theory for this kind of systems comes from the fact that the models we use incorporate many simplifications in order to make the problem tractable. Thus, a system which is perfectly schedulable in theory, may not be schedulable in practice, after implemententation on a specific platform. As real-time systems become more complex and more dynamic, analysis based on measurement provides more help in understanding their temporal behaviour during execution. Thus, this kind of analysis can effectively help in bridging the gap between real-time scheduling theory and implementation realities. Here, we propose an analysis methodology of temporal behaviour of parallel and distributed real-time systems based on measurement, as a complement to the static analysis based on scheduling. The methodology starts with an initial design for the real-time system, which is the result of using a suitable design methodology for this kind of systems [7]. After building a system prototype and carrying out measurements during its execution, the methodology permits not only the real-time system to be checked in practice, but also the identification of a set of causes for the observed system behaviour. Knowledge of these causes can also help in refining the scheduling parameters (i.e. task priorities and mapping) when the timing constraints for the system are not fulfiled. The methodology is supported by metrics corresponding to three system views [19], which are behavioural, structural and resource views. The structural view is a static view of the system and provides information about the software structure and its mapping on the hardware. The resource view provides dynamic information about the use of the resources. The last view, the behavioural view, provides information about the temporal behaviour of the system in terms of sequences of activities carried out in the system. The organization of the rest of the article is as follows: Section 2 presents the computational model of the kind of real-time systems to which the methodology is oriented; in Section 3, the model used in the behavioural view is shown; Section 4 presents the main steps and aspects of the analysis methodology; in Section 5, a well-known case study is analysed using the methodology; finally, in Section 6, the conclusions and future work are presented. Although the methodology can be applied to real-time systems in general, this work deals with parallel and distributed real-time systems, hereafter simply referred to as real-time systems (RTS).

A methodology for temporal behaviour analysis of RTS based on measurement has been presented. The methodology was designed as a complement to the conventional static analysis approach based on scheduling, and permits tuning of the scheduling parameters in complex and non-deterministic real-time embedded systems. To achieve this goal, the approach followed by the methodology considers the RTS as a set of real-time transactions, giving response to the action events. The possibility for the transactions to have not only a pipeline structure (as in conventional end-to-end tasks), but also a parallel structure, is another important characteristic of the approach. The methodology involves the construction of a synthetic prototype for the initial design of the RTS, which is refined until the final implementation. This refinement is carried out in two repeated steps: the diagnosis of temporal behaviour and the configuration of the RTS prototype. These steps are based on a set of parameters and metrics, covering three complementary views of the RTS: the behavioural view, the structural view and the resource view. Several cases with different numbers of processors have been analysed and configured with the methodology, one of which is presented in this article. Although not all the causes of behaviour considered in the methodology were covered by these cases, the fulfilment of the real-time constraints after the configuration steps have demonstrated the validity of the methodology. The future work has two main objectives: firstly, to derive automatic rules for proper configuration of systems using the expertise gained with the use of the methodology; secondly, to apply the methodology to real-time POSIX applications implemented with either parallel or distributed architectures.