Composition of Schedulability Analyses for Real-Time Multiprocessor Systems
With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2018
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/89363 http://hdl.handle.net/10220/44848 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-89363 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-893632020-03-07T11:49:00Z Composition of Schedulability Analyses for Real-Time Multiprocessor Systems Lee, Jinkyu Shin, Kang G. Shin, Insik Easwaran, Arvind School of Computer Science and Engineering Real-time Scheduling Composition Of Schedulability Analyses With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms often comes with several different schedulability tests, especially when it is difficult to find exact schedulability tests for the algorithm. Such tests usually find different task sets deemed schedulable even under the same scheduling algorithm. While these different tests have been compared with each other in terms of schedulability performance, little has been done on how to combine such different tests to improve the overall schedulability of a given scheduling algorithm beyond a simple union of their individual schedulability. Motivated by this, we propose a composition theory for schedulability tests with two new methods. The first method composes task-level timing guarantees derived from different schedulability tests, and the second one derives system-level schedulability results from a single schedulability test. The unified composition theory with these two methods then utilizes existing schedulability tests effectively so as to cover additional schedulable task sets. The proposed composition theory is shown to be applicable to most existing preemptive/non-preemptive scheduling algorithms. We also present three case-studies, demonstrating how and by how much the theory can improve schedulability by composing existing schedulability tests. Our evaluation results also show that the composition theory makes it possible to cover up to 181.7 percent additional schedulable task sets for preemptive fpEDF, preemptive EDF and non-preemptive EDF scheduling algorithms beyond their existing tests. MOE (Min. of Education, S’pore) Accepted version 2018-05-21T08:15:44Z 2019-12-06T17:23:52Z 2018-05-21T08:15:44Z 2019-12-06T17:23:52Z 2014 Journal Article Lee, J., Shin, K. G., Shin, I., & Easwaran, A. (2015). Composition of Schedulability Analyses for Real-Time Multiprocessor Systems. IEEE Transactions on Computers, 64(4), 941-954. 0018-9340 https://hdl.handle.net/10356/89363 http://hdl.handle.net/10220/44848 10.1109/TC.2014.2308183 en IEEE Transactions on Computers © 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/TC.2014.2308183]. 14 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Real-time Scheduling Composition Of Schedulability Analyses |
spellingShingle |
Real-time Scheduling Composition Of Schedulability Analyses Lee, Jinkyu Shin, Kang G. Shin, Insik Easwaran, Arvind Composition of Schedulability Analyses for Real-Time Multiprocessor Systems |
description |
With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms often comes with several different schedulability tests, especially when it is difficult to find exact schedulability tests for the algorithm. Such tests usually find different task sets deemed schedulable even under the same scheduling algorithm. While these different tests have been compared with each other in terms of schedulability performance, little has been done on how to combine such different tests to improve the overall schedulability of a given scheduling algorithm beyond a simple union of their individual schedulability. Motivated by this, we propose a composition theory for schedulability tests with two new methods. The first method composes task-level timing guarantees derived from different schedulability tests, and the second one derives system-level schedulability results from a single schedulability test. The unified composition theory with these two methods then utilizes existing schedulability tests effectively so as to cover additional schedulable task sets. The proposed composition theory is shown to be applicable to most existing preemptive/non-preemptive scheduling algorithms. We also present three case-studies, demonstrating how and by how much the theory can improve schedulability by composing existing schedulability tests. Our evaluation results also show that the composition theory makes it possible to cover up to 181.7 percent additional schedulable task sets for preemptive fpEDF, preemptive EDF and non-preemptive EDF scheduling algorithms beyond their existing tests. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering Lee, Jinkyu Shin, Kang G. Shin, Insik Easwaran, Arvind |
format |
Article |
author |
Lee, Jinkyu Shin, Kang G. Shin, Insik Easwaran, Arvind |
author_sort |
Lee, Jinkyu |
title |
Composition of Schedulability Analyses for Real-Time Multiprocessor Systems |
title_short |
Composition of Schedulability Analyses for Real-Time Multiprocessor Systems |
title_full |
Composition of Schedulability Analyses for Real-Time Multiprocessor Systems |
title_fullStr |
Composition of Schedulability Analyses for Real-Time Multiprocessor Systems |
title_full_unstemmed |
Composition of Schedulability Analyses for Real-Time Multiprocessor Systems |
title_sort |
composition of schedulability analyses for real-time multiprocessor systems |
publishDate |
2018 |
url |
https://hdl.handle.net/10356/89363 http://hdl.handle.net/10220/44848 |
_version_ |
1681044118765043712 |