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
Este post faz da série Meu Kernel, Minha Vida. Leia também os outros posts da série:
NEWSLETTER

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

Obrigado! Sua inscrição foi um sucesso.

Ops, algo deu errado. Por favor tente novamente.

Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Evandro Teixeira
Desenvolvedor de Sistemas Embarcados. Sou formado Técnico em Instrumentação e Automação Industrial/Mecatrônica pelo Colégio Salesiano Dom Bosco de Americana-SP, cursei o Engenharia Elétrica com Ênfase em Eletrônica pela UNISAL Centro Universitário Salesiano de São Paulo e atualmente estou cursando Superior de Tecnologia em Análise e Desenvolvimento de Sistemas pela UNIP Universidade Paulista.

Deixe um comentário

avatar
 
  Notificações  
Notificar