Sistemas Concurrentes y Distribuidos: Enunciados de Problemas - PDF

Sistemas Concurrentes y Distribuidos: Enunciados de Problemas. Dpt. Lenguajes y Sistemas Informáticos ETSI Informática y de Telecomunicación Universidad de Granada Curso 2024-25 SCD (24-25). Índice general. PDF creado: 11 de octubre de 2024 Pág. 2 / 41 Índice general 1. Introducción 5 Problema 1.................................................. 5 Problema 2.................................................. 5 Problema 3.................................................. 6 Problema 4.................................................. 6 Problema 5.................................................. 7 Problema 6.................................................. 8 Problema 7.................................................. 8 Problema 8.................................................. 9 Problema 9.................................................. 10 Problema 10.................................................. 12 Problema 11.................................................. 12 Problema 12.................................................. 13 2. Sincronización en memoria compartida. 15 Problema 13.................................................. 15 Problema 14.................................................. 15 Problema 15.................................................. 16 Problema 16.................................................. 17 Problema 17.................................................. 17 Problema 18.................................................. 17 Problema 19.................................................. 17 Problema 20.................................................. 18 Problema 21.................................................. 19 Problema 22.................................................. 19 Problema 23.................................................. 20 Problema 24.................................................. 20 Problema 25.................................................. 21 Problema 26.................................................. 22 Problema 27.................................................. 23 3 SCD (24-25). Índice general. Problema 28.................................................. 23 Problema 29.................................................. 23 Problema 30.................................................. 24 3. Sistemas basados en paso de mensajes. 27 Problema 31.................................................. 27 Problema 32.................................................. 27 Problema 33.................................................. 28 Problema 34.................................................. 28 Problema 35.................................................. 29 Problema 36.................................................. 30 Problema 37.................................................. 30 Problema 38.................................................. 31 Problema 39.................................................. 32 Problema 40.................................................. 33 Problema 41.................................................. 34 Problema 42.................................................. 35 Problema 43.................................................. 35 Problema 44.................................................. 36 Problema 45.................................................. 36 Problema 46.................................................. 36 Problema 47.................................................. 37 4. Sistemas de Tiempo Real. 39 Problema 48.................................................. 39 Problema 49.................................................. 39 Problema 50.................................................. 39 Problema 51.................................................. 40 Problema 52.................................................. 40 Problema 53.................................................. 40 Problema 54.................................................. 40 PDF creado: 11 de octubre de 2024 Pág. 4 / 41 Tema 1 Introducción 1 Considerar el siguiente fragmento de programa para 2 procesos P1 y P2 : Los dos procesos pueden ejecutarse a cualquier velocidad. ¿ Cuáles son los posibles valores resultantes para x ?. Suponer que x debe ser cargada en un registro para incrementarse y que cada proceso usa un registro diferente para realizar el incremento. { variables compartidas } var x : integer := 0 ; process P1 ; process P2 ; var i : integer ; var j : integer ; begin begin for i := 1 to 2 do begin for j := 1 to 2 do begin x := x+1 ; x := x+1 ; end end end end 2 Dada la declaración de proceso secuencial (que forma parte de un programa concurrente) que aparece abajo, donde S es una sentencia que puede ser simple o compuesta, indica, razonando la respuesta, qué versiones de S son sentencias atómicas y cuáles no lo son. Para aquellas sentencias no atómicas, dar la traza detallada indicando aquel estado o estados que sean accesibles por otros procesos secuenciales. { Declaraci ón variables globales } var x : integer := 0; z : integer := 2; { Procesos } process P; var i : integer := 0; j : integer := 1; begin S; end (a) S ≡ z:=i+1; (b) S ≡ z:=2*x+j; 5 SCD (24-25). Tema 1: Introducción. (c) S ≡ i:=z+j; (d) S ≡ i:=i+j; x:=i+1; (e) S ≡ x:=x+j; (f) S ≡ j:=z+2; i:=i*5+j; j:=j+1; (g) S ≡ j:=i+2; i:=j+1; x:=j+i; (h) S ≡ x:=2*z+x; (i) S ≡ i:=2*i+j+3; j:=j+i*i; (j) S ≡ j:=z+2*x; 3 Dado el programa concurrente que se muestra abajo, responde a cada una de estas cuestiones: (a) indica cómo se descomponen las sentencias de cada proceso en secuencias de sentencias que únicamente hacen operaciones aritméticas en los registros, (b) indica como se descomponen las sentencias de cada proceso en un número mínimo de sentencias atómicas, (c) proporciona todos los posibles valores que puede tomar la variable x al finalizar la ejecución del programa, (d) proporciona una traza (en base a las sentencias del caso (a)) para cada valor diferente de x que se pueda obtener al finalizar la ejecución concurrente, (e) indica cuantas interfoliaciones posibles hay de las sentencias del caso (a) y cuantas del caso (b). { Variables compartidas } var x : integer := 0 ; process P0; process P1; var i0 : integer := 3 ; var i1 : integer := 1 ; begin begin x:= 2*i0+1; x:= x+i1; end end 4 Consideramos un programa concurrente en el cual varios procesos comparten dos variables enteras x e y, y que- remos que siempre se cumpla x+y == 10. PDF creado: 11 de octubre de 2024 Pág. 6 / 41 SCD (24-25). Tema 1: Introducción. Apartado (a) Dado un valor n cualquiera (puede ser una constante o una variable local), para asignarle n a la variable x (y ac- tualizar adecuadamente y) todos los procesos usan alguna de estas tres sentencias alternativas (todos la misma): { Opción 1 } { Opción 2 } { Opción 3 } begin begin begin x:= n; ; < x:= n; y:= 10-n; ; y:= 10-n; > end end end Para cada opción: describe razonadamente si la opción es correcta. Se considera correcta una opción si, al ejecutarse la sentencia bloque en un estado previo en el cual se cumple x+y==10, se garantiza que siempre en el estado inmediatamente posterior se cumplirá x+y==10. Apartado (b) Para verificar que la suma de ambas variables siempre es 10, escribimos código que imprime dicha suma. Los procesos podrán ejecutar ese código en cualquier momento, de forma concurrente con los procesos que actualizan x e y. Para ello, todos los procesos usarán una variable local propia (a) y alguna de las siguientes sentencias alternativas (todos la misma): { Opción 1 } { Opción 2 } { Opción 3 } begin begin begin a:= x+y; < a:= x+y >; < a:= x+y; print(a); print(a); print(a); > end end end Para cada opción: describe razonadamente si la opción es correcta. Se considera correcta una opción si, al ejecutarse la sentencia bloque en un estado previo con x+y==10, se garantiza que siempre se imprimirá el valor 10. Además, responde a esta pregunta: ¿ es atómica la sentencia begin-end de la opción 2 ? 5 ¿ Cómo se podría hacer la copia del fichero f en otro g, de forma concurrente, utilizando la instrucción concurrente cobegin-coend ?. Para ello, suponer que: los archivos son secuencia de items de un tipo arbitrario T, y se encuentran ya abiertos para lectura (f) y escritura (g). Para leer un ítem de f se usa la llamada a función leer(f) y para saber si se han leído todos los ítems de f, se puede usar la llamada fin(f) que devuelve verdadero si ha habido al menos un intento de leer cuando ya no quedan datos. Para escribir un dato x en g se puede usar la llamada a procedimiento escribir(g,x). El orden de los ítems escritos en g debe coincidir con el de f. PDF creado: 11 de octubre de 2024 Pág. 7 / 41 SCD (24-25). Tema 1: Introducción. Dos accesos a dos archivos distintos pueden solaparse en el tiempo. Para ilustrar como se accede a los archivos, aquí se encuentra una versión secuencial del código que copia f sobre g: process CopiaSecuencial ; var v : T ; begin v := leer(f) ; { lectura adelantada } while not fin(f) do begin escribir(g,v); { leer de la variable v y escribir en el archivo g } v := leer(f); { leer del archivo f y escribir variable v } end end 6 Construir, utilizando las instrucciones concurrentes cobegin-coend y fork-join, programas concurrentes que se correspondan con los grafos de precedencia que se muestran a continuación: 7 Dados los siguientes fragmentos de programas concurrentes, obtener sus grafos de precedencia asociados: PDF creado: 11 de octubre de 2024 Pág. 8 / 41 SCD (24-25). Tema 1: Introducción. begin begin P0 ; P0 ; cobegin cobegin P1 ; begin P2 ; cobegin cobegin P1;P2; P3 ; P4 ; P5 ; P6 ; coend coend P5; P7 ; end coend begin P8; cobegin end P3;P4; coend P6; end coend P7 ; end 8 Suponer un sistema de tiempo real que dispone de un captador de impulsos conectado a un contador de ener- gía eléctrica. La función del sistema consiste en contar el número de impulsos producidos en 1 hora (cada Kwh consumido se cuenta como un impulso) e imprimir este número en un dispositivo de salida. Para ello se dispone de un programa concurrente con 2 procesos: un proceso acumulador (lleva la cuenta de los impulsos recibidos) y un proceso escritor (escribe en la impresora). En la variable común a los 2 procesos n se lleva la cuenta de los impulsos. El proceso acumulador puede invocar un procedimiento Espera_impulso para esperar a que llegue un impulso, y el proceso escritor puede llamar a Espera_fin_hora para esperar a que termine una hora. El código de los procesos de este programa podría ser el siguiente: { variable compartida: } var n : integer; { contabiliza impulsos } process Acumulador ; process Escritor ; begin begin while true do begin while true do begin Espera_impulso(); Espera_fin_hora(); < n := n+1 > ; { (1) } write( n ) ; { (2) } end < n := 0 > ; { (3) } end end end En el programa se usan sentencias de acceso a la variable n encerradas entre los símbolos < y >. Esto significa que cada una de esas sentencias se ejecuta en exclusión mutua entre los dos procesos, es decir, esas sentencias se ejecutan de principio a fin sin entremezclarse entre ellas. PDF creado: 11 de octubre de 2024 Pág. 9 / 41 SCD (24-25). Tema 1: Introducción. Supongamos que en un instante dado el acumulador está esperando un impulso, el escritor está esperando el fin de una hora, y la variable n vale k. Después se produce de forma simultánea un nuevo impulso y el fin del periódo de una hora. Obtener las posibles secuencias de interfolicación de las instrucciones (1),(2), y (3) a partir de dicho instante, e indicar cuales de ellas son correctas y cuales incorrectas (las incorrectas son aquellas en las cuales el impulso no se contabiliza). 9 Supongamos un programa concurrente en el cual hay, en memoria compartida dos vectores a y b de enteros y con tamaño par, declarados como sigue: var a,b : array[0..2*n-1] of integer ; { n es una constante predefinida (>2) } Queremos escribir un programa para obtener en b una copia ordenada del contenido de a (nos da igual el estado en que queda a después de obtener b). Para ello disponemos de la función Sort que ordena un tramo de a (entre las entradas s, incluida, y t, no incluida), usando el método de la burbuja. También disponemos la función Copiar, que copia un tramo de a (desde s, incluido, hasta t, sin incluir) sobre b (a partir de o). procedure Sort( s,t : integer ); procedure Copiar( o,s,t : integer ); var i, j : integer ; var d : integer ; begin begin for i := s to t-1 do for d := 0 to t-s-1 do for j:= s+1 to t-1 do b[o+d] := a[s+d] ; if a[i] < a[j] then end swap( a[i], a[j] ) ; end La función swap intercambia dos variables. El programa para ordenar se puede implementar de dos formas: Ordenar todo el vector a, de forma secuencial con la función Sort, y después copiar cada entrada de a en b, con la función Copiar. Ordenar las dos mitades de a de forma concurrente, y después mezclar dichas dos mitades en un segundo vector b (para mezclar usamos un procedimiento Merge). A continuación vemos el código de ambas versiones: procedure Secuencial() ; procedure Concurrente() ; var i : integer ; begin begin cobegin Sort( 0, 2*n ); { ordena a } Sort( 0, n ); Copiar( 0, 0, 2*n ); { copia a en b } Sort( n, 2*n ); end coend Merge( 0, n, 2*n ); end PDF creado: 11 de octubre de 2024 Pág. 10 / 41 SCD (24-25). Tema 1: Introducción. El código de Merge se encarga de ir leyendo las dos mitades de a. En cada paso primero se selecciona el menor elemento de los dos siguientes por leer (uno en cada mitad), y después se escribe dicho menor elemento en la siguiente mitad del vector mezclado b. Al acabar este bucle, será necesario copiar el resto de elementos no leídos de una de las dos mitades. El código es el siguiente: procedure Merge( inferior, medio, superior: integer ) ; var escribir : integer := 0 ; { siguiente posicion a escribir en b } var leer1 : integer := inferior ; { siguiente pos. a leer en primera mitad de a } var leer2 : integer := medio ; { siguiente pos. a leer en segunda mitad de a } begin { mientras no haya terminado con alguna mitad } while leer1 < medio and leer2 < superior do begin if a[leer1] < a[leer2] then begin { minimo en la primera mitad } b[escribir] := a[leer1] ; leer1 := leer1 + 1 ; end else begin { minimo en la segunda mitad } b[escribir] := a[leer2] ; leer2 := leer2 + 1 ; end escribir := escribir+1 ; end { se ha terminado de copiar una de las mitades, copiar lo que quede de la otra } if leer2 >= superior then Copiar( escribir, leer1, medio ); { copiar primera } else Copiar( escribir, leer2, superior ); { copiar segunda } end Llamaremos Ts (k) al tiempo que tarda el procedimiento Sort cuando actua sobre un segmento del vector con k entradas. Suponemos que el tiempo que (en media) tarda cada iteración del bucle interno que hay en Sort es la unidad (por definición). Es evidente que ese bucle tiene k(k − 1)/2 iteraciones, luego: k(k − 1) 1 1 Ts (k) = = k2 − k 2 2 2 El tiempo que tarda la versión secuencial sobre 2n elementos (llamaremos S a dicho tiempo) será el tiempo de Sort (Ts (2n)) más el tiempo de Copiar (que es 2n, pues copiar un elemento tarda una unidad de tiempo), luego 1 1 S = Ts (2n) + 2n = (2n)2 − (2n) + 2n = 2n2 + n 2 2 con estas definiciones, calcula el tiempo que tardará la versión paralela, en dos casos: (1) Las dos instancias concurrentes de Sort se ejecutan en el mismo procesador (llamamos P1 al tiempo que tarda). (2) Cada instancia de Sort se ejecuta en un procesador distinto (lo llamamos P2 ) escribe una comparación cualitativa de los tres tiempos (S,P1 y P2 ). Para esto, hay que suponer que cuando el procedimiento Merge actua sobre un vector con p entradas, tarda p unidades de tiempo en ello, lo cual es razonable teniendo en cuenta que en esas circunstancias Merge copia p valores desde a hacia b. Si llamamos a este tiempo Tm (p), podemos escribir Tm (p) = p PDF creado: 11 de octubre de 2024 Pág. 11 / 41 SCD (24-25). Tema 1: Introducción.. 10 Supongamos que tenemos un programa con tres matrices (a,b y c) de valores flotantes declaradas como varia- bles globales. La multiplicación secuencial de a y b (almacenando el resultado en c) se puede hacer mediante un procedimiento MultiplicacionSec declarado como aparece aquí: var a, b, c : array[1..3,1..3] of real ; procedure MultiplicacionSec() var i,j,k : integer ; begin for i := 1 to 3 do for j := 1 to 3 do begin c[i,j] := 0 ; for k := 1 to 3 do c[i,j] := c[i,j] + a[i,k]*b[k,j] ; end end Escribir un programa con el mismo fin, pero que use 3 procesos concurrentes. Suponer que los elementos de las matrices a y b se pueden leer simultáneamente, así como que elementos distintos de c pueden escribirse simultá- neamente. 11 Un trozo de programa ejecuta nueve rutinas o actividades (P1 , P2 ,... , P9 ), repetidas veces, de forma concurren- temente con cobegin coend (ver la figura de la izquierda), pero que requieren sincronizarse según determinado grafo (ver la figura de la derecha): Trozo de programa: Grafo de sincronización: while true do cobegin PP11 PP22 PP33 P1 ; P2 ; P3 ; P4 ; P5 ; P6 ; P7 ; P8 ; P9 ; PP44 PP55 PP66 coend PP77 PP88 PP99 Supón que queremos realizar la sincronización indicada en el grafo, usando para ello llamadas desde cada rutina a dos procedimientos (EsperarPor y Acabar). Se dan los siguientes hechos: PDF creado: 11 de octubre de 2024 Pág. 12 / 41 SCD (24-25). Tema 1: Sincronización en memoria compartida.. El procedimiento EsperarPor(i) es llamado por una rutina cualquiera (la número k) para esperar a que termine la rutina número i, usando espera ocupada. Por tanto, se usa por la rutina k al inicio para esperar la terminación de las otras rutinas que corresponda según el grafo. El procedimiento Acabar(i) es llamado por la rutina número i, al final de la misma, para indicar que dicha rutina ya ha finalizado. Ambos procedimientos pueden acceder a variables globales en memoria compartida. Las rutinas se sincronizan única y exclusivamente mediante llamadas a estos procedimientos, siendo la implementación de los mismos completamente transparente para las rutinas. Escribe una implementación de EsperarPor y Acabar (junto con la declaración e inicialización de las variables compartidas necesarias) que cumpla con los requisitos dados. 12 En el problema anterior los procesos P1, P2,..., P9 se ponen en marcha usando cobegin/coend. Escribe un programa equivalente, que ponga en marcha todos los procesos, pero que use declaración estática de procesos, usando un vector de procesos P, con índices desde 1 hasta 9, ambos incluidos. El proceso P[n] contiene un bucle infinito, y en cada iteración se ejecuta Pn. Ejecutar Pn supone incluir las llamadas necesarias a EsperarPor (con la misma implementación que antes), luego una secuencia de instrucciones Sn, y finalmente las llamada a Acabar. Se incluye aquí un plantilla: Process P[ n : 1..9 ] begin while true do begin..... { esperar (si es necesario) a los procesos que corresponda } Sn ; { sentencias específicas de este proceso (desconocidas) }..... { señalar que hemos terminado } end end PDF creado: 11 de octubre de 2024 Pág. 13 / 41 SCD (24-25). Tema 1: Sincronización en memoria compartida.. PDF creado: 11 de octubre de 2024 Pág. 14 / 41 Tema 2 Sincronización en memoria compartida. 13 ¿Podría pensarse que una posible solución al problema de la exclusión mutua, sería el siguiente algoritmo que no necesita compartir una variable Turno entre los 2 procesos? (a) ¿Se satisface la exclusión mutua? (b) ¿Se satisface la ausencia de interbloqueo? { variables compartidas y valores iniciales } var b0 : boolean := false , { true si P0 quiere acceder o está en SC } b1 : boolean := false ; { true si P1 quiere acceder o está en SC } 1 Process P0 ; process P1 ; 1 2 begin begin 2 3 while true do begin while true do begin 3 4 { protocolo de entrada: } { protocolo de entrada: } 4 5 b0 := true ; {indica quiere entrar} b1 := true ; {indica quiere entrar} 5 6 while b1 do begin {si el otro también: } while b0 do begin {si el otro también: } 6 7 b0 := false ; {cede temporalmente } b1 := false ; {cede temporalmente } 7 8 while b1 do begin end {espera } while b0 do begin end {espera } 8 9 b0 := true ; {vuelve a cerrar paso} b1 := true ; {vuelve a cerrar paso} 9 10 end end 10 11 { seccion critica.... } { seccion critica.... } 11 12 { protocolo de salida } { protocolo de salida } 12 13 b0 := false ; b1 := false ; 13 14 { resto sentencias.... } { resto sentencias.... } 14 15 end end 15 16 end end 16 14 Al siguiente algoritmo se le conoce como solución de Hyman al problema de la exclusión mutua. ¿Es correcta dicha solución? 15 SCD (24-25). Tema 2: Sincronización en memoria compartida.. { variables compartidas y valores iniciales } var c0 : integer := 1 ; c1 : integer := 1 ; turno : integer := 1 ; 1 process P0 ; process P1 ; 1 2 begin begin 2 3 while true do begin while true do begin 3 4 c0 := 0 ; c1 := 0 ; 4 5 while turno != 0 do begin while turno != 1 do begin 5 6 while c1 = 0 do begin end while c0 = 0 do begin end 6 7 turno := 0 ; turno := 1 ; 7 8 end end 8 9 { seccion critica } { seccion critica } 9 10 c0 := 1 ; c1 := 1 ; 10 11 { resto sentencias } { resto sentencias } 11 12 end end 12 13 end end 13 15 Se tienen 2 procesos concurrentes que representan 2 máquinas expendedoras de tickets (señalan el turno en que ha de ser atendido el cliente), los números de los tickets se representan por dos variables n1 y n2 que valen inicialmente 0. El proceso con el número de ticket más bajo entra en su sección crítica. En caso de tener 2 números iguales se procesa primero el proceso número 1. a) Demostrar que se verifica la ausencia de interbloqueo (progreso), la ausencia de inanción (espera limitada) y la exclusión mutua. b) Demostrar que las asignaciones n1:=1 y n2:=1 son ambas necesarias. Para ello { variables compartidas y valores iniciales } var n1 : integer := 0 ; n2 : integer := 0 ; process P1 ; process P2 ; begin begin while true do begin while true do begin n1 := 1 ; { E1.1 } n2 := 1 ; { E1.2 } n1 := n2+1 ; { L1.1 ; E2.1 } n2 := n1+1 ; { L1.2 ; E2.2 } while n2 != 0 and { L2.1 } while n1 != 0 and { L2.2 } n2 < n1 do begin end;{ L3.1 } n1

Sistemas Concurrentes y Distribuidos: Enunciados de Problemas - PDF

Document Details

Tags

Related

Summary

Full Transcript