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

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

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

Итак… Мне очень давно стало интересно, насколько это сложно, круто ли, с какими проблемами придется столкнуться в процессе и какие задачи придется решить.

Вот и решил, пару месяцев назад, сделать свою ОС.

У меня нет цели сделать ОС, дать ей пафосное имя и выложить ее потом, как делают крутые пацаны. Я ее выложу, когда доделаю. А может и нет. А может и не доделаю... Меня скорее интересует - разобраться, как сделать, нежели сделать.

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

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

Да, я решил заняться этим, не попользовавшись ничем подобным. Из ОС использовал только кооперативную OSA на PIC24F. Да это очень профессиональный подход. Как говорится – профессионала видно из далека. Спасибо ​

Хотя..., я же пользуюсь Windows? Да! Она же вытесняющая? Тоже да! К тому же, я очень опытный пользователь! Наверное зря наговариваю на себя...

Определение ОС

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

На правах опытного пользователя Google (или Senior Google User, если хотите) – именую результат этой статьи «Embedded Operating System».

Если я не прав – можем позже похоливарить!)

Итак, скажем, что у нас это «Embedded OS», а дальше будем называть просто «ОС» или «операционная система».

Мое определение

Embedded OS – это программная прослойка, позволяющая реализовать псевдо многопоточность, на однопроцессорной системе. То есть – обычном микроконтроллере (да, даже на ардуино, уже предвкушаю этот вопрос :D).

Принцип работы ОС

Исходя из определения – основная задача, которую должна решать наша ОС, это реализация искусственной многопоточности на однопоточном процессоре.

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

1. Выполняется задача «1»;

2. Квант времени задачи заканчивается, и возникает прерывание таймера ОС;

3. Вызывается ядро ОС;

4. Сохраняется контекст текущей задачи в стек этой задачи;

5. Планировщик выбирает следующую задачу;

6. Контекст следующей задачи восстанавливается из стека новой задачи;

7. Происходит прыжок в то место задачи «2», на котором она была прервана в последний раз;

8. Выполняется задача «2»;

9. Квант времени задачи … ну вы поняли … и … «here we go again».

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

И вот в этом алгоритме уже фигурируют некоторые фичи, которые нужно понять и простить реализовать. Итого нам нужно:

1. Понять, что такое «Задача»;

2. Понять, что такое «Квант времени задачи»;

3. Понять, что такое «Контекст задачи»;

4. Понять, что такое «Переключение контекста»;

5. Понять, что такое «Стек задачи»;

6. Понять, что такое «Планировщик»;

7. Понять, что такое «Ядро»;

8. Убедиться, что все точно понятно;

9. Реализовать все эти приблуды!

10. Понять, что все было понятно не точно;

11. Переделать все заново.

Термины и определения

Задача

Это просто Си-функция, содержащая бесконечный цикл.

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

Пример задачи:

void Task1(void)
{
  for(;;)
  {
      /* some important actions */
  }
}

Квант времени задачи

Это отрезок времени, который задача гарантированно получает в свое распоряжение на выполнение своих действий, не боясь быть прерванной другими задачами или самой ОС.

Например, если квант времени возьмем как 1мс, тогда временная диаграмма работы ОС будет выглядеть как на рисунке ниже. Условимся, что время выполнения кода ядра, для переключения контекста занимает 50мкс.

Получается, что это можно использовать в своих целях, например, если нужно выполнить код, который выполняется быстрее, чем квант времени – то можно не париться по поводу синхронизации потоков и успеть выполнить его и так, но это другой вопрос. Мы не должны уйти в лес от основной темы, держу себя в руках!

Алгоритм работы выглядит примерно так:

1. Настраивается прерывание таймера на 1мс;

2. Запускается ОС;

3. Задача 1 работает;

4. Таймер делает «тик-так» много раз;

5. Срабатывает прерывание таймера;

6. ОС переключает контекст на задачу 2 и сбрасывает таймер;

7. Задача 2 работает;

8. Таймер делает «тик-так» много раз;

9. Срабатывает прерывание таймера;

10. ОС переключает контекст на задачу 2 и сбрасывает таймер;

11. Aaaand … here we go again …

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

Контекст задачи

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

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

Глобальные переменные хранятся в ОЗУ. Это когда вы объявляете переменную вне функций, или в функциях с модификатором «static».

А локальные?

Ну а их как бы и не существует вовсе. Они как бы есть. Но и в то же время – их нет.

Но должны же они где-то храниться?

А вот они, как раз, и хранятся в регистрах общего назначения, но хранятся там только в конкретные моменты.

На самом деле, то, что вы пишете на Си – нужно только для понимания кода, на самом деле в ассемблере все выглядит сильно по-другому.

Например, на Си, функция выглядит так:

uint8_t d;

void Function(void)
{
	uint8_t a;
	uint8_t b;
	uint8_t c;
	
	c = a + b;

	PORTB = c;

	d = c – a;
}

Объявление переменных a, b и c, на самом деле, вообще не содержат действий, и не скрывают за собой ассемблерных инструкций.

И вот только в строке «c = a + b» начинают работать регистры общего назначения.

А вот переменная «d» – уже хранится в ОЗУ, и поэтому существует всегда.

Как это работает без использования ОС: функция использует РОН для выполнения своего кода, и она уверена, что все РОН принадлежат ей, и она точно сделает все действия и никто ей не сможет помешать!

Ну…, есть еще прерывания. Обработчик прерывания – это такая же функция, которая может тоже вызвать функцию и так далее. И как они используют одни и те же регистры? Если, по сути, могут прервать любую функцию в любой момент, и данные в регистрах будут повреждены.

А все просто.

Во-первых, есть стандарт, описывающий, какие регистры для каких целей и как используются компилятором, например вот: здесь.

Во-вторых, из «во-первых» получаем, что каждая функция, кроме прерываний, может свободно использовать регистры R18-R27, R30, R31, не думая о том, что эти регистры нужны еще кому-то, а вот регистры R2-17, R28, R29 должна в начале работы сохранить, а после работы – вернуть на место.

Вот для этого, компилятор втихаря вначале каждой функции и прерывания вставляет код вида:

push R15
push R16
push R17

И в конце функции, перед выходом:

pop R17
pop R16
pop R15

Сохраняя регистры в стек, перед началом своей работы, и восстанавливая их обратно, в конце работы, чтобы вернуть все как было.

push/pop – это ассемблерные инструкции для работы со стеком.

Итак...

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

Это и есть контекст задачи – регистры общего назначения, или, грубо говоря – локальные переменные функции, с точки зрения Си.

Сохраняется контекст в стек соответствующей задачи.

Уточненьице...

Для AVR нужно еще сохранить регистр «SREG», который также каждый раз сохраняется компилятором при входе в каждое прерывание, это уже особенности каждой архитектуры процессоров, пока что это не важно.

Переключение контекста

Это действие, при котором сохраняется контекст последней выполняющейся задачи, выбирается следующая задача, и восстанавливается контекст этой выбранной задачи.

Получается, что код, а точнее псевдокод, для переключения контекста будет выглядеть так:

void ChangeContext(void)
{
	SaveRegsIntoStack();
	SelectNextTask();
	RestoreRegsFromStack();
	return;
}

SaveRegsIntoStack – это макрос, содержащий ассемблерный код для сохранения всех регистров в стек.

RestoreRegsFromStack – это макрос, содержащий ассемблерный код для выгрузки всех регистров из стека.

В итоге, если расшифровать эти макросы, все будет выглядеть так:

void ChangeContext(void)
{
	push R0
	push R1
	… R2 … R30 …
	push R31
	push SREG 
	
	currentTask = GetNextTask();
	
	pop SREG
	pop R31
	… R30 … R2 …
	pop R1
	pop R0
	
	return;
}

Стек задачи

Стек – это тип памяти, или способ хранения данных, который используется, в основном, для сохранения адресов возврата при вызове функций и возникновении прерываний.

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

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

Например, у AVR – всего 32 регистра общего назначения, это значит, что если у вас 4 задачи, то вам необходимо отдать на это (32 * 4) = 128 байт. Учитывая, что, например, в ATmega88 всего 1Кб ОЗУ – это таки потеря потерь.

Вывод: создавать отдельную задачу на каждый светодиод – явно неразумно :D

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

Сам по себе, процессор содержит аппаратный указатель стека, который, в начале работы, сразу после сброса процессора, указывает на конец таблицы ОЗУ и в ходе вызова функций туда сохраняются адреса, а в момент выхода из функций обратно выгружаются.

Без использования вытесняющей ОС, ОЗУ микроконтроллера будет выглядеть так:

С использованием ОС, уже будет выглядеть так:

Получается, стек задачи можно описать структурой вида:

typedef struct {
	uint8_t *buf;	// Указатель на буфер
	uint8_t *ptr;	// Указатель на текущий байт в буфере
} Stack_t

При переключении контекста, аппаратный указатель на стек должен перемещаться на буфер стека задачи.

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

Тогда код для переключения контекста уже будет иметь вид:

void ChangeContext(void)
{
	/* Сохраняем контекст задачи */
	push R0
	push R1
	… R2 … R30 …
	push R31
	push SREG 
	
	/* Сохраняем текущее состояние аппаратного указателя на стек */
	currentTask->stack.ptr = HARDWARE_STACK_POINTER;

	/* Выбираем следующую задачу */
	currentTask = GetNextTask();
	
	/* Перемещаем аппаратный указатель стека на буфер стека следующей задачи */
	HARDWARE_STACK_POINTER = currentTask->stack.ptr;
	
	/* Восстанавливаем контекст задачи */
	pop SREG
	pop R31
	… R30 … R2 …
	pop R1
	pop R0

	return;
}

Это практически готовый код для переключения контекста.

Стек ядра и стек прерывания

Стоит еще уточнить, что в идеале ядро и прерывания тоже должны иметь свой стек.

Об этом написано, опять же, в статье, на которую я уже давал ссылку: тут.

Стек ядра

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

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

Как это выглядит в коде – представлено ниже. Уже знакомая функция изменения контекста:

void ChangeContext(void)
{
	/* Сохраняем контекст задачи */
	push R0
	push R1
	… R2 … R30 …
	push R31
	push SREG 
	
	/* Сохраняем текущее состояние аппаратного указателя на стек */
	currentTask->stack.ptr = HARDWARE_STACK_POINTER;

	/* Перемещаем аппаратный указатель стека на буфер стека ядра */
	HARDWARE_STACK_POINTER = kernelStack.ptr;

	/* Выбираем следующую задачу */
	currentTask = GetNextTask();

	/* Сохраняем аппаратный указатель стека */
	/* На самом деле это не обязательно, т.к. мы вернулись из функции, */
	/* и указатель вернулся в исходное состояние до вызова функции. */
	/* Но это для понимания и предсказуемости кода */
	kernelStack.ptr = HARDWARE_STACK_POINTER;
	
	/* Перемещаем аппаратный указатель стека на буфер стека следующей задачи */
	HARDWARE_STACK_POINTER = currentTask->stack.ptr;
	
	/* Восстанавливаем контекст задачи */
	pop SREG
	pop R31
	… R30 … R2 …
	pop R1
	pop R0

	return;
}

Стек прерываний

Стека прерывания у нас не будет. Почему? Я уже почти дописал статью, и вспомнил, что я его не сделал, да, там всего пара макросов, но я не хочу быстро их добавлять, не протестировав нормально, и прикрепить этот проект к статье. Это как-то неправильно. Пусть, лучше, его не будет. Но я его опишу. Это уже что-то ​

В дальнейшем, может быть, вернусь к этой статье и исправлю этот недостаток, когда и ОС допилю.

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

Если мы добавим стек прерываний, то пользователь ОС просто должен в каждое свое прерывание добавить строку для перемещения стека в начало обработчика прерывания и для восстановления в конце.

Тогда любое прерывание будет выглядеть как-то так:

ISR(SOME_IMPORTANT_INTERRUPT)
{
	/* Здесь могут быть скрытые PUSH, которые добавит компилятор */

	/* Сохраняем значение аппаратного указателя стека текущей задачи */
	currentTask->stack.ptr = HARDWARE_STACK_POINTER;
	
	/* Перемещаем аппаратный указатель стека на буфер стека ядра/прерывания */
	HARDWARE_STACK_POINTER = kernelStack.ptr;

	/* Что-то делаем, пользовательский код */
	/* …………………… */
	/* …………………… */
	
	/* Восстанавливаем аппаратный указатель стека на буфер стека текущей задачи */
	HARDWARE_STACK_POINTER = currentTask->stack.ptr;
	
	/* Здесь могут быть скрытые POP, которые добавит компилятор */

	return;
}

Понятно, что это должно быть скрыто в макросы, но пока что для наглядности и для понимания принципа, как это должно работать.

Планировщик

Это отдельная история, которая будет реализована примитивно, т.к. это отдельная тема, но суть планировщика не меняется – это просто Си функция, которая должна вернуть нам указатель на следующую задачу.

В нашей ОС не будет алгоритмов планирования, планировщик будет примитивным.

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

Я работал однокристальщиком в одной небольшой фирме, где меня заставляли поддерживать 1С, так что я знаю, что он чувствует, когда занимается не тем, для чего был рожден ​

Это я не таю злобу на 1С, я просто не был рожден чтобы работать XD

Планировщик должен выполнять две функции:

1. Определить, какая задача будет выполняться следующей;

2. Минимизировать простой процессора.

Т.к. мы не забываем, что делаем ОС на AVR, то лучшей оптимизацией для минимизации простоя процессора является – отказ от сложных алгоритмов планирования. Тем более, что объем ОЗУ так и говорит, что несколько задач – это прям максимум!

А тупой перебор массива из 2, 4 или даже 10 (десять задач, карл) элементов – это гораздо быстрее, чем какой-то, даже самый примитивный алгоритм планирования.

Я не буду заливать про односвязный список, чтобы не перегружать, т.к. это просто оптимизация планировщика. А оптимизация – это не про сейчас, это «future simple» ​

Код планировщика я тупо скопировал реальный, который у меня был на данным момент. На самом у меня было много вариантов, и с одно- и с двусвязным списком, но пока что решил вернуться на изначальный, т.к. для меня он проще на этапе отладки и более предсказуемый.

Реальный код здесь вставлять я не хотел, т.к. псевдокод понятнее. Но не смог написать "рабочий" псевдокод и забил, скинув настоящий)

static Task_t *GetNextTask (void)
{
	static uint8_t currentTaskIndex = 0;
	bool taskAvailable;
	uint8_t i;
	
	if(Kernel_currentTask->status == TASK_STATUS_RUN)
	{
		Kernel_currentTask->status = TASK_STATUS_READY;
	}
	
	i = CONFIG_USER_TASKS_NUMBER;
	while(i--)
	{
		Kernel_currentTask = &Kernel_tasksList[currentTaskIndex];
		
		taskAvailable = false;
		if(Kernel_currentTask->status == TASK_STATUS_READY)
		{
			taskAvailable = true;
		}
		
		currentTaskIndex++;
		if(currentTaskIndex >= CONFIG_USER_TASKS_NUMBER)
		{
			currentTaskIndex = 0;
		}
		
		if(taskAvailable)
		{
			break;
		}
	}
	
	if(!taskAvailable)
	{
		Kernel_currentTask = &taskIdle;
	}
	
	Kernel_currentTask->status = TASK_STATUS_RUN;

return Kernel_currentTask;
}

