Monotonicity and run-time scheduling

M.H. Wiggers, Marco Jan Gerrit Bekooij, Gerardus Johannes Maria Smit

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

    31 Citations (Scopus)


    Modern embedded multi-processors can execute several streamprocessing applications concurrently. Typically, these applications are partitioned into tasks that communicate over buffers together forming a task graph. The fact that these applications are started and stopped by the user combined with the knowledge that not all applications are necessarily completely characterised makes it attractive to use run-time scheduling. We define and characterise a class of budget schedulers that by construction bound the interference from other applications. Furthermore, we will show that the worst-case effects of these schedulers can be included in dataflow process networks. The execution of the resulting dataflow process network is shown to result in tight and conservative bounds on the end-to-end temporal behaviour of the execution of the task graph on a cycle-true simulator. Given that the inter-task synchronisation of the application allows for a dataflow model that is functionally deterministic, this enables exploration of various buffer capacities and scheduler settings at a high level of abstraction.
    Original languageUndefined
    Title of host publicationProceedings of the seventh ACM international conference on Embedded Software
    Place of PublicationNew York
    PublisherAssociation for Computing Machinery
    Number of pages10
    ISBN (Print)978-1-60558-627-4
    Publication statusPublished - 12 Oct 2009
    Event9th ACM & IEEE International Conference on Embedded Software, EMSOFT 2009 - Grenoble, France
    Duration: 12 Oct 200916 Oct 2009
    Conference number: 9

    Publication series



    Conference9th ACM & IEEE International Conference on Embedded Software, EMSOFT 2009
    Abbreviated titleEMSOFT


    • METIS-264471
    • EWI-17184
    • IR-69781

    Cite this