Операционная система реального времени (ОСРВ)

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

Именно поэтому в Apollo Guidance Computer использовалась операционная система.

Не все задачи имеют строго детерминированное время выполнения. Задержка при получении пакетов из сети может плавать: она зависит от многих факторов, таких как состояние сети и ее топология. Если составить несколько подобных операций последовательно (линейная программа), девиация задержки может оказаться значительной, что не есть хорошо. Такая разница во времени выполнения называется джиттером (англ. jitter, дрожание).

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

Операционная система (англ. operating system) позволяет выполнять несколько подпрограмм одновременно, периодически переключаясь между контекстами и распределяя такие системные ресурсы, как память и вычислительные мощности. Здесь стоит оговориться: операционная система для встраиваемых систем отличается от систем на компьютере или телефоне, которые обычно называют операционными системами общего назначения (или ОСОН, англ. General Purpose Operating System, GPOS).

В отличие от настольного компьютера, во встраиваемых системах важно время реакции на событие (завершение передачи данных по некоторому интерфейсу, переполнение счетчика и т.д.), а не «честное» распределение ресурсов, которое обеспечивает «плавность» выполнения. Поэтому такие системы называют операционными системами реального времени (англ. real-time operating system).

На самом деле не всё так просто. В таких системах, как Windows 10 или Ubuntu, пользователь может менять приоритет программы, т.е. отдавать большее или меньшее предпочтение чему-то. Приведу пример: в университете я использовал программу, написанную на MATLAB, для моделирования распределения электромагнитных волн. Её выполнение на стационарном компьютере (с Core i7) занимало примерно 4 часа. После изменения приоритета программы на более высокий программа выполнялась за 3 (прирост в 25 %), но пользоваться графическим интерфейсом при этом становилось невозможно.

В ОСОН важно создать иллюзию у пользователя, что всё работает плавно, без рывков. То есть если при нажатии на клавишу клавиатуры символ в редакторе появится через 100 миллисекунд вместо должных 10, то ничего страшного в этом нет (хотя время реакции отличается в 10 раз), при условии, что видеоролик в браузере работает так же, как и до нажатия, без зависаний и пропадания звука. Можно ли доверить управлять чем-то критически важным такой системе? Нет! Если подушка безопасности начнет надуваться после того, как водитель ударится головой об руль, то… Разработчик должен обеспечить минимальную задержку между событием и реакцией на нее, поэтому «честное» распределение ресурсов здесь не подходит.

Все люди задачи равны, но некоторые равнее.

Еще раз отметим, чтобы не возникало ложных представлений о сущности «реального времени»:

Операционная система реального времени — это не про высокую производительность, а про гарантию времени отклика.

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

Подобных систем множество, и у каждой есть свои преимущества и недостатки. Тем не менее, все они устроены примерно одинаково. Мы рассмотрим, как создавать приложения на основе FreeRTOS — по данным UBS она занимает лидирующую позицию.

Рассмотрим типичную реализацию bare-metal прошивки еще раз.

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

• блок инициализации, где настраивается периферия, тактирование и т.д.;
• блок с главным циклом, действия в котором являются реакцией на происходящие прерывания (нажатие кнопки, получение данных по UART и т.д.), обычно в виде машины состояний;
• и блок прерываний (англ. interrupt service routine, ISR).

Минимальная реализация ОСРВ состоит из тех же частей, однако называются они по-другому и выполняют другие функции. Главный цикл заменяется на «задачу» с низшим приоритетом, и вместе с блоком прерываний он образует ядро (англ. kernel). Помимо них, к программе добавляются и другие задачи, в которых задается логика работы устройства.

Задачи

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

• Выполняющаяся (англ. running). В Cortex-M3 имеется только одно ядро, соответственно, в данном состоянии в один момент времени может находиться только один поток.
• Не выполняющиеся (англ. not running). Во FreeRTOS все выполняющиеся задачи имеют три подсостояния.
  • Готовая к выполнению (англ. ready). Задачи в данном состоянии ждут своей очереди на выполнение, т.е. они не заблокированы и не подвешены.
  • Заблокированная (англ. blocked). Задача, находящаяся в заблокированном состоянии, ожидает либо временного (истечение заданной задержки), либо внешнего события (например, нажатие кнопки). Если две задачи хотят работать с одним блоком памяти (или периферией), то, очевидно, пока одна задача не завершит работу, другая не должна вмешиваться и производить какие-либо действия. Пока работает первая, вторая будет заблокирована. Задаче можно задавать максимальное время нахождения в заблокированном состоянии, называемое тайм-аутом (англ. time-out), по истечении которого она будет разблокирована.
  • Подвешенный (англ. suspended). Данное состояние похоже на заблокированное, с тем отличием, что временного ограничения у нее нет, вход и выход из этого состояния осуществляются вызовом соответствующих функций.

