Разработка алгоритмов функционирования вычислительной системы
В реальных условиях эксплуатации вычислительные системы рассчитаны на непрерывное поступление заданий. Два последовательно найденных расписания должны удовлетворять условию сопряжения. Другими словами, между выполнением заданий этих расписаний не должно быть лишнего времени простаивания вычислительных ресурсов, если того не требуют сами задания.
На следующем рисунке 13 показан пример сопряженных расписаний выполнения непараллельных заданий.
|
Рисунок 13. Пример двух сопряженных расписаний 
и 
запуска непараллельных заданий
На рисунке 13 схематически изображены два сопряженных расписания и для системы из трех ВУ, которые обозначены как 
, 
и 
. Для каждого расписания , на основании предыдущего расписания , формируются холостые слоты-ограничители, размещаемые в самом “начале”. На указанные слоты алгоритм составления расписаний не должен оказывать влияния. В результате эти слоты ограничивают по времени запуска процессы 
, обеспечивая максимально плотную состыковку двух последовательных расписаний. За момент времени 
на данном рисунке обозначеноначало участка расписания , на основании которого создаются холостые слоты-ограничители в расписании .
На рисунке 14 показан пример сопряженных расписаний выполнения параллельных заданий. Для каждого нового расписания на основании предыдущего расписания формируется множество холостых слотов ограничителей аналогично ситуации с непараллельными заданиями.
|
|
|
|
Рисунок 14. Пример двух сопряженных расписаний и выполнения параллельных заданий
Схема планирования выполнения заданий с составлением расписаний генетическим алгоритмом для РВС изображена на рисунке 8.
Формальное описание алгоритма планирования, схематически изображенного на рисунке 15, следующее.
1. Задается начальный номер периода планирования 
.
2. По истечении отрезка времени 
составляется множество непротиворечивых допустимых расписаний для заданий, поступивших в этот период. Для этого запускается генетический алгоритм с передачей ему на вход множества процессов и множества 
всех ВУ в РВС. Запущенный ГА завершает поиск расписаний только по окончанию периода планирования 
.
|
Рисунок 15. Схема планирования заданий в РВС
3. Из множества найденных генетическим алгоритмом расписаний выбирается лучшее расписание согласно целевой функции.
4. Если 
, то работа алгоритма завершается.
5. Задается новый номер периода планирования 
.
6. Осуществляется переход на шаг 2.
Система планирования непрерывно накапливает задания, поступившие к ней от пользователей. В конце каждого периода множество заданий, поступивших в этот период, фиксируется, и для них составляется расписание. Все последовательно составленные расписания 
помещаются в общий пул расписаний, образуя единый план выполнения заданий. Система планирования должна следить за изменениями пула расписаний запускать задания на узлах РВС в определенный соответствующим расписанием момент времени.
|
|
|
Так как для каждого множества процессов можно составить несколько расписаний, то введение целевой функции позволяет ранжировать полученные для каждого периода планирования расписания согласно их эффективности.
Часто в качестве критериев оценки расписаний используются критерий длины расписания и среднего взвешенного времени прохождения процессов. Пусть для одного множества процессов можно составить несколько расписаний: 
. Под длиной 
расписания 
понимается следующая величина:
Тогда лучшим расписанием 
будет расписание с минимальным значением его длины:
Целевая функция с критерием среднего взвешенного времени прохождения процессов в расписании S q определяется следующим образом:
где 
вес процесса 
при запуске его на ВУ 
, 
и | 
| - начало и длина слота 
соответственно, 
, 
множество номеров ВУ, с которыми сопоставлены слоты в расписании , 
- число слотов в расписании .
|
|
|
Обе эти целевые функции имеют существенные достоинства и недостатки при применении в качестве функции пригодности в генетических алгоритмах для составления расписания в РВС. Длина расписания учитывает лишь последние по времени завершения процессы и плохо “справляется” с уплотнением остальных процессов. Критерий среднего взвешенного “справляется” с уплотнением расписания. Тем не менее, значение целевой функции с этим критерием существенно зависит от порядка следования слотов на ВУ. Для равнозначных расписаний это ведет (при большом числе сильно различающихся по длине слотов) к существенно различным значениям целевой функции, что мешает работе генетических алгоритмов.
Для устранения вышеописанных недостатков, а также в целях учета приоритета заданий в разработанных автором алгоритмах используется следующая целевая функция:
где 
- множество номеров ВУ, которым сопоставлены слоты из расписания 
; 
- множество номеров слотов, сопоставленных с ВУ ;G - число всех виртуальных узлов в РВС; 
- длина слота 
; 
- вес процесса 
при запуске его на ВУ . Вес процесса наВУ необходим для учета его приоритета: 
, где 
- приоритет процесса , 
- порядковый номер следования слота 
на ВУ .Приоритет процесса равен установленному администратором приоритету для каждой из очередей заданий, с которой задание данного процесса сопоставлено.
|
|
|
В программной реализации целевой функции при больших значениях 
вес процесса 
может превысить максимальное число, которое можно представить типом данных. Решением данной проблемы может стать масштабирование . Так, в исследуемых программных реализациях алгоритмов значение масштабировалось как 
.
Дата добавления: 2019-08-31; просмотров: 243; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!