Artigo: Fault-Tolerant Rate-Monotonic First-Fit Scheduling in Hard-Real-Time Systems
O artigo propõe uma extensão para o algoritmo Rate Monotonic Fist-Fit (RMFF), para que este seja tolerante a falhas. A justificativa do artigo é que sistemas hard de tempo-real precisam de uma performance previsível, mesmo que haja a ocorrência de falhas.
O artigo faz um apanhado formal sobre as definições do problema de escalonamento, o modelo de tolerância a falhas, o algoritmo Rate Monotonic (RM) e RMFF, e do Completion Time Test (CTT). O CTT é um teste suficiente e necessário.
O algoritmo RMFF é resumido neste artigo como uma generalização do Rate Monotonic para permitir o uso em sistemas com multiprocessadores. Esse algoritmo faz um particionamento das tarefas, tal que elas são alocadas para os processadores seguindo a ordem de prioridade do RM e depois todas as tarefas alocadas para o mesmo processador são escalonadas com o algoritmo do RM.
No artigo, tolerância a falha é implementada usando uma técnica de duplicação em que cada tarefa escalonada no processador tem ou um backup ativo ou um backup passivo escalonado em um processador diferente. Uma cópia ativa é sempre executada, enquanto uma cópia passiva é executada somente em caso de falha. Essa seria a técnica de replicação passiva. Porém, também existe uma outra técnica chamada de replicação ativa, em que o mesmo conjunto de tarefas é executada em dois ou mais conjuntos de processadores, tendo cada tarefa primária uma cópia ativa de backup, e caso alguma falhe, as demais continuam sua execução.
Primeiramente, o artigo considera a capacidade do algoritmo Rate-Monotonic de atender os prazos das tarefas no caso de uma falha no processador. O CTT é estendido para verificar a escalonabilidade em um único processador de um conjunto de tarefas que incluem cópias de backup. Em seguida, estende o algoritmo RM, onde todas as tarefas, incluídas as cópias de backup, são consideradas na ordem de prioridade do RM e alocadas ao primeiro processador em que se encaixam.
O algoritmo proposto determina quais tarefas devem utilizar a duplicação ativa
e quais podem usar a duplicação passiva. A duplicação passiva é preferível sempre que possível, até para superlotar cada processador com muitas cópias passivas cujas cópias primárias são atribuídas para diferentes processadores. Mais ainda, o espaço alocado para cópias ativas é requisitado assim que uma falha é detectada. Superlotação de cópias passivas e desalocação de cópias ativas permitem muitas cópias passivas serem escalonadas compartilhando o mesmo tempo de intervalo no mesmo processador, ainda reduzindo o número total de processadores necessários. Estudos com simulação revelam uma notável economia dos processadores em relação a aqueles que precisam fazer uso da duplicação ativa em que a escala do caso de não tolerância a falhas é duplicada em dois conjuntos de processadores.
Nenhum comentário:
Postar um comentário