Compartir a través de

Consideraciones de programación sin bloqueo para Xbox 360 y Microsoft Windows

  • Artículo

La programación sin bloqueos es una manera de compartir de forma segura los datos que van cambiando entre varios subprocesos sin tener que obtener y liberar bloqueos. Esto puede parecer la solución ideal, pero la programación sin bloqueos es compleja y sutil y a veces no aporta las ventajas que promete. La programación sin bloqueos es especialmente compleja en Xbox 360.

La programación sin bloqueos es una técnica válida para la programación multiproceso, pero no se debe usar a la ligera. Antes de usarla, debe conocer las complejidades y debe tener especial cuidado para asegurarse de que realmente le resulta efectivo de verdad. En muchos casos, hay soluciones más sencillas y rápidas, como compartir datos con menos frecuencia, que se deben usar en su lugar.

Para usar la programación sin bloqueos correctamente y de forma segura, se necesita bastantes conocimientos relacionados con el hardware y del compilador. En este artículo se da información general sobre algunos de los problemas que se deben tener en cuenta al intentar usar técnicas de programación sin bloqueos.

Programación con bloqueos

Al escribir código multiproceso, a menudo es necesario compartir datos entre subprocesos. Si varios subprocesos leen y escriben a la vez las estructuras de datos compartidos, puede producirse daños en la memoria. La manera más sencilla de resolver este problema es usar bloqueos. Por ejemplo, si ManipulateSharedData solo debe ejecutarse mediante un subproceso a la vez, se puede usar una CRITICAL_SECTION para garantizar esto, como en el código siguiente:

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

Este código es bastante sencillo y directo y se ve que es correcto. Sin embargo, la programación con bloqueos acarrea algunas posibles desventajas. Por ejemplo, si dos subprocesos intentan obtener los mismos dos bloqueos, pero en un orden diferente, podría generar un interbloqueo. Si un programa mantiene un bloqueo durante demasiado tiempo, por un diseño deficiente o porque el subproceso se ha cambiado por un subproceso de prioridad más alta, es posible que otros subprocesos se bloqueen durante mucho tiempo. Este riesgo es especialmente grave en Xbox 360 porque el desarrollador asigna a los subprocesos de software un subproceso de hardware y el sistema operativo no los moverá a otro subproceso de hardware, aunque uno esté inactivo. La Xbox 360 tampoco tiene protección frente a inversiones de prioridad, donde un subproceso de alta prioridad gira en bucle mientras espera a que un subproceso de prioridad baja libere un bloqueo. Por último, si una llamada a un procedimiento diferido o una rutina de servicio de interrupción intenta obtener un bloqueo, se podría generar un interbloqueo.

A pesar de estos problemas, los primitivos de sincronización, como las secciones críticas, suelen ser la mejor manera de coordinar varios subprocesos. Si los primitivos de sincronización son demasiado lentos, la mejor solución suele ser usarlos con menos frecuencia. Sin embargo, para aquellos que puedan permitirse una complejidad extra, otra opción es la programación sin bloqueos.

Programación sin bloqueos

La programación sin bloqueos, como sugiere el nombre, es una familia de técnicas para manipular datos compartidos de forma segura sin usar bloqueos. Hay algoritmos sin bloqueos disponibles para pasar mensajes, compartir listas y colas de datos y otras tareas.

Al poner en práctica la programación sin bloqueos, hay dos cuestiones que hay que abordar: las operaciones no atómicas y la reordenación.

Operaciones no atómicas

Una operación atómica es aquella que es indivisible, que garantiza que otros subprocesos nunca vean la operación cuando va por la mitad. Las operaciones atómicas son importantes para la programación sin bloqueos, ya que sin ellas, otros subprocesos pueden ver valores medio escritos o estados incoherentes.

En todos los procesadores modernos, podría suponer que las lecturas y escrituras de tipos nativos alineadas naturalmente son atómicas. Siempre que el bus de memoria sean al menos igual de ancho que el tipo que se lee o se escribe, la CPU lee y escribe estos tipos en una sola transacción de bus, lo que hace imposible que otros subprocesos los vean en un estado completado a medias. En x86 y x64, no hay ninguna garantía de que las lecturas y escrituras superiores a ocho bytes sean atómicas. Esto significa que las lecturas y escrituras de 16 bytes de registros de extensiones SIMD de streaming (SSE) y las operaciones de cadena podrían no ser atómicas.

