Examen de Programación Concurrente
sep02
Dpto. LSIIS. Unidad de Programación
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.
Se pretende dar una solución concurrente al problema de la
ordenación de una secuencia de
datos (
), basándonos en el
algoritmo que se explicará a continuación.
La idea consiste en utilizar
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
,
y un proceso de tipo impar controla las posiciones
para algún índice
.
El siguiente dibujo expone la estructura de procesos para una secuencia de
longitud 8:
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.
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.
Manuel Carro
2002-09-26