Computação Avançadanpereira/aulas/compa/09/COMPA... · 2. E agora modelamos a activação do processo de monitorização t 1 t 2 t 3 t 4 t 5 t 6 t 7 TP - Módulo 1; Com Resoluções

1

TP - Módulo 1; Com Resoluções 1

Computação Avançada

Módulo 1 (Aula Teórico-Prática)Modelação e Análise de Sistemas Computacionais

Nuno Pereira [email protected] Tovar [email protected]


PARTE I

Revisão das Regras das RdP

2


A

Conjunto de Exemplos (1)(Marcação Inicial)

B

22

C

22


A B

22

C

22

A C

22

Transição habilitada. Transição não habilitada.

Transição habilitada.

Conjunto de Exemplos (1)(Evolução da Marcação)

Após disparo Após disparo

3



F

22

D

22

E

1010 100100



F

22

D

22

E

1010 100100

F

22

D

22

E

1010 100100

1010

Disparo acrescenta dez marcas na posição posterior.

100100

Após disparo Após disparoApós disparo

Disparo acrescenta duas marcas na posição posterior.

Disparo acrescenta cem marcas na

posição posterior.

4



G H

22

I

22

33



G H

22

IH

22

22 33

I

22

33

Após disparoApós disparo

Transição não habilitada.

5



J K L

22 22

33

55



J K L

22 22

33

55

J K L

22 22

33

55

Após disparo Após disparoApós disparo

6


M


N

33


M


N

33

M N

33

Após disparoApós disparo

7


Exercício

2233

•Qual é a sequência de disparo de transições?

t1

t2

t3

t4

P1

P2 P3

P4

P5

P6

P7

P8


Exercício

2233

t1

t2

t3

t4

P1

P2 P3

P4

P5

P6

P7

P8

8


Exercício

2233

t1

t2

t3

t4

P1

P2 P3

P4

P5

P6

P7

P8


Exercício

2233

t1

t2

t3

t4

P1

P2 P3

P4

P5

P6

P7

P8

9


Exercício

2233

t1

t2

t3

t4

P1

P2 P3

P4

P5

P6

P7

P8


Exercício

2233

t1

t2

t3

t4

P1

P2 P3

P4

P5

P6

P7

P8

10


Exercício

• Elaborar o respectivo gráfico das marcações acessíveis


Exercício

• Elaborar o respectivo gráfico das marcações acessíveis

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

=

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎣

⎡

= →→→→→

11010000

00130000

00001100

00001011

00000102

00000013

543210

43121

MMMMMMttttt

11


PARTE II

Exemplos de Modelação


Exemplos de Modelação

1. Semáforos de Trânsito2. Sistema Sequencial c/ Monitorização3. Comutador Simples4. Trabalhos de Impressão 5. Servidor de Base de Dados (Exercício)

12


1. Semáforos de Trânsito

• Um semáforo de trânsito com três cores.• Apenas uma cor está acesa de

cada vez



• Um semáforo de trânsito com três cores.• Apenas uma cor está acesa de

cada vez

VerdeVerde

AmareloAmarelo

VermelhoVermelho

t1

t2

t3

13


1. Semáforos de Trânsito• Dois semáforos de trânsito num cruzamento (S1 e S2).• Não podemos ter dois semáforos a verde!

S1S1 S2S2



Este modelo NÃO garante alternância!Este modelo NÃO garante alternância!

Verde S2Verde S2

Amarelo S2Amarelo S2

Vermelho S2Vermelho S2

Verde S1Verde S1



S1S1 S2S2

• Dois semáforos de trânsito num cruzamento (S1 e S2).• Não podemos ter dois semáforos a verde!• Devemos garantir alternância entre os dois semáforos.

t1

t2

t3

t4

t5

t6

14



Verde S2Verde S2



Verde S1Verde S1



• Dois semáforos de trânsito num cruzamento (S1 e S2).• Não podemos ter dois semáforos a verde!• Devemos garantir alternância entre os dois semáforos.

S1S1 S2S2

t1

t2

t3

t4

t5

t6



• Sequência de transições

S1S1 S2S2

Verde S2Verde S2



Verde S1Verde S1



t1

t2

t3

t4

t5

t6

15




Verde S2Verde S2



Verde S1Verde S1



S1S1 S2S2

t1

t2

t3

t4

t5

t6




Verde S2Verde S2



Verde S1Verde S1



S1S1 S2S2NOTA: A duração deste estado é zero.

t1

t2

t3

t4

t5

t6

16




Verde S2Verde S2



Verde S1Verde S1



S1S1 S2S2

t1

t2

t3

t4

t5

t6




Verde S2Verde S2



Verde S1Verde S1



S1S1 S2S2

t1

t2

t3

t4

t5

t6

17




Verde S2Verde S2



Verde S1Verde S1



S1S1 S2S2

t1

t2

t3

t4

t5

t6


2. Sistema Sequencial c/ Monitorização

• Um sistema executa 4 processos sequenciais: A, B, C e D.• Enquanto estiverem a ser executados os processos B ou D, é

despoletado um processo secundário de monitorização

• Passos de modelação:

1. Começamos por modelar a sequência de processos;2. Depois, modelamos a activação do processo de monitorização.

18





MonitorizaMonitorizaççãoão

AA

BB

CC

DD

1. Come1. Começçamos por modelar a amos por modelar a sequência de processossequência de processos

EsperaEspera

t1

t2

t3

t4

t5

t6






AA

BB

CC

DD

EsperaEspera

2. E agora modelamos a 2. E agora modelamos a activaactivaçção do processo de ão do processo de monitorizamonitorizaççãoão

t1

t2

t3

t4

t5

t6

19





AA

BB

CC

DD

O processo de monitorizaO processo de monitorizaçção ão éédespoletado despoletado enquantoenquanto existir uma existir uma marca em B marca em B ouou DD


EsperaEspera

2. E agora modelamos a 2. E agora modelamos a activaactivaçção do processo de ão do processo de monitorizamonitorizaççãoão

t1

t2

t3

t4

t5t6

t7


3. Comutador Simples

RoundRound--RobinRobinPISCOPISCO

• Um comutador (switch) que serve as portas de entrada em Round-Robin (RR).

• Consideremos que:– Cada porta tem uma fila de entrada de mensagens com capacidade

máxima de 50 mensagens;– O comutador precisa de V unidades de tempo para verificar se fila de

entrada de mensagens tem mensagens;– O comutador demora C unidades de tempo para colocar a mensagem

na fila de saída da porta de destino;– A chegada de mensagens a uma porta do comutador acontece de

acordo com um processo de poisson (tempo entre chegadas exponencial).

20


3. Comutador Simples• Por simplicidade vamos modelar apenas 4 portas.

• Passos de modelação:1. Comecemos por modelar o mecanismo RR de serviço às filas do

comutador; 2. De seguida modelamos a verificação das filas de mensagens e

comutação em cada nó;3. Finalmente, modelar o caso quando o Buffer de mensagens

está vazio.


3. Comutador Simples• Por simplicidade vamos modelar apenas 4 portas.• Comecemos por modelar o mecanismo RR de serviço às filas do

comutador:

Estes blocos vão ser substituídos pela verificação das filas de mensagens e comutação das mensagens

InInííciocio FimFim InInííciocio FimFim InInííciocio FimFim InInííciocio FimFim

Porta 1 Porta 2 Porta 3 Porta 4

21


3. Comutador Simples• De seguida modelamos a verificação das filas de

mensagens e comutação em cada nó:

FimFim

Chegada Chegada MsgMsg

BufferBuffer MsgMsg

BufferBuffer c/ c/ MsgMsg

Porta XPorta X

Tempo de verificaTempo de verificaçção da ão da fila de mensagens (fila de mensagens (VV))

InInííciocio

Tempo Tempo para colocar a para colocar a mensagem na fila de mensagem na fila de sasaíída da porta de da da porta de destinodestino ((CC))Comuta Comuta MsgMsg


3. Comutador Simples• Falta modelar o caso quando o Buffer de mensagens

está vazio:

FimFim


BufferBuffer MsgMsg


Porta XPorta X


InInííciocio


22


3. Comutador Simples• Falta modelar o caso quando o Buffer de mensagens

está vazio:

FimFim


BufferBuffer MsgMsg


Porta XPorta X

5050

5050

BufferBuffer VazioVazio

5050

Tamanho do Tamanho do BufferBuffer Leitura da posiLeitura da posiçção. Se tem menos de 50 ão. Se tem menos de 50 marcas, então existem mensagens no marcas, então existem mensagens no bufferbuffer; senão, o ; senão, o bufferbuffer estestáá vazio.vazio.

InInííciocio




3. Comutador Simples

Porta 1 Porta 2 Porta 3 Porta 4

50505050

5050

InInííciocio FimFim 50505050

5050


5050


5050

InInííciocio FimFim

• O modelo final:

23


4. Trabalhos de Impressão• Temos 3 processos P1, P2, P3.• O processo P1 faz o pré-processamento de trabalhos de

impressão.• Após o pré-processamento de P1, pode ser executado o

processo P2 ou P3 que enviam os trabalhos para as impressoras

• Os processos acedem às seguintes estruturas de dados partilhadas:– P1: Acede a I1 ou I2– P2: Acede a I1– P3: Acede a I2


4. Trabalhos de Impressão

• Passos de modelação:

1. Vamos começar por fazer a estrutura sequencial básica: Chegada de pedidos → P1 → P2 ou P3;

2. Modelar os acessos aos recursos (Impressoras I1 e I2):1. Começamos por modelar o acesso feito por P2 e P3;2. Modelar o acesso feito por P1 aos recursos partilhados.

24



Fila PedidosFila Pedidos

Chegada Chegada PedidoPedido

P2P2

Pedido Pedido ImpressoImpresso

• Vamos começar por fazer a estrutura sequencial básica: Chegada de pedidos → P1 → P2 ou P3:

P1P1

P3P3

Executa P2 Executa P2 OUOU P3P3





P2P2


• Temos de modelar os acessos aos recursos (Impressoras I1 e I2); Começamos por modelar o acesso feito por P2 e P3:

P1P1

P3P3

I1I1

I2I2

Acesso de P2 a I1Acesso de P2 a I1

Acesso de P3 a I2Acesso de P3 a I2

25





P2P2


• Como modelar o acesso feito por P1 aos recursos partilhados?

P1P1

P3P3

I1I1

I2I2

Esta opção de modelação indica que P1utiliza I1 e I2 ao mesmo tempo.





P2P2


• Temos de modelar a alternativa de aceder a um recurso ou outro (I1 ou I2)…

P1P1

P3P3

I1I1

I2I2

26



• Modelar a alternativa de aceder a um recurso ou outro:



I2I2

I1I1

P1 utiliza I1P1 utiliza I1


P2P2

P3P3


P1 utiliza I1 P1 utiliza I1 OUOU I2I2

P1 enquanto utiliza I1P1 enquanto utiliza I1

P1 enquanto utiliza I2P1 enquanto utiliza I2



• Temos de modelar o facto de apenas poder ser executada uma das opções:



I2I2

I1I1



P2P2

P3P3


27





I2I2

I1I1



P2P2

P3P3


• Adicionando todos os acesso aos recursos, temos o modelo final:


Exercício: 5. Servidor de Base de Dados

• Uma base de dados cria processos que acedem a uma tabela. Os processos podem ter dois estados: escrita e leitura.

• As operações de leitura e escrita são exclusivas; Quando temos um leitor a aceder à tabela, nenhum escritor pode aceder a esta e vice-versa.

• São permitidos vários leitores ao mesmo tempo, mas por restrições do sistema, apenas podemos ter um máximo de cinco leitores a aceder àtabela ao mesmo tempo.

• Apenas podemos ter um escritor de cada vez.

• Podem existir em simultâneo um máximo de 50 processos a pendentes para efectuar leituras.

• Podem existir em simultâneo um máximo de 10 processos a pendentes para efectuar escritas.

28


5. Servidor de Base de Dados

Fila LeitoresFila Leitores Fila EscritoresFila Escritores5050 1010

• Começamos pelas duas filas; Leitores e escritores:

Limitador da fila de leitores (Limitador da fila de leitores (““mmááximo de ximo de 50 50 processos a pendentes para efectuar processos a pendentes para efectuar leiturasleituras””))

Limitador da fila de escritores (Limitador da fila de escritores (““mmááximo ximo de 10 de 10 processos a pendentes para processos a pendentes para efectuar leiturasefectuar leituras””))


5. Servidor de Base de Dados

Fila LeitoresFila Leitores Fila EscritoresFila Escritores

LeituraLeitura EscritaEscrita

55

55

5050 1010

55

• E depois modelamos a leitura e escrita:

Limitador do nLimitador do núúmero de processos a ler (5)mero de processos a ler (5)Limitador do nLimitador do núúmero de processos a escrever (1)mero de processos a escrever (1)

Exclusão mExclusão múútua entre leitores e escritorestua entre leitores e escritores

Documents

Computação Avançadanpereira/aulas/compa/09/COMPA... · 2. E agora modelamos a activação do processo de monitorização t 1 t 2 t 3 t 4 t 5 t 6 t 7 TP - Módulo 1; Com Resoluções