Граф переходов и состояний можно изобразить следующим образом:

Ядро ОС по некоторому внутреннему правилу дает выполняться одной из задач в один момент времени. Таким образом, система становится многозадачной (англ. multitasking) и уже чем-то напоминает модель работы Windows-стиля исполнения программ (это не официальная терминология): передавая управление от одной задачи к другой достаточно быстро, можно создать иллюзию одновременного выполнения. Однако переключать задачи слишком часто не стоит, так как это приводит к потере производительности: процессорное время приходится тратить на определение того, кому передать управление, и переключение контекстов выполнения. Картинка ниже иллюстрирует процесс работы трех задач во времени.

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

Приоритет задачи

Каждой задаче присваивается приоритет — целое число, принадлежащее множеству [0;N]. Чем выше приоритет (0 — наивысший приоритет), тем важнее участок кода, т. е. его следует выполнить в первую очередь. Из всех задач, находящихся в режиме ожидания, формируется список, который сортируется по приоритету. Далее задачи из этого списка выполняются одна за другой. Количество приоритетов, как правило, настраиваемая величина, определяемая на этапе компиляции.

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

Создавать задачи с более высоким приоритетом с чистым вечным циклом нельзя. Проблема в том, что если сама задача не отдаст управление операционной системе (через специальные функции), то все задачи с более низким приоритетом никогда не смогут быть выполнены, так как задача с вечным циклом будет постоянно переходить из режима выполнения в режим ожидания и обратно. Все задачи следует писать таким образом, чтобы они являлись реакцией на событие (англ. event-driven).

Как выбирать приоритеты?

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

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

Оптимальным называется тот алгоритм, который при любом сочетании параметров задач гарантирует составление выполняемого расписания (т.е. все задачи успевают выполниться до их крайнего срока выполнения). Оптимальность была доказана в 1973 году, см. статью Liu, C.L.; Layland, J. (1973), «Scheduling algorithms for multiprogramming in a hard real-time environment», Journal of the ACM, 20 (1): 46—61, doi:10.1145/321738.321743.

Допустим, имеется две периодических задачи, task_01 и task_02, крайний срок выполнения (англ. deadline) которых равен их периоду. Период первой задачи составляет 50 мс (T₁), а максимальное (худшее) время выполнения 25 мс (C₁). Период второй задачи — 100 мс (T₂), худшее время выполнения — 40 мс (C₂). Могут ли эти две задачи успеть выполниться одновременно? Для ответа на этот вопрос вводят понятие утилизации (англ. utilization).

U = (C / T) · 100 %

Для первой задачи U₁ равно 50% процессорного времени, а для второй, U₂, 40%. Просуммировав, получим 90%, т.е. остается еще 10% свободного времени. Если приоритеты уникальны — а алгоритм, который мы рассматриваем, требует этого, — то возможны две ситуации:

• P(T₁) > P(T₂) — приоритет первой задачи выше, чем второй;
• P(T₁) < P(T₂) — приоритет второй задачи выше, чем первой.

Если запустить обе задачи, можно будет наблюдать следующую картину:

В первом случае обе задачи успевают отработать, а во втором нет, несмотря на то, что остается 10% свободного времени. Выбор приоритета влияет на результат. Алгоритм, по которому задачам с меньшим периодом назначают более высокий приоритет, называется Rate Monotonic, или RMA. Однако он имеет очень серьезное ограничение — он не гарантирует, что все задачи успеют выполниться, если утилизация времени выше, чем U_n.

U_n = n · sqrt[n]{2} — 1) · 100 %

Для нашего случая U_n (2) составляет 82,84%, т.е. причина, по которой все задачи успели выполниться, — обыкновенная удача. При большом количестве задач данный порог стремится к 69,3%. Давайте немного изменим условия, сохранив всё то же требование в 90% времени процессора, чтобы убедиться в утверждении выше. Параметры первой задачи оставим без изменений, а вот период второй понизим до 70 мс, а худшее время выполнения поднимем до 30 мс.

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

