Sistemas Operativos

Para ilustrarlo, veamos un problema clásico de concurrencia: el problema del productor-consumidor.

Supongamos que dos hilos o procesos comparten una región de la memoria que contiene un vector de elementos y un contador con el número de elementos del vector.

El primer hilo realiza varias tareas, que no entraremos a describir. Lo importante es que, como resultado de esas tareas, en ocasiones añade un elemento al vector e incrementa el contador que indica el número de elementos en el vector. Es decir, el primer hilo actúa como un productor de elementos del vector.

A continuación mostramos una porción de la función del productor:

El segundo hilo también realiza varias tareas que no describiremos. Pero para realizar esas tareas en ocasiones debe tomar un elemento del vector compartido, decrementando el contador para indicar que ahora hay un elemento menos en el vector. Es decir, el segundo hilo actúa como un consumidor de elementos del vector.

A continuación mostramos una porción de la función del consumidor:

Aunque el código anterior del productor y del consumidor es correcto cuando no coinciden en el tiempo al ejecutarse, no funciona adecuadamente cuando sí lo hacen. El motivo es que los dos hilos comparten y modifican la variable count.

Obviamente, las sentencias ++count y --count pueden modificar count al mismo tiempo si los hilos se ejecutan en núcleos diferentes en máquinas multiprocesador o multinúcleo. Eso también puede ocurrir en máquinas monoprocesador con sistemas operativos con planificación expropiativa (véase el Apartado 14.1) dado que en esos sistemas un hilo puede ser interrumpido en cualquier momento para dar paso a la ejecución de otro.

Por ejemplo, ++count podría dividirse por el compilador en las siguientes operaciones, al generar las instrucciones del procesador:

Donde registro1 representa un registro de la CPU. De forma parecida la sentencia --count podría ser implementada de la siguiente manera:

Donde nuevamente registro2 representa un registro de la CPU.

En sistemas monoprocesador, el que las sentencias ++count y --count se ejecute de forma concurrente, es similar a que las instrucciones de lenguaje máquina de ambas sentencias en ambos hilos o procesos se entrelacen en algún orden aleatorio.

Por ejemplo, un posible entrelazado de las instrucciones en lenguaje máquina entre hilos, suponiendo que inicialmente count = 5, podría ser el siguiente:

Como se puede apreciar, hemos llegado a estos valores incorrectos porque hemos permitido la manipulación concurrente de la variable count. Según como se entrelacen las instrucciones de ++count y --count en la CPU, el resultado final podría ser: 4, 5 o 6. Sin embargo, el único resultado correcto es 5, que es el que obtendremos si ejecutamos las sentencias secuencialmente, sin mezclar las operaciones en las que se dividen.

Obviamente, el problema comentado no aparece solo en sentencias simples, sino también en bloques de código destinados a hacer tareas complejas, como manipular estructuras de datos.

Por ejemplo, supongamos que vector no es un simple array de elementos, sino una lista enlazada, de tal forma que ahora extraer un elemento sería así:

y el método extract() tendría que dar los siguientes pasos:

Esto genera varios momentos cruciales en torno al paso 3, que puedan dar lugar a condiciones de carrera. Por ejemplo, si el hilo es interrumpido tras guardar el puntero al nodo en una variable local y llega otro hilo que extrae —y destruye— antes ese mismo nodo, el puntero ya no es válido —es un dangling pointer o referencia colgante— al continuar la ejecución del primer hilo. Y lo mismo ocurre con el puntero al nodo previo o al siguiente, si el hilo es interrumpido y otro hilo destruye antes alguno de ellos.

Los problemas que esto puede causar son diversos, según el momento exacto en el que ocurra. Puede haberlos al intentar leer el elemento guardado en el nodo en el paso 4, porque este último ya no exista. También, al intentar actualizar, en el paso 3, el puntero al siguiente nodo en el nodo previo, porque el nodo previo no exista. Incluso puede que la función termine con aparente normalidad, pero dejando que el nodo previo apunte a un nodo siguiente que no existe. En este último supuesto, la lista quedaría en estado inconsistente y así el problema se lo encontraría el próximo hilo que intente usarla.

Para evitar que estas situaciones lleven a la corrupción de datos y a caídas de servicios y sistemas, debemos asegurarnos que solo un hilo en cada momento puede manipular recursos y variables compartidas. Por tanto, necesitamos algún tipo de mecanismo de sincronización para que mientras se ejecuta ++count no se pueda ejecutar --count en otro hilo, ni viceversa. O para que mientras un hilo haga un insert() o un extract() en una lista, otro no pueda utilizar ni estas ni otras funciones de la misma clase.

Para resolver esto, debemos empezar buscando las secciones críticas de nuestro código. Una sección crítica es una porción del código donde se accede a variables, tablas, listas, archivos y otros recursos compartidos.

Para evitar condiciones de carrera, el acceso a las secciones críticas debe ser controlado, de manera que cuando un hilo se esté ejecutando en una sección de este tipo ningún otro pueda hacerlo en la suya correspondiente para manipular los mismos recursos. En estos casos se dice que existe exclusión mutua entre las secciones críticas.

Las condiciones de carrera son el principal problema del código anterior del productor y el consumidor, pero no el único. En ambos ejemplos se usan bucles para que el hilo espere si el vector está lleno o vacío, antes de continuar. A esta técnica se la denomina espera ocupada o espera activa y está completamente desaconsejada usarla en código del espacio de usuario, porque contribuye a gastar tiempo de CPU inútilmente.

