1.7 Exercícios

1) Liste três aplicações de software que podem ser claramente identificadas como apresentando requisitos de tempo real (exemplo: piloto automático do avião).

2) Liste três aplicações de software que podem ser claramente identificadas como não apresentando requisitos de tempo real (exemplo: folha de pagamento).

3) Liste três aplicações de software que geram dúvida sobre apresentarem ou não requisitos de tempo real (exemplo: caixa automático no banco).

4) Considerando videogames, podemos considerar o Sid Meier's Civilization como uma aplicação de tempo real? E o Battlefield 1942? Justifique sua resposta.

5) O que você responderia caso alguém perguntasse: “afinal, o que é um sistema de tempo real”?

6) Identifique um requisito de tempo real que existe em sua vida, pode ser periódico ou eventual.

2.11 Exercícios

1) Descreva exemplos de tarefas com deadline hard, deadline firm e deadline soft.

2) Procure identificar no Sistema de Defesa Anti-Míssil descrito na seção 1.6 as propriedades temporais listadas na seção 2.10, quando as mesmas são fornecidas.

3) Os horários das aulas na faculdade representam uma forma de escalonamento de horários para alunos e professores. Trata-se de um escalonamento dinâmico ou estático ? Justifique.

4) Qual a diferença entre tarefa aperiódica e tarefa esporádica ?

5) Considerando suas atividades pessoais do dia a dia, identifique atividades periódicas, esporádicas e aperiódicas.

6) Suponha que você está em Blumenau-SC e tem uma prova as 16:00 em Florianópolis-SC. Quanto tempo leva para ir de carro de uma cidade a outra em uma situação típica ? Quanto tempo a viagem leva no pior caso ? E no melhor caso ? Suponha que é uma prova muito importante, quanto tempo você vai sair de casa antes ? Quais as vantagens e desvantagens de sair com maior ou menor antecedência ?

Obs: Substitua Blumenau e Florianópolis por cidades do seu estado.

7) Descubra como medir o tempo total de resposta de um programa em sua plataforma de trabalho usual. Por exemplo, no Linux é possível usar o comando “time” na inteface de console (“bash”). Meça este tempo para algum programa várias vezes. Neste caso, o tempo variou ?

8) Os conceitos de “tarefa”, “tempo de execução” e “tempo de resposta” são fundamentais para os sistemas de tempo real. Eles foram definidos aqui de forma um pouco diferente daquela encontrada nas conversas do dia. Para cada um destes três termos, compare a definição usada aqui com a definição que você conhecia antes.

9) Suponha que uma tarefa precise 50ms de tempo de processador para executar, e um deadline relativo de 200ms. Entretanto, durante sua execução, outras tarefas ocupam o processador por 120ms. Esta tarefa vai cumprir o seu requisito temporal ? Qual o seu tempo de resposta ?

10) Uma tarefa periódica é criada em t=1000s e tem um período de 3s. Quais os instantes de tempo de suas primeiras três chegadas ?

11) Uma tarefa demanda 50ms de tempo de processador para executar, possui um deadline relativo de 200ms, porém o sistema operacional demora 20ms entre a sinalização da chegada da tarefa através de uma interrupção de periférico e sua inclusão na lista de tarefas aptas a executar. Qual a folga desta tarefa ?

12) Considerando uma tarefa periódica τk descrita por (Jk=4, Ck=3, Pk=10, Dk=8), determine os valores absolutos para a terceira ativação da tarefa: instante de chegada, instante de liberação, deadline absoluto e um limite inferior para o tempo de resposta no pior caso.

3.6 Exercícios

1) Tente montar uma solução de escalonamento do tipo executivo cíclico para o sistema composto pelas quatro tarefas abaixo. Construa um digrama de tempo como aquele apresentado na figura 3.1.

 

T1:       C1=1               P1=5               D1=5

T2:       C2=2               P2=6               D2=6

T3:       C3=2               P3=10             D3=10

T4:       C3=3               P3=15             D3=15

2) Faça o mesmo para o seguinte sistema com três tarefas:

 

T1:       C1=3               P1=10             D1=10

T2:       C2=3               P2=15             D2=15

T3:       C3=15             P3=30             D3=30

3) Faça o mesmo para o seguinte sistema com quatro tarefas:

 

T1:       C1=2               P1=8               D1=8

T2:       C2=8               P2=16             D2=16

T3:       C3=4               P3=24             D3=24

T4:       C4=4               P4=48             D4=48

4) Cite alguns fatores que orientam a definição do ciclo menor na construção da grade de tempo de um executivo cíclico ?

5) Cite uma vantagem e uma desvantagem da implementação de tarefas através de executivo cíclico em relação à implementação através de threads em microkernel.

6) Suponha uma tarefa esporádica com tempo de execução de 20ms, intervalo mínimo de tempo entre chegadas de 30ms e deadline relativo também 30ms. Qual o percentual de tempo do processador será necessário reservar para atender esta tarefa ? Qual o percentual de tempo do processador mínimo e máximo que esta tarefa pode efetivamente utilizar ?

7) Quando uma tarefa de tempo real é implementada como um tratador de interrupção em uma solução do tipo laço principal com tratadores de interrupções, qual o pior cenário possível no que diz respeito ao seu tempo de resposta ?

8) Tipicamente, na ocorrência de uma interrupção, os processadores automaticamente desabilitam interrupções, para permitir que o tratador da interrupção execute de forma segura. Entretanto, a maioria dos sistemas operacionais torna a habilitar interrupções tão logo quanto possível, mesmo não tendo ainda terminado a execução de todas as ações desencadeadas pela ocorrência da interrupção sendo tratada. Ilustre através de exemplo uma potencial desvantagem de manter as interrupções desabilitadas além do estritamente necessário.

9) Qual dos itens abaixo NÃO é uma razão para implementar chamadas de sistema como interrupções de software.

(a) É possível evitar chamadas de sistema desabilitando as interrupções.

(b) A aplicação não precisa conhecer os endereços das rotinas do microkernel.

(c) No ativamento de um tratador de interrupções as interrupções são automaticamente

desabilitadas.

10) É possível usar a própria pilha de execução da thread para salvar seu contexto de execução, através de uma sequência de instruções do tipo PUSH ? Comente as vantagens e desvantagens de tal solução. Considere aspectos tais como:

- Espaço na pilha da thread para salvar o conteúdo dos registradores;

- Viabilidade de salvar todos os registradores do processador na pilha da thread (pense no stack pointer);

- Regras para uso da pilha por parte da própria thread.

11) Descreva de forma sucinta o que é necessário fazer para criar uma nova thread dentro do microkernel, ou seja, quais as ações do microkernel para atender uma chamada de sistema que solicita a criação de uma nova thread ? Alocar bloco descritor livre, preencher os campos, inserir na fila de aptos.

12) Considere um microkernel simples, que executa com interrupções desabilitadas, implementa multiprogramação e algumas poucas chamadas de sistema. Esboce, através de um fluxograma, o comportamento deste microkernel na ocorrência de interrupção de software (chamada de sistema) e de interrupção de hardware (gerada por periférico). Considere no fluxograma duas chamadas de sistema: sleep (suspende o processo por alguns segundos) e rxchar (recebe um caractere pela porta serial). Apenas dois tipos de interrupções de hardware são possíveis: uma do temporizador em hardware avisando a passagem de 100ms e outra da porta serial avisando a chegada de um caractere.

Descrever o fluxograma supondo a existência das seguintes funções: insere_fila_x, remove_fila_x, salva_contexto, coloca_contexto, seleciona_processo. Supor a existência de quaisquer funções auxiliares necessárias.

4.12 Exercícios

1) Responda as questões com respeito às consequências da multiprogramação, e justifique:

a) Multiprogramação gera uma pior/melhor utilização do processador?

b) Multiprogramação gera uma pior/melhor utilização dos periféricos?

c) Multiprogramação gera uma menor/maior necessidade de memória?

d) Multiprogramação gera uma menor/maior necessidade de hardware para proteção?

2) Quais das operações abaixo devem ser privilegiadas? justifique.

a) Desabilita interrupções.

b) Escreve caractere na interface da impressora.

c) Desliga o temporizador.

3) Em qual das situações abaixo não é necessário ocorrer a passagem do processador de modo usuário para modo supervisor ?

(a) Controlador de disco gera interrupção avisando que comando anterior foi concluído.

(b) Processo faz uma chamada de sistema.

(c) Processo chama uma rotina da biblioteca da linguagem.

(d) Processo executa um opcode que na verdade não existe naquele processador.

(e) Timer gera uma interrupção alertando a passagem de mais 10 ms.

4) Explique quais são as vantagens do processador realizar a passagem de modo usuário para modo supervisor automaticamente com o atendimento de uma interrupção.

5) Explique como o mecanismo de modos de execução do processador, associado com o mecanismo de interrupções, pode impedir que um processo executando código de usuário possa, por exemplo, acessar diretamente o controlador do disco ou qualquer controlador de periférico.

6) Explique os vários mecanismos do kernel que, em conjunto, impedem que um programador coloque um processo de usuário propositadamente em loop infinito para travar a máquina (ele vai tentar todas as possibilidades).

7) Considerando o modo dual de operação dos processadores que oferecem suporte para a proteção entre processos, é ERRADO afirmar que:

(a) A execução de qualquer instrução privilegiada em modo usuário dispara uma interrupção de proteção (exceção).

(b) Quando os registradores dos controladores são mapeados em endereços de memória, a proteção de memória evita o acesso indevido aos periféricos.

(c) Em modo usuário, as interrupções de periféricos podem ser desabilitadas, desde que as interrupções de proteção (exceções) não sejam desabilitadas.

(d) Uma instrução do tipo “passa para modo usuário” não precisa ser privilegiada.

