Meu Kernel Minha Vida - Round-Robin

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? Vamos dar continuidade à série de artigos sobre desenvolvimento de Kernel. No último artigo, Meu Kernel Minha Vida, foram apresentados os conceitos básicos de kernel cooperativo e o código-fonte do projeto desenvolvido. Para este artigo serão apresentados conceitos básicos de kernel preemptivo do tipo Round-Robin, o código-fonte do kernel desenvolvido e a aplicação de demonstração.

 

 

Escalonador Round-Robin

O Round-Robin é um algoritmo escalonador de tarefas (processos) que consiste em dividir o tempo de uso da CPU (Central Processing Unit). Cada processo recebe uma fatia de tempo, esse tempo é chamado Time-Slice, também conhecido por Quantum. Os processos são todos armazenados em Fila (Buffer) circular. O escalonador executa cada tarefa pelo tempo determinado pelo Time-Slice e ao fim deste período é executada a troca de contexto, onde o próximo processo fila passa a ser executado pela CPU até percorrer o período do Time-Slice. Após percorrer todos os processos da fila, essas atividades se repetem e o escalonador aponta para a primeira tarefa. A figura a seguir ilustra bem todo esse processo.

 

Buffer Circular
Figura 1 - Buffer Circular

 

 

Kernel Preemptivo

Como dito anteriormente, trata-se de um kernel preemptivo do tipo Round-Round. Antes de descrever sobre o projeto desenvolvido, serão apresentadas as principais características de sistema preemptivo, são elas:

  • O uso de maneira uniforme da CPU entre os processos da aplicação;
  • Troca de contexto.

 

A troca de contexto é um recurso computacional de armazenar e restaurar o estado de uma tarefa em um sistema de múltiplos processos. Por um lado, é uma característica positiva de um sistema preemptivo. Mas a implementação desse recurso é mais complexo em comparação ao sistema cooperativo. E sua implementação está intimamente ligada à arquitetura da CPU, pois é necessária a manipulação de registradores específicos, que mudam de acordo com a CPU utilizada.

 

Outro ponto que pode ser considerado como uma desvantagem nesse tipo de sistema é fazer o uso de linguagem Assembly, manipulando alguns registradores a fim de realizar a troca de contexto.

 

 

O Kernel

 

O kernel desenvolvido é especifico para microcontroladores ARM Cortex-M0. Para utilizar esse código-fonte em outra arquitetura é necessário realizar uma serie de mudanças para realizar a troca de contexto.

 

Os microcontroladores ARM Cortex-M0/M3/M4/M7 possuem alguns recursos que facilita o desenvolvimento de sistemas operacionais. São as seguintes interrupções:

  • SysTick: é um “Timer” periódico utilizado como base de tempo. No artigo passado já utilizamos essa interrupção;
  • PendSV (Pendable SerVice): é uma interrupção que a arquitetura ARM Cortex-M fornece para o uso dos sistemas operacionais realizar a troca de contexto;
  • SVCall (SuperVisor Call): São chamadas de supervisor, normalmente usadas para solicitar operações privilegiadas.

 

A outra característica importante de se destacar nos microcontroladores ARM Cortex-M é que eles possuem dois ponteiros de pilha (Stack Pointers):

  • MSP (Main Stack Pointer): Ponteiro de pilha principal, utilizado para a inicialização do sistema e na função main(). E as interrupções do sistema também fazem uso deste ponteiro;
  • PSP (Process Stack Pointer): Ponteiro de pilha de processo, usado para manipular os processos / tarefas em sistema operacional.

 

O projeto desenvolvido faz uso das interrupções SysTick como base de tempo do kernel. Para realizar as trocas de contexto entre as tarefas é utilizada a interrupção PendSV em conjunto com PSP, passando o endereço de memória que contém as instruções da próxima tarefa.

 

O código-fonte do kernel foi apresentado no artigo Context Switch on the ARM Cortex-M0 do Adam Heinrich em seu Blog com algumas alterações. O projeto desenvolvido para o STM32F0DISCOVERY, utilizando o STM32Cube MX em conjunto com Atollic TrueSTUDIO for STM32 9.0.0.

 

Das alterações que realizei, a mais relevante se encontra na API que adiciona os processos ao kernel. No código-fonte original, a alocação de memória é feita através de Array (vetor), e parâmetros são passados à função. A seguir temos trechos do código-fonte apresentado por Adam Heinrich em seu artigo:

 

//main.c
static os_stack_t stack1[128];
os_task_init(&task1_handler, stack1, 128);

 

//os.c
bool os_task_init(void (*handler)(void), os_stack_t *p_stack, uint32_t stack_size)

 

No código-fonte apresentado neste artigo, essa operação é feita na própria API, sem a necessidade de receber um vetor como parâmetro. A alocação de memoria é realizada utilizando a função malloc(), como pode ser observado no trecho de código-fonte abaixo.

 

//main.c
Kernel_Init();
Kernel_Add_Task(&app_task_push_button,NULL,SIZE_TASK_PUSH_BUTTON);

 

//kernel.c
bool Kernel_Add_Task(void (*handler)(void *p_params), void *p_task_params,uint32_t size)
{ 
  //...
  uint32_t *stack_size;
  stack_size = malloc(size * sizeof(uint32_t))

 

O funcionamento do kernel é bem simples, o mesmo contém API’s (Application Programming Interface) para inicializar, adicionar as tarefas da aplicação e para iniciar o escalonador do kernel. A seguir temos os protótipos das funções presente no kernel.

 

//kernel.h
bool Kernel_Init(void);
bool Kernel_Add_Task(void (*handler)(void *p_params), void *p_task_params,uint32_t size);
bool Kernel_Start(uint32_t systick_ticks);

 

Uma vez inicializado o Kernel, são adicionadas as tarefas ao Buffer circular. O escalonador assume o controle e passa a gerenciar o processo que deve ser executado pela CPU. O gerenciamento dos processos se dá início pela APIKernel_Start”, onde é configurada a utilização do Ponteiro de Pilha de Processo.

 

A troca de contexto entre as tarefas é realizada a cada ocorrência da interrupção do SysTick, onde é incrementado o index do Buffer e, em seguida, é disparado o Trigger gerar a interrupção do PendSV. O algoritmo que é executado quando ocorre a interrupção do PendSV é: salvar o contexto da tarefa que estava em execução e restaurar as informações da próxima tarefa a ser processada pela CPU. A figura a seguir ilustra com mais detalhes o funcionamento do Kernel.

 

Escalonador do Kernel Round-Robin
Figura 2 - Escalonador do Kernel Round-Robin

 

A seguir será apresentado o código-fonte do Kernel (arquivos kernel.c, kernel.h e kernel.s).

 

/*
 * kernel.c
 *
 *  Created on: 29 de abr de 2018
 *      Author: evandro
 */

#include "../inc/kernel.h"


static KernelStr m_task_table;
static KernelState m_state = KERNEL_STATE_DEFAULT;
volatile TaskStr *kernel_curr_task;
volatile TaskStr *kernel_next_task;


bool Kernel_Init(void)
{
	if (m_state != KERNEL_STATE_DEFAULT)
		return false;

	memset(&m_task_table, 0, sizeof(m_task_table));
	m_state = KERNEL_STATE_INITIALIZED;

	return true;
}

bool Kernel_Add_Task(void (*handler)(void *p_params), void *p_task_params,uint32_t size)
{
	if (m_state != KERNEL_STATE_INITIALIZED && m_state != KERNEL_STATE_TASKS_INITIALIZED)
		return false;

	if (m_task_table.size >= KERNEL_CONFIG_MAX_TASKS-1)
		return false;

	uint32_t *stack_size;

	stack_size 					= malloc(size * sizeof(uint32_t));
	uint32_t stack_offset 		= (size * sizeof(uint32_t));
	TaskStr *p_task 			= &m_task_table.tasks[m_task_table.size];
	p_task->handler 			= handler;
	p_task->p_params 			= p_task_params;
	p_task->sp 					= (uint32_t)(stack_size+stack_offset-16);
	p_task->status 				= KERNEL_TASK_STATUS_IDLE;
	stack_size[stack_offset-1] 	= 0x1000000;
	stack_size[stack_offset-2] 	= (uint32_t)handler;
	stack_size[stack_offset-8] 	= (uint32_t)p_task_params;

#if KERNEL_CONFIG_DEBUG
	uint32_t base = (m_task_table.size+1)*1000;
	p_stack[stack_offset-4] = base+12;  /* R12 */
	p_stack[stack_offset-5] = base+3;   /* R3  */
	p_stack[stack_offset-6] = base+2;   /* R2  */
	p_stack[stack_offset-7] = base+1;   /* R1  */
	/* p_stack[stack_offset-8] is R0 */
	p_stack[stack_offset-9] = base+7;   /* R7  */
	p_stack[stack_offset-10] = base+6;  /* R6  */
	p_stack[stack_offset-11] = base+5;  /* R5  */
	p_stack[stack_offset-12] = base+4;  /* R4  */
	p_stack[stack_offset-13] = base+11; /* R11 */
	p_stack[stack_offset-14] = base+10; /* R10 */
	p_stack[stack_offset-15] = base+9;  /* R9  */
	p_stack[stack_offset-16] = base+8;  /* R8  */
#endif /* KERNEL_CONFIG_DEBUG */

	m_state = KERNEL_STATE_TASKS_INITIALIZED;
	m_task_table.size++;

	return true;
}

bool Kernel_Start(uint32_t systick_ticks)
{
	if (m_state != KERNEL_STATE_TASKS_INITIALIZED)
		return false;

	NVIC_SetPriority(PendSV_IRQn, 0xff);
	NVIC_SetPriority(SysTick_IRQn, 0x00);

	SysTick_Config(systick_ticks);

	kernel_curr_task = &m_task_table.tasks[m_task_table.current_task];
	m_state = KERNEL_STATE_STARTED;

	__set_PSP(kernel_curr_task->sp+64);
	__set_CONTROL(0x03);
	__ISB();

	kernel_curr_task->handler(kernel_curr_task->p_params);

	return true;
}


void Kernel_Systick_Callback(void)
{
	kernel_curr_task = &m_task_table.tasks[m_task_table.current_task];
	kernel_curr_task->status = KERNEL_TASK_STATUS_IDLE;

	// Select next task:
	m_task_table.current_task++;
	if (m_task_table.current_task >= m_task_table.size)
		m_task_table.current_task = 0;

	kernel_next_task = &m_task_table.tasks[m_task_table.current_task];
	kernel_next_task->status = KERNEL_TASK_STATUS_ACTIVE;

	// Trigger PendSV which performs the actual context switch:
	SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk;
}

 

/*
 * kernel.h
 *
 *  Created on: 29 de abr de 2018
 *      Author: evandro
 */

#ifndef KERNEL_INC_KERNEL_H_
#define KERNEL_INC_KERNEL_H_

#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include "stm32f0xx_hal.h"
#include "stm32f0xx.h"

#define KERNEL_CONFIG_MAX_TASKS		8
#define KERNEL_CONFIG_DEBUG 		0

typedef enum
{
	KERNEL_TASK_STATUS_IDLE = 1,
	KERNEL_TASK_STATUS_ACTIVE,
}TaskStatus;

typedef struct
{
	volatile uint32_t sp;
	void (*handler)(void *p_params);
	void *p_params;
	volatile TaskStatus status;
}TaskStr;

typedef enum
{
	KERNEL_STATE_DEFAULT = 1,
	KERNEL_STATE_INITIALIZED,
	KERNEL_STATE_TASKS_INITIALIZED,
	KERNEL_STATE_STARTED,
}KernelState;

typedef struct
{
	TaskStr tasks[KERNEL_CONFIG_MAX_TASKS];
	volatile uint32_t current_task;
	uint32_t size;
}KernelStr;

bool Kernel_Init(void);
bool Kernel_Add_Task(void (*handler)(void *p_params), void *p_task_params,uint32_t size);
bool Kernel_Start(uint32_t systick_ticks);
void Kernel_PendSV_Callback(void);
void Kernel_Systick_Callback(void);

#endif /* KERNEL_INC_KERNEL_H_ */

 

/*
 * PendSV_Handler
 */

.syntax unified
.cpu cortex-m0
.fpu softvfp
.thumb

.global PendSV_Handler
.type PendSV_Handler, %function
PendSV_Handler:
	cpsid	i
	mrs	r0, psp
	subs	r0, #16
	stmia	r0!,{r4-r7}
	mov	r4, r8
	mov	r5, r9
	mov	r6, r10
	mov	r7, r11
	subs	r0, #32
	stmia	r0!,{r4-r7}
	subs	r0, #16
	ldr	r2, =kernel_curr_task
	ldr	r1, [r2]
	str	r0, [r1]
	ldr	r2, =kernel_next_task
	ldr	r1, [r2]
	ldr	r0, [r1]
	ldmia	r0!,{r4-r7}
	mov	r8, r4
	mov	r9, r5
	mov	r10, r6
	mov	r11, r7
	ldmia	r0!,{r4-r7}
	msr	psp, r0
	ldr r0, =0xFFFFFFFD
	cpsie	i
	bx	r0
.size PendSV_Handler, .-PendSV_Handler


 

 

Aplicação de demonstração

Para demonstrar o funcionamento do kernel, foi desenvolvida uma aplicação com três tarefas. A primeira tarefa ficará executando o algoritmo LED Blinking no LED verde. A segunda tarefa será responsável pelo acionamento do LED azul. E a última tarefa executará o algoritmo de leitura do Push Button.

 

A seguir é apresentado o código-fonte da aplicação, composto pelo main.c, onde temos as funções de inicialização do kernel, e pelos arquivos app.c e app.h.

 

/**
  ******************************************************************************
  * @file           : main.c
  * @brief          : Main program body
  ******************************************************************************
  */
/* Includes ------------------------------------------------------------------*/
#include "main.h"
#include "stm32f0xx_hal.h"
#include "gpio.h"

/* USER CODE BEGIN Includes */
#include "kernel/inc/kernel.h"
#include "app/inc/app.h"
/* USER CODE END Includes */

/* Private variables ---------------------------------------------------------*/

/* USER CODE BEGIN PV */
/* Private variables ---------------------------------------------------------*/

/* USER CODE END PV */

/* Private function prototypes -----------------------------------------------*/
void SystemClock_Config(void);

/* USER CODE BEGIN PFP */
/* Private function prototypes -----------------------------------------------*/

/* USER CODE END PFP */

/* USER CODE BEGIN 0 */

/* USER CODE END 0 */

/**
  * @brief  The application entry point.
  *
  * @retval None
  */
int main(void)
{
  /* USER CODE BEGIN 1 */

  /* USER CODE END 1 */

  /* MCU Configuration----------------------------------------------------------*/

  /* Reset of all peripherals, Initializes the Flash interface and the Systick. */
  HAL_Init();

  /* USER CODE BEGIN Init */

  /* USER CODE END Init */

  /* Configure the system clock */
  SystemClock_Config();

  /* USER CODE BEGIN SysInit */

  /* USER CODE END SysInit */

  /* Initialize all configured peripherals */
  MX_GPIO_Init();
  /* USER CODE BEGIN 2 */

  Kernel_Init();

  Kernel_Add_Task(&app_task_push_button,NULL,SIZE_TASK_PUSH_BUTTON);
  Kernel_Add_Task(&app_task_led_green,(void*)TIME_LED_GREEN,SIZE_TASK_LED_GREEN);
  Kernel_Add_Task(&app_task_led_blue,NULL,SIZE_TASK_LED_BLUE);

  Kernel_Start(SystemCoreClock);
  /* USER CODE END 2 */

  /* Infinite loop */
  /* USER CODE BEGIN WHILE */
  while (1)
  {

  /* USER CODE END WHILE */

  /* USER CODE BEGIN 3 */

  }
  /* USER CODE END 3 */

}

/**
  * @brief System Clock Configuration
  * @retval None
  */
void SystemClock_Config(void)
{

  RCC_OscInitTypeDef RCC_OscInitStruct;
  RCC_ClkInitTypeDef RCC_ClkInitStruct;

    /**Initializes the CPU, AHB and APB busses clocks 
    */
  RCC_OscInitStruct.OscillatorType = RCC_OSCILLATORTYPE_HSI;
  RCC_OscInitStruct.HSIState = RCC_HSI_ON;
  RCC_OscInitStruct.HSICalibrationValue = 16;
  RCC_OscInitStruct.PLL.PLLState = RCC_PLL_ON;
  RCC_OscInitStruct.PLL.PLLSource = RCC_PLLSOURCE_HSI;
  RCC_OscInitStruct.PLL.PLLMUL = RCC_PLL_MUL12;
  RCC_OscInitStruct.PLL.PREDIV = RCC_PREDIV_DIV1;
  if (HAL_RCC_OscConfig(&RCC_OscInitStruct) != HAL_OK)
  {
    _Error_Handler(__FILE__, __LINE__);
  }

    /**Initializes the CPU, AHB and APB busses clocks 
    */
  RCC_ClkInitStruct.ClockType = RCC_CLOCKTYPE_HCLK|RCC_CLOCKTYPE_SYSCLK
                              |RCC_CLOCKTYPE_PCLK1;
  RCC_ClkInitStruct.SYSCLKSource = RCC_SYSCLKSOURCE_PLLCLK;
  RCC_ClkInitStruct.AHBCLKDivider = RCC_SYSCLK_DIV1;
  RCC_ClkInitStruct.APB1CLKDivider = RCC_HCLK_DIV1;

  if (HAL_RCC_ClockConfig(&RCC_ClkInitStruct, FLASH_LATENCY_1) != HAL_OK)
  {
    _Error_Handler(__FILE__, __LINE__);
  }

    /**Configure the Systick interrupt time 
    */
  HAL_SYSTICK_Config(HAL_RCC_GetHCLKFreq()/1000);

    /**Configure the Systick 
    */
  HAL_SYSTICK_CLKSourceConfig(SYSTICK_CLKSOURCE_HCLK);

  /* SysTick_IRQn interrupt configuration */
  HAL_NVIC_SetPriority(SysTick_IRQn, 0, 0);
}

/* USER CODE BEGIN 4 */

/* USER CODE END 4 */

/**
  * @brief  This function is executed in case of error occurrence.
  * @param  file: The file name as string.
  * @param  line: The line in file as a number.
  * @retval None
  */
void _Error_Handler(char *file, int line)
{
  /* USER CODE BEGIN Error_Handler_Debug */
  /* User can add his own implementation to report the HAL error return state */
  while(1)
  {
  }
  /* USER CODE END Error_Handler_Debug */
}

#ifdef  USE_FULL_ASSERT
/**
  * @brief  Reports the name of the source file and the source line number
  *         where the assert_param error has occurred.
  * @param  file: pointer to the source file name
  * @param  line: assert_param error line source number
  * @retval None
  */
void assert_failed(uint8_t* file, uint32_t line)
{ 
  /* USER CODE BEGIN 6 */
  /* User can add his own implementation to report the file name and line number,
     tex: printf("Wrong parameters value: file %s on line %d\r\n", file, line) */
  /* USER CODE END 6 */
}
#endif /* USE_FULL_ASSERT */

/**
  * @}
  */

/**
  * @}
  */

/************************ (C) COPYRIGHT STMicroelectronics *****END OF FILE****/

 

/*
 * app.c
 *
 *  Created on: 29 de abr de 2018
 *      Author: evandro
 */

#include "../inc/app.h"

static bool flag_push_button = false;

static void app_flag_push_button_set(bool flag);
static bool app_flag_push_button_get(void);

static void app_flag_push_button_set(bool flag)
{
	flag_push_button = flag;
}

static bool app_flag_push_button_get(void)
{
	return flag_push_button;
}

void app_task_push_button(void *parameters)
{
	while(1)
	{
		if(HAL_GPIO_ReadPin(GPIOA,B1_Pin) == GPIO_PIN_SET)
		{
			app_flag_push_button_set(true);
		}
	}
}

void app_task_led_green(void *parameters)
{
	static uint32_t time_delay = 0;
	uint32_t i = (uint32_t)parameters;

	while(1)
	{
		time_delay++;
		if(time_delay >= i)
		{
			time_delay = 0;
			HAL_GPIO_TogglePin(GPIOC, LD3_Pin);
		}
	}
}

void app_task_led_blue(void *parameters)
{
	uint32_t i = 0;

	while(1)
	{
		if(app_flag_push_button_get() == true)
		{
			app_flag_push_button_set(false);
			HAL_GPIO_TogglePin(GPIOC, LD4_Pin);
		}
	}
}

 

/*
 * app.h
 *
 *  Created on: 29 de abr de 2018
 *      Author: evandro
 */

#ifndef APP_INC_APP_H_
#define APP_INC_APP_H_

#include <stdio.h>
#include <stdbool.h>
#include "main.h"
#include "stm32f0xx_hal.h"
#include "gpio.h"
#include "main.h"


#define TIME_LED_BLUE	200000
#define TIME_LED_GREEN	500000

#define SIZE_TASK_LED_GREEN		(uint32_t)(128*2)
#define SIZE_TASK_LED_BLUE		(uint32_t)(128*2)
#define SIZE_TASK_PUSH_BUTTON	(uint32_t)(128*2)

void app_task_led_green(void *parameters);
void app_task_led_blue(void *parameters);
void app_task_push_button(void *parameters);

#endif /* APP_INC_APP_H_ */

 

 

Conclusão

 

Neste segundo artigo da série Meu Kernel Minha Vida foram apresentados os conceitos básicos sobre kernel preemptivo e do escalonador Round-Robin. Também foi apresentado o código-fonte do kernel e  da aplicação de demonstração. O objetivo foi trazer a você, caro leitor, mais uma alternativa para o desenvolvimento de firmware.

 

O código-fonte do projeto com a aplicação e kernel está 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.

 

 

Saiba mais

 

Desenvolvendo com o Zephyr RTOS: Controlando o Kernel

Implementando elementos de RTOS no Arduino

Desenvolvendo um RTOS: Introdução

 

 

Referências

 

MCU on Eclipse - ARM Cortex-M, Interrupts and FreeRTOS: Part 1
MCU on Eclipse - ARM Cortex-M, Interrupts and FreeRTOS: Part 2
MCU on Eclipse - ARM Cortex-M, Interrupts and FreeRTOS: Part 3
Adam Heinrich - Context Switch on the ARM Cortex-M0
GitHub - Adam Heinrich - Context Switch on the ARM Cortex-M0

Outros artigos da série

<< Meu Kernel - Minha VidaMeu Kernel, Minha Vida - Escalonador Cooperativo com Lista Circular >>
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.

2
Deixe um comentário

avatar
 
1 Comment threads
1 Thread replies
2 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Evandro TeixeiraLucas Zampar Bernardi Recent comment authors
  Notificações  
recentes antigos mais votados
Notificar
Lucas Zampar Bernardi
Visitante
Lucas Zampar Bernardi

Excelente artigo Evandro! Meus parabéns!