Concorrência (ciência da computação): Quais são algumas desvantagens do uso do CAS (comparar e trocar)?

A questão é um pouco geral para produzir uma resposta muito precisa, mas eu vou dar um jeito nisso … Receio não poder sugerir uma orientação melhor para a abordagem sem bloqueio do que “pensar muito sobre isso” e teste muito sua solução “.

Para problemas com comparar e trocar, só consigo pensar em um, mas nas condições certas, ele aparece. Toda a família de operações de “busca e phi” de vários poderes expressivos (variando de teste e configuração, busca e adição, comparação e troca) compartilham a questão de que eles fazem o verdadeiro café da manhã de um porco coerência fora do cache. Em uma configuração em que há alguma contenção para o local que você deseja atualizar atomicamente, as cópias armazenadas em cache localmente (potencialmente espalhadas por toda a máquina) exigem invalidação e liberação / gravação durante a operação atômica. em um processador, que se torna uma penalidade séria se for feito muito. Além disso, se imaginarmos algum tipo de esquema de diretório ou outra propriedade NUMA para grandes memórias compartilhadas. acesso, o armazenamento em cache (sob contenção) favoreceria os processadores que estão perto do banco de memória em que o valor está hospedado.

Se você olhar os documentos sobre o design do Stanford DASH, eles chegaram a recomendar a implementação de um sistema de memória totalmente separado e sem cache, especialmente para fins de operações atômicas, e algumas arquiteturas comerciais seguiram o exemplo (as máquinas Origin apresentaram instruções como esta que funcionam apenas com “memória de reservatório atômico”, completa com a política de alocação independente desajeitada, IIRC).

Se você usar atômicos não bloqueadores de rolagem (cargas vinculadas a um write-back condicional), descobrirá o efeito de cache injusto acima mencionado se muitos processadores estiverem lutando pelo mesmo endereço, mas, caso contrário, arriscaria adivinhar que existem é uma certa compatibilidade futura na criação de algoritmos que exigem suporte do ISA para operações de busca e phi. (Isso é um palpite, isenções de responsabilidade e tudo mais, faça do que você quiser.)

Nos casos em que você realmente não espera ver muita contenda (ou seja, a atomicidade é mais uma salvaguarda contra raças raras do que um meio de impor ordem em uma corrida muito comum), eu suspeito que você terá dificuldade em produzir qualquer evidência quantitativa de que uma ou outra abordagem é melhor.

Antes de começar a fazer inferências sobre isso, verifique se o compare-and-swap está no ISA da sua máquina ou se é algum compilador simples intrínseco a gerar uma sequência de instruções equivalente. Pode não haver tanta escolha quanto as aparências indicam.

Para discutir as desvantagens, você precisaria mencionar outro para comparar o CAS. Suponho que você esteja interessado nas dificuldades de implementar corretamente algoritmos sem bloqueio.

  1. Você deve ter um entendimento detalhado do compilador que está usando e que tipo de otimização ele pode executar. Para C e C ++, isso significa entender pontos de sequência.
  2. Você deve ter um entendimento detalhado da sua arquitetura de hardware e o tipo de coerência de memória que ela oferece. As implementações estão vinculadas a um hardware específico e não podem ser usadas diretamente em outras plataformas.
  3. É fácil para um desenvolvedor introduzir bugs fazendo modificações aparentemente inofensivas em um pedaço de código. Suas práticas de codificação devem levar isso em consideração, por exemplo, através de revisões sistemáticas de código.

Mesmo assim, como você não pode avaliar realisticamente a correção de uma implementação usando o teste, sua implementação deve estar correta por construção. Você não pode usar métodos tradicionais de desenvolvimento onde começa com um protótipo que funciona principalmente e, em seguida, corrige-o através da depuração.
Em vez disso, você deve começar com uma especificação que esteja claramente correta e deve ficar claro que a implementação é uma tradução fiel da especificação.