# Ordonnancement des processus temps réel sur une ressource préemptive

Jacques Labetoulle

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

## To cite this version:

Jacques Labetoulle. Ordonnancement des processus temps réel sur une ressource préemptive. [Rapport de recherche] IRIA-RR-074, IRIA. 1974, pp.79. hal-04715988

HAL Id: hal-04715988

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

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
Inv=02035 RR74

RIA
laboria

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

laboratoire de recherche
en informatique
et automatique

Ordonnancement
des processus temps réel
sur une ressource
préemptive

J.Labetoulle

79p

TH3

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 74

mai 1974
ORDONNANCEMENT DES PROCESSUS TEMPS RÉEL SUR UNE
RESSOURCE PRÉEMPTIVE*

J. Labetoulle

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

RESUME

Nous présentons une formalisation des algorithmes d'ordonnancement d'un ensemble de processus réactivés periodiquement et soumis à des contraintes de temps sur une ressource. On démontre certaines propriétés fondamentales de ces algorithmes dont certaines liées à la décidabilité de l'acceptation d'une configuration de processus par un algorithme et à l'optimalité des méthodes d'ordonnancement.

ABSTRACT

A formal model of scheduling algorithms for a set of repetitively
reactivated processes with deadlines is presented. It is then
used as a framework for the classification of these algorithms
with respect to the set of processes which they can schedule so
as to respect all of their deadlines. A new scheduling algorithm
obtained as a generalization of ITS is presented. A decision
procedure for this algorithm (which is shown to be sub-optimal)
is given allowing us to determine whether a given set of processes
can be accepted.

<footnote>+) Thèse de troisième cycle soutenue à l'université Paris VI le
18 Mars 1974.</footnote>
REMERCIEMENTS

Je tiens à remercier Monsieur le Professeur J. ARSAC qui a
bien voulu me faire l'honneur de présider mon jury.

Je tiens à remercier tout particulièrement Monsieur le
Professeur E. GELENBE qui a suivi avec beaucoup d'attention le travail
présenté ici, et qui m'a prodigué énormément de conseils tant pour
l'obtention que pour la rédaction des résultats.

Je tiens à remercier aussi Monsieur le Professeur DUPUY qui
a accepté de participer à mon jury, et qui m'a aidé de ses remarques
fort utiles.

J'exprime toute ma reconnaissance à Monsieur M. DEPEYROT
qui m'a permis de développer cette étude dans le cadre de son projet
de recherche, ainsi que tous les membres de son équipe qui m'ont
aidé de leurs remarques.

Enfin je tiens à remercier tout particulièrement Monsieur
le Professeur J.L. LIONS grâce à qui j'ai pu trouver au LABORIA
l'environnement de recherche idéal pour mener à bien ce travail.
# PLAN DE L'ETUDE.

## I. INTRODUCTION.

I.1. Position du problème.

I.2. Remarques sur les hypothèses.

I.3. Présentation de l'étude.

## II. RAPPEL DES APPROCHES EXISTANTES ET RÉSULTATS D'ORDRE GENERAL.

II.1. Algorithme IFP.

II.2. Algorithme ITS.

II.3. Algorithme RU.

II.4. Commentaires sur ces diverses études.

II.5. Propriétés générales des algorithmes d'ordonnancement.

## III. L'ALGORITHME ITSG.

III.1. Description de l'algorithme.

III.2. Théorème fondamental.

## IV. CONDITIONS D'ACCEPTABILITE POUR ITSG.

IV.1. Résolution analytique.

IV.2. Exemple de résolution numérique.

## V. COMPARAISON DES ALGORITHMES AVEC ITSG ET SIMULATION.

V.1. Comparaison des différents algorithmes.

V.2. Programmes de simulation.

## Annexe 1 : Démonstration du lemme 1.

Annexe 2 : Un algorithme optimal pour la gestion des processus temps-réel.

Annexe 3 : Programmation de l'algorithme de recherche des coefficients.

Annexe 4 : Programme de simulation pour calculer les coefficients.

Annexe 5 : Programme général de simulation.
# CHAPITRE I

## Introduction

### I-1 Position du problème

L'utilisation de plus en plus importante de l'ordinateur pour contrôler la conduite de processus industriels a amené ces dernières années à développer le software spécialisé dans ce type d'utilisation. Deux points caractérisent l'ensemble des programmes utilisés dans ce domaine : D'une part, la présence d'autres sorties analogiques avec les processus industriels et d'autre part les contraintes de temps auxquelles sont soumis les programmes. C'est le second de ces points qui nous intéresse dans cette étude. Il a déjà donné lieu à un certain nombre de développements théoriques et pratiques ([1], [2], [3] et [4]).

Cette étude concerne l'ordonnancement, sur un monoprocesseur, de programmes ayant la contrainte suivante :

Ces programmes, activés à un instant $t_1$ sur un évènement externe, doivent impérativement être terminés avant une date $t_2$ appelée *date critique* (deadline).

Deux aspects seront dégagés :

i) l'étude du fonctionnement des différents algorithmes d'ordonnancement, c'est-à-dire des algorithmes qui gèrent à chaque instant l'allocation de l'unité centrale.

ii) l'étude a priori du comportement d'un ensemble de processus. Il s'agit en particulier de savoir prévoir si les contraintes de temps citées plus haut, pourront ou non être respectées.

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

En conservant pour processus la définition classique de déroulement d'une procédure, nous appelerons *tâche* un ensemble de processus se déroulant sur la même procédure. Une *configuration de tâches* est un ensemble de tâches 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'activité** du processus, temps pendant lequel il est actif, doit être inférieure ou égale à la **durée maximale** ($\tau$), qui est la longueur de l'intervalle de temps compris entre l'activation et la date critique du processus. Une tâche est à l'état **actif** si un de ses processus est actif. Elle est à l'état **mort** dans le cas contraire.

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

## Représentation d'une tâche

<caption>Fig. 1</caption>

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 sera égale à 1. La **puissance d'unité centrale allouée à un processus** est la quantité de calcul effectuée par l'unité centrale pour ce processus dans l'unité de temps. Elle est forcément inférieure ou égale à 1. Si nous la désignons par $\mu(t)$, on définit le **travail effectué par un processus** (ou une tâche) pendant un intervalle de temps $[t_1, t_2]$ par :

$$W(t_1, t_2) = \int_{t_1}^{t_2} \mu(t) \, dt$$

On remarque que :

1) le travail se mesure en temps

2) le travail représente la quantité de calcul fait par l'unité centrale pour le processus (ou la tâche) pendant l'intervalle de temps.
L'étude qui suit concerne l'ordonnancement sur un processeur de con-
figuration de tâches ayant certaines propriétés généralement rencontrées dans
les problèmes de contrôle. Les hypothèses sont les suivantes.

H1. Les processus d'une même tâche $J_i$ sont activés périodiquement chaque $T_i$ unité de temps, $T_i$ étant fixe.

H2. La durée maximale $\tau_i$ est fixe pour chaque processus d'une même tâche, et elle est inférieure ou égale à la période : $\tau_i < T_i$.

H3. L'unité centrale doit exécuter pour chaque processus d'une tâche, le même travail $C_i$.

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

## I-2 Remarques sur les hypothèses

### Remarque 1.

Le fait que $\tau_i$ ne soit pas supérieur à $T_i$ implique qu'il n'y aura pas, à un moment donné, deux processus d'une même tâche actifs. Ceci limite donc les problèmes de files d'attente. S'il y a n tâches, il y aura au plus n processus actifs dans le système.

### Remarque 2.

Dans les études précédemment faites ([1], [2], [3]), on considère généralement que $\tau_i$ est égal à $T_i$. Cette hypothèse paraît trop contraignante parce que :

1. Certains processus peuvent être activés peu souvent et demander un temps de réponse très court.

2. Cette hypothèse ne tient pas compte de la présence des entrées-sorties.
Un processus de contrôle industriel se présente le plus souvent suivant le schema 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 tâche), une tâche se présente alors suivant le diagramme suivant :

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

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

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

Il correspond alors aux hypothèses H1 et H2.

Remarque 3.

L'hypothèse H2 implique $C_i < \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 tâche 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 tâches est complètement définie par un ensemble de paramètres $\{C_i, T_i, \tau_i\}, i = 1,n$

I-3 Présentation de l'étude

Après avoir décrit, dans le chapitre II, les résultats des travaux faits dans le domaine, nous démontrerons deux résultats originaux.
La suite concerne essentiellement l'étude d'un algorithme nouveau ITSG.
Sa description ainsi que ses propriétés fondamentales, qui en justifient l'existence, sont données dans le chapitre III. Le chapitre IV est consacré à l'étude plus approfondie de l'algorithme, et on établit des relations entre les variables $\{C_i, T_i, \tau_i\}$ qui garantissent l'exécution d'une configuration de tâches gérées par ITSG. Le dernier chapitre concerne les comparaisons entre ITSG et les algorithmes connus. En particulier on développe des méthodes qui permettent de comparer par simulation les différentes performances.
# CHAPITRE II.

## RAPPEL DES APPROCHES EXISTANTES ET
RESULTATS D'ORDRE GENERAL.

Dans ce chapitre nous présentons brièvement les propriétés
de trois algorithmes connus IFP, ITS et RU.

Le problème de la comparaison des performances des algorithmes est abordé ; il est suivi de l'ennoncé de deux théorèmes, le premier sur l'optimalité de l'algorithme RU, le second sur l'utilisation de l'unité centrale.
## II Rappel des approches existantes et résultats d'ordre général.

O. Serlin, dans [2], décrit quatre algorithmes, qu'il nomme IFP, ITS, MTS et RU. Dans les paragraphes qui suivent, nous décrivons ces algorithmes ainsi qu'un formalisme qui permet de mieux comprendre leur fonctionnement. D'autre part, nous citons les résultats obtenus par O. Serlin, ainsi que les conclusions des études faites par M.S. Fineberg [1], C.L. Liu et J.W. Layland [3].

Définissons, pour tout algorithme, la grandeur $\epsilon_i(t)$ par :

- $\epsilon_i(t) = 1$ si un processus de la tâche $J_i$ est actif à l'instant $t$, c'est-à-dire si un processus activé n'a pas terminé son travail.

- $\epsilon_i(t) = 0$ dans le cas contraire.

Désignons par $\mu_i(t)$ la puissance instantanée d'unité centrale utilisée par la tâche $J_i$ à l'instant $t$.

Nous définirons, pour chaque algorithme, une fonction $\alpha_i(t)$ telle que :

$$ \mu_i(t) = \epsilon_i(t) \alpha_i(t) $$

C'est la grandeur $\alpha_i(t)$ qui permet de caractériser chaque algorithme.

Nous dirons qu'une configuration C est _acceptée_ par un algorithme A si tous les processus composant chaque tâche de C ont leur date critique respectée, quel que soit l'instant d'activation du premier processus de chaque tâche. Une _configuration particulière_ (D) est une configuration pour laquelle on a précisé les dates d'activation des premiers processus. Une configuration particulière D sera acceptée si tous ses processus ont leur date critique respectée. Une configuration C est acceptée si toutes les configurations particulières bâties à partir de C sont acceptées.

### II-1 Algorithme IFP (Intelligent fixed Priority).

A chaque tâche nous attachons une valeur fixe $P_i$ telle que pour i différent de j, $P_i$ soit différent de $P_j$.

On définit $\alpha_i(t)$ comme suit :

