Meu Kernel, Minha Vida – Escalonador Cooperativo com Lista Circular

Este post faz parte da série Meu Kernel, Minha Vida. Leia também os outros posts da série:

Olá caro leitor, tudo bem? Dando continuidade na série de artigos Meu Kernel – Minha Vida. Nos dois primeiros artigos foram apresentados os conceitos básico de kernel cooperativo e Round-Robin, com demonstração de código-fonte e exemplo de aplicação. Neste artigo será apresentado uma nova implementação do kernel cooperativo, utilizando Lista Circular, além de uma breve introdução sobre Lista. Também será apresentado o código-fonte do kernel e uma aplicação de demonstração.

Lista Encadeada

Lista encadeada ou lista ligada é uma série elementos, todos do mesmo tipos interligados. Cada elemento da série é uma célula da lista. As célula essencialmente é composta por dois itens; o primeiro informação ou dado, o segundo item é endereço da próxima célula (um ponteiro).

Lista Circular
Imagem que ilustra a composição de célula

A célula de uma lista basicamente é estrutura, composta por uma variável onde será armazenada a informação, outro item da estrutura é um ponteiro, onde será armazenado o endereço da próxima célula. Essa estrutura de dados comumente é chamado de “nó” ou de “registro”.

Lista Circular
Imagem que ilustra Lista encadeada com as série de elemento

Para manipulação de listas, necessita de algumas operações fundamentais, são elas:

criação / inicialização,

O processo de criação (ou inicialização) é criar uma lista vazia, sem nenhum elemento. A lista é representado por ponteiro que aponta para um determinado elemento, já uma lista vazia é representado por ponteiro que aponta para um endereço nulo (NULL), pois a lista não possui nenhum elemento.

inclusão / inserção,

Uma vez que uma lista foi inicializada, podemos inserir elementos nela. Todo elemento que inserido na lista, deve ser alocado dinamicamente, o espaço ocupado na memória por cada elemento e encadeá cada novo elemento na lista.

busca,

Função que realiza a busca de um determinado elemento na lista. A função recebe a informação referente ao elemento que deseja ser buscado e fornece como resposta o ponteiro com endereço do elemento desejado.

Para os caso no qual o valor informado não corresponder a nenhum elemento da lista, a função retorna o valor nulo (NULL).

remoção,

Outra função que é muito importe é recurso de remover elemento da lista. Esse processo recebe como parâmetro a informação do elemento que deseja remover da lista.

destruição / deletar

E por fim temos a função que deleta a lista. Essa função libera os espaços alocado em memória de cada elemento que foi inserido na lista.

Lista encadeada pode ser utilizada em diversos algoritmos, onde se faz necessário obter a representação uma sequência de objetos (dados) do mesmo tipo. Diferente de vetor (ou array) que se faz necessário informar o número de elementos, no momento de sua criação, a lista é mais dinâmica, podendo assim adicionar e remover elementos a qualquer momento do código fonte, sem se preocupar com a quantidade de elementos.

Nota: A preocupação com a quantidade de memória utilizada ainda continua.

Lista Circular
Removendo item da lista

Lista Circular

A principal diferença entre lista encadeada e lista circular, é que o último elemento da lista circular aponta para o primeiro item da lista, assim obtendo uma estrutura de dados circular. Enquanto na lista encadeada o último elemento da lista aponta para um endereço nulo (NULL).

A lista circular conta com o mesmo recursos de;

  • criação / inicialização,
  • inclusão / inserção,
  • busca,
  • remoção,
  • destruição / deletar
Lista Circular
Lista Circular

Mudando apenas alguns detalhes em sua implementação, que tem como objetivo garantir a representação de forma cíclica do seu conjunto de elementos.

O kernel

O kernel desenvolvido segue com a mesma estrutura utilizada no primeiro artigo da série (Meu Kernel – Minha Vida, que conta com escalonador cooperativo). Na verdade algoritmo passou por um upgrade, trocando o vetor por uma lista circular em seu escalonador. A seguir é apresentado resultado do novo kernel cooperativo.

Código fonte do kernel.h

Código fonte do kernel.c

O projeto de demonstração

O projeto de demonstração utiliza o NXP Freedom Board K22F, que conta com o microcontrolador ARM Cortex-M4 que contém as seguintes características: MK22FN512VLH12 MCU – 120 MHz, 512 KB memória Flash, 128 KB memória RAM.

O algoritmo contém três tarefas que inverte o valor do GPIO que possuem os LED’s. Sendo que a tarefa “task_led_red” realizar uma contagem de execução, e quando essa contagem atinja o valor de 20, a tarefa “task_led_red” é removida do escalonador do kernel. A tarefa “tarefa_led_blue” também realiza a contagem de execução, quando a contagem chegar ao número 40, é adicionado novamente ao escalonador a tarefa “task_led_red”.

Código fonte do main.c

Conclusão

Objetivo neste artigo foi apresentando os conceitos básicos de lista encadeada e circular e demonstração da utilização de lista circular para realizar o “upgrade” no kernel cooperativo.
Próximos passos… É estudar sobre a troca de contexto e as técnicas existentes para o mesmo. E assim conseguir desenvolver kernel preemptivo. Assim que for evoluindo nos meus estudos, prometo trazer mais artigos relacionados ao assunto.

O código fonte do projeto com aplicação e kernel deixei disponível no meu Github. E fica aqui o meu convite a você caro leitor, que se interessou pelo assunto, a contribuir com o projeto, testando e aperfeiçoando o mesmo.

Referencia 

https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html
https://www.cprogressivo.net/2013/10/Como-fazer-uma-lista-em-C.html
https://pt.wikipedia.org/wiki/Lista_ligada
http://www.ic.unicamp.br/~ra069320/PED/MC102/1s2008/Apostilas/Cap10.pdf
https://github.com/evandro-teixeira/kernel_lista_circular
https://www.nxp.com/support/developer-resources/evaluation-and-development-boards/freedom-development-boards/mcu-boards/nxp-freedom-development-platform-for-kinetis-k22-mcus:FRDM-K22F

Outros artigos da série

<< Meu Kernel Minha Vida – Round-Robin
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 » Meu Kernel, Minha Vida - Escalonador Cooperativo com Lista Circular
Comentários:
Notificações
Notificar
guest
0 Comentários
Inline Feedbacks
View all comments
Talvez você goste:

Séries



Outros da Série

Menu

WEBINAR
 
Porque o RTOS não faz o que eu quero?

Data: 28/10 às 19:30h - Apoio: Mouser Electronics
 
INSCREVA-SE AGORA »



 
close-link