(e) O hardware de proteção pode ser desativado em modo supervisor.

8) Descreva as ações do kernel para atender uma chamada de sistema que solicita a criação de um novo processo, o qual inclui uma única thread.

9) Qual a potencial desvantagem de manter as interrupções desabilitadas além do estritamente necessário, enquanto código do kernel é executado ?

(a) Dispositivos livres ficam parados desnecessariamente.

(b) Pode ocorrer a postergação indefinida de processos com baixa prioridade.

(c) O sistema passa a não contar com a proteção entre processos.

(d) Desabilitar interrupções é uma instrução privilegiada.

10) Qual o impacto potencial de uma interrupção gerada pelo controlador  de disco sobre o estado dos processos no sistema ?

(a) Processo executando pode ser substituído por um processo liberado de mais alta prioridade.

(b) Processo executando pode ficar bloqueado.

(c) Sinaliza o término da fatia de tempo do processo executando.

11) Embora ambos tenham seu escalonamento feito pelo gerenciamento de processos, threads e processos são estruturalmente distintos. Qual é a principal diferença entre eles?

a) Apenas threads podem ser executadas em paralelo.

b) Threads possuem contexto simplificado.

c) Processos executam mais rapidamente.

d) Threads apenas podem ocorrer em processadores multicore.

12) Assim como o processador, outros recursos do computador podem ser gerenciados de tal forma que os mesmos possam ou não possam ser preemptados, isto é, o recurso é retirado temporariamente do processo para que outro ocupe. Discuta a possibilidade de preemptar a memória de um processo. Em que situação isto é desejável ? Como o processo pode ser retomado mais tarde sem inconsistência ?

13) Fragmentação externa é o principal problema das partições variáveis. Entretanto, podem existir atenuantes em um sistema computacional embutido em uma máquina industrial onde são sempre executados os mesmos processos. Em que situações partições variáveis tornam-se menos problemáticas ?

14) Considere um sistema operacional que trabalha com paginação simples. As páginas são de 1Kbyte. O endereço lógico é formado por 16 bits. O endereço físico é formado por 20 bits. Qual o tamanho do:

- Espaço de endereçamento lógico (maior programa possível) ?

- Espaço de endereçamento físico (memória principal) ?

- Entrada da tabela de páginas, sem considerar bits de proteção ?

- Tabela de páginas (número de entradas necessárias no pior caso) ?

15) Qual a fragmentação apresentada pelo método de gerência de memória baseado em partições variáveis ?

16) Qual a fragmentação apresentada pelo método de gerência de memória baseado em paginação ?

17) Como seria possível determinar se uma interrupção de proteção acionada pela MMU é devida a um acesso ilegal à memória ou a uma falta de página? Suponha que a MMU informa o endereço lógico de memória que causou a interrupção de proteção ?

18) Considere um sistema operacional que trabalha com paginação simples. As páginas são de 2Kbytes. O endereço lógico é formado por 20 bits. O endereço físico é formado por 24 bits. Assinale a afirmativa CORRETA:

EEL = Espaço de endereçamento lógico (maior programa possível)

EEF = Espaço de endereçamento físico (memória principal)

NTP = Número de entradas na maior tabela de páginas possível

(a)        EEL = 1Mbytes          EEF = 1Mbytes          NTP = 8K entradas

(b)       EEL = 1Mbytes          EEF = 16Mbytes        NTP = 8K entradas

(c)        EEL = 16Mbytes        EEF = 1Mbytes          NTP = 512 entradas

(d)       EEL = 1Mbytes          EEF = 16Mbytes        NTP = 512 entradas

19) Assinale a opção correta: Na gerência de memória os tamanhos de páginas são sempre potência de 2 pois:

(a) Na computação existe um preferência por trabalhar com potências de dois.

(b) Para que o tamanho das páginas lógicas e das páginas físicas possa ser o mesmo.

(c) Para que o deslocamento ocupe um número inteiro de bits dentro do endereço.

(d) Para que o número de páginas físicas possa ser maior que o número de páginas lógicas.

(e) Para que dois processos possam compartilhar páginas na segmentação paginada.

20) Um dado computador possui MMU que suporta paginação. O espaço de memória física é de 4 Gbytes. O tamanho do endereço lógico é de 30 bits. Os projetistas então em dúvida se devem usar páginas com tamanho de 1Kbyte ou 16Kbytes. Argumente a favor de cada uma das opções, na perspectiva da gerência de memória baseada em paginação pura.

21) Um dado computador possui MMU que suporta paginação. O espaço de memória física é de 4 Gbytes. O tamanho do endereço lógico é de 30 bits. Os projetistas então em dúvida se devem usar páginas com tamanho de 1Kbyte ou 16Kbytes. Qual dos argumentos abaixo, a favor ou contra uma opção, está ERRADO na perspectiva da gerência de memória baseada em paginação.

(a) Páginas menores geram menos fragmentação interna.

(b) Com páginas maiores os processos necessitam tabelas de páginas menores.

(c) No caso de memória virtual, páginas menores são mais eficientes para capturar exatamente a localidade do processo.

(d) Com páginas maiores a cache interna à MMU (TLB) também precisa ser maior.

22) Qual a origem da motivação para colocar um bit de válido/inválido na tabela de páginas?

23) Suponha que não existe o bit de válido/inválido na tabela de páginas, como isto poderia ser contornado, embora gerando ineficiências ? Aponte as ineficiências de sua solução.

24) Em um sistema de paginação, suponha que o espaço de endereçamento lógico é no máximo 4 Gbytes e o tamanho de uma página é 4 Kbytes. Mostre através de um desenho como tabelas de páginas hierárquicas permitem executar um programa pequeno (poucas páginas lógicas) sem gastar memória com uma tabela de páginas completa. Faça o exemplo com 1 processo que precisa apenas de 1 página lógica.

25) Em um sistema de paginação, suponha que o espaço de endereçamento lógico é no máximo de 4 Gbytes e o tamanho de uma página é 4 Kbytes. Cada entrada na tabela de páginas tem 4 bytes. A unidade de alocação de memória é a página. A tabela de páginas completa fica na memória. Analise os problemas decorrentes dos seguintes métodos de alocação de memória para armazenar a tabela de páginas (um problema/desvantagem para cada método):

a) Sempre alocar uma tabela de páginas com tamanho máximo e marcar as entradas não usadas como inválidas.

b) Sempre alocar uma tabela de páginas com o tamanho exato necessário para o processo e colocá-la em uma área de memória contígua.

c) Usar uma tabela de páginas hierárquica (dividida em 2 níveis como visto neste capítulo).

26) Suponha que um computador possua, na sua MPU (memory protection unit), dois conjuntos de registradores limite, os quais são usados para proteger separadamente o código e os dados do processo. No arquivo executável são identificados dois segmentos para o programa, um de código e outro de dados. Discuta as conseqüências deste esquema, considerando os seguintes aspectos:

(a) Fragmentação interna.

(b) Fragmentação externa.

(c) Compartilhamento de código entre processos diferentes.

(d) Possibilidade de implementar memória virtual.

27) Descreva passo a passo o que acontece após uma falta de página.

28) Considerando os sistemas de memória virtual, sobre a relação entre a quantidade de memória física que um processo dispõe e a sua taxa de falta de páginas, assinale verdadeiro ou falso, e justifique:

(a) A taxa de falta de página jamais será zero, não importando quanta memória física o processo disponha.

(b) A taxa de falta de páginas jamais será um, não importando quanta memória física o processo disponha.

(c) A taxa de falta de páginas cresce linearmente com o número de páginas físicas disponíveis.

(d) A taxa de falta de páginas decresce linearmente com o número de páginas físicas disponíveis.

(e) A taxa de falta de páginas decresce de forma proporcional ao quadrado do número de páginas físicas disponíveis.

(f) Após uma certa quantidade de páginas físicas, não é mais possível reduzir a taxa de falta de páginas do processo.

29) Em um dado computador, suponha que o tempo de acesso à memória física seja 100nS, o tempo médio de acesso ao disco seja 10mS e o overhead associado com o atendimento da falta de página (manipulação de tabelas) seja 10uS. Um programa é composto por 100 páginas lógicas e recebe 50 páginas físicas para executar em um sistema com memória virtual. Discuta o impacto da taxa de falta de páginas sobre o tempo efetivo de acesso à memória. Use um exemplo numérico.

30) Um programa escrito em C utiliza as rotinas de biblioteca malloc() e free(), as quais administram uma parte da memória lógica do processo. Malloc(x) serve para o programa alocar uma área contínua de memória com x bytes de tamanho. Free() permite o programa liberar uma área previamente alocada com malloc(). Malloc()/Free() são implementadas pela biblioteca do C.

A parte da memória lógica do processo administrada pelas rotinas da biblioteca malloc()/free() pode ser definida estaticamente (tamanho fixado já no arquivo executável) ou pode ser definida dinamicamente (tamanho do processo é alterado durante a execução através de chamadas de sistema feitas pela biblioteca na medida da necessidade, ou seja, quando é feito um malloc e a biblioteca não tem memória para atende-lo). Discuta quais as implicações dessas duas abordagens (malloc/free administra área alocada estaticamente ou dinamicamente) considerando que o sistema operacional utiliza para a gerência de memória dos processos:

(a) Partições variáveis.

(b) Paginação.

5.7 Exercícios

1) Alguns algoritmos de escalonamento do processador apresentados são preemptivos, outros são não preemptivos, e outros ainda podem ser implementados de uma ou outra forma. Pode-se afirmar que:

(a) Escalonamento baseado em fatia de tempo pode ser implementado de uma ou de outra forma.

(b) Algoritmos preemptivos são mais fiéis aos níveis de prioridade, no caso de escalonamento baseado em prioridades.

(c) Algoritmos não preemptivos geram maior overhead.

