Please use this identifier to cite or link to this item:
Title: Flow network models for online scheduling real-time tasks on multiprocessors
Authors: Cho, Hyeonjoong
Easwaran, Arvind
Keywords: Engineering::Computer science and engineering
Issue Date: 2020
Source: 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
Journal: IEEE Access 
Abstract: 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.
ISSN: 2169-3536
DOI: 10.1109/ACCESS.2020.3024692
Rights: © 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.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Journal Articles

Files in This Item:
File Description SizeFormat 
09199814.pdf1.15 MBAdobe PDFView/Open

Page view(s)

Updated on May 15, 2022


Updated on May 15, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.