Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems
In hard real-time task systems where periodic and aperiodic tasks coexist, the object of task scheduling is to reduce the response time of the aperiodic tasks while meeting the deadline of periodic tasks. Total bandwidth server (TBS) and advanced TBS (ATBS) are used in dynamic priority systems. Howe...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-11-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/8/11/1286 |
| _version_ | 1798034953220390912 |
|---|---|
| author | Wonbo Jeon Wonsop Kim Heoncheol Lee Cheol-Hoon Lee |
| author_facet | Wonbo Jeon Wonsop Kim Heoncheol Lee Cheol-Hoon Lee |
| author_sort | Wonbo Jeon |
| collection | DOAJ |
| description | In hard real-time task systems where periodic and aperiodic tasks coexist, the object of task scheduling is to reduce the response time of the aperiodic tasks while meeting the deadline of periodic tasks. Total bandwidth server (TBS) and advanced TBS (ATBS) are used in dynamic priority systems. However, these methods are not optimal solutions because they use the worst-case execution time (WCET) or the estimation value of the actual execution time of the aperiodic tasks. This paper presents an online slack-stealing algorithm called SSML that can make significant response time reducing by modification of look-ahead earliest deadline first (laEDF) algorithm as the slack computation method. While the conventional slack-stealing method has a disadvantage that the slack amount of each frame must be calculated in advance, SSML calculates the slack when aperiodic tasks arrive. Our simulation results show that SSML outperforms the existing TBS based algorithms when the periodic task utilization is higher than 60%. Compared to ATBS with virtual release advancing (VRA), the proposed algorithm can reduce the response time up to about 75%. The performance advantage becomes much larger as the utilization increases. Moreover, it shows a small performance variation of response time for various task environments. |
| first_indexed | 2024-04-11T20:50:33Z |
| format | Article |
| id | doaj.art-ee802fc24bdc4565ba3404295807033e |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-04-11T20:50:33Z |
| publishDate | 2019-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-ee802fc24bdc4565ba3404295807033e2022-12-22T04:03:51ZengMDPI AGElectronics2079-92922019-11-01811128610.3390/electronics8111286electronics8111286Online Slack-Stealing Scheduling with Modified laEDF in Real-Time SystemsWonbo Jeon0Wonsop Kim1Heoncheol Lee2Cheol-Hoon Lee3Agency for Defense Development, P.O. Box 35, Yuseong, Daejeon 34134, KoreaAgency for Defense Development, P.O. Box 35, Yuseong, Daejeon 34134, KoreaSchool of Electronic Engineering, Kumoh National Institute of Technology, 61 Daehak-ro, Gumi, Gyeongbuk 39177, KoreaDepartment of Computer Science & Engineering, ChungNam National University, 99 Daehak-ro, Yuseong-gu, Daejeon 34134, KoreaIn hard real-time task systems where periodic and aperiodic tasks coexist, the object of task scheduling is to reduce the response time of the aperiodic tasks while meeting the deadline of periodic tasks. Total bandwidth server (TBS) and advanced TBS (ATBS) are used in dynamic priority systems. However, these methods are not optimal solutions because they use the worst-case execution time (WCET) or the estimation value of the actual execution time of the aperiodic tasks. This paper presents an online slack-stealing algorithm called SSML that can make significant response time reducing by modification of look-ahead earliest deadline first (laEDF) algorithm as the slack computation method. While the conventional slack-stealing method has a disadvantage that the slack amount of each frame must be calculated in advance, SSML calculates the slack when aperiodic tasks arrive. Our simulation results show that SSML outperforms the existing TBS based algorithms when the periodic task utilization is higher than 60%. Compared to ATBS with virtual release advancing (VRA), the proposed algorithm can reduce the response time up to about 75%. The performance advantage becomes much larger as the utilization increases. Moreover, it shows a small performance variation of response time for various task environments.https://www.mdpi.com/2079-9292/8/11/1286ssmlslack computationaperiodic task schedulingmixed task systemslack-stealing |
| spellingShingle | Wonbo Jeon Wonsop Kim Heoncheol Lee Cheol-Hoon Lee Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems Electronics ssml slack computation aperiodic task scheduling mixed task system slack-stealing |
| title | Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems |
| title_full | Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems |
| title_fullStr | Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems |
| title_full_unstemmed | Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems |
| title_short | Online Slack-Stealing Scheduling with Modified laEDF in Real-Time Systems |
| title_sort | online slack stealing scheduling with modified laedf in real time systems |
| topic | ssml slack computation aperiodic task scheduling mixed task system slack-stealing |
| url | https://www.mdpi.com/2079-9292/8/11/1286 |
| work_keys_str_mv | AT wonbojeon onlineslackstealingschedulingwithmodifiedlaedfinrealtimesystems AT wonsopkim onlineslackstealingschedulingwithmodifiedlaedfinrealtimesystems AT heoncheollee onlineslackstealingschedulingwithmodifiedlaedfinrealtimesystems AT cheolhoonlee onlineslackstealingschedulingwithmodifiedlaedfinrealtimesystems |