Programmation parallèle¶
Motivation¶
Motivation¶
Certaines applications peuvent avoir besoin d’effectuer plusieurs traitements en parallèle. Elles peuvent être constituées de plusieurs processus, bénéficiant ainsi:
- de l’ordonnancement du SE (multi-cœurs),
- de l’arbitrage des ressources par le SE.
Mais cette solution présente aussi des inconvénients :
- obligation de passer par le SE pour communiquer (entrées-sorties, IPC),
- surcoût en temps lié aux IPC et à l’ordonnancement (commutation de contexte).
Remarque¶
- Les inconvénients identifiés viennent du fait que les processus séparés sont la norme, et que la communication inter-processus est l”exception.
- Solution satisfaisante lorsque les tâches de l’application ont un couplage faible : les besoins d’arbitrage sont plus important que les besoins de communication.
- Lorsque les tâches de l’application ont un couplage fort, il devient nécessaire de séparer:
- la possibilité d’exécuter des programmes en parallèle,
- la possibilité d’isoler les exécution les unes des autres.
Thread¶
Définition¶
Un thread (ou fil d’exécution) est l’exécution d’une procédure/fonction en parallèle de la fonction principale d’un processus
Un processus comporte un ou plusieurs threads.
Le PCB du processus contient pour chaque thread:
- un état
- un contexte processeur
En revanche, toutes les autres ressources (mémoire, fichiers, etc…) sont partagées par tous les threads du processus;
→ c’est au programmeur de les arbitrer
Processus léger¶
Les threads sont souvent appelés « processus légers ».
Ils bénéficient des mêmes avantages en terme de parallélisme, que les processus (l’ordonnanceur considère chaque thread individuellement).
Avantages par rapport aux processus :
- la commutation de contexte est plus rapide (même PCB),
- la communication entre eux est plus rapide (pas besoin d’appel système).
Exemple¶
void process_partial(section_t* sec) {
// traite la section du tableau spécifiée par sec
// ...
}
void process_all(int *tab) {
pthread_t t;
// traite la 1e moitié dans un thread séparé t
pthread_create(&t, NULL, process_partial,
section(tab, 0, SIZE/2));
// traite la 2e moitié dans ce thread
process_partial(section(tab, SIZE/2, SIZE));
// attend la fin du thread t
pthread_join(t, NULL);
}
Green thread¶
Dans certains contextes, les threads ne sont pas gérés par le noyau, mais émulés par un programme (par exemple la VM Java),
- qui s’exécute en mode utilisateur (d’où l’appellation thread utilisateur, qu’on oppose aux threads noyaux) ;
- et économise le temps de passer par le noyau (d’où l’appellation green thread).
Avantages et inconvénients¶
- En contexte mono-cœur, cette économie faire gagner des performances (pas de passage par le mode noyau).
- L’ordonnanceur ne « voit » qu’un seul thread, et donc :
- le cas échéant, on perd le bénéfice d’avoir plusieurs cœurs de calcul ;
- tout appel système bloquant bloque tous les threads utilisateurs du même thread (mais ceci est en général géré par la VM).
Note
Concernant les appels systèmes bloquants, les bibliothèques et les VM qui implémentent les threads utilisateurs fournissent des fonctions à utiliser à leur place.
Ces fonctions sont pseudo-bloquantes, dans le sens ou elles « bloquent » le thread seul (pour leur ordonnanceur interne), mais utilisent en interne un appel non bloquant.
Coroutine¶
Motivation¶
La commutation préemptive entre les threads pose certains problèmes :
- coûteuse en temps (surtout lorsqu’elle est gérée par le noyau),
- pose de nombreux problèmes de synchronisation,
- imposant des solutions de verouillages également pénalisant en temps.
Coroutine¶
Des coroutines sont des fonctions qui ont vocation
- à s’exécuter de manière séquentielle (i.e. sans parallélisme), mais entrelacée ;
- à être ordonnancées de manière coopérative et non préemptive.
Disponibles dans de nombreux langages :
- bibliothèques en C, C++, Java…
- intégrées dans certains langages (Python, Ruby…),
- gérées par certaines systèmes d’exploitation (on parle alors de fibre).
Remarques¶
- Il est toujours possible d’écrire les co-routines sous forme d’une seule fonction, mais le programme gagne en lisibilité / maintenabilité si on peut expliciter la séparation entre les différentes tâches.
- L’ordonnancement peut être fait de manière plus ou moins explicite,
par exemple :
- sous Windows, on spécifie la fibre à qui on passe la main
(
SwitchToFiber) ; - dans les générateurs python, on rend explicitement la main à l’appelant,
quel qu’il soit (
yield) ; - dans certains frameworks, les primitives d’entrée-sortie entrainent automatiquement un changement de coroutine.
- sous Windows, on spécifie la fibre à qui on passe la main
(
Exemple générateur¶
def chaine_de_traitement():
for i in range(10):
obj = produit(i)
if obj.val == 0:
continue
elif obj.val == 2:
consomme(obj[0])
consomme(obj[1])
else:
consome(obj)
def producteur():
for i in range(10):
yield produit(i)
def transformateur():
for obj in producteur():
if obj.val == 0:
continue
elif obj.val == 2:
yield obj[0]
yield obj[1]
else:
yield obj
def consommateur():
for obj in transformateur():
consomme(obj)
def producteur():
for i in range(10):
yield produit(i)
def transformateur():
for obj in producteur():
if obj.val == 0:
continue
elif obj.val == 2:
yield obj[0]
yield obj[1]
else:
yield obj
def consommateur():
for obj in transformateur():
consomme(obj)
Exemple serveur¶
def handle_request(req):
rep1 = calcule_debut_reponse(req)
req.send(rep1) # rend la main
rep2 = calcule_fin_reponse(req, rep1)
impacte_donnees_locales(rep1, rep2)
req.send(rep2) # rend la main
Note
À l’avant-dernière ligne, on note qu’on modifie les données locales au serveur ; avec des threads, cette procédure comporterait des sections critiques, et devrait donc avoir recours à des mutex.
Avec des co-routines :
- en mono-thread, il n’y a même pas besoin de mutex, puisque la préemption n’a lieu qu’aux moments des entrées / sorties, donc l’atomicité de la procédure est garantie ;
- même si on utilise du multi-thread (sur une architecture multi-cœurs), on devra mettre des mutex, mais les situations ou ils seront bloquants seront beaucoup plus rares.