Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Полностью честный планировщик
Автор (ы) оригиналаИнго Мольнар
Разработчики)Разработчики ядра Linux
Написано вC
Операционная системаЯдро Linux
Типпланировщик процессов
ЛицензияGPL-2.0
Интернет сайтядро .org
Расположение «Completely Fair Scheduler» (планировщика процессов) в упрощенной структуре ядра Linux.

Completely Fair Scheduler ( CFS ) представляет собой процесс планировщик , который был слит в 2.6.23 (октябрь 2007) выпуск Linux ядра и планировщик по умолчанию. Он обрабатывает выделение ресурсов ЦП для выполнения процессов и нацелен на максимальное использование ЦП в целом, а также на максимальную интерактивную производительность.

В отличие от предыдущего планировщика O (1), который использовался в старых ядрах Linux 2.6, реализация планировщика CFS не основана на очередях выполнения . Вместо этого красно-черное дерево реализует «временную шкалу» будущего выполнения задачи. Кроме того, планировщик использует учет наносекундной детализации, то есть атомарные единицы, с помощью которых выделялась отдельная доля процесса в ЦП (что делает излишним предыдущее понятие временных интервалов). Это точное знание также означает, что не требуется специальных эвристик, например , для определения интерактивности процесса. [1]

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

Алгоритм [ править ]

Структура данных, используемая для алгоритма планирования, представляет собой красно-черное дерево, в котором узлы являются sched_entityструктурами, зависящими от планировщика . Они получены из общего task_structдескриптора процесса с добавленными элементами планировщика.

Узлы индексируются по « времени выполнения » процессора в наносекундах. [2]

« Максимальное время выполнения » также рассчитывается для каждого процесса, чтобы представить время, которое процесс ожидал бы для работы на «идеальном процессоре». Это время ожидания процесса, деленное на общее количество процессов.

Когда планировщик вызывается для запуска нового процесса:

  1. Выбирается крайний левый узел дерева планирования (так как у него будет наименьшее затраченное время выполнения ) и отправляется на выполнение.
  2. Если процесс просто завершает выполнение, он удаляется из системы и дерева планирования.
  3. Если процесс достигает максимального времени выполнения или останавливается иным образом (добровольно или посредством прерывания), он повторно вставляется в дерево планирования на основе его нового затраченного времени выполнения .
  4. Затем новый крайний левый узел будет выбран из дерева, повторяя итерацию.

Если процесс проводит большую часть своего времени в спящем режиме, то значение затраченного времени является низким, и он автоматически получает повышение приоритета, когда ему наконец это нужно. Следовательно, такие задачи получают не меньше процессорного времени, чем задачи, которые постоянно выполняются.

Планировщик CFS с справедливой организацией очередей имеет сложность планирования O ( журнал N), где N - количество задач в очереди выполнения . Выбор задачи может быть выполнен за постоянное время, но для повторной вставки задачи после ее выполнения требуется O (log N) операций, поскольку очередь выполнения реализована в виде красно-черного дерева .

История [ править ]

Работа Кон Коливаса с составлением расписания, в первую очередь его реализация « справедливого расписания » под названием « Крайний срок по вращающейся лестнице» , вдохновила Инго Мольнара на разработку своего CFS в качестве замены более раннему планировщику O (1) , указав Коливаса в своем заявлении. [3] CFS - это реализация хорошо изученного классического алгоритма планирования, называемого взвешенной справедливой очередью . [4] Справедливая организация очереди, первоначально изобретенная для пакетных сетей , ранее применялась к планированию ЦП под названием « планирование шага» . CFS - первая реализация планировщика процессов справедливой организации очередей.широко используется в операционных системах общего назначения. [4]

В ноябре 2010 года ядро ​​Linux получило исправление для CFS для ядра 2.6.38, которое сделало планировщик более справедливым для использования на настольных компьютерах и рабочих станциях. Патч, разработанный Майком Гэлбрейтом с использованием идей, предложенных Линусом Торвальдсом , реализует функцию, называемую автогруппированием, которая значительно повышает производительность интерактивного рабочего стола. [5] Алгоритм помещает родительские процессы в ту же группу задач, что и дочерние процессы. [6] (Группы задач привязаны к сеансам, созданным с помощью setsid()системного вызова. [7] ) Это решило проблему медленного интерактивного времени отклика на многоядерных и многопроцессорных системах ( SMP) системы, когда они выполняли другие задачи, которые используют много потоков, интенсивно использующих ЦП в этих задачах. Простое объяснение состоит в том, что с применением этого патча можно будет по-прежнему смотреть видео, читать электронную почту и выполнять другие типичные действия на рабочем столе без сбоев или прерываний, например, при компиляции ядра Linux или кодировании видео.

В 2016 году планировщик Linux был исправлен для улучшения многоядерной производительности на основе предложений, изложенных в документе «Планировщик Linux: десятилетие потраченных впустую ядер». [8]

См. Также [ править ]

  • Планировщик Brain Fuck
  • SCHED_DEADLINE

Ссылки [ править ]

  1. ^ Эндрюс, Джереми (2007-04-18). «Linux: полностью честный планировщик» . KernelTrap . Архивировано из оригинала на 2007-04-19.
  2. ^ Описание CFS на ibm.com
  3. ^ Молнар, Инго (2007-04-13). «[патч] Ядро модульного планировщика и полностью справедливый планировщик [CFS]» . linux-kernel (список рассылки).
  4. ^ a b Li, T .; Baumberger, D .; Хан, С. (2009). «Эффективное и масштабируемое многопроцессорное справедливое планирование с использованием распределенного взвешенного циклического перебора» (PDF) . Уведомления ACM SIGPLAN . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . DOI : 10.1145 / 1594835.1504188 .  
  5. ^ Патч ядра Linux ~ 200 строк, который творит чудеса
  6. ^ Гэлбрейт, Майк (2010-11-15). «[RFC / RFT PATCH v3] Re: [RFC / RFT PATCH v3] sched: автоматические группы задач для каждого tty [CFS]» . linux-kernel (список рассылки).
  7. ^ Гэлбрейт, Майк (2010-11-20). «[PATCH v4] sched: автоматические группы задач для сеанса» . linux-kernel (список рассылки).
  8. ^ Лози, Жан-Пьер; Прокаженный, Батист; Фанстон, Джастин; Гауд, Фабьен; Кема, Вивиан; Федорова, Александра. «Планировщик Linux: десятилетие потраченных зря ядер» (PDF) . EuroSys 2016 . Проверено 15 июня 2019 .

Внешние ссылки [ править ]

  • Корбет, Джонатан (17 апреля 2007 г.). «Планировщики: сюжет сгущается» . LWN.net . Архивировано из оригинала на 2017-09-06 . Проверено 21 июля 2016 .
  • Корбет, Дж. (2007-07-02). «Планирование группы CFS» . LWN.net. Архивировано из оригинала на 2017-09-06 . Проверено 21 июля 2016 .
  • Корбет, Дж. (16 октября 2007 г.). «Справедливое планирование пользователей и другие исправления планировщика» . LWN.net. Архивировано из оригинала на 2017-06-12 . Проверено 24 ноября 2016 .
  • Корбет, Дж. (17 ноября 2010 г.). «Групповое планирование на основе телетайпа» . LWN.net. Архивировано из оригинала на 2018-05-21 . Проверено 24 ноября 2016 .
  • Корбет, Дж. (06.12.2010). «Групповое планирование и альтернативы» . LWN.net. Архивировано из оригинала на 2017-06-11 . Проверено 24 ноября 2016 .
  • Сингх Пабла, Чандандип (1 августа 2009 г.). «Полностью честный планировщик» . linuxjournal.com . Архивировано из оригинала на 2018-03-18 . Проверено 17 ноября 2014 .
  • Джонс, Тим (15 декабря 2009 г.). «Внутри Linux 2.6 полностью честный планировщик» . ibm .
  • Лози, Жан-Пьер (2016-04-21). «Планировщик Linux: десятилетие потраченных зря ядер» (PDF) . ACM . Архивировано из оригинального (PDF) 05 февраля 2018 года . Проверено 24 ноября 2016 .