Планирование виртуальных вычислений

ПЛАНИРОВАНИЕ 
ВИРТУАЛЬНЫХ 
ВЫЧИСЛЕНИЙ

А. Б. Барский

Рекомендовано научно-методическим советом федерального государственного 
бюджетного образовательного учреждения высшего образования «Московский 
государственный университет путей сообщения (МИИТ)» в качестве 
учебного пособия для студентов, обучающихся по направлениям подготовки 
09.03.01 и 09.04.01 «Информатика и вычислительная техника» (бакалавриат 
и магистратура), профиль «Вычислительные машины, комплексы, системы 
и сети», и 10.03.01 «Информационная безопасность» (бакалавриат), профиль 
«Безопасность компьютерных систем»

УЧЕБНОЕ ПОСОБИЕ

Москва 
ИД «ФОРУМ» — ИНФРА-М
2018

УДК 519.687(075.8)
ББК 32.97я73
 
Б24

Барский А. Б.
Б24 
 
Планирование виртуальных вычислений : учеб. пособие / А. Б. Барский. — М. : ИД «ФОРУМ» : ИНФРА-М, 2018. — 200 с. — (Высшее 
образование). — www.dx.doi.org / 10.12737 / 19901.

ISBN 978-5-8199-0655-2 (ИД «ФОРУМ»)
ISBN 978-5-16-011892-5 (ИНФРА-М, print)
ISBN 978-5-16-104400-1 (ИНФРА-М, online)

Рассматриваются задачи и способы выполнения виртуальных вычислений Центром Grid-технологий по запросам, поступающим из глобальной 
сети. Предлагаются методы параллельных и распределенных вычислений, 
реализуемые пакетом прикладных программ Центра. Рекомендуется и иллюстрируется возможность широкого применения SPMD-технологии распараллеливания. Решаются проблемы выделения ресурсов, оптимизации 
их загрузки, оперативной сборки результатов распределенных вычислений. Обсуждаются проблемы виртуализации средств управления сложными системами в реальном времени. Исследуются возможности построения 
виртуальных баз данных с циркулирующими сегментами. Приводятся методы точного решения задач исследования операций для параллельного 
и распределенного программирования.
Соответствует требованиям Федерального государственного образовательного стандарта высшего образования последнего поколения.
Учебное пособие предназначено для студентов бакалавриата и магистратуры, аспирантов, преподавателей вузов, инженеров и научных работников, повышающих квалификацию, а также для разработчиков информационных и управляющих систем.

УДК 519.687(075.8)
ББК 32.97я73

А в т о р:
Барский Аркадий Бенционович, доктор технических наук, профессор, 
профессор кафедры «Вычислительные системы и сети» Московского 
государственного университета путей сообщения Императора Николая II

Р е ц е н з е н т ы:
Гагарина Л. Г., доктор технических наук, профессор Национального 
исследовательского университета «Московский институт электронной 
техники»;
Шилов В. В., кандидат технических наук, профессор Московского 
авиационного института (национального исследовательского университета)

ISBN 978-5-8199-0655-2 (ИД «ФОРУМ»)
ISBN 978-5-16-011892-5 (ИНФРА-М, print)
ISBN 978-5-16-104400-1 (ИНФРА-М, online)

ФЗ 
№ 436-ФЗ
Издание не подлежит маркировке 
в соответствии с п. 1 ч. 4 ст. 11

© Барский А.Б., 2017
© «ФОРУМ»: «ИНФРА-М», 2017

Предисловие

В основе данного учебного пособия лежит подход, в традициях 

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

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

Сегодня большое внимание уделяется организации и обеспече
нию виртуальных вычислений. Возникла некоторая «однобокость» 
исследований, когда почти без внимания остается «математика» — 
методы параллельных и распределенных вычислений для решения 
особо трудоемких задач. Поэтому в предлагаемом пособии большое 
внимание уделяется методам вычислений и их планированию, реализованным в Пакете параллельных прикладных программ Центра 
Grid-технологий. Некоторые предложения еще нуждаются в доработке и развитии.

Введение

Идеи виртуальных вычислений возникли на фоне развитой 

системы связи и информационного обслуживания, обеспечиваемой глобальной сетью Интернет. Современный уровень информатизации закономерно приблизился к разработке этих идей. 
Однако при их технической реализации запросы широкого пользователя, зачастую знакомого с компьютерными технологиями 
на основе стихийных знаний, не должны отправляться в некоторое глобально-сетевое информационное пространство, они предполагают вполне адресную составляющую. Специалисты в области информационных (в том числе компьютерных) технологий 
вынуждены задуматься: «Как это сделать?» и прежде всего: «Зачем 
это делать?».

Осуществляя практическое, «земное» обеспечение виртуальных, 

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

Термин Grid-вычисления (Grid-computing), где «grid» означает 

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

Пользователь может в любое время и в любом месте запросить 

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

Однако вряд ли работы вычислительного характера можно 

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

С Grid-технологиями связывают и задачи информационного 

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

Первые опыты в области Grid-технологий связаны с расчетами 

