Позови пингвина на планерку

Владимир «turbina» Ляшко (v.turbina@gmail.com)

Хакер, номер #108, стр. 108-098-1

Знакомимся с планировщиками Linux

Сердцем любой операционной системы является ядро, от реализаций имеющихся функций в котором зависит очень многое. Это не только поддержка разнообразных устройств и файловых систем, но и распределение системных ресурсов. А так как требования, предъявляемые к планированию ресурсов, на каждом десктопе/сервере/марштутизаторе/мобильнике с Linux существенно отличаются, разработчики наперебой предлагают планировщики, альтернативные штатным.

Планировщики ввода/вывода

В любой системе можно выделить два типа планировщиков: планировщики ввода/вывода и планировщики процессорного времени. Начнем по порядку. Планировщики ввода/вывода (I/O scheduler) являются интерфейсом между блочными устройствами и драйверами низкого уровня. Задача такого планировщика - оптимальным образом обеспечить доступ процесса к запрашиваемому дисковому устройству. Не смотря на кажущуюся простоту вопроса, это настоящая проблема. Ведь работа с дисками относится к очень медленным операциям, поэтому алгоритм I/O шедулера должен обеспечивать решение часто противоречивых задач:

• минимизация времени поиска информации на диске;
• выдача информации в соответствии с приоритетом;
• гарантия получения данных приложению за определенное время и в нужном количестве.

Многократное переключение между задачами приводит к тому, что головка диска большую часть времени просто переходит на разные позиции. Именно поэтому в последнее время используются так называемые конвейерные (elevator) механизмы, в которых данные считываются не в порядке поступления запроса (вроде FIFO, LIFO и других), а с ближайших секторов.

Планировщик ввода/вывода ядра 2.4 использует один сложный конвейер общего назначения. Хотя он и имеет достаточное количество параметров, позволяющих управлять временем ожидания запроса в очереди, его возможностей часто не хватает для более тонкой настройки под специфические задачи. После многочисленных дискуссий, экспериментов и патчей в ядро 2.6 было включено 4 разных планировщика ввода/вывода, и теперь пользователь, в зависимости от конкретных задач, может подобрать себе наиболее оптимальный. Чтобы узнать, какие планировщики I/O включены в ядро, достаточно ввести команду:

$ dmesg | grep schedule

[1.348000] io scheduler noop registered

[1.348000] io scheduler anticipatory registered

[1.348000] io scheduler deadline registered

[1.348000] io scheduler cfq registered (default)

Как видишь, в моем KUbuntu присутствуют все четыре. Алгоритм CFQ отмечен как используемый по умолчанию, причем, так обстоят дела практически во всех современных дистрибутивах с ядром старше 2.6.18. Поэтому с него и начнем наше знакомство.

Completely Fair Queuing (CFQ) появился как расширение к SFQ (stochastic fair queuing) - планировщику, предназначенному для работы с сетевыми пакетами. CFQ был включен в ядро 2.6.6 в апреле 2004. В CFQ (и SFQ) для каждого процесса поддерживается своя очередь ввода/вывода, а задача планировщика состоит в том, чтобы как можно равномерней распределять доступную полосу пропускания между всеми запросами. Поэтому CFQ идеально подходит для тех случаев, когда множество программ требуют доступ к диску, а также для многопроцессорных систем, где требуется сбалансированная работа подсистемы ввода/вывода с различными устройствами. За период развития ядра 2.6 алгоритм CFQ несколько раз совершенствовался, и сегодня доступна его четвертая версия. В ней применен принцип time slice, аналогичный используемому в планировщике процессов, поэтому он стал несколько похож на Anticipatory. Время, выдаваемое каждому процессу на работу с устройством, и число запросов теперь зависят и от приоритета.

Планировщик NOOP - самый простой планировщик, потребляющий минимальное количество ресурсов. Выполняет простые операции объединения и сортировки. Фактически его реализация представляет собой очередь FIFO (First In, First Out), другими словами, он просто выставляет запросы в очередь в том порядке, в котором они пришли. В основном NOOP используется для работы с "не дисковыми" устройствами (например, ОЗУ или флешками) или со специализированными решениями, имеющими свой собственный планировщик I/O и требующими минимальной помощи ядра. В этом случае применение NOOP уменьшает нагрузку на процессор, а его простота имеет преимущество перед остальными планировщиками.