Ядро

Ядро ОС – это часть ОС, которая и занимается переключением контекста.

Казалось бы, важнейшая часть ОС, че так мало написал?! А? А? А? А?

Ну а я отвечу – ядро содержит фичи, которые мы уже рассмотрели чуть выше.

Вот, как бы и все…

Инициализация и запуск

Вот тут сейчас и будут основные прЕколы, которые не давали мне спать спокойно.

В ходе работы получается классный конечный автомат. Аппаратный стек работает сам по себе. Он же на то и «аппаратный». Задачи переключаются.

А вот, как оказалось, запустить этот «конечный автомат» – та еще дилемма.

На самом деле идей было полно. Все они разные. Но каждая из них имеет заметный такой недостаток. Я, до сих пор, и не знаю какой вариант действительно самый крутой. Сейчас выбрал последний, т.к. он наиболее оптимальный по объему кода и быстродействию.

Дилемма

Вот есть у нас, например, три задачи.

У каждой уже есть свой стек, каждая – как на подбор, хоть «косынку» запускай!

Но, ядро ОС вызывается в прерывании. А как работает вызов функций и прерываний? Правильно, при вызове функции в стек сохраняется адрес последней инструкции плюс единичка.

И вот произошло первое прерывание, мы попали в обработчик прерывания:

• Из него мы вызываем обработчик ядра ОС «Kernel()»;

• Сохраняем регистры в стек;

• Выбираем следующую задачу;

• Указатель стека перемещаем на буфер стека задачи;

• И возвращаемся из функции «Kernel()».

А куда возвращаемся?

Адрес возврата в прерывание находится не в стеке этой задачи, т.к. аппаратный указатель стека (Hardware SP) и карта ОЗУ после первого прерывания будет выглядеть так:

• 0xCCDD – адрес возврата в прерывание;

• 0xAABB – адрес возврата в main() из прерывания.

Видно, что адреса возврата попали в исходный стек, который не имеет отношения ни к одной из задач. Если мы теперь переключили указатель стека на буфер стека задачи при смене контекста, то после выхода из функции «Kernel()» мы не вернемся в обработчик прерывания, и из него потом не вернемся в задачу, т.к, если сейчас выбрана «Задача 1», то указатель стека будет указывать на ячейку «38», а там явно нет адреса возврата, там либо мусор, либо нули.

Очевидно, что в стек каждой задачи необходимо вручную подставить:

1. Адрес возврата в тело функции соответствующей задачи (это просто адрес функции);

2. Адрес возврата в обработчик прерывания.

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

А вот второе – далее посмотрим… В этом и проблема!

Решение 1

Первое, что я придумал и реализовал было так.

В «ChangeContext()» есть флаг «static bool firstEntry = true;», который указывает на то, что это первый вход в функцию «ChangeContext()» после сброса процессора.

Если это первый вход – значит мы берем из ОЗУ, по указателю на стек, адрес возврата в прерывание, и можем его подставить в стек каждой задачи.

Этот флаг потом сбрасываем в «false».

И при повторных входах этот код не выполняется.

Получается, что все задачи получают в свой стек адрес возврата, если это первое прерывание ОС.

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

Мы же крутые? Конечно крутые!

Идем дальше!

Решение 2

Адреса обработчиков всех прерываний хранятся в памяти программы, а именно в самом ее начале, начиная с нулевого адреса.

Как получить адреса обработчиков прерываний из памяти программы

Итак, как получить адрес обработчика прерывания из памяти программы.

Открыв HEX файл, ну или проект в режиме отладки, находим, что в памяти программы есть такие буквы:

Красным выделены вектора прерываний. Далее я привожу кривой, но все же наглядный рисунок, совмещенный с даташитом.

И оно же, в увеличенном виде, красным выделил нужные нам данные, для нужного вектора прерывания. Мне нужно было прерывание «TIMER0 COMPA».

Видим данные «0x76C0». Т.к. это Big-endian, на самом деле там «0xC076».

Шо такое 0xC076?

А вот вспомнив, что вначале всех программ на ASM (когда писал на ASM, да, я крутой) я писал:

RJMP 0x0000	; Reset
RJMP 0x0001	; INT0
RJMP 0x0002	; INT1
...

Понимаем, шо это такое есть на самом деле! Точнее, я надеюсь, что я понимаю…

В даташите «AVR Assembler Instruction Set Manual» находим инструкцию RJMP, и видим ее формат:

Где 0b1100 => 0xC

И подтверждаем, что «0xC0» вначале – это инструкция RJMP, отбросив которую получим относительный адрес обработчика прерывания.

Далее получаем фактический адрес в памяти:

Где «15» – это порядковый номер нашего прерывания в таблице векторов прерываний.

В отладке у меня действительно, обработчик прерывания располагался по адресу 0x85.

То есть, в момент инициализации мы можем прочитать адрес оттуда, и во время инициализации каждой задачи сразу подставлять этот адрес в стек этой задачи.

Процессорное время в ядре мы не теряем, т.к. это выполняется только один раз на этапе инициализации.

Уже круто!

Но только это строки кода, которые содержат код для конкретной архитектуры, и конкретно под этот микроконтроллер. И берет адрес конкретного прерывания. А если нам нужен будет Timer2 вместо Timer0? Та вы шо? Это нам шо, городить дефайны, в которых потом можно ногу сломать? И так для каждого микроконтроллера и для каждого прерывания?

Так ну не, это, конечно круто! Но это перебор крутости!

Решение 3

Я держал это решение в голове с самого начала, но принимать его на вооружение ну капец как не хотел.

Оно избавляет нас от недостатков как первого, так и второго способов.

Но приносит свой недостаток. Та бл…

В прерывании мы не вызываем «ChangeContext()» как функцию, а при помощи ассемблера «прыгаем» в эту функцию. Тогда мы оказываемся внутри функции, но при этом, в стек не сохраняется адрес возврата, а значит, вернувшись из функции «ChangeContext()», из стека будет взят сразу адрес возврата в задачу.

Одни плюсы!

Сейчас этот вариант мне, конечно, нравится, т.к. он самый быстрый, и экономит 2 байта на лишний адрес возврата, да и не нужно городить дефайны в config-файле и лишний код.

Но только теперь теряется предсказуемость. Когда мы вызываем функцию – ожидается, что мы из нее вернемся, а мы – не возвращаемся. Работает как часы, но не эстетично.

Оператор «goto» тоже работает как часы, но от него отказались по этой же причине. И не зря, хотя в некоторых ситуациях он наоборот делает код более понятным.

Получается, со скрипом принимаем это решение и тогда код запуска ОС будет выглядеть как в листинге ниже. Это опять псевдокод. Код «OS_Init» и «OS_CreateTask» опустим, т.к. это банально инициализация внутренних переменных.

int main(void)
{
cli();
	Timer1A_Init();
	OS_Init();
	OS_CreateTask(Task1, stackBufTask1, sizeof(stackBufTask1));
	OS_CreateTask(Task2, stackBufTask2, sizeof(stackBufTask2));
sei();
	OS_Start();
}

void OS_Start (void)
{
	currentTask = &tasksList[0];
	StackPointer_SetAddress(currentTask->stackPointer);
	/* Ща буит ассемблер */
	RJMP ChangeContext
  /* Ассемблера не буит */
   
}

void ChangeContext(void)
{
	/* Код написан сильно выше */
}

Голые функции

Гугл не хочет сохранять мой запрос «naked functions», наверное, думает, что я ищу порно, поэтому вот еще один мем, который напрашивается сам по себе:

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

А т.к. компилятор, как упоминалось сильно выше, сам добавляет инструкции push/pop в каждую функцию и прерывание, чтобы сохранить регистры, которые считает нужными, то нам необходимо это как-то отключить, иначе ничего не поедет. Стек просто сломается, или в регистрах будут не те данные.