экспериментов в ядерной физике. Считается, что этот опыт стал 
базой формирования World Wide Web, WWW — всемирной паутины. С ним связывают имя Тима Бернерса-Ли. Перед ним была 
поставлена задача найти способ, который позволил бы ученым, 
участвующим в экспериментах на Большом адронном коллайдере, 
обмениваться данными и представлять результаты их обработки 
на всеобщее обсуждение. Т. Бернерс-Ли предложил создать в Европейской организации ядерных исследований (CERN) систему 
распределенного информационного обеспечения, основанную 
на использовании гипертекста и способную объединить научные 
центры всей Земли. Были написаны специальные программы, 
установленные на многих компьютерах мира, разбитых на группы, 
связанные со своим сервером. Эти программы могли взаимодействовать с единой базой данных (БД) CERN, перерабатывая данные 
и возвращая результаты.

В 1990 г. прототип того, что впоследствии получило название 

Всемирной паутины, был создан в CERN, а, начиная с 1991 г., первые браузеры и WWW-серверы появились в распоряжении ядерных 

физиков всего мира. Широкое распространение сразу же получили 
язык HTML и протокол HTTP.

Американские ученые Я. Фостер, К. Кессельман, Д. М. Ник, 

С. Тьюке и др. произвели теоретическое обобщение опыта CERN
и развили идеи WWW в область современного представления о будущей сети Grid. По их мнению, Grid является «надстройкой» Интернета, предназначенной для распределенных вычислений при 
решении задач высокой сложности в области науки и технологий. 
Однако математическими и алгоритмическими вопросами Grid-вычислений до настоящего времени не занимается почти никто!

Конечно, очень важно уметь связывать между собой ресурсные 

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

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

Tреш → min.

Как в свете данного критерия организовать обмен данными 

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

Численные методы вычислений должны быть ориентированы 

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

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

ется SPMD-технология (Single Program — Multiple Data, «одна программа — много потоков данных»). Эта технология отображает способ распараллеливания по информации и наиболее приемлема для 
организации Grid-вычислений.

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

Глава 1

ЗАДАЧИ ЦЕНТРА GRID-ТЕХНОЛОГИЙ

1.1. НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ

Концентрируя внимание на структуре и задачах Центра Grid
технологий, мы подразумеваем смелое, фантастическое развитие 
именно того, что фантастическим казалось вчера, — развитие «всемирной паутины», внедрение в нее вычислительных функций для 
повышения качества информационного обслуживания. Именно 
так и намечается дальнейший путь развития Интернета: от WWW 
к Grid. Таким образом, для Grid-технологии характерны два (традиционно смешиваемых) направления развития, определяющие 
их важность и различия в средствах достижения и исследования.

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

Однако неуправляемое, стихийное, даже «дикое» развитие Ин
тернета приводит к парадоксу: доступность огромных объемов мировой информации породила значительный вес отказов, ответов 
о действительной недоступности этой информации, о превышении 
допустимого времени поиска, об ошибках. Поисковые системы 
блуждают по иерархической, запутанной системе веб-серверов, натыкаясь на их перегрузку, образуя трафик для обратного движения 
информации. Мы с отчаянием следим за замершей планкой индикатора в ожидании выдачи знакомой записи «Error…» — с указанием предположения об окончании допустимого времени адресного обращения.

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

задача. Можно ли объединить всю информацию мира, имеющуюся 
в Интернете, в одну огромную базу данных, размеры которой даже 
трудно оценить, хотя такие попытки известны, чтобы при этом 
имелся неограниченный многоканальный доступ? Движение в направлении осуществления этой глобальной идеи и является задачей 
исследователей в области Grid-технологий. Ясно, что идеального 
и полного решения эта задача может никогда не получить. Однако 
стремиться к минимизации времени выполнения запроса, несмотря 
на структурную «удаленность» информации, несомненно, следует.

Второе направление развития Grid-технологий связано, как ранее 

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

Это означает, что в составе Интернета должны быть мощные 

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

При построении Grid-систем особую актуальность обретают 

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

Базовыми элементами защиты являются:

• аутентификация — проверка подлинности участника взаимо
действия с системой;

• механизм авторизации — проверка допустимости затребованной 

операции;

• конфиденциальность и целостность данных — защита от неле
гитимного доступа;

• биллинг и аудит — способность контролировать и подсчитывать 

объем использованных ресурсов и обеспечиваемых ими служб;

• строгое выполнение обязательств — способность устанавливать, 

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

1.2. GRID-ТЕХНОЛОГИИ РЕШЕНИЯ ИНФОРМАЦИОННЫХ ЗАДАЧ

Уже известны разработки, поддерживающие сложные распреде
ленные базы данных для многоканального использования. Одним 
из проектов является Oracle 10G, предназначенный для реализации 
коммерческой Grid-системы. Механизмы этой системы поддерживают следующие подсистемы и функции:
• Grid-хранения данных;
• Grid-серверов БД;
• Grid-серверов приложений;
• средства самонастройки узлов БД;
• система управления Grid;
• средства для разделения информации между узлами Grid.

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

В работе [8] на основе теории массового обслуживания доказано, 

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

Одним из способов построения БД с циркулирующей инфор
мацией является объединение серверов в единую замкнутую систему — «кольцо», по которому циркулируют сегменты этой базы. 
Абоненты же жестко связаны со своими серверами, обеспечивая 
примерно равные потоки запросов на каждый сервер. При этом 
должно учитываться среднее время ожидания нужного сегмента