$$ \begin{aligned} \alpha_i(t) &= 1 & \text{si } \epsilon_i(t) P_i &= \sup_j \{\epsilon_i(t) P_j\} \\ \alpha_i(t) &= 0 & \text{dans le cas contraire.} \end{aligned} $$
Autrement dit, l'unité centrale est donnée à un instant t au processus actif dont la priorité ($P_i$) est la plus forte. Avec cet algorithme, l'unité centrale est toujours allouée tant qu'il y a un processus actif.

O. Serlin a montré dans [2] que si on prenait des configurations telles que $\tau_i = T_i$, on pourrait accepter le maximum de configurations en choisisant les $P_i$ inversement proportionnels aux $\tau_i$. Il a aussi démontré, de même que LIU et Layland dans [3] que l'algorithme accepte toute configuration de m tâches qui vérifie :

$$ \sum_{i=1}^{m} \frac{C_i}{T_i} < m(2^{\frac{1}{m}} - 1) $$

Cette propriété n'est pas nécessaire ; en effet IFP peut gérer des configurations qui utilisent 100 % d'unité centrale. Par exemple deux tâches telles que $T_1 = T_2$, $C_1 = C_2 = \frac{T_1}{2}$, $\tau_1 = \tau_2 = T_1$.

La figure 1 ci-dessous donne un exemple de 3 tâches gérées par IFP, avec le diagramme d'occupation de l'unité centrale.

<figure><img src="image_6.png" /><figcaption>Fig II.1 : Gestion par IFP.</figcaption></figure>

## II-2 Algorithme LTS (Infinite time-slicing)

A chaque tâche est associée une valeur fixe $l_i$. $\alpha_i(t)$ est constant et égal à $l_i$.

Le travail fait par un processus pendant un intervalle de temps $[t_1, t_2]$ est
donc :

$$ \int_{t_1}^{t_2} \varepsilon_i(t) \cdot l_i \ dt $$
Pour réaliser un ordonnancement suivant cet algorithme, on définit un intervalle de temps $\Delta_t$ et on donne à chaque processus $l_i$ temps d'unité centrale pendant cet intervalle. On fait tendre $\Delta_t$ vers 0

Pour garantir qu'un processus aura sa date critique respectée, il faut que $l_i \ge \frac{C_i}{\tau_i}$ et la condition pour qu'une configuration soit acceptée est :

$$ \sum_{i=1}^{n} \frac{C_i}{\tau_i} < 1 $$

Dans le cas $\tau_i = T_i$, la condition devient $\sum_{i} \frac{C_i}{T_i} < 1$ ce qui prouve que dans ce cas, ITS est meilleur que IFP (c'est-à-dire qu'il accepte des configurations réfusées par IFP).

La réalisation d'un processeur partagé n'étant pas rigoureusement possible, ITS a été implémenté sous une forme différente appelée MTS, pour laquelle $\Delta_t$ est fini et égal au plus petit intervalle de temps séparant deux évènements (interruption d'activation ou fin de processus).

<figure><img src="image_7.png" /><figcaption>**Fig. 2 :** Gestion par ITS.

**II-3 Algorithme RU (Relative Urgency)**</figcaption></figure>

Cet algorithme est aussi appelé Deadline Driven Scheduling dans [3].

Pour RU, $\alpha_i(t)$ est défini comme suit :

Si on appelle $d_i(t)$ la date critique du processus en cours de la tâche $J_i$ :

$$ \alpha_i(t) = 1 \quad \text{si} \quad \varepsilon_i(t) \cdot (d_i(t)-t) = \inf \{\varepsilon_j(t) \cdot (d_j(t)-t)\} $$

$$ \alpha_i(t) = 0 \quad \text{dans le cas contraire.} $$
Autrement dit, à tout instant, l'unité centrale est donnée au processus actif dont la date critique est la plus proche dans le temps.

O. Serlin et J.C. Liu ont démontré que pour des configurations qui vérifient $\tau_i = T_i$, la condition nécessaire et suffisante pour accepter une configuration est :

$$ \Sigma \quad \frac{C_i}{T_i} \ll 1. $$

Ce résultat prouve donc que RU et ITS sont équivalents pour les configurations telles que $\tau_i = T_i$.

<figure><img src="image_8.png" /><figcaption>Fig. 3 : Gestion par RU.</figcaption></figure>

## II-4 Commentaires sur ces diverses études

Les problèmes posés concernent essentiellement la comparaison de ces divers algorithmes, et la puissance d'unité centrale utilisée. Dans le cas $\tau_i = T_i$, RU et ITS permettent d'utiliser l'unité centrale à 100 % et sont donc les meilleurs algorithmes possibles. Nous allons définir un critère qui permette de comparer les algorithmes même si cette hypothèse n'est pas remplie.

Appelons $\delta_A$ l'ensemble des configurations acceptées par un algorithme A. Nous dirons que l'algorithme A est meilleur que l'algorithme B si :

$$ \delta_B \subset \delta_A $$

A et B sont équivalents si $\delta_A = \delta_B$.

Un algorithme X est dit optimal si, pour tout algorithme A il vérifie :

$$ \delta_A \subset \delta_X. $$
**Remarque :**

Pour tout algorithme, on sait trouver des configurations telles que l'unité centrale est utilisée à 100 % . Donc la puissance utilisée de l'unité centrale ne peut fournir un critère valable et général. L'intérêt du critère défini ci-dessus est précisément de faire intervenir toutes les configurations possibles et de ne pas se limiter à celles qui utilisent une certaine puissance de calcul.

II-5 Propriétés générales des algorithmes d'ordonnancement

**Théorème 1 :**

Pour tout algorithme A, $\delta_A \subset \delta_{RU}$.

Ce théorème peut également s'écrire sous la forme équivalente :
RU est un algorithme optimal.

**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 \delta_A$ et $C \notin \delta_{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 < t_2 \text{ et } w_e(t) = w_d(t)\}$.

$\quad$ 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_0, 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 \ll 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 \qquad (II.1)$$

(on a pris la convention que le travail se mesurait en temps d'occupation de l'UC).
δ 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$ ou $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 des 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 le temps de commutation de processus et le temps de déroulement de l'algorithme.
### Théorème II.

Nous appelons moyenne d'utilisation de l'UC le rapport $\frac{w_e(t_1, t_2)}{t_2 - t_1}$ du travail effectué par l'UC pour une configuration de tâches sur un intervalle $[t_1, t_2]$ par la longueur de l'intervalle.

### Théorème 2 :

Pour tout algorithme, quand une configuration de tâches est acceptée, la moyenne d'utilisation de l'UC sur l'intervalle $[0,t]$ tend vers $\Sigma \frac{C_i}{T_i}$ quand $t$ tend vers l'infini.

### Démonstration

Appelons $t_{i,0}$ la date d'activation du premier processus de la tâche $J_i$.

Le travail fait par l'UC pour la configuration de tâches doit vérifier la double inégalité :

$$ \sum_i \left[ \frac{t - t_{io}}{T_i} \right] C_i \le w_e(t) < \sum_i \left[ \frac{t - t_{io}}{T_i} \right] C_i \quad (II.2) $$

En constatant que :

$$ t - t_{i,0} = \left[ \frac{t - t_{io}}{T_i} \right] T_i + P_i \quad \text{avec } 0 \le P_i < T_i $$

$$ \text{et } t - t_{i,0} = \left[ \frac{t - t_{io}}{T_i} \right] T_i + Q_i \quad \text{avec } 0 \le Q_i < T_i $$

(II.2) devient :

$$ t \sum_i \frac{C_i}{T_i} - \sum_i \frac{t_{io}}{T_i} - \sum_i \frac{P_i}{T_i} \le w_e(t) < t \sum_i \frac{C_i}{T_i} - \sum_i \frac{t_{io}}{T_i} + \sum_i \frac{Q_i}{T_i} $$

Les quantités $\sum_i \frac{P_i}{T_i}$ et $\sum_i \frac{Q_i}{T_i}$ sont bornées, on en déduit :
$$ \lim_{t \to +\infty} \left( \frac{w_e(t)}{t} + \frac{1}{t} \sum_i \frac{t_{io}}{T_i} \right) = \sum_i \frac{C_i}{T_i} $$

$$ \text{donc :} \quad \lim_{t \to +\infty} \frac{w_e(t)}{t} = \sum_i \frac{C_i}{T_i} $$

ce qui prouve le théorème 2.
# CHAPITRE III.

## L'ALGORITHME ITSG.

Après avoir donné les justifications pour l'étude d'un nouvel algorithme, nous donnons sa description ainsi qu'une méthode possible d'implémentation grâce à quelques éléments hardware. Nous démontrons ensuite un théorème fondamental qui permet d'établir un ensemble des conditions nécessaires et suffisantes pour qu'une configuration de tâches soit acceptée.
### III L'algorithme ITSG (ITS Généralisé)

La définition et l'étude d'un nouvel algorithme se justifient par les remarques suivantes :

i) Bien que RU soit un algorithme optimal, on ne connait pas un ensemble de conditions qui garantissent l'acceptabilité d'une configuration.

ii) On ne sait pas sur quel espace de temps il faut étudier le déroulement de RU (en simulation ou par observation) pour être certain qu'une configuration puisse être acceptée.

L'algorithme ITSG qui va être défini ne présente pas ces inconvénients. En particulier, on sait trouver un intervalle de temps de longueur inférieure à sup $\tau_i$, telle qu'en observant le déroulement sur cet intervalle, on peut dire si une configuration est ou non acceptée.

### III-1 Description de l'algorithme.

En reprenant les notations du paragraphe II, on définit :

$$ \alpha_i(t) = \frac{\lambda_i}{\sum_j \varepsilon_j(t)\lambda_j} $$

si tous les $\varepsilon_j(t)$ ne sont pas nuls.

$$ \alpha_i(t) = 0 \quad \text{sinon.} $$

Les $\lambda_i$ sont des coefficients fixes attachés aux tâches. L'algorithme ITSG est un "processor sharing" [5] sur l'ensemble des processus actifs et il peut être réalisé de la façon suivante :

- on classe les tâches de 1 à n

- on définit un intervalle de temps élémentaire $\Delta t$

- on alloue $\varepsilon_i(t) \lambda_i \Delta t$ temps d'UC à la tâche $J_i$

- puis on alloue $\varepsilon_{i+1}(t) \lambda_{i+1} \Delta t$ à la tâche $J_{i+1}$ (les i étant considérés modulo n)

- on procède indéfiniment de même, et on fait tendre $\Delta t$ vers 0.
Cet algorithme a les mêmes difficultés d'implémentation que ITS,
mais il est possible d'envisager une implémentation du type de celle de MTS,
en choisissant un Δt fini et en disposant d'un ensemble de registres comme
ci-dessous :

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

On peut imaginer un dispositif hardware qui, à la fin du quantum
$\lambda_i \Delta t$ alloué à la tâche $J_i$, alloue automatiquement un quantum $\lambda_j \Delta t$ au premier
processus rencontré après le rang i et qui vérifie $\varepsilon_j(t) = 1$. Il suffit pour
cela de tester par hardware si les bits $\varepsilon_j(t)$ sont égaux à 1 ou à 0. Le dispo-
sitif devrait automatiquement se déconnecter dès que le registre $\varepsilon_1(t), \varepsilon_2(t),$
$\varepsilon_N(t)$ serait nul.

Pour activer une tâche sur une interruption externe, il suffit de
mettre à 1 son bit $\varepsilon_i(t)$ directement sur l'interruption, après décodage.

