//img.uscri.be/pth/cce2fcf279bfa288063bc3f39b2e5ce5dd9deaae
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

De
213 pages
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
Voir plus Voir moins


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 : scdinpl@inpl-nancy.fr




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èmeprincipalestcommentdéterminerlaressourceminimalerequisepourlaga
rantie déterministe sous la contrainte (m, k)firm, ou comment servir au plus
d’applicationstempsréelaveclacapacitéderessourcedisponible.
Cebutde recherchese concentresurlaconceptiondesréseauxdenouvelle
génération(nextgenerationnetwork:NGN),enparticulier,ressourceetfonctionde
control d'admission («resource and adimission control functions» RACF) qui per
mettrontauxopérateursdegarantirlaqualitédeboutenboutpourdesservicesmul
timédia,telsqueVoIPetIPTV,etc.Notrerecherchepeutfourniràunopérateurla
capacitédedéfinirdesrèglespourlestypesdecommunicationspécifiques,afind'al
loueraumieuxdesressourcesderéseau.
Intuitivement, la ressource requise par un ensemble de tâches selon la
contrainte(m,k)firmdevraientêtremoinsquecellesansdégradation(HRT).Sila
contrainte(m, k)firmn’économisepaslaressourceparrapportàHRT, elleperdra
sesmotivationsetintérêtsoriginaux.Parconséquent,laressourcerequiseconstitueen
lecritèreetlamesurelesplusimportantsdel'efficacitéd’ordonnancement.
Danslapremièrepartiedecettethèse,nousintroduisonsl’étatdel’artconcer
nantalgorithmesd’ordonnancementssouscontrainte(m,k)firm(modèlefixeetmo
dèle dynamique) ainsi qu’une autre contrainte similaire, appelé DWCS (Dynamic
window constraint scheduling). Nous analysons et comparons alors les approches
d’ordonnancement et rappelons les conditions pour déterminer l’ordonnançabilité
d’unensembledetâches.Ensuite,nousprésentonslestroiscontributionsprincipales
decettethèse.
Lapremièrecontributionestuneconditionsuffisanted’ordonnançabilitépour
l’algorithmeclassiqueNPDBPEDF «Nonpreemptive–Distancebasedpriority–
earlieastdeadlinefirst[Hamanathan99]».Cetravailestimportantpuisqu'iln'yavait
aucuneconditionsuffisanted'approvisionnementavantpourl'algorithmedynamique
d’ordonnancementsouslacontraint(m,k)firm.
Ladeuxièmecontributionestunenovellecontraintetempsréelquimèneàune
meilleure utilisation de ressource que (m, k)firm. Pour cela nous présentons cette
contributionselonlesétapessuivantes:
4• D'abord, selon les littératures existantes [George02] [Mok01]
[Quan00] [Jeffay91], nous expliquons les raisons théoriques de
l’utilisation basse de ressources dans l'analyse d’ordonnançabilité du
pirecas[LiDEA03][LiETFA06].
• Deuxièmement, nous donnons les orientations de recherche visant à
augmentant le taux d'utilisation de ressources. En fait, comme nous
avonsdéjàexpliqué,touslesschémasd’ordonnancementdansl’étatde
l’artsuiventuneouuneautreorientationderechercheindiquéeici.
• Troisièmement, nous proposons une nouvel contrainte temps réel en
relaxant(m,k)firmpourdéfierlacontraintetraditionnelled’échéance
sur les instances individuelles. Cette novelle contraint temps réel est
appelé contrainte « relaxed (m, k)firm notée R(m,k)firm », qui
remplacel’échéancetraditionneldepaquet(parexemple)parunfac
teurdedélaid'un groupedepaquets(ou un groupd’instancesdetâ
che). Nous demontrons que cette contrainte est plus flexible et bien
adaptéeauxfluxmultimédias,telsqueMPEGetMP3,etc.Enfin,une
condition suffisant d'allocution de ressources est donnée pour un en
sembledetâchessousl'ordonnancementnonpréemptifàprioritéfixe.
Les simulations démontrent l'avantage en termes d'utilisation de res
sources.
Latroisièmecontributionestunnouveaumécanismedegestiondefiled'at
tente,appelé«doubleleaksbucket»(DLB),quipeutfournirlagarantiedéterministe
de la contrainte R(m, k)firm. DLB peut être mis en application dans Diffserv et
d'autres mécanismes de QoS, puisqu'il peut être simplement mis en application, en
remplaçantlemécanismelargementemployé«LeakyBucket»,pourgérerlestrans
missions multimédia temps réel sous la contrainte R(m, k)firm. Pour analyser ce
nouveaumécanisme,nousnousservonsdelathéoriedesfilesd’attenteet«network
calculus».
5L'applicabilité de notre nouvelle contrainte temps réel et le nouveau méca
nismesontdémontréssurlatransmissiondepaquetspourlesfluxmultimédiasetsur
unsystèmedecontrôleembarquédansl’automobile.
6


Chapitre 1
Contexte et état de l’art

Danscechapitre,nousprésentonsd'abordlecontextegénéraldesapproches
tempsréelcourantescomprenantlemodèledetâchestempsréeletlemodèledesys
tèmed’analyse.Lesdéfinitionsdetâchespériodiquesetsporadiquessontprésentées
endétailpuisqueleursparamètresréguliersmènenthabituellementàbeaucoupderé
sultatsdéterministes.Ensuite,nousprésentonsl’étatdel’artconcernantlacontrainte
« (m, k)firm » et les approches d'ordonnancement récentes à la garantie de la
contrainte(m,k)firm.Lacontraintedefenêtredynamique(windowcontrainte),une
contraintesemblableà(m,k)firm,seraégalementprésentéeainsiquesesapproches
d’ordonnancementdynamiques.Enplus,uneanalyseetunecomparaisonprofondes
sonteffectuéessurlesdiversalgorithmesd’ordonnancement.
Modèle de système
Danslesystèmetempsréelembarqué,lesaccèsconcourantsderessourcesse
produisentdansunsystème,quiauneressourcelimitée.Cetteressourcepourraitêtre
lacapacitéduprocesseurpourexécuterlademanded'exécutiondetâchesoulabande
passantederéseaupourlatransmissiondemessages.Donc,leproblèmeestcomment
ordonnancercesdemandesd’accèstandisquetoujoursgarantirlaperformancetem
porelledetâche.L'optimisationdutauxd'utilisationderessourcesestégalementim
portante puisque c'est un critère pour mesurer l'efficacité d'une méthode
7