Стронгин Р.Г (ред.) Высокопроизводительные параллельные вычисления на кластерных системах

Подождите немного. Документ загружается.

определяется путем чтения (ввода) содержимого регистра РгТП и его

анализа командами процессора.

В логику управления регистрами входят схема анализа

приоритетов (САП) и схема взаимного исключения (СВЗИ). Первая

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

нескольких поступивших, вторая исключает вхождение в критический

интервал запрашивающего процесса, когда в нем

находится текущий

процесс.

Возможен другой вариант построения устройства синхронизации,

когда команда запроса общего ресурса заменяется соответствующим

сигналом, формируемым короткой внутренней командой процессора,

время выполнения которой составит не более одного такта процессора.

Некоторые неудобства реализации состоят в необходимости введения

в процессор двух дополнительных внешних выводов: одного (выход)

для выдачи сигнала запроса общего

ресурса, другого (вход) - для

приема сигнала разрешения на доступ.

Рассмотренные выше способы синхронизации обладают высоким

быстродействием, однако, если в вычислительной системе имеется m

общих ресурсов, обслуживающих n процессов, то при возникновении

любых прерываний потребуется сохранение текущего состояния

регистров РгЗп и РгТП, чтобы иметь возможность корректного

возврата к прерванной программе. Избежать

значительных временных

потерь, связанных с сохранением состояния процесса, возможно, если

в устройство синхронизации включить m регистров запроса и m

регистров РгТП, которые образуют буферную память запросов и

текущих процессов. В этом случае каждая пара регистров РгЗп и РгТП

становится клиентской частью устройства синхронизации, а

единственная схема управления – серверной частью, причем i-

клиентская пара регистров принадлежит i-му общему ресурсу.

В распределённых ВС устройство синхронизации может быть

подключено как периферийное устройство, выполненное на основе

специализированного процессора, называемого процессором

синхронизации. Применение специализированного процессора

вызвано тем, что распределённые ВС используют механизм передачи

сообщений для организации обмена данными между любыми двумя

устройствами. Для реализации этого

механизма и необходим

процессор, осуществляющий функции контроллера для приема –

передачи информации. Одновременно на этот процессор можно

возложить функции синхронизации процессов [1].

В процессе исследований рассмотрены вопросы формального

представления алгоритмов синхронизации взаимодействующих

процессов, действующих в параллельных вычислительных системах,

при их обращении к общему ресурсу. Для формализации

использовалась теория недетерминированных автоматов [6].

Получены уравнения, описывающие процедуры вхождения i-го

процесса в критический интервал и его нахождения там с учетом

принятой дисциплины обеспечения приоритетности и

взаимоисключением несовместных событий, а также выхода процесса

из критического интервала, которые позволяют синтезировать

устройство синхронизации.

Основой для формализации алгоритмов управления

параллельными процессами при решении задач межпроцессного

взаимодействия, в т.ч. и в задаче «обращение к общему ресурсу»,

является формализация функций взаимоисключения критических

участков, т.е. таких участков программы, которые

содержат группу

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

технической литературе такую группу операторов принято называть

примитивами взаимоисключения.

Критический участок следует рассматривать как

последовательность действий, которые выполняются операторами

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

конфликтных ситуаций при взаимодействии параллельных процессов

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

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

1. в любой момент времени только один процесс может

находиться внутри критического интервала

;

2. ни один процесс не может оставаться внутри критического

интервала бесконечно долго;

3. ни один процесс не должен бесконечно долго ждать входа в

критический интервал.

Основой для формального синтеза устройства синхронизации

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

любого i-го процесса в свой критический интервал, которая имеет вид

( ) () () () () ()

iiiii

k вп вз пр k

tttttt

SSSSS

+= ∨1

ni ,1=

где -

сокращенное обозначение события, определяющего вход и

нахождение i-го процесса в своем критическом интервале;

- сокращенное обозначение события, обеспечивающего выход i-

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

обращения к разделяемым данным;

вз

- комбинационное событие, обеспечивающее

взаимоисключение критических интервалов на основе

несовместимости событий

с другими событиями из их общего

числа, равного n (первое требование):

()

[]

,1,

вз

≠αα∀

пр

