Garantir la qualité de service temps réel selon l'approche (m,k)-firm, Guarantee Real-Time Quality of Service according to (m,k)-firm approach

Jian Li

Description

Sous la direction de Ye-Qiong Song, Nicolas Navet
Thèse soutenue le 14 février 2007: INPL
Cette thèse se focalise sur le développement des algorithmes d’ordonnancement sous contrainte (m, k)-firm, ainsi que leurs applications pour la gestion de la qualité de service (QdS) dans les réseaux et systèmes temps réel distribués. L’objectif recherché est la garantie déterministe de la QdS tout en maintenant un fort taux d’utilisation des ressources. Les contributions sont (1) l’établissement d’une condition suffisante d’ordonnançabilité d'un ensemble de tâches sous l’algorithme « distance based priority »; (2) la définition de R-(m, k)-firm, un nouveau modèle qui relâche la contrainte (m, k)-firm et qui permet de modéliser de façon plus juste des exigences du temps réel souple; (3) le développement d’un algorithme efficace de dimensionnement de ressources sous contrainte (m, k)-firm relâchée; (4) la proposition de « Double Leaks Bucket » pour la gestion active de files d'attente permettant de maintenir une QdS en cas de surcharge des réseaux
-Ordonnancement temps réel
-(mk)-firm
-Gestion active file d'attente
-Qualité de service
This work focuses on the scheduling algorithms under (m,k)-firm constraint, as well as the applications for QoS (quality of service) management in the networks and distributed real-time system. The research aim is to achieve the deterministic guarantee of QoS with high resource utilization. The contributions in this thesis include (1) proposing a sufficient condition for determining the schedulability of a real-time task set under Distance Base Priority scheduling algorithm; (2) defining a novel real-time constraint which relaxes the (m,k)-firm constraint and provides a more suitable modelling of soft real-time; (3) developing an effective resource provisioning algorithm under this relaxed (m,k)-firm constraint; (4) proposing an active queue management mechanism, called Double Leaks Bucket, which can guarantee the QoS with dynamic dropping of the packets during the networks overload period
-Real time scheduling
-(mk)-firm
-Queue management
-Quality of service
Source: http://www.theses.fr/2007INPL012N/document

Sujets

• Qualité de service

Informations

• Publié par: Thesee
• Nombre de lectures: 37
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

AVERTISSEMENT



Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.

Contact SCD INPL : [e-mail]




LIENS




Code de la propriété intellectuelle. Articles L 122.4
Code de la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
Institut National Polytechnique de Lorraine
Département de la formation doctorale en Informatique Ecole doctorale IAE+M


Garantir la qualité de service
temps réel selon l’approche
(m,k)-firm


THESE

Présentée et soutenue publiquement le 14 Février
2007 Pour l’obtention du

Doctorat de l’Institut National Polytechnique de Lorraine
(Spécialité Informatique)
Par

LI Jian

Composition du Jury

Président JeanYvesMarion,Prof.àLORIAINPL

Rapporteurs PascaleMinet,ChargéderechercheàINRIARocquencourt
PascalLorenz,Prof.àl’UniversitédeHauteAlsace

Examinateurs PascalRichard,MaîtredeconférenceàLISI/ENSMA
ManLin,AssociateProf.àSt.FrancisXavierUniversity,Canada
FrançoiseSimonotLion,Prof.àLORIAINPL

Directeur de thèse YeQiongSong,Prof.àLORIAINPL
Codirecteur de thèseNicolasNavet,ChargéderechercheàINRIALorraine

LaboratoireLorraindeRechercheenInformatiqueetsesApplicationsUMR7503


Introduction générale

