Системы и службы управления доступом к ресурсам

Необходимость в особых механизмах управления ресурсами в локально и глобально распределенных средах хорошо осознана. К ресурсам относится все, что так или иначе участвует в обработке данных: вычислительные установки, файловые системы, коммуникации, программное обеспечение, хранилища данных. Локально распределенными средами, с определенной условностью, мы назовем «замкнутые» конфигурации: мультикомпьютеры, кластеры, симметричные мультипроцессоры, системы с распределенной памятью и массово-параллельные системы. Глобальная среда в настоящее время напрямую ассоциируется с грид-технологиями. Нынешняя интерпретация концепции грид подразумевает не только высокопроизводительные вычисления на суперкомпьютерах, но и использование в качестве процессорных ресурсов рабочих станций, а также обычных персональных компьютеров. Нужно сразу же заметить, что обеспечение доступа к ресурсам в глобальной среде грид и «замкнутых» конфигурациях имеет существенные различия. Это обусловлено, прежде всего, автономностью сайтов – основных структурных и административных единиц грид. Следствием является отсутствие единой политики обслуживания и планирования вычислительных работ.

Сначала рассмотрим особенности управления работами в локально распределенных средах. Эти функции выполняют системы управления ресурсами или СПО. В англоязычной литературе им соответствует такие термины, как JMS (job management system), RMS (resource management system или resource management and scheduling), CMS (cluster management software) и т.п. Использование для управления ресурсами штатных средств операционных систем, например, в локальной сети, требует отыскания свободных компьютеров, пересылки исполняемых файлов, файлов данных и т.д. Даже при небольшом числе пользователей административное управление этими процессами становится практически невозможным. Назначение систем управления ресурсами – распределение программных приложений по процессорным узлам или компьютерам. Цели, которые при этом могут преследоваться, это – увеличение реальной производительности, балансировка нагрузки процессоров и т.д. В программном обеспечении соответствующих систем, как правило, можно выделить два компонента – менеджер ресурсов и планировщик. Менеджер отвечает за распределение вычислительных ресурсов, их аутентификацию, создание и миграцию процессов. Планировщик определяет очередность выполнения работ и их назначение на те или иные ресурсы (рис. 1.1).

 

Рис. 1.1. Типичная структура системы управления ресурсами

 

В основе многих систем управления ресурсами лежит архитектура «клиент-сервер». Пользователь взаимодействует с системой через клиентскую программу – пользовательский интерфейс, который может быть, например, Web-браузером или системой X-Windows. На узлах (серверах), где выполняются работы, устанавливаются исполнительные демоны, которые поддерживают обновляемые таблицы данных о том окружении, в котором функционирует система управления ресурсами. Чаще всего реализуется не интерактивный доступ к ресурсам, а режим пакетной обработки заданий (job batch). В этом случае говорят об обработке пакетного задания. Чтобы запустить задание, пользователь через клиентскую часть должен представить информацию о местоположении входных и выходных данных, требуемой конфигурации аппаратной платформы, максимальном времени прогона программы и т.д.

Кратко рассмотрим основные функции систем управления ресурсами:

– поддержание очередей и планирование заданий;

– балансировку нагрузки;

– миграцию заданий;

– механизм контрольных точек.

В основе управления ресурсами лежит механизм очередей и планирования заданий, или диспетчеризации. Два наиболее часто реализуемых принципа организации очередей: «первым пришел – первым обслужен» (FCFS – first come first serve) и «наименее трудоемкая работа выполняется первой» (LWF – least work first). В принципе LWF трудоемкость может выражена через произведение необходимого числа процессорных узлов и оценки времени выполнения задания. Очереди конфигурируются с помощью специальных атрибутов. Например, в планировщике Moab Cluster Suite каждая из работ снабжается атрибутами geom и dur. Первый описывает требуемую конфигурацию ресурсов: запись geom=2,4 означает, что для выполнения задания требуется два узла, в одном из которых задействуется два, а в другом четыре процессора. Атрибут dur соответствует длительности выполнения задания. В соответствии со значениями атрибутов алгоритм планирования определяет очередность заданий и выделяет для них ресурсы. Так, из очереди первой может выбираться задание, для которого достаточно процессоров и свободного интервала времени, не занятого выполнением других заданий, причем начало очереди при этом не блокируется. Системы управления ресурсами, как правило, поддерживают совокупность очередей. Задания могут распределяться по очередям в зависимости от величины ресурсного запроса, на основе специальных требований к ресурсам, если необходим, в частности, доступ к высокопроизводительным графическим станциям и т.д. Ресурсный запрос оформляется в виде скрипта команды ввода задания qsub. В целом же диспетчеризация в режиме пакетной обработки позволяет эффективнее использовать вычислительные ресурсы: персональные компьютеры или рабочие станции какой-либо организации, обычно простаивающие по ночам или выходным дням, могут в это время загружаться трудоемкими, многочасовыми работами.

