Metodos de Especificação de Software 1ª Parte

Metodos de Especificação de Metodos de Especificação de SoftwareSoftware1ª Parte1ª Parte

Patrícia MacedoPatrícia MacedoJoaquim FilipeJoaquim FilipeJoão AscensoJoão Ascenso

Engenharia de Software 2004/2005Engenharia de Software 2004/2005EST, SetúbalEST, Setúbal

Engenharia de Software 2

Indice GeralIndice Geral1ª Parte1ª Parte Especificação de Software Especificação de Software DFD’sDFD’s Maquinas de estadosMaquinas de estados Petri NetsPetri Nets

2ª Parte2ª Parte UMLUML

3ª Parte3ª Parte ExemplosExemplos


MotivaçãoMotivação Ao longo de várias disciplinas do curso temos Ao longo de várias disciplinas do curso temos

utilizado várias formas de especificar o utilizado várias formas de especificar o software.software. Fluxogramas (IP, ATAI, POO Microprocessadores)Fluxogramas (IP, ATAI, POO Microprocessadores) DFD’s - ASIDFD’s - ASI Maquinas Finitas - MicroprocessadoresMaquinas Finitas - Microprocessadores Redes PetriRedes Petri UML – POOUML – POO

O objectivo desta aula é fazer uma breve revisão O objectivo desta aula é fazer uma breve revisão de algumas destas diferentes tecnicas de de algumas destas diferentes tecnicas de especificar o software.especificar o software.


EspecificaçãoEspecificação

No dicionário:No dicionário: Especifica: que pertence a uma espécie particularEspecifica: que pertence a uma espécie particular

No contexto da engenharia:No contexto da engenharia: Descrição dos detalhes estruturais e Descrição dos detalhes estruturais e

comportamentais de um produto a desenvolvercomportamentais de um produto a desenvolver No contexto da ES:No contexto da ES:

Descrição precisa das entidades de um sistema, Descrição precisa das entidades de um sistema, do conjunto de métodos para as manipular e do do conjunto de métodos para as manipular e do seu comportamento.seu comportamento.


EspecificaçãoEspecificação

Vários significados possíveis, em ES:Vários significados possíveis, em ES: Especificação de requisitosEspecificação de requisitos

Acordo entre o utilizador e o responsável pelo Acordo entre o utilizador e o responsável pelo sistema de SW completosistema de SW completo

Especificação de desenhoEspecificação de desenho Acordo entre o arquitecto do sistema e os Acordo entre o arquitecto do sistema e os

programadoresprogramadores Especificação de módulosEspecificação de módulos

Acordo entre os programadores que utilizam o Acordo entre os programadores que utilizam o módulo e os programadores que o implementammódulo e os programadores que o implementam


Para que servem as Para que servem as especificaçõesespecificações

Indicar as necessidades do utilizadorIndicar as necessidades do utilizador Importante para o programador saber quais Importante para o programador saber quais

são as necessidades do utilizadorsão as necessidades do utilizador O utilizador não sabe bem o que querO utilizador não sabe bem o que quer

Tentar obter uma especificação clara e precisaTentar obter uma especificação clara e precisa Evitar ambiguidades e diferentes Evitar ambiguidades e diferentes

interpretações entre o utilizador e o interpretações entre o utilizador e o programador programador

VERIFICARVERIFICAR as especificações as especificações As especificações podem ser construídas As especificações podem ser construídas

de uma forma muito clara e precisade uma forma muito clara e precisa e.g. métodos formaise.g. métodos formais


Para que servem as Para que servem as especificaçõesespecificações

Indicação dos requisitos para a Indicação dos requisitos para a implementaçãoimplementação Ponto de referência durante a implementaçãoPonto de referência durante a implementação Especificação define o comportamento:Especificação define o comportamento:

Interno – Interno – Especificação de desenhoEspecificação de desenho Externo – Externo – Especificação de requisitosEspecificação de requisitos

A especificação de desenho deve ser escrita de A especificação de desenho deve ser escrita de forma mais formal e precisa que as de requisitosforma mais formal e precisa que as de requisitos

Especificação de desenho Especificação de desenho programadores programadores Especificação de requisitos Especificação de requisitos utilizadores utilizadores


Qualidades das Qualidades das EspecificaçõesEspecificações

Três características fundamentais a ter em Três características fundamentais a ter em conta na especificaçaõ do software:conta na especificaçaõ do software: Clareza: Clareza:

Sem ambiguidades e compreensíveisSem ambiguidades e compreensíveis Consistência: Consistência:

Sem regras contraditóriasSem regras contraditórias Ser completaSer completa

Internamente: toda a terminologia interna estar definidaInternamente: toda a terminologia interna estar definida Relativamente aos requisitos: documentar todos os Relativamente aos requisitos: documentar todos os

requisitosrequisitos


Estilos de EspecificaçãoEstilos de Especificação Critério 1: especificações formais vs. Critério 1: especificações formais vs.

especificações informaisespecificações informais Formais: A notação utilizada possui uma sintaxe e uma Formais: A notação utilizada possui uma sintaxe e uma

semântica totalmente precisasemântica totalmente precisa Informal: Escritas em linguagem naturalInformal: Escritas em linguagem natural As linguagens TDN e GDN são semi-formais. Porquê?As linguagens TDN e GDN são semi-formais. Porquê?

Critério 2: Especificações operacionais vs. Critério 2: Especificações operacionais vs. especificações descritivasespecificações descritivas A especificação operacional define comportamentos A especificação operacional define comportamentos

desejados através de um modelo do sistemadesejados através de um modelo do sistema A especificação descritiva define propriedades desejáveis, A especificação descritiva define propriedades desejáveis,

de forma puramente declarativade forma puramente declarativa Exemplo: a especificação de uma elipse – através do Exemplo: a especificação de uma elipse – através do

desenho da sua forma ou através da sua fórmula: axdesenho da sua forma ou através da sua fórmula: ax22 + + byby22 + c = 0 + c = 0


Especificações InformaisEspecificações Informais

Escritas em linguagem naturalEscritas em linguagem natural Fáceis de serem entendidas pelo clienteFáceis de serem entendidas pelo cliente Mais susceptíveis de possuírem:Mais susceptíveis de possuírem:

Erros, omissões, imprecisões ou ambiguidadesErros, omissões, imprecisões ou ambiguidades As falhas são descobertas mais tarde, na As falhas são descobertas mais tarde, na

integração, no teste do sistema ou mesmo na integração, no teste do sistema ou mesmo na entrega do produtoentrega do produto

Conclusão: Não é uma boa forma de especificar Conclusão: Não é uma boa forma de especificar um sistema complexoum sistema complexo

Facto: ainda é utilizado por muitas empresas.Facto: ainda é utilizado por muitas empresas. Principais razões: gestão não uniformizada, pessoal não Principais razões: gestão não uniformizada, pessoal não

qualificado, pressões do cliente, falta de investimentoqualificado, pressões do cliente, falta de investimento No entanto, o panorama está a mudar.No entanto, o panorama está a mudar.


Especificações FormaisEspecificações Formais

Comunicação fácil entre os arquitectos do Comunicação fácil entre os arquitectos do sistema de SW, programadores e sistema de SW, programadores e responsáveis pela escrita dos requisitosresponsáveis pela escrita dos requisitos

Representações formais:Representações formais: Análise automáticaAnálise automática

O desempenho é baixo ? Existem deadlocks ?O desempenho é baixo ? Existem deadlocks ? Medidas objectivasMedidas objectivas

e.g. de acoplamento e/ou de coesão entre módulose.g. de acoplamento e/ou de coesão entre módulos Verificação de algumas propriedades do SWVerificação de algumas propriedades do SW Podem ser utilizadas para testar o sistema de SW:Podem ser utilizadas para testar o sistema de SW:

E.g. através de E.g. através de test scriptstest scripts


Formalidade vs Formalidade vs InformalidadeInformalidade

Método informalMétodo informal Linguagem naturalLinguagem natural

