redespetri 2009 intro

7/12/2019 RedesPetri 2009 Intro

http://slidepdf.com/reader/full/redespetri-2009-intro 1/32

1

Introducción a lasRedes de Petri

Juan de Lara con modificaciones deGonzalo Martínez Muñoz

Carlos Aguirre

Juan de Lara

Gonzalo Martínez Muñoz

Roberto Moriyón



Cliente

Camarero

libre

Pedir

Comanda

Cliente

espera

A cocina

En preparación

A cocina Fin prep.

Plato listo

Servir Cliente

come

Redes de Petri. Ejemplo restaurante.



3

Índice

Estructura del curso.

Modelado y Simulación.

Redes de Petri. Introducción

Bibliografía.



4

Estructura del curso

Introducción (1 sesión). GMM.

Redes de Petri Básicas (3 ó 4 sesiones). GMM.

Redes de Petri Temporales y Estocásticas (3 sesiones).

CA.

Redes de Petri Coloreadas (4 sesiones). RM.

Exposición de Trabajos (1 ó 2 sesiones). Vosotros.



5

Evaluación

Exposición de Trabajos/Proyecto.

Ejercicios.

Asistencia.



6

Índice




Bibliografía.



Modelado

Sistemas compuestos por componentes.

Su comportamiento puede ser descrito por separado.

Cada componente tiene un estado :

Cambia a lo largo del tiempo.

Contiene información relevante para describir sus

acciones futuras.



Modelado

Estudiar un fenómeno indirectamente a través de un

modelo.

Representación (matemática ) de características

importantes del sistema.

Manipulando el modelo se espera obtener nuevo

conocimiento sin el peligro , coste o molestias de

manipular el sistema real.



REALIDAD MODELO

Entidaddel Mundo Real

Sistema S

Datos Observados

del Experimento

Modelo Base

Modelo M

Resultados de la

Simulación

Estudiar comportamientoen contexto del experimento.

Experimento dentro decontexto.

validación

Simular= experimento virtual

en contexto

Proceso deModelado&Simulació

OBJETIVOS




Morfismo de comportamiento

Sistema Real

Resultadosdel Experimento

Experimento dentro decontexto.

Modelo Abstracto

Resultados de laSimulación

Experimento virtual

Modelado/Abstracción

Abstracción




Sistema Real

Modelo

Conceptual

Modelo

de Simulación

Causa Efecto

Validación del ModeloConceptual

Verificación

Entrada

Salid

a

Validación delComportamiento


Validación y Verificación.



Modelado. Base Temporal.

Todo formalismo de simulación debe tener una variable deindexación (normalmente es el tiempo) que permita la transición de

estados de los modelos.

TimeBase = T, <

Bases temporales comunes incluyen:

T = {NOW} (modelos algebraicos).

T = R (continuos, eventos discretos, etc.)

T = N (autómatas, Redes de Petri B&W, etc.)



Analógica. Modelo ~ circuitos electrónicos. Ordenador analógico. Vannevar Bush 30’s.

Digital Continua. Modelo ~ Ecuaciones diferenciales, diferenciales algebraicas, en derivadas parciales. Tiempo pseudo-continuo. Intervalo elemental de tiempo. El estado del sistema cambia de forma continua.

Digital Discreta Procesos estadísticos. Diversa forma dependiendo del formalismo. Base temporal continua, número finito de eventos en un intervalo. Valores nopredecibles. El estado del sistema cambia cuando se produce un evento.

Híbrida.

Modelado y Simulación. Tipos.



Las variables que representan el estado del sistema

cambian (instantáneamente) en instantes discretos detiempo (eventos).

El estado del sistema permanece inalterado entreeventos.

La base temporal es continua, pero durante un ciertointervalo de tiempo, sólo un número finito de eventosocurren.

Simulación Discreta.



Modelado: Productor-consumidorAutómata finito

prod1

wait2

ebuff

wait1

wait2

fbuff

wait1cons2

ebuff

p1

r 2

rp1

prod1

cons2

ebuff

wait1

wait2

ebuff

rc2 wait1cons2

fbuff

p1

rc2

Representación basada en estado(autómata finito).

Concurrencia: Entrelazado.

Representación explícita deindependencia secuencial de acciones:

rp1; r

2= rp

1; r

2

¿Buffer de capacidad 10, 100, 1000?

¿Varios productores y consumidores?

prod1 wait2

fbuff

rp1

r 2rp1

rc2



Modelado: Productor-consumidorStatechart

prod

wait

prod

[in Buffer.ebuff]

ebuff

fbuff

prod read rp

wait

cons

read

[in Buffer.fbuffer]

rc

Productor Buffer Consumidor

Representación basada en

estado (Statechart).



Modelado: Productor-consumidorProgramación de eventos: Grafo de eventos

Init

Ready to

Produce

{buffer=0}

[5, 10]

produce

buffer==0 {buffer=1}

[5, 10]

Ready to

consumeconsume

[5, 10]

buffer==1 {buffer=0}

[5, 10]

waiting

for

empty

buffer==1

[1, 1]

waiting

for

full

buffer==0

[1, 1]

Representación basada eneventos (event scheduling)



Modelado: Productor-consumidorInteracción de procesos: GPSS

5, 10

5, 10

1

CONSUMER

CONSUMER

CONSQ

CONSQ

* Producer consumer

GENERATE 5, 10 Create token

QUEUE CONSQ Queue for Consumer

SEIZE CONSUMER Get the consumer

DEPART CONSQ Leave queue

ADVANCE 5, 10 Consume

RELEASE CONSUMER Free Consumer

TERMINATE 1 Count tokens

START 1000 Run 1000 tokens

END



Modelado: Productor-consumidorÁlgebra de procesos

producer = p.rp.producer consumer = rc.r.consumer

buffer = p.r.buffer

(producer||consumer||buffer)\{p, r, p,r}

Representación basada enacciones (álgebra deprocesos. Milner)



Modelado: Productor-consumidorRedes de Petri

prod

wait

deliver Ready

Produce

cons

wait

Ready

consumeread

full

empty

Representación medianteRedes de Petri



Modelado: Productor-consumidor.

2 Consumidores.

prod

wait

deliver Ready

Produce

cons1

wait 1

Ready

consume1read 1

full

empty

cons2

wait 2

Ready

consume2read 2



22


Capacidad 100.

prod

wait

deliver Ready

Produce

cons1

wait 1

Ready

consume1read 1

100

full

empty

cons2

wait 2

Ready

consume2read 2



23


Con tiempo.

prod

wait

deliver Ready

Produce

cons

wait

Ready

consumeread

empty

full

=8=1 =1

Representación medianteRedes de Petri con tiempo.

=9



24

Modelado: Productor consumidor

con contador. Redes Coloreadas

prod

wait

deliver Ready

Produce

cons

wait

Ready

consumeread

full

empty

Representación medianteRedes de Petri coloreadas

(de Alto Nivel).

1’(0,“hola”)

1’(0)

(m,packet)

x

(x, packet)

X+1

(n+1,packet)

1’(0, “null”)

Declarations:

Type PCK = String.

Type CPCK = int x String

Var m, n, x : intVar packet: String

CPCK

CPCK

CPCK

int

(m+1, packet)

int

n

(n,packet)

n

CPCK

(m, packet)

(m, packet+str(m))



25

Índice




Bibliografía.



26

Redes de Petri. Definición Herramienta para la descripción y estudio de sistemas

discretos mediante grafos

Las redes de Petri pueden representar sistemas:

– Concurrentes

– Síncronos y asíncronos

– Distribuidos, paralelos y secuénciales

– No deterministas – Estocásticos

– Compartición de recursos

C.A. Petri a principios de los 60



Las redes de Petri son una herramienta demodelado:

– Gráfica:

– Matemática: Permite analizar las propiedades de unsistema asociado al modelo:

Grafos de alcanzabilidad y cubrimiento.

Técnicas lineales algebraicas.

Características Estructurales. Reducción.27

Redes de Petri. Definición

H2

O2

H2O

22



Cliente

Camarero

libre

Pedir

Comanda

Cliente

espera

A cocina

En preparación

A cocina Fin prep.

Plato listo

Servir Cliente

come

Redes de Petri. Restaurante

SincronizaciónProcesos paralelos Proceso secuencial

Se desincroniza

Sincronización

-Compartición de recursos-No determinismo



Redes de Petri con tiempo determinista oestocástico

– Permiten analizar

Rendimientos de sistemas: Llamadas medias a modulos

Scheduling

Modelar servidores: tiempos de respuestas

Redes de Petri coloreadas: Manejan tipos dedatos

– Diseño de grandes sistemas de software

29

Redes de Petri. Extensiones.



– Protocolos de comunicación

– Análisis de rendimientos de sistemas

– Diseño de software distribuido

– Sistemas de control industrial

– Sistemas multiprocesador

– Modelos de decisión – Circuitos

– etc.

30

Redes de Petri. Aplicaciones.



31

Índice




Bibliografía.



32

Bibliografía Peterson, J.L. 1981. “Petri Net Theory and the Modeling of Systems” .

Prentice-Hall, INC., Englewood Cliffs, N.J. (General).

Murata, T. 1989. “Petri Nets: Properties, Analysis and Applications” .

Proceedings of the IEE, Vol. 77(4). Pp.: 541-580. (General)

Jensen, K. “Coloured Petri nets basic concepts, analysis methods and

practical use” . Monographs in Theoretical Computer Science, Springer-

Verlag, 1997. (Redes de Petri Coloreadas).

Petri Nets world: http://www.daimi.au.dk/PetriNets/

Reisig, W., Rozenberg, G., Desel, J., Jensen, K., Silva, M., Balbo, G.

“Introductory Tutorial at PetriNets’2000”

http://www.daimi.au.dk/PetriNets/










redespetri 2009 intro

Documents