Микроконтроллеры

Очевидно, что без механизма ожидания -- получается полная ерунда, которая ничем не лучше биглупа. Когда событий станет много (типов событий, происходить им не обязательно) -- всё время только и будет уходить на такие циклы проверки, как и в биглупе. Зачем тогда сущность с громким названием "операционка"? 

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

С простыми примитивами синхронизации, вроде мьютекса или семафора -- всё просто. Они могут быть выполнены по большей части в юзерспейсе и от ядра нужна поддержка примитива наподобии futex из linux. На самом деле это просто ячейка памяти, адрес (что в ней записано и записано ли -- вообще не важно). И задача может ожидать события связанного с каким-либо адресом. А другая задача может пробудить остальные задачи ожидающие на каком-либо адресе. Фактически у самих задач значит нужно специальное состояние "ожидания" и этот самый адрес. И когда происходит побудка для какого-либо адреса, ядро перебирает список задач и если адрес соответствует -- будит. Тут можно оптимизировать уже для случая, когда задач много (например положить задачи в хеш-таблицу, где хеш соответствует адресу), но это уже отдельная история. А сами мьютексы и семафоры могут строиться на атомарных инструкциях и в случае необходимости сигнализации другим процессам -- звать ядро для побудки других процессов.

Сложно со случаем, когда задача ожидает одновременно множество событий. Для маленьких множеств, понятно, можно по описанной выше схеме ожидать несколько событий. Но для решения задач вроде C10K (https://en.wikipedia.org/wiki/C10k_problem) такой подход не реален. Потому во многих RTOS и нет такого механизма. Event flags очевидно относятся к простому случаю...

Можно сказать, мол, у нас маленький микроконтроллер и о чём я говорю (10 тыс. событий) -- не нужно. Казалось бы хватит десятка задач. Нет, это не так на самом деле... Или возникает вопрос, зачем операционка нужна. Десяток задач можно запустить из биглупа. Неудобно, но можно. Из биг лупа уже невозможно запустить сотню задач -- он съест, как описывалось выше, время на проверке условий больше, чем занимают задачи. Операционка нужна для сильного параллелизма, когда число параллельных пользовательских задач достаточно велико (не процессов уровня ОС, их может быть меньше, если некоторые задачи обслуживаются одним потоком -- например в отдельных потоках реализован цикл обработки событий множественных задач).

Кроме того, второй важный момент -- потребление энергии. Цикл с биглупом сложно заставить спать, когда задачам нечего делать и они ждут истечения временных интервалов или внешний событий (то и другое, фактически, прерывание в процессоре). Можно, я описывал как (http://caxapa.ru/1035321). Но при разрастании системы биглуп практически уже не спит и только проверяет флаги, условия.

Когда в операционке заводится небольшое число потоков и в них устраивается тот же биглуп (чтоб обслужить куда большее число задач не имеющих собственного потока) -- остаются те же проблемы, что и с биглупом. Ещё и приумноженные на необходимость синхронизации потоков.

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

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

Такой механизм может быть построен скорей на базе очереди с приоритетамиочереди с приоритетамиПрактическая реализация скорей будет видаbucket queue т.к. реализация на базе кучи слишком громоздка. События по факту возникновения должны попадать в очередь (повторно возникшие события, до их обработки, повторно в очередь не помещаются). Из головы очереди постоянно выбирается самое приоритетное событие и обрабатывается... Собственно такой событийный механизм скорей и должен быть "ядром ядра" ОС, а отнюдь не планировщик, планировщик может быть лишь обработчиком событий. И событийный механизм позволяет реализовать ожидание на мьютексах, семафорах и прочие механизмы синхронизации. Включая условную переменную и fifo-очереди.

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

И нужно сказать о thread local storage (TLS) -- переменных специфичных для потока. Для реализации некоторых (многих) алгоритмов нужно в каждом потоке иметь свою переменную, со значением отличным в разных потоках. Обычно это реализуется так, что с каждым потоком связан как минимум один указатель (в каждом потоке свой) который указывает на специфичную для потока область памяти. Вопрос в том, как этот указатель получить в произвольной функции. Понятно, что это всегда можно сделать вызовом функции ОС которая получит номер потока и из него потом вычислить как-то указатель... но это одновременно и не решение: потому и нужны локальные для потока переменные, что подразумевается, что они доступны быстро, со скоростью выполнения команд процессора, а не через системный вызов который может занять тысячи тактов. Многие современные процессоры предоставляют специальные регистры и специальные команды для считывания указателя на блок локальных для потока переменных. Если у процессора много регистров, то какой-то один может быть зарезервирован компилятором для этой задачи (и обновляться планировщиком). И наконец, универсальное решение: текущий поток и указатель на блок переменных может быть вычислен на основе регистра указателя стека (который у каждого потока разный). Но для последнего нужно иметь доступ к списку адресов стеков задач, если размеры стеков переменные -- нужны блокировки, всё обрастает сложностями. Поэтому вариант с выделенным регистром не так уж и плох.

Кроме того, возможно следует поступить как в linux и функции ОС разделить на два класса: "медленные", вызываемые через "тяжёлый" системный вызов и предусматривающие блокировку или переключение задач... И "быстрые", с кодом исполняющимся всё ещё в юзерспейсе. Фактически -- библиотека подгружаемая в пространство задачи пользователя (vdso). Части функций, вроде получения времени, получения номера текущего потока/процесса, получения указателя на блок TLS... не нужно заходить в ядро. Им достаточно лишь в пространстве пользователя выполнить код читающий переменные ядра, которые обновляются в прерываниях или планировщиком при переключении задач.