Etant donné que, pendant un quantum $\lambda_j \Delta t$, aucun $\varepsilon_k(t)$ ne passera
de 1 à 0 (sauf peut-être pour $J_j$), on peut doter l'UC d'un double jeux de re-
gistres de travail, fonctionnant en va et vient avec préchargement des contex-
tes, ce qui permettrait de rendre quasiment nul les temps de commutation et
de rendre les études théoriques faites ici concordantes avec la réalité.

L'avantage d'un tel algorithme par rapport à RU est la simplicité
de la fonction de choix du prochain processus à activer, qui ici, peut être
câblée.
### Remarque 1

Si, pendant un intervalle $[t_1, t_2]$ il existe toujours au moins une
tâche active, ITSG assure que l'UC travaille à 100 %, donc qu'elle effectue
un travail égal à $t_2 - t_1$.

### Remarque 2

La puissance allouée à un processus à un instant $t$ étant

$\mu_i(t) = \frac{\epsilon_i(t) \lambda_i}{\sum_j \epsilon_j(t) \lambda_j}$ le processus doit vérifier :

$$C_i = \int_t^{t+\tau_i} \frac{\epsilon_i(u) \lambda_i \ du}{\sum_j \epsilon_j(u) \lambda_j} \quad (III.1)$$

t étant sa date d'activation.

Cette égalité ne peut être vérifiée que si :

$$\int_t^{t+\tau_i} \frac{\lambda_i \ du}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} \geq C_i \quad (III.2)$$

En effet, si (III.1) est vérifiée, il existe un instant $t_1 \leq t + \tau_i$ où
$\epsilon_i(t)$ passe de 1 à 0.

$$ \text{On a alors :} \quad \begin{cases} \epsilon_i(t) = 1 & \text{sur } [t, t_1] \\ \epsilon_i(t) = 0 & \text{sur } [t_1, t + \tau_i] \end{cases} $$

$$ \text{et} \quad \int_t^{t+t_1} \frac{\lambda_i \ du}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} = C_i $$

Cette égalité démontre l'équivalence de (III.1) et (III.2).
### III-2 Théorème fondamental

Nous dirons qu'un ensemble de tâches est _synchrone_ à un instant $t$ si un processus de chaque tâche est activé à cet instant $t$.

On dit aussi que la configuration particulière est synchrone.

**Théorème :**

Supposons qu'une configuration soit synchrone à l'instant $t_0$. Si la date critique de tous les processus activés à l'instant $t_0$ est respectée, alors ITSG accepte la configuration.

Donnons quelques remarques avant de démontrer le théorème :

1. Ce théorème n'est pas satisfait par tout algorithme ; en particulier par RU, ce que l'on montre facilement sur un exemple :

Soient deux tâches :

$J_1$ ($T_1 = 15, \tau_1 = 13, C_1 = 6$)

$J_2$ ($T_2 = 5, \tau_2 = 4, C_2 = 3$)

et considérons le diagramme d'utilisation de l'UC :

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

A : Première date critique de $J_2$ respectée

B : Première date critique de $J_1$ respectée

C : Une date critique de $J_2$ n'est pas respectée.

2. Il faut démontrer non seulement que la configuration particulière synchrone à l'instant $t_0$ est acceptée, mais aussi que toute configuration particulière l'est.
Démonstration du théorème.

Il faut au préalable établir un classement des tâches en procédant comme suit. Si nous appelons $\theta_i$ la durée d'activation du premier processus de la tâche $J_i$, en supposant les tâches synchrones, nous les numérotons de telle façon que : $\theta_1 \ge \theta_2 \ge \dots \ge \theta_n$.

Pour démontrer le théorème, nous utilisons deux lemmes que nous al-
lons établir.

Lemme 1 :

On considère les hypothèses suivantes :

H1. Les dates critiques de tous les processus des tâches $J_{i+1}$, $J_{i+2}$, ..., $J_n$ sont respectées.

H2. Les tâches $J_1, \dots, J_{i-1}$ sont toujours actives pendant les in-
tervalles de temps considérés.

Alors la fonction :

$$
Q_i = \int_t^{t+\theta_i} \frac{\lambda_i \, d\theta_i}{\lambda_i + \sum_{j \neq i} \epsilon_j(\theta_i) \, dt}
$$

est minimum quand les tâches $J_{i+1}, J_{i+2}, \dots, J_n$ sont synchrones à l'instant $t$.

La démonstration du lemme 1 se trouve en annexe.

Lemme 2 :

Si tous les processus des tâches $J_{i+1}, \dots, J_n$ ont leur date critique respectée, les hypothèses du théorème impliquent que tous les processus de $J_i$ ont leur date critique respectée.
Démonstration du lemme 2 :

Il faut montrer que :

$$ \int_t^{t+\tau_i} \frac{\epsilon_i(u) \lambda_i \ \mathrm{du}}{\sum_j \epsilon_j(u) \lambda_j} = C_i $$

c'est-à-dire que le processus étudié fait exactement le travail demandé. Etant donnée la remarque 2, il est équivalent de montrer que :

$$ \int_t^{t+\tau_i} \frac{\lambda_i \ \mathrm{du}}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} \geq C_i $$

L'hypothèse du théorème qui dit que le premier processus de $J_i$ a sa date critique respectée implique, compte tenu de la définition de $\theta_i$ :

$$ C_i = \int_{t_o}^{t_o+\theta_i} \frac{\lambda_i \ \mathrm{du}}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} $$

Donc $C_i$ est rigoureusement égal au minimum de la fonction $w_i$, d'après le lemme 1.

$$ \text{Donc :} \quad \int_t^{t+\tau_i} \frac{\lambda_i \ \mathrm{du}}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} \geq \int_{t_o}^{t_o+\tau_i} \frac{\lambda_i \ \mathrm{du}}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} = C_i $$

$$ \text{Puisque } \int_t^{t+\tau_i} \frac{\lambda_i \ \mathrm{du}}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} \geq \int_t^{t+\tau_i} \frac{\lambda_i \ \mathrm{du}}{\lambda_i + \sum_{j \neq i} \epsilon_j(u) \lambda_j} $$

le lemme 2 est démontré.
Le théorème se démontre alors d'une manière évidente par récurrence à condition d'établir la première itération pour $i = n$.

Il reste donc à démontrer que :

$$ \int_t^{t+\tau_n} \frac{\lambda_n}{\sum_j \varepsilon_j(t) \lambda_j} dt \ge C_n = \int_{t_o}^{t+\tau_n} \frac{\lambda_n}{\sum_j \lambda_j} dt $$

Cette propriété est évidente puisque $\theta_n < \tau_n$. Le théorème est donc établi.
# CHAPITRE IV.

## CONDITIONS D'ACCEPTABILITE POUR ITSG.

Etant données les conditions nécessaires et suffisantes pour qu'une configuration de tâches soit acceptée, nous résolvons mathématiquement l'algorithme de manière à formuler des relations entre les paramètres {$Ci, Ti, ti$} qui garantiront l'acceptabilité. Un exemple numérique de résolution est ensuite donné.
IV Conditions d'acceptabilité pour ITSG

Du dernier théorème énoncé dans le paragraphe précédent, on peut
déduire immédiatement les conditions nécessaires et suffisantes pour qu'une
configuration de tâches soit acceptée par ITSG :

Une configuration de tâches C sera acceptée par ITSG si et seulement
si il existe un ensemble de coefficients $\lambda_i$, ($i = 1, \dots, n$) tels que, en sup-
posant les tâches synchrones à un instant $t_o$, la date critique du processus de
chaque tâche activé à l'instant $t_o$ est respectée.

Un tel ensemble de conditions ne peut se vérifier que par essai
direct ou par simulation : et encore faudrait-il savoir déterminer les va-
leurs $\lambda_i$. C'est pour cela que nous avons cherché un ensemble de relations entre
les variables $C_i$, $T_i$ et $\tau_i$ qui permettent :

- de calculer un ensemble de coefficients $\lambda_i$.

- de vérifier l'acceptabilité.

Nous commençons pour cela, par classer les tâches par $\tau_i$ décroissants :
$\tau_1 \ge \tau_2 \ge \dots \ge \tau_n$ et nous utiliserons la notation suivante :

$$ \Lambda_i = \sum_{j=1}^{i} \lambda_j $$

Pour toute solution $\lambda_1, \dots, \lambda_n$ telle que le premier processus de cha-
que tâche a sa date critique respectée (nous appelerons cela une **solution acceptable**), il existe une date $t$ à laquelle tous ces processus ont terminé.

Nous allons chercher une solution particulière au problème qui répond
à une hypothèse restrictive (HYPOTHESE H) :

* Si t existe, il existe un i tel que

$\tau_i < t < \tau_{i+1}$. L'hypothèse H veut que pour $j \ge i$, le premier proces-
sus des tâches $J_j$ se termine exactement à l'instant $t_o + \tau_j$.
Nous démontrerons plus loin que si la configuration possède une
solution acceptable, alors il existe une solution acceptable vérifiant l'hy-
pothèse H.

Etude de la tâche J_n.

L'hypothèse H précise que le premier processus de $J_n$ se termine à la date $t_o + \tau_n$. Ceci implique que le total du travail défini par l'ensemble des tâches dans l'intervalle $[t_o, t_o + \tau_n[$ n'est pas inférieur à $\tau_n$ ; en effet, sinon, l' UC s'arrêtera de travailler avant la date $t_o + \tau_n$ et quelques soient les coefficients $\lambda_i$, la configuration serait acceptée, et le problème résolu.(*)

Cette condition se traduit par $\sum_{j=1}^{n} C_i > \tau_n$

Nous devons alors vérifier :

$$
\int_{t_o}^{t_o + \tau_n} \frac{\lambda_n \, dt}{\Lambda_n} = C_n
$$

Cette équation donne :
$$
\frac{\lambda_n}{\Lambda_n} = \frac{C_n}{\tau_n}
$$

La seule condition d'acceptabilité est : $\tau_n > C_n$

Etude de la tâche J<sub>n-1</sub>

Appelons $\Gamma_{n-1}$ le travail fait pendant l'intervalle $[t_o, t_o + \tau_{n-1}]$
par la tâche $J_n$, en supposant que pendant cet intervalle, les tâches $J_1, J_2,$
..., $J_{n-1}$ sont toutes actives. Il est facile de constater que $\Gamma_{n-1}$ ne dépend
que de $\frac{\lambda_n}{\Lambda_n}$ et pas des valeurs $\lambda_1, \dots, \lambda_{n-1}$.

En effet :

$$
\Gamma_{n-1} = \int_{t_o}^{t_o + \tau_{n-1}} \frac{\varepsilon_n(t) \lambda_n}{\Lambda_n} dt
$$

$$
\text{et } \varepsilon_n(t) = \begin{cases} 1 & \text{pour } t \in ]t_o + k T_n, t_o + k T_n + \tau_n[ \\ 0 & \text{pour } t \in ]t_o + k T_n + \tau_n, t_o + (k+1) T_n[ \end{cases} \quad k \ge n
$$

<footnote>(*) L'hypothèse H serait alors vérifiée pour toute solution $\lambda_1 \dots \lambda_n$.</footnote>
Deux cas sont possibles :

$$1) \quad \sum_{j=1}^{n-1} C_j + \Gamma_{n-1} < \tau_{n-1}$$

