An Exact Schedulability Test for Non-Preemptive Self-Suspending Real-Time Tasks

Download

index.pdf

Date

2019-01-01

Author

Yalcinkaya, Beyazit
Nasri, Mitra
Brandenburg, Bjoern B.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

169
views

0
downloads

Exact schedulability analysis of limited-preemptive (or non-preemptive) real-time workloads with variable execution costs and release jitter is a notoriously difficult challenge due to the scheduling anomalies inherent in non-preemptive execution. Furthermore, the presence of self-suspending tasks is well-understood to add tremendous complications to an already difficult problem. By mapping the schedulability problem to the reachability problem in timed automata (TA), this paper provides the first exact schedulability test for this challenging model. Specifically, using TA extensions available in UPPAAL, this paper presents an exact schedulability test for sets of periodic and sporadic self-suspending tasks with fixed preemption points that are scheduled upon a multiprocessor under a global fixed-priority scheduling policy. To the best of our knowledge, this is the first exact schedulability test for non-and limited-preemptive self-suspending tasks (for both uniprocessor and multiprocessor systems), and thus also the first exact schedulability test for the special case of global non-preemptive fixed-priority scheduling (for either periodic or sporadic tasks). Additionally, the paper highlights some subtle pitfalls and limitations in existing TA-based schedulability tests for non-preemptive workloads.

Subject Keywords

Task analysis, Automata, Jitter, Synchronization, Real-time systems, Program processors, Clocks

URI

https://hdl.handle.net/11511/66825

DOI

https://doi.org/10.23919/date.2019.8715111

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

An Analysis of the Bidirectional LMS Algorithm over Fast-Fading Channels Yapici, Yavuz; Yılmaz, Ali Özgür (2012-07-01) A bidirectional LMS algorithm is considered for estimation of fast frequency-selective time-varying channels with a promise of near optimal tracking performance and robustness to parameter imperfections under various scenarios at a practical level of complexity. The performance of the algorithm is verified by the theoretical steady-state MSE analysis and experimental bit error rate (BER) results.
A True random generator in FPGA for cryptographic applications Yıldırım, Salih; Bazlamaçcı, Cüneyt Fehmi; Department of Electrical and Electronics Engineering (2012) In this thesis a True Random Number Generator (TRNG) employed for cryptographic applications is investigated, implemented and evaluated. The design of TRNG and its embedded tests are described in VHDL language and then implemented on an FPGA platform. Randomness is extracted from the jitter of ring oscillators that has self-failure detecting and sampling logic. The implementation needs only primitive resources which are common in all kinds of FPGAs. The embedded randomness tests described in Federal Informa...
An analytical model for source code distributability verification Isazadeh, Ayaz; Karimpour, Jaber; Elgedawy, Islam; Izadkhah, Habib (Zhejiang University Press, 2014-02-01) One way to speed up the execution of sequential programs is to divide them into concurrent segments and execute such segments in a parallel manner over a distributed computing environment. We argue that the execution speedup primarily depends on the concurrency degree between the identified segments as well as communication overhead between the segments. To guarantee the best speedup, we have to obtain the maximum possible concurrency degree between the identified segments, taking communication overhead int...
A Heuristic for Resource-Constrained Multi-ProjectDiscrete Time-Cost Trade-Off Problem Seyisoğlu, Oya Başak; Sönmez, Rifat (null; 2018-11-16) Resource-constrained project scheduling in a multi-project environment is a challenging optimization problem as it requires simultaneous scheduling of activities associated with multiple projects, considering availability of scarce resources while satisfying a set of constraints. Despite a large number of researches being concentrated on developing heuristics and metaheuristics for the discrete time-cost trade-off scheduling problem, very few of the proposed methods analyze multiple projects adequately to r...
A Hierarchical Partitioning Strategy for an Efficient Parallelization of the Multilevel Fast Multipole Algorithm Ergül, Özgür Salih (Institute of Electrical and Electronics Engineers (IEEE), 2009-06-01) We present a novel hierarchical partitioning strategy for the efficient parallelization of the multilevel fast multipole algorithm (MLFMA) on distributed-memory architectures to solve large-scale problems in electromagnetics. Unlike previous parallelization techniques, the tree structure of MLFMA is distributed among processors by partitioning both clusters and samples of fields at each level. Due to the improved load-balancing, the hierarchical strategy offers a higher parallelization efficiency than previ...

Citation Formats

B. Yalcinkaya, M. Nasri, and B. B. Brandenburg, “An Exact Schedulability Test for Non-Preemptive Self-Suspending Real-Time Tasks,” 2019, p. 1228, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66825.