Отправляет email-рассылки с помощью сервиса Sendsay

Linux Gazette на русском

  Все выпуски  

Linux Gazette на русском


Информационный Канал Subscribe.Ru

[lg89]: Планировщик задач в Linux

Linux Gazette на русском | Выпуск #132 | Тираж 8596 экз.


"Зри в корень!!" (c) Козьма Прутков

Здравствуйте! Вашему вниманию предлагается статья, описывающая "проблемы, с которыми столкнулись разработчики ядра при создании нового планировщика, как эти проблемы были решены и в каком направлении предполагается развивать планировщик дальше".

Спасибо за перевод Андрею Киселёву!

А теперь разбор полётов. Статья "Работаем с XSLT." Своими мысялми решил поделится Valery A. Ilychev (sarutobi at pisem.net):

> XSLT (от англ. eXtensible Stylesheet Language for Transformations --
> Расширяемый Язык Стилей для Преобразований) используется, по большей
> части, для преобразования данных из формата XML в формат HTML. Однако,
> XSLT может использоваться для преобразования из XML (или любого другого
> формата, использующего пространство имен xml, подобно RDF) в любой другой
> формат, даже в простой текст.


-->
Не совсем верное утверждение относительно основного использования. XSLT
предназначен для быстрого преобразования произвольных документов в формате XML
в XML документ с требуемой структурой.
И еще. Поскольку достаточно большое число форматов представляет из себя
обычный текст с разметкой (RTF, TeX, HTML, и т.п.), то можно сказать,
что с помощью XSLT можно получить выходной документ, пригодный для
обработки в большинстве имеющихся приложений,
-->


> Консорциум W3 (http://www.w3.org) определяет три составные части языка XSL
> (от англ. eXtensible Stylesheet Language -- Расширяемый Язык Стилей): XSLT, XPath
> (http://www.w3.org/TR/xpath)
> (язык путей и выражений, используемый в XSLT для доступа к отдельным
> частям XML-документа) и XSL Formatting Objects -- словарь, определяющий
> семантику форматирования документов.

-->
составные части XSL:
XSLT - расширяемый язык разметки. Отвечает за преобразование входного
документа.
XPath - язык, предназначенный для обращения к частям XML-документа,
проводить выборки и основные вычисления.
Что же касается XSL Formatting Objects - возможно, это только
рекомендация w3.org, так как в описании стандарта 1.0 мне эта часть не
попалась.
-->

> Прежде всего следует указать, что наш документ использует стилистику XML и
> импортировать пространство имен XML:
>
>     xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
>...
>

-->
Также в этом месте можно включить некоторые дополнительные возможности,
предоставляемые XSLT - определить тип выходного документа и
необходимость вывода XML-заголовка:


method может быть одним из трех вариантов - text, xml и html. Возможно,
в будущем w3.org добавит другие типы. Этот параметр влияет на способ
формирования выходного документа (например, нужно ли делать замены
"<" на "<")
omit-xml-declaration определяет, будет ли в начале каждого
результирующего документа выводиться строка
 ("no") или эту строку выводить не
нужно("yes").
-->

> Далее, основным элементом, который мы будем использовать, является
> xsl:template match. Этот элемент вызывается всякий раз, когда имя xml-узла
> совпадает со значением атрибута xsl:template match:

-->
XSLT предоставляет два способа определения правила шаблонного
преобразования:
xsl:template match и xsl:template name
Их можно назвать "условным" и "безусловным" определением шаблона. Первый
из них срабатывает, если название обрабатываемого элемента совпадает с
выражением, указанным в match. Для его вызова применяется инструкция

Второй вызывается по имени с помощью инструкции  и срабатывает всегда, независимо от названия
обрабатываемого элемента.
-->

><xsl:stylesheet version="1.0"
>                  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
>
><xsl:template match="/"> <!-- оператор '/' взят из XPath и -->
> <!-- ассоциируется с корневым элементом -->
>    <!-- выполнить какие либо действия с вложенными узлами -->
></xsl:template>
>
></xsl:stylesheet>

-->
xsl:template match="/" является аналогом функции main() в C/C++ и
применяется практически всегда. разбор документа начинаестя именно с
этого правила.
-->

> Внутри элемента xsl:template match следует указать вложенные узлы
> элементом: xsl:value-of select.

-->
Некорректное утверждение. Внутри элемента xsl:template можно указать
почти все допустимые с точки зрения xsl узлы. В данном случае автор
использует xsl:value-of select, возвращающее содержание узла, указанного в
select
-->

>      <title> <xsl:value-of select="//text"/> </title>
>    </head>
>
>    <body>
>       <p>
> Содержимое узла <b>text</b> корневого
> элемента: <b><xsl:value-of select="//text"/></b>

-->
В данном случае лучше было бы определить переменную, а не дважды
вычислять одно и то же выражение XPath
-->

> Получение значений атрибутов
> конструкция @att возвращает значение атрибута att. Например:

-->
Безо всяких переходов начали объяснять XPath.
С помощью этого языка возможно обращение к любому элементу в документе.
в данном случае применяется обращение к атрибуту.
-->


> Переменные
>
> Переменные в XSLT отличается от переменных в обычных языках
> программирования из-за того, что их значения не могут изменяться. После
> того как переменной присвоено какое-то значение, оно остается постоянным.
>
> (Странно, почему перменные названы переменными, а не константами.
> Прим.ред.)

-->
переменная в XSLT является именно полноправной переменой, а не
константой.:)) Невозможность же изменения переменной заложена в самой
технологии XSLT. Это связано с тем, что XSLT является _декларативным_
языком программирования (то есть нужно указать только входные данные и
требуемый вид результата. О том, _как_ это сделать, заботится уже не
программист, а процессор). То есть преобразование документа - это
применение набора шаблонов, а не последовательность действий.
-->


> Инструкция if
>
> Иногда возникает необходимость поместить в выходной документ некоторый
> текст, если задан какой-либо xml-элемент (или его атрибут), либо другой
> текст, если этот элемент (или атрибут) отсутствует. В таких случаях можно
> использовать элемент xsl:if.

-->
Одним из недостатков элемента xsl:if является его усеченность.
Конструкция if-then-else в XSLT отсутствует. Её приходится эмулировать с
помощью xsl:choose
-->

>  <xsl:choose>
>     <xsl:when test="$even = 1">
>       <![CDATA[<table width="100%" bgcolor="#cccccc">]]>
>     </xsl:when>
>     <xsl:when test="$even = 0">
>        <![CDATA[<table width="100%" bgcolor="#99b0bf">]]>
>     </xsl:when>
>     <xsl:otherwise>
>        <![CDATA[<table width="100%" bgcolor="#ffffff">]]>
>     </xsl:otherwise>
>  </xsl:choose>


> Если вы спросите меня зачем я вставил секцию CDATA, то я вам отвечу, если
> бы я этого не сделал, то XSLT-процессор генерировал бы сообщения об ошибке
> по поводу отсутствия закрывающего тега (), но в нашем случае этот
> тег находится ниже. По той же самой причине, закрывающий тег  так
> же должен быть оформлен в виде секции CDATA.

-->
Это один из вариантов. Также для решения этой задачи можно использовать сущности
< и >, которыми заменяются символы "<" и ">", или определить свои
собственные сущности.
-->

> Я знаю о существовании и других процессоров, таких как sablotron, но я ими
> не пользовался, а потому не могу рекомендовать их вам ;-).

-->
Я пользуюсь процессором Sablotron. Этот процессор существует в виде
исполняемой библиотеки для многих платформ. Имеются утилиты для работы
из командной строки и API для подключения к языкам высокого уровня (C,
PERL, PHP, Python).

Для работы из командной строки используется утилита sabcmd.
чтобы увидеть результат преобразования на экране, нужно дать команду
sabcmd XSLT_file XML_document
а чтобы отправить результат в файл
sabcmd XSLT_file XML_document result_document

также поддерживаются режимы batch, применить несколько XSLT к одному
документу, применить одну XSLT к нескольким документам. Подробнее об
этих режимах смотрите в документации.
-->

Спасибо за комментарии.

Александр Куприн


Планировщик задач в Linux.
Автор: Vinayak Hegde
Перевод: Андрей Киселев


Почему так важна архитектура планировщика

