Title: Aspectos de la Programación Secuencial
? Sentencias de alternativa: IF B ? S B expresión booleana (condición), S una instrucción simple o compuesta B “guarda” a S pues S no se ejecuta si B no es verdadera. Puede existir una condición ELSE para ¬B. En muchos casos pueden existir alternativas múltiples (CASE) Las guardas son evaluadas en algún orden arbitrario. Elección no determinística. Si ninguna B es verdadera, el IF no tiene efecto
Title: Aspectos de la Programación Secuencial
? Sentencias de alternativa iterativa múltiple: DO B1 ? S1 B2 ? S2 ……. Bn ? Sn OD Las sentencias guardadas son evaluadas y ejecutadas hasta que todas las guardas sean falsas. (relacionar con el SELECT –ACCEPT de ADA). La elección es no determinística si más de una guarda es verdadera.
Title: Aspectos de la Programación Secuencial
La repetición e iteración tienen una forma general que se puede expresar con una instrucción del tipo FOR-ALL: FA cuantificadores =? Secuencia de Instrucciones AF Cada cuantificador especifica un rango de valores para una variable de iteración (con un rango y una condición Such That): variable = expr_inicial to expr_final st B El cuerpo del for-all se ejecuta una vez por cada valor de la variable de iteración. Si hay cláusula such-that, la variable de iteración toma sólo los valores para los que B es verdadera. Si hay más de un cuantificador el cuerpo del fa se ejecuta para cada combinación de valores.
Title: Concurrencia y Sincronización
Programa concurrente ? dos o más procesos cooperantes.
Múltiples threads de control (en el mismo t ?), uno por cada proceso.
Los procesos interactúan comunicándose ? sincronización
Problema ? interferencia: un proceso toma una acción que invalida las suposiciones hechas por otro proceso.
co S1 // ….. // Sn oc ejecuta las Si concurrentemente La ejecución del co termina cuando todas las Si teminaron
Title: Acciones atómicas y sincronización
Ejecución de un programa concurrente ? interleaving de las acciones atómicas ejecutadas por procesos individuales Interacción ? no todos los interleavings son aceptables.
La sincronización debe prevenir los interleavings indeseables. Sincronizar => Combinar acciones atómicas de grano fino (fine-grained) en acciones (compuestas) de grano grueso (coarse grained) que den la exclusión mutua. Sincronizar=> Demorar un proceso hasta que el estado de programa satisfaga algún predicado (por condición).
Title: Acciones atómicas y sincronización. Atomicidad de grano fino.
Acción atómica ? hace una transformación de estado indivisible Los estados intermedios en la implementación de la acción no deben ser visibles para los otros procesos =? Se debe implementar por Hardware. Analicemos la atomicidad de la operación de asignación… a:=b La lectura y escritura de las variables x,y,z son atómicas. y = 1; x = 0; z=2; co x = y + z // y = x + y // z = 4 oc =? Analicemos los posibles resultados si tenemos tres procesadores ejecutando los procesos concurrentes (no necesariamente de la misma velocidad)
Title: Acciones atómicas y sincronización. Atomicidad de grano fino.
Cuáles serían los posibles “threads” del programa concurrente especificado?? Qué sucedería si tenemos un cambio en el tercer proceso: y = 1; x = 0; z=2; co x = y + z // y = x + y // z = z – 1 oc Se podría probar corrección??
Title: Acciones atómicas y sincronización
En lo que sigue, supondremos máquinas con las siguientes características: Los valores de los tipos básicos se almacenan en elementos de memoria leídos y escritos como acciones atómicas Los valores se cargan en registros, se opera sobre ellos, y luego se almacenan los resultados en memoria Todo resultado intermedio de evaluar una expresión se almacena en registros o en memoria privada del proceso
Cada proceso tiene su propio conjunto de registros
Title: Acciones atómicas y sincronización
=? Si una expresión e en un proceso no referencia una variable alterada por otro proceso, la evaluación será atómica, aunque requiera ejecutar varias acciones atómicas de grano fino. ? Si una asignación x=e en un proceso no referencia ninguna variable alterada por otro proceso, la ejecución de la asignación será atómica ? De algún modo habrá que “proteger” la variable compartida o especificar un orden de precedencia en las posibles operaciones concurrentes. Pero… normalmente los programas concurrentes no son disjuntos
Title: Especificación de la sincronización.
En general, necesitamos ejecutar secuencias de sentencias como una única acción atómica =?Mecanismo de sincronización para construir una acción atómica de grano grueso (coarse grained) como secuencia de acciones atómicas fine grained que aparecen como indivisibles.
En lo que sigue ?e? indica que la expresión e debe ser evaluada atómicamente
Title: Especificación de la sincronización.
await se debe implementar en su forma más general (exclusión mutua y sincronización por condición) Sólo exclusión mutua ? ?S? Ejemplo: ? x = x + 1 ; y = y + 1 ? El estado interno en el cual x e y son incrementadas resulta invisible a los otros procesos que referencian x o y.
Title: Especificación de la sincronización.
Sincronización por condición ? ? await B ? Ejemplo: ? await count > 0 ?
?await B? puede ser implementado como busy waiting o spinning:
do (not B) ? skip od Acción atómica incondicional ? no contiene una condición B
Acción atómica condicional ? sentencia await con guarda B
Title: Propiedades de seguridad(safety) y vida(liveness) en Concurrencia
Una propiedad de un programa concurrente es un atributo que resulta verdadero para cualquiera de los threads de ejecución del mismo. Toda propiedad puede ser formulada en términos de dos clases de propiedades: seguridad y vida. La clase de propiedades de “seguridad” se refiere a la NO ocurrencia de eventos “malos”. Por ejemplo son clásicas las propiedades de seguridad ausencia de deadlock y ausencia de interferencia (exclusión mútua) entre procesos. La clase de propiedades de “vida” se refiere a la posibilidad de ocurrencia de eventos “buenos”. Por ejemplo son clásicas: asegurar que un pedido de servicio será atendido, asegurar que un mensaje llega a destino, que un proceso eventualmente alcanzará su sección crítica, etc=> dependen de las políticas de scheduling.
Title: Propiedades de procesos concurrentes
Fairness: trata de garantizar que los procesos tengan chance de avanzar, sin importar lo que hagan los demás
Una acción atómica en un proceso es elegible si es la próxima acción atómica en el proceso que será ejecutado Si hay varios procesos, hay varias acciones atómicas elegibles Una política de scheduling determina cuál será la próxima en ejecutarse
Title: Propiedades de procesos concurrentes
Fairness Incondicional. Una política de scheduling es incondicionalmente fair si toda acción atómica incondicional que es elegible eventualmente es ejecutada. Fairness Débil. Una política de scheduling es débilmente fair si es incondicionalmente fair y toda acción atómica condicional que se vuelve elegible eventualmente es ejecutada si su guarda se convierte en true y de allí en adelante permanece true. No es suficiente para asegurar que cualquier sentencia await elegible eventualmente se ejecuta: la guarda podría cambiar el valor (de false a true y nuevamente a false) mientras un proceso está demorado. (Recordar el caso de lectores-escritores de ADA)
Title: Propiedades de procesos concurrentes
Fairness Incondicional. Una política de scheduling es incondicionalmente fair si toda acción atómica incondicional que es elegible eventualmente es ejecutada. Fairness Fuerte: Una política de scheduling es fuertemente fair si es incondicionalmente fair y toda acción atómica condicional que se vuelve elegible eventualmente es ejecutada pues su guarda se convierte en true con infinita frecuencia. Relacionar lo anterior con los esquemas de scheduling que tienen “memoria”para favorecer a los procesos retrasados==> Prioridad dinámica.
| Página siguiente |