Condición de carrera en C++
- ¿Qué son los hilos?
- ¿Qué es una condición de carrera?
- Evitar condición de carrera
- Evite la condición de carrera usando Mutex
- Evitar la condición de carrera usando el semáforo
- Conclusión
En este tutorial, aprenderemos sobre el concepto de una condición de carrera. Primero, haremos una introducción a los hilos y luego discutiremos la condición de carrera en los hilos con ejemplos.
Por último, veremos soluciones para evitar/controlar la condición de carrera.
¿Qué son los hilos?
Los hilos son procesos ligeros. Los procesos pueden tener varios subprocesos, que comparten muchos recursos del proceso.
Los hilos están destinados a cooperar; por lo tanto, comparten memoria/variables entre otros recursos.
Los subprocesos se utilizan para ejecutar tareas simultáneas dentro de un proceso. Por ejemplo, un proceso de procesamiento de MS Word tiene múltiples tareas realizadas simultáneamente.
Estas tareas incluyen ortografía, gramática, guardado automático, etiquetado de palabras clave, sangría y formato. Podemos usar subprocesos separados para ejecutar estas tareas simultáneas al mismo tiempo.
Clasificación e impresión simultáneas
Aquí, discutiremos un ejemplo de codificación para comprender mejor los hilos. Supongamos que tenemos que ordenar e imprimir muchos valores.
Primero, debemos ordenarlos por completo antes de poder imprimirlos.
Sin embargo, existen algunas técnicas de clasificación como clasificación de selección, que clasifica los números de tal manera que en cada iteración obtendremos elementos más pequeños al comienzo de la lista. Por lo tanto, podemos comenzar a imprimir en paralelo.
Aquí está el código:
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define SIZE 1000
int x[SIZE];
void init() {
int i;
for (i = 0; i < SIZE; i++) x[i] = rand() % 1000;
}
void* print(void* a) {
int i;
for (i = 0; i < SIZE; i++) printf("%d ", x[i]);
printf("\n");
}
void* sort(void* b) {
int i, j, temp;
for (i = 0; i < SIZE - 1; i++)
for (j = SIZE - 1; j >= 1; j--)
if (x[j] < x[j - 1]) {
temp = x[j];
x[j] = x[j - 1];
x[j - 1] = temp;
}
}
int main() {
srand(time(0));
init();
pthread_t tSort, tPrint;
pthread_create(&tSort, NULL, sort, NULL);
pthread_create(&tPrint, NULL, print, NULL);
pthread_join(tSort, NULL);
pthread_join(tPrint, NULL);
return 0;
}
En este código, las funciones ordenar e print se ejecutan en paralelo; sin embargo, si ve el resultado, no será correcto.
La razón es que el subproceso de clasificación es más lento que el subproceso de impresión y no hay sincronización entre ellos. Por lo tanto, el subproceso de impresión imprime rápidamente valores que aún no están ordenados; por lo tanto, la salida no está ordenada.
Un programa de subprocesos múltiples es propenso a estos problemas de sincronización y algunos otros problemas. A continuación, discutiremos uno de esos problemas llamado condición de carrera.
¿Qué es una condición de carrera?
Una condición de carrera es una condición no deseada que puede ocurrir cuando varios procesos o subprocesos acceden a algunos datos compartidos simultáneamente.
El valor final depende del proceso/hilo que acceda a los datos al final. Expliquémoslo con un ejemplo.
Supongamos que tenemos dos hilos, A y B, y una variable compartida x. Ambos subprocesos ejecutan una instrucción x++ en paralelo.
Si examina críticamente esta instrucción en un lenguaje de bajo nivel, esta instrucción se compone de tres instrucciones. Las tres instrucciones son:
read x inc x write x
La primera instrucción lee la variable de la memoria en un registro (dentro del procesador). En la segunda instrucción, una variable se incrementa en 1 y el resultado está en un registro.
La variable se vuelve a escribir en la memoria en la tercera y última instrucción.
Supongamos que dos subprocesos ejecutan estas instrucciones en paralelo. No tenemos idea de su secuencia de ejecución; depende de varios factores como el algoritmo de programación, el intervalo de tiempo, la prioridad de los procesos y el conjunto de procesos en ejecución/nuevos, etc.
Es posible que tengamos múltiples secuencias posibles ejecutando estas instrucciones, y cada vez puede ocurrir una secuencia diferente. Por ejemplo, el subproceso A puede ejecutar las dos primeras instrucciones y el sistema operativo cambia el contexto.
Supongamos que el valor de la variable es 5, el hilo A ha leído 5 y lo ha incrementado en 1, por lo que ahora el valor es 6 (pero dentro del registro). Cuando el contexto cambia y el hilo B comienza su ejecución, también leerá el mismo valor, 5.
El hilo B incrementará el valor en 1. El valor pasa a ser 6.
El hilo B completa la última instrucción y escribe un valor 6 en la memoria.
El contexto cambia de nuevo y el control finalmente llega al subproceso A; ahora, el hilo A ejecutará la última instrucción, escriba x.
Recuerde que el hilo A ha leído el valor 5 y lo incrementa en 1. El subproceso A también escribirá 6 en la memoria.
Como resultado, el valor será 6 en lugar de 7 porque dos subprocesos han realizado la operación de incremento y el valor debería ser 7. Por lo tanto, debido a un cambio de contexto inesperado, el resultado es incorrecto.
Problema productor-consumidor
Veamos el siguiente ejemplo de codificación antes de discutir el problema Productor-Consumidor.
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
void* producer(void* arg) {
for (int i = 0; i < 50000; i++) count++;
}
void* consumer(void* arg) {
for (int i = 0; i < 50000; i++) count--;
}
int main() {
pthread_t tid1, tid2;
printf("Count = %d\n", count);
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("Count = %d\n", count);
return 0;
}
Este código demuestra el problema clásico del sistema operativo denominado problema productor-consumidor. Este código tiene una variable global (compartida) contar, inicializada por 0.
La función productor incrementa la cuenta en 1, y la función consumidor decrementa la cuenta en 1.
Sin embargo, ambas funciones son ejecutadas por dos subprocesos diferentes, donde el cambio de contexto puede ocurrir en cualquier momento. Puede experimentar esto fácilmente ejecutando el código.
Si no hay condición de carrera, el resultado debería ser 0 porque ambas funciones incrementan y decrementan el mismo número de veces. El incremento y decremento de la unidad significa que el valor de la cuenta debe ser cero al final.
Sin embargo, cuando ejecute este código, observará que el valor no es cero. Más bien, aparecerán diferentes valores en cada iteración, lo que muestra claramente que la programación es impredecible.
Algunos ejemplos prácticos de productor-consumidor
El ejemplo de incremento de los dos subprocesos discutidos anteriormente no es un problema hipotético; muchos de estos escenarios prácticos existen cuando se trabaja con subprocesos múltiples.
Por ejemplo, en el sistema bancario, un cliente tiene dos opciones para retirar una cantidad. Una es presentar un cheque al banco, mientras que, en paralelo, alguien puede retirar el monto del cajero automático utilizando la tarjeta del cajero automático del cliente.
De manera similar, es posible que dos o más profesores, por casualidad, actualicen/publiquen las calificaciones de los mismos estudiantes, lo que a su vez aumenta/disminuye las calificaciones totales de los estudiantes. Dos o más empresas pueden deducir simultáneamente la suscripción semanal, mensual o anual del cliente.
La condición de carrera puede dar lugar a resultados incorrectos, lo que no es asequible. Por lo tanto, ¿deberíamos anunciar que debido a problemas de condiciones de carrera, la aplicabilidad de subprocesos múltiples no es práctica en muchos escenarios?
No, tenemos la solución para evitar/controlar la condición de carrera.
Evitar condición de carrera
Tenemos soluciones de hardware y software para condiciones de carrera. La solución de hardware es proporcionar instrucciones atómicas relacionadas como parte del conjunto de instrucciones de la CPU (por ejemplo, CMPXCHG en la arquitectura x86).
La solución de software utiliza mutex o semáforos para regularizar la entrada del proceso a las secciones críticas.
operación atómica
El fabricante puede implementar operaciones atómicas en el hardware. Después de implementar la operación atómica en el hardware, dicha instrucción completará su ejecución sin cambiar de contexto. En otras palabras, la ejecución del proceso/subproceso no debe dividirse en partes.
Sin embargo, esta solución es para fabricantes y no es posible implementarla por usuarios comunes.
Exclusión mutua
Una exclusión mutua significa que si un proceso/subproceso está accediendo a alguna variable compartida, entonces ningún otro proceso/subproceso debe tener acceso a la variable compartida que ya tiene otro proceso/subproceso.
La exclusión mutua se puede implementar mediante un mutex (bloqueo) o un semáforo. Puede hacer clic para leer sobre Mutex vs. Semaphore para aclarar los conceptos.
Evite la condición de carrera usando Mutex
Mutex es un concepto de bloqueo especial. Este bloqueo se comparte entre subprocesos; sin embargo, si varios subprocesos desean bloquear la exclusión mutua, solo un (primer) subproceso logrará bloquear y entrar en la sección crítica.
Los subprocesos restantes que intentan bloquear la exclusión mutua se bloquearán hasta que el primer subproceso salga de la sección crítica y desbloquee la exclusión mutua.
Un mutex desbloqueado puede ser bloqueado por un subproceso en cualquier momento. Al desbloquear el mutex, cualquiera de los subprocesos de bloqueo puede tener la oportunidad de bloquear el mutex y entrar en la sección crítica.
No hay concepto de la cola en mutex. Cualquiera de los subprocesos de bloqueo/espera puede tener la oportunidad de obtener el mutex y bloquearlo.
Es una solución muy simple y extremadamente útil cuando tenemos dos subprocesos en condiciones de carrera o múltiples subprocesos en condiciones de carrera, y no hay problema de turno/cola.
Realicemos la solución usando el siguiente ejemplo en C implementando un bloqueo mutex usando la biblioteca de Linux pthread.
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
pthread_mutex_t lock;
void* producer(void* arg) {
for (int i = 0; i < 50000; i++) {
pthread_mutex_lock(&lock);
count++;
pthread_mutex_unlock(&lock);
}
}
void* consumer(void* arg) {
for (int i = 0; i < 50000; i++) {
pthread_mutex_lock(&lock);
count--;
pthread_mutex_unlock(&lock);
}
}
int main() {
pthread_t tid1, tid2;
printf("Count = %d\n", count);
pthread_mutex_init(&lock, NULL);
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
pthread_mutex_destroy(&lock);
printf("Count = %d\n", count);
return 0;
}
Puede ejecutar este código varias veces. Cada vez, dará el valor de cuenta 0.
El código tiene un bloqueo de variable compartida de un tipo especial, pthread_mutex_t. Las funciones de productor y consumidor se bloquean antes de ejecutar las instrucciones de la sección crítica contar++ y contar--.
Nuevamente, ambos liberan mutex llamando a la función de desbloqueo después del final de su sección crítica.
En la función main, estamos inicializando mutex y destruyendo mutex después del uso de mutex.
Evitar la condición de carrera usando el semáforo
Semaphore es una solución proporcionada por el sistema operativo. Semaphore es una solución para la sincronización de subprocesos.
Podemos querer alguna secuencia específica de ejecución de instrucciones; sin embargo, podemos usarlo para evitar condiciones de carrera, pero no es una solución exacta; más adelante, discutiremos por qué.
Aquí, estamos evitando el tema largo y detallado de la sincronización y avanzando hacia el uso de semáforos para evitar condiciones de carrera. Usar un semáforo es detener el hilo en algún punto específico y esperar una señal de otro hilo.
Inicializaremos el semáforo en cero y llamaremos a la función de espera, disminuyendo el semáforo en 1 y entrando en estado de suspensión.
Más tarde, otro hilo llamará a la operación de señal, incrementando el semáforo en 1 y despertando algún hilo durmiente en la cola.
En Linux, el semáforo está disponible en la biblioteca semaphore.h. Tenemos funciones de espera y publicación para las operaciones de espera y señal.
Ver el código:
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
int count = 0;
sem_t semaphore1, semaphore2;
void* producer(void* arg) {
for (int i = 0; i < 50000; i++) {
count++;
sem_post(&semaphore1);
sem_wait(&semaphore2);
}
}
void* consumer(void* arg) {
for (int i = 0; i < 50000; i++) {
sem_wait(&semaphore1);
count--;
sem_post(&semaphore2);
}
}
int main() {
pthread_t tid1, tid2;
printf("Count = %d\n", count);
sem_init(&semaphore1, 0, 0);
sem_init(&semaphore1, 0, 0);
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
sem_destroy(&semaphore1);
sem_destroy(&semaphore2);
printf("Count = %d\n", count);
return 0;
}
Nuevamente, puede ejecutar este código y obtener el valor exacto/correcto de una variable compartida. La implementación es similar a un mutex; sin embargo, una diferencia importante es el paso de inicialización.
Hay tres parámetros en la función de inicialización. La primera es la variable semáforo.
El segundo es 0 o 1. Aquí, 0 significa que el semáforo se comparte entre subprocesos del mismo proceso, mientras que 1 significa que el semáforo se comparte entre subprocesos de diferentes procesos.
El tercer parámetro es el valor del semáforo; si desea que varios subprocesos (pero limitados a algún conteo) puedan ingresar juntos en la sección crítica, puede inicializar el valor del semáforo con el conteo.
La segunda diferencia en esta implementación es que estamos usando dos semáforos, mientras que usamos solo un candado en el caso del mutex.
El código mutex coloca el bloqueo antes de usar una variable compartida y libera el bloqueo después de usar una variable compartida. Cada vez que un cliente va a operar un casillero en el vestuario del banco, el personal le da una llave al cliente para cerrar el casillero antes de abrir el casillero y abrir el vestuario después de que el casillero esté cerrado.
Sin embargo, en semáforo, usamos dos semáforos; ambos se inicializan en 0, lo que significa que la espera del subproceso de llamada se bloqueará hasta que algún otro subproceso dé una señal. Aquí, el consumidor está esperando el semáforo 1, señalado por el hilo del productor, después de incrementar el conteo.
Al mismo tiempo, el subproceso productor está esperando el semáforo 2, que debe ser señalado por el subproceso consumidor después de disminuir la cuenta.
De esta forma, el productor y el consumidor incrementarán y disminuirán el conteo uno por uno, lo cual es sincronización. Usando semáforo, mantenemos el conteo correcto; sin embargo, restringimos los subprocesos para que se ejecuten en secuencia.
En el caso de mutex, ambos subprocesos pueden ejecutarse en cualquier secuencia sin afectar el valor de la cuenta variable compartida.
Conclusión
Los hilos son muy útiles para ejecutar códigos/funciones en paralelo; sin embargo, hay algunos problemas con los subprocesos, como una condición de carrera. La condición puede causar resultados inesperados.
Afortunadamente, podemos usar bloqueos mutex y semáforos para evitar condiciones de carrera. La forma mejor y correcta de manejar las condiciones de carrera es un mutex.