<figure><img src="image_1.png" /></figure>

HAL
open science

# Un algorithme optimal pour la gestion des processus en temps réel

Jacques Labetoulle

► To cite this version:

Jacques Labetoulle. Un algorithme optimal pour la gestion des processus en temps réel. [Rapport de recherche] IRIA-RR-073, IRIA. 1974, pp.15. hal-04715978

HAL Id: hal-04715978

https://inria.hal.science/hal-04715978v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

<table><tr><td>ARCHIVES</td></tr></table>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

<table><tr><td>ARCHIVES</td></tr></table>

Un algorithme optimal
pour la gestion des processus
en temps réel

J.Labetoulle

15p.

Rapport de Recherche n° 73

mai 1974
UN ALGORITHM OPTIMAL POUR LA GESTION DES PROCESSUS
EN TEMPS RÉEL

J. Labetoulle

(présenté par M. Depeyrot et E. Gelenbe)

RÉSUMÉ

Pour des ensembles de processus s'exécutant de manière répétitive avec des contraintes de temps
(''dates critiques''), nous montrons que l'algorithme RU d'allocation d'unité centrale est optimal.

ABSTRACT

For a set of repetitive processes, each of which must be executed before a given deadline, we show
that RU (relative urgency) algorithm is optimal in the following sense : if RU is unable to allocate
the CPU to the processes so that all of the deadlines are respected, then no other algorithm can
achieve this.

To appear in the French computer science journal *Revue d'Informatique de l'AFCET*

<footnote>* A paraître dans la **Revue d'Informatique de l'AFCET**</footnote>
# I - INTRODUCTION.

L'utilisation des ordinateurs en temps réel peut se décomposer en trois catégories principales :

a) Le calcul hybride : l'ordinateur est couplé avec un calculateur analogique. Un programme est découpé en processus travaillant sur l'un ou l'autre des calculateurs.

b) Le mode temps réel conversationnel : il s'agit d'une utilisation spécifique de l'ordinateur pour certains problèmes particuliers du type réservation de places.

c) Le contrôle de processus industriels.

Les catégories a) et c) se caractérisent généralement par l'utilisation de processus soumis à des contraintes de temps, c'est à dire que ces processus, activés à une date $t_1$, sur un événement externe, doivent impérativement être achevés avant une date $t_2$ appelée *date critique* (deadline).

O. Serlin dans [2], M.S. Fineberg et O. Serlin dans [1] ainsi que C.L. Liu et J.W. Layland dans [3] ont étudié quelques algorithmes d'ordonnancement utilisés pour gérer ce type de processus, sans toutefois tirer de conclusions générales sur la comparaison de ces différents algorithmes.
Le but de cette étude est de montrer que l'un des algorithmes, appelé RU (Relative Urgency) par O. Serlin et Deadline driven scheduling par C.L. Liu, est optimal, relativement à un critère objectif du fonctionnement d'un algorithme.

Avant de poursuivre, nous allons donner un ensemble de définitions qui permettront de poser plus clairement les hypothèses de l'étude et le critère d'optimalité.

En conservant pour *processus* la définition classique de déroulement d'une procédure, nous appelerons *tache* un ensemble de processus se déroulant sur la même procédure, et tel que les dates d'activation des différents processus soient séparées par la même durée de temps $T_i$, appelée *période* de la tache. Une *configuration de taches* est un ensemble de taches qui doivent s'exécuter en concurrence sur un même calculateur.

Un processus est dit *actif* s'il a été activé (on a demandé son exécution) et s'il n'est pas encore terminé. La *durée d'activation* du processus, temps pendant lequel il est actif, doit être inférieure ou égale à la durée maximale qui est la durée de l'intervalle de temps compris entre l'activation et la date critique du processus.
<figure><img src="image_3.png" /><figcaption>Figure 1 : Représentation d'une configuration de taches.</figcaption></figure>

