Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент icon

Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент



НазваниеДиссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент
Дата конвертации05.11.2012
Размер335.13 Kb.
ТипДиссертация

Министерство образования и науки

Российской Федерации.

Московский физико-технический институт

(государственный университет)

Факультет управления и прикладной математики

Кафедра информатики


МАТЕМАТИЧЕСКАЯ МОДЕЛЬ БАЛАНСИРОВКИ НАГРУЗКИ

ПУТЁМ МИГРАЦИИ ПРОЦЕССОВ


Диссертация на степень магистра

студента 273 «б» группы

Подлесных Дмитрия Артуровича


Научный руководитель: доцент,

кандидат физико-математических наук,

Александр Геннадьевич Тормасов .


Долгопрудный, 2008.

Содержание

Введение 3

1. Существующие системы балансировки нагрузки. 6

1.1 Балансировка нагрузки Web-серверов. 6

1.3 Внешний мониторинг состояния серверов 7

1.4 Внутренний мониторинг состояния серверов 8

1.5 Выбор сервера 8

1.6 Переадресация трафика 12

1.7 Выбор компьютера на глобальном уровне 14

1.8 Избыточные системы балансировки 16

2. Классификация ресурсов в операционных системах. 18

2.1 Булевские ресурсы 19

2.2 Пространственные ресурсы 19

2.3 Временные ресурсы 20

2.4 Понятие цены выделения ресурса 21

3. Математическая модель 23

3.1 Модель размещаемого процесса 23

3.2. Модель компьютера 24

3.3 Модель сети 24

3.4 Условия допустимости миграции 25

3.5 Что происходит при миграции 26

4. Выбор оптимального принимающего компьютера 27

4.1. Оценка будущего потребления ресурсов 27

4.2. Функция полезности 28

4.3 Функция оценки стоимости переноса 29

4.4 Функции оценки системы 30

4.5 Пример работы системы 30

Заключение 33

Список литературы 34






Введение


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


Под термином «процесс» может подразумеваться как обычный процесс в операционной системе, так и виртуальная (или паравиртуальная [1]) операционная система, например, виртуальный частный сервер в Virtuozzotm и OpenVZ, домен в Xen, зона в Solaris, а также группа процессов, связанных между собой средствами межпроцессной коммуникации (очередями сообщений, общей памятью, семафорами). На нити исполнения (threads) в данной работе термин «процесс» не будет распространяться, так как нити не переносятся отдельно друг от друга на разные компьютеры.

Перенос процессов с одного компьютера на другой без нарушения их работы средствами операционной системы назовём миграцией процесса.[2]. Если во время миграции процесс может работать, то миграцию называют живой (live migration) [3].

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

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

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

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

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

Операционная система (или, для систем паравиртуализации, гипервизор) должны поддерживать возможность переноса процесса средствами самой системы без нарушения работы мигрирующего процесса. Системы Virtuozzotm, OpenVZ, Xen и Solaris предоставляют такую возможность. В противном случае производить балансировку нагрузки можно только выбором компьютера, на котором будет запущен новый процесс.

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

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

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

1. Существующие системы балансировки нагрузки.

1.1 Балансировка нагрузки Web-серверов.


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



Рисунок 1.1. Система балансировки нагрузки на 2 web-сервера.

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

1.3 Внешний мониторинг состояния серверов


При проведении внешнего мониторинга система балансировки нагрузки рассчитывает время отклика сервера, для чего направляет на сервер запрос и замеряет время ответа, например, по протоколу управления сообщениями Internet Control Message Protocol (ICMP). Эти тесты позволяют системе проверить готовность сервера к работе и узнать, сколько времени необходимо для передачи информации с сервера на систему балансировки и обратно. Если система балансировки нагрузки не получает отклика от сервера после нескольких последовательных запросов, считается, что данный сервер недоступен, работает с большой нагрузкой или произошёл какой-либо сбой.

