uu.seUppsala University Publications
Change search
Refine search result
1 - 16 of 16
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Oldest first
  • Newest first
Select
The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.
  • 1.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Models and Complexity Results in Real-Time Scheduling Theory2015Doctoral 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.

    List of papers
    1. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
    Open this publication in new window or tab >>Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
    2014 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 50, no 1, 48-86 p.Article in journal (Refereed) Published
    Abstract [en]

    We generalize the commonly used mixed-criticality sporadic task model to let all task parameters (execution-time, deadline and period) change between criticality modes. In addition, new tasks may be added in higher criticality modes and the modes may be arranged using any directed acyclic graph, where the nodes represent the different criticality modes and the edges the possible mode switches. We formulate demand bound functions for mixed-criticality sporadic tasks and use these to determine EDF-schedulability. Tasks have different demand bound functions for each criticality mode. We show how to shift execution demand between different criticality modes by tuning the relative deadlines. This allows us to shape the demand characteristics of each task. We propose efficient algorithms for tuning all relative deadlines of a task set in order to shape the total demand to the available supply of thecomputing platform. Experiments indicate that this approach is successful in practice. This new approach has the added benefit of supporting hierarchical scheduling frameworks.

    National Category
    Computer Science
    Research subject
    Computer Science with specialization in Real Time Systems
    Identifiers
    urn:nbn:se:uu:diva-212779 (URN)10.1007/s11241-013-9187-z (DOI)000328351200003 ()
    Projects
    UPMARC
    Available from: 2013-06-15 Created: 2013-12-13 Last updated: 2015-12-17Bibliographically approved
    2. Schedulability analysis of a graph-based task model for mixed-criticality systems
    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, 1-37 p.Article in journal (Refereed) Published
    National Category
    Computer Science
    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: 2016-12-10Bibliographically approved
    3. An optimal resource sharing protocol for generalized multiframe tasks
    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-2216, E-ISSN 2352-2208, Vol. 84, no 1, 92-105 p.Article 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: 2017-03-16Bibliographically approved
    4. Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete
    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, 281-286 p.Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    Piscataway, NJ: IEEE, 2015
    National Category
    Computer Science
    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: 2017-03-16Bibliographically approved
    5. Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
    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, 87-95 p.Conference paper, Published paper (Refereed)
    Place, publisher, year, edition, pages
    IEEE Computer Society, 2015
    National Category
    Computer Science
    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: 2017-03-17Bibliographically approved
  • 2.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    An optimal resource sharing protocol for generalized multiframe tasks2015In: The Journal of logical and algebraic methods in programming, ISSN 2352-2216, E-ISSN 2352-2208, Vol. 84, no 1, 92-105 p.Article in journal (Refereed)
  • 3.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ngai, Edith C.-H.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    A distributed swarm-intelligent localization for sensor networks with mobile nodes2011In: Proc. 7th International Wireless Communications and Mobile Computing Conference, Piscataway, NJ: IEEE , 2011, 83-88 p.Conference paper (Refereed)
    Abstract [en]

    We present a novel distributed localization algorithm, called Swarm-Intelligent Localization (SIL), for computing the physical locations of nodes in wireless sensor networks. The algorithm assumes that only a small fraction of the nodes have a priori knowledge of their positions, and that noisy distance measurements are available between all neighboring nodes. The algorithm has no explicit global state and it can handle nodes that are both mobile and that can arrive in the network at any time. SIL works in two different phases, a coarse phase where nodes compute rough positions for themselves based on information about remote anchors, and a fine phase where nodes iteratively refine their positions from the coarse phase by collaborating with their neighbors. The average computational complexity per node running SIL is very low, namely constant in the network size and linear in the connectivity of the network. We evaluate the algorithm through extensive simulations. The results indicate that SIL is able to compute accurate positions for the majority of nodes in a wide range of network topologies and settings, and that it can handle difficulties such as large distance measurement errors and low network connectivity.

  • 4.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Bounding and shaping the demand of generalized mixed-criticality sporadic task systems2014In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 50, no 1, 48-86 p.Article in journal (Refereed)
    Abstract [en]

    We generalize the commonly used mixed-criticality sporadic task model to let all task parameters (execution-time, deadline and period) change between criticality modes. In addition, new tasks may be added in higher criticality modes and the modes may be arranged using any directed acyclic graph, where the nodes represent the different criticality modes and the edges the possible mode switches. We formulate demand bound functions for mixed-criticality sporadic tasks and use these to determine EDF-schedulability. Tasks have different demand bound functions for each criticality mode. We show how to shift execution demand between different criticality modes by tuning the relative deadlines. This allows us to shape the demand characteristics of each task. We propose efficient algorithms for tuning all relative deadlines of a task set in order to shape the total demand to the available supply of thecomputing platform. Experiments indicate that this approach is successful in practice. This new approach has the added benefit of supporting hierarchical scheduling frameworks.

  • 5.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Schedulability analysis of a graph-based task model for mixed-criticality systems2016In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 52, no 1, 1-37 p.Article in journal (Refereed)
  • 6.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete2015In: Proc. 27th Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE, 2015, 281-286 p.Conference paper (Refereed)
  • 7.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization2015In: Proc. 36th Real-Time Systems Symposium, IEEE Computer Society, 2015, 87-95 p.Conference paper (Refereed)
  • 8.
    Ekberg, Pontus
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Bounding and shaping the demand of mixed-criticality sporadic tasks2012In: Proc. 24th Euromicro Conference on Real-Time Systems, IEEE Computer Society, 2012, 135-144 p.Conference paper (Refereed)
  • 9.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems2011In: Proc. Real-Time Systems Symposium, Piscataway, NJ: IEEE , 2011, 13-23 p.Conference paper (Refereed)
  • 10.
    Guan, Nan
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Stigge, Martin
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Resource sharing protocols for real-time task graph systems2011In: Proc. 23rd Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE , 2011, 272-281 p.Conference paper (Refereed)
  • 11.
    Mohaqeqi, Morteza
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Abdullah, Jakaria
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Refinement of workload models for engine controllers by state space partitioning2017In: 29th Euromicro Conference on Real-Time Systems: ECRTS 2017, Dagstuhl, Germany: Leibniz-Zentrum für Informatik , 2017, 11:1-22 p.Conference paper (Refereed)
  • 12.
    Mohaqeqi, Morteza
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    On fixed-priority schedulability analysis of sporadic tasks with self-suspension2016In: Proc. 24th International Conference on Real-Time Networks and Systems, New York: ACM Press, 2016, 109-118 p.Conference paper (Refereed)
  • 13.
    Nemitz, Catherine E.
    et al.
    Department of Computer Science, University of North Carolina at Chapel Hill.
    Yang, Kecheng
    Department of Computer Science, University of North Carolina at Chapel Hill.
    Yang, Ming
    Department of Computer Science, University of North Carolina at Chapel Hill.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Anderson, James H.
    Department of Computer Science, University of North Carolina at Chapel Hill.
    Multiprocessor Real-Time Locking Protocols for Replicated Resources2016In: Proc. 28th Euromicro Conference on Real-Time Systems (ECRTS), 2016, 50-60 p.Conference 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.

  • 14.
    Stigge, Martin
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    On the tractability of digraph-based task models2011In: Proc. 23rd Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE , 2011, 162-171 p.Conference paper (Refereed)
  • 15.
    Stigge, Martin
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Guan, Nan
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    The digraph real-time task model2011In: 17th Real-Time and Embedded Technology and Applications Symposium, Piscataway, NJ: IEEE Computer Society, 2011, 71-80 p.Conference paper (Refereed)
    Abstract [en]

    Models for real-time systems have to balance the inherently contradicting goals of expressiveness and analysis efficiency. Current task models with tractable feasibility tests have limited expressiveness, restricting their ability to model many systems accurately. In particular, they are all recurrent, preventing the modeling of structures like mode switches, local loops, etc.

    In this paper, we advance the state-of-the-art with a model that is free from these constraints. Our proposed task model is based on arbitrary directed graphs (digraphs) for job releases. We show that the feasibility problem on preemptive uniprocessors for our model remains tractable. This even holds in the case of task systems with arbitrary deadlines.

  • 16.
    Stigge, Martin
    et al.
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Ekberg, Pontus
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    Yi, Wang
    Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
    The fork-join real-time task model2013In: ACM SIGBED Review, ISSN 1551-3688, Vol. 10, no 2, 20-20 p.Article in journal (Refereed)
    Abstract [en]

    Hard real-time task models have evolved from periodic models to more sophisticated graph-based ones like the Digraph Real-Time Task Model (DRT) [1]. These models have in common that tasks are sequential in nature and do not allow for forking structures, modeling job releases that occur in parallel within the same task. To capture these, we present a task model that extends the DRT model with the possibility of forking and joining release paths. We are developing an exact schedulability test for EDF on uniprocessor systems with a pseudo-polynomial bound of its runtime.

1 - 16 of 16
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf