next_inactive up previous



Examen de Programación Concurrente sep02






Dpto. LSIIS. Unidad de Programación

Normas

Esta prueba consta de dos partes diferenciadas. La primera, cuyo enunciado estás leyendo en este momento, contiene la primera pregunta y se recogerá una hora y media después de haberse entregado. Después se entregará el enunciado de la segunda parte, con las preguntas 2 y 3. Debe contestarse a cada pregunta en hojas separadas. La puntuación total del examen es de 10 puntos.

Las soluciones aparecerán publicadas antes de la fecha de revisión y las calificaciones se darán a conocer el martes 24 de septiembre. La revisión de este examen tendrá lugar el jueves 26 de septiembre.

Ordenación por burbuja - Análisis [1 hora 30 min., 3 puntos]

Se pretende dar una solución concurrente al problema de la ordenación de una secuencia de $ n$ datos ($ n>2$), basándonos en el algoritmo que se explicará a continuación. La idea consiste en utilizar $ n-1$ procesos intercambiadores más un par de procesos Productor y Consumidor que se encargan de rellenar la secuencia y de leerla una vez ordenada. Cada intercambiador controla dos posiciones consecutivas de la secuencia, y se ocupa de garantizar en cada momento la ordenación relativa de los elementos ubicados en dichas posiciones. La ordenación de la secuencia se consigue finalmente a base de realizar ordenaciones parciales de parejas de elementos situados en posiciones consecutivas. Distinguimos procesos intercambiadores pares e impares: un proceso de tipo par controla dos posiciones de índices $ (2i, 2i+1) $, y un proceso de tipo impar controla las posiciones $ (2i+1,2i+2)$ para algún índice $ i$. El siguiente dibujo expone la estructura de procesos para una secuencia de longitud 8:
\epsfig{figure=estructura8.eps,width=10cm}
Para simplificar el diseño de la solución, vamos a suponer que la ordenación se realiza en etapas sucesivas, en las que actúa exclusivamente un tipo de procesos, de tipo par o impar. Hay alternancia estricta de etapas de uno y otro tipo, es decir, un proceso de un tipo actúa sólo cuando todos los procesos del tipo complementario han completado su trabajo en la etapa anterior. En cada etapa, los procesos intercambiadores a los que les toca actuar se ocupan de comprobar si los elementos que en ese momento ocupan las dos posiciones que el proceso controla están ordenados crecientemente y, si no es así, procede a intercambiarlos. Las etapas se suceden de forma alterna, tal cual se ha dicho, hasta que finalmente la secuencia se encuentra totalmente ordenada. A este respecto, conviene observar que si en una etapa de cualquiera de los dos tipos - exceptuando la primera - no es necesario reordenar ningún par de elementos, se puede concluir que la secuencia ya está ordenada, y será necesario programar la terminación de los procesos (se quiere ordenar una única secuencia). La decisión sobre si la primera etapa debe ser de un tipo u otro es indiferente, no afecta a la corrección del algoritmo. Se quiere diseñar una solución que permita que los procesos de un mismo tipo puedan trabajar con simultaneidad en el desarrollo de una etapa, es decir, deben poder ejecutar simultáneamente las operaciones de acceso y, en su caso, modificación, de los elementos asociados a las posiciones correspondientes (obsérvese que procesos distintos de un mismo tipo acceden a posiciones disjuntas). Se debe analizar la sincronización necesaria entre los procesos para que el funcionamiento del algoritmo responda a esta organización en etapas. Se intentará especificar dicha interacción en función de la información mínima que deben compartir los procesos para satisfacer las exigencias del enunciado.


A título meramente descriptivo - es decir, no se añade nada a la especificación anterior - incluimos el siguiente ejemplo que refleja la evolución del sistema a partir de una secuencia de entrada concreta.
\epsfig{figure=fig2.eps}

Se pide:

que el alumno realice la fase de análisis de la concurrencia y proporcione los siguientes documentos:
a)
Grafo de procesos y recursos.
b)
Especificación formal del recurso necesario para la sincronización de los procesos.
c)
Código de los procesos en función de la interfaz del recurso especificado.




next_inactive up previous
Manuel Carro
2002-09-26