Чтобы убедиться в правильности функционирования стека TCP сервера, система балансировки нагрузки предпринимает попытку установить соединение по протоколу TCP, для чего требуется осуществить состоящий из трех этапов обмен подтверждающими сообщениями. Сначала серверу направляется TCP-пакет, в котором значение бита SYN установлено равным 1. Если после этого система балансировки получает от сервера TCP-пакет, в котором значение бита SYN равно 1, а значение бита ACK тоже установлено равным 1, она направляет серверу второй TCP-пакет со значением бита SYN равным 0 и значением бита ACK равным 1. Если обмен подтверждающими сообщениями завершился успешно, значит, TCP-стек сервера функционирует нормально. Качество TCP-соединения с сервером оценивается системой как время, необходимое для выполнения всех трех этапов обмена подтверждающими сообщениями.

Лучшие средства балансировки нагрузки могут обеспечивать мониторинг времени отклика и готовности как самого Web-сервера, так и установленных на нем приложений еще одним способом: на сервер направляется запрос по протоколу HTTP на получение информационных материалов или адреса URL. Пусть именем начальной страницы сервера web1.kto-to.com будет index.html. Система балансировки нагрузки на рисунке 1.1 может инициировать предусмотренную по протоколу HTTP команду Get, запрашивая тем самым у сервера web1.kto-to.com содержимое страницы index.html. Если код возврата, направляемый системе Web-сервером, будет 200, значит, начальная страница на сервере web1.kto-to.com недоступна. Время отклика определяется системой балансировки нагрузки как время с момента отправки запроса на предоставление информации до момента получения кода возврата.
^

1.4 Внутренний мониторинг состояния серверов


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

1.5 Выбор сервера


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

Современные системы балансировки нагрузки позволяют администратору определять правила выбора сервера по своему усмотрению. Можно, к примеру, включить в эти правила такие критерии, как коэффициент загрузки процессора и памяти, число открытых соединений TCP и количество пакетов, поступающих на сетевую интерфейсную плату того или иного сервера. Формула, по которой система балансировки определяет уровень загруженности серверов, может выглядеть примерно так: загрузка сервера = (10 * уровень использования ЦП) + (4 * уровень использования памяти) + (6 * число открытых TCP-соединений) + (3 * число переданных пакетов). При получении запроса от клиента система балансировки нагрузки рассчитывает по этой формуле нагрузку каждого сервера и направляет запрос серверу с наименьшей нагрузкой.

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

При организации устойчивого соединения основная задача системы состоит в том, чтобы идентифицировать клиента и связать соответствующий идентификатор с сервером-получателем запроса. Cистемы балансировки нагрузки могут используют в качестве идентификатора клиента применяемый им IP-адрес отправителя, но этот адрес может оказаться адресом шлюза, через который идёт связь с подсетью клиентов. Количество запросов, идущих через один шлюз, может быть таким, что требуется распределить их по нескольким серверам. Проблему идентификации клиентов можно решить, если воспользоваться защищенными сеансами связи по протоколу Secure Sockets Layer (SSL). Протокол SSL назначает каждому установленному сеансу связи специальный идентификатор, а прикладные программы для виртуальных магазинов часто пользуются этим протоколом. Ещё одно средство поддержания устойчивых соединений - это распространяемые по сети Web cookie-файлы. Эти файлы содержат как сведения о клиенте, так и другие данные (например, о том, с каким сервером клиент связывался в последний раз). Анализ содержимого cookie-файлов помогает системе балансировки нагрузки идентифицировать клиентов и подбирать для них наиболее подходящий сервер. В число поставщиков систем балансировки нагрузки, оснащенных средствами работы с cookie-файлами, входят такие компании, как Alteon WebSystems, ArrowPoint Communications, F5 Networks и Resonate.

Cуществует два варианта выбора сервера - непосредственное связывание (immediate binding) и отложенное связывание. ^ При непосредственном связывании система балансировки нагрузки подбирает сервер для клиента и направляет запрос на него в тот самый момент, когда система получает от клиента пакет TCP SYN. При этом система балансировки выбирает сервер, руководствуясь заданными правилами распределения нагрузки серверов, а также IP-адресом, содержащимся в полученном от клиента пакете TCP SYN. Этот метод обеспечивает высокое быстродействие, но при его применении система балансировки просто не успевает проанализировать другую информацию: в частности, идентификатор сеанса связи по протоколу SSL, содержимое cookie-файла, адрес URL и данные прикладной программы.

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