(d) Algoritmos não preemptivos tornam impossível a postergação indefinida.

2) Para cada um dos ítens abaixo, indique se trata-se de um problema para a implementação do shortest-job first no escalonamento do processador:

(a) É necessário conhecer a duração do próximo ciclo de processamento das threads.

(b) É possível a ocorrência de postergação indefinida no caso de uma thread com ciclo de processamento muito longo.

(c) É necessário manter a fila ordenada conforme a duração do próximo ciclo de processamento e o número de threads pode chegar à casa de centenas em alguns sistemas.

(d) É impossível adaptar este algoritmo para multiprocessadores.

3) Considere um sistema hipotético onde todas as threads apresentam ciclos de processamento com duração exatamente de 10ms (50% dos ciclos), 30ms (40% dos ciclos) ou 100ms (10% dos ciclos). Eles aparecem alternados na fila do processador. O tempo para chaveamento de contexto é de 1ms. Ignore os demais overhead do sistema. O escalonamento será feito com fatias de tempo. Do ponto de vista do escalonamento, está ERRADO afirmar que:

(a) Uma fatia de tempo de 10mS tem a vantagem de fornecer uma boa ilusão de paralelismo na execução das threads.

(b) Após certo valor a fatia de tempo transforma o algoritmo de escalonamento em FCFS (FIFO).

(c) Uma fatia de tempo de 100 ms vai gerar baixo overhead por chaveamento de contexto.

(d) Quanto menor a fatia de tempo mais rápida será a execução de todas as threads.

4) Sobre postergação indefinida no escalonamento do processador:

(a) Qualquer algoritmo de escalonamento de processador pode gerar postergação indefinida.

(b) O mecanismo de envelhecimento não é capaz de ser adaptado para impedir a postergação indefinida em todos os casos estudados.

(c) Postergação indefinida pode acontecer como consequência do desejo de favorecer threads com ciclos de processamento curtos.

(d) Fatias de tempo muito grandes podem levar à ocorrência de postergação indefinida.

5) O fato de um dado algoritmo de escalonamento ser “não preemptivo” torna impossível a ocorrência de postergação indefinida ?

(a) Sim, pois threads não podem mais ser suspensas arbitrariamente.

(b) Não, pois ainda é possível deixar uma thread para sempre esperando na fila de aptos.

(c) Sim, pois a thread executa sempre até o final do seu ciclo de processamento.

(d) Não, pois a preempção é intrínseca a todos os algoritmos de escalonamento.

6) Considere um sistema operacional cujo escalonamento do processador é feito através de prioridades, sendo que a prioridade de uma thread é sempre escolhida aleatoriamente entre 1 e 100, toda vez que esta thread passa do estado de bloqueado para o estado de apto. Ou seja, cada thread recebe uma nova prioridade aleatória entre 1 e 100 sempre que entra na fila de aptos. É correto afirmar que:

(a) Não existe a possibilidade de postergação indefinida dada a natureza aleatória do escalonamento.

(b) Esta solução será obrigatoriamente preemptiva.

(c) Esta solução evita o monopólio do processador por uma única thread.

(d) Esta solução apresenta overhead de chaveamento de contexto menor do que quando fatias de tempo são usadas.

7) Com respeito aos algoritmos de escalonamento FIFO (ordem de chegada) e FT (fatia de tempo), podemos afirmar que:

(a) Ambos podem ser preemptivos.

(b) Somente FIFO apresenta a possibilidade de postergação indefinida.

(c) FIFO apresenta um nível de overhead maior.

(d) O tempo médio de espera na fila de aptos é o mesmo.

8) Um dado sistema operacional emprega filas multinível como algoritmo de escalonamento, onde cada fila utiliza fatia de tempo e entre filas é utilizada prioridade preemptiva. Threads nunca mudam de fila. Pode-se afirmar que:

(a) É possível postergação indefinida.

(b) Threads podem ser preemptadas apenas por threads da mesma fila.

(c) É obrigatório usar fatias de tempo com a mesma duração em todas as filas.

(d) Não existe propósito em separar as threads em várias filas neste caso.

9) Um dado sistema operacional emprega filas multinível como algoritmo de escalonamento, onde cada fila utiliza fatia de tempo e entre filas é utilizada prioridade preemptiva. Threads nunca mudam de fila. Discuta os seguintes aspectos: Postergação indefinida e overhead.

10) Compare os algoritmos de escalonamento FIFO (ordem de chegada) e FT (fatia de tempo) com respeito aos seguintes aspectos: Preemptividade, postergação indefinida, tempo médio de espera na fila, overhead.

11) O fato de um dado algoritmo de escalonamento ser “não preemptivo” torna impossível a ocorrência de postergação indefinida ? Mostre através de um exemplo.

12) Em um sistema cujo escalonamento do processador é feito através de fatias de tempo, considerando a fila do processador mostrada abaixo, e uma fatia de tempo igual a 6, calcule o instante no qual cada thread conclui o seu ciclo de processamento. Construa o diagrama de tempo mostrando a escala de execução.

Thread             Duração do próximo ciclo de processamento

A                                4

B                                15

C                                8

D                                3

E                                17

F                                4

13) Em um sistema cujo escalonamento do processador é feito através de fatias de tempo, considerando a fila do processador mostrada abaixo, considere o valor 10 para a fatia de tempo. Construa o diagrama de tempo até a conclusão do ciclo de processamento das threads listadas.

Thread/Duração do próximo ciclo de processamento

A/4      B/15    C/8      D/3      E/17    F/4

14) O gerenciamento de processadores em sistemas modernos é feito, quase sempre, com o uso de preempção de threads através de técnicas de compartilhamento de tempo. O que a introdução de processadores com vários núcleos (cores) altera nesse gerenciamento?

(a) Torna possível a paralelização efetiva de threads concorrentes.

(b) Torna possível o uso do algoritmo de escalonamento shortest job first (SJF).

(c) Torna possível o uso de várias threads em um mesmo processo, o que não era possível antes.

(d) Torna possível separar os demais mecanismos de gerenciamento do sistema operacional do gerenciamento do processador.

(e) Torna possível o uso de sistemas operacionais multitarefas.

15) Aponte as diferenças de propósito do escalonamento em Sistema Operacional de Tempo Real e em Sistema Operacional de Propósito Geral.

16) Considere um sistema escalonado com prioridade preemptiva, composto por três tarefas periódicas independentes, com as seguintes características:

τ1: P1=100      C1=30             D1=100

τ2: P2=5          C2=1               D2=5

τ3: P3=25        C3=5               D3=25

Através de testes de utilização, tente determinar a escalonabilidade ou não deste sistema quando RM e quando EDF são usados.

Desenhe a escala de tempo resultante para RM e para EDF até o instante de conclusão da primeira ativação de τ3.

17) Considere um sistema escalonado com prioridade preemptiva, composto por três tarefas periódicas independentes, com as seguintes características:

τ1: P1=13        C1=6               D1=13

τ2: P2=5          C2=1               D2=5

τ3: P3=25        C3=7               D3=25

Através de testes de utilização tente determinar a escalonabilidade ou não deste sistema quando RM e quando EDF são usados.

Desenhe a escala de tempo resultante para RM e para EDF até o instante de conclusão da primeira ativação de τ3.

18) Crie um exemplo com duas tarefas periódicas que, desenhando a linha do tempo, ilustre a diferença entre as políticas de atribuição de prioridades DM (deadline monotônico) e EDF (earliest deadline first).

19) Por que DM (deadline monotônico) é considerada uma política de atribuição de prioridade fixa e EDF (earliest deadline first) uma política de prioridade variável ?

20) Considerando o sistema descrito abaixo, desenhe a escala de execução obtida quando usada a política RM (taxa monotônica) e quando usada a política EDF (earliest deadline first). Faça a escala até o instante 20.

Tarefas                        Tempo de computação           Período           Deadline

τ1:                               3                                                 6                      6

τ2:                               4                                                11                    11

τ3:                               1                                                20                    20

21) Crie um conjunto com três tarefas periódicas que possa ser escalonado por alguma política de prioridade dinâmica (ex. EDF), mas que não possa ser escalonado por prioridade estática (ex. RM).  Mostre através de um diagrama de tempo a execução dessas tarefas.

22) Crie um conjunto com três tarefas periódicas que seja escalonável pelo RM mas que não  passe no teste baseado em utilização. Mostre que esse conjunto é escalonável desenhando a escala de execução até o mínimo múltiplo comum dos períodos das tarefas.

23) Considerando o sistema descrito abaixo, desenhe a escala de execução quando RM é usado e quando DM é usado. Faça o desenho até o instante 30 de tempo.

Tarefas                        Tempo Computação   Período           Deadline

τ1:                               4                                    20                    10

τ2:                               3                                    30                    15

τ3:                               11                                  40                    30

24) Considere um sistema composto por três tarefas periódicas, independentes:

τ1:   P1=4                   C1=2               D1=4

τ2:   P2=7                   C2=3               D2=7

τ3:   P3=28                 C3=2               D3=28

Podemos escalonar este sistema com prioridades preemptivas fixas ? E com prioridades preemptivas variáveis ? Justifique sua resposta.

6.11 Exercícios

1) Com respeito ao uso de “desabilita interrupção” como mecanismo de sincronização, é correto afirmar que:

(a) Não existem restrições quanto ao seu uso em qualquer sistema operacional.

(b) Apresenta o problema de busy-waiting.

(c) Não funciona em multiprocessadores.

(d) Pode apresentar postergação indefinida.

2) Com respeito ao uso de spin-lock como mecanismo de sincronização, é correto afirmar que:

(a) Reduz a responsividade do sistema ao desabilitar interrupções.

(b) Apresenta o problema de busy-waiting.

(c) Não funciona em multiprocessadores.

(d) Trata-se de instrução privilegiada.

3) Com respeito às seções críticas em programas concorrentes, é correto afirmar que:

(a) É um problema que ocorre apenas em multiprocessadores (multicore).

(b) Pode ocorrer mesmo que todas as threads acessem as variáveis compartilhadas apenas para leitura.

(c) É responsabilidade do escalonador prover a atomicidade das seções críticas.

(d) Requerem um protocolo de acesso para garantir a exclusão mútua entre as threads.

4) Cite uma limitação do uso de “desabilita interrupção” como mecanismo de sincronização e também uma limitação do spin-lock como mecanismo de sincronização.

5) Em um sistema XYZ existe uma chamada de sistema comum (não privilegiada) que permite a uma tarefa qualquer desligar as preempções temporariamente. Ou seja, após executar DESLIGA_PREEMPÇÃO os chaveamentos de contexto entre tarefas ficam proibidos até que esta mesma tarefa execute a chamada de sistema LIGA_PREEMPÇÃO. Entretanto, as interrupções continuam habilitadas, e são atendidas pelo kernel, apenas os chaveamentos de contexto (preempções) são postergados até serem ligados novamente.

Considerando o problema da seção crítica em monoprocessadores, compare o uso destas chamadas de sistema com o simples desabilitar de interrupções, a respeito das propriedades e limitações. Liste pelo menos quatro aspectos.

6) Em muitos sistemas operacionais existe uma chamada de sistema “yield()”, cujo efeito é passar a thread chamadora para o final da fila de aptos. Suponha que um dado kernel escalone o processador utilizando fatias de tempo e suporte a chamada “yield()”. Suponha ainda que, em todas as aplicações, o tempo necessário para executar uma seção crítica seja menor que a duração de uma fatia de tempo. Para este caso em particular, buscando resolver o problema da seção crítica, considere o seguinte mecanismo de sincronização:

­ Imediatamente antes de entrar na seção crítica, a thread chama “yield()”;

­ Ao sair da seção crítica, a thread não faz nada.

Responda as questões abaixo, sempre justificando sua resposta com um exemplo.

(a) Esta solução oferece exclusão mútua ?

(b) Esta solução apresenta a possibilidade de postergação indefinida ?

(c) Esta solução funciona para mais de duas threads ?

(d) Esta solução apresenta busy­waiting ?

(e) Quais as maiores desvantagens de usa­la na prática.

7) Para que funcione, as operações “lock” e “unlock” sobre os mutexes precisam ser atômicas. Indique como isto pode ser obtido. Não precisa entrar em detalhes, apenas indicar como isto poderia ser implementado.

8) Em um sistema que suporta programação concorrente apenas através da troca de mensagens, será criado uma tarefa Servidor para controlar o uso das portas seriais. Quando uma tarefa Cliente deseja usar uma porta serial, ela envia uma mensagem “Aloca” para o Servidor. Existem N portas seriais, todas equivalentes, mas cada uma pode ser usada somente por um Cliente de cada vez. O Servidor informa ao Cliente a porta que ele vai usar através da mensagem “Porta p”. Ao concluir o uso, o Cliente envia para o Servidor a mensagem “Libera p”. Suponha que exista mais do que N tarefas Clientes. Mostre o algoritmo do Servidor, em português estruturado. Supor RECEIVE bloqueante.

9) Em um sistema que suporta programação concorrente apenas através da troca de

mensagens, deve ser criado um Servidor de Medições para o mesmo problema da questão anterior. Supor que o Servidor é monothread. As mensagens existentes são mostradas abaixo. Usar apenas RECEIVE bloqueante.

“M”+123.4     Informa uma medição válida com o valor 123.4

“N”                 Informa que uma medição inválida aconteceu

“P”                  Solicita a medição corrente, desde que válida

“L”+123.4      Solicita uma resposta quando a medição válida for maior que 123.4

“A”                 Informa que o limite foi atingido

Mostre o algoritmo do Servidor de Medições em português estruturado, o qual deve implementar operações com a mesma semântica da questão anterior. Mostre como estas três operações podem ser realizadas pelos clientes através das primitivas SEND e RECEIVE.

10)(2 pontos) Considere um programa concorrente que implementa um sistema semelhante à bolsa de valores. Várias threads do tipo “Comprador” e do tipo “Vendedor” fazem ofertas de compra e venda através de um “Servidor de Negócios”. Suponha a existência de ações de uma única empresa.

Mostre o algoritmo da tarefa “Servidor de Negócios” em português estruturado (apenas o algoritmo). Supor que o Servidor é monothread e a primitiva RECEIVE é bloqueante. Não precisa descrever as demais tarefas. Os seguintes serviços são oferecidos pelo servidor:

Comprador envia “ofertaCompra valor”

Usada por uma tarefa compradora para fazer uma oferta de compra, “valor” é o valor da oferta. A tarefa compradora ficará bloqueada em um RECEIVE até que o negócio seja fechado (o valor do negócio é retornado) ou que uma outra oferta de compra melhor seja feita por outra tarefa (o valor retornado é -1 neste caso). Para o negócio ser fechado a oferta de compra deve ser maior ou igual à oferta de venda. O valor do negócio é a média entre os dois.

Vendedor envia “ofertaVenda valor”

Usada por uma tarefa vendedora para fazer uma oferta de venda, “valor” é o valor da oferta. A tarefa vendedora ficará bloqueada em um RECEIVE até que o negócio seja fechado (o valor do negócio é retornado) ou que uma outra oferta de venda melhor seja feita por outra tarefa (o valor retornado é -1 neste caso). Para o negócio ser fechado a oferta de compra deve ser maior ou igual à oferta de venda. O valor do negócio é a média entre os dois.

O servidor deve manter sempre a melhor oferta de compra e a melhor oferta de venda recebidas até o momento. Ao receber uma nova oferta de compra ou de venda este valor pode ou não ser atualizado, dependendo dos valores em questão. Também é possível que o negócio seja fechado ou não. Inicialmente, a melhor oferta de compra é INFINITO_NEGATIVO e a melhor oferta de venda é INFINITO_POSITIVO. Estes mesmos valores devem ser assumidos logo em seguida ao fechamento de um negócio.

11) Ilustre um aninhamento imperfeito de LOCK através de um exemplo.

7.8 Exercícios

1) Um sistema contém os cinco jobs a seguir, em ordem decrescente de prioridade: J1, J2, J3, J4 e J5. Existe neste sistema dois recursos: X e Y. As necessidades de recursos estão listadas abaixo:

J1: C1 = 5       composto por              1 [ X ; 3 ]1

J2: C2 = 5       composto por              1 [ Y ; 3 ]1

J3: C3 = 4       composto por              nenhum

J4: C4 = 6       composto por              1 [ Y ; 4 ]1

J5: C5 = 7       composto por              1 [ X ; 2 [ Y ; 2 ] 1 ]1

a) Determine o tempo máximo de bloqueio de cada um dos jobs, assumindo como política de alocação de recursos Desabilita Preempção.

b) Determine o tempo máximo de bloqueio de cada um dos jobs, assumindo como política de alocação de recursos Teto de prioridade (Priority Ceiling).

2) Um sistema contém os cinco jobs a seguir, em ordem decrescente de prioridade: J1, J2, J3, J4 e J5. Existe neste sistema três recursos: X, Y e Z. Os instantes de liberação (release) de cada job e as suas necessidades de recursos estão listadas abaixo:

J1:       r1 = 8              C1 = 4             1 [ X ; 3 ]       

J2:       r2 = 6              C2 = 6             1 [ Y ; 5 ]       

J3:       r3 = 4              C3 = 3             nenhum                      

J4:       r4 = 2              C4 = 5             1 [ Z ; 4 ]        

J5:       r5 = 0              C5 = 6             1[ X ; 1 [ Y ; 2 [ Z ; 1 ] 1 ] ]

Desenhe a escala de tempo deste sistema, de zero até a conclusão do último job, considerando que recursos são gerenciados através de Herança de prioridade.

3) Para este mesmo sistema da questão anterior, determine o tempo máximo de bloqueio de cada uma das tarefas, assumindo como política de alocação de recursos:

a) Desliga Preempção

b) Teto de prioridade (Priority Ceiling)

4) Um sistema contém os cinco jobs a seguir, em ordem decrescente de prioridade: J1, J2, J3, J4 e J5. Existe neste sistema dois recursos: X e Y. Os instantes de liberação (release) de cada job e as suas necessidades de recursos estão listadas abaixo:

J1:       r1 = 5              C1 = 4             1 [ Y ; 3 ]       

J2:       r2 = 4              C2 = 6             1 [ X ; 5 ]       

J3:       r3 = 3              C3 = 3             nenhum                      

J4:       r4 = 2              C4 = 5             1 [ Y ; 4 ]       

J5:       r5 = 0              C5 = 6             1[ X ; 3 [ Y ; 1 ] 1 ] ] 

Desenhe a escala de tempo deste sistema, de zero até a conclusão do último job, considerando que recursos são gerenciados através de Teto de Prioridade Imediato (Immediate Priority Ceiling).

5) Para este mesmo sistema da questão anterior, determine o tempo máximo de bloqueio de cada uma das tarefas, assumindo como política de alocação de recursos:

a) Desliga Preempção

b) Teto de Prioridade (Priority Ceiling)

6) Três tarefas periódicas τ1, τ2 e τ3 compartilham os recursos R1 e R2. As restrições temporais das tarefas e as durações de suas seções críticas que atuam nos recursos compartilhados são indicadas nas tabelas abaixo. Com base nestes dados calcule os piores casos de bloqueios (Bi) que podem estar sujeitas cada uma destas tarefas quando o protocolo Herança de Prioridade é usado no controle de acesso aos recursos compartilhados. Também desenhe a escala de execução correspondente ao pior caso de execução de cada tarefa na forma de um diagrama de tempo.

Tarefas            Tempo de computação           Prioridade       Recurso R1     Recurso R2

τ1                                15                               Alta                            1                      0

τ2                                16                               Média                         3                      4

τ3                                20                               Baixa                          0                      2

7) Um sistema contém os cinco jobs a seguir, em ordem decrescente de prioridade: J1, J2, J3, J4 e J5. Existe neste sistema três recursos: X, Y e Z. Os instantes de liberação (release) de cada job e as suas necessidades de recursos estão listadas abaixo:

J1:       r1 = 8              C1 = 5             1 [ X ; 4 ]       

J2:       r2 = 6              C2 = 7             1 [ Y ; 6 ]       

J3:       r3 = 4              C3 = 3             nenhum                      

J4:       r4 = 2              C4 = 6             1 [ Z ; 5 ]        

J5:       r5 = 0              C5 = 5             [ X ; 1 [ Y ; 2 [ Z ; 1 ] 1 ] ]    

Desenhe a escala de tempo deste sistema de zero até a conclusão do último job, considerando que recursos são gerenciados através da seguinte política:

a) Seção crítica não preemptiva.

b) Herança de prioridade.

c) Teto de Prioridade (Priority Ceiling).

d) Teto de Prioridade Imediato (Immediate Priority Ceiling).

8) Três tarefas periódicas τ1, τ2 e τ3 compartilham os recursos R1 e R2. As restrições temporais das tarefas e as durações de suas seções críticas que atuam nos recursos compartilhados são indicadas nas tabelas abaixo. Com base nestes dados, calcule os piores casos de bloqueios (Bi) a que podem estar sujeitas cada uma destas tarefas quando o Protocolo “Desliga a Preempção” é usado no controle de acesso aos recursos compartilhados. Desenhe a escala de execução correspondente ao pior caso de execução da tarefa τ1.

Calcule também os piores casos de bloqueios (Bi) a que podem estar sujeitas cada uma destas tarefas quando o Protocolo Teto de Prioridade (Priority Ceiling) é usado no controle de acesso aos recursos compartilhados. Desenhe a escala de execução correspondente ao pior caso de execução da tarefa τ1.

Tarefas            Tempo de computação           Prioridade       Recurso R1     Recurso R2

τ1                                4                                 Alta                            1                      0

τ2                                8                                 Média                         3                      5

τ3                                20                               Baixa                          0                      2

τ1:       2 [ R1 ; 1 ] 1

τ2:       2 [ R2 ; 1 [ R1 ; 3 ] 1 ] 1

τ3:       8 [ R2 ; 2 ] 10

9) Quatro tarefas compartilham os recursos globais R1 e R2. Desliga Preempção é utilizado, sendo que as preempções são desligadas em todos os processadores. As restrições temporais das tarefas e as durações de suas seções críticas que atuam nos recursos compartilhados são indicadas na tabela abaixo. As tarefas são particionadas entre dois processadores. Com base nestes dados, construa o diagrama descrevendo a escala de ocupação dos processadores até o completo atendimento destas requisições. A exclusão mútua é obtida ?

Tarefas            Processador    Chegada         Execução                    Prioridade      

τ1                    A                     2                      1[R1, 2]1                    mais alta

τ2                    B                     1                      2[R2, 2]2

τ3                    B                     0                      1[R1, 3]2

τ4                    A                     0                      1[R2, 4]2                    mais baixa

8.5 Exercícios

1) Comparando semáforos com variáveis condição, é correto afirmar que:

(a) A decisão de bloquear ou não uma thread no caso de semáforos depende do passado, mas no caso da Variável Condição não depende.

(b) A operação P é idêntica a WAIT e a operação V é idêntica ao SIGNAL.

(c) Somente semáforos são implementados de forma atômica.

(d) As operações V e SIGNAL são usadas para incrementar um contador inteiro.

2) Considere um sistema de medição onde várias threads colaboram através de um monitor que encapsula variáveis compartilhadas relacionadas com os dados medidos via dois sensores, um sensor de corrente e um sensor de tensão. O monitor mantém a medida mais recente de corrente e de tensão, juntamente com a hora de cada uma das medições.

Implemente o monitor utilizando as funções da biblioteca de pthreads, sem busy-waiting. Várias threads podem chamar cada uma das rotinas de entrada do monitor. Não precisa criar as threads, apenas implementar o monitor. O monitor em questão possui 5 rotinas de acesso:

/* set_medida_tensao

Permite a uma thread registrar a última medição que ela obteve do sensor de tensão e a hora da medida. Medidas de tensão antigas são descartadas.

*/

void set_medida_tensao( double tensao, long hora);

/* set_medida_corrente

Permite a uma thread registrar a última medição que ela obteve do sensor de corrente e a hora da medida. Medidas de corrente antigas são descartadas.

*/

void set_medida_corrente( double corrente, long hora);

/* pega_tensao

Permite a uma thread ler do monitor a medição de tensão registrada no monitor. Fica bloqueada caso nenhuma tensão tenha sido registrada até o momento.

*/

double pega_tensao( void);

/* pega_corrente

Permite a uma thread ler do monitor a medição de corrente registrada no monitor. Fica bloqueada caso nenhuma corrente tenha sido registrada até o momento.

*/

double pega_corrente( void);

/* espera_medicao_sincrona

Bloqueia a thread chamadora até que a diferença entre a hora da leitura de tensão e a hora da leitura de corrente registradas seja menor que 10.

*/

void espera_sincronizacao( void);

3) Considere um sistema bancário onde uma conta é implementada na forma de um monitor com Pthreads. A conta mantém um valor de saldo e oferece 4 rotinas de acesso, as quais podem ser chamadas por muitas threads. Implemente apenas o monitor.

/* Deposita um valor na conta, soma no saldo, nunca bloqueia.

*/

void deposita( double valor);

/* Retira o valor da conta, subtrai do saldo, fica bloqueado até que exista saldo suficiente na conta para atender a retirada. Pedidos de retirada são atendidos por ordem de chegada.

*/

void retira( double valor);

/* Bloqueia a thread até que o somatório dos depósitos, sem considerar as retiradas, ultrapasse o valor_vip.

*/

void espera_saldo_vip( double valor_vip);

/* Aplica sobre o saldo da conta uma correção monetária, fornecida em pontos percentuais.

*/

void aplica_correcao( double correcaoPP);

4) Em um programa concorrente existem várias tarefas do tipo “calcula” e várias tarefas do tipo “mostra”. As tarefas do tipo “calcula” iniciam sua execução no início do programa. Já as tarefas do tipo “mostra” precisam esperar autorização das tarefas “calcula” para começar. Além disto, cada três tarefas “calcula” permitem que exatamente uma tarefa “mostra” execute. Implemente uma solução para este problema usando semáforos. A solução consiste de 2 rotinas:

/* tarefa “calcula” usa para informar que está autorizando, ela mesmo nunca fica bloqueada

*/

void  autoriza (void);

/* tarefa “mostra” usa para ficar bloqueada até que pelo menos três autorizações sejam feitas, quando então ela é liberada, não importa quando as autorizações foram feitas

*/

void espera_3_autorizacoes( void );

Cada 3 autorizações permite a liberação de apenas uma tarefa “mostra”. Não importa se as autorizações aconteceram antes ou depois da tarefa “mostra” chamar a rotina “espera_3_autorizacoes()”. Não é permitido deixar uma tarefa “mostra” bloqueada no caso de já terem acontecido 3 chamadas da rotina “autoriza” que não foram usadas. A tarefa “calcula” nunca bloqueia.

5) Um simulador de tráfego urbano foi implementado como um programa concorrente para melhor aproveitar os computadores com arquitetura multicore. Neste simulador cada carro é representado por uma thread. Todas as vias são de sentido único. Cada cruzamento é representado por um monitor.

Quando um carro deseja passar por um cruzamento, a thread que o representa chama a rotina “pedePassar()” do monitor e passa como parâmetro o sentido desejado. A thread então fica bloqueada até que a passagem seja autorizada. Depois que o carro passou pelo cruzamento, a thread que o representa chama a rotina “jaPassei()” do monitor.

A gerência do recurso cruzamento é feita da seguinte forma:

- Se o carro pede para passar, e o cruzamento está livre, ele pode passar;

- Se o carro pede para passar, e estão passando carros no mesmo sentido que ele, ele pode passar;

- Se o carro pede para passar, e estão passando carros no outro sentido, ele fica em espera.

Implemente o monitor utilizando as funções da biblioteca de pthreads, sem busy-waiting, sem postergação indefinida e sem deadlock. Não precisa criar as threads, apenas implementar o monitor.  O monitor em questão possui duas rotinas de acesso:

void   pedePassar( int sentido );                    // 1 é norte-sul,         -1 é leste-oeste

void   jaPassei( void );           

6) Implemente a semântica de um semáforo (primitivas P e V) usando para isto as primitivas da biblioteca das pthreads (mutex e variável condição). As funções a serem implementadas são:

void p(void);

void v(void);

Suponha que existe um único semáforo.

7) Considere um programa concorrente que implementa um sistema semelhante à bolsa de valores. Várias threads do tipo “Comprador” e do tipo “Vendedor” fazem ofertas de compra e venda através de um “Pregão de Negócios”. Suponha a existência de ações de uma única empresa.

Implemente o “Pregão de Negócios” seguindo a idéia de um monitor, utilizando as funções da biblioteca de pthreads, sem busy-waiting. Várias threads podem chamar cada uma das rotinas de entrada do monitor. Não precisa criar as threads, apenas implementar o monitor. O monitor em questão possui 2 rotinas de acesso: ofertaCompra e ofertaVenda.

As variáveis compartilhadas do monitor incluem a atual melhor oferta de compra e atual melhor oferta de venda. Uma oferta de compra é melhor do que outra quando apresenta um preço maior. Uma oferta de venda é melhor do que outra quando apresenta um preço menor. O negócio é fechado quando a oferta de compra é maior do que a oferta de venda e neste caso o negócio acontece com o preço médio entre as duas ofertas.

Inicialmente, como não existem ofertas ainda, a melhor oferta de compra é INFINITO_NEGATIVO e a melhor oferta de venda é INFINITO_POSITIVO.

double ofertaCompra( double valor);

Usada por uma thread compradora para fazer uma oferta de compra, “valor” é o valor da oferta. Existem 3 cenários possíveis.

- Caso a oferta de compra seja alta o bastante para fechar o negócio, o negócio é fechado, a correspondente thread vendedora é liberada e a função retorna o valor do negócio.

- Caso a oferta de compra não seja suficiente para fechar o negócio, mas é mais alta do que a atual melhor oferta de compra, a antiga thread com a melhor oferta de compra é liberada e a thread chamadora ficará bloqueada, pois possui agora a melhor oferta de compra.

- Caso a oferta de compra seja menor do que a atual melhor oferta de compra, a thread chamadora retorna imediatamente com -1.

double ofertaVenda( double valor);

Usada por uma thread vendedora para fazer uma oferta de venda, “valor” é o valor da oferta. Existem 3 cenários possíveis.

- Caso a oferta de venda seja baixa o bastante para fechar o negócio, o negócio é fechado, a correspondente thread compradora é liberada e a função retorna o valor do negócio.

- Caso a oferta de venda não seja suficiente para fechar o negócio, mas é mais baixa do que a atual melhor oferta de venda, a antiga thread com a melhor oferta de venda é liberada e a thread chamadora ficará bloqueada, pois possui agora a melhor oferta de venda.

- Caso a oferta de venda seja maior do que a atual melhor oferta de venda, a thread chamadora retorna imediatamente com -1.

8) Considerando o código abaixo, uma variação da implementação do produtor/consumidor, responda as seguintes perguntas (justificando):

a) Está garantido o acesso exclusivo à variável “buffer” no caso de 1 produtor e 1 consumidor?

b) É possível a ocorrência de deadlock no caso de 2 produtores e 2 consumidores ?

c) É possível a postergação indefinida de um consumidor ?

 

struct tipo_dado buffer;

semaphore espera_vaga = 1;

semaphore espera_dado = 0;

 

void produtor( void)

{

     ...

     P( espera_vaga );

     buffer = dado_produzido;

     V( espera_dado );

     ...

}

 

void consumidor( void)

{

     ...

     P( espera_dado );

     dado_a_consumir = buffer;

     V( espera_vaga );

     ...

}

9) Considere um sistema de medição onde existem duas threads sensoras. Cada thread sensora faz medições em vários pontos da planta, gerando uma “struct C” com todos os dados lidos por ela em uma dada medição. As threads sensoras são identificadas como tipo A e tipo B.

Existe neste sistema também uma série de threads que utilizam os dados medidos para vários propósitos, tais como alimentar sinótico, gerar históricos, etc. Essas threads consultam sempre a última medição disponível de um dado tipo.

Finalmente, existe neste sistema também uma thread de alarme, a qual fica bloqueada até que a condição de alarme torne­se verdadeira. Esta condição é indicada por uma função auxiliar “int situacao_alarme(void)”, a qual retorna “1” quando a situação de alarme está ocorrendo. Considere que esta função auxiliar já está implementada. Implemente um monitor utilizando as funções da biblioteca de pthreads, sem busy­waiting, tal que existam 3 chamadas possíveis:

 

 

 

Struct dados_medidos_t {

...

};

 

#define TIPO_A 0

#define TIPO_B 1

 

void insere_medicao( int tipo, struct dados_medidos_t xxx);

struct dados_medidos_t consulta_medicao( int tipo);

void espera_alarme(void );

Dentro do monitor são mantidas apenas a última medição disponível para cada tipo, ou seja, existe uma estrutura para a medição mais recente do tipo A e outra para a medição mais recente do tipo B.

A função “consulta_medicao()” apenas informa o valor atual daquele tipo de medição sem consumi­lo (apaga-lo) do monitor. No caso de não haver ainda nenhuma medição do tipo desejado no monitor, a thread fica bloqueada até uma medição do tipo desejado ser incluída no monitor.

A função “espera_alarme()” bloqueia a thread chamadora até que a situação de alarme seja detectada (torne­se verdadeira). A condição de alarme é testada quando a função “insere_medicao()” é chamada.

10) Em um programa concorrente existem N threads trabalhadoras e uma única thread finalizadora. O programa é tal que a thread finalizadora precisa esperar todas as threads trabalhadoras terminarem para então ela finalizar o programa. Este tipo de sincronização é chamada de “barreira” e é típica da programação em máquinas paralelas. O valor de N é conhecido.

Implemente uma solução para o problema da barreira usando pthreads. A solução consiste de 2 rotinas:

/* thread trabalhadora “meuId” informa que acabou sua parte do serviço

*/

void acabei (int meuId);

/* thread finalizadora fica bloqueada até todos os N trabalhadores acabarem o serviço

*/

void espera_todos( void );

11) Para que funcionem, as operações “P” e “V” sobre os semáforos precisam ser atômicas. Indique como isto pode ser obtido. Não precisa entrar em detalhes, apenas indicar como isto poderia ser implementado em um processador.

12) Considere uma relação produtor/consumidor onde vários produtores e vários consumidores acessam o mesmo buffer circular. O buffer circular possui capacidade para N caracteres. Cada produtor deposita no buffer um número variável de caracteres, sempre menor do que N. Da mesma forma, cada consumidor retira do buffer um número variável de caracteres, sempre menor do que N, que não guarda relação com a quantidade de caracteres que são depositados de cada vez. O número de caracteres a ser inserido ou retirado do buffer é fornecido como parâmetro pela thread.

Crie uma solução para este problema utilizando pthreads. Tanto produtor quanto consumidor devem ficar bloqueados caso o buffer não tenha como atender o pedido imediatamente. Soluções com busy­waiting não são aceitáveis. Os produtores precisam ser atendidos na ordem de chegada.

Os consumidores precisam ser atendidos na ordem de chegada. Os dados precisam ser consumidos na mesma ordem na qual foram produzidos. Rotinas a serem implementadas:

insere( char *s, int numero_caracteres);

retira( char *s, int numero_caracteres);

Pode ser usada uma rotina auxiliar “copiachar” para fazer cópias de caracteres, desde que ela faça uma simples cópia sem qualquer tipo de sincronização dentro dela.

13) Em um programa concorrente que controla o estacionamento da universidade, a gerência das vagas é feita através de um monitor programado usando Pthreads. Existem no estacionamento NP+NA vagas. A principio são NP vagas para profesores e NA vagas para alunos, mas quando as vagas para professores acabam, eles podem usar as vagas dos alunos. Alunos podem usar somente as vagas dos alunos. O monitor oferece 4 rotinas de acesso.

/* Se existe vaga para professor, ocupa 1 vaga de professor. Se não existe vaga para professor porem existe vaga para aluno, pega a vaga emprestada e ocupa uma vaga de aluno. Se não existe nenhum tipo de vaga, bloqueia até que surja uma vaga de qualquer tipo. */

void entra_prof( void);

/* Se existe vaga para aluno, ocupa 1 vaga de aluno. Se não existe vaga para aluno, bloqueia até que surja uma vaga de aluno. */

void entra_aluno( void);

/* Libera uma vaga do estacionamento. Se professores pegaram vagas emprestadas dos alunos, devolve a vaga para os alunos. Poderá liberar um professor ou aluno esperando por vaga. */

void sai_prof( void);

/* Libera uma vaga do estacionamento para alunos. Poderá liberar um professor ou aluno esperando por vaga. */

void sai_aluno( void);

9.8 Exercícios

1) Como são definidas a UT (Universal Time), a TAI (International Atomic Time) e a UTC (Universal Time Coordinated) ?

2) Qual o oscilador fundamental usado pela UT ? E pela ET ?

3) Quais as fontes de variação que afetam a UT ?

4) Eventos são coletados em uma rede composta por 4 computadores, e associados com a hora local do computador que detecta cada evento. Para que os mesmos possam ser analisados em conjunto, é necessário um erro máximo entre relógios de 300 milissegundos. Os cristais usados nesses computadores possuem uma taxa de deriva de 10­5 em relação uns aos outros, para mais ou para menos.

Supondo que pode existir um erro inicial máximo de 50 milissegundos entre quaisquer dois relógios da rede, calcule quanto tempo vai levar até que os dois relógios com maior erro entre eles apresentem um erro de 300 milissegundos, supondo sempre o pior caso. Dica: adote um deles como o relógio de referência.

5) Em um sistema industrial, um computador A é responsável por ler um certo sensor S a cada 100 milissegundos, e enviar a medida para um outro computador B, o qual executa a estratégia de controle. Os cristais de quartzo usados nos relógios desses computadores divergem um do outro no máximo por uma taxa de deriva (drift rate) de 10­5 . Não existe sincronização de relógios, e cada computador utiliza seu relógio local. Na perspectiva do computador B, qual o intervalo de tempo entre as medições realizadas pelo computador A ? Justifique. Dica: Use o relógio do computador B como referência.

6) Em um sistema industrial, um computador A é responsável por registrar um certo evento EVA enquanto o computador B é responsável por registrar um certo evento EVB. Os cristais de quartzo usados nos relógios desses computadores divergem um do outro no máximo por uma  taxa de deriva (drift rate) de 10­4. Quando o sistema foi ligado, o relógio do computador A estava adiantado em relação ao relógio do computador B por 1mS. Os eventos foram registrados nos seguintes horários: EVA aos 20002mS e EVB aos 20000 mS.

Qual evento aconteceu antes ? Justifique numericamente a sua resposta. Dica: Use o relógio do computador B como referência.

7) Em um sistema industrial, um computador A é responsável por ler a tensão e enviar para o computador central o valor lido e sua hora local em segundos desde 1/1/1970. Um outro computador B é responsável por ler a corrente e enviar para o computador central o valor lido e sua hora local em segundos desde 1/1/1970. O computador central recebeu as seguintes mensagens:

Do computador A: 15V aos 120000 segundos

Do computador B: 13A aos 130000 segundos

Suponha que os relógios dos computadores A e B estavam perfeitamente sincronizados em 1/1/1970 e que os cristais de quartzo usados nos relógios desses computadores divergem em relação ao relógio do computador central no máximo por uma taxa de deriva (drift rate) de  10-4. Qual a máxima diferença de tempo que pode haver entre estas duas medidas, em segundos do computador central ?

8) Em um sistema industrial, um computador A é responsável por registrar um certo evento EVA enquanto o computador B é responsável por registrar um certo evento EVB. Os cristais de quartzo usados nos relógios desses computadores divergem da UTC no máximo por uma taxa de deriva (drift rate) de 10-4. Quando o sistema foi ligado, o relógio do computador A estava adiantado em relação a UTC por 4ms e o relógio do computador B estava adiantado em relação a UTC por 2mS.

Após o sistema estar ligado por exatamente 20000ms segundo a UTC, qual o intervalo de valores possíveis que pode ser apresentado pelo relógio do computador A e pelo relógio do computador B ?

9) Em uma aplicação industrial são utilizados dois computadores para coleta simultânea dos dados. Os relógios destes dois computadores são sincronizados a cada P segundos com a UTC, mas o mecanismo de sincronização usado deixa um erro residual no momento da sincronização de 5ms (para mais ou para menos). Assume-se uma taxa de deriva máxima (drift rate) em relação à UTC de 10-4, e a aplicação tolera erros de no máximo 1s entre as coletas dos dois computadores. Qual o valor máximo de P para manter o sistema dentro dos limites operacionais desejados ?

10) Suponha que o sistema operacional do seu computador sincronize o relógio local a cada uma hora, quando o erro em relação a UTC é reduzido para mais ou menos 50ms. O relógio local apresenta uma taxa de deriva máxima de 10-5. Qual o maior erro que o relógio local poderá apresentar em relação a UTC ?

11) Investigue se computadores desktop atuais também possuem todos os relógios descritos na seção 9.5.1 deste capítulo.

12) Pesquise na Internet receptores GPS de tempo. Quais valores de exatidão são mencionados nas descrições dos produtos ? Existem condicionantes ?

10.4 Exercícios

1) Construa uma função ou subrotina simples, preferencialmente em C ou assembly, e construa manualmente o Grafo de Fluxo de Controle dela. Se ficar muito complexo para fazer a mão, simplifique o programa. Precisa ter pelo menos um IF e um laço.

2) Considerando o Grafo de Fluxo de Controle construído na questão anterior, quantos caminhos de execução diferentes existem entre o início e o fim da função ?

3) É possível identificar quais dados de entrada conduzem ao caminho mais longo em termos de linhas de código ?

4) Como dados de entrada do passado, de ativações passadas da tarefa, podem alterar o seu fluxo de controle em uma execução no futuro ?

5) Caso já tenha programado um microcontrolador alguma vez, o microcontrolador que você programou tinha memória cache ? Tinha pipeline ? O que a documentação dele fala sobre o tempo de execução de cada instrução de máquina ?

6) Suponha que no computador em questão o acesso a um dado na cache demore 1us e o acesso ao mesmo dado na memória principal demore 100us. A tarefa X possui uma taxa média de acertos na cache de 95%. Considerando apenas este fator, e o fato da tarefa fazer 100.000 acessos a dados durante sua execução, qual será o seu tempo de execução ? Se não existisse a memória cache, qual seria o seu tempo de execução ?

7) Considere o computador desktop ou notebook que você utiliza no dia a dia. Identifique qual processador ele usa. Pesquise a documentação do fabricante deste modelo de processador e liste os elementos de aceleração probabilista que ele inclui. Esta informação provavelmente estará espalhada pelo site do fornecedor.

8) Na implementação de threads é possível que uma thread B em execução seja temporariamente suspensa para a execução de uma outra thread A de mais alta prioridade. De que maneira a execução da thread A poderá aumentar o tempo de execução que falta para completar a thread B ?

11.9 Exercícios

1) Considerando a figura 11.1, é possível obter um HWM maior do que o verdadeiro WCET ? É possível obter um HWM igual ao verdadeiro WCET ? Em que cenários seria possível garantir que o HWM obtido é mesmo igual ao verdadeiro WCET ?

2) Que tipo de código possui tempo de execução com baixa variância ? Pense em termos de algoritmo e dependência dos dados de entrada.

3) E o contrário da questão anterior, que tipo de código possui tempo de execução com alta variância ?

4) Suponha que o Intel MCS-51 é usado e temos o código da tarefa em assembly. O que deveríamos fazer para determinar o seu WCET ? Descreva quais passos seriam necessários. Lembre-se que dados de entrada podem variar.

5) Suponha agora que o processador em questão é um Intel i7, com pipeline superescalar (paralelo), branch predictor, vários níveis de cache, etc. De que maneira o problema de obter o WCET ficou mais complicado ?

6) O que é um bloco básico ?

7) Qual o propósito da análise de valor ?

8) O que é uma anomalia temporal ?

9) Por que são usados previsores de saltos (branch predictors) para tentar adivinhar de antemão se um salto (branch) condicional vai ocorrer ou não ? O que muda no tempo de execução da tarefa se o previsor acerta ou não a sua previsão ?

10) Visite o site da ferramenta aiT. Localize a lista de processadores suportados. Escolha um deles, visite o site do fabricante daquele processador, e procure identificar os elementos de aceleração probabilista empregados naquele processador.

12.8 Exercícios

1) Considerando o seu ambiente usual de programação, existe algum recurso pronto para medir o tempo de resposta de uma tarefa ? E o seu tempo de execução ?

2) Caso já tenha programado microcontroladores, que recursos de hardware poderiam ser usados para medir tempos em um computador auxiliar ? Pense em pinos de entrada/saída digital, portas seriais, etc.

3) Durante a bateria de testes, todas as linhas de código da tarefa foram executadas pelo menos uma vez. Isto garante que o WCET será observado ? Justifique.

4) Vários autores propõe o uso de Algoritmo Genético para procurar a entrada de dados que maximiza o tempo de execução. Cite uma vantagem e uma desvantagem de usar meta-heurísticas com este propósito.

5) Qual a vantagem de usar o método híbrido sobre o método completamente analítico descrito no capítulo 11 ?

6) Qual a vantagem de usar o método híbrido sobre o método completamente baseado em medição ?

7) Pesquise na Internet em quais áreas a Teoria de Valores Extremos é mais usada. Liste exemplos de aplicações em quaisquer outras áreas.

8) Quais os grandes atrativos da Teoria de Valores Extremos para a indústria que precisa lidar com o WCET das tarefas, como por exemplo a indústria aeronáutica ?

9) O que significa “qualidade de ajuste (goodness-of-fitness)” ? Como isto pode impedir a aplicabilidade da Teoria de Valores Extremos ?

10) Normalmente o tempo de execução de uma tarefa é uma variável aleatória com algum tipo de distribuição. Em que tipo de algoritmo, em que tipo de processador, uma tarefa apresentaria um tempo de execução constante ?

13.13 Exercícios

1) Cite uma vantagem e uma desvantagem do executivo cíclico em relação ao escalonamento baseado em prioridades, com relação à variância dos tempos de resposta.

2) Com respeito ao worst-case execution time de um tratador de interrupção, descreva duas fontes de não determinismo que dificultam sua determinação exata.

3) Com respeito ao worst-case response time de um tratador de interrupção, descreva duas fontes de não determinismo que dificultam sua determinação exata.

4) O número de chaveamentos de contexto que uma tarefa experimenta varia ? Justifique a sua resposta.

5) Suponha que, em um microkernel, a thread X receba a máxima prioridade do sistema. Ainda assim, que aspectos do sistema vão gerar variância no seu tempo de resposta ?

6) Considerando os diversos fatores que causam variância em tempos de resposta, é razoável esperar uma maior variância quando a tarefa executa sobre o FreeRTOS ou sobre o Linux ? Justifique.

7) Pesquise na Internet as diferenças entre o Linux normal e o Linux com o patch Preempt_RT. O que pode ser esperado com respeito à variância do tempo de resposta das tarefas implementadas em um e outro sistema. Justifique sua resposta a partir das informações encontradas sobre os dois sistemas.

8) Que fontes de variância do tempo de resposta são totalmente definidas e controladas pelo programador da aplicação ?

14.14 Exercícios

1) Por que é possível usar as mesmas equações tanto para tarefas periódicas como para tarefas esporádicas ?

2) Como é possível incorporar o tempo gasto com o chaveamento de contexto entre tarefas nas equações da análise do tempo de resposta ?

3) Quais são as duas formas de impacto que desabilitar interrupções causa no tempo de resposta de uma tarefa no pior caso ? Descreva o que acontece.

4) Considerando um sistema de tempo real que trabalha com escalonamento preemptivo e prioridades fixas, como apareceria para uma tarefa de alta prioridade, em termos de impacto sobre o seu tempo de resposta, os seguintes fatores:

a) Tratador das interrupções de hardware do timer, tratador demora CT mS para executar e o timer está programado para ocorrer a cada PT mS.

b) Kernel desabilita interrupções para executar operações críticas, o trecho mais longo de interrupções desabilitadas demora ID mS.

5) Como poderia ser incorporado na análise do tempo de resposta o fato de uma tarefa A preceder uma tarefa B. Preceder significa que a tarefa B só pode iniciar depois da tarefa A terminar. Suponha que as duas possuem o mesmo período.

Dica: Pode usar o atraso de liberação, mas pode também jogar com as prioridades delas.

6) Em um sistema operacional, a resolução dos clocks e timers do sistema é X. O tempo de processador que o escalonador precisa para atender cada evento de timer é E. Um chaveamento de contexto de processo para o kernel leva no máximo CS unidades de tempo. Suponha que o kernel trata os eventos de tempo uma vez a cada Y unidades de tempo. Ou seja, X é a unidade de tempo usada pela função de “sleep()” e Y é o período do temporizador em hardware (timer).

a) Suponha que somente uma tarefa no sistema executa “sleep()”. Qual o erro máximo que pode ser observado em uma chamada do “sleep()” ? Considere o tempo entre a chamada do “sleep()” e a inclusão do processo acordado na fila de aptos.

b) Suponha que no máximo N processos podem requisitar “sleep()” simultaneamente. Qual o erro máximo que pode ser observado em uma chamada do “sleep()” ? Novamente considere o tempo entre a chamada do “sleep()” e a inclusão do processo acordado na fila de aptos.

Explique o raciocínio que justifica uma solução algébrica.

7) Qual a diferença entre interferência e bloqueio ?

8) Determine se o conjunto de tarefas abaixo é escalonável com deadline monotônico (prioridades preemptivas), aplicando a análise para D ≤ P. Existe uma seção crítica protegida por mutex comum entre as tarefas τ1 e τ2, a qual demora 1 unidade de tempo para ser executada.

τ1:                   C1=2   P1=5   D1=5

τ2:                   C2=5   P2=20 D2=16

τ3:                   C3=3   P3=30 D3=30

9) Faça o mesmo para o sistema abaixo. Existe uma seção crítica protegida por mutex comum entre as tarefas τ1 e τ2, a qual demora 1 unidade de tempo para ser executada. Interrupções ficam desabilitadas por no máximo 1 unidade de tempo.

τ1:                   C1=2   P1=5   D1=5

τ2:                   C2=5   P2=25 D2=20

τ3:                   C3=6   P3=30 D3=30

10) Considerando a tabela abaixo, usando a política de atribuição de prioridades Deadline Monotônico:

τ1:                   C1=4             P1=20             D1=10

τ2:                   C2=3             P2=30             D2=15

τ3:                   C3=11           P3=40             D3=30

Calcule os tempos de resposta e mostre a escalonabilidade (ou não escalonabilidade) desse conjunto de tarefas. Interrupções podem ficar desabilitadas por no máximo 1 u.t. e as tarefas τ1 e τ2 compartilham uma estrutura de dados protegida por mutex cuja seção crítica demora 2 u.t. para ser executada.

11) Considerando a tabela abaixo, usando a política de atribuição de prioridades Deadline Monotônico:

τ1:                   C1=4            P1=10             D1=10

τ2:                   C2=3            P2=30             D2=15

τ3:                   C3=11          P3=40             D3=30

Calcule os tempos de resposta e mostre a escalonabilidade (ou não escalonabilidade) desse conjunto de tarefas. Interrupções podem ficar desabilitadas por no máximo 2 u.t. e as tarefas τ1 e τ2 compartilham uma estrutura de dados protegida por mutex cuja seção crítica demora 3 u.t. para ser executada.

12) Considere um sistema escalonado com prioridade preemptiva, composto por três tarefas periódicas independentes, com as seguintes características:

τ1:                   C1=30          P1=100           D1=100

τ2:                   C2=1            P2=5               D2=5

τ3:                   C3=5            P3=25             D3=25

As tarefas foram numeradas conforme a sua ordem de importância para o sistema.

a) O sistema é escalonável se a prioridade for baseada em importância ?

b) O sistema é escalonável se EDF (earliest deadline first) for utilizado ?

13) Considerando a tabela abaixo, usando a política de atribuição de prioridades Deadline Monotônico:

τ1:                   C1=4   P1=10 D1=10

τ2:                   C2=5   P2=30 D2=15

τ3:                   C3=11 P3=45 D3=33

Calcule os tempos de resposta e mostre a escalonabilidade (ou não escalonabilidade) desse conjunto de tarefas. Interrupções podem ficar desabilitadas por no máximo 2 u.t. e as tarefas τ1 e τ2 compartilham uma estrutura de dados protegida por mutex cuja seção crítica demora 3 u.t. para ser executada.

14) Considerando a tabela abaixo, usando a política de atribuição de prioridades Deadline Monotônico:

τ1:                   C1=4   P1=11 D1=11

τ2:                   C2=3   P2=30 D2=25

τ3:                   C3=11 P3=45 D3=30

Calcule os tempos de resposta desse conjunto de tarefas. Interrupções podem ficar desabilitadas por no máximo 2 u.t. e as tarefas τ1 e τ2 compartilham uma estrutura de dados protegida por mutex cuja seção crítica demora 2 u.t. para ser executada.

15) Considerando a tabela abaixo, usando a política de atribuição de prioridades Deadline Monotônico:

τ1:                   C1=2   P1=10 D1=9

τ2:                   C2=3   P2=30 D2=20

τ3:                   C3=8   P3=40 D3=30

Calcule os tempos de resposta e mostre a escalonabilidade (ou não escalonabilidade) desse conjunto de tarefas. Interrupções podem ficar desabilitadas por no máximo 2 u.t. e as tarefas τ2 e τ3 compartilham uma estrutura de dados protegida por mutex cuja seção crítica demora 3 u.t. para ser executada. A τ1 é esporádica. Interrupções do timer acontecem a cada 10 u.t. para ativar um tratador que demora no máximo 1 u.t. para executar.

16) O que acontece no sistema da questão anterior se existirem apenas dois níveis de prioridade para atribuir às tarefas ?

15.6 Exercícios

1) O que significa ter uma hipótese de carga em sistemas de tempo real críticos?

2) O que significa ter uma hipótese de faltas em sistemas de tempo real críticos ?

3) Descreva as diferenças entre “hard real-time” e “soft real-time”, na visão da literatura acadêmica.

4) Imagine aplicações onde faria sentido cada uma das técnicas citadas para tratar de sobrecarga em sistemas sem garantia: atrasa deadline, reduz precisão, não executa, reduz período.

5) Cite uma vantagem e uma desvantagem da Garantia Testada sobre a Garantia Provada.

6) Imagine aplicações onde faria sentido cada uma das abordagens práticas adotadas pela indústria: garantia provada, garantia testada e sem garantia.

7) Qual tipo de abordagem você usaria em uma aplicação como:

a) Controle de temperatura da caldeira de um hotel;

b) Controle da tensão elétrica gerada por uma turbina em usina hidroelétrica;

c) Detecção de possível colisão em um avião civil.

16.9 Exercícios

1) Qual a diferença básica entre o que se espera de um sistema operacional de propósito geral e de um sistema operacional de tempo real ?

2) Que funcionalidades relacionadas com a noção de tempo real são esperados de um SOTR ?

3) Por que memória virtual é em geral problemática no contexto de um SOTR ?

4) Quais são os três aspectos construtivos mais relevantes para um SOTR ? Justifique sua escolha.

5) Qual o problema de usar uma chamada de sistema “sleep()” comum para implementar uma tarefa periódica ?

6) Pesquise na Internet aplicações de tempo real que usam o FreeRTOS.

7) O que caracteriza o FreeRTOS como um microkernel ?

8) Pesquise na Internet aplicações de tempo real que usam o Linux Preempt_RT.

9) Por que o modelo de preempção “Fully Preemptible Kernel (RT)” é o modelo mais apropriado para aplicações de tempo real no Linux Preempt_RT ?

10) Como o modelo de preempção escolhido no Linux impactará nos tempos de resposta das tarefas ?

11) Discuta dois fatores que podem ser considerados na escolha de um SOTR. Argumente a favor da importância dos fatores escolhidos.

12) Por que a gestão de energia do computador feita pelo sistema operacional é importante para aplicações de tempo real ?

13) Pesquise na Internet sobre outros microkernel de tempo real além do FreeRTOS ? Existem muitos ? Até que ponto os aspectos construtivos de cada um são descritos no site do fornecedor ?

14) Procure na Internet estudos de mercado sobre sistemas embutidos (embedded systems) e o uso de SOTR. Por exemplo, a revista EETimes faz uma pesquisa anualmente. Como aparecem o Linux Preempt_RT e o FreeRTOS nas últimas pesquisas disponíveis ? Que outros SOTR são bastante usados na indústria ?

17.7 Exercícios

1) Qual o propósito de um servidor de tarefas aperiódicas ?

2) Considerando os servidores de tarefas aperiódicas, qual a vantagem de um servidor periódico sobre um servidor de background ?

3) Qual a diferença entre escalonadores globais e escalonadores particionados para multiprocessadores ?

4) Quais as dificuldades para aplicar a análise de tempo de resposta no caso de multiprocessadores ?

5) O que é um barramento de campo (fieldbus) ?

6) Procure na Internet por implementações do PTP (Precision Time Protocol) para Linux e para FreeRTOS. Existem implementações disponíveis com código aberto ?

7) Tente imaginar uma tarefa onde o conceito de parte obrigatória e parte opcional da Computação Imprecisa poderia ser aplicado. Identifique qual das três formas descritas no texto seria mais apropriada para implementá-la.

8) Considerando tudo o que foi visto neste livro, cite alguns cuidados a serem tomados na engenharia de software para sistemas de tempo real.