[TencentOS tiny] Углубленный анализ исходного кода (3) — очередь

Интернет вещей

Основные понятия очереди

Очередь — это структура данных, обычно используемая для взаимодействия между задачами.任务与任务间、中断和任务间Доставка сообщений, которая позволяет задачам получать сообщения неопределенной длины от других задач или прерываний. Задачи могут читать сообщения из очереди. Когда сообщения в очереди пусты, задача чтения сообщений будет заблокирована. Пользователи также могут указать Время задача ожидает сообщенияtimeout, за это время, если очередь пуста, задача保持阻塞Статус ожидания, пока данные очереди станут действительными. Когда в очереди есть новое сообщение, заблокированная задача будет пробуждена и обработает новое сообщение; когда время ожидания превышает указанное время блокировки, даже если в очереди нет действительных данных, задача автоматически изменится с состояния блокировки в состояние готовности, очередь сообщений — это异步способ общения.

При использовании служб очередей задача или процедура обслуживания прерывания может поместить одно или несколько сообщений в очередь. Точно так же одна или несколько задач могут получать сообщения из очереди. Когда в очередь отправляется несколько сообщений, то сообщение, поступившее в очередь первым, обычно передается задаче первым, т. е. задача получает сообщение, поступившее в очередь первым, то есть по принципу «первым поступил — первым обслужен». (FIFO),фактическиTencentOS tinyПринцип «последним пришел — первым вышел» временно не поддерживается.LIFOОчередь операций, но поддерживает операции LIFO消息队列.

намекать:TencentOS tinyОчередь не эквивалентна очереди сообщений, хотя队列Базовая реализацияполагаться消息队列, но вTencentOS tinyРазделить их посередине — это две концепции, в конце концов, операции разные.

Механизм блокировки очереди

Возьмем простой пример, чтобы понять механизм блокировки в операционной системе:

Предположим, однажды вы идете в ресторан на ужин, но в ресторане нет еды, тогда у вас может быть три варианта: вы поворачиваете голову и уходите. Поскольку еды нет, вы должны перейти в другой ресторан, верно? Или вы выберете подождать некоторое время, может быть, босс пойдет купить еды, через некоторое время будет еда, и вы сможете поесть. Или вы думаете, что этот ресторан очень вкусный, и вы не уйдете, если не пообедаете, просто подождите здесь~

То же самое: предположим, что когда задача A читает очередь (出队), и обнаружил, что сообщения в это время нет, то у задачи А есть 3 варианта выбора в это время: первый выбор, задача А поворачивает голову и уходит, так как сообщения в очереди нет, то я не буду ждать, заниматься другими делами, поэтому подзадача A不会进入阻塞态; Второй вариант, здесь должна ждать задача А, через некоторое время в очереди могут быть сообщения, в это время задача А перейдет в состояние блокировки, ожидая прихода сообщения, а время ожидания задачи А равно由我们自己指定, когда задача А ожидает сообщение очереди в течение периода блокировки, то задача А перейдет из состояния блокировки в состояние готовности; если время ожидания истекло и в очереди нет сообщения, то задача А не будет ждать, от блокирующее состояние Третий вариант — дождаться, пока задача А умрет, и не уходить, пока сообщение не будет достигнуто, так что подзадача А перейдет в блокирующее состояние, пока не закончит чтение сообщений в очереди.

Структура данных, реализованная очередью

блок управления очередью

TencentOS tinyУправление очередью осуществляется через блок управления очередью, тип данных которогоk_queue_t, блок управления очередью состоит из нескольких элементов, в основном в том числеpend_obj_tТипpend_objа такжеk_msg_queue_t Типmsg_queueсписок сообщений. На самом деле реализация всей очереди очень проста, в основном полагаясь наmsg_queueсерединаqueue_headПеременная-член (на самом деле это список сообщений (связный список сообщений)), все сообщения будут записываться в этот список сообщений, при чтении сообщений сообщения будут считываться из списка сообщений.

Структуры данных, унаследованные от объектов ядра, находятся в строке 35 файла kernelcoreincludetos_pend.h.

typedef struct pend_object_st {
    pend_type_t     type;
    k_list_t        list;
} pend_obj_t;

Тип данных списка сообщений (блок управления очередью сообщений), строка 13 файла kernelcoreincludetos_msg.h

typedef struct k_msg_queue_st {
#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    knl_obj_t       knl_obj;
#endif

    k_list_t        queue_head;
} k_msg_queue_t;

Блок управления очередью в строке 6 файла kernelcoreincludetos_queue.h

