Frank Singhoff Bureau C-203 Université de Brest, …beru.univ-brest.fr/~singhoff/ENS/UE_temps_reel/CM/intro.pdf · Introduction aux systèmes temps réel Frank Singhoff Bureau C-203

Introduction aux systèmes temps réelFrank Singhoff

Bureau C-203

Université de Brest, France

Laboratoire Lab-STICC UMR CNRS 6285

[email protected]

UE systèmes temps réel Univ. Brest/Lab-STICC Page 1/35

Sommaire

1. Concepts de base.

2. A propos du temps réel dans les systèmes tempspartagés.

3. Cycle de vie d’un système temps réel.

4. Résumé.

5. Références.


Présentation, définitions (1)

• "En informatique temps réel, le comportement correct d’un systèmedépend, non seulement des résultats logiques des traitements, mais aussidu temps auquel les résultats sont produits" [STA 88].

• Objectifs :

Déterminisme logique : les mêmes entrées appliquées au systèmeproduisent les mêmes résultats.

Déterminisme temporel : respect des contraintes temporelles (ex :échéance).

Fiabilité : le système répond à des contraintes de disponibilité(fiabilité du logiciel et du matériel).

=⇒ Système prédictible : on cherche à déterminer a priori si le systèmeva répondre aux exigences temporelles.

• Un système temps réel n’est pas un système "qui va vite" mais u nsystème qui satisfait à des contraintes temporelles.



• Exemples de grandeur [ DOR 91, DEM 99] :

La milliseconde pour les systèmes radar.

La seconde pour les systèmes de visualisation humain.

Quelques heures pour le contrôle de productionimpliquant des réactions chimiques.

24 heures pour les prévisions météo.

Plusieurs mois ou années pour les systèmes denavigation de sonde spatiale.



• Classement des systèmes temps réel selon leurbesoin en garantie de service :

Garantie de service = niveau de respect descontraintes. Garanties déterministes, probabilistes ou“best effort”.

Systèmes temps réel dur ou critique .

Systèmes temps réel souple .

Systèmes temps réel ouvert ou fermé .



• Classement des systèmes temps réel selon leur environnement.

• Systèmes embarqués, ou Embedded systems, ou systèmesenfouis : systèmes informatiques dans lequel le processeur/calculateurest englobé dans un système plus large et/ou que le logiciel estentièrement dédié à une application donnée. (ex : une sonde spatiale, untéléphone mobile).

• Systèmes répartis : "Un système réparti est un ensemble de machinesautonomes connectées par un réseau, et équipées d’un logiciel dédié à lacoordination des activités du système ainsi qu’au partage de sesressources." Coulouris et al. [COU 94].

• Système réparti temps réel pour des raisons de :

Fiabilité (redondance).

Contraintes physiques, commerciales, industrielles.

Partage des ressources (données, périphériques, ... ).



• Problèmes liés aux systèmes embarqués :

Intervention humaine directe difficile voire impossible(contre-exemple : PathFinder).

• Problèmes liés aux systèmes répartis :

Localisation des ressources.

Hétérogénéité (matériel et logiciel).

Performance.

Peu de problèmes de synchronisation et de cohérencedans le contexte temps réel (ex : mise au point, e-mail).

Autres : sécurité, maintenance.


Exemple 1 : domaine de l’avionique

• Système temps réel critique :

Contraintes temporelles : temps de réponse, échéance, dated’exécution au plus tôt, cadence, etc.

Dimensionnement au pire cas et réservation des ressources.

Utilisation de redondance matérielle et logicielle.

Matériel et logiciel dédiés. Système fermé, validé a priori.

Système réparti synchrone : commandes de vol, radars, moteurs, etc


Exemple 2 : multimédia sur le Web

• Système temps réel souple :

RéseauProcesseur Processeur

Contraintes temporelles : gigue, délais de bout en bout, temps deréponse. Synchronisations intra et inter-flux.

Plate-forme généraliste. Non déterminisme temporel à cause dumatériel et du logiciel (ex : PC + windows).

Application interactive.

