59
14/10/04 1 Technologie des micronoyaux et des noyaux temps-réel Concepts de base et exemples Jean-Charles Fabre 14/10/04 2 Pourquoi? ! Caractéristiques des systèmes embarqués ! Logiciel de commande-contrôle de processus industriel ! Fonctions applicatives, de gestion de ressources, de gestion des interactions avec l’environnement ! Forte connexion avec des équipements physiques ! Stratégies de réalisation ! Développement spécifique (stand-alone) ! Développement croisé d’un logiciel agrégeant toutes les fonctions nécessaires ! Génération d’une image mémoire + chargement sur cible ! Développement multicouche ! Logiciel générique de gestion de ressources (noyau) ! Applications découpées en tâches indépendantes

Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

  • Upload
    others

  • View
    21

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 1

Technologie des micronoyauxet des noyaux temps-réel

Concepts de base et exemples

Jean-Charles Fabre

14/10/04 2

Pourquoi?! Caractéristiques des systèmes embarqués

! Logiciel de commande-contrôle de processus industriel

! Fonctions applicatives, de gestion de ressources, de gestion desinteractions avec l’environnement

! Forte connexion avec des équipements physiques

! Stratégies de réalisation! Développement spécifique (stand-alone)

! Développement croisé d’un logiciel agrégeant toutes les fonctionsnécessaires

! Génération d’une image mémoire + chargement sur cible

! Développement multicouche! Logiciel générique de gestion de ressources (noyau)

! Applications découpées en tâches indépendantes

Page 2: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 3

Comment?

processor

I/Odevices

Applicationfunctions

Resources mgt (clk, mem,etc.)

I/O handling

(Int, E/S, etc.

Logiciel C & C

14/10/04 4

Comment?

processor

I/Odevices

Applicationfunctions

Resources mgt (clk, mem,etc.)

I/O handling

(Int, E/S, etc.

Logiciel C & C

processor

I/Odevices

Logiciel C & C RTK DRV

Page 3: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 5

Noyaux Temps-Réel pourSystèmes embarqués

Production etProduction ettransport dtransport d’é’énergienergie

MMééddéécine cine et santet santééIndustriesIndustries

manufacturimanufacturièèresres

EspaceEspace DDééfensefense

TransportsTransports

AutomobileAutomobile

TTéélléécommunicationscommunications

14/10/04 6

Noyaux Temps-Réel pourSystèmes embarqués

Production etProduction ettransport dtransport d’é’énergienergie

MMééddéécine cine et santet santééIndustriesIndustries

manufacturimanufacturièèresres

EspaceEspace DDééfensefense

TransportsTransports

AutomobileAutomobile

TTéélléécommunicationscommunications

Interface noyau (API)

SYN COM SCHMEM

Noyau Temps-RéelPlateforme matérielle (HW)

Applications

Page 4: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 7

Couches exécutives…

mémoiretâches

ordonnancement

sémaphoresdrivers horloge

fichiers

processus

protocolesmessages

Interpréteurde commande

noyau

OS

Intergiciel

distribution

autres extensions

objets

gestion denoms

IHM

transactions

Basesde données

messageriesGestion

de configuration

administration

14/10/04 8

Des exemples?! Applications spatiales

! VxWorks

! ORK

! Avionique! LynxOS

! Commande-contrôle! QNX

! Téléphonie! Chorus

! Grand public! Mach (dans MacOS X )

! Windows CE

! Nouvelles générations! Choices

! L4

! ExoKernel

! Spin

! Think

! C5

Recherche d’une meilleureConfigurabilité, réutilisation,Flexibilité, portabilité,« minimum footprint », etc.

Page 5: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 9

Concepts de base

14/10/04 10

Concepts de base! Tâches

! Plusieurs programmes peuvent s’exécuter en « même temps »

! Sur un seul processeur, on partage équitablement l’exécutionentre les différents programmes ou selon un critère d’ordre

! Une tâche = un programme qui s’exécute

! Temps! Horloge matérielle cadence l’exécution des instructions

! On peut aussi définir des timers :! Init_timer(T,12) ! décrémentation à chaque top d’horloge

! Lorsque T=0 ! signal renvoyé au programme

! Ressources! Partage de la mémoire entre toutes les tâches (programmes)

! Entrées/sorties: notion de pilote (drivers)

Page 6: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 11

Concepts de base! Gestion des tâches

! Création, destruction dynamique

! Ordonnancement

! Synchronisation

! Communication

! Gestion du temps! Horloge

! Timers

! Gestion des ressources! Mémoire

! Entrées/sorties! drivers

! interruptions

14/10/04 12

Concepts de base! Gestion des tâches

! Création, destruction dynamique

! Ordonnancement

! Synchronisation

! Communication

! Gestion du temps! Horloge

! Timers

! Gestion des ressources! Mémoire

! Entrées/sorties! drivers

! interruptions

APIfonctions

fonctions

fonctions

fonctions

fonctions

fonctions

Fonctionnement autonome

Fonctionnement autonome

Fonctionnement autonome

Page 7: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 13

RTK vs Operating Systems! RTK

! Factorisation des fonctionsélémentaires nécessaires à

! la gestion de tâche,

! la communication (IPC),

! la synchronisation

! La gestion de ressources:! Logiques

! Physiques

! Le minimum nécessaire à laréalisation d’applicationsembarquées

! Les propriétés:! Minimalité

! Prédictabilité

! Performance

! OS! Toutes les fonctions de base

nécessaires à l’exécution desapplications

! Gestion d’applications

! Gestion de fichiers

! Gestion d’E/S

! Gestion réseau

! MMI (Men Machine interface)

! Etc……

! Exemples: Unix, Windows

RTK DRV

fichiers

protocoles

communication

MemoireVirtuelle

IHM

14/10/04 14

Principes! OS traditionnels :

! problèmes : complexité, portabilité, extensibilité,

configurabilité, adaptabilité

! Objectifs:! transparence de la distribution,

! configuration dynamique,

! développement et intégration de drivers

! modularité et réutilisation de serveurs existants

! multi-threading et aspects temps-réel

! compatibilité avec les standards (ex: Posix)

! portabilité, efficacité, temps-réel

Page 8: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 15

datacode

Abstractions de base! Tâches, processus, objet, acteur, agent

! objet de structuration des applications

! contexte d’exécution (espace d’adressage:data+code)

! une ou plusieurs unités d’exécution : les threads

! Communication: boîtes aux lettres, boîtes à messages, ports

! objet de structuration des interactions

! boites à messages identifiés

14/10/04 16

Abstractions de base! Communication

! par message avec identification source-destination

! IPC Inter-Process Communications

! Désignation! ports: ce sont des boîtes à messages (émission / réception)

! groups: groupes de portes protocoles simples (1/N, N/N, etc.),garantie? QoS?

! Ordonnancement : différentes politiques (scheduling)

! Gestion mémoire: différents niveaux de mémoire

! Interruptions: différents niveaux d’IT (! IT Handler)

! Synchronisation: sémaphores et autres techniques

Page 9: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 17

Modèle d’architecture

IPC(messages / ports)Real-Time

executiveMemory

management

IT, traps, MMU...micro-core executive (machine dependent)

Application Programming Interface

Multi-threadedactive objects

port

message

Subsystem

14/10/04 18

Modèle comportemental

Application Programming Interface

Fonctionnement explicite(appels des fonctions noyau)

Fonctionnement implicite(fonction internes)

SchedulerIT,

E/S,Etc.

clock E/S IT

Multi-threadedactive objects

port

message

Subsystem

Page 10: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 19

Profil d’exécution

Application Programming Interface

Fonctionnement explicite(appels des fonctions noyau)

Fonctionnement implicite(fonction internes)

SchedulerIT,

E/S,Etc.

clock E/S IT

Début d’exécutiondu thread

Fin d’exécutiondu thread

Appel 1 S SA2 S, etc. A

3 S

Temps de réponse

14/10/04 20

Notion de tâche! Définition

! Une tâche représente l’exécution d’un programme

! Programme: fichier binaire (support externe)

! Tâche: exécution d’un programme en mémoire

! Exemple:! Programme Reveil (nom, heure, clock)

! Begin

If (clock=heure) then

! sonnerie (clock)

! print (« Bonjour », nom)

Endif

! End

! Décomposition des applications! Modules et appels de procédure ou de fonction

! Ensemble de tâches indépendantes et communicantes

RTK DRV

Reveil(Bob, 6:00

R3)

Reveil(Tom, 6:30,

R1)

Reveil(Elsa, 8:00,

R4)

Reveil(Bill, 6:45,

R2)

Page 11: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 21

Modèle d’exécution! Exécution concurrente

! À l’intérieur d’une tâche, plusieurs activités (fils de contrôle outhread, en anglais) peuvent s’exécuter en même temps.

! Un thread, c’est quoi? Une procédure, une fonction, unmorceau de programme.

! A quoi ça sert? A concevoir des tâches dont les fonctionspeuvent s’exécuter sans attendre la fin d’une autre!

! Exécution séquentielle vs. Exécution concurrente! Séquentiel:

! Concurrent:

F G H G H F FF

GH

GH

F F

t0 t2 t3

14/10/04 22

Comparaison des modeles…! Pourquoi ce phénomène?

! Il y a des temps de blocage (E/S) dans l’exécution d’unprogramme (ex: lecture/écriture sur un périphérique, attentemsg, etc.).

! Ces temps de blocages sont perdus en mode séquentiel

! Il sont attribués à l’exécution d’autres threads en modeconcurrent

FExécution

Attente E/SExécution

GExécution

Attente E/SExécution

ExécutionExécutionExécution

Attente E/SExécution

Fin de G

Fin de G

Récupération du temps De blocage de F pour exécuter Une partie de G

Exécution H

Page 12: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 23

Introduction à l’ordonnancement! Principe

! Gérer l’exécution concomittante de plusieurs tâches

! Définir une politique d’élection d’une tâche parmi N! N tâches prêtes à l’exécuter

! Choisir une tâche! Selon une relation d’ordre

! Classement par priorité

! Classement par échéance

! De façon équitable

! Cyclique en allouant un espace temps à chaque tâche

! Déterminer quand cette procédure d’élection doit s’effectuer! A la terminaison d’une tâche

! Lors de la suspension d’une tâche (suspension volontaire, E/S,…)

! De façon périodique (donc temporelle)

Pro

cess

eur

14/10/04 24

Election

Suspension

Modélisation de l’ordonnancement

READY EXEC

WAIT

Task_create

Ces tâches sont prêteset en attente du CPU

Une seule tâche est active

Des tâches sont en attente: E/S, accès à une ressource occupée, etc.

Fin d’E/S ou d’autre condition

de blocage

Demande d’E/S ou D’accès à une

Ressource occupée.

Page 13: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 25

Introduction à la synchronisation! Principe

! Il existe des ressources partagées dans un système;

! Ces ressources partagées ont une représentation informatique.

! Les tâches pouvant s’exécuter de façon discontinue, il peut yavoir des conflits pour accéder à une ressource partagée.

! La zone de code dans un programme qui accède à uneressource partagée est appelée « section critique ».

Ressourcepartagée

Principe de l’exclusion mutuelle:Indépendamment de l’ordonnancement

des tâches, une tâche et une seulepeut accéder à la ressource partagée.

Section critique Section critique

14/10/04 26

Modélisation & synchronisation

Début Section critique

Execution Section critique

Fin Section critique

Thread 1 (t1) Thread 2 (t2)

t1 et t2 sont concurrents pour accéder à la section critique

Page 14: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 27

Modélisation & synchronisation

Début Section critique

Execution Section critique

Fin Section critique

Thread 1 (t1) Thread 2 (t2)

t1 a gagné le « jeton » et s’exécute en section critique SEUL, t2 est en attente

14/10/04 28

Modélisation & synchronisation

Début Section critique

Execution Section critique

Fin Section critique

Thread 1 (t1) Thread 2 (t2)

t1 termine l’exécution en section critique et relâche le « jeton »

Page 15: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 29

Modélisation & synchronisation

Début Section critique

Execution Section critique

Fin Section critique

Thread 1 (t1) Thread 2 (t2)

t2 récupère le « jeton » et s’exécute en section critique SEUL

14/10/04 30

Modélisation & synchronisation

Début Section critique

Execution Section critique

Fin Section critique

Thread 1 (t1) Thread 2 (t2)

t2 termine l’exécution en section critique et relâche le « jeton »

Page 16: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 31

Exemple! Principe

! Programme de gestiond’images

! Stockage d’images dans untableau

! Fonctions d’accès

! Clients multiples

! Tâche Buffer: 2 fonctions! Read_image

! Store_image

! Types & structures dedonnées

! Type image 5 mega pixels

! Array [1,1000] of image

Read_image Store_image

Tâche Image_Buffer

Thread 1 Thread 2

RS

ExécutionExécutionExécution

Attente E/SExécution

14/10/04 32

Notion de partage

Read_image Store_image

Tâche Image_Buffer

Thread 1 Thread 2

ExécutionExécutionExécution

Attente E/SExécution

! Accès multiples à desvariables globales partagées

! Les threads peuvent accéderaux mêmes variables

! Les threads peuvent êtreinterrompus lors de lamanipulation de ces variables

! On ne peut pas faired’hypothèse a priori surl’entrelacement des threads(échéance temporelle,priorité, etc.)

! Toute zone de code quimanipule des donnéespartagées et considéréecomme critique:

! Notion de section critique

Page 17: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 33

Read_image Store_image

Tâche Image_Buffer

Thread 1 Thread 2

Notion de partage! Accès multiples à des

variables globales partagées! Les threads peuvent accéder

aux mêmes variables

! Les threads peuvent êtreinterrompus lors de lamanipulation de ces variables

! On ne peut pas faired’hypothèse a priori surl’entrelacement des threads(échéance temporelle,priorité, etc.)

! Toute zone de code quimanipule des donnéespartagées est considéréecomme critique:

! Notion de section critique

Store_imageBeginScan(out X.jpg);Get_Free(out I);Buffer[I]:=X.jpg;Next_Free(I);End

Read_imageBeginGet_Full(out I);X.jpg=Buffer[I];Next_Full(I);Send(X.jpg); End

14/10/04 34

Read_image Store_image

Tâche Image_Buffer

Thread 1 Thread 2

Store_imageBeginScan(out X.jpg);Get_Free(out I);Buffer[I]:=X.jpg;Next_Free(I);End

Read_imageBeginGet_Full(out I);X.jpg=Buffer[I];Next_Full(I);Send(X.jpg); End

Notion de partage! Get_Full (out X)

! Rends le premier élémentcontenant une image: Full

! Next_Full (X)! Marque l’élément full comme

vide: Full:=Full+1

! Get_Free (out X)! Rends le premier élément

libre: Free

! Next_Free (X)! Marque l’élément libre:

Free:=Free+1

Premier « plein »:Full

Premier « libre »:Free

Global_variables: Integer P = 0; (mod N)Integer L = 1; (mod N)Buffer array [1..N] of images

Page 18: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 35

Notion de partage! Supposons: P=1; L=4

! Exécution: Deux demandessimultanées d’exécution de Store_image

Tâche Image_Buffer

Read_image Store_image

Thread 1 Thread 2

Store_imageBeginScan(out X.jpg);Get_Free(out I);Buffer[I]:=X.jpg;Next_Free(I);End

Read_imageBeginGet_Full(out I);X.jpg=Buffer[I];Next_Full(I);Send(X.jpg); End

Global_variables: Integer P = 0; (mod N)Integer L = 1; (mod N)Buffer array [1..N] of images

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Buffer[I]:=X.jpg;Next_Free(I);End

Buffer[I]:=X.jpg;Next_Free(I);End

I=4

I=4

Free=5

Free=6

Premier « plein »:Full

Premier « libre »:Free

I: variable locale à chaque thread

14/10/04 36

Tâche Image_Buffer

Full=1 Free=6

Notion de partage! Supposons: P=1; L=4

! Exécution: Deux demandessimultanées d’exécution de Store_image

! Commentaires! La case 4 contient l’image jaune

! La case 5 ne contient rien!!! BUG!

! L’image verte a été perdue!!! BUG!

! La valeur de L est bonne…. Mais…

! Lorsque on fera Read_image sur lacase 5, il y aura une erreur puisque la

case est vide!!!!! BUG!

! Résultats corrects

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Buffer[I]:=X.jpg;Next_Free(I);End

Buffer[I]:=X.jpg;Next_Free(I);End

I=4

I=4

Free=5

Free=6

I: variable locale à chaque thread

Page 19: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 37

Notion de synchronisation! Comment empêcher

l’entrelacement?! Interdire au noyau de

commuter d’un thread surl’autre?

! Impossible

! Trop risqué!

! La solution:! Faire en sorte que l’accès à

tout objet partagé soit

EXCLUSIF!

! La notion de sémaphore estfaite pour ça!

! Prise de sémaphore

! Manipulation exclusive

! Relâchement du sémaphore

! Supposons: P=1; L=4

! Exécution: Deux demandessimultanées d’exécution de Store_image

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Buffer[I]:=X.jpg;Next_Free(I);End

Buffer[I]:=X.jpg;Next_Free(I);End

I=4

I=4

Free=5

Free=6

I: variable locale à chaque thread

Insécable(atomique)

14/10/04 38

Notion de synchronisation! Comment empêcher

l’entrelacement?! Interdire au noyau de

commuter d’un thread surl’autre?

! Impossible

! Trop risqué!

! La solution:! Faire en sorte que l’accès à

tout objet partagé soit

EXCLUSIF!

! La notion de sémaphore estfaite pour ça!

! Prise de sémaphore

! Manipulation exclusive

! Relâchement du sémaphore

! Supposons: P=1; L=4

! Exécution: Deux demandessimultanées d’exécution de Store_image

Store_imageBeginScan(out X.jpg);Get_sem(Free);Get_Free(out I);

Store_imageBeginScan(out X.jpg);Get_sem(Free);

Buffer[I]:=X.jpg;Next_Free(I);Release_sem(Free);End

Get_Free(out I);Buffer[I]:=X.jpg;Next_Free(I);Release_sem(Free);End

I=4

I=5

Free=5

Free=6

Page 20: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 39

Notion de synchronisationAPRES

Store_imageBeginScan(out X.jpg);Get_sem(Free);Get_Free(out I);

Store_imageBeginScan(out X.jpg);Get_sem(Free);

Buffer[I]:=X.jpg;Next_Free(I);Release_sem(Free);End

Get_Free(out I);Buffer[I]:=X.jpg;Next_Free(I);Release_sem(Free);End

I=4

I=5

Free=5

Free=6

AVANT

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Store_imageBeginScan(out X.jpg);Get_Free(out I);

Buffer[I]:=X.jpg;Next_Free(I);End

Buffer[I]:=X.jpg;Next_Free(I);End

I=4

I=4

Free=5

Free=6

Insécable(atomique)

14/10/04 40

Principe des sémaphoresGet_sem, Release_sem

! Fonctionnement:! Le noyau interdit le basculement pendant l’exécution de Get

! Si « le sémaphore est pris » alors le thread demandeur attend

! Implémentation! Un sémaphore correspond à un entier

! La valeur est 1 pour l’exclusion mutuelle

! L’idée de l’algorithme du Get_sem :! Si (valeur = 0) alors attendre dans une file d’attente

! Sinon valeur:=valeur-1;

! L’idée de l’algorithme du Release_sem :! Si « thread en attente » alors réveiller le premier

! Sinon valeur:=valeur+1;

! Le noyau garantit que ces fonctions sont insécables!

Page 21: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 41

Notion de timer! Définition/principe

! Un timer permet au programmeur d’application de gérer leséchéances temporelles

! Un timer peut être vu comme un compteur qui se décrémente

! Lorsqu’il passe a « zéro », un signal est envoyé au thread qui l’ainitialisé

! Exemple:! Set_timer (20 ms)! Décrémentation toutes les 20 µs

! 20 µs est donc la précision de la mesure

! Résolution de l’horloge système à 20 µs (est un exemple)

! Différent de l’horloge physique qui cadence l’exécution desinstructions élémentaires.

14/10/04 42

Notion d’ordonnancement! Principe

! Tâches et états! Plusieurs tâches/threads peuvent être prêtes à s’exécuter

! D’autres sont en attente (E/S, synchronisation, message, etc.)

! Sur un processeur, une seule tâche est « en cours »!

READY

WAIT

SCHEDULER RUNNINGsleep wakeup

create

yield

Le premier objectif de l’ordonnanceur (scheduler) est desélectionner parmi les tâches prêtes, celle qui va s’exécuterselon un certain nombre de critères: élection pour exécution!

Suspend(by scheduler)

Suspend(by task)

Page 22: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 43

Critères d’ordonnancement! Choisir la tâche prête, qui est….

! La prochaine dans l’ordre d’arrivée (FIFO)

! La plus urgente selon:! Son niveau de priorité (PRIORITY)

! Son échéance temporelle (EDF)

! FAQs (Frequently Asked Questions)

! Combien de temps une tâche s’exécute-t-elle après être sélectionnée?

! Un certain temps (Time Sharing), e.g. 10ms

! Jusqu’à ce qu’elle s’arrête d’elle même

! Y-a-t’il différents modèles de tâches?

! Les tâches a-périodiques:! Elles sont prises en compte, activées quand elles arrivent!

! Les tâches périodiques! Elles sont activées à intervalle temporel fixe (période)

14/10/04 44

Critères associés aux tâches! Le modèle

! A-périodique: systèmes réactifs asynchrones(event->task)

! Périodique: systèmes en boucle (timer->task)

! Les paramètres temporels! r (release time) :heure de déclenchement

! C (worst-case Computation time): durée au pire (WCET)

! D (relative Deadline): échéance temporelle

! T (Task period): période (pour les tâches périodiques :-)

! Commentaires! Le paramètre T est absent pour les tâches apériodiques

! Les 4 paramètres modélisent les tâches périodiques! rk=r0 + kT

! dk=rk + D (si D=T, l’échéance équivaut à la période)

! 0 < C ≤ D ≤ T

Page 23: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 45

Réflexions sur les critères! La qualité de l’ordonnancement dépend de la détermination

exacte de ces critères

! En général, les durées d’exécution des fonctions du noyau nepeuvent pas être négligées:

! Commutation de tâche

! Durée des appels noyaux

! Exécution scheduler

! estimation des temps d’exécution ➜ inclusion dans WCET (tâche)

! Implications et autres commentaires:! L’exécution des fonctions du noyau doit être déterministe

temporellement

! Un temps d’exécution maximum doit pouvoir être déterminé pour cesopérations

! Le temps de réponse peut être égal au temps d’exécution lorsque latâche est immédiatement élue, sans E/S et sans pré-emption

! Préemption = suspension de l’exécution d’une tâche pour en exécuterune autre.

14/10/04 46

Qques approches classiques! FIFO scheduling policy

! Les tâches les plus anciennes (temporellement) sont les premières! Les tâches courtes sont pénalisées par les longues qui les précèdent

! Shortest First scheduling policy! Les tâches sont ordonnées par leur durée (WCET)! Les tâches longues sont pénalisées

! Variante: ordre = durée restante

! Round-Robin scheduling policy! Notion de time-slice (10 à 100ms)! exec(10ms)"stop"autres"exec(10ms)" stop"autres"exec(10ms)

! Constant priority scheduling policy! Classement des tâches par priorité fixe (tâche, priorité)! Les tâches de basse priorité peuvent attendre indéfiniement

! Variante: la priorité change en fonction du temps d’attente

Page 24: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 47

Sur l’importance des choix…! Tâches

! T1 contrôle moteur! Périodique

! D=T=320ms

! T2 commande direction! Sporadique

! D=21ms

! Processeur TORTUE! 1 Mips

! Temps de commutation: 1ms

! WCET(T1)=270ms

! WCET(T2)=15ms

! Scheduling policy! Earliest Deadline First (EDF)

Le Lièvre et la Tortue (Jean De La Fontaine, Fable VI, 17ième siècle)

! Tâches! T1 contrôle moteur

! Périodique

! D=T=320ms

! T2 commande direction! Sporadique

! D=21ms

! Processeur LIEVRE! 10 Mips

! Temps de commutation: 0ms

! WCET(T1)=27ms

! WCET(T2)=1,5ms

! Scheduling policy! FIFO sans préemption

14/10/04 48

Sur l’importance des choix…

T1 T2 T1

T1 T2

S

temps

t0 ti ti+16 t0+276

D(T1)=320sD(T2)=21s

LA TORTUE

ET

LE LIEVRE

T1

T1 T2

ti ti+21

CRASH !!!!Missed Deadline ➡

t0+27t0+28,5

Tout••••••••••

Doucement…

WCET(T1)=270ms et WCET(T2)=15ms

WCET(T1)=27ms et WCET(T2)=1,5ms

Page 25: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 49

Propriétés de l’ordonnancement! Ensemble de tâches

! Une application temps réel estspécifiée par un ensemble detâches (task set) ayant desparamètres temporels(r,C,D,T)

! Types d’ordonnancement! Hors ligne (off-line) ou en-

ligne (on-line)

! Pré-emptif ou non-préemptif

! « Au mieux » (best effort)

! Temps-réel « dur »⇒ pas de fautes temporelles

! Propriétés! Un ensemble de tâches est

« ordonnançable » si on peutsatisfaire les contraintestemporelles de cet ensemblede tâches

! Un test d’ordonnancementpermet de savoir si unensemble de tâchespériodiques est« ordonnançable » selon unepolitique d’ordonnancement

! Un test d’acceptation en-lignepermet de savoir si unenouvelle tâche peut êtreacceptée tout en permettantde satisfaire les échéances

14/10/04 50

Quelques mesures! Temps de réponse: TR = e-r

! UtilisationU = Σn

i=1 Ci / Ti! Pour un ensemble de n tâches périodiques

! ChargeU = Σn

i=1 Ci / Di! Pour un ensemble de n tâches périodiques

! LaxitéLi(t) = Di - ΣjCj(t)

! La laxité à l’instant t est le temps maximum pendant lequel leprocesseur reste oisif (idle) sans qu’il y ait dépassement d’échéance

! La somme sur j correspond au temps d’exécution restant de toutes lestâches (incluant i) qui sont déclenchées à t et qui précèdent i dans laséquence d’exécution

Page 26: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 51

Exemple:Rate Monotonic Scheduling

! Principe et propriété! Assigner des priorités à des tâches périodiques en fonction de

paramètres temporels! Les tâches avec une période courte ont une priorité haute

! La priorité d’une tâche est inversement proportionnelle à sa période

! Optimal dans la classe des algorithmes à priorités fixes pour destâches indépendantes

! Remarques! Il est très difficile d’analyser toutes les relations possibles entre

les instants de déclenchement d’un ensemble de tâches

! L’objectif est d’identifier la combinaison « pire cas » des instantsde déclenchement pour un ensemble de tâches

! Le « pire cas » est celui où les tâches seraient toutesdéclenchées au même instant ⇒ temps de réponse le + grand

14/10/04 52

Exemple! Soit 2 tâches périodiques

! t1(r1, 1, 4, 4) et t2(0, 10, 14, 14)

! t1 a donc un priorité plus forte que t2: Prio(t1)>Prio(t2)

! L’exécution de t2 est retardée par les activations de t1! Le temps de réponse de t2 est une fonction de t1 (à savoir de r1)

! Chronogrammes! r1=4! TR(t2)=12 ≤ 14

! r1=2! TR(t2)=13 ≤ 14

! r1=0! TR(t2)=14 ≤ 14

t

t

t

t

tt

Page 27: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 53

Optimalité (1/4)! Démarche

! Instant critique: date d’arrivée des tâches simultanées

! Si un ordonnancement est faisable avec des priorités arbitraires,alors il l’est également avec le Rate Monotonic Scheduling.

! Idée de la démonstration (pour 2 tâches, généralisation à n tâches)

! Soit t1(r1, C1, D1, T1) et t2(r2, C2, D2, T2), avec T1 ≤T2 et (Di=Ti)

! Si les priorités ne sont pas assignées avec le RM,! alors prio(T2) ≥ prio(T1)! A T1 la tâche t1 doit être terminée ⇒ C1+ C2 ≤ T1 (1)

! Si les priorités sont assignées avec le RM! alors prio(T2) ≤ prio(T1)

! Soit , le nombre de périodes de t1 entièrement incluses

dans la période de t2

β =

T

T2

1

ConditionD’ordonnançabilité

14/10/04 54

Optimalité (2/4)! Cas n°1: C1 est suffisamment court pour que toutes les instances

de t1 se terminent complètement avant la fin de la période T2

! Donc : C1≤ T2 - β.T1 (2)

! et : C2 + ( β+1 ).C1 ≤ T2 (3)

! Cas n°2: C1 est suffisamment grand pour que la dernière instancede t1 ne se termine pas complètement

avant la fin le la période T2

! Donc : C1≥ T2 - β.T1 (4)

! et : β.C1 + C2 ≤ β.T1 (5)

t1t2

T2

t1t2

T2

ConditionD’ordonnançabilité

ConditionD’ordonnançabilité

T1

T1

Just in time!

Too late!

Page 28: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 55

Optimalité (3/4)! On démontre l’optimalité de RM si l’inégalité (1) implique

les inégalités (3) et (5)! (1)⇒ (3)

! C1+ C2 ≤ T1

! ⇒ β. (C1+ C2)≤ β. T1 (avec β≥1 puisque T2≥T1)

! ⇒ β. C1+ C2≤ β.(C1+ C2)≤ β. T1

! ⇒ β. C1+ C2 + C1 ≤ β.(C1+ C2) + C1 ≤ β. T1 + C1 (ajout de C1)

! ⇒ (β+1). C1+ C2 ≤ β. T1 + C1

! ⇒ (β+1). C1+ C2 ≤ β. T1 + C1 ≤ T2 (avec (2) C1≤ T2 - β.T1)

! ⇒ C2 + (β+1).C1 ≤ T2 (CQFD: (3))

! (1)⇒ (5)! C1+ C2 ≤ T1

! ⇒ β. (C1+ C2)≤ β. T1

! ⇒ β. C1+ C2≤ β.(C1+ C2)≤ β. T1

! ⇒ β. C1+ C2≤ β. T1 (CQFD: (5))

14/10/04 56

Optimalité (4/4)! Résumé

! Pour un ensemble de 2 tâches t1 et t2 avec des échéances relativeségales à la période ( Di = Ti )

! Si un ordonnancement est faisable pour une assignation arbitrairede priorités, alors il l’est avec le Rate Monotonic Scheduling

! Généralisation! Démonstration pour n tâches

! Références! Liu C. et Layland J.W., Scheduling algorithms for multiprogramming in

hard real-time environment, Journal of the ACM,20(1), pp. 46-61.1973.

! Buzzato C.G., Hard Real-Time Computing Systems, PredictableScheduling, Algorithms and Applications,Kluwer Academics, 1997.

Page 29: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 57

Condition d’ordonnançabilité

! Remarques! Pour des ensembles de tâches générées de façon aléatoire, le

taux d’utilisation converge vers 88%

! A cause de l’assignation de priorités basée sur la période,l’algorithme convient pour des tâches dont Di=Ti

! Si ce n’est pas le cas, (Di < Ti), un autre algorithme a été défini,Inverse Deadline Algorithm:

! La priorité est assignée en fonction de l ’échéance Di

! La condition suffisante d’ordonnançablité est:

C

Tn

i

ii

nn

=∑ ≤ −

1

1

2 1( )

C

Dn

i

ii

nn

=∑ ≤ −

1

1

2 1( )

14/10/04 58

Problématique de l’évaluationdes WCET

! Déterminer les Ci (WCET: Worst Case Execution Time)

! Analyse de flot de contrôles (du logiciel: tâches, noyau,…)

! Analyse de bas niveau (matériel, processeur, pipeline, caches...)

! Le problème! Calculer la borne sup du temps d’exécution d’une portion de

code (temps par le processeur ≠ temps de réponse)

! Tâches simples! Entrées disponibles au lancement

! Pas de blocage (synchronisation, E/S, par exemple)

! Variations dépendantes! Des entrées

! De l’état de la tâche

! Du matériel utilisé

Page 30: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 59

Problématique de l’évaluationdes WCET

! Analyse! Durée des actions

! Chemins d’exécutions

! Architectures simples! Durée des actions=cte

! Bornes des boucles

! Chemin le plus long

! Architectures complexes! Durées variables / contexte

! Boucles ouvertes

! Synchronisation, E/S

! Fonctions noyau! Explicites

! Implicites

! Pipelines, caches, etc.

t1

t2

t3 t4

t5 t6

t7

t8

t9

Action: durée des instructions

Chemin

14/10/04 60

Du concept à la pratique! De nombreux « noyaux temps-réel »

! Plusieurs noyaux TR bâtis sur ces concepts existent

! Utilisés dans des applications industrielles, y compris critiques

! Le noyau temps-réel fourni la « mécanique » ! Pour construire un système ou une application temps-réel

! Il faut donc! Choisir les bonnes fonctionnalités, les bonnes API (standards)

! Choisir les bonnes caractéristiques (taille, performance, QoS)

! Les difficultés sont dans le processus dedéveloppement

! WCET (tâches, noyau)⇒ langages, complexité, structures, HW, etc.

! Analyse d’ordonnancement ⇒ ensemble, modèle de tâche(indépendance, partage, distribution), modèle de calcul (périodique,ou a-périodique,…), etc.

Page 31: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 61

Tâches critiques et partage deressources

14/10/04 62

Evaluation du temps de réponse

Page 32: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 63

Phénomène d’inversion de priorité

14/10/04 64

Problèmes d’interblocages

Page 33: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 65

Protocole d’héritage de priorité

14/10/04 66

Protocole à priorité plafond

Page 34: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 67

Exemples

14/10/04 68

Exemples: Chorus v.s. Mach! Concepts communs

! acteurs / tâches + threads

! messages non typés et ports

! VM / serveur de pages

! Concepts similaires

! Nommage global / local

! Protection programmable (capacités Chorus) / r,w (Mach)

! Notion de groupe! de port (Chorus) ou d’ensemble de ports,

! de site (Mach)

! Notion d’acteur superviseur (Chorus)

! Sous-systèmes similaires

! Unix/Chorus

! OSX/Mach

Page 35: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 69

API Chorus

• Actors

• Threads

• Messages, ports, groups

• Global naming

• VM management

• Protection (capabilities)

• User , supervisor mode

Actor: create, delete...

Thread : create, delete, suspend, activate, priority

Port : create, delete, attach, detach, migrate,..

Group : create, include, delete

IPC : RPC, send, recv, reply, broadcast

Semaphore : mutex (init, get,release), P,V

Identifier : UI_create, UI_delete

Regions : allocate, free, init, map, lock,...(segments)

Hdl / IT : connect, disconnect, activate, mask

...and a few others

14/10/04 70

ActeurUnité de structuration des applications

CTX

CTX

CTX

System défaut

exception

ports attachéssuperviseur

Espace d’adressage Threads courants Ports

Page 36: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 71

Thread (activité)Flot séquentiel de contrôle

Environnement d'exécution

= Acteur / Tâche

Exécution concurrente

Contexte d'exécution

Parallélisme /multi-processeur

unités de scheduling

priorités(statiques

ou dynamiques)

pré-emptiontempspartagé

Communications inter-activités parmessage ou mémoire partagée

mécanismes desynchronisation

(µ-noyau)

14/10/04 72

Messages / Ports / Groupesunité de communication / file de messages

Désignation Attaché à un seul acteur

Migration

Reconfiguration dynamique

Identifieur local Global UI

Appartenance à un groupe

Communication mode

Datagrammesasynchrones

RPC

optimisationlocale

Page 37: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 73

Identifieurs

LocalUnique Ids

Identification

Localisation parle micronoyau et

quelques serveurssystème

Protection

Le champ "capability"peut être modifié et

utilisé par un serveur

Protection statiquemicronoyau

(r,w, send, recv)

! Messages identifiés par l’UI de l’acteur et l’UI du port d’émission! Objets identifiés: acteurs, ports, segments

UI capability

! Network Managers: OSI, UDP-TCP/IP,etc.

14/10/04 74

Identification et localisation

! Caractéristiques

! Indépendants de la localisation

! Générés par le noyau

! Utilisés pour référencer toutobjet global (acteurs et ports,etc.)

! Noms transmis sans contrôlenoyau d’un objet à un autre

! Ils sont globaux, donc peuventmigrer (reconfiguration)

! Capacité

! Nom global : UI + Key

! Key : champ protection

! Service de localisation

! localisation d’objets distants

! cache des UIs connus

! Principe

! chercher UI dans le cache

! send (site, message)

! si succès alors OK

! si échec alors

! diffuser recherche UI

! réception réponse diffusée

! mise à jour cache (UI, site)

! send (site, message)

Page 38: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 75

Types d’acteurs! Acteurs utilisateurs

! application

! espace d’adressage protégé

! Acteurs systèmes

! services généraux

! acteurs de confiance

! Acteurs superviseurs

! exécution privilégiée

! espace d’adressage commun

! espace noyau

! Handlers d’IT, trap, exceptionsnoyau

14/10/04 76

Invocations

! Asynchrone : ipcSend, ipcReceive

! Synchrone (RPC): ipcCall, ipcReceive, ipcReply

ipcSend

ipcReceivep1 p2

ipcCall

ipcReceivep1 p2

ipcReply

Page 39: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 77

Groupes

p1 p2

p3

p4

site 1

site 3

site 2

14/10/04 78

Invocations de groupe

! Groupe : ensemble dynamique de ports

! grpPortAllocate, grpPortInsert, grpPortRemove

! notion de groupe statique (boot) et dynamique

! Modes d’adressage

! mode diffusion: diffusion sur tous les membres du groupeaccessibles (non garantie de réception ni d’ordre)

! mode fonctionnel: transmission du message à un membre dugroupe parmi N

! exemple: pool de serveurs d’impression banalisés

! mode associatif : transmission à un membre du groupe qui setrouve sur un site déterminé

! exemple: serveur impression mais sur un site particulier

Page 40: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 79

Exemple de configuration (1)

p1p2

p3

Site 1

Site 2

14/10/04 80

Exemple de configuration (2)

p1p2

p3

Site 2

Site 1

Site 3

Page 41: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 81

Exemple de migration

p1p2

p2

Site 2

Site 1

Site 3

CRASHACTEUR

checkpointing

14/10/04 82

Exemple : Primary-Backup

Site 2

Site 3

p2 = porte de serviceT = thread de serviceS = thread de checkpointingR = thread de reconfiguration

ipcReceivep2

SaveStateipcReply

requête

reponse

T S

R

T

state

detection

p2

Page 42: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 83

Fonctionnement! SaveState

! sauvegarde de tout ou partie des données locales de l’acteur

! ipcCall (porte “checkpoint”, message “checkpoint”)

! Thread S

! enregistrement de l’état interne de l’acteur

! ipcReply (OK)

! Thread R

! activé sur signal (message) “crash primaire”

! restauration de la porte de service

! reprise des traitements (protocole de bout-en-bout C-S)

14/10/04 84

Gestion mémoire! Mémoire virtuelle

! espace global d’adressage

! éléments de base

! segment : unitéd’adressage en mémoiresecondaire

! région : unité destructuration de l’espaced’adressage d’un acteur

! unité de gestion mémoire :table des registres derégions pour un acteur

code

data

fichier

segment

région

Page 43: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 85

Gestion mémoire! Régions

! plusieurs régions pour définirl’espace d’adressage d’unacteur

! une région correspond à unepartie d’un segment dansl’espace d’adressage

! partage de mémoire enassociant plusieurs régions(de plusieurs acteurs) à unmême segment (tout oupartie)

exemple: partage de code

! Segment

! désigné par une capacité etdonc indépendant de lalocalisation

! utilisé pour implémenter lesfichiers-mémoire et leswapping

! géré par des serveursspécifiques appelés mappers

! représentation et gestion de laprotection ou de la cohérence(partage) par les mappers

! gestion de caches

14/10/04 86

Gestion d’acteurs! Acteurs au boot

! chargés par le noyau au boot

! archive de boot = noyau + acteurs

! fichier de boot créé à la génération

! fichiers binaires du noyau

! fichiers binaires des acteurs

! Chargement et manipulation dynamique

! actorCreate, actorDelete, actorExcept, actorPi

! actorPriority, actorSelf, actorStart, actorStop

Page 44: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 87

Interface noyau: acteurs! actorCreate

! création d’acteur(U,S,Sup)-> cap

! actorDelete! destruction d’un acteur (cap)

! actorExcept! définition port exception

! actorPi! définiton de la protection

! actorPriority! définition de la priorité

! actorSelf! renvoi de la capacité de l’acteur

! ActorStop! arrêt de l’acteur (thread courant)

! actorStart! reprise de l’acteur (thread courant)

14/10/04 88

Gestion des threads

! Politique d’ordonnancement de base

! “priority-based preemptive scheduling”

! 256 niveaux de priorité

! pour chaque niveau le noyau maintient une liste des threads“ready-to-run”

! le thread actif est toujours celui “ready-to-run” de plus forte priorité

! préemption même quand le thread exécute du code noyau horsdes sections critiques

! Classes d’ordonnancement

! priorités <128 (pré-emptive) priorités >=128 (Time slicing)

! WCET (Worst Case execution Time) and “deadlines”

Page 45: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 89

Interface noyau : threads! threadAbort

! arrêt (exit) d’un thread

! threadCreate! création d’un thread

! threadDelete! destruction d’un thread

! threadDelay! temporisation de l’exécution

! threadSuspend! mise en attente infinie

! threadResume! réveil d’un thread en attente

! threadSelf! renvoi de l’identificateur threadli

! ThreadTimes! temps d’exécution d’un thread

Et quelques autres!

14/10/04 90

Synchonisation! semInit

! initialisation d’un sémaphore à une valeur

! semP

! prise d’un sémaphore (bloquant)

! semV

! relâchement d’un sémaphore

! mutexInit

! initialisation d’un sémaphore d’exclusion mutuelle (v = 1)

! mutexGet

! prise d’un mutex (bloquant)

! mutexRel

! relâchement d’un mutex

! mutexTry

! prise d’un mutex (non bloquant)

Page 46: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 91

Exceptions! Erreurs (div 0, bus, etc.)

! Stratégies

! défaut: abort du thread courant

! handler: exécution d’un handler défini par un sous-système

! ipc_mode: le thread effectue un RPC sur le port d’exception

! Handler d’exception

! un défini par l’acteur

! attachement dynamique

! fourni par un acteur superviseur

! appels :

! svExcHandler (actor, handler)

! actorExcept (actor, threadli)

• sauvegarde du contexte• accès au contexte

14/10/04 92

Interruptions

! Traitement d’IT, temporisations, masquage

! Handlers fournis par des acteurs superviseurs

! Connexion-Déconnexion dynamique

! svItConnect (intNb, handler, priorité)

! cvItDisconnect (intNB, handler, priorité)

! Sauvegarde du contexte du thread courant

! Exécuté dans la pile d’interruption (mode superviseur)

! Time-out :

! svTimeOut (handler, param, delay)

! svUnTimeOut

! Masquage :

! spin lock svMaskedLockGet, svMaskedLockRel

! scheduling locking svLock, svUnLock

Page 47: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 93

Gestion de fichiers

S1 S2 S3

! Notion de “file manager réparti”

! Notion de porte symbolique (mount NFS)

! Gestion de fichiers type Unix

14/10/04 94

Chorus et MachUNIX

Abstractions de base

MACH • protection type UNIX figée

• identificateurs locaux

• intègre les drivers

DISTRIBUTION hors µ-noyau!

DISTRIBUTION

Abstractions de base

CHORUS

MiX

UNIX modulaire réparti

Page 48: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 95

Notion de micro-noyau ouvert

openmicrokernel

processorPortability

Scalability

API layer

Multiple Personalities UNIXCORBART-POSIXRTOS / legacy

Distribution transparente

Portable phones Switching systems

real-timeembeddedsystems

! "Componentized", incrémental, noyau de système temps-réel

14/10/04 96

Composants du noyau

communications Time Utilities MemoryManagement

Restart

SchedulersInterrupts Invocations

Synchronisation

micro-core executive Core executive

Page 49: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 97

! Microcore executive

! de l’ordre du 8 K

! un seul acteur multithread

! threads application

! scheduler thread

! interruption

! traps

! exceptions

! exemple: téléphonesportables

! Core executive

! de l’ordre du 100 K

! support application

! acteurs applications

! acteurs systèmes

! acteurs superviseurs

! notion de sous-système

! différents espacesd’adressage

! gestion dynamique de lamémoire

! exemple: PBX

Du µcore au core executive

14/10/04 98

Composants de base

• Schedulers- préemptif à prioritéFIFO (*)- a quantum fixe et priorité- Unix Time-Sharing and Temps-Réel- politique d’ordonnancement utilisateur

• Memory management- mémoire physique plate- espaces d’adressage protégés multiples- partage de région entre espaces

d’adressage

• Communication- IPC local (async., RPC)- IPC réparti (localisation transparente)

• Synchonisation- sémaphores- mutexes, RT mutexes- événements

• Time- timers- time of the day- utilitaires

• Interrupts- interruptions génériques- gestion d’interruptions

définie par l’utilisateur

Page 50: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 99

Exemple: Chorus ClassiX

Chorus microkernel

Chorus/Posixservices

Actors/processes

ChorusClassixTools

HOST

• UNIX workstation• Cross development tools• X interface• File system

TARGET

14/10/04 100

Exemples de produitsChorus micro Chorus Classix Chorus Fusion (SCO Unix)

10k-100k 100K-1M ! 10Mb

• micro RT Posix• COOL-ORB• Promability• Host-Target dvlp:

UNIX, Windows

• micro RT Posix• COOL-ORB• File system support• Host-Target dvlp:

UNIX, Windows• Hot restart• Streams

68000, 68010, 68030,68040, 68060x86, PentiumPower PC (601,603,604)ARM, i960

68030, 68040x86, PentiumPower PC (603,604)SPARC (µ, let,IIe)ARM, MIPS R4400

• UNIX

x86, Pentium

Page 51: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 101

Applications industrielles

Exemples

14/10/04 102

Domaines d’application

Telecoms AlcatelPhilips, Matra Com, NORTEL, SCO Telecoms...

Embedded systems Alcatel Austria, Fuji Electric, Dassault,ASTRIUM ...

Others JVC ... buy a "Karaoke-on-Demand" set

you have a µ-Kernel inside!!!

SupercomputingCray Research,

MultiprocessingETRI,Systran,

General-purposeFault tolerant systems

Stratus,Tandem

Page 52: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 103

ELEKTRA - An Electronic Interlocking and Railway

Operations Management System

Objectif ➟ Fiabilité et disponibilité(défaillance critique pour de petits systèmes de 10-9/h— CENELEC)

Architecture ➟ Double canal basé sur des spécifications diversifiées (functional, safety-bag)

Les action sont effectuées sur l’environnement physique si les deux canaux sont d’accord

Chaque canal est tripliqué au niveau matériel

Canal fonctionnel ➟ effectue les fonctions de contrôle de l’aiguillage

Canal safety-bag ➟ contrôle des situations (règles) de sécurité

14/10/04 104

Architecture du système

MMI

ILP SBP

• • • • • •

Railway periphery

PC

operatorsubsystem

managementsubsystem

peripheralcontrollersubsystem

MMI: Man-Machine Interface SBP: Safety-Bag ProcessorILP : InterLocking Processor PC: Peripheral Controller

Page 53: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 105

Concepts et Spécifications...

• Prouver qu’un système est sans faute de conception vis-à-vis dela sécurité est extraordinairement difficile pour un système complexe

! conception telle que l'occurrence de faute de conceptionn'entraîne pas le système dans un état de défaillancecritique (donc pas de preuve!)

• Concepts de tolérance aux fautes- diversité de la spécification des canaux- utilisation diversifiée du hard et du soft OS- mécanismes de contrôle intégrés- détection d’erreur et compensation: vote bit-à-bit

• Autres aspects- Utilisation d’un langage temps-réel fortement typé: CHILL- Ré-utilisation totale de logiciels de contrôle propriétaires

14/10/04 106

Nouvelle plate-forme

POSIX personality

runtime server

Databaseserver

Chorus microkernel

HW

processesfiles

shell

libs onlineselfchecksdevices

CAR personality

CHILLapplication

CHILLapplication

POSIXapplication

standard CHILLinterface

POSIX interface

Chorus interface

HW interface

Page 54: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 107

Expérience actuelle...• Configuration système à deux canaux en service depuis 1989

• Pas de problème de sécurité• quelques problème de configuration et de synchronisation

• (réplication active faiblement couplée)

• Aujourd’hui:• - plus de 20 systèmes ELEKTRA en opération depuis Sept. 95 avec:

✂! Chorus / Intel 486✂! POSIX layer✂! CHILL API server personality (CAR)

• - portage de 100% des applications CHILL propriétaires

• Gare de Salzburg “contrôle d’aiguillage électronique”• - basé sur des 486• - a passé la phase d’autorisation• - succès en opération régulière depuis le 21 Mai 96• - 4000 positionnements d’aiguillage par jour

14/10/04 108

Conclusion

Page 55: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 109

Conclusion! Un micronoyau temps-réel

! Concepts et mécanismes de base pour les systèmes (opératoires) etrépartis industriels

! Le développement temps -réel ➟ caractéristiques des tâches, taux, perf,WCET, scheduling analysis, etc

! L’utilisation de COTS y compris pour le logiciel de base est de plus en plusenvisagée, même pour des systèmes critiques

! Contrôle ferroviaire, contrôle-commande,

! Aéronautique, spatial, automobile

! Le processus de développement est le « point dur »! Analyse des WCET, architecture logicielle et matérielle

! Définition des tâches et analyse d’ordonnancement

! Qualité de services et systèmes temps-réel « robustes »! Des mécanismes de tolérance aux fautes peuvent être bâtis avec ces

concepts,

! La validation des COTS reste un problème ouvert... mais leur utilisationgrandissante renforce la confiance et permet la réduction des coûts.

14/10/04 110

Annexe 1

Plate-forme UNIX à base de µnoyau

Page 56: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 111

OS standard vs OS à µnoyau TR

API

core executive

processmgt.

VM mgt.

Hdls / IT

File system

Drivers

Sockets

IPC Sys-V

Protocols

deamons

Application

microkernel

SGFdrv.

Procnet.sock.

UNIX API

subsystem

microkernel API

othersub-

system

cache

14/10/04 112

Unix réparti

FSProcProc

Drv.Drv.

ProcSocket

Drv.

microkernel microkernel microkernel

UNIX API UNIX API UNIX API

Page 57: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 113

Annexe 2

Exemple de programme sur µnoyau

14/10/04 114

Exemple : émission/* send0.c * * Envoi d'un message avec utilisation d'un groupe de portes en * choisissant le mode de transmission. Le récepteur est receive0. * * USAGE : send0 [mode ipcSend] * avec mode = BROAD ou FUNC ou FUNCU <site> * et site = numéro de site Chorus sous forme entière * * Par défaut send0 utilise le mode BROAD. */

#include <chorus.h>#include "tests.h"

#define USAGE "Usage: send0 [BROAD|FUNC|FUNCU site]\n"#define STAMP 1965#define MSG_MAX_SIZE 30#define MESSAGE "bonjour"

char buffer[MSG_MAX_SIZE];

Page 58: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 115

/* preparation du message */ strcpy(buffer,MESSAGE); msgDesc.bodyAddr = (VmAddr)buffer; msgDesc.bodySize = MSG_MAX_SIZE;

/* destinataire */ IpcDest.target = GroupCap.ui; if (argc==1) result = u_ipcTarget(&IpcDest.target,K_BROADMODE); else if (strcmp(argv[1],"BROAD")==0) result = u_ipcTarget(&IpcDest.target,K_BROADMODE); else if (strcmp(argv[1],"FUNC") == 0) result = u_ipcTarget(&IpcDest.target,K_FUNCMODE); else if (strcmp(argv[1],"FUNCU") == 0) { result = u_ipcTarget(&IpcDest.target,K_FUNCUMODE); sscanf(argv[2],"%u",&site); u_uiSite(&SiteUi,site); IpcDest.coTarget = SiteUi; } else { printf(USAGE); exit(1); } tst_retour("u_ipcTarget",result); tst_affdest(&IpcDest);

/* envoi du message */ for(;;) { if ((result = u_ipcSend(&msgDesc, SendPortLi, &IpcDest) ) != 0) tst_retour("Probleme u_ipcSend",result); else printf ("Message envoye : %s\n",buffer); sleep(10); } }

main(argc, argv)char *argv[];int argc;{

KnMsgDesc msgDesc; int SendPortLi; KnUniqueId SendPortUi; KnCap GroupCap; int result; KnIpcDest IpcDest; KnUniqueId SiteUi; unsigned long site;

/* verification des arguments */

if ( (argc==2 && strcmp(argv[1],"FUNCU")==0) || (argc==3 && strcmp(argv[1],"FUNCU")!=0) || (argc>3) ) { printf(USAGE); exit(1); }/* creation port emetteur */

SendPortLi = u_portCreate(&SendPortUi); tst_retour("u_portCreate",SendPortLi);

/* creation du groupe de ports emetteur/recepteur */

result = u_grpAllocate(K_STATUSER,&GroupCap,STAMP); tst_retour("u_grpAllocate",result);

/* insertion du port emetteur dans le groupe */

result = u_grpPortInsert(&GroupCap,&SendPortUi); tst_retour("u_grpPortInsert",result);

14/10/04 116

Exemple : réception

/* receive0.c * * Réception d'un message avec utilisation d'un groupe de portes. * L'émetteur est send0. */

#include <chorus.h>#include "tests.h"

#define SERVERSTAMP 1965#define MSG_MAX_SIZE 30#define MESSAGE "bonjour"

char buffer[MSG_MAX_SIZE];

Page 59: Technologie des micronoyaux et des noyaux temps …homepages.laas.fr/fabre/ENSEIGNEMENT/RTK/Cours-RTK.pdf14/10/04 5 Noyaux Temps-Réel pour Systèmes embarqués Production et transport

14/10/04 117

main(){

KnMsgDesc msgDesc; int RecPortLi; KnUniqueId RecPortUi; KnCap GroupCap,MyCap; int result;

/* creation port recepteur */

RecPortLi = u_portCreate(&RecPortUi); tst_retour("u_portCreate",RecPortLi); /* creation du groupe de ports emetteur/recepteur */

result = u_grpAllocate(K_STATUSER,&GroupCap,SERVERSTAMP); tst_retour("u_grpAllocate",result); /* insertion du port recepteur dans le groupe */

result = u_grpPortInsert(&GroupCap,&RecPortUi); tst_retour("u_grpPortInsert",result);

/* preparation du message */

msgDesc.bodySize = MSG_MAX_SIZE; msgDesc.bodyAddr = (VmAddr)buffer; msgDesc.annexAddr = NULL;

/* reception bloquante des messages */

for(;;) { result = u_ipcReceive(&msgDesc,&RecPortLi,-1); if (result<0) tst_retour("u_ipcReceive",result); else printf("\tMessage recu : %s\n",msgDesc.bodyAddr); } }

14/10/04 118

The End

« Quand on voit ce qu’on voit, que l’on entend ce qu’on entend et que l’on sait ceque qu’on sait, on a raison de penser ce qu’on pense! »

Pierre Dac