typedef struct k_queue_st {
    pend_obj_t      pend_obj;
    k_msg_queue_t msg_queue;
} k_queue_t;

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

блок управления сообщениями

В дополнение к указанному выше блоку управления очередью существует также блок управления очередью сообщений, т.к.TencentOS tinyРеализация очередей в Китае основана на очередях сообщений. Поскольку очередь может передавать данные (сообщения), должна быть структура данных, которая может хранить сообщения. Я называю это блоком управления сообщениями. Блок управления сообщениями записывает адрес хранения сообщениеmsg_addrи размер сообщенияmsg_size, а также естьlistПеременная-член, вы можете смонтировать сообщение в список сообщений очереди.

Структура данных блока управления сообщениями, строка 7 файла kernelcoreincludetos_msg.h

typedef struct k_message_st {
    k_list_t        list;
    void           *msg_addr;
    size_t          msg_size;
} k_msg_t;

На самом деле реализация очереди зависит от очереди сообщений, и их взаимосвязь такова:

Переменная-член сообщения в блоке управления задачами

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

Структура данных блока управления задачами находится в строке 90 файла kernelcoreincludetos_task.h.

typedef struct k_task_st {
···
#if TOS_CFG_MSG_EN > 0u
    void               *msg_addr;           /**< 保存接收到的消息地址 */
    size_t              msg_size;            /**< 保存接收到的消息大小 */
#endif
···
} k_task_t;

Определения макросов, связанных с сообщениями

существуетtos_config.hВ файле определение макроса включения компонента очередиTOS_CFG_QUEUE_EN, включить определение макроса компонента очереди сообщенийTOS_CFG_MSG_EN, макроопределение количества сообщений в пуле сообщений, поддерживаемом системойTOS_CFG_MSG_POOL_SIZE.

#define TOS_CFG_QUEUE_EN                1u

#define TOS_CFG_MSG_EN                    1u

#define TOS_CFG_MSG_POOL_SIZE           3u

пул сообщений

существуетTencentOS tinyопределяет массив вk_msg_pool[TOS_CFG_MSG_POOL_SIZE]В качестве пула сообщений его тип данных является типом блока управления сообщениями.k_msg_t, потому что к сообщениям часто обращаются при использовании очередей сообщений, и каждая строка элемента этого большого массива инициализируется, когда система инициализируется и монтируется в список незанятых сообщений.k_msg_freelist, что составляет то, что мы называем пулом сообщенийk_msg_pool, а переменные-члены в пуле — это то, что мы называем сообщениями.

Зачем использовать метод объединения для обработки сообщений, из-за высокой эффективности и высокой скорости повторного использования, точно так же, как мы кладем ложку воды в пруд, а затем возвращаем ее в пруд после использования, эта операция очень эффективна, и в ограниченном объеме. встроенные ресурсы могут использоваться многократно и эффективно.

Определение пула сообщений находится в строке 51 файла kernelcoretos_global.c.

#if TOS_CFG_MSG_EN > 0u
TOS_LIST_DEFINE(k_msg_freelist);

k_msg_t             k_msg_pool[TOS_CFG_MSG_POOL_SIZE];

#endif

создание очереди

tos_queue_create()Функция используется для создания очереди, которая представляет собой структуру данных, используемую для передачи данных между задачами. Каждый раз, когда создается новая очередь, для нее нужно выделять оперативную память, при создании очереди нам нужно определить блок управления очередью, память для которого автоматически выделяется компилятором. В процессе создания фактически инициализируется содержимое блока управления очередью, а также инициализируется содержимое блока управления очередью.pend_objпеременная-членtypeимущество, идентифицированное какPEND_TYPE_QUEUE, указав, что это очередь, а затем вызвать функцию API в очереди сообщенийtos_msg_queue_create()переменная-член сообщения очередиmsg_queueИнициализация, по сути, заключается в инициализации списка сообщений.

Создайте функцию очереди в строке 5 kernelcoretos_queue.c.

__API__ k_err_t tos_queue_create(k_queue_t *queue)
{
    TOS_PTR_SANITY_CHECK(queue);

    pend_object_init(&queue->pend_obj, PEND_TYPE_QUEUE);
    tos_msg_queue_create(&queue->msg_queue);
    return K_ERR_NONE;
}

уничтожить очередь