Задача алгоритма Deadline - минимизация задержек ввода/вывода и обеспечение поведения, близкого к реальному времени. Для улучшения производительности планировщик использует алгоритм предельного срока, постоянно переупорядочивая запросы. Суть алгоритма заключается в том, что операциям чтения всегда отдается предпочтение перед операциями записи. По умолчанию операция чтения будет выполнена максимально через 500 мс, записи - через 5 с. Из очереди извлекается следующий процесс, который и получает практически монопольный доступ к ресурсу, затем он переводится в состояние ожидания, а планировщик выбирает следующую программу. Появившись в 2002 году, этот алгоритм сразу был включен в стабильную ветку ядра. Deadline больше подходит для систем, где количество считываемой информации превосходит количество записываемой, например, базы данных или веб-сервер. При больших последовательных операциях чтения этот планировщик превосходит CFQ. Теоретически для десктопа он подходит меньше, так как пока один процесс пользуется диском, все остальное практически замирает. Хотя если ты любишь слушать музыку и смотреть фильмы, а жесткий диск не самый быстрый, то, вероятно, стоит внимательно присмотреться к этому алгоритму.

В планировщике Anticipatory (упреждающий конвейер), который основан на Deadline, пытаются минимизировать перемещение головки по диску. Для этого перед запросом вводится управляемая задержка. Таким образом достигается переупорядочение и объединение операций обращения к диску. Поэтому есть вероятность того, что предыдущий запрос успеет получить нужные данные до того, как головка диска будет вынуждена перейти на новый сектор. Однако результатом работы Anticipatory может быть увеличение времени задержки выполнения операций ввода/вывода, поэтому его лучше всего использовать на клиентских машинах с медленной дисковой подсистемой, для которых более важна интерактивность работы, чем задержки ввода/вывода. Этот алгоритм использовался по умолчанию в ядрах 2.6.0 – 2.6.17. Кстати, при его использовании в некоторых ситуациях веб-сервер Apache показывал большую производительность (на 50%), чем с остальными алгоритмами.

Чтобы увидеть все алгоритмы в новом ядре при самостоятельной пересборке, не забудь включить следующие параметры:

$ grep IOSCHED .config

CONFIG_IOSCHED_NOOP=y

CONFIG_IOSCHED_AS=y

CONFIG_IOSCHED_DEADLINE=y

CONFIG_IOSCHED_CFQ=y

CONFIG_DEFAULT_IOSCHED="cfq"

Как ты понимаешь, последний параметр определяет алгоритм, который будет использоваться по умолчанию. В ядрах до версии 2.6.18 дефолтным стоял anticipatory.

Переключить один планировщик на другой очень просто. Для этого следует добавить параметр elevator, передаваемый ядру при загрузке, с указанием алгоритма - as, deadline, noop или cfq. Хотя для эксперимента можно изменить алгоритм на лету, записав в файл /sys/block/<block_device>/queue/scheduler нужную строку:

$ cat /sys/block/sda/queue/scheduler

noop anticipatory deadline [cfq]

Меняем CFQ на Anticipatory:

$ echo anticipatory > /sys/block/sda/queue/scheduler

Выбранный планировщик вступит в действие не сразу, а через некоторое время. С выходом CFQ v3 в Linux 2.6.13 появилась возможность выставлять для процессов приоритеты использования дисковой подсистемы, чего раньше не хватало. Подобно утилите nice, которая используется для назначения приоритетов использования процессора, приоритеты ввода/вывода указываются при помощи ionice. В Ubuntu она входит в пакет schedutils. Синтаксис команды прост:

ionice -c класс -n приоритет -p PID

Приоритет - число от 0 до 7 (меньшее соответствует большему приоритету). В позиции "класс" возможны три значения:

• 1 (Real time) – планировщик дает выбранному процессу преимущество при доступе к диску, без обращения внимания на работу других процессов. Доступно 8 уровней приоритета [0-7];
• 2 (Best Effort) – класс, устанавливаемый по умолчанию для всех процессов, доступны те же 8 уровней приоритета;
• 3 (Idle) - получает право на использование жесткого диска только в том случае, если другая программа не требует диск, приоритеты на этом уровне не используются.

Вместо PID можно указать имя процесса:

$ sudo ionice -c2 -n0 xine

Для эксперимента запустим программу тестирования dbench с имитацией работы 50 клиентов: «dbench -t 60 50». Получаем CFQ – 88,02 Мб/с, Anticipatory – 81,14 Мб/с, Deadline – 134,66 Мб/с, NOOP – 63,15 Мб/с. Результат понятен и без комментариев, но однозначно сказать, какой алгоритм лучше, довольно сложно. Хотя Deadline и обогнал все остальные, попробуй в это время запустить Amarok или сохранить скрин, придется чуток подождать.

