Schedulability Analysis for the Abort-and-Restart Model

In real-time systems, a schedulable task-set guarantees that all tasks complete before their deadlines. In functional programming, atomic execution provides the correctness of the program. Priority-based functional reactive programming (P-FRP) allows the usage of functional programming in the real-time system environment. The abort-and-restart (AR) is a scheme to implement P-FRP but an appropriate scheduling approach does not exist at the moment. Hence, efficient analysis is needed for the AR model.

In this thesis, the schedulability analysis for the AR model is introduced and it shows that finding the critical instant for the AR model with periodic and sporadic tasks is intractable, and a new formulation is derived. Afterwards, a new priority assignment scheme is developed that has the performance close to the exhaustive search method, which is intractable for large systems. The technique of deferred preemption is employed and a new model, deferred abort (DA), provides better schedulability and dominates the non-preemptive model. Lastly, a tighter analysis is introduced and the technique of the multi-set approach from the analysis of cache related preemption delay is employed to introduce a new approach, multi-bag. The multi-bag approach can apply to both the AR model and the DA model. In the experiments, the schedulability of the AR model is improved at each stage of the research in this thesis.