Nous appelons **puissance de l'unité centrale** la quantité de calcul que l'unité centrale effectue dans l'unité de temps. Par définition, cette puissance est égale à 1. La **puissance d'UC alouée à un processus** (ou une tache) est la quantité de calcul effectuée par l'UC pour ce processus (ou cette tache) dans l'unité de temps. Elle est toujours inférieure ou égale à 1. Si nous la désignons par $\lambda(t)$, nous définissons le **travail effectué par un processus** (ou une tache) pendant un intervalle $[t_1, t_2]$:

$$w(t_1, t_2) = \int_{t_1}^{t_2} \lambda(t) dt$$
## II - CARACTERISATION DES CONFIGURATIONS DE TACHES ETUDIEES.

Nous n'envisageons dans cette étude que des algorithmes capables de gérer des configurations ayant certaines propriétés caractéristiques propres aux catégories a) et c) de temps réel. Les hypothèses sont les suivantes :

$H_1$. La durée maximale $\tau_i$ est fixe pour chaque processus d'une même tache, et elle est inférieure ou égale à la période. $\tau_i \le T_i$.

$H_2$. L'organe de calcul doit exécuter, pour chaque processus d'une tache, le même travail $C_i$.

De tels processus sont appelés processus périodiques à date critique.

**Remarque 1 :**

Le fait que $\tau_i$ ne soit pas supérieur à $T_i$, implique qu'il n'y aura pas, à un instant donné, plus d'un processus d'une même tache actif. Ceci élimine donc les problèmes de files d'attente.

**Remarque 2 :**

Dans les études précédement faites ([1], [2] et [3]) on considère généralement que $\tau_i$ est égal à $T_i$. Cette hypothèse paraît trop contraignante parce que :
(i) Certains processus peuvent être activés peu souvent et demander un temps de réponse très court.

(ii) Cette hypothèse ne tient pas compte de la présence des entrées-sorties ou d'activités des processus sur d'autres processeurs.

Un processus de contrôle industriel se présente le plus souvent suivant le schéma suivant :

- une entrée (ou prise de mesure).

- un traitement sur l'unité centrale.

- une sortie (ou commande).

Si nous considérons que les entrées-sorties ont une durée fixe (hypothèse valable si les voies de liaison sont allouées à la tache), une tache se présente alors suivant le diagramme suivant :

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

IT = interruption

d'activation

Si on ne tient compte que de ce qui se passe sur l'UC, le diagramme devient :

<figure><img src="image_6.png" /></figure>

Il correspond alors aux hypothèses $H_1$ et $H_2$.
### Remarque 3 :

L'hypothèse $H_2$ implique $C_i \le \tau_i$, pour que l'unité centrale puisse exécuter le travail demandé pendant le temps disponible.

Le fait que $C_i$ soit identique pour chaque processus d'une tache est une hypothèse généralement vérifiée.

### Remarque 4 :

Dans l'étude qui suit, nous négligerons les temps de commutation de processus, ainsi que les temps de déroulement de l'algorithme d'ordonnancement.

### Remarque 5 :

Etant données les hypothèses choisies, une configuration de taches est complétement définie par un ensemble de paramètres :

$$ \{(C_i, T_i, \tau_i)\}, 1 \le i \le n $$

## III - DEFINITION D'UN CRITERE DE COMPARAISON.

D'abord, définissons ce que nous appelons l'acceptation d'une configuration de taches par un algorithme.

On dira qu'un algorithme _accepte_ une configuration de taches
s'il est capable de faire respecter les dates critiques de tous les processus qui composent chaque tache de la configuration, quelle que soient les conditions initiales.

Appelons $\xi_A$ l'ensemble des configurations de taches acceptées par l'algorithme A.

Nous dirons que l'algorithme A est meilleur que l'algorithme B si :

$$ \xi_B \subset \xi_A $$

A et B sont équivalents si $\xi_A = \xi_B$.