Прилунение «Аполлона-11» не было гладким: во время спуска на лунную поверхность бортовой компьютер AGC выдал неизвестную экипажу ошибку «1202». К счастью, Стив Бэйлс (Steve Bales), сотрудник ЦУПа, знал о природе данной проблемы, и посадку удалось завершить успешно, не прерывая миссию. Расследование показало: а) нормальная загрузка процессора во время спуска — 85%; б) расчёт разности между реальной и расчётной высотой модуля утилизировал ещё 10% времени процессора (соответствующую команду ввёл Базз Олдрин, после чего и появилась ошибка); в) дополнительные 13% расходовались из-за ошибки в проектировании железа. Компьютер и радар работали от разных источников (800 Гц), которые не были синхронизированы по фазе. Небольшое смещение фазы выглядело для компьютера как колебание в реальности неподвижной антенны, которое приходилось обрабатывать. Ошибка «1202» сигнализировала о перегрузке процессора: он не успевал обрабатывать все необходимые операции в реальном времени. Проблема была обнаружена и задокументирована ещё при работе с аппаратом «Аполлон-5», но изменения в железо решили не вносить, так как ошибка появилась только однажды, а замена оборудования на новое (исправленное) могло привести к более серьёзным проблемам. // https://www.hq.nasa.gov/alsj/a11/a11.1201-pa.html

Планировщик

Сущность, отвечающая за переключение задач, называется диспетчером, или планировщиком (англ. scheduler), и входит в состав ядра операционной системы. Алгоритмов планировщика существует довольно много. FreeRTOS поддерживает три: вытесняющий (англ. pre-emptive) с квантованием времени (англ. time slicing) и без, а также кооперативный (англ. co-operative). Рассмотрим их далее.

Вытесняющий алгоритм с квантованием времени

Название алгоритма говорит само за себя: как только появляется задача с более высоким приоритетом, операционная система переключается на нее, т.е. «вытесняет» менее приоритетную задачу. Для задач с одинаковым приоритетом системные ресурсы распределяются при помощи квантования времени.

Квант равен времени между двумя прерываниями системного таймера операционной системы. Обычно это число выбирается равным 1 миллисекунде.

Возьмем три задачи с разным приоритетом: idle, task_01 и task_02. Задача idle имеет наименьший приоритет, поэтому ее выполнение происходит только в то время, когда никакой другой задаче не нужны системные ресурсы. Задача task_02 имеет средний приоритет (выше, чем у idle) и большую часть времени находится в заблокированном состоянии (в ожидании некоторого события). task_01 аналогична task_02, но имеет более высокий приоритет. Как только происходит событие, вызывающее task_02, планировщик переключается на нее. Если в момент выполнения task_02 срабатывает событие, вызывающее task_01, то task_02 приостанавливается и переходит в режим ожидания, в то время как task_01 переходит в режим выполнения. Графически всё это можно представить следующим образом:

А что если задачам idle и taks_02 назначить одинаковые приоритеты? Планировщик будет переключаться между этими задачами по очереди. Допустим, в момент исполнения idle происходит событие, вызывающее task_01, и оно, выполнив свою работу, до наступления прерывания от системного таймера передает управление планировщику. Тот, для того чтобы равномерно распорядиться системными ресурсами, не даст продолжить работу idle, а переключится на task_02.

Т.е. проблемы «нечестного» распределения времени нет.

Вытесняющий алгоритм без квантования времени

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

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

Кооперативный алгоритм

В описанных выше алгоритмах принятие решения о запуске задачи полностью лежало на планировщике. Другой подход, называемый кооперативным (англ. co-operative), заключается в добровольной передаче управления. Т.е. пока выполняемая задача сама себя не заблокирует или не подвесит, никакая другая задача выполняться не сможет. Другими словами, переключение происходит только с позволения (англ. yield) текущей задачи.

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

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

Переключение контекста выполнения

Когда задача выполняется, она использует регистры ядра и периферии и доступ к памяти. Все эти ресурсы называют контекстом выполнения (англ. context). При переключении с одной задачи на другую контекст выполнения меняется. Задача — это фрагмент кода, который понятия не имеет, когда его могут прервать (англ. swapped out / switch out) или возобновить (англ. swapped in / switch in / resume).

Предположим, что переключение задачи произошло, когда она выполняла операцию сложения.

