Arquitetura de Sistemas Embarcadosensb/pub/apse/design-tech-ensb-cap8-11...Embarcados – Pode ser extremamente difícil • Complexidade crescente com a crescente capacidade dos IC´s

Arquitetura de Arquitetura de Sistemas EmbarcadosSistemas EmbarcadosEdna Barros ([email protected])Edna Barros ([email protected])

Centro de Informática – UFPE

Capítulo 8: Máquinas de Capítulo 8: Máquinas de Estado Finitos (FSM) e Estado Finitos (FSM) e Modelos de Programação Modelos de Programação ConcorrenteConcorrente

RoteiroRoteiro

• Modelos vs. Linguagens

• Modelo de Máquinas de Estado Finitos– FSM/FSMD– HCFSM e Linguagem Statecharts – Program-State Machine (PSM) Model

Engenharia de Sistemas Embarcados 3

– Program-State Machine (PSM) Model

• Modelo de Programação Concorrente– Communicação– Sincronização– Implementação

• Modelo de Fluxo de Dados (Dataflow)

• Sistemas de Tempo Real

• Descrevendo o Comportamento de Sistemas Embarcados– Pode ser extremamente difícil

• Complexidade crescente com a crescente capacidade dos IC´s

– Passado: máquinas de lavar, jogos, etc…» Centenas de linhas de código

IntroduçãoIntrodução


– Passado: máquinas de lavar, jogos, etc…» Centenas de linhas de código

– Hoje: TV set-top boxes, Telefones celulares, etc.» Centenas de milhares de linhas de código

• Comportamento desejado não está completamente definido (entendido) no início do projeto

– Vários erros de implementação devido a erros na descrições (omissões)

– Linguagem Natural é a linguagem inicial de especificação• Descrição precisa é muito difícil

Modelos e linguagensModelos e linguagens

• Como capturar o comportamento de maneira precisa?– Importância de modelo de computação

• Modelos de Computação Comuns


• Modelos de Computação Comuns– Modelo de programação Sequencial

• Atribuições, regras para composição, semantica de execução das regras

– Modelos de Processos Comunicantes• Múltiplos programas sequenciais executando

concorrentemente

Modelos e linguagensModelos e linguagens

• Modelos de Computação Comuns :– Modelo de Máquinas de Estado

• Para sistemas de controle: monitoramento das entradas, ativação de saídas

– Modelo de Fluxo de Dados


– Modelo de Fluxo de Dados• Para sistemas de processamento de informações:

transformação de streams de entrada gerando streams de saída

– Modelo Orientado a Objetos• Uso de abstrações

Modelos vs. linguagensModelos vs. linguagens

Models

Languages

Recipe

SpanishEnglish Japanese

Poetry Story Sequent.

program

C++C Java

State

machine

Data-

flow

Recipes vs. Sequential programs vs.


• Modelos Computacionais descrevem o comportamento do sistema

• Linguagens capturam os modelos

• Um modelo pode ser capturado por uma variedade de linguagens– E.x., programa sequencial � C,C++, Java

• Uma linguagem pode capturar uma variedade de modelos– E.X., C++ → modelo de programa sequencial program model, modelo

orientado a objetos, modelo de máquinas de estado

Recipes vs.

English

Sequential programs vs.

C

Texto vs GráficoTexto vs Gráfico

• Modelos versus linguagens não devem ser confundidos com descrição textual versus descrição gráfica– Textos e gráficos são dois tipos de linguagens


X = 1;

Y = X + 1;

X = 1

Y = X + 1

Exemplo Introdutório:Exemplo Introdutório:Controle de um ElevadorControle de um Elevador

• Controle Simples

“Move the elevator either up or down to

reach the requested floor. Once at the

requested floor, open the door for at least

10 seconds, and keep it open until the

requested floor changes. Ensure the door

is never open while moving. Don’t

change directions unless there are no

higher requests when moving up or no

Partial English description

buttons

Unit

Control

b1

down

open

floor

Request

Resolver

req

up

System interface


