2. Escriba una definición de concurrencia. Diferencie procesamiento secuencial, concurrente y paralelo.
Concurrencia: es la capacidad de ejecutar múltiples actividades en paralelo o simultáneamente (o intercalando la ejecución de distintos programas secuencias). Permite a distintos objetos actuar al mismo tiempo.
Procesamiento secuencial: Es aquel donde las instrucciones se ejecutan una detrás de la otra, en un flujo lineal único.
determinístico: para los mismos datos de entrada, ejecuta siempre la misma secuencia de instrucciones y obtiene la misma salida.
Procesamiento Concurrente: Es aquel en el que varios programas (flujos) secuenciales pueden ejecutarse simultáneamente o de forma intercalada (interleaving), tanto en un unico procesador como en un multiprocesador
Procesamiento Paralelo: Es aquel en el que varios programas secuenciales se ejecutan simultáneamente, en distintos procesadores físicos, es decir, de forma paralela. (paralelismo full)
La concurrencia no es (sólo) paralelismo. Los programas concurrentes pueden ser no-determinísticos: pueden dar distintos resultados al ejecutarse sobre los mismos datos de entrada.
##3. Cuáles son las 3 grandes clases de aplicaciones concurrentes que podemos encontrar? Ejemplifique
Las grandes clases (superpuestas) de aplicaciones son:
- Sistemas multithreaded: maneja simultáneamente tareas independientes, asignando los procesadores de acuerdo a alguna política. Ej. sistemas de ventanas en sistemas operativos
- Sistemas de cómputo distribuido: red de comunicaciones vincula procesadores diferentes sobre los que se ejecutan procesos que se comunican esencialmente por mensajes. Ej. aplicación web cliente/servidor, servidor de archivos en una red
- Sistemas de cómputo paralelo: usando una arq. multiprocesador en la que se pueda distribuir la tarea global en tareas que puedan ejecutarse en distintos procesadores. Ej. aplicaciones de cómputo científicas, procesamiento de gráficos, realidad virtual.
##4. Describa el concepto de deadlock y qué condiciones deben darse para que ocurra.
Deadlock es un término que hace referencia al estado en el que varios procesos están ejecutándose concurrentemente y ninguno de ellos puede continuar con su ejecución debido a que cada uno de ellos depende de una condición que nunca será satisfecha por otro para poder seguir ejecutando sus instrucciones.
- Recursos de adquisición serial/secuencial: Los procesos comparten recursos que usan con exclusión mutua.
- Adquisición incremental: Los procesos mantienen los recursos que poseen mientras esperan adquirir recursos adicionales.
- No-preemption: Una vez que son adquiridos por un proceso, los recursos no pueden quitarse de manera forzada sino que sólo son liberados voluntariamente.
- Espera cíclica: Existe una cadena circular (ciclo) de procesos tal que c/u tiene un recurso que su sucesor en el ciclo está esperando adquirir.
##5. Defina inanición. Ejemplifique.
Inanición es el estado de un programa concurrente en el cual un proceso nunca logra acceder a un recurso compartido. Ejemplo: En una planificación de SJN, un proceso con mayor tiempo nunca podría ejecutar, si siempre se encolan otros procesos que tienen menor tiempo.
##6. Qué entiende por no determinismo? Cómo se aplica este concepto a la ejecución concurrente?
No determinismo es una propiedad (no exclusiva) de los programas concurrentes que indican que para distintas ejecuciones de un mismo programa con los mismos datos de entrada, genera diferentes datos de salida. En la ejecución concurrente las acciones no atómicas que pueden descomponerse en varias instrucciones de máquina atómicas, pueden ejecutarse de forma superpuesta con otras instrucciones atómicas de otro proceso, de forma aleatoria, de forma que los valores de variables compartidas podrían verse afectados de forma diferente (por lo random), y en consecuencia, producir diferentes resultados para las mismas operaciones sobre los mismos datos.
##7 Defina comunicación. Explique los mecanismos de comunicación que conozca.
La comunicación es el protocolo que especifica los modos con los que los procesos de un programa concurrente se organizan e intercambian información.
Memoria Compartida: El intercambio de información se da sobre memoria accesible a todos los procesos, con exclusión mutua, lo que significa que no pueden operar simultáneamente sobre los mismos datos.
Pasaje de Mensajes: El intercambio de información se da a través de canales lógicos o físicos.
##8. Sincronización
- a) Defina sincronización. Explique los mecanismos de sincronización que conozca.
- b) En un programa concurrente pueden estar presentes más de un mecanismo de sincronización? Ejemplifique
Sincronización es la forma en que los procesos orquestran su ejecución de forma de limitar el trace de ejecución a aquellos que producen resultados aceptables.
Exclusión mutua: Consiste en asegurar que las secciones críticas de sentencias que acceden a objetos compartidos no se ejecuntan al mismo tiempo. Sincronización por condición: asegura que un proceso se demora si es necesario hasta que sea verdadera una condición dada.
Puede estar presente más de un mecanismo, por ejemplo un programa con varios procesos que deben actualizar varias variables compartidas que se sincronizan con barreras para comenzar la modificación de la siguiente variable.
##9.
- a) Analice en qué tipo de problemas son más adecuados cada uno de los 5 paradigmas de resolución de problemas concurrentes descriptos en clase.
- b) Qué relación encuentra entre el paralelismo recursivo y la estrategia de “dividir y conquistar”? Cómo aplicaría este concepto a un problema de ordenación de un arreglo (por ejemplo usando un algoritmo de tipo “quicksort” o uno de tipo “sorting by merging”).?
- c) Mencione algún sistema de tipo cliente/servidor que conozca.
##10.
a) Analizando el código de multiplicación de matrices en paralelo planteado en la teoría, y suponiendo que N=256 y P=8 indique cuántas asignaciones, cuántas sumas y cuántos productos realiza cada proceso. Cuál sería la cantidad de cada operación en la solución secuencial realizada por un único proceso?
a) 8388608 sumas, 4210690 asignaciones, 2097153 productos cada procesador. multiplicar cada uno por 8 para saber la cantidad de cada operación en el algoritmo secuencial.
b) Si los procesadores P1 a P7 son iguales, y sus tiempos de asignación son 1, de suma 2 y de producto 3, si el procesador P8 es 4 veces más lento, cuánto tarda el proceso total concurrente? Cuál es el valor del speedup? Cómo podría modificar el código para mejorar el speedup?
b) P1 a P7 tardan: 8388608x2 en sumar + 4210690x1 en asignar + 2097153x3 en multiplicar = 27279365 unidades de tiempo P8 tarda 27279365x4 = 109117460 unidades de tiempo El proceso total tarda 109117460 unidades de tiempo, igual que P8. El tiempo secuencial es de 27279365x8 = 218234920 unidades de tiempo (asumiendo que el procesador que ejecuta dicho programa es tan veloz como P1). El speedup del algoritmo es Ts/Tp = 218234920/109117460 = 2. El speedup podría modificarse reasignando strips de la matriz de manera que los procesadores más rápidos tomen más filas, y P8 menos, así, se equilibraria la diferencia de tiempos y en consecuencia mejoraría el tiempo paralelo y el speedup.
##11.
a) Cómo puede influir la topología de conexión de los procesadores en el diseño de aplicaciones concurrentes/paralelas/distribuidas? Ejemplifique.
La topología influye fuertemente en el algoritmo que conviene implementar para la resolución del problema. Por ejemplo, una topología en forma de estrella facilita la implementación de un algoritmo centralizado, en lugar de uno descentralizado, para minimizar la cantidad de comunicaciones (mensajes o accesos a recursos compartidos) que se realizan. La granularidad de la aplicación determina la relación entre la cantidad de computación que se realiza y la comunicación, por lo que una arquitectura con procesadores veloces y un canal lento maximizará la performance de una aplicación de grano grueso, mientras que una con procesadores lentos pero un canal de comunicación veloz maximizará la de una de grano fino, porque la comunicación resulta barata en comparación al cómputo.
##12. Qué significa el problema de “interferencia” en programación concurrente? Cómo puede evitarse?
La interferencia sucede cuando un proceso se ejecuta luego de otro, y utiliza datos que el otro estaba consumiendo, invalidando el estado del proceso previo.
##13. En qué consiste la propiedad de “A lo sumo una vez” y qué efecto tiene sobre las sentencias de un programa concurrente? De ejemplos de sentencias que cumplan y de sentencias que no cumplan con ASV.
A lo sumo una vez especifica que dada la expresión x = e, cumple con la regla si:
- e contiene a lo sumo una referencia crítica y x no es referenciada por otro proceso. o
- e no contiene referencias críticas, en cuyo caso x puede ser leída por otro proceso.
##14. Dado el siguiente programa concurrente:
x = 2; y = 4; z = 3;
co
x = y - z // z = x * 2 // y = y - 1
oc
cumple y = y - 1
Nota 1: las instrucciones NO SON atómicas. Nota 2: no es necesario que liste TODOS los resultados pero si los que sean representativos de las diferentes situaciones que pueden darse.