# Sincronización de procesos --- ## Procesos independientes vs cooperantes --- ## Problema del productor-consumidor - Es un problema recurrente en informática. - Es necesario sincronizar el proceso consumidor y el proceso productor para: - Evitar el consumo si no hay nada que consumir - Evitar superproducción, en el caso de que no haya espacio en el buffer. Note: Desacoplar actividades entre sí, actividades independientes que pueden tener requisitos temporales diferentes, por lo que admiten distintas configuraciones en cuanto al número de productores y consumidores. Se puede hablar aquí a modo de introducción de arquitecturas PUB/SUB ---- ### Código del productor ```cpp= do { ... produce un nuevo elemento (elemento_p) ... while (contador == MAX_ELEMENTOS) haz_nada(); buffer[indice_p] = elemento_p; indice_p = (indice_p + 1) % MAX_ELEMENTOS; contador = contador + 1; } while (TRUE); ``` :::spoiler ¿Qué significa `haz_nada()` Espera activa. Aún pasará algo de tiempo hasta que podamos solucionar eso. ::: ---- ### Código del consumidor ```cpp= do { while (contador == 0) haz_nada(); elemento_c = buffer[indice_c]; indice_c = (indice_c + 1) % MAX_ELEMENTOS; contador = contador - 1; ... consume el elemento (elemento_c) ... } while (TRUE); ``` :::spoiler ¿Qué sucede si ambos, productor y consumidor, hacen simultáneamente `contador + 1` y `contador - 1` respectivamente? No se sabe. Se produce una situación no determinista denomina **condición de carrera** ::: --- ## Condiciones de carrera | `contador + 1` | `contador - 1` | | ---- | --- | | `load r0, contador` | `load r0, contador` | | `add r0, 1` | `sub r0, 1` | | `store r0, contador` | `store r0, contador` | --- ## Condiciones de carrera - Deriva de la velocidad relativa entre dos procesos a la hora de operar sobre datos compartidos. - Dependiendo de esa velocidad obtenemos resultados diferentes (no determinista) - La operación de incremento o decremento no es atómica :::danger Una operación atómica es aquella que o se ejecuta por completo o no se ejecuta en absoluto. ::: - Necesitamos que partes del código se ejecuten de forma exclusiva: **secciones críticas** --- ## Sección crítica - Sección de código en la que se actualizan variables compartidas - La **exclusión mutua** es un mecanismo que asegura que solo un proceso accede a una sección crítica de forma exclusiva. --- ## Condiciones de una sección crítica - Se debe asegurar exclusión mutua - Se debe de garantizar progreso - Se debe de garantizar la espera limitada Note: - Progreso: un proceso que se encuentre fuera de la sección crítica no debe impedir a otro entrar en la sección crítica (Esto se ve bien con un ejemplo que se muestra más adelante) - Espera limitada: un proceso que quiera entrar en la sección crítica debe poder hacerlo en un tiempo finito --- ## ¿Cómo proporcionar secciones críticas? - Variables de control - Instrucciones máquina específicas (`test_and_set`, `swap`) - Primitivas del sistema operativo (semáforos) - Soluciones proporcionadas por terceros (lenguaje, servicios externos, etc.) Note: - Todas las soluciones asumen que los programas avanzan (progresan) y que no se puede asumir la velocidad relativa de unos con respecto a otros (los efectos de la planificación de CPU del SO) --- ## Variables de control #1 - Las operaciones de carga y almacenamiento son atómicas - Dos hilos $T_i$ y $T_j$ comparten la variable `turno` ```cpp= do { while (turno != i) haz_nada(); sección crítica turno = j; resto de la sección } while (TRUE); ``` - :heavy_check_mark: exclusión mutua - :negative_squared_cross_mark: progreso - :negative_squared_cross_mark: espera limitada Note: El mismo proceso no puede entrar dos veces seguidas, incluso si el otro proceso no necesita entrar. Eso viola la condición de progreso. --- ## Variables de control #2 ```cpp= flag[i] = false flag[j] = false ``` `flag` indica la intención del hilo `i` de acceder a la SC ```cpp= do { flag[i] = true; while (flag[j]) haz_nada(); sección crítica flag[i] = FALSE; resto de la sección } while (true); ``` - :negative_squared_cross_mark: exclusión mutua - :heavy_check_mark: progreso - :heavy_check_mark: espera limitada --- ## Variables de control #3 ```cpp= flag[i] = false flag[j] = false turno = i ``` ```cpp= do { flag[i] = true; turno = j; while (flag[j] && (turno == j)) haz_nada(); sección crítica flag[i] = false; resto de la sección } while (true); ``` - :heavy_check_mark: exclusión mutua - :heavy_check_mark: progreso - :heavy_check_mark: espera limitada --- ## Variables de control #3 - :heavy_check_mark: exclusión mutua - :heavy_check_mark: progreso - :heavy_check_mark: espera limitada - :negative_squared_cross_mark: difícil de extender a muchos procesos - :negative_squared_cross_mark: requiere memoria compartida - :negative_squared_cross_mark: implica espera activa --- ## Instrucciones `test_and_set` ``` test_and_set(&memoria) ``` ```cpp= int test_and_set (int *destino) { int aux; aux = *destino; *destino = TRUE; return (aux); } ``` ```cpp= do { while (test_and_set (&cerrojo)) haz_nada(); sección crítica cerrojo = false; resto de la sección } while (TRUE); ``` --- ## Instrucciones `test_and_set` - :heavy_check_mark: exclusión mutua - :heavy_check_mark: progreso - :heavy_check_mark: espera limitada - :heavy_check_mark: fácil de extender a muchos procesos - :negative_squared_cross_mark: requiere memoria compartida - :negative_squared_cross_mark: implica espera activa --- ## Semáforos - Son objetos gestionados por el SO - Es un tipo especial de variable que admite dos operaciones - `P(S)` Espera hasta que el semáforo sea positivo, y en ese momento lo decrementa. - `V(S)` Incrementa el semáforo en una unidad - Ambas operaciones `P` y `V` son atómicas Note: - Es el sistema operativo el que garantiza que las operaciones son atómicas. - Indicar que más adelante se explicará cómo es capaz el sistema operativo de garantizar ejecución atómica. --- ## Semáforos - :heavy_check_mark: exclusión mutua - :heavy_check_mark: progreso - :heavy_check_mark: espera limitada - :heavy_check_mark: fácil de extender a muchos procesos - :heavy_check_mark: no requiere memoria compartida - :heavy_check_mark: no implica espera activa. El SO bloquea al proceso si fuera necesario ---- ### Productor-Consumidor con semáforos - El consumidor se bloquea si no hay nada que consumir - El productor se bloquea si no hay sitio en el buffer - Se debe de poder garantizar exclusión mutua ``` smf_llenos <- 0 ; controla el número de elementos en el buffer smf_vacios <- N; controla el número de huecos en el buffer mutex <- 1; proporciona acceso en exclusión mútua ``` ---- ### Productor-Consumidor con semáforos #### Código del productor ```cpp= dato = producir() P(smf_vacios) P(exmut) insertar(dato) V(exmut) V(smf_llenos) ``` #### Código del consumidor ```cpp= P(smf_llenos) P(exmut) dato = extraer() V(exmut) V(smf_vacios) ``` ---- ### Productor-Consumidor con semáforos - ¿Importa el orden de las operaciones `P`y `V`? - ¿Cómo sería si hubiera dos productores o dos consumidores? - Si algún participante tuviera que esperar, ¿lo haría de forma activa? ###### tags: `SOG` `Sincronización`