Dans ce cas, quels que soient les $\lambda_j$ pour $j = 1, \dots, n-1$, le premier processus de chaque tâche $J_j$ pour $j = 1, \dots, n-1$ sera terminé avant la date $t_o + \tau_{n-1}$. La solution du problème est donc :

$\lambda_j$ quelconque pour $j = 1, \dots, n-1$.

$$\frac{\lambda_n}{\Lambda_n} = \frac{C_n}{\tau_n}$$

L'hypothèse H est donc vérifiée.

$$2) \quad \sum_{j=1}^{n-1} C_j + \Gamma_{n-1} > \tau_{n-1}$$

Dans ce cas, cherchons la solution qui correspond à l'hypothèse H :

$$\int_{t_o}^{t_o + \tau_{n-1}} \frac{\lambda_{n-1} dt}{\Lambda_{n-1} + \varepsilon_n(t) \lambda_n} = C_{n-1} \quad (IV.2)$$

(IV.2) peut se transformer en :

$$\frac{\lambda_{n-1}}{\Lambda_{n-1}} \int_{t_o}^{t_o + \tau_{n-1}} \frac{\Lambda_{n-1} + \varepsilon_n(t) \lambda_n - \varepsilon_n(t) \Lambda_n}{\Lambda_{n-1} + \varepsilon_n(t) \lambda_n} = C_{n-1}$$

$$\text{d'où la solution : } \quad \frac{\lambda_{n-1}}{\Lambda_{n-1}} = \frac{C_{n-1}}{\tau_{n-1} - \Gamma_{n-1}}$$

Les conditions d'acceptabilité sont :

$$\Gamma_{n-1} < \tau_{n-1} \quad \text{et} \quad C_{n-1} < \tau_{n-1} - \Gamma_{n-1}$$

## Etude de la tâche $J_i$

Nous supposons que les rapports $\frac{\lambda_i}{\Lambda_j}$ sont connus pour $j > i$ : que toutes les conditions d'acceptabilité rencontrées sont remplies et que le problème n'est pas résolu à la date $t_o + \tau_{i+1}$.
Appelons $\Gamma_i$ le travail fait pendant l'intervalle $[t_o, t_o + \tau_i]$ pour les tâches $J_{i+1}, J_{i+2}, \dots, J_n$, en supposant que pendant cet intervalle les tâches $J_1, J_2, \dots, J_{n-1}$ sont toutes actives. Démontrons d'abord que $\Gamma_i$ ne dé-

pend que des valeurs $\frac{\lambda_j}{\Lambda_j}$ pour $j > i$.

$$ \Gamma_i = \int_{t_o}^{t_o + \tau_i} \frac{\sum_{j=i+1}^{n} \varepsilon_j(t) \lambda_j}{\Lambda_i + \sum_{j=i+1}^{n} \varepsilon_j(t) \lambda_j} dt $$

remarquons que la fonction

$$ f_j(t) = \frac{\lambda_j \varepsilon_j(t)}{\Lambda_i + \sum_{k=i+1}^{n} \varepsilon_k(t) \lambda_k} $$

est constante par intervalles, et que l'on peut calculer son inverse, $\frac{1}{f_j(t)}$ sur chaque intervalle :

$$ \frac{1}{f_j(t)} = \frac{\Lambda_i}{\lambda_j \varepsilon_j(t)} + \sum_{k=i+1}^{n} \frac{\varepsilon_k(t)}{\varepsilon_j(t)} \frac{\lambda_k}{\lambda_j} $$

et on sait calculer $\frac{\Lambda_i}{\lambda_j}$ et $\frac{\lambda_k}{\lambda_j}$ pour $j$ et $k > i$, connaissant $\frac{\lambda_j}{\Lambda_j}$ pour $j > i$.

En effet :

$$ 1) \quad \frac{\Lambda_k}{\lambda_k} = \frac{\Lambda_{k-1} + \lambda_k}{\lambda_k} = 1 + \frac{\Lambda_{k-1}}{\lambda_k} $$

En posant $\frac{\Lambda_k}{\lambda_k} = A_k$ :

$$ A_k = 1 + A_{k-1} \frac{\lambda_{k-1}}{\lambda_k} \quad \text{D'où :} \quad \frac{\lambda_{k-1}}{\lambda_k} = \frac{A_k - 1}{A_{k-1}} $$

Cette relation permet, par multiplication, de connaître tous les rapports

$$ \frac{\lambda_k}{\lambda_j} $$
$$2) \quad \frac{\Lambda_i}{\lambda_j} = \frac{\Lambda_{i+1} - \Lambda_{i+1}}{\lambda_j} = \frac{\Lambda_{i+1}}{\lambda_{i+1}} * \frac{\lambda_{i+1}}{\lambda_j} - \frac{\lambda_{i+1}}{\lambda_j}$$

ce qui est calculable, d'après la remarque précédente.

Tout ceci prouve que l'on peut calculer rigoureusement $\Gamma_i$, sans connaître $\lambda_i$, ni $\frac{\lambda_i}{\Lambda_i}$.

Alors deux cas sont possibles :

$$1. \quad \sum_{j=1}^{i} c_j + \Gamma_i \le \tau_i$$

Dans ce cas, quelques soient les $\lambda_j$ pour $j = 1, \dots, i$ le premier processus de chaque tâche $J_j$ pour $j = 1, \dots, n$ sera terminé avant la date $t_o + \tau_i$. La solution de ce problème est donc :

$$- \lambda_j \text{ quelconque pour } j = 1, \dots, i$$

- pour $j > i$, les $\lambda_j$ sont calculés à partir des rapports $\frac{\lambda_i}{\Lambda_j}$ tous connus.

$$2. \quad \sum_{j=1}^{i} c_j + \Gamma_i > \tau_i$$

Dans ce cas, cherchons la solution qui correspond à l'hypothèse H :

$$\int_{t_o}^{t_o + \tau_i} \frac{\lambda_i \, dt}{\Lambda_i + \sum_{j=i+1}^{n} \varepsilon_j(t) \lambda_j} = c_i \quad (\text{IV.3})$$

(IV.3) peut se transformer en :

$$\frac{\lambda_i}{\Lambda_i} \int_{t_o}^{t_o + \tau_i} \frac{\Lambda_i + \sum_{j=i+1}^{n} \varepsilon_j(t) \lambda_j - \sum_{j=i+1}^{n} \varepsilon_j(t) \lambda_i}{\Lambda_i + \sum_{j=i+1}^{n} \varepsilon_j(t) \lambda_j} \, dt = c_i$$

$$\text{D'où : } \frac{\lambda_i}{\Lambda_i} \left[ \tau_i - \int_{t_o}^{t_o + \tau_i} \frac{\sum_{j>i} \varepsilon_j(t) \lambda_j}{\Lambda_i + \sum_{j>i} \varepsilon_j(t) \lambda_j} dt \right] = c_i$$
et la solution est : $$\frac{\lambda_i}{\Lambda_i} = \frac{c_i}{\tau_i - \Gamma_i}$$
Les conditions d'acceptabilité sont :

$$ \Gamma_i < \tau_i \text{ et } C_i > \tau_i - \Gamma_i $$

### Etude de la tâche $J_1$

On suppose ici qu'à la date $t_0 + \tau_2$ le problème n'était pas encore résolu et que tous les rapports $\frac{\lambda_i}{\Lambda_j}$ sont connus pour $j = 2, 3, \dots, n$.

Deux cas sont possibles :

$$ 1) C_1 + \Gamma_1 \ll \tau_1 $$

La solution du problème est alors :

- $\lambda_1$ quelconque

- pour $j > 1$, les $\lambda_j$ sont calculés à partir des rapports $\frac{\lambda_j}{\Lambda_j}$

2) $C_1 + \Gamma_1 > \tau_1$. Il n'y a alors pas de solution et la configuration doit être refusée.

Il faut maintenant justifier l'hypothèse H : nous allons montrer que si il existe une solution acceptable $\lambda_1, \dots, \lambda_n$ pour la configuration particulière donnée, alors il existe aussi une solution acceptable qui vérifie l'hypothèse H. Nous indiquons par o toutes les valeurs qui se rapportent à la solution qui vérifie H.

Nous raisonnons par l'absurde, c'est-à-dire que nous supposons que :

i) Il existe une solution $\lambda_1, \dots, \lambda_n$ acceptable

ii) Il n'existe pas de solution $\lambda_1^o, \dots, \lambda_n^o$ qui vérifie H.

La deuxième supposition implique l'existence d'un indice i qui vérifie :

$$ C_i > \tau_i - \Gamma_i^o \text{ et } C_j < \tau_j - \Gamma_j^o \text{ pour } j > i $$

A partir de la solution $\{\lambda_i\}$, nous allons construire une suite de solutions, $\{\lambda_j^o\}$, toutes acceptables et nous mettons en lumière l'existence d'un indice $\alpha$ qui vérifie : $\Gamma_i^\alpha = \Gamma_i^o$
Cette solution vérifiera : $C_i < \theta_i^\alpha - \Gamma_i^\alpha$, $\theta_i^\alpha$ étant la date de fin d'activité du premier processus de la tâche $\mathcal{J}_i$, avec la solution $\{\lambda_i^\alpha\}$.
Donc : $\theta_i^\alpha < \tau_i$.

Une contradiction apparaît alors :

$$C_i < \theta_i^\alpha - \Gamma_i^\alpha, \quad \theta_i^\alpha < \tau_i \quad \text{et} \quad \Gamma_i^\alpha = \Gamma_i^0$$

impliquant que $C_i < \tau_i - \Gamma_i^0$. Les suppositions i) et ii) ne pouvant être vérifiées simultanément, l'hypothèse H se trouvera justifiée.

Construction de la suite de solution :

Nous notons $\theta_j^\alpha$ la date de fin d'activité du premier processus de la tâche $\mathcal{J}_j$, en utilisant la solution $\{\lambda_j^\alpha\}$.

- Posons $\lambda_j^1 = \lambda_j$ pour tout $j = 1, n$.

- On construit $\{\lambda_j^2\}$ comme suit :

$$\text{Si } \theta_n^1 = \tau_n, \text{ on pose } \lambda_j^2 = \lambda_j^1 \text{ pour tout } j$$

$$\text{Si } \theta_n^1 < \tau_n, \text{ on pose } \lambda_j^2 = \lambda_j^1 \text{ pour } j < n$$

et on diminue $\lambda_n^1$ jusqu'à une valeur $\lambda_n^2$ qui vérifie : $\theta_n^2 = \tau_n$. Pour les autres tâches, on a alors $\theta_j^2 < \theta_j^1$, donc la solution $\{\lambda_j^2\}$ est acceptable.

- On construit $\{\lambda_j^3\}$ comme suit :

$$\text{Si } \theta_{n-1}^2 = \tau_{n-1}, \text{ on pose } \lambda_j^3 = \lambda_j^2 \text{ pour tout } j$$

$$\text{Si } \theta_{n-1}^2 < \tau_{n-1}, \text{ on pose } \lambda_j^3 = \lambda_j^2 \text{ pour } j < n-1$$

et on diminue conjointement $\lambda_n^2$ et $\lambda_{n-1}^2$ jusqu'à obtenir deux valeurs $\lambda_n^3$ et $\lambda_{n-1}^3$ qui vérifient :

$$\theta_n^3 = \tau_n \quad \text{et} \quad \theta_{n-1}^3 = \tau_{n-1}$$

Pour les autres tâches, on a alors $\theta_j^3 < \theta_j^2$, ce qui vérifie que la solution $\{\lambda_j^3\}$ est acceptable.

