научная статья по теме ЭКОНОМИЧЕСКАЯ МОДЕЛЬ ПЛАНИРОВАНИЯ И СПРАВЕДЛИВОГО РАЗДЕЛЕНИЯ РЕСУРСОВ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЯХ Математика

Текст научной статьи на тему «ЭКОНОМИЧЕСКАЯ МОДЕЛЬ ПЛАНИРОВАНИЯ И СПРАВЕДЛИВОГО РАЗДЕЛЕНИЯ РЕСУРСОВ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЯХ»

ПРОГРАММИРОВАНИЕ, 2014, No 1, с. 54 65

= РАСПРЕДЕЛЕННЫЕ ВСТРОЕННЫЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ

УДК 681.3.06

ЭКОНОМИЧЕСКАЯ МОДЕЛЬ ПЛАНИРОВАНИЯ И СПРАВЕДЛИВОГО РАЗДЕЛЕНИЯ РЕСУРСОВ В РАСПРЕДЕЛЕННЫХ ВЫЧИСЛЕНИЯХ *

© 2014 г. В.В. Топорков, Д.М. Емельянов

Национальный исследовательский университет "МЭИ" 111250 Москва, ул. Красноказарменная, 14 E-mail: ToporkovVV@mpei.ru , yemelyanov.dmitry@gmail.com Поступила в редакцию 12.05.2013

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

1. ВВЕДЕНИЕ

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

Среди различных подходов к организации вычислений в распределенных средах можно выявить две устойчивых тенденции [3]. Одна из них основывается на использовании брокеров ре-

* Работа выполнена при частичном содействии Совета по грантам Президента Российской Федерации для поддержки ведущих научных школ (шифр НШ-362.2014.9), Российского фонда фундаментальных исследований (проект № 12-07-00042), Министерства образования и науки Российской Федерации в рамках федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009-2013 годы (государственные контракты № 16.740.11.0038 и 16.740.11.0516).

сурсов для поиска подходящих наборов ресурсов и оптимизации каждого задания в отдельности. Другая тенденция связана с образованием виртуальных организаций (ВО) и ориентирована, прежде всего, на грид-системы. При образовании ВО осуществляется оптимизация планирования на уровне потоков заданий [4]. Соответствующие функции реализуются иерархической структурой, состоящей из метапланировщи-ка и подчиненных ему менеджеров заданий [5, 6]. Преимущества таких структур хорошо известны [3, 7-9]. Важным аспектом здесь является объединение под управлением одного менеджера тех вычислительных узлов, которые являются схожими по архитектуре, составу, политике администрирования [8, 10]. В таких структурах задания группируются в потоки и направляются в различные домены узлов [5, 6]. Существенно также сокращение времени обмена данными между менеджерами различных уровней иерархии и ме-тапланировщиком. Нужно подчеркнуть, что оба подхода предполагают планирование приложений на основе динамично меняющейся информации о глобальной среде и позволяют реализовать различные сценарии управления ресурсами.

В одних из известных моделях распределенной обработки данных на неотчуждаемых ресурсах, в зависимости от состояния среды, отыскивается

ЦИКЛ ¡-1 ЦИКЛ \ Микл 1+1

Рис. 1. Цикличное планирование; потока заданий.

.лишь подходящий набор ресурсов [8, 11, 12] и не поддерживаются оптимизационные механизмы планирования заданий. В других моделях [3, 13, 14] не представлены аспекты, весьма характерные для распределенных сред с неотчуждаемыми ресурсами и связанные с динамикой изменения загрузки узлов, конкуренцией независимых пользователей, а также глобальных (пользовательских) и локальных (внутренних) потоков заданий собственников ресурсов [1 3].

В настоящей статье предлагается модель планирования и разделения ресурсов на основе иерархической (древовидной) структуры управления заданиями в ВО. Концепция мета-планирования, предлагаемая в данной работе, принципиально отличается от известных решений тем, что строится на комплексном сочетании методов планирования параллельных приложений и управления потоками независимых заданий [5, 6, 15, 16]. Полученные результаты позволяют повысить качество обслуживания заданий и эффективность использования ресурсов распределенных вычислительных сред с использованием мши'офакторных и мшихжрите-риальных стратегий справедливохх) выделения ресурсов, с учетом особенностей административной политики предоставления и потребления ресурсов, а также свойств заданий и пожеланий пользователей.

