Systemes-repartis

SYSTEMES REPARTIS CONCEPTS ET ALGORITHMIQUE Prof. Yahya SLIMANI Département des Sciences de l’Informatique Faculté des Sciences de Tunis Tél: 98537921 E-mail: [email protected]

1

Présentation du module

 Objectifs

 Introduire les systèmes répartis ou

distribués

 Concepts  Problématique  Développement d’applications réparties

 Prérequis  Architecture, OS, Programmation,

Réseaux Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

2

Introduction Générale 3

Introduction (1)

 Informatique classique  Centralisation

 Des moyens de calcul  Des moyens de stockage  Du contrôle  Du calcul  Des données

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

4

Introduction (2)

 Informatique parallèle  Motivations

 Calcul intensif 

Applications scientifiques

 Gestion de grandes masses de données

 Solution  Augmenter la puissance de calcul  Augmenter le nombre de processeurs Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

5

Introduction (3)

 Informatique répartie  Réalité

 Développement des réseaux  Intégration d’applications séparées  Pénétration de l’informatique dans tous

les domaines

 Solution  Répartition des ressources et du contrôle Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

6

Introduction (4)

 Informatique mobile  Motivations

 Utilisateurs nomades  Moyens de traitement légers  Informatique intégrée aux objets du

monde réel 

Mastère Informatique ISIG Kairouan

Téléphone, carte à puce, …

Yahya SLIMANI - FST Tunis

7

Introduction (5)

 Informatique pervasive  Motivations

 Accès à l’information  A tout moment  De n’importe où  Avec n’importe quel composant électronique

 Accès à des services au moyen de

différents médias  Informatique ubiquitaire, diffuse Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

8

Systèmes répartis (1)

 Présentation  Idée centrale  Répartition     

Mastère Informatique ISIG Kairouan

Des moyens de calcul Des moyens de stockage Des données Du calcul Du contrôle

Yahya SLIMANI - FST Tunis

9

Systèmes répartis (2)  Définition  Ensemble d’éléments reliés par un réseau  Eléments de calcul  Eléments de stockage  Equipements spécifiques 

Sondes, capteurs, satellites, etc.

 Fonctionnement collaboratif Participation à la réalisation de tâches communes  Collaboration grâce au réseau 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

10

Systèmes répartis (3)

 Exigences

 Fonctionnement continu  Tolérer la défaillance d’éléments  Fonctionnement dégradé

 Résister au réseau  Défaillances du système de

communication 

Mastère Informatique ISIG Kairouan

Perte de messages, déconnexion, … Yahya SLIMANI - FST Tunis

11

Systèmes répartis (3)  Flexible  Adaptation aux changements

 Passage à l’échelle (Scalability)  Dispersion géographique  Changements de taille Eléments  Utilisateurs  … 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

12

Systèmes répartis (4)  Non vulnérable  La répartition ne doit pas dégrader la

sécurité

 Fiabilité  Rendre des services conformes à leurs

spécifications

 Facile à utiliser  Cacher la répartition à l’utilisateur Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

13

Systèmes répartis (5)

 Problématiques

 Très nombreuses et très diverses  Absence d’état global du système  Forte dynamicité  Administration du système très

complexe  Influence du réseau sur le système 

Mastère Informatique ISIG Kairouan

Asynchronisme lié à la communication Yahya SLIMANI - FST Tunis

14

Schéma d’un système réparti Source : S. Krakowiak

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

15

Systèmes répartis (6)

 Problématiques de base

 Comment définir l’état d’un système  Existence d’états locaux uniquement

 Comment définir un calcul dans le cas

réparti

 Lancement  Suivi de l’exécution  Terminaison Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

16

Systèmes répartis (7)  Comment coordonner différents

calculs

 Absence de référentiel temporel

commun

 Comment partager des données  Absence de référentiel spatial commun

 Comment garantir la cohérence de

données réparties

 Cas d’une base de donnée répartie Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

17

Systèmes répartis (8)  Comment assurer le fonctionnement

continu du système

 Tolérer (accepter des défaillances)

 Comment développer et mettre au

point des applications réparties  Comment tolérer les aléas du réseau de communication

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

18

ORDONNANCEMENT DES EVENEMENTS Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

19

Ordonnancement (1)

 Problématique  Pourquoi ordonner

 Système = { Evénements }  Un événement nécessite une réaction  Que faire si plusieurs événements

arrivent en même temps Trouver un ordre pour les traiter  Décision dépend de cet ordre 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

20

Ordonnancement (2)  Nécessité de connaître l’état d’un

système

 Suivre l’évolution du système Ressources  Processus 

 Coordonner des processus  Définir des propriétés 

Mastère Informatique ISIG Kairouan

Système, processus, ressources, etc.

Yahya SLIMANI - FST Tunis

21

Ordonnancement (3)

 Cas centralisé

 Pas de complexité particulière  Possibilité de connaître l’état d’un

système à tout instant Interruption  Prendre une image du système 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

22

Ordonnancement (4)  Pourquoi  Existence de deux référentiels uniques  Mémoire commune 

Support de l’état du système

 Horloge commune 

Mastère Informatique ISIG Kairouan

Définit l’ordre des événements

Yahya SLIMANI - FST Tunis

23

Ordonnancement (5)

 Cas distribué  Plus complexe

 Pas de référentiels communs Temporel  Spatial 

 Communications asynchrones 

Mastère Informatique ISIG Kairouan

Temps de communication non borné

Yahya SLIMANI - FST Tunis

24

Ordonnancement (6)  Calcul asynchrone Différentes de vitesses entre sites  Temps non borné  Charges variables entre sites 

 Observation différente du même

événement

 Solution  Trouver un modèle temporel  Modèle asynchrone Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

25

Modèle asynchrone (1)

 Hypothèse de base  Asynchronisme

 Du calcul  Des communications

 Modèle

 Asynchrone  Imposer des contraintes (parfois fortes)  Fixer des bornes

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

26

Evénements (1)

 Types

 2 types d’événements  Locaux Internes à un processus  Ordonnés par l’horloge physique 

 Communication Emetteur (Send)  Récepteur (Receive) 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

27

Evénements (2)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

28

Evénements (3)

 Hypothèses sur les messages  Message

 Seul moyen de communication entre

processus distants

 Propriétés  Arrivée d’un message Garantie  Sans possibilité de borner le temps de transmission 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

29

Evénements (4)  Contenu 

Message non modifié

 Canal de communication  Lien entre deux processus  Peut avoir certaines propriétés FIFO  … 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

30

Evénements (5)  Instants  Réception 

Par le système de communication

 Délivrance 

Mastère Informatique ISIG Kairouan

Remis à son destinataire

Yahya SLIMANI - FST Tunis

31

Evénements (6)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

32

Evénements (7)

 Exécution locale  Suite d’événements

 Propre à chaque processus  Constitue son passé ou son historique  Suite ordonnée Horloge physique du site où se trouve le processus  P1: < e11, e12, …, e1n > 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

33

Evénements (8)

 Exécution globale

 Définir une suite à partir de deux suites

d’événements  Intérêt

Synchroniser deux processus  Trouver un ordre entre les événements des deux suites  Exemple: Accès à une ressource critique  Définir un ordre d’accès: Fin(P1) < Début(P2) ou Fin(P2) < Début(P1) 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

34

Evénements (9)

 Ordonnancement global  Problématique

 Comment définir la suite des événements

d’un système réparti 

Passage d’un ensemble de suites locales à une suite globale



Relation de précédence Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

35

Evénements (10)  Contrainte  Connaissances locales sur les

événements

 Solution  Définir un opérateur de précédence et lui

associer une sémantique  Utiliser le principe de causalité 

Mastère Informatique ISIG Kairouan

Cause précède toujours l’effet

Yahya SLIMANI - FST Tunis

36

Evénements (11)  3 niveaux de causalité Processus  Evénement local n’agit que sur les événements futurs  Entre processus  Communication  Emission précède toujours la réception  Composition  Relation transitive 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

37

Causalité (1)

 Définition

 Proposée par Lamport [78]  Principe  Evénement e précède causalement

l’événement e’  e → e’

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

38

Causalité (2)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

39

Causalité (3)

 Causalité potentielle  Propriété de la causalité

 Définit uniquement une causalité potentielle  On ne peut pas affirmer que e est la cause

effective de e’  Par contre e’ ne peut pas être la cause de e 

Affirmation par négation

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

40

Causalité (4)

 Indépendance causale  Définition

 ¬ (e → e’ ) et ¬ (e’ → e)  Aucun de ces événements ne peut

influencer l’autre Ils sont causalement indépendants  e || e’ 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

41

Causalité (5)

 Passé

 Notion rattachée à un événement  Passé(e) = { e* } | (e* → e)  {e}

 Intérêt  Indépendance causale Aucun événement ne fait partie du passé de l’autre  Aucun n’influence l’autre 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

42

Causalité (6)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

43

Causalité (7)

 Chaîne causale

 e0, ... ,en : ei-1 → ei,