1.6 Переадресация трафика


Системы балансировки нагрузки могут перенаправлять трафик клиентов на избранный сервер несколькими способами: по методу трансляции адресов с управлением доступом к среде передачи (media access control (MAC) address translation, MAT), по методу трансляции сетевых адресов (Network Address Translation, NAT), или - при использовании отложенного связывания - с помощью механизма шлюза TCP (TCP gateway).

Метод MAT может быть реализован системой балансировки нагрузки при условии, что каждый Web-сервер наряду со своим физическим IP-адресом использует в качестве интерфейсного адреса обратной связи (loopback interface address) VIP-адрес системы балансировки. Получив от клиента пакет и назначив ему соответствующий сервер, система балансировки заменяет в этом пакете MAC-адрес получателя MAC-адресом соответствующего сервера, после чего направляет пакет на выделенный сервер. В пакете содержится IP-адрес клиента, так что для прямого ответа клиенту сервер использует в качестве IP-адреса получателя первоначальный IP-адрес клиента. Однако в качестве IP-адреса отправителя сервер указывает VIP-адрес системы балансировки нагрузки, как если бы трафик поступал клиенту именно от нее. Таким образом, следующий пакет от клиента направляется не ответившему ему серверу, а системе балансировки нагрузки.

При использовании метода NAT система балансировки направляет полученный от клиента пакет назначенному серверу лишь после того, как выполнит над пакетом несколько операций: во-первых, она замещает в пакете адрес получателя (т. е. собственный VIP-адрес) IP-адресом назначенного сервера, а во-вторых, - меняет IP-адрес отправителя на свой VIP-адрес. Данный метод позволяет скрывать от клиентов IP-адреса Web-серверов, так что последние могут использовать любые IP-адреса, в том числе и частные. При этом Web-серверы не обязательно должны быть непосредственно соединены с системой балансировки (иначе говоря, входить в один и тот же сегмент ЛВС); достаточно, чтобы они могли устанавливать соединения по протоколам статической или сетевой маршрутизации.

Шлюз TCP. При установке непосредственного (немедленного) связывания системы балансировки нагрузки могут направлять трафик по методам MAT или NAT на уровнях 2 или 3. Но если речь идет об отложенном связывании, системы балансировки должны управлять трафиком на уровне TCP и на более высоких уровнях. Отложенное связывание предполагает, что система балансировки нагрузки и клиент устанавливают соединение по протоколу TCP так, чтобы система могла получить данные приложения еще до назначения сервера. Затем средство балансировки устанавливает TCP-соединение с назначенным сервером и передает ему клиентский запрос. Далее система балансировки передает клиенту ответ сервера, для чего опять-таки используется TCP-соединение "система балансировки - клиент". Описанная функция и называется шлюзом TCP. Специалисты компании Resonate реализуют ее в системе балансировки нагрузки с помощью специального агента (этот агент устанавливается на сервере, который обеспечивает прямое TCP-соединение между клиентом и сервером, выступающим в роли средства балансировки). По терминологии, предложенной компанией-поставщиком, данная реализация именуется системой с транзитом TCP-соединений (TCP connection hop).
^

1.7 Выбор компьютера на глобальном уровне


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

Допустим, виртуальная система с именем www.kto-to.com представлена на двух сайтах. Функции серверов DNS для этой машины выполняют две системы балансировки нагрузки: одна — в России, вторая — в США. Разрешение имен для таких служб, как ftp и электронная почта, а также для других серверов и компьютеров в Internet осуществляется официальным сервером DNS домена kto-to.com. Администратор может делегировать имя поддомена www.kto-to.com обоим средствам балансировки, после чего обе системы выравнивания нагрузки станут серверами имен для поддомена www.kto-to.com. Чтобы получить подобную конфигурацию, нужно для каждой системы балансировки определить DNS-имя www.kto-to.com и поставить его в соответствии с ее собственным локальным VIP-адресом. Поскольку две системы балансировки обмениваются информацией о конфигурации и нагрузке, обе они "понимают", что виртуальная система www.kto-to.com имеет два VIP-адреса (т. е. представлена двумя узлами), а также имеют информацию о нагрузке и доступности каждого из сайтов.

