Что необходимо знать, чтобы написать свою Embedded RTOS (часть 1)

Хотел бы написать небольшой цикл статей посвященных тому, как я написал свою RTOS с какими трудностями столкнулся и зачем вообще писать свою RTOS если уже есть FreeRTOS, RTX, embOS и т.д. список достаточно большой.

Начнем с того, что по мере работы я сталкивался с тем, что часть разработчиков (и я в том числе когда-то и сам) относятся к RTOS как к некоторому черному магическому ящику, мол что-то там происходит как-то все это работает и лучше туда не лесть, а то поломается ящик и проекту «ХАНА». И все хорошо пока хорошо, но как только появляются проблемы, то начинаются бессонные ночи с отладчиком, сроки по проекту горят, а самое главное и коварное, что ошибки в RTOS отловить крайне сложно. Зачастую они имеют плавающий характер и такие эффекты как переполнение стека, инверсия приоритетов, взаимные блокировки, и все, что связанное со средствами синхронизации отладить крайне сложно.

Cо всем этим я решил разобраться в корне, и чисто в академичесеких целях начал писать свою RTOS, чтобы так сказать прочувствовать все изнутри.

В итоге, оказалось, что написать RTOS ни так уж и сложно как кажется. И есть один существенный плюс, когда пишешь все сам и осознанно, то на поиск артефактов в виде багов уходит гораздо меньше времени (пара часов или полдня максиму).  Кроме того открываются внутренние чакры и начинаешь чувствовать как работают другие RTOS в чем плюсы или минусы разных RTOS, в общем возникает чувство явного прозрения.

При написании RTOS, я осознанно отказался от поддержки проприетарных архитектур как AVR, PIC и мой выбор пал на семействе CORTEX, поскольку cortex-mX, на сегодня самая распространенная архитектура в Embedded.

И как оказалось cortex-mX просто создан для RTOS в нем есть все необходимое, а именно:

1. Два стека, один для прерываний, второй для задач

2. Гибкая настройка приоритетов

3. Программное прерывание для переключения контекста

4. Хорошая поддержка в GCC, кстати, писать мы будем именно на нем

Для начала хочу сказать, что это моя первая статья на хабре, я не Пушкин и даже не Лермонтов и не обладаю слоганом поэта, поэтому наверняка будут опечатки и ошибки, прошу отнестись к ним с пониманием. Любые комментарии будут приветствоваться, и я постараюсь исправить те недочеты, которые явно допущу.

Готовый код вы можете найти на github по ссылке.

Итак, поехали …

Начнем с фундаментальных определений

RTOS – операционная система реального времени, основная задача которой – предоставление интерфейсов и средств синхронизации для распараллеливания кода.

Task – задача, единица программного кода, которая позволяет писать логику в линейном (последовательном) виде. У каждой задачи есть свой стек для хранения локальных переменных. Задачи обладают приоритетом. Более приоритетная задача должна вытеснять менее приоритетную задачу (так называемая вытесняемая многозадачность).

На самом деле, на контроллере в каждый момент времени выполняется только одна задача (в нашем случае мы рассматриваем только одноядерные микроконтроллеры).

Scheduler – планировщик, программный код, который переключает задачи между собой и тем самым создает иллюзию одновременного выполнения нескольких задач.

Мьютексы, семафоры, очереди, события, критические секции – это основные объекты межпоточной синхронизации.

Задача может находиться в нескольких состояниях, представим эти состояния графом переходом:

Где:

• Inited – задача создана и помещена в список созданных задач, но еще не управляется планировщиком (scheduler)

• Deleting – задача закончила свою работу и нуждается в уничтожение (помещена в очередь на удаление). Задачу нельзя «убить», она должна сама завершиться

• Ready – задача готова к выполнению (находится в очереди готовых) и ждет, когда ее запустит планировщик

• WaitTimeout – задача заблокирована на некоторое время (помещена в очередь ожидания таймаута)

• WaitObj – задача ждет объект синхронизации: событие, семафор, мьютекс, очередь (помещена в очередь объекта синхронизации)

• Work – задача выполняется в текущий момент времени

Итак, проблема №1

Первая проблема, с которой я столкнулся – это как ставить задачи в очередь на ожидание чего либо?

У каждой задачи есть структура em_task_t в которой хранится все, что нужно для задачи: указатель стека, приоритет, состояние задачи и т.д. Рассмотрим пример – задачи 2 и 3 пытаются захватить мьютекс, которым владеет задача 1, в этом случае задачи 2 и 3 должны встать в очередь на ожидание мьютекса. Понятно, что в некоторую очередь должна поместиться структура em_task_t, но как?

