ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2011, № 3, с. 62-78
= КОМПЬЮТЕРНЫЕ МЕТОДЫ =
УДК 681.3.06+519.6
УПРАВЛЕНИЕ ЗАДАНИЯМИ В РАСПРЕДЕЛЕННЫХ СРЕДАХ С НЕОТЧУЖДАЕМЫМИ РЕСУРСАМИ* © 2011 г. В. В. Топорков
Москва, МЭИ (технический ун-т) Поступила в редакцию 25.10.10 г., после доработки 21.01.11 г.
Предлагается и обосновывается модель обработки заданий в распределенных средах с неотчуждаемыми ресурсами, имеющих своих владельцев. Модель предполагает реализацию так называемого справедливого разделения ресурсов между независимыми пользователями и собственниками вычислительных узлов. Рассматриваются задачи поиска оптимальной и эффективной комбинаций доступных ресурсов на основе динамично обновляемых расписаний — списков слотов, каждому из которых сопоставлены временной отрезок для выполнения составной части задания и тот или иной тип ресурса.
Введение. Вопросы управления заданиями являются одними из наиболее сложных в организации распределенной обработки данных в условиях неотчуждаемости ресурсов, используемых совместно с их владельцами. Необходимо учитывать неоднородность, динамичность состава, различную административную принадлежность обрабатывающих узлов и масштабность распределенной среды. Весьма эффективными здесь оказываются так называемые экономические модели планирования в грид [1], мультиагентных системах [2] и облачных вычислениях [3]. При этом возникает серьезная проблема ценообразования в зависимости от уровня качества обслуживания [3]. В [4] дается хороший обзор различных подходов к ее решению, а также к формированию различных стратегий планирования при наличии ограничений на время и бюджет выполнения задания. В [5] рассматриваются эвристические алгоритмы подбора ресурсов на основе задаваемых пользователем функций полезности.
Среди различных подходов к организации вычислений в распределенных средах можно выявить две устойчивые тенденции [6—9]. Одна из них основывается на использовании доступных ресурсов, когда роль посредников между пользователями и вычислительными узлами выполняют агенты приложений — брокеры. При реализации той или иной экономической политики брокерами ресурсов [4, 5], как правило, проводится оптимизация выполнения конкретного приложения [8, 9]. Другая тенденция связана с образованием виртуальных организаций и ориентирована, прежде всего, на грид-системы [6, 8, 9]. При образовании виртуальных организаций [6] осуществляется оптимизация планирования на уровне потоков заданий. Соответствующие функции реализуются иерархической структурой, состоящей из метапланировщика и подчиненных ему менеджеров заданий [6—9], которые подконтрольны метапланировщику и в свою очередь взаимодействуют с локальными менеджерами управления ресурсами, например системами пакетной обработки заданий [7, 10]. Нужно подчеркнуть, что оба подхода предполагают планирование приложений на основе динамично меняющейся информации о глобальной среде и позволяют реализовать различные сценарии управления ресурсами. Все это заставляет говорить не просто об алгоритме, а о стратегии планирования, т.е. комбинации различных методов внешнего и локального планирования, размещения данных и т.д. [11, 12]. И тот и другой подходы имеют свои достоинства и недостатки. В рамках первого из направлений системы управления ресурсами являются хорошо масштабируемыми и адаптируемыми к особенностям приложений. Однако использование независимыми пользователями различных критериев для оптимизации планов выполнения своих заданий (в условиях возможной конкуренции с другими заданиями) может ухудшать такие интегральные характеристики, как время выполнения пакета заданий и загрузка ресурсов. Образование виртуальных организаций естественным образом ограничивает масшта-
* Работа выполнена при частичном содействии Совета по грантам Президента РФ для поддержки ведущих научных школ (грант НШ-7239.2010.9), РФФИ (проект № 09-01-00095), Минобрнауки в рамках аналитической ведомственной целевой программы "Развитие научного потенциала высшей школы" (проекты № 2.1.2/6718; 2.1.2/13283) и федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009— 2013 годы (государственные контракты № П2227; 16.740.11.0038).
Слоты 1 2
3
4
5
6
'Окно" 3 х t с неровным правым краем
Старт
Окончание
Время
Слоты
1 2
3
4
5
6
Старт
Прямоугольное "окно" 3 х ?
Окончание
Время
Рис. 1. Отбор подходящих слотов для запуска задания
а
бируемость систем управления заданиями. Тем не менее наличие определенных правил предоставления и потребления ресурсов позволяет повысить эффективность планирования и распределения ресурсов на уровне потоков заданий.
В одних из известных моделей распределенной обработки данных на неотчуждаемых ресурсах, в зависимости от состояния среды, отыскивается лишь подходящий набор ресурсов [7] и не поддерживаются оптимизационные механизмы планирования заданий. В других [6] моделях не представлены аспекты, весьма характерные для распределенных сред с неотчуждаемыми ресурсами и связанные с динамикой изменения загрузки узлов, конкуренцией независимых пользователей, а также глобальных (пользовательских) и локальных (внутренних) потоков заданий собственников ресурсов [1—5, 8, 9].
В настоящей работе предлагается и обосновывается модель для управления выполнением независимых заданий в рамках виртуальной организации на основе экономических принципов, причем планирование заданий выполняется циклично на альтернативных наборах предварительно отобранных ресурсов. В отличие от известных рассматриваемая модель предполагает группирование заданий в пакеты в соответствии с их свойствами и потребностями в ресурсах, а также цикличное планирование системы заданий на основе динамично обновляемых стратегий и ограничений. План выполнения системы заданий оптимизируется по совокупности критериев в соответствии с политикой предоставления и потребления ресурсов, принятой в виртуальной организации. Доступные ресурсы представляются совокупностью слотов, каждому из которых соответствуют временной отрезок для выполнения составной части задания и тот или иной тип ресурса. Наборы доступных слотов динамично обновляются на основе информации, поступающей от локальных менеджеров ресурсов.
1. Основные компоненты модели отбора слотов и постановка задачи. Выполнение многопроцессорного задания требует согласованного (одновременного) выделения ресурсов таким образом, чтобы составные части задания могли стартовать одновременно на соответствующих типах ресурсов (вычислительных узлах). Требование задания к ресурсам оформляется в виде ресурсного запроса, содержащего тип, количество, характеристики вычислительных узлов, а также время t их использования [10]. Для запуска задания необходимо согласованное выделение требуемого числа г слотов на время t. Проблема заключается в том, что слотам, ассоциированным с разными обрабатывающими узлами распределенной среды, соответствуют произвольные и не совпадающие моменты времени начала и окончания. В случае однородных ресурсов из совокупности слотов, предварительно упорядоченных по неубыванию времени старта, выделяется прямоугольное "окно" размером г х t для выполнения задания (рис. 1, а). Для узлов с разной производительно-
Таблица 1
Задание
Набор слотов 1 2 3
с1 Н с2 t2 с3 tз
1 7 7 3 3 5 5
2 10 5 2 1 8 4
3 9 3 - - 6 2
4 - - - - 4 1
стью это — "окно" с неровным правым краем, где t — время выполнения составной части задания на наименее производительном процессоре (рис. 1, б). План выполнения задания представляет собой набор слотов.
В рамках рассматриваемой модели фигурируют пользователи и собственники вычислительных ресурсов, интересы которых зачастую противоречивы. Условие неотчуждаемости ресурсов подразумевает, что наряду с глобальными потоками заданий внешних пользователей выполняются локальные задания собственников рассматриваемого домена узлов. При этом имеет место конкуренция как независимых пользователей, так и глобальных и локальных потоков заданий за использование ресурсов. Эти факторы существенно усложняют решение задачи отбора слотов. Пользователь, запускающий 1-е задание, должен иметь возможность управлять временем его старта, оперируя платой с, которую он вносит за выполнение задания в течение времени ti [1—7]. Цена с устанавливается собственником на основе соображений балансирования глобальных и локальных потоков заданий, получения соответствующего дохода и т.п.
Предлагаемая модель строится на иерархической (древовидной) структуре управления заданиями в виртуальной организации. Преимущества таких структур хорошо известны [6—9, 13]. Иерархия промежуточных серверов [13] позволяет снизить простой узлов из-за заметных задержек в передаче данных и занятости управляющего сервера обслуживанием других узлов. Древовидная структура менеджеров в сетевой среде распределенной обработки позволяет избежать тупиков при доступе к разделяемым ресурсам [10]. Важный аспект — объединение под управлением одного менеджера тех вычислительных узлов, которые являются схожими по архитектуре, составу, политике администрирования [7, 14]. В таких структурах задания группируются в пакеты и направляются в различные домены узлов [8, 9]. Однако при этом допускается миграция: задания, для которых, например, не удается найти подходящих слотов в текущем цикле планирования, могут направляться в другие домены узлов. Политика предоставления и потребления ресурсов, принятая в виртуальной организации и формализуемая совокупностью заданных критериев, строится на основе динамично обновляемых расписаний узлов — совокупности слотов, информация о которых поступает из локальных систем обработки заданий вышестоящим менеджерам [10].
Планирование выполнения системы независимых заданий, сгруппированных в N пакетов по схожести ресурсных требований [14], осуществляется циклично. В каждом цикле планирования локальные расписания обновляются, и при этом требуется решение двух задач. Во-первых, нужно отобрать подходящие (по ресурсу, цене с, времени t¡) слоты для каждого задания пакета. Во-вторых, необходимо найти ко
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.