tos_queue_destroy()Функция используется для уничтожения очереди.Когда очередь не используется, ее можно уничтожить.Суть уничтожения заключается в очистке содержимого блока управления очередью.Во-первых, определить тип блока управления очередью.PEND_TYPE_QUEUE, эта функция может уничтожить только управляющий блок типа очереди. Затем оцените, есть ли задача, ожидающая сообщения в очереди, и если да, вызовитеpend_wakeup_all()Функция пробуждает эту задачу, а затем вызываетtos_msg_queue_flush()Функция поставит в очередь все сообщения в списке сообщений "清空", "Пустой" означает освобождение сообщения, смонтированного в очереди, обратно в пул сообщений (если в списке сообщений очереди есть сообщения, используйтеmsgpool_free()сообщение об освобождении функции),knl_object_deinit()Функция состоит в том, чтобы гарантировать, что очередь была уничтожена, и в это время блок управления очередьюpend_objпеременная-членtypeимущество, идентифицированное какKNL_OBJ_TYPE_NONE. Наконец, выполните планирование задачи после уничтожения очереди для переключения задач (в конце концов, простоСкорее всегоразбудить задачу).

Но есть одно замечание, потому что оперативная память блока управления очередью статически выделяется компилятором, поэтому даже если очередь уничтожена, эта память не может быть освобождена~

Уничтожьте функцию очереди в kernelcoretos_queue.c, строка 14.

__API__ k_err_t tos_queue_destroy(k_queue_t *queue)
{
    TOS_CPU_CPSR_ALLOC();

    TOS_PTR_SANITY_CHECK(queue);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();

    if (!pend_is_nopending(&queue->pend_obj)) {
        pend_wakeup_all(&queue->pend_obj, PEND_STATE_DESTROY);
    }

    pend_object_deinit(&queue->pend_obj);
    tos_msg_queue_flush(&queue->msg_queue);

    TOS_CPU_INT_ENABLE();
    knl_sched();

    return K_ERR_NONE;
}

очистить очередь

Очистка очереди фактически возвращает сообщение обратно в пул сообщений, который, по сути, вызываетtos_msg_queue_flush()функция. Он реализован на основе очередей сообщений.

Функция пустой очереди в kernelcoretos_queue.c, строка 41.

__API__ k_err_t tos_queue_flush(k_queue_t *queue)
{
    TOS_CPU_CPSR_ALLOC();

    TOS_PTR_SANITY_CHECK(queue);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();
    tos_msg_queue_flush(&queue->msg_queue);
    TOS_CPU_INT_ENABLE();

    return K_ERR_NONE;
}

очередь ожидания (сообщение)

Когда задача пытается получить сообщение из очереди, пользователь может указать время ожидания, если и только если в очереди есть сообщение, задача может получить сообщение. В течение времени ожидания, если очередь пуста, задача останется заблокированной, ожидая, пока сообщение очереди станет действительным. Когда другие задачи или программы обработки прерываний записывают данные в очередь ожидания, задача автоматически переходит из состояния блокировки в состояние готовности. Когда задача ждет тайм-аут, даже если в очереди нет действительного сообщения, задача автоматически переходит из состояния блокировки в состояние готовности. Процесс ожидания очереди тоже очень прост, давайте посмотрим на параметры (среди нихmsg_addrиmsg_sizeПараметр — это то, что используется для хранения того, что возвращает функция, то есть вывода):

параметр инструкция
queue указатель блока управления очередью
msg_addr Используется для сохранения выбранных сообщений (это вывод)
msg_size Используется для сохранения размера получаемых сообщений (выводится)
timeout время ожидания (в тыс.tickт это единица измерения)

Процесс ожидания сообщения в очереди выглядит следующим образом:

  1. Сначала проверьте правильность входящих параметров
  2. попробуй позвонитьtos_msg_queue_get()Функция получает сообщение, если в очереди есть сообщение, она получит успех (возвратK_ERR_NONE), в противном случае получение не удастся. (Об этой функции будет рассказано в следующей главе)
  3. При успешном получении функция может быть закрыта напрямую, а при неудачном получении сообщения функция может быть закрыта в соответствии с заданным временем ожидания.timeoutзаблокировать, если не ждет(timeout =TOS_TIME_NOWAIT), код ошибки возвращается напрямуюK_ERR_PEND_NOWAIT.
  4. Если планировщик заблокированknl_is_sched_locked(), операция ожидания не может быть выполнена и возвращается код ошибкиK_ERR_PEND_SCHED_LOCKED, ведь надо переключать задачи, а планировщик не может переключать задачи, когда он заблокирован.
  5. перечислитьpend_task_block()Функция блокирует задачу, что фактически удаляет задачу из списка готовыхk_rdyq.task_list_head[task_prio], и внесите в лист ожиданияobject->list, если время ожидания не вечное ожиданиеTOS_TIME_FOREVER, который также вставляет задачу в список времениk_tick_list, время блокировкиtimeout, а затем выполнить планирование задачиknl_sched().
  6. Когда программа может быть выполнена дляpend_state2errno(), это значит任务等待到消息,или发生超时, затем позвонитеpend_state2errno()Функция получает состояние ожидания задачи и видит, какая ситуация заставляет задачу возобновить выполнение.
  7. Если это нормально (ожидание получения сообщения), то сообщение удаляется из блока управления задачами.k_curr_task->msg_addrчитать и писатьmsg_addrиспользуется для возврата. Тот же размер сообщения также будет передаватьсяmsg_size возвращение.

    Получить (подождать) функцию сообщения очереди, в строке 60 kernelcoretos_queue.c

