Schedulability, Response Time Analysis and New Models of P-FRP Systems

Date

2017-08

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Functional Reactive Programming (FRP) is a declarative approach for modeling and building reactive systems. FRP has been shown to be an expressive formalism for building applications of computer graphics, computer vision, robotics, etc. Priority-based FRP (P-FRP) is a formalism that allows preemption of executing programs and guarantees real-time response. Since functional programs cannot maintain state and mutable data, changes made by programs that are preempted have to be rolled back. Hence in P-FRP, a higher priority task can preempt the execution of a lower priority task, but the preempted lower priority task will have to restart after the higher priority task has completed execution. This execution paradigm is called Abort-and-Restart (AR). Current real-time research is focused on preemptive of non-preemptive models of execution and several state-of-the-art methods have been developed to analyze the real-time guarantees of these models. Unfortunately, due to its transactional nature where preempted tasks are aborted and have to restart, the execution semantics of P-FRP does not fit into the standard definitions of preemptive or non-preemptive execution, and the research on the standard preemptive and non-preemptive may not applicable for the P-FRP AR model. Out of many research areas that P-FRP may demands, we focus on task scheduling which includes task and system modeling, priority assignment, schedulability analysis, response time analysis, improved P-FRP AR models, algorithms and corresponding software. In this work, we review existing results on P-FRP task scheduling and then present our research contributions: (1) a tighter feasibility test interval regarding the task release offsets as well as a linked list based algorithm and implementation for scheduling simulation; (2) P-FRP with software transactional memory-lazy conflict detection (STM-LCD); (3) a non-work-conserving scheduling model called Deferred Start; (4) a multi-mode P-FRP task model; (5) SimSo-PFRP, the P-FRP extension of SimSo - a SimPy-based, highly extensible and user friendly task generator and task scheduling simulator.

Description

Keywords

Real-time scheduling, P-FRP

Citation

Portions of this document appear in: Jiang, Yu, Albert MK Cheng, and Xingliang Zou. "Schedulability analysis for real-time P-FRP tasks under fixed priority scheduling." In 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 31-40. IEEE, 2015. And in: Zou, Xingliang, Albert MK Cheng, and Yu Jiang. "A non-work-conserving model for P-FRP fixed priority scheduling." In 2016 13th International Conference on Embedded Software and Systems (ICESS), pp. 12-17. IEEE, 2016. And in: Zou, Xingliang, Albert MK Cheng, Carlos Rincon, and Yu Jiang. "Multi-mode P-FRP Task Scheduling." In 2017 IEEE 20th International Symposium on Real-Time Distributed Computing (ISORC), pp. 150-157. IEEE, 2017.