Flow Network Models for Online Scheduling Real-Time Tasks on Multiprocessors
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cho, Hyeonjoong | - |
dc.contributor.author | Easwaran, Arvind | - |
dc.date.accessioned | 2021-08-31T16:16:26Z | - |
dc.date.available | 2021-08-31T16:16:26Z | - |
dc.date.created | 2021-06-18 | - |
dc.date.issued | 2020 | - |
dc.identifier.issn | 2169-3536 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/59078 | - |
dc.description.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. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | - |
dc.subject | ALGORITHM | - |
dc.title | Flow Network Models for Online Scheduling Real-Time Tasks on Multiprocessors | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Cho, Hyeonjoong | - |
dc.identifier.doi | 10.1109/ACCESS.2020.3024692 | - |
dc.identifier.scopusid | 2-s2.0-85102815359 | - |
dc.identifier.wosid | 000575906800001 | - |
dc.identifier.bibliographicCitation | IEEE ACCESS, v.8, pp.172136 - 172151 | - |
dc.relation.isPartOf | IEEE ACCESS | - |
dc.citation.title | IEEE ACCESS | - |
dc.citation.volume | 8 | - |
dc.citation.startPage | 172136 | - |
dc.citation.endPage | 172151 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Engineering | - |
dc.relation.journalResearchArea | Telecommunications | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Information Systems | - |
dc.relation.journalWebOfScienceCategory | Engineering, Electrical & Electronic | - |
dc.relation.journalWebOfScienceCategory | Telecommunications | - |
dc.subject.keywordPlus | ALGORITHM | - |
dc.subject.keywordAuthor | Task analysis | - |
dc.subject.keywordAuthor | Schedules | - |
dc.subject.keywordAuthor | Program processors | - |
dc.subject.keywordAuthor | Processor scheduling | - |
dc.subject.keywordAuthor | Optimal scheduling | - |
dc.subject.keywordAuthor | Real-time systems | - |
dc.subject.keywordAuthor | Scheduling | - |
dc.subject.keywordAuthor | Flow networks | - |
dc.subject.keywordAuthor | maximum flow problem | - |
dc.subject.keywordAuthor | minimum cost flow problem | - |
dc.subject.keywordAuthor | multicores | - |
dc.subject.keywordAuthor | multiprocessors | - |
dc.subject.keywordAuthor | real-time scheduling | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
(02841) 서울특별시 성북구 안암로 14502-3290-1114
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.