Балансировка нагрузки необходима для полного и эффективного использования ресурсов. Понятно, что вычислительный процесс организован плохо, если одна часть узлов перегружена, в то время как другая простаивает. Здесь опять-таки важен механизм планирования – работы выполняются вовсе не обязательно в порядке поступления (FCFS).Задание, оформляющее свои потребности в ресурсах в виде соответствующей опции команды qsub, будет запущено на узле, который подходит по конфигурации и предполагаемому времени вычислений. Сбалансировать нагрузку позволяет и функция миграции заданий. Она определяет возможность прерывания, перемещения в другие узлы и повторного запуска задания. Миграция может быть вызвана перегрузкой одних узлов и простоем других. Эта функция в системах управления ресурсами чаще всего поддерживается с помощью очередей. Так, утилита администратора qmqr позволяет создавать очереди и устанавливать их атрибуты. Например, доступ к очереди может быть разрешен заданиям, принадлежащим определенным группам или введенным с конкретных рабочих мест, могут быть определены ограничения на размер очереди и число запускаемых из нее заданий. Система очередей часто является сложно организованной. Одни очереди, исполнительные, непосредственно связаны с процессорными узлами, другие, маршрутизирующие, в качестве пунктов назначения имеют опять-таки очереди. Соответствующее конфигурирование очередей позволяет реализовать гибкую политику миграции работ.

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

