¿Una implementación probada del algoritmo de bloqueo Peterson?

concurrency locking

Question

¿Alguien sabe de una buena / correcta implementación del algoritmo de Bloqueo de Peterson en C? Parece que no puedo encontrar esto. Gracias.

Answer 1

El algoritmo de Peterson no se puede implementar correctamente en C99, como se explica en quién ordenó vallas de memoria en un x86 .

El algoritmo de Peterson es el siguiente:

LOCK:

interested[id] = 1                interested[other] = 1
turn = other                      turn = id

while turn == other               while turn == id
  and interested[other] == 1        and interested[id] == 1


UNLOCK:

interested[id] = 0                interested[other] = 0

Hay algunas suposiciones ocultas aquí. Para empezar, cada hilo debe notar su interés en adquirir la cerradura antes de regalar su turno. Regalar el turno debe hacer visible para el otro hilo que estamos interesados ​​en adquirir el candado.

Además, como en cada bloqueo, los accesos a la memoria en la sección crítica no pueden ser izados más allá de la llamada a lock (), ni hundirse más allá del desbloqueo (). Es decir: lock () debe tener al menos una semántica, y unlock () debe tener al menos una semántica de lanzamiento.

En C11, la forma más sencilla de lograr esto sería utilizar un orden de memoria secuencialmente consistente, que hace que el código se ejecute como si fuera un simple entrelazado de subprocesos que se ejecutan en orden de programa ( ADVERTENCIA: código totalmente no probado , pero es similar a un ejemplo en el Detector de Razas Relacy de Dmitriy V''jukov):

lock(int id)
{
    atomic_store(&interested[id], 1);
    atomic_store(&turn, 1 - id);

    while (atomic_load(&turn) == 1 - id
           && atomic_load(&interested[1 - id]) == 1);
}

unlock(int id)
{
    atomic_store(&interested[id], 0);
}

Esto garantiza que el compilador no realice optimizaciones que rompan el algoritmo (alzando / hundiendo cargas / almacenamientos en operaciones atómicas), y emite las instrucciones adecuadas de la CPU para garantizar que la CPU tampoco rompa el algoritmo. El modelo de memoria predeterminado para las operaciones atómicas C11 / C ++ 11 que no seleccionan explícitamente un modelo de memoria es el modelo de memoria secuencialmente consistente.

C11 / C ++ 11 también admite modelos de memoria más débiles, permitiendo la mayor optimización posible. La siguiente es una traducción a C11 de la traducción a C ++ 11 por Anthony Williams de un algoritmo originalmente de Dmitriy V''jukov en la sintaxis de su propio Detector de Raza Relacionada [petersons_lock_with_C ++ 0x_atomics] [the-incrutable-c-memory -model] . Si este algoritmo es incorrecto, es mi culpa ( ADVERTENCIA: también código no probado , pero basado en un buen código de Dmitriy V''jukov y Anthony Williams):

lock(int id)
{
    atomic_store_explicit(&interested[id], 1, memory_order_relaxed);
    atomic_exchange_explicit(&turn, 1 - id, memory_order_acq_rel);

    while (atomic_load_explicit(&interested[1 - id], memory_order_acquire) == 1
           && atomic_load_explicit(&turn, memory_order_relaxed) == 1 - id);
}

unlock(int id)
{
    atomic_store_explicit(&interested[id], 0, memory_order_release);
}

Observe el intercambio con la semántica de adquisición y liberación. Un intercambio es una operación RMW atómica. Las operaciones RMW atómicas siempre leen el último valor almacenado antes de la escritura en la operación RMW. Además, una adquisición en un objeto atómico que lee una escritura de un lanzamiento en ese mismo objeto atómico (o cualquier escritura posterior en ese objeto del hilo que realizó el lanzamiento o cualquier escritura posterior de cualquier operación RMW atómica) crea una sincronización con relación entre la liberación y la adquisición.

Por lo tanto, esta operación es un punto de sincronización entre los hilos, siempre hay una relación synchronizes-with entre el intercambio en un hilo y el último intercambio realizado por un hilo (o la inicialización del giro, para el primer intercambio).

Entonces, tenemos una relación secuencia-antes entre la tienda para interested[id] y el intercambio de / a turn , una relación de sincronización-entre dos intercambios consecutivos de / a turn , y una relación secuencia-antes entre el intercambio de / a turn y la carga de interested[1 - id] . Esto equivale a una relación de pasar antes a los accesos a los interested[x] en diferentes subprocesos, que a turn proporciona la sincronización entre los subprocesos. Esto obliga a todos los pedidos necesarios para que el algoritmo funcione.