Las lecturas y escrituras de tipos que no están alineadas de forma natural (por ejemplo, operaciones de escritura de DWORD que cruzan los límites de cuatro bytes) no se garantiza que sean atómicas. Es posible que la CPU tenga que realizar estas lecturas y escrituras como varias transacciones de bus, lo que podría permitir que otro subproceso modifique o vea los datos en medio de la lectura o de la escritura.

Las operaciones complejas, como la secuencia read-modify-write que se produce cuando se incrementa una variable compartida, no son atómicas. En Xbox 360, estas operaciones se implementan como varias instrucciones (lwz, addi y stw) y el subproceso podría intercambiarse en parte a través de la secuencia. En x86 y x64, hay una sola instrucción (inc) que se puede usar para incrementar una variable en la memoria. Si usa esta instrucción, la operación de incrementar una variable es atómica en sistemas de procesador único, pero sigue sin ser atómica en sistemas con varios procesadores. Para hacer atómica una inc en sistemas con varios procesadores basados en x86 y x64, se debe usar el prefijo de bloqueo, que impide que otro procesador realice su propia secuencia read-modify-write (lectura, modificación y escritura) entre la lectura y la escritura de la instrucción inc.

En el código siguiente se muestran algunos ejemplos:

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Cómo garantizar la atomicidad

Puede asegurarse de que usa operaciones atómicas combinando lo siguiente:

  • Operaciones atómicas de forma natural
  • Bloqueos para ajustar las operaciones complejas
  • Funciones del sistema operativo que implementan versiones atómicas de operaciones complejas populares

El incremento de una variable no es una operación atómica y el incremento puede provocar daños en los datos si se ejecutan en varios subprocesos.

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

Win32 incluye una familia de funciones que ofrecen versiones atómicas de read-modify-write de varias operaciones comunes. Se trata de la familia InterlockedXxx de funciones. Si todas las modificaciones de la variable compartida usan estas funciones, las modificaciones serán seguras en los subprocesos.

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Reordenación

Hay otra cuestión más sutil que es la reordenación. Las lecturas y escrituras no siempre se producen en el orden en que se ha escrito en el código y esto puede provocar problemas que llevan a confusión. En muchos algoritmos multiproceso, un subproceso escribe algunos datos y luego escribe en una flag que indica a otros subprocesos que los datos están listos. Esto se conoce como write-release. Si las escrituras se reordenan, es posible que otros subprocesos vean que la flag se ha activado antes de que puedan ver los datos escritos.

De forma similar, en muchos casos, un subproceso lee una flag y luego lee algunos datos compartidos si la flag indica que el subproceso ha obtenido acceso a los datos compartidos. Esto se conoce como read-acquire. Si se reordenan las lecturas, es posible que los datos se lean a través del almacenamiento compartido antes de la flag y que los valores vistos no estén actualizados.

El compilador y el procesador pueden realizar el reordenamiento de lecturas y escrituras. Los compiladores y procesadores han llevado a cabo esta reordenación durante años, pero en equipos de un solo procesador no planteaba apenas problemas. Esto se debe a que la reorganización en las lecturas y escrituras de la CPU es invisible en equipos con un solo procesador (con código de controlador que no forma parte de un controlador de dispositivo) y es menos probable que el compilador reorganice las lecturas y escrituras en equipos con un solo procesador.

Si el compilador o la CPU reorganizan las escrituras que aparecen en el código siguiente, es posible que otro subproceso vea que se ha creado la flag activa mientras sigue viendo los valores antiguos de x o y. Se puede producir un reorganización similar en las lecturas.

En este código, un subproceso agrega una nueva entrada al grupo de sprites:

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

En este siguiente bloque de código, otro subproceso lee el grupo de sprites:

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Para que este sistema de sprites sea seguro, es necesario evitar que el compilador y el reordenamiento de lecturas y escrituras de la CPU sean seguros.

En qué consiste la reorganización de escrituras de CPU

Algunas CPU reorganizan las escrituras para las puedan ver externamente otros procesadores o dispositivos en un orden distinto del programa. Esta reorganización nunca es visible en el código que no se basa en un único subproceso, pero puede causar problemas en el código multiproceso.

Xbox 360

