Разделение ресурсов с владельцами

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

На практике применяются два варианта разделения ресурсов между локальным и глобальным потоками.

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

2. Ресурсы кластера образуют одно множество. Задания грид запускаются в СПО с некоторым фиксированным приоритетом.

И первый, и второй вариант имеют недостатки и не позволяют эффективно управлять разделением ресурсов. В первом варианте одна часть ресурсов будет простаивать, если нет распределяемых на эту часть заданий, в то время как ресурсов для обслуживания заданий другого сорта может не хватать. Имеющаяся статистика показывает [34], что при таком статическом разделении средний уровень использования ресурсов не превышает 25%. Во втором варианте время получения ресурсов глобальными заданиями будет неопределенным, так как оно зависит от приоритетов локальных заданий, находящихся в СПО. Если же глобальным заданиям присваивается максимально возможный приоритет, то они всегда будут иметь преимущественное право получения ресурсов, и при интенсивном их потоке обработка локальных заданий может быть блокирована полностью.

Мы предлагаем соглашение о разделении ресурсов, которое осуществляет динамическую балансировку потоков заданий. Соглашение состоит в том, что ресурсы, которые получает глобальное задание, должны оплачиваться, и глобальное задание может занять ресурсы при условии, что назначенная пользователем при его запуске плата не меньше их стоимости. Принципиальной особенностью этого соглашения является то, что стоимость ресурсов меняется во времени и определяется не только их объемами, а вычисляется с учетом приоритетов локальных заданий, которое могут занять те же ресурсы. Цена использования ресурсов в единицу времени задается формулой PR(t)=C*P(t)*F(R), где F(R) – неубывающая функция, зависящая от объема ресурсов R каждого типа, которыми располагает компьютер, а P(t) – приоритет локального задания, которое должно выполняться на компьютере во время t. Это дает гибкий механизм балансировки потоков, позволяющий, с одной стороны, администратору кластера путем изменения цены ресурсов (коэффициент C) ограничивать интенсивность потока внешних заданий (при достаточно больших значениях коэффициента C глобальные задания вообще не будут поступать в кластер), и, с другой стороны, дающий возможность пользователю грид влиять на скорость получения ресурсов для своих заданий, повышая плату.

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

СХЕМА ОПЕРЕЖАЮЩЕГО ПЛАНИРОВАНИЯ

Представим схему опережающего планирования следующим псевдокодом.

 

1. Цикл планирования:

{

2. Получение стоящих в очереди заданий грид;

3. Получение расписаний всех кластеров;

4. Цикл размещения заданий:

{

5. Построение аллокации для задания;

6. Если время начала аллокации близко:

7. { резервирование; доставка задания в кластер;}

}

}

 

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

Первые два оператора цикла планирования получают из информационной базы стоящие в глобальной очереди задания (оператор 2) и множество локальных расписаний (3). Заполнение информационной базы осуществляется отдельным процессом, который может работать параллельно с процессом планирования. Каждый цикл планирования, однако, происходит при фиксированном состоянии информационной базы, а происходящие за время одного цикла изменения состояния учитываются на следующем. Локальные расписания объединяются в общий массив слотов, по которому ведется планирование глобальных заданий.

Собственно планирование заключается в построении аллокаций для заданий в порядке их приоритетов. Обозначим N требуемое заданию количество процессорных узлов, и T - длительность выполнения задания. Задача построения аллокации (5) состоит в том, чтобы найти такие N процессорных узлов и такой интервал времени [t₀, t₀+T], на котором ресурсы этих процессорных узлов могут быть выделены данному заданию. Возможность выделения определяется следующими условиями:

- характеристики ресурсов каждого процессорного узла соответствуют ресурсному запросу задания,

- суммарная стоимость ресурсов, вычисляемая по слотам, попадающим в интервал действия аллокации, не превышает платы за ресурсы, назначенной пользователем.

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

Способ отбора аллокаций (6), для которых необходимо инициировать запуск заданий, иллюстрирует рис. 3.

 

Рис. 3. Выбор времени запуска задания.

 

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

Что же касается минимального упреждения, необходимого для обеспечения запуска задания, то оно определяется двумя условиями. Первое условие: упреждение должно быть таким, чтобы ресурсы аллокации не оказались занятыми локальными заданиями. При этом надо учесть, что эти ресурсы могут освободиться раньше прогнозируемого в расписании времени. Если происходит такое “преждевременное” освобождение ресурсов, на них может начать выполняться локальное задание, окончание которого происходит после начала аллокации. В связи с этим, первое условие начала доставки задания задается неравенством: T_пс>T_ц, где T_пс – начало слота, непосредственно предшествующего аллокации на тех же ресурсах, T_ц – время начала цикла планирования.