Entonces, ¿cómo se hicieron estas cosas antes de C11? Implicó el uso de compiladores y magia específica de la CPU. Como ejemplo, veamos el x86 bastante ordenado. IIRC, todas las cargas x86 tienen semántica de adquisición, y todas las tiendas tienen semántica de lanzamiento (excepto movimientos no temporales, en SSE, utilizados precisamente para lograr un mayor rendimiento a costa de tener que emitir ocasionalmente vallas de CPU para lograr coherencia entre las CPU). Pero esto no es suficiente para el algoritmo de Peterson, como explica Bartosz Milewsky en who-ordered-memory-fences-on-an-x86 , para que funcione el algoritmo de Peterson necesitamos establecer un orden entre accesos para turn e interested , no hacer eso puede provocar que se muestren cargas de interested[1 - id] interested[id] antes de escribir en la interested[id] , lo cual es algo malo.

Entonces, una forma de hacerlo en GCC / x86 sería ( ADVERTENCIA: aunque probé algo similar a lo siguiente, en realidad una versión modificada del código en wrong-implementation-of-petersons-algorithm , las pruebas están lejos de asegurar la corrección de multiproceso código ):

lock(int id)
{
    interested[id] = 1;
    turn = 1 - id;
    __asm__ __volatile__("mfence");

    do {
        __asm__ __volatile__("":::"memory");
    } while (turn == 1 - id
           && interested[1 - id] == 1);
}

unlock(int id)
{
   interested[id] = 0;
}

El MFENCE evita que las tiendas y cargas a diferentes direcciones de memoria se reordenen. De lo contrario, la escritura en la interested[id] podría ponerse en cola en el búfer de la tienda mientras continúa la carga del interested[1 - id] . En muchas microarquitecturas actuales, un SFENCE puede ser suficiente, ya que puede implementarse como un desagüe del búfer de tienda, pero IIUC SFENCE no necesita implementarse de esa manera, y puede evitar simplemente el reordenamiento entre tiendas. Así que SFENCE puede no ser suficiente en todas partes, y necesitamos un MFENCE completo.

La barrera del compilador ( __asm__ __volatile__("":::"memory") ) evita que el compilador decida que ya conoce el valor del turn . Le estamos diciendo al compilador que hemos destruido la memoria, por lo que todos los valores en caché en los registros deben volver a cargarse desde la memoria.

PD: Siento que esto necesita un párrafo final, pero mi cerebro está agotado.

Answer 2

No haré ninguna afirmación sobre qué tan buena o correcta es la implementación, pero se probó (brevemente). Esta es una traducción directa del algoritmo descrito en wikipedia.

struct petersonslock_t {
    volatile unsigned flag[2];
    volatile unsigned turn;
};
typedef struct petersonslock_t petersonslock_t;

petersonslock_t petersonslock () {
    petersonslock_t l = { { 0U, 0U }, ~0U };
    return l;
}

void petersonslock_lock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    l->flag[p] = 1;
    l->turn = !p;
    while (l->flag[!p] && (l->turn == !p)) {}
};

void petersonslock_unlock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    l->flag[p] = 0;
};

Greg señala que en una arquitectura SMP con coherencia de memoria ligeramente relajada (como x86), aunque las cargas en la misma ubicación de memoria están en orden, las cargas a diferentes ubicaciones en un procesador pueden aparecer desordenadas para el otro procesador.

Jens Gustedt y Ninjalj recomiendan modificar el algoritmo original para usar el tipo atomic_flag . Esto significa establecer las banderas y los giros que usarían atomic_flag_test_and_set y atomic_flag_clear usaría atomic_flag_clear desde C11. Alternativamente, se podría imponer una barrera de memoria entre las actualizaciones del flag .

Editar: Originalmente intenté corregir esto escribiendo a la misma ubicación de memoria para todos los estados. ninjalj señaló que las operaciones a nivel de bit convirtieron las operaciones de estado en RMW en lugar de cargar y almacenar el algoritmo original. Por lo tanto, se requieren operaciones atómicas bit a bit. C11 proporciona dichos operadores, al igual que GCC con integradores. El algoritmo que se muestra a continuación utiliza integrables GCC, pero está envuelto en macros para que pueda cambiarse fácilmente a alguna otra implementación. Sin embargo, la solución preferida es modificar el algoritmo original anterior.

struct petersonslock_t {
    volatile unsigned state;
};
typedef struct petersonslock_t petersonslock_t;

#define ATOMIC_OR(x,v)   __sync_or_and_fetch(&x, v)
#define ATOMIC_AND(x,v)  __sync_and_and_fetch(&x, v)

petersonslock_t petersonslock () {
    petersonslock_t l = { 0x000000U };
    return l;
}

void petersonslock_lock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    unsigned mask = (p == 0) ? 0xFF0000 : 0x00FF00;
    ATOMIC_OR(l->state, (p == 0) ? 0x000100 : 0x010000);
    (p == 0) ? ATOMIC_OR(l->state, 0x000001) : ATOMIC_AND(l->state, 0xFFFF00);
    while ((l->state & mask) && (l->state & 0x0000FF) == !p) {}
};

void petersonslock_unlock (petersonslock_t *l, int p) {
    assert(p == 0 || p == 1);
    ATOMIC_AND(l->state, (p == 0) ? 0xFF00FF : 0x00FFFF);
};