6 Sincronización¶

Sincronización de tareas¶

En sistemas concurrentes, podemos hablar de sincronización como la coordinación de dos o más tareas para obtener el resultado deseado. Tenemos dos tipos de sincronización:

Sincronización de acceso a datos: Cuando dos o más tareas tienen acceso a una variable compartida y en un momento dado sólo una de las tareas debería estar accediendo a ella. Se dice que un determinado código es thread-safe (seguro para uso con hilos) si está protegido por mecanismos de sincronización que aseguran el acceso concurrente a los datos (o los objetos son inmutables y por tanto no hay problema con acceder concurrentemente a ellos).
Sincronización de control: Cuando, por ejemplo, la continuidad de la ejecución de una tarea depende de la terminación de otra tarea.

Exclusión mutua¶

Bernstein determinó que dos conjuntos de instrucciones pueden ejecutarse concurrentemente siempre y cuando cumplan las siguientes condiciones:

Que no haya intersección entre el conjunto de variables leídas por el conjunto de instrucciones 1 y el conjunto de variables escritas por el conjunto de instrucciones 2 (y viceversa).
Que no haya intersección entre el conjunto de variables escritas por el conjunto de instrucciones 1 y el conjunto de variables escritas por el conjunto de instrucciones 2.

Empecemos con la primera condición. Se pueden producir conflictos si un hilo está leyendo un objeto compartido mientras otro hilo lo está escribiendo, porque el objeto compartido puede quedar en un estado inconsistente.

Para demostrarlo, supongamos que dos procesos en ejecución comparten memoria y ambos quieren ejecutar la instrucción x = x + 1. Cuando dicha instrucción se traduce a lenguaje ensamblador se convierte en tres instrucciones independientes:

Cargar desde memoria el valor de x en un registro (LOAD X R1).
Incrementar el valor del registro (ADD R1 1).
Almacenar el contenido del registro en la posición de memoria de x (STORE R1 X).

Como hemos dicho anteriormente, no podemos determinar de antemano el orden exacto en el que se ejecutarán ambos procesos. Esto implica que es posible que exista algún orden de ejecución entrelazado de las 6 líneas de código (las 3 de cada proceso) que NO produzca el valor esperado. En principio el resultado de ejecutar ambos procesos concurrentemente debería de producir un incremento de dos unidades en la variable x, sin embargo existen trazas (ordenes de ejecución) que harán que se pierda uno de los incrementos, por ejemplo si ambas instrucciones LOAD X R1 se ejecutan antes de cualquiera de las instrucciones ADD R1 1.

El motivo por el que ambos procesos no puedan ejecutarse concurrentemente es que no cumplen las condiciones de Bernstein, ya que existe solapamiento entre el conjunto de variables que escriben. El problema radica en que dos procesos distintos están accediendo al mismo tiempo a una variable compartida entre ambos para actualizarla. Pero ¿qué ocurriría si esas tres instrucciones en ensamblador se ejecutaran seguidas de forma indivisible en un solo paso, sin ningún tipo de intercalado con las instrucciones del otro proceso? La respuesta es que no se habría producido el problema.

La secuencia de instrucciones que queremos que se ejecute de forma indivisible se denomina sección crítica. Se llama así porque es crítico que dicha sección de código se ejecute de forma atómica, indivisible.

La segunda condición de Berntein establece que se pueden producir conflictos si varios hilos escriben el mismo objeto compartido, porque el resultado pueden ser inconsistente. Estos problemas pueden ocurrir en procesadores con varios núcleos que trabajen con cachés para cada núcleo que permitan la carga y almacenamiento de valores sin asegurar que no estén siendo actualizados en otro núcleo (ver).

Como consecuencia de estos conflictos, el de lectura-escritura y el de escritura-escritura, deberemos establecer algún mecanismo para que cuando un proceso inicie la ejecución de una sección crítica, dicha ejecución se realice en exclusión mutua, es decir que ningún otro proceso pueda ejecutar concurrentemente instrucciones problemáticas para con la sección crítica.

Se denomina exclusión mutua porque no podemos determinar de antemano cuál de los dos procesos ejecutarán dichas instrucciones antes, pero lo que sí podemos asegurar es que en cuanto el primero que llegue comience la ejecución de la sección crítica el otro quedará excluido hasta que el primero termine de ejecutarla. Al fin y al cabo son dos procesos compitiendo por un recurso común, que se concederá primero a uno o a otro, dependiendo del orden de ejecución, pero NO a los dos a la vez. A esta competición por acceder a la sección crítica se le conoce como lock contention.

Los lenguajes de programación que nos permiten crear programas concurrentes proporcionan distintos mecanismo que nos permitan asegurar la exclusión mutua.

Condición de Sincronización¶

Otro de los problemas inherentes a la programación concurrente es el hecho de que un recurso compartido por varios procesos, y por tanto protegido por exclusión mutua, como por ejemplo una estructura de datos como un array o una cola, se encuentre en un estado en el que un proceso que ha conseguido entrar en la sección crítica no pueda llevar a cabo una determinada acción con la estructura de datos hasta que no cambie su estado. Es decir, que el proceso no puede continuar hasta que no se cumpla una determinada condición de sincronización. El principal inconveniente es que mientras no se dé dicha condición, el proceso sigue estando en la sección crítica y el recurso permanece inaccesible a otros procesos por exclusión mutua.

El problema se agrava aún más si para que se cumpla dicha condición de sincronización es imprescindible que otro proceso pueda ejecutar una sección crítica que acceda al mismo recurso (estructura de datos), lo cual es imposible dado que el primero proceso no ha abandonado la sección crítica y por tanto el recurso está en exclusión mutua. Este hecho se conoce como el problema de productor-consumidor.

La solución a este problema consiste en que el lenguaje de programación proporcione mecanismos que permitan suspender temporalmente la ejecución de un proceso que esté a la espera de que se cumpla la condición de sincronización, lo que hará que se libere el recurso protegido por la sección crítica. Cuando se produzca algún evento que haga que la condición de sincronización se cumpla, se deberá notificar al proceso que había sido suspendido, para que compita de nuevo por el recurso y si lo obtiene pueda continuar la ejecución de su sección crítica y finalmente abandonarla, liberando el recurso correspondiente.