Padrões de design para comunicação interprocessos em software embarcado (2/3)

«Primeira parte»

4.3. Queuing Pattern

Quando tasks têm baixo acomplamento temporal, i.e., virtualmente1 o tempo em que um processo consumidor leva para resgatar o resultado de um processo produtor não é condição para diferenciar falha de sucesso, o padrão de Message Queueing é bastante comum.

O processo produtor envia uma mensagem a uma fila (um buffer, normalmente circular) e algum tempo depois o processo consumidor resgata esta mensagem para seguir adiante. A mensagem pode ser desde um simples booleano ou qualquer outra estrutura mais complexa.

1 isto não significa que o sistema não tenha condições temporais. Significa somente que determinadas tasks não têm relação temporal rígida entre si naquele ponto de sincronização (coordenação).

Figura 10. Message Queue para coordenar processos [2]
Figura 11. Generalização do padrão Queuing em UML

4.3.1. Rationale

Se os processos são fracamente acoplados no tempo, podemos coordená-los (ou sincronizá-los) com um mecanismo assíncrono: um processo envia a mensagem e o outro lê “quando puder”.

4.3.2 Elementos

Na Figura 11, diversas tarefas QTask compartilham uma única MessageQueue. Um Mutex agregado a esta fila de mensagens, coordena o acesso de cada tarefa à fila de mensagens. A fila tem QUEUE_SIZE elementos do tipo Message, que podem ser qualquer dado/comando – desde um simples booleano até uma PDU do tipo CAN, por exemplo. Este tamanho deve comportar o pior caso para filas no sistema1. Poderíamos dispensar o Mutex se agregássemos a cada processo a sua própria caixa de mensagens, obviamente ao custo de utilizarmos mais memória.

1 Um dos métodos empregados para calcular o tamanho da fila é o Teorema de Little

4.3.3. Implementação

No que diz respeito à complexidade, este tipo de mecanismo de IPC é relativamente simples, mas existem muitas variantes. Algumas mensagens podem ser mais prioritárias que outras, em sistemas complexos o tamanho da fila é difícil de ser optimizado e algumas implementações fazem uso de alocação dinâmica (o que em embarcados, é controverso) ou até mesmo guardam mensagens pouco prioritárias no sistema de arquivos [1]. A utilização de linked lists para implementação também é uma abordagem que conta com a flexibilidade do próximo item a ser lido ser passado por referência, e com esta flexibilidade também os potenciais problemas que o extensivo uso de ponteiros trás.

Neste artigo um scheduler cooperativo manejava as tarefas em fila, onde aquelas mais urgentes (baseados na deadline) eram colocadas no início da fila. Fundamentalmente isto é um mecanismo de comunicação interprocessos do padrão queueing: a fila coordena o disparo dos processos que concorrem para utilizar um recurso: o microprocessador.

4.3.4. Exemplo

A Figura 12 mostra um sistema, em que sensores de determinados gases compartilham um queue para registrar os valores medidos na estrutura de dados GasData. Um GasDataQueue tem GAS_QUEUE_SIZE elementos do tipo GasData. Este por sua vez contém um enum GAS_TYPE.

Figura 12. Queing Example [1]

O programa GasDataQueue.c é o núcleo deste design pattern, com os métodos para incluir novos dados na fila e remover os antigos (este código mostra uma boa implementação de buffer circular, um workhorse em sistemas embebidos). A Figura 12 nos diz que duas threads, GasProcessingThread e SensorThread, compartilham o recurso GasDataQueue, como consumidor e provedor respectivamente.

A SensorThread atua provendo os dados à fila: atualiza os dados recebidos pelos sensores e os concatena para corretamente alocá-los em uma das estruturas GasData de GasDataQueue. Este processo de alocar dados de um objeto em uma outra estrutura, para transmiti-los, representá-los e/ou armazená-los de forma significativa, em computação é conhecido como marshalling.

Do lado consumidor, a thread GasProcessingThread periodicamente resgata dados da fila. No exemplo em questão, os dados estão somente sendo impressos na tela de um computador.

Lista 5. Implementação em C do modelo descrito na Figura 12

/*********************************
@file GasDataExample.h
*********************************/
#ifndef QueuingExample_H
#define QueuingExample_H
struct GasController;
struct GasData;
struct GasDataQueue;
struct GasDisplay;
struct GasProcessingThread;
struct HeSensor;
struct N2Sensor;
struct O2Sensor;
struct OSSemaphore;
struct SensorThread;
typedef enum GAS_TYPE {
 O2_GAS,
 N2_GAS,
 HE_GAS,
 UNKNOWN_GAS
} GAS_TYPE;
/* define the size of the queue */
#define GAS_QUEUE_SIZE (10)
/* OS semaphore services */
struct OSSemaphore* OS_create_semaphore(void);
void OS_destroy_semaphore(struct OSSemaphore* sPtr);
void OS_lock_semaphore(struct OSSemaphore* sPtr);
void OS_release_semaphore(struct OSSemaphore* sPtr);
#endif

/*********************************
@file GasData.h
*********************************/
#ifndef GasData_H
#define GasData_H
#include "QueuingExample.h"
typedef struct GasData GasData;
struct GasData {
double conc;
unsigned int flowInCCPerMin;
GAS_TYPE gType;
};
/* Constructors and destructors:*/
void GasData_Init(GasData* const me);
void GasData_Cleanup(GasData* const me);
GasData * GasData_Create(void);
void GasData_Destroy(GasData* const me);
#endif

//EOF
/*********************************
@file GasDataQueue.h
*********************************/
#ifndef GasDataQueue_H
#define GasDataQueue_H
#include "QueuingExample.h"
#include "GasData.h"
#include "OSSemaphore.h"
typedef struct GasDataQueue GasDataQueue;
struct GasDataQueue {
  int head;
  OSSemaphore * sema;
  int size;
  int tail;
  struct GasData itsGasData[GAS_QUEUE_SIZE];
};
/* Constructors and destructors:*/
void GasDataQueue_Init(GasDataQueue* const me);
void GasDataQueue_Cleanup(GasDataQueue* const me);
/* Operations */
int GasDataQueue_insert(GasDataQueue* const me, GasData g);
GasData * GasDataQueue_remove(GasDataQueue* const me);
int GasDataQueue_getItsGasData(const GasDataQueue* const me);
GasDataQueue * GasDataQueue_Create(void);
void GasDataQueue_Destroy(GasDataQueue* const me);
#endif

//EOF
/*********************************
@file GasDataQueue.c
*********************************/
#include "GasDataQueue.h"
#include <stdio.h>
/* private (static) methods */
static void cleanUpRelations(GasDataQueue* const me);
static int getNextIndex(GasDataQueue* const me, int index);
static unsigned char isEmpty(GasDataQueue* const me);
static unsigned char isFull(GasDataQueue* const me);
static void initRelations(GasDataQueue* const me);

void GasDataQueue_Init(GasDataQueue* const me) 
{
  me->head = 0;
  me->sema = NULL;
  me->size = 0;
  me->tail = 0;
  initRelations(me);
  me->sema = OS_create_semaphore();
}
void GasDataQueue_Cleanup(GasDataQueue* const me) 
{
  OS_destroy_semaphore(me->sema);
  cleanUpRelations(me);
}
/*
Insert puts new gas data elements into the queue
if possible. It returns 1 if successful, 0 otherwise.
*/
int GasDataQueue_insert(GasDataQueue* const me, GasData g)
{
  OS_lock_semaphore(me->sema);
  if (!isFull(me)) {
    me->itsGasData[me->head] = g;
    me->head = getNextIndex(me, me->head);
    ++me->size;
    /* instrumentation */
    /* print stuff out, just to visualize the insertions */
    switch (g.gType) 
    {
      case O2_GAS:
      printf("+++ Oxygen ");
      break;
      case N2_GAS:
      printf("+++ Nitrogen ");
      break;
      case HE_GAS:
      printf("+++ Helium ");
      break;
      default:
      printf("UNKNWON ");
      break;
   };
   printf(" at conc %f, flow %d\n",g.conc,g.flowInCCPerMin);
   printf(" Number of elements queued %d, head = %d, tail = %d\n",
   me->size, me->head, me->tail);
   /* end instrumentation */
   OS_release_semaphore(me->sema);
   return 1;
  }
  else 
  { 
    /* return error indication */
    OS_release_semaphore(me->sema);
    return 0;
  }
}
/*
remove creates a new element on the heap, copies
the contents of the oldest data into it, and
returns the pointer. Returns NULL if the queue
is empty
*/
GasData * GasDataQueue_remove(GasDataQueue* const me) 
{
  GasData* gPtr;
  OS_lock_semaphore(me->sema);
  if (!isEmpty(me)) 
  {
    gPtr = (GasData*)malloc(sizeof(GasData));
    gPtr->gType = me->itsGasData[me->tail].gType;
    gPtr->conc = me->itsGasData[me->tail].conc;
    gPtr->flowInCCPerMin = me->itsGasData[me->tail].flowInCCPerMin;
    me->tail = getNextIndex(me, me->tail);
    /* instrumentation */
    switch (gPtr->gType) 
    {
       case O2_GAS:
       printf("— Oxygen ");
       break;
       case N2_GAS:
       printf("— Nitrogen ");
       break;
       case HE_GAS:
       printf("— Helium ");
       break;
       default:
       printf("— UNKNWON ");
       break;
    };
    printf(" at conc %f, flow %d\n",gPtr->conc,gPtr->flowInCCPerMin);
    printf(" Number of elements queued %d, head = %d, tail = %d\n",
    me->size, me->head, me->tail);
 /* end instrumentation */
   OS_release_semaphore(me->sema);
   return gPtr;
  }
  else 
  { /* if empty return NULL ptr */
    OS_release_semaphore(me->sema);
    return NULL;
  }
}
static int getNextIndex(GasDataQueue* const me, int index) 
{
   /* this operation computes the next index from the
   first using modulo arithmetic
   */
   return (index+1) % QUEUE_SIZE;
}
static unsigned char isEmpty(GasDataQueue* const me) 
{
  return (me->size == 0);
}
static unsigned char isFull(GasDataQueue* const me) 
{
  return (me->size == GAS_QUEUE_SIZE);
}
int GasDataQueue_getItsGasData(const GasDataQueue* const me) 
{
  int iter = 0;
  return iter;
}
GasDataQueue * GasDataQueue_Create(void) 
{
  GasDataQueue* me = (GasDataQueue *)
  malloc(sizeof(GasDataQueue));
  if(me!=NULL) 
  {
    GasDataQueue_Init(me);
   }
 return me;
}
void GasDataQueue_Destroy(GasDataQueue* const me)
{
  if(me!=NULL) 
  {
    GasDataQueue_Cleanup(me);
  }
  free(me);
}
static void initRelations(GasDataQueue* const me) 
{
  int iter = 0;
  while (iter < GAS_QUEUE_SIZE)
  {
    GasData_Init(&((me->itsGasData)[iter]));
    iter++;
  }
}
static void cleanUpRelations(GasDataQueue* const me) 
{
  int iter = 0;
  while (iter < GAS_QUEUE_SIZE)
  {
    GasData_Cleanup(&((me->itsGasData)[iter]));
    iter++;
  }
}

