LINUX.ORG.RU

Собственная Мини-RTOS

 ,


1

2

Пилю я тут потихоньку свой фреймворк для микроконтроллеров (https://github.com/KivApple/controllerFramework) и дошёл до осознания того, что там обязательно нужна небольшая RTOS (разумеется, опциональная). Разобраться, как переключать задачи на ARM Cortex-M3 мне труда не составило (для M4, насколько я понимаю, надо просто добавить сохранение состояния FPU), но теперь встали некоторые архитектурные вопросы.

1) Реализация планировщика. Собственно как? Сейчас тупой алгоритм со сложностью О(N). Бежим по связанному списку процессов и ищем процесс с максимальным приоритетом, который при этом готов к исполнению. Переключаемся на найденный процесс.

int maxPriority = THREAD_PRIORITY_STOPPED;
Thread *thread = currentThread;
do {
	thread = thread->next;
	if ((thread->priority > maxPriority) && (threadReady(thread, tickCounter))) {
		maxPriority = thread->priority;
		nextThread = thread;
	}
} while (thread != currentThread->next);

Но это, вероятно, что-то не то. Нужна очередь с приоритетом. Типа извлекаем из очереди очередной процесс и переключаемся на него, а текущий процесс пихаем обратно в очередь. Если мы попали в планировщик раньше времени (обычно мы попадаем туда из обработчика SysTick), потому что процесс уснул - то не пихаем его обратно в очередь. Если мы хотим разбудить процесс (это делается в функции отправки сигнала процессу, а не в планировщике), то пихаем его в очередь. И тут я вижу множество разных вариантов реализации очереди с приоритетом - бинарная куча, полиноминальная куча, куча Фибоначчи, 2-3 куча... Какой из них следует выбрать? Какие алгоритмы применяются в других RTOS?

2) Как организовать запуск RTOS? Я создаю процесс с именем main и переключаюсь на него. Однако получается, что выполнение начинается с нового адреса, указанного юзером при инициализации RTOS. А существующие RTOS позволяют просто вызвать из main функцию типа start_rtos и дальнейший код автоматически продолжает исполнятся в рамках первого процесса. Как они так делают? Это получается надо весь текущий стек скопировать на место стека только что созданного процесса, а начинать с адреса возврата из функции инициализации (текущий стек обычно остаётся в качестве стека для прерываний)? Я туплю, как всё происходит.

★★★★★

чем тебя бугуртос не устроила?)

devl547 ★★★★★ ()
Ответ на: комментарий от beastie

У тебя вообще есть приоритеты задач (не вижу ничего про них в коде)? А то без приоритетов мне более-менее понятно, как реализовывать.

KivApple ★★★★★ ()
Ответ на: комментарий от exception13

Я делаю это в первую очередь ради HAL с нормальной кросс-платформенностью. В том числе эта штука должна быть оберёткой для pthread, i2c-dev и т. п., если выбрать в качестве целевой платформы Linux.

KivApple ★★★★★ ()
Ответ на: комментарий от exception13

У ChibiOS мне категорически не нравится, как там проводится инициализация модулей HAL. Там нужно буквально указать значения основных регистров периферии (например, для I2C надо указать значение нескольких CRx). Да, потом с ней можно работать кросс-платформенными функциями, но инициализация достаточно неприятная процедура. И всё ради чего? Чтобы сэкономить несколько байтиков и микросекунд на инициализации (к инициализации вообще обычно не особо строгие временные требования)?

Плюс основная платформа для ChibiOS таки микроконтроллеры. Там нет обёрток для i2c-dev, gpio и других вещей, которые работают под Linux. Платформа simulator по сути лишь предоставляет заглушки для всех функций работы с аппаратурой. А я хочу, чтобы можно было легко портировать прошивку от микроконтроллера на одноплатник, если плевать на риалтаймовость. При этом были доступны все библиотеки, написанные для моего фреймворка (в качестве примера я реализовал драйвера для I2C-сенсоров MPU6050, HMC5883 и MS5611). Портировать ChibiOS на Linux также затруднительно, потому что там гвоздями прибито, что должен использоваться собственный планировщик и примитивы синхронизации от ChibiOS (я же на платформе Linux предполагаю просто предоставить свои обёртки над pthread).

Про Inferno гуглится какая-то не та ОС. Не очень подходящая для микроконтроллеров (на википедии пишут что-то про свой язык программирования и байт код, а на скриншоте изображён гуй).

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 3)
Ответ на: комментарий от KivApple

Нет, у меня там first-come, first-serve и preemptive time-sharing.

Т.е. каждый таск в очереди будет гарантированно запущен на 200ms. Или он сам вернёт управление (sleep), или будет насильно прерван.