Планировщики процессов

Второй важной задачей по обеспечению нормальной работы любого сервиса, помимо доступа к дисковым устройствам, является доступ к процессору. За распределение процессорного времени между работающими приложениями отвечают другие планировщики. На первый взгляд, это простая задача, но так как на современных компьютерах могут выполняться сотни, а то и тысячи процессов, неправильная его реализация может снизить общую производительность системы (учти, что даже на переключение контекста процесса тратится драгоценное и, причем, не малое время). Кроме того, планировщик постоянно сталкивается с такой проблемой, как ограниченное время ответа для критических задач, рьяно борющихся за CPU.

Долгое время в Linux присутствовал один шедулер - O(1). Да, были и другие предложения, вроде Staircase от Кона Коливаса (sched-staircase-17.1.patch), и Fairsched (sf.net/projects/fairsched), в котором процессы разбиты на группы, а стандартный планировщик гарантирует распределение времени в зависимости от веса группы. Но все они не попадали в основную ветку ядра. Сегодня наметилась явная активность разработчиков в этом направлении. Сообщения о новых реализациях появляются на Kerneltrap чуть ли не ежемесячно.

Стандартному планировщику O(1) в этом году исполнилось 15 лет. В июле 1993 года Линус Торвальдс описал принцип работы планировщика задач Linux. Оригинальный файл sched.c содержал всего 254 строк кода, это был простой и понятный алгоритм. В 1996 году в нем было уже более 6000 строк - Дэйв Грот устранил проблему с семафорами и SMP системами. 2002 год был отмечен появлением "ultra-scalable O(1) scheduler" от Инго Молнара. В настоящее время sched.c содержит уже более 7000 строк.

Алгоритм работы O(1) очень прост. Каждая задача имеет фиксированное число (tick), которое пересчитывается с каждым системным тиком (по умолчанию 100 Hz) при выходе из режима ядра или при появлении более приоритетной задачи. Алгоритм делит число на 2 и добавляет базовую величину (по умолчанию 15, с учетом величины nice). Когда тик становится равным 0, процесс устанавливает флаг need_resched, и тик пересчитывается. Кроме этого, каждый процесс имеет две очереди. В одной находятся готовые к запуску задачи, во вторую помещаются отработавшие и спящие задачи, которые, например, ожидают не доступного в настоящее время ресурса. Когда первая очередь пустеет, очереди меняются местами. Поэтому время работы алгоритма постоянно и не зависит от количества процессов. Современная реализация O(1) использует более сложные алгоритмы (например, анализируя среднее время сна), чтобы обнаружить интерактивные процессы и постараться задержать их в активном дереве.

В ядро 2.6.23 в качестве основного был включен планировщик CFS (Completely Fair Scheduler, абсолютно справедливый планировщик), над которым работает Инго Молнар. В нем для хранения процессов используется red-black дерево, где ключом является значение wait_runtime каждого процесса. Эта переменная определяет количество наносекунд, которое переработал или недоработал процесс. В зависимости от этого значения процесс и получает свое место в дереве. В CFS используются наносекунды, а не time slices или тики, в его работе нет никакой эвристики. Извлечение процесса и его вставка в дерево требует перестройки, что при большом количестве процессов приводит к увеличению накладных расходов. Поэтому CFS рекомендуется в первую очередь для десктопов, где нет большого количества одновременно запущенных процессов. В отличие от O(1), CFS равномернее планирует процессорное время (фактически если задачи две, то каждая получит ровно 50% CPU), распределяет задачи по нескольким ядрам и имеет меньшее время отклика. Для настройки CFS используется файл /proc/sys/kernel/sched_granularity_ns, в котором по умолчанию установлен режим desktop (меньшее время задержки), но при необходимости его можно переключить в server, обеспечив лучшую группировку.

Патч CFS для ядер >=2.6.20 можно взять по адресу people.redhat.com/mingo/cfs-scheduler. Далее качаем сырцы ядра и накладываем патч (обрати внимание, что v22 отражает версию патча CFS, планировщик сейчас находится в постоянном развитии, поэтому следует выбирать последнюю доступную версию):

$ cd /usr/src/linux

$ patch -p1 < ~/sched-cfs-v2.6.22.9-v22.patch

Стоит отметить появление новых параметров:

CONFIG_FAIR_GROUP_SCHED=y