Aunque la CPU de Xbox 360 no reordena las instrucciones, reorganiza las operaciones de escritura, que se completan después de las instrucciones. El modelo de memoria de PowerPC permite específicamente esta reorganización de escrituras.

Las escrituras en Xbox 360 no van directamente a la memoria caché L2. En su lugar, para mejorar el ancho de banda de escritura de la caché L2, pasan por colas de almacén y después a búferes de recopilación en almacén. Los búferes de recopilación en almacén permiten escribir bloques de 64 bytes en la caché L2 en una sola operación. Hay ocho búferes de recopilación en almacén, que permiten escribir eficazmente en varias zonas de memoria diferentes.

Normalmente, los búferes de recopilación en almacén se escriben en la memoria caché L2 según el orden de "el primero en entrar es el primero en salir" (FIFO). Sin embargo, si la línea de caché de destino de una escritura no está en la caché L2, esa escritura puede retrasarse mientras la línea de caché se captura de la memoria.

Aunque los búferes de recopilación en almacén se escriben en la caché L2 según un orden FIFO estricto, esto no garantiza que cada una de las escrituras se escriban en la caché L2 en orden. Por ejemplo, imagine que la CPU escribe en la ubicación 0x1000, luego en la ubicación 0x2000 y finalmente en la ubicación 0x1004. La primera escritura asigna un búfer de recopilación en almacén y lo coloca en la parte delantera de la cola. La segunda escritura asigna otro búfer de recopilación en almacén y lo coloca seguidamente en la cola. La tercera escritura agrega sus datos al primer búfer de recopilación en almacén, que se queda delante de la cola. Así pues, la tercera escritura termina en la caché L2 antes de la segunda escritura.

El reordenamiento causado por los búferes de recopilación en almacén es básicamente impredecible, sobre todo porque ambos subprocesos de un núcleo comparten los búferes de recopilación en almacén, lo que hace que la asignación y el vaciado de búferes de recopilación en almacén sean muy variables.

Este es un ejemplo de cómo se pueden reordenar las escrituras. Puede haber otras posibilidades.

x86 y x64

Aunque las CPU basadas en x86 y x64 reordenan las instrucciones, por lo general, no reordenan las operaciones de escritura en relación con otras escrituras. Hay algunas excepciones con la memoria combinada de escritura. Además, las operaciones de cadena (MOVS y STOS) y las escrituras de SSE de 16 bytes se pueden reordenar internamente pero, si esto no pasa, las escrituras no se reordenan entre sí.

En qué consiste la reorganización de lecturas de CPU

Algunas CPU reorganizan las lecturas para que procedan eficazmente del almacenamiento compartido en el orden que no sea del programa. Esta reorganización nunca es visible en el código que no se basa en un único subproceso, pero puede causar problemas en el código multiproceso.

Xbox 360

Los errores de caché pueden hacer que algunas lecturas se retrasen, lo que hace que las lecturas vengan de la memoria compartida desordenada y la aparición de estos errores de caché es bastante impredecible. La captura previa y la predicción de saltos también pueden hacer que los datos vengan de la memoria compartida que no está ordenada. Estos son solo algunos ejemplos de cómo se pueden reordenar las lecturas. Puede haber otras posibilidades. El modelo de memoria de PowerPC permite específicamente esta reorganización de lecturas.

x86 y x64

Aunque las CPU basadas en x86 y x64 reordenan las instrucciones, por lo general, no reordenan las operaciones de lectura en relación con otras lecturas. Las operaciones de cadena (MOVS y STOS) y las lecturas de SSE de 16 bytes se pueden reordenar internamente pero, si esto no pasa, las lecturas no se reordenan entre sí.

Otros reordenamientos

Aunque las CPU basadas en x86 y x64 no reordenan las escrituras en relación con otras escrituras o reordenan las lecturas relativas a otras lecturas, pueden reordenar las lecturas en relación con las escrituras. En concreto, si un programa escribe en una ubicación seguida de una lectura de otra ubicación, los datos de lectura podrán provenir de la memoria compartida antes de que los datos escritos lo hagan allí. Esta reordenación puede interrumpir algunos algoritmos, como los algoritmos de exclusión mutua de Dekker. En el algoritmo de Dekker, cada subproceso crea una flag para indicar que quiere entrar en la región crítica y luego comprueba la flag del otro subproceso para ver si el otro subproceso está en la región crítica o intenta entrar en ella. Este es el código inicial.

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

