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

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

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

Lines Club

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

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

ОС реального времени 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.


Продолжение статьи: Очереди


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

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