Lidando com Wrap Around em contadores

Por

24/01/2014

Em qualquer tipo de sistema existem aqueles contadores de frequência de eventos, tanto em hardware quanto em software. Com relação à implementação em hardware, pode-se citar, como exemplo, o periférico em silício chamado time counter que existe em todos os controladores e processadores modernos. Já com relação à presença de contadores em software, é muito utilizado o tick counter, encontrado nas implementações de sistemas operacionais, desde o FreeRTOS até o Linux. Em termos de software ainda, pode-se mencionar também qualquer contador de eventos que o programador tenha que inserir no seu sistema, como quando é necessário medir qual a frequência que um pacote de dados é recebido.

O mistério sobre esses contadores é que são incrementados livremente, geralmente sem qualquer controle. No caso de software por questões de desempenho, e no caso de hardware por razões de tangibilidade. Essencialmente, precisam ser operados atomicamente para eliminar a problemática da concorrência. Além disso, lidar com wrap around em contadores pode criar um código menos legível devido aos condicionais.

Adota-se como exemplo, neste artigo, a criação de uma função de timeout baseada em um contador de tempo de unsigned int, onde time_now() retorna o valor atual do contador de tempo e é dependente de plataforma. Abaixo construímos a função que verifica se um timeout aconteceu.

unsigned int time_now();

/* Returns true if has elapsed `delay` time since `start`, 
   otherwise returns false. */
bool timeout_check(unsigned int delay, unsigned int start)
{
    return ( !( (time_now() - start) < delay) );
}

unsigned int time_now();

/* Returns true if has elapsed `delay` time since `start`,

otherwise returns false. */

bool timeout_check(unsigned int delay, unsigned int start)

{

return ( !( (time_now() - start) < delay) );

}

A subtração no corpo do timeout_check é responsável em anular o efeito do wrap around. Quando incide, no contador que conta o tempo e é obtido por time_now(), o primeiro operando da subtração fica menor que o segundo, mas, graças ao limite de bits, o resultado dessa subtração se mantém correto. Sendo a exata diferença desejada independente da incidência de um wrap around.

Abaixo um exemplo de uso da função timeout_check.

unsigned int start = time_now();

while (!timeout_check(10, start))
{
    /* Executa este loop pelo menos por
       10 períodos do contador de tempo */
}

unsigned int start = time_now();

while (!timeout_check(10, start))

{

/* Executa este loop pelo menos por

10 períodos do contador de tempo */

}

A técnica da subtração é válida para qualquer tipo, inteiro ou não, de qualquer largura de bits, contanto que todas as variáveis que participam da operação sejam do mesmo tipo, inclusive o contador, e, contanto que, ocorra apenas um único wrap around. No Codepad encontra-se um teste em C da técnica apresentada: http://codepad.org/WjoIpV85.

Devido a sua simplicidade, a técnica é largamente usada, a exemplo da variável jiffies, acessível de dentro do kernel do Linux (#include <linux/jiffies.h>) que tem a função de contar ticks do sistema operacional, onde suas funções auxiliares fazem uso da subtração apresentada.