Meu Kernel, Minha Vida – Escalonador Cooperativo com Lista Circular

Continuando a serie Meu Kernel, minha vida, nesse artigo será apresentado uma nova implementação do kernel cooperativo, utilizando 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

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.

Notificações
Notificar
guest
0 Comentários
Inline Feedbacks
View all comments

WEBINAR

Imagens de Ultrassom: Princípios e Aplicações

DATA: 26/10 ÀS 19:30 H