08.25.08

Extensão do algoritmo de Liu e Layland

Enviado em Artigos tagged , , , às 10:15 pm por tfraga

Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines

O artigo trata de uma extensão do clássico algoritmo de Taxa Monotônica para o caso de tarefas com deadline maior que o período. O algoritmo descrito é semi-estático e orientado a prioridades. O artigo é estruturado em seis partes, que serão descritas a seguir.

A primeira parte é a introdução. Nela os autores apresentam os conceitos básicos de tarefas e escalonadores. Apresentam também a motivação por detrás da modificação: estender o deadline além do período é uma técnica utilizada em situações de sobrecarga transiente.

A segunda parte trata de uma caracterização melhor das tarefas com deadline maior que o período. São apresentados conceitos e fórmulas que serão utilizadas principalmente na prova formal das características do novo algoritmo.

A terceira parte apresenta o algoritmo em si. A modificação divide as requisições em dois grupos: as antigas e as atuais. Para a determinação das prioridades das requisições, foram apresentadas três regras:

  1. Todas as requisições atuais possuem prioridade menor que as antigas;

  2. As prioridades de todas as requisições em cada grupo seguem as regras do algoritmo de Taxa Monotônica;

  3. Todos as requisições antigas da mesma tarefa são escalonadas e executadas de forma FIFO (First In, First Out).

É apresentada ainda uma forma de implementação desse algoritmo. Não entrarei em detalhes nesse post, mas deve-se dizer que sua implementação não requer grandes mudanças em um framework que utiliza escalonamento de Taxa Monotônica.

A quarta e a quinta parte tratam da optimalidade do algoritmo e análise de um caso especial de tarefas no qual o algoritmo não é ótimo, respectivamente. Os seguintes corolários são válidos (considere a diferença entre o deadline de uma tarefa e o seu período como δ e o tempo de processamento dessa tarefa como τ):

  1. O algoritmo é ótimo para escalonar tarefas cuja diferença entre o deadline e o período é igual a ou maior que o maior período p1 de todas as tarefas;

  2. O algoritmo é ótimo para escalonar um conjunto de duas tarefas, contanto que δ2 ≥ τ2 e δ1 ≥ p1.

Entretanto, esse algoritmo não é ótimo no caso que o deadline de uma tarefa é o dobro do seu período, para todas as tarefas do conjunto.

A última parte apresenta uma forma de tratar o caso de tratar um conjunto de tarefas que possuas tarefas que necessitem ser completadas até o seu período e outras com deadline maior que seu período. Nesse caso, as tarefas pertencentes à primeira classe são consideradas urgentes e são tratadas como tarefas antigas, o que garante a elas uma prioridade alta.

Referências

SHIN, Wei Kuan, LIU, Jane W. S., LIU, Chung L. (1993) “Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines”.

06.10.08

Java e Sistemas de Tempo Real: Vale a pena utilizar?

Enviado em Artigos tagged , às 10:10 pm por tfraga

Tradicionalmente, no desenvolvimento de sistemas de tempo real, os desenvolvedores escolhem linguagens como C, C++ e Ada para o desenvolvimento de seus projetos. Entretanto, a atual popularidade de Java faz com que vários desenvolvedores desejem trabalhar com essa linguagem também em sistemas de tempo real. Mas poderia Java ser usada para esse tipo de sistemas?

Em sua versão tradicional, não. Java possui vários fatores que introduzem um indeterminismo temporal inaceitável em sistemas de tempo real hard, como o sistema de coleta de lixo e falta de um modelo de threads baseado em prioridades. Para solucionar esses problemas, introduziu-se um conjunto de especificações para a utilização de Java em sistemas de tempo real: a Real-Time Specification for Java (RTSJ). Esse post analisará a RTSJ e algumas soluções que surgiram a partir delas: a Java Real-Time System (Java RTS), da Sun; a WebSphere Real Time¸ da IBM; e a biblioteca Javolution.