__API__ k_err_t tos_queue_pend(k_queue_t *queue, void **msg_addr, size_t *msg_size, k_tick_t timeout)
{
    TOS_CPU_CPSR_ALLOC();
    k_err_t err;

    TOS_PTR_SANITY_CHECK(queue);
    TOS_PTR_SANITY_CHECK(msg_addr);
    TOS_PTR_SANITY_CHECK(msg_size);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();

    if (tos_msg_queue_get(&queue->msg_queue, msg_addr, msg_size) == K_ERR_NONE) {
        TOS_CPU_INT_ENABLE();
        return K_ERR_NONE;
    }

    if (timeout == TOS_TIME_NOWAIT) {
        *msg_addr = K_NULL;
        *msg_size = 0;
        TOS_CPU_INT_ENABLE();
        return K_ERR_PEND_NOWAIT;
    }

    if (knl_is_sched_locked()) {
        TOS_CPU_INT_ENABLE();
        return K_ERR_PEND_SCHED_LOCKED;
    }

    pend_task_block(k_curr_task, &queue->pend_obj, timeout);

    TOS_CPU_INT_ENABLE();
    knl_sched();

    err = pend_state2errno(k_curr_task->pend_state);

    if (err == K_ERR_NONE) {
        *msg_addr = k_curr_task->msg_addr;
        *msg_size = k_curr_task->msg_size;
        k_curr_task->msg_addr = K_NULL;
        k_curr_task->msg_size = 0;
    }

    return err;
}

Добавьте задачу, ожидающую сообщения, в соответствующую функцию списка ожидания в строке 106 файла kernelcoretos_pend.c.

__KERNEL__ void pend_task_block(k_task_t *task, pend_obj_t *object, k_tick_t timeout)
{
    readyqueue_remove(task);
    pend_list_add(task, object);

    if (timeout != TOS_TIME_FOREVER) {
        tick_list_add(task, timeout);
    }
}

Функция получения состояния ожидания задачи в строке 72 файла kernelcoretos_pend.c.


__KERNEL__ k_err_t pend_state2errno(pend_state_t state)
{
    if (state == PEND_STATE_POST) {
        return K_ERR_NONE;
    } else if (state == PEND_STATE_TIMEOUT) {
        return K_ERR_PEND_TIMEOUT;
    } else if (state == PEND_STATE_DESTROY) {
        return K_ERR_PEND_DESTROY;
    } else if (state == PEND_STATE_OWNER_DIE) {
        return K_ERR_PEND_OWNER_DIE;
    } else {
        return K_ERR_PEND_ABNORMAL;
    }
}

(сообщение) записать в очередь

