Отбор подходящих слотов

В каждом цикле планирования на основе локальных расписаний для каждого задания пакета должно быть отобрано требуемое число подходящих по ресурсу, цене и времени слотов. Множество доступных слотов известно к началу каждого цикла планирования. Локальные расписания представляются неупорядоченными по времени доступными слотами (рис. 3.1, а). Выполнение параллельного задания может начаться при согласованном выделении слотов таким образом, чтобы параллельные процессы, соответствующие задачам задания, стартовали одновременно. Для однородных ресурсов с процессорами одинаковой производительности и задачами примерно одинаковой сложности из совокупности доступных слотов требуется выделить прямоугольное «окно» , где – время использования слотов. В случае неоднородных узлов и существенно различных по сложности задач это - непрямоугольное «окно», с неровным правым краем.

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

1°. Доступные слоты (см. рис. 3.1, а) упорядочиваются по неубыванию времени старта (рис. 3.1, б и в).

2°. Из полученного на шаге 1° списка выбирается очередной подходящий по ресурсу, цене и длительности слот .

3°. Из списка ранее просмотренных подходящих слотов от 1 до удаляются слоты с временем окончания , где .

4°. Шаги 2°, 3° повторяются до тех пор, пока не наберется заданное число слотов.

а

б

в

Рис. 3.1. Отбор слотов для выполнения задания

Заметим, что в этой схеме на шаге 2° фигурирует не только время, но и требования к ресурсу и цене.

В примерах, иллюстрируемых рис. 3.1, =3. Время запуска задания определяется временем начала последнего из отобранных подходящих слотов (на рис. 3.1 это слот 6). Время окончания выполнения задания зависит от , это - максимум длительности выполнения задачи соответствующего задания по всем отобранным слотам (на рис. 3.1, в ему соответствует слот 4).

Рассмотренная выше схема применяется для каждого из заданий пакета. Сначала делается попытка найти комбинацию подходящих слотов для всех заданий пакета. Если для какого-либо из заданий такого набора не существует, его планирование переносится в следующий цикл и задание занимает место в очереди в соответствии с заданным приоритетом, например в начале очереди. При успешном отборе слотов для -го задания список просматриваемых слотов для -го задания модифицируется. Из соответствующих временных отрезков исключаются периоды, занятые выполнением -го задания. Отбор слотов для -го задания осуществляется на модифицированном списке по вышерассмотренной схеме. После просмотра слотов для всех заданий пакета отыскиваются альтернативные наборы, поскольку при отборе слотов для каких-либо заданий не весь исходный список может быть просмотрен. Эта процедура итеративно повторяется для всех заданий, планирование которых не перенесено в следующий цикл. В очередном цикле совокупность доступных слотов (см. рис. 3.1, а) обновляется в соответствии с динамикой загрузки локальных узлов распределенной среды.

В табл. 3.1 приведен пример числовых характеристик наборов слотов для пакета из трех заданий. Параметр связан с временем , которое указывает пользователь в ресурсном запросе, при этом на условиях соответствующей оплаты . Вопросы ценообразования и пересчета в выходят за рамки данного пособия. Параметры , – исходные данные для выбора оптимальной или эффективной комбинации слотов. Согласно обозначениям, введенным в разделе 3.2, , и . Так, для задания 1 существует три альтернативных набора слотов, для заданий 2 и 3 – соответственно два и четыре набора подходящих слотов. Каждое из заданий использует один и только один набор слотов. Наборы слотов и могут разделяться всеми тремя заданиями, набор – заданиями 1 и 3, набор может быть выделен лишь заданию 3.

Таблица 3.1

Номер набора	Задание 1	Задание 2	Задание 3
слотов
			-	-
	-	-	-	-

Прочерки в соответствующих позициях табл. 3.1 означают, что в данном наборе отсутствуют подходящие для данного задания слоты. Например, для задания 1 альтернативные варианты подходящих слотов имеются в наборах и отсутствуют в наборе , а для задания 2 подходящими являются наборы и , в наборах и подходящих слотов нет. В соответствии с рассмотренной схемой отбора прочерки в столбцах табл. 3.1 могут быть расположены лишь после параметров, соответствующих наборам подходящих слотов. Комбинация для выполнения пакета – тройка наборов слотов.