6 Comentários

Desenvolvendo um RTOS: Utilizando buffer circular como gestor de processos

buffer circular
Este post faz parte da série Desenvolvendo um RTOS. Leia também os outros posts da série:

Nos primeiros artigos falamos sobre o que é um sistema operacional e como descrever/implementar um processo. Neste artigo eu e o Marcelo vamos falar sobre como desenvolver uma estrutura para gestão destes processos, ou seja, como criar o próprio kernel.

Para gerenciar a execução dos processos é necessário armazenar suas referências de algum modo. Existem diversos modos de se criar uma estrutura de dados para armazenamento/gerenciamento de informações. Visando equilibrar a simplicidade de operação com recursos disponíveis optamos por utilizar um buffer circular.

Buffers são regiões de memória que servem para armazenar dados temporários. Os buffers circulares podem ser implementados utilizando uma lista linkada, onde o último elemento se conecta com o primeiro. O problema dessa abordagem é o gasto extra de memória para colocar os ponteiros da lista. O modo mais "econômico" é utilizar apenas um vetor com dois índices, indicando o início e o fim do buffer. Os elementos devem ser adicionados no "fim" do vetor e removidos no "início". A declaração destas variáveis é bastante simples:

A cada inserção de elementos a variável fim é incrementada. A cada remoção de elementos a variável ini é incrementada. Quando as variáveis fim ou ini chegam no final do vetor, elas devem voltar a apontar para a posição zero. Apesar de ser chamado circular, na memória o buffer é armazenado como um vetor sequencial, conforme a figura a seguir.

 buffer circular como gestor de processos

O buffer vazio indica que não existe nenhum elemento de interesse armazenado no buffer. Isso não quer dizer que o vetor está vazio. Na verdade, existem valores armazenados em cada posição, só que esses valores não tem importância para a aplicação, sendo geralmente chamados de lixo. Esses valores são resultados de cálculos anteriores de variáveis temporárias ou qualquer outra função do processador.

O indice fim sempre aponta para uma posição "disponível" na memória, ou seja, que pode receber um valor. Deste modo, adicionando 2 elementos no buffer temos a seguinte representação

 buffer circular como gestor de processos

A remoção de um elemento significa incrementar o indice ini, "removendo" o item da lista de itens úteis. Podemos notar na figura abaixo que o elemento não é fisicamente removido do buffer, mas agora ele está na região de elementos que consideramos como lixo. Todos os elementos válidos estão entre o índice ini e o índice fim.

 buffer circular como gestor de processos

Ao adicionar mais dois elementos o índice fim passa a apontar para a última posição linear do vetor: a posição 4. Nesta situação o buffer possue três elementos válidos ('B', 'C' e 'D') e duas posições com lixo (apesar de sabermos que a posição 0 possui o valor 'A', neste momento ele é um lixo na memória).

 buffer circular como gestor de processos

Como o sistema será desenvolvido para que o vetor se comporte como um buffer circular, quando adicionarmos o último elemento no buffer o índice fim passa a valer zero e, nesse momento, a posição 0 poderá ser reescrita.

 buffer circular como gestor de processos

Como pode ser visto na sequência acima, a próxima posição livre é sempre uma unidade à frente da posição atual, exceto quando o índice aponta para a última posição do vetor.

Para simplificar o processo de procura da próxima posição, podemos utilizar um incremento seguido do resto de divisão pelo tamanho do vetor. Esse processo pode ser definido com o seguinte código:

O resto da divisão faz com que o resultado retorne para zero sempre que o índice ultrapassar o final do vetor. Esta é uma estratégia simples, mas com um custo computacional maior pois requer uma operação de cálculo de resto da divisão. Se processamento mais baixo for um requisito para o seu projeto, faça a verificação por teste de limites, mesmo que isto gere um código maior, como no código abaixo:

Um problema que aparece no gerenciamento de buffers circulares é definir quando o vetor está cheio ou vazio, já que, em ambos os estados, o indicador de inicio e fim estão no mesmo local.

Existem pelo menos 3 alternativas de se resolver este problema: manter um slot sempre aberto, usar um indicador de cheio/vazio ou contar a quantidade de leituras/escritas. Procurando manter o código mais simples possível optamos por manter sempre um slot vazio.

O processo de adicionar elementos no buffer consiste em atribuir um valor ao elemento apontado pelo índice fim.  No entanto devemos primeiro verificar se o buffer não está cheio.

Quando o buffer estiver vazio, os índices ini e fim possuem o mesmo valor. Quando o buffer estiver cheio, o índice fim está uma posição atrás de ini.

Para verificar se o buffer não está cheio podemos verificar se a próxima posição do índice fim não é igual ao índice  ini, ou seja, se incrementando fim ele não sobrepõe o valor de ini

