Una práctica práctica de comparación e intercambio de varias palabras

En el documento con el mismo título que el de esta pregunta, los autores describen cómo construir una operación CAS de varias palabras linealizable sin bloqueo utilizando solo un CAS de una sola palabra. Primero presentan la operación de doble comparación, intercambio único, RDCSS, de la siguiente manera:

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);
}

donde el RDCSSDescriptor_tes una estructura con los siguientes campos:

• a1 - dirección de la primera condición
• o1 - valor esperado en la primera dirección
• a2 - dirección de la segunda condición
• o2 - valor esperado en la segunda dirección
• n2 - el nuevo valor que se escribirá en la segunda dirección

Este descriptor se crea e inicializa una vez en un subproceso que inicia la operación RDCSS: ningún otro subproceso tiene una referencia hasta que el primer CAS1 en la función RDCSStiene éxito, haciendo que el descriptor sea accesible (o activo en la terminología del documento).

La idea detrás del algoritmo es la siguiente: reemplace la segunda ubicación de memoria con un descriptor que diga lo que desea hacer. Luego, dado que el descriptor está presente, verifique la primera ubicación de la memoria para ver si su valor cambió. Si no es así, reemplace el descriptor en la segunda ubicación de memoria con el nuevo valor. De lo contrario, vuelva a establecer la segunda ubicación de memoria en el valor anterior.

Los autores no explican por qué la línea con el !!comentario es necesaria dentro del artículo. Me parece que las CAS1instrucciones en la Completefunción siempre fallarán después de esta verificación, siempre que no haya una modificación concurrente. Y si hubo una modificación concurrente entre la verificación y el CAS Complete, entonces el hilo que realiza la verificación aún debería fallar con su CAS Complete, ya que la modificación concurrente no debería usar el mismo descriptor d.

Mi pregunta es: ¿se puede omitir la verificación en la función RDCSSS, if (r == d->o2)...con RDCSS aún manteniendo la semántica de una instrucción de doble comparación, intercambio único que es linealizable y sin bloqueo ? (línea con !!comentario)

Si no, ¿puede describir el escenario en el que esta línea es realmente necesaria para garantizar la corrección?

Gracias.

En un entorno de tiempo de ejecución concurrente, las cosas simples pueden parecer extrañas ... espero que esto pueda ayudar.

Tenemos un CAS1 ATÓMICO INCORPORADO que tiene esta semántica:

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

Necesitamos definir una función RDCSS ATÓMICA usando CAS1 y que tenga la siguiente 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: necesitamos cambiar CONCURRENTEMENTE el valor en addr2 solo si * addr1 == oldval1 ... si otro hilo lo está cambiando, podemos ayudar al otro hilo a completar la operación, entonces podemos volver a intentarlo.

Se utilizará la función RDCSS (ver artículo) para definir CASN. Ahora, definimos un Descriptor RDCSS de la siguiente manera:

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

Luego implementamos RDCSS de la siguiente manera:

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);  
}

• PASO 1: primero intentamos cambiar el valor de * addr2 a nuestro (propio) descriptor d, si CAS1 tiene éxito entonces res == d-> oldval2 (es decir, res NO es un descriptor)
• PASO 2: compruebe si res es un descriptor, es decir, PASO 1 falló (otro hilo cambió addr2) ... ayude a otro hilo a completar la operación
• PASO 3: vuelva a intentar el PASO 1 si no logramos almacenar nuestro descriptor d
• PASO 4: si obtuvimos nuestro valor esperado de addr2, entonces logramos almacenar nuestro descriptor (puntero) en addr2 y podemos completar nuestra tarea almacenando newval2 en * addr2 iif * addr1 == oldval1

RESPUESTA A SU PREGUNTA

Si omitimos STEP4, entonces la parte if (... && * addr1 == oldval1) * addr2 = newval2 de la semántica RDCSS nunca se ejecutará (... o mejor: puede ser ejecutada de manera impredecible por otros hilos que ayudan el actual).

Como señaló en su comentario, la condición si (res == d1-> oldval2) en STEP4 es innecesaria: incluso si lo omitimos, ambos CAS1 en Complete () fallarán porque * (d-> addr2)! = D . Su único propósito es evitar una llamada a la función.

Ejemplo T1 = hilo1, T2 = hilo2:

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)