Дело в том, что мы не можем помещать указатель на задачу в массив, поскольку мы не знаем, сколько будет создано задач (задачи могут создаваться, и удалятся в процессе работы динамически), можно конечно реализовать динамический массив и в него помещать указатель на задачу, но это не лучшее решение особенно для Embedded. К тому же задача можем покинуть очередь находясь в середине очереди, например, задача находилась в середине очереди WaitObj – ожидала событие, событие произошло – задача покинула очередь WaitObj и переместилась в очередь Ready. Кроме того, перемещение задачи из одной очереди в другую должно происходить как можно быстро (не забываем, что мы пишем RTOS и у нее должна быть низкая латентность).

Решение проблемы №1

К нам на помощь приходят двух связные списки, именно на их основе мы и будем организовывать очередь. Давайте же вспомним что это такое. Классический двух связный список выглядит следующим образом:

typedef struct _em_list_t
{
	struct _em_list_t *next;
	struct _em_list_t *prev;
} em_list_t;

Данный двухсвязный список позволяет добавлять и удалять элементы списка из любой позиции в списке.
Например, добавить в начало/конец списка:

//--------------------------------------------------------------
// Add to head
//--------------------------------------------------------------
void rt_em_list_add_head(em_list_t *lst, em_list_t *nlst)
{
	nlst->next = lst->next;
	nlst->prev = lst;
	lst->next->prev = nlst;
	lst->next = nlst;
}
//--------------------------------------------------------------
// Add to tail
//--------------------------------------------------------------
void rt_em_list_add_tail(em_list_t *lst, em_list_t *nlst)
{
	nlst->prev = lst->prev;
	nlst->next = lst;
	lst->prev->next = nlst;
	lst->prev = nlst;
}

Удалить из текущей позиции в списке:

//--------------------------------------------------------------
// Remove entry
//--------------------------------------------------------------
void rt_em_list_remove_entry(em_list_t * lst)
{
	lst->prev->next = lst->next;
	lst->next->prev = lst->prev;
	lst->prev = lst->next = lst;
}

И т. д. не будем сейчас останавливаться на этом, скажем только, что работа со списком описана в файле em_list.c

Как же теперь связать наш список и структуру em_task_t, ведь именно ее мы и должны помещать или удалять из очереди. Для этих целей мы будем использовать способ определения адреса структуры по указателю на элемент данной структуры (прошу не пугаться, понимаю, что выглядит все как-то сложно, но на самом деле это очень распространенный метод, он используется во многих RTOS и OS в том числе и в Linux)

Объясню на примере очереди ожидающих задач task_wait_list.
Основная идея состоит в том, что сами структуры em_task_t (каждой задачи) никуда не перемещаются, но в каждой структуре em_task_t есть двухсвязный список wait_list.  Именно по мену задачи и встают в очередь и по нему же можно определить к какой структуре em_task_t он относится, для этого нам поможет простой универсальный макрос.

#define rt_em_get_struct_by_field(addr_field, type, field)	
	((type *)((unsigned char *)(addr_field) - (unsigned char *)(&((type *)0)->field)))

Теперь по указателю на wait_list можно определить указатель структуры em_task к которой он относится:

inline em_task_t* rt_em_get_task_by_wait_list(em_list_t* list)
{
	return rt_em_get_struct_by_field(list, em_task_t, wait_list);
}

Если работа макроса  rt_em_get_struct_by_field не понятна и вызывает вопросы, рекомендую почитать про макрос container_of (он используется в Linux), если понимает все еще не придет, напишите в комментариях и я опишу его более подробно.

В общем виде по этому принципу формируется список (очередь) ожидающих задач:

Где task_wait_list – вход в список ожидания (глобальна переменная типа em_list_t).

Понимание этого механизма крайне важно, так как в дальнейшем списки (очереди) мы будем использовать повсеместно и где только можно, задачи будут вставать в список ожидания у мьютексов, семафоров, очередей и т.д.

Еще раз сформулируем все плюсы данного подхода:

• Добавление задачи в конец списка позволяет сохранять временную последовательность, поскольку задачи встают в список друг за другом

• Удаление задачи из середины списка осуществляется очень быстро для этого необходимо соединить указатели next и prev соседних списков

• Сами структуры не перемещаются по памяти, но мы можем всегда по указателю на список определить адрес основной структуры (например, em_task_t) к которой он относится