De posse destes dados, entretanto, tarefas mais úteis poderiam ser executadas a depender das necessidades da planta, como manter a concentração de determinado gás constante, através de algum tipo de controle retroalimentado, por exemplo.

A Figura 13 mostra o sistema em execução. A tarefa GasProcessingThread é disparada primeiro, com um período de 1000 ms e a a tarefa SensorThread é posteriormente disparada a um período de 500 ms. A fila tem 10 elementos. Note que apesar de cada um dos três sensores terem uma chance de 1/3 de produzir dados neste intervalo, os dados estão sendo mais rapidamente inseridos do que removidos, até que a fila enche. [1]

Figura 13. Queueing exemplo sendo executado

4.4. Rendez-Vous

Se as condições para coordenar uma task são mais complexas que as apresentadas anteriormente, quando fundamentalmente estávamos a proteger um recurso de acesso mútuo, podemos “concretizar” estas condições em um objeto de fato. O padrão Rende-Vouz modela as pré-condições para a coordenação de tasks, na forma de um objeto explicitamente separado com seus próprios dados e funções. É um padrão generalista aplicado para garantir que um conjunto de pré-condições arbitrárias sejam atendidas em tempo de execução. [1]

Figura 14. Rende-vouz pattern modelado em UML [1]

4.4.1 Rationale

Duas ou mais tarefas podem ser sincronizadas utilizando-se de uma estratégia a sua escolha que será codificada na classe Rendevouz. O padrão é facilmente adaptável. Quando uma thread encontra um ponto de sincronização, ela registra-se em um objeto da classe Rendevouz, e bloqueia-se até que este objeto a libere para ser executado, usando qualquer que seja a política de scheduling do sistema. É como se um veículo parasse em algum ponto de inspeção na estrada – o fiscal, i.e., o objeto Rendevouz, só a deixa seguir adiante se as condições (papelada, pneus, etc.), estiverem todas satisfeitas.

4.4.2. Elementos

A classe Rendezvous coordena as tarefas através de duas funções primárias:

void reset(void): reseta os critérios de sincronização, i.e., coloca-os de volta em suas condições iniciais.

void synchronize(void): este método é chamado quando uma task quer ser sincronizada. Se os critérios não estão satisfeitos, esta task será de alguma forma bloqueada. A estratégia para pode ser através de um Observer Pattern ou um Guarded Call Pattern, por exemplo. A complexidade deste padrão concentra-se primariamente neste método que avalia se as condições estão satisfeitas. Estas condições podem ser internas (como a Thread Barrier do padrão), externas, ou qualquer combinação das duas.

Normalmente o objeto RendeVouz é agnóstico em relação às threads que coordena. Se não o for, o método synchronize() terá um mais parâmetros para identificação das threads. [1]

O Semaphore é um semáforo comum, com as operações de lock e release.

SynchronizingThread representa uma task que utiliza o objeto Rendezvous para ser sincronizada: quando atinge seu ponto de sincronização, deve explicitamente chamar o método synchronize().

4.4.3 Implementação

Se o padrão for implementado com auxílio de um Observer Pattern, então as tasks precisam registrarem-se com o endereço de um callback a ser chamado quando os critérios de sincronização foram atendidos. Se o padrão Guarded Call Pattern (veja publicação anterior) for utilizado, então cada objeto RendezVous tem somente um único semáforo, que maneja uma fila de tasks que registraram-se naquele objeto RendezVous. Note que neste último caso, o padrão acaba por ser uma solução custosa (overkill), mas que simplifica a implementação de guarded calls, ao concentrá-las em um único componente do programa. É o típico trade-off reusabilidade/custo, que normalmente nos deparamos nas escolhas de design.

4.4.4 Exemplo

No exemplo da Figura 15, uma forma específica do padrão Rendezvous, conhecida como Thread Barrier Pattern [1] é implementada.

Figura 15. Rendezvous implementando uma Thread Barrier

Note que neste snippet, a única informação que o objeto recebe, fora do seu escopo, é o número de tarefas a serem sincronizadas, através do atributo expectedCount. Quando o número de tasks que invocaram o método synchronize() atinge 3, as tarefas são liberadas para o kernel manejá-las com a política de agendamento que utiliza. Os objetos do tipo semáforo e barrier são ponteiros que assumem a referência passada pela task que chamou o ThreadBarrier. O snippet não mostra nenhuma lógica que avalie informações externas, portanto estamos simplesmente a implementar um Guarded Call Pattern, de uma maneira bastante reutilizável. O importante é perceber o forte caráter extensível deste padrão.

Vale aqui replicar a Figura 3 da primeira parte do artigo:

Figura 16. Representação dinâmica de uma Thread Barrier; neste caso expectedCount = 4

Lista 6. Implementação em C do modelo descrito na Figura 15

/******************************
@file ThreadBarrier.h
******************************/
#ifndef ThreadBarrier_H
#define ThreadBarrier_H
/*# # auto_generated */
#include <oxf/Ric.h>
/*# # auto_generated */
#include "RendezvousExample.h"
/*# # auto_generated */
#include <oxf/RiCTask.h>
/*# # package RendezvousPattern::RendezvousExample */
/*# # class ThreadBarrier */
typedef struct ThreadBarrier ThreadBarrier;
struct ThreadBarrier {
  int currentCount;
  int expectedCount;
  OSSemaphore* barrier;
  OSSemaphore* mutex;
};
/* Constructors and destructors:*/
void ThreadBarrier_Init(ThreadBarrier* const me);
void ThreadBarrier_Cleanup(ThreadBarrier* const me);
/* Operations */
void ThreadBarrier_reset(ThreadBarrier* const me, int x);
void ThreadBarrier_synchronize(ThreadBarrier* const me);
ThreadBarrier * ThreadBarrier_Create(void);
void ThreadBarrier_Destroy(ThreadBarrier* const me);
#endif
// EOF
/******************************
@file ThreadBarrier.c
******************************/
#include "ThreadBarrier.h"
void ThreadBarrier_Init(ThreadBarrier* const me) 
{
  me->currentCount = 0;
  me->expectedCount = 3;
  if (me->barrier) 
  {
    OSSemaphore_lock(me->barrier);
    printf("BARRIER IS LOCKED FIRST TIME\n");
 }
}
void ThreadBarrier_Cleanup(ThreadBarrier* const me) 
{
  OSSemaphore_Destroy(me->barrier);
  OSSemaphore_Destroy(me->mutex);
}
void ThreadBarrier_reset(ThreadBarrier* const me, int x) 
{
  me->expectedCount = x;
  me->currentCount = 0;
}
void ThreadBarrier_synchronize(ThreadBarrier* const me) 
{
/*
protect the critical region around
the currentCount
*/
  OSSemaphore_lock(me->mutex);
  ++me->currentCount; /* critical region */
  OSSemaphore_release(me->mutex);
/*
are conditions for unblocking all threads met?
if so, then release the first blocked
thread or the highest priority blocked
thread (depending on the OS)
*/
  if (me->currentCount == me->expectedCount) 
  {
   printf("Conditions met\n");
   OSSemaphore_release(me->barrier);
   //let the scheduler do its job
  }
/*
lock the semaphore and when condition met
then release it for the next blocked thread
*/
  OSSemaphore_lock(me->barrier);
  /* code to check if condition met */
  OSSemaphore_release(me->barrier);
}
ThreadBarrier * ThreadBarrier_Create(void) 
{
  ThreadBarrier* me = (ThreadBarrier *) malloc(sizeof(ThreadBarrier));
  if(me!=NULL)
  {
    ThreadBarrier_Init(me);
    return me;
  }
void ThreadBarrier_Destroy(ThreadBarrier* const me) 
{
   if(me!=NULL)
   ThreadBarrier_Cleanup(me);
   free(me);
}

Fim da segunda parte.

Todos os padrões e exemplos aqui apresentados são de: 
[1] Douglass, Bruce Powel. Design patterns for embedded C: an embedded software engineering toolkit, 1st ed. ISBN 978-1-85617-707-8

Padrões de design para comunicação interprocessos em software embarcado (1/3)

A quem interessar: A depender do dispositivo em que escrevi parte dos textos, algumas palavras estão grafadas em português brasileiro (o meu nativo) ou português europeu (quando o auto corretor assim desejou).

1. Introdução

Nos dois últimos artigos demonstrei um pequeno kernel com escalonador de tarefas cíclico, porém preemptivo (round-robin) implementado em um ARM Cortex-M3. Além do escalonamento de tarefas também separavam-se os processos de usuário dos processos de supervisor, o que trouxe a necessidade da implementação de mecanismos de System Calls.

Durante os artigos, muitas vezes mencionei que o kernel ainda não estava preparado para a sincronização de tarefas e gerenciamento de recursos, ou de forma geral, não havia mecanismos para comunicação interprocessos.

Se quisermos generalizar o uso deste kernel – i.e., reutilizá-lo para uma solução em que as tasks não atuam isoladamente, um ou mais mecanismos de IPC é fundamental. Se por um lado os processos precisam cooperar para atingir determinados objetivos, por outro eles concorrem pelo uso limitado de recursos. [4]

2. IPCs: proteger e coordenar

O fenômeno que nos leva à necessidade de comunicação interprocessos é o da  Concorrência: os recursos finitos de um computador faz com que seja necessário coordenar as diversas actividades que concorrem simultaneamente ou paralelamente. Isto nos leva a ter que proteger uma atividade dos efeitos de outra e sincronizar atividades que são mutualmente dependentes. [4]

Figura 1. Multithreading e multiprocessing, conceitualmente [2]

Na publicação passada em que três tasks acessavam o mesmo hardware para imprimir na tela do PC, a coordenação para compartilhar o recurso foi feita com o sinal de TX_READY lido no registro do próprio dispositivo. Independente da quota de tempo que cada task tinha para ser executada, o kernel só liberava o processador após garantir que os dados da UART haviam sido transmitidos ao computador. Uma forma de IPC que não abstrai o hardware (UART) ou a aplicação (transmitir dados).

static void SysCallUART_PrintLn_(const char* args)
{
    __disable_irq(); // sessão crítica inicio
    uart_write_line(UART, args); // transmite dados        
    while (uart_get_status(UART) != UART_SR_TXRDY); //aguarda fim da transmissão
    __enable_irq(); // sessão crítica fim
    exitKernel_();
}

Lista 0. System Call lendo diretamente o sinal de TX_READY em uma critical region para coordenar as tarefas de acesso à UART

2.1. A Unidade Concorrente

O design do modelo de concorrência é uma parte crítica na arquitetura do sistema a ser desenvolvido. Vamos definir Process, Task e Thread.

Entendo um Process como algo estático (previamente definido) e encapsulado. Uma Task é um processo em execução. As Threads são tasks que acabam por ser dependentes entre si: uma consequência da topologia do sistema em que estes processos são executados [2, 3]. Se analisarmos a Figura 1, é intuitivo notar que a multithreading implica em complexidade de implementação em troca de economia/limitação de recursos.

Para efetivamente entender estes conceitos e modelar a arquitectura mais adequada ao gerenciamento da concorrência de tarefas em um dado sistema, a melhor definição que eu conheço é a de Unidade Concorrente [1]: 

«Unidade Concorrente é um conjunto de ações seqüenciais no mesmo segmento de execução. Também conhecido como task ou thread.» Em [2] uma Thread é definida como o «contexto de um processo em execução» – i.e., o contexto de uma Task – o que não se sobrepõe ou contradiz a definição dada por [1], e complementa a ideia de que uma thread é essencialmente dinâmica. Não à toa, a estrutura de dados em que salvamos o contexto de uma task é classicamente chamada de Thread Control Block.

Powell em [1] ainda observa: «muitos fazem uma distinção entre Task, Thread e Process. Entretanto, todos são o mesmo conceito em diferentes escopos.» Novamente analise a Figura 1. Se o “escopo”for a granularidade, diante do que consta na literatura apresentada, podemos dizer sem danos que: a thread é a menor unidade concorrente de um sistema quando em execução.

Figura 2. A, B, C e D são Unidades Concorrentes: a) A compartilhar um único core (pseudoconcorrentes)  b) Cada unidade tem seu próprio core c) Em execução, somente uma unidade concorrente estará activa em um dado instante de tempo (adaptado de [3])