Métodos semi-formaisMétodos semi-formais Gane & Sarsen/DeMarco/YourdonGane & Sarsen/DeMarco/Yourdon Entity-Relationship DiagramsEntity-Relationship Diagrams Jackson/Orr/Warnier, Jackson/Orr/Warnier, SADT, PSL/PSA, SREM, etc.SADT, PSL/PSA, SREM, etc.

Métodos formaisMétodos formais Finite State MachinesFinite State Machines Petri NetsPetri Nets ZZ ANNA, VDM, CSP, etc.ANNA, VDM, CSP, etc.


Formalidade vs Formalidade vs InformalidadeInformalidade

Notações semi-formaisNotações semi-formais Possuem uma fraca semântica associada com Possuem uma fraca semântica associada com

a estrutruraa estrutrura Muito utilizadas, fácil compreensãoMuito utilizadas, fácil compreensão

Notações formaisNotações formais A semântica é claramente definida (conceito A semântica é claramente definida (conceito

matemático)matemático) As especificações não são ambíguas As especificações não são ambíguas

Menos atrito entre o cliente e o produtor de SWMenos atrito entre o cliente e o produtor de SW Implementação mais fácilImplementação mais fácil

Díficil compreensãoDíficil compreensão


Especificação Formal: Especificação Formal: ExemploExemplo

A system consists of a set of object files. Each object file is derived from one or more source files. Object and source files have a timestamp indicating when they were last modified. If an object file is older than any source file, then the object file must be rederived.


Especificação Formal: Primeiro Especificação Formal: Primeiro PassoPasso

A system consists of a set of object files. Each object file is derived from one or more source files. Object and source files have a timestamp indicating when they were last modified. If an object file is older than any source file, then the object file must be rederived.


Especificação FormalEspecificação Formal

O = {o1, o2, o3, …} S = {s1, s2, s3, …} F = O U S T: F → R D: O → PowerSet(S) ForAll(o ε O), ForAll(s ε D(o)) T(o) > T(s)

O = conjunto dos ficheiros obj

S = conjunto dos ficheiros fonte

F = Todos os ficheiros T = relação do timestamp D = relação deriva Um exemplo: os

timestamp de O devem ser maiores que os

timestamps de s


Especificações OperacionaisEspecificações Operacionais

Notações para indicação de especificações em Notações para indicação de especificações em estilo operacional: estilo operacional: Diagramas de Fluxo de Dados - Diagramas de Fluxo de Dados - Data Flow DiagramsData Flow Diagrams

Especificação de colecções de dados que são manipulados Especificação de colecções de dados que são manipulados por funções, em termos de repositórios e fluxos de dadospor funções, em termos de repositórios e fluxos de dados

Máquinas de Estados Finitas - Máquinas de Estados Finitas - Finite State MachinesFinite State Machines Especificação de estruturas de controloEspecificação de estruturas de controlo

Redes de Petri – Redes de Petri – Petri NetsPetri Nets Especificação de sistemas assíncronos, em termos de Especificação de sistemas assíncronos, em termos de

lugares e transições entre lugareslugares e transições entre lugares

Data Flow Diagrams Data Flow Diagrams (DFDs)(DFDs)


DFDsDFDs

Servem para especificar as funções de um Servem para especificar as funções de um sistema de informaçãosistema de informação

O sistema é descrito como uma colecção de O sistema é descrito como uma colecção de dados manipulados por funçõesdados manipulados por funções

Os dados podem ser organizados de várias Os dados podem ser organizados de várias formas:formas: Repositórios de dadosRepositórios de dados Transferências de dadosTransferências de dados Entradas/saídasEntradas/saídas


DFDsDFDs

Notação gráfica:Notação gráfica: Nós (“bubble”): representam funções.Nós (“bubble”): representam funções. Setas: representam fluxos de dadosSetas: representam fluxos de dados Caixas abertas: representam repositórios de dados.Caixas abertas: representam repositórios de dados. Caixas de E/S: Representam a aquisição e produção Caixas de E/S: Representam a aquisição e produção

de dados durante a interacção humano-máquina.de dados durante a interacção humano-máquina.

Função Dispositivo de entrada

Dispositivode saída

Fluxo de Dados

Repositório De Dados


ExemploExemplo

(a + b) * (c + a * d)(a + b) * (c + a * d)

ou,ou,em notação prefixa:em notação prefixa:(* (+ a b) (+ c (* a d)))(* (+ a b) (+ c (* a d)))

ab d c

+ * +

*


Outro Exemplo: BibliotecaOutro Exemplo: Biblioteca

PrateleiraPrateleira

Lista de Lista de AutoresAutores

Lista de Lista de TitulosTitulos

Lista de Lista de TópicosTópicos

Obter um livro

Procurar por

Tópico

Pedido de Pedido de Livro pelo Livro pelo utilizadorutilizador

Recepção do Livro

Lista de livros Lista de livros emprestadosemprestados

Lista de TítulosTópico Tópico

pedido pelo pedido pelo utilizador.utilizador.

Livro

Autor

Título

Título

TópicoTópico Lista de Títulos

Referentes aoTópico

Titulo; utilizador

Livro

Título e Autor do livro pedido;Nome do utilizador


Problemas com os DFDsProblemas com os DFDs

Os DFDs possuem uma notação gráfica atractiva Os DFDs possuem uma notação gráfica atractiva capaz de capturar de forma intuitiva o fluxo de capaz de capturar de forma intuitiva o fluxo de dados e as operações envolvidas num sistema de dados e as operações envolvidas num sistema de informação:informação: No entanto falta-lhes uma semântica precisaNo entanto falta-lhes uma semântica precisa Requerem uma interpretação intuitivaRequerem uma interpretação intuitiva Notação semi-formalNotação semi-formal

O controlo não é definido por este modelo:O controlo não é definido por este modelo: Um nó ("bubble") utiliza todas as suas entradas ? Um nó ("bubble") utiliza todas as suas entradas ? Espera por todas ou por um determinado número ? Espera por todas ou por um determinado número ? Repete os cálculos quando as entradas são constantes ?Repete os cálculos quando as entradas são constantes ?


Ultrapassar os problemasUltrapassar os problemas

Utilizar uma notação complementar para Utilizar uma notação complementar para descrever os aspectos não abrangidos pelas DFDsdescrever os aspectos não abrangidos pelas DFDs Especificação completa = DFDs + descrições auxiliaresEspecificação completa = DFDs + descrições auxiliares

Aumentar o modelo DFDAumentar o modelo DFD, por forma a abranger , por forma a abranger mais funcionalidades. mais funcionalidades. e.g. Introdução de setas de controlo de fluxoe.g. Introdução de setas de controlo de fluxo

Rever a notação DFDRever a notação DFD tradicionaltradicional para a tornar para a tornar completamente formalcompletamente formal Revela-se muito complicado !!!Revela-se muito complicado !!!

Máquinas de estado finitasMáquinas de estado finitas


Switch on

Switch off

Current StateAction Off On

Switch on

Switch off

On On

Off Off

Off OnSwitch on

Switch off

Switch off Switch on

Máquinas de Estado FinitasMáquinas de Estado FinitasAs MEF assumem que o sistema está sempre em As MEF assumem que o sistema está sempre em

um dos estados permitidosum dos estados permitidos


Máquinas de Estados FinitasMáquinas de Estados Finitas

Trata-se de um modelo bem conhecido para Trata-se de um modelo bem conhecido para representar controlo. representar controlo.

Uma MEF é adequada para representar:Uma MEF é adequada para representar: Sistemas com num número finito de estados, e Sistemas com num número finito de estados, e Transições entre estados como consequência de um eventoTransições entre estados como consequência de um evento

Anos de experiência com as MEF !!!Anos de experiência com as MEF !!! Exemplos:Exemplos:

RelógiosRelógios CalculadorasCalculadoras Máquinas ATMMáquinas ATM

Por vezes o manual de utilização têm diagramas de Por vezes o manual de utilização têm diagramas de MEFMEF


Máquinas de Estado FinitasMáquinas de Estado Finitas

EstadosEstados Distinção entre estado iniciais e/ou Distinção entre estado iniciais e/ou

finaisfinais Transição entre estados é accionada Transição entre estados é accionada

por eventos:por eventos: Tais como pressionar o botão de uma Tais como pressionar o botão de uma

calculadora calculadora Ou de um relógio Ou de um relógio Ou uma item de um menu numa GUIOu uma item de um menu numa GUI



Definição formal:Definição formal: M = {Q,I,M = {Q,I,}, onde}, onde

Q é um conjunto finito de estadosQ é um conjunto finito de estados I é um conjunto finito de entradasI é um conjunto finito de entradas é uma função de transição : Q x I -> Qé uma função de transição : Q x I -> Q

A função A função pode ser uma função parcial pode ser uma função parcial (i.e. indefinida para certos valores do (i.e. indefinida para certos valores do seu domínio)seu domínio)



Representação gráficaRepresentação gráfica Os nós (círculos) representam estadosOs nós (círculos) representam estados Os arcos são dirigidos e possuem uma Os arcos são dirigidos e possuem uma

etiqueta (etiqueta (labellabel) que pertence ao ) que pertence ao conjunto Iconjunto I

Um arco com uma etiqueta i vai do Um arco com uma etiqueta i vai do estado q1 para q2 se e só se estado q1 para q2 se e só se (q1,i) = (q1,i) = q2q2


Exemplo IExemplo I

q0

q1

q3

q2

a a

bc

b


Exemplo IIExemplo II



Modelo de execuçãoModelo de execução A MEF está sempre em algum estadoA MEF está sempre em algum estado A entrada obriga a mudanças de estado A entrada obriga a mudanças de estado

de acordo com de acordo com Extensões comuns:Extensões comuns:

Estados iniciais e estados de paragemEstados iniciais e estados de paragem A saída é gerada quando existe uma A saída é gerada quando existe uma

transição entre estadostransição entre estados : Q x I -> Q x O: Q x I -> Q x O


Exemplo IIIExemplo III


Geração de LinguagensGeração de Linguagens

Seja E = {a,b} um conjunto de eventos. Seja E = {a,b} um conjunto de eventos. Considere a linguagem:Considere a linguagem: L = {a,aa,ba,aaa,aba,baa,bba,...}L = {a,aa,ba,aaa,aba,baa,bba,...} i.e. Todas as strings de a e b seguidas de a.i.e. Todas as strings de a e b seguidas de a.

0 1b

a

ab


MEF equivalentesMEF equivalentes

0 1b

a

ab

0 1b

a

a

0 1b

a2a

a

0 1b

ana … a n+1a a

b

b

b


Blocking and LivelockBlocking and Livelock

Estado 5 é uma deadlockEstado 5 é uma deadlock Estados 3 e 4 uma livelockEstados 3 e 4 uma livelock


Vantagens do modelo MEFVantagens do modelo MEF

Simples de entender e mais precisa que Simples de entender e mais precisa que outras abordagens semi-formais:outras abordagens semi-formais: Um menu de um GUI é uma MEFUm menu de um GUI é uma MEF

Representação gráfica evidente e claraRepresentação gráfica evidente e clara É fácil construir ferramentas de suporteÉ fácil construir ferramentas de suporte

Transformadores:Transformadores: Transformam o modelo MEF em outras Transformam o modelo MEF em outras

representações, e.g. código C++representações, e.g. código C++ Análise e Validação:Análise e Validação:

Esta MEF irá correr para sempre ? Quando é que irá Esta MEF irá correr para sempre ? Quando é que irá parar ? Deadlock ? parar ? Deadlock ?


Limitações das MEFLimitações das MEF Limite teórico no poder computacionalLimite teórico no poder computacional

A MEF não possui memóriaA MEF não possui memória A utilização de estados como memória é A utilização de estados como memória é

ineficiente:ineficiente: Considere modelar um sistema de navegação com Considere modelar um sistema de navegação com

estados que modelam a velocidade:estados que modelam a velocidade: Registo de 8 bits = 256 estadosRegisto de 8 bits = 256 estados

Explosão de estados na combinação de Explosão de estados na combinação de vários módulos:vários módulos: Os estados são multiplicativosOs estados são multiplicativos

Inerentemente síncrona: Inerentemente síncrona: Em cada instante, o estado global do sistema Em cada instante, o estado global do sistema

tem de estar definido e apenas pode ocorrer tem de estar definido e apenas pode ocorrer uma transição de cada vezuma transição de cada vez

Redes de PetriRedes de Petri


IntroduçãoIntrodução

• Introduzidas por Carl Adam Petri em Introduzidas por Carl Adam Petri em 19621962

• Ferramenta de diagramas para Ferramenta de diagramas para modelar concorrência e sincronização modelar concorrência e sincronização em sistemas distribuídosem sistemas distribuídos

• Baseada numa fundação matemática Baseada numa fundação matemática muito fortemuito forte


Uma especificação de Redes PetriUma especificação de Redes Petri

Consiste em três tipos de componentes: Consiste em três tipos de componentes: lugares (círculos), transições lugares (círculos), transições (rectângulos ou barras) e arcos (setas):(rectângulos ou barras) e arcos (setas): Os lugares representam os estados Os lugares representam os estados

possíveis do sistemapossíveis do sistema As transições são eventos ou acções que As transições são eventos ou acções que

causam a mudança de estadocausam a mudança de estado Cada arco liga um lugar com uma transição Cada arco liga um lugar com uma transição

ou uma transição com um lugarou uma transição com um lugar


Exemplo de Rede de PetriExemplo de Rede de Petri


Exemplo: Sistema de SegurançaExemplo: Sistema de Segurança

Initial

1 digit 1 digit 1 digit 1 digit

d1 d2 d3

d4

OK

OKpressed

approve

approved

OK OK OKOK

RejectRejected!


Mudança de estadoMudança de estado Ocorre quando existe um movimento Ocorre quando existe um movimento

de de token(s)token(s) (pontos pretos) de lugar (pontos pretos) de lugar em lugar e é causado pelo disparo de em lugar e é causado pelo disparo de uma transiçãouma transição

O disparo representa a ocorrência de O disparo representa a ocorrência de um evento ou uma acção tomadaum evento ou uma acção tomada

O disparo é sujeito às condições de O disparo é sujeito às condições de entrada, i.e. pela disponibilidade de entrada, i.e. pela disponibilidade de tokens(s)tokens(s)


Mudança de estadoMudança de estado

Uma transição está activa quando existem Uma transição está activa quando existem tokens suficientes nas suas entradastokens suficientes nas suas entradas

Depois do disparo, os tokens irão ser Depois do disparo, os tokens irão ser transferidos dos lugares de entrada (estado transferidos dos lugares de entrada (estado anterior) para os lugares de saída (novo anterior) para os lugares de saída (novo estado)estado)

Quando uma transição está activa a rede Quando uma transição está activa a rede pode evoluir de formas diferentes: pode evoluir de formas diferentes: O modelo é não determinístico O modelo é não determinístico

Mesmo estado inicial – vários estados finais possíveisMesmo estado inicial – vários estados finais possíveis Salienta-se que o exemplo anterior é uma rede Salienta-se que o exemplo anterior é uma rede

de Petri de uma MEFde Petri de uma MEF



• Cenário 1: Normal Cenário 1: Normal • Introduz os 4 dígitos e pressiona em OK.Introduz os 4 dígitos e pressiona em OK.

• Cenário 2: ExcepcionalCenário 2: Excepcional• Introduz apenas 3 dígitos e pressiona Introduz apenas 3 dígitos e pressiona

em OK.em OK.



Initial

1 digit 1 digit 1 digit 1 digit

d1 d2 d3

d4

OK

OKpressed

approve

approved

OK OK OKOK

RejectRejected!


Múltiplos estados locaisMúltiplos estados locais

No mundo real, existem eventos que No mundo real, existem eventos que acontecem ao mesmo tempoacontecem ao mesmo tempo

Um sistema pode ter muitos estados Um sistema pode ter muitos estados locais para obter um estado globallocais para obter um estado global

Existe uma necessidade de modelar Existe uma necessidade de modelar concorrência e sincronizaçãoconcorrência e sincronização


Estruturas da redeEstruturas da rede

