Думаю многие слышали, что помимо стандартного O(1) планировщика в linux, появился CFS(Completely Fair Scheduler; «абсолютно справедливый планировщик»), над которым работает Ingo Molnar. Собственно эту заметку я хотел бы посвятить сравнению этих двух планировщиков и краткому рассмотрению их основных алгоритмов. В конце заметки можно немного почитать по FreeBSD'шный планировщие ULE.
preamble:
amble:
кто-то возможно видел статью на slashdot'e про то, что создатель bsd'шного ULE-планировщика, Jeff Roberson, прокомментировал CFS:
действительно, извлечение очередного процесса из дерева иногда требует ребалансинга, вставка процесса в деревно требует обхода по одной ломаной и возможного ребалансинга. но этот недостаток проявляет себя только при очень большом n, что с очень малой долей вероятности встретится на десктопах, но может встретится на больших work stations. отсюда можно сделать вывод: статвить этот планировщик на нагруженные сервера/work stations и прочие машинки, расчитанные на работу с большим количеством одновременно запущенных процессов/тредов, пока что не стоит.
а проявляет себя этот недостаток так:
к недостаткам же O(1) scheduler'a можно отнести недостаточно хороший, 'справедливый' ребалансинг по ядрам. вот, что говорит сам Ingo в этом комментарие:
CFS действительно лучше лучше распределяет процессорное время и раскидывает таски по ядрам(проверенно на личной практике).
Также к плюсам CFS можно отнести заметно меньшее время отклика, нежели у O(1). Это подтверждают тесты, сделанные Михаилом Пиатровски. посмотреть результаты можно здесь. Таким образом, CFS можно смело ставить на десктоп, где нет огромного количества одновременно запущенных процессов.
как поставить CFS:
прежде всего отмечу, что CFS доступен для ядер начиная с версии 2.6.20.
взять патч по версию ядра >= 2.6.20 можно здесь.
далее за ходим в каталог с linux sources и накладываем патч:
также для разработки CFS планировщика выделен отдельный git-репозиторий. стянуть клон репозитория можно отсюда.
fw about ULE:
каждый cpu имеет 3 очереди, проиндексированные по приоритетам. 2 очереди используются для имплементации таких sheduling-classes, как прерывания, риал-тайм и разделение времени. последняя очередь используется для idle-класса.
политика переключения очередей аналогична O(1) shceduler, т.е. когда одна очередь опустеет, она тут же заменяется другой. следовательно время переключения не зависит от кл-ва процессов.
также ULE использует гибкие и эффективные политики на SMP системах, по словам Jeff'a раскидывая таски между CPU (цит.) «как минимум не менее 'справедливо', чем это делает 'абсолютно справедливый планировщик'».
подробнее про ULE: ULE.pdf и здесь.
собственно, это была пробная заметка, тк она является первой в этом блоге. отсюда есть несколько вопросов к прочитавшим: интересно ли вам было бы почитать более(гораздо) подробно про реализацию CFS и стоит ли в дальнейшим переводить какие либо цитаты, вставленные в контекст заметки с английского?
спасибо за внимание.
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 и стоит ли в дальнейшим переводить какие либо цитаты, вставленные в контекст заметки с английского?
спасибо за внимание.