В ядре имеются две, наиболее критичные ко времени исполнения, части -- это подсистема управления памятью и планировщик задач. Связано это с тем, что они влияют на работу практически всех остальных частей ядра и операционной системы в целом. По этой причине они должны быть абсолютно безупречны и оптимальны. Ядро Linux имеет широкую область применения, начиная от небольших встроенных устройств и заканчивая супер-ЭВМ. Разработка планировщика -- это настоящее "шаманство". Независимо от того насколько хорошо реализован планировщик, всегда найдется человек, который будет полагать, что некоторые категории процессов планируются на исполнение недостаточно хорошо.

В этой статье я преднамеренно старался избегать комментариев исходного кода планировщика, поскольку вы легко сможете найти их (комментарии) в Сети (см. радел Ссылки). Здесь рассматриваются проблемы, с которыми столкнулись разработчики при создании нового планировщика, как эти проблемы были решены и в каком направлении предполагается развивать планировщик дальше. Могу сказать, что лучший путь к пониманию лежит через изучение исходного кода. Если у вас установлены исходные тексты ядра, то реализацию планировщика вы найдете в kernel/sched.c.

Цели планирования

Планировщик Linux преследует несколько целей :

  1. Беспристрастность :

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

  2. Производительность и загрузка процессора :

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

  3. Минимальные накладные расходы :

    Сам планировщик должен занимать процессор настолько малое время, насколько это возможно. Время реакции планировщика должно быть минимальным. Но тут есть хитрый момент. Вообще считается, что процесс планирования не есть полезная работа (??). Однако, если планирование произведено безупречно, даже если оно потребовало дополнительных затрат некоторого количества времени, то это определенно стоит затраченных усилий. Но как решить -- где "золотая середина"? Большинство планировщиков решают эту проблему с помощью эвристических алгоритмов.

  4. Планирование на основе приоритетов :

    Приоритетное планирование означает, что одни процессы могут иметь превосходство перед другими в конкуренции за процессор. Планировщик, по крайней мере, должен различать процессы занятые вводом-выводом и "числодробилки". Кроме того должен быть учтен эффект "застаивания" так, чтобы в системе не было "зависших" процессов. Linux поддерживает приоритеты и различает разные категории процессов. Ядро различает пакетные и интерактивные задачи. Каждая из них получает свою долю процессорного времени в соответствии со своим приоритетом. Вероятно кто-то из вас уже пользовался командой nice для изменения приоритета процесса.

  5. Время цикла обслуживания, время ожидания :

    Время цикла обслуживания -- это сумма времени, потраченного на обслуживание процесса и время, проведенное задачей в очереди готовых к запуску процессов. Это время должно быть сведено к минимуму.

  6. Время отклика и дисперсия :

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

  7. Прочие :

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

Усовершенствования в планировщике

  • Алгоритм планирования сложности O(1)

    Вы можете спросить: "Что такое O(1)?". Об O() (часто эту нотацию называют "большое О") я расскажу лишь вкратце. Более подробную информацию о "большом О" вы найдете в любой хорошей книге, посвященной алгоритмам (от себя могу порекомендовать http://algolist.manual.ru/misc/o_n.php прим. перев.). Методика O() используется для оценки производительности алгоритмов вне зависимости от машинной реализации. Она определяет верхний предел времени работы алгоритма для самого тяжелого случая. Это исключительная методика, применяемая для сравнения эффективности алгоритмов относительно времени исполнения.

    Возьмем в качестве примера алгоритм, который основан на двух вложенных циклах от 1 до n-1, тогда верхний предел времени работы алгоритма в самом тяжелом случае составит O(N2). Аналогично: алгоритм поиска по неупорядоченному связанному списку, в самом тяжелом случае, должен будет пройти через весь список, чтобы найти необходимый элемент (не забывайте, речь идет о самом худшем случае -- когда искомый элемент находится в самом конце списка прим. перев.), или хуже того -- обнаружить, что такого элемента в списке нет. Этот алгоритм имеет сложность O(N), поскольку продолжительность работы такого алгоритма прямо пропорциональна количеству элементов в списке -- N.

    Планировщик Linux тратит постоянное время для того, чтобы наметить процессы в очереди готовых к запуску задач. Следовательно, можно сказать, что он имеет уровень сложности O(1). Независимо от количества активных процессов в системе, планировщик всегда затрачивает одинаковое время на их планирование. Алгоритм "пробуждения" процесса, выбор следующего, переключение контекста и накладные расходы на обработку прерываний от таймера в текущей версии ядра (здесь имеется ввиду ядро 2.5.49 -- см. раздел Ссылки) имеет сложность O(1).

  • Улучшенная поддержка SMP и масштабируемость

    Как уже упоминалось в самом начале, ядро Linux имеет очень широкий диапазон применений, начиная от наручных часов и заканчивая супер-ЭВМ. В более ранних версиях планировщика имелись определенные проблемы с масштабируемостью. Частично эти проблемы снимались путем внесения изменения в ядро, предназначенного для целевой архитектуры. Однако, в целом масштабируемость планировщика оставляла желать лучшего. В новом планировщике значительно улучшена масштабируемость и поддержка SMP (от англ. Symmetric Multi Processing -- Симметричное Мультипроцессирование, т.е. поддержка многопроцессорных систем прим. перев.) Значительно улучшена производительность планировщика на многопроцессорных системах. Одна из целей, обозначенных Инго Молнаром (Ingo Molnar) -- автора O(1)-планировщика, состоит в том, чтобы полностью загрузить процессоры работой на SMP-системах, если таковая (работа) имеется. Кроме того, необходимо обратить внимание на то, что задачи иногда не планируются на различные процессоры. Это должно помочь избежать переполнения кеша с запрашиваемыми данными.

  • Пакетное планирование задач

    Это не совсем новая особенность, но имеется ряд "заплат", которые могли бы быть приняты в ядро для поддержки пакетного планирования. В ранних версиях ядра также имелась некоторая поддержка пакетного планирования. На текущий момент выполняется приоритетное пакетное планирование. В ядре используется примерно 40 уровней приоритетов[*1] (хотя все они отображаются примерно на 5 различных уровней). Пакетные задания получают процессор главным образом тогда, когда в системе не очень много интерактивных процессов или процессов, занятых вычислительной работой ("числодробилок"), которые имеют более высокий приоритет. Пакетным задачам выделяются большие кванты времени, по сравнению с обычными процессами, что в свою очередь минимизирует количество обращений к кешу с целью подкачки данных, повышая тем самым общую производительность пакетных заданий.

  • Улучшена производительность интерактивных задач

    Одно из главных усовершенствований в планировщике -- это обнаружение и повышение производительности интерактивных задач. Достичь этого в старом планировщике было очень тяжело. В новом планировщике обнаружение интерактивных процессов отделено от других задач планирования, таких как управление квантами времени. Интерактивные процессы обнаруживаются на основе статистики времени использования. Это означает, что интерактивные процессы имеют короткое время отклика при тяжелых нагрузках, а "жадные" до процессора задачи не смогут его монополизировать. Новый планировщик определяет активность интерактивного процесса и отдает ему преимущество перед другими процессами. Даже тогда, когда задача планируется среди других интерактивных процессов с использованием циклического (Round-Robin) алгоритма. Это очень важно для настольных систем, так как теперь пользователь не будет замечать увеличения времени отклика, когда он запускает задачи, интенсивно использующие процессор, например перевод музыкальных файлов в формат ogg. В будущем планируется объединение алгоритма O(1) с кодом приоритетного прерывания (preemption), чтобы уменьшить время отклика для интерактивных задач.

  • Улучшена масштабируемость и поддержка большего количества архитектур

    Благодаря изменениям, внесенным в новый планировщик, он легче переносится на другие архитектуры, типа NUMA (от англ. Non-Uniform Memory Access -- неоднородный доступ к памяти прим. перев.) и SMT (от англ. Simultaneous Multithreading -- Параллельная Многопоточность прим. перев.)

    От переводчика:
    Основная идея NUMA архитектуры заключается в образовании основной вычислительной системы посредством объединения однотипных модулей, коммутируемых высокоскоростной сетью. Каждый модуль может состоять из одного или нескольких процессоров со своей локальной памятью, которая образует единое адресное пространство системы и часто подсистемы ввода/вывода.
    Технология SMT позволяет одному процессору работать за нескольких сразу, повышая эффективность распределения и управления вычислительной нагрузкой. Когда обычный процессор выполняет несколько задач, он может перейти к следующей лишь после того, как завершит предыдущую. Многопоточный процессор способен обрабатывать сразу несколько потоков команд (или "нитей" -- threads) одновременно. Используя механизм многопоточности, SMT-процессор может выполнять от четырех до десяти команд за такт, тогда как обычный выполняет, как правило, лишь от одной до четырех. Кроме того, чтобы воспользоваться технологией SMT, переписывать приложения не потребуется.


    Архитектура NUMA используется на некоторых высокопроизводительных серверах и супер-ЭВМ. Кроме того, продолжается работа над SMT (Symmetric Multithreading -- Симметричная Многопоточность. Здесь я хочу внести некоторую ясность -- автор расшифровывает аббревиатуру SMT как Symmetric Multithreading -- Симметричная Многопоточность, однако в процессе работы над переводом я встречал расшифровку этой аббревиатуры как Simultaneous Multithreading -- Параллельная Многопоточность, что на мой взгляд, более точно отражает смысл этой технологии прим. перев.). SMT также известна под термином : HyperThreading (Гиперпоточность). Одна из причин этой работы состоит в том, что сейчас каждый процессор имеет свою очередь задач. И только код, управляющий распределением вычислительной нагрузки, имеет "глобальное" значение для системы. Таким образом, для отдельных архитектур, необходимо внести изменения в эту согласующую часть. Недавно были выпущены "заплаты" для NUMA. Они были введены в состав ядра 2.5.59. SMT-процессоры имеют два (или более) виртуальных процессора на одном физическом кристалле -- один "логический" процессор может выполнять какую нибудь работу, в то время как другой ожидает доступа к памяти. SMT может рассматриваться как своего рода NUMA, поскольку совместно используют кеш-память, а поэтому получают более быстрый доступ к памяти, к которой недавно обращался один из них. В направлении SMT также ведется работа, но новый O(1)-планировщик способен обслуживать SMT-процессоры достаточно хорошо и без внесения каких либо изменений. Недавно были выпущены "заплаты" к ядру для SMT. Хотя архитектура NUMA и имеет некоторое сходство с архитектурой SMT, тем не менее, планировщик Linux обрабатывает их по-разному.

  • Прочие улучшения

    Планировщик дает дочерним (fork()ed) процессам более высокий приоритет, чем родительским процессам. Это может оказаться полезным для серверов, в которых ветвление часто используется для обслуживания запросов. Кроме того, это может оказаться полезным для приложений с графическим интерфейсом. Имеются также некоторые дополнения к планированию процессов реального времени (real-time), базирующемуся на приоритетах.

Ссылки

Vinayak

В настоящее время ведет курс APGDST в NCST. Область его интересов - сети, системы параллельных вычислений и языки программирования. Он верит, что Linux даст программной индустрии то же, что в свое время дало изобретение печати миру науки и литературы. В редкие периоды свободного времени он любит слушать музыку и читать книги. В настоящее время работает в проекте LIberatioN-UX, где он занимается настройкой удаленно-загружаемых рабочих станций под управлением Linux (тонкие клиенты) для учебных заведений/корпораций.


Примечания редактора

[*1] См. info-страницы к программе nice -- уровни от -20 (самый высокий уровень) до 19 (самый низкий уровень).


Copyright (C) 2003, Vinayak Hegde. Copying license http://www.linuxgazette.com/copying.html
Published in Issue 89 of Linux Gazette, April 2003


Команда переводчиков:
Александр Куприн, Андрей Киселев, Александр Михайлов, Александр Саввин, Владимир Меренков, Иван Песин, Игорь Яровинский, Павел Соколов, Роман Шумихин, Сергей Скороходов, Юрий Прушинский

Со всеми предложениями, идеями и комментариями обращайтесь к Александру Куприну (ru_classic at mail.ru). Убедительная просьба: указывайте сразу, не возражаете ли Вы против публикации Ваших отзывов в рассылке.

Сайт рассылки: http://gazette.linux.ru.net
Эту статью можно взять здесь: http://gazette.linux.ru.net/lg89/vinayak2.html
Архивы выпусков находятся здесь: http://gazette.linux.ru.net/archive/




http://subscribe.ru/
E-mail: ask@subscribe.ru
Отписаться
Убрать рекламу

В избранное