Когда клиент обращается по адресу www.kto-to.com, он запрашивает у локального сервера DNS провайдера IP-адрес компьютера www.kto-to.com. Если в кэше не содержится данных о запрошенном IP-адресе, этот сервер направляет запрос официальному серверу DNS домена kto-to.com. Cервер DNS домена kto-to.com назначил имя www.kto-to.com двум системам балансировки нагрузки, поэтому домен kto-to.com возвращает серверу DNS провайдера IP-адреса двух систем балансировки нагрузки в качестве сервера имен www.kto-to.com. Затем сервер DNS провайдера направляет запрос на получение имени одной из двух систем балансировки нагрузки. Обе системы представляют собой серверы имен, поэтому, не получив ответа от первого сервера, локальный сервер DNS направит повторный запрос уже второй машине. Система балансировки нагрузки выбирает на основе заданных для сайта критериев наиболее подходящий сервер и возвращает локальному серверу DNS провайдера VIP-адрес сервера сайта. Получив от сервера DNS провайдера VIP-адрес главной машины www.kto-to.com, клиент адресует свой HTTP-трафик системе балансировки нагрузки ближайшего сайта, и эта система выбирает для клиента один из локальных серверов. Поскольку локальный сервер DNS кэширует разрешенную запись DNS на срок, соответствующий указанному в записи параметру Time To Live (TTL), поставщики обычно рекомендуют не задавать больших значений TTL, чтобы клиент имел возможность быстро получить новый VIP-адрес и переключиться на другой доступный сайт.

Системы балансировки нагрузки могут выбирать подходящий сайт, а также перенаправлять трафик и другим методом: с помощью переадресации средствами протокола HTTP. Данный метод не предусматривает использования DNS-функции системы балансировки нагрузки. Вместо этого администратор определяет на сервере DNS запись о www.kto-to.com и соответствующие ей VIP-адреса. Когда клиент получает VIP-адрес www.kto-to.com и направляет по протоколу HTTP запрос системе балансировки нагрузки, последняя подбирает для него наиболее подходящий узел. Если избранный сайт не расположен не слишком далеко, система балансировки направляет браузеру клиента HTTP-команду на переадресацию, и браузер устанавливает соединение с указанным сайтом. Описанный метод дает системе балансировки нагрузки возможность еще до выбора узла получить о клиенте более подробные сведения (например, его IP-адрес). Однако клиент может воспользоваться VIP-адресом, возвращенным сервером DNS, и попытаться установить соединение с не отвечающим на запросы узлом.

Помимо метода динамического назначения клиенту того или иного узла системы балансировки нагрузки могут использовать для связывания конкретных клиентов с конкретными сайтами метод статического назначения (static mapping method). Допустим, у нас имеется зеркальный узел Web в Европе. Нам нужно, чтобы клиенты из Европы все время попадали именно на европейский сайт - за исключением тех случаев, когда он выходит из строя и система балансировки нагрузки направляет европейский трафик на узел, расположенный в США. Администратор имеет возможность ввести в систему балансировки весь блок европейских IP-адресов и настроить её так, чтобы любой запрос от клиента с европейским IP-адресом сначала направлялся на сайт в Европе.
^

1.8 Избыточные системы балансировки


Системы балансировки нагрузки - средства доступа к серверам Web, и потому выход такого средства из строя может повлечь за собой полное прекращение работы узла. Отсюда вывод: при планировании и реализации инфраструктуры с выравниванием нагрузок важно принимать во внимание отказоустойчивость средств балансировки, а также выбирать решения с широкой полосой пропускания, способные обеспечить высокую производительность системы в целом. В распоряжении администратора имеются две схемы организации избыточных систем балансировки нагрузки: первая предполагает, что одна система балансировки функционирует в активном режиме, а другая - находится в состоянии ожидания (active-and-standby type); вторая же схема предусматривает одновременное функционирование обеих систем балансировки (active-and-active type). Обе схемы предполагают наличие на одном узле двух экземпляров систем балансировки нагрузки.

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