Aujourd’hui, la technologie temps réel est omniprésente, et de plus en plus
d’infrastructuresdépendentd’elle.Lesdomainesdesapplicationstypiquesducalcul
tempsréeletdelacommunicationtempsréelincluentlecontrôledesprocédésindus
triels, la fabrication, l'avionique, la commande de trafic aérien, les multimédia, les
télécommunications(l'autoroutedel'information),latélémédicineetlesoinintensif
surveillé,ladéfense,etc.
Danslessystèmesdecontrôletempsréel,lestâchessonthabituellementpé
riodiques et ils ont des contraintes de l’échéance, avant lesquelles chaque instance
d'unetâchedevraitaccomplirsoncalcul.Danslescasdéfavorablesoùilyalescom
posantsenpannes,lestechniquesd’unereconfigurations’appliquepourrestaurerdes
échecsdeprocesseur;quiassignenttouteslestâchesauxprocesseursenétat.Cette
reconfigurationpeutconduireàlasurchargedeprocesseuràpointqu'iln'estpluspos
sibledesatisfairetoutesleséchéancesdestâches.D'ailleurs,bienquelabandepas
santedesréseauxd’aujourd’huisoitrelativementabondante,l'apparitiondesnouvel
lesapplicationsdel'Internet,tellesquelatransmissionaudio/vidéomultimédia,mè
nentaumêmeproblèmedesressourceslimitéesqu'avant.
Généralementlessystèmesfonctionnentpendantdelonguespériodesdansdes
environnements non déterministes assujettis à des fautes, tant que possible, ils de
vraientpouvoirtolérerlesfautesetcontinuerdefonctionnercorrectement.Ladégra
dationcontrôlée(gracefuldegradation)estunemanièredefournirunniveauréduitde
serviceplutôtqued'échouercomplètementencasdesurchargedesystèmeouencas
defautesinattendues.Parexemple,lesfluxmultimédiasonthabituellementlestaux
detransmissionvariablesetpeuventtolérerdeséchéancesratéesoudespaquetsper
dusàconditionqu’ilssoientespacéscorrectementdansletemps,cefaitestdûàla
redondance dans le code et la tolérance de perception humane. Jusqu'à maintenant,
commentmesurerexactementleQoSrésultantedesapplicationsmultimédiaresteen
coreunequestionouverte.
Ilexistededifférentescontraintestempsréelselonlesapplicationsetsurtout
en termes de leur niveau de tolérance aux fautes temporelles. Formellement, la
contraintetempsréelpeutêtreclassifiéedansletempsréeldur(hardrealtimeHRT),
letempsréelsouple(softrealtimeSRT),etletempsréelfirm(firmrealtime).Un
système temps réel dur exige de servir toutes les instances avant leurs échéances.
Cette condition rigoureuse, d'une part, n'est pas nécessaire pour tous les systèmes
puisqu’uncertainnombred’échéancesratéesesttolérablepourcertainesapplications.
D'unautrepart,l'occurrencedesfautes(parexemplel’échéanceratée,paquetsperdus,
etc.) ne peut pas toujours être évitée pour les systèmes temps réel adaptatifs parce
que,essentiellement,lessystèmesetsesenvironnementsnesontpasentièrementpré
visiblesàl'avance.
Parcontre,lessystèmessouscontrairestempsréelsouple(softrealtimeSRT)
peutaccepteruncertainnombred’échéancesratéesdetempsentemps,quiaumieux
estexprimépardesgarantiesprobabilistesoudestatistiques.Cependant,ladégrada
tion contrôlée exige non seulement la fiabilité mais également la disponibilité. Par
exemple,beaucoupdefautesquiseproduisentdansunintervallecourtpeuventmener
àunedégradationstatistiquementacceptablepourquelquesapplications,néanmoins
ladensitédesfautespeutêtrenuisiblepourquelquesautresapplications.
Parconséquent,lacontraintetempsréelfirm(firmrealtime:FRT)[Ramana
than95]s’avèreintéressantepouréviterlecasoùil yaun grandnombredefautes
consécutives dans un intervalle court. En particulier, la contrainte «(m, k)firm»
exigequ'aumoinsminstancesdevraientêtrefinisavantleurséchéancesparmin'im
portequelkinstancesconsécutives.
Étroitementliéeauxcontraintestempsréelfirmest«weaklyhardrealtime»
(WHRT)quimetdesrestrictionssurlenombred’échéancesquipeuventêtreratées
(ou doivent être rencontrées) dans un certain nombre d’échéances consécutives. Et
quelquepart,letempsréel«(m,k)firm»aétésuggérépourêtreunesousclassede
2WHRT[Bernat01].Bienqu'ilstouslesdeuxcontraindrentdeséchéancesratéesàune
limite précise, une différence inhérente existe entre les deux types de contraintes
tempsréel.Enfait,leFRTsupposequ'ilestinutiled’exécuterl'instancesiellenepeut
pasêtreentièrementfinieavantsonéchéance.Tandisque,sousWHRT,uneinstance
est encore exécutée quand elle excède son échéance et peut causer la suspension
d’ellemême. De notre point de vue, WHRT est une sousclasse de SRT. Récipro
quement,FRTpeutêtreconsidérécommeunordonnancementactifauxfautespourle
system,quijettel’instancequandellen'estpaspossibledefiniravantsonéchéance.
Ce rejet actif peut réduire la quantité de travail à l'avenir pour le processus
d’ordonnancement, et le facilite, en comparaison de WHRT, pour ordonnancer les
instancessuivantes.Enoutre,FRTpeutéviterlapertedesressourcesparl’exécution
inutiledesinstancesquinesatisfontpasleurscontraintes.
Lebutdessystèmestempsréeladaptatifsestdefournirdesgarantiesdeper
formances acceptables a priori au niveau de système et de fournir la dégradation
contrôlée en présence des fautes. Ceci exige un certain genre de détermi
nisme/prévisibilité,quiimpliqueque,ayantprétentionsdelaquantitédetravailetcer
tainestolérancesauxfautes,ondoitpourvoirdimensionnerlesressourcesexigéesau
momentdelaconception.
Denotrepointdevue,lacontrainte(m,k)firmfournituncadreconvenableet
puissant pour indiquer le niveau de la tolérance aux fautes. Nous choisissons de
concentrercettethèsesurl'utilisationdelacontraintes(m,k)firmdanslessystèmes
tempsréeladaptatifs.Ledéfidelarechercheestdedévelopperlestechniqueseffica
cesde gestionderessources enutilisantla contrainte(m, k)firm etd'évaluerleurs
exécutionsdanslecontextedelatransmissiontempsréeladaptativedesystèmesde
contrôlecommande et de multimédia. Traditionnellement, la garantie de la QoS
(QualityofService)tempsréelestréaliséeenréservantàl'avancelesressourcesselon
lepirescas,appelélesurapprovisionnement,etilinduituntauxd’utilisationdesres
sourcesbasse.Évidemment,sifaisable,ilvautmieuxderéserverlaressourceselonle
tauxmoyendelacharge,etdejeterquelquesdemandesencasdesurcharges.Cefait
estplusefficaceàl’utilisationderessourceplutôtquederéserverbeaucoupplusde
ressourcesengarantissanttouteslesdemandesdanslepirecas.Autrementditque,le
3problèmeprincip