2. ЦИКЛИЧНАЯ СХЕМА ПЛАНИРОВАНИЯ

Модель предполах'ает хруппирование заданий в пакеты в соответствии с их свойствами и потребностями в ресурсах, а также цикличное планирование системы заданий на основе динамично обновляемых критериев и ограничений [10] (рис. 1).

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

Для поиска множества альтернативных наборов слотов на первом этапе рассматриваемой схемы планирования, необходимо построить алх'о-ритм поиска "окна" на множестве слотов, удо-влетворяющихо ресурсным требованиям отдельных заданий. "Окно" представляет собой набор из п слотов с одинаковым временем старта. Время, на которое выделяются ресурсы, определяется пользовательской оценкой времени выполнения задания. Каждая альтернатива (набор сло-

Рис. 2. "Окно" на множестве слотов.

тов) характеризуется временем и стоимостью использования соответствующего вычислительного ресурса. Линейные по сложности алгоритмы отбора слотов ранее предложены и исследованы в [15). В частности, это алгоритм AMP (Algorithm based on Maximal job Price) - поиск "окна" с ограничением на общую стоимость выполнения задания. В данной статье исследуется целая группа вновь разработанных алгоритмов выбора слотов. Часть из них использует и развивает базовые принципы, лежащие в основе решений, описанных в [15], в том числе AMP.

Известны различные подходы к отбору подходящих слотов в задачах планирования и диспетчеризации заданий. Так, при планировании на основе бэкфиллинга [17] для заданий, находящихся в очереди, осуществляется поиск первых подходящих вариантов слотов. В планировщике Maui (Moab Suite) [17], который реализует бэкфиллинг, поиск "окон" для выполнения заданий осуществляется без учета аддитивных требований и ограничений, например, на суммарную стоимость найденного "окна". Система NWIRE [18] разрабатывалась с целыо гибкого учета требований пользователей и наиболее близка к предлагаемому подходу. Система генерирует альтернативы выполнения задания, из которых выбирается наиболее подходящая по заданному критерию и другим показателям, в том числе экономическим возможностям пользователя. Однако следует отметить, что на этапе поиска альтернатив в домене ресурсов, не учитывается ограничение на общую стоимость "окна". Выборка множества предложений из найденного "окна" осуществляется с использованием эвристики перебора подходящих слотов. Поиск прекращается при отборе заданного числа альтер-

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

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

3. ОБЩАЯ СХЕМА ПОИСКА АЛЬТЕРНАТИВНЫХ НАБОРОВ СЛОТОВ

Положим, согласно ресурсному запросу, требуется найти "окно" из слотов, длительность каждого из которых определяется производительностью соответствующего ресурса. Таким образом, в условиях неоднородности вычислительных ресурсов с различной производительностью это будет «окно» с неровным правым краем (рис. 2).

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

Поиск "окна" осуществляется на списке всех доступных слотов, упорядоченных по неубыванию времени старта. Это условие необходимо для поочередного просмотра всего списка слотов и построения алгоритмов линейной сложности [15]. Схема поиска "окна", удовлетворяющего поставленным требованиям и оптимального по заданному критерию, может быть представлена следующим образом:

/*Job - Задание, для которого происходит поиск;

**windowSlots - список слотов "окна"; */

slotList = orderSystemSlotsByStartTimeO; for(i=0; i< slotList.size; i++){ nextSlot = slotList[i]; if(!properHardwareAndSoftware(nextSlot)) break;// Данный слот не подходит

windowSlotList.add(nextSlot); windowStart = nextSlot.startTime;

{

wSlot = windowSlots[j] ; minLength = wSlot.Resource.getTime(Job); if((wSlot.EndTime - windowStart) < < minLength) windowSlots.remove(wSlot);

}

{

curWindow = getBestWindow(windowSlots);

crW = getCriteria(curWindow);

{

maxCriteria = crW; bestWindow = curWindow;

}

}

}

В конце работы алгоритма в переменной bestWindow будет находиться оптимальное по заданному критерию "окно". Сам критерий определяется видом функции

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком