97-these-dumoulin

Sujets

• informatique
• réseau
• réseaux

Informations

• Publié par: Ormo
• Nombre de lectures: 53
• Langue: Français

Extrait

Numéro d’ordre: 1924 Année : 1997
Laboratoire d’Informatique
Fondamentale de LilleLLIF
THESE
présentée à
L’UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE
pour obtenir le titre de
DOCTEUR EN INFORMATIQUE
par
Cedric Dumoulin
Dream : Une mémoire partagée répartie à cohérence
programmable
Thèse soutenue le 9 janvier 1997, devant la commission d’examen :
Président: J.L. DEKEYSER LIFL
Rapporteurs: H. GUYENNET LIB
G. LIBERT PIP
Examinateurs:
I. DEMEURE ENST
J-M. GEIB LIFL LIFL USTL
J-F. MEHAUT LIFL
J-F. ROOS LIFL
UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE
U.F.R. d’I.E.E.A. Bât M3. 59655 Villeneuve d’Ascq CEDEX
Tél. [phone] Fax. [phone]Table des Matières
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Les systèmes distribués . . . . . . . . . . . . . . . . . 11
Programmation des systèmes distribués. . . . . 11
Les mémoires partagées réparties . . . . . . . . . 12
Dream. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Cadre de travail . . . . . . . . . . . . . . . . . . . . . . . 13
Plan de la thèse. . . . . . . . . . . . . . . . . . . . . . . . 14
Chapitre 1
Programmation des Systèmes Distribués. . . . . . . . . . . . 15
1.1 Introduction aux systèmes distribués. . . . . . . . . . . . . . . 16
1.1.1 Qu’est ce qu’un système distribué?. . . . . . . . . . 16
Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Aspect matériel. . . . . . . . . . . . . . . . . . . . . . . . 16
Aspect logiciel . . . . . . . . . . . . . . . . . . . . . . . . 18
1.1.2 Services de base des systèmes distribués . . . . . 19
Exécution des processus. . . . . . . . . . . . . . . . . 20
Communication inter-processus. . . . . . . . . . . 20
Synchronisation . . . . . . . . . . . . . . . . . . . . . . . 21
1.1.3 Environnement d’exécution. . . . . . . . . . . . . . . . 22
Ramasse-miettes. . . . . . . . . . . . . . . . . . . . . . . 22
Mise au point des programmes. . . . . . . . . . . . 23
1.2 Modèles de programmation . . . . . . . . . . . . . . . . . . . . . . 23
1.2.1 Processus communicants. . . . . . . . . . . . . . . . . . 23
Création, répartition et contrôle des processus 24
Implémentations. . . . . . . . . . . . . . . . . . . . . . . 25
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.2.2 Remote Procedure Call (RPC). . . . . . . . . . . . . . 27
Implémentation. . . . . . . . . . . . . . . . . . . . . . . . 27
Conclusion 27
1.2.3 Mémoire partagée répartie. . . . . . . . . . . . . . . . . 28
Implémentation 28
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Chapitre 2
- 1 -
21/1/97Table des Matières
Classification et modélisation des DSM. . . . . . . . . . . . . 31
2.1 Partage matériel ou partage logiciel. . . . . . . . . . . . . . . . 31
2.1.1 Mémoire partagée, partage matériel (Hardware) 32
2.1.2 Mémoire partagée répartie (DSM), partage logiciel 32
2.1.3 Solutions hybrides . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Granularité du partage . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Pages, approche système . . . . . . . . . . . . . . . . . . 34
Problème du faux partage. . . . . . . . . . . . . . . . 34
2.2.2 Objets, approche programmation . . . . . . . . . . . 35
2.3 Modèles et protocoles de cohérences. . . . . . . . . . . . . . . 35
2.3.1 Modèles sans synchronisation . . . . . . . . . . . . . . 37
Cohérence séquentielle (Sequential Consistency) 37
Cohérence causale (Causal consistency) . . . . 38
Cohérence PRAM (PRAM Consistency). . . . 39
2.3.2 Modèles avec synchronisation. . . . . . . . . . . . . . 40
Cohérence faible (Weak Consistency) . . . . . . 41
Cohérence relâchée (Release Consistency) . . 42
Cohérence par entrée (Entry Consistency). . . 43
2.3.3 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4 Interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4.1 Déclaration et identification des objets partagés 44
2.4.2 Création du partage . . . . . . . . . . . . . . . . . . . . . . 46
2.4.3 Choix de la cohérence ou du protocole . . . . . . . 47
2.4.4 Accès aux objets partagés . . . . . . . . . . . . . . . . . 47
Accès par copie . . . . . . . . . . . . . . . . . . . . . . . 47
Accès dans une section critique . . . . . . . . . . . 48
2.4.5 Adresse d’un objet partagé . . . . . . . . . . . . . . . . 49
2.4.6 Des exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Crl. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Phosphorus 51
Orca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5 Synchronisation inter-processus . . . . . . . . . . . . . . . . . . 53
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Chapitre 3
Le modèle DREAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1 Objets, régions et caches . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1.1 Objets partagés . . . . . . . . . . . . . . . . . . . . . . . . . 58
Objet partagé constant . . . . . . . . . . . . . . . . . . 59
Objet partagé faiblement variable . . . . . . . . . 60
Objet partagé fortement variable . . . . . . . . . . 61
3.1.2 Régions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Régions et objets partagés . . . . . . . . . . . . . . . 62
- 2 -Table des Matières
Propriétaire unique . . . . . . . . . . . . . . . . . . . . . 63
Régions miroirs . . . . . . . . . . . . . . . . . . . . . . . 64
Régions et espace virtuel partagé (Dsm) . . . . 64
3.1.3 Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2 Cohérence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2.1 Caractéristiques de la cohérence faible . . . . . . . 66
3.2.2 Mise à jour automatique . . . . . . . . . . . . . . . . . . 67
Intervalle de mise à jour. . . . . . . . . . . . . . . . . 67
Intervalle de mise à jour et cohérence . . . . . . 68
Degré instantané de cohérence. . . . . . . . . . . . 68
3.2.3 Programmation de la cohérence . . . . . . . . . . . . 69
Mise à jour explicite. . . . . . . . . . . . . . . . . . . . 69
Gel d’une région. . . . . . . . . . . . . . . . . . . . . . . 70
Inhibition de la mise à jour automatique . . . . 72
Propagation de l’état modifié . . . . . . . . . . . . . 72
3.3 Interface d’accès à la mémoire partagée . . . . . . . . . . . . 73
3.3.1 Initialisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Structure d’une application . . . . . . . . . . . . . . 74
Identification d’une région. . . . . . . . . . . . . . . 74
Déclaration d’un objet partagé . . . . . . . . . . . . 75
Création du partage . . . . . . . . . . . . . . . . . . . . 75
3.3.2 Utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Adresse d’une région . . . . . . . . . . . . . . . . . . . 77
Recherche d’une région . . . . . . . . . . . . . . . . . 77
Accès à un objet partagé. . . . . . . . . . . . . . . . . 78
Récupération des erreurs d’accès . . . . . . . . . . 79
Plusieurs objets dans une région . . . . . . . . . . 79
Plusieurs régions pour un objet . . . . . . . . . . . 80
Attributs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.3.3 Terminaison. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Destruction . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Détachement. . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.4 Synchronisation inter-processus . . . . . . . . . . . . . . . . . . 83
3.4.1 Propriétaire d’une région. . . . . . . . . . . . . . . . . . 84
Changement . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Section critique. . . . . . . . . . . . . . . . . . . . . . . . 85
Notification de changement . . . . . . . . . . . . . . 86
3.4.2 Synchronisation d’une région . . . . . . . . . . . . . . 86
Attente d’une mise à jour . . . . . . . . . . . . . . . . 87
Notification de mise à jour. . . . . . . . . . . . . . . 87
3.4.3 Synchronisation par messages. . . . . . . . . . . . . . 88
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Structuration de l’espace partagé . . . . . . . . . . 88
modèle de cohérence . . . . . . . . . . . . . . . . . . . 89
Interface de programmation . . . . . .