Ce qui suit est principalement d'intérêt historique. Nos machines ont évolué depuis l'époque où ces algorithmes ont été conçus, et il en va de même pour nos langages de programmation et nos pratiques. Tout de même, les intuitions derrière ces algorithmes nous instruisent quant à ce qui sous-tend, justement, nous outils plus contemporains.
Très tôt dans le développement d'algorithmes concurrents et parallèles, la question de la synchronisation s'est imposée. En effet, bien que l'on souhaite que nos algorithmes parallèles soient bel et bien parallèles, donc qu'ils procèdent de la manière la plus indépendante possible les uns des autres pour pouvoir faire plus de traitement dans un même intervalle de temps, il y a presque toujours des moments dans l'exécution des divers chemins parallèles d'un algorithme où ceux-ci doivent de synchroniser, même si ce n'est que pour communiquer entre eux.
Danms la littérature, ces algorithmes s'expriment en termes de processus concurrents, et sont destinés à du matériel spécialisé. Aujourd'hui, nos ordinateurs ont pratiquement tous plusieurs coeurs, et la métaphore privilégiée est plus souvent le thread que le processus, mais cela ne change pas le fond du problème exploré.
Ne confondez pas « section critique » au sens que prend ce terme dans la littérature et les outils de synchronisation spécifiques à certains systèmes d'exploitation qui portent ce nom. En termes contemporains, une section critique au sens entendu dans la littérature est une séquence d'opérations ne pouvant être accédée que par une seule unité d'exécution à la fois.
Les algorithmes de synchronisation ont en commun les objectifs suivants :
Certains des algorithmes classiques de synchronisation listés ici ne s'appliquent qu'à deux unités d'exécution à la fois; d'autres ne sont pas assujettis à cette contrainte. De même, certains des algorithmes proposés ici ne sont pas utilisables tels quels sur des ordinateurs contemporains, du moins pas sans que certains ajustements ne leur soient appliqués pour gérer des cas potentiels de réordonnancement des opérations, en particulier les écritures concurrentes sur des états partagés.
Nous illustrerons ces algorithmes par des exemples concrets.Chaque exemple est offert en version C++ 11 et est accompagné d'explications sommaires, faute d'avoir le temps de faire mieux, mais vous pouvez m'écrire si vous avez des questions et je vous répondrai avec plaisir. Chacun d'eux reposera sur une base commune qui, pour simplifier le propos, ne sera pas répétée d'un article à l'autre : Algos-Section-Critique-General.html que je vous invite à examiner d'abord.
Je vous propose donc :
