Metodos de Especificação de
Software
1ª Parte
Patrícia Macedo
Joaquim Filipe
João Ascenso
Engenharia de Software 2004/2005
EST, Setúbal
Indice Geral
1ª Parte
 Especificação de Software
 DFD’s
 Maquinas de estados
 Petri Nets
2ª Parte

UML
3ª Parte
 Exemplos
Engenharia de Software
2
Motivação

Ao longo de várias disciplinas do curso temos
utilizado várias formas de especificar o software.





Fluxogramas (IP, ATAI, POO Microprocessadores)
DFD’s - ASI
Maquinas Finitas - Microprocessadores
Redes Petri
UML – POO
O objectivo desta aula é fazer uma breve revisão de
algumas destas diferentes tecnicas de especificar o
software.
Engenharia de Software
3
Especificação

No dicionário:


No contexto da engenharia:


Especifica: que pertence a uma espécie particular
Descrição dos detalhes estruturais e comportamentais
de um produto a desenvolver
No contexto da ES:

Descrição precisa das entidades de um sistema, do
conjunto de métodos para as manipular e do seu
comportamento.
Engenharia de Software
4
Especificação

Vários significados possíveis, em ES:

Especificação de requisitos


Especificação de desenho


Acordo entre o utilizador e o responsável pelo sistema de SW
completo
Acordo entre o arquitecto do sistema e os programadores
Especificação de módulos

Acordo entre os programadores que utilizam o módulo e os
programadores que o implementam
Engenharia de Software
5
Para que servem as especificações

Indicar as necessidades do utilizador


Importante para o programador saber quais são as
necessidades do utilizador
O utilizador não sabe bem o que quer


Evitar ambiguidades e diferentes interpretações entre
o utilizador e o programador


Tentar obter uma especificação clara e precisa
VERIFICAR as especificações
As especificações podem ser construídas de uma
forma muito clara e precisa

e.g. métodos formais
Engenharia de Software
6
Para que servem as especificações

Indicação dos requisitos para a implementação


Ponto de referência durante a implementação
Especificação define o comportamento:



Interno – Especificação de desenho
Externo – Especificação de requisitos
A especificação de desenho deve ser escrita de forma
mais formal e precisa que as de requisitos


Especificação de desenho  programadores
Especificação de requisitos  utilizadores
Engenharia de Software
7
Qualidades das Especificações

Três características fundamentais a ter em conta na
especificaçaõ do software:

Clareza:


Consistência:


Sem ambiguidades e compreensíveis
Sem regras contraditórias
Ser completa


Internamente: toda a terminologia interna estar definida
Relativamente aos requisitos: documentar todos os requisitos
Engenharia de Software
8
Estilos de Especificação

Critério 1: especificações formais vs. especificações
informais




Formais: A notação utilizada possui uma sintaxe e uma
semântica totalmente precisa
Informal: Escritas em linguagem natural
As linguagens TDN e GDN são semi-formais. Porquê?
Critério 2: Especificações operacionais vs. especificações
descritivas



A especificação operacional define comportamentos desejados
através de um modelo do sistema
A especificação descritiva define propriedades desejáveis, de
forma puramente declarativa
Exemplo: a especificação de uma elipse – através do desenho da
sua forma ou através da sua fórmula: ax2 + by2 + c = 0
Engenharia de Software
9
Especificações Informais



Escritas em linguagem natural
Fáceis de serem entendidas pelo cliente
Mais susceptíveis de possuírem:




Erros, omissões, imprecisões ou ambiguidades
As falhas são descobertas mais tarde, na integração,
no teste do sistema ou mesmo na entrega do produto
Conclusão: Não é uma boa forma de especificar um
sistema complexo
Facto: ainda é utilizado por muitas empresas.


Principais razões: gestão não uniformizada, pessoal não
qualificado, pressões do cliente, falta de investimento
No entanto, o panorama está a mudar.
Engenharia de Software
10
Especificações Formais


Comunicação fácil entre os arquitectos do sistema
de SW, programadores e responsáveis pela escrita
dos requisitos
Representações formais:

Análise automática


Medidas objectivas



O desempenho é baixo ? Existem deadlocks ?
e.g. de acoplamento e/ou de coesão entre módulos
Verificação de algumas propriedades do SW
Podem ser utilizadas para testar o sistema de SW:

E.g. através de test scripts
Engenharia de Software
11
Formalidade vs Informalidade

Método informal


Métodos semi-formais





Linguagem natural
Gane & Sarsen/DeMarco/Yourdon
Entity-Relationship Diagrams
Jackson/Orr/Warnier,
SADT, PSL/PSA, SREM, etc.
Métodos formais




Finite State Machines
Petri Nets
Z
ANNA, VDM, CSP, etc.
Engenharia de Software
12
Formalidade vs Informalidade

Notações semi-formais



Possuem uma fraca semântica associada com a
estrutrura
Muito utilizadas, fácil compreensão
Notações formais


A semântica é claramente definida (conceito
matemático)
As especificações não são ambíguas



Menos atrito entre o cliente e o produtor de SW
Implementação mais fácil
Díficil compreensão
Engenharia de Software
13
Especificação Formal: Exemplo
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.
Engenharia de Software
14
Especificação Formal: Primeiro Passo
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.
Engenharia de Software
15
Especificação Formal








O = {o1, o2, o3, …}
S = {s1, s2, s3, …}
F=OUS
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
Engenharia de Software
16
Especificações Operacionais

Notações para indicação de especificações em
estilo operacional:

Diagramas de Fluxo de Dados - Data Flow Diagrams


Máquinas de Estados Finitas - Finite State Machines


Especificação de colecções de dados que são manipulados
por funções, em termos de repositórios e fluxos de dados
Especificação de estruturas de controlo
Redes de Petri – Petri Nets

Especificação de sistemas assíncronos, em termos de lugares
e transições entre lugares
Engenharia de Software
17
Data Flow Diagrams (DFDs)
DFDs



Servem para especificar as funções de um
sistema de informação
O sistema é descrito como uma colecção de
dados manipulados por funções
Os dados podem ser organizados de várias
formas:



Repositórios de dados
Transferências de dados
Entradas/saídas
Engenharia de Software
19
DFDs

Notação gráfica:




Nós (“bubble”): representam funções.
Setas: representam fluxos de dados
Caixas abertas: representam repositórios de dados.
Caixas de E/S: Representam a aquisição e produção
de dados durante a interacção humano-máquina.
Função
Dispositivo
de entrada
Dispositivo
de saída
Engenharia de Software
Fluxo de
Dados
Repositório
De Dados
20
Exemplo
(a + b) * (c + a * d)
b
+
ou,
em notação prefixa:
(* (+ a b) (+ c (* a d)))
Engenharia de Software
a
d
*
c
+
*
21
Outro Exemplo: Biblioteca
Livro
Título e Autor
do livro pedido;
Nome do utilizador
Prateleira
Obter
um
livro
Autor
Lista de
Autores
Lista de Titulos
Lista de
Tópicos
Livro
Título
Pedido de Livro
pelo utilizador
Recepção
do Livro
Titulo; utilizador
Título
Procurar
por
Tópico
Tópico
Tópico
Tópico
pedido pelo
utilizador.
Engenharia de Software
Lista de livros
emprestados
Lista de Títulos
Referentes ao
Tópico
Lista de
Títulos
22
Problemas com os DFDs

Os DFDs possuem uma notação gráfica atractiva capaz
de capturar de forma intuitiva o fluxo de dados e as
operações envolvidas num sistema de informação:




No entanto falta-lhes uma semântica precisa
Requerem uma interpretação intuitiva
Notação semi-formal
O controlo não é definido por este modelo:



Um nó ("bubble") utiliza todas as suas entradas ?
Espera por todas ou por um determinado número ?
Repete os cálculos quando as entradas são constantes ?
Engenharia de Software
23
Ultrapassar os problemas

Utilizar uma notação complementar para descrever os
aspectos não abrangidos pelas DFDs


Aumentar o modelo DFD, por forma a abranger mais
funcionalidades.


Especificação completa = DFDs + descrições auxiliares
e.g. Introdução de setas de controlo de fluxo
Rever a notação DFD tradicional para a tornar
completamente formal

Revela-se muito complicado !!!
Engenharia de Software
24
Máquinas de estado finitas
Máquinas de Estado Finitas
As MEF assumem que o sistema está sempre em
um dos estados permitidos
Switch on
Switch off
Current State
Action
Off
On
Switch on
On
On
Switch off
Off
Off
Switch off
Off
On
Switch on
Switch off
Engenharia de Software
Switch on
26
Máquinas de Estados Finitas


Trata-se de um modelo bem conhecido para representar
controlo.
Uma MEF é adequada para representar:




Anos de experiência com as MEF !!!
Exemplos:




Sistemas com num número finito de estados, e
Transições entre estados como consequência de um evento
Relógios
Calculadoras
Máquinas ATM
Por vezes o manual de utilização têm diagramas de MEF
Engenharia de Software
27
Máquinas de Estado Finitas



Estados
Distinção entre estado iniciais e/ou finais
Transição entre estados é accionada por
eventos:



Tais como pressionar o botão de uma
calculadora
Ou de um relógio
Ou uma item de um menu numa GUI
Engenharia de Software
28
Máquinas de Estado Finitas

Definição formal:

M = {Q,I,}, onde
Q é um conjunto finito de estados
 I é um conjunto finito de entradas
  é uma função de transição : Q x I -> Q


A função  pode ser uma função parcial (i.e.
indefinida para certos valores do seu domínio)
Engenharia de Software
29
Máquinas de Estado Finitas

Representação gráfica



Os nós (círculos) representam estados
Os arcos são dirigidos e possuem uma
etiqueta (label) que pertence ao conjunto I
Um arco com uma etiqueta i vai do estado q1
para q2 se e só se (q1,i) = q2
Engenharia de Software
30
Exemplo I
a
q0
q1
a
q2
b
c
q3
Engenharia de Software
b
31
Exemplo II
Engenharia de Software
32
Máquinas de Estado Finitas

Modelo de execução



A MEF está sempre em algum estado
A entrada obriga a mudanças de estado de
acordo com 
Extensões comuns:


Estados iniciais e estados de paragem
A saída é gerada quando existe uma transição
entre estados

 : Q x I -> Q x O
Engenharia de Software
33
Exemplo III
Engenharia de Software
34
Geração de Linguagens

Seja E = {a,b} um conjunto de eventos.
Considere a linguagem:


L = {a,aa,ba,aaa,aba,baa,bba,...}
i.e. Todas as strings de a e b seguidas de a.
a
b
0
a
b
Engenharia de Software
1
35
MEF equivalentes
a
b
a
0
1
b
a
a
0
1
b
a
a
0
a
1
b
2
b
0
a
b
1
a
…
a
b
Engenharia de Software
n
a
n+1
a
b
36
Blocking and Livelock


Estado 5 é uma deadlock
Estados 3 e 4 uma livelock
Engenharia de Software
37
Vantagens do modelo MEF

Simples de entender e mais precisa que outras
abordagens semi-formais:



Um menu de um GUI é uma MEF
Representação gráfica evidente e clara
É fácil construir ferramentas de suporte

Transformadores:


Transformam o modelo MEF em outras representações, e.g.
código C++
Análise e Validação:

Esta MEF irá correr para sempre ? Quando é que irá parar ?
Deadlock ?
Engenharia de Software
38
Limitações das MEF

Limite teórico no poder computacional


A MEF não possui memória
A utilização de estados como memória é ineficiente:



Explosão de estados na combinação de vários
módulos:


Considere modelar um sistema de navegação com estados
que modelam a velocidade:
Registo de 8 bits = 256 estados
Os estados são multiplicativos
Inerentemente síncrona:

Em cada instante, o estado global do sistema tem de
estar definido e apenas pode ocorrer uma transição
de cada vez
Engenharia de Software
39
Redes de Petri
Introdução
•
•
•
Introduzidas por Carl Adam Petri em 1962
Ferramenta de diagramas para modelar
concorrência e sincronização em sistemas
distribuídos
Baseada numa fundação matemática
muito forte
Engenharia de Software
41
Uma especificação de Redes Petri

Consiste em três tipos de componentes:
lugares (círculos), transições (rectângulos
ou barras) e arcos (setas):



Os lugares representam os estados possíveis
do sistema
As transições são eventos ou acções que
causam a mudança de estado
Cada arco liga um lugar com uma transição ou
uma transição com um lugar
Engenharia de Software
42
Exemplo de Rede de Petri
Engenharia de Software
43
Exemplo: Sistema de Segurança
1 digit
Initial
1 digit
d1
1 digit
d2
1 digit
d4
d3
OK
OK
OK
OK
OK
OK
pressed
Rejected!
Reject
approve
approved
Engenharia de Software
44
Mudança de estado



Ocorre quando existe um movimento de
token(s) (pontos pretos) de lugar em lugar
e é causado pelo disparo de uma transição
O disparo representa a ocorrência de um
evento ou uma acção tomada
O disparo é sujeito às condições de
entrada, i.e. pela disponibilidade de
tokens(s)
Engenharia de Software
45
Mudança de estado



Uma transição está activa quando existem
tokens suficientes nas suas entradas
Depois do disparo, os tokens irão ser
transferidos dos lugares de entrada (estado
anterior) para os lugares de saída (novo estado)
Quando uma transição está activa a rede pode
evoluir de formas diferentes:

O modelo é não determinístico


Mesmo estado inicial – vários estados finais possíveis
Salienta-se que o exemplo anterior é uma rede
de Petri de uma MEF
Engenharia de Software
46
Exemplo: Sistema de Segurança
• Cenário 1: Normal
•
Introduz os 4 dígitos e pressiona em OK.
• Cenário 2: Excepcional
•
Introduz apenas 3 dígitos e pressiona em OK.
Engenharia de Software
47
Exemplo: Sistema de Segurança
1 digit
Initial
1 digit
d1
1 digit
d2
1 digit
d4
d3
OK
OK
OK
OK
OK
OK
pressed
Rejected!
Reject
approve
approved
Engenharia de Software
48
Múltiplos estados locais



No mundo real, existem eventos que
acontecem ao mesmo tempo
Um sistema pode ter muitos estados locais
para obter um estado global
Existe uma necessidade de modelar
concorrência e sincronização
Engenharia de Software
49
Estruturas da rede

Uma sequência de eventos/acções:
e1

e2
e3
Execuções concorrentes:
e2
e3
e4
e5
e1
Engenharia de Software
50
Estruturas de rede

Eventos não determínisticos - conflito, escolha
ou decisão : A escolha de e1, e2 … ou e3, e4 ...
e1
e2
e3
e4
Engenharia de Software
51
Estrutura da rede

Sincronização
e1
Engenharia de Software
52
Estruturas de Rede

Sincronização e Concorrência
e1
Engenharia de Software
53
Exemplo: Obtenção de um recurso
Estado Inicial
T1 dispara
T2 dispara
Modelo não
deterministico
Tanto t3 como
t4 podem disparar
Modelo
concorrente.
O disparo de t1
não impede t2
de disparar
Engenharia de Software
54
Exemplo: Obtenção de um recurso
Estado Inicial
T1 e T2 dispara
Não está definida
uma política
de resolução
de conflitos
T3 dispara
T5 dispara
Pode ocorrer
starvation
Engenharia de Software
55
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)
A  ( P  T )  (T  P) é o conjunto de arcos de lugares para
transições (pi,tj) e transições para lugares (tj,pi)
w : A  1,2,3, é a função de pesos associados aos arcos
Conjunto de lugares de entrada de t j  T
I (t j )  { pi  P : ( pi , t j )  A}
Conjunto de lugares de saída de t j  T
O(t j )  { pi  P : (t j , pi )  A}
Engenharia de Software
57
Exemplo de Rede de Petri
p2
t2
p1
p4
t1
p3
t3
P  p1 , p 2 , p3 , p 4 }
T  t1 ,t 2 , t 3 }
A  {( p1 , t1 ), ( p 2 , t 2 ), ( p 2 , t 3 ), ( p3 , t 3 ), (t1 , p 2 ), (t1 , p3 ), (t 2 , p1 ), (t 3 , p3 ), (t 3 , p 4 )}
T odosos pesossão  1
Engenharia de Software
58
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;
x  [ x( p1), x( p2 ),, x( pn )]  Nn
é o vector linha associado a x.
Def. (Dinâmica de RdP): A função de transição de estado,
f : N n  T  N n da rede de Petri (P,T,A,w,x), está definida
para a transição t j  T sse
tj Permitida
x( pi )  w( pi , t j ), pi  I (t j ).
(Enabled)
Se f(x,tj) estiver definida, o novo estado é dado por x’ = f(x,tj), onde
x' ( pi )  x( pi )  w( pi , t j )  w(t j , pi ), i  1,, n.
Engenharia de Software
59
Marcações, Dinâmica e Espaço de Estados
p2
t2
p1
p4
t1
p3
t3
x  x 0  1 0 0 0
Engenharia de Software
60
Marcações, Dinâmica e Espaço de Estados
p2
t2
p1
p4
t1
p3
t3
x  0 1 1 0
Engenharia de Software
61
Marcações, Dinâmica e Espaço de Estados
p2
t2
p1
p4
t1
p3
t3
x  1 0 1 0
Engenharia de Software
62
Marcações, Dinâmica e Espaço de Estados
p2
t2
p1
p4
t1
p3
t3
x  0 1 2 0
Engenharia de Software
63
Marcações, Dinâmica e Espaço de Estados
p2
t2
p1
p4
t1
p3
t3
x  0 0 2 1
Engenharia de Software
64
Caracteristicas das Petri Nets







Petri Nets servem para modelar o comportamento de um
sistema durante o desenvolvimento do SW
Petri Nets modelam MEF
Modelam um estado global e muitos estado locais no
mundo real
Uma rede de Petri permite múltiplos cenários
Diferentes tokens para diferentes cenários
Redes de Petri : Sequência, Escolha, Sincronização e
Concorrência
Mais expressivas que as MEF
Engenharia de Software
65
Comportamento
• Estados alcançáveis
•
“Pode-se alcançar um estado particular a partir
de outro?”
• Limite de armazenamento
•
“Irá haver overflows num círculo ?”
• Deadlocks ?
•
“Irá o sistema morrer num estado particular ?”
Engenharia de Software
66
Limite
•
•
Diz-se que uma rede de Petri possui um
limite em k ou é simplesmente limitada se
o número de tokens em cada lugar não
excede um número finito k para qualquer
estado a partir de M0
A rede de Petri para a máquina de vendas
possui um limite em 1
•
A rede de Petri net diz-se segura (safe)
Engenharia de Software
67
Bloqueio



Uma rede de Petri pode entrar num estado de
bloqueio (deadlock) quando não é possível
disparar nenhuma transição
Uma rede de Petri em que não é possível haver
bloqueios diz-se “viva”
É possível analisar a existência de estados de
bloqueio no sistema através da análise manual
da rede de Petri que modela o sistema
Engenharia de Software
68
Deadlocks ?
•
•
•
A máquina de vendas e o sistema produtorconsumidor não possuem deadlocks
Uma transição está morta se não pode ser
disparada por qualquer sequência de disparo
Outra definição: “Uma rede de Petri com um
marcas iniciais M0 não possui deadlocks se, para
qualquer situação alcançada a partir de M0, é
possível disparar uma transição através de uma
sequência de disparo”
Engenharia de Software
69
Bloqueio
Engenharia de Software
70
Um exemplo
t1
p3
p2
p1
t3
t4
p4
t2
M0 = (1,0,0,1)
M1 = (0,1,0,1)
M2 = (0,0,1,0)
M3 = (0,0,0,1)
A bounded but non-live Petri net
Engenharia de Software
71
Outro exemplo
M0 = (1, 0, 0, 0, 0)
p1
M1 = (0, 1, 1, 0, 0)
M2 = (0, 0, 0, 1, 1)
t1
M3 = (1, 1, 0, 0, 0)
p2
p3
t2
t3
p4
p5
t4
M4 = (0, 2, 1, 0, 0)
An unbounded but live Petri net
Engenharia de Software
72
Métodos de Análise
• Análise de alcançabilidade:
•
•
Árvore de cobertura
Problema na explosão de estados
• Matriz de Incidência e Equações de estado
• Análise estrutural
•
Baseado em estruturas de rede
Engenharia de Software
73
Limitações das Redes de Petri


Marcas anónimas => não é possível a
tomada de decisões (de selecção) com
base no conteúdo nem a modificação do
conteúdo
Não existe o conceito de “tempo” de uma
forma explicita:

Limita a sua utilização em sistemas de tempo
real
Engenharia de Software
74