CONFIG_FAIR_USER_SCHED=y

CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER=y

CONFIG_SCHED_DEBUG=y

После конфигурирования собираем ядро обычным образом.

Утилита hackbench (developer.osdl.org/craiger/hackbench/src/hackbench.c), которая измеряет скорость создания указанного числа процессов и скорость обмена данных между ними, со стандартным планировщиком показывает результат 6,5, а с CFS - 5,9. Но если эти цифры тебе ничего не говорят, приведу такой пример. После запуска теста contest (он есть в репозитарии Ubuntu) при использовании O(1) Amarok загружался минуты две, и музыка постоянно прерывалась, а при CFS – Amarok запустился и работал, как ни в чем не бывало.

Кон Коливас, остановив разработку ветки ck, в марте анонсировал совершенно новый планировщик RSDL (Rotating Staircase DeadLine scheduler), который в последствии был переименован в SD (Staircase Deadline, ck.kolivas.org/patches/staircase-deadline). За его основу был взят Staircase. Задача нового планировщика - исключить зависания, присущие O(1). Здесь все процессы равны, каждому выделяется своя квота, исчерпав которую, он опускается на следующий уровень приоритета, где получает новую квоту. Причем каждый уровень также имеет свою квоту, если ее исчерпает хотя бы один процесс, все перейдут на следующий уровень, вне зависимости от того, отработали ли они свою квоту, или нет. Планировщик также пытается определить интерактивные процессы, автоматически повышая им приоритет. Версия SD показывала неплохие результаты на серверах, и поговаривали, что этот планировщик будет включен в основную ветку, начиная с 2.6.22, но из-за проблем со здоровьем Кона разработка шла относительно медленно, и Инго Молнар обогнал соперника.

Посетовав на сложность CFS, Роман Зиппель представил рабочий прототип базового алгоритма нового планировщика RFS (Really Fair Scheduler, kerneltrap.org/RFS), который помещает задачу в виртуальную (нормализованную) временную линию, где имеет значение только относительное расстояние между двумя любыми задачами. После жарких споров в ответ на этот прототип Инго Молнар представил свою версию, которую он назвал RSRFS (Really Simple Really Fair Scheduler), реализованную поверх CFS и включающую алгоритм из RFS.

За последние 2,5 года было предложено около 300 различных алгоритмов, так что в ближайшее время на этом фронте вряд ли будет спокойно :).

Проект DeskOpt

Интересный проект был представлен в списке рассылки разработчиков ядра Linux. Программа DeskOpt (www.stardust.webpages.pl/files/tools/deskopt) представляет собой демон, написанный на языке высокого уровня Python, который отслеживает запускаемые пользователем приложения и автоматически выбирает оптимальные параметры работы планировщика процессов CFS и планировщика ввода/вывода (CFQ, anticipatory, deadline). Все настройки осуществляются путем редактирования конфигурационного файла, в котором по умолчанию описано три класса оптимизации: игры, просмотр видео и прослушивание музыки. DeskOpt легко устанавливается и, судя по тестам, дает прирост производительности, особо ощутимый в играх.

ВИДЕО К ЭТОМУ НОМЕРУ

Под знаком VoIP
Часто компания имеет несколько офисов, удаленных друг от друга. Использовать только один сервер телефонии в таком случае очень накладно. Кроме того, нельзя забывать о том, что в настоящее время существует достаточно сервисов, предлагающи...

Фокусы с UPX
это простое видео иллюстрирует выполнение двух очень часто встречающихся в работе крэкера задач. первая задача - это установка точки останова на функцию, принимающую текст, введенный пользователем (в нашем случае текстом был серийный ном...

Взлом Борландии
Демонстрация использования утилиты DEDE, предназначенной для исследования программ, использующих библиотеку VCL от Borland. В качестве подопытного кролика выступает Etlin HTTP Proxy, а за штурвалом сидит опытный хакер и рулит с ультрафи...

Страж файлового дерева
Сегодня уже трудно кого-либо удивить разветвленными сетями со сложной топологией, наличием удаленных и мобильных офисов. Для администратора организация любого сервиса в таких условиях - дело непростое. Но не нужно забывать и о наших поль...

Футбольный XSS
В этом ролике ты увидишь, как хакер находит XSS-багу на сайте известного немецкого футбольного клуба. После чего, заливает на один из своих веб-шеллов php-снифер. Затем взломщик пишет маленький js-скрипт, который внедряет в страницу на а...

Предыдущие номера