1) Considerando a tarefa periódica descrita por (Ji=4, Ci=3, Pi=10, Di=8), determine os parâmetros absolutos da terceira ativação da tarefa: chegada, liberação, deadline absoluto e um limite inferior para o tempo de resposta.


2)

  1. Considerando a tabela abaixo, descreva a escala obtida, na forma de um diagrama de Gantt, quando usada a política Rate Monotonic. Faça até o instante 20. 

  1. Considerando a tabela abaixo, descreva a escala obtida, na forma de um diagrama de Gantt, quando usada a política Earliest Deadline First. Faça até o instante 20.

Tarefas

Tempo de computação

Período

Deadline

A

3

6

6

B

4

11

11

C

1

20

20


3) Dadas as tarefas com as restrições temporais descritas abaixo, e sabendo que a tarefa A precede a tarefa B, calcule os tempos de respostas das tarefas. A atribuição de prioridades segue o deadline monotonic. 

Tarefas


Release jitter

Tempo de computação

Período

Deadline

A

3

4

20

20

B

0

3

30

30

C

1

11

50

50


4) Três tarefas periódicas T1, T2 e T3 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

  1. Calcule os piores casos de bloqueios (Bi) que podem estar sujeitas cada uma destas tarefas quando o Protocolo Herança de Prioridade (PHP) é usado no controle de acesso aos recursos compartilhados.

  2. Descreva a escala de execução correspondente ao pior caso de execução de cada tarefa na forma de um diagrama de Gantt.

Tarefas


Tempo de computação

Prioridade

Recurso R1

Recurso R2

T1

15

Alta

1


T2

16

Média

3

4

T3

20

Baixa


2


5) Desenhe o diagrama de tempo correspondente a cada servidor de carga aperiódica apresentado na tabela abaixo. Use como política de atribuição de prioridades a Taxa Monotônica (RM) e assuma o servidor como descrito na tabela. Considere ainda duas requisições aperiódicas, uma da tarefa B ocorrendo no instante 4 solicitando 2 unidades de tempo, e uma requisição da tarefa A ocorrendo no instante 8 solicitando 1 unidade de tempo. Construa o diagrama descrevendo a escala de ocupação do processador e também o gráfico de capacidade associados a estes servidores.

a) Servidor DS (deferrable)

b) Servidor SS (sporadic)


Tarefas


Tempo de computação

Período

T1

2

10

T2

6

14


Servidores


Tempo de computação

Período

Servidor DS

1

5

Servidor SS

1

5



6) Considerando um algoritmo rate-monotonic:


a) Use o método de análise por demanda de tempo (time-demand analysis) para mostrar que o algoritmo rate-monotonic irá produzir uma escala viável das tarefas (6,1), (8,2), e (15,6).


b) Para o mesmo conjunto de tarefas, mude o período de uma das tarefas para obter um novo conjunto de tarefas com uma utilização total máxima e que seja viável quando escalonado usando algoritmo rate-monotonic (considere apenas valores inteiros para os períodos).



7) Em um sistema com prioridades fixas com duas tarefas periódicas T1 = (3,1) e T2 = (9,3), existe um servidor esporádico (ps,es) = (8,2). Suponha que dois jobs aperiódicos A1 e A2, ambos com tempo de execução igual a 1, cheguem no tempo 0.5 e 5, respectivamente:


a) Qual é o tempo de resposta de A2 se o servidor é um servidor esporádico simples?


b) Qual é o tempo de resposta de A2 se o servidor é um servidor SpSL?


8) Um sistema contém as seguintes cinco tarefas periódicas. As tarefas são escalonadas segundo o rate-monotonic.

T1 = (6,3,[X;2])

T2 = (20,5,[Y;1])

T3 = (200,5,[X;3[Z;1]])

T4 = (210,6,[Z;5[Y;4]])


Compare a escalonabilidade do sistema quando o protocolo de prioridade teto (priority-ceiling) é usado com relação ao protocolo NPCS.


9) Crie um conjunto com 3 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.


10) Crie um conjunto com 3 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 por algum outro teste.


11)) Considerando a tabela abaixo, usando a política Deadline Monotonic,:


Tarefas


Release Jitter

Tempo Computação

Período

Deadline

A

3

4

20

10

B

0

3

30

15

C

5

11

40

30

a) Calcule os tempos de respostas e mostre a escalonabilidade (ou não escalonabilidade) desse conjunto de tarefas utilizando algum teste exato.

b) Mostre a escala de execução, usando um diagrama de tempo, até o tempo 30.


12) 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 ]

e,X,X,X,X


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

e,Y,Y,Y,Y,Y,Y


J3: r3 = 4 C3 = 3 nenhum

e,e,e


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

e,Z,Z,Z,Z,Z


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

X, XY, XY, XYZ, XY



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) Priority Ceiling.


(d) Immediate Priority Ceiling (Ceiling Priority).



13) Considere um sistema composto por 3 tarefas periódicas, independentes, com período igual ao deadline. Mostre através de um exemplo quais podem ser as tarefas afetadas quando um job qualquer executa mais tempo do que o previsto em seu WCET. Para tanto, desenhe a linha de tempo do exemplo. O sistema é escalonado com EDF.


14) Desenhe o diagrama de tempo correspondente ao servidor esporádico apresentado na tabela abaixo. Use como política de atribuição de prioridades a Taxa Monotônica (RM) e assuma o servidor como descrito na tabela. Considere ainda duas requisições aperiódicas, uma da tarefa X ocorrendo no instante 4 solicitando 2 unidades de tempo, e uma requisição da tarefa Y ocorrendo no instante 8 solicitando 1 unidade de tempo. Construa o diagrama descrevendo a escala de ocupação do processador e também o gráfico de capacidade associado ao servidor.


Tarefas


Tempo de computação

Período

T1

2

10

T2

6

14


Servidores


Tempo de computação

Período

Servidor SS

1

5


15) Três tarefas periódicas T1, T2 e T3 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 T1.

    - Calcule os piores casos de bloqueios (Bi) a que podem estar sujeitas cada uma destas tarefas quando o Protocolo “Highest Locker Priority” ou “Immediate 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 T1.

    - Calcule os piores casos de bloqueios (Bi) a que podem estar sujeitas cada uma destas tarefas quando o Protocolo “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 T1.



Tarefas


Tempo de computação

Prioridade

Recurso R1

Recurso R2

T1

15

Alta

1


T2

16

Média

3

4

T3

20

Baixa


2


16) Considerando a tabela abaixo, desenhe a escala de tempo até o instante 20 e analise a escalonabilidade do sistema, quando usada a política Deadline Monotonic.

Considerando a tabela abaixo, desenhe a escala de tempo até o instante 20 e analise a escalonabilidade do sistema, quando usada a política Earliest Deadline First.


Tarefas

Tempo de computação

Período

Deadline


A

3

5

5

B

2

6

6

C

1

20

20


17) Desenhe o diagrama de tempo correspondente ao servidor esporádico apresentado na tabela abaixo. Use como política de atribuição de prioridades a Taxa Monotônica (RM) e assuma o servidor “Sporadic Server”. Considere ainda duas requisições aperiódicas, uma da tarefa X ocorrendo no instante 2 solicitando 2 unidades de tempo, e uma requisição da tarefa Y ocorrendo no instante 10 solicitando 3 unidades de tempo. Construa o diagrama descrevendo a escala de ocupação do processador e também o gráfico de capacidade associado ao servidor, até a conclusão das duas chegadas aperiódicas.

Tarefas Tempo de computação Período

T1 1 3

T2 2 7

Servidores Tempo de computação Período

Servidor SS 2 6