Со списками вроде разобрались, но теперь еще один момент – у каждой задачи должен быть приоритет и если все готовые к выполнению задачи помещать в один глобальный список Ready, то это крайне не удобно, потому что придется каждый раз пробегаться по всему спуску Ready и искать задачу с наивысшем приоритетом, к тому же возникает вопрос как при таком подходе реализовать алгоритм Round-robin.

Round-robin – это алгоритм, по которому задачи с одинаковым приоритетом по кругу передают управление друг другу. Отсюда вытекает следующая проблема.

Проблема № 2. Как реализовать быстрый поиск наиболее приоритетной задачи из готовых к выполнению, и к тому же, чтобы между задачами равного приоритета можно было легко и быстро реализовать алгоритм Round-robin.

Решение проблемы № 2

Для решения данной проблемы необходимо иметь массив списков Ready глубина массива определяется количеством возможных приоритетов, то есть каждый элемент Ready[N] – список задач готовых к выполнению с приоритетом N, чем выше N тем приоритетнее задача (например, задача Idle имеет самый низкий приоритет 0, и находится в списке Ready[0]). Задача, когда становится готовой к выполнению, помещается в соответствие со своим приоритетом в нужных список из массива Ready, например, если задача имеет приоритет 2, то когда она готова к выполнению, то она помещается в конец списка Ready[2]. Если список Ready[N]  не пуст значит выполняем задачу, которая  расположена по часовой стрелки от входной метки (указатель next), если список пуст, то переходим к следующему элементу Ready[N-1] и т.д. Так реализуется алгоритм выбора наиболее приоритетной задачи из готовых к выполнению.

В этом случае алгоритм Round-robin  реализуется также очень просто, достаточно на каждом временном этапе работы задач с одинаковым приоритетом перемещать входную метку по часовой стрелке (вдоль указателя next).

Для пояснения рассмотрим пример алгоритма Round-robin в картинках, допустим у нас есть список, в котором хранятся готовые к выполнению задачи с приоритетом 2. Выглядеть это будет следующим образом (желтым светом обозначена задача, которая будет выполняться):

Первый тайм-слот

Второй тайм-слот

Третий тайм-слот

И т.д.  Если task_ready_list[2] пустой

Проверить список на пустоту можно очень быстро:

//--------------------------------------------------------------
// Is empty?
//--------------------------------------------------------------
int rt_em_is_list_empty(em_list_t* lst)
{
	return (lst->next == lst);
}

То переходим к следующему элементу task_ready_list[1] и так далее.

И вроде теперь все хорошо, но не совсем. А дело вот в чем. Допустим наша RTOS имеет 32 приоритета, самые высокоприоритетные задачи находятся в списке task_ready_list[31], а самые низко приоритетный в списке task_ready_list[0]. Так вот, чтобы найти наиболее приоритетную задачу надо пробегаться по спискам начиная с task_ready_list[31] по task_ready_list[0], в худшем случае необходимо проверить 32 списка на пустоту. Это конечно тоже решение, но не забываем, что мы боремся за низкую латентность.

Чтобы снизить время поиска используем следующий метод.
Заведем переменную:

static unsigned task_mask_pri = 0; 

В ней будет храниться маска приоритетов готовых к выполнению задач.
Теперь каждый раз, когда задача с приоритетов pri ,будет помещаться в список task_ready_list[pri], будем  устанавливать бит в нашей маске.

task_mask_pri |= (1 << task->pri);

Когда задача покидает список task_ready_list[pri] и при этом task_ready_list[pri] становится пустым – сбрасываем бит в маске.

if (rt_em_is_list_empty(&task_ready_list[task->pri]))
		task_mask_pri &= ~(1 << task->pri);

При таком подходе номер самого старшего бита установленного в  1 – это и есть номер самого приоритетного списка готовых к выполнению задач. Для архитектуры cortex-mX его можно определить очень и очень быстро (помните, в самом начале я говорил, что cortex-mX  просто создан для RTOS).

int rt_em_find_first_bit(int value)
{
	__asm volatile ( "clz	%0, %0" : "=r" (value) );
	return 31 - value;
}

Эта функция работает следующим образом, команда clz подсчитывает количество старших 0 до первой 1 и выполняет это за 1 MIPS. Затем от 31 отнимет полученное значение, и получаем номер списка.

Чуть не забыл, в общем виде clz может вернуть значение от 0 до 32 включительно.
32 – означает, что маска равна 0. Искушенный опытом читатель, возможно, подумает, что в этом случае произойдет крах системы, по сколько 31 – 32 =  -1.

Однако в нашем случае этого ни когда не произойдет, поскольку есть задача Idle (о ней мы поговорим в другой раз), которая ни когда не переходит в заблокированное состояние – она всегда активна, как следствие в маске всегда будет установлен младший бит.
Теперь проблема №2 решена в полном объёме.