sum = a + b;

Регистры ядра были заняты значениями переменных a и b, а в конвейер была подгружена инструкция ADD. Очевидно, что другая задача тоже будет использовать и конвейер, и регистры. Когда работа первой задачи возобновится, она не будет знать о том, что состояние регистров изменилось, а значит, результат сложения (если это всё еще будет сложение) окажется неверным.

Для предотвращения таких ситуаций ядро операционной системы сохраняет необходимые данные, а при возобновлении работы задачи подгружает их снова. Данный процесс называется переключением контекста (англ. context switching).

Архитектура ARM Cortex-M3 имеет специальные возможности для работы планировщика с вытеснением. Когда мы разбирались с его архитектурой, то упомянули, что ядро может работать в двух режимах: режиме «потока» (пользовательском) и «привилегированном» (это системный режим для операционной системы и прерываний). В первом случае используется PSP-стек, а во втором MSP. По истечении временного периода срабатывает системный тик (обычно заведенный через системный таймер SysTick) и вызывается обработчик прерывания (SysTick_Handler()). Далее, при условии что других более важных прерываний нет, запускается PendSV_Handler(), отвечающий за смену контекста. При входе в это прерывание ядро (процессора) автоматически помещает регистры R0—R3, R12, LR, PC, PSR в пользовательский стек PSP и записывает адрес возврата в R14 (LR). Это происходит аппаратно. Остальные регистры сохраняются программно. Затем содержимое стека сохраняется в памяти, и загружается стек следующей задачи.

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

Взаимодействие потоков

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

Любая ОСРВ предоставляет стандартные механизмы взаимодействия, такие как семафоры (англ. semaphore), мьютексы (англ. mutex), очередь сообщений (англ. message queues). Если разграничить очередь и семафор с мьютексом не вызывает проблем, то разделить понятия семафора и мьютекса (который является частным случаем семафора) получается не у всех сразу. Очень упрощенно говоря: очереди — это про защиту памяти, они позволяют организовать безопасную передачу данных; семафоры — это про упорядочивание какого-то распределенного процесса, его синхронизацию; а мьютексы — это про защиту аппаратных ресурсов, т.е. для обеспечения эксклюзивного доступа к ним. Рассмотрим их подробнее.

Очередь сообщений

Реализовать сложное устройство с применением ОСРВ и избежать необходимости передавать данные из одного потока в другой невозможно. Использовать глобальные переменные, как это было в bare-metal прошивке, — плохая идея. Все задачи асинхронные, но не все задачи атомарные (выполняющиеся за один такт, англ. atomic). Банальный пример: разрядность шины в Cortex-M3 32 бита, но переменная может занимать два слова (64 бита), т. е. ее чтение и запись не происходит за один такт; что будет, если во время записи 64-битной переменной планировщик решит передать управление другой задаче, которая также использует эту переменную? Результат выполнения будет непредсказуем, так как в переменной окажется не то, что должно было быть.

Или другой пример, более распространенный при написании программ. Если нашему устройству необходимо обрабатывать данные (команды), приходящие через какой-нибудь интерфейс (UART, SPI), то прием в любом случае будет происходить по одному символу. Типовое (ошибочное) решение будет выглядеть примерно следующим образом:

Не обязательно. В некоторых микроконтроллерах, например LPC, на вход может быть повешен аппаратный FIFO-буфер на 8 или 16 байт, соответственно, считывать можно сразу несколько символов.

void USRART1_IRQHandler () {
    ch = USART1_Read();
    if(ch != '\n') {
        buffer[index++] = ch;
    } else {
        processing();
        index = 0;
    }
}

Здесь нарушено первое правило работы с прерыванием — оно должно отрабатывать как можно быстрее. Если processing() будет работать слишком долго, то может прийти следующий байт информации, входной регистр порта просто перезапишется, и мы потеряем символ. Решая эту проблему, логично ввести флаг (в окружении ОСРВ лучше использовать семафор, но о нем чуть позже), который будет сигнализировать задаче, что пора обрабатывать данные в буфере. Но появляется другая проблема: когда буфер заполнится, мы снова начнем терять символы. Переписав обычный линейный буфер на круговой (его описание есть в соответствующей главе), мы начнем затирать необработанные данные. Вот бы как-нибудь сохранять целые строчки (команды) в отдельный массив, и уже потом не спеша его обрабатывать в отдельной задаче…

В ОСРВ широко применяется механизм под названием «очередь» (англ. queue) для разрешения проблемы передачи данных. Очередь создается и удаляется разработчиком при необходимости.

По сути очередь — это массив однотипных (одноразмерных) данных с особым способом записи и чтения из него, называемым FIFO (от англ. First In, First Out) — первый пришел, первый ушел. Размер очереди называется длиной (англ. length), запись осуществляется в конец, он же «хвост» (англ. tail), а чтение из начала, оно же «голова» (англ. head).

В FreeRTOS существует возможность записывать в начало очереди, но мы не будем рассматривать данную ситуацию.

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

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

Задача task_02 записала данные в очередь.

Далее task_03 отправила туда свои данные. Переданное число записалось сразу за значением от задачи task_02.

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

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

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

Критические секции

В машине состояний используется глобальная переменная для контроля режима работы программы. Очевидно, глобальные переменные могут быть использованы и в других целях, например, для хранения значения некоторого счетчика. Если такая переменная будет использоваться в нескольких задачах, то появление ошибки более чем вероятно, ведь корректность работы будет зависеть от последовательности выполнения частей кода. Такая ситуация называется состоянием гонки (англ. race condition). Рассмотрим простой пример.

Так как появление ошибки случайно, её называют «гейзенбагом» (англ. heisenbug), от имени немецкого физика-теоретика Вернера Карла Гейзенберга, сформулировавшего принцип неопределённости.

volatile int x;
// task 1
while (!stop) {
    x++;
    // ...
}
// task 2:
while (!stop) {
if (x%2 == 0)
    show_number(x);
    // ...
}

Допустим, в некоторый момент времени значение переменной x равно 0. Тогда в задаче task_02 оператор if убедится в том, что значение четное, и перейдет к выводу числа на дисплей. В это же время выполнится другая задача, task_01, которая изменит значение x на единицу. В итоге на дисплей вместо 0 выведется 1, что является неправильным поведением.

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

В аппарате лучевой терапии Therac-25 механизмы защиты были реализованы программным путём, в отличие от предыдущих версий. Такое решение и ошибка в ПО привели к облучению как минимум шести пациентов дозой в десятки тысяч рад (смертельная доза около 1000 рад). Минимум два пациента умерли по причине передозировки. Как установило расследование, одна и та же переменная применялась как для анализа вводимых оператором чисел, так и для определения положения поворотного круга, отвечающего за режим работы. Настройка одной из частей аппарата (отклоняющегося магнита) занимала около 8 секунд, и если некоторые параметры менялись, а курсор диска был установлен в финальную позицию, то система не обнаруживала изменений. Therac-25 работал под управлением собственной ОСРВ, всё программное обеспечение было написано на языке ассемблера (20 тысяч строк). Поиск и анализ ошибки занял около 3 лет. // Medical Devices: The Therac-25, http://sunnyday.mit.edu/papers/therac.pdf

Функция, которую можно безопасно вызвать из любой задачи или в прерывании, называется реентерабельной (англ. reentrant), т.е. она работает исключительно с собственными данными, выделенными на стеке, и не пытается получить доступ к другим данным в системе. Однако, как можно догадаться, не все функции являются такими: часть кода ни в коем случае нельзя прерывать. Такой участок называют критической секцией (англ. critical section), или критическим регионом (англ. critical region). Конкретно в FreeRTOS существует два способа создания критической секции: а) приостановить работу планировщика на время прохождения данного фрагмента кода; б) временно запретить смену контекста. Пример такого фрагмента мы рассмотрим чуть позже, в главе про FreeRTOS.

Семафоры и мьютексы

Рассуждая об очереди, мы упомянули такую сущность, как семафор, и сравнили его с флагом (глобальной переменной)^semaphore. Концепция бинарного семафора (англ. binary semaphore) была предложена в 1965 году голландским инженером Эдсгером Вибе Дейкстром. Идея довольно проста: для оповещения операционной системы о выполнении критического участка кода используются две функции, условно, enter() и leave().

Семафор — это не просто глобальная переменная! Пользователь Хабрахабр под ником kiltum в статье «STM32 и FreeRTOS. 2. Семафорим по-черному» исчерпывающе показал преимущество использования семафоров в многопоточном приложении на примере заказа еды в McDonalds.

Могут называться по-другому, post / signal или p / v.

enter(); {
    // critical section here
} leave();

