Optimal Scheduling of Periodic Gang Tasks
The gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every in...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
2016-06-01
|
| Series: | Leibniz Transactions on Embedded Systems |
| Subjects: | |
| Online Access: | https://drops.dagstuhl.de/storage/07lites/lites_vol003/lites_vol003_issue001/LITES-v003-i001-a004/LITES-v003-i001-a004.pdf |
| _version_ | 1797208370162171904 |
|---|---|
| author | Goossens, Joël Richard, Pascal |
| author_facet | Goossens, Joël Richard, Pascal |
| author_sort | Goossens, Joël |
| collection | DOAJ |
| description | The gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every interval of time delimited by two subsequent deadlines. These algorithms define a static schedule pattern that is stretched at run-time in every interval of the DPFAIR schedule. The first algorithm is based on linear programming and is the first one to be proved optimal for the considered gang scheduling problem. Furthermore, it runs in polynomial time for a fixed number m of processors and an efficient implementation is fully detailed. The second algorithm is an approximation algorithm based on a fixed-priority rule that is competitive under resource augmentation analysis in order to compute an optimal schedule pattern. Precisely, its speedup factor is bounded by (2-1/m). Both algorithms are also evaluated through intensive numerical experiments. |
| first_indexed | 2024-04-24T09:37:43Z |
| format | Article |
| id | doaj.art-815ff9bf89ce44fcbd5971adca4d1981 |
| institution | Directory Open Access Journal |
| issn | 2199-2002 |
| language | English |
| last_indexed | 2024-04-24T09:37:43Z |
| publishDate | 2016-06-01 |
| publisher | Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik |
| record_format | Article |
| series | Leibniz Transactions on Embedded Systems |
| spelling | doaj.art-815ff9bf89ce44fcbd5971adca4d19812024-04-15T07:51:14ZengSchloss Dagstuhl -- Leibniz-Zentrum fuer InformatikLeibniz Transactions on Embedded Systems2199-20022016-06-013104:104:1810.4230/LITES-v003-i001-a004Optimal Scheduling of Periodic Gang TasksGoossens, Joël0Richard, Pascal1Université Libre de Bruxelles (ULB), 50 av. F.D. Roosevelt 1050 Brussels, BelgiumLIAS/Isae-Ensma-Université de Poitiers, 1 av. Clément Ader, BP 40109, 86961 Chasseneuil du Poitou, FranceThe gang scheduling of parallel implicit-deadline periodic task systems upon identical multiprocessor platforms is considered. In this scheduling problem, parallel tasks use several processors simultaneously. We propose two DPFAIR (deadline partitioning) algorithms that schedule all jobs in every interval of time delimited by two subsequent deadlines. These algorithms define a static schedule pattern that is stretched at run-time in every interval of the DPFAIR schedule. The first algorithm is based on linear programming and is the first one to be proved optimal for the considered gang scheduling problem. Furthermore, it runs in polynomial time for a fixed number m of processors and an efficient implementation is fully detailed. The second algorithm is an approximation algorithm based on a fixed-priority rule that is competitive under resource augmentation analysis in order to compute an optimal schedule pattern. Precisely, its speedup factor is bounded by (2-1/m). Both algorithms are also evaluated through intensive numerical experiments.https://drops.dagstuhl.de/storage/07lites/lites_vol003/lites_vol003_issue001/LITES-v003-i001-a004/LITES-v003-i001-a004.pdfreal-time systemsschedulingparallel tasks |
| spellingShingle | Goossens, Joël Richard, Pascal Optimal Scheduling of Periodic Gang Tasks Leibniz Transactions on Embedded Systems real-time systems scheduling parallel tasks |
| title | Optimal Scheduling of Periodic Gang Tasks |
| title_full | Optimal Scheduling of Periodic Gang Tasks |
| title_fullStr | Optimal Scheduling of Periodic Gang Tasks |
| title_full_unstemmed | Optimal Scheduling of Periodic Gang Tasks |
| title_short | Optimal Scheduling of Periodic Gang Tasks |
| title_sort | optimal scheduling of periodic gang tasks |
| topic | real-time systems scheduling parallel tasks |
| url | https://drops.dagstuhl.de/storage/07lites/lites_vol003/lites_vol003_issue001/LITES-v003-i001-a004/LITES-v003-i001-a004.pdf |
| work_keys_str_mv | AT goossensjoel optimalschedulingofperiodicgangtasks AT richardpascal optimalschedulingofperiodicgangtasks |