2.2 A necessidade de sincronização

Antes de prosseguirmos, mais uma definição:

«Pontos de sincronização são aqueles em que as tasks compartilharão informações e/ou garantirão que determinadas pré-condições estejam satisfeitas antes  de prosseguirem.» [1]

A Figura 3 ilustra esta ideia. A barreira de sincronização só permite que o programa siga adiante quando todos os processos tiverem atingido aquele ponto – i.e., as condições para que todas as ações do sistema estejam corretamente sincronizados são verdadeiras.

Figura 3. a) Processos em execução b) Todos os processos exceto C estão prontos c) Assim que o processo C atinge o ponto de sincronização, o programa segue adiante. [3]

Eu prefiro o termo coordenação a sincronização, porque sincronia não é necessariamente um fenômeno desejável ou relacionado entre duas partes, portanto, gosto da ideia de pontos de coordenação. A literatura entretanto normalmente utiliza o termo sincronizado como sinônimo de coordenado.

A Figura 4 mostra unidades concorrentes, modeladas em três tasks. O que sabemos sobre elas? Se a analisarmos individualmente fica claro que na Task 1 a Acção A ocorre antes da B, que percorre um caminho condicional até chegar a E. O mesmo raciocínio  vale para as Tasks 2 e 3.

De que forma as acções individuais das Tasks 1, 2, e 3 relacionam-se entre si? Se a resposta (verdadeira) for “não se relacionam, ou não importa“, não há nenhum problema de concorrência a ser resolvido. E provavelmente o teu sistema é muito simples ou  muito bem desenhado.

Figura 4. Unidades concorrentes representadas como fluxogramas [1]

Entretanto, se em algum ponto é necessário garantir, por exemplo, que as Acções F, X e Zeta sejam executadas somente depois que as Ações E, Z e Gamma atingirem determinadas condições, precisamos de alguma forma reunir (join) cada um dos estados destas tasks em logicamente uma única thread, a partir de um ponto de sincronização. Após as condições necessárias terem sido atingidas no ponto de sincronização, as threads são novamente separadas (fork), e o programa segue.

Isto significa que sempre que houver condições entre dois ou mais processos para atingir determinado objectivo, precisamos criar mecanismos para que estes se comuniquem.

2.2.1. Mecanismos de Exclusão mútua

Recursos podem ser classificados como compartilháveis ou não compartilháveis. Isto depende da natureza física ou lógica de determinado recurso [4]. Por exemplo, a menor unidade de memória do sistema não pode ser lida e escrita ao mesmo tempo por dois processos distintos. Já uma estrutura de dados que guarda um resultado para ser consumido por um processo, precisa ser protegida para não ser sobrescrita antes de consumida (ou enquanto consumida, se pensarmos em pseudo-paralelismo), porque isto causará uma falha lógica no sistema. A exclusão mútua coordena o acesso de várias unidades concorrentes a um recurso.

2.2.2. Falha por deadlock

Quando processos concorrem por recursos, podemos chegar em uma situação em que nenhum deles consegue seguir adiante. Suponhamos dois processos A e B. O processo A está bloqueado, a espera de que um recurso seja liberado para seguir adiante. O processo B por sua vez só vai liberar este recurso quando determinada condição for satisfeita. Se esta condição depender do processo A, que já está bloqueado, temos um deadlock

3. Modelagem de Tasks em UML

Em UML há 3 maneiras de modelar concorrência [1]: objetos com o estereótipo «active» em diagramas estruturais, forks e joins em diagramas de seqüência, e regiões ortogonais em diagramas de máquinas de estado. Um objeto com o estereótipo «active» em geral é uma estrutura de outros objetos. O objeto ativo tem uma thread associada, que executa a ações sequenciais que correm em um contexto (contexto este que pode ou não estar representado ou inferido do diagrama). O símbolo de um objeto ativo pode tanto dar-se como um objeto comum com o estereótipo «active», ou com as bordas esquerda e direita destacadas. Na Figura 5, uma Task é modelada com cinco objetos ativos, um recurso (database) compartilhado e protegido por um semáforo e comentários com os metaparâmetros de cada thread associada (prioridade, período e deadline – parâmetros estes que dependem escalonador utilizado). Objetos «active» que não são um conjunto de outros objetos, como itsBuiltInTestThread  ou itsControlThread correm na sua própria thread. Por fim, em alguns casos utilizamos portas nas Tasks para conectarem-se diretamente com objetos – o que geralmente indica que passaremos estes valores por cópia, e em outros utilizamos links, o que normalmente indica que estes valores serão passados por referência.

4. Padrões para exclusão mútua

Quatro padrões de design serão aqui apresentados com os seus respectivos modelos UML: Critical Region, Guarded Call, Message Queue e Rendez-vous. Todos estes padrões estão descritos em [1].

4.1. Critical Region Pattern

Esta é a forma mais primitiva de coordenar tasks: desligar os mecanismos que poderiam interromper um trecho de execução, para evitar que a task ceda lugar a outra antes de as condições necessárias serem atendidas, ou para evitar a concorrência de acesso a um recurso.

Figura 6.Generalização do Padrão Critical Section em UML [1]

4.1.1. Rationale

Este padrão é utilizado em sistemas com escalonamento preemptivo, quando múltiplas unidades concorrentes podem acessar um mesmo recurso ou interromper uma tarefa em andamento. Ao desabilitarmos a troca de tarefas em determinado trecho de execução, garantimos a atomicidade da operação.

4.1.2 Elementos

CRSharedResource: O recurso a ser protegido é o  atributo value. Qualquer trecho de código que utilize os métodos setValue e getValue precisam ser colocados em regiões críticas.

TaskWithSharedResource: Este elemento simboliza o conjunto de tasks que acessam o recurso anteriormente mencionado (por isso a multiplicidade ‘*’ na associação de dependência). As tarefas não têm conhecimento de que recurso esta a ser utilizado; ele está encapsulado dentro do objeto CRSharedResource.

4.1.3. Implementação

Usualmente o kernel provê uma API com funções como osDisableTaskSwitch()/osEnableTaskSwitch(). Caso não, alguma diretiva em C/ASM pode ser utilizada para desabilitar as interrupções diretamente em hardware – no caso da API de abstração de hardware CMSIS para processadores ARM, esta diretiva seria __disable_irq()/__enable_irq(), e estamos na verdade a desabilitar toda e qualquer interrupção do sistema. Na publicação anterior, vários trechos do código do kernel estavam em critical regions porque necessitavam ser atômicos.

4.1.4. Exemplo

Na Figura 6, um hipotético sistema para mover o braço de um robô. Uma única Task move este braço (CRRobotArmManager). As entradas do usuário são as coordenadas (x, y, z) no espaço,  passadas por referência à Task.

