См. две другие статьи этой группы — Делаем многозадачность и Преемптивность: как отнять процессор.

Сразу просьба к строгим читателям. Если вы не поняли какой-либо термин из применённых — спросите, я подскажу, что я имел в виду. А если вам нравится другое написание или перевод этого термина — укажите его в комментарии. Я применяю те, которые нравятся мне.

Итак, в прошлых статьях описан механизм реализации многозадачности за вычетом планировщика, он же шедулер, он же скедулер, он же Васька меченый, сорри, заговариваюсь я с этими терминами…

Как я уже говорил, шедулер — это просто функция, которая отвечает на вопрос: какую нить и на сколько времени поставить на процессор.

Кстати, в SMP системе шедулер ничем не отличается от однопроцессорного. Вообще, чтобы проще понимать структуру взаимодействия сущностей на одном и нескольких процессорах, проще всего представить себе следующую модель: для каждого процессора есть нить «простоя» (которая работает, если вообще больше некому и просто останавливае процессор до прерывания), которая постоянно пытается «отдать» процессор (которым она как бы владеет) другим нитям, выбирая нить с помощью шедулера.

Говоря о шедулере нельзя не сказать о приоритетах.

Приоритет — свойство нити (или процесса) влияющее на конкуренцию этой нити с другими нитями за процессор.

Приоритет обычно описывается парой <класс приоритета, значение приоритета внутри класса>.

На сегодня сформировалась довольно чёткая схема реализации приоритетов. Приоритеты нитей делятся на три класса:

• Реальное время: нити такого класса всегда вытесняют с процессора нити других классов так быстро, как это возможно, и никогда не снимаются с процессора кроме как по наличию нити с более высоким приоритетом реального времени. То есть — такие нити сами должны решать, когда им больше не нужен процессор.
• Разделение времени: нити такого класса всегда вытесняют с процессора нити класса idle, между собой нити разделения времени конкурируют мягко. Две нити такого класса с разными значениями приоритета будут получать разный процент процессорного времени, но обязательно будут его получать, даже если значения приоритетов различаются предельным образом.
• Idle класс: нити такого класса получают процессор только если нет готовых к исполнению нитей других классов, «на сдачу». Лично я не вижу смысла в значении приоритета внутри класса idle. Хотя так тоже бывает.

Кстати. Говорят, Кернигана как-то спросили, что бы он сделал иначе, если бы писал Юникс заново. «Написал бы creat как create», — ответил мэтр. Я бы добавил к списку исправлений ещё мешок несуразностей, начиная с nice — понятие приоритета в Юниксе почему-то первёрнуто. Чем nice меньше, тем приоритет выше.

Мы в данной статье будем придерживаться более человеколюбивой шкалы: выше численное значение = больше процессора.

Кому-то, наверное, уже хочется заглянуть в код. Вот он:
Исходный текст Фантомовского шедулера.



Кстати о Пушкине. Я категорически не претендую на какие-то сакральные знания в области написания планировщиков. Приведённый пример — сермяжная и банальная, хотя и вполне разумная реализация. Тем не менее, написание хорошего шедулера — очень серьёзная научная задача, про это диссертации пишут, и если речь заходит про настоящее реальное время — всё становится совсем серьёзно. В этой статье я затрагиваю только основы. В нашей стране есть специалисты, которые по этой теме знают примерно на три порядка больше, чем ваш покорный слуга.

За сим — продолжим.

Достаточно традиционная реализация шедулера предполагает наличие так называемой run queue — очереди нитей, готовых к исполнению. Вообще-то это не обязательно очередь, и если и очередь — то, обычно, множество очередей, относящихся к разным классам, а иногда и уровням приоритетов.

Конкретно в Фантоме это три очереди, согласно классам:

/** Idle prio threads */
static queue_head_t	runq_idle = {0,0};

/** Normal prio threads */
static queue_head_t	runq_norm = {0,0};

/** Realtime prio threads */
static queue_head_t	runq_rt = {0,0};

В целом нить по отношению к процессору может находиться в трёх состояниях:

• Заблокирована. Не находится на процессоре, не может быть на него поставлена. Отсутствует в какой-либо run queue.
• Исполняется. Отсутствует в какой-либо run queue.
• Может исполняться. Присутствует в какой-либо run queue.

То есть, в run queue находятся нити, которые хотели бы попасть на процессор.

Отсюда работа планировщика сводится к тому, чтобы:

1. Определиться с тем, нить какого класса приоритета сейчас будем запускать. Это просто — проверить, не пуста ли очередь realtime — если не пуста, то мы запускаем нить realtime, проверить очередь нормальных приоритетов — если не пуста, то запускаем нормальную нить. Иначе — запускаем idle нить. Если и таких нет, отмечаем, что процессор idle и уходим в нить «вечного» сна.
2. Если определились с приоритетом — выбрать правильную нить для исполнения в данном приоритете.
3. Назначить нити временной интервал для исполнения.

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

    // Have some realtime?
    if( !queue_empty(&runq_rt) )
    {
        int maxprio = -1;
        phantom_thread_t *best = 0;
        phantom_thread_t *it = 0;
        queue_iterate(&runq_rt, it, phantom_thread_t *, runq_chain)
        {
            if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue;
            if( ((int)it->priority) > maxprio )
            {
                maxprio = it->priority;
                best = it;
            }
        }
        if( best )
        {
            assert(t_is_runnable(best));
            return best;
        }
    }

Очевидная доработка кода заключается в том, чтобы не сортировать все нити в шедулере, а вставлять нить в очередь в порядке убывания численного приоритета. Тогда планировщику достаточно просто вынуть из очереди первую нить и её запустить.

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

Здесь надо отметить, что переменная ticks_left в структуре состояния нити определяет, сколько 10 мсек интервалов нить продержится на процессоре.

Сначала рассмотрим, что делает функция t_assign_time():

        it->ticks_left = NORM_TICKS + it->priority;

Она проверяет, что все нити истратили свои ticks_left, и если да — назначает им новые ticks_left — тем, у кого приоритет больше — даёт больше процессорного времени.

Что делает сам планировщик? Выбирает нить с максимальным приоритетом и с ненулевым остатком процессорного времени, её и запускает:

    // Have normal one?
    if( !queue_empty(&runq_norm) )
    {
        // If no normal thread has ticks left, reassign
        // ticks and retry
        do {
            unsigned int maxprio = 0; // NB! not a negative number!
            phantom_thread_t *best = 0;
            phantom_thread_t *it = 0;
            queue_iterate(&runq_norm, it, phantom_thread_t *, runq_chain)
            {
                if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue;

                if( (it->priority > maxprio) && (it->ticks_left > 0) )
                {
                    maxprio = it->priority;
                    best = it;
                }
            }
            if( best )
            {
                return best;
            }
        } while(t_assign_time());
    }

Когда все остатки у всех нитей кончились — просит t_assign_time() назначить нитям новые остатки.

Вообще-то, сортировка здесь относительно избыточна. Достаточно просто добавлять нити в конец очереди, а выбирать из начала — fair enough. Вообще, сортировать все нити — очевидно плохо, не делайте так. Я тоже этот кусок перепишу более оптимальным образом, например, так как уже описал выше, для realtime.

Кстати, при чтении кода планировщика надо учитывать, что нити не всегда «съедают» свой квант времени — нить может заблокироваться на примитиве синхронизации и часть времени простоять не по своей воле. Этим и обусловлена сортировка: если приоритет нити высок, то нить после разблокирования вернётся на процессор раньше, чем доработают все остальные нити.

Хорошо, перейдём к idle priority class. Мы попадём сюда только если в предыдущих классах все нити спят или отсутствуют.

    // Have idle one?
    ret = (phantom_thread_t *)queue_first(&runq_idle);
    if( ret )
    {
        if( ret->thread_flags & THREAD_FLAG_NOSCHEDULE )
            goto idle_retry;

        // Just take first. Switched off thread will become
        // last on runq, so all idle threads will run in cycle
        ret->ticks_left = NORM_TICKS;
        return ret;
    }
    else
        goto idle_no;

Здесь всё просто — берём первую попавшуюся, запускаем на стандартное время. Поскольку при снятии с процессора она попадёт в конец очереди runq_idle, все такие нити будут запускаться по кругу.

Наконец, если вообще ничего не нашлось, у нас есть специальная idlest thread на этот случай.

    STAT_INC_CNT(STAT_CNT_THREAD_IDLE);
    percpu_idle_status[GET_CPU_ID()] = 1; // idle
    return GET_IDLEST_THREAD(); // No real thread is ready to run

Она у каждого процессора своя просто потому, что одну нить нельзя запустить дважды. Проста как мычание:

    while(1)
    {
        hal_sti();
        hal_wait_for_interrupt();
    }

Почти всё.

Что здесь не учтено.

Interactive thread prio boost: обычно планировщики увеличивают фактический приоритет нитям, которые замечены во вводе-выводе с консоли или другой сущности, за которой, потенциально, прячется интерактивный юзер. Это повышает перцептивную реактивность системы — «операционка меньше тупит» с точки зрения человека. И наоборот — если нить «доедает» свой таймслайс до конца, и делает это стабильно, ей немного понижают приоритет, считая её чисто вычислительной. С той же целью — повысить реактивность системы.

Это, конечно, касается только нитей с обычным классом приоритетов — никто и никогда не трогает приоритеты реального времени.

Планирование реального времени с гарантией доли процессора. Строгие системы реального времени имеют жёсткий план, в рамках которого нить или группа нитей может получать чётко оговоренное количество процессорного времени.

Инверсия приоритетов.

Предположим, у нас есть страшно важная нить R с максимальным приоритетом реального времени, и нить I с приоритетом класса idle, которая занимается несущественной ерундой. А так же обычная нить U, которая работает с юзером — читает команды с консоли. Шелл, например.

Юзер бездействует, ждёт ввода-вывода и нить U.

Нить I получает процессор, решает поделать свою ерунду и хочет для этого выделить себе немного памяти. Функция выделения памяти ядра запирает глобальный мьютекс и начинает выделять. Работая на idle prio, очевидно.

В этот момент просыпается ото сна нить R, которой пора скорректировать положение стержня поглотителя активной зоны реактора. И тоже хочет немного памяти.

(Давайте не будем привередничать и спрашивать, что U и R делают на одной машине — U может быть сервером статистики по TCP, например.)

Естественно, R забирает процессор у I, но упирается в глобальный мьютекс при выделении памяти, и останавливается.

Тут бы I продолжить работу, но юзер набирает команду, и U принимается за работу, отбирая процессор у I. Теперь, внезапно, высокоприоритетная нить реального времени R ждёт окончания работы нити U, и реактор взрывается к чертям.

Для того, чтобы это не случалось, делают то, что у меня в Фантоме пока не сделано — инверсию приоритетов.

Она формулируется так: если нить более высокого приоритета заблокирована на ресурсе, занятом нитью низкого приоритета, вторая нить получает на время такой блокировки приоритет первой нити.

То есть, в нашем примере, нить I на время блокировки мьютекса выделения памяти должна была получить приоритет реального времени от нити R, вытеснить к чертям нить U и доделать то, что блокирует нить R. После разблокировки мьютекса её приоритет должен понизиться обратно до idle и процессор перейдёт к R, как и должно быть.

Вот теперь, наверное, всё. :)