Can CompareExchange peut-il être implémenté avec CompareAndSwap?

Question

En supposant que CompareAndSwap (ou CAS) ne manque jamais faussement, est-ce que CompareExchange peut être implémenté avec CAS? CompareExchange prend un pointeur, une valeur attendue et une nouvelle valeur et définit atomiquement la mémoire référencée par le pointeur sur la nouvelle valeur s'il correspond à la valeur attendue. La différence entre les deux est que CompareExchange renvoie la valeur précédente de la zone de mémoire et CompareAndSwap renvoie un bool indiquant le succès ou l'échec.

Il est trivial de mettre en œuvre CAS avec CompareExchange:

int CompareExchange (int* p, int expected, int newvalue); 

bool CAS (int* p, int expected, int newvalue) 
{ 
    return CompareExchange (p, expected, newvalue) != expected; 
} 

... mais est-il possible de mettre en œuvre CompareExchange avec CAS? Toutes les tentatives que j'ai vues ont des conditions de course ou ne garantissent pas des propriétés sans clé. Je ne crois pas que ce soit possible.

Answer 1

Je ne vois pas comment c'est possible. Dans le cas où CAS échoue, vous aurez besoin d'une opération séparée pour obtenir la valeur précédente. Cette opération séparée ne sera pas atomique par rapport au CAS.

Vous pouvez obtenir une partie chemin:

int CompareExchnage(int *p, int expected, int newvalue) 
{ 
    if (CAS(p, expected, newvalue)) 
     return expected; 
    else 
     ???; 
} 

Il est le cas où CAS échoue lorsque vous avez des problèmes. Obtenir *p pour trouver ce que la valeur précédente est ne sera pas atomique par rapport à CAS donc vous avez soit une condition de concurrence ou vous auriez à verrouiller le CAS et le déréférencement *p.

Answer 2

Vous pouvez, et il est sans verrou, mais il n'est pas sans attendre:

int CompareExchange(int *p, int expected, int newvalue) 
{ 
    for (;;) { 
     oldValue = *p; 
     if (oldValue != expected) 
      return oldValue; 
     if (CAS(p, expected, newvalue)) 
      return expected; 
    } 
} 

L'idée est qu'une modification de p * après le retour de CompareExchange ne se distingue pas d'une modification entre les deux ifs. De même, vous pouvez implémenter l'échange atomique et l'extraction-et-extraction atomique basés sur CAS, mais il ne sera pas sans attente.