Meu Kernel, Minha Vida – Escalonador Cooperativo com Lista Circular

11/04/2019

ÍNDICE DE CONTEÚDO

Este post faz parte da série Meu Kernel, Minha Vida

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”.

/*  estrutura de No*/
struct no
{
    <tipo da variável> dado; 
    struct no *próximo;
};

/* declaração do No*/
typedef struct no
{
    int data;
    struct no next;
}list_t;

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

Os Melhores Treinamentos sobre Sistemas embarcados e IoT

Cursos com professores qualificados para acelerar sua carreira e projetos

MATRÍCULE-SE AGORA

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.

/* Função de inicialização de lista */ 
lista_t* list_init(void)
{
    return NULL;
}

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.

/*  Função de inserção de elementos */
list_t* list_insert(list_t* list, int data)
{
    list_t * new = (list_t*)malloc( sizeof(list_t) );
    new->data = data;
    new->next = list;
    return new;
}

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.

/* Função busca elemento na lista */
list_t* list_search (list_t* list, int data)
{
  list_t* aux;
  for (aux = 1; aux != NULL; aux = aux->next;
  {
  if (aux->data == data)
    {
      return aux;
    }
  }
  return NULL;
}

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.

/* Remove item da lista  */
list_t* list_remove (list_t* list, int data)
{
  list_t* previous  = NULL;
  list_t* aux = list;

  while ( aux != NULL && aux->data != data)
  {
    previous = aux;
    aux = aux->next;
  }
  if ( aux == NULL )
  {
    return list;
  }
  if ( previous == NULL )
  {
    list = aux->next;
  }
  else
  {
    previous->next = aux->next;
  }
  free( aux );
  return list;
}

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.

/* Função que apaga  lista */
void list_delete( list_t* list)
{
  list_t* aux = list;
  while ( aux != NULL )
  {
    list_t* no_next = aux->next;
    free( aux );
    aux = no_next;
  }
}

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

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

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

/*
   kernel.h
        Author: Evandro Teixeira
*/

#ifndef KERNEL_KERNEL_H_
#define KERNEL_KERNEL_H_

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include "MK22F51212.h"

#ifndef ptrTask
typedef void(*ptrTask_t)(void);
#endif

#ifndef kernel_tick
typedef uint32_t kernelTick_t;
#endif

#ifndef idTask
typedef uint8_t idTask_t;
#endif

#ifndef KERNEL_NULL
#define KERNEL_NULL ((void *)0)
#endif

typedef enum
{
  kernel_fail = false,
  kernel_ok = true,
} kernelStatus_t;

typedef enum
{
  kernel_task_running = true,
  kernel_task_waiting = false,
} kernelTask_t;

typedef enum
{
  Task_Ready = 0,
  Task_Blocked,
  Task_Paused,
  //Task_Deleted,
} stateTask_t;

typedef enum
{
  Priority_Idle = 0,
  Priority_Low,
  Priority_Medium,
  Priority_High,
} priorityTask_t;

typedef struct
{
  ptrTask_t task;
  stateTask_t state;
  priorityTask_t priority;
  kernelTick_t pausedtime;
  kernelTask_t kernel_task_state;
} strTask_t;

/**
   Parametros da Lista
*/
typedef struct no
{
  idTask_t index;
  strTask_t param;
  struct no * next;
} noKernel_t;


void kernel_init(void);
void kernel_run(void);
void kernel_add_task_ilde(ptrTask_t task);
idTask_t kernel_add_task(ptrTask_t task, priorityTask_t priority, stateTask_t state);
void kernel_task_delete(idTask_t index);
void kernel_task_delay(idTask_t id, kernelTick_t tick);
void kernel_idle(idTask_t id);

#endif /* KERNEL_KERNEL_H_ */

Código fonte do kernel.c

/*
   kernel.c
        Author: Evandro Teixeira
*/
#include "kernel.h"
/**

*/
static idTask_t id = 0;
static ptrTask_t idleTask;
static kernelTick_t kernelTick = 0;
noKernel_t* kernel_list;
noKernel_t* kernel_list_init;
idTask_t id_idle;

/**

*/
noKernel_t* kernel_init_list(void);
noKernel_t* kernel_list_insert(noKernel_t* list, idTask_t index, strTask_t param);
noKernel_t* kernel_list_get(noKernel_t* list, idTask_t index);
noKernel_t* kernel_list_remove(noKernel_t* list, idTask_t index, idTask_t max);
void kernel_list_delete(noKernel_t* list);
void kernel_task_idle(void);
void kernel_tick_init(void);
uint32_t kernel_tick_get(void);
/**

*/
void kernel_init(void)
{
  kernel_tick_init();
  kernel_list = kernel_init_list();
  id_idle = kernel_add_task(kernel_task_idle, Priority_Idle, Task_Ready);
}

/**

*/
void kernel_task_delay(idTask_t index, kernelTick_t tick)
{
  uint8_t i = 0;

  for (i = 0; i < id; i++)
  {
    if (kernel_list->index == index)
    {
      kernel_list->param.pausedtime = tick + kernel_tick_get();
      kernel_list->param.state = Task_Paused;
      break;
    }
    kernel_list = kernel_list->next;
  }
}

/**

*/
void kernel_run(void)
{
  ptrTask_t taskRun = {KERNEL_NULL};
  idTask_t index = 0;

  while (1)
  {
    // Checa se existe alguma tarefa pausada
    for (index = 0; index < id; index++)
    {
      if (kernel_list->param.state == Task_Paused)
      {
        if (kernel_list->param.pausedtime <= kernel_tick_get())
        {
          kernel_list->param.state = Task_Ready;
        }
      }

      kernel_list = kernel_list->next;
    }

    // Busca tarefa de alta prioridade
    for (index = 1; index < (id + 1); index++)
    {
      if ( (kernel_list->param.state == Task_Ready) &&
           (kernel_list->param.priority == Priority_High) &&
           (kernel_list->param.kernel_task_state == kernel_task_waiting))
      {
        taskRun = kernel_list->param.task;
        kernel_list->param.kernel_task_state = kernel_task_running;
        break;
      }

      kernel_list = kernel_list->next;
    }
    if (index > id)
    {
      // Busca tarefa de media prioridade
      for (index = 1; index < (id + 1); index++)
      {
        if ( (kernel_list->param.state == Task_Ready) &&
             (kernel_list->param.priority == Priority_Medium) &&
             (kernel_list->param.kernel_task_state == kernel_task_waiting))
        {
          taskRun = kernel_list->param.task;
          kernel_list->param.kernel_task_state = kernel_task_running;
          break;
        }

        kernel_list = kernel_list->next;
      }
      if (index > id)
      {
        // Busca tarefa de baixa prioridade
        for (index = 1; index < (id + 1); index++)
        {
          if ( (kernel_list->param.state == Task_Ready) &&
               (kernel_list->param.priority == Priority_Low) &&
               (kernel_list->param.kernel_task_state == kernel_task_waiting))
          {
            taskRun = kernel_list->param.task;
            kernel_list->param.kernel_task_state = kernel_task_running;
            break;
          }

          kernel_list = kernel_list->next;
        }
        if (index > id)
        {
          // Busca tarefa de Idle
          for (index = 1; index < (id + 1); index++)
          {
            if ( (kernel_list->param.state == Task_Ready) &&
                 (kernel_list->param.priority == Priority_Idle) &&
                 (kernel_list->param.kernel_task_state == kernel_task_waiting))
            {
              taskRun = kernel_list->param.task;
              kernel_list->param.kernel_task_state = kernel_task_running;
              break;
            }

            kernel_list = kernel_list->next;
          }
          if (!(index > id))
          {
            kernel_list->param.kernel_task_state = kernel_task_waiting;
          }
        }
        else
        {
          kernel_list->param.kernel_task_state = kernel_task_waiting;
        }
      }
      else
      {
        kernel_list->param.kernel_task_state = kernel_task_waiting;
      }
    }
    else
    {
      kernel_list->param.kernel_task_state = kernel_task_waiting;
    }

    if (taskRun != KERNEL_NULL)
      taskRun();
  }
}

/**

*/
idTask_t kernel_add_task(ptrTask_t task, priorityTask_t priority, stateTask_t state)
{
  strTask_t param;
  param.pausedtime = 0;
  param.priority = priority;
  param.state = state;
  param.task = task;
  param.kernel_task_state = kernel_task_waiting;
  kernel_list = kernel_list_insert(kernel_list, ++id, param);
  return id;
}

/**

*/
void kernel_add_task_ilde(ptrTask_t task)
{
  idleTask = task;
}

/**

*/
void kernel_task_idle(void)
{
  if (idleTask != KERNEL_NULL)
    idleTask();
}

/**

*/
void kernel_task_delete(idTask_t index)
{
  kernel_list = kernel_list_remove(kernel_list, index, id);
}

/**

*/
void kernel_idle(idTask_t id)
{
  kernel_task_delay(id, 0);
}

/*************** List ********************************************/
/**
   @brief
*/
noKernel_t* kernel_init_list(void)
{
  return KERNEL_NULL;
}

/**

*/
noKernel_t* kernel_list_insert(noKernel_t* list, idTask_t index, strTask_t param)
{
  static noKernel_t* init_no;
  noKernel_t* new_no = (noKernel_t*)malloc(sizeof(noKernel_t));

  // checa se lista já possui algum elemento
  if (list == KERNEL_NULL)
  {
    init_no = new_no;
  }
  else
  {
    list->next = new_no;
  }

  new_no->index = index;
  new_no->param = param;
  new_no->next = init_no;
  return new_no;
}

/**

*/
noKernel_t* kernel_list_get(noKernel_t* list, idTask_t index)
{
  noKernel_t* item;
  for (item = list; item != KERNEL_NULL; item = item->next)
  {
    if (item->index == index)
      return item;
  }
  return KERNEL_NULL;
}

/**

*/
noKernel_t* kernel_list_remove(noKernel_t* list, idTask_t index, idTask_t max)
{
  idTask_t i = 0;
  noKernel_t* previous;// = list;
  noKernel_t* item = list;

  for (i = 1; i < (max + 1); i++)
  {
    previous = item;
    if (item->index == index)
    {
      item = item->next;
      break; // achou
    }
    //previous = item;
    item = item->next;
  }
  if (i > max)
  {
    return list;
  }
  else
  {
    // Busca o no que aponta para index que  deseja remover
    noKernel_t* no = item;

    for (i = 1; i < (max + 1); i++)
    {
      if (no->next == previous)
      {
        no->next = previous->next;
        break; // achou
      }
      no = no->next;
    }
    if (i > max)
    {
      return list;
    }

    free(previous);
    previous->next = item->next;
    return no;
  }
}

/**

*/
void kernel_list_delete(noKernel_t* list)
{
  noKernel_t* aux = list;
  while (aux != KERNEL_NULL)
  {
    noKernel_t* no_next = aux->next;
    free(aux);
    aux = no_next;
  }
}

/**

*/
void kernel_tick_init(void)
{
  uint32_t ticks = SystemCoreClock / 1000;
  SysTick->LOAD  = ticks - 1;
  SysTick->VAL   = 0;
  SysTick->CTRL  = SysTick_CTRL_CLKSOURCE_Msk | SysTick_CTRL_TICKINT_Msk | SysTick_CTRL_ENABLE_Msk;

  NVIC_EnableIRQ(SysTick_IRQn);
}

/**

*/
uint32_t kernel_tick_get(void)
{
  return kernelTick;
}

/**

*/
void SysTick_Handler(void)
{
  kernelTick++;
}

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

/**
   This is template for main module created by New Kinetis SDK 2.x Project Wizard. Enjoy!
 **/

#include "board.h"
#include "pin_mux.h"
#include "clock_config.h"
#include "fsl_common.h"
#include "fsl_port.h"
#include "../kernel/kernel.h"

#define DELAY_LED_GREEN    50000

void task_led_red(void);
void task_led_blue(void);
void task_led_green(void);

idTask_t red, blue;

/*!
   @brief Application entry point.
*/
int main(void)
{
  /* Init board hardware. */
  BOARD_InitPins();
  BOARD_BootClockRUN();
  BOARD_InitDebugConsole();

  /* Add your code here */
  CLOCK_EnableClock(kCLOCK_PortA);
  CLOCK_EnableClock(kCLOCK_PortD);
  PORT_SetPinMux(PORTA, 1U, kPORT_MuxAsGpio);
  PORT_SetPinMux(PORTA, 2U, kPORT_MuxAsGpio);
  PORT_SetPinMux(PORTD, 5U, kPORT_MuxAsGpio);

  // Inicializa LED's
  LED_RED_INIT(LOGIC_LED_OFF);
  LED_BLUE_INIT(LOGIC_LED_ON);
  LED_GREEN_INIT(LOGIC_LED_OFF);

  // Inicializa kernel
  kernel_init();

  // Adiciona tarefa no kernel
  red = kernel_add_task(task_led_red, Priority_High, Task_Ready);
  blue = kernel_add_task(task_led_blue, Priority_High, Task_Ready);
  kernel_add_task_ilde(task_led_green);

  // Executa Kernel
  kernel_run();

  for (;;)
  {
    /* Infinite loop to avoid leaving the main function */
    __asm("NOP"); /* something to use as a breakpoint stop while looping */
  }
}

/**

*/
void task_led_red(void)
{
  static uint8_t counter = 0;

  LED_RED_TOGGLE();

  counter++;
  if (counter > 20)
  {
    // Deleta Task RED
    counter = 0;
    kernel_task_delete(red);
    return;
  }
  // Pausa Task RED por 1000 tick's
  kernel_task_delay(red, 1000);
}

/**

*/
void task_led_blue(void)
{
  static uint8_t counter = 0;

  LED_BLUE_TOGGLE();

  counter++;
  if (counter > 40)
  {
    counter = 0;
    red = kernel_add_task(task_led_red, Priority_High, Task_Ready);
  }
  // Pausa Task BLUE por 2000 tick's
  kernel_task_delay(blue, 2000);
}

/**

*/
void task_led_green(void)
{
  static uint32_t i = 0;

  i++;
  if (i > DELAY_LED_GREEN)
  {
    i = 0;
    LED_GREEN_TOGGLE();
  }
}

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.