Chapter 1 Introduction
Le but de ce cours est de donner une idée de la programmation, algorithmique
et sémantique de systèmes parallèles et distribués; vaste tâche!
Pour y arriver, on utilise donc un biais, qui nous permettra d'aborder la plupart
des thèmes ultra-classiques du domaine. On va utiliser le système de ``threads''
de JAVA pour simuler des processus parallèles et distribués.
Les ``threads'' en tant que tel sont une première approche du parallélisme
qui peut même aller jusqu'au ``vrai parallélisme'' sur une machine
multi-processeurs. Pour avoir un panorama un peu plus complet du parallélisme
et de la distribution, il faut être capable de faire travailler plusieurs
machines (éventuellement très éloignées l'une de l'autre; penser à
internet) en même temps. On en fera une approche, soit par simulation par
des threads, soit par le mécanisme de sockets dans le chapitre 6, qui
arrivera plus tard...
Dans les sections 3.2.1 et 3.2.3, on présente d'abord intuitivement le modèle
de threads de JAVA (communication par mémoire partagée) et la façon
dont on peut créer et contrôler un minimum les threads utilisateurs.
On voit un peu plus en détail
à la section 3.2.2 le fonctionnement de la JVM
en présence de threads. On donne des éléments plus avancés de contrôle
des threads JAVA à la section 3.3, en particulier en ce qui concerne
le cycle de vie des threads, les groupes de processus, les priorités, et
l'ordonnancement.
Dans le chapitre suivant on s'intéresse au très classique et important problème
de l'accès concurrent aux variables partagées. En effet la machine JVM sous-jacente
n'est pas une P-RAM CRCW mais ressemble plus à une CREW! (voir Chapitre 1 de [Rob00]) Il faut donc faire très attention à verrouiller les accès, au moins
au moment de l'écriture comme on le verra à la section
4.1. Pour ce faire on utilisera essentiellement le mot clé
synchronized introduit à la section
4.2. On en profitera pour voir un peu de sémantique très minimaliste
dans la section
4.4.2. En effet le premier problème que l'on rencontre, et que l'on
ne voit pas dans le monde séquentiel, est le problème de point mort ou
étreinte fatale, ou encore deadlock en anglais. On commence à le rencontrer
en section 4.4.2 mais ce sera toujours un thème récurrent.
A partir de synchronized on peut implémenter les mécanismes de synchronisation
et d'exclusion mutuelle typiques que l'on rencontre sous une forme ou une autre
dans tout langage parallèle. On commence par les moniteurs [Hoa74], section
4.3, puis les sémaphores binaires [Dij68], section
4.4.1 et les sémaphores plus généraux, dits à compteur,
section 4.4.5,
qui sont d'ailleurs implémentables à partir des sémaphores binaires
[Dij68]. En fait, synchronized n'est jamais qu'un sémaphore
binaire (ou verrou, ou mutex) associé à une méthode ou à un bout de code.
On en profite aussi dans la section 4.5
pour donner une implémentation des barrières de synchronisation,
très utilisées dans des programmes parallèles à gros grain, par exemple
fonctionnant sur cluster de PC.
Quand on ne veut pas mettre des barrières de synchronisation partout, mais
que l'on veut ordonnancer ces processus plus mollement (on peut alors gagner
en efficacité car l'ordonnancement a plus de degrés de liberté)
de façon à ce que l'état global
du système reste ``cohérent'' en un certain sens, on tombe sur les problèmes
classique de séquentialisation. On en donne quelques exemples, très classiques
en bases de données distribuées, et on développe
le protocole le plus connu permettant d'assurer cette cohérence dans ce cadre,
le protocole 2PL (``2-Phase Locking'') ou protocole à deux phases, en section
4.6. On se reportera au cours de S. Abiteboul, [Abi00],
pour
plus de détails et de références.
On voit que l'on se rapproche de plus en plus de la distribution.
C'est bien le but et on trouve dans le chapitre 6.
une façon de simuler le passage de messages entre processus
par la mémoire partagée de JAVA. Dans la section suivante
on dit un mot de la façon de programmer sur réseau
de stations UNIX, par les sockets. Cela reste très bref car c'est traité
dans le cours de F. Bourdoncle [Bou00].
Ensuite on fait quelques classiques de la programmation distribuée,
exclusion mutuelle, élection, estampillage, dans le chapitre 6
Entre temps, on en aura profité
au le chapitre 5 pour voir les grands classiques des algorithmes
permettant de programmer l'exclusion mutuelle (le synchronized) sur
des machines à mémoire partagée et sous certaines hypothèses. Cela peut
paraître assez académique mais est un excellent moyen de s'habituer à
raisonner sur des programmes parallèles se coordonnant par lecture écriture
en mémoire partagée, et ce n'est pas si facile! Cela nous permet également
d'introduire à la preuve de programmes.
La dernière section
est consacrée au problème de la programmation distribuée
en présence de pannes (crash) d'une on plusieurs machines. On se contente
de traiter du cas très classique du consensus en présence d'une panne
dans un système à mémoire partagée (avec lecture et écritures atomiques).
C'est également un domaine considérable, que l'on ne fait qu'aborder et
on recommande au lecteur de se plonger dans la lecture de [Lyn96] pour
avoir quelques compléments.
Références
Pour des compléments, ou des applications du parallélisme au calcul scientifique,
on pourra se reporter à [GNS00].
Ces notes très préliminaires sont un complément du cours de Yves Robert
[Rob00] qui montre l'algorithmique et la complexité
moins proches de la machine. On se reportera aussi au
complément de D. Rémy [Rem00]
pour tout ce qui concerne l'orienté objet. Le livre
[Ray97] apportera au lecteur toutes les précisions voulues sur les
algorithmes vus au chapitre 5.Enfin, je remercie Matthieu Martel d'avoir
relu cette première version de polycopié. Les erreurs qui restent (nombreuses!)
sont néanmoins les miennes!