По сути, функции инкапсулируют в себе работу с некоторой переменной, флагом, который может принимать одно из двух состояний: условно, 0 или 1. Взяв семафор, функция enter() выставляет флаг равным 0. Другая задача, проверив это значение, понимает, что выполнять последующий код нельзя, пока семафор не будет возвращен. После вызова функции leave() значение флага восстанавливается (теперь он равен 1), т. е. семафор выдается обратно. Здесь нужно обратить внимание: выдать семафор может не та задача, которая его забрала.

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

На конвейерной линии установлены три руки-манипулятора. В любой момент времени могут работать, не мешая друг другу, только две из них. (Если менять руки время от времени, продлевается срок службы). Их задача — раскладывать приезжающие по ленте продукты в упаковки. Они могут приезжать по одному, могут сразу кучей, а могут не приезжать совсем. Программист создал три задачи под каждую руку: arm1(), arm2(), arm3(). По конвейеру поступил один продукт, внутреннее состояние семафора говорит, что ни одна из рук не используется, т.е. счетчик хранит число 2. Задача arm1() забирает семафор (счетчик равен 1) и начинает упаковывать продукт в коробку. В это время подъезжает еще два продукта. Задача arm2() забирает семафор (счетчик равен 0). Задача arm3() пробует получить семафор, но счетчик равен нулю, поэтому она уходит в блокированный режим. Задача arm1() заканчивает упаковку и отдает семафор. В это время происходит вытеснение этой задачи, и arm3() снова пытается получить семафор, на этот раз успешно, — таким образом arm1() перестает работать, ожидая новой продукции и семафора.

Бинарные семафоры хорошо подходят для синхронизации действий. Например, один поток (или прерывание) создает некоторое событие, а вторая задача его обрабатывает. В таком случае задача-обработчик, выставив семафор в 1, отправляет себя в заблокированное состояние и ожидает, пока произойдет событие, т.е. первая задача (прерывание) выдаст семафор. Когда управление будет передано задаче-обработчику, она захватит семафор, обработает данные и снова уйдет в заблокированное состояние, ожидая появления новых данных.

Такое поведение чем-то похоже на очередь, которую мы рассмотрели ранее.

Еще одна разновидность семафора — это мьютекс (англ. mutual exclusion lock, взаимное исключение). Он служит для синхронизации одновременно выполняющихся задач и отличается тем, что только владеющий им поток может его освободить.

Семафорами можно заменить мьютексы, но не наоборот.

Чтобы провести аналогию, представьте дверь с навесным замком (некоторый аппаратный ресурс).

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

Возьмем, к примеру, шину CAN, которая является полудуплексом (англ. half-duplex), т.е. может находится либо в состоянии приема, либо в состоянии отправки. Если две задачи захотят работать с данным интерфейсом, то по закону Мёрфи непременно сложится ситуация, когда одна задача, передав данные, переведет шину в режим чтения и уйдет в заблокированное состояние, ожидая ответа, а вторая в это время, получив управление, переведет линию в состояние передачи и начнет что-то отправлять. Первая задача не дождется ответа, так как вторая просто испортит принимаемые данные, при этом так и не отправив команду удаленному узлу. В такой ситуации мьютекс — это серебряная пуля: если пометить шину CAN как «используемую», никакая другая задача не сможет с ней работать. Все задачи просто уйдут в режим блокировки, пока мьютекс не будет освобожден.

Шутливый философский принцип — «всё, что может пойти не так, пойдёт не так». История термина хорошо описана в подкасте «Эффект Стаховского» (радио Маяк), http://radiomayak.ru/podcasts/podcast/id/1381/.

В точке (1) задача idle вытесняется задачей task_02, после чего та захватывает мьютекс и начинает работать с общим ресурсом — CAN-шиной. Отправка сообщения заняла много времени, и произошел системный тик в точке (2). Более приоритетная задача, task_01, попыталась захватить мьютекс, но у нее это не получилось, так как мьютекс был захвачен task_02. task_01 уходит в блокированный режим (3), и планировщик возобновляет работу задачи task02. Задача отдает мьютекс сразу же по окончании работы с шиной, однако после этого должна обработать полученный ответ. В это время подходит конец очередного кванта времени, и планировщик отдает управление задаче task_01 (4), которая на этот раз успешно захватывает мьютекс и работает с шиной. Задача task_01 уложилась в квант времени, поэтому отдает мьютекс и завершается до переключения контекста (5). Управление снова получает задача task_02 и заканчивает обработку ответа, полученного от удаленного узла.

