Flow network models for online scheduling real-time tasks on multiprocessors
We consider the flow network model to solve the multiprocessor real-time task scheduling problems. Using the flow network model or its generic form, linear programming (LP) formulation, for the problems is not new. However, the previous works have limitations, for example, that they are classified a...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145816 |
| _version_ | 1824453983935135744 |
|---|---|
| author | Cho, Hyeonjoong Easwaran, Arvind |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Cho, Hyeonjoong Easwaran, Arvind |
| author_sort | Cho, Hyeonjoong |
| collection | NTU |
| description | We consider the flow network model to solve the multiprocessor real-time task scheduling problems. Using the flow network model or its generic form, linear programming (LP) formulation, for the problems is not new. However, the previous works have limitations, for example, that they are classified as offline scheduling techniques since they establish a flow network model or an LP problem considering a very long time interval. In this study, we propose how to construct the flow network model for online scheduling periodic real-time tasks on multiprocessors. Our key idea is to construct the flow network only for the active instances of tasks at the current scheduling time, while guaranteeing the existence of an optimal schedule for the future instances of the tasks. The optimal scheduling is here defined to ensure that all real-time tasks meet their deadlines when the total utilization demand of the given tasks does not exceed the total processing capacity. We then propose the flow network model-based polynomial-time scheduling algorithms. Advantageously, the flow network model allows the task workload to be collected unfairly within a certain time interval without losing the optimality. It thus leads us to designing three unfair-but-optimal scheduling algorithms on both continuous and discrete-time models. Especially, our unfair-but-optimal scheduling algorithm on a discrete-time model is, to the best of our knowledge, the first in the problem domain. We experimentally demonstrate that it significantly alleviates the scheduling overheads, i.e., the reduced number of preemptions with the comparable number of task migrations across processors, in comparison with an existing algorithm on the discrete-time model. |
| first_indexed | 2025-02-19T03:15:05Z |
| format | Journal Article |
| id | ntu-10356/145816 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:15:05Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1458162021-01-08T08:41:34Z Flow network models for online scheduling real-time tasks on multiprocessors Cho, Hyeonjoong Easwaran, Arvind School of Computer Science and Engineering Engineering::Computer science and engineering Flow Networks Maximum Flow Problem We consider the flow network model to solve the multiprocessor real-time task scheduling problems. Using the flow network model or its generic form, linear programming (LP) formulation, for the problems is not new. However, the previous works have limitations, for example, that they are classified as offline scheduling techniques since they establish a flow network model or an LP problem considering a very long time interval. In this study, we propose how to construct the flow network model for online scheduling periodic real-time tasks on multiprocessors. Our key idea is to construct the flow network only for the active instances of tasks at the current scheduling time, while guaranteeing the existence of an optimal schedule for the future instances of the tasks. The optimal scheduling is here defined to ensure that all real-time tasks meet their deadlines when the total utilization demand of the given tasks does not exceed the total processing capacity. We then propose the flow network model-based polynomial-time scheduling algorithms. Advantageously, the flow network model allows the task workload to be collected unfairly within a certain time interval without losing the optimality. It thus leads us to designing three unfair-but-optimal scheduling algorithms on both continuous and discrete-time models. Especially, our unfair-but-optimal scheduling algorithm on a discrete-time model is, to the best of our knowledge, the first in the problem domain. We experimentally demonstrate that it significantly alleviates the scheduling overheads, i.e., the reduced number of preemptions with the comparable number of task migrations across processors, in comparison with an existing algorithm on the discrete-time model. Published version 2021-01-08T08:41:34Z 2021-01-08T08:41:34Z 2020 Journal Article Cho, H., & Easwaran, A. (2020). Flow network models for online scheduling real-time tasks on multiprocessors. IEEE Access, 8, 172136-172151. doi:10.1109/ACCESS.2020.3024692 2169-3536 https://hdl.handle.net/10356/145816 10.1109/ACCESS.2020.3024692 8 172136 172151 en IEEE Access © 2020 IEEE. This journal is 100% open access, which means that all content is freely available without charge to users or their institutions. All articles accepted after 12 June 2019 are published under a CC BY 4.0 license, and the author retains copyright. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, as long as proper attribution is given. application/pdf |
| spellingShingle | Engineering::Computer science and engineering Flow Networks Maximum Flow Problem Cho, Hyeonjoong Easwaran, Arvind Flow network models for online scheduling real-time tasks on multiprocessors |
| title | Flow network models for online scheduling real-time tasks on multiprocessors |
| title_full | Flow network models for online scheduling real-time tasks on multiprocessors |
| title_fullStr | Flow network models for online scheduling real-time tasks on multiprocessors |
| title_full_unstemmed | Flow network models for online scheduling real-time tasks on multiprocessors |
| title_short | Flow network models for online scheduling real-time tasks on multiprocessors |
| title_sort | flow network models for online scheduling real time tasks on multiprocessors |
| topic | Engineering::Computer science and engineering Flow Networks Maximum Flow Problem |
| url | https://hdl.handle.net/10356/145816 |
| work_keys_str_mv | AT chohyeonjoong flownetworkmodelsforonlineschedulingrealtimetasksonmultiprocessors AT easwaranarvind flownetworkmodelsforonlineschedulingrealtimetasksonmultiprocessors |