В схеме с двумя активными системами балансировки нагрузки обе системы обслуживают трафик и подстраховывают друг друга. Представим для примера узел Web, состоящий из четырех серверов. Два из них обслуживаются первой системой балансировки нагрузки, и два - второй. Когда одна система балансировки выходит из строя, заботу обо всех четырех серверах берет на себя вторая система. Этот метод в полной мере использует ресурсы средств балансировки и повышает производительность узла.
^

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


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

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

2.1 Булевские ресурсы


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

2.2 Пространственные ресурсы


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



Рисунок 2.1 Пространственный ресурс.

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

2.3 Временные ресурсы


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

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



Рисунок 2.2. Временной ресурс.

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

2.4 Понятие цены выделения ресурса


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

Цена выделения пространственного или временного ресурса – это количество условных единиц, за которое засчитывается одна единица измерения ресурса в данной ситуации. Это положительное действительное число используется, как коэффициент пропорциональности в формулах. Значение цен различных ресурсов изменяется в ходе работы системы независимо друг от друга. При уменьшении количества свободного ресурса она растёт, при уменьшении – падает. Для настройки системы оптимизации администратор может изменять значения цены выделения любого ресурса.
^

3. Математическая модель


Рассмотрим распределённую вычислительную систему из c компьютеров, в которой учитываются x видов булевских ресурсов, y видов пространственных ресурсов и z видов временных ресурсов [4]. Мигрирующий процесс изначально находится на компьютере s.
^

3.1 Модель размещаемого процесса


Пусть рассматриваемый процесс требует b1...bx булевских ресурсов (bi=0, если процесс не требует ресурса i, bi=1, если процесс требует ресурс i, 1ix); v1...vz временных ресурсов. p1...py пространственных ресурсов. Для пространственных ресурсов известны максимальные значения потребления h1...hy.

Известно время t1...tc, за которое процесс может быть перенесён на каждый компьютеров сети. Процессу требуется связь с компьютерами сети с пропускной способностью n1...nc. Процесс может быть остановлен без нарушения его работы на время T. Для миграции требуется связь между компьютерами с пропускной способностью m.

Сделаем следующие допущения.

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

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

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

3.2. Модель компьютера


  1. Для каждого компьютера j известно, сколько у него есть булевских B1j...Bxj, временных V1j...Vzj и пространственных P1j...Pyj ресурсов. Компьютер будет доступен в течение времени Rj, после чего количество свободных ресурсов на компьютере уменьшится (например, будет запущен какой-то новый процесс или компьютер будет выведен из кластера для использования в учебном процессе).

  2. Сделаем следующие допущения:

  3. 1. Все компьютеры могут принять мигрирующий процесс при достаточном количестве ресурсов. Если планируется, например, освободить несколько компьютеров для занятий, один из булевских ресурсов – доступность – станет равным 0.

  4. 2. За время поиска оптимального варианта и миграции процесса существенных изменений, могущих привести к изменению выбора целевого компьютера для миграции, не произойдёт.
    1. ^

      3.3 Модель сети


  5. Сеть, связывающую компьютеры, считаем полносвязным графом. Современные кластерные сети, например, Myrinet [5], несмотря на физическое исполнение в виде кабелей, соединяющих узлы кластера с центральным коммутатором, логически представляются как соединение каждого компьютера с каждым. Пропускная способность канала связи между компьютерами i и j принимаем равной Nij.
    1. ^

      3.4 Условия допустимости миграции


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

наличие необходимых булевских ресурсов:

  1. biBid i: 1ix;

наличие необходимого количества пространстваенных ресурсов:

  1. piPid i: 1iy;

наличие необходимого количества временных ресурсов:

  1. viVid i: 1iz;

допустимость времени миграции:

  1. tdT;

достаточная для миграции пропускная способность сети:

  1. Nsdm;

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

  1. Ndini i: 1ic;

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

  1. 2*tdRd

(считаем, что время миграции в обоих направлениях одинаково).

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

3.5 Что происходит при миграции


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

  1. Pid - = pi i: 1iy;

  2. Vid - = vi i: 1iz.

А на исходном количества временных и пространственных ресурсов после истечения времени миграции td увеличатся:

  1. Pis + = pi i: 1iy;

  2. Vis + = vi i: 1iz.

Свободная пропускная способность сети тоже изменится:

  1. Nsi + = ni i: 1ic;

  2. Ndi - = ni i: 1ic.
^

4. Выбор оптимального принимающего компьютера


Если условиям (1)-(6) допустимости миграции отвечает только один компьютер, именно на него и будет произведен перенос. Если же таких компьютеров несколько, возникает проблема выбора.
^

4.1. Оценка будущего потребления ресурсов


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

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

  1. Если процесс не требовал какого-либо булевского ресурса, то он и не потребует его в будущем.

  2. Если процесс требовал в прошлом какой-то объём пространстваенного ресурса, то он может потребовать такой же объём ресурса в будущем.

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

  1. hiPid i: 1iy

Для надёжности можно рассматривать также наличие большего количества ресурсов на целевом компьютере. Пусть k>1 – коэффициент запаса, тогда условием отбора будет

  1. k*viVid i: 1iz.

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

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

4.2. Функция полезности


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

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

  1. W = S – V

В таком случае условие оптимальности выбора приобретает вид:

  1. W = S – V -> max
^

4.3 Функция оценки стоимости переноса


Функция оценки стоимости переноса должна учитывать возможные затраты ресурсов на само осуществление переноса. Во-первых, это время переноса td.

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

Введём функцию ^ V в виде:

  1. V = a1*td+a2*Ud

Коэффициенты a1 и a2 предназначены для компенсации различия единиц измерения и выбираются администратором системы.

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

4.4 Функции оценки системы


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

Состояние S системы определяется исходя из оставшихся свободными ресурсов и вычисляется как линейная комбинация различных функций, коэффициенты перед которыми выбирает администратор системы исходя из своих целей. Примеры функций:

  1. Минимальное отношение свободных ресурсов к имеющимся ресурсам среди всех машин системы для всех ресурсов.

  2. Доля или количество процессов, которым хватает ресурсов.

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

  4. Минимальное количество свободных ресурсов.

Для равномерного распределения нагрузки можно выбрать 4-ю из вышеуказанных функций

  1. ,

где gi и hi — коэффициенты цены выделения единицы ресурса соответствующего типа.
^

4.5 Пример работы системы


Рассмотрим сеть с c=4, x=1, y=1, z=1.

Булевский ресурс есть везде: B11=B12=B13=B14 =1.

Пространственных ресурсов разное количество:

P11 = 1; P12 = 2; P13 = 3; P14 = 4.

Аналогичная ситуация с временными ресурсами:

V11 = 1; V12 = 2; V13 = 3; V14 = 4.


Все компьютеры будут работать достаточно долго:

R1=R2=R3=R4=1000.

Процесс требует ресурс b1, p1=2 , v1=2, h1=3.

