ПРОГРАММИРОВАНИЕ, 2014, No 1, с. 36-44
= РАСПРЕДЕЛЕННЫЕ ВСТРОЕННЫЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ
•V. 'К ••».
НЕКОТОРЫЕ АЛГОРИТМЫ АНАЛИЗА И СИНТЕЗА МНОГОПРОЦЕССОРНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
РЕАЛЬНОГО ВРЕМЕНИ
© 2014 г. М.Г. Фуругян МГУ им. М.В. Ломоносова, факультет вычислительной математики и кибернетики 119991 Москва, Ленинские Горы мкр., 1, корп.2, стр. 52 E-mail: rtsccas@yandex.ru Поступила в редакцию 08.04.2013
Исследуется задача составления расписаний с прерываниями в многопроцессорной вычислительной системе реального времени с директивными интервалами. Разработаны приближенные алгоритмы, основанные на обобщении однопроцессорного алгоритма относительной срочности, и проведен их сравнительный анализ с точным потоковым алгоритмом. Разработан алгоритм для случая, когда запросы на выполнение работ поступают циклически с заданными периодами. Разработан алгоритм нахождения производительностей процессоров, при которых существует допустимое расписание для заданного множества работ с директивными интервалами.
1. ВВЕДЕНИЕ
Одна из основных задач, возникающих при разработке программного обеспечения многопроцессорных вычислительных систем жесткого реального времени (МПВСРВ, систем, в которых заданиям сопоставляются директивные сроки, не подлежащие нарушению), заключается, во-первых, в создании математической модели, адекватной реальной вычислительной системе, и во-вторых, в расчете с помощью этой модели режима функционирования системы, в результате которого получается расписание, показывающее, когда и какой программе должны быть выделены те или иные ресурсы ЭВМ. Это необходимо для обеспечения работоспособности и надежности таких систем. В данной статье рассматриваются эффективные алгоритмы составления расписаний для МПВСРВ.
Рассматриваемый класс задач имеет, помимо чисто научной, большую практическую важность. Потребность в быстрых алгоритмах, составляющих многопроцессорные расписания, часто возникает в задачах оперативного управления на основе обработки и анализа поступающих в реальном времени данных. В качестве приме-
ров можно привести задачи управления работой ядерных реакторов, управления испытаниями летательных аппаратов, анализа текущей ситуации в космосе на предмет оповещения об атаке баллистическими ракетами и многие другие практические задачи управления, в которых для принятия адекватных решений нужно успевать обрабатывать данные в темпе поступления. Корректность систем реального времени зависит не только от правильности результатов ее вычислений, но и от времени, за которое эти результаты были получены. Составление расписаний реального времени - важная часть подобных систем, так как все задания должны быть выполнены в срок. Большое число алгоритмов, которые могут быть использованы в МПВСРВ, содержится
в[1].
В разд. 2 рассматривается задача составления допустимого расписания с прерываниями при заданных сложностях (или объемах) работ, директивных интервалах и производительностях процессоров. Разработаны эвристические алгоритмы для случая, когда издержки на обработку прерываний и переключений не учитываются. Алгоритмы основаны на обобщении известного однопроцессорного алгоритма относительной
срочности. Вычислительная сложность предложенных алгоритмов значительно меньше сложности точного потокового алгоритма, что подтверждается также машинными экспериментами (выигрыш во времени составляет до нескольких тысяч раз). При этом процент некорректной работы алгоритмов незначительный (от 1 до 20% в зависимости от параметров задачи).
В разд. 3 рассматривается задача построения допустимого расписания с прерываниями для случая, когда имеется несколько различных по производительности процессоров, работы допускают прерывания, а требования на выполнение работ поступают циклически с заданными периодами. Случай циклического выполнения работ на одном процессоре описан в [2, 3].
В разд. 4 рассматривается своего рода обратная задача по отношению к тем, которые исследованы в разд. 2, 3, а именно, задача построения такой системы жесткого реального времени, в которой допустимое расписание заведомо существует при заданных условиях задачи.
2. ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ ПОСТРОЕНИЯ РАСПИСАНИЙ
2.1. Постановка задачи
Сформулируем задачу о допустимом многопроцессорном расписании для системы жесткого реального времени следующим образом. Рассматривается вычислительная система, состоящая из т процессоров. Каждый процессор .](.] = 1,..., т) характеризуется производительностью вз. Предполагается, что процессоры упорядочены по не возрастанию производительностей (в1 > в2 > ••• > вт). Задан набор работ N = {1, 2,..., п}, подлежащих выполнению. Каждая работа г характеризуется своим директивным интервалом А = (г^, (т.е. работа г может быть начата после момента времени г% и должна быть выполнена не позднее момента времени (¿), а также сложностью (или объемом работы процессоров по ее выполнению) Qi (г = 1,... ,п). Работа сложности Qi может быть выполнена на процессоре ] за время Qi/sj. В фиксированный момент времени каждая работа может выполняться не более чем одним процессором и каждый процессор может выполнять не более одной работы. При выполнении работ допускаются
прерывания и переключения с одного процессора на другой. Предполагается, что прерывания и переключения не требуют временных затрат. Задача состоит в том, чтобы определить, существует ли расписание, позволяющее выполнить все работы в их директивные интервалы на имеющихся процессорах и, в случае положительного ответа, указать такое расписание. Будем называть в дальнейшем такое расписание допустимым расписанием, а саму задачу - поиском допустимого расписания.
2.2. Точный алгоритм
Алгоритм, находящий точное решение рассматриваемой в этом разделе задачи был разработан и реализован как комбинация полиномиальных алгоритмов, предложенных в [4] и [5]. Будем предполагать, что имеется Ь типов процессоров, каждый из которых характеризуется скоростью вз (] = 1, ..., Ь), всего имеется т(] = 1, ..., Ь) процессоров ^'-го типа, т = ^3=1 .
В [4] доказывается, что такая задача может быть сведена к задаче поиска максимального потока в сети, построенной специальным образом. Для поиска максимального потока в построенной сети применялся алгоритм "поднять-и-в-начало", описанный в [6]. Предложенный алгоритм находит точное решение задачи о многопроцессорном расписании за время 0(Ь3п3), допуская при этом не более 2 (п2 + 2тп — 3п — т + 1) прерываний. Несмотря на то, что предложенный алгоритм является полиномиальным, время его работы в ряде случаев является слишком большим для практического применения в задачах достаточно большой размерности, имеющих практический смысл и возникающих при разработке МПВСРВ. Одним из решений возникшей проблемы может быть разработка существенно более быстрого эвристического алгоритма, который находил бы правильное решение задачи в достаточно широком спектре случаев.
Построим и проанализируем два эвристических алгоритма, эффективно решающих поставленную задачу. Оба эти алгоритма будут являться обобщениями однопроцессорного алгоритма Коффмана [2] на случай нескольких процессоров с различными производительностями. Назовем эти два алгоритма Эвристика 1 и Эвристика 2.
2.3. Эвристические алгоритмы
Пусть п < т2 < ■ ■ ■ < тк (к < 2п) - все различные моменты времени, в каждый из которых либо завершается выполнение одной или нескольких работ, либо наступает готовность одной или нескольких работ, либо происходят оба эти события. Работа г завершается, когда суммарный объем работы процессоров по ее выполнению становится равным Qi (если работа в течение интервала времени величиной А выполняется процессором то объем выполненной работы составляет в]А). В момент т наступает готовность работы г, если т = ri. Величины тг вычисляются в ходе работы алгоритма следующим образом.
,р - все различные ве-
Пусть ai < а2 < ■ ■ ■ < а,
личины n(i = 1,..., n). Тогда полагаем Ti = ai. Пусть Aj = Qi/sj, если на процессоре j в момент ^выполняется работа i (Qi - невыполненный объем работы i к моменту ti), и Aj = 0, если процессор j в момент т простаивает. Пусть A = min {Aj : Aj > 0}. Далее, полагаем
j=1,...,m
Ti+1 = min{Ti + A, av}, если т e [a^-i, av), (1 < v < p) и т1+1 = т + A, если т1 > ap.
Для каждого момента Ti(l = 1,..., k) определим два множества: C - множество работ, выполняемых в момент Ti, и D множество работ, готовых к выполнению в момент т. Введем обозначения: если C = 0, то ii - это работа из C с наибольшим директивным сроком, т.е. di1 = max di;
iEC
если D = 0, то i2 - это работа из D с минимальным директивным сроком, т.е. di2 = min di. Ал-
i€D
горитм Эвристика 1 основан на следующих трех процедурах.
Ti
пает готовность работы io, то io включается в D. Если таких работ несколько, включение выполняется поочередно в произвольном порядке.
Ti
io e C, которая выполнялась на процессоре j0,
C,
jo
ко, данная процедура выполняется для каждой из них в произвольном порядке.
Ti
процессоры заняты, то работа i2 e D назначается на свободный процессор с минимальным номе-
ром, включается в С и исключается из О. Если свободных процессоров нет, ^ > ,и работа г1 выполнялась на процессоре ^о, то работа г1 снимается с процессора ^работа г2 исключается из О, назначается на процессор ^'о и включается в С, а работа г1 включается в О.
Величины ^^ ^^^ работ г £ С хранятся в виде кучи с максимальным элементом в вершине, а величины ^^ ^^^ раб от г £ О хранятся в виде кучи с минимальным элементом в вершине. Таким образом, в вершине первой кучи хранится значение ^, а в вершине второй кучи - значение di2. Добавление элементов в множества С и О и исключение их предполагает такие преобразования этих множеств, при которых сохраняется основное свойство кучи [6].
Алгоритм Эвристика 1. Для каждого I = 1, 2,..., к выполнять шаги 1-4.
1. Вычислить тг.
2. Выполнить процедуру 1. (Пусть Н - число работ, готовность которых наступила в момент тг.)
3. Выполнить процедуру 2.
4. Выполнять процедуру 3 до тех пор, пока изменяется множество О (но те более Н раз).
Вычислительная сложность шага 1 и процедур 1, 2 и 3 (
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.