- сокращенное обозначение события, обеспечивающего

заданное приоритетное обслуживание i-го процесса. В синтезируемом

устройстве использованы циклически изменяющиеся относительные

приоритеты (обеспечение второго требования);

вп

- сокращенное обозначение события, определяющего прием

заявки i-го процесса на обслуживание для обращения к разделяемым

данным. Прием заявок какого-либо процесса на обслуживание

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

находится в своем критическом участке (выполнение третьего

требования). Тем самым исключается повторное обращение к

разделяемым данным для процесса,

имеющего наивысший приоритет,

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

имеющего более низкий приоритет. С учетом этих замечаний,

событие, определяющее прием заявки для i-процесса, будет иметь

следующий вид:

( ) () ()

()

вп з вп

t1 ,

iii

ttt

SSS

+= ∨

где

- сокращенное обозначение события, определяющего заявку i-го

процесса на обслуживание.

Осуществлено моделирование устройства на 4 входа запросов к

общему ресурсу на языке VHDL, а также проведена его

экспериментальная реализация на ПЛИС.

Литература

1. Ганькин А.Л., Сидоров Ю.В., Соловьев Г.Н. Исследования и

разработки в области аппаратной реализации алгоритмов

операционных систем // Зарубежная радиоэлектроника. №2,

1984.

2. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.-

СПб.: БХВ-Петербург, 2002.- 599 с.

3. Программирование на параллельных вычислительных

системах / Под ред. Р. Боба II [перевод с англ.]. – М.: Мир,

1991.- 372 с.

4. Хоар Ч. Взаимодействующие последовательные процессы. -

М.: Мир, 1989 264 с.

5. Таненбаум Э. Современные операционные системы. 2-

е изд. –

СПб: Питер, 2004.

6. Вашкевич Н.П. Недетерминированные автоматы в

проектировании систем параллельной обработки.

Учеб. пособие. - Пенза: Изд-во Пенз. гос.ун-та, 2004. - 280 с.

АВТОМАТНАЯ МОДЕЛЬ СЕТЕВОГО ПРОТОКОЛА

ТРАНЗАКЦИЙ С ДВУХФАЗНОЙ ФИКСАЦИЕЙ 2PC

(TWO-PHASE COMMIT)

Н.П. Вашкевич, Е.И. Калиниченко, И. Диянов

Пензенский государственный университет

Введение

В настоящее время широкое распространение

получили

распределенные системы управления базами данных (СУБД). Для

поддержания согласованного состояния баз данных в узлах

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

транзакций. Одним из наиболее распространенных является протокол

транзакций с двухфазной фиксацией (Two Phase Commit - 2PC). В

рамках проводимой научно-исследовательской работы по созданию

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

реализована модель этого протокола. При

создании модели

использовалась теория недетерминированных конечных автоматов [1].

Транзакция с двухфазной фиксацией - это транзакция, которая

обновляет, добавляет или удаляет информацию в базе данных не на

одном, а на нескольких серверах, распределенных в разных

географических местах. Транзакция обычно разделяется на части, и

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

завершения второй.

Сервер-инициатор выступает в качестве

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

Менеджер транзакций управляет транзакциями, которые

обрабатываются несколькими менеджерами ресурсов. Когда

приложение запрашивает у менеджера транзакций, завершена ли

транзакция, менеджер транзакций инициирует протокол двухфазной

фиксации. Выполнение этого протокола начинается с того, что

менеджер транзакций запрашивает каждый менеджер ресурсов о

готовности завершить транзакцию. Когда различным

менеджерам

ресурсов послан запрос о готовности к завершению транзакции, они

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

транзакции в случае ее прерывания. Если какой-то из серверов не

готов к завершению транзакции, он посылает соответствующее

сообщение назад менеджеру транзакций и транзакция прерывается.

Если же все серверы заявляют о своей готовности к

завершению

транзакции, они ждут решения менеджера транзакций - завершать или

прерывать транзакцию. Менеджер транзакций принимает решение

завершить транзакцию и приказывает менеджерам ресурсов

осуществить этот процесс. После чего менеджер транзакций ожидает

сообщения от каждого сервера об успешном или неуспешном ее

завершении, так как не знает, все ли менеджеры ресурсов завершили

транзакцию. На

период, пока менеджер транзакций не уверен в

завершении транзакции, для данных, которые должны быть

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

данных. Она гарантирует, что транзакция останется изолированной от

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

изменить эти данные. Менеджер транзакций должен следить за

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

произошел сбой

менеджера ресурсов, менеджер транзакций

поддерживает журнал всех транзакций, которыми он управляет. Этот

журнал может быть использован для восстановления неудачной

попытки одного из менеджеров ресурсов завершить транзакцию в

случае какого-либо сбоя. Таким образом, транзакция, завершенная

менеджером транзакций, может быть завершена всеми менеджерами

ресурсов, или все они произведут откат этой транзакции.

Описание алгоритма работы протокола на языке UML приведено

на рис.1.

Менеджер транзакций Менеджер ресурсов1 Менеджер ресурсов 2 Менеджер ресурсов3

Запрос о готовности завершить транзакцию

Готовность к завершению транзакции

Зав ершение транзакции

Подтверждение завершения транзакции

Рис. 1

Модель

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

состоящей из узлов (серверов баз данных) и каналов связи (тип канала

связи не имеет значения) между ними. Функционирование каждого

узла и канала описывается недетерминированным конечным

автоматом, что позволяет неявно учитывать поведение каждого из них

во времени. Чтобы учитывать согласованное поведение узлов и

каналов во

времени в составе системы, в модель введены как линейные

автоматы времени для каждого узла и канала, так и линейный автомат

времени, описывающий общее системное время. Таким образом,

модель распределенной системы представляет собой систему

недетерминированных автоматов. Учет быстродействия узла в модели

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

на входное событие.

Задержка распространения сигнала в канале

реализована в виде очереди сообщений таким образом, что

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

время задержки канала. Отказ работы узлов можно инициировать

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

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

полностью отключить узел

. В обоих случаях узел не реагирует на

входные сигналы, но во втором случае при отключении узла

обнуляется его текущее состояние, а при включении работа узла

начинается с нулевого состояния. Отказ работы канала можно

инициировать его отключением, причем поступающие на вход канала

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

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

настроек.

Формализация алгоритма работы протокола

Для формального описания алгоритма работы использовалась

система канонических уравнений [1], описывающая поведение

каждого сервера (узла распределенной системы) в качестве менеджера

транзакции или менеджера ресурсов. Причем каждый узел может

функционировать как в качестве менеджера транзакции, так и в

качестве менеджера ресурсов.

S0=x_pusk V S4 V S7 V (S5&!x3&!x4) V (x5&S3) V (S0&!x1&!x_per);

S1=(S0&!x1&x_per) V (S1&!x2&!x4&!x_sch);

S2=(S0&x1&x_pri) V (S2 V S6)&!x3&!x4&!x_sch&x1;

S3=S1&x2 V S3&!x5&!x4;

S4=(S0&x1&!x_pri) V ((S2 V S6)&!x3&!x4&x_sch) V

V (S1&!x2&(x4 V !x4&x_sch)) V (!x5&S3&x4);

S5=(S2&x3) V (S6&x3) V (S5&x3);

S6=(S2&!x3&!x4&!x_sch&!x1) V (S6&!x3&!x4&!x_sch&!x1);

S7=((S2 V S6)&!x3&x4) V (S5&!x3&x4).

В системе канонических уравнений введены следующие

обозначения:

 S0 – начальное состояние хоста, перед началом каких-либо

действий;

 S1 – посылка запроса о готовности завершения транзакции,

первый этап;

 S2 – посылка сообщения о готовности завершить транзакцию;

 S3 – посылка сообщения о завершении транзакции, второй

этап;

 S4 – посылка сообщения об отмене транзакции;

 S5 – посылка

подтверждения завершения транзакции;

 S6 – ожидание второго этапа завершения транзакции;

 S7 – откат транзакции;

 x1 – запрос о готовности завершения транзакции;

 x2 – сообщение о готовности завершить транзакцию;

 x3 – сообщение о завершении транзакции;

 x4 – сообщение об отмене транзакции;

 x5 – подтверждение завершения транзакции;

 x_pusk – сигнал, запускающий работу алгоритма;

 x_pri – сигнал, определяющий

готовность хоста к завершению

транзакции;

 x_per – сигнал, определяющий возможность хоста стать

инициатором завершения транзакции;

 x_sch – сигнал, определяющий превышение времени

ожидания ответа определенного тайм-аута.

Программная реализация модели

При программной реализации модели использовались следующие

ограничения, необходимые для корректного описания ''реактивных''

систем:

 состояния хостов разбиваются на два подсостояния. На

первом этапе просчитываются промежуточные состояния с

учетом входных сигналов и предыдущего состояния хоста. На

втором этапе промежуточные состояния, полученные на

первом этапе, переписываются в переменные, определяющие

состояние хоста и используемые при просчете системы

канонических уравнений в следующий такт работы хоста;

 состояния каналов просчитываются каждый такт системного

времени, что позволило обрабатывать входные сигналы в

каждый такт, а

выходные сигналы получаются на такт

системного времени, равный такту поступления сигнала в

канал увеличенного на время задержки канала. Выходные

сигналы непосредственно в канале не сохраняются и

действуют только в такт их появления на выходе канала;

 каждый канал разбит на два подканала, описывающих

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

наоборот, таким

образом реализован принцип дуплексной передачи

информации;

 введен автомат, реализующий просчет входных сигналов для

хоста, что позволило связать выходные сигналы каналов и

входные сигналы хостов. В данном автомате также реализован

принцип псевдослучайной выборки выходных сигналов

каналов, который применяется в случае прихода сигнала от

нескольких хостов одновременно. Благодаря этому принципу

обрабатывается только один сигнал, а остальные сигналы

сохраняются в буфер и обрабатываются хостом в следующий

такт работы;

 введен автомат, определяющий готовность хоста к приему или

передаче информации;

 введен автомат, определяющий время ожидания ответа

хостом.

Выводы по результатам моделирования

Результатом работы программы является таблица, каждый столбец

которой содержит состояния канала или хоста. Каждой строке таблицы

соответствует состояние канала или хоста в определенный момент

системного времени (рис. 2).

Рис. 2

Моделирование показало сильные и слабые стороны протокола

двойной фиксации транзакций. Протокол обеспечивает корректное

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

распределенной базы данных. Единственным слабым местом в работе

протокола является вторая стадия фиксации транзакции, когда

менеджер транзакций ожидает ответа от всех менеджеров ресурсов.

Если во время второй стадии один из хостов

или каналов выйдет из

строя, то менеджер ресурсов ''зависает'' на неопределенное время, тем

самым транзакция остается в неопределенном состоянии.

Литература

1. Н.П. Вашкевич, С.Н. Вашкевич. Недетерминированные

автоматы и их использование для синтеза систем управления".

Учебное пособие, Изд-во ПГТУ, Пенза: 1996.

ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ОБУЧЕНИЯ

МАШИН ОПОРНЫХ ВЕКТОРОВ

Р.А. Веснин, Т.А. Стародубова

Вятский государственный гуманитарный университет

В настоящее время актуальной является задача классификации

данных, формальная постановка которой выглядит следующим

образом. Имеются:

 подмножество евклидова пространства Х – обучающие

объекты, заданные векторами признаков: X={X

, X

, ..., X

⊂

;

 множество Y ответов для обучающих объектов,

принадлежащих одному из двух классов: Y={y

, y

, ..., y

∈

{–1, +1}.

Необходимо построить оптимальное классифицирующее правило

(функцию) вида f: Х → Y, которое правильно классифицирует все

обучающие объекты пространства Х, то есть для любого вектора X

(i=1..N) находит соответствующий ответ Y

Одним из эффективных методов, применяемых для классификации

текстов, является метод опорных векторов (SVM – Support Vector

Machines), предложенный В. Н. Вапником [1]. В последнее время этот

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

ряде задач анализа изображений, регрессии, идентификации и др.

В SVM в качестве функции f выбрана плоскость, расстояния до

которой ближайших векторов обоих классов

равны (рис. 1).

Ближайшие точки-векторы называются опорными. При этом для всех

объектов одного класса должно выполняться неравенство f(X

)>0, а для

всех объектов другого класса – неравенство f(X

)<0.