David Rodríguez - dribeas a écrit dans un commentaire sur StackOverflow que "toutes les collections ne peuvent pas être implémentées sans verrous". Je ne suis pas sûr que ce soit vrai, et je ne trouve aucune preuve de toute façon.
Cette déclaration n'est pas très précise, mais permettez-moi d'essayer de la reformuler de manière légèrement plus formelle: pour chaque type de collection C, il existe un type de collection sans verrou CLF qui offre le même ensemble d'opérations, et où chaque opération sur CLF a la même complexité big-O que l'opération correspondante C.
Au fait, je ne m'attends pas à une transformation.
LOCKinstructions du CPU mais le planificateur de threads, via mutexes / semaphores / etc.Réponses:
Comme j'étais moi-même quelque peu confus, je commence par clarifier quelques concepts de la question.
Collection . Je ne vois aucune raison de passer du temps à définir rigoureusement ce que signifie «collecte» alors que nous pouvons simplement demander ce qui se passe pour les structures de données en général. Une structure de données occupe un morceau de mémoire et comporte certaines opérations qui peuvent accéder à cette mémoire et qui peuvent être invoquées par les utilisateurs . Ces utilisateurs peuvent être des processeurs distincts ou simplement des threads différents, cela ne nous concerne pas. Tout ce qui compte, c'est qu'ils puissent exécuter des opérations en parallèle.
Sans verrou . Herlihy et Boss affirment qu'une structure de données est sans verrouillage lorsqu'un utilisateur en panne n'empêche pas d'autres utilisations de la structure de données. Par exemple, imaginez que l'on verse de l'eau sur un processeur qui est en train d'insérer un nœud dans un ensemble trié. Eh bien, si d'autres processeurs tentent plus tard de s'insérer dans cet ensemble trié, ils devraient réussir. ( Modifier: selon cette définition, il est vrai que si une structure de données utilise des verrous, elle n'est pas sans verrouillage, mais il n'est pas vrai que si une structure de données n'utilise pas de verrous, elle est sans verrouillage.)
Avec ces définitions, je pense que Herlihy et Boss disent essentiellement que la réponse est de transformer les régions critiques en transactions.
Mais, demandez-vous, cela a-t-il la même complexité? Je ne suis pas sûr que la question ait un sens. Considérez
push(x) { lock(); stack[size++] = x; unlock(); }. S'agit-il d'une opération à temps constant? Si vous ignorez l'opération de verrouillage et donc les autres utilisateurs, vous pouvez répondre OUI. Si vous ne souhaitez pas ignorer les autres utilisateurs, il n'y a vraiment aucun moyen de dire si le push s'exécutera en temps constant. Si vous montez d'un niveau et voyez comment la pile est utilisée par un algorithme particulier, vous pourrez peut-être dire que la poussée prendra toujours un temps constant (mesuré maintenant en termes de tout ce qui se trouve être l'entrée de votre algorithme parallèle). Mais c'est vraiment une propriété de votre algorithme, il n'est donc pas logique de dire que la poussée est une opération à temps constant.En résumé, si vous ignorez combien un utilisateur exécutant une opération attend d'autres utilisateurs, l'utilisation de transactions au lieu de régions critiques répond à votre question par l'affirmative. Si vous n'ignorez pas le temps d'attente, vous devez regarder comment la structure de données est utilisée.
la source
pushopération comme indiqué ci-dessus n'est pas une opération à temps constant. Pour un nombre fixe de processeurs, et une implémentation communelockqui ne garantit pas de famine, l'opération ci-dessus (dans le pire des cas, pour un processeur donné prend N_proc * O (1), qui peut naïvement être supposé être O (1) ( nombre de processeurs pris en compte dans la constante cachée.)Je pense que "COLLECTIONS" signifie "files d'attente, piles, listes liées, arbres, ..."
Sur http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
Grâce à une conception et une implémentation minutieuses, il est possible de créer des structures de données qui peuvent être utilisées simultanément sans avoir à gérer les verrous ou les threads de bloc. Ces structures de données non bloquantes peuvent augmenter les performances en permettant une concurrence supplémentaire et peuvent améliorer la robustesse en évitant certains des problèmes causés par l'inversion de priorité dans les paramètres locaux ou les défaillances de machine et de liaison dans les systèmes distribués.
La meilleure introduction générale à nos algorithmes non bloquants est la programmation papier simultanée sans verrous, actuellement soumise, qui couvre nos conceptions de comparaison et d'échange de plusieurs mots, la mémoire transactionnelle logicielle basée sur des mots et la mémoire transactionnelle logicielle basée sur des objets.
Si "sans verrou" signifie "n'utilisez pas les sémaphores, mutex, moniteurs, ...", alors je pense (mais je ne suis pas un expert) que chaque collection peut être rendue sans verrou en utilisant la lecture-écriture atomique- modifier les primitives qui doivent être prises en charge par le matériel.
Une surcharge de calcul est nécessaire, mais je pense que pour les structures simples comme les listes, les arbres, les tables de hachage ... la complexité de calcul globale des recherches / insertions / suppressions ne change pas.O(⋅)
Une documentation exhaustive sur le sujet est disponible en ligne:
http://www.google.it/search?q=lock+free+algorithm+filetype%3Apdf
(... et autres références à la fin de chaque document)
la source