Time-Reversibility for Real-Time Scheduling on Multiprocessor Systems
| Autor: | Jinkyu Lee |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Rate-monotonic scheduling
Earliest deadline first scheduling 020203 distributed computing Least slack time scheduling Computer science Distributed computing Multiprocessing 02 engineering and technology Dynamic priority scheduling Flow shop scheduling Round-robin scheduling Gang scheduling Fair-share scheduling Deadline-monotonic scheduling Multiprocessor scheduling Stride scheduling 020202 computer hardware & architecture Scheduling (computing) Fixed-priority pre-emptive scheduling Computational Theory and Mathematics Hardware and Architecture Two-level scheduling Signal Processing Lottery scheduling 0202 electrical engineering electronic engineering information engineering |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 28:230-243 |
| ISSN: | 1045-9219 |
| DOI: | 10.1109/tpds.2016.2533615 |
| Popis: | The real-time systems community has widely studied real-time scheduling, focusing on how to guarantee schedulability (i.e., timely execution) of a set of real-time tasks. However, there still exist a number of task sets that are actually schedulable by a target scheduling algorithm, but proven schedulable by none of existing schedulability tests, especially on a multiprocessor. In this paper, we propose a new paradigm for real-time scheduling, called time-reversibility , which views real-time scheduling under a change in the sign of time , and present how to utilize the paradigm for schedulability improvement. To this end, we first define the notion of a time-reversed scheduling algorithm and a time-reversible schedulability test ; for example, the time-reversed scheduling algorithm against Earliest Deadline First (EDF) is Latest Release-time First (LRF). Then, we develop time-reversibility theories for schedulability improvement, which utilizes the definitions so as to compose schedulability . Finally, we generalize the definitions and theories to job-level dynamic-priority scheduling in which the priority of a job may vary with time, such as Earliest Deadline first until Zero Laxity (EDZL). Specifically, we accommodate time-varying job parameters to the time-reversibility definitions, and adapt the time-reversibility theories for the additional necessary deadline-miss conditions specialized for a class of job-level dynamic-priority scheduling algorithms. As case studies, we demonstrate that the time-reversibility theories help to find up to 13.6 percent additional EDF- and EDZL-schedulable task sets. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|