É importante notar a estratégia para desacoplamento entre a Task e os objetos a ela associados: as regiões críticas são implementadas dentro dos métodos da Task, e não no método moveTo, por exemplo. A definição de regiões críticas dentro do método moveTo fatalmente acoplaria uma entidade que não é da natureza do kernel, o braço do robô - que deve poder ser movimentado por outros sistemas operacionais - à uma entidade totalmente acoplada ao kernel, a Task. Se não houver justificativa, o contrário é uma má escolha de design.
Figura 7. Exemplo de Task modelada que necessita do uso de sessão crítica [1]

Abaixo, o cabeçalho do programa, e a implementação de uma operação para facilitar a compreensão da linguagem UML [1]:

Lista 1. Cabeçalho da Task CRRobotArmManager [1]

#ifndef CRRobotArmManager_H
#define CRRobotArmManager_H
struct CRDisplay;
struct RobotArm;
struct UserInput;
typedef struct CRRobotArmManager CRRobotArmManager;
struct CRRobotArmManager 
{
  struct CRDisplay* itsCRDisplay;
  struct RobotArm* itsRobotArm;
  struct UserInput* itsUserInput;
};
/* Constructors and destructors:*/
void CRRobotArmManager_Init(CRRobotArmManager* const me);
void CRRobotArmManager_Cleanup(CRRobotArmManager* const me);
/* Operations */
void CRRobotArmManager_motorZero(CRRobotArmManager* const me);
void CRRobotArmManager_moveRobotArm(CRRobotArmManager* const me);
struct CRDisplay* CRRobotArmManager_getItsCRDisplay(const
CRRobotArmManager* const me);
void CRRobotArmManager_setItsCRDisplay(CRRobotArmManager* const
me, struct CRDisplay* p_CRDisplay);
struct RobotArm* CRRobotArmManager_getItsRobotArm(const
CRRobotArmManager* const me);
void CRRobotArmManager_setItsRobotArm(CRRobotArmManager* const me,
struct RobotArm* p_RobotArm);
struct UserInput* CRRobotArmManager_getItsUserInput(const
CRRobotArmManager* const me);
void CRRobotArmManager_setItsUserInput(CRRobotArmManager* const me,
struct UserInput* p_UserInput);
CRRobotArmManager * CRRobotArmManager_Create(void);
void CRRobotArmManager_Destroy(CRRobotArmManager* const me);
#endif

Lista 2. Método com o uso de critical regions [1]

void CRRobotArmManager_moveRobotArm(CRRobotArmManager* const me) 
{
 /* local stack variable declarations */
 int x, y, z, success = 1; 
 /*noncritical region code */
 /* note that the function below has its own critical region and so cannot be
 called inside of the critical region of this function
 */
 CRRobotArmManager_motorZero(me);
 x = UserInput_getX(me->itsUserInput);
 y = UserInput_getY(me->itsUserInput);
 z = UserInput_getX(me->itsUserInput);
 /* critical region begins */
 OS_disable_task_switching();
 /* critical region code */
 success = RobotArm_moveTo(me->itsRobotArm, x, y, z);
 /* critical region ends */
 OS_enable_task_switching();
 /* more noncritical region code */
 CRDisplay_printInt(me->itsCRDisplay, "Result is ", success);
}

4.2. Guarded Call Pattern

O padrão Guarded Call, serializa o acesso a um conjunto de serviços que potencialmente causam danos se chamados simultaneamente. Neste padrão, o acesso serializado é implementado através de um semáforo que previne que outras threads invoquem este serviço enquanto ele estiver em uso.

Figura 8. Generalização do Guarded Call Pattern modelado em UML [1]

4.2.1 Rationale

Múltiplas tarefas preemptivas acessam um recurso protegido invocando os métodos deste. O escalonador de tarefas por sua vez deve colocar a task que tentou acessar um recurso ocupado em uma fila de tasks bloqueadas, desbloqueando-a assim que o recurso for liberado.

4.2.2. Elementos

GuardedResource é um recurso compartilhado que emprega um Semaphore do tipo mutex para forçar a exclusão mútua entre múltiplas PreemptiveTasks (note que existe um único semáforo agregado a um único recurso, e portanto é um semáforo para um elemento, ou seja, um mutex1). Quando uma tarefa quer utilizar este recurso, as funções relevantes deste chamarão ao semáforo para colocá-lo em lock. Caso o recurso esteja livre, ele é locked e a tarefa pode utilizá-lo, e liberá-lo ao final. Caso o recurso já esteja em locked, este sinaliza ao escalonador para colocar a tarefa atual em estado blocked até que ele seja liberado. Outras tarefas que tentam acessar o recurso enquanto ele está bloqueado também tornar-se-ão blocked. Cabe ao escalonador do sistema fazer o manejo desta fila de tarefas bloqueadas a espera do recurso; ou seja, quais critérios serão utilizados para cada tarefa na fila – pode ser a prioridade, por exemplo.2

1 a implementação de semáforos/ mutexes é um assunto que será abordado na continuidade da construção do kernelzito já apresentado.

2 um problema comum nesta implementação é quando ocorre a chamada “inversão de prioridade”

4.2.3 Implementação

A parte mais complicada é a implementação dos semáforos. Normalmente o sistema operacional provê semáforos, acessados através de uma API do tipo:

  • Semaphore* osCreateSemaphore(): cria um semáforo e retorna um ponteiro para a instância.
  • void osDestroySemaphore(Semaphore*): destrói a instância semáforo para o qual aponta.
  • void osLockSemaphore(Semaphore*): trava o dispositivo associado ao semáforo se ele estiver livre. Caso não esteja, o contexto da tarefa que o requisitou é salvo, bem como a ID do semáforo do recurso requisitado, e a tarefa é colocada em blocked.
  • void osUnlockSemaphore(Semaphore*): destrava o dispositivo associado ao semáforo, e libera a tarefa que estava a sua espera.

4.2.4 Exemplo

A Figura 9 mostra a porção de um hipotético controlador de vôo. A classe KinematicData é compartilhada por diversos clientes. Para garantir a serialização de acesso um semáforo é instanciado neste recurso.

Figura 9. Padrão Guarded Pattern aplicado a um controlador de vôo [1]

Isto evita que o método FlightDataDisplay::ShowFlightData()seja interrompido enquanto disponibiliza os dados de vôo, pelo método Navigator::updatePosition() por exemplo. Perceba que as Tasks não estão modeladas. A utilização do semáforo está acoplada ao escalonador – o seu estado quando a thread é disparada influencia no manejo da fila de threads no qual cada método em espera será executado. Abaixo snippets de parte da implementação para facilitar o entendimento.

Lista 3. Cabeçalho da classe KinematicData

#ifndef KinematicData_H
#define KinematicData_H
#include "GuardedCallExample.h"
#include "Attitude.h"
#include "OSSemaphore.h"
#include "Position.h"
typedef struct KinematicData KinematicData;
struct KinematicData 
{
 struct Attitude attitude;
 struct Position position;
 OSSemaphore* sema; /*## mutex semaphore */
};
/* Constructors and destructors:*/
void KinematicData_Init(KinematicData* const me);
void KinematicData_Cleanup(KinematicData* const me);
/* Operations */
Attitude KinematicData_getAttitude(KinematicData* const me);
struct Position KinematicData_getPosition(KinematicData* const me);
void KinematicData_setAttitude(KinematicData* const me, Attitude a);
void KinematicData_setPosition(KinematicData* const me, Position p);
KinematicData * KinematicData_Create(void);
void KinematicData_Destroy(KinematicData* const me);
#endif

Lista 4. Implementação da classe KinematicData

#include "KinematicData.h"
void KinematicData_Init(KinematicData* const me) 
{
  Attitude_Init(&(me->attitude));
  Position_Init(&(me->position));
  me->sema = OS_create_semaphore();
}
void KinematicData_Cleanup(KinematicData* const me) 
{
  OS_destroy_semaphore(me->sema);
}
struct Position KinematicData_getPosition(KinematicData* const me) 
{
  Position p;
  /* engage the lock */
  OS_lock_semaphore(me->sema);
  p = me->position;
  /* release the lock */
  OS_release_semaphore(me->sema);
  return p;
}
void KinematicData_setAttitude(KinematicData* const me, Attitude a) 
{
/* engage the lock */
  OS_lock_semaphore(me->sema);
  me->attitude = a;
  /* release the lock */
  OS_release_semaphore(me->sema);
}
void KinematicData_setPosition(KinematicData* const me, Position p) 
{
  /* engage the lock */
  OS_lock_semaphore(me->sema);
  me->position = p;
  /* release the lock */
  OS_release_semaphore(me->sema);
}
KinematicData * KinematicData_Create(void) 
{
  KinematicData* me = (KinematicData *)
  malloc(sizeof(KinematicData));
  if(me!=NULL) 
  {
   KinematicData_Init(me);
  }
  return me;
}
void KinematicData_Destroy(KinematicData* const me) 
{
  if(me!=NULL) 
  {
   KinematicData_Cleanup(me);
  }
  free(me);
}
Attitude KinematicData_getAttitude(KinematicData* const me) 
{
  Attitude a;
  /* engage the lock */
  OS_lock_semaphore(me->sema);
  a = me->attitude;
  /* release the lock */
  OS_release_semaphore(me->sema);
  return a;
}

Fim da primeira parte

Referências:
[1] Design Patterns for Embedded Systems in C (Douglass Powell, 2009)
[2] Embedded Systems: Real-Time Operating Systems for Arm Cortex-M MCUs (Jonathan Valvanno, 2012)
[3] Modern Operating Systems (Andrew Taneunbaum, Herbert Boss, 2014)
[4] Fundamentals of Operating Systems (A. M. Lister, 1984)

SOA para diminuição da hardware-dependência em C

aa480021.aj1soa01(en-us,msdn.10)
(MS Software Architecture Journal, 2004)

1. Impacto do software hardware-dependente (HdS)

É dito na literatura que o custo do software embarcado tem dominado o projeto de sistemas eletrônicos [1]. Sistemas embarcados, tradicionalmente limitados em memória e processamento, conseguem hoje rodar aplicações mais complexas fruto do avanço no projeto e fabricação de circuitos integrados. Ora, a introdução de hardware mais complexo permite a utilização de recursos de programação também mais complexos. De fato, mais de 90% das inovações na indústria automotiva da última década são decorrência direta do desenvolvimento em software embarcado. A especialização do dispositivo leva à especialização do software e ao conceito de software hardware-dependente:

  • é especialmente desenvolvido para um bloco de hardware específico: o software é inútil sem aquele hardware
  • software e hardware juntos implementam uma funcionalidade: isto é, o hardware é inútil sem aquele software

