View
0
Download
0
Category
Preview:
Citation preview
Arquitetura de Arquitetura de Sistemas EmbarcadosSistemas EmbarcadosEdna Barros (ensb@cin.ufpe.br)Edna Barros (ensb@cin.ufpe.br)
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
Engenharia de Sistemas Embarcados 4
– 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
Engenharia de Sistemas Embarcados 5
• 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
Engenharia de Sistemas Embarcados 6
– 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.
Engenharia de Sistemas Embarcados 7
• 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
Engenharia de Sistemas Embarcados 8
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
Engenharia de Sistemas Embarcados 9
• 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;
Engenharia de Sistemas Embarcados 10
when moving down…”inside
elevator...
...
up/down
buttons on
each
floor
b2
bN
up1
up2
dn2
dnN
up3
dn3
up = down = 0; open = 1;
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
Engenharia de Sistemas Embarcados 11
• 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
Engenharia de Sistemas Embarcados 12
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)
Engenharia de Sistemas Embarcados 13
– 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 }
Engenharia de Sistemas Embarcados 14
– 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
Engenharia de Sistemas Embarcados 15
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
Engenharia de Sistemas Embarcados 16
• 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
Engenharia de Sistemas Embarcados 17
– 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;}
Engenharia de Sistemas Embarcados 18
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 = GOINGUP;}
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*/
}
Engenharia de Sistemas Embarcados 19
}
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
Engenharia de Sistemas Embarcados 20
• 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!
Engenharia de Sistemas Embarcados 21
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
up = down = 0; open = 1;
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;
Engenharia de Sistemas Embarcados 22
– 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 ) {
Engenharia de Sistemas Embarcados 23
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)
Hello world. (Time = 2 s)
How are you? (Time = 2 s)
Hello world. (Time = 3 s)
How are you? (Time = 4 s)
Hello world. (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)
Engenharia de Sistemas Embarcados 24
• 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
Engenharia de Sistemas Embarcados 25
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
Engenharia de Sistemas Embarcados 26
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
Engenharia de Sistemas Embarcados 27
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
Engenharia de Sistemas Embarcados 28
• 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
Engenharia de Sistemas Embarcados 29
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() {
Engenharia de Sistemas Embarcados 30
– 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
13: void processB() {
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);
}
}
Engenharia de Sistemas Embarcados 31
– 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
Engenharia de Sistemas Embarcados 32
• 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)
01: data_type buffer[N];
02: int count = 0;
03: mutex count_mutex;
04: void processA() {
05: int i;
06: while( 1 ) {
07: produce(&data);
08: while( count == N );/*loop*/
09: buffer[i] = data;
10: i = (i + 1) % N;
11: count_mutex.lock();
12: count = count + 1;
13: count_mutex.unlock();
Engenharia de Sistemas Embarcados 33
– 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
13: count_mutex.unlock();
14: }
15: }
16: void processB() {
17: int i;
18: while( 1 ) {
19: while( count == 0 );/*loop*/
20: data = buffer[i];
21: i = (i + 1) % N;
22: count_mutex.lock();
23: count = count - 1;
24: count_mutex.unlock();
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();
Engenharia de Sistemas Embarcados 34
• 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
Engenharia de Sistemas Embarcados 35
• 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
Engenharia de Sistemas Embarcados 36
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
Engenharia de Sistemas Embarcados 37
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
Engenharia de Sistemas Embarcados 38
– 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
Engenharia de Sistemas Embarcados 39
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 {
02: data_type buffer[N];
03: int count = 0;
04: condition buffer_full, condition buffer_empty;
06: void processA() {
07: int i;
08: while( 1 ) {
09: produce(&data);
10: if( count == N ) buffer_empty.wait();
12: buffer[i] = data;
13: i = (i + 1) % N;
14: count = count + 1;
15: buffer_full.signal();
Engenharia de Sistemas Embarcados 40
– 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
15: buffer_full.signal();
16: }
17: }
18: void processB() {
19: int i;
20: while( 1 ) {
21: if( count == 0 ) buffer_full.wait();
23: data = buffer[i];
24: i = (i + 1) % N;
25: count = count - 1;
26: buffer_empty.signal();
27: consume(&data);
28: buffer_full.signal();
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
Engenharia de Sistemas Embarcados 41
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
Engenharia de Sistemas Embarcados 42
– 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
Engenharia de Sistemas Embarcados 43
– 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
Engenharia de Sistemas Embarcados 44
• 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.
Recommended