Para remover um elemento, devemos verificar se o buffer não está vazio, ou seja, se o índice ini é diferente de fim. Sendo diferente podemos remover o elemento do buffer, simplesmente incrementando o índice ini

Note que nada é feito com a posição do buffer. Na verdade, o valor antigo continua armazenado no vetor. Com o uso do buffer esse valor será eventualmente sobreescrito.

Estamos prontos agora para implementar a primeira versão do kernel, utilizando um buffer circular como estrutura de dados de armazenamento dos processos.

Implementando um kernel com buffer circular

Nesta primeira versão os processos serão implementados como funções, e o gerenciamento dos processos será feito através de um buffer circular. O código do kernel pode ser dividido em três seções:

  1. criação dos processos;
  2. rotinas do kernel;
  3. função principal.

1 - Processos

As funções que serão executadas pelo kernel (tst1(), tst2(), tst3()) passarão a ser denominadas processos, com ideia semelhante aos processos de um desktop. Além disso, todos os processos têm que ter a mesma assinatura do ponteiro ptrFunc, no caso void F(void);

2 - Kernel

Este primeiro kernel possui três funções: uma para inicializar as variáveis internas, uma para adicionar processos no buffer circular e uma para executar o kernel. Em geral, a função que executa o kernel possui um loop infinito. Nesta primeira versão apenas executamos as funções na ordem em que foram passadas. Não existe nenhum outro tipo de controle sobre os processos, isto fica para o próximo artigo.

3 - Rotina Principal

Utilizar o kernel desenvolvido é bastante simples. Com os processos já implementados de acordo com a assinatura padrão, basta:

  1. inicializar o sistema;
  2. adicionar os processos que devem ser executados na ordem em que serão executados e, por fim;
  3. executar o kernel.

Esta primeira versão do kernel é capaz de receber os processos (codificados como ponteiros de funções) e executá-los sequencialmente. O próximo passo é fazer com que a função ExecutaKernel() seja capaz de gerenciar os processos, reexecutando-os e tomando decisões sobre qual é o próximo a ser executado.

Outros artigos da série

<< Desenvolvendo um RTOS: processos e tarefas
Este post faz da série Desenvolvendo um RTOS. Leia também os outros posts da série:
Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Software » Desenvolvendo um RTOS: Utilizando buffer circular como gestor de processos
Talvez você goste:
Comentários:

6
Deixe um comentário

avatar
4 Comentários
2 Respostas
0 Seguidores
 
Discussão de maior alcance
Discussão mais quente
5 Autores de comentários
Marlon PedersoliCleiton BuenoRodrigo AlmeidaJosué LimaRodrigo Arnhold Comentários recentes
  Notificações  
recentes antigos mais votados
Notificar
Marlon Pedersoli
Visitante
Marlon

Onde posso compilar o projeto para ve-lo funcionando?

Cleiton Bueno
Visitante

Estão de parabéns, esta serie esta ficando excelente.

Notei que na função addBuff() na linha três esta recebendo a variável 'elemen' que não existe.

Abraço.

Josué Lima
Visitante
Josué Lima

Rodrigo Almeida, em primeiro lugar parabéns por esta série de artigos e também pelos demais conteúdos disponibilizados em seu website (Estou estudando o projeto do MicroKernel).

Me permita fazer uma observação. Na função que procura pela próxima posição disponível, o correto não seria if((elem+1) < BUFFSIZE) ao invés de if((elem+1) <= BUFFSIZE)? Abç!

Rodrigo Almeida
Visitante
Rodrigo Almeida

Olá Josué,
A sua afirmação está correta! Como BUFFSIZE é utilizado para informar o tamanho do vetor, e os indices em C começam em zero, o fim é "BUFFSIZE-1", portanto temos que usar apenas o menor, ao invéz de menor igual.

Erro meu em não ter testado a fundo as duas opções de funções.

Obrigado por apontar!

Rodrigo Arnhold
Visitante
Rodrigo Arnhold

Um pequeno detalhe. Pode ser que para você tenha funcionado. Mas para quem não conseguiu que nem eu. Deve se mudar a rotina "next", nela o return elem++, não funciona.
Tive que trocar por elem +=1.
Só uma dica para quem vier a testar.

Rodrigo Almeida
Visitante
Rodrigo Almeida

Obrigado Rodrigo,
Realmente dá errado com a rotina do jeito que estava escrito. O comportamento da expressão "return elem++", incrementa a variável e *depois* incrementa a variável, portanto vem o valor anterior no return. Trocar por "return elem +=1" funciona pois o operador atribuição tem prioridade sobre o return. O melhor nesse caso é trocar por "return (elem+1)" pois economiza uma atribuição.

Erro meu em não testar as duas opções!

Obrigado por apontar!

Séries



Outros da Série

Menu