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: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9199814/ |
| _version_ | 1818446692713758720 |
|---|---|
| author | Hyeonjoong Cho Arvind Easwaran |
| author_facet | Hyeonjoong Cho Arvind Easwaran |
| author_sort | Hyeonjoong Cho |
| collection | DOAJ |
| 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 | 2024-12-14T19:51:46Z |
| format | Article |
| id | doaj.art-3bf50be579ce49bc919ffca94fd692c6 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-14T19:51:46Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-3bf50be579ce49bc919ffca94fd692c62022-12-21T22:49:23ZengIEEEIEEE Access2169-35362020-01-01817213617215110.1109/ACCESS.2020.30246929199814Flow Network Models for Online Scheduling Real-Time Tasks on MultiprocessorsHyeonjoong Cho0https://orcid.org/0000-0003-1487-895XArvind Easwaran1https://orcid.org/0000-0002-9628-3847Department of Computer and Information Science, Korea University, Sejong, South KoreaSchool of Computer Engineering, Nanyang Technological University, SingaporeWe 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.https://ieeexplore.ieee.org/document/9199814/Flow networksmaximum flow problemminimum cost flow problemmulticoresmultiprocessorsreal-time scheduling |
| spellingShingle | Hyeonjoong Cho Arvind Easwaran Flow Network Models for Online Scheduling Real-Time Tasks on Multiprocessors IEEE Access Flow networks maximum flow problem minimum cost flow problem multicores multiprocessors real-time scheduling |
| 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 | Flow networks maximum flow problem minimum cost flow problem multicores multiprocessors real-time scheduling |
| url | https://ieeexplore.ieee.org/document/9199814/ |
| work_keys_str_mv | AT hyeonjoongcho flownetworkmodelsforonlineschedulingrealtimetasksonmultiprocessors AT arvindeaswaran flownetworkmodelsforonlineschedulingrealtimetasksonmultiprocessors |