Проблема № 3. Как правильно использовать аппаратный стек и при этом экономить на памяти

Сделаю небольшое пояснение. Архитектура cortex-mX имеет очень гибкую настройку приоритетов прерываний и допускает вложенные прерывания, при этом часть регистров общего назначения и локальные переменные вытесненного прерывания также будут сохраняться в стек.

Поясню это на упрощенном примере.
Допустим, есть 8 прерываний с разным приоритетом, и каждое прерывание потребляет 256 байт локальных переменных и к тому же у нас есть, допустим, 10 задач.

Может произойти следующее:
Прерывание 2 вытеснило прерывание 1, прерывание 3 вытеснило прерывание 2 и т.д. На картинке это будет выглядеть следующим образом:

В итого получаем общую глубину стека в прерываниях 256*8 = 2 Кбайта.

Прерывания могут произойти в любой момент и если использовать в прерываниях стек текущей задачи, то необходимо этот размер учитывать в стеке каждой задачи, поскольку прерывания могут произойти при работе любой задачи. Как следствие при 10 задачах получаем  10 * 2 Кбайта = 20 Кбайт. Мягко говоря, это много и хотелось бы от этого избавиться.

Давайте же подумаем, как этого можно избежать. Первая мысль, которая наверняка Вас уже посетила – «А что если у прерываний будет свой стек?».

И действительно если у прерываний будет свой стек, а у задач свой, то для прерываний достаточно тех же 2 Кбайт вместо 20 Кбайт.

И у cortex-mX как раз есть два аппаратных стека: main и process  (MSP и PSP соответственно). Но вот только дело  в том, что по умолчанию при старте контроллера используется только MSP.

Так как же нам все-таки задействовать второй стек (PSP)?

Для начало хочу сказать, что всю ниже приведенную информацию вы можете найти на официальном сайте от ARM в разделе документация, там есть документация по всем ядрам от ARM https://developer.arm.com

Если найти будет сложно, то например, по ядру сortex-m3 туже самую документацию  можно скачать вот по этой ссылке: https://github.com/ARM-software/CMSIS/blob/master/CMSIS/Pack/Example/Documents/dui0552a_cortex_m3_dgug.pdf

Далее на примере cortex-m3 я постараюсь кратко и понятно, насколько возможно, объяснить, как же все-таки заставить работать PSP стек в задачах, а MSP в прерываниях и как правильно инициализировать стек задач при создании, а затем их правильно переключать.

И так, в ядре есть следующие регистры:

Регистр R13 (SP) – это и есть текущий указатель стека, он может подменяться теневыми регистрами PSP и MSP.
На самом деле, когда вызывается ассемблерную инструкцию вида:

stmdb sp!, {r3, r14}

То в какой именно стек (PSP или MSP) сохранятся регистры R3 и R14 определяется регистром CONTROL.

Если сказать еще проще - все команды, которые работают с регистром SP сами не знаю с каким именно регистром, отечающим за стек, (PSP или MSP) они работаю это определяет само ядро по 1-му биту в регистре CONTROL.

Как же теперь установить данный бит?

В документации сказано следующее:

Если коротко, то сказано, что для того чтобы задействовать PSP надо особым образом выйти из прерывания. В общем надо разобраться, что происходит на входе и выходе из прерываний.

Если вкратце, то говорится о следующем:

1. При входе в прерывание в стек SP аппаратно сохраняется часть регистров общего назначение в количестве 8 штук. Если прерывания вложенные, то аппаратное сохранение происходит 1 раз при первом прерывании. При выходе из прерываний (при условии, что это не вложенное прерывание) происходит аппаратное восстановление тех же самых регистров.

2. Если при выходе из прерывания в регистр LR записать 0xFFFFFFFD (вернее даже в младших 4 битах должно быть 0xD), то указатель стека SP переключится на PSP. Причем это не обходимо сделать один раз далее все будет работать автоматом.

Итак, тезисно сформулируем, что же необходимо сделать:

1. При создании любой задачи - подготовить стек задачи к использованию. Для этого необходимо заранее загрузить в стек задачи значение тех регистров, которые будут сохраняться и восстанавливаться аппаратно.

2. При самом первом запуске самой первой задачи, необходимо вызвать любое прерывание переключиться в нем на первую задачу и при выходе из прерывания обеспечить, чтобы в младших 4 битах регистра LR было записано число 0xD.

3. Переключение контекста также лучше делать в прерывании, поскольку аппаратное сохранение регистров будет происходить само и в нужный стек.

У cortex-mX как раз есть все необходимое, чтобы это осуществить. На самом деле пункт 2 и 3 возможно реализовать через одно прерывание, но cortex-mX настолько крут, что позволяет разделить данные процедуры на 2-а разных прерывания.

1. Инициализация стека при создании задачи

unsigned* rt_em_port_init_stack(unsigned* sp, unsigned size_sp,
		void (*start_func)(void*), void* par, void (*exit_func)(void))
{
	// Initialization stack
	for (int i = 0; i < size_sp; i++)
		*sp++ = cfgFILL_SP;
	--sp;
	*sp = 0x01000000;								// xPSR
	--sp;
	*sp = (unsigned) start_func;
	--sp;
	*sp = (unsigned) exit_func; 		// LR
	sp -= 5; 												// R12, R3, R2, R1
	*sp = (unsigned) par; 					// R0
	sp -= 8; 												// R11, R10, R9, R8, R7, R6, R5, R4
	*sp = 0;
	return sp;
}

Пояснение:

• for (int i = 0; i < size_sp; i++)
     *sp++ = cfgFILL_SP;
  Заполняем стек значением по умолчанию, далее это пригодится для диагностики глубины  использования стека

• *sp = 0x01000000; // xPSR
  Устанавливаем режим Thumb, собственно говоря cortex-mX по другому работать и не умеет

• *sp = (unsigned) start_func;
Записываем в PC адрес входа  в задачу

• *sp = (unsigned) exit_func; // LR
  Адрес функции, которая удалит задачу при ее заверщении (при выходе из функции start_func)

• sp -= 5;                     // R12, R3, R2, R1
Инициализацию регистров можно пропустить

• *sp = (unsigned) par;        // R0
Указатель, который передается в функцию start_func в виде параметра

• sp -= 8;                     // R11, R10, R9, R8, R7, R6, R5, R4
Инициализацию регистров также можно пропустить

• *sp = 0;
Метка насколько заполнен стек. Может быть любое значение не равное cfgFILL_SP. Это также нужно для диагностики заполненности стека.

2. Запуск первой задачи. Используется прерывание SVC

static void __rt_em_port_start_first_task(void)
{
	__asm volatile
	(
		" ldr 	r0, =0xE000ED08		n"
		" ldr 	r0, [r0]					n"
		" ldr 	r0, [r0]					n"
		" msr 	msp, r0	    			n"
		" cpsie	i									n"
		" cpsie	f									n"
		" svc 	0									n"
		" nop											n"
	);
}

Пояснение:

• " ldr r0, =0xE000ED08      n"
" ldr r0, [r0]              n"
" ldr r0, [r0]              n"
" msr msp, r0               n"
Инициализируем стек MSP, который будет использоваться в прерываниях. Остановимся на этом  подробнее. Дело в том, что когда контроллер стартует по умолчанию уже используется стек MSP, который хранится в начале таблицы прерываний. Однако пока код дойдет до этой функции стек MSP уже заполнится какими-то внутренними локальными переменными, поэтому в нем уже будет что-то лежать и это что-то нам уже больше не понадобится. В общем, мы это делаем, чтобы не терять лишнее пространство стека MSP.
  Белее подробно делается следующее:
  - берем указатель на адрес начала таблицы прерываний (0xE000ED08)
  - разыменовываем его, и получаем указатель на таблицу прерываний
  - в первой строчке таблицы прерываний лежит адрес начального значения MSP,
  поэтому разыменовываем полученный указатель и получаем адрес начального буфера для MSP стека
  - сохраняем полученный адрес буфера в MSP стек

• " cpsie      i           n"
" cpsie      f            n"
  Разрешаем глобальный прерывания

• " svc 0                 n"
Вызываем прерывание SVC

Обработчик прерывания SVC - запуск первой задачи

//--------------------------------------------------------------
// SVC ISR
//--------------------------------------------------------------
void SVC_Handler(void)
{
	__asm volatile
	(
		" ldr	r3, =ctask			n"
		" ldr 	r1, [r3]			n"
		" ldr 	r0, [r1]			n"
		" ldmia r0!, {r4-r11}	n"
		" msr 	psp, r0				n"
		" mov 	r0, #0				n"
		" msr	basepri, r0			n"
		" orr 	r14, r14, #13	n"
		" bx 	r14							n"
	);
}

Пояснение:

• " ldr  r3, =ctask      n"
" ldr r1, [r3]         n"
" ldr r0, [r1]         n"
  В переменой ctask находится адрес текущей задачи (указатель на структуру em_task_t), в нашем случаем это адрес первой задачи. Первое поле в структуре em_task_t это указатель на стек задачи. Суть этих действий такая же, как и выше получить адрес начала буфера, который используется для стека задачи.

• " ldmia r0!, {r4-r11}   n"
Восстанавливаем регистры с r4 по r11, которые предварительно сохранили  при создании задачи

• " mov r0, #0           n"
" msr  basepri, r0       n"
  Восстанавливаем базовый приоритет (об этом мы поговорим в следующий раз)

• " orr r14, r14, #13    n"
" bx   r14               n"
А вот здесь мы как раз добиваемся, чтобы в регистре LR(r14) младшие 4 бита были установлены в 0xD.

3. Переключение контекста - прерывание PendSV

//--------------------------------------------------------------
// PendSV ISR
//--------------------------------------------------------------
void PendSV_Handler(void)
{
	__asm volatile
	(
		" mrs   r0, psp							n"

		" ldr 	r3, =ctask					n" // Get SP for current task
		" ldr 	r2, [r3]						n" // Get stack

		" stmdb	r0!, {r4-r11}				n" // Save registers
		" str 	r0, [r2]						n"

		" stmdb sp!, {r3, r14}			n"
		" mov   r0, %0      				n" // Up base priority
		" msr 	basepri, r0		    	n"
		" bl 	rt_em_switch_context	n" // Change task
		" mov 	r0, #0			    		n"
		" msr 	basepri, r0		    	n" // Down base priority
		" ldmia	sp!, {r3, r14}			n"

		" ldr 	r1, [r3]						n" // Get SP for current task
		" ldr 	r0, [r1]						n"

		" ldmia r0!, {r4-r11}	    	n" // Load registers

		" msr 	psp, r0							n"
		" bx 	r14										n"
		:: "i" (cfgKERNEL_MAX_PRI)
	);
}

Пояснение:

• " mrs   r0, psp             n"
  Поскольку ядро уже переключилось на стек MSP, чтобы получить указатель на стек задачи (PSP) его необходимо явно загрузить в один из рабочих регистров

• " ldr r3, =ctask             n"
" ldr r2, [r3]                n"
Получаем адрес куда потом будем сохранять стек PSP

• " stmdb      r0!, {r4-r11} n" // Save registers
В стек задачи сохраняем те регистры, которые не сохранены аппаратно

• " str r0, [r2]               n"
  Сохраняем текущий указатель стека PSP в поле задачи, чтобы потом его можно восстановить при следующем запуске задачи

• " stmdb sp!, {r3, r14}        n"
  Сохраняем скретч-регистры, потому что затем мы будем вызывать Си функцию шедулера

• " mov   r0, %0                n"
" msr basepri, r0             n"
  Подымаем текущей базовый приоритете до cfgKERNEL_MAX_PRI, что бы во время работы Си функции шедулера нас не могли вытеснить прерывания, которые использует функции RTOS

• " bl   rt_em_switch_context    n"
Вызываем Си функцию шедулера. Именно она найдет самую приоритетную задачу из готовых и выполнит Round-robin алгоритм для задач с одинаковым приоритетом

• " mov r0, #0                  n"
" msr basepri, r0              n"
" ldmia      sp!, {r3, r14}     n"
" ldr r1, [r3]                 n"
" ldr r0, [r1]                 n"
" ldmia r0!, {r4-r11}           n"
" msr psp, r0                  n"
" bx   r14                      n"
  Здесь я думаю все понятно. Восстанавливаем базовый приоритет, теперь нас могут вытеснять прерыванию, которые используют функции RTOS. Восстанавливаем регистры для новой задачи и выходим из прерывания.

Читатель, хорошо знакомый с механизмами переключения задач во FreeRTOS заметит, что это очень сильно похоже на то, как реализованно во FreeRTOS. И будет совершено прав, поскольку проанализировав несколько RTOS, мне больше всего понравилось реализация переключения контекста именно во FreeRTOS («Велосипед то можно изобретать и свой, но что мешает позаимствовать хорошее колесо у соседа»). К тому же есть еще один плюс при добавлении нового порта, например cortex-m0 или cortex-m4f, можно всегда подсмотреть, как это сделано во FreeRTOS и при необходимости позаимствовать, естественно обдуманно и если их решение понравится.

А вот и сама функция, которая ищет и переключает задачи согласно приоритетам, а также выполняет Round-robin алгоритм, и работает она ОЧЕНЬ быстро.

//-------------------------------------------------------------
// Switch Context
//-------------------------------------------------------------
void rt_em_switch_context(void)
{
	unsigned task_pri_redy;

#if cfgTEST_SP_SWITCH_TASK
	extern void rt_em_port_test_sp_switch_task(void);
	rt_em_port_test_sp_switch_task();
#endif /* cfgTEST_SP_SWITCH_TASK */

	task_pri_redy = rt_em_find_first_bit(task_mask_pri);
	ctask = rt_em_get_task_by_task_list(task_ready_list[task_pri_redy].next);
	rt_em_list_jump_head(&task_ready_list[task_pri_redy]);
}

Пояснение:

• task_pri_redy = rt_em_find_first_bit(task_mask_pri);
находим номер наиболее приоритетного списка, готовых к выполнению задач

• ctask = rt_em_get_task_by_task_list(task_ready_list[task_pri_redy].next);
Определяем задачу, которая будет выполняться по часовой стрелке от входной метки (по указателю next)

• rt_em_list_jump_head(&task_ready_list[task_pri_redy]);
смещаем метку по часовой стрелке (по указателю next), для реализации алгоритма Round-robin.

 Следующие вопросы, которые я изначально хотел обсудить:

1. Правильная настройка прерываний для RTOS, и работа вложенных прерываний, которые могут вытеснять любой код RTOS, включая функции планировщика

2. Особенности использования сопроцессора в RTOS (для архитектуры cortex-m4f). Нюансы при переключении контекста для cortex-m0 и cortex-m4f.

3. Использование средств межпоточной синхронизации: мьютексы, семафоры, очереди, события, критические секции

Однако в данную статья я решил это не включать (иначе статья увеличится до нереальных размеров). Если есть интерес к этим вопросам, напишите в комментариях, и я опишу их в отдельной большой статье. В связи, с чем предлагаю сменить вектор и поговорит о более общих вопросах.

Поэтому последняя проблема, которую предлагаю обсудить посвящена  динамической памяти в Embedded RTOS.

Проблема №4. Как правильно использования динамической памяти в RTOS и нужна ли она?

Собственно говоря, почему я решил остановиться на heap, потому что наверняка многие из Вас слышали, что использование heap в Embedded системах не желательно и может привести к печальным последствиям. В тоже время в «больших системах» динамическая память используется везде где только можно и не вызывает ни какого негатива, вопрос почему?

И дело тут не в объеме оперативной памяти, потому что современный микроконтроллеры (например, STM32F7 или SAME51) позволяют подключить внешнюю SRAM и увеличить объем оперативной памяти до нескольких МБайт. Так же скажу, что мы не будем обсуждать утечку памяти, потому что утечка - это человеческий фактор и аппаратура в этом случае не причем.

А дело в том, что «большие системы» всегда строятся с использованием MMU (Memory Management Unit). MMU – блок управления памятью, который решает ряд важных вопросов, а именно: виртуализацию адресного пространства, устранение эффекта фрагментации памяти, защиту памяти от других процессов (задач) и т.д.

Не будем сейчас обсуждать, как именно работает MMU (у нас его все равно нет), скажем только следующее - в «больших системах» нет проблем с динамической памятью, поскольку там есть MMU, который позволяет сделать все «красиво».

В «маленьких системах» MMU нет, как следствие чтобы мы не придумали – «красиво» все равно не получится. Поэтому динамическую память необходимо использовать осознанно и понимать, как она работает.

И так, динамическую память в Embedded RTOS можно реализовать двумя способами:

1. На буферах фиксированного размера

2. На одном большом буфере, который динамически делится на нужные кусочки (блоки) по запросу RTOS

Способ организации динамической памяти на буферах фиксированного размера

Поясним на примере.
Заводим несколько массивом, допустим 3:
unsigned char buf1[30][64];
unsigned char buf2[20][128];
unsigned char buf3[10][512];

Теперь если нам нужно выделить память объемом <= 64 байт, то мы резервируем под это ячейки из буфера buf1, если нужно выделить > 64 байт, но <= 128 – резервируем под это ячейки из буфера buf2 и т.д. Естественно есть некий менеджер, который учитывает свободные и занятые ячейки в каждом буфере.

При таком подходе в нашем примере мы можем выделить до 30 ячеек размером до 64 байт, 20 ячеек до 128 байт и 10 ячеек до 512 байт.

Плюсы данного способа (а он всего один, но очень важный):

• память гарантированно, ни при каких условиях не фрагментируется

Минусы данного способа:

• Память используется крайне не оптимально, если надо выделить 10 байт, то будет зарезервирована вся ячейка из buf1 (то есть 64 байта). Если buf1 заполнен, то будет зарезервирована ячейка из buf2 (то есть 128 байт) и т.д.

• Несмотря на то, что в сумме под буфер мы выделили размер 64*30+ 128*20 + 512*10 = 9600 байт и если даже все ячейки будут свободны, нельзя выделить 1024 байта, потому что под этот размер изначально нет буферов. Можно конечно сделать алгоритм, который для этих целей резервировал бы несколько подряд идущих ячеек, но тогда теряется единственный плюс данного способа – мы не сможем гарантировать отсутствие фрагментации памяти при запросе свыше 512 байт.

• Поиск свободного блока не детерминирован во времени. Как следствие один и тот же запрос памяти может выполняться разное время в зависимости от текущего состояния heap (Хотя дополнительными ухищрениями можно все-таки этот минус можно устранить)

 В общем, этот способ хорошо работает тогда, когда мы знаем размеры и количество выделяемой памяти и можем предусмотреть под это буферы на этапе компиляции.

Способ организации динамической памяти на одном большом буфере, который динамически делится на нужные кусочки (блоки)

Допустим, есть некий буфер heap и на его основе мы ходим реализовать динамическое выделение памяти. Тогда буфер будет динамически делится на блоки, в каждом блоке есть:

• размер блока

• флаг занят блок или нет

• указатель на следующий блок, если указатель = NULL, то это признак, что данный блок последний

Сами блоки вместе с выделенными данными лежит в том же буфере heap.
Изначально буфер heap. Будет выглядеть следующим образом:

По мере того как мы будем выделять/освобождать память он примет следующий вид:

Плюсы данного способа:

• Память используется очень эффективно

• Нет ограничений на длину запрашиваемой памяти, главное чтобы нашелся блок нужного размера

Минусы данного способа:

• Память неизбежно фрагментируется. Частично проблему фрагментации можно решить путем слияния соседних свободных блоков в один блок большего размера. Однако гарантированно решить проблему фрагментации в корне, данный способ не позволяет

• Поиск свободного блока не детерминирован по времени. Как следствие один и тот же запрос памяти может выполняться разное время в зависимости от текущего состояния heap.

При таком способе есть еще один нюанс – блоки, а вернее область памяти, которую они предоставляют пользователю, должна быть выровнена по 4 байт (а лучше по 8 байт для полной совместимости со всеми ядрами). Это связана с тем, что в cortex-mX часть команд требует, чтобы память, к которой они адресуются, была выровнена. Например, указатель стека всегда должен быть выровнен по слову (4 байта), а cortex-m0 вообще вызовет ошибку ядра, если разименовать не выровненный указатель типа int.

В общем подводя итоги можно сказать, что использование heap несет в себя ряд неопределенных моментов, которые имеют абсолютно плавающий эффект они могут проявиться сразу, либо через месяц после стабильной работы прибора или не проявиться вообще никогда. Все зависит от того какой вид в текущий момент принял heap.

В своей RTOS я заложил второй способ организации heap, поскольку он более эффективно использует память. Однако, чтобы не столкнутся с выше описанными эффектами я всегда рекомендую закладывать размер heap как минимум в два раза больше чем реально понадобится, а также не злоупотреблять выделением памяти маленкого размера, в этом случае высока вероятность, что проблем связанных с фрагментацией памяти никогда не возникнет.

Так же в своей RTOS я предусмотрел работу без heap – все можно сделать на статических переменных.

Так что использовать heap в Embedded или нет - это вопрос на который к сожалению нет однозначного ответа, разраотчик сам должен принять решение и помнить о последствиях.

Более детально работу heap можно посмотреть в файле em_heap.c

На этом все. Всем кто дочитал до конца - БОЛЬШОЕ СПАСИБО. Если есть интерес к данной теме - напишите об этом в коментариях и может быть появится "Часть 2", а за ней и "Часть 3" в которых можно обсудить более глубокии и интересные проблемы, а именно:

• Правильная настройка прерываний для RTOS, и работа вложенных прерываний, которые могут вытеснять любой код RTOS, включая функции планировщика

• Особенности использования сопроцессора в RTOS (для архитектуры cortex-m4f). Нюансы при переключении контекста для cortex-m0 и cortex-m4f.

• Использование средств межпоточной синхронизации: мьютексы, семафоры, очереди, события, критические секции

• В чем принципиальная разница между семафором и мьютексом

• Что такое инверсия приоритетов и взаимная блокировка (как этого избежать)

• Как правильно в RTOS использовать стандартную Си библиотеку из пакета GCC (в ней очень много потоко не безопасных функци, например, printf)

• и т.д.

Вопросов можно обсудить очень много, что будет интересно, то и обсудим дальше.