7.2.4 Время работы планировщика

Как уже обсуждалось ранее, продолжительность времени работы планировщика представляет собой время, затраченное планировщиком на выбор следующей задачей для выполнения и на переключение на неё контекста. Планировщик Linux, как и остальная часть системы, был изначально написан для настольного ПК и оставался почти неизменным, за исключением добавления возможностей реального времени POSIX. Основным недостатком планировщика было его недетерминированное поведение: длительность работы планировщика линейно возрастала с увеличением числа задач в системе по причине того, что все задачи, в том числе задачи реального времени, содержались в одной очереди выполнения и каждый раз, когда вызывался планировщик, он проходил через всю очередь выполнения, чтобы найти задачу с наивысшим приоритетом. Этот цикл называется полезным циклом. Кроме того, когда квант времени всех исполняемых процессов истекает, он заново перерасчитывает их новые временные интервалы. Этот цикл известен как цикл перерасчёта. Чем больше количество задач (независимо от того, являются ли они задачами реального времени или нет), тем больше было время, затрачиваемое планировщиком в обоих этих циклах.

Создание планировщика реального времени: планировщик O(1)

В ядро версии 2.4.20 был введён планировщик O(1), который внёс детерминизм. Планировщик O(1) от Инго Молнара является превосходным куском кода, который пытается решить проблемы задачи составления расписания работы от больших серверов, стараясь сбалансировать нагрузку, вплоть до встраиваемых систем, которым требуется детерминированное время планирования. Как следует из названия, для перерасчёта интервалов времени процессов и их перепланирования, планировщик выполняет расчёт O(1), вместо прежнего O(n) (где n обозначает количество процессов в очереди выполнения). Он делает это с помощью двух массивов: массива активных задача и массива закончивших работу задач. Оба массива упорядочены по приоритету и они поддерживают отдельные очереди выполнения для каждого приоритета. Индексы массивов хранятся в битовом виде, так что поиск наиболее приоритетной задачи становится операцией поиска O(1). Когда задача исчерпывает свой квант времени, она перемещается в массив закончивших работу задач и переопределяется её новый квант времени. Когда массив активных задач становится пустым, планировщик переключает оба массива, так что массив закончивших работу задач становится новым массивом активных задач и начинается планирование из нового массива. Обращение к очереди активных и  закончившихся задач происходит с помощью указателей, так что переключение между двумя массивами означает просто переключение указателей.

Таким образом, наличие упорядоченных массивов решает проблему полезного цикла, а переключение между указателями решает проблему цикла перерасчёта. Наряду с этими, планировщик O(1) предлагает давать более высокий приоритет интерактивным задачам. Хотя это более полезно для среды настольного ПК, системы реального времени, выполняющие смесь из процессов реального времени и обычных процессов, тоже могут извлечь выгоду из этой возможности. Рисунок 7.2 показывает планировщик O(1) в упрощённом виде.

Рисунок 7.2 Упрощённый вид планировщика O(1).

Время переключения контекста

Измерение времени переключения контекста в Linux было любимым времяпрепровождением для энтузиастов режима реального времени Linux. Как сделать его в Linux сопоставимым с временем переключения контекста коммерческих RTOS? Поскольку переключение контекста осуществляется планировщиком, оно влияет на продолжительность работы планировщика и, следовательно, время отклика ядра. Объектами для планирования в Linux являются:

▪Потоки ядра: они проводят время своей жизни только в режиме ядра. Они не имеют памяти, отображённой в пространство пользователя.

▪Пользовательские процессы и пользовательские потоки: потоки пользовательского пространства совместно используют общее пространство для текста, данных и "кучи". Они имеют отдельные стеки. Другие ресурсы, такие как открытые файлы и обработчики сигналов, также являются общими для всех потоков.

При принятии решений о планировании планировщик не делает различия между любыми из этих объектов. Время переключения контекста меняется, когда планировщик пытается переключить процессы вместо потоков. Переключение контекста в основном заключается в следующем:

▪Переключение на новый набор регистров и стек ядра: это время переключения контекста является общим для потоков и процессов.

▪Переключение с одной виртуальной области памяти для другую: это необходимо для переключения контекста между процессами. Оно явно или неявно приводит к перезагрузке TLB (или таблиц страниц) новыми значениями, что является дорогостоящей операцией.

Значения времени переключения контекста варьируются в зависимости от архитектуры. Измерение времени переключения контекста осуществляется с помощью программы lmbench. Для получения более подробной информации о LMBench™ посетите, пожалуйста, www.bitmover.com/lmbench/.