Задачи или подпрограммы обслуживания прерываний могут отправлять сообщения в очередь сообщений.TencentOS tinyСообщение будет взято из пула сообщений и смонтировано в конец списка сообщений очереди (метод отправки FIFO).tos_queue_post()это разбудить задачу, ожидающую сообщения очереди,tos_queue_post_all()Он разбудит все задачи, ожидающие сообщений очереди, независимо от ситуации, это называетсяqueue_do_postЗапишите сообщение в очередь. Процесс записи сообщения в очередь:

  1. Сначала проверьте правильность входящих параметров
  2. Определить, есть ли задача, ожидающая сообщения, и если да, то в соответствии сoptПараметр решает разбудить задачу или все ожидающие задачи, в противном случае напрямую записать сообщение в очередь.
  3. Вызывается, когда ни одна задача не ожидает сообщенияtos_msg_queue_put()Функция записывает сообщение в очередь, и способ записи в очередь следуетFIFOв общем(TOS_OPT_MSG_PUT_FIFO), запись успешно возвращаетсяK_ERR_NONE. И если в пуле сообщений нет сообщений (максимальное количество сообщений определяетсяTOS_CFG_MSG_POOL_SIZEопределение макроса), запись завершается ошибкой и возвращаетсяK_ERR_QUEUE_FULLкод ошибки. (Об этой функции будет рассказано в следующей главе)
  4. Если есть задача, ожидающая сообщения, вызовитеqueue_task_msg_recv()Функция записывает содержимое и размер сообщения в блок управления задачами.msg_addrиmsg_sizeВ переменной-члене, помимо необходимости разбудить задачу, просто вызовитеpend_task_wakeup()Функция пробуждает соответствующую ожидающую задачу, и основная идея обработки состоит в том, чтобы передатьTOS_LIST_FIRST_ENTRYПолучите задачу, ожидающую в очереди, и разбудите ее.
  5. Процесс пробуждения всех ожидающих задач на самом деле такой же, за исключением того, что есть дополнительный цикл для пробуждения всех задач в списке ожидания по очереди, и все~

    Напишите функцию сообщения очереди в kernelcoretos_queue.c, строки 159, 164.

__API__ k_err_t tos_queue_post(k_queue_t *queue, void *msg_addr, size_t msg_size)
{
    TOS_PTR_SANITY_CHECK(queue);
    TOS_PTR_SANITY_CHECK(msg_addr);

    return queue_do_post(queue, msg_addr, msg_size, OPT_POST_ONE);
}

__API__ k_err_t tos_queue_post_all(k_queue_t *queue, void *msg_addr, size_t msg_size)
{
    TOS_PTR_SANITY_CHECK(queue);
    TOS_PTR_SANITY_CHECK(msg_addr);

    return queue_do_post(queue, msg_addr, msg_size, OPT_POST_ALL);
}

Функция, фактически вызываемая функцией сообщения очереди записи, черезoptПараметры обрабатываются по-разному, в строке 118 файла kernelcoretos_queue.c.

__STATIC__ k_err_t queue_do_post(k_queue_t *queue, void *msg_addr, size_t msg_size, opt_post_t opt)
{
    TOS_CPU_CPSR_ALLOC();
    k_list_t *curr, *next;

    TOS_PTR_SANITY_CHECK(queue);

#if TOS_CFG_OBJECT_VERIFY_EN > 0u
    if (!pend_object_verify(&queue->pend_obj, PEND_TYPE_QUEUE)) {
        return K_ERR_OBJ_INVALID;
    }
#endif

    TOS_CPU_INT_DISABLE();

    if (pend_is_nopending(&queue->pend_obj)) {
        if (tos_msg_queue_put(&queue->msg_queue, msg_addr, msg_size, TOS_OPT_MSG_PUT_FIFO) != K_ERR_NONE) {
            TOS_CPU_INT_ENABLE();
            return K_ERR_QUEUE_FULL;
        }
        TOS_CPU_INT_ENABLE();
        return K_ERR_NONE;
    }

    if (opt == OPT_POST_ONE) {
        queue_task_msg_recv(TOS_LIST_FIRST_ENTRY(&queue->pend_obj.list, k_task_t, pend_list),
                                msg_addr, msg_size);
    } else { // OPT_QUEUE_POST_ALL
        TOS_LIST_FOR_EACH_SAFE(curr, next, &queue->pend_obj.list) {
            queue_task_msg_recv(TOS_LIST_ENTRY(curr, k_task_t, pend_list),
                                msg_addr, msg_size);
        }
    }

    TOS_CPU_INT_ENABLE();
    knl_sched();

    return K_ERR_NONE;
}

Разбудите функцию ожидающей задачи, строка 87 файла kernelcoretos_pend.c

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

__KERNEL__ void pend_task_wakeup(k_task_t *task, pend_state_t state)
{
    if (task_state_is_pending(task)) {
        // mark why we wakeup
        task->pend_state = state;
        pend_list_remove(task);
    }

    if (task_state_is_sleeping(task)) {
        tick_list_remove(task);
    }

    if (task_state_is_suspended(task)) {
        return;
    }

    readyqueue_add(task);
}

Суммировать

Код лаконичен и краток, а мысли ясны, настоятельно рекомендуется изучить его поглубже~

Следуй за мной, если хочешь!

欢迎关注我公众号

Добро пожаловать в публичный аккаунт «Развития Интернета вещей IoT»

Категории