Второе условие заключается в том, что должно хватать времени для передачи задания на исполнительные ресурсы. Процесс передачи включает пересылку всех его входных файлов, так что время передачи может быть значительным. Это условие можно записать в виде: (T_а-T_ц)>T_пз, где T_а – время начала аллокации, T_пз – время передачи задания.

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

СРАВНЕНИЕ С СОВРЕМЕННЫМИ ПЛАНИРОВЩИКАМИ

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

Большинство разработок предназначены для обслуживания кластеризованных ресурсов, в том числе система WMS [8] наиболее крупного на сегодняшний день грид проекта EGEE [44], имеющего мировой масштаб. Брокер системы WMS реализует централизованную схему планирования, работающую в двух режимах распределения заданий: жадного и ленивого (ленивый режим был впервые реализован в проекте Alien [45]). В жадном режиме распределение заданий происходит без глобальной очереди: поступившее в брокер задание сразу же отправляется в некоторый кластер. Для выбора кластера используется информационная база, содержащая данные о текущем состоянии всех ресурсов грид. Задания, запускаемые пользователями в ленивом режиме поступают в глобальную очередь. Кластеры, имеющие свободные ресурсы, информируют брокер о характеристиках свободных ресурсов, а тот, выбирая из очереди подходящее задание, передает его в кластер.

В обоих режимах происходит сопоставление характеристик ресурсов и заданий на предмет выяснения возможности выполнения. Информационная база жадного режима, построенная на информационной службе MDS [19] системы Globus Toolkit [14], недостаточно полна: она не содержит данных, описывающих процессорные узлы, так что этот режим может использоваться только в грид с однородными ресурсами. Сопоставление характеристик ресурсов и заданий в ленивом режиме производится на основе метода matchmaking [15] и не имеет такого недостатка.

Основное решение планирования – выбор исполнительных ресурсов – в жадном режиме делается по интегральной характеристике состояния кластера: выбирается тот, у которого в локальной очереди меньше всего заданий. Как было показано, это потенциально ведет к зависанию заданий, тем более, что глобальная очередь в этом режиме не поддерживается и распределение происходит в момент поступления задания в брокер. Подход ленивого режима более аккуратный – задания грид находятся в очереди, а кластер запрашивает у брокера новое задание в моменты времени, определяемые политикой, заданной администратором. Однако, вопрос о том, какой должна быть эта политика, остается открытым. Простейший подход – запрашивать задание при пустой локальной очереди – не разрешает проблем неоднородного кластера и неотчуждаемых ресурсов.

Система управления заданиями ARC [27] проекта NorduGrid представляет интерес как пример децентрализованной архитектуры планирования. В целом, схема планирования в ARC аналогична жадному режиму брокера WMS, однако планировщик здесь входит в состав программного обеспечения каждого рабочего места пользователя, а планирование и передача задания в кластер, выполняется непосредственно с места выдачи запроса. Преимущества децентрализованной архитектуры известны – это отсутствие “критической точки”, живучесть и масштабируемость. Отметим также, что в данной архитектуре планирование производится отдельно для каждого задания и принимаемые решения могут оказаться не согласованными друг с другом.

В некоторых системах находят применение два новых механизма – резервирование и миграция. Сценарий Moab Grid Scheduler [40] выглядит следующим образом:

- задания грид поступают в глобальную очередь,

- планировщик посылает запросы в кластеры и получает от них время возможных аллокаций,

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

Moab, также как и CSF (Community Scheduler Framework) [46], который также поддерживает резервирование в службе планирования, не дает все-таки полного решения, предполагая, что кластерное обеспечение имеет средства для принятия решений о том, когда могут быть отведены ресурсы для резервирования. В стандартных СПО таких средств нет, и их создание составляет отдельную задачу.

Системы GridWay [47] и GridLab Resource Management System (GRMS) [48] используют механизм перераспределения заданий - миграцию. В GridWay после того как глобальное задание отправлено в кластер, специальная служба осуществляет его мониторинг. В случае, если задание не запущено на счет в локальном менеджере ресурсов за некий интервал времени, происходит перепланирование данного глобального задания, и оно перемещается на другие ресурсы.

Миграция представляет собой мощный механизм, который способен расширить возможности планирования. Однако, его применение сопряжено с большими временными затратами на перемещение файлов заданий, так что миграция, по-видимому, может рассматриваться как дополнение к качественному способу планирования.