dc.contributor.author | Philippou, Anna | en |
dc.contributor.author | Lee, I. | en |
dc.contributor.author | Sokolsky, O. | en |
dc.creator | Philippou, Anna | en |
dc.creator | Lee, I. | en |
dc.creator | Sokolsky, O. | en |
dc.date.accessioned | 2019-11-13T10:41:59Z | |
dc.date.available | 2019-11-13T10:41:59Z | |
dc.date.issued | 2012 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/54839 | |
dc.description.abstract | As real-time embedded systems become more complex, resource partitioning is increasingly used to guarantee real-time performance. Recently, several compositional frameworks of resource partitioning have been proposed using real-time scheduling theory with various notions of real-time tasks running under restricted resource supply environments. However, these real-time scheduling-based approaches are limited in their expressiveness in that, although capable of describing resource-demand tasks, they are unable to model resource supply. This paper describes a process algebraic framework PADSfor reasoning about resource demand and resource supply inspired by the timed process algebra ACSR. In ACSR, real-time tasks are specified by enunciating their consumption needs for resources. To also accommodate resource-supply processes in PADS, given a resource cpu, we write cpū to denote the availability of cpu for a requesting task process. Using PADS, we define a supply-demand relation where a pair (T,S) belongs to the relation if the demand process T can be scheduled under supply S. We develop a theory of compositional schedulability analysis as well as a technique for synthesizing an optimal supply process for a set of tasks. Furthermore, we define ordering relations between supplies which describe when a supply offers more resource capacity than another. With this notion it is possible to formally represent hierarchical scheduling approaches that assign more "generous" resource allocations to tasks in exchange for a simple representation. We illustrate our techniques via a number of examples. © 2011 Elsevier B.V. All rights reserved. | en |
dc.source | Theoretical Computer Science | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-81955160716&doi=10.1016%2fj.tcs.2011.08.025&partnerID=40&md5=47c2dfbb47f6725310cee7d16d0bedb2 | |
dc.subject | Ecology | en |
dc.subject | Algebra | en |
dc.subject | Real time systems | en |
dc.subject | Hierarchical systems | en |
dc.subject | Scheduling | en |
dc.subject | Resource capacity | en |
dc.subject | Embedded systems | en |
dc.subject | Real time performance | en |
dc.subject | Real-time embedded systems | en |
dc.subject | Formal analysis | en |
dc.subject | Schedulability analysis | en |
dc.subject | Real-time process algebra | en |
dc.subject | Algebraic framework | en |
dc.subject | Compositional schedulability analysis | en |
dc.subject | Hierarchical scheduling | en |
dc.subject | Ordering relations | en |
dc.subject | Real time scheduling | en |
dc.subject | Real-time tasks | en |
dc.subject | Resource demand and resource supply | en |
dc.subject | Resource demands | en |
dc.subject | Resource partitioning | en |
dc.subject | Supply process | en |
dc.subject | Supply-demand relation | en |
dc.subject | Task process | en |
dc.subject | Timed process algebra | en |
dc.title | PADS: An approach to modeling resource demand and supply for the formal analysis of hierarchical scheduling | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1016/j.tcs.2011.08.025 | |
dc.description.volume | 413 | |
dc.description.issue | 1 | |
dc.description.startingpage | 2 | |
dc.description.endingpage | 20 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :6</p> | en |
dc.source.abbreviation | Theor.Comput.Sci. | en |