DETI - UFCSistema em Tempo Real Jarbas Silveira
Sistemas em Tempo Real
Módulo 2: Concorrência: Conceito de processos; estados de processos; algoritmos para escalonamento de processos; Regiões Críticas; Exclusão Mútua; Comunicação e sincronização de processos (semáforos, monitores, passagem de mensagens); Deadlocks.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
-Definição de tarefa (processo, actividade)
Seqüência de ativações (instâncias ou jobs), cada uma composta por um conjunto de instruções que, na ausência de outras atividades, é executada pelo CPU sem interrupção.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
Quanto à periodicidade as tarefas podem ser
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
Caracterização das Tarefas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
Os requisitos das tarefas podem ser:
• Temporais – limites temporais aos instantes de terminação ou degeração de determinados eventos de saída.
• Precedência – estabelecem uma determinada ordem de execuçãoentre tarefas.
• Uso de recursos – necessidade de utilização de recursos partilhados(e.g. portos de comunicação, um buffer em memória partilhada,variáveis globais, periféricos do sistema). Pode implicar uso deoperações atômicas (cuja seqüência não pode ser interrompida)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
Preempção
• Quando uma tarefa pode ser interrompida temporariamente paraexecução de outra mais prioritária, diz-se que admite preempção.• Quando um sistema utiliza a propriedade de preempção das tarefasque executa diz-se preemptivo.• Um conjunto de tarefas diz-se admitir preempção total quando todas as tarefas admitem preempção em qualquer ponto da sua execução (tarefas independentes)
Nota: o acesso a recursos partilhados (tarefas com dependências) pode impor restrições sobre o grau de preempção que uma tarefa admite.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
Os requisitos temporais podem ser de vários tipos:
• Deadline – Limitação ao tempo máximo para terminação da tarefa.• Janela – Delimitação máxima e mínima ao instante de terminação.• Sincronismo – Limitação à diferença temporal entre a geração de dois eventos de saídas (existem outras formas).• Distância – Limitação ao atraso (distância) entre a terminação, ou activação, de duas instâncias consecutivas(e.g., a mudança do óleo do motor num carro)
Tipo deadline é o mais comum!
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Conceito de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Estados de Processos
Criação de uma tarefa
associação do código (e.g. C function) a um espaço devariáveis privado (private stack) e a uma estrutura de gestão (task control block – TCB);
Execução de uma tarefa
Execução concorrente do código da tarefa, usando orespectivo espaço privado de variáveis, sob controlo dokernel, com reactivação de cada instância periodicamente ou como resposta a um evento externo.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Estados de Processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Estados de Processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Estados de Processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Estados de Processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
•Um escalonamento diz-se praticável (feasible schedule) se cumpre as restrições associadas ao conjunto de tarefas (temporais, não preempção, recursos partilhados, precedências)
•Um conjunto de tarefas diz-se escalonável (schedulable task set) se existe pelo menos um escalonamento praticável para esse conjunto.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
- Escalonamento de tarefas periódicas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
- Escalonamento estático cíclico
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
-Escalonamento estático cíclico
A favor•Implementação simples (timer+tabela)•Overhead de execução muito baixo (dispatcher)•Permite optimização do escalonamento(e.g. controlo de jitter, relações de precedência)Contra•Pouco escalável (alterações nas tarefas podem causar grandes alterações na tabela, em particular podem levar a tabelas enormes!)•Pouco robusto a sobrecargas (sensível ao efeito dominó)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
-Escalonamento estático cíclico
Construção da tabela•Calcular o micro-ciclo uC e o macro-ciclo MC•Expressar os períodos e fases iniciais em micro-ciclos•Determinar os ciclos onde as tarefas são ativadas•Utilizando um critério de escalonamento adequado, determinar a ordem de execução das tarefas ativas •Verificar se todas as tarefas ativas num micro-ciclo podem sercompletamente executadas nele. Senão algumas terão que ficarpara ciclos seguintes•Poderá ser necessário partir uma tarefa em várias partes de modo a cada uma poder ser executada dentro de um micro-ciclo.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento preemptivo com prioridade fixa
Todas tarefas têm uma prioridade fixa, que não é alterada a menos que a aplicação modifique-a. Uma tarefa com prioridade mais alta interrompe uma tarefa com prioridade inferior. A maioria dos sistemas operacionais Tempo Real suportam este esquema.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
- Escalonamento on-line com prioridades fixas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
- Escalonamento on-line com prioridades fixas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
- Escalonamento on-line com prioridades fixas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
- Escalonamento on-line com prioridades fixas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento preemptivo com prioridade dinâmica
Uma tarefa com prioridade mais alta interrompe uma tarefa com prioridade inferior. A prioridade de uma tarefa pode mudar de uma instância a outra ou durante a execução de uma instância para atender um objetivo específico de resposta temporal. Poucos sistemas operacionais comerciais de Tempo Real suportam esta política.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento rate-monotonic
Política de escalonamento preemptivo ótimo de prioridade fixa no qual quanto mais alta a freqüência de ativação de uma tarefa periódica, maior a prioridade. Assume que o deadline de uma tarefa periódica é igual ao seu período. Pode ser implementado em qualquer sistema operacional que suporta escalonamento preemptivo com prioridade fixa ou generalizado para tarefas aperiódicas.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento RM – exemplo 1
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento RM – exemplo 2
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento RM – exemplo 3
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento deadline-monotonic
Generalização da política de escalonamento rate-monotonic, no qual o deadline de uma tarefa é um ponto fixo no tempo, relativo ao início do período. Quanto mais próximo este deadline (fixo) maior a prioridade. Quando o tempo do deadline iguala o período esta política é idêntica ao esquema de escalonamento ratemonotonic.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento earliest-deadline-first
Política de escalonamento preemptivo com prioridade dinâmica. O deadline da instância de uma tarefa é o ponto absoluto no tempo no qual a instância tem que concluir. O deadline é computado quando a instância é criada. O escalonador escolhe a tarefa com o deadline mais próximo para executar primeiro. Uma tarefa com um deadline mais próximo interrompe uma tarefa com um deadline posterior. Esta política minimiza o atraso máximo de um conjunto de tarefas, em relação a todas as outras políticas deescalonamento.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Escalonamento de processos
Escalonamento least-laxity-first (least slack)
Política de escalonamento não preemptivo com prioridadedinâmica. A folga ou relaxação da instância de uma tarefa é o deadline absoluto para conclusão menos o restante do pior caso do tempo de execução da instância da tarefa. O escalonador escolhe a tarefa com a menor relaxação para executar primeiro. Uma tarefa com um deadline mais próximo interrompe uma tarefa com umdeadline posterior. Esta política maximiza o atraso mínimo de um conjunto de tarefas.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Acesso exclusivo a recursos partilhados
-O acesso exclusivo a recursos partilhados
-A inversão de prioridades como conseqüência do bloqueio
-Técnicas básicas para acesso exclusivo a recursos partilhados
-Herança de prioridades (Priority Inheritance Protocol – PIP)
-Protocolo de tecto de prioridades (Priority Ceiling Protocol – PCP)
- Protocolo de pilha de recursos (Stack Resource Protocol- SRP)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
O fenômeno da inversão de prioridades
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
O fenômeno da inversão de prioridades
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Técnicas para acesso exclusivo a recursos
Primitivas de sincronização• Inibição de interrupções (disable / enable ou cli / sti)• Inibição de preempção (no_preemp / preempt)• Utilização de locks ou flags atómicas (mutexes – se bem queeste termo por vezes também é usado para designar semáforos –lock / unlock)• Utilização de semáforos (contador+lista – P / V ou wait / signal)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Protocolo de Herança de Prioridades (PIP – Priority Inheritance Protocol)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Protocolo de Herança de Prioridades (PIP – Priority Inheritance Protocol)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Protocolo de Herança de Prioridades (PIP – Priority Inheritance Protocol)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Protocolo de Teto de Prioridades (PCP – Priority Ceiling Protocol)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Protocolo de Teto de Prioridades (PCP – Priority Ceiling Protocol)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Protocolo de Teto de Prioridades (PCP – Priority Ceiling Protocol)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Política de Pilha de Recursos (SRP – Stack Resource Policy)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Política de Pilha de Recursos (SRP – Stack Resource Policy)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Regiões Críticas
Política de Pilha de Recursos (SRP – Stack Resource Policy)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Semáforos
São objetos de Kernel que uma ou mais threads podem adquirir ou liberar com o propósito de sincronização ou exclusão mútua.
-SCB (Semaphore Control Block)-ID Semaphore-Binário ou do tipo contador
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
- Semáforo e sua estrutura de dados
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Semáforos binários
- Podem ter valor 0 (não disponível) ou 1(disponível);- São utilizados como recursos globais
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Semáforos do tipo contadores
- Usa um contador para ser adquirido ou liberado múltiplas vezes;- Semáforo é criado com 0 (não disponível)- Quando adquirido contagem inicia;- Uma ou mais tarefas podem adquirir fichas do semáforo;- Algumas implementações permitem limitar o número de fichas.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
- Diagrama de estados de um semáforo contador
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Semáforos de Mútua Exclusão (Mutex)
- Um mutex é um semáforo binário especial que suporta um Proprietário, acesso recursivo e proteção segura de tarefas;
- Um proprietário de um mutex é assinalado quando o mesmo é travado na primeira vez que é adquirido;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
- Semáforos de Mútua Exclusão (Mutex)
- Muitos Mutex implementam recursividade, permitindo que o proprietário deste mutex possa adquiri-lo múltiplas vezes;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Semáforos de Mútua Exclusão (Mutex)
- Esta propriedade permite a proteção contra deleção da tarefa enquanto o semáforo encontra-se travado;
- Mudanda de prioridade: os protocolos PIP e CPP são utilizados em alguns semáforos;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Aplicações típicas de semáforos
- Wait and Signal Syncronization: tem o propósito de coordenar ações entre 2 tarefas;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Multiple-task Wait and Signal Synchronization
- Quando uma ou mais tarefas esperam por um tarefa para iniciarem suas execuções;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Credit-Tracking Synchronization
-Quando a taxa de produção e consumo são diferentes, podemos utilizar semáforos contadores para sincronizar estas tarefas;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Acesso exclusivo a uma região compartilhada
- Um dos usos mais comuns de semáforos;- Um semáforo binário controla o acesso a região compartilhada;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Acesso exclusivo recursivo a uma região compartilhada
- Necessário quando uma tarefa deseja acessar uma região crítica e uma das tarefas desta atividade também necessita acessar esta mesma região crítica;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Exclusão Mútua
-Sincronização de múltiplas recursos compartilhados
- Nesta situação, onde múltiplos recursos precisam ser compartilhados é recomendado o uso de um semáforo do tipo contador;
DETI - UFCSistema em Tempo Real Jarbas Silveira
Sincronização de Processos
Mensagens entre processos
- Um fila de mensagens é um buffer onde processos podem transmitir e receber mensagens.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Estados de Fila de Mensagens
DETI - UFCSistema em Tempo Real Jarbas Silveira
- Algumas implementações de Kernel permitem mover blocos de mensagens para listas de espera em memória;
Comunicação e sincronização de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
-Armazenamento de Filas de Mensagens
- Systems Pools: Área única de memória
- Private Buffers: Áreas separadas de memória
Comunicação e sincronização de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
-Operações típicas de Filas de mensagens (TX)
- First-in, First-out (FIFO)
Comunicação e sincronização de processos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Operações típicas de Filas de mensagens (TX)
- First-in, First-out (LIFO)
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Operações típicas de Filas de mensagens (RX)
- Recepção de mensagens com prioridade
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Uso típico de fila de mensagens
- Sem inter-travamento, em um sentido de comunicação
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Uso típico de fila de mensagens
- Com inter-travamento, em um sentido de comunicação
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Uso típico de fila de mensagens
- Sem inter-travamento, em duplo sentido de comunicação
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Uso típico de fila de mensagens
- Comunicação em broadcast
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
- Outros objetos de Kernel: PIPES- Não estruturados- Não permite prioridade- Stream de bytes
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Outros objetos de Kernel: PIPES
- Pipe Control Blocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Outros objetos de Kernel: PIPES
- Estados de um PIPE
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Uso típico de PIPES:
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Outros objetos de Kernel:
- Registradores de Eventos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Uso típico de registradores de eventos:- Sincronização unidirecional de tarefas
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
-Signals:- São interrupções de software que são
gerados quando um determinado evento ocorre.
DETI - UFCSistema em Tempo Real Jarbas Silveira
Comunicação e sincronização de processos
- Uso típico de Sinais: capturador de eventos
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks
DETI - UFCSistema em Tempo Real Jarbas Silveira
Deadlocks