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

Description

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

Sujets

• Processeur
• Système
• Ordonnancement
• Algorithmique
• Calcul
• Global

Informations

• Publié par: sewyeng
• Nombre de lectures: 66
• Langue: Français

Extrait

Nikita Veshchikov e-mail : [e-mail] 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 processeurP i possÈde sa propre puissance de calcul s i et rÉalise(s i ×t)unitÉs de travail lorsqu’il exÉcute un travail duranttunitÉs de temps. 3. les plates-formes spÉcialisÉes : un tauxr i,j est associÉ À chaque couple

( travailJ i , processeurP j )

avec l’interprÉtation suivante :P j rÉalise(r i,j ×t)unitÉs de travail lorsqu’il exÉcute le travail J i duranttunitÉs de temps.

Remarque :Nous avons la relation suivante entre ces diffÉrentes architectures :

plates-formes identiques⊂plates-formes uniformes⊂plates-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 mprocesseursP 1 ,P 2 ,. . .,P m .

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 processeurP i avec 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 queP i . Avec ce type d’ordonnan- ceur, chaque processeurP i possÈ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 processeurP i , tre prÉemptÉe et reprendre son exÉcution ultÉrieurement sur un autre processeur (disonsP j ). 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 processeurP i ∈ {P 1 , . . . ,P m }, on peut utiliser n’importe quelles heuristiques citÉes plus haut. Il suffit d’utiliser la condition suffisante

i1/n i U tot (τ)< n i ∙(2−1)

i afin de vÉrifier l’ordonnanÇabilitÉ des táches de chaque partitionτpar RM (n i dÉnote le nombre i de táches appartenant À la partitionτet assignÉes au processeurP i ). 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 À2−1≈41%(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 queU tot (τ)≤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) U tot (τ)<etU max (τ)≤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.

F IGURE 1 – 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 travauxJ 1 ,J 2 etJ 3 arrivent avecJ 1 = (e 1 : 2, d 1 : 4),J 2 = (e 2 : 2, d 2 : 4)etJ 3 = (e 3 : 4, d 3 : 8). Notre ordonnanceur optimal n’a que deux choix possibles : il exÉcuteJ 3 dans l’intervalle de temps[0,2]ou pas. 1.J 3 ne s’exÉcute pas dans l’intervalle de temps[0,2](cf. Figure 1, partie supÉrieure gauche). Dans ce cas, À l’instant4,J 3 s’est exÉcutÉ pour au plus2unitÉs. Donc, À l’instant4, le temps de calcul restant deJ 3 est au moins de deux unitÉs. A prÉsent, supposons queJ 4 = (e 4 : 4, d 4 : 8)etJ 5 (e 5 : 4, d 5 : 8)arrivent dans le systÈme. Notre ordonnanceur n’a pas d’autres choix que d’exÉcuterJ 4 etJ 5 dÈs l’instant4afin de respecter leur ÉchÉance. De cette faÇon,J 3 manquera obligatoirement son ÉchÉance À l’instant8et on voit qu’il aurait fallu commencer par exÉcuterJ 3 dÈs l’instant0(cf. Figure 1, partie supÉrieure droite), ce qui nous conduit au second scÉnario. 2.J 3 s’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 travauxJ 1 ouJ 2 n’a pas terminÉ son exÉcution À l’instant2. PuisqueJ 1 etJ 2 sont identiques, supposons que c’estJ 2 qui n’a pas terminÉ À l’instant2. A prÉsent, considÉrons le scÉnario oÙJ 4 = (e 4 : 2, d 4 : 4)etJ 5 = (e 5 : 2, d 5 : 4)arrivent À l’instant2. Notre ordonnanceur n’a pas d’autres choix que d’exÉcuterJ 4 etJ 5 dÈs l’instant2 afin de respecter leur ÉchÉance. Clairement,J 2 ne rencontrera pas son ÉchÉance À l’instant 4et on voit qu’il aurait fallu commencer par exÉcuterJ 2 À 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τ 1 et τ 2 . Une autre instance deτoÙ l’activation de la seconde instance deτ 1 est 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={J 1 , . . . , J ` }un ensemble de travaux avecJ i = (o i , e i , d i ). SoitS(J i )l’instant auquelJ i dÉbute son exÉcution dans un ordonnancement et, de maniÈre similaire, soitF(J i )l’instant auquelJ i termine son exÉcution dans un ordonnancement. Soit 0 0 0 0 0 0 J={J , . . . , J}un ensemble de travaux dÉrivÉ deJtel queJ= (o i , e , d i )ete≤e i ,∀i. Un algo- 1 i i` i 0 0 etF( )≤F(J), rithme d’ordonnancementAest prÉdictible si et seulement si on aS(J)≤S(J i )J i i i 0 ∀i(1≤i≤`),∀Jet∀J(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”.

U tot (τ)≤m−(m−1)∙U max

ce qui peut se rÉÉcrire :   U tot (τ)−U max (τ) m≥(2) 1−U max (τ) Malheureusement, lorsqueU max se 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 queC i ≤D i ∀τ i ) si le nombre de processeurs est Égale au nombre de táches. Nous avons donc :    U tot (τ)−U max (τ) m≥minn, 1−U max (τ) Lorsque le systÈme considÉrÉ n’est composÉ que d’une unique táche, on aU tot (τ) =U max (τ) et l’expression ci-dessus devientm≥0. Il est Évident que pour n’importe quel systÈme, il doit toujours y avoir au moins un processeur et donc :     U tot (τ)−U max (τ) m≥max 1,minn, 1−U max (τ) 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(n−i+ 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τ i aveci < k:

Pour toute tácheτ i aveci≥k:

(k) EDF attribue Àτ i la 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= (k−1) + 1−U(τ k )

Theorem 6.Un systÈme sporadique À ÉchÉance sur requteτest ordonnanÇable surm min pro- (`) cesseurs identiques par l’algorithme EDF , avec ( & ') (k+1) n U(τ) m min = min (k−1) +(3) k=1 1−U(τ k ) l m (k+1) U(τ) oÙ`est la valeur dekqui minimise l’expression(k−1) +. 1−U(τ 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

T ABLE 1 – 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

T ABLE 2 – 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