Muito provavelmente ao ler esta descrição pensaste em um sistema operacional para determinada plataforma e seus controladores (drivers). Abaixo segue um diagrama em camadas de um típico sistema embarcado. Conforme subimos as camadas, menos hardware-dependente será o nosso software, de forma que para escrevermos em linguagem interpretada, digamos, eu não preciso tomar conhecimento do microprocessador, e muito menos das tensões de operação dos meus dispositivos. O HAL (camada de abstração de hardware) é onde encontra-se o software mais hardware-dependente, i.e., mudanças no hardware invariavelmente implicarão em mudanças no software desta camada (Figura 1).

hal

Figura 1. Componentes e camadas de um típico sistema embarcado [ECKER]

2. Orientação a objetos para aumentar a coesão

O paradigma de orientação a objetos parte de um conceito muito intuitivo que é particionar um sistema em objetos classificados consoante à sua natureza. Não é necessário muito para perceber como isto aumenta o reuso e a portabilidade. A utilização do paradigma aumenta a coesão dos componentes de nossa arquitetura na medida da nossa habilidade em pensar de maneira orientada a objetos. Ao contrário do domínio de software aplicativo, em software embarcado sobretudo quando os requisitos são bastante específicos e o hardware limitado, a portabilidade e reuso esbarram na hardware-dependência. Se a OO é um bom paradigma para escrever software coeso, muitas vezes nestes domínio este recurso está indisponível. Podemos utilizar o C para escrever em um (meta-)padrão orientado a objetos, se soubermos fazer bom uso de ponteiros.

3. Exemplo de arquitetura orientada a serviços em C

Como exemplo vou descrever uma arquitetura para desacoplar a aplicação do hardware e que se beneficia dos conceitos de OO, entre eles o polimorfismo. O objetivo é escrever software para comunicação serial coeso o suficiente para quando o hardware mudar (ou for definido), somente o código mais fortemente hardware-dependente precise ser adaptado (ou escrito). O conceito de arquitetura orientada a serviços está presente em sistemas operativos baseados em microkernel (dois exemplos extremos: Windows NT e MicroC/OS). A arquitetura proposta está representada na Figura 2. Todo o software representado daqui em diante refere-se somente à camada de Serviços. A camada Board Support Package desacopla (ou diminui o acoplamento) entre o HAL e os Serviços; é a API do HAL para o programador dos Serviços.

layers

Figura 2. Layers em uma arquitetura orientada a serviços [do autor]

É uma boa ideia permitir que a aplicação utilize dois únicos métodos para transferir e receber um número de dados via serial, aplicados sob diferentes componentes de hardware: enviar(interface, x_bytes) e receber(interface, x_bytes). Estes são métodos que assumem uma forma ou outra a depender do objeto. Assim chegamos aos conceitos de interface (Classe abstrata), herança e polimorfismo. Abaixo o diagrama de classes da proposta. A assinatura completa dos métodos foi omitida.

class
Figura 3. Diagrama de classes da proposta

O padrão de design Proxy/Server permite que o hardware seja configurado de forma genérica abstraindo seus detalhes específicos. As mudanças no BSP são isoladas pela proxy ao programador da aplicação. O servidor por sua vez sustenta-se nos dados de configuração da proxy e na API do HAL para configurar e inicializar os serviços (this_proxy->this_service).

(Errata: na figura 3 os métodos de construção/inicialização e enviar/receber da classe SPI_proxy estão representados como se fossem iguais ao da UART, porém são métodos distintos.)

3.1. Implementação da Classe Abstrata

Uma interface pode ser percebida como um barramento de funções virtuais que aponta para um método ou outro em tempo de execução. Este apontamento segue por um caminho de endereços até chegar ao método para ser executado naquele contexto (etapa do fluxo do programa). Poderíamos também atribuir através de setters os métodos de cada objeto, i.e., ainda em tempo de compilação.

Começaremos por implementar a estrutura de dados que compreende a classe. Esta estrutura implementa 2 métodos que recebem e enviam frames de bytes. Uma classe Serial_Comm, portanto dá cria a um objeto que contém uma tabela de funções genéricas de enviar e receber. Os métodos públicos da interface são somente construtores e desconstrutores. Os métodos de enviar e receber ficam privados, haja vista que o objeto a ser utilizado pelo programador da aplicação é que vai defini-los. A estrutura com as funções virtuais Serial_Table é declarada mas não definida inicialmente. Mais adiante declaramos que a estrutura é somente leitura (definida em tempo de compilação) contém dois ponteiros para funções, e finalmente as definimos de forma limitada ao escopo. Isto é necessário para que ocorra o alinhamento do endereço desta tabela ao endereço da tabela do objeto que a utiliza em tempo de execução.

Abaixo o cabeçalho do Serial_Comm.

serial_comm_h-e1569800116804.png
Figura 4. Cabeçalho da classe Serial_Comm

No programa .c da interface, uma estrutura SerialTable é inicializada com endereço de funções dummy. A definição destes métodos com o assert(0) é uma forma de acusar um erro de programação em tempo de execução, se estas funções forem chamadas sem a devida sobrescrita.

serial_comm_c
Figura 5. Programa da Classe Virtual

3.2. Implementação do serviço UART

As classes de comunicação serial seguirão este padrão de design. O construtor inicialmente define uma estrutura SerialTable. Perceba que esta estrutura só pode ser definida uma vez, mas os elementos de vtbl podem assumir qualquer valor; i.e., se construímos um objeto que herda esta classe podemos estender os parâmetros e definir o endereço dos métodos, que ficarão ligados a uma e somente uma interface de funções virtuais.

Na estrutura de dados de uma classe herdeira a sua superclasse precisa ser declarada primeiramente. De outro modo não poderemos estender os atributos desta.

Na construção da proxy, uma tabela de funções definidas localmente é o endereço destino que contém a definição dos métodos virtuais da interface.

uart_proxy_hhh.png
Figura 6. Cabeçalho da classe Uart_proxy
uart_proxy_c-e1569704959728.png
uart_proxy_c_2
Figura 7. Programa uart_proxy.c

Um ponto chave é o downcast (linhas 51 e 57) feito nos métodos privados Uart_Send_ e Uart_Get_. Um ponteiro para Uart_proxy é inicializado com o endereço de uma interface Serial_Comm. O alinhamento da memória permite que acessemos os métodos desta proxy a partir desta interface. Além disso como servidor e proxy estão agregados, os metodos do BSP podem ser chamados na proxy. As funções que começam com “_” (_uart_init, _uart_get …) fazem parte deste BSP, cujo cabeçalho uart_driver_api.h está incluído no programa. No BSP podem-se utilizar as mesmas técnicas, para permitir por exemplo, que a definição do endereço do dispositivo a ser construído se dê também por uma interface abstrata que não muda com as características do dispositivo (mapeado em porta ou memória, plataforma alvo, etc.)

uart_server_hh
Figura 8. Cabeçalho da classe Uart_Server

Logicamente, a implementação do serviço para SPI segue o mesmo padrão de design.

4. Utilização dos serviços

Para a utilização dos serviços pela camada de aplicação, basta construir uma proxy com parâmetros de inicialização do dispositivo, neste exemplo UART ou SPI, e utilizar os métodos SendFrame e GetFrame que acessam a interface de cada objeto proxy.

main2.png
Figura 9. Um programa utilizando os Serviços e seus métodos polimórficos
run
Figura 10. Programa em execução

5. Conclusões

Conceitos do paradigma de programação orientado a objetos podem ser implementados, virtualmente, em qualquer linguagem se partirmos da ideia de que classes são estruturas de dados agregadas a um conjunto de funções que fornecem uma interface externa comum. Tanto estes métodos quanto estes dados podem ser privados ou não. No primeiro caso está o conceito de encapsulamento. A alocação destas estruturas com seus valores e funções, é a instância de um objeto. A instanciação de um objeto de uma classe dentro de outra classe implementa a herança. Uma interface que não implementa métodos pode ser utilizada para conectar-se à interface de uma outra classe, o que chamamos de funções virtuais. As funções virtuais podem então assumir uma forma ou outra a depender do fluxo do programa, o que caracteriza o polimorfismo.

Uma arquitetura orientada à serviço eleva a coesão dos componentes e a consequente reutilização e portabilidade, mitigando os problemas gerados pela natural hardware-dependência do software para sistemas embarcados. A orientação a objetos por sua vez é o paradigma natural para a construção de sistemas orientado a serviços. Este artigo demonstrou uma forma de aplicar estes conceitos em sistemas embarcados quando linguagens OO (comumente neste domínio C++ ou Ada) não estão disponíveis.


O texto desta postagem bem como as figuras não referenciadas são do autor.
As seguintes referências foram consultadas:
[1] Hardware-Dependent Software: Principles and Practices. Ecker, Muller, Dommer. Springer, 2009.
[2] Design Patterns for Embedded Systems in C. Bruce Douglass. Elsevier, 2001.
[3] Object-Oriented Programming in C: Application Note. Quantum Leaps. April, 2019.

Abordagens para projeto low power (2/3)

17zhswf3uasrj.jpg

(Um PDA da Nokia com acesso à internet, 1995. Fonte: gizmodo.com)

5 Abordagens low power no nível arquitetural

Penso que desenhar a arquitetura de um projeto é, para todos os efeitos, definir como cada módulo do sistema se comunica com os outros módulos para trabalharem em conjunto, e através de análises, seja pela experiência do projetista ou por resultados de modelos, elaborar a melhor forma de construí-los. Abaixo seguem algumas abordagens utilizadas na indústria para elaborar arquiteturas eficientes em consumo.

5.1 Redução dinâmica da tensão de alimentação e frequência (DVFS)

Apesar dos avanços, o problema entre o poder computacional disponível e o tempo de bateria ainda são os principais desafios da indústria. O seu smartphone aguenta 1 único de dia de uso pesado com navegação, músicas, redes sociais e sinal intermitente? O meu não.