El problema es que la lectura de f1 en P0Acquire puede leer en el almacenamiento compartido antes de que la escritura en f0 lo haga en el almacenamiento compartido. Mientras tanto, la lectura de f0 en P1Acquire puede leer en el almacenamiento compartido antes de que la escritura en f1 lo haga en el almacenamiento compartido. El impacto real es que ambos subprocesos ponen sus flags en TRUE y ambos subprocesos ven la flag del otro subproceso como FALSE, por lo que ambos entran en la región crítica. Por tanto, aunque los problemas de la reordenación en sistemas basados en x86 y x64 son menos comunes que en Xbox 360, está claro que podrían ocurrir. El algoritmo de Dekker no funcionará sin barreras de memoria de hardware en ninguna de estas plataformas.

Las CPU basadas en x86 y x64 no reordenarán una escritura antes de una lectura anterior. Las CPU basadas en x86 y x64 solo reordenan las lecturas antes de las escrituras anteriores si tienen como destino ubicaciones diferentes.

Las CPU de PowerPC pueden reordenar las lecturas antes de las escrituras y pueden reordenar las escrituras por delante de las lecturas, siempre y cuando estén en direcciones diferentes.

Resumen de reordenación

La CPU de Xbox 360 reordena las operaciones de memoria mucho más agresivas que las CPU basadas en x86 y x64, tal como se muestra en la tabla siguiente. Para obtener más información, consulte la documentación sobre el procesador.

Actividad de reordenamiento x86 y x64 Xbox 360
Lecturas que van por delante de las lecturas No Sí
Escrituras que van por delante de las escrituras No Sí
Escrituras que van por delante de las lecturas No Sí
Lecturas que van por delante de las escrituras Sí Sí

 

Barreras read-acquire y write-release

Las construcciones principales que se usan para evitar la reordenación de lecturas y escrituras se denominan barreras read-acquire y write-release. Una read-acquire es la lectura de una flag u otra variable para obtener la propiedad de un recurso, junto con la barrera de la reordenación. Del mismo modo, una write-release es la escritura de una flag u otra variable para devolver la propiedad de un recurso, junto con la barrera de la reordenación.

Las definiciones formales, cortesía de Herb Sutter, son las siguientes:

  • Una read-acquire se ejecuta antes que todas las lecturas y escrituras en el mismo subproceso que la sigue según el orden del programa.
  • Una write-release se ejecuta después de todas las lecturas y escrituras en el mismo subproceso que lo precede según la orden del programa.

Cuando el código obtiene la propiedad de alguna bloque de memoria, ya sea mediante un bloqueo o la extracción de un elemento en una lista vinculada compartida (sin bloqueo), siempre hay una lectura que interviene, consultando una flag o puntero para comprobar si se ha obtenido la propiedad de la memoria. Esta lectura puede formar parte de una operación InterlockedXxx, en cuyo caso implica tanto una lectura como una escritura, pero es la lectura la que indica si se ha obtenido la propiedad. Después de obtener la propiedad de la memoria, los valores suelen leerse o escribirse en esa memoria y es muy importante que estas lecturas y escrituras se ejecuten después de obtener la propiedad. Una barrera read-acquire puede garantizar esto.

Cuando se libera la propiedad de alguna parte de la memoria, liberando un bloqueo o insertando un elemento en una lista vinculada compartida, siempre hay una escritura que interviene que avisa a otros subprocesos de que ya pueden acceder a la memoria. Aunque el código haya sido propiedad de la memoria, probablemente se haya leído o escrito y es muy importante que estas lecturas y escrituras se ejecuten antes de liberar la propiedad. Una barrera write-release es capaz de garantizar esto.

Es más sencillo pensar en las barreras read-acquire y write-release como operaciones únicas. Sin embargo, a veces tienen que construirse a partir de dos partes: una lectura o escritura y una barrera que no permite que las lecturas o escrituras se muevan a través de ella. En este caso, es fundamentar saber cómo se coloca la barrera. En una barrera read-acquire , la lectura de la flag viene primero, luego la barrera y, finalmente, las lecturas y escrituras de los datos compartidos. En una barrera write-release, las lecturas y escrituras de los datos compartidos vienen primero, luego la barrera y, finalmente, la escritura de la flag.

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

