CFS vs O(1) scheduler

    Думаю многие слышали, что помимо стандартного O(1) планировщика в linux, появился CFS(Completely Fair Scheduler; «абсолютно справедливый планировщик»), над которым работает Ingo Molnar. Собственно эту заметку я хотел бы посвятить сравнению этих двух планировщиков и краткому рассмотрению их основных алгоритмов. В конце заметки можно немного почитать по FreeBSD'шный планировщие ULE.

    preamble:
    • O(1) scheduler — вкратце, политика планировщика была довольно проста: каждый cpu имел 2 очереди: в одной находятся таски, которые в скором времени будут запущены, в другом — спящие таски. когда первая очередь оказывалась пуста, она менялась местами со второй, соответсвенно во второй очереди все спящие процессы 'просыпались', а в первая служила очередью для отработавших и уснувших процессов. посему время работы алгоритма во-первых, не зависит от кл-ва процессов, во-вторых, оно постоянно — O(1).
    • Completely Fair Scheduler — для хранения процессов использует red-black дерево, где ключём является wait_runtime каждого процесса. wait_runtime — это кл-во наносекунд, которое данный процесс недоработал или переработал. т.е. если оно < 0, значит он переработал, если оно > 0, значит он недоработал. эта мера позволяет засечь out-of-ballance от 'идеального случая'. в зависимости от значения wait_runtime, процесс занимает своё место в дереве. если wait_runtime < 0, то, я полагаю, процесс будет сидеть на нижних уровнях, если больше 0, то ближе к вершине. следовательно, CFS — не O(1) scheduler, он O(logN).


    amble:
    кто-то возможно видел статью на slashdot'e про то, что создатель bsd'шного ULE-планировщика, Jeff Roberson, прокомментировал CFS:

    Представьте, что идёт работа с сотнями или даже тысячами запущенных тредов, кэш-промахи(cache misses) в случае log n обхода могут довольно дорого стоить. В особенности потому, что вы будете иметь гораздо больше событий планировщика(scheduling events) с таким количеством тредов


    действительно, извлечение очередного процесса из дерева иногда требует ребалансинга, вставка процесса в деревно требует обхода по одной ломаной и возможного ребалансинга. но этот недостаток проявляет себя только при очень большом n, что с очень малой долей вероятности встретится на десктопах, но может встретится на больших work stations. отсюда можно сделать вывод: статвить этот планировщик на нагруженные сервера/work stations и прочие машинки, расчитанные на работу с большим количеством одновременно запущенных процессов/тредов, пока что не стоит.

    а проявляет себя этот недостаток так:

    Ingo заявил, что имея 1000 запущенных тасков(таск — процесс или тред), в системе увеличится стоимость переключения контекста(context switching) на 20%. Это дерево из 10 уровней. В худшем случае может добавиться ещё 5 уровней, что приведёт к 30% увеличению стоимости. Это не смертельно, но и хорошим поведением это тоже не назовёшь.


    к недостаткам же O(1) scheduler'a можно отнести недостаточно хороший, 'справедливый' ребалансинг по ядрам. вот, что говорит сам Ingo в этом комментарие:

    Проще всего описать это на простом примере: если я на своей машие запускаю glxgears, она будет использовать ровно 50% CPU. Если я буду использовать SD планировщик(он же O(1) scheduler) и запущу на нём CPU hog вместе с glxgears, оба таска разделят CPU ресурсы. CPU hog получит ~60% процессорного времени, а glxgears — 40%. Если же я буду использовать CFS, оба таска получат по 50% процессорного времени.


    CFS действительно лучше лучше распределяет процессорное время и раскидывает таски по ядрам(проверенно на личной практике).
    Также к плюсам CFS можно отнести заметно меньшее время отклика, нежели у O(1). Это подтверждают тесты, сделанные Михаилом Пиатровски. посмотреть результаты можно здесь. Таким образом, CFS можно смело ставить на десктоп, где нет огромного количества одновременно запущенных процессов.

    как поставить CFS:

    прежде всего отмечу, что CFS доступен для ядер начиная с версии 2.6.20.
    взять патч по версию ядра >= 2.6.20 можно здесь.
    далее за ходим в каталог с linux sources и накладываем патч:

    # patch -p1 < sched-cfs-v2.6.2x.1-x.patch


    также для разработки CFS планировщика выделен отдельный git-репозиторий. стянуть клон репозитория можно отсюда.

    fw about ULE:

    каждый cpu имеет 3 очереди, проиндексированные по приоритетам. 2 очереди используются для имплементации таких sheduling-classes, как прерывания, риал-тайм и разделение времени. последняя очередь используется для idle-класса.
    политика переключения очередей аналогична O(1) shceduler, т.е. когда одна очередь опустеет, она тут же заменяется другой. следовательно время переключения не зависит от кл-ва процессов.
    также ULE использует гибкие и эффективные политики на SMP системах, по словам Jeff'a раскидывая таски между CPU (цит.) «как минимум не менее 'справедливо', чем это делает 'абсолютно справедливый планировщик'».

    подробнее про ULE: ULE.pdf и здесь.

    собственно, это была пробная заметка, тк она является первой в этом блоге. отсюда есть несколько вопросов к прочитавшим: интересно ли вам было бы почитать более(гораздо) подробно про реализацию CFS и стоит ли в дальнейшим переводить какие либо цитаты, вставленные в контекст заметки с английского?
    спасибо за внимание.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      0
      Да, интересно. Узнал про red-black trees. Задумался о пересборке ядра с этим шедулером — почему бы и нет?
        0
        спасибо за статью... очень интересно
        побольше бы таких статей на хабре
          0
          Этот планировщик, кажется, появился уже в ядре в 2.6.23. Я все сижу жду ебилдов, не терпится потестировать :)
            +2
            Интересная заметка, но можно добавить несколько замечаний (:
            - "таск" = "задача"
            - "тред" = "нить"
            - "сервер/work station" = "сервер/рабочая станция"
            Просто такой жуткий разнобой, где на русcком, где на английском (кроме аббревиатур), где транслитом. Еще можно новое предложение (обычно после точки) начинать с прописной буквы, но это уже придирки ;)
              0
              Еще можно новое предложение (обычно после точки) начинать с прописной буквы, но это уже придирки ;)

              это уже привычка - не нажимать шифт, очень трудно от неё избавиться =)
              0
              спасибо большое за статью. Давно слышал о CFS, но толком не знал что это и с чем это есть. Теперь все намного понятнее.
                0
                Познавательно. Спасибо. Переводите еще, очень интересно побольше узнать об этом.
                  0
                  Интересно, переводите ещё, только, может быть, не стоит плодить журналы? Есть же 'операционные системы' уже.

                  Кстати, вопрос: а почему именно низкоуровневый планировщик в ядре должен решать, как балансировать нагрузку? Не проще ли просто предоставить интерфейс для перетаскивания задач процессу пользователя, который может быть специализирован уже под конкретную миссию системы?
                    0
                    Это идея кооперативной (невытесняющей) многозадачности, или я вас неправильно понял? Например, в Windows 3.11 программы должны были вызывать yield() для передачи управления другой задаче.

                    Или вы говорите о планировщике, находящемся не в ядре — например, как в микро(нано?)ядерных системах?
                    0
                    Спасибо. Было интересно и хочется продолжения.
                      0
                      Читать интересно. Только вот цитаты белым на черном фоне мне не нравятся. Присоединяюсь к этому блогу. Только вот тематика блога какая? Исключительно "системное" программирования под никс?
                        0
                        Интересно, спасибо!
                          0
                          мне понравилось, буду читать вас регулярно.
                            0
                            очень интересная статья! Спасибо большое автору!
                              0
                              добавлю, что обязательно жду вашего продолжения и комментарии девелоперов мне тоже очень понравились.
                              0
                              Как-то уже давно был спор, что "scheduler" лучше все-таки переводить как "диспетчер".
                                0
                                "Диспетчер" — слишком общее слово. Не зря ведь он называется по-английски scheduler, а не dispatcher? Лично я за "планировщик".
                                0
                                Очень интересная статья. спасибо.
                                  0
                                  если wait_runtime < 0, то, я полагаю, процесс будет сидеть на нижних уровнях, если больше 0, то ближе к вершине.

                                  Красно-чёрное дерево всё-таки является деревом поиска. Таким образом ключ "горизонтальный", то есть вершины с меньшими значениями слева, с большими - справа (или наоборот - кому как нравится). Это относится к изображению дерева с вершиной сверху. Если слева, всё наоборот. Главное, что от глубины вершины ничего не зависит.
                                    0
                                    да, моя ошибка. спасибо за исправление
                                    0
                                    asgard, подскажите, пожалуйста.

                                    А как в планировщике O(1) учитываются приоритеты процессов?

                                    Спасибо!

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

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