По умолчанию, любое прерывание и любую функцию компилятор преобразует вот в такое:

/* Прерывание таймера TIMER0 COMPA */
ISR(TIMER0_COMPA_vect)
{
	push R16
	push R17
	
	/* User code */
	
	pop R17
	pop R16
}

/* Обработчик ядра нашей ОС */
void Kernel(void)
{
	push R16
	push R17
	
	/* User code */
	
	pop R17
	pop R16
}

Даже сохранение пары регистров все ломают. Даже одного. Даже на пол битика!

Для решения этой проблемы у функций могут быть атрибуты.

Одним из таких атрибутов является «naked», который говорит компилятору, что он не должен в эту функцию добавлять prolog (инструкции «push») и epilog (инструкции «pop» и возврата «ret» или «reti», если речь о прерывании).

Поэтому прерывание таймера, в котором мы вызываем ядро ОС, и само ядро ОС должны быть «naked» функциями.

Если кто не знает, все эти атрибуты описаны в документации на соответствующий компилятор.

В этом примере я использую стандартный компилятор WinAVR, если не ошибаюсь, который идет вместе с Atmel Studio (ну, или как там сейчас модно говорить – Microchip Studio).

В коде прототипы обработчика прерывания и функции «ChangeContext()» будут иметь вид:

/* Прерывание таймера TIMER0 COMPA */
ISR(TIMER0_COMPA_vect, ISR_NAKED)
{
	
}

/* Обработчик ядра нашей ОС */
void ChangeContext(void) __attribute__ ((naked));

Сервисы ОС

Операционная система должна обеспечивать синхронизацию потоков. Для примера будут реализованы только сервисы «Sleep» и семафоры.

Важным замечанием будет, что мы до сих пор не упоминали задачу «Idle».

Сейчас самое время, т.к. она нужна как раз для этих сервисов.

Задача "Idle"

Если у нас есть несколько задач и все они вызвали сервис «Sleep», и спят ближайшие 1000 мс, что-то же должно выполняться, но только не код самих задач.

Вот здесь нам и нужен Idle-task. Это такая же задача, как и пользовательские, просто она выполняется всегда, когда другие задачи чего-то ждут.

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

Тело этой задачи должно содержать проверку на наличие актуальных задач, и если они есть – инициировать смену контекста.

static void IdleTask(void)
{
	uint8_t i;
	for(;;)
	{
		for(i = 0; i < CONFIG_USER_TASKS_NUMBER; i++)
		{
			Kernel_DisableInterrupts();
			if(Kernel_tasksList[i].status == TASK_STATUS_READY)
			{
				Kernel_Isr();
			}
			Kernel_EnableInterrupts();
		}
	}
}

Sleep

Этот сервис должен позволить задаче передать управление операционной системе, и вернуть управление не ранее чем через указанное кол-во времени.

Тут почти как в ардуинах этих ваших, только во время «delay()» мы занимаемся чем-то полезным.

Логика сервиса проста как цикл «while»:

1. Изменяем статус задачи из «RUN» в «SLEEP»;

2. Сохраняем значение таймера, при котором планировщик изменит статус этой задачи из «SLEEP» в «READY»;

3. Вызываем ядро ОС «Kernel()»;

4. Ядро передает управление другой задаче;

5. И все…

Код сервиса выглядит примерно так:

void Service_Sleep(uint16_t cycles)
{
	Kernel_DisableInterrupts();
	currentTask->status = TASK_STATUS_SLEEP;
	currentTask->timer = cycles;
	ChangeContext();
	Kernel_EnableInterrupts();
}

Семафоры

Этот сервис должен позволить задаче передать управление операционной системе, и вернуть, как только указанный семафор будет кем-то установлен. Например, другой задачей или прерыванием.

Это почти как ничего не делать, только ничего не делать с пользой.

С семафорами чуть сложнее, чем с «Sleep», т.к. здесь появляются опять разные идеи как это все реализовать. Я сделал самый простой способ, где перебирал массив семафоров, но позже чуть оптимизировал.

Теперь задача содержит указатель на семафор, который ждет.

В общем, код, опять, не оптимальный, зато понятный и предсказуемый.

Для упрощения, в этом примере, установка семафора «Service_SetSemaphore()» запускает все задачи, которые ждут конкретный семафор, чтобы не перегружать пример.

void Service_WaitSemaphore(uint8_t semaphoreId)
{
	Kernel_DisableInterrupts();
	if(semaphoreId < CONFIG_SEMAPHORES_NUMBER)
	{
		if(currentTask->semaphorePtr == &semaphores[semaphoreId])
		{
			*currentTask->semaphorePtr = false;
		}
		else
		{
			currentTask->status = TASK_STATUS_SLEEP;
			currentTask->semaphorePtr = &semaphores[semaphoreId];
			ChangeContext();
		}
	}
	Kernel_EnableInterrupts();
}

void Service_SetSemaphore(uint8_t semaphoreId)
{
	uint8_t i;
	if(semaphoreId < CONFIG_SEMAPHORES_NUMBER)
	{
		semaphores[semaphoreId] = true;
		for(i = 0; i < CONFIG_USER_TASKS_NUMBER; i++)
		{
			if(tasksList[i].semaphorePtr == &semaphores[semaphoreId])
			{
				*tasksList[i].semaphorePtr = false;
				tasksList[i].semaphorePtr = NULL;
				tasksList[i].status = TASK_STATUS_READY;
			}
		}
	}
}

Пишем ОС, т.к. мы уже умные

Если мы уже все поняли – можно это все реализовать!

Писать это мы сейчас будем на ATmega88.

Файловая структура

Создаем структуру проекта, она будет выглядеть так:

Далее будем идти снизу вверх, реализуя фичи с самого низкого уровня абстракции до самого высокого.

os/kernel/config/cpu.h

В этом файле у нас будут дефайны для аппаратных фич микроконтроллера, а точнее, регистры.

Я не нашел в стандартной библиотеке "avr/io.h" адрес STACK_POINTER, поэтому пришлось взять его из даташита (0x005D) и задефайнить самостоятельно.

CPU_KERNEL_TIMER_REGISTER – регистр таймера, прерывание которого мы используем в качестве таймера ОС.

Cpu_KernelTimerClear() – должен очищать значение счетчика таймера. Он используется в ядре перед восстановлением контекста и прыжка в следующую задачу, чтобы минимизировать потери процессорного времени на выполнения кода ядра ОС. Как-никак 40 мкс…

#ifndef CPU_H_
#define CPU_H_

#include <avr/io.h>

/* Hardware stack interface config */
#define CPU_STACK_POINTER_REGISTER_ADDRESS	0x005D

/* Timer for 'kernel ISR' interface config */
#define CPU_KERNEL_TIMER_REGISTER		TCNT0
#define Cpu_KernelTimerClear()			(CPU_KERNEL_TIMER_REGISTER = 0x00)

#endif /* CPU_H_ */

os/kernel/config/stack_cfg.h

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

STACK_SPACE_FOR_GENERAL_PURPOSE_REGISTERS – кол-во байт для хранения регистров общего назначения в стеке.

STACK_SPACE_FOR_STATUS_REGISTER – кол-во байт для хранения регистра статуса. Это регистр «SREG» у AVR.

STACK_SPACE_FOR_RETURN_TO_TASK_ROUTINE – кол-во байт для хранения адреса возврата в задачу. Этот адрес используется для возврата в задачу из ядра ОС. Это либо начало задачи, либо точка, на которой задача была прервана в прошлый раз.

STACK_SPACE_FOR_COMMON_USE – это объем данных в стеке, который занят только регистрами.

STACK_MINIMUM_EXPECTED_SIZE_FOR_TASK – это минимальный требуемый размер стека для задачи в принципе.

