uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Ekberg, Pontus
Publications (10 of 18) Show all publications
Singh, A., Ekberg, P. & Baruah, S. (2019). Uniprocessor scheduling of real-time synchronous dataflow tasks. Real-time systems, 55(1), 1-31
Open this publication in new window or tab >>Uniprocessor scheduling of real-time synchronous dataflow tasks
2019 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 55, no 1, p. 1-31Article in journal (Refereed) Published
Abstract [en]

The synchronous dataflow graph (SDFG) model is widely used today for modeling real-time applications in safety-critical application domains. Schedulability analysis techniques that are well understood within the real-time scheduling community are applied to the analysis of recurrent real-time workloads that are represented using this model. An enhancement to the standard SDFG model is proposed, which supports the specification of a real-time latency constraint between a specified input and a specified output of an SDFG. A polynomial-time algorithm is derived for representing the computational requirement of each such enhanced SDFG task in terms of the notion of the demand bound function (dbf), which is widely used in real-time scheduling theory for characterizing computational requirements of recurrent processes represented by, e.g., the sporadic task model. By so doing, the extensive dbf-centered machinery that has been developed in real-time scheduling theory for the hard-real-time schedulability analysis of systems of recurrent tasks may be applied to the analysis of systems represented using the SDFG model as well. The applicability of this approach is illustrated by applying prior results from real-time scheduling theory to construct an exact preemptive uniprocessor schedulability test for collections of independent recurrent processes that are each represented using the enhanced SDFG model.

Keywords
Real-time systems, Synchronous dataflow (SDF), Hard real-time streaming dataflow applications, Algorithms
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-351328 (URN)10.1007/s11241-018-9310-2 (DOI)000463216800001 ()
Available from: 2018-05-21 Created: 2018-05-23 Last updated: 2019-04-24Bibliographically approved
Ekberg, P. & Wang, Y. (2017). Fixed-Priority Schedulability of Sporadic Tasks on Uniprocessors is NP-hard. In: 2017 IEEE Real-Time Systems Symposium (RTSS): . Paper presented at 38th IEEE Real-Time Systems Symposium (RTSS), Paris, France, December 5–8, 2017 (pp. 139-146). IEEE
Open this publication in new window or tab >>Fixed-Priority Schedulability of Sporadic Tasks on Uniprocessors is NP-hard
2017 (English)In: 2017 IEEE Real-Time Systems Symposium (RTSS), IEEE, 2017, p. 139-146Conference paper, Published paper (Refereed)
Abstract [en]

We study the computational complexity of the FP-schedulability problem for sporadic or synchronous periodic tasks on a preemptive uniprocessor. We show that this problem is (weakly) NP-hard, even when restricted to either (i) task sets with implicit deadlines and rate-monotonic priority ordering, or (ii) task sets with constrained deadlines, deadline-monotonic priority ordering and utilization bounded by any constant c, such that 0 < c < 1.

Place, publisher, year, edition, pages
IEEE, 2017
Series
Real-Time Systems Symposium-Proceedings, E-ISSN 1052-8725
Keywords
Scheduling, real-time, complexity, fixed-priority
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-337581 (URN)10.1109/RTSS.2017.00020 (DOI)000426466700013 ()978-1-5386-1415-0 (ISBN)
Conference
38th IEEE Real-Time Systems Symposium (RTSS), Paris, France, December 5–8, 2017
Available from: 2018-02-01 Created: 2018-01-02 Last updated: 2018-05-29Bibliographically approved
Mohaqeqi, M., Abdullah, J., Ekberg, P. & Yi, W. (2017). Refinement of workload models for engine controllers by state space partitioning. In: 29th Euromicro Conference on Real-Time Systems: ECRTS 2017. Paper presented at ECRTS 2017, June 27–30, Dubrovnik, Croatia (pp. 11:1-22). Dagstuhl, Germany: Leibniz-Zentrum für Informatik
Open this publication in new window or tab >>Refinement of workload models for engine controllers by state space partitioning
2017 (English)In: 29th Euromicro Conference on Real-Time Systems: ECRTS 2017, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2017, p. 11:1-22Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Dagstuhl, Germany: Leibniz-Zentrum für Informatik, 2017
Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 76
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-326690 (URN)10.4230/LIPIcs.ECRTS.2017.11 (DOI)978-3-95977-037-8 (ISBN)
Conference
ECRTS 2017, June 27–30, Dubrovnik, Croatia
Projects
UPMARC
Available from: 2017-06-30 Created: 2017-07-22 Last updated: 2017-07-25Bibliographically approved
Nemitz, C. E., Yang, K., Yang, M., Ekberg, P. & Anderson, J. H. (2016). Multiprocessor Real-Time Locking Protocols for Replicated Resources. In: Proc. 28th Euromicro Conference on Real-Time Systems (ECRTS): . Paper presented at Euromicro Conference on Real-Time Systems (ECRTS), Toulouse, FRANCE, JUL 05-08, 2016 (pp. 50-60).
Open this publication in new window or tab >>Multiprocessor Real-Time Locking Protocols for Replicated Resources
Show others...
2016 (English)In: Proc. 28th Euromicro Conference on Real-Time Systems (ECRTS), 2016, p. 50-60Conference paper, Published paper (Refereed)
Abstract [en]

A real-time multiprocessor synchronization problem is studied herein that has not be extensively studied before, namely, the management of replicated resources where tasks may require multiple replicas to execute. In prior work on replicated resources, k-exclusion locks have been used, but this restricts tasks to lock only one replica at a time. To motivate the need for unrestricted replica sharing, two use cases are discussed that reveal an interesting tradeoff: in one of the use cases, blocking is the dominant lock-related factor impacting schedulability, while in the other, lock/unlock overheads are. Motivated by these use cases, three replica-allocation protocols are presented. In the first two, the lock/unlock logic is very simple, yielding low overheads, but blocking is not optimal. In the third, blocking is optimal (ignoring constant factors), but additional lock/unlock overhead is incurred to properly order lock requests. Experiments are presented that examine the overhead/blocking tradeoff motivated by these protocols in some detail.

Series
Proceedings of the Euromicro Conference on Real-time Systems, ISSN 2159-3833
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-306902 (URN)10.1109/ECRTS.2016.29 (DOI)000389463400005 ()9781509028115 (ISBN)
Conference
Euromicro Conference on Real-Time Systems (ECRTS), Toulouse, FRANCE, JUL 05-08, 2016
Available from: 2016-11-04 Created: 2016-11-04 Last updated: 2018-01-13Bibliographically approved
Mohaqeqi, M., Ekberg, P. & Yi, W. (2016). On fixed-priority schedulability analysis of sporadic tasks with self-suspension. In: Proc. 24th International Conference on Real-Time Networks and Systems: . Paper presented at RTNS 2016, October 19–21, Brest, France (pp. 109-118). New York: ACM Press
Open this publication in new window or tab >>On fixed-priority schedulability analysis of sporadic tasks with self-suspension
2016 (English)In: Proc. 24th International Conference on Real-Time Networks and Systems, New York: ACM Press, 2016, p. 109-118Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2016
National Category
Embedded Systems
Identifiers
urn:nbn:se:uu:diva-305963 (URN)10.1145/2997465.2997485 (DOI)000391255400011 ()978-1-4503-4787-7 (ISBN)
Conference
RTNS 2016, October 19–21, Brest, France
Available from: 2016-10-19 Created: 2016-10-24 Last updated: 2017-03-16Bibliographically approved
Ekberg, P. & Yi, W. (2016). Schedulability analysis of a graph-based task model for mixed-criticality systems. Real-time systems, 52(1), 1-37
Open this publication in new window or tab >>Schedulability analysis of a graph-based task model for mixed-criticality systems
2016 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 52, no 1, p. 1-37Article in journal (Refereed) Published
National Category
Computer Sciences
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-265781 (URN)10.1007/s11241-015-9225-0 (DOI)000370819700001 ()
Available from: 2015-05-01 Created: 2015-11-03 Last updated: 2018-01-10Bibliographically approved
Ekberg, P., Guan, N., Stigge, M. & Yi, W. (2015). An optimal resource sharing protocol for generalized multiframe tasks. The Journal of logical and algebraic methods in programming, 84(1), 92-105
Open this publication in new window or tab >>An optimal resource sharing protocol for generalized multiframe tasks
2015 (English)In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 84, no 1, p. 92-105Article in journal (Refereed) Published
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-235474 (URN)10.1016/j.jlamp.2014.10.001 (DOI)000347601600007 ()
Projects
UPMARC
Available from: 2014-10-16 Created: 2014-11-04 Last updated: 2018-01-11Bibliographically approved
Ekberg, P. (2015). Models and Complexity Results in Real-Time Scheduling Theory. (Doctoral dissertation). Uppsala: Acta Universitatis Upsaliensis
Open this publication in new window or tab >>Models and Complexity Results in Real-Time Scheduling Theory
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

