Fonction temps-utilité
Le paradigme TUF/UA a été créé à l’origine pour répondre à certains besoins d’ordonnancement basés sur les délais et la qualité de service des applications de diverses applications militaires pour lesquelles les concepts et pratiques en temps réel traditionnels ne sont pas suffisamment expressifs (par exemple, pour les systèmes critiques en termes de délais qui n’ont pas de dates limites) et résilients (par exemple, pour les systèmes soumis à des surcharges de routine). Une classe d’exemple de telles applications est la défense contre les missiles balistiques (notionnellement).
Par la suite, de nombreuses variations du modèle original TUF, du modèle de système du paradigme TUF/UA, et donc des techniques d’ordonnancement, ont été étudiées dans la littérature académique – par ex,-et appliquées dans des contextes civils.
Ces dernières comprennent notamment : les systèmes cyber-physiques, l’IA, les systèmes multi-robots, l’ordonnancement des drones, les robots autonomes, les transferts de données de véhicules intelligents vers le cloud, le contrôle des processus industriels, les systèmes transactionnels, le calcul haute performance, les systèmes de cloud, les clusters hétérogènes, le calcul orienté services, la mise en réseau et la gestion de la mémoire pour les machines réelles et virtuelles. Un exemple d’aciérie est brièvement décrit dans l’introduction de la thèse de doctorat de Clark. Les informations sur les instances commerciales ou militaires du paradigme peuvent être inaccessibles au public (propriétaires ou classifiées, respectivement).
Les UTF et leurs interprétations de l’utilité (sémantique), leurs échelles et leurs valeurs sont dérivées de la connaissance du sujet spécifique au domaine. Une interprétation historiquement fréquente de l’utilité est l’importance relative des actions. Un cadre permettant d’attribuer à priori des valeurs d’utilité statiques soumises à de fortes contraintes sur les modèles de système a été conçu, mais la recherche et le développement ultérieurs (comme les précédents) sur les TUF/UA ont préféré dépendre de l’exploitation de la spécificité des applications plutôt que de tenter de créer des cadres plus généraux. Cependant, de tels cadres et outils demeurent un sujet de recherche important.
Selon la convention traditionnelle, une TUF est une fonction concave, y compris les fonctions linéaires. Voir la représentation de quelques exemples de TUF.
Les articles sur les TUF/UA dans la littérature de recherche, à quelques exceptions près, par exemple, ne concernent que les TUF linéaires ou linéaires par morceaux (y compris les TUF conventionnelles basées sur les délais) parce qu’elles sont plus faciles à spécifier et à ordonnancer. Dans de nombreux cas, les TUF ne sont que monotonement décroissantes.
Une fonction constante représente l’utilité d’une action qui n’est pas liée au temps de réalisation de l’action-par exemple, l’importance relative constante de l’action. Cela permet de planifier de manière cohérente les actions dépendantes et indépendantes du temps.
Une TUF a un temps critique global, après lequel son utilité n’augmente pas. Si une TUF ne diminue jamais, son temps critique global est le premier moment où son utilité maximale est atteinte. Une TUF constante a un temps critique arbitraire pour les besoins de l’ordonnancement, comme le temps de lancement de l’action ou le temps de fin de la TUF. Le temps critique global peut être suivi par des temps critiques locaux-par exemple, considérez une TUF ayant une séquence d’étapes descendantes, peut-être pour se rapprocher d’une courbe descendante lisse.
Les valeurs d’utilité de la TUF sont généralement des entiers ou des nombres rationnels.
L’utilité de la TUF peut inclure des valeurs négatives. (Une TUF qui a des valeurs négatives dans sa plage n’est pas nécessairement abandonnée de la considération d’ordonnancement ou avortée pendant son fonctionnement – cette décision dépend de l’algorithme d’ordonnancement.)
Un temps de délai conventionnel (d) représenté comme une TUF est un cas spécial – une TUF à étape descendante ayant une pénalité d’unité (c’est-à-dire, Plus généralement, une TUF permet aux fonctions d’étape descendante (et ascendante) d’avoir des utilités avant et après le temps critique.
Le retard représenté comme une TUF est un cas spécial dont l’utilité non nulle est la fonction linéaire C – d, où C est le temps d’achèvement de l’action – soit actuel, soit attendu, soit supposé. Plus généralement, un TUF permet à la précocité et au retard non nuls d’être non linéaires – par exemple, un retard croissant peut entraîner une utilité décroissante non linéaire, comme lors de la détection d’une menace.
Ainsi, les TUF fournissent une riche généralisation des contraintes traditionnelles de temps d’achèvement des actions dans l’informatique en temps réel.
Alternativement, le paradigme TUF/UA peut être employé pour utiliser la ponctualité par rapport au temps critique global comme un moyen d’atteindre une fin d’accumulation d’utilité – c’est-à-dire, Une TUF (sa forme et ses valeurs) peut être adaptée dynamiquement par une application ou son environnement opérationnel, indépendamment de toute action actuellement en attente ou en cours d’exécution, Ces adaptations se produisent habituellement lors d’événements discrets – par exemple, lors d’un changement de mode d’application, comme pour les phases de vol des missiles balistiques.
D’autre part, ces adaptations peuvent se produire en continu, comme pour les actions dont les durées opérationnelles et les TUF sont des fonctions spécifiques à l’application du moment où ces actions sont libérées ou commencent à fonctionner. Les durées d’opération peuvent augmenter ou diminuer ou les deux, et peuvent être non monotones. Ce cas continu est appelé ordonnancement en fonction du temps. L’ordonnancement dépendant du temps a été introduit pour (mais n’est pas limité à) certaines applications militaires en temps réel, telles que les systèmes de poursuite radar.