Se eu usar bloqueios, meu algoritmo ainda pode estar livre de bloqueios?

Uma definição comum de livre de bloqueio é que pelo menos um processo progride. ^{1 1}

Se eu tiver uma estrutura de dados simples, como uma fila, protegida por um bloqueio, um processo sempre poderá progredir, pois um processo pode adquirir o bloqueio, fazer o que ele deseja e liberá-lo.

Então, ele atende à definição de lock-free?

¹ Ver, por exemplo, M. Herlihy, V. Luchangco e M. Moir. Sincronização sem obstruções: Filas de duas extremidades como exemplo. Em Computação Distribuída, 2003. "É livre de bloqueios se garantir apenas que algum encadeamento sempre faça progresso".

Essa não é uma definição para livre de bloqueio.

Se você puder garantir o progresso, estará livre de impasse e , se tiver a conclusão final de cada solicitação, estará livre de fome , mas não de bloqueio.

Eu questiono se o seu exemplo simples realmente fornece isso de qualquer maneira. Você precisa de hierarquias de bloqueio e assim por diante para realmente garantir o progresso quando vários bloqueios estiverem envolvidos.

Estudei The Art of Multiprocessor Programming ¹ e seu texto está faltando em clareza, assim como o livro a que você se refere. Aqui estão algumas citações do TAMPP:

Citação 1 (Definição de bloqueio)

Um método é livre de bloqueios se garantir que infinitamente muitas vezes alguma chamada de método seja concluída em um número finito de etapas.

Citação 2 (Definição de não bloqueio)

uma invocação pendente de um método total nunca é necessária para aguardar a conclusão de outra invocação pendente.

Citação 3 (alegar que o bloqueio é livre de bloqueio)

As condições de progresso sem bloqueio e sem espera e sem bloqueio garantem que o cálculo como um todo progrida, independentemente de como o sistema agende os encadeamentos.

O problema é que a alegação na citação 3 obviamente não segue a definição da citação 1. Como já mencionado, uma fila sincronizada parece satisfazer a citação 1: infinitamente, com frequência, algum método obtém com êxito o bloqueio e é concluído.

Observe especificamente a frase bastante vaga da citação 3: "independentemente de como o sistema agende os threads". Isso não é precedido por nenhum tipo de descrição formal do "sistema de agendamento de encadeamentos"; portanto, resta reconstruir suas propriedades com base em nossos preconceitos sobre o que as definições devem significar:

1. o sistema sempre executa instruções de algum encadeamento;
2. ele nunca pode executar instruções de qualquer dado fio;
3. todos os threads estão invocando o método em consideração.

Nesse sistema, um método de bloqueio não pode ser livre de bloqueios: se o encadeamento que segura o trava nunca for agendado novamente para execução, não haverá outro encadeamento que possa concluir sua invocação de método em um número finito de etapas, mas haverá alguns segmentos que estão executando etapas do método. Para um sistema mais realista, que garanta tempo de CPU para cada thread eventualmente, a definição deve incluir explicitamente a propriedade nonblocking:

Definição corrigida de livre de bloqueio

Um método é livre de bloqueios se não for bloqueador e, além disso, garante que infinitamente muitas vezes alguma chamada de método seja concluída em um número finito de etapas.

¹ Maurice Herlihy, Nir Shavit, A Arte da Programação em Multiprocessador, Elsevier 2008, pp. 58-60

A terminologia nem sempre é consistente, mas acho que é importante fazer as seguintes perguntas sobre um algoritmo ou sistema proposto:

