Uma operação prática de comparação e troca de várias palavras

No artigo com o mesmo título que o desta pergunta, os autores descrevem como construir uma operação CAS linearizável de múltiplas palavras sem bloqueio usando apenas um CAS de uma única palavra. Eles primeiro introduzem a operação de dupla comparação, troca única - RDCSS, da seguinte maneira:

word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d->a2, d->o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d->o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d->a1);
  if (v == d->o1) CAS1(d->a2, d, d->n2);
  else CAS1(d->a2, d, d->o2);
}

onde RDCSSDescriptor_té uma estrutura com os seguintes campos:

• a1 - endereço da primeira condição
• o1 - valor esperado no primeiro endereço
• a2 - endereço da segunda condição
• o2 - valor esperado no segundo endereço
• n2 - o novo valor a ser escrito no segundo endereço

Esse descritor é criado e inicializado uma vez em um encadeamento que inicia a operação RDCSS - nenhum outro encadeamento faz referência a ele até que o primeiro CAS1 da função seja RDCSSbem-sucedido, tornando o descritor acessível (ou ativo na terminologia do artigo).

A idéia por trás do algoritmo é a seguinte - substitua o segundo local da memória por um descritor dizendo o que você deseja fazer. Em seguida, como o descritor está presente, verifique o primeiro local da memória para ver se seu valor foi alterado. Caso contrário, substitua o descritor no segundo local da memória pelo novo valor. Caso contrário, defina o segundo local da memória novamente para o valor antigo.

Os autores não explicam por que a linha com o !!comentário é necessária no artigo. Parece-me que as CAS1instruções na Completefunção sempre falham após essa verificação, desde que não haja modificação simultânea. E se houve uma modificação simultânea entre a verificação e a entrada do CAS Complete, o segmento que está realizando a verificação ainda deve falhar com o seu CAS Complete, pois a modificação simultânea não deve usar o mesmo descritor d.

A minha pergunta é: Pode o check-in a função RDCSSS, if (r == d->o2)...ser omitido, com RDCSS ainda mantendo a semântica de um comparar única instrução dupla, troca que é linearizable e livre-lock ? (linha com !!comentário)

Caso contrário, você pode descrever o cenário em que essa linha é realmente necessária para garantir a correção?

Obrigado.

Em um ambiente de tempo de execução simultâneo, coisas simples podem parecer estranhas ... espero que isso ajude.

Temos um CAS1 ATÔMICO INCORPORADO com esta semântica:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

Precisamos definir uma função ATOMIC RDCSS usando CAS1 e ter a seguinte semântica:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Intuitivamente: precisamos alterar o valor em addr2 CONCURRENTE apenas se * addr1 == oldval1 ... se outro segmento estiver mudando, podemos ajudar o outro segmento a concluir a operação e tentar novamente.

A função RDCSS será usada (consulte o artigo) para definir o CASN. Agora, definimos um descritor RDCSS da seguinte maneira:

RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2

Em seguida, implementamos o RDCSS da seguinte maneira:

int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);  
}

• PASSO 1: primeiro tentamos alterar o valor de * addr2 para o nosso (próprio) descritor d, se o CAS1 for bem-sucedido, res == d-> oldval2 (ou seja, res NÃO é um descritor)
• PASSO 2: verifique se res é um descritor, isto é, PASSO 1 falhou (outro thread mudou addr2) ... ajude outro thread a concluir a operação
• PASSO 3: tente novamente o PASSO 1 se não conseguirmos armazenar nosso descritor d
• PASSO 4: se buscamos nosso valor esperado em addr2, conseguimos armazenar nosso descritor (ponteiro) em addr2 e podemos concluir nossa tarefa armazenando newval2 para * addr2 iif * addr1 == oldval1

RESPOSTA À SUA PERGUNTA

Se omitirmos o STEP4, a parte if (... && * addr1 == oldval1) * addr2 = newval2 da semântica do RDCSS nunca será executada (... ou melhor: ela pode ser executada de maneira imprevisível por outros threads, ajudando o atual).

Conforme indicado por você no seu comentário, a condição se (res == d1-> oldval2) no PASSO 4 é desnecessária: mesmo se o omitirmos, o CAS1 em Complete () falhará porque * (d-> addr2)! = D . Seu único objetivo é evitar uma chamada de função.

Exemplo T1 = segmento1, T2 = segmento2:

remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end 
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)