Mas como disse, uso pesado. Quer dizer, o seu smartphone sabe quando mais e quando menos energia serão necessárias para aplicação, reduzindo ou aumentado a tensão e/ou a frequência fornecidas dinamicamente para os periféricos do microprocessador.

Os próprios microprocessadores em geral são especificados de forma que a frequência de operação máxima depende da tensão fornecida. Assim quando a performance não estiver crítica a tensão (e a frequência) podem ser reduzidas. Infelizmente isto não vale para sistemas de tempo real cujo principal requisito é atender aos deadline. Existem soluções que incorporam DVFS entre o escalonador e o disparador do RTOS.

5.2 Múltiplas tensões

Projetar um chip utilizando uma única tensão de alimentação é comum e também tem a penalidade de que os piores caminhos de tempo a serem cumpridos terão a mesma força de drive dos demais. Ou seja, haverá slack times bastante altos para poder compensar os caminhos críticos. Claro que um bom projeto e uma boa ferramenta tentam encontrar um compromisso.

O ponto chave é que se todos os caminhos forem críticos, o consumo global vai ser o menor possível. A forma mais simples é: operar todos os caminhos que não são críticos em tensão mais baixa, e os críticos em tensão mais alta. A penalidade se dará principalmente em área pela adição de layers para comunicar blocos em diferentes tensões.

Formas mais eficientes adicionam inteligência nas ferramentas de projeto para escolher as tensões de cada caminhos. Falando de forma muito simplificada, um algoritmo calcula o slack de uma célula, e decide se ela pode ou não ser substituída por uma célula low voltage. Caso os demais caminhos continuem positivos esta célula é então substituída. Se não, será preciso sacrificar o consumo em detrimento da performance naquela célula.

Ainda, alguns autores sugerem que o caminho crítico de um circuito não é o caminho mais longo, mas sim o caminho mais longo e mais demandado na operação – uma variável a mais. Esta técnica demonstrou alguns ganhos em relação a anterior, e é chamada de PVCS (path-oriented clustered voltage scaling).

É preciso dizer que os layers adicionados para comunicar módulos em diferentes tensões também consumirão energia tanto estática quanto dinâmica. Existem pesquisas com as mais diversas soluções para a utilização de múltiplas tensões, inclusive com técnicas livres de conversores de nível de tensão.

5.3 Clock-gating

Em primeiro lugar é importante dizer que a árvore de clock consome aproximadamente 50% da energia em um circuito integrado digital. Depois, cada vez que um gate é chaveado, energia dinâmica será consumida. Se o dado a ser disponibilizado após o chaveamento é o mesmo que lá está, por que então consumir esta energia? Condições para habilitar ou não o clock são as técnicas chamadas de clock gating.

Está apresentada aqui em nível arquitetural pois, assim como as outras técnicas neste nível, é implementada no projeto através das diretivas de síntese que o projetista lança e das células disponíveis no PDK (Process Design Kit). Entretanto o código em que o hardware é descrito também tem forte influência no que a ferramenta vai conseguir fazer, pois é a partir desta descrição que as melhores ‘condições’ para habilitar ou não o clock serão inferidas.

A forma mais comum de clock-gating, simplesmente compara se a entrada D de um banco de registradores é igual ou não à saída Q.

clockcombinacional

Figura 1: Clock gating combinacional (figura retirada de Mohit Arora)

Na figura acima, uma condição de enable permite ou não que aquele registrador seja ‘clockado’, e o dado segue adiante na pipeline. (perceba que o segundo registrador não tem uma lógica de clock gating representada, e muitos menos relacionada com a primeira)Estima-se que 5-10% de energia dinâmica é salva com essa técnica se implementada combinacionalmente.

Pensando num pipeline onde lógicas são encadeadas entre um banco de registro e outros podemos também reduzir o chaveamento redundante na porção do circuito que está conectada à saída banco de registradores que estão sob clock gating, se toda a cadeia subsequente da pipeline for chaveada levando em conta as condições de enable da anterior. Na literatura costumam chamar esta técnica de “clock-gating avançado”.

clocksequencial

Figura 2: Clock gating sequencial (de Morit Ahora)

5.4 Power gating

Desabilitar completamente um módulo quando ele não está em uso, é consideravelmente importante nas atuais tecnologias onde a componente de consumo estático é dominante. Os módulos são habilitados ou desabilitados conforme a necessidade da aplicação. As chaves utilizadas para habilitar ou desabilitar passagem de corrente para o módulo são comumente chamadas de sleep transistors. As chaves conectadas entre Vdd e o módulo são os chamados ‘headers’ e entre o módulo de Vss são os ‘footers’. A inserção destes sleep transistors insere agora dois grandes domínios de tensão no sistema: um permanente, conectado à fonte de alimentação, e um virtual que é o visto pelo módulo de fato. O maior desafio é projetar uma chave que permita que o domínio de tensão real e virtual sejam muito similares em todas as suas características.

header-footer-swithces

Figura 3: Diagrama de blocos de dois circuitos utilizando sleep transitors, (a) header e (b) footer. (de Mohit Arora)

Não é difícil imaginar que o tamanho do sleep transistor seja bastante considerável (no dedão: ~3x a capacitância a ser driveada). Devido ao seu tamanho, ligar ou desligar um módulo através do seu chaveamento leva um tempo. Assim, não parece uma boa política adicionar estas chaves a módulos que ficarão pouco tempo em idle na operação típica do sistema. Assim, ou fazemos um sistema de power gating de baixa granularidade ou alta granularidade.

No modo fine-grain (alta granularidade) cada módulo tem um sleep transistors que são construídos como parte do PDK e adicionados durante a síntese, o que traz imensas vantagens na facilidade de projeto. A economia de corrente de leakage pode chegar a 10X.

No sistema de baixa granularidade, menos sleep-transitors são disponibilizados na forma de ‘grid’ que ligam ou desligam os domínios de módulos conforme a aplicação. Isto implica em menor overhead de área (e por consequência, menor variação de processo). Nesta abordagem os sleep-transistors são de fato parte das linhas de alimentação do circuito, não células adicionadas na síntese lógica, e portanto mais próximos do projetista de back-end.

Por outro lado, nesta abordagem de grid, com menos sleep-transistors chaveando mais circuitos, teremos mais domínios de power, com maiores variações de IR entre eles, maiores correntes de pico de power-up, que podem, entre outros problemas, ocasionar transições indesejadas em módulos vizinhos, o que vai exigir contra-medidas no back-end. Além de é claro, fritar um circuito cujas linhas foram subdimensionadas.

coarsepower

Figura 4: Representação de um esquema de power-gating de baixa granularidade com sleep transistor do tipo footer (de Mohit Arora)

Na prática não existe uma linha bem definida entre fine-grain e power-grain, e um misto de ambos é utilizado em um projeto real.

5.5 Sub-threshold/near-threshold design

A diminuição da tensão de alimentação (mantendo uma tensão de threshold fixa) resulta na diminuição quadrática do consumo dinâmico, às custas de performance, o que a depender da área de aplicação (sensores biomédicos, para dar um único exemplo) não é um problema.

Indo um pouco além, podemos pensar em utilizar o que seria a corrente de leakage desperdiçada para de fato implementar a lógica do sistema, o que é atingido quando se reduz a tensão de alimentação para um valor menor ou muito próximo de Vth. A corrente de sub-threshold é exponencialmente dependente da tensão no gate. A literatura demonstra algumas reduções de até 20X quando comparados com circuitos operando com (super)-Vth.

O grande problema? A pequeníssima diferença na corrente de um transistor ligado e um desligado, faz com que as variações de processo sejam muito impactantes no circuito construído. As contra medidas partem da arquitetura do sistema e chegam ao nível de transistor.

* * *

A próxima e última publicação vai falar das técnicas em nivel RTL.

Se não concorda, não entendeu, achou muito bom ou muito ruim, comentários são muito bem vindos.

O texto desta publicação é original. As seguintes fontes foram consultadas: The Art of Hardware Architecture, Mohit Ahora Ultra-Low Power Integrated Circuit Design, Niaxiong Nick Tan et al.

Abordagens para projeto low-power (1/3)

iphone-battery

1 Eficiência

Na última publicação sugeri que a Compaq teria percebido a portabilidade como requisito mais que desejável para a computação pessoal. Apesar de os primeiros computadores da companhia terem ~12 kg (!) e serem considerados “portáteis” simplesmente por serem apresentados em uma maleta com alças, ainda precisavam de uma tomada de corrente para funcionar.

Um pouco mais tarde, com a popularização das tecnologias multimídias e dos PDAs (personal digital assistants, ou “palmtops”), a computação portátil começa a precisar de cada vez mais performance, e aí a otimização de consumo passou a ser critério determinante em um projeto. O objetivo é ser eficiente: realizando tanto ou mais trabalho com menos energia, as baterias duram mais. Não sei dizer exatamente quando e nem quem começou as pesquisas no assunto, mas um dos trabalhos acadêmicos mais relevantes na área é datado de 1992 (Low-power CMOS Digital Design, CHANDRAKASAN et. al).

Nesta publicação quero falar um pouco sobre técnicas de baixo consumo e a oportunidade de aplicá-las nas diferentes fases e camadas de abstração de um projeto. Aqui estou assumindo que os circuitos são essencialmente digitais. O projeto low-power para circuitos (integrados) analógicos tem técnicas distintas que podem ser assunto para outra postagem.

2 Consumo estático e dinâmico

Dois componentes gerais de consumo são o consumo estático e o consumo dinâmico. Este refere-se ao consumo ocasionado pelas transições de uma porta lógica e é proporcional à corrente circulante, à frequência de transições e às capacitâncias que são carregadas e descarregadas nessas transições. O consumo estático se refere às correntes que circulam entre Vdd e Gnd mesmo quando os módulos de um dispositivo estão desligados. Com os comprimentos de canais dos transistores cada vez menores, as correntes de leakage passaram a ser uma significativa parcela do consumo total, quando não a componente dominante. Quanto menor o canal de um transistor, menor será a sua tensão de threshold e menor será a diferença entre a corrente de operação e a corrente de leakage. Na verdade, a corrente de leakage aumenta exponencialmente com a diminuição da tensão de threshold.