En su lugar, se recomienda usar mecanismos de sincronización ofrecidos por el sistema operativo; diseñados para que un hilo o proceso notifique eventos a otro, de tal forma que hasta que eso ocurre, el que espera permanezca en estado esperando, dejando la CPU para los hilos que la necesitan.

El problema de la sección crítica puede ser resuelto de forma sencilla en un sistema monoprocesador.

Como el núcleo del sistema operativo es un software controlado mediante interrupciones, basta con que los hilos bloqueen las interrupciones mientras se está dentro de la sección crítica. Así, el sistema operativo no puede tomar el control y asignar otro hilo a la CPU, lo que impide que se ejecute otra secuencia de instrucciones que podría modificar los datos compartidos.

Indudablemente esta solución no es práctica en sistema multiprocesador, donde hay varios procesadores ejecutándose a la vez.

Las CPU modernas disponen de instrucciones para comparar y modificar el contenido de una variable o intercambiar el contenido de dos variables, de forma atómica. El término atómico hace referencia a que las operaciones se ejecutan como una unidad ininterrumpible. No importa que varias CPU ejecuten estas instrucciones simultáneamente, puesto el hardware se encargará de que sean ejecutadas secuencialmente en algún orden arbitrario.

Estas instrucciones están disponibles para los programadores de C y C++ a través de tipos especiales. Por ejemplo, en C11 <stdatomic.h> define tipos como: atomic_bool, atomic_uint o atomic_char para declarar variables atómicas de los tipos bool, unsigned int y char, respectivamente. También declara funciones para inicializar, leer, guardar, intercambiar, sumar, restar y realizar operaciones lógicas, de forma atómica sobre estas variables:

En C++11, <atomic> declara la plantilla std::atomic que ofrece una funcionada similar:

La importancia de estas instrucciones está en que pueden ser utilizadas por el sistema operativo para ofrecer soluciones sencillas al problema de la sección crítica. Por ejemplo, semáforos o mutex.

Tanto el estándar POSIX como Windows API soportan semáforos y ambos admiten dos tipos de semáforos:

En el ejemplo anom-shared-memory.cpp de comunicación mediante memoria compartida, se usa un semáforo para que el proceso hijo indique al proceso padre que ha terminado de calcular el factorial y el resultado ya está en la memoria.

En shared-memory.cpp está el ejemplo completo de un programa que muestra periódicamente la hora del sistema y que puede ser controlado remotamente, mediante memoria compartida, con un programa como el de shared-memory-control.cpp.

Para enviar los mensajes entre ambos programas, en la memoria compartida se reserva hueco para un búfer, en el que el programa de control copia el comando que quiere enviar, y para dos semáforos:

El detalle de cómo ambos programas usan los semáforos, se puede ver en el código de shared-memory-control.cpp y shared-memory.cpp, respectivamente.

Finalmente, para resolver el problema del productor-consumidor tenemos que considerar que:

En pthreads-sync-factorial.cpp se puede estudiar el código completo de un ejemplo similar a pthreads.cpp, donde se calculaba el factorial de un número, repartiendo la tarea entre dos hilos, usando la API de POSIX Threads. La diferencia es que ahora los hilos no retornan el resultado, sino que cada uno lo mete en un vector compartido. Al terminar, el hilo principal recorre el vector multiplicando los resultados parciales.

Como ahora ambos hilos acceden a una estructura de datos compartida, esta debe ir protegida por un mutex:

Antes de meter un nuevo valor, cada hilo debe adquirir el mutex:

En pthreads-sync-counter.cpp se puede observar un ejemplo más simple donde dos hilos intentan incrementar un contador. El resultado es correcto siempre que cada hilo adquiera el mismo mutex antes del incremento:

En threads-sync-counter.cpp y threads-sync-factorial.cpp se puede ver ejemplos equivalentes pero usando std::thread y std::mutex, de la librería estándar de C++.

Vamos a intentar resolver el problema del productor-consumidor sin usar semáforos. Para lo que, nuevamente, tenemos que considerar que:

Una función es reentrante puede ser interrumpida en medio de su ejecución y, mientras espera, volver a ser llamada con total seguridad. Obviamente las funciones recursivas deben ser reentrantes para poder llamarse a sí mismas una y otra vez con seguridad.

En el contexto de la programación multihilo, ocurre una reentrada cuando durante la ejecución de una función por parte de un hilo, este es interrumpido por el sistema operativo para planificar posteriormente a otro del mismo proceso que invoca la misma función.

En general una función es reentrante, si:

Como hemos mencionado anteriormente, los manejadores de señal deben ser funciones reentrantes.

Una función es segura en hilos o thread-safe si al manipular estructuras compartidas de datos lo hace de tal manera que se garantiza la ejecución segura de la misma por múltiples hilos al mismo tiempo. Obviamente estamos hablando de un problema de secciones críticas, por lo que las funciones lo resuelven sincronizando el acceso a estos datos mediante el uso de semáforos, mutex u otros recursos similares ofrecidos por el sistema operativo.

A la hora de usar una función o librería que va a ser llamada desde múltiples hilos, primero debemos consultar la documentación para averiguar si es segura en hilos. Si no lo fuera, tendríamos que buscar funciones alternativas o recordar proteger las llamadas a las funciones no seguras con mecanismos de sincronización, para asegurar que solo son invocadas desde un hilo al mismo tiempo.

Esto se aplica tanto a librerías de otros desarrolladores como a la librería estándar del lenguaje que estemos usando y a la librería del sistema.