Приоритеты — imho это не очень хорошее решение. Посмотри лучше на EDF — он гарантирует (как единственный) 100% утилизации CPU.

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 2)
Ответ на: комментарий от beastie

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

Как это реализовать при использовании приоритетов? Максимальный приоритет у процесса руления железкой. Приоритет пониже у процесса работы с USB. И самый низкий приоритет у бесконечного цикла отправки МК в спящий режим.

Соответственно, если что в первую очередь отвалится USB-телеметрия, а железка будет продолжать корректно работать. Более того, это «если что» может быть штатным режимом. Пользователь может запрашивать телеметрию с любой частотой, но если железка потребует внимание, то не все запросы обработаются, но пользователь это как-нибудь переживёт (а железка нет). Также юзер не заметит отставания телеметрии на несколько миллисекунд, а железка задержку управляющего сигнала - заметит.

А когда делать нечего автоматически активируется idle-процесс и отправляет систему в спячку. Любое прерывание пробуждает МК и если обработчик разбудит какой-нибудь процесс, то МК будет бодрствовать, пока не закончит обработку (ведь любой процесс полностью вытеснит idle).

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от KivApple

У меня там всё таки чуть-чуть приоритетов есть: если таск возвращается из mutex он ставится в начало очереди, если из спячки — то в конец. Это можно развить дальше.

Проблема с приоритетами ещё в том: что ты будешь делать, если у тебя 2 (3, 4 ...) таска с одинаковым приоритетом?

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

beastie ★★★★★ ()
Ответ на: комментарий от beastie

Проблема с приоритетами ещё в том: что ты будешь делать, если у тебя 2 (3, 4 ...) таска с одинаковым приоритетом?

Выполнять их по очереди, предоставляя равные кванты времени, пока кто-нибудь не уснёт, не?

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от KivApple

PS: и да, решается очень просто: исходя из моего примера — просто добалением второй (приоритетной) очереди. Это для случая с фиксированными приоритетами.

beastie ★★★★★ ()
Ответ на: комментарий от KivApple

Про Inferno гуглится какая-то не та ОС.

То, что ты нагуглил — это продолжение Plan9.

beastie ★★★★★ ()

Касательно планировщика набросал вот такой код:

Thread *threadQueue[TASK_SCHEDULER_MAX_PRIORITY];
int threadMaxRunningPriority = 0;

inline Thread *schedulerFindNextTask(void) {
	for (; threadMaxRunningPriority >= 0; threadMaxRunningPriority--) {
		if (threadQueue[threadMaxRunningPriority] != NULL) {
			Thread *nextThread = threadQueue[threadMaxRunningPriority];
			threadQueue[threadMaxRunningPriority] = nextThread->platformData.nextScheduled;
			return nextThread;
		}
	}
	return NULL;
}

void schedulerResumeTask(Thread *thread) {
	if (threadQueue[thread->priority] == NULL) {
		thread->platformData.nextScheduled = thread;
		thread->platformData.prevScheduled = thread;
		threadQueue[thread->priority] = thread;
	} else {
		thread->platformData.nextScheduled = threadQueue[thread->priority];
		thread->platformData.prevScheduled = thread->platformData.nextScheduled->platformData.prevScheduled;
		thread->platformData.nextScheduled->platformData.prevScheduled = thread;
		thread->platformData.prevScheduled->platformData.nextScheduled = thread;
	}
	if (thread->priority > threadMaxRunningPriority) {
		threadMaxRunningPriority = thread->priority;
	}
}

void schedulerSuspendTask(Thread *thread) {
	if (threadQueue[thread->priority] == thread) {
		threadQueue[thread->priority] = thread->platformData.nextScheduled;
	}
	if (threadQueue[thread->priority] == thread) {
		threadQueue[thread->priority] = NULL;
	} else {
		thread->platformData.nextScheduled->platformData.prevScheduled = thread->platformData.prevScheduled;
		thread->platformData.prevScheduled->platformData.nextScheduled = thread->platformData.nextScheduled;
	}
}

По идее должна быть производительность получше (O(1) пока у нас не уснут все задачи с максимальным в текущий момент приоритетом, затем O(N) для понижения максимального активного приоритета, причём N зависит от того насколько нужно спуститься приоритетов, а не от количества задач, затем опять О(1)).

Соответственно, когда поток начинает чего-то ждать вызываем schedulerSuspendTask для него (если это текущий поток, то ещё и сразу надо вызвать преждевременное переключение задач). Если событие, которое ждал поток случилось, то вызываем schedulerResumeTask. Ну а планировщик вызывает schedulerFindTask, чтобы определить, кому теперь надо отдавать управление. NULL возвращаться не должен никогда (в системе должен быть хотя бы один неспящий поток в любой момент времени, в крайнем случае это будет idle-поток с минимальным приоритетом). Если он вернулся устраиваем Kernel Panic.

Однако в этом коде не хватает синхронизации. В том плане, что если случится переключение задач (или же прерывание, которое вызывает пробуждение процесса, усыплять потоки прерывания не могут) в середине функции засыпания или пробуждения, то может случиться непредсказуемое. Я пока туплю, как её правильно добавить. Не поможете?

sudo cast beastie

KivApple ★★★★★ ()
Последнее исправление: KivApple (всего исправлений: 1)

ОП, а что тебе мешает заюзать CMSIS-RTOS? ARM выкладывает адаптированную RTX в этом своем CMSIS.

Или твой фреймворк будет работать не только на ARMах?

Тогда могу предложить использовать мое поделие: https://github.com/shkolnick-kun/bugurtos Там есть все, о чем ты спрашиваешь.

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от KivApple

В том числе эта штука должна быть оберёткой для pthread, i2c-dev и т. п., если выбрать в качестве целевой платформы Linux.

Обычно phthread является оберткой для внутренностей конкретной ОС.

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

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

itn ★★ ()
Ответ на: комментарий от shkolnick-kun

Или твой фреймворк будет работать не только на ARMах?

this.

Там есть все, о чем ты спрашиваешь.

Там нет HAL (тесно интегрированного с RTOS) и поддержки Linux (так чтобы RTOS исчезла и просто стала прослойкой к pthread, а HAL прослойкой ко всяким разным интерфейсам ввода-вывода Linux типа i2cdev).

Кстати, твоя ОС умеет такой примитив синхронизации, как Condition Variables? Просто интересно, по исходникам с ходу не понятно.

KivApple ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

Но ничто не мешает сделать наоборот :-)

С учётом того, что под Linux все советуют использовать libc и pthread, а не дёргать syscall руками.

KivApple ★★★★★ ()
Ответ на: комментарий от itn

Р. Лав «Разработка ядра Linux», например.

Начать со спецификации ОС, а чтобы ее сделать - надо что-то вроде ТЗ, в котором распиши «Какие проблемы <программистов> я собираюсь решить».

На хорошую спецификацию уходит 2/3 времени на самом деле.

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от KivApple

Там нет HAL (тесно интегрированного с RTOS)

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

В сущности BuguRTOS - тупо драйвер процессора, а процессор - такой же девайс, как и все остальные.

поддержки Linux (так чтобы RTOS исчезла и просто стала прослойкой к pthread, а HAL прослойкой ко всяким разным интерфейсам ввода-вывода Linux типа i2cdev).

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

Кстати, твоя ОС умеет такой примитив синхронизации, как Condition Variables? Просто интересно, по исходникам с ходу не понятно.

Есть c версии 0.8.1: https://github.com/shkolnick-kun/bugurtos/blob/master/libs/native/cond.h

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от KivApple

Глянул в твои исходники, я бы сделал так:

1.framework/2.platform/3.device\arch

1. Тут лежат общие исходники для всего

2. Тут лежат исходники реализующие функционал под конкретную платформу (Linux, bare-metall, etc).

3. Ту лежат исходники для конкретных девайсов (Linux/Cubietruck не тоже, что Linux/RPi; stm8s105 не то же, что stm8l151).

shkolnick-kun ★★★★★ ()

http://www.freertos.org/RTOS_ports.html

Куда еще минимальнее? А также софт для тестирования потокобезопасности и прочего: http://www.freertos.org/FreeRTOS-Plus/FreeRTOS_Plus_Trace/FreeRTOS_Plus_Trace...

Извини, я твою RTOS ни за что не стану применять, меня ж повесят :)

Лучше вливайся в команду разработчиков FreeRTOS. Эта ОСРВ конечно не самая минимальная и на дохлых контроллерах не поедет (но она там и не нужна вовсе!), а на средних - годная.

I-Love-Microsoft ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

Явно не тебе, а автору темы :)

Просто мне доводилось применять FreeRTOS и на сайте electronix.ru вроде как хвалили. На AVR младших нет смысла использовать, а на ARMах как правило достаточно комфортно по части потребления памяти. С каждым годом она становилась всё лучше и известнее, и лицензия модифицированная GPL (можно не раскрывать код), не понимаю зачем эти другие ОСРВ? NIH?

P.S. Не являюсь разработчиком этой ОСРВ.

I-Love-Microsoft ★★★★★ ()
Ответ на: комментарий от I-Love-Microsoft

Тащемта, FreeRTOS очень хорошо пеарили, причем как в интернетах, так и в печатных изданиях. Она не то чтобы вылизана, она очень хорошо протестирована тысячами разрабов по всему миру. Чтобы отгрызть кусочек соответствующей ниши создателям той же чиби пришлось запиливать не просто голоя ядро, а ядро + куча плюшек, в т.ч. этот их HAL с дровами периферии.

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от KivApple

Я делаю это в первую очередь ради HAL с нормальной кросс-платформенностью. В том числе эта штука должна быть оберёткой для pthread, i2c-dev и т. п., если выбрать в качестве целевой платформы Linux.

Хм... может я погорячился, идея то интересная. Но смотри: https://en.wikipedia.org/wiki/ECos - была «and has compatibility layers and application programming interfaces for POSIX». Может у тебя другой подход.

Я даже не знаю что тебе сказать, смотри, работа с простейшими интерфейсами I2C/SPI и прочими не сильно поможет если они будет кроссплатформенной (приятно но не более того), у тебя будет поддержка ФС сложнее чем FAT32 - нет, а если речь идет о USB 3.0 или SATA и прочих интерфейсах - ты умрешь это реализовывать, или хотя бы Ethernet - и то не надо никаких абстракций, и без того хорошо на контроллерах.

Извини если убиваю твой энтузиазм, но для работы с I2C/SPI/дажеEthernet - приятно и без всяких ОСРВ. Хорошо, может ты сделаешь приятную кроссплатформенную обертку для USB-device для разных платформ? Например контроллеры со встроенным USB-device портом или таковые но с ОС Linux поверх? Не знаю...

I-Love-Microsoft ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

https://ru.wikipedia.org/wiki/ChibiOS/RT

А что, интересно: HAL-компонент поддержки различных абстрактных драйверов устройств: порт, последовательный порт, ADC, CAN, I2C, MAC, MMC, PWM, SPI, UART, USB, USB-CDC

P.S. Но всё равно Linux лучше всех (ну конечно, мы ж на ЛОРе) - пройдет лет 5 и то что Linux требует минимум 16 Мбайт ОЗУ всем будет просто пофиг - вообще процессоры будут выпускаться с интегрированной памятью DDR6 на 32 Мбайт... А для HRT и сейчас расширений хватает...

У ChibiOS мне категорически не нравится, как там проводится инициализация модулей HAL. Там нужно буквально указать значения основных регистров периферии (например, для I2C надо указать значение нескольких CRx). Да, потом с ней можно работать кросс-платформенными функциями, но инициализация достаточно неприятная процедура. И всё ради чего? Чтобы сэкономить несколько байтиков и микросекунд на инициализации (к инициализации вообще обычно не особо строгие временные требования)?

Но ведь это лучше исправить в самой этой ОС? GPL же.

I-Love-Microsoft ★★★★★ ()
Последнее исправление: I-Love-Microsoft (всего исправлений: 1)

Какие алгоритмы применяются в других RTOS?

лови

jtootf ★★★★★ ()
Ответ на: комментарий от alegz

Они все жручие.

Чтобы избежать этого, мне пришлось на 8-разрадных архитектурах делать отдельный стек для Ядра, как в ARM-ах.

Хочешь не жручую - бери http://www.contiki-os.org, работает на всем, начиная с Comodore64, ни строчки асма, но есть один нюанс: основана на протопотоках, которые по сути скрытые от глаз пользователя автоматы.

А вот коммерческая версия того же: http://www.thingsquare.com

Свежие версии, похоже, закопирастили, старые вот: https://github.com/errordeveloper/mist https://github.com/JelmerT/thingsquare-mist?files=1

shkolnick-kun ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

Спасибо за предложение, думаю так и реорганизую.

KivApple ★★★★★ ()
Ответ на: комментарий от shkolnick-kun

Хочешь не жручую - бери http://www.contiki-os.org, работает на всем, начиная с Comodore64

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

А ещё поддерживается, к сожалению, не всё: архитектуры с char 16 bit.

Свежие версии, похоже, закопирастили

Странно, они объявили, что открывают исходники, в сети встречается ещё инструкция загрузить thingsquare-mist-1.1.0.zip. А потом, значит, передумали.

Интересно, в чём отличия от contiki. Первое, что заметил, websockets.

gag ★★★★★ ()
Ответ на: комментарий от gag

Странно, они объявили, что открывают исходники, в сети встречается ещё инструкция загрузить thingsquare-mist-1.1.0.zip. А потом, значит, передумали.

Что поделаешь, пермиссив-лицензия...

shkolnick-kun ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.