книги хакеры / журнал хакер / 108_Optimized
.pdf
|
|
|
|
hang |
e |
|
|
|
|
|
|
|
|
C |
|
E |
|
|
|||
|
|
X |
|
|
|
|
|
|||
|
- |
|
|
|
|
|
d |
|
||
|
F |
|
|
|
|
|
|
t |
|
|
|
D |
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
r |
||
P |
|
|
|
|
|
NOW! |
o |
|||
|
|
|
|
|
|
|
||||
|
|
|
|
|
BUY |
|
|
|||
|
|
|
|
to |
|
|
|
|
|
|
w Click |
|
|
|
|
|
m |
||||
|
|
|
|
|
|
|||||
w |
|
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
|
o |
|
|
. |
|
|
|
|
|
.c |
|
||
|
|
p |
|
|
|
|
g |
|
|
|
|
|
|
df |
|
|
n |
e |
|
||
|
|
|
|
-xcha |
|
|
|
|
Кря...Э-э-э,стоп. Чегоэтомыкрякаем? Мыжепингвины!
|
|
|
|
|
hang |
e |
|
|
|
|
|
|
|
|
C |
E |
|
|
|||
|
|
|
X |
|
|
|
|
|||
|
|
- |
|
|
|
|
d |
|
||
|
|
F |
|
|
|
|
|
t |
|
|
|
|
D |
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
r |
||
|
P |
|
|
|
|
NOW! |
o |
|||
|
>> unixoidto BUY |
|
|
|||||||
|
|
|
|
|
|
|||||
|
w Click |
|
|
|
|
|
m |
|||
|
w |
|
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
o |
|
|
|
. |
|
|
|
|
.c |
|
||
|
|
|
p |
|
|
|
g |
|
|
|
|
|
|
|
df |
|
n |
e |
|
||
|
|
|
|
|
-x cha |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
во всех современных дистрибутивах с ядром старше 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—самыйпростойпланировщик,потребляющий минимальноеколичестворесурсов.Онвыполняетпростыеоперации
Тестируем планировщик I/O
объединенияисортировки.Фактическиегореализацияпредставляетсобой очередьFIFO(FirstIn,FirstOut).Другимисловами,онпростовыставляет запросывочередьвтомпорядке,вкоторомонипришли.Восновном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
xàêåð 12 /108/ 07 |
099 |
|
|
|
|
hang |
e |
|
|
|
|
|
|
|
C |
E |
|
|
|||
|
|
X |
|
|
|
|
|||
|
- |
|
|
|
|
d |
|
||
|
F |
|
|
|
|
|
t |
|
|
|
D |
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
r |
||
P |
|
|
|
|
NOW! |
o |
|||
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|||
w Click |
to BUY |
>> unixoid |
|||||||
|
|
|
|
|
m |
||||
w |
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
o |
|
|
. |
|
|
|
|
.c |
|
||
|
|
p |
|
|
|
g |
|
|
|
|
|
|
df |
|
n |
e |
|
||
|
|
|
|
-xcha |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
hang |
e |
|
|
|
|
||
|
|
|
C |
|
E |
|
|
||||
|
|
X |
|
|
|
|
|
|
|||
|
- |
|
|
|
|
|
|
d |
|
||
|
F |
|
|
|
|
|
|
|
t |
|
|
|
D |
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
|
r |
||
P |
|
|
|
|
|
|
NOW! |
o |
|||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
BUY |
|
|
|||
|
|
|
|
to |
|
|
|
|
|
||
w Click |
|
|
|
|
|
m |
|||||
|
|
|
|
|
|
|
|||||
w |
|
|
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
|
|
o |
|
|
. |
|
|
|
|
|
|
.c |
|
||
|
|
p |
|
|
|
|
|
g |
|
|
|
|
|
|
df |
|
|
|
n |
e |
|
||
|
|
|
|
-x cha |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
Новые параметры сборки ядра
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) — планировщик дает выбранному процессу преимущество при доступе к диску без обращения внимания на работу других процессов. Доступно восемь уровней приоритета (0-7);
•2 (Best Effort) — класс, устанавливаемый по умолчанию для всех процессов; доступны те же восемь уровней приоритета;
•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). Когда тик становится равным нулю, процесс устанавливает флаг need_resched и тик пересчитывается. Кроме этого, каждый процесс имеет две очереди. В одной находятся готовые к запуску задачи, во вторую помещаются отработавшие и спящие задачи, которые, например, ожидают недоступный в настоящее время ресурс. Когда первая очередь пустеет, очереди меняются местами. Поэтому время работы алгоритма постоянно и не зависит от количества процессов. Современная реализация O(1) использует более сложные алгоритмы (например, анализируя среднее время сна), чтобы обнаружить интерактивные процессы и постараться задержать их в активном дереве. В ядро 2.6.23 в качестве основного был включен планировщик CFS (Completely Fair Scheduler — абсолютно справедливый планировщик), над
100 |
xàêåð 12 /108/ 07 |
|
|
|
|
hang |
e |
|
|
|
|
|
|
|
|
C |
|
E |
|
|
|||
|
|
X |
|
|
|
|
|
|||
|
- |
|
|
|
|
|
d |
|
||
|
F |
|
|
|
|
|
|
t |
|
|
|
D |
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
|
r |
||
P |
|
|
|
|
|
NOW! |
o |
|||
|
|
|
|
|
|
|
||||
|
|
|
|
|
BUY |
|
|
|||
|
|
|
|
to |
|
|
|
|
|
|
w Click |
|
|
|
|
|
m |
||||
|
|
|
|
|
|
|||||
w |
|
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
|
o |
|
|
. |
|
|
|
|
|
.c |
|
||
|
|
p |
|
|
|
|
g |
|
|
|
|
|
|
df |
|
|
n |
e |
|
||
|
|
|
|
-xcha |
|
|
|
|
|
|
|
|
hang |
e |
|
|
|
|
|
|
|
C |
E |
|
|
|||
|
|
X |
|
|
|
|
|||
|
- |
|
|
|
|
d |
|
||
|
F |
|
|
|
|
|
t |
|
|
|
D |
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
r |
||
P |
|
|
|
|
NOW! |
o |
|||
>> unixoidto BUY |
|
|
|||||||
|
|
|
|
|
|||||
w Click |
|
|
|
|
|
m |
|||
w |
|
|
|
|
|
|
|
|
|
|
w |
|
|
|
|
|
|
o |
|
|
. |
|
|
|
|
.c |
|
||
|
|
p |
|
|
|
g |
|
|
|
|
|
|
df |
|
n |
e |
|
||
|
|
|
|
-x cha |
|
|
|
|
которым работает Инго Молнар. В нем для хранения процессов используется 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, в марте анонсировал совер-