Библиотека сайта rus-linux.net
ОС реального времени FreeRTOS
Глава 3 из книги "Архитектура приложений с открытым исходным кодом", том 2.
Оригинал: FreeRTOS
Автор: Christopher Svec
Перевод: Н.Ромоданов
3.5. Списки
После задач, следующими наиболее часто используемыми в системе FreeRTOS являются списки. Система FreeRTOS использует структуру списков для отслеживания состояния задач при планирования, а также для реализации очередей.
Рис.3.3: Полная схема списка готовности задач Ready List в системе FreeRTOS
Список в системе FreeRTOS является стандартным закольцованным двусвязным списком с парой интересных дополнений. Элементы списка следующие:
struct xLIST_ITEM
{
portTickType xItemValue; /* Значение, помещаемое в список. В большинстве
случае используется для сортировки
списка в порядке уменьшения значений */
volatile struct xLIST_ITEM * pxNext; /* Указатель на следующий элемент xListItem
в списке. */
volatile struct xLIST_ITEM * pxPrevious; /* Указатель на предыдущий элемент xListItem
в списке. */
void * pvOwner; /* Указатель на объект (обычно блок TCB),
в котором находится элемент списка. Таким
образом, организуется двусвязный список
между объектами, хранящимися в списке, и
элементами самого списка. */
void * pvContainer; /* Указатель на список (если таковой имеется),
в который этот элемент списка помещается. */
};
В каждом элементе хранится номер, xItemValue, которое обычно является приоритетом задачи, который отслеживается, или значением таймера для планирования событий. Списки хранятся в порядке убывания приоритета, а это означает, что наивысший приоритет xItemValue (наибольшее число) находится в начале списка и самый низкий приоритет xItemValue (наименьшее число) находится в конце списка.
Указатели pxNext и pxPrevious являются стандартными указателями, связывающие элементы списке. Указатель pvOwner является указателем на владельца элемента списка. Обычно это указатель на блок TCB задачи. Указатель pvOwner используется для быстрого переключения задач в vTaskSwitchContext(): как только в pxReadyTasksLists[] будет найден элемент списка с наивысшим приоритетом, указатель pvOwner элемента списка позволит нам непосредственно перейти к блоку TCB, который нужен при планировании запусков задачи.
Указатель pvContainer указывает на список, в котором находится этот элемент. Он используется для быстрого определения, принадлежит ли элемент некоторому списку. Каждый элемент списка может быть помещен в список, что осуществляется следующим образом:
typedef struct xLIST
{
volatile unsigned portBASE_TYPE uxNumberOfItems;
volatile xListItem * pxIndex; /* Используется для прохода по списку. Указывает
на последний элемент, возвращенный
функцией pvListGetOwnerOfNextEntry (). */
volatile xMiniListItem xListEnd; /* Элемент списка, в котором находится максимально
возможное значение, означающее, что он всегда
находится в конце списка и, поэтому,
используется как маркер. */
} xList;
Размер списка в любое время хранится в переменной uxNumberOfItems, предназначенной для быстрого выполнения операций с размерами списков. Все новые списки инициализируются таким образом, что в них есть один элемент: элемент xListEnd. Значение xListEnd.xItemValue является контрольным значением, равным наибольшему значению для переменной xItemValue: 0xffff в случае, если portTickType представляет собой 16-битное значение, и 0xffffffff в случае, если portTickType представляет собой 32-битное значение. Другие элементы списка также могут иметь такое же значение; алгоритм вставки элементов списка гарантирует, что xListEnd всегда будет последним элементом в списке.
Поскольку списки сортируются в порядке убывания, элемент xListEnd используется как маркер начала списка. А поскольку список кольцевой, этот элемент xListEnd также является маркером конца списка.
В большинстве «традиционных» операций доступа к списку, которыми вы пользуетесь, вся работа выполняется в одном цикле for() или в функции, вызываемой следующим образом:
for (listPtr = listStart; listPtr != NULL; listPtr = listPtr->next) {
// Что-то здесь делается с указателями listPtr ...
}
В системе FreeRTOS часто требуется получить доступ к спискам сразу с помощью нескольких циклов for() и while(), а также с помощью нескольких вызовов функций, и поэтому происходит обращение к функциям, в которых при обходе списка используется указатель pxIndex. Функция listGET_OWNER_OF_NEXT_ENTRY() выполняет операцию pxIndex = pxIndex->pxNext; и возвращает значение pxIndex. (Конечно, также осуществляется соответствующее определение конца списка). Таким образом, во время перемещения по списку с использованием pxIndex сам список отвечает за отслеживание «текущего положения», позволяя остальной части системы FreeRTOS не беспокоиться об этом.
Рис.3.4: Полная схема списка готовности задач Ready List в системе FreeRTOS после возникновения прерывания
То, что все действия со списком pxReadyTasksLists[] выполняются в функции vTaskSwitchContext(), является хорошим примером того, как используется указатель pxIndex. Давайте предположим, что у нас есть только один уровень приоритета, приоритет 0, и есть три задачи на этом уровне приоритета. Это похоже на общую схему списка готовности задач, которую мы рассмотрели ранее, но на этот раз мы будем рассматривать все структуры и поля данных.
Как видно на рис.3.3, pxCurrentTCB указывает, что в настоящее время выполняется Задача B. В следующий момент времени выполняется функция vTaskSwitchContext(), она вызывает функцию listGET_OWNER_OF_NEXT_ENTRY() с тем, чтобы перейти к запуску следующей задачи. Эта функция использует pxIndex->pxNext для того, чтобы выяснить, что следующей задачей является Задача С, и теперь pxIndex указывает на элемент списка Задачи C, а pxCurrentTCB указывает на блок TCB Задачи С так, как показано на рис.3.4.
Обратите внимание, что каждый объект struct xListItem является, на самом деле, объектом xGenericListItem из соответствующего блока TCB.
Продолжение статьи: Очереди