De maneira geral, para um gate lógico:

Potência total = Potência dinâmica + Potência estática [W]

Potência dinamica = Vdd^2 * Freq * Cl* p [W]

onde p é a probabilidade de uma transição lógica ocorrer.

3 Níveis de abstração de um projeto digital

Fazendo uma analogia com carros, uma Lamborghini Diablo 1991 é um sistema igual a um Renault Clio 2010. Ambos são automóveis, do tipo “carro”, compostos por carroceria, 4 rodas, motor, diferencial, volante, transmissão e etc. Porém arquiteturalmente são projetos radicalmente distintos.

Um sistema é concebido para prover uma solução. No caso dos automóveis o problema a ser resolvido é como deslocar algo de um lugar a outro. Se eu preciso levar uma pessoa de um ponto ao outro, eu posso escolher construir um carro, uma moto ou um patinete (que não é um automóvel!). Enfim, as escolhas em nível de sistema, são aquelas que irão definir o que é o meu projeto e quais são suas características. Estas escolhas terão como ponto de partida os requisitos do produto. Se o propósito é deslocar até 5 pessoas de um ponto ao outro e com economia de energia, o Clio faz muito mais sentido que a Lamborghini, se o requisito for um carro.

De maneira geral, podemos representar a estrutura de um projeto, nos seguintes níveis de abstração:

Nível de Sistema: refere-se a definição do conjunto de módulos de um projeto e suas conexões (microprocessador+RAM+NVM+I/O, etc.)

Nivel Arquitetural: refere-se a forma como são construído os módulos definidos no sistema e como eles interagem: a definição de interfaces, dos protocolos de controle, comunicação, etc. (ex.: microprocessador RISC-V 32-bit, 8KB de RAM, 64KB de memória NAND Flash, transreceptor compatível com NFC, camada MAC comunica-se com a PHY através de uma interface AMBA-PB, etc.)

Nível de Registradores (Register Transfer Level): representação do circuito digital como um conjunto de registros, ULAs, Muxes, contadores, etc. Pode ser chamado de “microarquitetura”.

Nível lógico: mapeamento do RTL como um conjunto de portas lógicas, latches e flip-flops.

Nível de Circuito: a representação elétrica do sistema, através de um esquemático de transistores e outros componentes elétricos.

4 Abordagens low-power no nível de sistema

Quando pensamos em sistemas digitais o consumo geralmente estará relacionado à área e performance. Uma maior performance exige uma operação em alta freqüência e com suficiente força de drive. A área relaciona-secom o tamanho dos dispositivos que por sua vez dita o tamanho das capacitâncias a serem carregadas/descarregadas.

4.1 Faça um SoC

O advento dos SoCs, sistemas inteiramente construídos em um único circuito integrado, possibilitou drástico aumento na eficiência energética. Se falamos de um sistema que está construído na forma de chips e componentes discretos conectados em uma placa, a transformação em SoC pode ser vista como uma técnica para redução de consumo. E das mais eficientes.

4.2 Capriche no co-projeto de hardware+software

O que implementar em hardware e o que implementar em software? Tipicamente as implementações em hardware consumirão menos energia que as suas contrapartes em software.

Podemos simplesmente identificar aquelas rotinas que consomem mais processamento e escolher implementá-las em hardware.

Entretanto em um fluxo de projeto que realmente aproveite a oportunidade de se poder implementar qualquer parte de um sistema em hardware ou software, uma abordagem baseada em modelos deve ser considerada. Existem linguagens como o SystemC ou SystemVerilog que permite a confecção de modelos em alto nível de abstração. Outras ferramentas como SystemVue, Matlab/Simulink são dedicadas a modelar sistemas. Depois de o sistema modelado, as simulações são utilizadas para fazer estimativas da performance e consumo das funcionalidades, e pode-se fazer escolhas direcionadas sobre o que será implementado em hardware ou software. As funcionalidades que consomem mais recursos beneficiarão todo o sistema se forem construídas com arquitetura visando baixo consumo. Ou seja, as análises no nível do sistema guiam nossas escolhas arquiteturais mais adiante.

A validação da arquitetura pode ser feita através de uma abordagem TLM (Transaction-Level Modeling).

lowpower_hwswcodesignflow

4.3 Software eficiente

Idealmente o seu compilador deve conseguir produzir um código objeto otimizado, mas ele não tem nenhuma outra informação a não ser o código que você entrega a ele, puro e duro. Compiladores “system aware” só amanhã.

Quantas instruções tem a task mais executada do sistema? Quantos ciclos de clock cada instrução consome? Se um sistema rodando a 5 MHz acorda o processador a cada segundo para executar 500 instruções, admitindo 1 instrução/ciclo, ao diminuírmos somente uma instrução desta task, estaremos dando uma sobrevida a bateria de ~ 6,5 segundos por ano, num sistema 24/7. Escalone isso para mais MHz de operação e mais instruções economizadas, e veja por si só.

Assim, o nosso código, como regra geral deve evitar primitivas complexas e ser otimizado em desempenho. Considero que conhecer o processador e o compilador, e a utilização de boas práticas de engenharia de software como a refatoração, são as melhores forma de escrever códigos eficientes. Abaixo alguns exemplos:

Código original

Código otimizado

if ((i % 10) == 0 )
{
   // faça algo
}
i++;
If (counter == 10)
{
   // faça algo
   counter=0;
}
else
{ 
   i ++
}
counter++;

A operação ‘módulo’ usualmente toma mais ciclos de instrução. É mais econômico reproduzir o mesmo efeito com operações mais baratas.

Código original

Código otimizado

for(i=0;i<10;i++)
{
   // faça algo 1
}
for(i=0;i<10;i++)
{
   // faça algo 2
}
for(i=0;i<10;i++)
{
   // faça algo 1
   // faça algo 2
}

Uma chamada de loop com inicialização, incremento e comparação é economizada.

Código original

Código otimizado

unsigned int x;
 for (x = 0; x < 100; x++)
 {
     A[x] = B[x];
 }
unsigned int x; 
 for (x = 0; x < 100; x += 5 )
 {
     A[x]   = B[x];
     A[x+1] = B[x+1];
     A[x+2] = B[x+2];
     A[x+3] = B[x+3];
     A[x+4] = B[x+4];
     
 }

No código acima, 100 elementos do vetor A serão copiados para as primeiras 100 posições do vetor B. A segunda implementação faz com que o loop precise ser rodado 20 vezes, ao invés de 100.

(Link externo: este AN da Atmel indica no capítulo 9 algumas formas de otimizar tamanho e tempo de execução para AVRs 8-bit)


 

Na parte 2 vou falar sobre técnicas aplicadas no nível arquitetural (power-gating, clock gating, multi Vdd, multi Vth, DVFS…).

Até mais!

O texto desta publicação é original. As seguintes fontes foram consultadas:
The Art of Hardware Architecture, Mohit Ahora
Ultra-Low Power Integrated Circuit Design, Niaxiong Nick Tan et al.

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. 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

Operando números negativos em computadores

maxresdefault

Os conceitos de aritmética modular eram utilizados em computadores mecânicos, e já não eram novidade naquela época. (Imagem de: https://www.youtube.com/watch?v=nmwSmwNF9XY)

1. 《Tudo é número》(Pitágoras)

Os autores costumam dizer que a Matemática é desenvolvida conforme o homem necessita. Assim, podemos imaginar que os humanos primitivos faziam risquinhos para representar uma coleção de objetos (cabras, peles, filhos…). Constatada sua ineficiência, criaram-se símbolos que representavam tamanhos de coleções diferentes, depois símbolos que representavam uma coleção de outros símbolos, e a coisa foi ficando cada vez mais sofisticada.

Costumamos representar os numerais em uma base B, da seguinte forma, em uma notação de ponto fixo onde “a” é inteiro:

eq

O sistema de base 10 que utilizamos é composto pelos símbolos {0,1,2,3,4,5,6,7,8,9} para representar as quantidades de zero a nove unidades de algo. Aliás, o zero é uma invenção muito interessante pois é um símbolo que representa ‘não há’. Sei que até há algum tempo não existia consenso sobre o zero ser Natural ou não.

Dizemos também que utilizamos um sistema posicional – desloque o número para esquerda ou direita ele assume centenas, dezenas, milhares, centésimos…

2. O sinal é outro símbolo

Certamente você já internalizou o conceito, mas se em engenharia os números são abstrações de grandezas físicas, o sinal sempre carrega outro significado. Se eu tenho +R$100,00 na conta-corrente esse dinheiro pode sair do banco e entrar no meu bolso. Se eu tenho -R$100,00, este dinheiro somente pode assumir a direção contrária. Um móvel com aceleração de -12m/s^2 permanece em repouso sob uma referência que acelera a 12m/s^2. Não à toa, os números negativos também são chamados de relativos, e ter isto em mente ajuda a entender como representá-los em um computador digital.

Vamos analisar um somador hipotético, sem sinal, que utiliza 3 bits para representar cada uma das suas parcelas, e também 3 bits para representar o resultado. Em notação decimal, as entradas variam de 0 a 7. Ao somarmos 7+7, por exemplo, a saída ‘estoura’:

 111
+111
====
1110

O importante aqui é você perceber que estamos trabalhando num universo onde o maior número possível de ser representado é o 7. E isto é exatamente o que ocorre quando construímos computadores. Se o meu computador pode somente ter 3 bits, é como se tudo o que tivéssemos fosse um conjunto de 8 elementos distintos.

(d.i) Definição. Um Grupo G é um conjunto de elementos em que se pode definir uma operação binária *, que satisfaz os critérios de fechamento, elemento neutro, elemento simétrico e associatividade. Um exemplo de grupo é o conjunto dos inteiros (Z) para as operações de soma e multiplicação.

G = {x, y, z} é um grupo, se para uma operação binária *, {G, *} satisfaz os seguintes axiomas:

a) fechamento: Se x e y ∈ G, x *y ∈ G
b) elemento neutro: Existe um elemento I ∈ G, tal que a*I = I*a = a,
c) elemento simétrico: Para todo elemento a ∈ G, existe um elemento s tal que a * s = I
d) associatividade: Para x, y, z ∈ G é verdadeiro que: x*y*z = (x*y)*z = x*(y*z)

