Механизм семафоров

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

Функция создания объекта типа семафор:

HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpSemaphoreAttributes, LONG lInitialCount, LONG lMaximumCount, LPCTSTR lpName);

Параметры:

lpSemaphoreAttributes - указатель на структуру SECURITY_ATTRIBUTES, который определяет, может ли возвращаемый дескриптор наследоваться порожденными процессами. Если NULL, то дескриптор не может наследоваться.

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

lMaximumCount - определяет максимальное значение семафора;

lpName - указывает на строку, определяющую имя семафора, если NULL, то семафор открывается без имени.

Функция возврата дескриптора существующего именованного семафора:

HANDLE OpenSemaphore(

DWORD dwDesiredAccess, // access flag

BOOL bInheritHandle, // inherit flag

LPCTSTR lpName // pointer to semaphore-object name

);

Функция увеличения счетчика семафора на заданное число:

BOOL ReleaseSemaphore(HANDLE hSemaphore, LONG lReleaseCount,LPLONG lpPreviousCount);

Параметры:

hSemaphore - дескриптор семафора;

lReleaseCount - определяет, на сколько увеличивать счетчик семафора;

lpPreviousCount - указатель на 32-битную переменную с предыдущим значением счетчика (NULL, если предыдущее значение не требуется).

Функция WaitForSingleObject определяет, свободен ли семафор, и если он свободен, то уменьшает значение счетчика семафора на 1, в противном случае поток будет приостановлен, пока семафор не освободится.

Посмотрим, как выглядит пример c критическими разделами, если переписать его, используя классические семафоры (см. листинг 3).

Листинг 3. Ограничение доступа к массиву с использованием классических семафоров

// Массив значений.

int mas[1000];

// Семафор, регулирующий доступ к критическому разделу.

HANDLE Semaph;

{

...

// Создаем семафор;

Semaph = CreateSemaphore(NULL, 1, 1, NULL);

// Запускаем потоки

CreateThread(NULL,0,thread1,NULL,0,NULL);

CreateThread(NULL,0,thread2,NULL,0,NULL);

... // Текст программы.

// Удаляем семафор

CloseHandle(Semaph);

}

// Первый поток: запись в массив данных.

DWORD WINAPI thread1(LPVOID par)

{ // Запись значения в массив.

// Запрос на вход в критический раздел.

WaitForSingleObject(Semaph, INFINITE);

// Выполнение кода в критическом разделе.

for(int i = 0;i<1000;i++)

{

mas[i] = i;

}

// Выход из критического раздела:

// освобождаем семафор для доступа

// других задач к критическому разделу

ReleaseSemaphore(Semaph, 1, NULL);

// завершаем поток

return 0;

}

// Второй поток: считывание данных из массива.

DWORD WINAPI thread2(LPVOID par)

{ // Считывание значений из массива.

int j;

// Запрос на вход в критический раздел.

WaitForSingleObject(Semaph, INFINITE);

// Выполнение кода в критическом разделе.

for(int i = 0;i<1000;i++)

{

j = mas[i];

}

// Выход из критического раздела:

// освобождаем семафор для доступа

// других задач к критическому разделу

ReleaseSemaphore(Semaph, 1, NULL);

// завершаем поток

return 0;

}

Реализация многозадачности и многопоточности в UNIX.

Средства управления процессами

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

Функции execl,execv позволяют заменить текущий процесс новым.

Функция waitpid позволяет ожидать окончания порожденного процесса

Функция kill посылает сигнал процессу

Функция signal позволяет указать функцию, выполняющуся при получении сигнала.

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

Для реализации многопоточности используется библиотека PTHREAD.

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

Для условной синхронизации в библиотеке PTHREAD имеются условные переменные (condvar). С условной переменной связана очередь потоков, ожидающих ее освобождения. Поток может проверить, пуста ли очередт (empty), встать в очередь (wait), запустить первый поток из очереди (signal).

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

Параллельные алгоритмы.

Для обычных алгоритмов важное понятие – выч. Сложность. Для пар. Алгоритмов вводится понятие коэффициент ускорения (насколько ПА быстрее оптимвльного обычного). Например для сорт О(nlogn). Если пар алгоритм имеет сложность O(n) то КУ будет O(log n).

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

