Редактирование: UNИX, весна 2008, 02 семинар (от 04 апреля)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 1: | Строка 1: | ||
| - | '''Тема | + | '''Тема''': Война планировщиков<br /> |
| - | '''Лектор:''' Ющенко Никита<br /> | + | '''Лектор:''': Ющенко Никита<br /> |
| - | '''Презентация | + | '''Презентация''': <br /> |
'''Диктофонная запись:''' http://esyr.org/lections/audio/uneex_2008_summer/uneex_seminar_08_04_04.ogg | '''Диктофонная запись:''' http://esyr.org/lections/audio/uneex_2008_summer/uneex_seminar_08_04_04.ogg | ||
== Введение == | == Введение == | ||
| - | Идея такая: поскольку началась война планировщиков, было бы интересно расказать про это студентам, но поскольку просто про войну рассказывать неинтересно, | + | Идея такая: поскольку началась война планировщиков, было бы интересно расказать про это студентам, но поскольку просто про войну рассказывать неинтересно, от было решено провести лекцию про планировшики |
| - | MMU --- Memory Management Unit --- базовый объект управления памятью. Идея в том, что переключение | + | MMU --- Memory Management Unit --- базовый объект управления памятью. Идея в том, что переключение абресных пр-в --- очень тяжёлая операция, поскольку связана со сбросом кэша. На самом деле переключение процесса --- 4 операции (сохранить регистр стека, восстановить регистр стрека, сохранить ip, восстановить ip). |
| - | Планировщик --- такой объект, который выбирает, какому объекту в какой момент времени передать | + | Планировщик --- такой объект, который выбирает, какому объекту в какой момент времени передать управлений. |
| - | Всегда, когда идёт речь про планирование процесса, | + | Всегда, когда идёт речь про планирование процесса, емсть приоритет. Приоритет --- такая хпрактеристика, которая говорит, каким процессам отдавать предпочтение. Что за характеристика и какое предпочтение, у кажлого планир. по своему. |
* Статическое планирование | * Статическое планирование | ||
| - | * | + | * ЖДинамическое планирование |
| - | * | + | * Статические приоритет --- назначается раз и на всегда |
* Динамический приоритет --- может меняться во времени | * Динамический приоритет --- может меняться во времени | ||
| - | * Планирование без вытеснение --- | + | * Планирование без вытеснение --- прилож. само решает, когда закончить работу |
* Планирование с вытеснением --- решает планировщик | * Планирование с вытеснением --- решает планировщик | ||
== Планирование в ОС реального времени == | == Планирование в ОС реального времени == | ||
| - | Перед тем, как расск. про линух и ... системы, лектор расск. про ОСРВ. Там всё проще, поскольку | + | Перед тем, как расск. про линух и ... системы, лектор расск. про ОСРВ. Там всё проще, поскольку ограничсений больше, и пространство ... меньше. Особенности: |
* Директивные сроки | * Директивные сроки | ||
* Работа в цикле. Все задачи цикличны и планировщик может это использовать. | * Работа в цикле. Все задачи цикличны и планировщик может это использовать. | ||
| Строка 36: | Строка 36: | ||
* Сложность изменения построенного расп. | * Сложность изменения построенного расп. | ||
| - | Это приводит к тому, что в проектных | + | Это приводит к тому, что в проектных задания указано, что расп. должно быть загружено не более, чем на 50 процентов. |
Переход к дин. планир --- вопрос с гарант. сроков. Есть много мат. статей, где доказывается, что если набор задач такой-то, алгоритм такой-то, то гарантия есть. Но при это загрузка процессора малая. | Переход к дин. планир --- вопрос с гарант. сроков. Есть много мат. статей, где доказывается, что если набор задач такой-то, алгоритм такой-то, то гарантия есть. Но при это загрузка процессора малая. | ||
| Строка 53: | Строка 53: | ||
* Характ. св-вом систем общ. назн. является то, что пользователь ничего не хочет настраивать, но хочет, чтобы всё работало. Поэтому все задачи ложатся на планировщик. Поэтому задача намного сложнее. Бо требования противоречивы | * Характ. св-вом систем общ. назн. является то, что пользователь ничего не хочет настраивать, но хочет, чтобы всё работало. Поэтому все задачи ложатся на планировщик. Поэтому задача намного сложнее. Бо требования противоречивы | ||
| - | === Разделение задач на | + | === Разделение задач на СЗГ-ищгтв b IO-bound === |
На практике, задачи являются либо такой, либо такой. Исключеним явл. разве что СУБД. Политика такая, что те, кто хотят I/O, надо пускать первыми, потому что они его быстро отпустят и общяя пропуск. способность повысится. Пробелма в том, что планировщик не знает, какой процесс, разве что историю. Поэтому планир. вынужден с помощью эвристик выявлять, какие процессы IO-bound. | На практике, задачи являются либо такой, либо такой. Исключеним явл. разве что СУБД. Политика такая, что те, кто хотят I/O, надо пускать первыми, потому что они его быстро отпустят и общяя пропуск. способность повысится. Пробелма в том, что планировщик не знает, какой процесс, разве что историю. Поэтому планир. вынужден с помощью эвристик выявлять, какие процессы IO-bound. | ||
| Строка 76: | Строка 76: | ||
=== Планировщик Linux 2.4.x === | === Планировщик Linux 2.4.x === | ||
| - | Он отличался от простого раунд-робина только тем, что когда | + | Он отличался от простого раунд-робина только тем, что когда нуно было выбрать задачи, он сканировал все доступные и выбирал лучшу. Кроме того, делалась попытка дать приоритет IO-bound задачам путём давания большего приоритета им. |
* Время разбивается на эпо | * Время разбивается на эпо | ||
Умерло это дело тогда, когда распространилась Java (2000-2001), потому что народ начал пистаь программы с большим количеством потоков, и сканирование готовых процессов отнимало большое количество времени. | Умерло это дело тогда, когда распространилась Java (2000-2001), потому что народ начал пистаь программы с большим количеством потоков, и сканирование готовых процессов отнимало большое количество времени. | ||
=== О(1) планировщик (2.6.0---2.6.22) === | === О(1) планировщик (2.6.0---2.6.22) === | ||
| - | Все опреации этого | + | Все опреации этого планировщига не зависели от количества процессов. |
| - | * Все процессы в системе готовые хранились в двух массивах списков. Количество списков равно 140, и он деражал по своему списков для каждого уровня приоритетов. И держалась маска, где список не пуст. И поиск по битовой маске очень быстрый. Из списка бралась первая задача. Когда задача отрабатывала квант времени, она перемещалась в список, | + | * Все процессы в системе готовые хранились в двух массивах списков. Количество списков равно 140, и он деражал по своему списков для каждого уровня приоритетов. И держалась маска, где список не пуст. И поиск по битовой маске очень быстрый. Из списка бралась первая задача. Когда задача отрабатывала квант времени, она перемещалась в список, воотв. приоритету, она перемещалась в другой массив. В какой-то момент все в массиве active перемещались в expired. И пока active не пуст, он опустошается, потом они меняются местами. |
* Если несколько процессоров, то раз в 500 секунд делает перебалансировка | * Если несколько процессоров, то раз в 500 секунд делает перебалансировка | ||
* Хуже для IO-bound/ Для этого планировщик начал обрастать эвристиками, которые динамически начали менять приоритет. Они в результате всё испортили. Система стала потихоньку неустойчивой. Нехорошо, когда планировщик разрастается. | * Хуже для IO-bound/ Для этого планировщик начал обрастать эвристиками, которые динамически начали менять приоритет. Они в результате всё испортили. Система стала потихоньку неустойчивой. Нехорошо, когда планировщик разрастается. | ||
На базе этого началась война плнировщиков. В 2005 году Кон Коливас предложил идею обеспечить хорошую эфф. не на уровне эвристик а на уровне алгоритма. Планировщик тоже имел О(1). | На базе этого началась война плнировщиков. В 2005 году Кон Коливас предложил идею обеспечить хорошую эфф. не на уровне эвристик а на уровне алгоритма. Планировщик тоже имел О(1). | ||
| - | * Имеется отдельный список на каждый уровень приоритета. Меняется то, как готовые процессы по списку перемещ. Вначале процесс находится в начале списка, он получает. фикс. квант времени. Когда он отработает, он опускается на уровень вниз. Потом опять тот же кван и ещё на ступень вниз. | + | * Имеется отдельный список на каждый уровень приоритета. Меняется то, как готовые процессы по списку перемещ. Вначале процесс находится в начале списка, он получает. фикс. квант времени. Когда он отработает, он опускается на уровень вниз. Потом опять тот же кван и ещё на ступень вниз. Врезуьтате все имеющиеся процессы опуск. вниз, и начинается новая эпоха. Потом всё восстанавливается, но те, которые отрабатывали, помещаются на ступеньку ниже и получают по 2T. То есть, распред. справедливое, IO-bound получает часто кванты. |
Потом было добавлено 4 звено: ограничение времени обслуживания списка на лесенке. Если кол-во процессов в списке больше некоторого предела, то процессы проваливаются сразу на след. ступеньку. Это немного ухудшает справедливость, но уменьшает starvation. | Потом было добавлено 4 звено: ограничение времени обслуживания списка на лесенке. Если кол-во процессов в списке больше некоторого предела, то процессы проваливаются сразу на след. ступеньку. Это немного ухудшает справедливость, но уменьшает starvation. | ||
| Строка 105: | Строка 105: | ||
Соответственно, выбор быстрый --- берётся самый левый элемент из дерева. Чуть медленнее включение --- логарифм. операция. | Соответственно, выбор быстрый --- берётся самый левый элемент из дерева. Чуть медленнее включение --- логарифм. операция. | ||
| - | Весь планировщик занимает строк 200. Старвейшена нет, интерактивность хорошая. Не зависит от тиков планировщика. | + | Весь планировщик занимает строк 200. Старвейшена нет,интерактивность хорошая. Не зависит от тиков планировщика. |
CFS включён в 2.6.23. | CFS включён в 2.6.23. | ||