Времена миграции: t1=0 (процесс переносится как раз с этого компьютера; t2=1; t3=2; t4=3.

Процесс не требует связи по сети n1=n2=n3=n4=0.

Для миграции требуется пропускная способность сети m=1, процесс можно останавливать на T=10, пропускная способность всех каналов связи Nij =10.


В соответствии с формулами (1)-(7) допустимыми будут признаны компьютеры 2, 3 и 4, на которых достаточно ресурсов. Далее по формуле (14) будет отброшен компьютер 2, так как процесс потреблял когда-то больше ресурсов, чем на нём есть. После миграции на 3-й компьютер на нём останется 1 единица свободных пространственных и временных ресурсов, а на 4-й – 2 единицы. Для компьютеров 3 и 4 рассчитаем функцию полезности.









Видим, что дальнейшее решение системы зависит от заданных администратором коэффициентов: если, например, g1=h1=a1=1, то будет по максимуму функции полезности будет выбран 4 компьютер (с большим количеством ресурсов), если время миграции более важно и a1=3, то будет выбран 3-й компьютер.


Заключение


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

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

Список литературы


  1. Подлесных Д. А. Сравнение технологий виртуализации операционных систем. //Труды XLVIII научной конференции «Современные проблемы фундаментальных и прикладных наук», часть VII. Долгопрудный, издательский центр оперативной полиграфии, 2005.

  2. Миркин А. Л. Миграция виртуальных серверов в режиме реального времени. //Труды XLVIII научной конференции «Современные проблемы фундаментальных и прикладных наук», часть VII. Долгопрудный, издательский центр оперативной полиграфии, 2005.

  3. Подлесных Д. А. Алгоритм переноса процессов без их остановки в современных операционных системах. //Труды 49 научной конференции «Современные проблемы фундаментальных и прикладных наук», часть VII. Москва, «Солар», 2007

  4. Подлесных Д. А. Балансировка нагрузки с помощью миграции процессов. //Сборник «Моделирование и обработка информации», в печати.

  5. Сайт производителя оборудования Myrinet http://www.myri.com/

  6. В.А. Петров, А.Г. Тормасов. Перенос задания в вычислительной системе. //Сборник «Моделирование и обработка информации», в печати.

  7. Протасов С.С., Белоусов С.М., Тормасов А.Г. Математическая модель и метод построения сервиса балансирования нагрузки между серверами асимметричной фермы // Электронный журнал "Исследовано в России", 7, 2166-2177, 2004. http://zhurnal.gpi.ru/articles/2004/204.pdf

  8. Тао Чжоу. Системы балансировки нагрузки Web-серверов. http://www.citforum.ru/internet/webservers/websbal.shtml

  9. Петров В.А. Функции потребления ресурсов заданием на различных компьютерах вычислительной сети //XXXIV Гагаринские чтения. Научные труды Международной молодёжной научной конференции в 8 томах. М.: МАТИ, 2008 – Т 6. – С. 232.

  10. Петров В.А., Тормасов А.Г. Доставка информации пользователю в распределенной системе // Моделирование и обработка информации: Сб. ст. МФТИ – М., 2007 – С. 260-271.

  11. Миркин А.Л. Виртуальные серверы и их миграция в режиме реального времени // XXXIV Гагаринские чтения. Научные труды Международной молодёжной научной конференции в 8 томах. М.: МАТИ, 2008 – Т 6. – С. 200.








Похожие:

Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДиссертация на соискание академической степени магистра по направлению информационные технологии в физико-математическом образовании Научный
Охватывает все позиции, информация по которым может быть представлена в глобальной сети
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДиссертация на соискание академической степени магистра по направлению «Информационные технологии в физико-математическом образовании» Научный к ф. м н
...
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДиссертация рекомендована к защите на заседании кафедры
Председателю Диссертационного совета (шифр совета) по (отрасль) наукам в Московском государственном социальном университете (уч степень,...
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДиссертация на соискание учёной степени кандидата экономических наук Научный руководитель к э. н., профессор Давтян М. А. Москва 2004 оглавление
Новая концепция и современный российский вторичный рынок акций
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconЛобачевский Николай Иванович [20. 11 12). 1792
Родился в семье мелкого чиновника. Почти всю жизнь Лобачевский провел в Казани. Там он учился в Казанском университете (1807-11)....
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДокументы
1. /Автореферат/Автореферат.txt
2. /Автореферат/Аннотация.txt
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДокументы
1. /Диссертация (Козачок)/1/1_1н.doc
2. /Диссертация...

Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconОрганизация практики студентов (часто задаваемые вопросы)
Практика, коротко говоря, участие в работе психолога на каком-то конкретном предприятии. Практика бывает ознакомительная, производственная,...
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconДиссертация на соискание ученой степени кандидата педагогических наук Научный руководитель доктор педагогических наук
...
Диссертация на степень магистра студента 273 «б» группы Подлесных Дмитрия Артуровича Научный доцент iconВнешний оппонент Юрий Иосифович Фрейдин, Мандельштамовское общество
Бут Екатерина Александровна «Композиционные особенности сборника Каллимаха «Ямбы»», научный руководитель – Ольга Леонидовна Ахунова,...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов