РАЗДЕЛ 2
АНАЛИЗ ЭФФЕКТИВНОСТИ КЛАСТЕРНЫХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНЫХ МОДЕЛЕЙ МАРКОВА
Одним из примеров вычислительных систем с распределенной обработкой являются кластеры. Они обладают высокой производительностью и "живучестью" вычислительных ресурсов. Классификация кластерных систем по cовместному использованию одних и тех же дисков отдельными узлами является самой распространенной [57,59,60]. Одной из основных проблем при построении ВС с распределенной обработкой является выработка рекомендации для рационального использования ресурсов этой сети. Эта задача возникает как при эксплуатации, так и при проектировании сети. Для эффективной эксплуатации кластерной системы необходимо построить её аналитическую модель и для каждого класса решаемых задач определить основные параметры вычислительной среды. Эти модели можно использовать и для оптимизации ВС на стадии проектирования.
2.1 Дискретная модель функционирования однородной кластерной системы
В модели с разделяемыми дисками каждый узел в кластере имеет свою собственную память, все узлы совместно используют дисковую подсистему. Такие узлы связаны высокоскоростным соединением для того, чтобы передавать регулярные контрольные сообщения. При отсутствии таких сообщений определяются неисправности в вычислительной системе. Узлы в кластере обращаются к дисковой подсистеме по системной шине.
2.1.1 Модель однородного кластера с совместным использованием дискового пространства
Одна из разновидностей кластера с совместным использованием дискового пространства представлена на рис. 2.1. Такие топологии используют СУБД Oracle Parallel Server и Informix [60].
Упрощенная модель кластера с совместным использованием дискового пространства приведена на рис. 2.2. Входной узел (управляющий сервер) равномерно распределяет между серверами приложений (выполняющими одинаковые приложения) задачи. Количество серверов - приложений - N1. Каждый из них может обратиться к данным, расположенным на дисках, количество которых N2. Ввиду ограниченных вычислительных возможностей будем считать, что количество задач, обрабатываемое такой вычислительной системой не более М.
Построим дискретную марковскую модель. Так как кластер однородный, представим серверы, и, аналогично, дисковые накопители многоканальными устройствами. Требования, поступающие на обслуживание на серверы, поступают в ограниченную очередь (не более М), из которой на обслуживание выбираются по правилу "первый пришел - первый обслужился".
Допустим, задачи, обрабатываемые на таком кластере, однородные и имеют следующие характеристики:
p12 - вероятность запроса к одному из N1 серверов,
p23 - вероятность запроса к одному из N2 дисков,
p21 - вероятность завершения обслуживания одним из N1 серверов,
p10 - вероятность завершения обслуживания задачи,
q0 - вероятность появления новой задачи.
Для вычислительных ресурсов примем, что длительности времен обслуживания заявок на входном узле, сервере приложений или дисковом массиве, соответственно, имеют геометрическое распределение со средним, равным Ti, (). Тогда
qi - вероятность завершения обслуживания задачи на входном узле, сервере приложений или дисковом массиве, соответственно, (),
ri - вероятность продолжения обслуживания задачи на входном узле, сервере приложений или дисковом массиве, соответственно, (), ri=1-qi.
Рис. 2.1. Архитектура кластера с совместным использованием дискового пространства
Рис.2.2. Структурная схема марковской модели кластера с совместным использованием дискового пространства
Для построения дискретной модели вычислительной системы, приведенной на рис.2.1 используем методику, описанную в [97].
За состояние системы примем размещение М заявок по трем узлам , где - количество задач в -ом узле. Определим все возможные состояния. Обозначим множество состояний через |}. Число состояний системы для одного и того же количества задач j= равно числу размещений j задач по N узлам и определяется по формуле , общее количество состояний вычисляется так:
. (2.1)
Вектор определяет количество устройств в каждом узле ВС. Определим переходные вероятности для каждой пары состояний , т.е. вероятности перехода из состояния Si, в котором она находилась на (l-1)-м шаге, в состояние Sj на l-м шаге. Определим матрицу переходных вероятностей .
Рассмотрим переход из произвольного состояния в состояние . В состоянии обрабатывается задач, а в состоянии - . Так как за один такт может поступить на обработку в ВС или покинуть ее одна задача, то разница должна удовлетворять условию
. (2.2)
Введем вектор , s-я компонента которого определяет число
(2.3)
загруженных устройств в s-м узле.
Вычислим вектор
(2.4)
каждая компонента которого представляет изменение числа задач в s-ом узле. Если >0, то на рассматриваемом переходе из узла s должны уйти минимум задач. Если < 0, то в узел s должны прийти || задач. При любом переходе из число задач, обслуженных s-м узлом обработки, не может быть больше ?s, т.е.
(2.5)
Определим множество J номеров узлов обработки, в которых < 0, т.е.
(2.6)
Если , то величиныопределяют минимально воз-можное число программ, которые поступают к тем узлам обработки, номера s которых принадлежат множеству J. Число программ, поступивших в один из таких узлов s равно . Количество поступивших задач к управляющему серверу от серверов-приложений не может превышать количества работающих серверов (за исключением случая, когда появляется новая задача или покидает ВС обслуженная задача, о чем свидетельствует символ ), т.е.
,