Планирование задач и ресурсов в распределённых системах | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 18 июля, печатный экземпляр отправим 22 июля.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №18 (308) май 2020 г.

Дата публикации: 04.05.2020

Статья просмотрена: 18 раз

Библиографическое описание:

Филимонов, Д. Н. Планирование задач и ресурсов в распределённых системах / Д. Н. Филимонов, О. А. Савина. — Текст : непосредственный // Молодой ученый. — 2020. — № 18 (308). — С. 25-28. — URL: https://moluch.ru/archive/308/69574/ (дата обращения: 07.07.2020).



В статье рассматриваются аспекты планирования задач в системах распределенных вычислений.

Ключевые слова: распределенные вычисления, стратегия планирования, GRID.

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

Традиционные требования, которые предъявляются со стороны приложений:

  1. Сетевые требования (пропускная способность и задержка);
  2. Конфигурационные требования (процессор и память);
  3. Права доступа к определённым программным ресурсам.

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

Таким образом, на вход метода выделения ресурсов подаются следующие данные:

  1. Физические и виртуальные ресурсы;
  2. Требования приложений;
  3. Модели ресурсов.

При моделировании ресурсов производится разбивка доступных аппаратных ресурсов (памяти, процессора, пропускной способности сети и т. п.) на части, которые могут быть ассоциированы с конкретной задачей. К примеру, доступную задачам память можно делить на блоки по 16, 32, 64 и т. д. мегабайт, а пропускную способность сети — по 10 мегабит/с, а процессора можно предоставлять как эксклюзивно, так и предоставляя ядра одного процессора для планирования работы нескольких прикладных приложений. Здесь важно соблюсти баланс между наиболее точным выделением ресурсов и накладными расходами на планирование их использования: распределение ресурсов при очень мелком их дроблении само по себе становится сложной задачей, что усложняет работу на стадии планирования ресурсов и оптимизации [3].

Привлекаемые распределенные ресурсы почти всегда гетерогенны: различные архитектуры, программное и аппаратное обеспечение. В связи с этим, разработка адекватной ресурсной модели является первой задачей, которую необходимо решить при разработке системы выделения ресурсов [3].

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

Оптимальным представляется подход, когда на этапе создания системы строятся модели ресурсов исходя из типов предоставляемых сервисов.

К примеру в решении Elastic Computing Cloud от Amazon выделяются классы арендуемых машин (instance families): общего назначения, оптимизированные по производительности процессора, с большим объёмом основной памяти (RAM), c большим объёмом внешней памяти и оптимизированные под графическую обработку. Кроме того, в каждом классе машин идёт разделение по мощности (instance types): малые, средние, большие, сверхбольшие и т. п.

Среди стратегий выбора ресурсов можно выделить апостериорные и априорные [3].

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

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

Большинство существующих алгоритмов планирования задач исходит из предположения, что время выполнения приложения (задачи) известно заранее, ещё до реального выполнения [2]. Это упрощает сопоставление задач и ресурсов, но слабо применимо к реальным задачам. Более обоснованный подход — мониторинг прикладных приложений с целью выяснения характеристик выполнения. Это позволяет на основе предположения о корреляции между состоянием выполнения задачи и общим временем её выполнения прогнозировать время, оставшееся до завершения задачи.

Многие из алгоритмов, оценивающие время выполнения и прогнозирующие загрузку ресурсов, основаны на статистических моделях [4]. Статистика предыдущих запусков успешно применяется в кластерных и облачных платформах. Решения о масштабировании на практике базируется на множестве критериев, среди которых накладные расходы на выделение ресурсов, на миграцию заданий, оценку ожидаемого эффекта от масштабирования и перепланирования.

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

Динамические стратегии применяются в тех случаях, когда система назначает ресурсы по мере поступления задач. Здесь можно минимизировать время обработки пакета или иную метрику, отражающую качество предоставляемого сервиса. Динамический подход к планированию предполагает возможность планировщика менять стратегию планирования при появлении новых задач и освобождении ресурсов. В этом случае планирование становится уже не единовременным отвлечением ресурсов на внутренние нужды, а систематической работой, влияние которой на общее время выполнения задачи нужно также минимизировать [5].

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

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

  1. Планирование независимых задач;
  2. Планирование задач с зависимостями (описание на основе DAG).

Например, в статье [2] производится оценка производительности и оптимизация для существующего алгоритма адаптивного планирования в грид-системах. Алгоритм обрабатывает задачи, имеющие перекрестные зависимости, которые можно описать направленным ацикличным графом, для которых отсутствует информация об общем времени выполнения. Авторы в статье [5] также исследуют вопрос планирования задач с зависимостями.

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

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

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

Авторы в статье [8] отмечают, что установление соответствия между приложениями и вычислительными ресурсами в грид-системах является трудоёмкой задачей ввиду гетерогенности ресурсов и динамичности изменения их состояния. Для преодоления этих проблем предлагается использовать искусственную нейронную сеть для прогнозирования состояния узлов обработки. В работе сравниваются два алгоритма прогнозирования на основе нейронных сетей. Авторы используют статический подход к планированию: делается допущение о том, что время выполнения задач может быть оценено на стадии планирования.

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

