Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: Научного журнала «Инновации в науке» № 6(82)

Рубрика журнала: Информационные технологии

Скачать книгу(-и): скачать журнал

Библиографическое описание:
Кобылянский В.Г., Рябец М.А. МОДЕЛИРОВАНИЕ ПЛАНИРОВЩИКА ЗАДАЧ РЕАЛЬНОГО ВРЕМЕНИ // Инновации в науке: научный журнал. – № 6(82). – Новосибирск., Изд. АНС «СибАК», 2018. – С. 19-23.

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

Кобылянский Валерий Григорьевич

канд. техн. наук, доцент кафедры теоретической и прикладной информатики Новосибирского государственного технического университета,

РФ, г. Новосибирск

Рябец Михаил Александрович

магистрант кафедры теоретической и прикладной информатики Новосибирского государственного технического университета,

РФ, г. Новосибирск

MODELING OF THE REAL-TIME TASK SCHEDULER

 

Valery Kobylyansky

Candidate of Science, assistant professor of Theoretical and Applied Informatics department, Novosibirsk State Technical University,

Russia, Novosibirsk

Mihail Ryabets

Master of Science, Theoretical and Applied Informatics department, Novosibirsk State Technical University,

Russia, Novosibirsk

 

АННОТАЦИЯ

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

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 analysisRMA).

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

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

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

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

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

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

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

 

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

 

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

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

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

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

 

Рисунок 2. График обработки первого набора задач (алгоритм RMS)

 

Рисунок 3. График обработки первого набора задач (алгоритм EDF)

 

  1. Рассматривается набор из трех задач.

Task1, Task2 и Task3 имеют периоды 10, 7 и 9, время выполнения 4, 1 и 5 соответственно, плотность загрузки – 1.098.

Результаты выполнения программы для первого набора задач приведены в Табл. 1.

Таблица 1.

Результаты выполнения программы для первого набора задач

 

Алгоритм

Задача

(номер/период/время выполнения)

Количество успешных запусков

Количество пропущенных крайних сроков

Среднее время ответа

RMS

1,10,4

0

5

-

2,7,1

8

0

1

3,9,5

5

0

6

EDF

1,10,4

4

1

10

2,7,1

7

0

4.43

3,9,5

4

1

7.5

LLF

1,10,4

0

5

-

2,7,1

8

0

1.63

3,9,5

5

0

8.4

 

Можно отметить, что только EDF оказался способен запустить первую задачу, потому что RMS-планировщик пытается как можно чаще ответить на задачу с меньшим периодом, а LLF пытается как можно чаще реагировать на задачи с наименьшим свободным временным окном.

Также можно заметить, что разброс времени отклика для EDF меньше, чем для RMS и LLF.

  1. Рассматривается набор из трех задач.

Task1, Task2 и Task3 имеют периоды 3, 4 и 5, время выполнения 1, 1 и 2 соответственно, плотность загрузки – 0.983.

Результаты выполнения программы для второго набора задач приведены в Табл. 2.

Таблица 2.

Результаты выполнения программы для второго набора задач

Алгоритм

Задача

(номер/период/время выполнения)

Количество успешных запусков

Количество пропущенных крайних сроков

Среднее время ответа

RMS

1,3,1

17

0

1

2,4,1

13

0

1.38

3,5,2

9

1

3.89

EDF

1,3,1

17

0

1.12

2,4,1

13

0

1.93

3,5,2

10

0

3.8

LLF

1,3,1

17

0

1

2,4,1

13

0

1.38

3,5,2

9

1

3.89

 

RMS и LLF не справляются с планированием выполнения задачи 3, так как она вытесняется задачами 1 и 2. Однако EDF учитывает приближающийся крайний срок выполнения задачи и справляется с временными ограничениями.

RMS и LLF имеют одинаковый график, потому что RMS и LLF рассматривают задачи в одинаковом порядке.

Task1, Task2 и Task3 имеют свободное окно, равное 2, 3 и 3 соответственно (в начальный момент времени).

Так как все задачи могут быть завершены с общим временем 1 + 1 + 2 = 4 < 5 (максимальный период в наборе задач), то порядок, в котором RMS и LLF реагируют на задачи, в обоих случаях одинаковый.

  1. Рассматривается набор из трех задач.

Task1, Task2 и Task3 имеют периоды 5, 10 и 4, время выполнения 4, 3 и 2 соответственно, плотность загрузки – 1.6.

Результаты выполнения программы для третьего набора задач приведены в Табл. 3.

Таблица 3.

Результаты выполнения программы для третьего набора задач

Алгоритм

Задача

(номер/период/время выполнения)

Количество успешных запусков

Количество пропущенных крайних сроков

Среднее время ответа

RMS

1,5,4

0

10

-

2,10,3

0

5

-

3,4,2

13

0

2

EDF

1,5,4

0

10

-

2,10,3

0

5

-

3,4,2

10

2

2.7

LLF

1,5,4

0

10

-

2,10,3

0

5

-

3,4,2

10

3

2.8

 

RMS-планировщик пытается как можно чаще ответить на задачу с меньшим периодом (задача 3).

ОБСУЖДЕНИЕ РЕЗУЛЬТАТОВ

EDF во всех трех случаях пытается выполнить задачи с самым ранним крайним сроком, распределяя таким образом время между задачами. Можно понять это, посмотрев на количество пропусков крайних сроков в первых двух случаях. В третьем случае EDF оказался хуже RMS, потому что пытался выполнить задачу 1, которой требуется 80% процессорного времени, и которая практически наверняка пропустит свой крайний срок.

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

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

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

 

Список литературы:

  1. Kopetz H. Real-Time Systems. Design Principles for Distributed Embedded Applications. – Dordrecht: Kluwer Academic Publishers, 1997, p. 338.
  2. Данилов М. Методы планирования выполнения задач в системах реального времени. // Программные продукты и системы. – 2001. – №4.

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом