Extensão do algoritmo Rate-Monotonic

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.

Vale a pena usar Java em aplicações de tempo-real?

Para responder a essa pergunta, foi feito um levantamento das vantagens e desvantagens da utilização da tecnologia Java para tempo-real. Também buscou-se as tentativas de tornar Java apta para atuar no campo dos sistemas de tempo-real. Um produto da IBM que utiliza a tecnologia Java é descrito. Por fim, com o que foi levantado, pode-se tirar uma conclusão sobre a viabilidade ou não do Java para tempo-real.

Vantagens

Portabilidade

A manutenção das ferramentas apropriadas para trans-desenvolvimento (cross-development) para todos os tipos diferentes de microprocessadores é que se pode chamar de um “pesadelo administrativo”. Garantir que todas as combinações de componentes de hardware e software trabalhem corretamente no sentido de tempo-real é um desafio bastante difícil. O processo de desenvolvimento seria muito mais fácil se os programadores pudessem escrever seus códigos em uma linguagem que fosse portátil entre todas essas arquiteturas, mantendo uma versão única de seus sistemas.

Tolerância à Falhas

Na presença de falhas no nó ou na rede, freqüentemente torna-se necessário redistribuir informações e carga de trabalho. Seria bastante desejável poder dispor de um ambiente de execução no qual fosse permitido, de forma transparente (ou o mais simples possível), realizar essa transferência, mesmo considerando que os outros nós podem conter arquiteturas e sistemas operacionais heterogêneos, tornando-os capazes de executar quaisquer das tarefas que precisem ser executadas.

Adaptabilidade Dinâmica

Outra dificuldade freqüente na manutenção de sistemas em tempo- real embarcados é que os refinamentos de software incrementais tem de ser instalados sem que o sistema seja desligado para uma reinicialização completa. Isso inclui aplicações que tem de prover serviços ininterruptos para sua comunidade de usuários (ex.: controle de tráfego aéreo, centrais comutadoras de telefonia, e reconhecimento militar), e aplicações para as quais o custo de desligamento (downtime) são proibitivos (ex.: controle de reatores nucleares, e sistemas de automação de manufatura).

De forma resumida, o Grupo de Requerimentos considerou as pontos abaixo como sendo a base para os requerimentos e motivações para uso de Java pela comunidade de tempo-real [Carnahan 1999]:

• O alto nível de abstração presente em Java conduz a uma melhora na produtividade dos programadores (embora seja reconhecido que este compromisso comprometa a eficiência de tempo de execução). Java é claramente mais fácil de ser dominada do que C++.

• Java é relativamente segura, mantendo componentes de software (incluindo a própria Java Virtual Machine) protegidos entre si.

• Java suporta o carregamento dinâmico de novas classes. Java é altamente dinâmica, oferecendo suporte à criação de objetos e de threads em tempo de execução. As tecnologias ligadas à Java dão suporte a criação de aplicações distribuídas.

• Java foi projetada para dar suporte à integração de componentes e reutilização. As tecnologias ligadas à Java foram desenvolvidas com considerações criteriosas, utilizando conceitos e técnicas que foram averiguados pela comunidade.

• A linguagem de programação Java e a plataforma Java dão suporte à portabilidade de aplicações. Java oferece uma semântica de execução bem-definida, o que torna possível essa portabilidade.

Desvantagens

Aplicações comuns em Java rodando em JVM comuns em um sistema operacional de uso geral, só consegue atender requisitos soft de tempo (na casa das centenas de milissegundos). Alguns problemas do Java estão relacionados a impossibilidade de obter um determinismo devido ao gerenciamento automático de memória (garbage collection), carregador e compilador de classes e gerenciador de threads.

Carregador e compilador de classes

A JVM somente faz o carregamento de uma classe quando esta é referenciada a primeira vez. Esse carregamento pode demorar um certo tempo (geralmente mais que 10 milissegundos) dependendo de alguns fatores, dentre eles, o tamanho da classe. Se for preciso carregar várias classes, o atraso para fazer isso, pode gerar um atraso bastante significante. É preciso então fazer o projeto para o carregamento antecipado de todas as classes, porém a JVM padrão não permite isso, fazendo com que seja necessário o carregamento manual das classes.

A compilação de classes para código nativo encontra um problema similar ao do carregamento. A maioria das JVM modernas interpretam métodos Java, compilando somente métodos frequentemente executados para código nativo. A não compilação imediata poupa tempo ao iniciar a aplicação, porém é terrível para aplicações com requisitos hard de tempo, pois métodos executados inicialmente na fase de interpretação executam mais devagar. Um atenuante para isso pode ser a criação de um método que utilize o compilador de classes para compilar os métodos ao iniciar a aplicação.

Coletor de Lixo

Os coletores de lixo tradicionais podem gerar atrasos grandes atrasos nas aplicações, que são virtualmente impossíveis de prever. Atrasos de centenas de segundos não são incomuns de acontecerem. Uma solução é a prevenção do uso do coletor de lixo com a criação de objetos que possam ser reutilizados, ajudando a assegurar que a memória heap da JVM nunca irá se esgotar. Essa solução, infelizmente, é falhas, pois não permite o uso de muitas bibliotecas da JDK e de terceiros que fazem uso freqüente da criação de objetos temporários.

Gerenciamento de Thread

A Java padrão não garante nem o escalonamento e nem a prioridade das threads. Uma aplicação que não tem como assegurar que uma thread de menor prioridade não será escalonada na frente de uma de maior prioridade. Para compensar, um programador deve participar sua aplicação em diversas aplicações que devem ser executadas com diferentes prioridades pelo sistema operacional. Porém esta técnica aumenta a sobrecarga e a comunicação entre as thread fica muito mais difícil.

Especificação de Java para Tempo Real – Real Time Specification for Java (RTSJ)

Para resolver esses e outros problemas, iniciando em junho de 1998 e culminando em novembro de 20011 com a publicação da especificação de Java para Tempo Real – Real Time Specification for Java (RTSJ). É também definido de forma clara e precisa, um vocabulário de tempo-real, com conceitos antes usados de forma contraditória, e as vezes até mesmo errônea, pela comunidade de usuários, desenvolvedores e revendedores. Nela são feitas algumas ampliações na definição original da linguagem Java, as quais são descritas abaixo:

Escalonamento

O RTSJ introduz o conceito de objeto escalonável. Qualquer instância de qualquer classe que implemente a interface Schedulable é um objeto escalonável e seu escalonamento e despacho serão gerenciados pela instância de Scheduler da qual ele tenha uma referência.

Com a RTSJ, prioridades e um escalonador preemptivo de prioridades fixas com suporte a herança de prioridades é utilizado. Este escalonamento possibilita que a thread de maior prioridade sempre esteja a tarefa que esteja executando, e continuará até que libere o processador voluntariamente ou seja preemptada por uma thread de maior prioridade.

Thread

A RTSJ adiciona o suporte a duas novas classes para thread: RealtimeThreads e NoHeapRealtimeThreads (NHRTs). Estas novas classes provêem suporte a prioridades, comportamento periódico, deadline com manipuladores que podem ser acionados quando o deadline é excedido, e o uso de outras áreas de memória que não a heap. NHRTs não podem acessar a head, e diferentemente de outros tipos de threads, não precisam ser interrompidas ou preemptadas pelo coletor de lixo. Sistemas de tempo-real geralmente usam a NHRTs com maior prioridade para taregas com rigorosos requisitos de latência, e RealtimeThreads para tarefas com requisitos de latência que podem ser acomodados pelo coletor de lixo e threads Java regulares para qualquer outra finalidade.

Gerenciamento de Memória

A RTSJ define dois tipos de áreas de memória para suplementar a head padrão do Java: imortal e de escopo. Objetos alocados na área de memória imortal podem ser acessados por todas as threads e nunca são coletados, representando um recurso limitado para ser usado com cuidado. Áreas de memória de escopo podem ser criadas e destruídas pelo programador. Cada área desta é alocada com um tamanho máximo e pode ser usada para alocação de objetos. Para assegurar a integridade de referência entre objetos, regras regulam como objetos em uma área de memória (heap, imortal, escopo) podem referenciar objetos de outra área de memória. Mais regras definem quando objetos em um escopo são finalizados e quando a área de memória é reusada. Por causa desta complexidade, o uso de áreas imortais e de escopo deve ser limitado a componentes que não podem tolerar as pausas do coletor de lixo.

Sincronização e Compartilhamento de Recursos

A RTSJ inclue suporte a herança de prioridade para gerenciar a sincronização quando ela ocorre, e provê a capacidade de trheads se comunicarem sem sincronização usando filas de espera livre de leitura e escrita.

Tempo e clock

As novas classes HighResolutionTime e Clock encapsulam os serviços de tempo de maior resolução de clocks.

Gerenciamento de Eventos Assíncronos

A RTSJ inclue suporte para manipulação de eventos assíncronos acionados por um número de fontes incluindo tempo, sinais do sistema operacional, deadlines esquecidos e outros tipos de eventos definidos pela aplicação.

Produto

O pessoal da IBM afirmam que Java Linux para tempo real realmente funcionam através de um caso concreto, que é a implementação pela IBM e Raytheon dos sistemas de controle (incluem-se command-and-control, navegação, detecção de alvos, controle de armas e sistema de radar) da nova geração de destroyers da marinha americana, a série DDG 1000. Este sistema é baseado em servidores blade, operando WebSphere e Java, em cima de Linux, em tempo real.

A implementação da IBM WebSphere Real-Time Java é compatível com a Real-Time Specification for Java (RTSJ) e a extensão para tempo-real do Linux é compatível com o padrão Portable Operating System Interface (POSIX). Ele utiliza um coletor de lixo chamado Metronome, que garante baixos tempo de pausa pelo coletor, como também o uso do programa não menos que certa porcentagem durante uma janela de tempo específica, graças a incrementos de baixas pausas individuais no ciclo do coletor de lixo, bem como mantendo a taxa de utilização ao longo da janela de tempo.

A tecnologia também está sendo avaliada por outros ramos do Departamento de Defesa americano, Departamento de Segurança Interno, Agencias de Inteligência e outras indústrias não governamentais como Serviços Financeiros e Telecomunicação, onde segurança e soluções de alta previsibilidade são requisitos. A IBM também faz a propaganda de se basear em um padrão industrial forte de soluções Java e Linux para tempo real e que diminui os custos de desenvolvimento, riscos, como também o custo total do ciclo de vida.

Conclusão

Com a especificação de Java para tempo real RTSJ, fornecendo técnicas para melhorar a sua utilização em tempo real com modificações na JVM, a sua implementação sendo desenvolvida por grandes empresas como a IBM, e os produtos desenvolvidos a partir dela sendo utilizados por grandes empresas e órgãos importantes do governo americano, mostra-se que a linguagem Java está pronta para concorrer com linguagens mais tradicionais para tempo real como C, C++, ADA e outras.

A marinha americana não estaria utilizando um produto que não fosse eficiente para o controle do arsenal de um destroyer (navio de guerra), e importantes empresas financeiras não deixariam que um sistema falho controlasse as transações, ou qualquer controle que pudesse resultar em perdas de até milhões de dólares.

Com a garantia do coletor de lixo trabalhando de modo determinístico, que era uma das maiores desvantagens do Java, e outros modificações na JVM, a previsibilidade no desenvolvimento de aplicações passa a ser garantido.

Referências:

[1] TAURION, Cezar. Implementando Linux e Java em tempo real. Disponível em: <http://www2.eletronica.org/artigos/eletronica-digital/implementando-linux-e-java-em-tempo-real>

[2] IBM and Raytheon Deliver Technology Solution for DDG 1000 Next Generation Navy Destroyers. Disponível em: <http://www-03.ibm.com/press/us/en/pressrelease/21033.wss>

[3] Creating predictable-performance Java applications in real time. Technical overview White paper . Disponível em: <ftp://ftp.software.ibm.com/software/webservers/realtime/pdfs/WebSphere_Real_Time_Technical_Overview.pdf>

[4] Programming in Real-Time Specification for Java (RTSJ): A Conversation with Distinguished Engineer Greg Bollella. Disponível em: <http://java.sun.com/developer/technicalArticles/Interviews/Bollella_qa2.html>

[5] CUNHA, Paulo Roberto. RTSJ - Programação em Tempo-Real através da Ampliação e Especificação da Plataforma JAVA . Disponível em <http://www.cci.unama.br/paulo.cunha/academia/academia_arquivos/Papers/RealTimeDistributedJava.pdf>