Миро Самек, Роберт Вард "Построение наипростейшего диспетчера задач" (перевод)

Диспетчер SST

Диспетчер SST оформлен в виде простой Си-функции "SST_schedule_()", чья работа заключается в поиске готовых к исполнению задач с наивысшим приоритетом и их запуске, если текущий приоритет ниже найденного. Для выполнения указанной работы диспетчер использует две переменные: уже описанную "SST_readySet_" и хранящую текущий уровень приоритета "SST_currPrio_". Для сохранения целостности данных обращение к обеим переменным происходит только внутри критических секций (см. макросы "SST_ISR_ENTRY" и "SST_ISR_EXIT"). Полный исходный текст диспетчера SST приведён в листинге 4 (да, это весь код). Функция "SST_schedule_()" должна вызываться и возвращать управление при запрещённых прерываниях.

    void SST_schedule_(void) {
        static uint8_t const log2Lkup[] = {       /* log-base-2 lookup table */
            0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
            5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            . . .
            8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
            . . .
        };
(1)     uint8_t pin = SST_currPrio_;              /* save the initial priority */
        uint8_t p;                                /* the new priority */
                                                  /* is the new priority higher than the initial? */
(2)     while ((p = log2Lkup[SST_readySet_]) > pin) {
            TaskCB *tcb  = &l_taskCB[p - 1];
                                                  /* get the event out of the queue */
(3)         SSTEvent e = tcb->queue__[tcb->tail__];
            if ((++tcb->tail__) == tcb->end__) {
                tcb->tail__ = (uint8_t)0;
            }
            if ((--tcb->nUsed__) == (uint8_t)0) { /* is the queue becoming empty?*/
(4)             SST_readySet_ &= ~tcb->mask__;    /* remove from the ready set */
            }
(5)         SST_currPrio_ = p;                    /* this becomes the current task priority */
(6)         SST_INT_UNLOCK();                     /* unlock the interrupts */

(7)         (*tcb->task__)(e);                    /* call the SST task */

(8)         SST_INT_LOCK();                       /* lock the interrupts for the next pass */
        }
(9)     SST_currPrio_ = pin;                      /* restore the initial priority */
    }

				

Работа диспетчера подобна функционированию аппаратного контроллера прерываний при обслуживании очередного события. Процедура начинается с сохранения текущего приоритета в стековой переменной "pin" (1). Далее он сравнивается с наивысшим приоритетом задачи из числа готовых к исполнению (вычисляемому по значению "SST_readySet_"). Самой быстродействующей реализаций такого сравнения является табличный алгоритм бинарного поиска (а если точнее, то log₂ (x) + 1), выясняющий номер самого старшего единичного бита в "SST_readySet_" (2). Если приоритет найденной задачи "p" выше текущего приоритета, то диспетчер должен запусить именно её. Для начала из очереди событий изымается очередная запись (3) и, если очередь опустела, в "SST_readySet_" сбрасывается соответствующий бит (4). Затем текущий приоритет "SST_currPrio_" поднимается до нового уровня "p" (5), разблокируются прерывания (6) и вызывается задача с приоритетом "p" (7). По завершении её работы и возврате управления диспетчеру прерывания вновь блокируются (8) и повторяется цекл "while" поиска готовой к запуску задачи (2). Процедура продолжается, пока обнаруживаются готовые к исполнению процессы, чей приоритет выше значения, сохраненного в переменной "pin". Перед завершением работы диспетчер восстанавливает приоритет "SST_currPrio_" из переменной "pin" (9).

Взаимоисключающая блокировка в SST (Mutual exclusion)

SST - ядро вытесняющей операционной системы и, как при работе со всеми ядрами такого типа, следует очень аккуратно проводить распределение общего ресурса среди нескольких задач. В идеале задачи SST не должны разделять общих ресурсов, сократив всё межпроцессное взаимодействие к обмену событиями. Такой идеализированный подход позволил бы вести разработку каждой задачи с использованием простейшей последовательной техники, оставляя все детали потокобезопасного обмена сообщениями и обслуживание очередей на SST. Конечно, возможно использование и разделяемых ресурсов в обмен на увеличение взаимного влияния между задачами. Выбор такого пути вынуждает самостоятельно заниматься синхронизацией доступа к общим ресурсам (разделяемым переменным или устройствам). Одной из возможностей является защита доступа с помощью критических секций, что требует от разработчика постоянно запрещать и разрешать прерывания при каждом обращении к ресурсу. Такой вариант, возможно, будет самым оптимальным методом синхронизации при кратковременных обращениях к резурсам. Но SST предлагает средства более тонкой синхронизации: мьютекс с повышением приоритета. Этот тип мьютекса не подвержен инверсии приоритета [5], но при этом позволяет аппаратным прерываниям и приоритетным процессам работать как обычно. SST-вариант мьютекса с повышением приоритета весьма прост. Следует напомнить, что диспетчер SST может запускать только те процессы, приоритет которых выше приоритета задачи, диспетчер вызвавшей. Это означает, что кратковременное повышение приоритета посредством переменной "SST_currPrio_" блокирует все процессы с приоритетом ниже, чем "поднятый". Это именно то, для чего мьютекс с повышением риоритета и предназначен. Реализация показана в листинге 5.

    uint8_t SST_mutexLock(uint8_t prioCeiling) {
        uint8_t p;
        SST_INT_LOCK();
        p = SST_currPrio_;                /* save the original SST priority to return */
        if (prioCeiling > SST_currPrio_) {
            SST_currPrio_ = prioCeiling;  /* set the SST priority to the ceiling */
        }
        SST_INT_UNLOCK();
        return p;
    }

    /*..........................................................................*/

    void SST_mutexUnlock(uint8_t orgPrio) {
        SST_INT_LOCK();
        if (orgPrio < SST_currPrio_) {
            SST_currPrio_ = orgPrio;      /* restore the saved priority to unlock */
            SST_schedule_();              /* the scheduler unlocks the interrupts internally */
        }
        SST_INT_UNLOCK();
    }

				

В отличие от макроса "INT_LOCK", SST-мьютекс допускает вложенность процедур, запрещающих / разрешающих прерывания, потому что предшествующее состояние системы прерываний сохраняется в стеке. Листинг 6 показывает использование мьютекса внутри обработчиков прерываний "tickTaskA()" и "tickTaskB()" при вызове программного генератора случайных чисел, который не допускает повторной входимости.

    void tickTaskA(SSTEvent e) {
        . . .
        uint8_t x, y;
        uint8_t mutex;                            /* mutex object preserved on the stack */

        mutex = SST_mutexLock(TICK_TASK_B_PRIO);  /* mutex lock */
        x = random(34);                           /* call to non-reentrant random number generator */
        y = random(13);                           /* call to non-reentrant random number generator */
        SST_mutexUnlock(mutex);                   /* mutex unlock */
        . . .
    }