Quel est le numéro de consensus pour les sémaphores?

Question

(Je pense que le numéro de consensus pour un mutex est 2.

Quel est le numéro de consensus pour les sémaphores (comme dans pthread_sem_ *)?

Quel est le numéro de consensus pour les variables de condition (comme dans pthread_cond_ *)?

Answer 1

Le numéro de consensus pour un mutex serait 1. Il est trivialement clair qu'un mutex sera sans attente pour un seul thread. D'après sa définition, il est également clair qu'un mutex n'est plus attendu pour deux threads. Le nombre de consensus est donc> = 1 et <2, il doit donc être 1.

De même, d'autres mécanismes de synchronisation qui fonctionnent en arrêtant un thread en faveur d'un autre ont également un consensus numéro 1, et ne peuvent donc pas être utilisés pour construire un objet sans attente partagé par 2 threads.

Answer 2

La réponse dépend des opérations prises en charge sur le mutex ou le sémaphore. Si seuls les verrous de blocage sont pris en charge, le numéro de consensus est 1. Si un fil peut essayer de verrouiller le mutex sans attendre, le numéro de consensus est 2. C'est parce que s'il y a deux threads, les deux peuvent essayer de verrouiller le mutex, les deux peuvent Convenez lequel l'a obtenu, donc il y a un consensus. Si le mutex peut en outre déterminer, pour n'importe quel nombre de threads, quel thread l'a verrouillé, le numéro de consensus est infini. Je pense que la situation des sémaphores est similaire. Les mutex sont équivalents aux sémaphores avec le comptoir 1. Je ne pense pas que le consensus puisse être atteint avec des compteurs plus grands, il se résume toujours aux mêmes opérations. Pthreads prend en charge les verrous non bloquant mais pas les requêtes, donc la réponse serait 2.

La signalisation d'une variable de condition ne fait rien si des threads ne l'attendent pas, ils ont donc le consensus numéro 1.

Answer 3

Infini, sûrement? Mais ils n'attendent pas gratuitement.

Je suis peut-être un malentendu. Vous dites qu'un mutex a un numéro consensuel de 2 - quelle est votre source pour cela? Il est conçu pour permettre à un certain nombre de threads de partager une ressource, avec le compromis de blocage.

Atomique test et ensemble a un numéro consensuel de 2, mais ne bloque pas.

---

Pour clarifier: les sémaphores, les mutex, etc. sont des primitives que vous pouvez simplement enrouler autour d'une ressource partagée pour la rendre sûre (tant que vous le faites correctement). Ils peuvent bloquer, mais ils garantiront que vos données sont sûres.

Le document que vous citez concerne les primitives nécessaires pour protéger les données sans blocage, lequel est dur. Les mêmes primitives peuvent également être utiles pour les verrous, mais c'est juste un bon supplément.

Answer 4

À partir de cet article, vous pouvez conclure qu'un sémaphore doit avoir un nombre de consensus inférieur ou égal à 2. Voici pourquoi:

Sur la troisième page de l'article, ils indiquent: "L'opération Fetch & Add est assez flexible: elle peut être utilisée pour les sémaphores ...". Puisque nous savons que Fetch & Add a un nombre de consensus égal à 2, le théorème 1 de ce papier peut alors être utilisé pour montrer qu'un sémaphore doit avoir un nombre de consensus inférieur ou égal à 2. La preuve va comme ceci:

Preuve

Supposons qu'une implémentation sans attente de sémaphores par Fetch & Add existe. Supposons en outre qu'un sémaphore a un nombre de consensus supérieur à 2. Nous savons que Fetch & Add a un numéro consensuel de 2. du théorème 1, nous pouvons conclure qu'il n'existe pas de mise en œuvre sans attente d'un sémaphore par Fetch & Add dans un système de plus de 2 processus . Cela contredit l'hypothèse selon laquelle une implémentation par Fetch & Add existe. Par conséquent, un sémaphore doit avoir un nombre consensuel inférieur ou égal à 2.

QED