Литература:

  1. Caniou, Y. Experimental study of multi-criteria Scheduling Heuristics for GridRPC Systems / Y. Caniou, E. Jeannot // Euro-Par. — 2004. — P. 1048–1055.
  2. Chtepen, M. Performance evaluation and optimization of an adaptive scheduling approach for dependent grid jobs with unknown execution time / M. Chtepen, F. Claeys, B. Dhoedt // 18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation, Proceedings. — 2009. — P. 1003–1009.
  3. Endo, P. Resource allocation for distributed cloud: concepts and research challenges / P. Endo, A. D. A. Palhares, N. Pereira // Ieee Network. — 2011. — Vol. 25 — № 4. — P. 42–46.
  4. Imam, M. T., Neural network and regression based processor load prediction for efficient scaling of Grid and Cloud resources / M. T. Imam, S. F. Miskhat, R. M. Rahman, M. A. Amin // 14th International Conference on Computer and Information Technology (ICCIT). — IEEE — 2011.
  5. Kwok, Y.-K. Static scheduling algorithms for allocating directed task graphs to multiprocessors / Y.-K. Kwok, I. Ahmad // ACM Computing Survey. — 1999. — Vol. 31. — № 4. — P. 406–471.
  6. Kim, J.-K. Dynamically mapping tasks with priorities and multiple deadlines in a heterogeneous environment / J.-K. Kim, S. Shivle, H. J. Siegel // Journal of Parallel and Distributed Computing. — 2007. — Vol. 67. — № 2. — P. 154–169.
  7. Sun, W. Dynamic task flow scheduling for heterogeneous distributed computing: Algorithm and Strategy / W. Sun, Y. Zhang, Y. Inoguchi // IEICE Transactions on Information and Systems. — 2007. — Vol. E90-D, № 4. — P. 736–744.
  8. Xue. S. Resource state prediction in the grid based on neural network / S. Xue, L. Chen, G. Liu // Proceedings of the 5th international conference on Natural computation. ICNC’09. Piscataway, NJ, USA: IEEE Press, 2009. — P. 294–298.
Основные термины (генерируются автоматически): алгоритм планирования, ресурс, задача, модель ресурсов, стратегия планирования, динамическое планирование, промежуточное программное обеспечение, пропускная способность, пропускная способность сети, DAG.


Ключевые слова

распределённые вычисления, Grid, стратегия планирования

Похожие статьи

Алгоритмы планирования масштабируемых заданий кластерной...

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

Генетический алгоритм планирования конкурирующих за канал...

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

Задача размещения задач на вычислительных ресурсах сводится к выбору таких параметров

"Планирование задач для вычислительного кластера с учетом сети и многопроцессорности...

Формирование оптимальной производственной программы на...

Исследуется проблема планирования производственной программы в условиях риска и неопределенности. Рассматривается многопродуктовая стохастическая модель оптимизации плана производства. Для формирования оптимального плана разработан алгоритм...

Выявление и классификация временных точек срыва плана...

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

Применение генетического алгоритма для решения задачи...

Таким образом, задача распределения ресурсов схожа с классической задачей распределения ресурсов в транспортной сети (между поставщиками и потребителями, мощностей между каналами передачи данных и т. п.) и состоит в определении величин xnk — поставка n-субъекта...

Оценка перспективной пропускной способности участков...

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

Алгоритмы балансировки в сети OSPF | Статья в журнале...

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

Методы оптимального планирования в системах военного...

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

Применение методов и моделей сетевого планирования...

Таким образом, применение системы сетевого планирования и управления на ООО «УОП «Нефтехим» способствует более эффективному распределению и рациональному использованию имеющихся на предприятии ограниченных ресурсов.

Алгоритмы оптимальной структуры компьютерной сети

генетический алгоритм сети, метод моделирования сети, оптимальная структура сети, инновация сети, оптимизация сети.

Недостаточная пропускная способность сети, наиболее сильно. Нейронные сети и генетические алгоритмы.

Похожие статьи

Алгоритмы планирования масштабируемых заданий кластерной...

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

Генетический алгоритм планирования конкурирующих за канал...

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

Задача размещения задач на вычислительных ресурсах сводится к выбору таких параметров

"Планирование задач для вычислительного кластера с учетом сети и многопроцессорности...

Формирование оптимальной производственной программы на...

Исследуется проблема планирования производственной программы в условиях риска и неопределенности. Рассматривается многопродуктовая стохастическая модель оптимизации плана производства. Для формирования оптимального плана разработан алгоритм...

Выявление и классификация временных точек срыва плана...

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

Применение генетического алгоритма для решения задачи...

Таким образом, задача распределения ресурсов схожа с классической задачей распределения ресурсов в транспортной сети (между поставщиками и потребителями, мощностей между каналами передачи данных и т. п.) и состоит в определении величин xnk — поставка n-субъекта...

Оценка перспективной пропускной способности участков...

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

Алгоритмы балансировки в сети OSPF | Статья в журнале...

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

Методы оптимального планирования в системах военного...

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

Применение методов и моделей сетевого планирования...

Таким образом, применение системы сетевого планирования и управления на ООО «УОП «Нефтехим» способствует более эффективному распределению и рациональному использованию имеющихся на предприятии ограниченных ресурсов.

Алгоритмы оптимальной структуры компьютерной сети

генетический алгоритм сети, метод моделирования сети, оптимальная структура сети, инновация сети, оптимизация сети.

Недостаточная пропускная способность сети, наиболее сильно. Нейронные сети и генетические алгоритмы.

Задать вопрос