• Controle Simples– Request Resolver

resolve várias requisições

– Unit Control move o elevador para o andar requisitado

• Tente descrever em C...

higher requests when moving up or no

lower requests when moving down…”

buttons

inside

elevator

b1

...

Resolver

...

up/down

buttons on

each

floor

b2

bN

up1

up2

dn2

dnN

up3

dn3

Controle do Elevador: Modelo Controle do Elevador: Modelo Sequencial…Sequencial…

“Move the elevator either up or down

to reach the requested floor. Once at

the requested floor, open the door for

at least 10 seconds, and keep it open

until the requested floor changes.

Ensure the door is never open while

moving. Don’t change directions

unless there are no higher requests

when moving up or no lower requests

when moving down…”

Partial English description

buttons

inside

Unit

Control

b1

down

open

floor

Request

Resolver

b2

req

up

System interface

Sequential program model

void UnitControl()

{

up = down = 0; open = 1;

void RequestResolver()

{

while (1)

Inputs: int floor; bit b1..bN; up1..upN-1; dn2..dnN;

Outputs: bit up, down, open;

Global variables: int req;


when moving down…”inside

elevator...

...

up/down

buttons on

each

floor

b2

bN

up1

up2

dn2

dnN

up3

dn3


while (1) {

while (req == floor);

open = 0;

if (req > floor) { up = 1;}

else {down = 1;}

while (req != floor);

up = down = 0;

open = 1;

delay(10);

}

}

while (1)

...

req = ...

...

}

void main()

{

Call concurrently:

UnitControl() and

RequestResolver()

}

Modelo de Máquina de Estados Modelo de Máquina de Estados Finito (FSM)Finito (FSM)

• Descrever o sistema como:– Estados Possíveis

• E.x., Idle, GoingUp, GoingDn, DoorOpen

– Transições possíveis de estado dependendo das entradas• E.x., req > floor


• E.x., req > floor

– Ações que devem ser feitas em cada estado• E.x., No estado GoingUp: u,d,o,t = 1,0,0,0 (up = 1, down, open,

and timer_start = 0)

Modelo de Máquina de Estados Modelo de Máquina de Estados Finito (FSM)Finito (FSM)

GoingUp

req > floor

!(req > floor)

req > floor

u,d,o, t = 1,0,0,0

timer < 10

UnitControl process using a state machine


Idle

req < floor

!(timer < 10)

req < floor

DoorOpen

GoingDn

req > floor

u,d,o,t = 0,0,1,0

u,d,o,t = 0,1,0,0

u,d,o,t = 0,0,1,1

u is up, d is down, o is open

req == floor

!(req<floor)

timer < 10

t is timer_start

Definição FormalDefinição Formal

• Uma FSM é uma 6-tuple F<S, I, O, F, H, s0>– S : conjunto de todos os estados {s0, s1, …, sl}– I : conjunto de entradas {i0, i1, …, im}– O : conjunto de saídas {o0, o1, …, on}– F é a função de próximo estado (S x I → S)– H é a função de saída (S → O)


– H é a função de saída (S → O)– s0 é o estado inicial

• Tipo Moore– Saídas mudam nos estados

• Tipo Mealy – Saídas mudam na transição

Máquina de Estados Finito com Máquina de Estados Finito com Processamento de Dados(FSMD)Processamento de Dados(FSMD)• FSMD estende FSM: tipos de dados e variáveis para armazenar

dados

• FSMD: 7-tuple <S, I , O, V, F, H, s0>– S : conjunto de todos os estados {s0, s1, …, sl}– I : conjunto de entradas {i0, i1, …, im}– O : conjunto de saídas {o , o , …, o }


– O : conjunto de saídas {o0, o1, …, on}– V é o conjunto de variáveis {v0, v1, …, vn}– F é a função de próximo estado (S x I x V → S)

– H á uma função de ação (S → O + V)

– s0 é o estado inicial

• I,O,V podem representar tipos de dados complexos (inteiros, ponto-flutuante, etc.

• F,H podem incluir operações aritméticas

• H : descreve atualização das variáveis

Máquina de Estados Finito com Máquina de Estados Finito com Processamento de Dados(FSMD)Processamento de Dados(FSMD)

GoingUp

req > floor

!(req > floor) u,d,o, t = 1,0,0,0

We described UnitControl as an FSMD


Idle

GoingUp

req < floor

!(req > floor)

!(timer < 10)

req < floor

DoorOpen

GoingDn

req > floor

u,d,o, t = 1,0,0,0

u,d,o,t = 0,0,1,0

u,d,o,t = 0,1,0,0

u,d,o,t =

0,0,1,1

u is up, d is down, o is open

req ==

floor

!(req<floor)

timer < 10

t is timer_start

FSM vs. Programa SequencialFSM vs. Programa Sequencial

• Máquina de Estado:– O projetista deve pensar em todos os estados e transições de

acordo com os valores dos sinais de entrada

• Modelo de programação Sequencial


• Modelo de programação Sequencial– Projetista transforma dados através de um conjunto de

instruções de forma repetitiva ou condicional

Descrevendo FSM com Descrevendo FSM com Linguagens de ProgramaçãoLinguagens de Programação• Linguagens são amplamente utilizadas:

– C, C++, Java, Ada, VHDL, Verilog, etc.– Alto custo de ferramenta de desenvolvimento

• Duas abordagens para Descrição de FSM´s usando Linguagens de programação


– Ferramenta de Front-end • Suporte a especificações gráficas com geração automática de

código

– Definição de subconjunto da Linguagem

Subconjunto de uma LinguagemSubconjunto de uma Linguagem

#define IDLE0

#define GOINGUP1

#define GOINGDN2

#define DOOROPEN3

void UnitControl() {

int state = IDLE;

while (1) {

switch (state) {

IDLE: up=0; down=0; open=1; timer_start=0;

if (req==floor) {state = IDLE;}

if (req > floor) {state = GOINGUP;}



if (req < floor) {state = GOINGDN;}

break;

GOINGUP: up=1; down=0; open=0; timer_start=0;


if (!(req>floor)) {state = DOOROPEN;}

break;

GOINGDN: up=1; down=0; open=0; timer_start=0;

if (req < floor) {state = GOINGDN;}

if (!(req<floor)) {state = DOOROPEN;}

break;

DOOROPEN: up=0; down=0; open=1; timer_start=1;

if (timer < 10) {state = DOOROPEN;}

if (!(timer<10)){state = IDLE;}break;

}}

}

UnitControl state machine in sequential programming

language

Template GenéricoTemplate Genérico#define S0 0

#define S1 1

...

#define SN N

void StateMachine() {

int state = S0; // or whatever is the initial state.

while (1) {

switch (state) {

S0:

// Insert S0’s actions here & Insert transitions Ti leaving S0:

if( T0’s condition is true ) {state = T0’s next state; /*actions*/

}


}

if( T1’s condition is true ) {state = T1’s next state; /*actions*/

}

...

if( Tm’s condition is true ) {state = Tm’s next state; /*actions*/

}

break;

S1:

// Insert S1’s actions here

// Insert transitions Ti leaving S1

break;

...

SN:

// Insert SN’s actions here

// Insert transitions Ti leaving SN

break;

}

}

}

HCFSM e Linguagem StatechartsHCFSM e Linguagem Statecharts

• Modelo de FSM´s Hieráquicas (HCFSM)– Extensão para suportar hierarquia e

concorrência

– Estados podem ser decompostos em outras FSM´s

– Estados podem executar concorrentemente

• Statecharts

A1 z

B

A2 z

xy

w

Without hierarchy

A1 z

B

A2

x y

A

w

With hierarchy


• Statecharts– Linguagem gráfica

– timeout: transição com tempo limite de execução

C1

C2

x y

C

B

D1

D2

u v

D

Concurrency

UnitControlUnitControl com com FireModeFireMode• FireMode

– Quando fire é verdade elevador move para 1o. Andar e porta abre

Without hierarchy

Idle

GoingUp

req>floor

req<floor

!(req>floor)

timeout(10)

req<floor

DoorOpen

GoingDn

req>floor

u,d,o = 1,0,0

u,d,o = 0,0,1

u,d,o = 0,1,0

req==floor!(req<floor)

firefire

firefire

FireGoingDn

floor>1

u,d,o = 0,1,0

u,d,o = 0,0,1

!fire

FireDrOpen

floor==1

fire

u,d,o = 0,0,1

UnitControl

With hierarchy

UnitControl

– Sem hierarquia: confuso!

– Com hierarquia: Simples!


Without hierarchy

fire

!fireFireGoingDn

floor>1

u,d,o = 0,1,0

FireDrOpen

floor==1

fire

FireMode

u,d,o = 0,0,1

Idle

GoingUp

req>floor

req<floor

!(req>floor)

timeout(10)

req<floor

DoorOpen

GoingDn

req>floor

u,d,o = 1,0,0

u,d,o = 0,0,1

u,d,o = 0,1,0

req==floor!(req>floor)

u,d,o = 0,0,1

NormalMode

UnitControl

NormalMode

FireMode

fire!fire

UnitControl

ElevatorController

RequestResolver

...

With concurrent RequestResolver

Modelo PSM (ProgramModelo PSM (Program--state machine model) : state machine model) : HCFSM + Programação SequencialHCFSM + Programação Sequencial

• Ações podem ser FSM´s ou Programas

• Hierarquia mais restritiva – Única ponto de entrada

– Program-state deve executar


while (1) {

while (req == floor);

open = 0;

if (req > floor) { up = 1;}

else {down = 1;}

while (req != floor);

open = 1;

delay(10);

}

}

NormalMode

UnitControl

ElevatorController

RequestResolver

...

req = ...

...

int req;


– Program-state deve executar completamente

• PSM tem dois tipos de transições:– Transition-immediately (TI): – Transition-on-completion (TOC):

– SpecCharts: extensão de VHDL para capturar Modelo PSM

– SpecC: extensão de C para capturar modelo PSM

}

FireMode

up = 0; down = 1; open = 0;

while (floor > 1);

up = 0; down = 0; open = 1;

fire!fire

• NormalMode and FireMode described as

sequential programs

• Black square originating within

FireMode indicates !fire is a TOC

transition

– Transition from FireMode to

NormalMode only after FireMode

completed

Modelo de Processos Modelo de Processos ConcorrentesConcorrentes

• Descreve a funcionalidade como dois ou mais processos que executam concorrentemente

• Exemplo– Leitura de dois números X e Y– Mostre a mensagem “Hello world.” a cada X segundos

– Mostre a mensagem “How are you?” a cada Y segundos

ConcurrentProcessExample() {

x = ReadX()

y = ReadY()

Call concurrently:

PrintHelloWorld(x) and

PrintHowAreYou(y)

}

PrintHelloWorld(x) {

while( 1 ) {


Subroutine execution over time

time

ReadX ReadY

PrintHelloWorld

PrintHowAreYou

Simple concurrent process example

print "Hello world."

delay(x);

}

}

PrintHowAreYou(x) {

while( 1 ) {

print "How are you?"

delay(y);

}

}

Sample input and output

Enter X: 1

Enter Y: 2

Hello world. (Time = 1 s)


How are you? (Time = 2 s)


How are you? (Time = 4 s)


...

Modelo DataflowModelo Dataflow• Derivado do modelo de processo concorrente

• Nós representam transformações– Podem executar concorrentemente

• Arcos representam fluxo de dados de um nó para outro

– Pode haver ou não um arco num instante de tempo

• Quando os dados estão disponíveis o nó pode realizar a

+ –

*

A B C D

t1 t2

Z = (A + B) * (C - D)


• Quando os dados estão disponíveis o nó pode realizar a operação

• Quando a operação é realizada no nó os dados são consumidos e um dado é colocado na saída no nó

• Nós podem operar simultaneamente modulate convolve

transform

A B C D

Z

Nodes with more complex

transformations

t1 t2

Z

Nodes with arithmetic

transformations

Dataflow SíncronoDataflow Síncrono

• Nos processadores DSP o fluxo de dados tem uma taxa fixa

• Vantagens do modelo síncrono– Cada arco pode ser rotulado com

número de dados

modulate convolve

A B C D

mt1 ct2

mA mB mC mD

tt1 tt2

t1 t2


número de dados consumido/produzido em cada operação

– Nós podem ser escalonados estaticamente

transform

Z

Synchronous dataflow

tZ

Processos Concorrentes e Processos Concorrentes e Sistemas de Tempo RealSistemas de Tempo Real


Sistemas de Tempo RealSistemas de Tempo Real

Processos ConcorrentesProcessos Concorrentes

• 2 Exemplos:– Tarefas separadas– Compartilhando

dados

• Dificuldade de descrever usando

Heartbeat Monitoring System

B[1..4]

Heart-beat

pulse

Task 1:

Read pulse

If pulse < Lo then

Activate Siren

If pulse > Hi then

Activate Siren

Sleep 1 second

Repeat

Task 2:

If B1/B2 pressed then

Lo = Lo +/– 1

If B3/B4 pressed then

Hi = Hi +/– 1

Sleep 500 ms

Repeat


descrever usando programa sequencial

• Modelo como processos concorrente– Cada tarefa é um

programa sequencial– Tarefas se

comunicam

Set-top Box

Input

Signal

Task 1:

Read Signal

Separate Audio/Video

Send Audio to Task 2

Send Video to Task 3

Repeat

Task 2:

Wait on Task 1

Decode/output Audio

Repeat

Task 3:

Wait on Task 1

Decode/output Video

Repeat

Video

Audio

ProcessoProcesso

• Programa sequencial (tipicamente em loop infinito)

• Operações básicas– Criação e término

• Criação: semelhante a chamada de procedimento, mas quem chama não espera

• A operação de término “mata” o processo


• A operação de término “mata” o processo

– Suspensão e resume• Suspensão: coloca o processo em estado de espera salvando estado• Resume: reativa o processo que executa a partir de onde tinha

parado

– Join• Um processo é suspenso até que um processo filho tenha terminado

sua execução

Comunicação entre processosComunicação entre processos

• Processos necessitam de receber enviar dados de/para outros processos

• Exemplo básico: produtor/consumidor

processA() {

// Decode packet

// Communicate

packet to B

}

}

Encoded

video packets


produtor/consumidor– Processo A produz dados, Processo

B consome dados produzidos– Ex: A decodifica pacotes de vídeo,

B mostra pacotes decodificados na tela

• Como a comunicação é feita?– Memória Compartilhada– Passagem de Mensagem

void processB() {

// Get packet from A

// Display packet

}

Decoded

video packets

To display

Memória CompartilhadaMemória Compartilhada• Processos leem e escrevem em

variáveis compartilhada– Fácil implementação

– Difícil de utilizar• Exemplo: Produtor/Consumidor com erro

– Compartilham buffer[N], count– ProcessA produz dados e armazena no buffer

01: data_type buffer[N];

02: int count = 0;

03: void processA() {

04: int i;

05: while( 1 ) {

06: produce(&data);

07: while( count == N );/*loop*/

08: buffer[i] = data;

09: i = (i + 1) % N;

10: count = count + 1;

11: }

12: }

13: void processB() {


– ProcessA produz dados e armazena no buffer• Se buffer está cheio deve esperar

– processB consome dados do buffer• Se buffer estiver vazio deve esperar

– Erro quando os processos tentam atualizar o contador (linhas 10 e 19) e a seguinte sequencia ocorre

– Considere que “count” é 3.• A carrega count (count = 3) no registrador R1 (R1 = 3)• A incrementa R1 (R1 = 4)• B carrega (count = 3) no registrador R2 (R2 = 3)• B decrementa R2 (R2 = 2)• A armazena R1 na memória na variável (count = 4)• B armazena R2 na memória na variável count (count = 2)

– count tem um valor incorreto


14: int i;

15: while( 1 ) {

16: while( count == 0 );/*loop*/

17: data = buffer[i];

18: i = (i + 1) % N;

19: count = count - 1;

20: consume(&data);

21: }

22: }