StackPointer_GetAddress() – этот макрос должен возвращать байт, расположенный по указателю на аппаратный указатель стека.

StackPointer_SetAddress(__addr__) – этот макрос должен устанавливать аппаратный указатель на стек на указанный адрес.

#ifndef STACK_CFG_H_
#define STACK_CFG_H_

#include "cpu.h"

#define STACK_SPACE_FOR_GENERAL_PURPOSE_REGISTERS		32
#define STACK_SPACE_FOR_STATUS_REGISTER							1
#define STACK_SPACE_FOR_RETURN_TO_TASK_ROUTINE			2
#define STACK_SPACE_FOR_COMMON_USE									(STACK_SPACE_FOR_GENERAL_PURPOSE_REGISTERS + STACK_SPACE_FOR_STATUS_REGISTER)
#define STACK_MINIMUM_EXPECTED_SIZE_FOR_TASK				(STACK_SPACE_FOR_COMMON_USE + STACK_SPACE_FOR_RETURN_TO_TASK_ROUTINE)

#define STACK_POINTER_REGISTER											(*((uint16_t *)CPU_STACK_POINTER_REGISTER_ADDRESS))
#define StackPointer_GetAddress()										((uint8_t *)STACK_POINTER_REGISTER)
#define StackPointer_SetAddress(__addr__)						(STACK_POINTER_REGISTER = (uint16_t)(__addr__))

#endif /* STACK_CFG_H_ */

os/kernel/core/…

Модуль «stack» содержит только структуру стека и функции для работы с ним. Там ничего интересного:

stack.h

#ifndef STACK_H_
#define STACK_H_

#include <stdint.h>
#include <stddef.h>

typedef struct {
	uint8_t *stackPointer;
	uint8_t *stackBegin;
	uint8_t *stackEnd;
} Stack_t;

void Stack_Init(Stack_t *stack, uint8_t *stackBuf, size_t stackSize);
void Stack_PushByte(Stack_t *stack, uint8_t byte);

#endif /* STACK_H_ */

stack.c

#include <stdint.h>
#include <stddef.h>
#include "stack.h"

void Stack_Init(Stack_t *stack, uint8_t *stackBuf, size_t stackSize)
{
	uint8_t *stackBegin;
	uint8_t *stackEnd;
	
	stackBegin = (stackBuf + stackSize - 1);
	stackEnd = stackBuf;
	
	stack->stackPointer = stackBegin;
	stack->stackBegin = stackBegin;
	stack->stackEnd = stackEnd;
}

void Stack_PushByte(Stack_t *stack, uint8_t byte)
{
	*stack->stackPointer = byte;
	stack->stackPointer--;
}

С модулем «task» аналогично, только мы уже объединяем некоторые структуры, в т.ч. и «stack», и получаем «задачу».

task.h

#ifndef TASK_H_
#define TASK_H_

#include <stdint.h>
#include <stdbool.h>
#include "stack.h"

typedef enum {
	TASK_STATUS_INIT=0,
	TASK_STATUS_SLEEP_TIMER,
	TASK_STATUS_SLEEP_SEMAPHORE,
	TASK_STATUS_READY,
	TASK_STATUS_RUN
} TaskStatus_e;

typedef union {
	struct {
		unsigned stackOverflow	:1;
		unsigned unused			:7;
	} bits;
	uint8_t byte;
} TaskErrorFlags_t;

typedef struct {
	bool firstEntry;
	TaskStatus_e status;
	TaskErrorFlags_t errorFlags;
	bool *semaphorePtr;
	void (*function)(void);
	Stack_t stack;
	uint16_t timer;
} Task_t;

bool Task_Setup(Task_t *taskPointer, void *taskFunction, uint8_t *stackBuf, size_t stackSize);

#endif /* TASK_H_ */

task.c

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include "../config/stack_cfg.h"
#include "stack.h"
#include "task.h"

bool Task_Setup(Task_t *taskPointer, void *taskFunction, uint8_t *stackBuf, size_t stackSize)
{
	bool result = false;
	bool taskSlotAvailable;
	uint16_t word;
	uint8_t byteHigh;
	uint8_t byteLow;
	
	if((taskPointer == NULL) || (taskFunction == NULL) || (stackBuf == NULL) || (stackSize < STACK_MINIMUM_EXPECTED_SIZE_FOR_TASK))
	{
		result = false;
	}
	else
	{
		taskSlotAvailable = ((void *)taskPointer->function == NULL) ? true : false;
		if(taskSlotAvailable)
		{
			taskPointer->firstEntry = true;
			
			taskPointer->status = TASK_STATUS_READY;
			taskPointer->errorFlags.byte = 0x00;
			taskPointer->semaphorePtr = NULL;
			taskPointer->function = taskFunction;
			taskPointer->timer = 0;
			
			/* Init task stack */
			Stack_Init(&taskPointer->stack, stackBuf, stackSize);
			
			/* Set return address to the task body */
			word = (uint16_t)(taskPointer->function);
			byteHigh = (uint8_t)(word >> 8);
			byteLow = (uint8_t)(word & 0x00FF);
			Stack_PushByte(&taskPointer->stack, byteLow);
			Stack_PushByte(&taskPointer->stack, byteHigh);
			
			/*  */
			result = true;
		}
	}
	return result;
}

Далее уже рассмотрим модуль «kernel». Там есть на что обратить внимание, хотя, не так уж и много.

kernel.h

Здесь есть макросы «Kernel_SaveTaskContext()» и «Kernel_RestoreTaskContext()», для сохранения и восстановления контекста задачи соответственно. Есть два варианта макросов – один сделан через список push/pop, второй через цикл на ассемблере. Первый вариант – заметно быстрее, второй – заметно компактнее. Экономим 84 байта, что для AVR таки заметно, но выполняется этот код на 35 мкс дольше, что тоже заметно, но я не думаю, что кто-то планирует делать на AVR систему реального времени – так что это быстродействие тоже не смертельно, и имеет место быть.

Также, к большому сожалению, многие переменные объявлены как extern, для использования отдельного модуля «services». Если перенести все сервисы в модуль «kernel» – можно будет убрать модификатор «extern», но я так не хочу.

#ifndef KERNEL_H_
#define KERNEL_H_

#include <stdint.h>
#include <stdbool.h>
#include "task.h"
#include "../../config.h"

#if(CONFIG_KERNEL_USE_COMPACT_PUSH_POP)
/***************************************/
#define Kernel_SaveTaskContext()		\
	asm volatile(						\
	";------------------\r\n"			\
	"	push r31		\r\n"			\
	"	push r30		\r\n"			\
	"	push r29		\r\n"			\
	"	push r28		\r\n"			\
	";------------------\r\n"			\
	"	in r28,__SREG__	\r\n"			\
	"	push r28		\r\n"			\
	";------------------\r\n"			\
	"	ldi r29,(32-4)	\r\n"			\
	"	ldi ZL,(32-4)	\r\n"			\
	"	ldi ZH,0		\r\n"			\
	";------------------\r\n"			\
	"loop_push:			\r\n"			\
	"	ld r28,-Z		\r\n"			\
	"	push r28		\r\n"			\
	"	dec r29			\r\n"			\
	"	brne loop_push	\r\n"			\
	";------------------\r\n");
/***************************************/
#define Kernel_RestoreTaskContext()		\
	asm volatile(						\
	";----------------------\r\n"		\
	"	ldi r29,(32-4)		\r\n"		\
	"	ldi ZL,0			\r\n"		\
	"	ldi ZH,0			\r\n"		\
	"loop_pop:				\r\n"		\
	"	pop r28				\r\n"		\
	"	st Z+,r28			\r\n"		\
	"	dec r29				\r\n"		\
	"	brne loop_pop		\r\n"		\
	";----------------------\r\n"		\
	"	pop r28				\r\n"		\
	"	out __SREG__,r28	\r\n"		\
	";----------------------\r\n"		\
	"	pop r28				\r\n"		\
	"	pop r29				\r\n"		\
	"	pop r30				\r\n"		\
	"	pop r31				\r\n"		\
	";----------------------\r\n");
