Réponses aux questions des exercices - …wcours.gel.ulaval.ca/2016/h/GIF3003/default/5notes/notes/pdf_A10/... · temporelles et un fonctionnement en continu sur ... le système

GIF-3003 Systèmes parallèles et temps réel 292

April 29, 2009

Réponses aux questions des exercices

Chapitre 1 Introduction

R1.1 Le modèle SPTR inclut du matériel distribué, un traitement concourant, des contraintestemporelles et un fonctionnement en continu sur de longues périodes. On y différentie lesrétroactions interne et externe et les interfaces avec l’environnement sont explicites.

R1.2 Voir les notes de cours.

R1.3 besoins: agir (traitement et action) sur l’environnement d’une façon particulière (e.g. lecontrôler) en fonction de son état (données brutes de la perception et données transforméessuite au traitement).contraintes: limites sur les mesures et actions imposées par l’environnement et objectifs oucritères de performance (vitesse maximale, temps réel, fiabilité, ratio performance/coût,flexibilité, etc.).ressources: caractéristiques des interfaces avec l’environnement (capteurs et actuateurs) et desarchitectures de traitement disponibles (matériel et logiciel système).logiciel d’application: concerne principalement le traitement mais intervient aussi pour laperception et l’action (incluant la rétroaction entre les deux).

R1.4 Pour ce système il y a 3 phases cycliques qui fonctionnent en continu. Les calculs intensespouvant être réalisés par des mécanismes matériels sont les traitements des images provenantdes caméras et les calculs de cinématique pour la robotique. Les événements principauxauxquels doit réagir le système est l’arrivée d’un objet dans le champ de vision des caméras etson déplacement selon une trajectoire inconnue. Des contraintes de temps doivent alors êtrerespectées. De plus, le système doit être tolérant aux fautes, en particulier si l’application estcritique, e.g. dans l’espace.

R1.5 A-d, B-c, C-g, D-a, E-h, F-e, G-f, H-b.

Lorsque plusieurs processus peuvent être actifs en même temps, on parle de traitementconcourant. Si ces processus s’exécutent sur différents processeurs, on parlera alors detraitement parallèle. Le traitement concourant est un traitement potentiellement parallèle.

R1.6 a-D, b-A,G, c-B, d-A,B,G,H, e-A,(G), f-A,G, g-B, h-B, i-D, j-B,G, k-H, l-F, m-H, n-G, o-C,D,E,F, p-A,G.

R1.7 Les navigateurs Internet ont des contraintes explicites (sévères) sur le temps de réponse, aumoins en ce qui concerne l’établissement d’une communication. De plus, ils ont plusieurscontraintes implicites (indulgentes) fixées par l’utilisateur, en particulier pour les applicationsmultimédia véhiculant des signaux audio (voix, musique) ou vidéo, en direct ou en différé.


Réponses aux questions des exercices Robert Bergevin (c)

Chapitre 2 Architectures et traitement parallèles

R2.1 Le couplage est serré lorsque les interactions sont nombreuses entre les processeurs. Il estlâche lorsqu’elles sont rares.

R2.2 A: b,e,g,i,j.B: c,d,f,j.C: a,h.

R2.3 MIMD car temps de calcul = maximum des sommes vs. somme des maximums pour SIMD.

MIMD car les communications créent des délais de synchronisation entre les processus (ilsdoivent s’attendre). Pour le SIMD, la synchronisation existe déjà pour toutes les instructions.

R2.4 SIMD: 1 programme, granularité fine, calcul à référence spatiale, processeurs moins puissantset plus nombreux, processeurs en couplage serré, structures de données spéciales dans leslangages de programmation (e.g. plural), exécution synchrone.MIMD: n programmes, granularité grossière, plus flexible, processeurs plus puissants,processeurs autonomes, R/C élevé, primitives de communication dans le langage, exécutionasynchrone.

Capacité d’augmentation de performance proportionnelle à l’augmentation des ressources(e.g. nombre de processeurs ou liens de communication) donc idéalement pas de perted’efficacité.

R2.5 Dans une architecture dite de Harvard, il y a 2 mémoires séparant les instructions et lesdonnées.

R2.6 L’explication peut se faire facilement par un dessin:

R2.7 MIMD avec mémoire distribuée:

R2.8 Dans ce type de langage, l’ordre d’évaluation des instructions n’est pas décrit par le

N x NN:N

NxN n:n



programmeur mais plutôt déterminée par les données et leurs interdépendances. L’ordred’évaluation est choisi par le compilateur ou l’environnement d’exécution. Ceci permet defaciliter la programmation lorsque plusieurs threads de contrôle s’exécutent simultanément etqu’ils sont en interaction. Ces machines sont particulières en ce qu’elles n’ont pas de IPs ni deIMs. Les DPs doivent générer les étiquettes de leurs données eux-mêmes.

R2.9 IP: unité de contrôle, CU, CCU.DP: unité arithmétique et logique, ALU.

R2.10 Pour IP/DP n:n.Pour DP/DM nxn (aucun réseau DP/DP car mémoire partagée donc communiquent par lamémoire).

R2.11 IP: processeur d’instruction. Il lit instructions en mémoire, les décode et transmet lesinformations au DP (il exécute aussi les branchements e.g. jmp si nécessaire).DP: processeur de données. Il va chercher les données en mémoire DM et exécute lesopérations arithmétiques et logiques puis transcrit les résultats en mémoire. Il comporte lesregistres d’usage général.IM: mémoire d’instruction. Elle contient le code à exécuter.DM: mémoire de données. Elle contient les données.commutateurs. Ils relient les unités entre elles.

Classification selon nombre d’unités de chaque type et types de commutateurs. Aussi, il y a undiagramme d’état pour décrire le fonctionnement interne de l’architecture.

n IP; n IM; n-to-n IP-IM; n DP; n DM; n-to-n DP-DM; n-to-n IP-DP; nxn DP-DP.

IP et IM.

R2.12 C

A

A (ou B)

C

A

C

C

B



B

R2.13 de gauche à droite: réseau nxn, DM, DP, réseau n:n, IP, réseau n:n, IM.

R2.14 boucle 5, 2, 3, 7, 1, 4, 6 avec communications 5 (IP), 2 (IP), 3 (DM), 7 (DM), 4 (IP), 6 (DM).

R2.15 niveau 1: un seul IP (une seule instruction décodée à la fois).niveau 1: un seul DP (une seule instruction exécutée à la fois).niveau 2: N états séquentiels et durée minimale de chaque état (e.g. vitesse d’exécution desinstructions).niveau 2: limite sur vitesse de transfert entre les éléments aux points de synchronisation (IP/DP, IP/IM, DP/DM).

non, car étant interne à un processeur il affecte également les ordinateurs séquentiel etparallèle.

SIMD car synchronisation des processeurs au niveau des instructions (ou MIMD émulant leSIMD!)

non, le temps sera le même pour les deux car structurée implique que le temps de calcul estindépendant des données et l’application sera donc synchronisée au niveau des instructionspeu importe si elle est sur SIMD ou MIMD.

R2.16 Nombre N de données supérieur au nombre P de processeurs donc plus d’une donnée parprocesseur. Il y a deux types: hiérarchique (données voisines sur un même processeur) et cut-and-stack (données voisines distribuées sur les différents processeurs) Cette division desdonnées se retrouve au niveau du partitionnement dans lequel on peut aussi diviser les calculsen plusieurs processus.

diamètre: étoile est mieux.degré: anneau est mieux.uniformité: anneau est mieux (maître n’importe où)coût: identique n-1 liens.extension: à peu près égal (mais anneau affecte deux noeuds existants)connexité: anneau est mieux.fiabilité: anneau mieux.transformation vers hypercube: anneau est mieux (expansion et dilatation)routage: étoile est mieux.

minimum de noeuds à ajouter sans changer la topologie.nombre de noeuds existants affectés par cet ajout minimum.

extension: considère l’architecture matérielle seulement.mise à l’échelle: la performance d’un algorithme s’exécutant sur cette architecture estconsidérée.



dilatation = n.

M: partitionnement car on décide de la décomposition du calcul en processus.R/C et P: allocation (et mise à l’échelle pour P) car cette phase inclut le choix del’architecture.

La durée des calculs est celle du processeur ayant le plus de processus et elle dépend de cenombre et de la vitesse des processeurs R.La durée des communications correspond à une communication de durée C pour chaque pairede processus sur des processeurs différents. Chaque processeur a donc ki (M-ki)communications mais il faut diviser par 2 la somme de tous les processeurs sinon on comptedeux fois la communication entre deux processeurs donnés.

TC= (M/P)R + (M*M)C/2 - (M*M)C/(2P) = RM donne R/C = M/2.

terme de droite devient M’(P’-1)C/2 où P’ est le nombre de processeurs utilisés dansl’allocation.

(M/P)R + M(P-1)C/2 = RM donc R/C = P/2.

R2.17 Ratio du nombre de noeuds du réseau physique sur le nombre de noeuds du réseau logique.

dilatation = n.

R2.18 Un nombre plus élevé de processus qu’il y a de processeurs disponibles.

R2.19 Vrai.

R2.20 Vrai.

R2.21 hiérarchique: le nombre de blocs de données est égal au nombre de processeurs disponibles.cut-and-stack: la dimension des blocs de données est égale au nombre de processeursdisponibles.

R2.22 hiérarchique: 48 données doivent être divisées en un nombre entier P de blocs de mêmedimension. P = 48, 24, 16, 12, 8, 6, 4, 3, 2 ou 1.cut-and-stack: 48 données doivent être divisées en un nombre entier de blocs de mêmedimension P. mêmes valeurs de P (inversées): P = 1, 2, 3, 4, 6, 8, 12, 16, 24 ou 48.

le nombre de rangées d’un bloc doit être le même que son nombre de colonnes. Ce nombre estdonc égal à 1 ou 2. hiérarchique: P = 48 ou P = 12.cut-and-stack: P = 1 ou P = 4.



R2.23 maître-esclaves.

R2.24 Une topologie ouverte a des liens libres (ex. pipeline, maille). Elle peut utiliser ces liens pourcommuniquer avec l’extérieur et ainsi améliorer l’efficacité.

R2.25 Elles dépendent de la dimension du problème, du nombre de processeurs et de l’architecturede l’ordinateur parallèle sur lequel il sera implémenté.

R2.26 C’est la proportion intrinsèquement séquentielle d’un programme.

R2.27 Vrai.

R2.28 Si les processus sont de granularité grossière, le ratio R/C est élevé.

S’ils sont de granularité fine, le ratio R/C est faible.

R2.29 Vrai.

R2.30 R: courbe ascendante car le parallélisme diminue lorsque la granularité est plus grossière(moins de processeurs en parallèle) et donc le temps de calcul augmente.C: courbe descendante car le nombre de communications diminue lorsque le parallélismediminue et le temps de communication total diminue donc.

point de rencontre des deux courbes donne T = R+C minimum. À gauche et à droite, unecourbe augmente plus vite que l’autre diminue donc le total est plus grand qu’au point derencontre.

R2.31 non car l’accélération S est définie en comparant le temps de l’application (algo) parallèle àcelui de l’application (algo) séquentielle. Ici, E est défini en fonction de l’application parallèleseulement.

E = (R/C) / (1 + (R/C)) donc E maximum si R/C >> 1 ce qui veut dire granularité grossière.

R2.32 Faux, c’est le minimum.

R2.33 Vrai.

R2.34 Rapport entre T(n,1) et T(n,P) où n est la dimension du problème et P le nombre deprocesseurs.

Accélération par processeur.

Amdahl: 1/s = 1/0.1 = 10.

R2.35 L’accélération est le rapport entre le débit de l’ordinateur parallèle sur le débit de l’ordinateurséquentiel.

L’efficacité est le débit par processeur de l’ordinateur parallèle.

L’efficacité est le rapport entre R/C et (1 + R/C).



Si R/C << 1.

Généralement faible car R et C sont comparables (R/C est d’ordre de grandeur 1 et peut mêmeêtre assez petit si le nombre de communications dépasse le nombre de calculs).

Le débit peut être élevé même si l’efficacité est faible car il y a un grand nombre deprocesseurs.

R2.36 ordonnancement: moins de perte de temps par changement de contexte si la granularité estgrossière.interdépendances: moins de blocage si la granularité est grossière.équilibrage: plus de temps morts si la granularité est grossière.communications: moins de traitement utile (calcul) en proportion si la granularité est fine.calculs: plus rapides si la granularité est fine (augmentation du parallélisme).

R2.37 1/s = 20.

Loi de Amdahl avec s+p = 1.

Loi de Amdahl avec S = 19 donne P = 361.

R2.38 V

F

F.

R2.39 Dans les deux cas on fait le rapport du temps séquentiel sur le temps parallèle.Amdahl: p est la proportion parallélisable du calcul séquentiel. Elle prend un temps P fois pluscourt. La proportion s prend un temps identique dans la version parallèle. S = (s+p)/ ((p/P)+s)et s+p = 1.Gustafson: s est la proportion non-parallélisée du calcul parallèle. Elle prend un tempsidentique dans la version séquentielle: S = (s+pP)/(s+p) et s+p = 1.

R2.40 E = S/P vient de S qui est basée sur les proportions s et p. Ces proportions ne tiennent pascompte du fait qu’il existe dans la version parallèle une surcharge due aux traitements quin’existent pas dans la version séquentielle (e.g. communications supplémentaires,synchronisations, etc.).

Smax = 1/s = 20.

20 (0.95) = 1/((0.95/P) + 0.05) donc P >= (20)(0.95)(0.95) / (1 - (20)(0.95)(0.05)) = 361.

n est constant.

R2.41 S’ = (s+pP)/(s+p) = s + pP = s + (1-s) P = P - s(P-1).



R2.42 S = T1/TP et T1 = s+p =1 où p est la partie parallélisable.hypothèses: mêmes opérations et s (et p) constante.p = influence et P = amélioration.

La durée parallèle est normalisée. La proportion parallélisée est plus longue en séquentiel parun facteur P.

p = (1-c) pT et S’ = s+pP / (s + pT).

E=S/P.

On vise n = n(P) tel que E = constante (iso-efficacité).

R2.43 TC= (M/P)R + (M*M)C/2 - (M*M)C/(2P) = RM donne R/C = M/2.

S=1 (TC identiques).

R2.44 L’accélération est tracée pour une dimension n du problème qui est fixe. L’algorithme 1 estcomplètement parallélisable. L’algorithme 2 a une proportion non-parallélisable. L’algorithme3 a une proportion non parallélisable et doit aussi ajouter des opérations en surcharge lors dela parallélisation.

S = T1/TP et T1 = s+p =1 où p est la partie parallélisable.hypothèses: mêmes opérations et s (et p) constante.p = influence et P = amélioration.

Smax = 1/s = 1/.20 = 5. 0.9 * 5 = 4.5 = 1/ (0.2 + 0.8/P) donc P = 36.

R2.45 n (P) = 8 P logP

oui (puisque E est constant)

non (s diminue sinon S ne serait pas proportionnelle à P et E ne serait donc pas constant)

oui (car n est supérieur à P)

Après addition des nombres sur chaque processeur aux feuilles de l’arbre (lorsque n estsupérieur à P i.e. lorsqu’il y a virtualisation), le calcul de la somme des m nombres résultants(m=n si n=P) aux feuilles de l’arbre de log(m) niveaux (+ la racine) correspond au calcul de lasomme de m/2 nombres, obtenus par les sommes des paires de nombres consécutifs, sur unarbre de log(m)-1 niveaux. Il s’agit donc d’une série de sommes imbriquées sur des arbres deplus en plus petits (jusqu’à 1 niveau).

R2.46 m=n=P donc hypercube de dimension i.



Ceci correspond aux P processeurs au dernier niveau (feuilles) de l’arbre binaire duredoublement récursif. Dans cet algo, un seul niveau de l’arbre est utilisé à la fois donc il n’estpas nécessaire d’avoir des processeurs différents sur les autres niveaux. De plus, seul le noeudracine et son fils de droite doit communiquer avec tous les autres niveaux donc avec iprocesseurs voisins si on veut garder des communications directes. Le réseau hypercube dedimension i a aussi un degré i i.e. suffisamment de voisins pour le noeud racine (celui quicalcule la somme totale).

oui. Si les niveaux de l’arbre sont actifs simultanément, il y aura plusieurs processus (noeudsde l’arbre) placés sur un même processeur de l’hypercube. L’expansion sera inférieure à 1avec une perte de parallélisme potentiel (la performance des calculs sera réduite, celle descommunications augmentée). Certains noeuds voisins de l’arbre seront voisins surl’hypercube et d’autres seront sur le même processeur.

non. Si tous les noeuds de l’arbre sont placés sur un hypercube ayant un noeud de plus, dèsque la dimension i est supérieure ou égale à 3, il y a une dilatation supérieure à 1.

oui, les calculs et les communications sont très structurés. Un même algorithme est exécutépar chaque processeur.

R2.47 Amélioration de l’accélération S entre P=8 et P=16. Tableau donne E=S/P donc S=EP

Avec N=64: P=8 donne S=0.57*8=4,6 et P=16 donne S=0.33*16=5,3.

Donc amélioration de l’accélération de 5,3-4,6 = 0,7.

Avec N=512: P=8 donne S=0.91*8=7,3 et P=16 donne S=0.80*16=12,8.

Donc amélioration de l’accélération de 12,8-7,3 = 5,5.

R2.48 T (n,p): (n/p)-1 = (10000/128)-1 = 77,125 et 2*log p = 2*log128 = 14.Donc T(n,p) = 77,125 + 14 = 91,125.

L’accélération est S = T(n,1) / T(n,p) = (10 000 -1) / 81,34 = 123.

Infinie.

Oui, selon la loi de Amdahl, la limite de l’accélération donne l’avantage maximal obtenu enaugmentant le nombre de processeurs même jusqu’à l’infini. En théorie, cette limite augmentetoujours avec P même si cette augmentation se fait de plus en plus lentement.

R2.49 Par redoublement récursif, i.e. que l’on fait des sommes de paires en parallèle et de façonhiérarchique.



L’efficacité tend vers 0.

Parce que la proportion parallèle du traitement n’est plus limitée et qu’elle devientprépondérante dans le calcul.

R2.50 Rapport entre la complexité temporelle du meilleur algorithme séquentiel connu pour ceproblème et la complexité temporelle de l’algorithme parallèle correspondant.

SIMD ou granularité fine car R/C << 1 et efficacité << 1.

s = 0.01; p=0.99; Amdahl donne Smax = 100 donc ici S=95. Amdahl et isole P donne P =1881.

Parce que la proportion parallèle ou locale du traitement n’est plus fixe si le nombre dedonnées assignées à chaque processeur augmente. Elle peut devenir prépondérante dans lecalcul, ce qui augmentera l’efficacité des processeurs. Autrement dit, la partie globale (sommerécursive) devient négligeable si le nombre de données assignées à chaque processeuraugmente beaucoup.

R2.51 Log2(N).

1/log2(N).

Elle n’est pas parfaite car E diminue avec N (et P).

R2.52 Elle est égale à: (n/P - 1) + 11 logP.

T(n,1) = 255, S=255/((255/P - 1) + 11logP);1:1.0, 4:3.0, 16:4.32, 64:3.7, 256:2.9

S’(n,P)= (nP-1)/((nP/P-1)+11logP)=nP-1/((n-1)+11logP)=(256P-1)/255+11logP.1:1.0, 4:3.69, 16:13.7, 64:51.04, 256:191.06

Loi de Amdahl: n fixe et P augmente donc s, la proportion séquentielle, augmente etl’efficacité diminue, tendant rapidement vers zero. (E= 1.0, 0.75, 0.27, 0.058, 0.011)Loi de Gustafson: n augmente avec P donc l’accélération augmente toujours. Par contre, sil’augmentation de n n’est pas suffisante (ici n = 256P), on est en-dessous de la fonction d’iso-efficacité et donc l’efficacité diminue graduellement (quoique beaucoup plus lentement quepour n fixe). (E= 1.0, 0.92, 0.86, 0.80, 0.75))

n=n(P)=PlogP pour E constant.

R2.53 sum = 0for i = 0 to log2(N-1)for j = 0 to (N/(2^^(i+1)))-1)



index = 2^^(i+1);index2 = index + 2^^i;A(index) = A(index) + A(index2);endforendfor(...(((A0+A1) + (A2+A3)) + ((A4 +A5) + (A6+A7))) +... + (...+ (A(N-2) + A(N-1)))...)

Sommation{i =0 to (log_2 N) -1} N / 2^^(i+1) = N/2 + N/4 + N/8 +... + 1 = 1 + 2 + 4 + 8 +...+ N/2 = N-1 additions.

N-1 additions sont faites en partie en parallèle (à chaque “niveau” i.e. pour i constant doncadditions dans la boucle j se font en parallèle). Il faut ajouter les temps de transfert(communication) des résultats partiels mais ils peuvent être compensés par les additions enparallèle.

R2.54 E = R / (R + C) = Rmat (n/P - 1) / (Rmat (n/P - 1) + 1.25 Rmat logP) = 0.8donc (n/P - 1) = 5logP et n = (5logP +1) P.

Tp = R + C et T1 = Rmat (n-1).E = S/P = Rmat (n-1) / (Rmat (n/P - 1) + 1.25 Rmat logP) P.Si n/P >> 1 et n >> 1, on obtient E = Rmat (n) / (Rmat (n/P) + 1.25 Rmat logP) P = 0.8donc n = 5 P logP.

R2.55 n-1 dans les deux cas.

niveau 1 (racine): 1 addition S=1.niveau 2: 2 additions en parallèle: S=2.niveau 3: 4 additions en parallèle: S=4.moyenne = (4+2+1)/3 = 7/3 = (n-1)/log n pour n = P = 8 processeurs. Même formule si n plusélevé mais toujours une puissance de 2.

S=1/((1-p) + p/P) = (n-1)/log n.en développant on obtient p = (1 - log n/(n-1)) (n / (n-1)).

S non changée si communications négligées.E 2 fois meilleure.

cut-and-stack: max de L = n/P répétitions de chaque étape (niveau de l’arbre) de l’algo sansvirtualisation avec n processeurs.S = O (n)/(n/P) log P = O (P)/ (log P)E = O (1/logP)hiérarchique: L = n/P additions séquentielles sur chaque processeur au début, suivi de l’algosans virtualisation avec P processeurs.S = O (n / (L + logP))



E = O (L / L + logP).

E = O (1).

L’hypothèse que l’on doit faire les mêmes additions que pour l’algorithme sans virtualisationn’est pas nécessaire car l’ordre des additions ne change pas le résultat. Autrement dit, onpourrait exécuter l’algorithme sur un vecteur de nombres permuté et le résultat serait le même.Donc, dans le cas de l’addition des nombres on peut prendre l’algorithme hiérarchique mêmeavec la virtualisation cut-and-stack.

R2.56 8 noeuds, 16 liens, diamètre 2, degré 4.

Oui, même degré pour tous les noeuds.

4 = degré.

4 = valeur maximale. C’est un réseau régulier donc = au degré.

Non.

R2.57 Capacité d’extension: facilité d’obtenir un réseau avec plus de processeurs mais de mêmetopologie.Capacité de mise à l’échelle: facilité d’obtenir une performance proportionnelle au nombre deprocesseurs.

R2.58 Améliorer la robustesse et l’efficacité du réseau en anneau.

R2.59 dimension i implique degré i. Donc chaque noeud a i liens. Dans l’anneau, chaque noeud a 2liens. Il faut ajouter i-2 liens par noeud. Le nombre total de cordes ajoutées est obtenu enmultipliant le nombre de noeuds par le nombre de liens ajoutés par noeud et en divisant par 2(liens bidirectionnels!).Noeuds (anneau): 2i

Cordes ajoutées: 2i*(i-2)/2 = (i-2)2(i-1). Exemple: i = 3 donne N=8 et C=4; i=2, 3,...

R2.60 Étape 1: On étiquette les noeuds de l’anneau de 0 à 7 en binaire.

Étape 2: On étiquette les noeuds de l’hypercube selon le code de Gray binaire réfléchi.

Étape 3: On fait la transposition directement.

R2.61 On a r=1, s=2, i = {0,1} et j={0,1,2,3}.

Codes obtenus par concaténation d’un élément du premier groupe G(i,r) avec un élément dusecond groupe G(j,s) ci-dessous (2x4 = 8 codes pour 8 noeuds).G(0,1) = 00G(1,1) = 01



G(0,2) = 00G(1,2) = 01G(2,2) = 11G(3,2) = 10

R2.62 Maximum, pour toute paire de noeuds, du nombre minimum de noeuds intermédiaires, pourtout chemin, entre les deux noeuds.

8.

Nombre de liens vers tous les autres noeuds.

Noeud central: 7; autres noeuds en périphérie: 1.

Hypercube.

R2.63 Vrai: anneau peut être transpose sur hypercube; liens supplémentaires de l’hypercube (en plusdes deux présents sur l’anneau avec les voisins de chaque côté) sont ajoutés comme cordes del’anneau.

R2.64 3 (4x4), 1 (6x3), 2 (8x4).

R2.65 H(A,B).

123 (010 011 001 101) 231 (010 000 100 101) 312 (010 110 111 101) ou132 (010 011 111 101) 213 (010 000 001 101) 321 (010 110 100 101).

Oui, 2.

R2.66 8.

48.

n! 2n (choix du noeud 0 * choix de l’ordre des dimensions i.e. voisins du noeud 0)

R2.67 On a 3 pour H(A,B)=3.

d.

R2.68 H(A,B) + 2

H(A,B) + 2

R2.69 1/0.1=10

Amdahl: P = Sp/(1-sS) = 8(0.9)/(1-0.8)=7.2/0.2=36-> P = 64 (S>=8) et dimension = 6.

R2.70 16 noeuds: 2 cubes reliés noeud à noeud. Adresses selon construction hiérarchique.



LSB -> MSB: 1011, 1001, 1101, 0101(ou MSB -> LSB: 1011, 0011, 0111, 0101)

R2.71 4, 2, 2

Ajouter liens 1:4, 2:4, 3:6, 3:53, 2, (2, 3, 3, 4, 4, 3, 3, 2)

Tolérance aux fautes (plus de liens et chemins).Moins de conflits ou contentions (plus de liens et chemins)Plus rapide (diamètre réduit)

R2.72 Chemin possible: 00100 -> 00110 -> 01110 -> 11110.

Pour obtenir la distance, on fait un ou-exclusif entre la source et la destination, soit:

00100 XOR 11110 = 11010 et on compte le nombre de 1. Ici, la distance est donc égale à 3.

R2.73 V

V

V

F

F

F (identiques car tous les chemins sont directs).

V (pas de cycle car on change de dimension séquentiellement sans revenir à la première).

F

R2.74 réseau dynamique car il est configuré selon les chemins pris dans le réseau par chaque paquet.Si c’était un réseau statique, on aurait une structure récursive à l’infini...

log2(64) = 6

nombre de 1 dans XOR(source, destination) = 3.

on aura le nombre maximum de chemins possibles si la longueur minimale est égale audiamètre i.e. 6. Dans ce cas, il faut se déplacer dans chaque dimension du réseau. L’ordrechoisi pour ces déplacements correspond à un chemin possible. Pour le premier déplacement,il y a 6 choix, pour le deuxième il en reste 5, etc. donc le nombre maximum est 6! = 720.



SAF: chaque paquet est emmagasiné à chaque noeud au complet avant de poursuivre.VCT: un paquet est emmagasiné ssi le noeud suivi n’est pas libre (n’a pas d’espace pour cepaquet).WR: le paquet n’est pas emmagasiné mais plutôt décomposé en flits et distribué le long duchemin.

R2.75 P-1 étapes.

étoile car le diamètre est le plus petit dès que P > 4.

hypercube: k étapesanneau: [P/2] étapesétoile: P-1 étapes

1. nombre d’étapes minimum (à toute étape, tous les processeurs ayant les données vont lestransmettre à un processeur ne les ayant pas).2. performance maximale de chaque étape (toute communication 1:1 est directe).

R2.76 logP étapes de durée D donc T = DlogP

R2.77 sans virtualisation, l’expansion minimum ne peut être inférieure à 1.hypercube k-D donne 2^^k processeurs qui sont placés sur arbre binaire de 2^^(k+1) - 1processeurs i.e. k+1 niveaux, en incluant la racine de l’arbre. Ex: hypercube 3-D a 8processeurs qui sont placés sur arbre binaire de 4 niveaux ou 15 processeurs (8 feuilles).L’expansion est donc (2^^(k+1) - 1) / 2^^k. Ex: 7/4, 15/8, 31/16, etc.Pour minimiser la dilatation, on place les processeurs sur les feuilles de l’arbre et le parent esttoujours le même processeur que l’enfant de gauche. La dilatation est égale à 2k - 3 ce quicorrespond à un chemin du noeud d’extrême droite en bas de la 1ère branche de gauche vers lenoeud d’extrême droite en bas de la branche de droite..

V

F: hypercube: k(2^^(k-1)) liens et arbre binaire: (2^^k)-2 liens.

R2.78 minimale: phase 1: negative hops i.e. s=1 d=0phase 2: positive hops i.e. s=0 d=1ordre des hops à chaque phase: arbitrairenon-minimale: ajoute “neutral-1” hops à la phase 1 i.e. s=1 et d=1 (va vers 0)

Hops MSB à LSB: negative, positive, negative, neutral-1.2 chemins de longueur 3: (2! choix de l’ordre à la phase 1)1011, 1001, 0001, 0101 ou 1011, 0011, 0001, 0101.



12 chemins de plus de longueur 5 (en plus des 2 minimaux de longueur 3).3! = 6 choix de l’ordre à la phase 1 et 2! = 2 choix de l’ordre à la phase 2 (neutral-1 a créé unhop +)1011, ((1010, (0010 ou 1000)) ou (1001, (1000 ou 0001)) ou (0011, (0010 ou 0001))), 0000,(0100 ou 0001), 0101.

R2.79 exclusion mutuelle: un seul paquet occupe une partie donnée du tampon à la fois.hold-and-wait: un paquet occupera une partie du tampon tant qu’il est bloqué sur son chemin.aucune préemption: les tampons ne sont pas vidés automatiquement par le réseau.

cycle horaire et cycle anti-horaire sont formés chacun de 4 changements de directiongéographique.

élimine deux changements de direction par cycle.

parce qu’un changement dans le cycle horaire donne un chemin équivalent à un changementdans le cycle anti-horaire (et vice-versa). Si on enlève le changement équivalent dans l’autrecycle, on obtient un cycle avec croisement (un “huit”).

NW et ES.

R2.80 De l’extérieur vers l’intérieur: banyan, banyan régulier, delta, oméga.

R2.81 Permutation de type mélange parfait.

R2.82 Méthode de routage: le i ème bit le plus significatif de l’adresse de destination déterminel’activation du i ème commutateur. Ainsi, si ce bit est à 0 le chemin passe par la sortie du hautsur le commutateur du i ème étage, tandis que si le bit est à 1, la sortie du bas est utilisée.

R2.83 Vrai.

R2.84 On a 2 exp 7 =128 donc 7 étages (log2128).

R2.85 Plutôt que de transiter seulement à travers les commutateurs, le message peut passer par desprocesseurs (noeuds) intermédiaires et ainsi passer plusieurs fois par les commutateurs afind’arriver à destination.

R2.86 Direct (STR: “straight”).

R2.87 2 étages de 2 commutateurs reliés shuffle-exchange.

Adresse binaire de départ = 01; adresse binaire de destination = 11.Donc sort par le bas sur les 2 commutateurs du chemin.1er étage: XCH ou UB; 2ième étage: STR ou LB.

Non car il y a une faute dans l’étage d’entrée (certaines sources sont inaccessibles).

R2.88 N! = 4! = 24; 2^^4 = 16 non bloquantes (2 états possibles pour 4 commutateurs) donc PC =16/24 = 66.7%.



R2.89 Adresse binaire de M5: 100; départ de P2; étage 1/rangée 2: sort par le bas (MSB=1); étage 2/rangée 4: sort par le haut (2ième bit=0); étage 3/rangée 3: sort par le haut (LSB = 0).

Étage 1: XCH ou UB; étage 2: STR ou UB; étage 3: XCH ou LB.

P1: M5P3, P5, P7: M5P4, P8: M5 et M6P6: M5 à M8.

R2.90

3 étages de 4 commutateurs. 2 processeurs consécutifs par commutateur à l’entrée du 1erétage; 2 mémoires consécutives par commutateur à la sortie du dernier étage.liens entre étages 1/2 et 2/3 pour permettre connexité du réseau butterfly.donc, entre 1er et 2ième étages: liens directs et croisements haut/bas et bas/haut; entre 2ièmeet 3ième étages: liens directs et croisements haut/haut et bas/bas (haut: 2 premières rangées;bas: 2 dernières rangées).

Oui, même algorithme que pour réseau oméga avec le réseau produit en b.

R2.91 On a 2 étages de 2 commutateurs reliés shuffle-exchange.

Adresse binaire de départ = 01; adresse binaire de destination = 11.Donc sort par le bas sur les 2 commutateurs du chemin.1er étage: XCH ou UB; 2ième étage: STR ou LB.

3 étages de 2 commutateurs.Même algorithme pour les 2 derniers étages. évitement du commutateur brisé au 1ercommutateur.1er étage: UB ou STR; 2ième étage: LB ou STR; 3ième étage: XCH ou UB.

R2.92 A XOR B et si ième MSB bit = 0 alors état = DIRECT sinon (bit = 1) état = ÉCHANGE pour

M0P0

P7 M7

P1 M1

l=0 l=1 l=2 l=3



étage i.

1,2,4.

UB / LB,LB / UB,XCH,UB,UB

8! = 40320.

Non-bloquante si configurations non-conflictuelles des commutateurs i.e. chaquecommutateur est dans un état ÉCHANGE (XCH) ou DIRECT (STR); donc le nombre total est2^^12 = 4096.

4096/40320 = 10.16%

R2.93 16

Format (sorties entrée high - sorties entrée low): h-h, h-hl, hl-h, l-l, hl-l, l-hl, hl-hl

R2.94 Commutateur matriciel, multi-étages, pipeline (maille 1-D), anneau, étoile, hypercube, arbreélargi, etc.

R2.95

V

F

V

Un commutateur en faute dans l’étage d’entrée ou de sortie (ou tous les commutateurs d’unecolonne en faute, ou tous les commutateurs du réseau en faute, etc.).entrée: 2 sources sont inutilisables; sortie: 2 destinations sont inutilisables.

Chapitre 3 Systèmes temps réel et fiabilité

R3.1 Places: donne les éléments qui définissent l’état du réseau.

000001

010

011

100101

110

111

000001

010011

100

110

101

111



Transitions: donne les endroits où l’état du réseau peut changer.

Arcs (entrée et sortie): donne les conditions d’activation des transitions et l’effet de cetteactivation sur les places avant et après.

Marquage: donne l’état du réseau par le nombre de jetons dans chaque place.

R3.2

vrai. le producteur peut écrire indéfiniment même si le consommateur ne lit pas.

pour le consommateur: aucune donnée en trop, aucune donnée manquante, ordre préservé.

aucune donnée en trop: place A et transition b. ne peut lire de donnée non écrite.aucune donnée manquante: transitions a et c. toute donnée générée pourra être utilisée.ordre préservé: non modélisé par le réseau.

R3.3 Nombre max de mots supplémentaires = nombre de mots de 20 (prochain) à N=1 (dernierpossible) + nombre de mots de 0 (début) à 9 (dernier libre i.e. queue - 1). Max = ((N-1) - 20 + 1) + 10 = N - 10

R3.4 Celle du centre en haut car elle indique le nombre de valeurs dans le tampon ou celle du centreen bas car elle indique l’espace libre qui reste dans le tampon.

Impossible en tout temps car le total des deux places du centre est toujours N (une écritureajoute 1 au tampon et retire 1 de la place au-dessous; une lecture retire 1 au tampon et ajoute 1à la place au-dessous) et le nombre initial de valeurs dans le tampon est 0.

1. remplace N par 1 (R/W sans accès simultané à un tampon)2. remplace l’arc de gauche du producteur par un arc d’entrée allant de la sortie de transitionLecture vers la place du haut du producteur (communication bloquante en R et W). (transitionÉcriture devient: “demande” d’écriture).

R3.5 M/D/1 considère le temps de service déterministe (e.g. durée fixe) plutôt qu’aléatoire.

seule la variable N est aléatoire car elle dépend de la fonction aléatoire régissant l’arrivée desclients.

lecture

utilisation

génération

écriture

PRODUCTEUR CONSOMMATEUR

TAMPON

A

ba c



on veut que la probabilité que la file contienne 2 clients ou plus soit égale à 5%. TSM = sqrt(0.05/1^2) = 0.22 minutes = 13.4 secondes.

R3.6 et on a: msec. msec.Donc: et clients

R3.7 Temps d’attente=T= msec. donc si on soustrait msec, onobtient un temps moyen d’attente de 34 msec.

La borne sur le temps moyen entre deux interruptions pour msec: donc:

et msec.

R3.8 msec. msec. donc . Ainsi, donne x=0,076 soit 7,6%.

Le temps de réponse moyen est T= 10 / (1-0,909) = 110 msec.

R3.9 Débordement si N >= 4. P(N>=4) = (lambda/mu)4 <= 0,05. Donc 1/lambda >= (1/mu)/(0,05)1/4 = 42,29msec.

Débordement si N>=x. P(N>= x) = (lambda/mu)x <= 0,02. Donc x >= (ln 0,02)/(ln (20/30)) = 9,65 et donc débordement si N=10 interruptions dans lafile. Le tampon sera donc de dimension 8 (8 en attente et 1 en traitement sans débordement).

R3.10 Wait: prendre une baguette; signal: déposer une baguette.Chaque p(i) commence par vouloir manger; il prend la baguette de gauche (droite) dès qu’elleest libre et ensuite il prend la baguette de droite (gauche) dès qu’elle est libre. Il mange ensuitepour un temps fini puis redépose i.e. libère les baguettes dans le même ordre. Il pense pendantun temps fini puis recommence le cycle.

Impasse: tous les philosophes saisissent une baguette puis sont bloqués.Famine: tout p(i) détiendra une baguette éventuellement; si un p(i) est bloqué indéfiniment, ilfinira par bloquer son voisin du côté de la baguette qu’il détient et ainsi de suite jusqu’audernier; donc, une famine se transformera nécessairement en impasse à plus ou moins longterme.

Le cinquième philosophe p(4) saisit ses baguettes dans l’ordre inverse des autres i.e. wait(0)puis wait(4); ainsi il aura éventuellement 2 baguettes et il y aura toujours quelqu’un quimange et tous finiront toujours par manger.

R3.11 S1=1, S2=0, R=N

MV(R)P(S1) ;bloque l’accès au compteur

n ρ 1 ρ–( )⁄= ρ λ µ⁄= 1 µ⁄ 10= 1 λ⁄ 13=λ µ⁄ 0 77,= n 4=

1 µ⁄( ) 1 ρ–( )⁄ 44= 1 µ⁄ 10=

1 µ⁄ 10=λ µ⁄( )

6 0 05,≤

1 λ⁄ 1 µ 0 05,6( )⁄≥ 1 λ⁄ 17=

1 µ⁄ 10= 1 λ⁄ 11= ρ 10 11⁄ 0 909,= = 0 90927x≤,



R = R + 1 ;libère une ressourcesi (R <= 0) alors { ;un processus en attente d’une ressource?

;i.e. toutes les ressources étaient occupées etV(S2)} ;on permet à un processus en attente d’utiliser

;la nouvelle ressource libresinon {V(S1)} ;relâche le compteur

Il sera mis dans une file d’attente de la ressource

R3.12 Un jeton dans les deux places du haut et un autre dans la place du centre.(aussi, un dans une place du haut et l’autre dans la place du bas opposée)

Place du centre: 3 jetons et 3 branches de sortie et 3 branches d’entrée vers la droite.Place du haut à gauche: 3 jetons (ou répéter 3 branches de lecteurs à gauche avec un jeton enhaut chacune et 3 branches d’entrée et de sortie vers la gauche à partir de la place du centre).

R3.13 2: deux MP(S) suivis de deux MV(S)

S=nombre de ressources disponibles au total.

Oui: 2 peuvent faire un premier MP(S) avant qu’un des 2 ait fait un deuxième MP(S); ilsbloqueraient alors au 2ieme MP(S) tandis que le 3ieme bloquerait au 1er MP(S). Les 4conditions sont respectées par les 2 premiers processus. Le troisième est simplement bloquépar eux car l’impasse se produit avec un sous-ensemble des processus. On a: exclusionmutuelle (ressources utilisées par 1 à la fois), hold-and-wait (2 ont fait 1 MP(S) et attendent),attente circulaire (1->2->1), aucune préemption forcée (aucune limite dans le tempsd’attente).

Non: 2 peuvent faire les deux MP(S) à tour de rôle mais dès que le troisième atteindra sonpremier MP(S) il entrera dans la file d’attente et finira par saisir une première ressource puisune deuxième à moins qu’il y ait eu impasse.

Presque aucun changement: impasse toujours possible mais cette fois-ci les 3 processusrespectent les 4 conditions ensemble.

4: car si il y a un cycle avec les 2 premiers Pi, le troisième finira toujours par saisir une 1èreressource (comme dans le cas de 2 ressources) puis une deuxième car les impasses ne sont paspossibles, le nombre de ressources étant plus grand que le nombre de processus.prévention: aucune attente circulaire (ou hold and wait) car 1 ressource en plus.

1: réalisation matérielle du sémaphore serait différente: variable partagée accédée par bussystème donc verrouillage du bus, etc.2: pas de changement p/r aux impasses et famines.



R3.14 Si à un moment donné 3 processus utilisent chacun une ressource et que trois autres processusont effectué un MP(s) et attendent qu’une ressource se libère (ils sont suspendus), il pourra yavoir une impasse si un autre processus effectue MP(s) avant qu’une ressource se libère. Eneffet, s prendra alors la valeur -4 et ne pourra plus redevenir >=0, même si les trois ressourcesse libèrent. Lorsque tous les processus actifs auront demandé l’accès à une ressource, ilsseront tous bloqués, donc impasse.

Parce que les ressources occupées sont utilisées et qu’elles seront toutes libérées à un momentou un autre et pourront alors être utilisées par un autre ou par le même processus (pas d’attentecirculaire ni de hold and wait).

MP(s): while (s < 1) {;}; s=s-1; MV(s): s=s+1; init(s): s=N

Lorsqu’un processus est suspendu, il sera placé dans une file d’attente et chaque fois qu’uneressource se libérera, le premier processus de la file pourra s’exécuter à nouveau. Il faut doncinterpréter le test while comme un test vérifiant s’il y a une ressource libre ou non.

R3.15 2 processus utilisent une ressource commune. La partie de programme incluant l’accès à laressource est en exclusion mutuelle entre ces deux processus.

un processus qui est dans une section critique ne pourra être remplacé par un processus plusprioritaire voulant utiliser la même ressource. Il n’y a donc pas de préemption de la ressource.

faux: l’absence de préemption est une des 4 conditions nécessaires aux impasses.

R3.16 La ressource processeur est la seule qui permet la préemption. Toutes les autres ressources nepeuvent pas être libérées en cours d’utilisation par un processus.

R3.17 Faux. Ça dépend des critères utilisés pour définir le meilleur.

Faux. Ça concerne seulement la réalisabilité i.e. le respect des contraintes temporelles desprocessus.

Faux. Les processus peuvent apparaître et disparaître dynamiquement dans la file d’attente.

Vrai. Les calculs sont identiques et simples.

Vrai. Les processus ne sont plus indépendants et il y a des blocages en plus des suspensions,donc les temps de réponse sont plus grands et les échéances plus difficiles à respecter.

R3.18 Faux: famine plutôt. Impasse entre P2 et P4 mais P1, P3 et P5 ne sont pas bloqués.

R3.19 En se basant sur les différentes techniques d’optimisation exposées dans les notes, on devrait:

i) inclure les deux fonctions, taxe et imprime, à l’intérieur de la fonction “main” pour éviter lepassage de paramètres, la gestion de la pile et des variables locales,



ii) éliminer la variable “temp” qui est intermédiaire et inutile, iii) éliminer la variable morte (non-utilisée) “numéro” et iv) effectuer le calcul 0,075+0,015 et mettre “taux” comme une constante en dehors de lafonction “main”.

R3.20 Règle#1: TL = 2/15 + 4/15 + 2/10 + 1/5 = 4/5. L’ordonnancement serait réalisable avec les temps d’exécution moyens.Règle#2: TL = 5/10 + 3/10 = 11/10. Donc, cet ordonnancement n’est pas réalisable car l’ordonnancement des processus critiquesn’est pas réalisable avec les temps d’exécution maximums.

R3.21 Voir la figure dans les notes de cours.

R3.22 vrai: en plus, il y a une limite inférieure sur le délai entre deux arrivées.

vrai: on décide d’abord où vont les processus avant de déterminer quand ils vont s’exécuter.

faux: elle n’est même pas une stratégie à base temporelle.

R3.23 PPCM de 10, 15, 20, 25 = 300 u.t.

R3.24 3 processus p1 > p2 > p3. 1 ressource R1 commune à P1 et P3.P3 est lancé et saisit R1.P3 est suspendu dans sa section critique et P1 est lancé.P1 est bloqué en voulant saisir R1.P3 est relancé.P3 est suspendu et P2 est lancé.P2 s’exécute et bloque donc P1 même s’ils n’ont pas de ressource commune: inversion despriorités.

R1 a une priorité plafond égale à p1.P3 prend la priorité de P1 lorsque ce dernier veut saisir R1. P3 termine avec R1 puis reprend sa priorité p3. P1 s’exécute alors avec R1 et puis termine. P2 peut seulement s’exécuter après P1, conformément aux priorités statiques.

R3.25 Il s’agit d’écrire l’équation de contraintes sur la période PPCM et prendre la valeur maximalepour C2 qui la vérifie; vérifier ensuite pour les autres périodes au moyen d’un diagrammetemporel. Si ça ne fonctionne pas, diminuer C2 graduellement jusqu’à ce que toutes lescontraintes soient respectées.Sur 60 u.t: 2 C2 + 6 C3 + 3 C4 + C1 <= 60. Donc 2 C2 + 12 + 12 + 3 <= 60 et C2 <= 16.5.On peut vérifier que C2 = 16 satisfait toutes les contraintes (voir question b).

Processus (durée):3(2), 4(4), 2(4), 3(2), 2(8), 3(2), 4(4), 2(4), 3(2), 2(8), 3(2), 4(4), 2(4), 3(2), 2(4), 1(3), idle(1).



Sur 60 u.t, il faut enlever 6 u.t au total (10% de 60). Donc C2 <= 13.5 = 13 u.t et encore unefois les contraintes sont respectées.

Refaire le calcul sur 60 u.t en changeant C1. Donne C2 <= 15.5 = 15 u.t.

D’abord écrire les équations de contraintes sur 60, 20 et 10 u.t et prendre la contrainte la plussévère. Vérifier au moyen d’un diagramme. Diminuer les valeurs de C1 et C2 par essais eterreurs au besoin.Sur 60 u.t: 6 C2 + 6 C3 + 3 C4 + C1 <= 60.Sur 20 u.t: 2 C2 + C4 + 2 C3 <= 20.Sur 10 u.t: C2 + C3 <= 10.Donne C2=5 et C1=6 (ou C2=6 et C1=0).Diagramme sur 20 u.t (répété 3 fois): 2(5), 3(2), 4(3), 2(5), 3(2), 4(1), 1(2)

R3.26 PPCM = 60. Une condition suffisante est Somme (ci/Ti) <= n (21/n - 1) = 0.757 car n = 4.Sur 60 u.t, on obtient 4C1+2C2+12C3+3C4<= 0.757(60) soit 8+20+12+3C4<= 45.42Donc C4 <= 1.81 = 1 u.t.

TL max = 1.0 (ordonnancement non assuré) donne C4<= 6.67 = 6 u.t.

(8+20+12+18)/60 = 96.7%

Processus (durée):3(1), 1(2), 4(2), 3(1), 4(4), 3(1), 2(4), 3(1), 1(2), 2(2), 3(1), 4(4), 3(1), 4(2), 2(2) (reste 2 u.td’exécution au processus 2 arrivé à u.t. 30 donc échéance non respectée)...

Comme il manque 2 u.t au processus 2 sur 30 u.t, on est certain qu’en enlevant 2 u.t auprocessus 4 (à chaque 20 u.t), on pourra satisfaire toutes les échéances. Par contre, on peutvoir sur le diagramme qu’en enlevant seulement 1 u.t (C4 = 5 u.t) on réussit aussi à satisfaireles contraintes. C’est donc cette option qu’il faut retenir.

R3.27 c1 = 2 msec, c2 = 2 msec, c3 = 6 msec.

b1 = 4 msec, b2 = 1 msec, b3 = 0 msec.

P1: aucun P2: aucun P3: 1, 4, 6 et 8 msec.

P1: aucun P2: aucun P3: 2 et 5 msec.

R3.28 processus (durée, sémaphores saisis):4(2,A), 2(2,B), 4(1,A), 3(2), 1(1), 3(2), 4(1,A), 1(2,A), 2(2,AB), 1(1,B), 2(1), 4(1).

processus (durée, sémaphores saisis):4(2,A), 2(2,B), 4(2,A), 2(1,AB), 1(1), 2(1,AB), 1(2,A), 1(1,B), 2(1), 3(4), 4(1).

R3.29 Le temps de réponse R4 est élevé p/r à son temps de calcul. Il est bloqué longtemps à cause de



l’inversion des priorités. Si le temps de réponse R4 est trop grand, il risque de dépasser lacontrainte d’échéance.

Il limite à 1 le nombre de fois qu’il peut être bloqué par un processus de moindre priorité.

Voir les diagrammes dans les notes de cours.

En fait, il est bloqué une fois par le premier processus ce qui est normal car ce dernier utiliseun sémaphore de priorité plus grande (p4). La durée totale du blocage est de 3 ce qui est pluspetit que la longueur de la section critique de P1 (=4) ce qui est aussi normal. Le fait que leblocage soit coupé en deux provient du fait que P4 est plus prioritaire et n’a donc rien a voiravec les interdépendances et le protocole lui-même.

Non car on ne connaît pas leurs contraintes d’échéance (ou s’ils en ont une!). En fait, on nesait même pas si ils sont périodiques ni quelle est leur période. On ne sait pas quelle doit êtrela période d’ordonnancement à considérer (ex: PPCM). On ne peut pas évaluer le chargementtemporel ni vérifier si les temps de réponse sont acceptables.

R3.30 Le 1er processus qui entre dans la section critique devra en sortir avant que le 2e puisses’exécuter donc accéder à son tour a la section critique (le 1er arrivé a l’accès a la ressource etil bloque le second jusqu’a ce qu’il termine cet accès).

Non car le 2ième processus pourra s’exécuter même si le 1er est déjà en exécution et qu’ilsont la même priorité s’ils sont sur 2 processeurs différents.

R3.31

c1 = 2 msec, c2 = 2 msec, c3 = 6 msec

b1 = 4 msec, b2 = 1 msec, b3 = 0 msec.

P1: aucun P2: aucun P3: 1, 4, 6 et 8 msec

P1: aucun P2: aucun P3: 2 et 5 msec.

t

en exécution avec S2


bloqué

suspendu

en exécution

P3

P2

P1

t10t0 t1 t2 t3 t4 t5 t6 t7 t8 t9




Ti = Ri où Ri = bi + ci + temps suspendu ou bloqué (7, 9, 10 msec, respectivement).

non car TL > 1 même sans tenir compte du blocage.

non, car l’hypothèse que les durées des sections critiques correspondantes sont les mêmesn’est pas respectée, ni pour S2 (utilisée par P1 et P3) ni pour S3 (utilisée par P2 et P3).

R3.32 TL > 1stratégie RM: t=8 processus 3.

TL = 0.833 > Condition_Suffisante(n=2) = 0.828simulation RM: ordonnancement réalisable (période d’ordonnancement = PPCM = 6): 1 2 1 21 2 1

TL = 0.93 > CS(n=3) = 0.7798simulation RM: ordonnancement non réalisable: 1 2 2 3 3 1 3 2 2 (processus 3 rate sonéchéance à t=9)

Peut-être car stratégie dynamique fonctionne parfois même si RM ne fonctionne pas.

Même chose que ci-dessus.

simulation EDF: 1 2 2 3 3 3 3 1 2 2 1 3 3 3 3 1 2 2 3 3 1 2 2 3 3: aucune échéance ratée.Réalisable car instant critique à la première unité de temps (PPCM = 315).

R3.33 Pour chaque processus, il faut calculer à chaque instant le relâchement et donc le temps decalcul restant. On obtient le diagramme suivant sur 60 u.t. avec processus (durée): idle(5),1(10), 3(11), 2(2), 3(2), 2(2), 3(2), 2(6), 1(5), idle(15)

TL = 78.3% supérieur à n (2^^1/n - 1) = 77.98% donc non suffisant pour affirmer que c’estréalisable mais nécessaire pour affirmer que c’est peut-être réalisable.

PPCM (60,50,45) = 900

Temps de calcul total = 55 u.t. Il doit être réalisé dans l’intervalle [max di, min bi] i.e. [10, 60]soit sur une période de 50 u.t. ce qui est impossible.

R3.34 Ça dépend de: contraintes temporelles des processus, chargement temporel, vitesse du(des)CPU, nombre de capteurs/actuateurs/périphériques, complexité des traitements, fiabilité, etc.

Ça limite les communications inter-processus (moins de perte de temps) et ça simplifie p/r àl’utilisation des sémaphores pour partage des ressources et synchronisation.

Oui (ou non) mais c’est insuffisant car seul P2 est assuré de respecter ses contraintes



temporelles (si elles sont cohérentes entre elles).

TL = Sommation des ci/Ti > 1

Sommation des ni*ci = 90 > PPCM = 80.

Non, TL <= 1 est une condition nécessaire mais non suffisante.

PPCM= 80

R3.35 F

V

R3.36 Fiabilité: probabilité que le système soit opérationnel au temps t, étant donné qu’il estopérationnel au temps 0.Disponibilité: pourcentage de temps où le système est opérationnel sur une période donnée(tient compte du temps de réparation).

R3.37 elle est constante (fonction de probabilité uniforme). Ainsi, la probabilité de défaillance F(t)est une rampe positive (fonction linéaire croissante) entre 0 et le temps de mission.

R(t) = 1 - F(t) est une rampe négative allant de 1.0 à t=0 à 1 - 10^-9 à t = 10 heures.

Vrai. Une bonne disponibilité n’assure pas que le nombre de pannes est pratiquement nul. Eneffet, s’il y a des pannes et que le temps de réparation est très court, on pourra avoir une bonnedisponibilité instantanée, ce qui n’est pas suffisant pour un STR sévère et critique.

R3.38 La probabilité que le système tombe en panne augmente avec le temps.

MTBF = et donc MTBF = 5h.

1 - probabilité qu’il y ait une panne entre 0 et 7 heures (intégrale de la fonction de défaillance).On obtient soit 24,5%.

DS = MTBF/ (MTBF+MTTR) soit 5/(5+2)=0.714 donc 71,4%. 1/5 = 0,2 défaillances par heure

La probabilité de défaillance s’obtient en calculant l’intégrale de la fonction de défaillance dusystème.

à t=2 on a: donc 33,0%

1 λ⁄ λ 0 2,=

e7 5⁄–

0 247,=

eax

xd∫ eax

a⁄=

1e0 2t,( )–

0

2– 0 330,=



à t=10 on a: donc 86,5%

à t = infini, on a: donc 100%

La disponibilité du système avant la première panne est égale à la fiabilité du système. Cettedonc une fonction du temps t. Si on veut un résultat moyen, on utilise t=5h et on obtient alors0.368 soit 36.8%.

La fonction doit être une fonction de probabilité, donc son intégrale doit être égale à 1.

R3.39 La fiabilité est égale à 1 - F(t) où F(t) est la probabilité de défaillance au temps t soitl’intégrale entre 0 et t de la fonction de probabilité du temps de défaillance.MTBF = Ef(t=infini) où Ef est l’espérance mathématique de cette fonction de probabilité dutemps de défaillance.

R3.40 Minimum au point de rencontre commun des 2 fonctions: f(t0) = B.

Deux fonctions égales à f(t0) donc extrait t de la première expression ce qui donnet0= ln (A/B)/alpha.

Baignoire

Calcul de t0 pour ces valeurs donne: 6.9315, donc t=7 secondes tombe dans la 2ieme portion.La probabilité de défaillance F(t) à t=7 se calcule donc en faisant l’intégrale de la portion àgauche du minimum et en additionnant l’intégrale de la portion à droite du minimum jusqu’àt=7.La fiabilité R(t) = 1 = F(t).L’intégrale de la portion gauche donne (-A/alpha)e-alpha t évalué de 0 à t0 donc 0.4999.L’intégrale de la portion droite donne (B/beta ebeta t0)ebeta t évalué de t0 à 7 donc 0.00351.F(7) est donc égal à 0.503 et R(7) = 1 - F(t) = 0.497.

On veut que l’intégrale donne 1 entre tmin et tmax i.e. que la probabilité de défaillance soitégale à 1 à la fin de l’intervalle.Comme le temps ne peut être négatif, on choisit tmin = 0.tmax est obtenu en calculant l’intégrale en 2 portions comme ci-dessus pour avoirF(tmax)=1.0.On garde le même temps minimum entre les deux portions.En résolvant, on obtient tmax = 13.8629.

R3.41 Faux: la probabilité de défaillance est l’intégrale de la fonction (positive) qui augmente avec t.

R3.42 1ère expression: plus disponible (SA->1.0) si dénominateur petit i.e. MTTR faible et/ou

1e0 2t,( )–

0

10– 0 865,=

1e0 2t,( )–

0

∞

– 1=



MTBF élevé.

R3.43 1. complexité du système et de l’application (matériel et logiciel, capteurs, traitement,actuateurs) peut nuire à la fiabilité2. coût élevé du système et de l’application (vol interplanétaire)3. difficulté de réparation à distance et importance de la durée de vie

Les conditions d’opération ne sont pas déterministes (imprévus possibles dans le déroulementde l’application). De plus, la complexité du système le rend difficile à tester de façonexhaustive en essayant d’éviter i.e. éliminer toutes les fautes possibles.

Action. Vu de l’extérieur l’utilité du système est définie par ses actions.

La fonction de défaillance permet de calculer F(t) la probabilité de défaillance au temps t(intégrale sous la courbe de t=0 à t=t). La fiabilité instantanée R(t) = 1 - F(t).

Programmation N exemplaires (NVP) et blocs de reprise (RB).NVP est plus approprié parce que parallèle (statique) et ne cause donc pas de délaissupplémentaires.

1. acquisition des images, traitement (compression etc.) et transmission au taux vidéo (sévèrecar chaque image doit être compréhensible mais interruptions possibles dans le déroulement)2. réception des fichiers de tracé (sévère car on ne peut manquer de données)3. contrôle (asservissement) du déplacement du véhicule (sévère si veut suivre le tracé avecprécision).

R3.44 Plus faible car il faut multiplier les deux fiabilités (les deux modules doivent êtrefonctionnels).

R3.45 Tolérance car ces tests sont typiquement faits dans le système en opération (“on-line”) et nonavant de le lancer (“off-line”). L’évitement des fautes consiste à trouver les fautes avant delancer le système e.g. par un design rigoureux, le choix de modules fiables, les essaisexhaustifs, etc.

R3.46 Blocs de reprise: méthode séquentielle; programmation N-exemplaires: méthode parallèle.

Exécution du bloc; vérification de la validité du résultat; retour au début du bloc pourréexécution si non valide; après n essais, essai d’un nouveau bloc pour même traitement maisréalisé différemment.

R3.47 R(t) = 1 - F(t) = 1 - intégrale(lambda*exp(-lambda*t)) entre 0 et t = 1-(1-exp(-lambda*t) = exp(-lambda*t)

Allure d’une fonction de rodage: logiciel d’abord si matériel a été bien testé sinon les deux.

R(t) = P(OP(t)/OP(t=0)) donc R(0)=1 par définition i.e. que la probabilité que le système soit



opérationnel au temps 0 est égale à 1.0. Par contre, si lambda est très élevé alors R tend verszéro très rapidement ce qui peut indiquer des problèmes existants à la mise en marche. Il fautcependant additionner à la fonction de défaillance une fonction de vieillissement(exponentielle positive bornée à droite) pour tenir compte de la correction de ces erreursinitiales. Ceci donne une fonction de type “baignoire” qui est plus réaliste.

R12 = R1 + R2 - R1R2 = 2exp(-lambda*t) - exp(-2*lambda*t)

La redondance se fait par un mécanisme séquentiel, donc on risque de rater des échéances. Ilfaut changer pour un mécanisme de redondance parallèle. De plus, l’utilisation d’un système identique n’est pas idéale du point de vue des fauteslogicielles. Il faudrait un système de fonctionnalité identique mais avec deux logicielsdifférents pour que la redondance soit vraiment efficace.

R3.48 plusieurs versions du logiciel obtenues par une diversité de la conception (outils, personnes,etc.) à partir des mêmes spécifications.

Programmation N exemplaires (NVP) et blocs de reprise (RB).NVP est plus approprié parce que parallèle (statique) et ne cause donc pas de délaissupplémentaires.

Faux. Dans ces situations, un processeur est en faute mais il ne peut pas être identifié. Ilproduit des données qui sont arbitraires plutôt que de devenir silencieux (inaccessible,déconnecté). On ne peut donc pas reprendre le calcul avec le même processeur ou avec unautre processeur (mécanisme séquentiel RB) ni utiliser un autre résultat déjà calculé à la placede celui du processeur en faute (mécanisme parallèle NVP). Le mécanisme parallèle pourraitparfois être utile car la décision se base seulement sur une comparaison des résultats qui peutêtre plus complexe que la simple majorité. Il faudrait alors que les modules soient dans unestructure hiérarchique et que ce soit les esclaves qui contiennent des éléments redondants etpossiblement en faute.

R3.49 une faute dans le système ne se traduit pas par une mise hors service mais par uncomportement imprévisible de certains éléments. L’objectif est que le reste des élémentsrestent prévisibles.

Documents

Réponses aux questions des exercices - …wcours.gel.ulaval.ca/2016/h/GIF3003/default/5notes/notes/pdf_A10/... · temporelles et un fonctionnement en continu sur ... le système