Выглядит здорово, но мьютекс имеет недостатки.

Диаграмма выше демонстрирует потенциальную «ловушку», в которую можно попасть — инверсию приоритетов (англ. priority inversion). Допустим, мы имеем три задачи с разным приоритетом (по возрастанию): task03 (low), task_02 (normal) и task_01 (nigh). Задача task_03 захватывает мьютекс и очень долго работает с ресурсом. Планировщик вытесняет задачу и передает управление task_01 (1), которая также желает получить доступ к нему, однако, так как мьютекс захвачен, ей приходится ждать, управление передаётся задаче task_03 (2). Далее «просыпаются» и другие задачи, имеющие более высокий приоритет, чем task_03, — в нашем случае task_02 (3). Не смотря на то, что task_01 имеет наивысший приоритет, ей придётся ждать пока отработает сначала task_02, а затем и task_03, пока последняя не вернёт мьютекс.

В 1997 году NASA запустило марсианский аппарат «Марсоход» (англ. Mars Pathfinder). В предполётном тестировании обнаружилась ошибка с инверсией приоритетов, однако её пометили как не критическую ввиду того, что её было сложно воспроизвести. Усилия были потрачены на отладку функций посадки. По закону Мёрфи что-то пошло не так — проблему пришлось решать, когда аппарат находился на Марсе. Ошибка, а также то, как её устранили, подробно описана в статье «Mars Pathfinder: Priority Inversion Problem», Risat Mahmud Pathan.

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

Другая более серьезная ловушка, в которую можно угодить, называется взаимной блокировкой (англ. deadlock) задач. Допустим, двум задачам для корректной работы необходим доступ к двум ресурсам. Опять же по закону Мёрфи один из ресурсов может быть захвачен во время захвата. В таком случае обе задачи уйдут в заблокированное состояние и начнут ждать, пока кто-то из них отпустит мьютекс, чего явно никогда не произойдет. Предотвращение таких ситуаций — задача программиста.

Приведем условный пример. Имеется некоторое устройство с COM-портом (UART) и светодиодом. Согласно техническому заданию, во время передачи данных через порт светодиод должен гореть. Источников данных в устройстве два — задачи. Так как и светодиод и UART-порт являются ограниченными ресурсами, программист решил использовать мьютексы и написал примерно следующий код (псевдокод):

void task_01() {
    mutax_take(&mLED);
    mutax_take(&mUART);
    processing_1();
    mutax_leave(&mUART);
    mutax_leave(&mLED);
}
// ...
void task_02() {
    mutax_take(&mUART);
    mutax_take(&mLED);
    processing_2();
    mutax_leave(&mLED);
    mutax_leave(&mUART);
}

Как только задача task_01 захватит мьютекс светодиода, может произойти прерывание от планировщика, и задача task_02 перехватит управление, захватив мьютекс UART-порта. Обнаружив, что светодиод кем-то используется, задача передаст управление планировщику, который возобновит работу task_01. Последняя, попробовав захватить мьютекс порта, обнаружит, что он занят, и опять отдаст управление планировщику. В итоге никто не сможет отправить свои данные. Для избежания обеих проблем часто прибегают к созданию отдельной задачи, привратника (англ. gatekeeper), через которую осуществляется доступ к ресурсам. Все задачи, желающие работать с ресурсами, должны отправлять данные в очередь, которую обрабатывает привратник.

Прерывания

Основное правило работы с прерываниями в ОСРВ такое же, как и в bare-metal прошивках, — код должен быть настолько короток (быстр), насколько это возможно. В противном случае задержка, вносимая прерыванием, может сказаться на отклике системы. Для решения этой проблемы применяют «отложенную» (англ. deferred) обработку прерывания. Такой подход подразумевает, что обработчик прерывания совершит только первичную обработку данных, например, считает их из регистра в переменную и передаст управление операционной системе. Последняя, в свою очередь, в зависимости от приоритетов в списке ожидания может либо сразу, либо через какое-то время передать управление специальной задаче-обработчику. Если требуется быстрая реакция, то всё, что нужно сделать программисту, — это назначить высокий приоритет. В таком случае, при прочих равных, задача-обработчик начнет выполняться сразу же после обработчика прерывания.

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