Еще одно понятие – расщепляемость задачи (на сколько процессоров ее можно разбить). Нас будут интересовать алгоритмы, в которых число процессоров значительно менше объема входных данных и не требует увеличения при росте их объема.

Макконелл. Основы современных алгоритмов.

Распределенные вычисления.

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

Как правило, программирование для сетевых кластеров отличается от привычной модели программирования для многозадачных систем, построенных на базе одного или множества процессоров. Часто в таких системах необходимо обеспечить только синхронизацию процессов, и нет нужды задумываться об особых способах обмена информацией между ними, т.к. данные обычно располагаются в общей разделяемой памяти. В сети реализация такого механизма затруднительно из-за высоких накладных расходов, связанных с необходимостью предоставлять каждому процессу копию одной и той же разделяемой памяти для работы. Поэтому, обычно, при программировании для сетевых кластеров используется SPMD-технология [8] (Single Program – Multiple Data, одна программа – множественные данные). Идея SPMD в том, чтобы поделить большой массив информации между одинаковыми процессами, которые будут вести обработку своей части данных (рис. 1).

Рис. 1. Схема взаимодействия частей SPMD-программы.

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

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

Разработано несколько механизмов распределенного программирования. Они отличаются способами использования каналов и синхронизации взаимодействия. Каналы бывают однонаправленными и двунаправленными, обеспечивают асинхронную (неблокирующую) и синхронную передачу сообщений. Более высокоуровневые механизмы – удаленный вызов процедур и рандеву.

Простейший способ взаимодействия процессов в распределенных системах – асинхронная передача сообщений.

Канал – очередь сообщений, которые уже отправлены, но еще не получены.

Допустима операция send channel (x), ставящая x в очередь на отправку в канал channel. Очередь теоретически не ограничена, поэтому операция send не вызывает задержку и является неблокирующей.

Для получения сообщения используется операция receive channel (x). Процесс приостанавливается и ожидает, пока в очереди канала не появится сообщение.

Поскольку канал является очередью FIFO, то сообщения принимаются в порядке передачи.

Каналы глобальны относительно процессов и могут использоваться в любом процессе.

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

Процесс Merge циклически сравнивает числа, полученные из потоков in1 и in2 и отправляет в out меньшее из них.

Procedure Merge

begin

receive(in1, v1);

receive(in2, v2);

while (v1<> eof) and (v2<>eof) do

if v1<= v2 then begin send(out, v1); receive(in1, v1); end

else begin send(out, v2); receive(in2, v2); end;

if (v1 = eof)

while (v2<> eof) do begin send(out, v2); receive(in2, v2); end

else begin send(out, v1); receive(in1, v1); end

send(out,eof)

n-1 процессов слияния соединяются так, чтобы образовывать дерево.

V1 \ Merge\

V2 / \

\

Merge

/

Vn-1\ Merge/

Vn /

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

Недостаток синхронного обмена сообщениями – высокая вероятность взаимных блокировок.

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

Более удобно использовать механизмы взаимодействия – удаленный вызов процедуры и рандеву.

Клиент вызывает удаленную процедуру на сервере и ждет, пока она не вернет результаты.

RPC и рандеву отличаются способом обслуживания вызовов операций. RPC для каждой операции требует объявления процедуры и для обработки вызова создает новый процесс. Рандеву обеспечивает взаимодействие с уже существующим процессом. Процесс-сервер ждет вызова с помощью операции приема, обрабатывает вызов и возвращает результаты.

Пример RPC – технология COM. COM- объекты содержат методы, которые удаленно вызываются.

Недостаток RPC – отсутствует непосредственное взаимодействие процессов. Для его реализации нужно использовать семафорные механизмы синхронизации.

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

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

Интерфейс MPI (Message Parsing Interface) – фактически стандарт распределенного программирования. MPI – библиотека функций, реализованных для разных языков программирования (С/С++, Fortran, Delphi,…)

Имена функций начинаются с MPI_ и описаны в mpi.h.

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

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

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

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

Каждый MPI-процесс в пределах SPMD-программы уникально идентифицируется своим номером. Допускается объединять процессы в группы, которые могут быть вложенными. Внутри каждой группы все процессы перенумерованы, начиная с нуля. С каждой группой ассоциирован свой коммуникатор (уникальный идентификатор). Поэтому при осуществлении пересылки данных необходимо указать наряду с номером процесса и идентификатор группы, внутри которой производится эта пересылка. Все процессы изначально содержатся в группе с предопределенным идентификатором MPI_COMM_WORLD, который заводится для каждой запускаемой SPMD-программы (рис. 2). Разные SPMD-программы не знаю о существовании друг друга и обмен данными между ними невозможен.

Рис 2. Нумерация процессов и коммуникаторы в MPI

Рассмотрим основные функции библиотеки. Все они возвращают целое значение, которое либо равно константе MPI_SUCCESS, либо содержит код произошедшей ошибки.

Перед тем, как программа сможет работать с функциями библиотеки необходимо инициализировать MPI с помощью функции:

int MPI_Init(int *argc, char ***argv)

В качестве аргументов этой функции передаются параметры командной строки, поступающие в функцию main().

Если процессу MPI необходимо узнать свой порядковый номер в группе, то используется функция:

int MPI_Comm_rank (MPI_Comm, int *rank)

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

Чтобы узнать размер группы (количество процессов в ней) необходимо применить функцию:

int MPI_Comm_size (MPI_Comm, int *ranksize)

Для окончания работы с MPI необходимо использовать функцию:

int MPI_Finalize()

Перед тем, как начать рассмотрение функций передачи/приема сообщений, отметим, какие основные типы данных поддерживает MPI (таблица 1).

Таблица 1. Соответствие типов в MPI и языке Cи

Тип MPI	Тип Cи
MPI_CHAR	char
MPI_BYTE	unsigned char
MPI_SHORT	short
MPI_INT	int
MPI_LONG	long
MPI_FLOAT	float
MPI_DOUBLE	double
MPI_UNSIGNED_CHAR	unsigned char
MPI_UNSIGNED_SHORT	unsigned short
MPI_UNSIGNED	unsigned int
MPI_UNSIGNED_LONG	unsigned long
MPI_LONG_DOUBLE	long double

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

Рассмотрим эти функции подробнее.

int MPI_Send(void* buf, int count,
MPI_Datatype datatype, int dest,
int msgtag, MPI_Comm comm)

Функция выполняет блокирующую посылку сообщения с идентификатором msgtag (идентификатор выбирается самостоятельно программистом!), состоящего из count элементов типа datatype, процессу с номером dest и коммуникатором comm. Все элементы сообщения расположены подряд в буфере buf. Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа (таблица 1). Разрешается передавать сообщение самому себе.

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

int MPI_Recv(void* buf, int count,
MPI_Datatype datatype, int source,
int msgtag, MPI_Comm comm,
MPI_Status *status)

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

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

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

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

Параметр status содержит служебную информацию о ходе приема, которая может быть использована в программе. status является структурой и содержит поля: MPI_SOURCE, MPI_TAG и MPI_ERROR (источник сообщения, идентификатор сообщения и возникшая ошибка, соответственно).

int MPI_Isend(void *buf, int count,
MPI_Datatype datatype, int dest,
int msgtag, MPI_Comm comm,
MPI_Request *request)

Передача сообщения, аналогичная MPI_Send, однако, возврат из подпрограммы происходит сразу после инициализации процесса передачи без ожидания обработки всего сообщения, находящегося в буфере buf. Это означает, что нельзя повторно использовать данный буфер для других целей без получения дополнительной информации о завершении данной посылки. Окончание процесса передачи (т.е. тот момент, когда можно вновь использовать буфер buf без опасения испортить передаваемое сообщение) можно определить с помощью параметра request (идентификатор асинхронной операции определенного в MPI типа MPI_Request) и процедур MPI_Wait и MPI_Test, которые будут рассмотрены ниже.

Сообщение, отправленное любой из процедур MPI_Send и MPI_Isend, может быть принято как функцией MPI_Recv, так и MPI_Irecv.

int MPI_Irecv(void *buf, int count,
MPI_Datatype datatype, int source,
int msgtag, MPI_Comm comm,
MPI_Request *request)

Прием сообщения, аналогичный MPI_Recv, однако возврат из подпрограммы происходит сразу после инициализации процесса приема без ожидания получения сообщения в буфере buf. Окончание процесса приема можно определить с помощью параметра request и процедур MPI_Wait и MPI_Test.

int MPI_Wait(MPI_Request *request, MPI_Status *status)

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

int MPI_Test(MPI_Request *request, int *flag,
MPI_Status *status)

Проверка завершенности асинхронных процедур MPI_Isend или MPI_Irecv, ассоциированных с идентификатором request. В параметре flag возвращает значение 1, если соответствующая операция завершена, и значение 0 в противном случае. Если завершена процедура приема, параметры сообщения оказываются в status. MPI_Test не блокирует программу до окончания соответствующих операций приема/передачи, чем и отличается от MPI_Wait.

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

int MPI_Bcast(void *buf, int count,
MPI_Datatype datatype, int source,
MPI_Comm comm)

Рассылка сообщения от процесса source всем процессам, включая рассылающий процесс. При возврате из процедуры содержимое буфера buf процесса source будет скопировано в локальный буфер процесса. Значения параметров count, datatype и source должны быть одинаковыми у всех процессов.

int MPI_Gather(void *sbuf, int scount,
MPI_Datatype stype, void *rbuf,
int rcount, MPI_Datatype rtype,
int dest, MPI_Comm comm)

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

int MPI_Scatter(void *sbuf, int scount,
MPI_Datatype stype, void *rbuf,
int rcount, MPI_Datatype rtype,
int source, MPI_Comm comm)

Обратная к MPI_Gather функция. Процесс source рассылает порции данных из массива sbuf всем процессам группы, на которую указывает коммуникатор comm. Можно считать, что массив sbuf делится на n равных частей, состоящих из scount элементов типа stype, после чего i-я часть посылается i-му процессу. На процессе source существенным являются значений всех параметров, а на остальных процессах – только значения параметров rbuf, rcount, rtype, source и comm. Значения параметров source и comm должны быть одинаковыми у всех процессов.

Синхронизация MPI-процессов может быть выполнена с использованием блокирующих процедур приема/посылки сообщений или посредством функции, реализующей барьерную синхронизацию:

int MPI_Barrier(MPI_Comm comm)

MPI_Barrier блокирует работу процессов, вызвавших данную процедуру, до тех пор, пока все оставшиеся процессы группы comm также не выполнят эту процедуру.

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

Язык Occam. Разработан в середине 80-х годов для программирования транспьютеров – многопроцессорных систем, образующих двумерную решетку (каждый процессор связан с четырьмя другими).

Базовые операции языка –

• Присваивание пер:= выражение
• ввод (запросить) канал? переменная
• вывод (выдать) канал! выражение

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

Конструктор SEQ применяется для последовательного выполнения и PAR для параллельного. Есть конструкторы IF, CASE, WHILE.

INT x,y:

SEQ //PAR

x:=x+1

y:=y+1

CHANN OF BYTE comm.:

PAR

WHILE TRUE

BYTE ch:

SEQ

keyboard? ch

comm! ch

WHILE TRUE

BYTE ch:

SEQ

comm? ch

display! ch

Существует механизм условной блокировки ALT

Язык Java (Sun 1995 г). Java поддерживает потоки (класс Thread), разделяемые переменные, синхронизированные методы (выполняющиеся со взаимным исключением)

Библиотека Java поддерживает обмен сообщениями с помощью сокетов. Java поддерживает удаленный вызов методов RMI

Язык ADA. Разработан по заказу министерства обороны США в конце 70-х годов.

В языке есть понятие задача – независимый процесс внутри одной программы.

Для синхронизации используется механизм рандеву. Из одной задачи вызывается точка входа в другой задаче call T.E (аргументы)

Задача T обслуживает вызовы точки Е с помощью оператора accept

accept E(параметры) do

операторы

end;