Библиотека сайта rus-linux.net
ОС реального времени FreeRTOS
Глава 3 из книги "Архитектура приложений с открытым исходным кодом", том 2.
Оригинал: FreeRTOS
Автор: Christopher Svec
Перевод: Н.Ромоданов
3.6. Очереди
Система FreeRTOS позволяет задачам с помощью очередей общаться и синхронизироваться друг с другом. Процедуры сервиса прерываний (ISR) также используют очереди для взаимодействий и синхронизации.
Базовая структура данных очереди выглядит следующим образом:
typedef struct QueueDefinition
{
signed char *pcHead; /* Указывает на начало области хранения
очереди. */
signed char *pcTail; /* Указывает на байт в конце области хранения
очереди. Еще один байт требуется поскольку
хранятся отдельные элементы очереди;
он используется как маркер. */
signed char *pcWriteTo; /* Указывает на следующее свободное место в
в области хранения очереди. */
signed char *pcReadFrom; /* Указывает на последнюю позицию, откуда
происходило чтение очереди. */
xList xTasksWaitingToSend; /* Список задач, которые блокированы, ожидая
пока не произойдет обращение к этой очереди;
Запомнены в порядке приоритета. */
xList xTasksWaitingToReceive; /* Список задач, которые блокированы, ожидая
пока не произойдет чтение из этой очереди;
Запомнены в порядке приоритета. */
volatile unsigned portBASE_TYPE uxMessagesWaiting; /* Количество элементов, имеющихся
в очереди в текущий момент. */
unsigned portBASE_TYPE uxLength; /* Длина очереди, определяемая как
количество элементов, находящихся в
в очереди, а не как количество
байтов памяти, занимаемой очередью. */
unsigned portBASE_TYPE uxItemSize; /* Размер каждого элемента, который
хранится в очереди. */
} xQUEUE;
Это довольно стандартная очередь с указателями начала и конца, а также с указателями, позволяющими отслеживать, откуда мы только что выполнили чтение и куда мы только что сделали запись.
Когда создается очередь, пользователь указывает длину очереди и размер каждого элемента, который будет отслеживаться с помощью очереди. Указатели pcHead и pcTail используются для отслеживания того, как очередью используется внутренняя память. При добавлении элемента в очередь делается полная копия элемента во внутреннюю область хранения очереди.
Система FreeRTOS делает полную копию, а не хранит указатель на элемент, поскольку время жизни вставляемого элемента может быть намного короче, чем время жизни очереди. Рассмотрим, например, очередь из простых целых чисел, вставляемых и удаляемых с помощью локальных переменных в нескольких вызовах функций. Если в очереди хранятся указатели на целочисленные локальные переменные, то указатели станут недействительными как только целочисленные локальные переменные пропадут области видимости и память, используемая для локальных переменных, будет использована для некоторого нового значения.
Пользователь выбирает что следует помещать в очередь. Пользователь может помещать в очередь копии самих элементов, если элементы небольшие, например, как простые целые числа из предыдущего абзаца, либо пользователь может помещать в очередь указатели на элементы, если элементы большие. Обратите внимание, что в обоих случаях система FreeRTOS делает полную копию элементов: если пользователь выберет помещать в очередь копии элементов, то в очереди хранится полная копия каждого элемента, если пользователь выбирает помещать в очереди указатели, то в очереди хранится точная копия указателя. Конечно, если пользователь хранит в очереди указатели, то на него возлагается ответственность за управление памятью, связанной с указателями. Очереди безразлично, какие данные в ней хранятся, она просто должна знать размер каждого элемента данных.
В системе FreeRTOS поддерживаются вставки и удаления в очереди с блокировкой и без блокировки. Неблокирующие операции возвращают управление немедленно с указанием состояния «Вставлен элемент в очередь?» или «Удален элемент из очереди?». Блокирование указываются с тайм-аутом. Задача может ожидать снятие блокировки бесконечно или в течение ограниченного периода времени.
Заблокированная задача, назовем ее Задачей A, будет оставаться заблокированной до тех пор, пока не будет завершено выполнение операции вставки/удаления или пока не истечет (если оно установлено) время тайм-аута. Если прерывание или другая задача изменит очередь так, что может быть закончена операция для Задачи A, то Задача A будет разблокирована. Если операция в очереди, выполняемая для Задачи A можно выполнить в течение того, времени, пока задача выполняется, то Задача A завершит свою операцию с очередью и вернет значение состояния «success» (успешное завершение). Однако, в течение того времени, пока Задача A выполняется, может случиться так, что задача с более высоким приоритетом или прерывание выполнить еще одну операцию в очереди, которая помещает Задаче A выполнить свою операцию. В этом случае Задача A проверить значение тайм-аута и, если тайм-аут еще не истек, то продожит оставаться блокированной, либо вернет значение «failed» (не выполнено) в качестве состояния выполнения операции.
Важно отметить, что пока задача блокирована в очереди, остальная часть системы будет продолжать работать; другие задачи и прерывания будут продолжать выполняться. Таким образом, блокированная задача их не тратит ресурсы процессора, которые могут быть продуктивно использована другими задачами и прерываниями.
В системе FreeRTOS используется список xTasksWaitingToSend для отслеживания задач, которые блокированы при выполнении операции вставки элемента в очередь. Каждый раз, когда элемент удаляется из очереди, проверяется список xTasksWaitingToSend. Если задача находится в состянии ожидания в этом списке, то задача разблокируется.
Аналогично, с помощью списка xTasksWaitingToReceive отслеживаются задачи, которые блокируются при выполнении операции удаления из очереди. Каждый раз, когда новый элемент вставляется в очередь, проверяется список xTasksWaitingToReceive. Если задача находится в состоянии ожидания в этом списке, то задача разблокируется.
Семафоры и мютексы
Система FreeRTOS использует очереди для обмена данными между задачами и внутри задач. Система FreeRTOS также использует очереди для реализации семафоров и мютексов.
В чем разница?
Семафоры и мютексы могут рассматривать почти как одно и то же, но это не так. В системе FreeRTOS они реализуют аналогичным образом, но они предназначены для использования по-разному. Как они могут использоваться по-разному? Гуру встроенных систем Майкл Барр (Michael Barr) лучше всего это описывает в своей статье «Mutexes and Semaphores Demystified» («Демистификация мютексов и семафоров»):
Правильное использование семафора состоит в передаче сигнала от одной задачи в другую. Смысл мютексов в том, что каждая задача обращается к ним и отказывается от их использования в том порядке, в каком с их помощью устанавливается защита на совместно используемые ресурсы. В отличие от задач, в которых используются семафоры, может быть либо послан некоторый сигнал («send» или «отправить в терминах системы FreeRTOS), либо может происходить ожидание сигнала («receive» или «получить» в терминах системыFreeRTOS), но не оба варианта.
Мютекс используется для защиты общего ресурса. Задача включает мютекс, использует общий ресурс, а затем отключает мютекс. Никакая задача не может включить мютекс, пока мютекс включен другой задачей. Это гарантирует, что в каждый конкретный момент общим ресурсом может пользоваться только одна задача.
Семафоры, используемые некоторой задачей, посылают сигнал другой задаче. Процитирую статью Барра:
Например, в Задаче 1 может быть код, который, когда нажата кнопка «power» («Питание»), посылает сообщение (т.е. выдает сигнал или увеличивает на единицу некоторое значение) конкретному семафору, а Задача 2, которая включает дисплей, ожидает сигнала от того же самого семафора. В этом случае одна задача создает сигнал, а другая — его потребляет.
Если вам не все понятно с семафорами и мютексами, пожалуйста, ознакомьтесь со статьей Майкла.
Реализация
В системе FreeRTOS реализован N-элементный семафор в виде очереди, в которой может быть N элементов. В ней не хранятся какие-либо данные в виде элементов очереди; семафор просто следит за тем, сколько записей в текущий момент помещено в очередь, что осуществляется с помощью поля uxMessagesWaiting, имеющегося в очереди. Семафор реализует «чистую синхронизацию» так, как это названо в вызовах заголовочного файла semphr.h системы FreeRTOS. Поэтому размер элемента в очереди указан равным нулю байтов (uxItemSize == 0). Каждое обращение к семафору увеличивает или уменьшают на единицу значение поля uxMessagesWaiting; копирование элементов очереди или данных выполнять не требуется.
Точно также, как и семафоры, мютексы реализованы в виде очередей, но в них с помощью определений #defines перегружены несколько полей xQUEUE:
/* Перепределение полей структуры xQUEUE. */ #define uxQueueType pcHead #define pxMutexHolder pcTail
Поскольку мютекс не хранит никаких данных в очереди, ему не нужна внутренняя память, и, поэтому, не нужны поля pcHead и pcTail. Система FreeRTOS устанавливает поле uxQueueType (в действительности поле pcHead) равным 0, указывая, что эта очередь используется для мютекса. Система FreeRTOS использует перегрузку полей pcTail для реализации в мютексах механизма наследования приоритетов.
В случае, если вы не знакомы с наследованием приоритетов, я для того, чтобы определить его, еще раз процитирую Майкла Барра, на этот раз его статью «Introduction to Priority Inversion» («Введение в инверсии приоритетов):
[Наследование приоритетов] разрешает чтобы задача с низким приоритетом наследовала приоритет любой задачи более высокого приоритета, ожидающей ресурс, которым эти задачи пользуются совместно. Такое изменение приоритета должно происходить сразу, как только задача с большим приоритетом переходит в состояние ожидания; оно должно прекращаться сразу, как только ресурс будет освобожден.
Система FreeRTOS реализует наследование приоритетов с использованием поля pxMutexHolder (которое, на самом деле, является перегруженным полем #define pcTail). Система FreeRTOS записывает задачу, которая использует мютекс, в поле pxMutexHolder. Когда будет обнаружено, что задача с более высоким приоритетом также пользуется мютексом, установленным задачей с низким приоритетом, система FreeRTOS «обновит» приоритет задачи с более низким приоритетом до приоритета задачи с более высоким приоритетом и будет его поддерживать таким до тех пор, пока первая задача не освободит ресурс.
Продолжение статьи: Заключение и благодарности