The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Une tâche qui s'interrompt pour attendre la fin d'une E/S ou pour attendre un événement provenant d'un autre nœud dans des environnements distribués est appelée tâche de blocage d'E/S. Les théories conventionnelles de planification en temps réel utilisent un cadre d'analyse monotone de débit (RMA) pour planifier de telles tâches de blocage d'E/S. Mais la plupart d’entre eux sont pessimistes. Dans cet article, nous proposons des algorithmes efficaces capables de planifier un ensemble de tâches comportant des tâches de blocage d'E/S sous attribution de priorité dynamique. Nous présentons un nouveau théorème de l'instant critique pour la tâche multi-trame définie sous assignation de priorité dynamique. L'ordonnabilité est analysée selon le nouveau théorème de l'instant critique. Pour l'analyse de l'ordonnabilité, cet article présente la sommation de saturation qui est utilisée pour calculer la fonction d'interférence maximale (MIF). Grâce à la sommation à saturation, la programmabilité d'un ensemble de tâches comportant des tâches de blocage d'E/S peut être analysée avec plus de précision. Nous proposons un algorithme appelé Frame Laxity Monotonic Scheduling (FLMS). Un algorithme génétique (GA) est également appliqué. De nos expériences, nous pouvons conclure que FLMS peut réduire considérablement le temps de calcul et que GA peut améliorer le taux de planification des tâches plus que ce qui est possible avec FLMS.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Shan DING, Hiroyuki TOMIYAMA, Hiroaki TAKADA, "Effective Scheduling Algorithms for I/O Blocking with a Multi-Frame Task Model" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 7, pp. 1412-1420, July 2009, doi: 10.1587/transinf.E92.D.1412.
Abstract: A task that suspends itself to wait for an I/O completion or to wait for an event from another node in distributed environments is called an I/O blocking task. Conventional hard real-time scheduling theories use framework of rate monotonic analysis (RMA) to schedule such I/O blocking tasks. However, most of them are pessimistic. In this paper, we propose effective algorithms that can schedule a task set which has I/O blocking tasks under dynamic priority assignment. We present a new critical instant theorem for the multi-frame task set under dynamic priority assignment. The schedulability is analyzed under the new critical instant theorem. For the schedulability analysis, this paper presents saturation summation which is used to calculate the maximum interference function (MIF). With saturation summation, the schedulability of a task set having I/O blocking tasks can be analyzed more accurately. We propose an algorithm which is called Frame Laxity Monotonic Scheduling (FLMS). A genetic algorithm (GA) is also applied. From our experiments, we can conclude that FLMS can significantly reduce the calculation time, and GA can improve task schedulability ratio more than is possible with FLMS.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.1412/_p
Copier
@ARTICLE{e92-d_7_1412,
author={Shan DING, Hiroyuki TOMIYAMA, Hiroaki TAKADA, },
journal={IEICE TRANSACTIONS on Information},
title={Effective Scheduling Algorithms for I/O Blocking with a Multi-Frame Task Model},
year={2009},
volume={E92-D},
number={7},
pages={1412-1420},
abstract={A task that suspends itself to wait for an I/O completion or to wait for an event from another node in distributed environments is called an I/O blocking task. Conventional hard real-time scheduling theories use framework of rate monotonic analysis (RMA) to schedule such I/O blocking tasks. However, most of them are pessimistic. In this paper, we propose effective algorithms that can schedule a task set which has I/O blocking tasks under dynamic priority assignment. We present a new critical instant theorem for the multi-frame task set under dynamic priority assignment. The schedulability is analyzed under the new critical instant theorem. For the schedulability analysis, this paper presents saturation summation which is used to calculate the maximum interference function (MIF). With saturation summation, the schedulability of a task set having I/O blocking tasks can be analyzed more accurately. We propose an algorithm which is called Frame Laxity Monotonic Scheduling (FLMS). A genetic algorithm (GA) is also applied. From our experiments, we can conclude that FLMS can significantly reduce the calculation time, and GA can improve task schedulability ratio more than is possible with FLMS.},
keywords={},
doi={10.1587/transinf.E92.D.1412},
ISSN={1745-1361},
month={July},}
Copier
TY - JOUR
TI - Effective Scheduling Algorithms for I/O Blocking with a Multi-Frame Task Model
T2 - IEICE TRANSACTIONS on Information
SP - 1412
EP - 1420
AU - Shan DING
AU - Hiroyuki TOMIYAMA
AU - Hiroaki TAKADA
PY - 2009
DO - 10.1587/transinf.E92.D.1412
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2009
AB - A task that suspends itself to wait for an I/O completion or to wait for an event from another node in distributed environments is called an I/O blocking task. Conventional hard real-time scheduling theories use framework of rate monotonic analysis (RMA) to schedule such I/O blocking tasks. However, most of them are pessimistic. In this paper, we propose effective algorithms that can schedule a task set which has I/O blocking tasks under dynamic priority assignment. We present a new critical instant theorem for the multi-frame task set under dynamic priority assignment. The schedulability is analyzed under the new critical instant theorem. For the schedulability analysis, this paper presents saturation summation which is used to calculate the maximum interference function (MIF). With saturation summation, the schedulability of a task set having I/O blocking tasks can be analyzed more accurately. We propose an algorithm which is called Frame Laxity Monotonic Scheduling (FLMS). A genetic algorithm (GA) is also applied. From our experiments, we can conclude that FLMS can significantly reduce the calculation time, and GA can improve task schedulability ratio more than is possible with FLMS.
ER -