A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays
In multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have b...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
2014-04-01
|
| Series: | Leibniz Transactions on Embedded Systems |
| Subjects: | |
| Online Access: | https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue001/LITES-v001-i001-a001/LITES-v001-i001-a001.pdf |
| _version_ | 1797208351968329728 |
|---|---|
| author | Lunniss, Will Altmeyer, Sebastian Davis, Robert I. |
| author_facet | Lunniss, Will Altmeyer, Sebastian Davis, Robert I. |
| author_sort | Lunniss, Will |
| collection | DOAJ |
| description | In multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have been studied in great detail before, they have not been compared when taking into account cache related pre-emption delays (CRPD). Memory and cache are split into a number of blocks containing instructions and data. During a pre-emption, cache blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicted blocks, CRPD are introduced which then affect the schedulability of the task. In this paper we compare FP and EDF scheduling algorithms in the presence of CRPD using the state-of-the-art CRPD analysis. We find that when CRPD is accounted for, the performance gains offered by EDF over FP, while still notable, are diminished. Furthermore, we find that under scenarios that cause relatively high CRPD, task layout optimisation techniques can be applied to allow FP to schedule tasksets at a similar processor utilisation to EDF. Thus making the choice of the task layout in memory as important as the choice of scheduling algorithm. This is very relevant for industry, as it is much cheaper and simpler to adjust the task layout through the linker than it is to switch the scheduling algorithm. |
| first_indexed | 2024-04-24T09:37:26Z |
| format | Article |
| id | doaj.art-560bdf8096da439ca801752d404f154f |
| institution | Directory Open Access Journal |
| issn | 2199-2002 |
| language | English |
| last_indexed | 2024-04-24T09:37:26Z |
| publishDate | 2014-04-01 |
| publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| record_format | Article |
| series | Leibniz Transactions on Embedded Systems |
| spelling | doaj.art-560bdf8096da439ca801752d404f154f2024-04-15T07:55:19ZengSchloss Dagstuhl -- Leibniz-Zentrum fuer InformatikLeibniz Transactions on Embedded Systems2199-20022014-04-011101:101:2410.4230/LITES-v001-i001-a0012A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption DelaysLunniss, Will0Altmeyer, Sebastian1Davis, Robert I.2University of YorkUniversity of AmsterdamUniversity of YorkIn multitasking real-time systems, the choice of scheduling algorithm is an important factor to ensure that response time requirements are met while maximising limited system resources. Two popular scheduling algorithms include fixed priority (FP) and earliest deadline first (EDF). While they have been studied in great detail before, they have not been compared when taking into account cache related pre-emption delays (CRPD). Memory and cache are split into a number of blocks containing instructions and data. During a pre-emption, cache blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicted blocks, CRPD are introduced which then affect the schedulability of the task. In this paper we compare FP and EDF scheduling algorithms in the presence of CRPD using the state-of-the-art CRPD analysis. We find that when CRPD is accounted for, the performance gains offered by EDF over FP, while still notable, are diminished. Furthermore, we find that under scenarios that cause relatively high CRPD, task layout optimisation techniques can be applied to allow FP to schedule tasksets at a similar processor utilisation to EDF. Thus making the choice of the task layout in memory as important as the choice of scheduling algorithm. This is very relevant for industry, as it is much cheaper and simpler to adjust the task layout through the linker than it is to switch the scheduling algorithm.https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue001/LITES-v001-i001-a001/LITES-v001-i001-a001.pdfreal-time systemsfixed priorityedfpre-emptive schedulingcache related pre-emption delays |
| spellingShingle | Lunniss, Will Altmeyer, Sebastian Davis, Robert I. A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays Leibniz Transactions on Embedded Systems real-time systems fixed priority edf pre-emptive scheduling cache related pre-emption delays |
| title | A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays |
| title_full | A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays |
| title_fullStr | A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays |
| title_full_unstemmed | A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays |
| title_short | A Comparison between Fixed Priority and EDF Scheduling accounting for Cache Related Pre-emption Delays |
| title_sort | comparison between fixed priority and edf scheduling accounting for cache related pre emption delays |
| topic | real-time systems fixed priority edf pre-emptive scheduling cache related pre-emption delays |
| url | https://drops.dagstuhl.de/storage/07lites/lites_vol001/lites_vol001_issue001/LITES-v001-i001-a001/LITES-v001-i001-a001.pdf |
| work_keys_str_mv | AT lunnisswill acomparisonbetweenfixedpriorityandedfschedulingaccountingforcacherelatedpreemptiondelays AT altmeyersebastian acomparisonbetweenfixedpriorityandedfschedulingaccountingforcacherelatedpreemptiondelays AT davisroberti acomparisonbetweenfixedpriorityandedfschedulingaccountingforcacherelatedpreemptiondelays AT lunnisswill comparisonbetweenfixedpriorityandedfschedulingaccountingforcacherelatedpreemptiondelays AT altmeyersebastian comparisonbetweenfixedpriorityandedfschedulingaccountingforcacherelatedpreemptiondelays AT davisroberti comparisonbetweenfixedpriorityandedfschedulingaccountingforcacherelatedpreemptiondelays |