Mastère Informatique ISIG Kairouan

i=1,...,n

Yahya SLIMANI - FST Tunis

44

Horloges logiques (1)

 Présentation

 Définies par Lamport  But  Dater des événements Assurer la condition de validité  Déterminée par une connaissance locale 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

45

Horloges logiques (2)

 Principe

 Horloge logique sur chaque site  Compteur (dater les événements)  Site i  Horloge Hi  Estampille

 Datation  Evénement e dans site i  Mastère Informatique ISIG Kairouan

H(e) = Hi Yahya SLIMANI - FST Tunis

46

Horloges logiques (3)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

47

Horloges logiques (4)

 Algorithmique  Initialisation

Hi = 0 pour tout i  Evénement e local (site i) 

 Hi = Hi + 1  Dater e avec Hi  Emission d’un message m Estampiller m  ( m , Hi(m) ) 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

48

Horloges logiques (5)  Réception d’un message 

Hj = max ( Hj , Hi ) + 1

 Dater l’événement de réception avec la valeur de

Hj  La date de l’émission peut influencer la date de

réception

 Intérêt

 Ordonner les événements d’un système

réparti

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

49

Horloges logiques (6)

 Condition de validité

 Ordonnancement par estampille  Condition suffisante de validité 

e → e’ ⇒ Hi(e) < Hj(e’)

 Propriété faible de la validité de l’horloge 

Mastère Informatique ISIG Kairouan

Implication dans un seul sens

Yahya SLIMANI - FST Tunis

50

Horloges logiques (7)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

51

Horloges logiques (8)

 Type d’ordre  Partiel

 L’ordre donné par les estampilles n’est pas

strict Deux événements peuvent avoir la même date  Ils sont causalement indépendants  Comment les ordonner ?  Ajouter un autre critère  Numéro de processus, Adresse MAC, … 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

52

Horloges logiques (9)  Ordre total  2 événements 

a sur Si et b sur Sj

 b ssi

 a 

Mastère Informatique ISIG Kairouan

(H(a) < H(b)) ou (H(a) = H(b) et i<j)

Yahya SLIMANI - FST Tunis

53

Horloges logiques (10)

 Limites des estampilles

 Définissent un ordre total  Mais, la relation de dépendance

causale est un ordre partiel  Eliminent artificiellement la dépendance causale  e → e’ : e → e’ ou e || e’  He = He’ , He< He’ , He> He’ Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

54

Horloges logiques (11)  Ne sont pas denses  Si H(e) < H(e’), on ne peut pas savoir s’il

existe un événement e’’ tel que : 

Mastère Informatique ISIG Kairouan

e → e’’    et e’’  → e ’  Problème insoluble  Est-ce qu’un événement va arriver ?  Si oui Quand ?

Yahya SLIMANI - FST Tunis

55

Horloges logiques (12)

 Effets de l’asynchronisme  Ambiguïté des horloges logiques  Exemple 4 processus P1, P2, P3 et P4  P2, P3 et P4 envoient des messages à P1  Contrainte  Délivrés dans l’ordre de leurs estampilles  Le message m2(3) a été délivré 

 Mastère Informatique ISIG Kairouan

Peut-on délivrer m4(8) ? Yahya SLIMANI - FST Tunis

56

Horloges logiques (13) Cas 1

Mastère Informatique ISIG Kairouan

Cas 2

Yahya SLIMANI - FST Tunis

Cas 3

57

Datation (1)

 Constat

 Horloges logiques  Satisfont la propriété de validité faible

 Problème  Comment caractériser la dépendance

causale ? 

Définir un système de datation tel que 

Mastère Informatique ISIG Kairouan

e → e’

⇔ Hi(e) < Hj(e’)

Yahya SLIMANI - FST Tunis

58

Datation (2)

 Idée

 Utiliser le passé ou l’historique d’un

événement  Passé

 Passé(e) = { e* | (e* → e)}  {e}  Passéi(e) = { e* } | (e* → e) ∧ e* ∈ pi  Passé(e) = Passéi(e) , {e}

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

59

Datation (3)  Connaître le passé reviendrait à

définir la dépendance causale

 e → e’ ≡ e ∈ Passé( e’ )  Comment représenter le passé Définir des Horloges Vectorielles  Estampillage d’un message avec l’historique à la place d’une simple valeur d’une horloge logique 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

60

Datation (4)

 Définition du passé  Passé d’un événement

 Evénement le plus récent  Le connaître c’est connaître le passé  Définit par un vecteur de n éléments

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

61