1. Existe alguma sequência de eventos em que os threads possam ficar presos esperando um pelo outro, mesmo que todos os threads tenham tempo de CPU suficiente para usar [nesse caso, não há impasse]
2. Se um encadeamento foi bloqueado por um longo período de tempo arbitrário, isso poderia interromper outros encadeamentos ou prejudicar a operação do sistema por um longo tempo arbitrariamente [se assim for, não é sem bloqueio].
3. Existe alguma combinação pelo menos teoricamente possível de agendamento de encadeamentos que poderia fazer com que todos os encadeamentos repetissem as mesmas operações repetidamente, invalidando o trabalho uns dos outros, sem que ninguém progredisse [nesse caso, não é livre de bloqueios]
4. Se alguns segmentos tiverem tempo de CPU suficiente em relação a outro, eles poderiam forçar o último segmento a continuar repetindo suas operações indefinidamente [nesse caso, não é sem espera].

Muito do significado dos algoritmos sem bloqueio não é que eles são mais rápidos do que os algoritmos sem bloqueio, mas o fato de que eles não são propensos a morrer se um encadeamento for desviado [observe que essa garantia apenas exige que os algoritmos não bloqueiam, mas todos os algoritmos sem bloqueios são]. É possível que um algoritmo sem bloqueios use bloqueios, mas somente se as tentativas de aquisição de bloqueios incluírem tempos limites, juntamente com algoritmos, para garantir que sempre seja possível alguém progredir (por exemplo, um algoritmo pode usar um CompareExchangeloop como principal) método de arbitragem, mas use bloqueios para arbitrar o acesso quando a contenção parecer alta; se um bloqueio parecer mantido excessivamente longo, outros threads poderão decidir abandonar os esforços para usá-lo e criar um novo.CompareExchange, fazer com que os clientes abandonem o bloqueio não comprometeria a consistência do sistema, embora isso possa significar que o código que estava mantendo o bloqueio antigo não será executado até que abandone o bloqueio antigo e se alinhe ao novo.

Você precisa observar a "definição" citada no contexto :

A maneira tradicional de implementar estruturas de dados compartilhadas é usar exclusão mútua (bloqueios) para garantir que operações simultâneas não interfiram entre si. O bloqueio tem várias desvantagens em relação à engenharia de software, tolerância a falhas e escalabilidade (consulte [8]). Em resposta, os pesquisadores investigaram uma variedade de técnicas alternativas de sincronização que não empregam exclusão mútua . Uma técnica de sincronização fica livre de espera se garantir que todos os encadeamentos continuarão progredindo diante de atraso arbitrário (ou até falha) de outros encadeamentos. É livre de bloqueio se garantir apenas que algum encadeamento sempre progrida.

Você está usando bloqueios para exclusão mútua, portanto, não é uma técnica sem bloqueios sobre a qual eles estão falando.

Se eu usar bloqueios, meu algoritmo ainda pode estar livre de bloqueios?

Poderia ser, mas depende do algoritmo.

Se eu tiver uma estrutura de dados simples, como uma fila, protegida por um bloqueio, um processo sempre poderá progredir, pois um processo pode adquirir o bloqueio, fazer o que ele deseja e liberá-lo.

Então, ele atende à definição de lock-free?

Nota per se .

Se a etapa "faça o que quiser" não envolver a aquisição de outros bloqueios e for garantida a conclusão em um tempo finito, essa parte específica do seu algoritmo estará livre de impasse.

No entanto, se essas pré-condições não forem atendidas, há pelo menos o potencial de conflitos ...

O exemplo que você dá não é bloqueado pelo seguinte motivo.

O suporte a um encadeamento adquire o bloqueio e o agendador do SO suspendeu o encadeamento por um período infinito e solitário; então, todo o encadeamento não pode progredir, pois não é possível adquirir o bloqueio adquirido pelo encadeamento suspenso.

De um modo geral, algoritmos que usam bloqueios não são livres de bloqueios.

Observe que sem conflito e sem bloqueio são dois conceitos diferentes. sem impasse significa que não há possibilidade de impasse, mas poderia haver impasse que pode impedir que todo o sistema progrida. A liberdade de bloqueio é mais forte do que isso, porque significa que alguns encadeamentos no sistema sempre progridem com um número finito de etapas.