Глобальная вычислительная среда грид формируется из автономных распределенных узлов, конфигурация ресурсов динамически изменяется, узлы свободно отключаются и подключаются. Все это требует принципиально новых моделей вычислений и управления ресурсами. Главная задача, решаемая грид-технологиями, это – обеспечение доступа к глобально распределенным ресурсам с помощью специального инструментария, а именно, набора служб. Модель «клиент-сервер» уже перестает быть адекватной такого рода средам, поскольку свой набор служб устанавливается на каждом из ресурсов. При этом должен быть обеспечен стандартный протокол доступа к ним, а службы различных ресурсов должны быть согласованными. Осуществить это позволяет архитектура OGSA (Open Grid Services Architecture). Она вводит унифицированную семантику предоставления служб, общие правила создания, именования и поиска экземпляров грид-служб, связывание различных протоколов доступа к ресурсам. Фактически стандартом разработки грид-систем стал свободно распространяемый инструментарий Globus Toolkit на базе архитектуры OGSA (http://www.globus.org/ogsa).

Сложность управления глобально распределенными ресурсами заключается в том, что запуск, выполнение задания и доступ к необходимым данным могут производиться в совершенно различных местах. Системы управления ресурсами в «замкнутых» конфигурациях опираются на единую политику администрирования, грид – динамически самоорганизующаяся система, в которой, естественно, не может быть единого администратора, а сайты автономны. Владельцы ресурсов лишь на время отдают их в общее пользование. Кроме этого, локальные системы управления ресурсами не стандартизованы. Как быть в такой ситуации? Инструментарий Globus включает ряд служб, которые позволяют справиться с этой проблемой. Это, в частности, служба распределения и управления ресурсами (GRAM – Grid Resource Allocation and Management), информационная служба сбора метаданных (GIS – Grid Information Service) и служба инфраструктуры безопасности (GSI – Grid Security Infrastructure). Служба GIS позволяет получить данные о состоянии распределенных ресурсов и базируется на использовании протокола LDAP (Lightweight Directory Access Protocol). Служба GSI представляет собой, по сути, общий интерфейс для локальных систем безопасности автономных сайтов. Она поддерживает однократную проверку пользователя в течение одного сеанса, делегирование ему полномочий и отображение прав доступа на локальные системы.

Примерная схема доступа к ресурсам в глобальной среде такова. Пользователь в команде запуска задания специфицирует требования к ресурсам с помощью специального языка RSL (Resource Specification Language). За поиск ресурсов, адекватных требованиям, отвечает служба брокеров, которые преобразовывают требования на языке RSL в более детальную спецификацию. Для поиска ресурсов необходима метаинформация, поставляемая службой MDS (Metacomputing Directory Service). В MDS данные представляют различные типы распределенных ресурсов, формализуемые в протоколе LDAP понятиями объекта и атрибутов. Возвращаемая информация содержит адреса сайтов, которые обладают необходимыми ресурсами. Нижний уровень управления в архитектуре глобальной среды представляет GRAM. Он обрабатывает спецификации RSL, отвергает или запускает запросы от пользовательских утилит Globus, наконец, вводит задание на локальном узле в пакетном режиме с помощью команды qsub. По полученным с помощью брокеров адресам пользовательскими утилитами, в частности, globus-job-submit, можно осуществить удаленный запуск задания. Из опций утилиты job-submit формируется паспорт задания, который пересылается в GRAM. Такой его компонент, как Gatekeeper, осуществляет аутентификацию и авторизацию пользователя. Менеджер локальной системы управления ресурсами ставит задание в одну из очередей. Разумеется, ключевым звеном в этой схеме является распределение ресурсов в глобальной среде. Здесь необходимо поддерживать такие службы планирования, которые бы собирали запросы пользователей, организовывали очереди и определяли порядок выполнения заданий. Это функции своего рода метадиспетчера. Метадиспетчер является промежуточным звеном в цепи «удаленный запуск задания – выделение ресурса» и представляет собой надстройку над стандартными компонентами Globus. Таким образом, метадиспетчер – это интерфейс с менеджерами ресурсов для совокупности отдельных сайтов. Понятно, что для создания таких средств необходимы новые принципы планирования вычислительных заданий и распределения ресурсов. Об этом подробнее мы поговорим чуть позже.

 

Планирование вычислений в грид

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

Рассмотрим принципы глобального планирования на основе следующей модели (рис. 1.2). В этой модели внешний планировщик выполняет роль промежуточного звена между пользователями и множеством систем управления ресурсами на распределенных сайтах.

 

Рис. 1.2. Взаимодействие компонентов глобальной среды

 

Внешний планировщик в соответствии с некоторым алгоритмом определяет сайт, куда направляется поток заданий пользователя. Выбор сайта зависит от многих факторов: степени загруженности работами, наличия требуемых для вычислений данных и т.д. Эта информация может предоставляться локальными СПО. Для этого в них предусмотрена команда получения данных о текущем состоянии qstat. Однако информация, выдаваемая командой qstat, все-таки ориентирована на локальное управление ресурсами и, как правило, ее недостаточно для внешнего планирования. В преодолении этих трудностей может помочь механизм предварительного резервирования ресурсов, поддерживаемый рядом СПО. Сбор информации о состоянии локальных сайтов может опираться на информационную службу MDS системы Globus Toolkit. После того, как для задания выбран сайт, локальный планировщик (см. рис. 1.2) ставит это задание в очередь. Планировщик данных отвечает за доступ к данным на удаленных сайтах, перемещение и репликацию (тиражирование) данных. Репликация и перемещение данных в сочетании с внешним планированием является весьма действенным механизмом для управления заданиями в грид. В рассматриваемой модели (см. рис. 1.2) возможны различные сценарии взаимодействия пользователей, внешних планировщиков, локальных систем управления ресурсами и планировщиков данных. При этом эффективность планирования может оцениваться по совокупности критериев: использованию ресурсов, времени ответа на запросы пользователя и др.

Вкратце на примере проекта AppLeS рассмотрим идею планирования на уровне приложений. Основная идея подхода состоит в том, что агенты-планировщики подбирают набор ресурсов для эффективного выполнения конкретного программного приложения. При этом у пользователя поддерживается иллюзия использования глобально распределенных вычислительных ресурсов исключительно в интересах его программы. Различные пользователи, естественно, пытаются оптимизировать свои приложения, разделяющие общие ресурсы, по совершенно различным критериям. Основная концепция проекта AppLeS – реализация заказного планировщика с учетом особенностей программного приложения. Эти особенности включают парадигму программирования, структуру данных, требования к памяти, модели обмена данными и т.д. Примерная структура агента-планировщика показана на рис. 1.3.

Данные о распределенных ресурсах среды, особенностях приложения, пользовательских критериях производительности, моделях для оценки производительности и распределения ресурсов образуют так называемый информационный пул. Сбор информации о среде и прогнозирование загруженности ресурсов обеспечивается службой Network Weather Service. Четыре основные подсистемы агента, управляемые агентом-координатором, выполняют функции отбора той или иной комбинации ресурсов; планирования в соответствии с заданным пользователем критерием; взаимодействия с локальной системой управления ресурсами. Агент-координатор на основе оценки производительности отбирает лучший, с точки зрения пользователя, план и передает его через подсистему-исполнитель локальному планировщику в систему управления ресурсами.

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

 

 

Рис. 1.3. Структура агента-планировщика

 

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

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

 

2. Согласованное выделение ресурсов

2.1. Масштабируемая модель планирования

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

 

                       

а                                       б                                   в

Рис. 2.1. Структуры заданий в моделях (а), (б), (в)

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

 

Таблица 2.1

Длительность,	Задачи обработки
объем вычислений
	2	3	1	2	1	2
	4	6	2	4	2	4
	6	9	3	6	3	6
	8	12	4	8	4	8
	20	30	10	20	10	20

 

Параметризованный граф  будем именовать моделью задания.

Распределение  ресурсов между задачами из  для соответствующей модели задания на отрезке времени  зададим следующим образом:

,

(2.1.1)

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

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

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

. (2.1.2)

Подчеркнем, что соотношения (2.1.1), (2.1.2) принципиально отличают масштабируемую модель планирования вычислений от традиционных моделей составления расписаний.

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

, , ,                      (2.1.3)

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

План, соответствующий варианту допустимого, согласно (2.1.2), (2.1.3), распределения (2.1.1), в критерии  эффективности использования вычислительных ресурсов представим вектором . Пусть  – функции для оценки эффективности выполнения -й, -й задач на ресурсах, типы которых определяются назначениями , . Критерий  представим следующим образом:

= . (2.1.4)

Эффективность распределения ресурсов (2.1.1) будем оценивать по вектору , где каждый из критериев , , можно записать в виде (2.1.4).

Пример критерия – функция стоимости завершения обработки:

, ,                               (2.1.5)

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

Другой пример – коэффициент загрузки  процессоров -го типа:

,     (2.1.6)

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

Пусть  – множество планов, каждый из которых  соответствует допустимому распределению ресурсов (2.1.1) и своей модели  задания. Для сравнения между собой различных планов на  будем использовать понятие оптимальности по бинарному отношению , формируемому векторным критерием . Например,  может быть отношением Парето, которое формируется критериями  и , согласно (2.1.5) и (2.1.6). Пару  будем называть моделью выбора, а множество , оптимальных по отношению  планов в модели выбора , назовем -оптимальной стратегией распределения ресурсов.

Постановка задачи распределения ресурсов, согласованного со структурой выполняемого задания, представленного множеством  моделей, заключается в отыскании -оптимальной стратегии  допустимого в соответствии с (2.1.2), (2.1.3) распределения ресурсов (2.1.1), где  формируется вектором  критериев вида (2.1.4). Получаемая стратегия  должна обеспечивать приемлемую аппроксимацию: совпадение ; включение ; совпадение с точностью до эквивалентности , где  – квазипорядок, а  – отношение эквивалентности на .

2.2. Формирование планов по частному критерию

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

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

Пусть  – функция для оценки эффективности выполнения -й работы по критерию , ;  – число работ в задании;  –план;  – число задач; ;  – соответственно длительность выполнения и назначение -й задачи, . С учетом свойства аддитивной сепарабельности (2.1.4) критерий  можно представить в виде:

, (2.2.1)

где .

В соответствии с методом критических работ условный экстремум функции  в (2.2.1) при заданном значении запаса  по времени выполнения к моменту запуска -й задачи может быть получен из следующего функционального уравнения:

,              (2.2.2)

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

Условно оптимальные длительность выполнения и назначение на ресурс при запасе  по времени определяются из следующих функциональных уравнений:

,                               (2.2.3)

.           (2.2.4)

В (2.2.3)  – диапазон изменения длительности , зависящий от запаса  по времени к моменту начала выполнения соответствующей задачи, а  в (2.2.4) получается из (2.2.3)

Условно оптимальным является план следующего вида:

.             (2.2.5)

Схема последовательного формирования планов для частной модели задания может быть определена как набор шагов

, ,           (2.2.6)

где  – подмножество задач, образующих -ю работу;  – множество условно оптимальных планов (2.2.5), получаемых на шаге .

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

Пусть частный критерий  формирует бинарное отношение:

,       (2.2.7)

где  – подмножество планов, являющееся одновременно внутренне и внешне устойчивым в модели выбора .

Будем называть  в (2.2.7) стратегией, условно оптимальной по критерию .