Datation (5)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

62

Horloges vectorielles (1)

 Présentation

 Proposées par Fidge et Mattern (88)  Principe  Un vecteur de taille n par site  Chaque site a une composante dans ce

vecteur  Date d’un événement 

Mastère Informatique ISIG Kairouan

Valeur du vecteur Yahya SLIMANI - FST Tunis

63

Horloges vectorielles (2)

 Algorithmique  Initialement

 Tous les vecteurs à 0 

Vi = (0,…,0)

 Evénement local (Site i)  Vi[i] = Vi[i]+1

 Envoi d’un message par site i  Estampillé par valeur courante de Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

64

Horloges vectorielles (3)  Réception d’un message (m,Vm)  Vi[i] = Vi[i]+1  Vi[i] = max(Vi[i],Vm[i]) pour j = 1..n, j ≠ i

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

65

Horloges vectorielles (4)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

66

Horloges vectorielles (5)

 Propriétés

 Relation d’ordre partiel  V ≤ V’ défini par ∀i : V[i] ≤ V’[i]  V < V’ défini par V ≠ V’ et V ≤ V’  V || V’ défini par ¬ (V ≤ V’) et ¬ (V’ ≤

V)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

67

Horloges vectorielles (6)  Densité  Soient ei ∈ Si et ej ∈ Sj.  Si Vk(ei) < Vk(ej), pour k≠ j, alors il existe ek

tel que ¬(ek → ei) et (ek → ej)

 Dépendance causale

 Lien entre les horloges vectorielles et

la dépendance causale

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

68

Horloges vectorielles (7)  ∀a,b : 

a → b ⇔ HVect (a) < HVect (b)



a || b ⇔ HVect (a) || HVect (b)

 Condition forte de validité

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

69

Horloges matricielles (1)  Présentation  Horloge dans chaque site  HMi = matrice nxn  Permet de dater un événement

 Signification  HMi(j,k) 

nombre de messages issus de pj vers pk dont pi a connaissance  envoi est causalement antérieur à l’instant présent

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

70

Horloges matricielles (2)

 Algorithmique  Evénement local

 HMi[i, i] = HMi[i, i] + 1

 Emission d’un message m  HMi[i, i] = HMi[i, i] + 1  HMi[i, j] = HMi[i, j] + 1  le message est estampillé par Em=HMi

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

71

Horloges matricielles (3)  Réception d’un message m  Contrôler la dépendance causale 

Ne délivrer m que si tous les messages qui lui sont antérieurs ont été délivrés

Mastère Informatique ISIG Kairouan



Em[j, i] = HMi[j, i] + 1 (ordre FIFO j → i)



∀ k ≠ i, j : Em[k, i] = HMi[k, i] (messages des autres sites)

Yahya SLIMANI - FST Tunis

72

Horloges matricielles (4)  Délivrer et mettre à jour les horloges 

HMi[i, i] = HMi[i, i] + 1



HMi[j, i] = HMi[j, i] + 1



∀ k ≠ i, j et ∀ l ≠ i : HMi[k, l] = max(HMi[k,l], Em[k,l]

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

73

Horloges matricielles (5)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

74

Observation (1)

 Présentation

 Observer un calcul réparti  Introduire un processus observateur  Reçoit des messages des autres

processus 

Informé des événements

 Observation Suite des événements reçus  Doit être compatible avec la relation de causalité 

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

75

Observation (2)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

76

Observation (3)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

77

Observation (4)

 Validité d’une observation  Principe

 Temps de transmission borné : d  Instant T  Délivrer, à l’instant T, tous les messages ayant

des estampilles < T – d dans l’ordre des estampilles

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

78

Observation (5)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

79

Coupure (1)

 Présentation  Notion d’état

 Système centralisé 

Etat global et instantané  Horloge commune  Mémoire commune

 Système réparti 

Mastère Informatique ISIG Kairouan

Notion d’état assez floue

Yahya SLIMANI - FST Tunis

80

Coupure (2)

 Définition

 Image « instantanée » de l’état  Ensemble d’événements  Permet de définir un passé et un futur

par rapport à la coupure  Pour chaque processus 

Capturer l’état après le dernier événement avant la coupure

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

81

Coupure (3)

 Cohérence

 Doit vérifier la causalité  (e’ ∈ C ∧ e → e’ ) ⇒ e ∈ C

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

82

Coupure (4)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

83

Coupure (5)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

84

Coupure (6)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

85

Coupure (7)

Mastère Informatique ISIG Kairouan

Yahya SLIMANI - FST Tunis

86