Эмуляция работы планировщика задач в Linux

Использование LinSched для симуляции планировщика Linux в среде пользователя

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

M. Тим Джонс, инженер-консультант, Emulex Corp.

М. Тим ДжонсМ. Тим Джонс - архитектор встроенного ПО и, кроме того, автор книг Artificial Intelligence: A Systems Approach, GNU/Linux Application Programming (выдержавшей на данный момент второе издание), AI Application Programming (второе издание) и BSD Sockets Programming from a Multilanguage Perspective. Он имеет обширный опыт разработки ПО в самых разных предметных областях - от ядер специальных ОС для геосинхронных космических аппаратов до архитектур встраиваемых систем и сетевых протоколов. Тим - инженер-консультант Emulex Corp., Лонгмонт, Колорадо.



17.01.2012

При планировании задач в Linux могут возникать определенные трудности. ОС Linux поддерживает множество моделей использования (например, корпоративный сервер, настольный компьютер или встраиваемое устройство) на основе широкого диапазона процессоров (одноядерные, многоядерные, многоядерные/многопоточные и т.д.). Просто удивительно, что всего несколько политик инструментов планирования, доступных в Linux, покрывает все возможные области применения.

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

К счастью, существуют проекты, такие как LinSched, способные помочь в решении этой проблемы.

Знакомство с LinSched

LinSched – это эмулятор планировщика Linux, располагающийся в пользовательской среде. Он эмулирует подсистему планировщика Linux и воспроизводит фрагменты инфраструктуры ядра, необходимые для работы планировщика, так что полученное решение может исполняться в среде пользователя. Также в LinSched входят API-интерфейсы, позволяющие проверить, как запланировано выполнение того или иного задания, и собрать статистику для анализа результатов работы этого задания, как будет показано ниже.

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

В качестве альтернативы можно рассмотреть виртуализацию но LinSched предпочтительнее в силу своей простоты и эффективнее, так как ему не требуется загружать другое ядро. Также к процессу, запущенному в пространстве пользователя, проще подключить отладчик, например GDB (GNU Debugger), чтобы еще глубже проникнуть во внутренние аспекты работы планировщика.


История LinSched

Первоначально LinSched был разработан в Университете Северной Каролины в рамках гранта, полученного от компаний IBM и Intel, но недавно он был обновлен Google для проверки политик планирования. Со стороны Google это был интересный ход с далеко идущими последствиями. Хотя Linux поддерживает различные типы планирования и успешно справляется с планированием для различных заданий, он не очень подходит для планирования запуска конкретного задания на определенной аппаратной платформе. Так как Google использует крупные кластеры, состоящие из одинаковых систем, выполняющих определенные задачу (например, MapReduce), то имеет смысл настроить планировщик конкретно под эту задачу и платформу. В ходе работы с LinSched Google также внесла улучшения и в Linux-компонент CFS (completely fair scheduler – абсолютно честный планировщик), включая инициализацию канала и балансировку нагрузки, когда "весовые коэффициенты" задач сильно отличаются друг от друга.


Архитектура LinSched

LinSched – это больше, чем просто эмулятор планировщика, работающий в среде пользователя. В рамках проекта LinSched планировщик Linux был перенесен в пространство пользователя с прозрачной эмуляцией всех необходимых компонентов, так что стало возможным запускать планировщик за пределами ядра Linux. Исходный код LinSched – это на самом деле дистрибутив Linux (на данный момент версии 2.6.35) c новым подкаталогом ./linsched, содержащим интерфейсы и исполняемый модуль эмулятора. Так как LinSched использует для эмуляции саму подсистему планировщика Linux, то с его помощью гораздо проще вносить изменения в работу планировщика, а затем встраивать их обратно в ядро.

Архитектура LinSched показана на рисунке 1. В нижней части находится базовая операционная система. LinSched – это приложение, запускаемое в среде пользователя и построенное из определенных компонентов, включая фрагменты самого ядра Linux.

Рисунок 1. Архитектура LinSched - симулятора планировщика задач для ОС Linux
Рисунок 1. Архитектура LinSched - симулятора планировщика задач для ОС Linux

Модуль среды представляет собой абстракцию ядра Linux (с флагами поддержки компиляции в режиме симуляции). Поверх модуля среды располагается исполняемый модуль эмулятора, предоставляющий API для конфигурации среды и выполнения симуляции. В API исполняемого модуля содержится функция для инициализации, определяющая топологию процессоров, функции для создания задач и обратных вызовов (вызываемых после завершения задачи). Также стоит упомянуть функцию run(), при вызове которой будет выполнена эмуляция определенного числа тактов процессора (что в свою очередь приведет к вызову schedule() – внутренней функции Linux, отвечающей за принятие решений по планированию задач).

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

В следующих разделах будет показано, как установить и использовать LinSched. Также будет представлен обзор некоторых функций, входящих в LinSched API.


Установка LinSched

Проект LinSched был недавно обновлен для поддержки ядра версии 2.6.35. Актуальную версию LinSched можно загрузить несколькими способами – с помощью утилиты git или на Web-странице проекта LinSched (см. раздел Ресурсы). При использовании git необходимо клонировать репозиторий с LinSched, как показано ниже:

$ git clone git://google3-2.osuosl.org/linsched/2.6.35.git

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

$ make run_all_tests

Эта команда запустит несколько тестов планировщика для различных топологий процессоров и выведет в консоль результаты их выполнения.


LinSched API

Чтобы воспроизвести действия планировщика Linux с помощью LinSched потребуется создать сценарий и инициализировать эмулятор для подготовки к запуску рассматриваемой конфигурации. Инициализация выполняется c помощью вызовов LinSched API. В этом разделе рассматриваются только наиболее важные функции и приводятся примеры их использования. Но в исходном коде проекта, находящемся в каталоге ./linsched, можно найти полный список функций, доступных в API.

Перед запуском сценария необходимо вызвать метод linsched_init() для инициализации эмулятора. Эта функция принимает в качестве аргумента топологию процессоров, которую необходимо воспроизвести, выполняет настройку внутренней среды эмулятора и запускает ядро Linux в пространстве пользователя.

void linsched_init( struct linsched_topology *topo );

Структура, описывающая топологию процессоров, объявлена в файле linux_linsched.h. В ней определяется количество процессоров (physical package) и связи между ними (node distance map). Однопроцессорную конфигурацию можно объявить с помощью константы TOPO_UNIPROCESSOR, а 4-хсокетную 4-х ядерную топологию - с помощью константы TOPO_QUAD_CPU_QUAD_SOCKET.

Хотя задачи в LinSched являются "виртуальными", а не "реальными" сущностями, эмулятор позволяет создавать большое количество сценариев для задач различных типов. Так, существует функция create_tasks(), позволяющая создать задачи с неоднократными переключениями из рабочего режима в режим ожидания. При вызове этой функции ей передаются четыре параметра:

  • count - количество задач, которые необходимо создать;
  • mask – шаблон конфигурации, на которой будут выполняться задачи;
  • sleep – количество переключений в режим ожидания;
  • run – количество переключений в рабочий режим.
void create_tasks( unsigned int count, unsigned long mask, int sleep, int run );

В листинге 1 перечислены дополнительные функции LinSched API, позволяющие создавать более сложные сценарии планирования задач. Эти функции применяются для создания задач различных типов: обычных, пакетных или реального времени (типа FIFO (первым вошел – первым вышел) или round-robin (циклических)), позволяя назначать задачам определенный приоритет или уровень nice. Для создания обычных задач следует использовать политику планирования SCHED_NORMAL, а для пакетных задач или задач реального времени соответственно используются политики SCHED_BATCH, SCHED_FIFO и SCHED_RR. Пользователь может предоставить структуру с информацией о задаче, чтобы получить возможность управлять её поведением. Также можно использовать функцию linsched_create_sleep_run() для создания стандартной задачи, переключающейся из режима ожидания в рабочий режим. Описания различных типов задач можно найти в файле linux_linsched.c.

Листинг 1. Функции LinSched API для создания задач
int linsched_create_normal_task( struct task_data* td, int niceval );
void linsched_create_batch_task( struct task_data* td, int niceval );
void linsched_create_RTfifo_task( struct task_data* td, int prio );
void linsched_create_RTrr_task( struct task_data* td, int prio );
struct task_data *linsched_create_sleep_run( int sleep, int busy );

С помощью LinSched API можно создать группы и добавлять в них задачи, а затем распределять время процессора между группами для планирования задач. В листинге 2 приведен список подобных функций, расположенных в файле linux_linsched.c.

Листинг 2. Функции LinSched API для создания и управления группами задач
int linsched_create_task_group( int parent_group_id );
void linsched_set_task_group_shares( int group_id, unsigned long shares );
int linsched_add_task_to_group( int task_id, int group_id );

Для начала сеанса эмуляции необходимо вызвать метод linsched_run_sim(), который принимает на вход единственный параметр, определяющий количество тактов процессора. На каждом такте оценивается состояние запланированных задач. Когда сеанс эмуляции завершается, то функция возвращает управление. Эту функцию можно найти в файле hrtimer.c.

void linsched_run_sim( int sim_ticks );

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

Листинг 3. Методы LinSched API для просмотра результатов сеанса эмуляции
void linsched_print_task_stats( void );
void linsched_print_group_stats( void );

Для более детального анализа используется функция linsched_get_task(), в которую необходимо передать идентификатор интересующей задачи.

struct task_struct *linsched_get_task( int task_id );

Эта функция возвращает структуру с информацией о задаче, в которой содержится общее время исполнения задачи (извлекается с помощью метода task_exec_time(task)) и время, потраченное в режиме ожидания (через свойство task->sched_info.run_delay). Также из этой структуры можно узнать, сколько раз планировщик вызывал эту задачу (через свойство task->sched_info.pcount).

Уже по этому краткому обзору, можно увидеть, что LinSched предоставляет API, позволяющий создавать различные сценарии для проверки работы планировщика Linux. Функции API могут вызываться циклически, так что после запуска и завершения одного сеанса список задач можно обновить и начать новый сеанс эмуляции, вызвав метод linsched_run_sim(). Также допускается создание динамических сценариев, которые можно будет запускать неограниченное число раз.


Использование LinSched

После знакомства с API можно переходить к практическому использованию LinSched. В примере, приведенном в листинге 4, шаблон LinSched basic_test используется для создания нового сценария. Второй параметр, передаваемый в этот сценарий, определяет топологию, которая будет использоваться для запуска сеанса. Список поддерживаемых топологий, которые с помощью различных опций можно запускать в инфраструктуре LinSched, находится в массиве topo_db. После определения топологии необходимо вызвать метод linsched_init() для настройки среды в соответствии с выбранной топологией. Затем в листинге 4 создаются 11 задач 3-х различных типов. Первые пять задач, эмулирующие загрузку процессора (процессор "работает" 90% времени и "простаивает" оставшиеся 10%), создаются с помощью простой функции create_tasks(). Следующие пять задач относятся к типу "работа с вводом/выводом" (процессор "работает" 10% времени и "простаивает" 90% времени). Последняя задача относится к типу "реального времени" и создается с помощью функции linsched_create_RTrr_task() (процессор "работает" 100% времени и задача имеет приоритет 90). После создания задач вызывается метод linssched_run_sim() для запуска эмулятора, а результаты его работы выводятся при помощи метода linsched_print_task_stats().

Примечание: В этом примере используется стандартный планировщик CFS, который вызывается методом schedule() из метода linsched_run_sim().

Листинг 4. Пример использования LinSched
void new_test(int argc, char **argv)
{
  int count, mask;
  struct linsched_topology topo;
  int type = parse_topology(argv[2]);

  topo = topo_db[type];

  // разрешить всем задачам использование процессора.
  mask = (1 << count) - 1;

  // инициализировать топологию, указанную в параметрах сценария
  linsched_init(&topo);

  // создать пять задач типа "загрузка процессора"
  create_tasks(5, mask, 10, 90);

  // создать пять задач типа "работа с вводом/выводом"
  create_tasks(5, mask, 90, 10);

  // создать циклическую задачу "реального времени" с приоритетом 90
  linsched_create_RTrr_task( linsched_create_sleep_run(0,100), 90 );

  // запустить сеанс симуляции
  linsched_run_sim(TEST_TICKS);

  // вывести статистику по результатам выполнения задач
  linsched_print_task_stats();

  return;
}

После запуска этого сценария будут распечатаны результаты выполнения каждой задачи. Результаты запуска сценария на однопроцессорной топологии приведены в листинг 5. В нём содержится список задач с указанием их идентификаторов, общее время выполнения (в тактах процессора), количество времени, проведенного в режиме ожидания и количество вызовов данной задачи планировщиком. Стоит отметить, что запущенные задачи продолжают работать бесконечно, хотя задачу и можно остановить с помощью API.

В представленном сценарии первые пять задач большую часть времени "работали" и "отдыхали" только 10% времени. Вторые пять задач большую часть времени находились в режиме ожидания и "работали" только 10% от общего времени. Последняя задача реального времени "проработала" все отведенное ей время. Наглядно видно, что задача реального времени захватила большую часть процессорного времени, и поэтому вызывалась планировщиком всего 61 раз. Можно сравнить ее с обычными задачи и задачами ввода/вывода, которые вызывались в три раза чаще, при этом получив значительно меньше процессорного времени. Также видно, что планировщик справедливо распределял ресурсы между обычными задачами и задачами ввода/вывода, так как они получили примерно одинаковые фрагменты процессорного времени.

Листинг 5. Тестирование планировщика на однопроцессорной топологии
Task id =  1, exec_time =   305000000, run_delay = 59659000000, pcount = 156
Task id =  2, exec_time =   302000000, run_delay = 58680000000, pcount = 154
Task id =  3, exec_time =   304000000, run_delay = 58708000000, pcount = 155
Task id =  4, exec_time =   304000000, run_delay = 58708000000, pcount = 155
Task id =  5, exec_time =   304000000, run_delay = 58708000000, pcount = 155
Task id =  6, exec_time =   296000000, run_delay = 56118000000, pcount = 177
Task id =  7, exec_time =   296000000, run_delay = 56118000000, pcount = 177
Task id =  8, exec_time =   296000000, run_delay = 56118000000, pcount = 177
Task id =  9, exec_time =   296000000, run_delay = 56118000000, pcount = 177
Task id = 10, exec_time =   296000000, run_delay = 56118000000, pcount = 177
Task id = 11, exec_time = 57001000000, run_delay =  2998000000, pcount = 61

Теперь выполним сценарий, описанный в листинге 4, на 4-хсокетной 4-ядерной топологии (16 логических процессоров). Результаты запуска подобного теста приведены в листинге 6. Так как для каждой задачи выделяется отдельный логический процессор, то она получает значительно больше процессорного времени, при этом длительность тестирования не изменяется. Хотя нагрузочные задачи и задачи ввода/вывода вызываются одинаковое количество раз, но последние занимают только 10% от времени исполнения нагрузочных задач. Эта разница связана с настройками соотношения между режимом работы и режимом ожидания (обычные задачи выполняются в течение 90 тактов, а задачи ввода/вывода, не нагружающие процессор, выполняются в течение 10 тактов). Также стоит отметить, что задача реального времени была вызвана только один раз и исполнялась на протяжении всего теста (так как она никогда не останавливалась, то и не требовалось планировать её повторный запуск).

Листинг 6. Тестирование планировщика на 4-хсокетной 4-ядерной топологии
Task id =  1, exec_time = 54000000000, run_delay = 0, pcount = 601
Task id =  2, exec_time = 54000156250, run_delay = 0, pcount = 600
Task id =  3, exec_time = 54000281250, run_delay = 0, pcount = 600
Task id =  4, exec_time = 54000406250, run_delay = 0, pcount = 600
Task id =  5, exec_time = 54000031250, run_delay = 0, pcount = 600
Task id =  6, exec_time =  6000187500, run_delay = 0, pcount = 600
Task id =  7, exec_time =  6000312500, run_delay = 0, pcount = 600
Task id =  8, exec_time =  6000437500, run_delay = 0, pcount = 600
Task id =  9, exec_time =  6000062500, run_delay = 0, pcount = 600
Task id = 10, exec_time =  6000218750, run_delay = 0, pcount = 600
Task id = 11, exec_time = 59999343750, run_delay = 0, pcount = 1

Данные, полученные из LinSched, также можно визуализировать, как показано в следующем примере. В примере, приведенном в листинге 7, создаются 40 задач с nice-значениями в диапазоне от -20 до 19. Изменение nice-значения задачи приводит к изменению её приоритета, (-20 – это максимальный, а 20 – минимальный приоритет). При стандартном планировании задачи получают доступ к ресурсам процессора в соответствии со своим nice-значением.

Листинг 7. Влияние nice-значений на стандартное поведение планировщика
void new_test(int argc, char **argv)
{
  int count, mask, i;
  struct linsched_topology topo;
  int type = parse_topology(argv[2]);

  topo = topo_db[type];

  // все задачи могут использовать любые процессоры
  mask = (1 << count) - 1;

  // инициализировать топологию, указанную в параметрах сценария
  linsched_init(&topo);

  for (i = 0 ; i < 40 ; i++) {
    linsched_create_normal_task( linsched_create_sleep_run(0,100), i-20 );
  }

  // запустить сеанс симуляции
  linsched_run_sim(TEST_TICKS*10);

  // вывести статистику по результатам выполнения задач
  linsched_print_task_stats();

  return;
}

Результат запуска этого теста на однопроцессорной топологии изображен на рисунке 2. Как видно, высокоприоритетные задачи получили большую часть процессорного времени, а низкоприоритетные получили значительно меньше ресурсов. Полученная зависимость времени исполнения задачи от её приоритета имеет экспоненциальную форму, так задача с максимальным приоритетом (nice -20) получила 120 миллиардов тактов, а задача с минимальным приоритетом (nice 19) получила только 21 миллион тактов процессорного времени.

Рисунок 2. График зависимости времени исполнения задачи от её приоритета
Рисунок 2. График зависимости времени исполнения задачи от её приоритета

Другие варианты визуализации планирования задач в Linux

Хотя LinSched обладает уникальными возможностями по симуляции планировщика Linux в пользовательском пространстве, существуют и другие инструменты для визуализации планирования и других операций, происходящих в ядре Linux. Инструмент LTT (Linux Trace Toolkit – набор для трассирования Linux) содержит подробный каталог системных событий, который позволяет «заглянуть» внутрь работающего ядра Linux. Этот проект развивается, и текущей является версия LTTng (новое поколение LTT). Версия LTTng предоставляет инструмент, работающий в пространстве пользователя, для графической или текстовой визуализации функционирования ядра. Также этот инструмент можно использовать для выполнения трассировки в пользовательском пространстве вместе с объединенной трассировкой (combined tracing), которая одновременно охватывает пространство ядра и пространство пользователя. Дополнительная информация об LTT приведена в разделе Ресурсы.


Заключение

Эта короткая статья помогает понять преимущества эмулирования планировщика Linux в среде пользователя. В ходе работы с LinSched удалось установить, что результаты эмуляции в пользовательском пространстве достаточно точно совпадают с поведением реального планировщика в ядре Linux, так что этот подход можно использовать для прогнозирования действий планировщика в продукционной среде. Определенный интерес представляет и подход, используемый в эмуляторе LinSched. Вместо того чтобы создать новую инфраструктуру, позволяющую выполнять планирование в пространстве пользователя, LinSched использует код самого ядра Linux и специальные «оболочки» для эмуляции платформы. Благодаря этому после проверки планировщика в пользовательском пространстве его можно легко перенести в ядро для практического применения.

В разделе Ресурсы приведена дополнительная информация о LinSched и других инструментах, используемых для симуляции и визуализации планирования задач в ядре Linux.

Ресурсы

  • Linux Scheduler simulation: оригинал статьи (EN).
  • Один из лучших способов познакомиться с особенностями реализации LinSched – это короткая статья LinSched: The Linux Scheduler Simulator. В этой статье представлен подробный обзор LinSched и примеры использования для эмуляции различных видов нагрузки.
  • В начале разработки ядра Linux версии 2.6, в него был добавлен новый планировщик, который должен был заменить существующую сложную реализацию планировщика. Новый планировщик получил название O(1) scheduler, так как он тратит постоянное количество времени на планирование задач, в независимости от их количества. Дополнительную информацию о O(1) scheduler можно найти в статье Inside the Linux Scheduler (developerWorks, июнь 2006).
  • Планировщик CFS, появившийся после O(1) scheduler, был также добавлен в ядро Linux. CFS основан на идее, что у всех процессов должны быть одинаковые полномочия на доступ ко всем имеющимся процессорам. Правильность этого подхода была продемонстрирована в примерах, представленных в этой статье, когда все процессы (даже с минимальным приоритетом) получали доступ к процессору. Дополнительную информацию о CFS можно найти в статье Inside the Linux 2.6 Completely Fair Scheduler (developerWorks, декабрь 2009).
  • Инструмент LTTng (The Linux Trace Toolkit next generation), запускаемый в пользовательском пространстве, может производить трассировку действий, выполняемых в ядре или пространстве пользователя, и визуализировать полученные результаты. Этот инструмент помогает понять поведение системы и выполнить отладку при возникновении различных проблем с ПО или производительностью. Также стоит упомянуть другой полезный проект - Distributed Multi-Core Tracing Research Project, в рамках которого разрабатываются приемы и алгоритмы для трассировки многоядерных систем с минимальными накладными расходами.
  • На странице Scheduling (computing) в Wikipedia приведена дополнительная информация о планировании задач и алгоритмах, реализованных в ядре Linux. Эта статья охватывает FIFO и циклическое планирование, а также описывает планировщики, применяющиеся в основных операционных системах.

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=787918
ArticleTitle=Эмуляция работы планировщика задач в Linux
publish-date=01172012