МОДЕЛИРОВАНИЕ ПЛАНИРОВЩИКА ЗАДАЧ РЕАЛЬНОГО ВРЕМЕНИ

АННОТАЦИЯ

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

ABSTRACT

In this paper, the classification of real-time task scheduling algorithms is considered. A developed task scheduler emulator with the use of an agent approach to simulation modeling is described. A study of scheduling algorithms for several sets of periodic tasks using various algorithms, including dynamic ones, is carried out.

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

Keywords: emulator, task scheduling, real-time systems.

ВВЕДЕНИЕ

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

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

ПОСТАНОВКА ЗАДАЧИ

Цели данной работы:

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

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

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

• системная динамика;
• дискретно-событийное моделирование;
• агентное моделирование.

Кроме того, AnyLogic включает в себя графический язык моделирования, а также позволяет пользователю расширять созданные модели с помощью языка программирования Java. Интеграция компилятора Java в AnyLogic предоставляет более широкие возможности при создании моделей.

ТЕОРИЯ

1. Описание алгоритмов планирования

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

Наиболее срочная первой. Алгоритм планирования задач наиболее срочная первой (earliest deadline first – EDF) основан на использовании динамических приоритетов [1]. Согласно алгоритму EDF, активные задачи упорядочиваются по значению абсолютного срока выполнения, задача с наименьшим абсолютным сроком выполнения является наиболее приоритетной.

Необходимым и достаточным условием выполнимости множества задач является выполнение неравенства

                                                                 (1)

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

С наименьшим резервом первой. Алгоритм планирования задач с наименьшим резервом первой (least laxity first – LLF) [1, с. 232] – еще один алгоритм, использующий динамические приоритеты. Согласно алгоритму LLF, все активные задачи упорядочиваются по значению резерва времени, задача с наименьшим резервом является наиболее приоритетной.

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

Планирование, монотонное по частоте. Алгоритм планирования, монотонный по частоте (rate-monotonic scheduling – RMS) [1, с. 231], основан на использовании фиксированных приоритетов. Все задачи упорядочиваются по значению частоты порождения задачи (величине, обратной периоду задачи). Задаче с наибольшей частотой назначается максимальный приоритет. RMS является оптимальным алгоритмом в классе статических алгоритмов планирования.

Разработчиками алгоритма RMS был предложен метод анализа выполнимости набора задач, в котором критерием является так называемая граничная плотность загрузки (utilization bound). Если плотность загрузки процессора не превышает расчетной границы, то набор задач выполним всегда [2]. Ниже приведены формулы для расчета граничной плотности загрузки для n задач и основное условие критерия:

При больших n значение граничной плотности загрузки сходится к 69%. Отсюда следует, что любое множество задач выполнимо, если суммарная плотность загрузки процессора не превышает 69%. Применение этого критерия называют частотно-монотонным анализом выполнимости приложения реального времени (rate-monotonic analysis – RMA).

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

2. Описание разработанной модели

Была разработана программа, позволяющая моделировать планирование набора периодических задач в соответствии с конкретными алгоритмами (EDF, LLF, RMS).

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

Разработан агент Task, расширяющий возможности стандартного агента в системе AnyLogic и содержащий поля и методы для имитации поведения отдельного экземпляра задачи. По расписанию (в соответствии с периодами) экземпляры задач помещаются в популяцию текущих задач currentTasks, откуда они поступают в сервис scheduler (планировщик). Обрабатываемые задачи сортируются в соответствии с методом приоритезации, предусмотренным алгоритмом. Планировщик выделяет ресурс processor задаче с наивысшим приоритетом. Графический вид модели представлен на Рис. 1.

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

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

Рисунок 1. Графическое представление модели в системе AnyLogic

Результаты экспериментов

Время моделирования – 50 мс.

На графиках задачи отображены сверху вниз в соответствии с номерами, горизонтальная ось – временная, на вертикальной отложены номера задач. Серые прямоугольники соответствуют выполнению соответствующей задачи в текущий момент времени, черные стрелки, направленные вверх – начало периода, стрелки с пометкой «Deadline Missed» – пропуск крайнего срока.

При проведении моделирования были рассмотрены три набора задач. Все параметры указаны в миллисекундах.