A ideia de infinito não é concebível para uma máquina, e utilizaremos grupos finitos.

(d.ii) Definição. Um grupo finito é um conjunto finito de elementos com uma operação binária que satisfaz os axiomas do fechamento, associatividade, e cancelamento (Se a*x = b*x, a = b).

Para o meu computador de 3 bits talvez seria conveniente utilizarmos os conjuntos:

A= { 0, 1, 2, 3, 4, 5, 6, 7}, ou

B = { 16, 17, 18, 19, 20, 21, 22, 23} quem sabe.

Eu empilhei os conjuntos acima para forçar a ideia de congruência entre os elementos. Além disso, para a operação de adição +, os axiomas de (d.ii) são satisfeitos se definirmos: 7+1 =0 em A e 23+1=16 e A e B podem ser considerados grupos.

(d.iii) Definição. Dizemos que dois grupos são equivalentes quando existe uma relação biunívoca, tal que para todo elemento a ∈ A e b ∈ B, existe k inteiro tal que a = b + kN, onde N é o número de elementos (módulo) de A e B.

Utilizando os exemplos A e B acima:

2 = 18 + 8k, se k = -2

20 = 4 + 8k, se k = 2,

3. Subtração com números não-negativos

Talvez seja conveniente representarmos um grupo finito G onde o maior módulo possível é 8, na forma de um círculo de comprimento 8:

modulo

Desta forma, podemos representar qualquer número inteiro a = b + kN, onde k é o “número de voltas” dadas no círculo de comprimento N, e ‘b’ o restante de arco (em unidades) necessário para completar ‘a’, que chamamos de resto ou resíduo.

Assim, para o nosso grupo de módulo 8:
i) 21 = 5 + 2x8
ii) 64 = 0 + 8x8
iii) 10 = 2 + 1x8

Que podemos escrever da seguinte forma:
iv) 21 ≡ 5 (mod8) (21 é congruente a 5 módulo 8)
v) 64 ≡ 0 (mod8) (64 é congruente a 0 módulo 8)
vi) 10 ≡ 2 (mod8) (10 é conguente a 2 módulo 8)

Se eu quero resolver 8 – 6, posso evitar trabalhar com subtrações. Primeiro vamos pensar graficamente:

  • Partindo do zero e andando 8 unidades voltamos ao zero, ou: 8 ≡ 0 (mod8)
  • Partindo do zero e andando 6 unidades a esquerda, chegamos ao 2, ou: -6 ≡ 2 mod8

Logo: 8 (mod8) – 6 (mod8) ≡ 0 (mod8) + 2 (mod8) ≡ 2 (mod8).

Abaixo, com exemplos, descrevo um algoritmo para resolver subtrações utilizando números não-negativos em um grupo módulo N.

(p.1) Problema.
Resolva 15 – 8 somente com números não-negativos, em G = {0,1,2,3,4,5,6,7}
1o - Ache o minuendo congruente no grupo desejado. 
O ‘equivalente modulo 8’ de 15 pode ser encontrado em G com (1):
15 = b + 8k, se k = 1, b = 7.
2o - Ache o subtraendo equivalente ao grupo desejado e some ao minuendo:
O equivalente a 8 em G é 0.
8 = b + 8x1; b = 0
Assim:
7 + 0 = 7.
3o - Encontre o equivalente do resultado no grupo desejado:
7 já esta no grupo desejado, e é o resultado.

(p.2) Problema.
Resolva: 22 – 12, somente com números não negativos em 
G = {8,9,10,11,12,13,14,15}
O equivalente de 22 no grupo G é:
22 = a + 8k, k = 1, e a = 14 
Assim:
14 + 12 = 26
Cujo equivalente em {8, 9, 10, 11, 12, 13, 14, 15} é:
26 = b + k8, k = 2 e b = 10.

Uma pequena demonstração algébrica do método pode ser feita.
(dm.i) Demonstração.
Sejam M, S e D pontos do meu universo módulo N, de forma que:
(i) M-S=D para
(ii) M>=S e D <= N.
e
(iii) D = 0 para M=S.
Queremos demonstrar que:
(iv) D = N - [(N-M) + S]
O lado direito de (iv) satifaz (ii) para M>=S.
Ainda para M=S, (iii) é satisfeito: D=N-N-M+M=0
Naturalmente em (iv):
D= M-S = N-N+M-S
D = M-S
como queria demonstrar.

4. Complementos numéricos

(d.iv) Definição.
(d.iv’) O complemento de b de um número de n dígitos y, na base b, é dado por: b^n – y.
(d.iv’’) O complemento de b-1 de um número de n dígitos y, na base b, é dado por (b^n – 1) - y

Os livros em geral começam a tratando do assunto desta postagem com uma tabela:

 Elemento | Complemento de 9 
 ---------------------------
    0     |    9
    1     |    8
    2     |    7  
    3     |    6
    4     |    5
    5     |    4
    6     |    3
    7     |    2
    8     |    1
    9     |    0

Tabela 1. Complementos de 9 para dos inteiros de 0 a 9

O método dos complementos é uma aplicação direta da aritmética modular, e fundamentalmente utiliza dos mesmos conceitos explicados nas seções anteriores.

Podemos efetuar as subtrações somente com números não-negativos, usando o complemento do minuendo somado ao subtraendo, e tomando o complemento da soma como resposta.

8-3 → 1 + 3 = 4.

O complemento para 9 de 4 é 5, que é a nossa resposta.

Quando tratamos de números maiores que dezenas, fazemos o complemento para 99, 999, 9999… (nossa aritmética continua posicional!)

Exemplo:

Resolva 953 – 53 utilizando o método dos complementos, em módulo 9

046+ 53 = 99

Cujo complemento para 999 é 900, que é a nossa resposta.

5. Complemento de 2

A base para a representação numérica digital é a binária B = {0, 1}, e vamos utilizar os conceitos de aritmética modular para operarmos subtrações com números binários.

Decimal 0 a 7 | Binário | Congruentes
-----------------------------------------
      0       |   000   | ...,-8,0,8,...
      1       |   001   | ...,-7,1,9,...
      2       |   010   | ...,-6,2,10,...
      3       |   011   | ...,-5,3,11,...
      4       |   100   | ...,-4,4,12,...
      5       |   101   | ...,-3,5,13,...
      6       |   110   | ...,-2,6,14,...
      7       |   111   | ...,-1,7,15,...

Tabela 2. Inteiros decimais de 0 a 7 representados na forma binária, e seus congruentes módulo 8.

No nosso computador de três bits podemos representar a reta numérica com os pontos decimais 0 a 7, em base 2, da seguinte forma:

    b'    a'    a     b    c    d    e    f    g    h
    ?     ?    000  001  010  011  100  101  110  111
   ------------------------------------------------->

Queremos representar números negativos. Ora, 
Se a + s = 0, s é o simétrico de a se 0 representar o elemento neutro 
da álgebra.

No caso dos números representados na reta numérica acima:
a + s = 000 ↔ a' = 000; (000 + 000 = 000) 
b + s = 000 ↔ b’ = 111; (001 + 111 = 1000)
c + s = 000 ↔ c’ = 110; 
d + s = 000 ↔ d’ = 101;
e + s = 000 ↔ e’ = 100;
f + s = 000 ↔ f’ = 011;
g + s = 000 ↔ g’ = 001.

Exceto para f e g, todos os simétricos tem 1 no bit mais significativo, de forma que para lançar mão de números negativos poderíamos definir nosso grupo com os seguintes elementos escritos em base 2:

Decimal | Binário
------------------
  -4    | 100
  -3    | 101
  -2    | 110
  -1    | 111
   0    | 000
   1    | 001
   2    | 010
   3    | 011

Escolhemos não representar o 4, e sim o -4 a partir dos resultados empíricos para encontrar o elemento simétrico.

Perceba que continuamos com o mesmos elementos de antes, entretanto, atribuímos a ele um grupo equivalente, com elementos côngruos modulo 2, mantendo todas as propriedades que já tornavam aquele um grupo finito válido (definições d.i, d.ii, d.iii). É possível provar que o conjunto G = {100, 101, 110, 111, 000, 001, 010, 011} é um grupo finito.

O complemento de 2, do número binário y de três dígitos por (d.iv’) é então 8 – y. A representação binária do complemento de 2 de um número y, é utilizada para a representar o elemento simétrico s, tal que y + s = 0.  Como regra prática dizemos que o complemento de 2 de um número na base 2, é sua negação adicionada a 1. (Pense em um círculo somente com os pontos 0 e 1 na base 2, e comprove graficamente por que funciona).
Interpretação do '1' como sinal: 

Peguemos como exemplo a igualdade 011 + 101 = 1000, que poderia significar 3 + 5 = 8, que é côngruo a 0 módulo 8. Ainda na base 2, oito é representado por 1000. O ‘1’ se pensado como sinal, indica o sentido pelo qual ultrapassamos a origem ao representarmos nossos arcos de maneira contínua. Andando da esquerda para direita os elementos assumem valores cada vez maiores. Quando os 3 bits estouram e o vai-um é necessário para representar o estado naquele instante , significa que os elementos agora estão assumindo valores cada vez mais negativos em relação aos anteriores.

Você pode experimentar efetuar as operações com o complemento de 2 e verificar como a notação é muito conveniente.

Note que:
O complemento de 2 é definido para representar números de base 2, de
N bits, no intervalo de -2^(N-1) a 2^(N-1) – 1.
Ao operarmos representações com números de dígitos diferentes, devemos estender o sinal. 
Exemplo:

-16 - 2 =
 10000
+11110
======
101110
O texto deste artigo é original. As seguintes referências foram consultadas durante sua elaboração:
Conceitos Fundamentais da Matemática (Bento Jesus de Caraça)
Introduction to Logic Circuits and Logic Design With Verilog (Brock J. LaMeres)
Group Theory, em https://crypto.stanford.edu/pbc/notes/group/group.html
Introdução à Teoria dos Números, em http://vigo.ime.unicamp.br/Projeto/2012-1/ms777/ms777_Viviane.pdf