On poursuit de même jusqu'à l'indice $\alpha = n-i+1$.

La solution $\{\lambda_j^\alpha\}$ vérifie alors :
$$ \text{pour } j > i : \theta_j^\alpha = \tau_j $$

$$ \text{pour } j < i : \theta_j^\alpha \le \theta_j \le \tau_j $$

Donc, pour $j > i$, on a $\frac{\lambda_i^\alpha}{\Lambda_j^\alpha} = \frac{\lambda_i^0}{\Lambda_j^0}$, ce qui prouve que $\Gamma_i^\alpha = \Gamma_i^0$. Nous sommes donc arrivé à construire la solution désirée et donc à justifier l'hy-pothèse H.

## IV-2 Exemple de résolution numérique d'une configuration de tâches pour ITSG.

Nous allons prendre un exemple de 3 tâches et montrer comment on calcule les $\lambda_i$. La configuration choisie est telle qu'elle sera refusée par les algorithmes IFP et ITS. Le chapitre V donnera les raisons de ses refus, dans le paragraphe V-1, réservé à la comparaison des différents algorithmes.

Soit la configuration de tâches :

$\mathcal{J}_1 (C_1 = 1,2 , \tau_1 = 7 , T_1 = 10)$

$\mathcal{J}_2 (C_2 = 2 , \tau_2 = 4 , T_2 = 5)$

$\mathcal{J}_3 (C_3 = 1 , \tau_3 = 2 , T_3 = 3)$

Voici les différentes étapes par lesquelles on doit passer :

1) Vérifier que les trois premiers processus ne sont pas terminés à l'instant $t_o + \tau_1$ :

$$ \begin{array}{l} C_1 + C_2 + C_3 < \tau_3 \\ 1,2 + 2 + 1 < 2 \end{array} $$

Ce n'est pas le cas, donc il faut calculer $\frac{\lambda_3}{\Lambda_3}$

$$ \text{La formule générale donne : } \frac{\lambda_3}{\Lambda_3} = \frac{C_3}{\tau_3} = \frac{4}{2} = 0,5 $$
2) Calculer $\Gamma_2$.

$$ \Gamma_2 = \int_{t_0}^{t_0+\tau_2} \frac{\epsilon_3(t) \lambda_3}{\sum_{j=1}^{3} \epsilon_j(t) \lambda_j} dt = C_3 + \int_{3}^{4} \frac{\lambda_3}{\Lambda_3} dt $$

$$ \Gamma_2 = 1 + \frac{1}{2} = 1,5 $$

3) Vérifier qu'à l'instant $t_0 + \tau_2$ le premier processus de $J_1$ et $J_2$ n'est pas terminé.

$$ C_1 + C_2 + \Gamma_2 < \tau_2 $$

$$ 1,2 + 2 + 1,5 < 4 $$

Ce n'est pas le cas, donc il faut calculer $\frac{\lambda_2}{\Lambda_2}$

4) Calcul de $\frac{\lambda_2}{\Lambda_2}$

La formule générale donne : $\frac{\lambda_2}{\Lambda_2} = \frac{C_2}{\tau_2 - \Gamma_2} = \frac{2}{4-1,5}$

Donc $\frac{\lambda_2}{\Lambda_2} = 0,8$

5) Calcul de $\Gamma_1$

$$ \Gamma_1 = \int_{t_0}^{t_0+\tau_1} \frac{(\epsilon_3(t) \lambda_3 + \epsilon_2(t) \lambda_2)}{\lambda_1 + \epsilon_2(t) \lambda_2 + \epsilon_3(t) \lambda_3} dt \\ = C_2 + 2 \cdot C_3 + \int_{5}^{6} \frac{\lambda_2}{\Lambda_2} dt + \int_{6}^{7} \frac{\lambda_2 + \lambda_3}{\Lambda_3} dt $$

Or : $\frac{\lambda_2 + \lambda_3}{\Lambda_3} = \frac{\lambda_3}{\Lambda_3} + \frac{\lambda_2}{\lambda_1 + \lambda_2 + \lambda_3} = \frac{\lambda_3}{\Lambda_3} + \frac{1}{\frac{\lambda_2}{\lambda_1} + \frac{\lambda_3}{\lambda_2}}$
Il faut donc calculer $\frac{\lambda_3}{\lambda_2}$

De l'expression $\frac{\lambda_1 + \lambda_2 + \lambda_3}{\lambda_3} = \frac{\lambda_1 + \lambda_2}{\lambda_2} * \frac{\lambda_2}{\lambda_3} + 1$

on tire : $\frac{\lambda_2}{\lambda_3} = \left(\frac{\Lambda_3}{\lambda_3} - 1\right) * \frac{\lambda_2}{\Lambda_2}$

Donc $\frac{\lambda_2}{\lambda_3} = (2 - 1) * 0,8 = 0,8$

Donc $\frac{\lambda_2 + \lambda_3}{\Lambda_3} = 0,5 + \frac{1}{1_{0,8} + 1_{0,8}} = 0,9$

et $\Gamma_1 = 2 + 2 + 0,8 + 0,9 = 5,7$

6) Il faut alors vérifier que $C_1 + \Gamma_1 < \tau_1$

$$1,2 + 5,7 = 6,9 < \tau_1 = 7$$

7) Cette vérification étant faite, on sait qu'on peut choisir arbi-
trairement $\lambda_1$. Prenons par exemple $\lambda_1 = 1 \Rightarrow \lambda_3 = 4 \Rightarrow \lambda_3 = 5$

On constate d'après ces calculs que le maximum de travail que pouvait
demander $\Gamma_1$, avec une durée maximale égale à 7 est 1,3. Au delà, ITSG refuse-
rait la configuration.

Dans ce calcul, on n'a fait aucune approximation sur les $\Gamma_i$, parce
que dans ce cas particulier, il était facile de les évaluer rigoureusement.
Si on avait utilisé le calcul majoré défini dans le paragraphe précédent, le
calcul de $\Gamma_1$ aurait donné :

$$\Gamma_1 = C_2 + 2C_1 + \int_5^7 \frac{\lambda_2}{\Lambda_2} d\lambda_2 + \int_6^7 \frac{\lambda_3}{\lambda_1 + \lambda_3} d\lambda_3$$
ce qui donnait, tous calculs faits :

$$ \Gamma_1 = 2 + 2 + 1,6 + 0,8 = 6,4 $$

Le maximum de calcul autorisé n'est alors que de 0,6 pour $C_1$.

C'est pour cela que nous allons, dans le chapitre suivant, développer une méthode de simulation, permettant de calculer rigoureusement les $\Gamma_i$.

Nous donnons, dans la figure IV-1 une représentation de la puissance d'UC allouée à chaque tâche.
5-

J₁

1

0.5 -

0.4

0

0.2

0.2

0.1

0.1

0.2

0.1

> t

1-

J₂

4

0.5-

0.8

0.8

0.8

0.4

0.4

0

1-

>

0.5-

0.5

J₃

5

1

0.5

0.5

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

>

Fig. W-1 : Distribution de la puissance de l'UC entre les 3 tâches.
# CHAPITRE V.

## COMPARAISON DES ALGORITHMES AVEC ITSG ET SIMULATION.

ITSG est ici comparé aux autres algorithmes et nous examinons aussi la cause des différences de performances. Ensuite nous étudions une méthode de simulation qui permet de suivre le déroulement d'un algorithme et de calculer les coefficients optimaux pour ITSG.
## V Comparaison des algorithmes avec ITSG et simulation.

Les résultats précédents mettent en lumière certaines propriétés de l'algorithme ITSG qui en font l'originalité et l'intérêt. Il serait bon maintenant de faire une évaluation comparative des différents algorithmes mentionnés précédemment. Pour cela, nous allons d'abord étudier d'une manière analytique des différences de performance entre les algorithmes, puis nous décrirons des outils de simulation qui permettent de vérifier ces résultats. Nous montrerons aussi qu'un programme de simulation légèrement modifié permet de calculer rigoureusement les valeurs $\lambda_i$ optimales pour l'algorithme ITSG, alors que la résolution analytique de l'IV ne permettait que d'en avoir une approximation.

### V-1 Comparaison des différents algorithmes avec ITSG.

La comparaison avec RU est immédiate compte tenu du théorème I de III. Il est néanmoins intéressant de comprendre pourquoi RU est meilleur. Con- sidérons la figure V-1 ci-dessous.

<figure><img src="image_11.png" /><figcaption>Figure 1.</figcaption></figure>

Quel que soit l'algorithme d'ordonnancement, une condition nécessaire pour accepter une configuration doit être :

$$C_i < \tau_i - \sum_{j \neq i} \int_{t_o}^{t_o + \tau_i} \mu_j(t) \, dt$$

Pour RU, compte tenu du fait que les tâches $J_1, \dots, J_{i-1}$ ne peuvent travailler sur $[t_o, t_o + \tau_i]$ que si le premier processus de $J_i$ est terminé, la condition devient :

$$C_i < \tau_i - \sum_{j>i} \int_{t_o}^{t_o + \tau_i} \mu_j(t) \, dt$$
C'est donc la même que pour ITSG : $C_i < \tau_i - \Gamma_i$ (à l'égalité près).

Dans le cas de RU : $$ \int_{t_o}^{t_o + \tau_i} \mu_j^{\text{RU}}(t) \, dt = p \cdot C_j + r_j $$

$r_j$ étant le travail fait par $\mathcal{J}_j$ sur $[t, t_o + \tau_i]$ avec $t = p \cdot T_j$ $r_j$ ne peut être non nul que si le premier processus de $\mathcal{J}_j$ a terminé.

Pour ITSG : $$ \int_{t_o}^{t_o + \tau_i} \mu_j^{\text{ITSG}}(t) \, dt = p \cdot C_j + r'_j $$

Mais ici $r'_j$ n'est jamais nul. Il en résulte que RU est capable d'accepter une configuration où $C_i$ serait plus grand que la limite acceptable par ITSG, soit $\tau_i - \Gamma_i$.

Par contre, dans le cas de RU, il faut tenir compte du fait que la condition "le premier processus de chaque tâche a son deadline respecté" n'est pas suffisante pour affirmer qu'une configuration sera acceptée.

Pour illustrer ce qui précède, considérons à nouveau la configuration étudiée dans le paragraphe IV-2. En particulier cherchons, en gardant $\mathcal{J}_1, \mathcal{J}_2$ et $\tau_1$ identiques, quel $C_1$ maximum est admissible par RU.
La figure V-2 ci-dessous montre que avec $C_1 = 1,5$, RU respectera tous les deadline jusqu'à $t = 14$, et ceci en supposant $T_1 = \tau_1 = 7$, ce qui est l'hypothèse la plus contraignante.

<figure><img src="image_12.png" /><figcaption>Figure V-2</figcaption></figure>

Ordonnancement de $\mathcal{J}_1, \mathcal{J}_2, \mathcal{J}_3$ avec RU.
Comparons maintenant IFP et ITSG. Pour cela, nous allons démontrer
la propriété suivante :

Théorème :

Quand, pour tout i plus grand ou égal à 1, $\frac{\lambda_i}{\lambda_{i+1}}$ tend vers o, alors l'algorithme ITSG tend vers IFP.

Remarque :

Explicitons d'abord ce que nous entendons par "tend vers". Nous disons
qu'un algorithme A tend vers un algorithme B si, pour tout t, et pour toute
tâche, on vérifie :