A Real-Time Specification for Java (RTSJ) e a abordagem da Sun: a Java Real-Time System (Java RTS)

A RTSJ é um conjunto de especificações de comportamento para a linguagem Java para permitir que a mesma possua comportamentos determinísticos, essenciais no desenvolvimento de sistemas de tempo real. A sua aprovação ocorreu em 2002, e a primeira implementação comercial em 2003. Algumas de suas maiores inovações são: acesso direto à memória física, threads de tempo real, e um novo modelo de gerência de memória.

O acesso direto à memória se dá através da classe RawMemory. Ela permite o acesso de dados inteiros e de ponto flutuante em endereços específicos do programa. Áreas da memória física podem ser definidas com determinadas características (por exemplo, RAM estática) e usadas para alocação de objetos [Brosgol 2003].

O sistema de threads de tempo real é subdividido em RealtimeThread e NoHeapRealtimeThread. A primeira é mais adequada a sistemas de tempo real soft, e é mais fácil de utilizar. A segunda é adequada a sistemas hard, já que não usa a heap e nem o coletor de lixo, necessitando de maior experiência em desenvolvimento de aplicações de tempo real. Cabe ressaltar que esse sistema possui 28 níveis de prioridade para as threads e foi desenvolvido para evitar completamente situações de inversão de prioridades.

O modelo de gerência de memória possui duas inovações principais: a inclusão de scoped memory e de immortal memory. A primeira é representada por um objeto que é instanciado no código e então utilizado para criar outros objetos dentro. As threads que executam dentro desse espaço de scoped memory governam o tempo de vida desses objetos. Quando não há threads no espaço de scoped memory, todos os objetos que estão dentro desse espaço são desalocados imediatamente [Bruno 2007]. Já objetos criados na segunda nunca estão sujeitos à coleta de lixo e persistem até o fim da aplicação. Portanto, esse segundo tipo de memória deve ser utilizado com muito cuidado e parcimônia.

A Java RTS foi a primeira implementação comercial totalmente de acordo com a RTSJ. Desenvolvida pela Sun, a primeira versão não contava com um sistema de coleta de lixo em tempo real e utilizava uma versão otimizada da HotSpot JVM. A versão 2.0 incluiu um sistema de coleta de lixo em tempo real. Esse pode apresentar uma vazão (throughput) menor que coletor que não seja de tempo real, mas é mais determinístico e possui métodos para otimizá-lo para cada aplicação.

A solução da IBM: WebSphere Real Time

A base da solução da IBM para sistemas de tempo real é a Máquina Virtual de tempo real (real-time VM) J9 estendida com a tecnologia Metronome de coleta de lixo em tempo real, compilação Ahead of Time, e total suporte à RTSJ, tudo isso sendo executado em um sistema operacional Linux de tempo real em desenvolvimento [Porpora e Fulton 2006]. Essa solução visa atacar uma das maiores causas de indeterminismo em Java, a coleta de lixo. Examinemos melhor essa solução.

A tecnologia Metronome permite coleta de lixo com determinismo “hard” na ordem de menos de um milissegundo [Porpora e Fulton 2006]. Ao manter a coleta de lixo mesmo em sistemas de tempo real, a gerência de memória é bastante facilitada para os desenvolvedores, o que torna a solução da IBM muito atrativa.

A compilação Ahead of Time e o suporte à RTSJ aperfeiçoam ainda mais o desenvolvimento de sistemas. A primeira permite a pré-compilação de código, que pode ser utilizada para aumentar o desempenho, enquanto a segunda permite utilizar, entre outras técnicas, escalonamento de threads baseado em prioridades e manipuladores de eventos assíncronos.

O desenvolvimento do sistema operacional Linux de tempo real visa oferecer um suporte melhor aos sistemas desenvolvidos. Implementações prévias de sistemas Linux de tempo real impunham restrições sobre o uso dos processadores por tarefas de tempo real, ou funcionavam como extensões do kernel. A IBM visa aperfeiçoar o kernel para oferecer maior suporte a tarefas de tempo real e remover essas restrições.

A biblioteca Javolution

A biblioteca Javolution foi desenvolvida principalmente por Jean-Marie Dautelle. Seu código é aberto baseado na licença BSD. Ela provê implementações alternativas determinísticas temporalmente e compatíveis com a RTSJ das interfaces da biblioteca padrão [Dautelle 2007]. Ela parte da seguinte premissa: as bibliotecas padrões não são adequadas para aplicações de segurança críticas, pois não são determinísticas em relação ao tempo; deve-se, portanto, desenvolver-se novas bibliotecas que sejam capazes de prover as mesmas funcionalidades das originais, mas de forma determinística, para poderem ser usadas em sistemas de tempo real. Essas bibliotecas devem ser totalmente compatíveis com a RTSJ (já que algumas das bibliotecas originais não são seguras para se utilizar com a NoHeapRealtimeThread).

A Javolution atualmente provê: implementações com determinismo temporal hard e alta eficiência das classes util, lang, text, io e xml; implementações em Java de Structs e Unions para facilitar a interface com aplicações em C/C++; serialização em XML com melhor desempenho e sem geração de lixo; entre outras coisas. Cabe lembrar que, por ser uma biblioteca, a Javolution pode ser utilizada pelas duas soluções acima apresentadas, ou mesmo em aplicações que não sejam de tempo real (para melhorar a previsibilidade e/ou a performance, já que algumas classes implementadas possuem desempenho melhor que as originais).

Conclusão

A partir do lançamento da RTSJ, desenvolver sistemas de tempo real utilizando a linguagem Java tornou-se uma realidade. Desenvolvedores agora possuem uma nova alternativa atraente a ser considerada para os projetos de sistemas de tempo real. Como exemplo prático de utilização de Java em sistemas de tempo real, pode-se citar a Marinha dos EUA, que utiliza a solução da IBM no seu projeto “Total Ship Computing Environment“, utilizado nos novos destroyers [Porpora e Fulton 2006].

Referências

Bosgrol, Benjamin M. (2003) “Introduction to Real-Time Java”, http://www.embedded.com/story/OEG20030430S0042, Maio.

Bruno, Eric. (2007) “Go Inside the Java Real-Time System”, http://www.devx.com/Java/Article/33475/0/page/1, Junho.

Dautelle, Jean-Marie. (2007) “Fully Time Deterministic Javatm“, http://javolution.org/doc/AIAA-2007-6184.pdf, Maio.

Fulton, Mike S. e Porpora, Gregory A. (2006) “Real-Time Javatm Solutions for Highly Deterministic Applications”, http://www.alphaworks.ibm.com/g/g.nsf/img/articles/$file/intrortjava.pdf, Maio.

Leituras adicionais

Bosgrol, Benjamin M. (2003) “Ada and Java: real-time advantages”, http://www.embedded.com/columns/technicalinsights/16100316?_requestid=135223, Maio.

Fulton, Michael S., Hard, Darren V. e Porpora, Gregory A. (2006) “IBM WebSphere Real Time: Providing predictable performance”, ftp://ftp.software.ibm.com/software/webservers/realtime/pdfs/WebSphere_Real_Time_Overview.pdf, Junho.

Heiss, Janice J. (2006) “Programming in Real-Time Specification for Java (RTSJ): A Conversation with Distinguished Engineer Greg Bollella”, http://java.sun.com/developer/technicalArticles/Interviews/Bollella_qa2.html, Maio.

Lammers, David. (2005) “IBM sets real-time tempo for Java code with Metronome”, http://www.embedded.com/news/embeddedindustry/170703019?pgno=1, Junho.

Mikhalenko, Peter. (2006) “Real-Time Java: An Introduction”, http://www.onjava.com/pub/a/onjava/2006/05/10/real-time-java-introduction.html?page=1, Junho.

Wikipedia. “Real Time Java”, http://en.wikipedia.org/wiki/Real_time_Java, Maio.