#else
/***************************************/
#define Kernel_SaveTaskContext()		\
	asm volatile(						\
	"push r31	\r\n"					\
	"push r30	\r\n"					\
	"push r29	\r\n"					\
	"push r28	\r\n"					\
	"push r27	\r\n"					\
	"push r26	\r\n"					\
	"push r25	\r\n"					\
	"push r24	\r\n"					\
	"push r23	\r\n"					\
	"push r22	\r\n"					\
	"push r21	\r\n"					\
	"push r20	\r\n"					\
	"push r19	\r\n"					\
	"push r18	\r\n"					\
	"push r17	\r\n"					\
	"push r16	\r\n"					\
	"push r15	\r\n"					\
	"push r14	\r\n"					\
	"push r13	\r\n"					\
	"push r12	\r\n"					\
	"push r11	\r\n"					\
	"push r10	\r\n"					\
	"push r9	\r\n"					\
	"push r8	\r\n"					\
	"push r7	\r\n"					\
	"push r6	\r\n"					\
	"push r5	\r\n"					\
	"push r4	\r\n"					\
	"push r3	\r\n"					\
	"push r2	\r\n"					\
	"push r1	\r\n"					\
	"push r0	\r\n"					\
	"in r16,__SREG__\r\n"				\
	"push r16	\r\n");
/***************************************/
#define Kernel_RestoreTaskContext()		\
	asm volatile(						\
	"pop r16	\r\n"					\
	"out __SREG__,r16\r\n"				\
	"pop r0		\r\n"					\
	"pop r1		\r\n"					\
	"pop r2		\r\n"					\
	"pop r3		\r\n"					\
	"pop r4		\r\n"					\
	"pop r5		\r\n"					\
	"pop r6		\r\n"					\
	"pop r7		\r\n"					\
	"pop r8		\r\n"					\
	"pop r9		\r\n"					\
	"pop r10	\r\n"					\
	"pop r11	\r\n"					\
	"pop r12	\r\n"					\
	"pop r13	\r\n"					\
	"pop r14	\r\n"					\
	"pop r15	\r\n"					\
	"pop r16	\r\n"					\
	"pop r17	\r\n"					\
	"pop r18	\r\n"					\
	"pop r19	\r\n"					\
	"pop r20	\r\n"					\
	"pop r21	\r\n"					\
	"pop r22	\r\n"					\
	"pop r23	\r\n"					\
	"pop r24	\r\n"					\
	"pop r25	\r\n"					\
	"pop r26	\r\n"					\
	"pop r27	\r\n"					\
	"pop r28	\r\n"					\
	"pop r29	\r\n"					\
	"pop r30	\r\n"					\
	"pop r31	\r\n");
#endif

#define Kernel_Nop()					asm volatile("nop")
#define Kernel_JumpToIsr()				asm volatile("rjmp Kernel_Isr")
#define Kernel_DisableInterrupts()		asm volatile("cli")
#define Kernel_EnableInterrupts()		asm volatile("sei")
#define Kernel_ReturnFromIsr()			asm volatile("reti")

extern uint16_t Kernel_timer;
extern Task_t *Kernel_currentTask;
extern Task_t Kernel_tasksList[CONFIG_USER_TASKS_NUMBER];
extern bool Kernel_semaphores[CONFIG_SEMAPHORES_NUMBER];

void Kernel_Init(void);
void Kernel_Start(void);
void Kernel_Isr(void) __attribute__ ((naked));

#endif /* KERNEL_H_ */

kernel.c

Здесь видно, что обработчик ядра не сильно изменился, в сравнении с нашим псевдокодом выше, все инструкции на месте, ну и, сюрприз-сюрприз, на самом деле она называется по-другому! О нет!

ErrorCheck_StackOverflowed() – макрос, для определения переполнения стека задачи. Далее в планировщике можно увидеть ловушку с бесконечным циклом. Но, на самом деле, эта проверка определяет переполнение стека, если мы вошли в ядро с переполнением, а вот если он в задаче переполнился, а потом вернулся обратно – ну никак. Это отдельная тема, есть пара идей, как это проверять, но это лютые глупости без аппаратных ловушек… Например – проверять содержимое ОЗУ каждый раз на порчу, при помощи контрольных сумм, или вроде того, но это медленно, шо капец… Так что здесь глупостей таких пока что не делаем. Возможно, потом ​

Хочу обратить внимание на функцию «TimersRoutine()». В нашем примере кода сервиса «Sleep» немного более примитивная реализация таймера, и там каждая задача имеет свой счетчик, на самом деле в моей реализации это не так. Видно, что каждая задача содержит константу, с которой сравнивается общий таймер ядра «Kernel_timer». И только он один инкрементируется, что оптимальнее.

kernelInterruptTimer – также интересный момент. Эта переменная хранит значение аппаратного таймера, прерывание которого мы используем для ОС. В функции планировщика «Scheduler()» мы проверяем его на вопрос – «аппаратный таймер дошел до своего предела и мы в обработчике ядра из-за прерывания, или из-за ручной смены контекста вызовом сервиса?». И только потом инкрементируется таймер сервиса «Sleep». Без этой фичи – вызовы сервисов для смены контекста дают сильную погрешность таймера «Sleep».

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include <string.h>
#include "../config/cpu.h"
#include "../config/stack_cfg.h"
#include "stack.h"
#include "kernel.h"

#define ErrorCheck_StackOverflowed()														\
	(((Kernel_currentTask->stack.stackPointer + 1) < Kernel_currentTask->stack.stackEnd)	\
	|| (Kernel_currentTask->stack.stackPointer > Kernel_currentTask->stack.stackBegin))

Task_t *Kernel_currentTask;
Task_t Kernel_tasksList[CONFIG_USER_TASKS_NUMBER];
bool Kernel_semaphores[CONFIG_SEMAPHORES_NUMBER];
uint16_t Kernel_timer;

static void Scheduler(void);
static void IdleTask(void);
static void TimersRoutine(void);
static void SelectNextTask(void);

static Task_t taskIdle;
static uint8_t taskIdleStackBuf[CONFIG_IDLE_TASK_STACK_SIZE];

static Stack_t kernelStack;
static uint8_t kernelStackBuf[CONFIG_KERNEL_STACK_SIZE];

void Kernel_Init(void)
{
	/* Clear variables */
	Kernel_timer = 0;
	memset(Kernel_tasksList, 0, sizeof(Kernel_tasksList));
	memset(Kernel_semaphores, 0, sizeof(Kernel_tasksList));
	
	/* Initialize variables */
	Task_Setup(&taskIdle, IdleTask, taskIdleStackBuf, sizeof(taskIdleStackBuf));
	Stack_Init(&kernelStack, kernelStackBuf, sizeof(kernelStackBuf));
}

void Kernel_Start(void)
{
	Kernel_currentTask = &taskIdle;
	Kernel_currentTask->firstEntry = false;
	StackPointer_SetAddress(Kernel_currentTask->stack.stackPointer);
	Kernel_JumpToIsr();
}

