Планировщик задач ядра linux что это

Linux в режиме реального времени

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

При этом разные события имеют различные временные требования. Например, требование к задержке для антиблокировочной тормозной системы может составлять от 3-5 миллисекунд. То есть с момента, когда колесо впервые обнаруживает, что оно скользит, у системы, управляющей антиблокировочными тормозами, есть от 3-5 миллисекунд, чтобы отреагировать и исправить ситуацию.

Возможности ядра в реальном времени существует уже более десяти лет в экосистеме программ с открытым исходным кодом. Столько же времени доступна поддержка Red Hat Enterprise Linux (RHEL) для ядра реального времени. Тем не менее многие системные администраторы неверно истолковывают его основные концепции и фактическое рабочее поведение. В этой статье я опишу некоторые из его основных функций, отличия от стандартного ядра и шаги по установке.

Планировщик ЦП в реальном времени

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

Мы называем задержкой события время, которое проходит с момента возникновения события до момента его обслуживания. Есть два типа задержек, оказывающих влияние на производительность ОС реального времени.

Задержка прерывания относится к периоду времени от поступления прерывания в CPU до запуска процедуры обработки. Когда происходит событие, ОС должна сначала завершить выполняемую инструкцию и определить тип возникшего прерывания. Затем она должна сохранить состояние текущего процесса до обработки прерывания с помощью специальной процедуры, interrupt service routine (ISR).

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

Рис. 2 Задержка диспетчеризации.

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

Наиболее важной особенностью ОС реального времени — немедленно реагировать на критический процесс, требующий доступ к ресурсам CPU. В результате планировщик для операционной системы реального времени должен поддерживать алгоритм приоритетного прерывания. Такие алгоритмы назначают каждому процессу приоритет в зависимости от его степени важности. Если планировщик также поддерживает приоритетное прерывание, текущий процесс на CPU по запросу будет вытеснен в пользу более приоритетного процесса.

Рис. 3 Классификация планировщиков.

Существует несколько алгоритмов для планировщика в реальном времени.

Rate-Monotonic Scheduling — алгоритм со статическим приоритетом класса планирования. Статические приоритеты назначаются в соответствии с продолжительностью цикла задачи, вследствие чего более короткие циклы имеют более высокий приоритет исполнения. В худшем случае КПД загрузки центрального процессора ограничен следующей величиной.

При числе процессов n, стремящемся к бесконечности ряд будет сходиться к ln2 ≈ 0.693147.
Earliest-deadline-first (EDF) Scheduling динамически назначает приоритеты в соответствии с крайним сроком. Чем раньше крайний срок, тем выше приоритет и чем позже крайний срок, тем ниже приоритет. В отличие от RMS, планировщик EDF не требует, чтобы процессы были периодическими и постоянно запрашивали одно и то же количество процессорного времени на пакет. Единственное требование состоит в том, чтобы процесс объявлял свой крайний срок планировщику, когда он готов к запуску.

Рис. 4 Планировщик EDF.

На рисунке видим общий принцип работы планировщика. На точке 4 был замещён T1 и его место занял T2 так как его крайний срок наступал раньше, чем у T2. После отработки T3 планировщик вернулся к T1, который завершился на отметке 23.
POSIX real-time-scheduling. Стандарт POSIX.4 определяет три политики планирования. Каждый процесс имеет атрибут планирования, который может быть выставлен в одну из трех вариантов политики.

• SCHED_FIFO — политика упреждающего планирования с постоянным приоритетом, при которой процессы с одинаковым приоритетом обрабатываются в порядке «первым пришел — первым обслужен» (FIFO). Данная политика может иметь не менее 32 уровней приоритета.
• SCHED_RR — политика аналогична SCHED_FIFO, но использует метод временного среза (циклический перебор) для планирования процессов с одинаковыми приоритетами. Он также имеет 32 уровня приоритета.
• SCHED_OTHER — политика не определена и зависит от системы; может вести себя по-разному в разных реализациях.

Установка и использование RHEL Real Time

Для начала следует подключить репозиторий Red Hat Enterprise Linux для Real Time, и установить группу пакетов RT.

В составе RT идут эти компоненты:

• kernel-rt — ядро с функционалом реального времени;
• rt-setup — установка окружения Red Hat Enterprise Linux Real Time;
• rt-tests — утилиты тестирования функций RT;
• rt-eval — для оценки возможности применять RT на данной системе;

После установки RT и перезагрузки нужно убедиться, что загружено ядро kernel-rt.

Посмотрим на некоторые отличия kernel-rt от стандартного ядра.

• При высокой нагрузке происходит проверка приоритета задачи (1-99).
• Высокоприоритетным (99) задачам отдается предпочтение при доступе к ресурсам центрального процессора.
• Не задействует политику Completely Fair Scheduling (CFS).
• Использует политику SCHED_FIFO, либо же SCHED_RR.

Рис. 5 Сравнение kernet_rt со стандартным ядром.

На графике показан замер времени отклика из миллиона повторений для систем, использующих ядра RHEL Linux 7 и RHEL Real Time соответственно. Синие точки на этом графике представляют время отклика (в микросекундах) систем со стандартным ядром RHEL 7, а зеленые — RHEL 7 Real Time. Из графика видно, что особенность kernel-rt в гораздо меньшей дисперсии и, соответственно, в большей предсказуемости времени отклика системы.

Настройка и тестирование

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

Утилита hwlatdetect из пакета rt-tests покажет задержки, вызванные аппаратным и микропрограммным обеспечением, путем опроса источника тактовых импульсов и поиска непонятных пропусков.

В данном примере parameters указывает на задержку и способ обнаружения. Порог задержки по умолчанию был выставлен на 10 микросекунд (10 μs).

RT имеет также утилиту rteval для тестирования производительности системы в реальном времени под нагрузкой. Программа создаёт большую нагрузку на систему, используя планировщик SCHED_OTHER, а затем измеряет отклик в реальном времени на каждом из активных CPU. Цель в том, чтобы постоянно выполнялись различные задачи, такие как выделение / освобождение памяти, дисковый I/O, вычисления, копирование памяти и другие.

Каждый поток измерений берет временную метку, бездействует в течение некоторого интервала, а затем принимает другую временную метку после пробуждения. Задержка по результатам измерения равна t1 — (t0 + i) , где

• t1 — фактическое время измерения;
• t0 — теоретическое время пробуждения первой временной метки;
• i — интервал ожидания.

Отчет утилиты rteval выглядит так.

Использованные материалы

• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne Operating System Concepts 9-th edition.
• What are the benefits of running the Red Hat Enterprise Linux for Real Time?
• Working with the real-time kernel for Red Hat Enterprise Linux
• Advanced tuning procedures to optimize latency in RHEL for Real Time

Источник

Принцип работы планировщика задач в 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 для ознакомления с множеством материалов по смежным и другим интересным темам, а также обмена идеями.

Источник