La única diferencia entre una read-acquire y una write-release es la ubicación de la barrera de memoria. Una read-acquire tiene la barrera después de la operación de bloqueo y una write-release tiene la barrera antes. En ambos casos, la barrera está entre las referencias a la memoria bloqueada y las referencias al bloqueo.

Para saber por qué se necesitan barreras al obtener y liberar datos, es mejor (y más preciso) pensar que estas barreras pueden garantizar la sincronización con memoria compartida, no con otros procesadores. Si un procesador usa una write-release para liberar una estructura de datos en la memoria compartida y otro procesador usa una read-acquire para tener acceso a esa estructura de datos de la memoria compartida, el código funcionará correctamente. Si alguno de los procesadores no usa la barrera adecuada, es posible que se produzca un error en el uso compartido de datos.

Es fundamental usar la barrera adecuada para evitar el reordenamiento del compilador y la CPU de la plataforma.

Una de las ventajas de usar los primitivos de sincronización que ofrece por el sistema operativo es que todos incluyen las barreras de memoria adecuadas.

Cómo impedir la reordenación del compilador

La operaciones del compilador se encargan de optimizar de forma agresiva el código para mejorar el rendimiento. Esto incluye la reorganización de instrucciones donde sea útil y dondequiera que no afecte al funcionamiento. Dado que el estándar de C++ nunca menciona los multiprocesos y, como el compilador no sabe qué código tiene que ser seguro para los subprocesos, el compilador asume que el código es de un solo subproceso al decidir qué reorganizaciones puede hacer de forma segura. Por tanto, debe indicar al compilador las veces que no se permite reordenar lecturas y escrituras.

Con Visual C++ puede evitar la reordenación del compilador mediante la función intrínseca (intrinsic) _ReadWriteBarrier del compilador. Cuando inserte _ReadWriteBarrier en el código, el compilador no moverá las lecturas y las escrituras en él.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

En el código siguiente, otro subproceso lee el grupo de sprites:

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Es importante comprender que _ReadWriteBarrier no inserta instrucciones adicionales y no impide que la CPU reorganice las lecturas y escrituras, sino que solo impide que el compilador las reorganice. Por ello, _ReadWriteBarrier es suficiente cuando se implementa una barrera de write-release en x86 y x64 (porque en x86 y x64 no se reordenan las escrituras y una escritura normal es suficiente para liberar un bloqueo), pero en la mayoría de los otros casos, es necesario evitar que la CPU reordene las lecturas y escrituras.

También puede usar _ReadWriteBarrier al escribir en memoria combinada de escritura no almacenada en caché para evitar el reordenamiento de escrituras. En este caso, _ReadWriteBarrier ayuda a mejorar el rendimiento, garantizando que las escrituras salgan en el orden lineal preferido del procesador.

También es posible usar las funciones intrínsecas _ReadBarrier y _WriteBarrier para tener un control más preciso del reordenamiento del compilador. El compilador no moverá las lecturas en una _ReadBarrier y no moverá las escrituras en una _WriteBarrier.

Cómo impedir el reordenamiento de la CPU

La reordenación de la CPU es más sutil que la reordenación del compilador. Nunca se puede ver qué sucede directamente, solo se ven errores inexplicables. Para evitar el reordenamiento de lecturas y escrituras de la CPU, se deben usar instrucciones de barrera de memoria en algunos procesadores. El nombre genérico de la instrucción de barrera de memoria, en Xbox 360 y en Windows, es MemoryBarrier. Esta macro se implementa correctamente en cada plataforma.

En Xbox 360, MemoryBarrier se define como lwsync (sincronización ligera), también disponible a través de la función intrínseca __lwsync, que se define en ppcintrinsics.h. __lwsync también actúa como barrera de memoria del compilador, lo que impide la reorganización de lecturas y escrituras por parte del compilador.

La instrucción lwsync es una barrera de memoria en Xbox 360 que sincroniza un núcleo del procesador con la caché L2. Garantiza que todas las escrituras antes de que lwsync consiga llegar a la caché L2 antes de las escrituras siguientes. También garantiza que las lecturas que sigan a lwsync no obtengan datos más antiguos en L2 que las lecturas anteriores. Un tipo de reordenación que no impide esto es que una lectura vaya por delante de una escritura a una dirección diferente. Por tanto, lwsync aplica el orden de memoria que coincide con el orden de memoria predeterminado en procesadores x86 y x64. Para conseguir toda la ordenación de memoria, se necesita usar la instrucción de sincronización más costosa (también conocida como sincronización pesada), pero en la mayoría de casos, esto no es necesario. Las opciones de reordenación de memoria en Xbox 360 figuran en la tabla siguiente.

