:tocdepth: 2 ========================= Programmation parallèle ========================= .. include:: common.rst.inc 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 `:doc:, `IPC `:doc:), * 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. .. index:: thread see: fil d'exécution; thread see: processus léger; thread 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_threads: Exemple ------- .. code-block:: c 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); } .. index:: single: thread; noyau single: thread; utilisateur single: thread; green thread 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 `:doc:, * imposant des solutions de verouillages également pénalisant en temps. .. index:: fibre, coroutine 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. Exemple générateur `````````````````` .. code-block:: python 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) .. nextslide:: .. code-block:: python 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) .. nextslide:: .. code-block:: python 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 ``````````````` .. code-block:: python 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. Conclusion ========== En résumé --------- * Il existe de multiples façon de programmer des tâches parallèles. * processus lourds → couplage faible * processus légers (thread noyau) → couplage fort, parallélisme réel * coroutines / threads utilisateurs → ordonnancement personnalisé