23: void main() {

24: create_process(processA);

25: create_process(processB);

26: }

Passagem de MensagemPassagem de Mensagem

• Envio de dado de forma explícita de um processo para o outro– Operações

• Send• Receive

– Operações devem explicitar o processo para onde se está enviando dados ou o

void processA() {

while( 1 ) {

produce(&data)

send(B, &data);

/* region 1 */

receive(B, &data);

consume(&data);

}

}


– Operações devem explicitar o processo para onde se está enviando dados ou o processo do qual se está recebendo dados

• Receive é bloqueante, send pode ser bloqueante ou não

– Modelo seguro, mas com pouca flexibilidade

void processB() {

while( 1 ) {

receive(A, &data);

transform(&data)

send(A, &data);

/* region 2 */

}

}

Memória Compartilhada: Exclusão Memória Compartilhada: Exclusão MútuaMútua• Algumas partes do código não podem ser executadas de forma

concorrente– Região Crítica

• Região do código onde as variáveis compartilhadas são lidas ou escritas

• Quando um processo começa a executar código da região crítica, todos os outros processos deveriam esperar até que o


• Quando um processo começa a executar código da região crítica, todos os outros processos deveriam esperar até que o processo saia da região crítica– Mutex

• Um objeto compartilhado usado para bloquear ou desbloquear a entrada na região crítica

• Desabilita o acesso de leitura/escrita no endereço que ele guarda• Vários processos podem tentar dar lock simultaneamente mas

apenas UM consegue sucesso• Os demais processos ficam bloqueados até que a operação de unlock

seja realizada pelo processo na região crítica• Os processos competirão novamente para entrar na região crítica

Solução correta para o Solução correta para o Produtor/ConsumidorProdutor/Consumidor

• Uso da variável count_mutex do tipo mutex

• Sequencia de execução– A/B executam operação de lock em count_mutex– Ou A ou B terão sucesso

• Vamos considerar que B conseguiu o lock• A é bloqueado

– B lê count (count = 3) no registrador R2 (R2 = 3)


02: int count = 0;

03: mutex count_mutex;


05: int i;

06: while( 1 ) {

07: produce(&data);

08: while( count == N );/*loop*/


10: i = (i + 1) % N;

11: count_mutex.lock();


13: count_mutex.unlock();


– B lê count (count = 3) no registrador R2 (R2 = 3)– B decrementa R2 (R2 = 2)– B escreve R2 back na memória (count = 2)– B executa operação de unlock

• A volta para o estado de execução– A carrega (count = 2) no registrador R1 (R1 = 2)– A incrementa R1 (R1 = 3)– A escreve count na memória (count = 3)

• Count tem o valor correto: 3


14: }

15: }


17: int i;

18: while( 1 ) {

19: while( count == 0 );/*loop*/


21: i = (i + 1) % N;

22: count_mutex.lock();



25: consume(&data);

26: }

27: }

28: void main() {

29: create_process(processA);

30: create_process(processB);

31: }

Um Problema em Programação Um Problema em Programação Concorrente: DeadlockConcorrente: Deadlock

• Deadlock: condição em que 2 ou mais processos são bloqueados um esperando pelo outro liberar a região crítica

• Exemplo com 2 regiões críticas que podem ser acessadas simultaneamente

– 2 locks (mutex1, mutex2)– Sequencia que produz deadlock

01: mutex mutex1, mutex2;02: void processA() {03: while( 1 ) {04: …05: mutex1.lock();06: /* critical section 1 */07: mutex2.lock();08: /* critical section 2 */09: mutex2.unlock();10: /* critical section 1 */11: mutex1.unlock();


• A executa operação de lock em mutex1• B executa operação de lock em mutex2• A/B executam em regiões críticas 1 e 2• A executa operação de lock em mutex2

(bloqueado)• B executa operação de lock em mutex1

(bloqueado)• DEADLOCK!

• Solução: locking em ordem crescente e em duas fases

11: mutex1.unlock();12: }13: }14: void processB() {15: while( 1 ) {16: …17: mutex2.lock();18: /* critical section 2 */19: mutex1.lock();20: /* critical section 1 */ 21: mutex1.unlock();22: /* critical section 2 */23: mutex2.unlock();24: }25: }

Sincronização entre processos Sincronização entre processos

• Em algumas situação processos concorrentes devem sincronizar durante sua execução– Quando um processo deve esperar:

• Outro processo para calcular algum valor• Atinge um determinado ponto de sua execução• Espera por algum sinal condicional


• Espera por algum sinal condicional

• No exemplo do Produtor/Consumidor– processA deve esperar se buffer está cheio– processB deve esperar se buffer está vazio– Técnica: busy-waiting

• Processo executa loop em vez de ser bloqueado• Gasto de tempo

Sincronização entre processos Sincronização entre processos

• Métodos mais eficientes:– Operações de join, blocking send e receive

– Variáveis condicionais e monitores


Variáveis de CondiçãoVariáveis de Condição

• Variável de Condição: objeto com duas operações : signal e wait

• Quando um processo executa um wait na variável, o processo é bloqueado até que outro processo execute um signal na mesma variável


execute um signal na mesma variável

ProdutorProdutor--Consumidor com Consumidor com variáveis de condiçãovariáveis de condição

• 2 variáveis de condição:– buffer_empty

• Sinaliza a existencia de pelo menos uma posição livre no buffer

– buffer_full• Sinaliza a existencia de pelo menos 1

dado no buffer

• processA: – produz dado

01: data_type buffer[N];02: int count = 0;03: mutex cs_mutex;04: condition buffer_empty, buffer_full;06: void processA() {07: int i;08: while( 1 ) {09: produce(&data);10: cs_mutex.lock();11: if( count == N ) buffer_empty.wait(cs_mutex);13: buffer[i] = data;14: i = (i + 1) % N;15: count = count + 1;

Consumer-producer using condition variables


– produz dado– Ativa lock (cs_mutex) para região crítica– Verifica valor de count– Se count = N, buffer está cheio

• executa wait em buffer_empty• Isto libera o lock em cs_mutex

permitindo processo B entrar na região crítica e consumir algum dado

• processB executa signal– Se count < N, buffer não está cheio

• processA insere dado no buffer• incrementa count• Executa signal o que pode tornar

processo B ativo se ele havia feito um wait em buffer_full

15: count = count + 1;16: cs_mutex.unlock();17: buffer_full.signal();18: }19: }20: void processB() {21: int i;22: while( 1 ) {23: cs_mutex.lock();24: if( count == 0 ) buffer_full.wait(cs_mutex);26: data = buffer[i];27: i = (i + 1) % N;28: count = count - 1;29: cs_mutex.unlock();30: buffer_empty.signal();31: consume(&data);32: }33: }34: void main() {35: create_process(processA); create_process(processB);37: }

MonitoresMonitores• Conjunto de dados e métodos

• Só um processo por vez pode estar executando um dos métodos associados a um monitor.

• (a) Processo X executa enquanto Processo Y está esperando

• (b) Processo X executa wait em uma condição Proces

Monitor

DATA

CODE

Proces Proces

Monitor

DATA

CODE

Proces

Waiting


condição

– Processo Y pode entrar e executar

• (c) Processo Y executa signal em condição que o Processo X está esperando

– Processo Y é bloqueado

– Processo X continua a executar

• (d) Processo X termina execução em um monitor or espera por nova condição

– Processo Y pode ser executado novamente

Proces

s X

(a)

Proces

s YProces

s X(b)

Proces

s Y

Proces

s X

Monitor

DATA

