UNИX, весна 2008, 02 семинар (от 04 апреля)
Материал из eSyr's wiki.
Тема: Война планировщиков
Лектор: Ющенко Никита
Презентация: Sched-sem.odp
Диктофонная запись: http://esyr.org/lections/audio/uneex_2008_summer/uneex_seminar_08_04_04.ogg
Содержание |
[править] Введение
Идея такая: поскольку началась война планировщиков, было бы интересно расказать про это студентам, но поскольку просто про войну рассказывать неинтересно, то было решено провести лекцию про планировщики.
MMU --- Memory Management Unit --- базовый объект управления памятью. Идея в том, что переключение адресных пространств --- очень тяжёлая операция, поскольку связана со сбросом кэша. На самом деле переключение процесса --- 4 операции (сохранить регистр стека, восстановить регистр стека, сохранить ip, восстановить ip).
Планировщик --- такой объект, который выбирает, какому объекту в какой момент времени передать управление.
Всегда, когда идёт речь про планирование процесса, есть приоритет. Приоритет --- такая характеристика, которая говорит, каким процессам отдавать предпочтение. Что за характеристика и какое предпочтение, у каждого планировщика по-своему.
- Статическое планирование
- Динамическое планирование
- Статический приоритет --- назначается раз и навсегда
- Динамический приоритет --- может меняться во времени
- Планирование без вытеснение --- приложение само решает, когда закончить работу
- Планирование с вытеснением --- решает планировщик
[править] Планирование в ОС реального времени
Перед тем, как расск. про линух и ... системы, лектор расск. про ОСРВ. Там всё проще, поскольку ограничений больше, и пространство ... меньше. Особенности:
- Директивные сроки
- Работа в цикле. Все задачи цикличны и планировщик может это использовать.
- Вопрос гарантируемой планируемости. Так как неполучение результата в гарант. сроки фатально, то надо гаранитровать время получ. результата.
[править] Статич. планирование
Обычно бывает большой цикл и малый цикл. Предп., что система функ. по большим циклам. Большой цикл разбивается на малые, для них просчитывается время работы, и можо рпосчитать время работы.
Преимущества:
- Гарантируется срок выполнения
- Отсутсвтие затрат runtime
Недостатки:
- Задача NP-полная
- Сложность изменения построенного расп.
Это приводит к тому, что в проектных заданиях указано, что расп. должно быть загружено не более, чем на 50 процентов.
Переход к дин. планир --- вопрос с гарант. сроков. Есть много мат. статей, где доказывается, что если набор задач такой-то, алгоритм такой-то, то гарантия есть. Но при это загрузка процессора малая.
Наиб. расп. алгоритмы:
- Rate monitonic
- Deadline monitonic
- EDF --- дин. назнач. приоритета. Проц. отдаётся той задаче, у которой дедлайн ближе. Лучший среди приведённых алгоритмов.
Но это всёэто хорошо, если крит. секций нет.
Зависимые задачи:
- Проблема инверсии приоритетов. Решение --- наслед. приоритетов. Приоритет задачи, вошедшей в крит. секции, поднимается до максимального.
[править] Планирование в системах общего назначения
- Возможно только дин. планирование
- Характ. св-вом систем общ. назн. является то, что пользователь ничего не хочет настраивать, но хочет, чтобы всё работало. Поэтому все задачи ложатся на планировщик. Поэтому задача намного сложнее. Бо требования противоречивы
[править] Разделение задач на CPU-bound и IO-bound
На практике, задачи являются либо такой, либо такой. Исключеним явл. разве что СУБД. Политика такая, что те, кто хотят I/O, надо пускать первыми, потому что они его быстро отпустят и общяя пропуск. способность повысится. Пробелма в том, что планировщик не знает, какой процесс, разве что историю. Поэтому планир. вынужден с помощью эвристик выявлять, какие процессы IO-bound.
Теоретически, программисты могли бы давать хинты, но такого не бывает.
Эвристики имеют след. эффект: планировщик может отдавать упр. одной задаче и не отдавать другой (starvation)
Другие особенности планирования:
- Наличие неск. процессоров. С одной стороны, если процессор свободен, хорошо бы задач ему отдать, с другой --- очень плохо кэщу
- SMT --- процессоры бывают разные, и лучше отдавать разным процессорам.
- NUMA --- неэфф. рассм. как SMP.
[править] Простейшая реализация SCHED_OTHER
- round-robin
- Квант времени, выделяемый процессу, зависит от приоритета
- Работать будет плохо, потому что не даёт приоритета IO-Bound задачам
[править] Классический планировщик Unix (по википедии)
- Очередей несколько
- Каждая очередь --- round-robin
- Таким образом, полчается, что IO-bound работают больше
[править] Планировщик Linux 2.4.x
Он отличался от простого раунд-робина только тем, что когда нужно было выбрать задачи, он сканировал все доступные и выбирал лучшу. Кроме того, делалась попытка дать приоритет IO-bound задачам путём давания большего приоритета им.
- Время разбивается на эпо
Умерло это дело тогда, когда распространилась Java (2000-2001), потому что народ начал пистаь программы с большим количеством потоков, и сканирование готовых процессов отнимало большое количество времени.
[править] О(1) планировщик (2.6.0---2.6.22)
Все опреации этого планировщика не зависели от количества процессов.
- Все процессы в системе готовые хранились в двух массивах списков. Количество списков равно 140, и он деражал по своему списков для каждого уровня приоритетов. И держалась маска, где список не пуст. И поиск по битовой маске очень быстрый. Из списка бралась первая задача. Когда задача отрабатывала квант времени, она перемещалась в список, соотв. приоритету, она перемещалась в другой массив. В какой-то момент все в массиве active перемещались в expired. И пока active не пуст, он опустошается, потом они меняются местами.
- Если несколько процессоров, то раз в 500 секунд делает перебалансировка
- Хуже для IO-bound/ Для этого планировщик начал обрастать эвристиками, которые динамически начали менять приоритет. Они в результате всё испортили. Система стала потихоньку неустойчивой. Нехорошо, когда планировщик разрастается.
На базе этого началась война плнировщиков. В 2005 году Кон Коливас предложил идею обеспечить хорошую эфф. не на уровне эвристик а на уровне алгоритма. Планировщик тоже имел О(1).
- Имеется отдельный список на каждый уровень приоритета. Меняется то, как готовые процессы по списку перемещ. Вначале процесс находится в начале списка, он получает. фикс. квант времени. Когда он отработает, он опускается на уровень вниз. Потом опять тот же кван и ещё на ступень вниз. В результате все имеющиеся процессы опуск. вниз, и начинается новая эпоха. Потом всё восстанавливается, но те, которые отрабатывали, помещаются на ступеньку ниже и получают по 2T. То есть, распред. справедливое, IO-bound получает часто кванты.
Потом было добавлено 4 звено: ограничение времени обслуживания списка на лесенке. Если кол-во процессов в списке больше некоторого предела, то процессы проваливаются сразу на след. ступеньку. Это немного ухудшает справедливость, но уменьшает starvation.
Всё шло к тому, что он должен был стать основным в 2.6.23, но ...
- Нашлись такие workload, на которых планировщик работает плохо. Но автор отреагировал на это воинственно.
В это же время был предложен другой алгоритм, CFS? rjnjhsq d bnjut b gj,tlbk.
[править] Completely Fair Scheduler
- Приоритетов нет вовсе
- Рассм. идеальная картина, когда все процессы получают равное проц. время. И отслеживаться, насколько имеещееся распред. отлич. от идеального. И это является ключом к выбору, какую задачу назн. на процессор.
Этот алгоритм не яв. константным, он логарифмический.
Соответственно, выбор быстрый --- берётся самый левый элемент из дерева. Чуть медленнее включение --- логарифм. операция.
Весь планировщик занимает строк 200. Старвейшена нет, интерактивность хорошая. Не зависит от тиков планировщика.
CFS включён в 2.6.23.
На самом деле, не всё шоколадно, и кто его знает, может тоже начнёт обрастать.
Есть ещё одно решение: group scheduling. Возможно справедливость делать между пользователями. Делать это вкладывванием CFS в себя. Сначлала для пользователей, потом для потоков. Есть в 2.6.24.
|
|
