Содержание к диссертации
Введение
ГЛАВА 1. Разработка структурно-функциональной модели центра обработки данных 10
1.1 Инфраструктура центра обработки данных 10
1.2 Технологии и структуры обработки и хранения данных ЦОД 16
1.3 Варианты применения ЦОД 23
1.4 Характеристики ЦОД 29
1.5 Соглашение о качестве обслуживания ЦОД 41
1.6 Постановка задачи исследования 46
Выводы по первой главе 50
ГЛАВА 2. Разработка моделей оценки качества предоставления информационных услуг в ЦОД 52
2.1 Модель оценки производительности ЦОД и запасов по
пропускным способностям 52
2.2 Модель распределения нагрузки в ЦОД 64
2.3 Модели размещения ресурсов в системах хранения данных ЦОД 68
2.4 Оценка надежности ЦОД 71
Выводы по второй главе 77
ГЛАВА 3. Разработка методов повышения эффективности редоставления информационных услуг в ЦОД 79
3.1 Понятие и определение эффективности ЦОД 79
3.2 Метод управления нагрузкой, поступающей на ЦОД 81
3.3 Обеспечение отказоустойчивости серверного комплекса ЦОД 86
3.4 Метод отказоустойчивого размещения задач в кластере ЦОД 99
3.5 Метод распределения памяти в кластере ЦОД 102
Выводы по третьей главе 111
ГЛАВА 4. Эксперимент на моделях и методах повышения эффективности предоставления информационных услуг в ЦОД 112
4.1 Оценка производительности ЦОД и запасов по пропускным способностям 112
4.2 Оценка влияния балансировки нагрузки на производительность ЦОД 114
4.3 Сравнение вариантов размещения ресурсов в системах хранения данных ЦОД 116
4.4 Оценка пропускной способности и вероятности потерь ЦОД 118
4.5 Оценка отказоустойчивости ЦОД 121
Выводы по четвертой главе 132
Заключение 134
Литература
- Варианты применения ЦОД
- Модель распределения нагрузки в ЦОД
- Обеспечение отказоустойчивости серверного комплекса ЦОД
- Сравнение вариантов размещения ресурсов в системах хранения данных ЦОД
Введение к работе
Актуальность темы диссертации. Фундаментом построения ИТ-инфраструктуры является Центр обработки данных (ЦОД). Предназначение ЦОД - обеспечение безотказной работы бизнес-процессов, надежное хранение данных и гарантированный доступ к ним, предоставление информационных услуг.
Центры обработки данных востребованы государственными службами (электронное правительство, госуслуги), крупными организациями, такими как, банки, страховые и торговые корпорации, предприятия добывающей отрасли, телекоммуникационные компании (биллинговые системы, хостинг, всевозможные Web-сервисы и социальные службы). Все они используют сложные бизнес-приложения, и их деятельность зависит от надежности функционирования ИТ-инфраструктуры.
Важнейшими преимуществами создания ЦОД являются консолидация вычислительных мощностей и систем хранения. В тоже время растущие потребности бизнеса необходимо удовлетворить в условиях ограниченных ресурсов: надо хранить больше данных в выделенном пространстве, быстрее производить вычисления, не потребляя и не выделяя слишком много энергии, передавать больше информации по имеющимся каналам связи, обеспечивать максимальную степень готовности эксплуатируемых ИТ-систем. И всё это с ограниченным финансированием. В таких условиях грамотное проектирование ЦОД является ключевым звеном для достижения эффективной работы предприятия, а указанные ограничения определяют выбор используемых технологий и оборудования.
Известно, что в области ИТ-систем высокой доступности ситуация постоянно и стремительно меняется. Отсутствие единого подхода к организации ЦОД, стандартов проектирования и эксплуатации различных серверных помещений и центров обработки ставят проблему выработки системного подхода к реализации инфраструктуры, а также разработки моделей и методов повышения эффективности предоставления информационных услуг в ЦОД. Появление опыта в виде стандартов, моделей и методов позволит унифицировать реализацию ЦОД и упростить внесение изменений в его инфраструктуру, способствовать тиражируемое и масштабируемости решений. Очевидно, что рациональным является выбор такой инфраструктуры, которая обеспечивала бы долгосрочную защиту инвестиций и позволяла компании выполнять текущие задачи и развиваться.
Особенное значение данная проблема приобретает в условиях экономического кризиса, который усилил дефицит ресурсов. Предприятия сокращают бюджеты на ИТ, меньше вкладывают в долговременные проекты вообще и в ЦОД в частности. Первостепенной становится задача создания легких, недорогих и в то же время эффективных решений, отвечающих требованиям бизнес-заказчиков. Основная проблема состоит в том, как в условиях постоянного увеличения стоимости ресурсов получать максимальную отдачу от их эксплуатации. Отсюда возникают ключевые вопросы, которые необходимо решать при реализации ЦОД, - каким образом добиться увеличения основных показателей (производительности, надежности и т.д.) при минимизации затрат (энергопотребление, администрирование), учесть возможный рост нагрузки, предусмотреть восстановление после сбоев и высокую доступность критически важных приложений и сервисов.
Сказанное говорит об актуальности разработки моделей и методов повышения эффективности предоставления информационных услуг в центрах обработки данных. Важно также учитывать технологии, базирующиеся на открытых отраслевых стандартах, минимизирующие проблемы взаимодействия по мере расширения ЦОД.
При оценке характеристик ЦОД большое значение имеют математическое моделирование и вычислительный эксперимент на модели.
Теория моделирования сложных систем и их элементов развита такими отечественными учеными, как В.А. Ершов, Г.П. Захаров, А.П. Кулешов, О.И. Кутузов, В.Г. Лазарев, И.А. Мизин, Ю.И. Рыжиков, Б.Я. Советов, С.А. Яковлев. Оценка вероятностно-временных характеристик систем, оптимизация и распределение ресурсов рассматривались в работах зарубежных ученых: Л. Клейнрок, Д. Мартин, У. Столлингс, Э. Таненбаум, М. Шварц и другие. Работы этих и ряда
других ученых составляют теоретическую базу моделирования систем, в том числе отдельных узлов, кластеров, центров обработки данных, сетей хранения данных и их элементов.
Сказанное говорит о важности научной задачи разработки моделей и методов повышения эффективности функционирования ЦОД при предоставлении информационных услуг, имеющей большое значение для экономики страны.
Целью работы является повышение эффективности функционирования центров обработки данных, предоставляющих информационные услуги.
Для достижения названной цели необходимо решение следующих задач:
-
Разработать структурно-функциональную модель центра обработки данных.
-
Разработать комплекс моделей оценки качества предоставления информационных услуг в центрах обработки данных.
3. Разработать методы повышения эффективности предоставления информационных
услуг в центрах обработки данных.
Объектом исследования являются центры обработки данных, выполненные в виде консолидации кластеров и систем хранения данных.
Предметом исследования являются процессы функционирования центров обработки данных при предоставлении информационных услуг.
Методы исследования. Для решения поставленных задач, в работе используются математические методы системного анализа, теории вероятности и математической статистики, эволюционных алгоритмов и теории массового обслуживания.
Научная новизна работы состоит в разработке моделей и методов повышения эффективности предоставления информационных услуг в ЦОД, позволяющих обеспечить соглашение о качестве обслуживания клиентов. Новые научные результаты:
-
Структурно-функциональная модель центра обработки данных отличается выделением набора структурных элементов и их функционального назЕїачения, присущих большинству современных ЦОД, что позволяет более полно описывать процессы предоставления информационных услуг.
-
Комплекс моделей оценки качества предоставления информационных услуг в центрах обработки данных отличается учетом многоэтапности обработки клиентского запроса, что дает возможность оценить необходимые требования к производительности ЦОД.
-
Методы повышения эффективности предоставления информационных услуг в центрах обработки данных учитывают зависимость показателей эффективности от характеристик ЦОД, что позволяет обеспечивать необходимое качество обслуживания клиентов.
Научные положения, выносимые на защиту:
-
Структурно-функциональная модель центра обработки данных.
-
Комплекс моделей оценки качества предоставления информационных услуг в центрах обработки данных.
-
Методы повышения эффективности предоставления информационных услуг в центрах обработки данных.
Достоверность научных результатов и выводов подтверждается: корректностью математических выкладок, обоснованностью используемых ограничений, корректностью интерпретации в предметной области, результатами моделирования.
Научная и практическая ценность диссертационной работы заключается в том, что модели и методы повышения эффективности предоставления услуг в ЦОД можно рассматривать как единую технологию обеспечения необходимого качества обслуживания клиентов. Полученные результаты моделирования представляют практическую ценность при выборе архитектуры центров обработки данных.
Результаты работы внедрены в учебный процесс СПбГЭТУ (ЛЭТИ) и используются при проведении лабораторных работ, а также в курсовом и дипломном проектировании по темам, связанным с функционированием ИТ-систсм, на кафедре автоматизированных систем обработки информации и управления.
Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись на XII международной конференции «Информатика: проблема, методология, технологии» (Воронеж, 9-12 февраля 2012 г.); ХШ международной конференции «Региональная информатика (РИ-2012)» (Санкт-Петербург, 24-26 октября 2012 г.); международной конференции «Региональная информатика», (Санкт-Петербург, 1-3 марта 2005 г.); второй всероссийской конференции «Абонентский доступ в сетях следующего поколения» (Санкт-Петербург, 2005 г.) и на научно-технических конференциях профессорско-преподавательского состава научных сотрудников и аспирантов СПбГУТ им. проф. М.А. Бонч-Бруевича в 2006 -2012 гг.
Публикации. По теме диссертационной работы опубликовано 12 научных работ, из них -3 статьи из перечня изданий, рекомендованных ВАК, и 9 - работ в научных трудах международных и всероссийских конференций.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 57 наименований. Основная часть работы изложена на 142 страницах машинописного текста. Работа содержит 41 рисунок, 12 таблиц.
Варианты применения ЦОД
Основным принципом создания ЦОД является принцип выделения областей обработки и хранения информации. К области обработки относятся вычислительные системы, такие как серверы приложений, баз данных. Область хранения отвечает за физическое хранение, размещение и доступ к данным, обеспечивает надежность хранения и целостность информации [40,41].
Разделение хранения и обработки данных позволяет использовать преимущества консолидации вычислительных ресурсов и позволяет управлять большими массивами данных, делая их доступными для любых сервисов вне зависимости от физического размещения серверов. Благодаря размещению физических массивов данных отдаленно друг от друга создаются катастрофоустойчивые системы, обеспечивающие непрерывность функционирования бизнес-приложений [55,62,63].
Организационно ЦОД строится вокруг центральных баз данных функционирующих на высокопроизводительных серверах. Вокруг них размещаются основные и вспомогательные системы, организуя вычислительную инфраструктуру для множества корпоративных ИТ-сервисов. Все серверы используют централизованную систему хранения данных на основе специализированной сети хранения и консолидирующих дисковых массивах, что позволяет гибко управлять ресурсами хранения в масштабах всего ЦОД. На базе сетевого оборудования организуются каналы связи, решения доступа и внутреннее взаимодействие между подсистемами ЦОД [28,29,40,41,63]. С точки зрения структурно-функциональной организации современный ЦОД включает серверный комплекс, систему хранения данных, систему эксплуатации и систему информационной безопасности, которые интегрированы между собой и объединены сетевыми решениями. ИТ-инфраструктура современного ЦОД приведена на рисунке 1.1.
Информационных ресурсов (ресурсный кластер). Отвечает за сохранение и предоставление данных серверам приложений. Ресурсными серверами являются, например, серверы СУБД и файл-серверы. ? Приложений. Выполняют обработку данных в соответствии с бизнес-логикой системы. К примеру, кластерами приложений является множество серверов, выполняющих модули Enterprise Application Server или Oracle Applications. " Представления информации. Осуществляют интерфейс между пользователями и серверами приложений. Терминальные серверы и web-серверы служат примером кластера представления информации. " Служебные. Обеспечивают работу других подсистем ЦОД. Так, служебными кластерами являются серверы управления системой резервного копирования. Обозначим СК как множество М1={СК. г": _ГБ, і - число кластеров у -й группы}.
Система хранения данных (СХД) предназначена для организации надёжного хранения информационных ресурсов и предоставления доступа к ним серверов; обозначим как множество М2={С ХД -_г . ,- YM z _ число СХД у -го типа}.
Сетевая инфраструктура включает: оборудование маршрутизации и коммутации; оборудование организации оптических каналов связи; оборудование подключения пользователей; средства обеспечения информационной безопасности; обозначим как множество М3={ СО _г _j y, і - наименований сетевого оборудования (СО) у -го типа}.
Инженерные системы, входящие в ЦОД, отвечают за надежное электропитание, климатику, физическую безопасность и кабельную инфраструктуру, предоставляя все необходимые условия для надежной эксплуатации вычислительного оборудования в целом, обозначим как множество М4. Системы управления ЦОД обеспечивают контроль и администрирование всех систем центра и являются частью инструментария перераспределения ИТ-ресурсов для наиболее эффективной эксплуатации приложений в меняющейся бизнес-среде. Компоненты управления образуют целостную систему, направленную на комплексное управление всей инфраструктурой ЦОД. Обозначим как множество М5.
ЦОД структурируется из функциональных модулей в зависимости от масштаба корпоративной сети, которую он обслуживает и собственно самого центра, нагрузки, особенностей запросов и бизнес-приложений. С увеличением нагрузки по определенному классу запросов производительность ЦОД увеличивается расширением серверного комплекса через добавление одного или нескольких серверов, появление новых бизнес-приложений может привести к появлению нового кластера серверов. При необходимости резервного копирования, зеркалирования и других процессов, требующих значительных объемов памяти все системы хранения являются съемными и взаимозаменяемыми. При необходимости можно добавлять дополнительные типы систем хранения - более современные или объемные [29,44,61,63].
Модель распределения нагрузки в ЦОД
К основным преимуществам DAS относятся: низкая стоимость в сравнении с другими решениями СХД, простота развертывания и администрирования, высокая скорость обмена данными между системой хранения и сервером. Благодаря этим преимуществам технология DAS завоевала популярность в сегменте малых офисов и небольших корпоративных ЦОД. В то же время DAS системы имеют и свои недостатки, к которым можно отнести: невозможность нескольким серверам совместно использовать файлы данных, ограниченное расстояние подключения сервера к системам хранилищ данных, невозможность применения виртуализации, так как доступная емкость равна физической емкости установленных в DAS дисков, проблемы масштабируемости - современные контроллеры способны обслуживать не больше четырех серверов, подключенных к DAS [12,62].
При относительно низкой стоимости оборудования DAS-системы используются для хранения потоковых мультимедиа данных благодаря высокой скорость обмена с дисками. При увеличении объема хранимой информации необходимо использовать другие решения.
В технологии Network Attached Storage (NAS) подключение системы хранения, роль которой часто выполняет обычный сервер, осуществляется непосредственно к сети ЦОД (рисунок 1.7). Соединение процессоров и устройств хранения обеспечивает высокопроизводительный канал Fibre Channel. Данное решение характеризуется простотой интеграции новых систем хранения в уже существующий ЦОД компании [28,29,49,62]. CepBqjbi обработки
Фактически NAS системы представляют собой эволюцию файл серверов. Серверы NAS, как правило, являются высокопроизводительными устройствами, подключаются непосредственно к сети и предназначены для организации доступа к файлам. Эти серверы оборудованы специальным программным обеспечением и аппаратной частью и оптимизированы для задач хранения [48].
Достоинства технология NAS: одновременный доступ к файловым ресурсам одной системы хранения с серверов и компьютеров различных архитектур; низкая стоимость подключения узлов за счет использования уже имеющейся инфраструктуры Ethernet; возможность соединения на больших расстояниях; NAS достаточно легко администрировать [15,41].
Недостатки технология NAS определяются применением Ethernet, а именно негарантированная доставка пакетов, сброс пакетов при переполнении буферов, задержки, связанные с маршрутизацией и фрагментацией пакетов.
Наиболее рационально NAS-решения применять для организации файлового доступа, размещения резервных копий файлов, кэширования файлов и для приложений, не имеющих жестких требований к времени отклика [41]. Storage Area Network (SAN) - сеть хранения данных. Это уже не отдельное устройство, а комплексное решение, представляющее собой специализированную сетевую инфраструктуру для хранения данных. Основой технологии является создание и подключение устройств хранения к специализированной сети, предназначенной исключительно для работы с запросами к этим устройствам. Подключение устройств хранения осуществляется через высокопроизводительный коммутатор, поддерживающий технологию Fibre Channel (FC-коммутатор). Подобное решение является наиболее эффективным при работе с большим объемом данных и высокой эффективностью запросов к системам хранения. Сети хранения данных интегрируются в виде отдельных специализированных подсетей в состав ЦОД [28,29].
SAN сети позволяют любому SAN серверу получать доступ к любому устройству хранения данных, не загружая при этом ни другие серверы, ни локальную сеть ЦОД. Кроме того, возможен обмен данными между устройствами хранения данных без участия серверов (рисунок 1.8).
Технология SAN Достоинства технологии SAN заключаются в независимости сети хранения SAN от внутренне сети ЦОД, что обеспечивает высокое быстродействие, отсутствие конфликта с трафиком сети ЦОД, удобное централизованное управление и соответственно высокая масштабируемость, гибкость, готовность и отказоустойчивость. Недостатки технологии SAN заключаются в высокой стоимости внедрения и достаточно медленный возврат инвестиций [29,41].
Таким образом, каждая из представленных технологий хранения лучше всего подходит для конкретных целей [12,15]. DAS - Оптимизирована для одиночных изолированных серверов и имеет низкую начальную стоимость капиталовложений. NAS - Оптимизирована по простоте управления и по совместному доступу к файлам с использованием недорогих сетей на основе Ethernet. SAN - Оптимизирована по производительности (большой объем передаваемых данных), по масштабируемости (несколько ленточных и дисковых накопителей управляются из одного центра) и по надежности (специализированные средства резервного копирования могут снизить загрузку серверов и локальной сети ЦОД) [28,29,41].
Классическая схема - построение собственного ЦОД. Такая модель применения ЦОД не всегда доступна даже крупным компаниям в силу высоких затрат на его создание и обслуживание. Поэтому данный подход рассматривается как частный случай, преимуществом которого является «право владения». Изначально корпоративный ЦОД создается для решения задач автоматизации бизнес-процессов самого заказчика и владельца ЦОД. При этом предполагается, что владелец может либо использовать его ресурсы единолично, либо предоставлять их в аренду другим лицам [40,44].
Обеспечение отказоустойчивости серверного комплекса ЦОД
Названные характеристики могут дать ценную информацию о свойствах ЦОД. Например, їотв характеризует среднее время обработки запроса на предоставление информационной услуги, а запасы D выражают готовность ЦОД продолжать устойчивое функционирование при увеличении нагрузки (интенсивности запросов) по тому или иному входу.
Выражение 2.1 не учитывает классов запросов и то, что в SLA-соглашениях могут задаваться ограничения на качество обслуживания для запросов различных видов, поэтому необходимо разработать модель ЦОД, которая учитывала бы современную структуру входного потока заявок. Для каждого класса запросов в SLA-соглашениях могут задаваться ограничения на среднее время ответа или максимальное время ответа для заданной доли запросов.
Рассмотрим следующие классы запросов: Поиск, Выбор, Добавление в корзину, Регистрация, Оплата и др., т.е. запросы, которые являются стандартными действиями пользователей при посещении коммерческих сайтов. Поведение пользователей на сайтах характеризуется их сессиями. Сессия пользователя состоит из последовательности запросов к сайту, а также времени на обдумывание, т.е. временем, прошедшим с момента отправки Web-сервером ответа и до поступления нового запроса в систему в рамках одной сессии. Типичная сессия может длиться несколько минут. Поэтому в модели необходимо учитывать длительное время жизни сессий.
Для различных коммерческих сайтов пользовательские сессии различны. Будем предполагать, что каждому сайту соответствует одна сессия. Пусть имеется п = 1, . . . , N кластеров, представляющих собой различные звенья Интернет-приложений. Для моделирования процесса обдумывания введем в систему виртуальный сервер (и=0) с бесконечным числом параллельных независимых каналов обслуживания. Бесконечное число каналов обслуживания в модели виртуального сервера характеризует время на обдумывание пользователей. Для примера рассмотрим случай, когда сессия состоит из двух и более запросов. После выполнения первого запроса сессии, он поступает в очередь к виртуальному серверу п, где, проведя некоторое время, характеризующее время на обдумывание, вновь поступает в систему в виде следующего запроса. Так продолжается до тех пор, пока не поступит последний запрос сессии, после чего сессия завершается, т.е. покидает систему. Сервер с бесконечным числом каналов обслуживания позволяет отразить в модели независимость времени на обдумывание пользователей от времени обработки запроса приложением.
Пусть также имеется к= 1,..., .К классов запросов, ./различных типов сессий, и /различных сайтову=1,...Д Каждый тип сессии соответствует одному сайту. Так же как и в модели ЦОД без учета сессий и классов запросов, предположим, что внешний источник поступлений запросов формирует пуассоновский процесс. Пользовательские сессии типа j поступают в систему с интенсивностью Xj и начинаются с запроса класса к, TRQJ-I,..., J. После выполнения запроса класса к, пользователи с типом сессии j тратят на обдумывание случайное время dj. После этого они либо возвращаются в систему с запросом класса к с вероятностью pfy,, is либо выходят из системы, завершая сессию, с вероятностью і - ]Г pfy. Пусть матрица pj = \р(Л] является матрицей вероятностей переходов пользователей по Web-страницам сайта j, имеющая размерность К К. Эта матрица определяет последовательность поступлений запросов в СеМО в пределах пользовательской сессии/ и отражает связь между поступлениями запросов класса к и к от одного и того же пользователя (рисунок 2.2). цод
Запросы класса к в многозвенной системе за одно посещение могут иметь различный маршрут и несколько раз посещать различные кластеры. Зная вероятности переходов запроса класса к между кластерами, можно определить интенсивности поступления запросов класса к в каждый кластер \пк, п = 1,..., N: xh + bipli = 1 P\,2 + зРз,2 3 2 P2,3 + 4P4,3
В качестве обслуживающего прибора в модели выберем кластер серверов, который в свою очередь может быть представлен как система М/G/l с дисциплиной обслуживания «разделение процессора». Предположим, что все серверы, принадлежащие одному кластеру, являются одинаковыми по производительности. Введем в рассмотрение вектор распределения серверов
Для эффективного использования кластеров нужно по возможности равномерно распределить задачи по серверам. В противном случае недогруженные серверы будут простаивать, в то время как задачи, работающие на перегруженном сервере, будут выполняться недопустимо медленно. Чтобы этого не происходило, требуется перераспределять задачи с загруженного узла на свободный. Данный процесс является одной из функций системы управления и носит название балансировки нагрузки.
При появлении новых заданий программное обеспечение, реализующее балансировку, должно принять решение о том, где (на каком вычислительном узле) следует выполнять вычисления, связанные с этим новым заданием. Кроме того, балансировка предполагает перенос {migration - миграция) части вычислений с наиболее загруженных узлов на менее загруженные узлы.
Задача распределения нагрузки актуальна и для ЦОД, поскольку в ЦОД в режиме реального времени параллельно выполняется множество различных задач. Распределение нагрузки может решаться, как для каждого кластера, так и для ЦОД в целом. При распределении задач по серверам их стараются распределять так, чтобы загрузка серверов была равномерной. Принятие решения о распределении происходит через определенные промежутки времени, которые назовем циклами.
Сравнение вариантов размещения ресурсов в системах хранения данных ЦОД
Рассмотрим вопрос обеспечения отказоустойчивости вычислительного кластера. Этот подход реализуется посредством отказоустойчивого размещения задач, то есть такого статического распределения задач по серверам, при котором определенное число копий каждой задачи размещается на различных серверах.
Кластер рассматривается как совокупность п однотипных серверов, объединенных коммутационной системой. Каждый сервер имеет один процессор и память ограниченного объема. Кластер выполняет фиксированное задание Г, которое представляет собой известное множество задач Y={U\, Ц, ... , UL} с заданными требованиями к порядку их выполнения и взаимосвязям.
В процессе работы кластера возможны отказы серверов. Состояние кластера определяется как sv =сті,..., a„, где a,=0, если Mt - работоспособный сервер (р-Сервер) и а,=1, если Mt- отказавший сервер (о-Сервер); .?0=00...0 -начальное состояние кластера; все состояния sv Ф s называются искаженными. Известно начальное распределение задач по серверам при отсутствии их отказов (для состояния s ), описываемое матрицей D задача Uj назначена для выполнения на сервере Mt и размещена в нем, d%=0 в противном случае; каждая задача назначена на один и только один сервер. Задачи, назначенные на сервер Mt в соответствии с начальным размещением задач, назовем собственными задачами этого сервера.
Качество работы кластера оцениваем его функциональной мощностью Ev в состоянии sv, которое определяется как сумма весов всех задач, назначаемых для выполнения в работоспособные серверы в состоянии sv.
Требуемый уровень отказоустойчивости кластера задается множеством =bv) работоспособных состояний, которое определяется как множество всех таких состояний, число к отказавших серверов для которых не превосходит заданного значения d, очевидно S=su$, где 5 со={5(й} - множество искаженных работоспособных состояний. Требуется путем организации при отказах сервера надлежащего перераспределения задач между различными р-Серверами обеспечить выполнение заданных требований к отказоустойчивости кластера и к другим его показателям. Для этого при проектировании кластера или при подготовке к реализации в нем определенного задания, необходимо найти оптимальные планы распределения задач для каждого состояния sa є S и результирующее отказоустойчивое размещение задач Z= где Zji =1, если задача Uj размещена на сервере Mt (то есть ее программный код загружен в память сервера Mt), zp =0 в противном случае; zy;- определяется как дизъюнкция значений б/ .для всех состояний sveS (включая начальное).
После того как оптимальные планы Da найдены, каждый сервер заранее обеспечивается аппаратными и программными ресурсами, необходимыми для выполнения задач, которые могут назначаться ему в любом состоянии sveS. При переходе кластера вследствие отказов некоторых серверов в любое искаженное состояние sw є S и обнаружении этого факта во всех р-Серверах начинается выполнение задач, назначенных им в соответствии с планом Da.
Рассматриваем случай, когда в каждом состоянии s подвергаются перераспределению, то есть передаются для выполнения в какие-либо р-Серверы, либо отбрасываются только собственные задачи отказавших серверов, а собственные задачи всех р-Серверов продолжают выполняться на «своих» серверах.
Эта задача относится к классу задач дискретной оптимизации с булевыми переменными, для решения которых в принципе могут применяться точные методы математического программирования. Однако, поскольку для многих задач практической сложности применение таких методов затруднено ввиду их чрезвычайно большой трудоемкости, то целесообразно использование эвристических методов, дающих не точное, а некоторое «хорошее» решение. К ним относятся различные модели эволюционных вычислений, в частности генетические алгоритмы [22,45,60,61].
Алгоритмы этого класса - поисковые алгоритмы, использующие механизмы, прототипом которых являются процессы эволюции популяции живых организмов, подчиняющиеся принципам естественного отбора и носят название генетических алгоритмов (ГА). Алгоритм осуществляет поиск лучшего решения в пространстве поиска решений. Это пространство под воздействием операторов алгоритма, имитирующих биологические механизмы эволюции изменяется (эволюционирует) в направлении «улучшения» содержащихся в нем решений. Результатом такой эволюции должно быть пространство поиска, содержащее наилучшие (или приемлемые) решения, которые и обнаруживаются алгоритмом. В них используется эволюционный принцип выживания наиболее приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частности, генетические алгоритмы [45,61]:
Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее, максимизируется) и называется целевой функцией [45].
