PDF de programación - PROGRAMACION CONCURRENTE Y DISTRIBUIDA - V.2 Redes de Petri: Implementación.

PROGRAMACION CONCURRENTE Y

DISTRIBUIDA

V.2 Redes de Petri: Implementación.

J.M. Drake

Notas:

1

Diseño basado en modelos

Diseño del
sistema

Propiedades cualitativas

Comportamiento

Planificación

Modelo del

Sistema
(Petri net)

Fase de diseño

Sistema

implementado

Controlador

Sistema real

controlado/monitorizado

Fase de ejecución

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

2

Notas:

2

Ventajas de utilizar redes de Petri

sincronización,

Facilidad para modelar características relevantes de sistemas
concurrentes; Concurrencia,
conflictos,
exclusión mutua, bloqueos, etc.
Buena visualización de las dependencias entre elementos del sistema
Capacidad de sucesivas vistas Top-Down (Refinamiento del modelo).
Capacidad de sucesivas vistas Bottom-Up (Composición modular).
Capacidad de implementar el sistema a partir del modelo.
Capacidad de validar el sistema contra patologías (Bloqueos,
inestabilidad, ilimitación, etc.)
Análisis de comportamiento
respuesta,
frecuencia de generación, utilización de recursos, etc.) sin
necesidad de simulación o ejecución de pruebas.
Posibilidad de análisis y animación mediante simuladores
basados en eventos discretos.

(velocidad de

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

3

Notas:

3

Parte de control y parte operativa

Para facilitar el diseño y mantenimiento del proceso de
control de un sistema físico, se descompone el controlador en
dos subsistema:
Parte operativa (PO): Ejecuta

los comandos de control y

monitorización del sistema real.

Parte de control o mando (PC): Parte inteligente que dirige la

estrategia de control y monitorización.

Sistema físico
controlado

Consignas

PC

PO

Controlador

Acciones

Eventos

Datos

Salidas
monitorizacón

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

4

Notas:

4

Formas de implementar una red de Petri

Implementación cableada (Lógica electrónica)
Implementación con PLAs (Matrices lógicas programables)
Implementación con computadores:
Flexibilidad frente a los cambios.
Potencia al poder integrar funciones complejas
Reducción del coste de desarrollo y fabricación.
Aumento de la fiabilidad de la operación:
Disminución del número de componentes
Tecnología mas fiable
Mayor capacidad de auto-diagnóstico.

Posibilidad de gestión distribuida

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

5

Notas:

5

Implementación de una RdeP mediante programa

Implementación programada de una RdeP: Es un programa
que simula el disparo de transiciones de la RdeP, respetando
la reglas de evolución del modelo teórico.

Diferencias entre el modelo teórico y la implementación:
Modelo teórico: El disparo de una transición es instantáneo e

indivisible.

No hay código asociado a la transición

Modelo programado: El disparo de una transición no es ni instantáneo

ni indivisible.

Existe un código asociado a la transición => Varias fases en el disparo:

Retirada de marcas de los lugares de entrada
Ejecución del código asociado
Depósito de marcas en los lugares de salida

ESTADO RdeP:= marcado + estado interno de las transiciones en disparo

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

6

Notas:

6

Modelo de representación

Entradas: Estado del sistema real que se controla u ordenes del operador del
sistema:
Eventos: Espera su llegada para que evolucione el sistema.

Polling: Periódicamente se exlora su estado.
Interrupción: Su llegada cambia el flujo del programa.

Entradas de nivel:

Lectura asíncrona: Las entradas se leen cuando se necesitan para tomar decisiones

(produce aleatoriedad)

Lectura síncrona: Todas las entradas se leen simultáneamente, y en función de sus

valores almacenados se toman las decisiones de control.

Salidas: Variables de control del sistema real, mensajes de monitorización:
Acciones. Tiempo breve y semántica “se inician para ser terminadas”

Se asocian a la ocurrencia del disparo de una transición.

Actividades:: Tiempos prolongados y semántica “se ejecuta hasta que sea

interrumpida”

Se asocian a la presencia de un testigo en una plaza.

Se pueden generar asíncronamente (cuando se calculan) o síncronamente

(simultáneamente al final).

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

7

Notas:

7

Implementación de las actividades

Transición temporizada

Plaza ocupada por testigo

Ejecución
del código

Se inicia código

Ejecutando
código

Se finaliza código

• Transición no instantánea
•Requieren nuevas normas
de gestión de los eventos

• Transiciones instantáneas
• No se requieren nuevas normas
de gestión de los eventos

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

8

Notas:

8

Tipos de implementaciones(1)

Interpretadas:La estructura de la RdeP y su marcado se
codifican en estructuras de datos de las cuales uno o varios
programas extraen la información para hacer evolucionar la
RdeP.
La RdeP se codifica como una estructura de datos.
Requieren un interprete que es independiente de la topología de la

RdeP

Compiladas: Se generan uno o varios programas cuyos flujos
de control reproducen el comportamiento de la RdeP.

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

9

Notas:

9

Tipos de implementación (2)

Secuencial: Un único proceso ejecuta la RdeP
Si hay código asociado a las transiciones => El único proceso secuencializa

su ejecución.

El orden en el que el proceso dispara las transiciones es crítica.

Retrasos sistemáticos.
Resolución determinista de los conflictos.

t2 y t3 se retrasan
sistemáticamente por t1

t1

100

1

t2

1

t3

Esta clase de implementación es adecuada para aplicaciones cuya parte
operacional está compuesta por acciones cuyo tiempo de ejecución es
irrelevante.

Concurrente: Varios procesos inter-actuantes ejecutan la RdeP
En entorno monoprocesador => no hay concurrencia sino entrelazado

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

10

Notas:

10

Tipos de implementación (3)

Centralizada: La interpretación de la RdeP se implementa con
un único proceso (coordinador) que actúa sobre la totalidad
de la red.
La parte operacional de
ejecutada secuencialmente o concurrentemente.

implementación puede ser

la

Descentralizada: La RdeP se descompone en diferentes
subredes, y de la evolución de cada una de ellas se realiza
por un interprete diferente que opera localmente.
Es muy adecuada para ser
implementada en sistemas
distribuidos en los que cada computador gestiona una subred
local.

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

11

Notas:

11

Síncrona: La RdeP es ejecutada en pasos ("steps"). Se
disparan todas las transiciones concurrentemente disparables
para un marcado M y no se considera ningún otro disparo
hasta haber alcanzado el sucesor de M.
Asíncrona: Cuando el disparo de una
transición ha
concluido se actualiza el marcado lo que puede posibilitar
nuevos disparos sin espera alguna.

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

12

Notas:

12

Ejemplo implementación con coordinador centralizado

El disparo de una transición habilitada tiene tres fases:
1. Extraer los testigos de las plazas de entrada de la transición.
2. Ejecuta el código asociado a la transición.
3. Entregar los testigos en las plazas de salida de la transición.
Cada transición tiene asociada una prioridad. Si dos transiciones están
habilitadas para un determinado marcado, se dispara la transición de
mayor prioridad.
Se manejan dos listas:
treatment_list: Contiene las transiciones que deben ser chequeadas en la actual

activación.

list_in_formation: Contiene las transiciones que como consecuencia de la actual

activación deben ser chequeadas en la próxima activación.

Se utilizan dos tipos de thread:
Una thread de la máxima prioridad interpreta la red de Petri y determina las

transiciones que están activadas.

Un pool de threads ejecutan concurrentemente las tareas asociadas al disparo

de cada transición.

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

13

Notas:

13

Seudocódigo del coordinador centralizado

while(true){

//enabling analysis phase
while elements in treatment_list {

T = next_element(treatment_list);
if enabled (T) {
//start of transition firings
Start_fire (T) ;
Demark_input_places (T);
Update (list_in_formation) ; // only in SRP
Change_representing_place (T) ; // only in DRP

}else{

wait for end_fire (T) ;
Mark_output_places (T) and Update (list_in_formation) ;

}

}
//end of firings phase
while(not end_fire pending ){

}
// lists update
treatment_list =list_in_formation;
clear list_in_formation ;

}

Procodis’08: V.2- Implementación redes de Petri

José M.Drake

14

Notas:

14

Estrategias de selección de transiciones analizables

La eficiencia del algoritmo se basa en que en cada activación
se pueda establecer un conjunto reducido de actividades de las
que se deben analizar si están habilitadas o no.
Estrategias:
Todas las transiciones (BF Brute Force): Se analizan todas la
transiciones y se activan las que estan habilitadas por orden de
prioridad

Static Representing Places (SRP). Se seleccionan las transiciones que

son salida de las plazas con marcado, seleccionadas de entre un
conjunto reducido de plazas (Representing Places) fijadas
estáticamente.

Dynamic Representing Places (DRP). Igual que el caso anterior pero