$|w_i^A(t_o, t) - w_i^B(t_o, t)| < \varepsilon$

pour tout $\varepsilon$ aussi petit soit-il.

La notation $w_i^1(t_o,t)$ représente le travail fait par l'unité centrale
pour la tâche $J_i$ en utilisant l'algorithme A.

Démonstration :

$$
W_i^{\text{ITSG}} = \int_{t_o}^{t} \frac{\epsilon_i(u) \lambda_i}{\sum_j \epsilon_j(u) \lambda_j} du
$$

Il faut montrer deux choses :

1) que $| \alpha_i^{\text{ITSG}}(t) - \alpha_i^{\text{IFP}}(t) |$ peut être rendu aussi petit que possible.

2) que, pour les deux algorithmes, les dates de commutation des $\epsilon_i(t)$ sont aussi voisines que l'on veut.

En fait, la deuxième propriété dépend uniquement de la première,
puisque la quantité de travail demandé par chaque processus, ainsi que leurs
dates d'activation sont les mêmes.

$$
\alpha_i^{\text{ITSG}}(t) = \frac{\lambda_i}{\sum_j \varepsilon_j(t) \lambda_j}
$$
Si il existe un indice $j$ supérieur à $i$ tel que $\epsilon_j(t) = 1$, alors $\lambda_i$ ITSG $\alpha_j(t)$ peut être rendu aussi petit que l'on veut, d'après l'hypothèse : $\frac{\lambda_i}{\lambda_{i+1}}$ tend vers 0. Dans ce cas, $\alpha_i^{IFP}(t) = 0$.

Si il n'existe pas un tel indice, $\alpha_i^{ITSG}(t)$ est compris entre $1-\epsilon$ et $1$, $\epsilon$ étant aussi petit que l'on veut, en vertu de la même hypothèse. Dans ce cas, $\alpha_i^{IFP}(t) = 1$.

D'après la remarque faite plus haut, la propriété 1) que nous venons de prouver entraine la vérité de 2) donc celle du théorème.

On déduit immédiatement de ce théorème, que ITSG est un algorithme
meilleur de IFP. On pourrait d'ailleurs voir ce résultat directement, par un
raisonnement analogue à celui qui a servi à comparer RU et ITSG.
Considérons la figure 1 ci-dessus.

A la date t, IFP donnera la priorité à la tâche $J_j$ (alors que RU
la donnait à $J_i$), ce qui fait que la quantité $r_j$ définie plus haut, est cer-
tainement plus grande dans le cas de IFP que dans celui de ITSG. L'inégalité

$$
C_i < \tau_i - \sum_{j>i} \int_{t_o}^{t_o+\tau_i} \mu_j(t) \, dt
$$

sera donc vérifiée automatiquement pour ITSG si elle l'est pour IFP, ce qui
montre bien la supériorité de ITSG.

Dans l'exemple précédent, IFP n'aurait pu accepter la configuration,
puisqu'à l'instant $t = t_o + \tau_1$, les tâches $J_1$ et $J_2$ auraient fait un travail
égal à :

$$
3 C_1 + C_2 + \frac{1}{2} C_2 = 7 \qquad (voir \ figure \ V-5)
$$

<figure><img src="image_13.png" /><figcaption>Figure V-3. Ordonnancement de $J_1, J_2, J_3$ avec IFP.</figcaption></figure>
La comparaison de ITSG avec ITS est évidente, puisque la condition d'acceptabilité pour ITS :

$$ \Sigma_i \frac{C_i}{\tau_i} < 1 $$

est plus contraignante que l'ensemble des conditions pour ITSG.

Si on reprend le même exemple, on obtient :

$$ l_3 = \frac{C_3}{\tau_3} = \frac{1}{2} $$

$$ l_2 = \frac{C_2}{\tau_2} = \frac{1}{2} $$

$$ l_1 = \frac{C_1}{\tau_1} = \frac{4,2}{7} $$

et $l_1 + l_2 + l_3 > 1$, ce qui implique que la configuration doit être refusée.

En conclusion, ITSG est un algorithme qui se classe entre IFP et RU et entre ITS et RU.

Son avantage par rapport à RU est la possibilité de pouvoir résoudre analytiquement le problème de l'acceptabilité.

L'argument selon lequel l'algorithme qui permet de calculer les $\lambda_i$ est trop long à exécuter, ou qu'il ne peut tourner sur un petit ordinateur (les plus employés dans le cas de temps réel) est de peu de valeur quand on remarque que cet algorithme ne doit tourner qu'une seule fois pour assurer qu'une configuration donnée tournera indéfiniment sans faute. Le rapport du temps machine nécessaire au test sur le temps utilement passé est donc pratiquement nul.

On a déjà remarqué que les conditions d'acceptabilité pour ITSG (qu sont des conditions nécessaires et suffisantes) deviennent des conditions suf fisantes pour RU. Il est bon de chercher dans quelles hypothèses, ces conditi deviennent aussi nécessaires pour RU : donc nous allons chercher quelles hypo thèses sur les configurations rendent ITSG et RU équivalents.
C'est le cas en particulier si $\tau_i = T_i$ pour tout i, puisqu'alors ITS et RU sont équivalents et que ITSG se classe entre ces deux algorithmes.

Dans le cas général, les hypothèses cherchées doivent vérifier l'ensemble d'équations :

$$ \text{Pour tout } i \quad : \quad \sum_{j>i} W_j^{\text{RU}} [t_o, t_o + \tau_i] = \sum_{j>i} W_j^{\text{ITSG}} [t_o, \tau_i] = \Gamma_i $$

Or, on a déjà vu : $W_j^{\text{RU}}[t_o, \tau_i] \le W_j^{\text{RU}}[t_o, \tau_i]$ au début du paragraphe V-1. L'égalité ne peut avoir lieu que si, à la date $t_o + \tau_i$ la tâche $J_j$ n'est pas active. On en déduit alors facilement les hypothèses sur la configuration qui rendent RU et ITSG équivalents :

Si, pour tout i, la date $t_o + \tau_i$ est telle que pour j plus grand que i, toutes les tâches $J_j$ soient inactives (avec RU ou ITSG), alors les algorithmes RU et ITSG sont équivalents.

Cette propriété est vérifiée en particulier si
Pour tout i et pour tout j supérieur à i :

$$ p_j T_j + \tau_j < \tau_i < (p_j + 1) T_j $$

On remarque que dans ce cas, le calcul des $\Gamma_i$ est évident.

$$ \Gamma_i = \sum_{j>i} \left[ \frac{\tau_i}{T_j} \right] c_j $$
## V-2 Programme de simulation pour suivre le déroulement des algorithmes d'ordonnancement.

L'étude du suivi des algorithmes a l'avantage de pouvoir faire l'étude de n'importe quel algorithme, et aussi celui de pouvoir faire intervenir des temps évalués d'overhead, ce qui serait délicat avec les méthodes analytiques précédemment décrites.

La méthode simulée permet, de plus, de calculer avec exactitude les valeurs $\Gamma_i$ et donc $\frac{\Lambda_i}{\Lambda_i}$ dans le cas de ITSG.

Donnons immédiatement le principe de la méthode.

Si on se place à une date t, on cherche le premier événement à venir e. Cet événement est le plus proche dans le temps des N événements $e_i$ définis comme suit :

- Il existe un événement $e_i$ par tâche $J_i$

- Si $\epsilon_i(t) = 0$, $e_i$ est la date de prochaine activation d'un processus de la tâche. Dans le cas synchrone à l'origine : $e_i = t_0 + n T_i$

- Si $\epsilon_i(t) = 1$, la tâche étant active à l'instant t, le prochain événement est

- soit la fin d'activité du processus actif

- soit le deadline du processus actif.

Si le deadline tombe avant la fin du processus, c'est que la configuration doit être refusée.

En fait, on ne connaît pas à l'instant t la date de fin du processus, car sinon il serait inutile de faire une simulation puisqu'on connaît déjà tous les résultats.

On remplace dans la simulation la date de fin réelle du processus par une date fictive représentant la *fin présumée* du processus, calculée en supposant que les conditions (ensemble des processus actifs) vraies sur $[t, e]$ le sont jusqu'à cette fin présumée.
Si alors $e = \inf (e_i)$ est égal à la fin présumée, d'un processus de $J_1$ c'est que la fin présumée de ce processus correspond à la fin réelle.

Si ce n'est pas le cas, la fin présumée est obligatoirement postérieure à e, donc à l'instant e le processus sera toujours actif et on peut calculer le travail fait pour lui sur l'intervalle $[t, e]$. On a besoin pour chaque tâche d'une variable $r_i(t)$ représentant le travail restant à faire à la date t par le processus actif de la tâche si il y en a un et valant o si aucun processus n'est actif.

Le programme de simulation a alors le schéma suivant : (les organigrammes se trouvent dans l'annexe IV).

Nous nous plaçons à un instant t.

Pour tout i nous exécutons alors le programme suivant :

Si t est différent de e(i) et si $\epsilon_i(t) = 0$, e(i) reste inchangé

Si t est égal à e(i) et si $\epsilon_i(t) = 0$, alors il faut :

1) activer la tâche : donc $\epsilon_i(t) = 1$

2) réinitialiser les variables :

$$r_i = c_i \\ e_i = \inf (t + \tau_i, t + r_i \frac{\sum \epsilon_j(t) \lambda_j}{\lambda_i})$$

D'autre part, on dispose d'une variable a(i) qui vaut :

o si e(i) est une activation

1 si e(i) est une date de fin de processus

-1 si e(i) est une date critique.

3) réinitialiser a(i)

Si t est différent de e(i) et si $\epsilon_i(t) = 1$, on doit recalculer e(i) et réajuster a(i) et r(i).

Si t est égal à e(i) et si $\epsilon_i(t) = 1$, deux cas sont possibles :
1) $a(i) = -1$ : un deadline n'est pas respecté et la configuration doit être refusée.

2) $a(i) = 1$ : le processus a terminé, on doit réinitialiser :

$\tau(i)$ à 0

$a(i)$ à 0

$e(i)$ à la prochaine activation.

Quand on a fini ce travail, il faut reclasser les $e(i)$ pour déterminer la prochaine date simulée.

### Cas particulier de ITSG.

Si on connaît déjà les $\lambda_i$, le calcul peut se faire comme indiqué ci-dessus. Dans le cas contraire, on peut utiliser cette simulation pour calculer les coefficients.

En effet, prenons une date $t$ comprise entre $t_0$ et $t_0 + \tau_1$. A cette date, les premiers processus des tâches $J_n, J_{n-1}, \dots, J_{i+1}$ sont terminés. On connaît donc les coefficients $\frac{\lambda_n}{\Lambda_n}, \frac{\lambda_{n-1}}{\Lambda_{n-1}}, \dots, \frac{\lambda_{i+1}}{\Lambda_{i+1}}$.

L'étude du chapitre IV permet alors d'affirmer (si on s'en tient bien sûr à l'hypothèse H) que $e = \inf (e_n, e_{n-1}, \dots, e_{i+1}, t_0 + \tau_i)$. En effet, pour les autres tâches ($J_{i-1}, \dots, J_1$) le prochain événement attendu est postérieur à $t_0 + \tau_i$.

On pourra avec ces hypothèses simuler jusqu'à la date $t_0 + \tau_i$ et donc calculer $\frac{\lambda_i}{\Lambda_i}$.

L'organigramme de cette simulation se trouve dans l'annexe III.
Reprenons à titre d'exemple, la configuration C étudiée dans le paragraphe IV-2.

J₁ (C₁ = 1,2 , τ₁ = 7 , T₁ = 10)

J₂ (C₂ = 2 , τ₂ = 4 , T₂ = 5)

J₃ (C₃ = 1 , τ₃ = 2 , T₃ = 3)

A l'instant t = t₀ nous avons :

r(1) = 1,2

ε(1) = 1

a(1) = -1

e(1) = t₀ + τ₁

r(2) = 2

ε(2) = 1

a(2) = -1

e(2) = t₀ + τ₂

r(3) = 1

ε(3) = 1

a(3) = +1

e(3) = t₀ + τ₃

$$
e = \inf (e_i) = e(3) = t_o + 2
$$

Posons t = t₀ + 2. Nous avons alors :

r(1) inconnu

ε(1) = 1

a(1) = -1

e(1) = t₀ + τ₁

r(2) inconnu

ε(2) = 1

a(2) = +1

e(2) = t₀ + τ₂

r(3) = 0

ε(3) = 0

a(3) = 0

e(3) = t₀ + T₃

$$
e = \inf (e_i) = e(3) = t_o + 3
$$

Posons t = t₀ + 3. Nous avons alors :

r(1) inconnu

ε(1) = 1

a(1) = -1

e(1) = t₀ + τ₁

r(2) inconnu

ε(2) = 1

a(2) = +1

e(2) = t₀ + τ₂

r(3) = 1

ε(3) = 1

a(3) = +1

e(3) = t₀ + T₃

$$
e = \inf (e_i) = e(2) = t_o + 4
$$
A la date $t = t_0 + 4$, $r(3) = \frac{1}{2}$

Donc, on sait calculer $\Gamma_2$ donc $\frac{\lambda_2}{\Lambda_2}$.

Les conditions deviennent alors :

$r(1)$ inconnu

$\varepsilon(1) = 1$

$a(1) = -1$

$e(1) = t_0 + \tau_1$

$r(2) = 0$

$\varepsilon(2) = 0$

$a(2) = 0$

$e(2) = t_0 + T_2$

$r(3) = \frac{1}{2}$

$\varepsilon(3) = 1$

$a(3) = +1$

$e(3) = t_0 + T_1 + \frac{1}{2} \frac{\lambda_1 + \lambda_3}{\lambda_3}$

Pour terminer la simulation, il suffit de continuer ainsi jusqu'à $t_0 + \tau_1$ et de vérifier : $C_1 + \Gamma_1 < \tau_1$.

Dans ce cas particulier, la simulation donnera exactement les valeurs optimales que l'on peut obtenir par le calcul normal.
# Annexe 1

## Démonstration du lemme 1:

Rappelons l'ennoncé du lemme.

On considère les hypothèses suivantes:

H1. Les dates critiques de tous les processus des tâches $J_{i+1}, J_{i+2}, \dots, J_n$ sont respectées.

H2. Les tâches $J_1, J_2, \dots, J_{l-1}$ sont toujours actives pendant les intervales de temps considérés.

Alors la fonction

$$Q_i = \int_t^{t+\theta_i} \frac{\lambda_i \, d\theta}{\lambda_i + \sum_{j \neq i} \epsilon_j(\theta)\lambda_j}$$

est minimum quand les tâches $J_{i+1}, \dots, J_n$ sont synchrones à l'instant t.

## Démonstration:

Pour démontrer ce lemme, nous allons démontrer une propriété plus forte, dont découlera automatiquement le lemme 1:

Avec les mêmes hypothèses H1 et H2, nous allons prouver que la fonction

$$R_i = \int_t^{t+u} \frac{\lambda_i \, d\theta}{\lambda_i + \sum_{j \neq i} \epsilon_j(\theta)\lambda_j}$$

est minimum quand les tâches $J_{i+1}, \dots, J_n$ sont synchrones à l'instant t, et pour u tel que : $\theta_{i+1} < u < \theta_{i-1}$

Nous constatons que $R_i$ est fonction du décalage existant, à l'instant t entre les dates d'activation des premiers processus des tâches $J_{i+1}, \dots, J_n$, c'est à dire de la valeur des variables $x_j = t-t_j$, où $t_j$ est la date d'activation du dernier processus de $J_j$ activé avant l'instant t.

Nous noterons X le vecteur de composantes $x_{i+1}, \dots, x_n$.

$R_i$ étant une fonction de t, X et u (t et X étant liés), nous voulons démontrer que, pour u appartenant à $]\theta_{i-1}, \theta_{i+1}[$, $R_i(t, 0, u) \le R_i(t, X, u)$
Nous noterons :

$$A_i = \sum_{j=1}^{i} \lambda_i$$

$$\Sigma_X(t)^- = \lim_{dt \to 0^+} \sum_{j=i+1}^{n} \varepsilon_j(t-dt)\lambda_j$$

$$\Sigma_X(t)^+ = \lim_{dt \to 0^+} \sum_{j=i+1}^{n} \varepsilon_j(t+dt)\lambda_j$$

Vu la définition des $\varepsilon_j(t)$, on peut trouver un intervalle ouvert $] u^*, u[$ tel que sur cet intervalle aucun $\varepsilon_j(t)$ ne soit discontinu.

En choisissant $u'$ dans cet intervalle, cherchons quel est le vecteur qui minimise $R_i(t,X,u')$ sachant que $X^*$ minimise $R_i(t,X,u)$.

Nous avons, en notant $\Delta u = u - u'$

$$R_i(t, X^*, u') = R_i(t, X^*, u) - \frac{\lambda_i \Delta u}{A_i + \Sigma_X^* (t+u)^-} \quad (A-1)$$

$$R_i(t, X_1, u) = R_i(t, X_1, u) - \frac{\lambda_i \Delta u}{A_i + \Sigma_{X_1} (t+u)^-} \quad (A-2)$$

pour tout $X_1$

Par hypothèse, nous avons : $R_i(t,X^*,u) \le R_i(t,X_1,u)$

Deux cas sont possibles :

1) L'inégalité est stricte. Dans ce cas :

$$R_i(t, X^*, u') < R_i(t, X_1, u') + \frac{\lambda_i \Delta u}{A_i + \Sigma_X^* (t+u)^-} - \frac{\lambda_i \Delta u}{A_i + \Sigma_{X_1} (t+u)^-}$$

On peut alors trouver $\Delta u$ assez petit pour que :

$$R_i(t, X^*, u') < R_i(t, X_1, u')$$
Donc $X^*$ minimise $R_i$ pour $u'=u - \Delta u$, et même pour tout $u$ appartenant
à $]u^*, u[$.

$$
2) R_i(t, X^*, u) = R_i(t, X_1, u)
$$

Remarquons que dans l'intervalle ] $u^*$, $u[$ les dérivées par rapport à $u$
des fonctions $R_i(t, X^*, u)$ et $R_i(t, X_1, u)$ sont constantes. Donc, pour $v$ ]$u^*$, $u[$

$$
R_i(t, X^*, v) = av + b
$$

$$
R_i(t, X_1, v) = cv + d
$$

et selon les valeurs des dérivées, ce sera $X_1$ ou $X^*$ qui minimisera $R_i(t,X,u)$.

Donc, choisissant $u - \Delta u > u^*$, on sait trouver un intervalle fermé
$[u - \Delta u, u]$ tel qu'il existe au moins un vecteur $X^*$ qui minimise $R_i$ sur
cet intervalle.

Puisque $R_i(t,X,u)$ est minimum pour le vecteur $X^*$, on doit avoir en
particulier:

$$
\frac{\delta R_i}{\delta t} \cdot dt > 0
$$

1) $dt > 0$

$$
\frac{\delta R_i}{\delta t} = \frac{\lambda_i}{\Lambda_i + \Sigma_X^* (t+u)^+} - \frac{\lambda_i}{\Lambda_i + \Sigma_X^* (t)^+}
$$

$$
\text{Donc: } \Sigma_X^* (t)^+ \ge \Sigma_X^* (t+u)^+ \quad (A-3)
$$

2) $dt < 0$

$$
\frac{\delta R_i}{\delta t} = \frac{\lambda_i}{\Lambda_i + \Sigma_X^* (t)^{-}} - \frac{\lambda_i}{\Lambda_i + \Sigma_X^* (t+u)^{+}}
$$

Donc :

$$
\Sigma_X^* (t+u)^- \ge \Sigma_X^* (t)^- \quad (A-4)
$$

Etant donné que $X^*$ minimise $R_i$ sur l'intervalle $[u - \Delta u, u]$, tout
$u$ appartenant à l'intervalle ouvert $]u - \Delta u, u[$ est tel que:

$$
\Sigma_X^* (t+u)^+ = \Sigma_X^* (t+u)^-
$$

De (A-3) et (A-4) , on déduit qu'il faut vérifier :

$$
\Sigma_X^* (t)^+ \ge \Sigma_X^* (t)^-
$$
La fonction $R_i(t,X,u)$ ne peut être partout constante (même si ç'était vrai, le lemme serait démontré puisqu'alors $X=0$ minimiserait la fonction);
En se plaçant aux bornes de l'intervalle où $R_i$ est constant, on devra avoir:

$$ \Sigma_X^* (t)^+ > \Sigma_X^* (t)^- $$

On en déduit donc qu'au moins un processus est activé à l'instant $t$.

Appelons $\pi_1$ l'ensemble des tâches telles qu'un de leurs processus soit activé à l'instant $t$, et $\pi_2$ l'ensemble des autres tâches.

Nous faisons alors $d x_j = -d x$ pour les tâches de $\pi_1$ et $d x_j = 0$ pour les autres.

On a alors:

$$ d R_i = \frac{\lambda_i \, dx}{\Lambda_i + \Sigma_X^* (t)^- + \sum_{j \in \pi_1} \lambda_j} - \frac{\lambda_i \, dx}{\Lambda_i + \Sigma_X^* (t+u)^-} $$

Or:

$$ \Sigma_X^* (t)^- + \sum_{j \in \pi_1} \lambda_j > \Sigma_X^* (t)^+ $$

Donc $d R_i$ est négatif.

Ceci est une contradiction puisque $R_i$ est minimum pour $X^*$. Donc il ne peut exister de processus de la classe $\pi_2$. Dans ce cas, toutes les tâches ont un processus activé à l'instant $t$, ce qui prouve le lemme 1.
# ANNEXE II

## UN ALGORITHME OPTIMAL POUR LA GESTION DES PROCESSUS EN TEMPS REEL
# UN ALGORITHMES OPTIMAL POUR LA GESTION DES PROCESSUS EN TEMPS REEL (1)

par Jacques LABETOUILLE (2)

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 de l'UC est optimal.

## 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.

<footnote>(1) Manuscrit reçu le 4 déc. 1973.</footnote>

<footnote>(2) IRIA, Domaine de Voluceau, Rocquencourt.</footnote>
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 *tâche* 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 tâche. Une *configuration de tâches* est un ensemble de tâches 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_14.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 allouée à un processus* (ou une *tâche*) est la quantité de calcul effectuée par l'UC pour ce processus (ou cette *tâche*) 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 *tâche*) pendant un intervalle $[t_1, t_2]$ :

$$w(t_1, t_2) = \int_{t_2}^{t_1} \lambda(t) dt$$

## II. CARACTERISATION DES CONFIGURATIONS DÉ 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 tâche, 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 tâche, 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 tâche actif. Ceci élimine donc les problèmes de files d'attente.

### REMARQUE 2 :

Dans les études précédemment 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 tâche), une tâche se présente alors suivant le diagramme suivant :

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

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

<figure><img src="image_16.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 tâche 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 :

Étant données les hypothèses choisies, une configuration de tâches est
complètement définie par un ensemble de paramètres :

$$ \{(C_i, T_i, \tau_i)\}, \quad 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 tâches par un algorithme.

On dira qu'un algorithme *accepte* une configuration de tâches s'il est capable de faire respecter les dates critiques de tous les processus qui composent chaque tâche de la configuration, quelles que soient les conditions initiales.

Appelons $\xi_A$ l'ensemble des configurations de tâches 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
ξ<sub>RU</sub> ≥ ξ<sub>A</sub>.

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 ∈ ξ_A
et C ⊢ ξ_{RU}.

Supposons que la première activation d'un processus des tâches de C a lieu
à t = 0 et que t = t₂ 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_0 = \sup \{t \mid t \le t_2 \text{ et } w_e(t) = w_d(t)\}$. $t_0$ 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_0 < t_2$

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

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

ii) tout processus activé avant $t_0$ est terminé avant $t_0$.

iii) avec l'algorithme RU, l'UC est constamment active pendant l'inter-
valle $]t_0, 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).

δ 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$.

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. Donc RU peut être qualifié d’algorithme théoriquement le meilleur. 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 par ITSG. 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 M. E. Gelenbe pour leur collaboration dans cette étude.

BIBLIOGRAPHIE

[1] M. S. FINEBERG et O. SERLIN, *Multiprogramming for hybrid computation*. Proc. AFIPS. FJCC, 1967.

[2] O. SERLIN, *Scheduling of time critical process*. Proc. SJCC (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 (janv. 1973), pp. 46-71.

[4] J. LABETOULLE, *L'ordonnancement des processus en temps réel*. Thèse de 3e cycle. Université de Paris VIe (1974), (à paraître).
# ANNEXE III

## PROGRAMMATION DE L'ALGORITHME DE RECHERCHE DES COEFFICIENTS $\lambda_i$ POUR ITSG
<figure><img src="image_17.png" /></figure>
<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>
<figure><img src="image_20.png" /></figure>
Classement des tâches par τ décroissant.

<figure><img src="image_21.png" /></figure>
# ANNEXE IV.

## PROGRAMME DE SIMULATION PERMETTANT DE CALCULER RIGOUREUSEMENT LES COEFFICIENTS $\lambda_i$ OPTIMAUX.

Les coefficients optimaux sont tels que la configuration particulière obtenue dans le cas synchrone vérifie l'hypothèse H. Les équations générales obtenues dans le chapitre IV sont donc vérifiées, ce qui rend possible l'écriture d'un programme de simulation. Les variables $\Gamma_i$ seront ici calculés rigoureusement, ce qui justifie la dénomination : coefficients $\lambda_i$ optimaux.

Le principe de ce programme est le suivant :

Il existe trois types d'évènements possibles : activation d'un processus, deadline d'un processus, fin d'activité d'un processus. Entre deux des évènements, chaque tâche se voit attribuer une puissance d'UC constante. On peut donc en déduire le travail fait pendant cet intervalle pour chaque processus. Donc on peut en déduire la date des évènements "fin de processus" ainsi que les valeurs des variables $\Gamma_i$. Il suffit de calculer à chaque instant la date de l'évènement le plus proche.

### Phase d'initialisation.

Il faut un tableau des évènements $e(i)$, dans lequel on doit mettre aussi le type d'évènement attendu :

* 0 pour une activation

* 1 pour une fin de processus

* -1 pour un deadline.
Si on a commencé par classer les tâches de façon que

$\tau n \le \tau n-1 \le \dots \le \tau 1$ on aura :

$e(i) = \tau i$

$\text{type } (i) = -1$

L'évènement le plus proche (e) est donc $e(n)$.

Pour chaque tâche on doit disposer d'une variable r(J)
qui indique le travail restant à faire pour le processus en activité
de cette tâche. Puisqu'on considère que les tâches sont synchrones, on doit
avoir : Pour t = 0 : r (J) = C<sub>j</sub> .

On doit disposer aussi d'une matrice n * n contenant les
valeurs $\frac{\lambda_j}{\lambda_j + \sum_{k>i} \epsilon_k(t)^{\lambda_k}}$ et qui est remplie au fur et à mesure.

Les formules utilisées au cours de la simulation sont les
suivantes :

1.Calcul des dates présumées de fin de processus.

(date à laquelle se terminerait le processus si les conditions restaient constantes).

$$
\begin{align*}
& \int_t^{x_j} \frac{\lambda_j}{\Lambda_i + \sum_{k>i} \epsilon_k(t)^{\lambda_k}} dt &&\equiv r_j \\
& \Rightarrow x_j = t + r_j * \left( \frac{\Lambda_i}{\lambda_j} + \sum_{k>i} \epsilon_k(t)^{\frac{\lambda_k}{\lambda_j}} \right)
\end{align*}
$$
Soit $d(J)$ la date critique du processus.

On sait calculer la date du prochain événement :

$$ \text{si } \epsilon_j(t) = 0, \quad e(J) = d_j + (T_j - \tau_j) $$

$$ \text{si } \epsilon_j(t) = 1, \quad e(J) = \inf (d_j, x_j) $$

sachant que $d_j$ est de la forme : $\rho T_j + \tau_j$

## 2.Calcul des Γi.

On dénote par $\gamma_i(t)$ le travail fait par les tâches $J_{i+1}, \dots, J_n$ sur $[0,t]$. On doit vérifier :

$$ \Gamma_i = \gamma_i(\tau_i) $$

On sait calculer le travail fait par les tâches $J_{i+1}, \dots, J_n$ sur un intervalle $(t_1, t_2)$ séparant deux événements.

$$ w = \int_{t_1}^{t_2} \frac{\sum_{j>i} \epsilon_j(t) \lambda_j}{\Lambda_i + \sum_{j>i} \epsilon_j(t) \lambda_j} dt $$

$$ w = (t_2 - t_1) \cdot f \cdot $$

$$ \frac{1}{f} = 1 + \frac{\Lambda_i}{\sum_{j>i} \epsilon_j(t) \lambda_j} $$

Il faut donc connaitre les rapports $\frac{\lambda_j}{\Lambda_i}$
On calcule aisément ceci par récurrence :

$$ \frac{\lambda_j}{\Lambda_i} = \frac{\lambda_j}{\Lambda_{i+1}} \times \frac{\Lambda_{i+1}}{\Lambda_i} = \frac{\lambda_j}{\Lambda_{i+1}} \cdot \left( 1 + \frac{\lambda_{i+1}}{\Lambda_i} \right) $$

$$ \Rightarrow \quad \frac{\lambda_j}{\Lambda_i} = \frac{\lambda_j}{\Lambda_{i+1}} \left( \frac{1}{1 - \frac{\lambda_{i+1}}{\Lambda_{i+1}}} \right) = K \cdot \frac{\lambda_j}{\Lambda_{i+1}} $$

La grandeur K est indépendante de j :

$$ \text{On a donc : } f = \left[ 1 + \left[ \sum_{j>i} \epsilon_j \cdot \frac{\lambda_j}{\Lambda_i} \right]^{-1} \right]^{-1} $$

$$ \text{Donc : } \gamma_i(t_2) = \gamma_i(t_1) + (t_2 - t_1) f. $$

Si $t_2$ est la date $t_0 + \tau_i$, on calcule facilement

$$ \gamma_{i-1}(t_2) = \Gamma_i + C_i. $$

On peut donc poursuivre le calcul pour calculer $\Gamma_{i-1}$.
<figure><img src="image_22.png" /><figcaption>Organigramme du programme de simulation.</figcaption></figure>
ANNEXE V.

Programme de simulation permettant de suivre le déroulement d'une
configuration particulière avec un algorithme quelconque.

Cet algorithme permettra aussi de savoir si une configuration
particulière sera acceptée (du moins pendant un intervalle de temps fini).
On pourra donc comparer plusieurs algorithmes avec une configuration par-
ticulière.

On emploiera les mêmes notations que dans l'annexe IV.
ORGANIGRAMME.

<figure><img src="image_23.png" /></figure>
Dans le cas de RU.

remise à jour des r(J) :

I = tâche active sur [t,e]

$$r_e(I) = r_t(I) - (e - t)$$

les autres r sont inchangés

$$\text{si } r_e(I) = 0 \text{ alors } \varepsilon(I) = 0$$

Calcul des 1<sup>ers</sup> évènements :

si e(J) = d(J) l'évènement reste inchangé sauf si e = e(I).

Dans ce cas, e(J) devient e + T(I) - τ(I)

$$\text{si } e(J) = \text{activation, } e(J) \text{ devient : } e(J) + \tau(J)$$

si e(J) = fin possible du processus :

$$e(J) = e(J) + (e - t) \text{ sauf si } J = I.$$

Cas de ITSG.

remise à jour des r(J).

$$r(J) \rightarrow r(J) - \lambda(J) \times K$$

avec

$$K = \frac{1}{\sum \varepsilon(J) \lambda(J)}$$

Calcul des 1<sup>ers</sup> évènements :

si r(J) = 0 alors le prochain évènement est une activation

si r(J) ≠ 0, e(J) = inf (deadline, fin de processus).
Bibliographie

[1] M.S. FINEBERG et O. SERLIN. "Multiprogramming for hybrid computation"
Proc. AFIPS, FJCC (1967)

[2] O. SERLIN. "Scheduling of time critical processes"
Proc. SJCC, pp. 925-932. (1972)

[3] C.L. LIU et J.W.LAYLAND. "Scheduling algorithms for multiprogramming
in a real-time environment"
JACM, Vol 20, n°1, pp. 46-71 (Janv. 1973)

[4] J. LABETOULLE. "Un algorithme optimal pour la gestion des processus
en temps réel"
Revue RAIRO, AFCET (1974)

[5] A.L. SCHERR. "An analysis of time-shared computer systems"
MIT Press, Cambridge, Masso. (1967)

[6] L. KLEINROCK. "Time-shared systems. A theoretical treatment"
JACM, pp. 242-261. (April 1967)

[7] L. KLEINROCK. "Certain analytic results for time-shared processors"
Information processing 68, North-Holland publishing company
Amsterdam (1969)

[8] V. DONZEAU-GOUGE. "Etude de la gestion des contextes et de son
application au temps-réel"
Thèse de 3e cycle. Université Paris 6, (1974), (à paraître)

[9] M. MIKELSONS. "A flexible task scheduling scheme for a real-time environment"
IBM Research, Watson research center, (March 1969)
[10] H.L. MORGAN. "An interrupt based organization for management information systems"
CACM, Vol 13, n° 12, pp. 734-739 (Decem. 1970)

[11] R. BINDER. "Time constraints in interrupt-driven programs"
University of Hawaii, (July 1971)

[12] G.K. MANACHER. "Production and stabilization of Real-time task schedules"
JACM, Vol 14, n°3, pp. 439-465. (July 1967)

[13] R.R.MUNTZ and E.G.COFFMAN. "Optimal preemptive scheduling on two-processor systems"
IEEE Transactions on computers, Vol C18, n°11) pp.1014-1020
(Nov. 1969)

[14] T.G. PRICE. "An analysis of central processor scheduling in multiprogrammed computer systems"
Technical report No 57, Digital systems laboratory
Standford electronics laboratories, (Oct. 1972)