When designing real-time systems, we want to prove that they will satisfy given timing constraints at run time. The main objective of real-time scheduling theory is to analyze properties of mathematical models that capture the temporal behaviors of such systems. These models typically consist of a collection of computational tasks, each of which generates an infinite sequence of task activations. In this thesis we study different classes of models and their corresponding analysis problems.

First, we consider models of mixed-criticality systems. The timing constraints of these systems state that all tasks must meet their deadlines for the run-time scenarios fulfilling certain assumptions, for example on execution times. For the other scenarios, only the most important tasks must meet their deadlines. We study both tasks with sporadic activation patterns and tasks with complicated activation patterns described by arbitrary directed graphs. We present sufficient schedulability tests, i.e., methods used to prove that a given collection of tasks will meet their timing constraints under a particular scheduling algorithm.

Second, we consider models where tasks can lock mutually exclusive resources and have activation patterns described by directed cycle graphs. We present an optimal scheduling algorithm and an exact schedulability test.

Third, we address a pair of longstanding open problems in real-time scheduling theory. These concern the computational complexity of deciding whether a collection of sporadic tasks are schedulable on a uniprocessor. We show that this decision problem is strongly coNP-complete in the general case. In the case where the asymptotic resource utilization of the tasks is bounded by a constant smaller than 1, we show that it is weakly coNP-complete.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2015. p. 32
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1324
Keywords
Real-time systems, Scheduling theory, Task models, Computational complexity
National Category
Computer Sciences
Research subject
Computer Science with specialization in Embedded Systems
Identifiers
urn:nbn:se:uu:diva-267017 (URN)978-91-554-9423-0 (ISBN)
Public defence
2016-01-15, ITC, 2446, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Projects
UPMARC
Available from: 2015-12-16 Created: 2015-11-16 Last updated: 2019-02-25
Ekberg, P. & Yi, W. (2015). Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization. In: Proc. 36th Real-Time Systems Symposium: . Paper presented at RTSS 2015, December 1–4, San Antonio, TX (pp. 87-95). IEEE Computer Society
Open this publication in new window or tab >>Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
2015 (English)In: Proc. 36th Real-Time Systems Symposium, IEEE Computer Society, 2015, p. 87-95Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE Computer Society, 2015
National Category
Computer Sciences
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-265784 (URN)10.1109/RTSS.2015.16 (DOI)000380424600009 ()978-1-4673-9507-6 (ISBN)
Conference
RTSS 2015, December 1–4, San Antonio, TX
Projects
UPMARC
Available from: 2016-01-18 Created: 2015-11-03 Last updated: 2018-01-10Bibliographically approved
Ekberg, P. & Yi, W. (2015). Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete. In: Proc. 27th Euromicro Conference on Real-Time Systems: . Paper presented at ECRTS 2015, July 7–10, Lund, Sweden (pp. 281-286). Piscataway, NJ: IEEE
Open this publication in new window or tab >>Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete
2015 (English)In: Proc. 27th Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE, 2015, p. 281-286Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2015
National Category
Computer Sciences
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-265783 (URN)10.1109/ECRTS.2015.32 (DOI)000375052900025 ()978-1-4673-7570-2 (ISBN)
Conference
ECRTS 2015, July 7–10, Lund, Sweden
Projects
UPMARC
Available from: 2015-08-06 Created: 2015-11-03 Last updated: 2018-01-10Bibliographically approved
Organisations

Search in DiVA

Show all publications