Sistemas Concurrentes y Distribuidos - Curso 2024-25 PDF

Sistemas Concurrentes y Distribuidos: Tema 2. Sincronización en memoria compartida. Carlos Ureña / Jose M. Mantas / Pedro Villar / Manuel Noguera Curso 2024-25 (archivo generado el 31 de octubre de 2024) Grado en Ingeniería Informática Dpt. Lenguajes y Sistemas Informáticos ETSI Informática y de Telecomunicación Universidad de Granada Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Índice. 1. Introducción a la sincronización en memoria compartida. 2. Soluciones software con espera ocupada para E.M. 3. Soluciones hardware con espera ocupada (cerrojos) para E.M. 4. Semáforos para sincronización 5. Monitores como mecanismo de alto nivel Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 1. Introducción a la sincronización en memoria compartida.. Sincronización en memoria compartida En esta tema estudiaremos soluciones para exclusión mutua y sincronización basadas en el uso de memoria compartida entre los procesos involucrados. Este tipo de soluciones se pueden dividir en dos categorías: I Soluciones de bajo nivel con espera ocupada están basadas en programas que contienen explícitamente instrucciones de bajo nivel para lectura y escritura directamente a la memoria compartida, y bucles para realizar las esperas. I Soluciones de alto nivel partiendo de las anteriores, se diseña una capa software por encima que ofrece un interfaz para las aplicaciones. La sincronización se consigue bloqueando un proceso cuando deba esperar. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 4 de 149. Soluciones de bajo nivel con espera ocupada Cuando un proceso debe esperar a que ocurra un evento o sea cierta determinada condición, entra en un bucle indefinido en el cual continuamente comprueba si la situación ya se da o no (a esto se le llama espera ocupada). Este tipo de soluciones se pueden dividir en dos categorías: I Soluciones software: se usan operaciones estándar sencillas de lectura y escritura de datos simples (típicamente valores lógicos o enteros) en la memoria compartida I Soluciones hardware (cerrojos): basadas en la existencia de instrucciones máquina específicas dentro del repertorio de instrucciones de los procesadores involucrados Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 5 de 149. Soluciones de alto nivel Las soluciones de bajo nivel con espera ocupada se prestan a errores, producen algoritmos complicados y tienen un impacto negativo en la eficiencia de uso de la CPU (por los bucles). En las soluciones de alto nivel se ofrecen interfaces de acceso a estructuras de datos y además se usa bloqueo de procesos en lugar de espera ocupada. Veremos algunas de estas soluciones: I Semáforos: se construyen directamente sobre las soluciones de bajo nivel, usando además servicios del SO que dan la capacidad de bloquear y reactivar procesos. I Regiones críticas condicionales: son soluciones de más alto nivel que los semáforos, y que se pueden implementar sobre ellos. I Monitores: son soluciones de más alto nivel que las anteriores y se pueden implementar en algunos lenguajes orientados a objetos como Java o Python. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 6 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 2. Soluciones software con espera ocupada para E.M.. 2.1. Estructura de los procesos con secciones críticas 2.2. Propiedades para exclusión mutua 2.3. Refinamiento sucesivo de Dijkstra 2.4. Algoritmo de Dekker 2.5. Algoritmo de Peterson Introducción En esta sección veremos diversas soluciones para lograr exclusión mutua en una sección crítica usando variables compartidas entre los procesos o hebras involucrados. I Estos algoritmos usan dichas variables para hacer espera ocupada cuando sea necesario en el protocolo de entrada. I Los algoritmos que resuelven este problema no son triviales, y menos para más de dos procesos. En la actualidad se conocen distintas soluciones con distintas propiedades. Veremos estos dos algoritmos: I Algoritmo de Dekker (para 2 procesos) I Algoritmo de Peterson (para 2 y para un número arbitrario de procesos). I Previamente a esos algoritmos, veremos la estructura de los procesos con secciónes críticas y las propiedades que deben cumplir los algoritmos. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 8 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 2. Soluciones software con espera ocupada para E.M. Subsección 2.1. Estructura de los procesos con secciones críticas. Entrada y salida en secciónes críticas Para analizar las soluciones a EM asumimos que un proceso que incluya un bloque considerado como sección crítica (SC) tendrá dicho bloque estructurado en tres etapas: 1. Protocolo de entrada (PE): una serie de instrucciones que incluyen posiblemente espera, en los casos en los que no se pueda conceder acceso a la sección crítica. 2. Sección crítica (SC): instrucciones que solo pueden ser ejecutadas por un proceso como mucho. 3. Protocolo de salida (PS): instrucciones que permiten que otros procesos puedan conocer que este proceso ha terminado la sección crítica. Todas las sentencias que no forman parte de ninguna de estas tres etapas se denominan Resto de Sentencias (RS). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 10 de 149. Acceso repetitivo a las secciónes críticas En general, un proceso puede contener más de una sección crítica, y cada sección crítica puede estar desglosada en varios bloques de código separados en el texto del proceso. Para simplificar el análisis, suponemos, sin pérdida de generalidad, que: I Cada proceso tiene una única sección crítica (SC). I La SC es un único bloque contiguo de instrucciones. I Se ejecuta un bucle infinito, con dos pasos: I Sección crítica (con el PE antes y el PS después) I Resto de sentencias: se emplea un tiempo arbitrario no acotado, e incluso el proceso puede finalizar en esta sección, de forma prevista o imprevista. Es el caso más general: no se supone nada acerca de cuantas veces un proceso puede intentar entrar en una SC. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 11 de 149. Diagrama de estados de un proceso Un proceso cualquiera pasa por los siguientes estados: no puede acceder PE SC PS RS Inicio del puede proceso Fin del Protocolo Sección Protocolo Resto de proceso acceder termina proceso de Entrada Crítica de Salida Sentencias proceso no termina I El proceso únicamente puede terminar cuando se encuentra en Resto de sentencias, I El código del Protocolo de Entrada introduce esperas (mediante bucles) para aseguar exclusión mútua en la Sección Crítica. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 12 de 149. Condiciones sobre el comportamiento de los procesos. Para que se puedan implementar soluciones correctas al problema de EM, es necesario suponer que: Los procesos siempre terminan una sección crítica y emplean un intervalo de tiempo finito desde que la comienzan hasta que la terminan. es decir, durante el tiempo en que un proceso se encuentra en una sección crítica nunca I Finaliza o aborta. I Es finalizado o abortado externamente. I Entra en un bucle infinito. I Es bloqueado o suspendido indefinidamente de forma externa. Es deseable que el tiempo empleado en SC sea lo menos posible. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 13 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 2. Soluciones software con espera ocupada para E.M. Subsección 2.2. Propiedades para exclusión mutua. Propiedades requeridas para las soluciones a EM Para que un algoritmo para EM sea correcto, se deben cumplir cada una de estas tres propiedades mínimas: 1. Exclusión mutua 2. Progreso 3. Espera limitada además, hay propiedades deseables adicionales que también deben cumplirse: 4. Eficiencia 5. Equidad Si bien consideramos correcto un algoritmo que no sea muy eficiente o para el que no pueda demostrarse claramente la equidad. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 15 de 149. Propiedad de exclusión mutua Es la propiedad fundamental para el problema de la sección crítica. Establece que En cada instante de tiempo, y para cada sección crítica exis- tente, habrá como mucho un proceso ejecutando alguna sen- tencia de dicha región crítica. En esta sección veremos soluciones de memoria compartida que permiten un único proceso en una sección crítica. Si bien esta es la propiedad fundamental, no puede conseguirse de cualquier forma, y para ello se establecen las otras dos condiciones mínimas que vemos a continuación. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 16 de 149. Propiedad de progreso Consideremos una SC en un instante en el cual no hay ningún proceso ejecutándola, pero sí hay procesos en el PE compitiendo por entrar a la SC. La propiedad de progreso establece: Un algoritmo de EM debe estar diseñado de forma tal que: 1. Después de un intervalo de tiempo finito desde que ingresó el primer proceso al PE, uno de los procesos en el mismo podrá acceder a la SC. 2. La selección del proceso anterior es completamente independiente del comportamiento de los procesos que durante todo ese intervalo no han estado en SC ni han intentado acceder. Cuando la condición (1) no se da, se dice que ocurre un interbloqueo, ya que todos los procesos en el PE quedan en espera ocupada indefinidamente sin que ninguno pueda avanzar. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 17 de 149. Espera limitada Supongamos que un proceso emplea un intervalo de tiempo en el PE intentando acceder a una SC. Durante ese intervalo de tiempo, cualquier otro proceso activo puede entrar un número arbitrario de veces n a ese mismo PE y lograr acceso a la SC (incluyendo la posibilidad de que n = 0). La propiedad de espera limitada establece que: Un algoritmo de exclusión mutua debe estar diseñado de for- ma que n nunca será superior a un valor máximo determi- nado. Esto implica que las esperas en el PE siempre serán finitas (suponiendo que los procesos emplean un tiempo finito en la SC). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 18 de 149. Propiedades deseables: eficiencia y equidad. Las propiedades deseables son estas dos: I Eficiencia: Los protocolos de entrada y salida deben emplear poco tiempo de procesamiento (excluyendo las esperas ocupadas del PE), y las variables compartidas deben usar poca cantidad de memoria. I Equidad: En los casos en que haya varios procesos compitiendo por acceder a una SC (de forma repetida en el tiempo), no debería existir la posibilidad de que sistemáticamente se perjudique a algunos y se beneficie a otros. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 19 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 2. Soluciones software con espera ocupada para E.M. Subsección 2.3. Refinamiento sucesivo de Dijkstra. Introducción al refinamiento sucesivo de Dijkstra El Refinamiento sucesivo de Dijskstra hace referencia a una serie de algoritmos que intentan resolver el problema de la exclusión mutua. I Se comienza desde una versión muy simple, incorrecta (no cumple alguna de las propiedades), y se hacen sucesivas mejoras para intentar cumplir las tres propiedades. Esto ilustra muy bien la importancia de dichas propiedades. I La versión final correcta se denomina Algoritmo de Dekker. I Por simplicidad, veremos algoritmos para 2 procesos únicamente. I Se asume que hay dos procesos, denominados P0 y P1, cada uno de ellos ejecuta un bucle infinito conteniendo: protocolo de entrada, sección crítica, protocolo de salida y otras sentencias del proceso. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 21 de 149. Versión 1. Pseudocódigo. En esta versión se usa una variable lógica compartida (p01sc) que valdrá true solo si el proceso 0 o el proceso 1 están en SC, y valdrá false si ninguno lo está: { variables compartidas y valores iniciales } var p01sc : boolean := false ; { indica si la SC esta ocupada } process P0 ; process P1 ; begin begin while true do begin while true do begin while p01sc do begin end while p01sc do begin end p01sc := true ; p01sc := true ; { sección crítica } { sección crítica } p01sc := false ; p01sc := false ; { resto sección } { resto sección } end end end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 22 de 149. Versión 1. Corrección. Sin embargo, esa versión no es correcta. El motivo es que no cumple la propiedad de exclusión mutua, pues ambos procesos pueden estar en la sección crítica. Esto puede ocurrir si ambos leen p01sc y ambos la ven a false. es decir, si ocurre la siguiente secuencia de eventos: 1. el proceso 0 accede al PE, ve p01sc con valor false, 2. el proceso 1 accede al PE, ve p01sc con valor false, 3. el proceso 0 pone p01sc a true y entra en la sección crítica, 4. el proceso 1 pone p01sc a true y entra en la sección crítica. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 23 de 149. Versión 2. Pseudocódigo. Para solucionar el problema se usará una única variable lógica (turno0), cuyo valor servirá para indicar cuál de los dos procesos tendrá prioridad para entrar SC la próxima vez que lleguen al PE. La variable valdrá true si la prioridad es para el proceso 0, y false si es para el proceso 1: { variables compartidas y valores iniciales } var turno0 : boolean := true ; { podría ser también |false| } process P0 ; process P1 ; begin begin while true do begin while true do begin while not turno0 do begin end while turno0 do begin end { sección crítica } { sección crítica } turno0 := false ; turno0 := true ; { resto sección } { resto sección } end end end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 24 de 149. Versión 2. Corrección. Esta segunda versión no es tampoco correcta, el motivo es distinto. Se dan estas circunstancias: I Se cumple la propiedad de exclusión mutua. Esto es fácil de verificar, ya que si un proceso está en SC ha logrado pasar el bucle del protocolo de entrada y por tanto la variable turno0 tiene un valor que forzosamente hace esperar al otro. I No se cumple la propiedad de progreso en la ejecución. El problema está en que este esquema obliga a los procesos a acceder de forma alterna a la sección crítica. En caso de que un proceso quiera acceder dos veces seguidas sin que el otro intente acceder más, la segunda vez quedará esperando indefinidamente. Este es un buen ejemplo de la necesidad de tener en cuenta cualquier secuencia posible de mezcla de pasos de procesamiento de los procesos a sincronizar. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 25 de 149. Versión 3. Pseudocódigo. Para solucionar el problema de la alternancia, ahora usamos dos variables lógicas (p0sc, p1sc) en lugar de solo una. Cada variable vale true si el correspondiente proceso está en la sección crítica: { variables compartidas y valores iniciales } var p0sc : boolean := false ; { verdadero solo si proc. 0 en SC } p1sc : boolean := false ; { verdadero solo si proc. 1 en SC } process P0 ; process P1 ; begin begin while true do begin while true do begin while p1sc do begin end while p0sc do begin end p0sc := true ; p1sc := true ; { sección crítica } { sección crítica } p0sc := false ; p1sc := false ; { resto sección } { resto sección } end end end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 26 de 149. Versión 3. Corrección. De nuevo, esta versión no es correcta: I Sí se cumple la propiedad de progreso: los procesos no tienen que entrar de forma necesariamente alterna, al usar dos variables independientes. I No se cumple, sin embargo, la exclusión mutua, por motivos parecidos a la primera versión, ya que se pueden producir secuencias de acciones como esta: I el proceso 0 accede al PE, ve p1sc con valor false, I el proceso 1 accede al PE, ve p0sc con valor false, I el proceso 0 pone p0sc a true y entra en SC, I el proceso 1 pone p1sc a true y entra en SC. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 27 de 149. Versión 4. Pseudocódigo. Para solucionar el problema anterior se puede cambiar el orden de las dos sentencias del PE. Ahora las variables lógicas p0sc y p1sc están a true cuando el correspondiente proceso está en SC, pero también cuando está intentando entrar (en el PE): { variables compartidas y valores iniciales } var p0sc : boolean := falso ; { verdadero solo si proc. 0 en PE o SC } p1sc : boolean := falso ; { verdadero solo si proc. 1 en PE o SC } process P0 ; process P1 ; begin begin while true do begin while true do begin p0sc := true ; p1sc := true ; while p1sc do begin end while p0sc do begin end { sección crítica } { sección crítica } p0sc := false ; p1sc := false ; { resto sección } { resto sección } end end end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 28 de 149. Versión 4. Corrección. De nuevo, esta versión no es correcta: I Ahora es fácil demostrar que sí se cumple la E.M. I También se permite el entrelazamiento con regiones no críticas, ya que si un proceso accede al PE cuando el otro no está en el PE ni en el SC, el primero logrará entrar a la SC. I Sin embargo, no se cumple el progreso en la ejecución, ya que puede ocurrir interbloqueo. En este caso en concreto, eso puede ocurrir si se produce una secuencia de acciones como esta: I el proceso 0 accede al PE, pone p0sc a true, I el proceso 1 accede al PE, pone p1sc a true, I el proceso 0 ve p1sc a true, y entra en el bucle de espera, I el proceso 1 ve p0sc a true, y entra en el bucle de espera. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 29 de 149. Versión 5. Pseudocódigo. Para solucionarlo, si un proceso ve que el otro quiere entrar, el primero pone su variable temporalmente a false: var p0sc : boolean := false ; { true solo si proc. 0 en PE o SC } p1sc : boolean := false ; { true solo si proc. 1 en PE o SC } 1 process P0 ; process P1 ; 1 2 begin begin 2 3 while true do begin while true do begin 3 4 p0sc := true ; p1sc := true ; 4 5 while p1sc do begin while p0sc do begin 5 6 p0sc := false ; p1sc := false ; 6 7 { espera durante un tiempo } { espera durante un tiempo } 7 8 p0sc := true ; p1sc := true ; 8 9 end end 9 10 { sección crítica } { sección crítica } 10 11 p0sc := false ; p1sc := false ; 11 12 { resto sección } { resto sección } 12 13 end end 13 14 end end 14 Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 30 de 149. Versión 5. Corrección. Ahora se cumple exclusión mutua pero no es posible afirmar que es imposible que se produzca interbloqueo en el PE: no se cumple la propiedad de progreso. I La posibilidad de interbloqueo es pequeña, y depende de cómo se seleccionen las duraciones de los tiempos de la espera de cortesía, de cómo se implemente dicha espera, y de la metodología usada para asignar la CPU a los procesos o hebras a lo largo del tiempo. I Por ejemplo, el interbloqueo podría ocurrir si ocurre que: I Hay una CPU y la espera de cortesía es espera ocupada. I Los dos procesos acceden al bucle de las líneas 4-8 (ambas variables están a verdadero). I Sistemáticamente, cuando un proceso está en la CPU y ha terminado de ejecutar la asignación de la línea 8, la CPU se le asigna al otro. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 31 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 2. Soluciones software con espera ocupada para E.M. Subsección 2.4. Algoritmo de Dekker. Algoritmo de Dekker. Descripción. El algoritmo de Dekker debe su nombre a su inventor, es un algoritmo correcto (es decir, cumple las propiedades mínimas establecidas), y se puede interpretar como el resultado final del refinamiento sucesivo de Dijkstra: I Al igual que en la versión 5, cada proceso incorpora una espera de cortesía durante la cual le cede al otro la posibilidad de entrar en SC, cuando ambos coinciden en el PE. I Para evitar interbloqueos, la espera de cortesía solo la realiza uno de los dos procesos, de forma alterna, mediante una variable de turno (parecido a la versión 2). I La variable de turno permite también saber cuando acabar la espera de cortesía, que se implementa mediante un bucle (espera ocupada). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 33 de 149. Algoritmo de Dekker. Pseudocódigo. { variables compartidas y valores iniciales } var p0sc : boolean := falso ; { true solo si proc.0 en PE o SC } p1sc : boolean := falso ; { true solo si proc.1 en PE o SC } turno0 : boolean := true ; { true ==> pr.0 no hace espera de cortesia } 1 process P0 ; process P1 ; 1 2 begin begin 2 3 while true do begin while true do begin 3 4 p0sc := true ; p1sc := true ; 4 5 while p1sc do begin while p0sc do begin 5 6 if not turno0 then begin if turno0 then begin 6 7 p0sc := false ; p1sc := false ; 7 8 while not turno0 do while turno0 do 8 9 begin end begin end 9 10 p0sc := true ; p1sc := true ; 10 11 end end 11 12 end end 12 13 { sección crítica } { sección crítica } 13 14 turno0 := false ; turno0 := true ; 14 15 p0sc := false ; p1sc := false ; 15 16 { resto sección } { resto sección } 16 17 end end 17 18 end end 18 Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 34 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 2. Soluciones software con espera ocupada para E.M. Subsección 2.5. Algoritmo de Peterson. Algoritmo de Peterson. Descripción. Este algoritmo (que también debe su nombre a su inventor), es otro algoritmo correcto para EM, que además es más simple que el algoritmo de Dekker. I Al igual que el algoritmo de Dekker, usa dos variables lógicas que expresan la presencia de cada proceso en el PE o la SC, más una variable de turno que permite romper el interbloqueo en caso de acceso simultáneo al PE. I La asignación a la variable de turno se hace al inicio del PE en lugar de en el PS, con lo cual, en caso de acceso simultáneo al PE, el segundo proceso en ejecutar la asignación (atómica) al turno da preferencia al otro (el primero en llegar). I A diferencia del algoritmo de Dekker, el PE no usa dos bucles anidados, sino que unifica ambos en uno solo. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 36 de 149. Pseudocódigo para 2 procesos. El esquema del algoritmo queda como sigue: { variables compartidas y valores iniciales } var p0sc : boolean := falso ; { true solo si proc.0 en PE o SC } p1sc : boolean := falso ; { true solo si proc.1 en PE o SC } turno0 : boolean := true ; { true ==> pr.0 no hace espera de cortesia } 1 process P0 ; process P1 ; 1 2 begin begin 2 3 while true do begin while true do begin 3 4 p0sc := true ; p1sc := true ; 4 5 turno0 := false ; turno0 := true ; 5 6 while p1sc and not turno0 do while p0sc and turno0 do 6 7 begin end begin end 7 8 { sección crítica } { sección crítica } 8 9 p0sc := false ; p1sc := false ; 9 10 { resto sección } { resto sección } 10 11 end end 11 12 end end 12 Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 37 de 149. Demostración de exclusión mutua. (1/2) Supongamos que en un instante de tiempo t ambos procesos están en SC, entonces: (a) La última asignación (atómica) a la variable turno0 (línea 5), previa a t, finalizó en un instante s (se cumple s < t). (b) En el intervalo de tiempo (s, t], ninguna variable compartida ha podido cambiar de valor, ya que en ese intervalo ambos procesos están en espera ocupada o en la sección crítica y no escriben esas variables. (c) Durante el intervalo (s, t], las variables p0sc y p1sc valen true, ya que cada proceso puso la suya a true antes de s, sin poder cambiarla durante (s, t]. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 38 de 149. Demostración de exclusión mutua. (2/2) de las premisas anteriores de deduce que (d) si el proceso 0 ejecutó el último la línea 5 en el instante s, entonces no habría podido entrar en SC entre s y t (la condición de espera del proc.0 se cumpliría en el intervalo (s, t]), y por tanto en s forzosamente fue el proceso 1 el último que asignó valor a turno0, luego turno0b vale true durante el intervalo (s, t]. (e) la condición anterior implica que el proceso 1 no estaba en SC en s, ni ha podido entrar a SC durante (s, t] (ya que p0sc and turno0 vale true), luego el proceso 1 no está en SC en t. Vemos que se ha llegado a una contradicción con la hipótesis de partida, que por tanto debe ser falsa, luego no puede existir ningún instante en el cual los dos procesos estén en SC, es decir, se cumple la exclusión mutua. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 39 de 149. Espera limitada Supongamos que hay un proceso (p.ej. el 0) en espera ocupada en el PE, en un instante t, y veamos cuántas veces m puede entrar a SC el proceso 1 antes de que el 0 logre hacerlo: I El proceso 0 puede pasar a la SC antes que el 1, en ese caso m = 0. I El proceso 1 puede pasar a la SC antes que el 0 (que continúa en el bucle). En ese caso m = 1. En cualquiera de los dos casos, el proceso 1 no puede después llegar (o volver) a SC mientras el 0 continúa en el bucle, ya que para eso el proceso 1 debería pasar antes por la asignación de true a turno0, y eso provocaría que (después de un tiempo finito) forzosamente el proceso 0 entra en SC mientras el 1 continúa en su bucle. Por tanto, la cota que requiere la propiedad es n = 1. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 40 de 149. Progreso en la ejecución Para asegurar el progreso es necesario asegurar I Ausencia de interbloqueos en el PE: Esto es fácil de demostrar pues si suponemos que hay interbloqueo de los dos procesos, eso significa que son indefinida y simultáneamente verdaderas las dos condiciones de los bucles de espera, y eso implica que es verdad turno0 and not turno0, lo cual es absurdo. I Independencia de procesos en RS: Si un proceso (p.ej. el 0) está en PE y el otro (el 1) está en RS, entonces p1sc vale false y el proceso 0 puede progresar a la SC independientemente del comportamiento del proceso 1 (que podría terminar o bloquearse estando en RS, sin impedir por ello el progreso del proc.0). El mismo razonamiento puede hacerse al revés. Luego es evidente que el algoritmo cumple la condición de progreso. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 41 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 3. Soluciones hardware con espera ocupada (cerrojos) para E.M.. Introducción Los cerrojos constituyen una solución hardware basada en espera ocupada que puede usarse en procesos concurrentes con memoria compartida para solucionar el problema de la exclusión mutua. I La espera ocupada constituye un bucle que se ejecuta hasta que ningún otro proceso esté ejecutando instrucciones de la sección crítica. I Existe un valor lógico en una posición de memoria compartida (llamado cerrojo) que indica si algún proceso está en la sección crítica o no. I En el protocolo de salida se actualiza el cerrojo de forma que se refleje que la SC ha quedado libre. Veremos una solución elemental que, sin embargo, es incorrecta e ilustra la necesidad de instrucciones hardware específicas (u otras soluciones más elaboradas). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 43 de 149. Una posible solución elemental Vemos un esquema para procesos que ejecutan SC y RS repetidamente: { variables compartidas y valores iniciales } var sc_ocupada : boolean := false ; { cerrojo: verdadero sólo si SC ocupada } { procesos } process P[ i : 1.. n ]; begin while true do begin while sc_ocupada do begin end sc_ocupada := true ; { sección crítica } sc_ocupada := false ; { resto de sentencias } end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 44 de 149. Errores de la solución simple La solución anterior no es correcta, ya que no garantiza exclusión mutua al existir secuencias de mezclado de instrucciones que permiten a más de un proceso ejecutar la SC a la vez: I La situación se da si n procesos acceden al protocolo de entrada y todos ellos leen el valor del cerrojo a false (ninguno lo escribe antes de que otro lo lea). I Todos los procesos registran que la SC está libre, y todos acceden a ella. I El problema es parecido al que ya vimos de acceso simultáneo a una variable en memoria compartida: la lectura y posterior escritura del cerrojo se hace en varias sentencias distintas que se entremezclan. Una solución es usar instrucciones máquina atómicas (indivisibles) para acceso a la zona de memoria donde se aloja el cerrojo. Veremos una de ellas: TestAndSet. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 45 de 149. La instrucción TestAndSet Es una instrucción máquina disponible en el repertorio de algunos procesadores. I Admite como argumento la dirección de memoria de la variable lógica que actúa como cerrojo. I Se invoca como una función desde LLPP de alto nivel, y ejecuta estas acciones: 1. lee el valor anterior del cerrojo 2. pone el cerrojo a true 3. devuelve el valor anterior del cerrojo I Durante su ejecución, ninguna otra instrucción ejecutada por otro proceso puede leer ni escribir la variable lógica: por tanto, se ejecuta de forma atómica. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 46 de 149. Protocolos de entrada y salida con TestAndSet. La forma adecuada de usar TestAndSet es la que se indica en este esquema: { variables compartidas y valores iniciales } var sc_ocupada : boolean := false ; { true sólo si la SC está ocupada } { procesos } process P[ i : 1.. n ]; begin while true do begin while TestAndSet( sc_ocupada ) do begin end { sección crítica } sc_ocupada := false ; { resto de sentencias } end end Cuando hay más de un proceso intentando entrar a la SC (estando SC libre), sólo uno de ellos (el primero en ejecutar TestAndSet) ve el cerrojo (sc_ocupada) a false, lo pone a true y logra entrar a SC. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 47 de 149. Desventajas de los cerrojos Los cerrojos constituyen una solucion válida para EM que consume poca memoria y es eficiente en tiempo (excluyendo las esperas ocupadas), sin embargo: I Las esperas ocupadas consumen tiempo de CPU que podría dedicarse a otros procesos para hacer trabajo útil. I Se puede acceder directamente a los cerrojos y, por tanto, un programa erróneo o escrito malintencionadamente podría poner un cerrojo en un estado incorrecto, pudiendo dejar a otros procesos indefinidamente en espera ocupada. I en la forma básica que hemos visto no se cumplen ciertas condiciones de equidad. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 48 de 149. Uso de los cerrojos Las desventajas indicadas hacen que el uso de cerrojos sea restringido, en el sentido que: I Por seguridad, normalmente sólo se usan desde componentes software que forman parte del sistema operativo, librerías de hebras, tiempo real o similares (estas componentes suelen estar bien comprobadas y, por tanto, libres de errores o código malicioso). I Para evitar la pérdida de eficiencia que supone la espera ocupada, se usan sólo en casos en los que la ejecución de la SC conlleva un intervalo de tiempo muy corto (por tanto, las esperas ocupadas son muy cortas y la CPU no se desaprovecha tanto). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 49 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 4. Semáforos para sincronización. 4.1. Estructura y operaciones de los semáforos 4.2. Uso de semáforos: patrones sencillos Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 4. Semáforos para sincronización Subsección 4.1. Estructura y operaciones de los semáforos. Semáforos. Introducción Los semáforos constituyen un mecanismo que soluciona o aminora los problemas de las soluciones de bajo nivel y tienen un ámbito de uso más amplio: I No se usa espera ocupada, sino bloqueo de procesos (uso mucho más eficiente de la CPU). I Resuelven fácilmente el problema de exclusión mutua con esquemas de uso sencillos. I Se pueden usar para resolver problemas de sincronización (aunque en ocasiones los esquemas de uso son complejos). I El mecanismo se implementa mediante instancias de una estructura de datos a las que se accede únicamente mediante subprogramas específicos. Esto aumenta la seguridad y simplicidad de los programas. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 52 de 149. Bloqueo y desbloqueo de procesos Los semáforos exigen que los procesos bloqueados no ocupen la CPU. Esto implica que: I Un proceso en ejecución debe poder solicitar quedarse bloqueado. I Un proceso bloqueado no puede ejecutar instrucciones en la CPU. I Un proceso en ejecución debe poder solicitar que se desbloquee (se reanude) algún otro proceso bloqueado. I Deben poder existir simultáneamente varios conjuntos de procesos bloqueados. I Cada petición de bloqueo o desbloqueo se debe referir a alguno de estos conjuntos. Todo esto requiere el uso de servicios externos (proporcionados por el sistema operativo o por la librería de hebras). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 53 de 149. Estructura de un semáforo Un semáforo es un instancia de una estructura de datos (un registro) que contiene los siguientes elementos: I Un conjunto de procesos bloqueados (de estos procesos decimos que están esperando al semáforo). I Un valor natural (un valor entero no negativo), al que llamaremos por simplicidad valor del semáforo. Estas estructuras de datos residen en memoria compartida. Un programa que usa semáforos debe poder inicializarlos al comienzo de su ejecución de forma que: I El conjunto de procesos asociados estará vacío. I Se deberá indicar un valor inicial del semáforo. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 54 de 149. Operaciones sobre los semáforos Además de la inicialización, sólo hay dos operaciones básicas que se pueden realizar sobre una variable u objeto cualquiera de tipo semáforo (que llamamos s) : I sem_wait(s) 1. Si el valor de s es 0, bloquear el proceso. Éste se reanudará después en un instante en que el valor ya es 1. 2. Decrementar el valor del semáforo en una unidad. I sem_signal(s) 1. Incrementar el valor de s en una unidad. 2. Si hay procesos esperando en s, reanudar o despertar a uno de ellos (ese proceso pondrá el valor del semáforo a 0 al salir). Este diseño implica que el valor del semáforo nunca es negativo, ya que antes de decrementar se espera a que sea 1. Además, sólo puede haber procesos esperando cuando el valor es 0. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 55 de 149. Invariante de un semáforo Dado un semáforo s, en un instante de tiempo cualquiera t, su valor (vt ) será el valor inicial (v0 ), más el número de llamadas a sem_signal completadas (ns ), menos el número de llamadas a sem_wait completadas (nw ). Ese valor nunca es negativo. Es decir: vt = v0 + n s − n w ≥ 0 I Los cuatro valores son enteros no negativos. I La igualdad se demuestra viendo que sem_signal siempre incrementa el valor y sem_wait siempre lo decrementa (cuando es 0, pasa una espera previa). I La igualdad se cumple cuando no se está ejecutando sem_wait o sem_signal (cuando no se está actualizando el valor). I No cuentan las llamadas a sem_wait no completadas en el instante t por haber dejado el proceso en espera. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 56 de 149. Implementación de sem_wait y sem_signal. Se pueden implementar con este esquema: procedure sem_wait( s :semaphore); procedure sem_signal( s :semaphore); begin begin if s.valor == 0 then s.valor := s.valor + 1 ; bloquearme( s.procesos ) ; if not vacio( s.procesos ) then s.valor := s.valor - 1 ; desbloquear_uno( s.procesos ) ; end end En un semáforo cualquiera, estas operaciones se ejecutan en exclusión mutua sobre cada semáforo, es decir, no puede haber dos procesos distintos ejecutando estas operaciones a la vez sobre un mismo semáforo (excluyendo el período de bloqueo que potencialmente conlleva la llamada a sem_wait). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 57 de 149. Diagrama de estados de un semáforo Vemos algunos posibles estados de un semáforo, según su número de procesos esperando, (esp.) y su valor (val.), y las posibles transiciones atómicas (en E.M.) entre esos estados, provocadas por hebras que invocan sem_wait o sem_signal. sem_signal sem_signal + fin de + fin de sem_wait sem_wait sem_signal sem_signal sem_signal........ val. = 0 val. = 0 val. = 0 val. = 1 val. = 2 val. = 3......... esp. = 2 esp. = 1 esp. = 0 esp. = 0 esp. = 0 esp. = 0 inicio de inicio de sem_wait sem_wait sem_wait sem_wait sem_wait + bloqueo + bloqueo I Los estados con esp. = 0 son posibles estados iniciales. I El color refleja si el semáforo está en rojo o en verde. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 58 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 4. Semáforos para sincronización Subsección 4.2. Uso de semáforos: patrones sencillos. Patrones de uso sencillos En esta sección veremos varios patrones sencillos de uso de semáforos. Cada patrón es un esquema que permite solucionar, usando semáforos, la sincronización de un problema típico sencillo. En concreto, veremos estos tres problemas: I Espera única: un proceso, antes de ejecutar una sentencia, debe esperar a que otro proceso complete otra sentencia (ocurre típicamente cuando un proceso debe leer una variable escrita por otro proceso). I Exclusión mutua: acceso en exclusión mutua a una sección crítica por parte de un número arbitrario de procesos. I Problema del Productor/Consumidor: similar a la espera única, pero de forma repetida en un bucle (un proceso escribe sucesivos valores en una variable y cada uno de ellos debe leerse una única vez por otro proceso). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 60 de 149. Espera única: problema El caso más sencillo de sincronización ocurre cuando un proceso (Consumidor) lee una variable compartida escrita por otro proceso (Productor): { variables compartidas y valores iniciales } var x : integer ; { variable escrita por Productor } puede_leer : semaphore := 0 ; { 1 si x ya escrita y aún no leída} process Productor ; { escribe 'x' } process Consumidor { lee 'x' } var a : integer ; var b : integer ; begin begin a := ProducirValor() ; b := x ; { sentencia L } x := a ; { sentencia E } UsarValor(b) ; end end I Las sentencias E y L son atómicas. I Únicamente son correctas las interfoliaciones en las que E ocurre antes que L. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 61 de 149. Espera única: solución con un semáforo Para introducir una espera previa a L, usamos un semáforo (puede_leer), cuyo valor es 1 sólo cuando x tiene un valor ya escrito, pero aún está pendiente de leer: { variables compartidas y valores iniciales } var x : integer ; { variable escrita por Productor } puede_leer : semaphore := 0; { 1 si x ya escrita y aun no leída } process Productor ; { escribe 'x' } process Consumidor { lee 'x' } var a : integer ; var b : integer ; begin begin a := ProducirValor() ; sem_wait( puede_leer ) ; x := a ; { sentencia E } b := x ; { sentencia L } sem_signal( puede_leer ) ; UsarValor(b) ; end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 62 de 149. Espera única: grafo de dependencia El semáforo puede_leer está inicializado a 0, luego: I el sem_wait no se puede completar antes de que se haga la llamada a sem_signal, y I por transitividad, la sentencia atómica E se ejecuta antes de la sentencia atómica L. El grafo de dependencia es como se indica en este esquema: producir v sent. E: Productor sem_signal en var. a x:= a Variable x v v inicio de bloqueo fin de sent. L: usar v Consumidor sem_wait (opcional) sem_wait b:= x (en b) Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 63 de 149. Espera única: verificación En cualquier instante durante la ejecución (en el que no se está actualizando el valor del semáforo): I El número de veces que se ha ejecutado E es #E. I El número de veces que se ha ejecutado L es #L. I Sólo son correctas interfoliaciones donde #L ≤ #E. I Puesto que sem_signal va después de E, se cumple ns ≤ #E. I Puesto que sem_wait va antes de L, se cumple #L ≤ nw. I El valor de puede_leer es vt = ns − nw , como no puede ser negativo nunca, se deduce nw ≤ ns. Encadenando las tres últimas desigualdades, obtenemos #L ≤ #E como queríamos demostrar. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 64 de 149. Uso de semáforos para exclusión mutua Los semáforos se pueden usar para EM usando un semáforo inicializado a 1, y haciendo wait antes de la sección crítica y signal después de la sección crítica: { variables compartidas y valores iniciales } var sc_libre : semaphore := 1 ; { 1 si SC está libre, 0 si SC ocupada } { (núm. de procs. que pueden entrar a SC) } process P[ i : 0..n ]; begin while true do begin { esperar hasta que sc_libre sea 1, entonces ponerla a 0 } sem_wait( sc_libre ) ; { sección crítica:...... } { poner sc_libre a 1, y desbloquear un proceso en espera si hay alguno} sem_signal( sc_libre ) ; { resto de sentencias:....... } end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 65 de 149. Verificación de la exclusión mutua En el programa anterior, se cumplen estas propiedades: I Por la estructura del programa, el número de procesos ejecutando la sección crítica (nsc ) en un momento dado es: 0 ≤ nsc = nw − ns I Puesto que el valor inicial v0 es 1, por el invariante y las propiedades de los semáforos, el valor vt de sc_libre es un entero no negativo, que cumple: 0 ≤ vt = 1 + ns − nw = 1 − nsc I Puesto que 0 ≤ 1 − nsc , sabemos que nsc cumple: 0 ≤ nsc ≤ 1 lo que demuestra que se cumple la exclusión mutua, ya que sólo puede haber 0 ó 1 procesos en S.C. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 66 de 149. Sincronización tipo Productor/Consumidor El problema del Productor-Consumidor (que vimos) es igual al problema simple anterior, pero con las lecturas y escrituras (E y L) repetidas en un bucle infinito: { variables compartidas y valores iniciales } var x : integer ; { contiene cada valor producido y pte. de leer } process Productor ; { calcula x } process Consumidor { lee x } var a : integer ; var b : integer ; begin begin while true do begin while true do begin a := ProducirValor() ; b := x ; { sentencia L } x := a ; { sentencia E } UsarValor(b) ; end end end end Ahora, únicamente son correctas las interfoliaciones en las que E y L se alternan, comenzando en E (es decir, interfoliaciones de la forma E, L, E, L,...). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 67 de 149. Solución del Productor/Consumidor con semáforos La solución parecida a la simple, pero con un nuevo semáforo (puede_escribir), inicializado a 1: { variables compartidas y valores iniciales } var x : integer ; { contiene cada valor producido } puede_leer : semaphore := 0 ; { 1 se puede leer x, 0 no } puede_escribir : semaphore := 1 ; { 1 se puede escribir x, 0 no } process Productor ; { escribe x } process Consumidor { lee x } var a : integer ; var b : integer ; begin begin while true do begin while true do begin a := ProducirValor() ; sem_wait( puede_leer ) ; sem_wait( puede_escribir ); b := x ; { sentencia L } x := a ; { sentencia E } sem_signal( puede_escribir ) ; sem_signal( puede_leer ) ; UsarValor(b) ; end end end end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 68 de 149. Verificación de la solución En este caso, solo son correctas las interfoliaciones que hacen siempre ciertas estas dos desigualdades: 0 ≤ #E − #L ≤ 1 ya que el número de valores escritos en x y pendientes de leer, es #E − #L, y ese valor solamente puede ser 0 o 1. En la solución: I El semáforo puede_escribir asegura la condición: #E − #L ≤ 1 I El semáforo puede_leer asegura la condición: 0 ≤ #E − #L Veremos cómo se pueden demostrar estas dos desigualdades a partir de la estructura del programa y del invariante de cada semáforo. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 69 de 149. Verificación (semáforo puede_leer) Respecto del semáforo puede_leer, el análisis es similar al que ya hemos hecho para la versión sin bucles. Se cumplen estas propiedades: I sem_signal se ejecuta una vez después de #E, luego ns ≤ #E I L se ejecuta una vez después de sem_wait, luego #L ≤ nw I El valor del semáforo es ns − nw , siempre positivo, luego nw ≤ ns Al igual que antes, encadenando las tres desigualdades, obtenemos: #L ≤ nw ≤ ns ≤ #E lo cual demuestra, como queríamos, que: 0 ≤ #E − #L Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 70 de 149. Verificación (semáforo puede_escribir) Respecto del semáforo puede_escribir, se cumplen estas propiedades: I sem_signal se ejecuta una vez después de #L, luego ns ≤ #L I E se ejecuta una vez después de sem_wait, luego #E ≤ nw I El valor del semáforo es 1 + ns − nw , siempre positivo, luego nw ≤ 1 + ns De nuevo encadenamos las tres desigualdades, obtenemos: #E ≤ nw ≤ 1 + ns ≤ 1 + #L lo cual demuestra, como queríamos, que: #E − #L ≤ 1 Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 71 de 149. Limitaciones de los semáforos Los semáforos resuelven de una forma eficiente y sencilla el problema de la exclusión mutua y problemas sencillos de sincronización, sin embargo: I Los problemas más complejos de sincronización se resuelven de forma algo más compleja (es difícil verificar su validez, y es fácil que sean incorrectos). I Al igual que los cerrojos, programas erróneos o malintencionados pueden provocar que haya procesos bloqueados indefinidamente o en estados incorrectos. En la siguiente sección se verá una solución de más alto nivel sin estas limitaciones (monitores). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 72 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 5. Monitores como mecanismo de alto nivel. 5.1. Introducción. Definición de monitor 5.2. Funcionamiento de los monitores 5.3. Sincronización en monitores. 5.4. Verificación de monitores 5.5. Patrones de solución con monitores 5.6. El problema de los Lectores/Escritores 5.7. Semántica de las señales de los monitores 5.8. Colas de prioridad 5.9. Implementación de monitores Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 5. Monitores como mecanismo de alto nivel Subsección 5.1. Introducción. Definición de monitor. Limitaciones de los semáforos Como se ha descrito, aparecen algunos inconvenientes al usar mecanismos como los semáforos: I Basados en variables globales: esto impide un diseño modular y reduce la escalabilidad (incorporar más procesos al programa suele requerir la revisión del uso de las variables globales). I El uso y función de las variables no se hace explícito en el programa, lo cual dificulta razonar sobre la corrección de los programas. I Las operaciones se encuentran dispersas y no protegidas (posibilidad de errores). Por tanto, es necesario un mecanismo que permita el acceso estructurado y la encapsulación, y que además proporcione herramientas para garantizar la exclusión mutua e implementar condiciones de sincronización. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 75 de 149. Estructura y funcionalidad de un monitor C.A.R. Hoare, en 1974, idea el concepto de Monitor: es un mecanismo de alto nivel que permite definir objetos abstractos compartidos, que incluyen: I Una colección de variables encapsuladas (datos) que representan un recurso compartido por varios procesos. I Un conjunto de procedimientos para manipular el recurso: afectan a las variables encapsuladas. Ambos conjuntos de elementos permiten al programador invocar a los procedimientos de forma que en ellos: I Se garantiza el acceso en exclusión mutua a las variables encapsuladas. I Se implementan la sincronización requerida por el problema mediante esperas bloqueadas. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 76 de 149. Propiedades del monitor Un monitor es un recurso compartido que se usa como un objeto al que se accede concurrentemente. Acceso estructurado y encapsulación: I El usuario (proceso) sólo puede acceder al recurso mediante un conjunto de operaciones. I El usuario ignora la/s variable/s que representan al recurso y la implementación de las operaciones asociadas. Exclusión mutua en el acceso a los procedimientos: I La exclusión mutua en el acceso a los procedimientos del monitor está garantizada por definición. I La implementación del monitor garantiza que nunca dos procesos estarán ejecutando simultáneamente algún procedimiento del monitor (el mismo o distintos). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 77 de 149. Ventajas sobre los semáforos La propiedades descritas de los monitores los hacen preferibles respecto de los semáforos, dado que el uso de los monitores facilita el diseño e implementación de programas libres de errores. I Las variables están protegidas: sólo pueden leerse o modificarse desde el código del monitor, no desde cualquier punto de un programa que puede tener miles de líneas de código. I La exclusión mutua está garantizada: el programador no tiene que usar mecanismos explícitos de exclusión mutua en el acceso a las variables compartidas. I Las operaciones de esperas bloqueadas y de señalización se programan exclusivamente dentro del monitor: es más fácil verificar que el diseño es correcto. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 78 de 149. Sintaxis de un monitor en pseudo-código Una instancia del monitor se declara especificando las variables permanentes, los procedimientos del monitor y opcionalmente el código de inicialización. monitor nombre_monitor ; { identificador con el que se referencia } var { decl. variables permanentes (privadas) }...... ; { (puede incluir valores iniciales) } export { nombres de procedimientos públicos } nom_exp_1, { (si no aparece, todos son públicos) } nom_exp_2,.... ; { declaraciones e implementación de procedimientos } procedure nom_exp_1(........ ); { nombre y parámetros formales } var..... ; { variables locales del procedimiento } begin... { código que implementa el procedimiento } end....... { resto de procedimientos del monitor } begin { código inicialización de vars. perm. }.... { (opcional) } end { fin de la declaración del monitor } Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 79 de 149. Componentes de un monitor Variables permanentes: son el estado interno del monitor. I Sólo pueden ser accedidas dentro del monitor (en el cuerpo de los procedimientos y código de inicialización). I Permanecen sin modificaciones entre dos llamadas consecutivas a procedimientos del monitor. Procedimientos: modifican el estado interno (en E.M.) I Pueden tener variables y parámetros locales, que toman un nuevo valor en cada activación del procedimiento. I Algunos (o todos) constituyen la interfaz externa del monitor y podrán ser llamados por los procesos que comparten el recurso. Código de inicialización: fija estado interno inicial (opcional) I Se ejecuta una única vez, antes de cualquier llamada a procedimientos del monitor. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 80 de 149. Diagrama de las componentes del monitor El monitor se puede visualizar como aparece en el diagrama: I El uso que se hace del moni- tor se hace exclusivamente usan- Monitor M do los procedimientos exporta- Variables permanentes dos (constituyen el interfaz con el exterior). OP1 I Las variables permanentes y los Procedimientos OP2 procedimientos no exportados no exportados ··· son accesibles desde fuera. OPn I Ventaja: la implementación de las Código de operaciones se puede cambiar sin inicialización modificar su semántica. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 81 de 149. Ejemplo de monitor (pseudocódigo) Tenemos varios procesos que pueden incrementar (en una unidad) una variable compartida y poder examinar su valor en cualquier momento: { declaracion del monitor } { ejemplo de uso del monitor } monitor VarCompartida ; { (debe aparecer en el ámbito } { de la declaración) } var x : integer; { permanente } export incremento, valor; { incrementar valor: } VarCompartida.incremento(); procedure incremento( ); begin { copiar en k el valor: } x := x+1 ; {incrementa valor } k := VarCompartida.valor() ; end; function valor() : integer ; Los procedimientos que devuel- begin return x; { devuelve valor } ven un valor usan return, y se end; declaran con function en lugar begin { código de inicialización} de procedure. Se especifica el x := 0 ; { inicializa valor } tipo del valor devuelto. end { fin del monitor} Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 82 de 149. Instanciación de monitores En algunos casos es conveniente crear múltiples instancias independientes de un monitor, podemos hacerlo con esta sintaxis class monitor nombre_clase_monitor( parametros_formales ) ;.............. { cuerpo del monitor semejante a los anteriores } end var nombre_instancia_1 : nombre_clase_monitor( parametros_actuales_1 ) , nombre_instancia_2 : nombre_clase_monitor( parametros_actuales_2 ) ; I Cada instancia tiene sus variables permanentes propias. I La E.M. ocurre en cada instancia por separado. I Esto facilita mucho escribir código reentrante. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 83 de 149. Ejemplo de instanciación de un monitor Similar a VarCompartida, pero ahora parametrizado: { declaracion de la clase monitor } { ejemplo de uso } class monitor VarComp(pini,pinc : integer); var mv1 : VarComp(0,1); mv2 : VarComp(10,4); var x, inc : integer ; i1,i2 : integer ; export incremento, valor; begin mv1.incremento(); procedure incremento( ); i1:= mv1.valor();{ i1 == 1 } begin mv2.incremento(); x := x+inc ; i2:= mv2.valor();{ i2 == 14 } end; end function valor(): integer ; begin return x ; end; begin x:= pini ; inc := pinc ; end Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 84 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 5. Monitores como mecanismo de alto nivel Subsección 5.2. Funcionamiento de los monitores. Funcionamiento de los monitores Comunicación monitor-mundo exterior: Cuando un proceso necesita operar sobre un recurso compartido controlado por un monitor deberá realizar una llamada a uno de los procedimientos exportados por el monitor usando los parámetros actuales apropiados: I Mientras el proceso está ejecutando algún procedimiento del monitor decimos que el proceso está dentro del monitor. Exclusión mutua: Si un proceso P está dentro de un monitor, cualquier otro proceso Q que llame a un procedimiento de ese monitor deberá esperar hasta que P salga del mismo: I Esta política de acceso asegura que las variables permanentes nunca son accedidas concurrentemente. I El acceso exclusivo entre los procedimientos del monitor debe estar garantizado en la implementación de los monitores Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 86 de 149. Funcionamiento de los monitores (2) Los monitores son objetos pasivos: Después de ejecutarse el código de inicialización, un monitor es un objeto pasivo y el código de sus procedimientos sólo se ejecuta cuando estos son invocados por los procesos. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 87 de 149. Cola del monitor para exclusión mutua El control de la exclusión mutua se basa en la existencia de la cola del monitor: I Si un proceso está dentro del monitor y otro proceso intenta ejecutar un procedimiento del monitor, éste último proceso queda bloqueado y se inserta en la cola del monitor I Cuando un proceso abandona el monitor (finaliza la ejecución del procedimiento), I si hay procesos en la cola, se desbloquea uno de ellos, que entra al monitor, I si no hay procesos en la cola, el monitor queda libre y después, el primer proceso que ejecute una llamada a uno de sus procedimientos, entrará en el monitor. I Para garantizar la vivacidad del sistema, la planificación de la cola del monitor debe seguir una política FIFO. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 88 de 149. Diagrama de estados de un proceso Los posibles estados (en gris) de un proceso (en relación a un monitor), y las posibles transiciones (en rojo claro) entre dichos estados se muestran en este diagrama: Ejecutando código EM llamada a proc. fuera del monitor proc. terminado Adquiriendo E.M. Ejecutando código mon. libre (cola del monitor) dentro del monitor (si el monitor está libre en el momento de la llamada al procedimiento del monitor, no habrá espera en la cola del monitor) Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 89 de 149. Estado del monitor Por tanto, el estado del monitor incluye la cola de procesos esperando a comenzar a ejecutar el código del mismo. Se puede representar por este diagrama: Monitor M Cola del Proceso7 Proceso4 · · · Proceson null Monitor ··· ··· ··· Variables M.OP2 () M.OP4 () M.OPi () permanentes ··· ··· ··· M.OP1 () M.OP1 () M.OPj () ··· ··· ··· OP1 Procedimientos OP2 exportados ··· OPn Código de inicialización Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 90 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 5. Monitores como mecanismo de alto nivel Subsección 5.3. Sincronización en monitores.. Sincronización en monitores Para implementar la sincronización, se requiere de una facilidad para que los procesos hagan esperas bloqueadas, hasta que sea cierta determinada condición: En semáforos, existe I la posibilidad de bloqueo (sem_wait) y activación (sem_signal) I un valor entero (el valor del semáforo), que indica si la condición se cumple (> 0) o no (== 0). En monitores, sin embargo I sólo se dispone de sentencias de bloqueo y activación. I los valores de las variables permanentes del monitor determinan si la condición se cumple o no se cumple. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 92 de 149. Bloqueo y activación con variables condición Para cada condición lógica distinta que pueda hacer que un proceso o un grupo de procesos tengan que esperar dentro de un monitor (para evitar comportamientos incorrectos), se debe declarar una variable permanente de tipo condition. A esas variables, que actúan como colas de procesos bloqueados, las llamamos señales o variables condición: I Cada variable condición tiene asociada una lista o cola (inicialmente vacía) de procesos en espera hasta que la condición se haga cierta. I Para una cualquiera de estas variables, un proceso puede invocar estas dos operaciones: I wait: Estoy esperando a que alguna condición ocurra. I signal: Estoy señalando que una condición ocurre. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 93 de 149. Operaciones sobre variables condición: Dada una variable condición cond, se definen al menos las siguientes operaciones asociadas a cond: I cond.wait(): bloquea incondicionalmente al proceso que la llama y lo introduce en la cola de la variable condición. I cond.signal(): si hay procesos bloqueados por esa condición, libera uno de ellos. Si no hay ninguno esperando no hace nada. Si hay más de uno, se sigue una política FIFO (first-in first-out): I Se reactivará al proceso que lleve más tiempo esperando. I Esto evita la inanición: Cada proceso en cola obtendrá eventualmente su turno. I cond.queue(): Función lógica que devuelve true si hay algún proceso esperando en la cola de cond, y false en caso contrario. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 94 de 149. Esperas bloqueadas y E.M. en el monitor Dado que los procesos pueden estar dentro del monitor, pero bloqueados: I Cuando un proceso llama a wait y queda bloqueado, se debe liberar la exclusión mutua del monitor, si no se hiciese, se produciría interbloqueo con seguridad (ese proceso quedaría quedaría bloqueado y el resto también cuando intentasen después entrar al monitor). I Cuando un proceso es reactivado después de una espera, adquiere de nuevo la exclusión mutua antes de ejecutar la sentencia siguiente a wait. I Más de un proceso podrá estar dentro del monitor, aunque solo uno de ellos estará ejecutándose, el resto estarán bloqueados en variables condición. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 95 de 149. Estado de un monitor con varias colas A modo de ejemplo: los procesos 2 y 5 ejecutan las operaciones 1 y 2, ambas producen esperas de la condición B. Monitor M Cola del Proceso7 Proceso4 · · · Proceson null Monitor Variables permanentes Variables Cond.A null condición Cond.B Proceso2 Proceso5 null ··· ··· ··· ··· M.OP1 () M.OP2 () OP1 B.wait ··· ··· ··· ··· B.wait Procedimientos OP2 ··· exportados B.wait ··· OPn Código de inicialización Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 96 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 5. Monitores como mecanismo de alto nivel Subsección 5.4. Verificación de monitores. Verificación de programas con monitores La verificación de la corrección de un programa concurrente con monitores requiere: I Probar la corrección de cada monitor. I Probar la corrección de cada proceso de forma aislada. I Probar la corrección de la ejecución concurrente de los procesos implicados. El programador no puede conocer a priori la interfoliación concreta de llamadas a los procedimientos del monitor. El enfoque de verificación que vamos a seguir utiliza un invariante de monitor: I Es una propiedad que el monitor cumple siempre (parecido al invariante de un semáforo, pero específico de cada monitor diseñado por un programador) I Unido a las propiedades de los procesos concurrentes que invocan al monitor, facilita la verificación de los programas Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 98 de 149. Características del Invariante del Monitor El Invariante del Monitor (IM) I Es un función lógica que se puede evaluar como true o false en cada estado del monitor a lo largo de la ejecución del programa concurrente. I Su valor depende de la traza del monitor y de los valores de las variables permanentes de dicho monitor. I La traza del monitor es la secuencia (ordenada en el tiempo) de llamadas a procedimientos del monitor ya completadas, desde el inicio del programa hasta llegar al estado indicado (se incluyen las llamadas de todos los procesos del monitor). I El IM debe ser cierto en cualquier estado del programa concurrente, excepto cuando un proceso está ejecutando código del monitor, en E.M. (está en proceso de actualización de los valores de las variables permanentes). Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 99 de 149. Características del Invariante del Monitor El invariante del monitor se escribe como un predicado I Determina que trazas y/o estados son posibles en el monitor. I Puede incluir referencias a las variables y/o a la traza, por ejemplo, al número de veces que se ha ejecutado un procedimiento, o al último procedimiento ejecutado. El invariante del monitor debe ser cierto I en el estado inicial, justo después de la inicialización de las variables permanentes. I antes y después de cada llamada a un procedimiento del monitor I antes y después de cada operación wait. I antes y después de cada operación signal. Justo antes de signal sobre una variable condición, además, debe ser cierta la condición lógica asociada a dicha variable. Sistemas Concurrentes y Distribuidos- Curso 2024-25- Creado: 31 de octubre de 2024 – transparencia 100 de 149. Sistemas Concurrentes y Distribuidos, curso 2024-25. Tema 2. Sincronización en memoria compartida. Sección 5. Monitores como mecanismo de alto nivel Subsección 5.5. Patrones de solución con monitores. Patrones de uso de monitores Para ilustrar el uso de monitores, veremos los patrones de solución para los mismos tres problemas típicos sencillos cuya soluciones con semáforos ya expusimos: I Espera única: un proceso, antes de ejecutar una sentencia, debe esperar a que otro proceso complete otra sentencia (ocurre típicamente cuando un proceso debe leer una variable escrita por otro proceso, el primero se suele denominar Consumidor y el segundo Productor). I Exclusión mut

Sistemas Concurrentes y Distribuidos - Curso 2024-25 PDF

Document Details

Tags

Related

Summary

Full Transcript