Escalonamento cooperativo em software embarcado (2/2)

sch

Escalonador cooperativo para soft real-time

Os sistemas com requisitos de tempo-real são classificados em soft, firm e hard, apesar de estes critérios não serem bem estabelecidos. Em sistemas ‘hard’, os requisitos de tempo precisam ser estritamente atendidos sob pena da falha total. No soft/firm, o não cumprimento das deadlines é tolerado em alguma medida, ocasionando degradação da qualidade do sistema sem levar à falha total.

Na última publicação descrevi algumas arquiteturas de escalonadores (schedulers) que na sua melhor forma executava toda tarefa agendada no mesmo intervalo de tempo, e também poderia reagendar ou descartar a tarefa.

Vou estender esta última arquitetura um pouco mais, agora ao invés de informar ao escalonador somente o endereço da função, também vou informar uma frequência de execução que deve ser cumprida.

Como agora precisamos contar os ticks do relógio para atender aos requisitos temporais, precisaremos de uma referência de tempo. Para isso podemos usar um temporizador que gere uma interrupção a cada Q segundos. O serviço que atende esta interrupção informa ao escalonador que houve um tick de relógio. O menor intervalo de tempo entre um tick e outro é por vezes chamado de quantum e é uma escolha importante de projeto.

O escalonador será composto basicamente por um buffer circular que aponta para os processos, e um disparador que fica responsável por arbitrar qual processo está pronto para ser disparado.

A figura abaixo ilustra a arquitetura proposta:

sch

Cada estrutura de processo é declarada com um período (em ticks do sistema). Quando o processo é adicionado ao buffer circular, um inteiro é inicializado, em tempo de execução, com o período informado na chamada de sistema. A cada interrupção gerada pelo tick do relógio, este número é decrementado e pode ser visto como uma deadline. A cada ciclo de máquina, o árbitro varre pelo processo com o menor prazo de execução, para dispará-lo em seguida (colocado na posição inicial do buffer). A função evocada retorna REPEAT ou ONESHOT, caso queira ou não ser reagendada, ou FAIL como código de erro. O código abaixo mostra o cabeçalho do programa (desisti de escrever os códigos no texto da publicação, o editor do WordPress é muito ruim!):

header

Na estrutura process a variável deadline é com sinal para poder registrar o atraso, quando ocorrer. Além disso, se a tarefa for reagendada, o contador do novo processo apontado no buffer vai iniciar subtraindo este atraso para ajustar o atraso total do sistema.

buffer

Quando o disparador varre o buffer para selecionar o processo com a menor deadline, ele também organiza a fila em ordem decrescente de deadlines. Se o processo anterior retornou FAIL, o escalonador analisa se o deadline do próximo processo a ser executado é menor que o período do atual. Caso verdadeiro ele dispara o processo mais uma vez. Por isso foi necessário organizar o buffer sempre em ordem crescente de atraso, para garantir que o processo atual seja comparado com o mais crítico da fila.

Quando a menor deadline da fila for maior que 0,  será necessário esperar até o contador chegar a zero, e uma boa prática é utilizar este tempo para colocar o processador em um modo de baixo consumo (verificando no manual do processador se neste modo ele ainda é sensível à interrupção que gera o tick!).

escalonador

escalonador2

A configuração do temporizador que realiza a interrupção para gerar o tick do relógio depende da arquitetura. O código abaixo escrevi para um ATMega328p rodando a 16MHz. Ele está gerando o tick a cada 4ms.

isr

Abaixo as rotinas para habilitar e sair do modo IDLE:

powersch-2.jpg

A função schInit() inicializa o scheduler, zerando os índices do buffer e inicializando o temporizador para geração do tick do sistema.

O programa principal de um sistema utilizando este scheduler teria a seguinte cara:

mainsch

Aviso: o código acima tem propósitos didáticos e não é um artefato validado. Não há nenhuma garantia de funcionamento livre de erros, e o autor não se responsabiliza pelo uso.

O texto desta postagem é original. Os seguintes livros foram consultados para sua elaboração:
[1] Programação de sistemas embarcados, Rodrigo Almeida e outros.
[2] Real-Time Systems Development, Rob Williams 
[3] Patterns for Time-Triggered Embedded Systems,  Michael J. Pont

Escalonamento cooperativo de tarefas em software embarcado (1/2)

sch

Arquiteturas para escalonamento cooperativo de tarefas

Na publicação anterior escrevi sobre o uso do chamado super-loop e suas limitações quando falamos em atender requisitos de tempo em uma planta. Além disso, também mostrei que podemos utilizar interrupções disparadas por temporizadores para garantir que tarefas sejam executados em intervalos definidos. Neste caso, para cada tarefa periódica precisamos de um temporizador. Em sistemas um pouco mais complexos, ambas as arquiteturas são muito suscetíveis a erros e de difícil manutenção e reuso/extensão.

Um escalonador é um bloco de código que permite ao programador inserir tarefas que serão chamadas em intervalos regulares sem que seja necessário um serviço de interrupção (ISR) dedicado a cada uma delas (podemos pensá-lo como um ISR compartilhado). Quando comparado ao super-loop, o escalonador permite que o programador não se preocupe em manejar os delays entre uma tarefa e outra para garantir a periodicidade desejada. Quando comparado a utilização com temporizadores, o uso de um escalonador é menos custoso pois não necessitamos de um temporizador para cada tarefa periódica.

Existem dois tipos gerais de escalonadores os cooperativos e os preemptivos. Os escalonadores cooperativos simplesmente executam uma tarefa após a outra, com ou sem deadline no tempo, e são implementados em sistemas monotarefas. Os escalonadores preemptivos indexam prioridades a cada uma das tarefas, e caso um evento que chame uma tarefa de maior prioridade ocorra durante a execução de uma menos prioritária, esta é pausada e retomada após a conclusão daquela. Por isso estes escalanadores são ditos multitarefas. (A tarefa atual não precisa terminar para que outra seja executada. Guardadas as devidas proporções e aplicabilidade, o MS Windows é multitarefas pois o usuário do PC pode alternar entre uma tarefa e outra, e o sistema operacional chaveia o contexto do microprocessador – alterna entre um processo e outro – dando a impressão de que todas as tarefas estão sendo executadas ao mesmo tempo. O antigo MS-DOS é monotarefa. )

Vou explorar aqui algumas implementações para escalonadores cooperativos.

Escalonamento cooperativo utilizando máquinas de estados

Independente da arquitetura do escalonador, se ele for cooperativo suas operações podem ser descritas da seguinte forma:

  • as tarefas são agendadas para ocorrer em um determinado período de tempo

  • quando o agendamento ocorre, a tarefa é armazenada em uma lista de espera

  • quando a tarefa atual termina, a próxima é executada (se houver)

  • após a completude das tarefas, o controle do sistema volta ao escalonador

Se a solução a ser implementada não tiver padrões rígidos de resposta temporal, a utilização de uma máquina de estados garante a facilidade no reuso e manutenção do código.

Supomos um programa que utilize um display, um teclado e uma porta serial. A porta serial responde aos comandos vindos pelo teclado ou pela serial. O display é atualizado periodicamente. A máquina de estados pode ser modelada da seguinte forma (figura retirada de [1]):

fsm001

Uma implementação em C para esta FSM poderia ser:

#include <serial.h>
#include <keypad.h>
#include <display.h>
#define LE_TECLADO 0
#define LE_SERIAL 1
#define ESCREVE_SERIAL 2
// programa principal
void main(void)
{
   kpInit();
   displayInit();
   serialInit();
while (1)
{
 // atualiza display
    displayUpdate();
    switch(state)
    case LE_TECLADO:
    if (kpRead() != 0) // chegou comando
    {
    /* mais processamento */
      state = ESCREVE_SERIAL;
    }
    else
    {
      state = LE_TECLADO;
    }
    break;
    case LE_SERIAL:
    if (serialRead() != 0) // chegou comando
    {
      state = ESCREVE_SERIAL;
    }
    else
    {
      state = LE_SERIAL;
    }
   break;
   case ESCREVE_SERIAL:
   /* processa comando e responde */
   break; 
   default: 
     state=LE_TECLADO;
     break;
}

Perceba que como a função de atualizar o display precisa ser executada intermitentemente entre um estado e outro, ela pode ser acomodada antes do switch-case.

Neste caso, as funções serão executadas até a completude antes de passar a vez. Uma característica desejável de um sistema embarcado é o determinismo. Podemos então configurar um período de tempo fixo para todas as tarefas ocorrerem. Este período obviamente precisa ser maior que o pior caso de tempo de execução.

// programa principal
void main(void)
{
  kpInit();
  displayInit();
  serialInit();
  while (1)
  {
    // atualiza display
     displayUpdate();
     timerInit(300); // liga contador que vira a cada 300 ms 
     switch(state) 
     { 
      case LE_TECLADO: 
        if (kpRead() != 0) // chegou comando 
        { 
        /* algum processamento */ 
          state = ESCREVE_SERIAL; 
        } 
        else 
        { 
          state = LE_TECLADO; 
        } 
        break; 
     case LE_SERIAL: 
        if (serialRead() != 0) // chegou comando 
        { 
          state = ESCREVE_SERIAL; 
        } 
        else 
        { 
          state = LE_SERIAL;
        }
        break; 
     case ESCREVE_SERIAL: 
       /* processa comando e responde */ 
       break; 
     default: 
       state=LE_TECLADO; 
       break; 
  } 
  timerWait(); // espera o contador virar 
}

A desvantagem aqui é o tempo ocioso que o processador espera “somente” para padronizar as tarefas. Porém perceba que passamos de uma arquitetura cujo tempo de execução era difícil de prever para uma com tempo bem definido, e isto é um ganho enorme. O tempo livre aliás poderia ser utilizado para colocar o sistema em baixo consumo de energia, o acordando novamente com a interrupção do temporizador. Esta arquitetura é uma boa escolha para hardwares limitados em memória.

Escalonamento cooperativo com ponteiros para funções

Collins Walls no seu blog descreve o que diz ser um RTOS de uma linha, que basicamente utiliza um ponteiro para funções.

#define NTASKS 3
// pool de funções
void (*tasklist[NTASKS])() = {alpha, beta, gamma};
int taskcount;
void main()
{
  while (1)
  {
  // dispatcher
  for (taskcount=0; taskcount<NTASKS; taskcount++)
  {
   (*tasklist[taskcount])();
  } 
}

Apesar de simples, esta estrutura nos fornece muitos conceitos úteis. O uso de ponteiros para função já nos permite imaginar que as informações das tarefas a serem executada estarão armazenadas em algum espaço da memória, e o escalonador fica responsável por buscá-las e executá-las, sob alguma lógica de controle. Neste caso, é simplesmente a ordem do endereço das funções na matriz de ponteiros tasklist. Mas poderíamos adicionar mais critérios de escolha. Talvez um deadline temporal, informação de prioridade ou delay inicial.

Poderíamos garantir que todas as tarefas fossem executadas em um mesmo intervalo de tempo, com a mesma técnica aplicada na máquina de estados.

Poderíamos também criar uma pequena API:

// para adicionar tarefas

#define N_TASK 4 // numero de tarefas
typedef void(* ptrFunc)();
int pos;
void() addTask(ptrFunc newFunc)
{
  if (pos < N_TASK-1) // verifica se ha espaço no vetor
  {
    tasklist[pos] = newFunc;
  }
    pos++; //incremente posicao
}
// para disparar o escalonador
void sch_loop(void)
{
  int i;
  while(1)
  {
    for(i=0;i<N_TASK-1;i++)
    { 
      (*tasklist[i])();
    }
  }
}
// inicializa sch
void sch_init()
{
 pos=0;
}

E aí nosso código principal seria:

void main();
{
 schInit();
 addTask(alpha);
 addTask(beta);
 addTask(gama);
 schLoop();
}

Esta codificação parece ser desnecessária para executar três funções em fila, sem nenhum critério. O super-loop resolveria. Concordo, porém é o esqueleto de uma arquitetura que pode ser estendida para criar um scheduler mais robusto.

Executando processos uma única vez ou indefinidamente

No código apresentado as tarefas serão executadas na mesma ordem, ad infinitum. É interessante informarmos ao escalonador se a tarefa que acaba de retornar quer ou não ser executada ciclicamente. Para isso podemos criar códigos de retorno para as funções:

#define ONESHOT 0;
#define FAIL 1;
#define REPEAT 2;

Para executar processos uma única vez, precisamos poder removê-los do vetor de processos dinamicamente. Para isso, vamos transformar o vetor tasklist num buffer circular. As funções são inseridas no início do buffer e executadas em ordem. Caso uma função retorne REPEAT ela é inserida ao final do buffer. As tarefas são (re)agendadas dinamicamente.

Assim, precisamos alterar a função addTask para controlar o buffer tasklist de forma circular:

char addTask(ptrFunc newFunc)
{
 if ((last+1)%(N_TASK+1) != first)
 {
   tasklist[last] = newFunc;
   last=(last+1)%(N_TASK+1);
   return 0;
 }
 else 
 {
   return 1; //error
 }
}

A função schLoop agora precisa checar pelo valor de retorno do processo que acabou de executar. Se ele for REPEAT, ele é armazenado ao final do buffer.

void schLoop()
{
 while (1)
 {
   if (first != last) // tem algo
   {
     if ((*tasklist[first])() == REPEAT)
     {
       addTask(tasklist[first]); // reagenda
     }
      first=(fist+1)%N_TASK; // proximo processo
   }
 }
}

No próximo texto irei estender este escalonador para atender requisitos temporais de um sistema soft real-time.

O texto desta postagem é original. Os seguintes livros foram consultados para sua elaboração:
[1] Programação de sistemas embarcados, Rodrigo Almeida e outros.
[2] Real-Time Systems Development, Rob Williams 
[3] Patterns for Time-Triggered Embedded Systems,  Michael J. Pont