Performance of periodic real-time processes: a vertex-removing synchronised graph product

Antoon Hendrik Boode, Johannes F. Broenink

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    30 Downloads (Pure)


    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. For this reason it can be advantageous to combine processes, to reduce the number of context switches. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these configurations to periodic real-time processes executing on a single-core mono-processor. These processes can be represented by finite directed acyclic labelled multi-graphs. The vertex-removing synchronised product of such graphs gives graphs that represent processes which have less context switches. To reduce the memory occupancy, the vertex-removing synchronised product removes vertices that are not reachable; i.e. represents states that can never occur. By means of a lattice, we show all possible products of a set of graphs, where the number of products is given by the Bell number. We finish with heuristics from which a set of graphs can be calculated that represents a set of processes that will not miss their deadline and which fits in the available memory.
    Original languageEnglish
    Title of host publication36th WoTUG conference on concurrent and parallel programming
    Place of PublicationOxford
    PublisherOpen Channel Publishing Ltd
    Number of pages20
    ISBN (Print)978-0-9565409-8-0
    Publication statusPublished - 27 Aug 2014
    EventCommunicating Process Architectures, CPA 2014: 36th WoTUG Conference on Concurrent and Parallel Programming 2014 - University of Oxford, Oxford, United Kingdom
    Duration: 24 Aug 201427 Aug 2014
    Conference number: 36

    Publication series

    PublisherOpen Channel Publishing Ltd.


    ConferenceCommunicating Process Architectures, CPA 2014
    Abbreviated titleCPA
    CountryUnited Kingdom
    Internet address


    • CE-advanced robotics
    • Vertex removing synchronised product
    • Performance of real-time periodic processes
    • Graph transformation
    • Process algebra

    Fingerprint Dive into the research topics of 'Performance of periodic real-time processes: a vertex-removing synchronised graph product'. Together they form a unique fingerprint.

    Cite this