Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
Решение задачи построения расписания
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 3.1. Схема кодирования
- 3.2. Функция качества
| 3. Решение задачи построения расписания
Для решения задачи построения расписания был использован ге- нетический алгоритм. Далее изложены основные решения, применен- ные при его создании. 3.1. Схема кодирования ГА-строка G={G 1 , G 2 , … G n } состоит из символов G i =(P i , R i ), где P i – это процессор, на котором будет исполняться задача T i , а R i – приоритет задачи. При составлении расписания по ГА-строке, значе- 154 ние R i используется тогда, когда в один и тот же момент времени на исполнение процессором P i претендует более одной задачи. 3.2. Функция качества В реализованном алгоритме, значением функции качества была выбрана длина соответствующего расписания. Вместо нее может быть выбрана любая другая функция, например, средняя загрузка системы, ускорение относительно последовательного выполнения программы, стоимость счета распределенной задачи при оплате процессорного времени и др. Таким образом, каждый раз, когда вычисляется функция качества, генетический алгоритм, используя закодированную ГА-строку, строит по ней расписание выполнения задач. Для построения расписания используется дискретный счетчик «те- кущего» времени, который принимает те значения, при которых осво- бождается очередной процессор. Также используются 3 пула задач: 1) уже распределенных на процессоры, 2) еще не распределенных, но уже (в текущий момент времени) готовых к выполнению и 3) не готовых к выполнению. Сначала выбираются все задачи, не имеющие внешних входных данных, и по возможности (с использованием приоритетов в случае коллизий) распределяются на «свои» процессоры. Затем увели- чивается счетчик, перестраиваются пулы 1,2,3 и по возможности (с использованием приоритетов в случае коллизий), готовые задачи рас- пределяются на «свои» свободные процессоры. Процесс заканчивается в случае отсутствия направленных циклов в графе алгоритма, когда все пулы, кроме 1, пусты. В случае некорректного графа алгоритма все процессоры освободятся, но ни одной задачи в пуле 2 не будет, при том, что пул 3 будет не пуст. Этим можно воспользоваться, чтобы оп- ределять корректность расписания. Также при построении расписания активно используется функция send (на самом деле время старта зада- чи с максимальным приоритетом на «ее» процессоре после его осво- бождения откладывается до прихода всех данных). Последний факт не означает, что в случае больших объемов передаваемых данных алго- ритм обязательно будет строить неоптимальные расписания по гене- тическому коду, т.к. существует система приоритетов, изменение ко- торых в коде могут привести к перестановке задач в расписании. Про- блема не является критичной, т.к. при наличии хотя бы 2-х процессо- 155 ров в системе перемещение конфликтующих задач с процессора на процессор может дать оптимальный результат. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|