Reordenación en Xbox 360 Sin sincronización lwsync sync
Lecturas que van por delante de las lecturas Sí No No
Escrituras que van por delante de las escrituras Sí No No
Escrituras que van por delante de las lecturas Sí No No
Lecturas que van por delante de las escrituras Sí Sí No

 

PowerPC también cuenta con las instrucciones de sincronización isync y eieio (que se usa para controlar el reordenamiento de la memoria inhibida del almacenamiento en caché). Estas instrucciones de sincronización no deberían ser necesarias en contextos de sincronización normales.

En Windows, MemoryBarrier viene definida en Winnt.h e incluye una instrucción de barrera de memoria diferente en función de si se compila para x86 o x64. La instrucción de barrera de memoria actúa como una barrera total, lo que impide que todas las lecturas y escrituras se reordenen en la barrera. Por eso, MemoryBarrier en Windows ofrece una garantía de reordenación más fiable que en Xbox 360.

En Xbox 360, y en muchas otras CPU, hay otra manera de evitar la reordenación de lecturas por parte de la CPU. Si lee un puntero y luego usa ese puntero para cargar otros datos, la CPU garantiza que las lecturas fuera del puntero no sean anteriores a la lectura del puntero. Si la flag de bloqueo es un puntero y si todas las lecturas de datos compartidos están desvinculadas del puntero, se puede omitir MemoryBarrier para optimizar el rendimiento en un cierto grado.

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

La instrucción MemoryBarrier solo impide el reordenamiento de lecturas y escrituras en memoria caché. Si asigna memoria como PAGE_NOCACHE o PAGE_WRITECOMBINE, una técnica común para editores de controladores de dispositivos y para desarrolladores de juegos en Xbox 360, MemoryBarrier no tiene ningún efecto en los accesos a esta memoria. La mayoría de desarrolladores no necesitan la sincronización de memoria no almacenable en caché. Eso va más allá del ámbito de este artículo.

Funciones de interbloqueo y reordenación de CPU

A veces, la lectura o escritura que obtiene o libera un recurso se realiza mediante una de las funciones InterlockedXxx. En Windows, esto facilita las cosas, ya que en Windows, las funciones InterlockedXxx son todas las barreras de memoria completa. Tienen efectivamente una barrera de memoria de CPU antes y después de ellas, lo que significa que son una barrera completa read-acquire o write-release por sí mismas.

En Xbox 360, las funciones InterlockedXxx no contienen barreras de memoria de CPU. Impiden el reordenamiento del compilador de lecturas y escrituras, pero no el reordenamiento de CPU. Por tanto, en la mayoría de casos cuando se usan funciones InterlockedXxx en Xbox 360, debe precederlas o seguirlas con __lwsync, para que sean una barrera read-acquire o write-release. Para que sea más cómodo y sencillo leerlas, hay versiones Acquire y Release de muchas de las funciones InterlockedXxx. Estas incluyen una barrera de memoria integrada. Por ejemplo, InterlockedIncrementAcquire realiza un incremento interbloqueado seguido de una barrera de memoria __lwsync para incluir la funcionalidad completa de read-acquire.

Se recomienda usar las versiones Acquire y Release de las funciones InterlockedXxx (la mayoría de estas están disponibles en Windows también, sin penalización de rendimiento) para hacer que la intención sea más obvia y facilitar la obtención de las instrucciones de barrera de memoria en el lugar correcto. Cualquier uso de InterlockedXxx en Xbox 360 sin una barrera de memoria debe examinarse con mucho cuidado, ya que a menudo es un error.

En este ejemplo se muestra cómo un subproceso puede pasar tareas u otros datos a otro subproceso mediante las versiones Acquire y Release de las funciones InterlockedXxxSList. Las funciones InterlockedXxxSList son una familia de funciones que sirven para mantener una lista vinculada compartida sin bloqueo. Tenga en cuenta que las variantes Acquire y Release de estas funciones no están disponibles en Windows, pero las versiones normales de estas funciones son una barrera de memoria completa en Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Variables volátiles y reordenación

El estándar de C++ establece que las lecturas de variables volátiles no se pueden almacenar en caché, no se pueden retrasar las escrituras volátiles y las lecturas y escrituras volátiles no pueden moverse de una a otra. Esto es suficiente para comunicarse con dispositivos de hardware, que es la finalidad de la palabra clave volatile en el estándar de C++.

Sin embargo, las garantías del estándar no son suficientes para usar volatile en multiprocesos. El estándar de C++ no impide que el compilador reordene las lecturas y escrituras no volátiles en relación con las lecturas y escrituras volátiles, y no dice nada al respecto sobre cómo evitar el reordenamiento de la CPU.

Visual C++ 2005 va más allá del estándar de C++ para definir la semántica compatible con varios subprocesos para acceder a variables volátiles. A partir de Visual C++ 2005, se definen las lecturas de variables volátiles para tener una semántica read-acquire y se definen escrituras en variables volátiles para tener una semántica write-release. Esto significa que el compilador no reorganizará las lecturas y escrituras después de ellas y en Windows se asegurará de que la CPU no lo haga.

Es importante saber que estas nuevas garantías solo se aplican a Visual C++ 2005 y futuras versiones de Visual C++. Los compiladores de otros proveedores suelen implementar diferentes semánticas, sin las garantías adicionales de Visual C++ 2005. Además, en Xbox 360, el compilador no inserta instrucciones para evitar que la CPU reordene las lecturas y escrituras.

Ejemplo de canalización de datos sin bloqueos

Una canalización es una construcción que permite que uno o varios subprocesos escriban datos que luego lean otros subprocesos. La versión sin bloqueos de una canalización puede ser un método elegante y eficaz para pasar las operaciones de un subproceso a otro. El SDK de DirectX incluye LockFreePipe, una canalización sin bloqueos de un solo lector y escritor que está disponible en DXUTLockFreePipe.h. El mismo LockFreePipe está disponible en el SDK de Xbox 360 en AtgLockFreePipe.h.

LockFreePipe se puede usar cuando dos subprocesos tienen una relación de productor/consumidor. El subproceso del productor puede escribir datos en la canalización para que el subproceso del consumidor los procese en una fecha posterior, sin ningún bloqueo en absoluto. Si la canalización se rellena, se genera un error en las escrituras y el subproceso del productor tendrá que volver a intentarlo más adelante, pero esto solo ocurrirá si el subproceso del productor está por delante. Si la canalización se vacía, se genera un error en las lecturas y el subproceso del consumidor tendrá que volver a intentarlo más adelante, pero esto solo ocurrirá si no hay operaciones que el subproceso del consumidor pueda realizar. Si los dos subprocesos están bien equilibrados y la canalización es lo suficientemente amplia, la canalización les permitirá pasar datos de forma fluida y sin retrasos ni bloques.

Rendimiento de Xbox 360

El rendimiento de las instrucciones y funciones de sincronización en Xbox 360 varían en función del otro código en que se esté ejecutando. La obtención de bloqueos tardará mucho más si hay otro subproceso que tiene asignado en ese momento el bloqueo. Las operaciones de InterlockedIncrement y de sección crítica tardarán mucho más si otros subprocesos están escribiendo en la misma línea de caché. El contenido de las colas en almacén también puede afectar al rendimiento. De ahí que todos estos números son solo aproximaciones, generados a partir de pruebas muy sencillas:

  • lwsync se midió según unos 33-48 ciclos.
  • InterlockedIncrement se midió según unos 225-260 ciclos.
  • La obtención o liberación de una sección crítica se midió según unos 345 ciclos.
  • La obtención o liberación de una exclusión mutua se midió según unos 2350 ciclos.

Rendimiento de Windows

El rendimiento de las instrucciones y funciones de sincronización en Windows cambian bastante según el tipo de procesador y la configuración y con qué otro código se está ejecutando. Los sistemas con varios núcleos y varios sockets suelen tardar más tiempo en ejecutar instrucciones de sincronización y se tarda mucho más en obtener bloqueos si otro subproceso tiene asignado el bloqueo.

Sin embargo, hay algunas medidas generadas a partir de pruebas muy sencillas que son útiles:

  • MemoryBarrier se midió según unos 20-90 ciclos.
  • InterlockedIncrement se midió según unos 36-90 ciclos.
  • La obtención o liberación de una sección crítica se midió según unos 40-100 ciclos.
  • La obtención o liberación de una exclusión mutua se midió según unos 750-2500 ciclos.

Estas pruebas se realizaron en Windows XP en varios tipos de procesadores. Los tiempos más cortos se producían en un equipo con un solo procesador y los tiempos más largos se producían en un equipo con varios procesadores.

Aunque la obtención y liberación de bloqueos cuesta más que la programación sin bloqueos, es aún mejor compartir datos con menos frecuencia, evitando así todos los costes.

Cuestiones sobre el rendimiento

La obtención o liberación de una sección crítica consta de una barrera de memoria, una operación InterlockedXxx y algunas comprobaciones adicionales para controlar la recurrencia y volver a una exclusión mutua, si es necesario. Debe tener cuidado con la implementación de su propia sección crítica, ya que si se gira en un bucle esperando a que se libere un bloqueo, sin volver a una exclusión mutua, el rendimiento puede verse afectado significativamente. En el caso de las secciones críticas que se sostienen de forma sólida, pero que no se mantienen durante mucho tiempo, se debe considerar el uso de InitializeCriticalSectionAndSpinCount para que el sistema operativo gire durante un tiempo esperando a que la sección crítica esté disponible, en lugar de posponer inmediatamente una exclusión mutua si la sección crítica ya es propiedad de otro cuando intenta obtenerla. Para identificar secciones críticas que pueden beneficiarse del número de giros, es necesario medir la duración de la espera típica de un bloqueo determinado.

Si se usa un montón compartido para las asignaciones de memoria (la acción predeterminada), cada asignación de memoria y libre implica obtener un bloqueo. A medida que aumenta el número de subprocesos y el número de asignaciones, los niveles de rendimiento paran y empiezan a decaer. El uso de montones por subproceso o la reducción del número de asignaciones puede evitar este cuello de botella de bloqueos.

Si un subproceso genera datos y otro subproceso consume datos, es posible que terminen compartiendo datos con frecuencia. Esto puede ocurrir si un subproceso está cargando recursos y otro subproceso renderiza la escena. Si el subproceso de renderización hace referencia a los datos compartidos en cada llamada de dibujado, la sobrecarga de bloqueo será alta. Se puede conseguir un rendimiento mucho mejor si cada subproceso tiene estructuras de datos privadas que se sincronizan una vez por fotograma o menos.

No se garantiza que los algoritmos sin bloqueos sean más rápidos que los algoritmos que usan bloqueos. Debe comprobar si los bloqueos causan problemas de verdad antes de intentar evitarlos y debe verificar si el código sin bloqueos mejora el rendimiento de forma efectiva.

Resumen de diferencias entre plataformas

  • Las funciones InterlockedXxx impiden la reordenación de lecturas y escrituras de CPU en Windows, pero no en Xbox 360.
  • La lectura y escritura de variables volátiles con Visual Studio C++ 2005 impide la reordenación de lecturas y escrituras de CPU en Windows, pero en Xbox 360, donde solo se impide la reordenación de lecturas y escrituras del compilador.
  • Las escrituras se reordenan en Xbox 360, pero no en sistemas x86 o x64.
  • Las lecturas se reordenan en Xbox 360, pero en sistemas x86 o x64 solo se reordenan en relación con las escrituras y solo si las lecturas y escrituras tienen como destino ubicaciones diferentes.

Recomendaciones

  • Use bloqueos siempre que sea posible porque son más fáciles de usar correctamente.
  • Evite los bloqueos con excesiva frecuencia, de modo que no incurra en costes altos por bloqueos.
  • Evite mantener los bloqueos durante demasiado tiempo con el fin de evitar pausas largas.
  • Use la programación sin bloqueos cuando corresponda, pero asegúrese de que las ventajas justifican la complejidad.
  • Use bloqueos de giro o programación sin bloqueos en situaciones en las que se prohíban otros bloqueos, como cuando se comparten datos entre llamadas a procedimientos diferidos y código normal.
  • Use solo los algoritmos de programación estándar sin bloqueos que han demostrado ser los apropiados.
  • Al realizar la programación sin bloqueos, asegúrese de usar las variables de flag volátiles y las instrucciones de barrera de memoria según sea necesario.
  • Al usar InterlockedXxx en Xbox 360, use las variantes Acquire y Release.

Referencias