Nombre de flots inconnu.

Débits variables et difficiles à estimer hors ligne.


Autres exemples d’application

• Préface d’un livre sur le temps réel souple :"This book is about real-world programming ... So real-world programs(and real-world programmers) are all around us. What characterizes all ofthese real-world applications is a critical dependence on time." [GAL 95]

Transports (métro, spatial, aéronautique, automobile).

Médias (décodeurs numériques openTV).

Services téléphoniques (téléphone mobile, auto-commutateur).

Supervision médicale, écologique.

Système de production industriel : centrale nucléaire, chaîne demontage, usine chimique.

Robotique (ex : PathFinder).

etc...


Sommaire




4. Résumé.

5. Références.


Système temps partagé (1)

Abstractions + API

Matériel

Système d’exploitation

Applicatifs

• Objectifs :

Facilite l’accès aux ressources.

Masquer les ressources (multiprocesseur, disques RAID, mémoire).

Recherche de l’équité. Absence de famine. Maximise le débit global.

Sûreté des applications (protection mémoire).

Vivacité du système (inter-blocage).


Système temps partagé (2)

Bus

Périphériques

Mémoire E/SProcesseur

Mono-programmation : interaction synchrone entre lecouple processeur/mémoire et les périphériques.

Multi-programmation : interaction asynchrone. Leprocesseur profite du temps ainsi libéré pour effectuerd’autres traitements : il ordonne son travail.


Le processeur (1)

• Architecture : caches internes, pipe-line, prédiction de branchement(ex : Pentium).

CPU

Liste de tâches

• Ordonnancement (ex : Linux) :

Tâches bloquées, prêtes ou élues.

Priorité = nice + priorité dynamique proportionnelle au tempsd’attente dans l’état "prêt".

Equité, pas de prise en compte de l’urgence ou de contraintetemporelle. Politique généralement opaque. Temps de réponseinconnu.


Le processeur (2)

=⇒ Utilisation d’ordonnanceurs spécialisés (priorité, préemption, etc ).

��

��

��

��

��

��

��

��

��

��

��

��

��

��

CiSi

k.Pi ....(k+1).Pi (k+2).Pi

<= Di

• Modèle de tâches de Liu et Layland [ LIU 73] :

Tâches périodiques et indépendantes.

Borne maximale sur le temps d’exécution : Ci (capacité).

Période d’activation : Pi.

Arrivée de la tâche dans le système : Si.

Délai critique relatif à la période : Di.

Echéance sur requête : Di = Pi.


Le processeur (3)

• L’algorithme Rate Monotonic :

Priorités fixes. Priorités = inverse de la période.Election de la plus forte priorité.

Analyse hors ligne =⇒applications statiques.

Cas préemptif + modèle de Liu et Layland =⇒ordonnançabilité =

n∑

i=1

Ci

Pi

≤ n(21

n − 1)

! Condition suffisante mais non nécessaire.


Le processeur (4)

• Exemple :

T2 : C2=3 ; P2=5 (blanc)

5 0 10 15

RR

RM

T1 : C1=3 ; P1=10 (gris)

T3 : C3=3 ; P3=10 (noir)

• Round-robin avec un quantum d’une unité de temps.Echec à l’instant 5.


Les entrées/sorties (1)

Bus

Périphériques

MémoireProcesseur

Caches

E/S

Contrôleur DMA

• Modes d’échanges :

Scrutation active de l’unité : polling. Monopolise le processeur.Comportement temporel déterministe.

Interruptions.

Accès direct à la mémoire (DMA ; Direct Memory Access).Contention sur le bus. Comportement temporel indéterministe.


Les entrées/sorties (2)

Tâche x

Restauration

interruption

Traitement

Prise en compte

contexteSauvegarde

contexte

Tâche xinterruption

• Interruptions et préemptivité :

Priorité des interruptions non modifiable par le concepteur.

Nombre d’occurrences inconnu. Acquisition et traitement successifs=⇒ éventuellement long.

UNIX = verrouillage important, peu préemptif.

=⇒ Découplage acquisition et traitement des interruptions. Co-gestiontâches/interruptions. Noyau préemptif. Choix de matériel adapté. Polling.


Synchronisation, autres ressources (1)

P(sem)

V(sem)

utilise_la_ressource(k)

P(sem)

V(sem)

utilise_la_ressource(k)

Tâche jTâche i

s.cpt=s.cpt-1; if (s.cpt<0)

}

P(s) {

}

{ ajouter_tâche_courante(s.file); bloquer_tâche();

{

} }

V(s)

s.cpt=s.cpt+1;

{

réveiller_tâche(); sortir_première_tâche(s.file);

if (s.cpt<=0)

• Synchronisation, communication et accès aux ressourceseffectués grâce à des sémaphores:

Sémaphore = compteur entier/boolean + file d’attente.

Utilisation : exclusion mutuelle, paradigme classique de coopération(producteur/consommateur, lecteur/rédacteur).


Synchronisation, autres ressources (2)

P(mutex)

P(mutex)

Arrivée

Bloquée

Préemptée

V(mutex)

T1

T3

T2

• Problèmes :

Impact sur l’ordonnancement car tâches bloquées.

Gestion FIFO =⇒ accès non prioritaire aux ressources.

Inversion de priorité : tâche de faible priorité bloquant une tâche deplus forte priorité pendant une durée inconnue.

=⇒ Héritage de priorité.UE systèmes temps réel Univ. Brest/Lab-STICC Page 21/35

Sommaire




4. Résumé.

5. Références.


Génie logiciel et temps réel (1)

• Génie logiciel = méthodes, modèles et ateliers préconisés pourmaîtriser la qualité des produits, leur coût et le respect des délais.

• Spécificités des applications temps réel :

Concurrentes et synchronisées. Manipulation du temps.

Coût de développement trés lourd (validation temporelle et logique,applications peu flexibles).

Maintenance souvent impossible (téléphone mobile, sonde spatiale)=⇒ erreur souvent irréversible.

Conséquences tragiques (vies humaines, faillites économiques).

=⇒ Utilisation de méthodes, outils afin d’éviter au mieux tous c es

pièges.



du logiciel

Conception du

Codage/réalisationdu logiciel

Recette/ validationdu logiciel

Tests unitaires

du logicielpuis d’intégration

Spécification

logiciel

• Spécification = quoi faire ? Conception = comment faire ?• Notions de méthodes, modèles et outils.• Couverture partielle ou totale du cycle. La "couverture"dépend aussi du domaine applicatif. Un modèle peutcouvrir plusieurs phases d’un projet.



• Vérifications amont d’un système.• Etude AMRDEC:

70% des anomalies sont introduites lors de la phase deconception.

3% d’entre elles trouvées lors de la conception. Cout :x1

Test unitaire : détection supplémentaire de 20% desanomalies. Cout : x5

Test d’intégration : détection supplémentaire de 10%des anomalies. Cout : x16

• Objectifs: trouver le plus d’anomalies lors de la phasede conception => Vérifications en amont.



1. Méthodes de spécification et de conception :Analyse d’ordonnancement.Réseaux de Petri.

2. Environnement d’exécution et de développement :Exécutifs temps réel embarqués.Langages pour le temps réel.


Les réseaux de Petri

Prêt àdéposer

Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer

Consommation

Place, jeton, transition. Modèle à états.

Vérification logique, éventuellement temporelle.

Etude du graphe d’état : vivacité (inter-blocage),respect d’invariant (ex : exclusion mutuelle).



ConsommationPrêt àdéposer

Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer







Fin deproduction

Placeslibres

Placesoccupées

Prêt àconsommer

P1

Fin deconsommation

��

��

��

��

��

��

Production

T1 T3

Retirer

T4T2

P5P4 P6

P2 P3

Déposer





Exécutif et OS temps réel (1)1. Exécutif (ou moniteur) :

Système de faible envergure (ex : pour application embarquée).

Collection de primitives =⇒ édition de liens.

Parfois mono-programmé (systèmes cycliques, calendrier). Avec ou sansprotection mémoire.

Environnement de compilation croisée.

2. Système d’exploitation :

Interaction par appels systèmes.

Système multi-programmé (souvent POSIX).

Avec ou sans environnement de compilation croisée.

AEnvironnements spécifiques. Exemple : compilation

croisée


Exécutif et OS temps réel (2)

• La compilation croisée :

séries, etcEthernet , liens. TCP/IP sur

. TFTP, NFSEnvironnement dedéveloppement

Disque NFS

Machine cible

Hôte (windows)

OS temps réel

rsh

GDB RGDB


Langage pour le temps réel (1)

• Principaux critères de choix :

Déterminisme temporel et logique validés. Fiabilité.

Présence d’abstractions "temps réel" (tâches,synchronisation, horloges, etc).

Accès aux ressources de bas niveau.

Portabilité, normalisation.

Compilation séparée.

Performance.

• Deux approches : langages de bas niveau et de hautniveau.



• Langages de bas niveau : C/C++, Assembleur.

Largement diffusés et utilisés à ce jour.

Accès direct aux ressources de bas niveau. Idéal pourles E/S.

Doit être couplé avec les services du système (poursynchronisation, ordonnancement) =⇒bibliothèques.

Langage généralement restreint (sous-partie ayant uncomportement temporel déterministe facile à évaluer).

Peu adapté aux logiciels complexes et/ou volumineux.

Pas de normalisation, donc peu de portabilité : logiciel“ad hoc” =⇒ comportement bibliothèques.



• Langages de haut niveau : Ada 2012 [ ZAF 99]

Langage conçu, entre autres, pour le support desapplications temps réel.

Abstractions temps réel : tâche, interruption,ordonnancement (priorité fixe et dynamique),synchronisation (sémaphore), timer et gestion dutemps, outils de communication (rendez-vous).

Interface/syntaxe et COMPORTEMENT du langagenormalisés par l’ISO =⇒ forte portabilité.

Compilation séparée. Typage fort =⇒ langage trèsfiable. Adapté à la production de logiciels volumineux.

Langage complexe.


Résumé

• Notion de base sur les systèmes temps réel : prise encompte du temps, concurrence et synchronisation.

• Contraintes spécifiques : sûreté fonctionnelle ettemporelle, répartition, environnement (systèmeembarqué), performance.

• Cycle de vie d’un système temps réel : méthodes etoutils de spécification/conception. Plates-formes dedéveloppement/exécution.


Références (1)

[BER 98] G. Berry. « The Foundations of Esterel ». in Proof, Language and Interaction:Essays in Honour of Robin Milner, G. Plotkin, C. Stirling and M. Tofte, editors, MIT Press,1998.

[COU 94] G. Coulouris, J. Dollimore, and T. Kindberg. Distributed Systems—Concepts andDesign, 2nd Ed. Addison-Wesley Publishers Ltd., 1994.

[DEM 99] I. Demeure and C. Bonnet. Introduction aux systèmes temps réel. Collectionpédagogique de télécommunications, Hermès, septembre 1999.

[DOR 91] A. Dorseuil and P. Pillot. Le temps réel en millieu industriel. Edition DUNOD,Collection Informatique Industrielle, 1991.

[GAL 95] B. O. Gallmeister. POSIX 4 : Programming for the Real World . O’Reilly andAssociates, January 1995.


Références (2)

[LIU 73] C. L. Liu and J. W. Layland. « Scheduling Algorithms for Multiprogramming in a HardReal-Time Environnment ». Journal of the Association for Computing Machinery,20(1):46–61, January 1973.

[STA 88] John Stankovic. « Misconceptions about real-time computing ». IEEE Computer,October 1988.

[ZAF 99] L. Zaffalon and P. Breguet. Programmation concurrente et temps réel avec ADA 95.Hermès, 1999.


Documents

Frank Singhoff Bureau C-203 Université de Brest, …beru.univ-brest.fr/~singhoff/ENS/UE_temps_reel/CM/intro.pdf · Introduction aux systèmes temps réel Frank Singhoff Bureau C-203