On the automation of periodic hard real-time processes

摘要

Summary In certain single-core mono-processor configurations, e.g. embedded control systems like robotic applications comprising many short processes, process context switches may consume a considerable amount of the available processing power. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application. Furthermore, the end-to-end processing time suffers from the idle time of the processor, because, for example, processes have to wait for controllers executing some task. By relaxing the rules for synchronous communication via channels in the process-algebraic specification language Communicating Sequential Processes (CSP), we are able to reduce the end-to-end processing time. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these applications to periodic real-time processes executing on a single-core mono-processor. Because these processes can be represented by finite, deterministic, labelled, acyclic, directed multigraphs, we address these two problems using graph theory. We introduce a model of computation that, based on these graphs, shows an improved performance when we multiply these graphs. This multiplication is based on a synchronised graph product for which we have developed three versions; the Vertex- Removing Synchronised Product (VRSP), the Dot Vertex-Removing Synchronised Product (DVRSP) and the Extended Dot Vertex-Removing Synchronised Product (EVRSP). The VRSP is solely developed to reduce the number of context switches. The DVRSP and the EVRSP are an extension of the VRSP and deal with the reduction of the end-to-end execution time of a set of Periodic Hard Real-Time Control Processes (PHRCPs). Of course, these multiplications preserve the behaviour of the PHRCPs represented by these graphs. Our research is based on three research questions, where we define the various graph products, prove that these products will give a performance gain (under certain conditions) and elaborate the numerical and combinatorial aspects of these graph products. We introduce the notion of a consistent and an inconsistent set of graphs (represent- ing periodic real-time processes). Consistency is based on the contraction of graphs together with the sink and the source of the Cartesian Product of these graphs, where the sink and the source have to be invariant over the graph multiplication by the synchronised product, VRSP. We show that consistency and associativity of the VRSP are closely related in the sense that a set of graphs under the VRSP is associative if all pairs of graphs in the set of graphs and their products under the VRSP are consistent. Whether or not a significant performance gain is achieved by combining processes depends on the ratio of the context-switch time and the calculation time of the processes itself; clearly, this depends on the type of hardware and operating system used. But still, if the Periodic Hard Real-Time Control System (PHRCS) does not fulfil the requirements with respect to the deadline of its PHRCPs, calculating all possible products of two or more graphs may produce a set of graphs for which the processes they represent comprise a PHRCS that will fulfil the requirements with respect to deadline and memory occupancy. To increase the chance that such a PHRCS exists, we develop two theorems that decompose the graphs into smaller graphs. Decomposition of the graphs gives a new set of graphs from which the VRSP gives outcomes that were not available in the original set of graphs. It could well be that these new outcomes contain a solution for the PHRCPs, whereas the original set of graphs did not contain a solution. We show that the number of possible combinations of multiplications of graphs by the VRSP follows the Bell number (Bn ) series if the multiplication is associative. Therefore we develop heuristics that calculate a set of multiplied gr