CODE

(c)

Proces

s YProces

s X

Monitor

DATA

CODE

(d)

Proces

s Y

Waiting

ProdutorProdutor--Consumidor com Consumidor com monitoresmonitores

• Um monitor inclui processos buffere count

• Um processo poderá iniciar a execução

• Se processB executar primeiro:– Irá executar até que count = 0– Executrá wait quando buffer_full

01: Monitor {


03: int count = 0;

04: condition buffer_full, condition buffer_empty;


07: int i;

08: while( 1 ) {

09: produce(&data);

10: if( count == N ) buffer_empty.wait();


13: i = (i + 1) % N;


15: buffer_full.signal();


– Executrá wait quando buffer_full– processA agora poderá entrar no

monitor e executar

– processA produz dado

– como count < N escreve no buffer e incrementa count

– processA executa signal em buffer_full

– processA é bloqueado

– processB entra novamente no monitor e continua sua execução


16: }

17: }


19: int i;

20: while( 1 ) {

21: if( count == 0 ) buffer_full.wait();


24: i = (i + 1) % N;


26: buffer_empty.signal();

27: consume(&data);


29: }

30: }

31: } /* end monitor */

32: void main() {

33: create_process(processA); create_process(processB);

35: }

ImplementaçãoImplementação

• Mapeamento das funcionalidades do sistema nos processadores– Capturado usando modelo

computacional– Especificado em alguma

linguagem

The choice of

computational

model(s) is based

on whether it

allows the designer

to describe the

system.

The choice of

Sequent.

program

State

machine

Data-

flow

Concurrent

processes


linguagem

• Implementação independente de linguagem

• Implementação baseada em : potência, tamanho, desempenho, custo, etc…

• Implementação final deve ser analisada

The choice of

language(s) is

based on whether

it captures the

computational

model(s) used by

the designer.

The choice of

implementation is

based on whether it

meets power, size,

performance and

cost requirements.

C/C++Pascal Java VHDL

Implementation A Implementation

B

Implementation

C

Processos concorrentes: modelo Processos concorrentes: modelo de implementação de implementação

• Pode usar um ou mais processadores

• (a) Multiplos processadores: cada um executa um processo

– Multitarefa verdadeira

– Processadores de propósito geral

– Processadores de aplicação específica

Process1

Process2

Process3

Process4

Processor A

Processor B

Processor C

Processor D Co

mm

unic

atio

n B

us

(a)

Process1

Process2General Purpose


– Processadores de aplicação específica

• (b) Um processador de propósito geral executando todos os processos

– Compartilhamento de recursos

• (c) Combinação de (a) e (b)– Multiplos processos executando em

processador de propósito geral enquanto um processo executa em um processador de aplicação específica.

(b)

Process2

Process3

Process4

General Purpose

Processor

Process1

Process2

Process3

Process4

Processor A

General

Purpose

Processor

Co

mm

unic

atio

n B

us

(c)

Suportando processos concorrentesSuportando processos concorrentes

• Necessário quando se tem vários processos compartilhando mesmo processador em aplicações de tempo real

• Mecanismo de Suporte– Criaçãoda lista de tarefas ou processos


– Criaçãoda lista de tarefas ou processos– Inicialização dos processos– Escalonamento dos processos

• Preemptiva ou não preemptiva• Estática ou dinâmica• Informações dos processos: tempo execução, deadline,

período, prioridade

– Uso de SO ou Escalonador

ResumoResumo

• Modelos computacionais são diferentes de linguagens

• Modelo de programa sequencial é bastante popular

• Modelo baseado em FSM´s são bons para controle


• Modelo de processos concorrentes para sistemas multi-tarefas– Métodos para comunicação e sincronização– Escalonamento é crítico

• Modelo de Dataflow adequado para processamento de sinal.

Documents

Arquitetura de Sistemas Embarcadosensb/pub/apse/design-tech-ensb-cap8-11...Embarcados – Pode ser extremamente difícil • Complexidade crescente com a crescente capacidade dos IC´s