void Kernel_Isr(void)
{
	/* Save task context to the stack buffer */
	Kernel_SaveTaskContext();
	
	/* Save current state of the hardware stack pointer to the current task structure */
	Kernel_currentTask->stack.stackPointer = StackPointer_GetAddress();
	
	/* Set stack pointer to the kernel stack buffer */
	StackPointer_SetAddress(kernelStack.stackPointer);
	
	/* Process scheduler logic */
	Scheduler();
	
	/* Save current state of the hardware stack pointer tor the kernel stack structure */
	kernelStack.stackPointer = StackPointer_GetAddress();
	
	/* Move stack pointer to the stack buffer of the next task */
	StackPointer_SetAddress(Kernel_currentTask->stack.stackPointer);
	
	Cpu_KernelTimerClear();
	
	/* If it's first entry to Kernel ISR from this task -> then do nothing */
	if(Kernel_currentTask->firstEntry)
	{
		Kernel_currentTask->firstEntry = false;
	}
	/* else -> restore task context from stack */
	else
	{
		Kernel_RestoreTaskContext();
	}
	
	/* Return from 'naked' function that is also interrupt routine */
	Kernel_ReturnFromIsr();
}

static void Scheduler(void)
{
	static uint8_t kernelInterruptTimer = 0;
	
	/* Traps */
	if(ErrorCheck_StackOverflowed())
	{
		for(;;)
		{
			Kernel_Nop();
		}
	}
	
	kernelInterruptTimer += CPU_KERNEL_TIMER_REGISTER;
	if(kernelInterruptTimer >= CONFIG_KERNEL_ISR_TIMER_COMPARATOR_VALUE)
	{
		kernelInterruptTimer = 0;
		TimersRoutine();
	}
	SelectNextTask();
}

static void IdleTask(void)
{
	uint8_t i;
	for(;;)
	{
		for(i = 0; i < CONFIG_USER_TASKS_NUMBER; i++)
		{
			Kernel_DisableInterrupts();
			if(Kernel_tasksList[i].status == TASK_STATUS_READY)
			{
				Kernel_Isr();
			}
			Kernel_EnableInterrupts();
		}
	}
}

static void TimersRoutine(void)
{
	uint8_t i;
	
	Kernel_timer++;
	
	for(i = 0; i < CONFIG_USER_TASKS_NUMBER; i++)
	{
		if(Kernel_tasksList[i].status == TASK_STATUS_SLEEP_TIMER)
		{
			if(Kernel_tasksList[i].timer == Kernel_timer)
			{
				Kernel_tasksList[i].status = TASK_STATUS_READY;
			}
		}
	}
}

static void SelectNextTask(void)
{
	static uint8_t currentTaskIndex = 0;
	bool taskAvailable;
	uint8_t i;
	
	if(Kernel_currentTask->status == TASK_STATUS_RUN)
	{
		Kernel_currentTask->status = TASK_STATUS_READY;
	}
	
	i = CONFIG_USER_TASKS_NUMBER;
	while(i--)
	{
		Kernel_currentTask = &Kernel_tasksList[currentTaskIndex];
		
		taskAvailable = false;
		if(Kernel_currentTask->status == TASK_STATUS_READY)
		{
			taskAvailable = true;
		}
		
		currentTaskIndex++;
		if(currentTaskIndex >= CONFIG_USER_TASKS_NUMBER)
		{
			currentTaskIndex = 0;
		}
		
		if(taskAvailable)
		{
			break;
		}
	}
	
	if(!taskAvailable)
	{
		Kernel_currentTask = &taskIdle;
	}
	
	Kernel_currentTask->status = TASK_STATUS_RUN;
}

os/services/…

 service.h

Ну тут скукотень, конечно же…

#ifndef SERVICES_H_
#define SERVICES_H_

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>

void Service_InitKernel(void);
void Service_Sleep(uint16_t cycles);
void Service_WaitSemaphore(uint8_t semaphoreId);
void Service_SetSemaphore(uint8_t semaphoreId, bool broadcast, bool changeContext);
bool Service_CreateUserTask(void *taskFunction, uint8_t *stackBuf, size_t stackSize);

#endif /* SERVICES_H_ */

service.c

А вот тут кое-что есть. Но лучше бы была скукотень, я не хочу описывать, я заеб устал…

Окей…

Service_Sleep() – здесь как раз таки видно тот прикол с таймером. Мы рассчитываем будущее значение «Kernel_timer» с учетом переполнения, когда пройдет указанное кол-во тактов операционной системы. И сохраняем это значение в таймер задачи.

Service_SetSemaphore() – сервис установки семафора, и у него есть аргументы «broadcast» и «changeContext». Если первый == «true», значит одновременно «поедут» все задачи, которые ждут данный семафор. Второй аргумент, если «true», инициирует смену контекста. Например, полезно, если вы устанавливаете семафор в другой задаче, а не в прерывании.

Установка семафора при аргументе «broadcast == false» возможно отработает не так как нужно, т.к. у меня сейчас не реализована очередь семафоров, и семафор будет все время забирать первая задача в списке задач. Назовем это не «Лень», а «Errata».

У «Atmel», кстати, тоже Errata есть, а чем я хуже?

#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>
#include "../config.h"
#include "../kernel/core/task.h"
#include "../kernel/core/kernel.h"

/*
* Initializes kernel
*/
void Service_InitKernel(void)
{
	Kernel_Init();
}

/*
* Sleep service.
* Immediately changes the context.
* Arguments:
*	cycles	- number of OS timer ticks, after which task will be continued.
*/
void Service_Sleep(uint16_t cycles)
{
	Kernel_DisableInterrupts();
	Kernel_currentTask->status = TASK_STATUS_SLEEP_TIMER;
	
	if((UINT16_MAX - Kernel_timer) < cycles)
	{
		cycles -= (UINT16_MAX - Kernel_timer);
		Kernel_currentTask->timer = cycles;
	}
	else
	{
		Kernel_currentTask->timer = (Kernel_timer + cycles);
	}
	
	Kernel_Isr();
	Kernel_EnableInterrupts();
}

/*
* Transfers task to the sleep state to wait for the binary semaphore.
* - If the semaphore is already set -> semaphore will be cleared and function returns to the current task.
* - If the semaphore isn't set yet -> it changes the context.
*/
void Service_WaitSemaphore(uint8_t semaphoreId)
{
	Kernel_DisableInterrupts();
	if(semaphoreId < CONFIG_SEMAPHORES_NUMBER)
	{
		if(Kernel_currentTask->semaphorePtr == &Kernel_semaphores[semaphoreId])
		{
			*Kernel_currentTask->semaphorePtr = false;
		}
		else
		{
			Kernel_currentTask->status = TASK_STATUS_SLEEP_SEMAPHORE;
			Kernel_currentTask->semaphorePtr = &Kernel_semaphores[semaphoreId];
			Kernel_Isr();
		}
	}
	Kernel_EnableInterrupts();
}

/*
* Sets the semaphore by ID.
* Arguments:
*	semaphoreId		- Semaphore ID;
*	broadcast		- allows you continue tasks synchronic, if all of them waits current semaphore:
*					  If 'true', then status of all tasks which waits this semaphore will be changed to the 'ready',
*					  If 'false', then first task which waits this semaphore will be changed to the 'ready'.
*	changeContext	- context will be changed immediately.
*/
void Service_SetSemaphore(uint8_t semaphoreId, bool broadcast, bool changeContext)
{
	uint8_t i;
	if(semaphoreId < CONFIG_SEMAPHORES_NUMBER)
	{
		Kernel_semaphores[semaphoreId] = true;
		for(i = 0; i < CONFIG_USER_TASKS_NUMBER; i++)
		{
			if(Kernel_tasksList[i].semaphorePtr == &Kernel_semaphores[semaphoreId])
			{
				*Kernel_tasksList[i].semaphorePtr = false;
				Kernel_tasksList[i].semaphorePtr = NULL;
				Kernel_tasksList[i].status = TASK_STATUS_READY;
				if(!broadcast)
				{
					break;
				}
			}
		}
		if(changeContext)
		{
			Kernel_DisableInterrupts();
			Kernel_currentTask->status = TASK_STATUS_READY;
			Kernel_Isr();
			Kernel_EnableInterrupts();
		}
	}
}

/*
* Creates user task in the scheduler queue.
*/
bool Service_CreateUserTask(void *taskFunction, uint8_t *stackBuf, size_t stackSize)
{
	bool result;
	uint8_t i;
	
	result = false;
	for(i = 0; i < CONFIG_USER_TASKS_NUMBER; i++)
	{
		result = Task_Setup(&Kernel_tasksList[i], taskFunction, stackBuf, stackSize);
		if(result)
		{
			break;
		}
	}
	return result;
}

os/config.h

Самое унылое.

Но все же.

Конфигурация ОС.

Интересного нет ничего, кроме оговорочки, что есть константа «CONFIG_KERNEL_ISR_TIMER_COMPARATOR_VALUE», которая должна хранить значение компаратора для таймера, который мы используем для ОС.

Это не круто, но, иначе никак, т.к. это число нам нужно для компенсации частых вызовов смены контекста вручную из задач (помните, было выше?).

#ifndef CONFIG_H_
#define CONFIG_H_

#include <stdint.h>
#include "kernel/config/stack_cfg.h"

#define CONFIG_KERNEL_USE_COMPACT_PUSH_POP			0
#define CONFIG_USER_TASKS_NUMBER					5
#define CONFIG_SEMAPHORES_NUMBER					10

#define CONFIG_KERNEL_ISR_TIMER_COMPARATOR_VALUE	125

/* Idle task stack must have extra space for return address when it's call 'Kernel_Isr()' from own body */
#define CONFIG_IDLE_TASK_STACK_SIZE					(STACK_MINIMUM_EXPECTED_SIZE_FOR_TASK + 2)

/* Kernel stack must have space only for function, that can be called in 'Kernel_Isr()' */
/* Please, change it only if you change 'Kernel_Isr' routine!!! */
#define CONFIG_KERNEL_STACK_SIZE					16

#endif /* CONFIG_H_ */

os/os.h

Ну и наконец-то… Дождались…

Этот файл нужно подключить в ваш «main()», ну или откуда вы там ОС вызывать собираетесь.

И этот файл содержит интерфейсы для работы с ОС.

#ifndef OS_H_
#define OS_H_

#include "kernel/core/kernel.h"
#include "services/services.h"

#define OS_Init()												Service_InitKernel()
#define OS_Start()												Kernel_Start()
#define OS_Isr()												Kernel_JumpToIsr()
#define OS_Sleep(__cycles__)									Service_Sleep((__cycles__))
#define OS_SemaphoreWait(__id__)								Service_WaitSemaphore((__id__))
#define OS_SemaphoreSet(__id__)									Service_SetSemaphore((__id__), false, false)
#define OS_SemaphoreSetImmidiately(__id__)						Service_SetSemaphore((__id__), false, true)
#define OS_SemaphoreSetBroadcast(__id__)						Service_SetSemaphore((__id__), true, false)
#define OS_SemaphoreSetBroadcastImmidiately(__id__)				Service_SetSemaphore((__id__), true, true)
#define OS_CreateTask(__func__, __stack_buf__, __stack_size__)	Service_CreateUserTask((__func__), (__stack_buf__), (__stack_size__))

#endif /* OS_H_ */

Результат работы

Далее скриншоты примера работы нашей ОС.

Квант времени задачи 1 мс, используем 4 задачи вызывая в каждой сервис «Sleep» на 100 мс.

Код «main()» ниже. Идентификаторы некоторых макросов и функций могут отличаться от примеров с псевдокодом. Простите, если найдете что-то отличающееся ​

Код "main()", для примера, как это сделано:

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include <avr/io.h>
#include <avr/interrupt.h>
#include "os/os.h"

#define TIMER_KERNEL_PERIOD_debug	1
#define TIMER_KERNEL_PERIOD_1ms		2
#define TIMER_KERNEL_PERIOD_8ms		3
#define TIMER_KERNEL_PERIOD			TIMER_KERNEL_PERIOD_1ms

void Gpio_Init(void);
void Timer1A_Init(void);
void Timer2A_Init(void);

uint8_t stackBufTask1[64];
uint8_t stackBufTask2[64];
uint8_t stackBufTask3[64];
uint8_t stackBufTask4[64];

void Task1(void);
void Task2(void);
void Task3(void);
void Task4(void);

int main(void)
{
	cli();
	Gpio_Init();
	Timer1A_Init();
	OS_Init();
	OS_CreateTask(Task1, stackBufTask1, sizeof(stackBufTask1));
	OS_CreateTask(Task2, stackBufTask2, sizeof(stackBufTask2));
	OS_CreateTask(Task3, stackBufTask3, sizeof(stackBufTask3));
	OS_CreateTask(Task4, stackBufTask4, sizeof(stackBufTask4));
	sei();
	OS_Start();
}

void Gpio_Init(void)
{
	DDRB |= 0xFF;
	PORTB = 0x00;
}

void Timer1A_Init(void)
{
	TCCR0A = 0x00;					/* Normal mode, PWM pin OC0A/OC0B disconnected */
	TIMSK0 |= (1<<OCIE0A);			/* Enable OVF A interrupt */
	#if(TIMER_KERNEL_PERIOD == TIMER_KERNEL_PERIOD_debug)
	TCCR0B = (1<<CS00);				/* Freq/1	*/
	OCR0A = 50;						/* 50 ticks	*/
	#elif(TIMER_KERNEL_PERIOD == TIMER_KERNEL_PERIOD_1ms)
	TCCR0B = (1<<CS01)|(1<<CS00);	/* Freq/64	*/
	OCR0A = 125;					/* 1 ms		*/
	#elif(TIMER_KERNEL_PERIOD == TIMER_KERNEL_PERIOD_8ms)
	TCCR0B = (1<<CS02);				/* Freq/256	*/
	OCR0A = 250;					/* 8 ms		*/
	#else
	#error "Wrong kernel timer period specified!"
	#endif
	TCNT0 = 0x00;					/*  */
	TIFR0 = 0xFF;					/* ISR flags resets by writing '0xFF' */
}

void Timer2A_Init(void)
{
	TCCR2A = 0x00;					/* Normal mode, PWM pin OC0A/OC0B disconnected */
	TIMSK2 |= (1<<OCIE2A);			/* Enable OVF A interrupt */
	TCCR2B = (1<<CS22);				/* Freq/64	*/
	OCR2A = 25;						/* 200 uS	*/
	TCNT2 = 0x00;					/*			*/
	TIFR2 = 0xFF;					/* ISR flags resets by writing '0xFF' */
}

void Task1(void)
{
	for(;;)
	{
		OS_Sleep(100);
		PORTB ^= 1;
	}
}

void Task2(void)
{
	for(;;)
	{
		OS_Sleep(100);
		PORTB ^= 2;
	}
}

void Task3(void)
{
	for(;;)
	{
		OS_Sleep(100);
		PORTB ^= 4;
	}
}

void Task4(void)
{
	for(;;)
	{
		OS_Sleep(100);
		PORTB ^= 8;
	}
}

ISR(TIMER0_COMPA_vect, ISR_NAKED)
{
	OS_Isr();
}

Скриншоты

Схема в протеусе для ардуинщиков 99-го левела:

Осцилоскопия

Вот так все работает. Видно, что есть 4 синхронизированных меандра.

Но, если присмотреться, видно смещение на 40 мкс между задачами. Как раз весь код ядра с планировщиком и сервисом «Sleep» выполняется около 40 мкс, что проверено в отладке.

Ссылки

GitHub я себе еще не завел, поэтому залил проект на свой гугл-диск: здесь

Ссылка на статью, на которую я уже ссылался пару раз: тут

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

Соглашение AVR-GCC для использования регистров компилятором: тут