Diferença entre número de consenso N e número de consenso infinito

Question

no livro Programação simultânea: algoritmos, princípios e fundações de Michel Raynal, na seção 16.5.1, Teorema 75 diz

.

Compare & Swap Objects tem um número de consenso infinito.

e na seção 16.5.2, o Lema 40 diz

.

O tipo de objeto MEM-TO-MEM-SWAP possui um número de consenso n em um sistema de n processos.

Então, na seção 16.1, o autor coloca na tabela em comparação e swap e swap e homens-mem-swap como objetos com um número de consenso infinito.

Então, qual é a diferença entre objetos com número de consenso n e objetos com número de consenso infinito?

Answer 1

O número de consenso de um objeto é o número máximo de processos simultâneos que você pode sincronizar com um desses objetos de uma maneira livre de espera (não vou entrar em que meios de espera aqui). Por exemplo, um registro apenas com as operações de leitura e gravação não ajuda com a sincronização livre de espera, por isso tem o número de consenso 1. Um registro com uma operação de teste e definição pode ser usado para sincronizar dois processos de espera -Free maneira, mas não três ou mais, então o número de consenso de test-and-set é 2.

$ n $ - atribuição -Register, onde um processo pode gravar atomicamente para vários registros, permite que até $ 2n- 2 $ processos para sincronizar livre de espera se houver $ n $ registradores. Mais processos exigem mais registros. Portanto, o número de consenso de um objet consistindo de $ n $ registradores que podem ser atribuídos atomicamente é $ 2N-2 $ .

Um único registro com uma operação de comparação e swap é suficiente para sincronizar qualquer número de processos de graça à espera. Portanto, o número de consenso de comparação e troca é infinito.

lema 40 afirma que um objeto mem-and-swap permite a sincronização livre de espera de todos os processos em um sistema de $ n $ processos simultâneos, para qualquer número $ n $ . Isso significa que para qualquer número $ n $ , o número de consenso de mem-and-swap é pelo menos $ n $ < / span>. (Afirmando que o número de consenso é $ n $ em um sistema de $ n $ Processos é um pouco de um equívoco, uma vez que a definição do número de consenso não depende realmente do número total de processos.) Como o número de consenso de mem-and-swap é pelo menos $ n $ para qualquer $ n $ , é infinito.

Se você preferir outra fonte do que o livro de Raynal, você pode ler o original papel por Maurice herlihy .