La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

INFO-F-404 : Techniques avancées de systèmes d'exploitation

9 pages
Nikita Veshchikov e-mail : téléphone : 02/650.58.56 bureau : 2N8.213 URL : INFO-F-404 : Techniques avancées de systèmes d'exploitation Table des matières 1 Rappel théorique 1 1.1 Hypothèses et classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  • origine de la conception des processeurs dual-core au lieu du processeur pen- tium
  • temps de calcul restant de j3
  • algorithmes global
  • ordonnancement
  • processeur
  • algorithmes
  • algorithme
  • tâche
  • tâches
  • systèmes temps réel
  • systèmes temps réels
  • système temps réel
  • systèmes
  • système
Voir plus Voir moins
Nikita Veshchikov e-mail : nikita.veshchikov@ulb.ac.be tÉlÉphone : 02/650.58.56 bureau : 2N8.213 URL : http://student.ulb.ac.be/~nveshchi/
INFO-F-404 : Techniques avancÉes de systÈmes d’exploitation
Table des matiÈres
1
2
Rappel thÉorique 1.1 HypothÈses et classifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Algorithmes d’ordonnancement multiprocesseurs . . . . . . . . . . . . . . . . . . . . 1.3 Techniques par partitionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 RM partitionnÉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 EDF partitionnÉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Techniques globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 OptimalitÉ impossible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Anomalies d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 PrÉdictabilitÉ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (k) 1.4.4 Les algorithmes global EDF et EDF . . . . . . . . . . . . . . . . . . . . . .
Exercices
1
1 1 2 3 3 3 3 4 4 5 6 6
8
1
1.1
Rappel thÉorique
HypothÈses et classifications
Dans ce TP, nous allons Étudier l’ordonnancement temps rÉel sur des plates-formes multipro-cesseurs. La premiÈre question qui se pose est : “Quel est l’intÉrt d’utiliser plusieurs processeurs au lieu d’un seul ?”. Il y a plusieurs rÉponses À cette question : 1. La raison principale est financiÈre. Si nous pouvions obtenir une puissance de calcul Équiva-A lente ÀA, alors il est moins coÛteux d’acheterÀ l’aide de deux processeurs de puissance 2 A deux processeurs de puissance qu’un unique processeur de puissanceA. 2 2. Utiliser une plate-forme multiprocesseur prÉsente Également un avantage sur le plan de la consommation ÉnergÉtique. De nombreuses Études montrent que l’Énergie consommÉe par un processeur Évolue de maniÈre exponentielle par rapport À sa frÉquence de fonctionne-ment, c’est-À-dire sa puissance de calcul. De ce fait, utiliser deux processeurs de puissance A consomme moins d’Énergie que d’utiliser un unique processeur de puissanceA. 2 3. Un comportement similaire a ÉtÉ dÉcelÉ entre la dissipation de chaleur des processeurs et leur frÉquence de fonctionnement. En ce qui concerne la sociÉtÉ Intel, c’est cette augmenta-tion exponentielle de la dissipation de chaleur par rapport À la frÉquence de fonctionnement qui est À l’origine de la conception des processeurs Dual-core au lieu du processeur Pen-tium 5.
Nous distinguons trois types de plates-formes multiprocesseurs : 1. les plates-formes identiques : tous les processeurs de la plate-forme sont interchangeables et ont la mme puissance de calcul. 2. les plates-formes uniformes : chaque processeurPipossÈde sa propre puissance de calcul siet rÉalise(si×t)unitÉs de travail lorsqu’il exÉcute un travail duranttunitÉs de temps. 3. les plates-formes spÉcialisÉes : un tauxri,jest associÉ À chaque couple
( travailJi, processeurPj)
avec l’interprÉtation suivante :PjrÉalise(ri,j×t)unitÉs de travail lorsqu’il exÉcute le travail JiduranttunitÉs de temps.
Remarque :Nous avons la relation suivante entre ces diffÉrentes architectures :
plates-formes identiquesplates-formes uniformesplates-formes spÉcialisÉes.
2
Dans le cadre de ce cours, nous considÉrons des systÈmesfortement couplÉs, c’est-À-dire que tous les processeurs de la plate-forme possÈdent une base commune du temps et une mÉ-moire commune. Dans la suite, nous considÉrerons des plates-formes identiques composÉes de mprocesseursP1,P2,. . .,Pm.
1.2
Algorithmes d’ordonnancement multiprocesseurs
On distingue deux types d’approche pour l’ordonnancement multiprocesseur : 1. L’ordonnancementpar partitionnement. L’ensemble desntáches est divisÉ enmsous-1 2m i ensembles disjoints :. . . , ττ , τ , . Chaque sous-ensembleτest ensuite ordonnancÉ sur le processeurPiavec une stratÉgie d’ordonnancement locale monoprocesseur (tel que RM, i DM, EDF, etc). Lors de l’ordonnancement, les táches appartenant À la partitionτne sont jamais autorisÉes À tre exÉcutÉe sur un autre processeur quePi. Avec ce type d’ordonnan-ceur, chaque processeurPipossÈde sa propre file d’attente (sa propre Ready-queue) qui i contient À tout moment les travaux actifs deτ. 2. L’ordonnancementglobal. Il s’agit d’appliquer globalement une stratÉgie d’ordonnancement sur l’entiÈretÉ de la plate-forme multiprocesseur et d’attribuer À chaque instant lesmpro-cesseurs auxmtáches/travaux les plus prioritaires. Dans ce cas, outre la prÉemption des táches, on autorise aussi la migration de ces derniÈres ; c’est-À-dire qu’une táche peut com-mencer son exÉcution sur un processeurPi, tre prÉemptÉe et reprendre son exÉcution ultÉrieurement sur un autre processeur (disonsPj). Avec ce type d’ordonnanceur, il n’y a qu’une seule file d’attente commune À tous les processeurs.
Remarque :Ces deux types d’ordonnancement sontincomparables, c’est-À-dire qu’il existe des systÈmes ordonnanÇables avec un partitionnement et pour lesquels toute approche globale Échoue, et rÉciproquement il existe des systÈmes ordonnanÇables avec une approche globale et pour lesquels tout partitionnement Échoue.
1.3
1.3.1
Techniques par partitionnement
Introduction
Le problÈme de partitionnement est un problÈme mieux connu sous le nom de Bin Packing qui consiste À placer dansmboïtes de tailles identiques,nobjets de tailles diffÉrentes. Ici, les boïtes sont les processeurs et les objets sont les táches. Pour les systÈmes pÉriodiques À ÉchÉance sur requte, la taille des objets (des táches) est leur facteur d’utilisation et la taille des boïtes (des processeurs) est l’utilisation maximale que l’on peut atteindre (ln 2pour RM et1pour EDF). Ce
3
problÈme de Bin Packing est NP-Hard et on utilise dÈs lors des heuristiques telles que next-fit, best-fit, etc. afin d’approcher la solution optimale.
1.3.2 RM partitionnÉ   1m Pour crÉer un partitionnement. . . , ττ , qui permette À l’algorithme RM d’ordonnancer localement ces partitions sur chaque processeurPi∈ {P1, . . . ,Pm}, on peut utiliser n’importe quelles heuristiques citÉes plus haut. Il suffit d’utiliser la condition suffisante
i1/ni Utot(τ)< ni(21)
i afin de vÉrifier l’ordonnanÇabilitÉ des táches de chaque partitionτpar RM (nidÉnote le nombre i de táches appartenant À la partitionτet assignÉes au processeurPi). Il est cependant possible de dÉmontrer qu’en utilisant cette borne, on ne peut pas garantir la faisabilitÉ d’un systÈme dont le facteur d’utilisation est supÉrieur À2141%(cf. cours). Cette borne est trÈs contraignante car elle ne fournit aucun rÉsultat pour un grand nombre de systÈmes.
1.3.3
EDF partitionnÉ
i En ce qui concerne EDF, nous savons queUtot(τ)1est une condition nÉcessaire et suf-  i1m fisante pour chaque partitionτ. Pour crÉer un partitionnement. . . , ττ , qui respecte cette condition, Lopez et al. ont dÉveloppÉ l’algorithme FFDU (First-Fit-Decreasing-Utilization). Le prin-cipe est le suivant : on choisit À chaque Étape la premiÈre boïte (c’est-À-dire le premier proces-seur) qui convient en considÉrant les táches par valeurs dÉcroissantes du facteur d’utilisation. Ces mmes chercheurs ont ensuite dÉmontrÉ la conditionsuffisanted’ordonnanÇabilitÉ suivante.
Theorem 1(FFDU, EDF utilisation).Soitτun systÈme pÉriodique À ÉchÉance sur requte. Ce systÈme est ordonnanÇable par l’une des partitions FFDU (et EDF localement sur chaque proces-seur) si : (m+ 1) Utot(τ)<etUmax(τ)1(1) 2
1.4
Techniques globales
En ce qui concerne les stratÉgies d’ordonnancement globales, il existe deux rÉsultats (trÈs) nÉga-tifs qui sont repris ci-dessous. Heureusement, il existe Également certain rÉsultats positifs.
1.4.1
OptimalitÉ impossible
Definition 1(Algorithmes en ligne).Les algorithmes d’ordonnancement en ligne prennent leur dÉcision À chaque instant sur base des caractÉristiques des travaux qui sont actifs, sans connais-
4
sance des travaux qui arriveront dans le futur.
Theorem 2.Pour toutm >1, aucun algorithme d’ordonnancement en ligne et optimal ne peut exister pour des systÈmes avec deux ou plus d’ÉchÉances distinctes.
FIGURE1 – OptimalitÉ impossible
DÉmonstration.La dÉmonstration se fait pourm= 2mais il est facile de constater que la preuve reste valable pourm >2. Supposons qu’il existe un algorithme d’ordonnancement en ligne optimal pour deux processeurs et considÉrons le scÉnario suivant. A l’instant0, trois travauxJ1,J2etJ3 arrivent avecJ1= (e1: 2, d1: 4),J2= (e2: 2, d2: 4)etJ3= (e3: 4, d3: 8). Notre ordonnanceur optimal n’a que deux choix possibles : il exÉcuteJ3dans l’intervalle de temps[0,2]ou pas. 1.J3ne s’exÉcute pas dans l’intervalle de temps[0,2](cf. Figure 1, partie supÉrieure gauche). Dans ce cas, À l’instant4,J3s’est exÉcutÉ pour au plus2unitÉs. Donc, À l’instant4, le temps de calcul restant deJ3est au moins de deux unitÉs. A prÉsent, supposons queJ4= (e4: 4, d4: 8)etJ5(e5: 4, d5: 8)arrivent dans le systÈme. Notre ordonnanceur n’a pas d’autres choix que d’exÉcuterJ4etJ5dÈs l’instant4afin de respecter leur ÉchÉance. De cette faÇon,J3manquera obligatoirement son ÉchÉance À l’instant8et on voit qu’il aurait fallu commencer par exÉcuterJ3dÈs l’instant0(cf. Figure 1, partie supÉrieure droite), ce qui nous conduit au second scÉnario. 2.J3s’exÉcute dans l’intervalle de temps[0,2](cf. Figure 1, partie infÉrieure gauche). Dans ce cas, au moins l’un des deux travauxJ1ouJ2n’a pas terminÉ son exÉcution À l’instant2. PuisqueJ1etJ2sont identiques, supposons que c’estJ2qui n’a pas terminÉ À l’instant2. A prÉsent, considÉrons le scÉnario oÙJ4= (e4: 2, d4: 4)etJ5= (e5: 2, d5: 4)arrivent À l’instant2. Notre ordonnanceur n’a pas d’autres choix que d’exÉcuterJ4etJ5dÈs l’instant2 afin de respecter leur ÉchÉance. Clairement,J2ne rencontrera pas son ÉchÉance À l’instant 4et on voit qu’il aurait fallu commencer par exÉcuterJ2À l’instant0, ce qui nous ramÈne au premier scÉnario.
5
1.4.2
Anomalies d’ordonnancement
Definition 2(Anomalie).Nous disons qu’un algorithme d’ordonnancement souffre d’anomalies si un changement qui est intuitivement positif dans un systÈme ordonnanÇable peut le rendre non ordonnanÇable. Nous entendons par “changement intuitivement positif” tout changement qui est sensÉ allÉger la charge du systÈme (comme par exemple rÉduire le facteur d’utilisation d’une tAche ou encore rajouter un processeur À la plate-forme).
Attention :Les algorithmes d’ordonnancement multiprocesseurs sont sujet À des anomalies.
Theorem 3.Le cas pÉriodique synchrone ne correspond pas au pire cas pour les systÈmes de tAches sporadiques en ordonnancement multiprocesseur.
DÉmonstration.Soit le systÈme de táches sporadiquesτ={(1,1,2),(1,1,3),(5,6,6)}. L’instance particuliÈre deτÀ dÉmarrage synchrone ayant une activation de tous les jobs dÈs que possible est ordonnanÇable surm= 2processeurs en assignant les prioritÉs les plus ÉlevÉes aux táchesτ1et τ2. Une autre instance deτoÙ l’activation de la seconde instance deτ1est retardÉe d’une unitÉ de temps est quant À elle malheureusement non ordonnanÇable, par inspection. Par consÉquent, il n’est pas possible de considÉrer le cas pÉriodique synchrone comme Étant le pire case pour les systÈmes de táches sporadiques en ordonnancement multiprocesseur.
Actuellement, le pire cas (en terme de temps de rÉponse) est inconnu pour l’Étude des táches sporadiques.
1.4.3
PrÉdictabilitÉ
Nous venons de constater que nous ne disposons pas de la notion de pire cas en ce qui concerne les táches sporadiques. En revanche, les algorithmes d’ordonnancement pour les táches pÉriodiques/sporadiques sont en gÉnÉral prÉdictibles.
Definition 3(PrÉdictabilitÉ).SoitJ={J1, . . . , J`}un ensemble de travaux avecJi= (oi, ei, di). SoitS(Ji)l’instant auquelJidÉbute son exÉcution dans un ordonnancement et, de maniÈre similaire, soitF(Ji)l’instant auquelJitermine son exÉcution dans un ordonnancement. Soit 0 0 0 0 0 0 J={J , . . . , J}un ensemble de travaux dÉrivÉ deJtel queJ= (oi, e , di)eteei,i. Un algo-1i i` i 0 0 etF( )F(J), rithme d’ordonnancementAest prÉdictible si et seulement si on aS(J)S(Ji)Ji i i 0 i(1i`),JetJ(tel que dÉfini prÉcÉdemment).
Cette dÉfinition introduit le fait que, pour un ordonnanceur prÉdictible, il est possible de dÉter-miner une borne supÉrieure sur les temps de rÉponse des travaux en analysant la situation sous l’hypothÈse que chaque travail prend son pire temps d’exÉcution pour se terminer. Le caractÈre
6
prÉdictible des algorithmes d’ordonnancement est important car il permet de vÉrifier l’ordonnan-ÇabilitÉ en se focalisant uniquement sur les pire temps d’exÉcution des travaux/táches et non sur les durÉe d’exÉcution exactes.
Lemme 1.Tous les ordonnanceurs prÉemptifs, conservatifs et À prioritÉ fixe au niveau des travaux sont prÉdictibles lorsqu’ils sont utilisÉs sur des plates-formes identiques.
Remarque :Les algorithmes non prÉemptifs sont en gÉnÉral non prÉdictibles.
1.4.4
(k) Les algorithmes global EDF et EDF
Voici un rÉsultat prÉliminaire qui concerne l’algorithme “global EDF” :
Theorem 4.Pour un ensemble sporadique À ÉchÉance sur requte, la condition suivante est suffisante pour l’ordonnanÇabilitÉ surmprocesseurs identiques avec “global EDF”.
Utot(τ)m(m1)Umax
ce qui peut se rÉÉcrire :   Utot(τ)Umax(τ) m(2) 1Umax(τ) Malheureusement, lorsqueUmaxse rapproche de l’unitÉ, le nombremde processeurs nÉcessaires obtenu par cette expression tend vers l’infini. Cependant, nous savons qu’un systÈme est faisable (pour autant queCiDiτi) si le nombre de processeurs est Égale au nombre de táches. Nous avons donc :    Utot(τ)Umax(τ) mminn, 1Umax(τ) Lorsque le systÈme considÉrÉ n’est composÉ que d’une unique táche, on aUtot(τ) =Umax(τ) et l’expression ci-dessus devientm0. Il est Évident que pour n’importe quel systÈme, il doit toujours y avoir au moins un processeur et donc :     Utot(τ)Umax(τ) mmax 1,minn, 1Umax(τ) Les deux derniÈres remarques Étant Évidentes, nous ne considÉrerons par la suite que l’expres-sion 2. Dans cette section, nous allons voir une variante de l’algorithme global EDF que nous (k) appelons EDF . Cette variante va notamment permettre de rÉduire l’Expression 2. Voici les no-tations que nous allons utiliser : 1. Nous supposons que les táches sont indexÉes de telle sorte queU(τ1)U(τ2). . .U(τn).
7
(i) 2. Nous notons parτle systÈme constituÉ des(ni+ 1)táches avec les plus petites utili-sations deτ: (i) τ={τi, τi+1, . . . , τn}
(k) Voici le fonctionnement de EDF :
Pour toute tácheτiaveci < k:
Pour toute tácheτiavecik:
(k) EDF attribue Àτila plus grande prioritÉ (il suffit de fixer son ÉchÉance À−∞). (k) EDF attribue la prioritÉ de maniÈre similaire À EDF.
Theorem 5.Un systÈme sporadique À ÉchÉance sur requteτest ordonnanÇable surmproces-(k) seurs identiques par l’algorithme EDF , avec & ' (k+1) U(τ) m= (k1) + 1U(τk)
Theorem 6.Un systÈme sporadique À ÉchÉance sur requteτest ordonnanÇable surmminpro-(`) cesseurs identiques par l’algorithme EDF , avec ( & ') (k+1) n U(τ) mmin= min (k1) +(3) k=11U(τk) l m (k+1) U(τ) `est la valeur dekqui minimise l’expression(k1) +. 1U(τk)
2
Exercices
Exercice 1 : l’algorithme RM global et partitionnÉ
a)
b)
Trouver un systÈme qui soit ordonnanÇable par RM global et pas par RM partitionnÉ.
Trouver un systÈme qui soit ordonnanÇable par RM partitionnÉ et pas par RM global.
Exercice 2 : l’algorithme EDF partitionnÉ
Soit le systÈme temps rÉel donnÉ À la Table 1. Les táches sontpÉriodiques,À dÉpart simultanÉ etÀ ÉchÉance sur requte. Nous supposons qu’elles sontindÉpendantesentre elles et qu’elles sontprÉemptives. Nous supposons Également que nous disposons d’une plate-forme composÉ de 3 processeurs identiques.
8
Task index Tácheτ1 Tácheτ2 Tácheτ3 Tácheτ4 Tácheτ5 Tácheτ6 Tácheτ7 Tácheτ8
WCET 10 30 10 50 20 50 250 10
Deadline = Period 50 120 100 200 100 200 300 200
TABLE1 – SystÈme temps rÉel composÉ de 8 táches pÉriodiques À dÉpart simultanÉ et À ÉchÉance sur requte.
a)
b)
Que nous dit l’expression 1 quant À la rÉpartition des táches par FFDU ?
Construisez un partitionnement par l’algorithme FFDU.
(k) Exercice 3 : l’algorithme EDF
Soit le systÈme temps rÉel donnÉ À la Table 2. Les táches sontpÉriodiques,À dÉpart simultanÉ etÀ ÉchÉance sur requte. Nous supposons qu’elles sontindÉpendantesentre elles et qu’elles sontprÉemptives.
Task index Tácheτ1 Tácheτ2 Tácheτ3 Tácheτ4 Tácheτ5
WCET 14 1 2 1 1
Deadline = Period 19 3 7 5 10
TABLE2 – SystÈme temps rÉel composÉ de 5 táches pÉriodiques À dÉpart simultanÉ et À ÉchÉance sur requte.
a)DÉterminez le nombre de processeurs À utiliser si on emploie l’algorithme global EDF pour ordonnancer le systÈme.
b)DÉterminez le nombre de processeurs (et donc la valeur optimale dek) À utiliser si on emploie (k) l’algorithme EDF pour ordonnancer le systÈme.
9
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin