ЭВОЛЮЦИЯ ПЛАНИРОВЩИКОВ ЗАДАЧ В ОПЕРАЦИОННОЙ СИСТЕМЕ LINUX
Степанов А.В., г. Москва
Последние достижения в компьютерном мире и коммуникационных технологиях привели к появлению широкого круга прикладных приложений с различными рабочими характеристиками. Современные операционные системы (ОС) общего назначения предоставляют возможность выполнять различные задачи, осуществляя, тем самым, поддержку различных информационных систем.
ОС Linux является ярким примером ОС общего назначения, используемой для обслуживания высокопроизводительных вычислительных комплексов, домашних рабочих станций и миниатюрных встраиваемых устройств. Эта ОС соответствует многим требованиям к обработке информации. Одним из таких требований является поддержка одновременного выполнения пользовательских и системных задач.
Ключевым моментом в обеспечении корректной работы ОС является планировщик выполнения задачмикропроцессорной техники вызывает сложные проблемы организации эффективного решения планирования. .
Архитектура планировщика в ОС Linux непрерывно изменялась. Рассмотрение эволюции планировщика задач данной ОС является необходимым для определения путей дальнейшего совершенствования механизмов выполнения программ. Исследованию этих вопросов посвящены отдельные работы таких ученых, как Таненбаум Э. С., Вудхалл А.С и др [5,6,7].
ОС Linux является открытой, что позволяет провести анализ текущих механизмов планирования и внедрить свой усовершенствованный алгоритм. ОС Linux можно использовать как базовую платформу для тестирования и внедрения усовершенствованного планировщика задач. Ниже приводится анализ разработок планировщиков задач за последнее десятилетие.
Основная задача планировщика состоит в выполнении максимального объёма работы в условиях ограничений.
Автором планировщика ОС Linux для ядер серии 2.6.x является Инго Молнар (Ingo Molnar) [10;11].
На вход планировщику поступает очередь задач, которую необходимо выполнить. Длина этой очереди определяет время работы планировщика ОС Linux ядер серии 2.4.x. но не 2.6.x серии.
0(n) - эта запись используется для отображения того факта, что с возрастанием количества входных данных, возрастает время работы самого планировщика.
0(1) - запись показывает что, время работы алгоритма константное. Алгоритм, который характеризуется 0(1), гарантирует завершиться за некий период времени вне зависимости от размера входящей очереди задач. Каждая часть такого алгоритма выполняется за некое константное время.
Работа планировщика ядра 2.6.x базируется на использовании следующих понятий:
Runqueue - очередь задач готовых к выполнению. Каждый ЦПУ имеет свою очередь задач.
Priority array - массив приоритетов. Очередь задач связана с двумя массивами приоритетов: один активный другой пассивный. Массивы приоритетов меняются местами, когда активный массив приоритетов опустошается. Задача массива приоритетов сводится к нахождению задачи с наибольшим приоритетом за константное время. Массив приоритетов представляет собой битовое поле, которое отображает приоритеты для активных задач.
Интерактивные кредиты - позволяют лучше распределять процессорное время между интерактивными задачами. Задача получает интерактивный кредит, когда долго спала, и наоборот, теряет интерактивный кредит, когда значительное время занимала ЦПУ.
Домен планирования (scheduler domain) - включает несколько вычислительных ресурсов. Каждый домен планировщика разделяет все свои доступные ЦПУ на группы. В многопроцессорной системе или одно процессорной системе каждый физический ЦПУ образует отдельную группу. Балансировка нагрузки происходит только внутри домена. Задачи перемещаются внутри домена между группами. Нагрузка группы равна нагрузке всех ЦПУ в этой группе. С целью предотвращения частых очисток кэша, каждая задача выполнятся на одном и том же ЦПУ. Тем не менее, иногда наступают моменты, когда некий ЦПУ имеет больше задач на выполнение чем другие ЦПУ в системе. Тогда планировщик пытается провести балансировку нагрузки, и равномерно распределить задачи между процессорами.
Классификации нитей является одним из ключевых мест работы планировщика ядра 2.6.x. Планировщик, для работы на пользовательских системах, ставит нитям В/В высокий приоритет доступа к ЦПУ. Это делается с целью повышения интерактивности. Без этого подхода, при большой нагрузке ЦПУ, в моменты больших вычислений, пользователь будет ощущать не достаточно быструю реакцию компьютера на свои действия.
Также известно, что нити В/В занимают много времени и их лучше запустить на выполнение как можно раньше. Например, программа, ожидающая данные из дискового накопителя, значительное время будет находиться в режиме ожидания, прежде чем она получи свои данные. Пока будут извлекаться данные из диска, ЦПУ сможет выполнить другую полезную работу.
Планировщик ОС Linux не делает различия между нитями которые работают с системой В/В, так не может знать, ожидает ли нить данных с клавиатуры или с дискового накопителя. Планировщик рассматривает все нити В/В одинаково.
Планировщик ядра ОС Linux 2.6.x позволяет приложениям реального времени (РВ) указывать очень жёсткие по времени предельные сроки выполнения (deadline), но не гарантирует их соблюдения. Под мягким планированием (soft RT scheduling) понимают, отсутствие гарантии, что задача будет выполнена к некоторому желаемому сроку (deadline).
Нити РВ выделяются в отдельный класс. Планировщик дает нитям РВ приоритет над всеми другими нитями в системе:
задачи РВ имеют приоритеты в диапазоне 0-99;
обычные задачи отображаются в диапазон 100-140.
Поскольку задачи РВ имеют приоритет "ниже" чем обычные задачи, они всегда вытесняют обычные задачи. В момент выполнения задач РВ, выполнения других задач невозможно. Это связано с тем, что задачи РВ работают с другими схемами планирования:
SCHED_FIFO
SCHED_RR
Обычные задачи маркируются как SCHED_NORMAL.
Планирование задач РВ по схеме SCHED_FIFO. Если процессор содержит SCHED_FIFO (First In First Out) задачу она вытесняет любую другую задачу и выполняется так долго, сколько ей необходимо. Такая задача не имеет ограничений по времени выполнения. Если в очереди задач несколько SCHED_FIFO задач, то планировщик распределит выполнение задач по приоритетам: задачи с более высоким приоритетом вытеснят задачи с более низким приоритетом.
Планирование задач РВ по схеме SCHED_RR. Механизм планирования SCHED_RR (Round-Robin) задач очень похож на планирование SCHED_FIFO задач. Отличие состоит в том что:
a) для каждой SCHED_RR задачи указано как много она может использовать процессорного времени (timeslice);
b) любая SCHED_RR задача будет безоговорочно вытеснена SCHED_FIFO задачей. SCHED_FIFO нити имеют более высокий приоритет, чем SCHED_RR нити.
SCHED_RR задачи планируются согласно своим приоритетам по кругу (round-robin). Задача, которая использовала отведённое ей процессорное время, помещается в конец очереди.
Каждая SCHED_RR задача согласно своему приоритету выполняется в течение отведённого ей процессорного времени, а потом заносится в конец списка очереди согласно своему приоритету (priority array queue).
Вначале файла kernel/sched.c определено несколько макросов. Изменяя определения этих макросов можно достичь желаемой работы планировщика.
Рассмотрим более раннюю реализацию планировщика ОС Linux в серии ядер 2.4.х. Он имеет надёжный дизайн. Но существует ряд нежелательных характеристик. Планировщик делит время на эпохи. Эпоха - период времени, за которое каждая задача может использовать своё процессорное время. В начале наступления новой эпохи для каждой задачи планировщик подсчитывает сколько времени она может выполнятся O(n) итераций.
Каждой задачи присваивается базовое значение в течении которого она может использовать ЦПУ. Это значение определяется пользователем с помощью утилиты nice. Установленное значение масштабируется в некое количество тактов микропроцессора. Значение 0 примерно масштабируется в 200 мили секунд.
Когда происходит подсчёт сколько процессорного времени выделить для задачи, это базовое значение может изменится в зависимости является ли задача В/В. Каждая задача имеет переменную counter. Эта переменная содержит количество оставшихся тактов микропроцессора. За всю эпоху, задача могла не использовать все выделенное ей процессорное время, т.е. значение переменной counter > 0. Это могло произойти например если задача спала находилась в ожидании операции В/В. Тогда в конце эпохи задаче будет выделено больше процессорного времени.
Когда задача порождает потомка, то, процессорное время родителя разделяется с потомком, что предотвращает захват ЦПУ размножением.
Функуия schedule() чтобы выбрать задачу для выполнения, вызывает функцию goodness(). Функция goodness() проверяет наличие задачи, которая может выполнится в текущем адресном пространстве (p->mm == prev->mm), и если есть, то ей отдаётся предпочтение.
Основные проблемы:
· Плохая масштабируемость (scalability) == 0(n). Планировщик назначает всем задачам приоритеты (цикл через все активные задачи).
· Планировщик ищет задачу с наивысшим приоритетом (также цикл через все задачи).
· Если существует 100 активных нитей, и одна нить с более низким приоритетом чем все остальные нити, то этой нити придётся ждать своего выполнения 20 сек: 200 мс * 100
· Если существует несколько интерактивных задач с более высоким приоритетом, обычные задачи будут голодать и долго ожидать времени выполнения. Пример: WEB-сервер получив данные c ресурса В/В будет очень долго формировать ответ.
Остановимся кратко на изложении дискуссионных моментов относительно предпринятых в последнее время попыток по совершенствованию планировщика задач. За последнее время эксплуатации ОС Linux были выявлены новые недостатки в текущей реализации работы планировщика, а также выдвинуты предложения по усовершенствованию подсистем планировщика и способы их осуществления.
Автор текущей реализации планировщика (2.6.x) Инго Молнар предложил полностью переписать подсистему планирования в ядре Linux. Тем не менее, Молнар заметил, что планировщик должен оставаться универсальным и пригодным для использования в пользовательских настольных системах и высокопроизводительных серверах.
Молнар предложил построить систему планирования по модульному принципу. Предполагается, что модули инкапсулируют (заключают) детали политики планирования. Базовая часть кода является инвариантной и представляет интерфейс, позволяющий подключать различные алгоритмы планирования.
Особенностью предложенного Молнаром подхода является то, что выбор алгоритма должен происходить на этапе компиляции ядра Linux.
В качестве базового модуля автор данной идеи предлагает использовать Completely Fair Scheduler (CFS) - полностью справедливый планировщик. Замысел алгоритма CFS вполне радикален: он не использует очередей задач (runqueues), а использует отсортированную во времени структуру Red Black Tree (сбалансированное красно-черное дерево). Эта структура используется для построения очередности выполнения задач. По заявлению автора, этот алгоритм избавлен недостатков текущего планировщика, источником которых были переключаемые массивы задач. Задачи помещаются в дерево согласно их приоритету (времени, оставшемуся от timeslice), и дерево постоянно перемешивается (подобно тому, как раньше массивы менялись местами). Алгоритм подсчитывает время, оставшееся от выделенного процессу на исполнение в данный интервал, что и является приоритетом.
Планировщик CFS использует наносекундный учет времени выполнения задач и не зависит от других рабочих характеристик ЦПУ, например его частоты.
Алгоритм CFS не учитывает процессорное время, выделенное задаче, или эвристические данные о потоке выполнения задач. Единственный способ управлять работой планировщика предусмотрен изменением параметра в файле /proc/sys/kernel/sched_granularity_ns. Таким образом, изменяя значение этого параметра, можно подстраивать функционирование ОС для работы в режиме:
сервера - задачи хорошо укомплектованы;
рабочей станции - минимальное время реакции на действия пользователя.
В любом случае, необходимые поправки, изменения, дополнения в работу алгоритма CFS можно внести в модуль sched_fair.c. Предполагается, что данный подход позволит упростить подсистему планирования.
Время работы алгоритма CFS оценивается в O(log(n)) по сравнению с O(1) в текущей реализации планировщика.
Модуль sched_rt.c содержит алгоритмы планирования для обслуживания выполнения задач в реальном времени. По заявлению автора, реализация механизма по обслуживанию задач реального времени по принципу SCHED_FIFO и SCHED_RR значительно упрощена. Используется только 100 очередей задач соответствующих каждому уровню приоритета (вместо 140 очередей в текущем ядре). Также, нет необходимости использовать массив для учета просроченных задач.