Рейтинг@Mail.ru
[Войти] [Зарегистрироваться]

Наши друзья и партнеры

UnixForum
Беспроводные выключатели nooLite купить дешевый 
компьютер родом из Dhgate.com

Lines Club

Ищем достойных соперников.

Библиотека сайта или "Мой Linux Documentation Project"

ОС реального времени 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 «обновит» приоритет задачи с более низким приоритетом до приоритета задачи с более высоким приоритетом и будет его поддерживать таким до тех пор, пока первая задача не освободит ресурс.


Продолжение статьи: Заключение и благодарности


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

Комментарии отсутствуют