Qual é o número de consenso para semáforos?

Question

(Eu acho que o número de consenso para um mutex é 2.

Qual é o número de consenso para semáforos (como em pthread_sem_*)?

Qual é o número de consenso para variáveis ​​de condição (como em pthread_cond_*)?

Answer 1

O número de consenso para um mutex seria 1.É trivialmente claro que um mutex não terá espera por um único thread.Pela sua definição, também fica claro que um mutex não é mais livre de espera por dois threads.O número de consenso, portanto, é >=1 e <2, portanto deve ser 1.

Da mesma forma, outros mecanismos de sincronização que funcionam interrompendo um thread em favor de outro também têm número de consenso 1 e, portanto, não podem ser usados ​​para construir um objeto livre de espera compartilhado por 2 threads.

Answer 2

A resposta depende das operações suportadas no mutex ou no semáforo.Se apenas os bloqueios de bloqueio forem suportados, o número de consenso será 1.Se um thread puder tentar bloquear o mutex sem esperar, o número de consenso será 2.Isso porque se houver dois threads, ambos podem tentar bloquear o mutex, ambos podem concordar em qual deles o obteve, então há consenso.Se o mutex puder determinar adicionalmente, para qualquer número de threads, qual thread o bloqueou, então o número de consenso será infinito.Acho que a situação dos semáforos é semelhante.Mutexes são equivalentes a semáforos com contador 1.Não creio que o consenso possa ser alcançado apenas com contadores maiores, ainda se resume às mesmas operações.Pthreads suporta bloqueios sem bloqueio, mas não consultas, então a resposta seria 2.

Sinalizar uma variável de condição não faz nada se algum thread não estiver esperando por ela, então eles têm o número de consenso 1.

Answer 3

Infinito, certamente?Mas eles não esperam de graça.

Talvez eu esteja entendendo mal.Você diz que um mutex tem um número de consenso 2 - qual é a sua fonte para isso?Ele foi projetado para permitir que qualquer número de threads compartilhe um recurso, com a contrapartida do bloqueio.

Atômico testar e definir tem um número de consenso de 2, mas não bloqueia.

---

Esclarecer:semáforos, mutexes, etc.são primitivos que você pode simplesmente envolver um recurso compartilhado para torná-lo seguro (desde que você faça isso corretamente).Eles podem bloquear, mas garantirão que seus dados estejam seguros.

O artigo que você cita é sobre os primitivos necessários para proteger os dados sem bloquear, qual é duro.As mesmas primitivas também podem ser úteis para bloqueios, mas isso é apenas um ótimo extra.

Answer 4

Somente a partir deste artigo você pode concluir que um semáforo deve ter um número de consenso menor ou igual a 2.Aqui está o porquê:

Na terceira página do artigo afirmam:"A operação fetch&add é bastante flexível:pode ser usado para semáforos...".Como sabemos que fetch&add tem número de consenso igual a 2, o Teorema 1 desse artigo pode então ser usado para mostrar que um semáforo deve ter número de consenso menor ou igual a 2.A prova é assim:

Prova

Suponha que exista uma implementação de semáforos sem espera por fetch&add.Suponha ainda que um semáforo tenha um número de consenso maior que 2.Sabemos que fetch&add tem um número de consenso de 2.Do Teorema 1 podemos concluir que não existe implementação sem espera de um semáforo por fetch&add em um sistema com mais de 2 processos.Isso contradiz a suposição de que existe uma implementação por fetch&add.Portanto, um semáforo deve ter um número de consenso menor ou igual a 2.

QED