Редактирование: UNИX, весна 2008, 02 семинар (от 04 апреля)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

'''Тема:''' Война планировщиков<br />
'''Лектор:''' Ющенко Никита<br />
'''Презентация:''' [[Media:Sched-sem.odp|Sched-sem.odp]]<br />
'''Диктофонная запись:''' 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.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/UN%D0%98X%2C_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2008%2C_02_%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80_%28%D0%BE%D1%82_04_%D0%B0%D0%BF%D1%80%D0%B5%D0%BB%D1%8F%29

Редактирование: UNИX, весна 2008, 02 семинар (от 04 апреля)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 21: / Строка 21: @@
 == Планирование в ОС реального времени ==
-Перед тем, как расск. про линух и ... системы, лектор расск. про ОСРВ. Там всё проще, поскольку ограничений больше, и пространство ... меньше. Особенности:
+Перед тем, как расск. про линух и ... системы, лектор расск. про ОСРВ. Там всё проще, поскольку ограничсений больше, и пространство ... меньше. Особенности:
 * Директивные сроки
 * Работа в цикле. Все задачи цикличны и планировщик может это использовать.