Remarquons que dans le cas $\tau_i = T_i$, ITS et RU sont équivalents puisqu'ils acceptent tous les deux les configurations qui vérifient $\sum c_i/T_i \le 1$.

Un algorithme X est dit optimal si, pour tout algorithme A, on a $\xi_A \subseteq \xi_X$.

Avant d'énoncer le théorème principal qui est le but de cette étude, nous allons rappeler brièvement la définition de l'algorithme RU :

RU est l'algorithme d'ordonnancement qui, à chaque instant, donne l'unité centrale au processus actif dont la date critique est la plus proche.
Avec une gestion des processus par l'algorithme RU, un processus actif P qui possède l'unité centrale, ne la perdra que pour l'une des deux raisons suivantes :

1. Il a terminé son travail.

2. Un autre processus, dont la date critique est antérieure à celle de P, a été activé.
IV - THEOREME.

RU est un algorithme optimal. C'est à dire pour tout algorithme A,
$ξ_{RU} ≥ ξ_A$.
Démonstration

Il suffit d'établir que si une configuration C est refusée
par $RU$, alors elle est refusée par tout autre algorithme A.

Nous raisonnerons par l'absurde. Soit A un algorithme tel
que $C \in \xi_A$ et $C \notin \xi_{RU}$.

Supposons que la première activation d'un processus des
tâches de C a lieu à t=0 et que $t=t_2$ est la première date
limite que RU ne respecte pas.

Appelons $w_e(t)$ le travail effectué par l'UC pour toutes
les tâches de C jusqu'à l'instant $t$, et $w_d(t)$ le travail demandé
par ces mêmes tâches jusqu'à $t$.

Posons $t_o=sup\{t|t \leq t_2$ et $w_e(t)=w_d(t)\}$ t_o existe
si on suppose que le travail demandé par un processus $P_{i,j}$ est
nul à son instant d'activation et qu'il est égal à $c_j$ pour tout
instant postérieur. On remarque que :

i) $0 \le t_o < t_2$

$t_o \ge 0$ parce que $t=0$ vérifie $w_e(0)=w_d(0)=0$

$t_o < t_2$ parce que $w_d(t_2) > w_e(t_2)$

ii) tout processus activé avant $t_o$ est terminé avant $t_o$

iii) avec l'algorithme RU, l'UC est constamment active pendant l'intervalle $[t_o, t_2]$.
Ceci permet de définir l'instant $t_1$ comme suit :

$t_1$ est le dernier instant, antérieur à $t_2$, auquel l'UC a
travaillé pour un processus de C dont la date critique est
postérieure à $t_2$, si un tel instant existe ; sinon, on pose
$t_1=t_0$. Donc : $t_0 \le t_1 < t_2$.

Nous avons besoin du résultat intermédiaire suivant, valable
seulement pour l'algorithme RU :

Lemme

Tout processus activé avant $t_1$ ne peut travailler dans
l'intervalle $]t_1, t_2]$.

Si $t_1=t_0$, le lemme est évident, puisque tout processus
activé avant $t_0$ est terminé à $t_0$.

Soit $t_1 > t_0$. Soit $\rho$ un processus travaillant dans l'intervalle $]t_1, t_2]$ et ayant travaillé avant $t_1$. Sa date limite est inférieure ou égale à $t_2$. A l'instant $t_1$, le processus qui travaille doit donc avoir sa date critique inférieure à celle de $\rho$ donc à $t_2$, ce qui est en contradiction avec la définition de $t_1$. Un processus tel que $\rho$ ne pouvant exister, le lemme est démontré.

En résumé, nous avons construit un intervalle $]t_1, t_2]$ tel
que

i) un processus travaille dans cet intervalle seulement si
il a été activé dans $]t_1, t_2]$

ii) tout processus activé dans $]t_1, t_2]$ dont la date critique est strictement antérieure à $t_2$, est terminé normalement.

