От шедулера к планировщику

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

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

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

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

    Кстати, в 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, как и должно быть.

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

    Комментарии 13

      +1
      Мне по этому поводу (или не по этому, а просто так) частенько вспоминается одна история: работал я как-то совместно с человеком, весьма неглупым, инженером-разработчиком, университетским преподавателем в области IT. И однажды обратил внимание, как запуская какую-то счетную задачу (матлаб что ли), он ставил ей наивысший приоритет «чтобы быстрее считало», после чего пару часов глядел в экран где даже курсор мыши двигался весьма неторопливо…
        0
        Угу. А ещё есть люди, которые на кондиционере ставят -16, чтобы посильнее холодило. :) Того же поля ягоды. :)
        +3
        Я бы все же разделил софт и хард риалтайм.
        То, что у вас описано — это софт риалтайм (тупо жадно забираем все ресурсы системы). По сути, если в системе есть софт-риалтайм нить или нити, все остальные нити становятся idle. Т.е. на самом деле это вообще не риалтайм, потому что никакое реальное время не гарантируется от слова совсем. Может быть повезет, а может и нет.

        В харде же все просто: кто не успел, тот опоздал и будет немедленно убит. У каждой хард-рт задачи (job) есть таймер, до которого она должна закончиться. Если не успела — процесс убивается, ресурсы освобождаются, гипс снимают, клиент уезжает.
        Это также означает, что другие задачи, у которых еще есть шансы успеть вовремя, получат больше ресурсов.
        Ну, приведу наглядный пример: декодирование видео на пределе аппаратных возможностей. Нет смысла рендерить кадр, если его время уже прошло и сейчас нужно показывать уже следующий. В софт-риалтайме (все обычные системы), например, во время внезапного свопа или там глобальной сборки мусора видео тупо начнет тормозить (проигрываться с замедлением), а затем резко ускорится, чтобы нагнать тайминг. В хард-рт выпадут несколько кадров (просядет фпс), но рассинхрона не будет.
        Для ядерного реактора, да и просто для любого банального промышленного робота, софт-рт подход неприменим. Ну представьте, несет промышленный робокран какую-нибудь тяжелую хрень на подвесе. Мозги ему выдают команды типа «перейти в позицию 11… перейти в позицию 12… перейти в позицию 13». Если время, во сколько точно выдаются команды, начнет сначала тормозить, а потом резво догонять, получится праща, которая может разрушить все вокруг. Если просто выпадет промежуточная команда «перейти в позицию 11.8», но команды «перейти в 11.7» и «перейти в 11.9» придут вовремя — за счет инерции последствия будут намного легче.
          0
          Есть разные модели хард риалтайма, и описание этих моделей в мои задачи на данном этапе не входило. Про выделение жёстких таймслотов я упомянул, а вот уже реакция на отказ — вопрос отдельный. Если у нас есть резервирование, и нить переиспользовала процессор, и мы считаем это проблемой, можно переключиться на горячий резерв. Но, вообще, это очень сложная тема. В анналах истории есть описание ситуации, в которой софт от старой ракеты перенесли на новую, новая полетела быстрее ожидаемого, в расчёте координат делитель оказался равным нулю и процессор упал в фолт. Система переключилась на резервный и он… тоже упрал в фолт — программа и данные-то те же самые. :)
          0
          «Реальное время: нити такого класса всегда вытесняют с процессора нити других классов так быстро, как это возможно»

          Дмитрий, я просто предупреждаю что со времени появления защищенного режима процессоров Intel такой класс нитей исчез, условно на этом уровне работает операционная система, daemon триды там глобальные. Но вы что-то свое пилите, отказались из соображений безопасности. Чтобы нить реального времени не сломала что-то (умышленно или случайно). Просто предупреждаю, чтобы вы знали и не наступили на те же грабли, что инженеры Intel. Если вы делаете real time нити это нужно делать осознанно. Извините, пожалуйста, что несколько резкое замечание, но не мог не схватиться за маузер.
            0

            OS разные бывают. Всякие специализированные RTOS принципиально не имеют деления на user и kernel-space.


            С другой стороны, у Linux есть группа RT приоритетов и оно, вроде как, даже работает. Конечно, что это особых привилегий процессу требует.


            Post Scriptum я не специалист, поэтому могу ошибаться во втором абзаце.

              0
              Да деление на юзер и кернел тоже не очень принципиально. Очевидно, что если в realtime нити случился вечный цикл — система умерла. Где бы это ни было. Оживить можно, но это требует дополнительных механизмов, которые логически неочевидны и это отдельный разговор.
                0
                Нужно больше ядер
                  0
                  :) ну — представьте, что приложение с ошибкой запускает треды по числу ядер. часто так и делают, чтобы получить максимальную производительность.
              0
              1. Такой класс никуда не исчез.

              2. «Даемон триды» — это тоже нити, у них тоже есть приоритет. Иногда именно такой. А ещё есть нити драйверов. И т.п.

              3. Я описываю механизм, а не его применение. Конкретная ОС может запретить нитям пользователя иметь приоритеты выше некоторого предела, чтобы гарантировать себя от зависания по вине ошибочной программы пользователя. Или выставить пределы на фактическую загрузку процессора.

              4. Все озвученные вопросы не имеют вообще никакого отношения к защищённому режиму процессоров Интел и вообще к процессору Интел. Они совершенно не зависят от процессора и всё вышесказанное специалистам по разработке ОС к моменту рождения компании Интел было более-менее известно.

              0

              Шикарный пост! Сам превратил черный ящик устройства многозадачности и работы планировщика (надо сказать, тоже достаточно примитивного) копаясь в недрах ThreadX, но такие посты прекрасно расставляют оставшиеся точки на i, а так же открывают глаза на некоторые тюки (например трюк с инверсией приоритетов), поэтому большое спасибо.

                0
                Кстати, в SMP системе шедулер ничем не отличается от однопроцессорного.

                Я не знаю деталей, но мне кажется там есть немало нюансов связанных с накладными расходами на перенос треда с одного ядра на другое, и на правильное балансирование тредов между процессорами. Еще есть вопрос какое ядро/ядра должны заниматься планированием. Например у нас 2 ядра и есть один очень требовательный к cpu тред, а все остальные idle. В таком случае, возможно, лучше запускать планировщик на втором ядре, а первому просто подсовывать результат и по прерыванию он без всяких проверок будет выполнять тот тред который ему сказали.

                Недавно наткнулся на интересную статью о багах в планировщике Linux, авторы которой обещают в среднем до 20% улучшения производительности при определенных задачах.
                  0
                  Вы правы — алгоритм назначения нити на процессор в SMP системах учитывает, на каком процессоре нить работала в предыдущем слоте, и предпочитает его.

                  Но это исключительно оптимизация. Если её не сделать, шедулер всё равно будет работать. Фактически, несколько процессоров занимаются назначением нити для себя совершенно самостоятельно и асинхронно.

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

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

                Самое читаемое