Планировщики для ядра linux

Принцип работы планировщика задач в Linux

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

Само планирование осуществляется планировщиком, который нацелен:

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

Если с этими метриками вы не знакомы, то предлагаю просмотреть несколько примеров в другой моей статье (англ.), посвященной алгоритмам планировщика.

Типы процессов в Linux

В Linux процессы делятся на два типа:

• Процессы реального времени.
• Условные процессы.

Процессы реального времени должны вписываться в границы времени ответа, независимо от загрузки системы. Иначе говоря, такие процессы являются срочными и ни при каких условиях не откладываются.

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

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

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

У каждого типа процессов есть свой алгоритм планирования. При этом пока есть готовые к выполнению процессы реального времени, выполняться будут они, оставляя условные процессы в ожидании.

Планирование в реальном времени

В случае с планированием в реальном времени используются две политики, SCHED_RR и SCHED_FIFO .

Политика определяет количество выделяемого процессу времени, а также принцип организации очереди на выполнение.

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

SCHED_FIFO

В данной политике планировщик выбирает процесс, ориентируясь на время его поступления (FIFO = первым вошел, первым вышел).

Процесс с политикой планирования SCHED_FIFO может «освободить» ЦПУ в нескольких случаях:

• Процесс ожидает, к примеру, операции ввода/вывода, после чего по возвращению в состояние «готов» помещается в конец очереди.
• Процесс уступил ЦПУ через системный вызов sched_yield , после чего он тут же возвращается в конец очереди.

SCHED_RR

SCHED_RR подразумевает циклическое планирование.

В этой политике каждый процесс в очереди получает интервал времени (квант) и выполняется в свою очередь (исходя из приоритета) по циклическому принципу.

Для лучшего понимания рассмотрим пример, где в очереди находятся три процесса, A B C , все из которых работают по политике SCHED_RR .

Как показано ниже, каждый процесс получает квант времени и выполняется в свою очередь. После однократного выполнения всех процессов они повторяются в той же последовательности.

Обобщение по планированию в реальном времени

Процесс реального времени может планироваться по двум разным политикам, SCHED_FIFO и SCHED_RR .

Политика влияет на принцип работы очереди и определяет, сколько времени нужно выделить тому или иному процессу.

Условное планирование

Здесь мы знакомимся с Completely Fair Scheduler (CFS, абсолютно справедливый планировщик), представляющим алгоритм планирования условных процессов, появившийся в версии Linux 2.6.23.

Помните метрики планирования, которые мы затронули в начале статьи? Так вот CFS фокусируется на одной из них – он стремится к максимальной равноправности процессов, то есть обеспечивает выделение всем процессам равных квантов времени ЦПУ.

Обратите внимание, что процессы с повышенным приоритетом все равно могут получать на обработку больше времени.

Для лучшего понимания принципа работы CFS нужно познакомиться с новым термином – виртуальное время выполнения ( vruntime ).

Виртуальное время выполнения

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

Как было сказано, CFS стремится быть максимально справедливым, в связи с чем по очереди планирует готовый к выполнению процесс с минимальным виртуальным временем.

CFS задействует переменные, содержащие максимальное и минимальное виртуальное время выполнения, и чуть позже станет ясно зачем.

CFS —Абсолютно справедливый планировщик

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

CFS задействует красно-черное дерево, представляющее бинарное дерево поиска – то есть добавление, удаление и поиск выполняются за O(logN) , где N выражает количество процессов.

Ключом в этом дереве выступает виртуальное время выполнения процесса. Новые процессы или процесс, возвращающиеся из ожидания в состояние готовности, добавляются в дерево с ключом vruntime = min_vruntime . Это очень важный момент, который позволяет избежать дефицита внимания ЦПУ для старых процессов.

Вернемся к самому алгоритму. В первую очередь он устанавливает себе лимит времени – sched_latency .

В течение этого времени алгоритм стремится выполнить все готовые процессы – N . Это означает, что каждый процесс получит интервал времени равный временному лимиту, поделенному на количество процессов: Qi = sched_latency/N .

Когда процесс исчерпывает свой интервал ( Qi ), алгоритм выбирает в дереве следующий процесс с наименьшим виртуальным временем.

Рассмотрим ситуацию, которая может стать проблематичной для такой схемы работы алгоритма.

Предположим, что алгоритм выбрал лимит времени 48мс при наличии 6 процессов – в этом случае каждый процесс получит на выполнение по 8мс.

Но что произойдет, если система окажется перегружена процессами? Предположим, что лимит времени остается равен 48мс, но теперь у нас 32 процесса. В результате каждый получит уже всего по 1.5мс на выполнение, что приведет к замедлению работы всей системы.

Почему?

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

Каждый раз, когда процесс исчерпывает свое время на выполнение, и планируется очередной процесс, активируется переключение контекста, которое также занимает некоторое время.

