Il y a eu beaucoup de recherches sur les algorithmes d'exclusion mutuelle - par exemple, beaucoup d'entre eux sont présentés dans des manuels classiques tels que The Art of Multiprocessor Programming , où un chapitre entier leur est consacré.
Je me demande quelles sont les situations pratiques où l'on pourrait avoir besoin de ces algorithmes lors de l'ingénierie d'un système simultané, plutôt que d'utiliser des primitives de synchronisation fournies par le langage et le système d'exploitation (par exemple, fournies par la bibliothèque pthread)?
Je peux penser à de nombreux cas particuliers où j'imagine que les primitives standard ne sont pas spécifiquement adaptées à eux, par exemple "un lecteur fréquent et un écrivain peu fréquent", ou vice versa, ou "exactement une opération d'écriture, de nombreux lecteurs", etc. - l'un des algorithmes d'exclusion mutuelle des manuels est-il significativement meilleur en pratique dans de telles situations?
Pour résumer: quels algorithmes d'exclusion mutuelle présentent un intérêt pratique pour un ingénieur qui a déjà à sa disposition une bibliothèque de primitives d'accès simultanées, fournie par le langage?
Réponses:
Réponse: aucun. Ce n'est pas le sujet de ces sections de Herlihy et Shavit's The Art of Multiprocessor Programming. Dans les chapitres sur l'exclusion mutuelle, Herlihy et Shavit ne vous proposent pas d'alternatives à la
pthreadbibliothèque, ils vous montrent comment implémenter l'équivalent de lapthreadbibliothèque.Le chapitre 2 de Herlihy et Shavit est intitulé «Exclusion mutuelle». Il donne une variété d'algorithmes classiques pour implémenter l'équivalent de
pthread_mutex_lock()avec uniquement une mémoire partagée séquentiellement cohérente. Mes réponses https://cs.stackexchange.com/a/12632/7459 et https://cs.stackexchange.com/a/30249/7459 discutent de l'importance de ces implémentations et ont un pointeur vers celui qui est pratique pour utiliser sur des machines qui n'ont pas d'opérations de synchronisation matérielle intégrées. (Article de Lamport de 1987 dans ACM Trans. On Computer Systems).Le chapitre 7 de Herlihy et Shavit donne une variété d'implémentations de verrouillage de rotation et de file d'attente de l'équivalent de
pthread_mutex_lock(), et le chapitre 8 se développe pour discuter despthread_cond_t(variables de condition),pthread_rwlock_t(verrous du lecteur / écrivain), et aborde brièvementsemaphores. Il peut y avoir des situations quipthread_rwlock_tpourraient être utilisées comme alternative àpthread_lock_tpour des raisons de performances (mais généralement pas) et dans Posix vous devez utilisersemaphorespour la synchronisation inter-processus.Les chapitres 9 à 16 traitent principalement des applications (différents types de conteneurs simultanés). Le chapitre 17 discute brièvement l'équivalent de
pthread_barrier_t.Cela dit, Herlihy et Shavit sont deux des partisans les plus actifs de la mémoire transactionnelle et d'une variété de types de synchronisation non bloquante (et sans attente). Ces techniques sont conçues comme des alternatives à l'exclusion mutuelle dans certains cas. Herlihy et Shavit saupoudrent diverses implémentations non bloquantes dans les chapitres 9 à 16, puis détaillent la mémoire transactionnelle au chapitre 18.
La mémoire transactionnelle et d'autres techniques de synchronisation non bloquantes sont destinées à résoudre le problème que certains algorithmes mal conçus nécessitent que les threads maintiennent leurs sections critiques pendant très longtemps. La mémoire transactionnelle et la synchronisation véritablement non bloquante ne sont actuellement pas des alternatives pratiques dans une situation réelle, mais les techniques de transformation des structures de données bloquantes en structures de données non bloquantes sont utiles dans la pratique pour minimiser la durée pendant laquelle une structure de données bloquante reste dans son état critique. section. (Souvent, vous pouvez réduire la taille de la section critique à quelques instructions de la machine.)
la source