Uma sequência de eventos/acções:Uma sequência de eventos/acções:

Execuções concorrentes:Execuções concorrentes:

e1 e2 e3

e1

e2 e3

e4 e5


Estruturas de redeEstruturas de rede

Eventos não determínisticos - conflito, Eventos não determínisticos - conflito, escolha ou decisão : A escolha de e1, e2 … escolha ou decisão : A escolha de e1, e2 … ou e3, e4 ... ou e3, e4 ...

e1 e2

e3 e4


Estrutura da redeEstrutura da rede

SincronizaçãoSincronização

e1


Estruturas de RedeEstruturas de Rede

Sincronização e ConcorrênciaSincronização e Concorrência

e1


Exemplo: Obtenção de um recursoExemplo: Obtenção de um recurso

Estado Inicial

T1 dispara

T2 dispara

Modelo não deterministicoTanto t3 como

t4 podem disparar

Modelo concorrente.

O disparo de t1 não impede t2

de disparar


Exemplo: Obtenção de um recursoExemplo: Obtenção de um recurso

Estado Inicial

T1 e T2 dispara

T3 dispara

T5 dispara

Não está definida uma política de resolução de conflitos

Pode ocorrer starvation

Formalizando...Formalizando...


Definição de Rede de Petri

Def.: Uma Rede de Petri (grafo ou estrutura) é um grafo pesado bipartido (P,T,A,w), onde:

P={p1, p2,... pn} é o conjunto finito de lugares (places)T ={t1, t2,... tm} é o conjunto finito de transições (transitions)

é o conjunto de arcos de lugares para transições (pi,tj) e transições para lugares (tj,pi)

é a função de pesos associados aos arcos

)()( PTTPA

,3,2,1: Aw

Conjunto de lugares de entrada de Tt j

}),(:{)( AtpPptI jiij

}),(:{)( AptPptO ijij

Conjunto de lugares de saída de Tt j


Exemplo de Rede de Petri

p1

p2

p3

p4

t1

t2

t3

1 são pesos os Todos

)},(),,(),,(),,(),,(),,(),,(),,(),,{(

},,

},,,

433312312133322211

321

4321

ptptptptpttptptptpA

tttT

ppppP


Marcações, Dinâmica e Espaço de Estados

Def.: Uma Rede de Petri marcada é um 5-túpulo (P,T,A,w,x), em que (P,T,A,w) é um grafo de Rede de Petri e x é uma marcação do conjunto de lugares P;

é o vector linha associado a x.

nnpxpxpx N)](,),(),([ 21 x

Def. (Dinâmica de RdP): A função de transição de estado, da rede de Petri (P,T,A,w,x), está definida

para a transição sse

nn Tf NN: Tt j

).(),,()( jijii tIptpwpx

Se f(x,tj) estiver definida, o novo estado é dado por x’ = f(x,tj), onde.,,1 ),,(),()()(' niptwtpwpxpx ijjiii

tj Permitida

(Enabled)

tj Permitida

(Enabled)


p1

p2

p3

p4

t1

t2

t3

00010 xx



p1

p2

p3

p4

t1

t2

t3

0110x



p1

p2

p3

p4

t1

t2

t3

0101x



p1

p2

p3

p4

t1

t2

t3

0210x



p1

p2

p3

p4

t1

t2

t3

1200x



Caracteristicas das Petri Caracteristicas das Petri NetsNets

Petri Nets servem para modelar o comportamento Petri Nets servem para modelar o comportamento de um sistema durante o desenvolvimento do SWde um sistema durante o desenvolvimento do SW

Petri Nets modelam MEFPetri Nets modelam MEF Modelam um estado global e muitos estado locais Modelam um estado global e muitos estado locais

no mundo realno mundo real Uma rede de Petri permite múltiplos cenáriosUma rede de Petri permite múltiplos cenários Diferentes Diferentes tokenstokens para diferentes cenários para diferentes cenários Redes de Petri : Sequência, Escolha, Redes de Petri : Sequência, Escolha,

Sincronização e ConcorrênciaSincronização e Concorrência Mais expressivas que as MEFMais expressivas que as MEF


ComportamentoComportamento

• Estados alcançáveis Estados alcançáveis • “ “Pode-se alcançar um estado particular a Pode-se alcançar um estado particular a

partir de outro?”partir de outro?”• Limite de armazenamentoLimite de armazenamento

• ““Irá haver Irá haver overflows overflows num círculo ?”num círculo ?”• Deadlocks ?Deadlocks ?

• ““Irá o sistema morrer num estado Irá o sistema morrer num estado particular ?”particular ?”


LimiteLimite

• Diz-se que uma rede de Petri possui um Diz-se que uma rede de Petri possui um limite em limite em kk ou é simplesmente limitada ou é simplesmente limitada se o número de se o número de tokenstokens em cada lugar em cada lugar não excede um número finito k para não excede um número finito k para qualquer estado a partir de M0qualquer estado a partir de M0

• A rede de Petri para a máquina de A rede de Petri para a máquina de vendas possui um limite em 1vendas possui um limite em 1• A rede de Petri net diz-se segura (safe)A rede de Petri net diz-se segura (safe)


BloqueioBloqueio

Uma rede de Petri pode entrar num estado Uma rede de Petri pode entrar num estado de bloqueio (de bloqueio (deadlockdeadlock) quando não é ) quando não é possível disparar nenhuma transiçãopossível disparar nenhuma transição

Uma rede de Petri em que não é possível Uma rede de Petri em que não é possível haver bloqueios diz-se “viva”haver bloqueios diz-se “viva”

É possível analisar a existência de estados É possível analisar a existência de estados de bloqueio no sistema através da análise de bloqueio no sistema através da análise manual da rede de Petri que modela o manual da rede de Petri que modela o sistemasistema


Deadlocks ?Deadlocks ?

• A máquina de vendas e o sistema produtor-A máquina de vendas e o sistema produtor-consumidor não possuem deadlocksconsumidor não possuem deadlocks

• Uma transição está Uma transição está mortamorta se não pode ser se não pode ser disparada por qualquer sequência de disparodisparada por qualquer sequência de disparo

• Outra definição: “Uma rede de Petri com um Outra definição: “Uma rede de Petri com um marcas iniciais M0 não possui deadlocks se, marcas iniciais M0 não possui deadlocks se, para qualquer situação alcançada a partir de para qualquer situação alcançada a partir de M0, é possível disparar uma transição M0, é possível disparar uma transição através de uma sequência de disparo”através de uma sequência de disparo”


BloqueioBloqueio


Um exemploUm exemplo

A bounded but non-live Petri net

p1 p2

p3

p4

t1

t2

t3 t4

M0 = (1,0,0,1)

M1 = (0,1,0,1)

M2 = (0,0,1,0)

M3 = (0,0,0,1)


Outro exemploOutro exemplop1

t1

p2 p3

t2 t3

p4 p5

t4 An unbounded but live Petri net

M0 = (1, 0, 0, 0, 0)

M1 = (0, 1, 1, 0, 0)

M2 = (0, 0, 0, 1, 1)

M3 = (1, 1, 0, 0, 0)

M4 = (0, 2, 1, 0, 0)


Métodos de AnáliseMétodos de Análise

• Análise de alcançabilidade:Análise de alcançabilidade:• Árvore de coberturaÁrvore de cobertura• Problema na explosão de estadosProblema na explosão de estados

• Matriz de Incidência e Equações de Matriz de Incidência e Equações de estadoestado

• Análise estruturalAnálise estrutural• Baseado em estruturas de redeBaseado em estruturas de rede


Limitações das Redes de Limitações das Redes de PetriPetri

Marcas anónimas => não é possível Marcas anónimas => não é possível a tomada de decisões (de selecção) a tomada de decisões (de selecção) com base no conteúdo nem a com base no conteúdo nem a modificação do conteúdo modificação do conteúdo

Não existe o conceito de “tempo” de Não existe o conceito de “tempo” de uma forma explicita:uma forma explicita: Limita a sua utilização em sistemas de Limita a sua utilização em sistemas de

tempo real tempo real

Documents

Metodos de Especificação de Software 1ª Parte