Предположим, что на него уходит 1мс. В первом примере, где каждому процессу у нас отводилось по 8мс, это вполне допустимо. Так мы тратим 1мс на переключение контекста и 7мс на фактическое выполнение процесса.

А вот во втором примере на выполнение каждого процесса останется уже всего по 0.5мс – то есть большая часть времени уходит на переключение контекста, отсюда и проблема с выполнением.

Для того, чтобы исправить ситуацию, мы вводим новую переменную, которая определит минимальную протяженность кванта времени выполнения – min_granularity .

Представим, что min_granularity = 6мс , и вернемся к нашему примеру, где лимит времени равен 48мс при наличии 32 процессов.

С помощью той же формулы, что и прежде, мы получаем по 1.5мс на каждый процесс, но теперь такой вариант не допускается, так как min_granularity задает минимальный квант времени, который должен получить каждый процесс.

В данном случае, где Qi , мы берем Qi равным min_granularity , то есть 6мс, и соответствующим образом изменяем временной лимит. В результате он составит Qi x N = 6мс x 32 = 192мс .

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

RR – циклический список	CFS – абсолютно справедливый планировщик
Квант времени статичен и не зависит от количества процессов в системе.	Квант времени динамичен и может изменяться в соответствии с количеством процессов в системе.
По исчерпанию процессом его кванта времени, RR выбирает очередной процесс с наименьшим виртуальным временем из циклического списка.	По исчерпанию процессом его кванта времени, CFS выбирает очередной процесс с наименьшим виртуальным временем из красно-черного дерева.

Надеюсь, что статься помогла вам лучше понять реализацию планирования задач в ядре Linux.

Прошу обратить внимание, что автор оригинальной статьи Eliran поблагодарил читателей за интерес и отдельно пригласил желающих со знанием английского языка в свой блог Coding Kaiser для ознакомления с множеством материалов по смежным и другим интересным темам, а также обмена идеями.

Источник

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

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

Они объясняются ниже.

Планировщик Linux предлагает три класса планирования, два для приложений реального времени и один для приложений не реального времени. Этими тремя классами являются:

▪ SCHED_FIFO : политика планирования реального времени первый вошёл, первый вышел (First-In First-Out). Алгоритм планирования не использует никаких интервалов времени. Процесс SCHED_FIFO выполняется до завершения, если он не заблокирован запросом ввода/вывода, вытеснен высокоприоритетным процессом, или он добровольно отказывается от процессора. Следует обратить внимание на следующие моменты:
– Процесс SCHED_FIFO , который был вытеснен другим процессом более высокого приоритета, остаётся во главе списка с его приоритетом и возобновит выполнение, как только все процессы с более высоким приоритетом будут вновь заблокированы.
– Когда процесс SCHED_FIFO готов к работе (например, после пробуждения от операции блокировки), он будет вставлен в конец списка с его приоритетом.
– Вызов sched_setscheduler или sched_setparam поставит процесс SCHED_FIFO в начало списка. Как следствие, это может вытеснить работающий в данный момент процесс, если его приоритет такой же, как и у работающего процесса.

▪ SCHED_RR : циклическая (Round-Robin) политика планирования реального времени. Она похожа на SCHED_FIFO с той лишь разницей, что процессу SCHED_RR разрешено работать как максимум время кванта. Если процесс SCHED_RR исчерпывает свой квант времени, он помещается в конец списка с его приоритетом. Процесс SCHED_RR , который был вытеснен процессом с более высоким приоритетом, завершит оставшуюся часть своего кванта времени после возобновления выполнения.

▪ SCHED_OTHER : стандартный планировщик Linux с разделением времени для процессов, работающих не в реальном времени.

Для установки и получения политики планирования процесса используются функции sched_setscheduler и sched_getscheduler , соответственно.

Диапазоны приоритетов для различных политик планирования показаны в Таблице 7.1. Функции sched_get_priority_max и sched_get_priority_min возвращают максимальный и минимальный приоритет, разрешённый для политики планирования, соответственно. Чем выше число, тем выше приоритет. Таким образом, процесс SCHED_FIFO или SCHED_RR всегда имеет более высокий приоритет, чем процесс SCHED_OTHER . Для процессов SCHED_FIFO и SCHED_RR функции sched_setparam и sched_getparam используются для установки и получения приоритета, соответственно. Для изменения приоритета процессов SCHED_OTHER используется системный вызов nice (или команды).

Таблица 7.1 Диапазон приоритетов в пространстве пользователя

Источник

Linuxoid

OpenSource forever

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

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

О чем собственно речь.

Вообще в любой системе можно выделить два типа планировщиков выполняющих свои задачи: планировщик процессорного времени и планировщик ввода/вывода. И хотя сегодня идет настоящая битва между разработчиками, предложившими за 2,5 года более 300 вариантов планировщиков CPU , а в ядре 2.6.23 стандартный O (1) проработавший 15 лет, будет (наконец то. ) заменен на более интерактивный CFS (Completely Fair Scheduler, абсолютно справедливый планировщик), трогать мы их пока не будем. Нас интересуют последние. Так планировщики ввода/вывода (I/O scheduler) являются прослойкой между блочными устройствами и драйверами низкого уровня, его задача планировщика оптимальным образом обеспечить доступ процесса к запрашиваемому дисковому устройству. Не смотря на всю кажущуюся простоту вопроса, это сложная и противоречивая задача. Работа с дисками относится к очень медленным операциям, имеющая к тому же долгое время поиска нужной информации, а процессов терпеливо ожидающих своей очереди может быть очень много. Поэтому алгоритм I/O scheduler должен с одной стороны уметь уменьшать время поиска информации на диске, ведь частое переключение между задачами приведет к тому, что головка диска будет большую часть времени будет просто переходить на разные позиции. Также I/O scheduler должен уметь выдавать информацию в соответствии с приоритетом и гарантировать получение данных приложению за определенное время и в нужном количестве.

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

Планировщики I / O ядра 2.6

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

$ dmesg | grep scheduler

[ 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 7.10, как и в любом современном дистрибутиве включены все четыре. Алгоритм CFQ отмечен как default то есть используется по умолчанию, причем так обстоят дела практически во всех в современных дистрибутивах с ядром старше 2.6.18.

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

$ grep IOSCHED .config

CONFIG _ DEFAULT _ IOSCHED =» cfq «

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

Кстати если посмотреть в ядра до 2.6.18 там по умолчанию стоит “CONFIG_DEFAULT_IOSCHED=»anticipatory»”, например в Ubuntu 6.06 установлено именно так.

Кратко о планировщиках

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

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

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

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

Кстати разработкой всех этих алгоритмов занимается один и тот же человек — Jens Axboe.

Изменение планировщика

Если нужный алгоритм ядром поддерживается, переключить планировщик на другой очень просто и это можно сделать двумя способами. Первый — добавить параметр elevator в строку kernel конфигурационного файла загрузчика с указанием алгоритма — as, deadline, noop или cfq. Второй — изменить алгоритм на лету, записав в файл /sys/block/ /queue/scheduler нужную строку. Смотрим что есть в этом файле:

noop anticipatory deadline [cfq]

Изменим cfq например на anticipatory :

$ sudo 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 уровней приоритета 1;

— 2 — Best Effort – класс устанавливаемый по-умолчанию для всех процессов, доступны те же 8 уровней приоритета.

— 3 — Idle — Получает право на использование жесткого диска только в том случае, если другая программа не требует диск, приоритеты на этом уровне не используются.

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

$ sudo ionice — c 2 — n 0 mplayer

Небольшой эксперимент

Попробуем провести несколько тестов. Для начала запустим программу для тестирования dbench c имитацией работы 50 клиентов “dbench -t 60 50”. Получаем Cfg – 88,02 Мб/с, anticipatory – 81,14 Мб/с, Deadline – 134,66 Мб/с, noop – 63,15 Мб/с. Естественно все это прогонялось несколько раз, полученный результат усреднялся. Теперь другая утилита iostat (в Ubuntu требуется установить пакет sysstat), которая умеет показывать сколько блоков было прочитано и записано на диск. Запускаем:

Для CFQ результат скорость считывания 3078,25 блоков в секунду, записи — 257,10. Для anticipatory соответственно — 2337,40 и 208,31, NOOP — 2100,70 и 201,23, deadline — 1981,75 и 195,83. Синтетические тесты не интересны, чтобы с иммитировать ситуацию, приближенную к реальной коммандой создадим файл размером 1 Гб и замерим время сначала в спокойной системе, а затем при просмотре фильма.

$ time dd if=/dev/zero of=test bs=1024 count=1024000

Компьютер с Athlon X 2 и SATA диском показывал результаты, отличающиеся приблизитительно на 2-3 Мб/с, что можно отнести к погрешности измерения. Поэтому был взят старый системный блок с 633 Целероном и ATA диском. Здесь уже результаты интересней и говорят сами за себя. При Anticipatory файл был создан (вообще то скопирован) со скоростью 9,2 Мб/с, а при запущенном видео уже за 5,0 Мб/с. Выбрав NOOP я устал ждать, так как скорость составила 1,0 Мб/с, а с видео – 973 кб/с. При этом практически прекратилось воспроизведение фильма. Идем далее Deadline результат 8,9 и 7,5 Мб/с, и CFQ – 9,7 и 8,1 Мб/с

Результаты вроде понятны и без комментариев, но вообще однозначно сказать какой алгоритм лучше тяжело. В любом случае следует подбирать планировщик изходя из конкретных условий. Например, хотя Deadline и обогнал все остальные в первом тесте, но попытка запустить Amarok или сохранить файл, приведет к тому, что некоторое время придется подождать. А вообще выбор это всегда хорошо . Linux forever!

Источник