iii) il existe au moins un processus activé dans cet intervalle,
ayant $t_2$ comme date critique, et qui n'est pas terminé à cet
instant.
Revenons à la démonstration du théorème. Appelons $P_1$ l'ensemble des processus activés dans $]t_1, t_2]$ et dont la date critique est strictement antérieure à $t_2$ (donc respectée) et soit $w_1$ le travail effectué pour ces processus, en utilisant $RU$.

$$w_1=t_2-t_1-\delta \quad (1)$$

(on a pris la convention que le travail se mesurait en temps d'occupation de l'UC).

$\delta$ est le travail effectué pendant $]t_1, t_2]$ par l'ensemble des processus $P_2$, activés dans cet intervalle et dont la date critique est $t_2$.

Remarquons que, d'après le lemme ci-dessus, dans l'intervalle $]t_1, t_2]$, l'UC ne travaille que pour $P_1 \cup P_2$ avec $RU$.

Alors l'algorithme A, qui respecte toutes les dates critiques des processus $P_1$ et $P_2$, doit pouvoir faire effectuer un travail

$$w_2=w_1+\delta'$$

à l'UC pendant $]t_1, t_2]$, où $\delta'$ représente le travail demandé, donc effectué, par les processus de $P_2$, plus éventuellement d'autres travaux.

Donc $\delta' > \delta$

$$\text{Alors : } w=t_2-t_1+\delta'-\delta > t_2-t_1$$

Or cela est impossible, l'UC ne pouvant faire qu'un travail au plus égal à $t_2-t_1$.

Cette contradiction prouve le théorème.

### Remarque 1

Ce théorème est vrai pour $\tau_1=T_1$ ou pour $\tau_1 < T_1$.
## Remarque 2

Le théorème n'est valable que si on néglige les temps de commutation de processus et les temps de déroulement de l'algorithme.

## Conclusions.

Ce théorème répond à la question posée par O. SERLIN dans [2], concernant les comparaisons d'algorithmes. Mais la validité de ce théorème n'est assurée que si l'on suppose nuls les temps d'overhead. Dans un cas concret, d'ailleurs, il faut considérer, non seulement l'algorithme lui-même, mais aussi son implémentation dont dépend la durée de déroulement de la fonction de choix. Pour RU, il faut disposer à tout instant d'une liste contenant les processus classés suivant leur date critique; un algorithme simple permet d'insérer un nouveau processus dans cette liste en un temps proportionnel à Log N, si N est le nombre de processus actifs.

Un deuxième problème important est celui de prévoir si une configuration donnée de tâches sera acceptée par un algorithme. Cette question n'a pas encore de réponse en ce qui concerne RU, par contre, dans [4], est présenté un algorithme, appelé ITSG, pour lequel un ensemble de conditions nécessaires et suffisantes garantissent qu'une configuration sera acceptée. D'après le théorème démontré plus haut, cet ensemble de conditions devient suffisant pour savoir si RU acceptera une configuration.
REMERCIEMENT.

Cette étude a été faite dans le cadre du projet SPECTRE dirigé
à l'IRIA par M. Depeyrot ; je tiens à remercier les membres de
cette équipe de recherche ainsi que Monsieur E. Gelenbe pour leur
collaboration dans cette étude.
BIBLIOGRAPHIE

[1] M.S. FINEBERG-O. SERLIN : Multiprogramming for hybrid computation. Proc. AFIPS. FJCC 1967.

[2] O. SERLIN : Scheduling of time critical processes spring joint computer conference. (1972) pp. 925-932.

[3] C.L. LIU and J.W. LAYLAND : Scheduling Algorithms for multiprogramming in a Hard Real-Time environment.
JACM Vol. 20. n°1. (Jan. 1973) pp. 46-71.

[4] J. LABETOULLE : L'ordonnancement des processus en temps réel sur une ressource préemptive.

Thèse de 3e cycle. Université de Paris VI (Mars 1974).