21 Вопрос. Планирование в системах реального времени

Внешние события, на которые система должна реагировать, можно разделить на периодические (возникающие через регулярные интервалы времени) и непериодические (возникающие непредсказуемо). Возможно наличие нескольких периодических потоков событий, которые система должна обрабатывать. В зависимости от времени, затрачиваемого на обработку каждого из событий, может оказаться, что система не в состоянии своевременно обработать все события. Если в систему поступает m периодических событий, событие с номером i поступает с периодом P_i и на его обработку уходит С_i, секунд работы процессора, все потоки могут быть своевременно обработаны только при выполнении условия

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

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

Таненбаум Э. Современные операционные системы. 2-е изд

5. Использование различных алгоритмов для разных классов процессов (на примере ядра Linux, например). Реальные алгоритмы планирования, несводимые к fifo/rr (например, взять O(1)-планировщик, как уже описанный). Проблема балансировки нагрузки в SMP-системах и её решение.

Необязательно планировать все задачи одинаковым образом. Поэтому вводится понятие «классы планирования». Для разных классов процессов используются различные классы планирования. У процессов разных классов планирования свои уровни приоритета и свои очереди на выполнение.

Из лекций:

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

22 Вопрос. Иерархия классов в Linux: rt, cfs, idle, stats.

В существующем планировщике имеется четыре класса планирования задач:

1. sched_rt (real-time), очереди с fifo, для rt-задач;

2. sched_cfs (completely fair scheduler), основной;

3. sched_idle, используется системой, когда первым двум классам нечем занять процессор;

4. sched_stats.

Каждый класс представлен структурой sched_class. Она содержит указатели на функции, связанные с помещением готовой задачи в очередь, извлечением её оттуда, балансировкой нагрузок и так далее. Основные из них:

• enqueue_task: эта функция вызывается, когда задача переходит в запущенное состояние.

• dequeue_task: когда задача завершает работу, эта функция вызывается для исключения соответствующей сущности.

• check_preempt_curr: эта функция проверяет, может ли быть выгружена работающая на данный момент задача.

• pick_next_task: эта функция выбирает наиболее подходящий для запуска в следующую очередь процесс.

• load_balance: в каждом модуле планировщика реализуется пара функций load_balance_start() и load_balance_next(), реализующая итератор, который вызывается в процедуре load_balance модуля. Основной планировщик с помощью этого метода балансирует нагрузку процессов, управляемых модулем планировщика.

• set_curr_task: эта функция вызывается, когда изменяется класс планирования или группа задач для задачи.

• task_tick: эта функция чаще всего вызывается из таймерных функций; она может вызвать переключение процесса. Это обеспечивает вытесняющую многозадачность для работающих процессов.

FIFO соответствует планированию в порядке линейной очереди. Процесс будет работать до тех пор, пока не:

• будет заблокирован на примитиве синхронизации

• явно не отдаст CPU

RR (Round-Robin, кольцевая очередь) соответствует планированию с квантами времени, когда процессы исполняются либо до момента явной отдачи управления, либо до истечения кванта времени. При истечении кванта времени процесс устанавливается в конец очереди.