Реферат: Операционные системы распределенных вычислительных систем (распределенные ос)

/

Операционные системы распределенных вычислительных систем (распределенные ОС).

(Крюков В.А.)

Распределенная система - совокупность независимых компьютеров, которая представляется пользователю единым компьютером (metacomputer), использование которого не намного сложнее, чем использование персональной ЭВМ.


Введение в ОС однопроцессорных ЭВМ.

Два взгляда:

менеджер ресурсов;

один слой в множестве слоев абстрактных машин.


Представление ОС как менеджера ресурсов


Управление процессами

Управление файлами

Управление процессорами

Управление памятью

Управление устройствами

Процессоры

Память

Устройства


^ Представление ОС как абстрактной машины

Абстрактная машина

Интерфейс пользователя

Интерфейс программы

Языки управления заданиями Командные языки
Окна, меню, пиктограммы

Система команд

Системные вызовы
Процессы Память Файлы
Информационные функции


Место ОС среди ПО

Прикладное ПО
(отдельные приложения, пакеты прикладных программ, информационные системы, САПР)

Системное ПО
(ОС + системы программирования, СУБД, графические библиотеки, сервисные программы)



^ История ОС.

1940-е и 1950-е

"Персональные ЭВМ" - "пультовый режим"

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

Середина 1950-х

Пакетная обработка. Однопрограммный и мультипрограммный режимы.

Инструкция оператору -> паспорт задачи (простейший язык управления заданиями).

Требования к аппаратуре:

защита памяти;

прерывания;

привилегированный режим;

таймер.

Как обеспечить мультипрограммный режим без таких механизмов.

Середина 1960-х

Режим разделения времени.

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

^ 1970-е

Многопроцессорные ЭВМ, многомашинные комплексы, сети ЭВМ

1980-е

Персональные ЭВМ

1990-е

MPP, открытые системы, Internet

*********Лекция 2

1 Введение в параллельные и распределенные системы

1.1 Достоинства многопроцессорных систем с общей памятью (мультипроцессоров)

(1) Производительность

(2) Надежность

1.2. Недостатки

(1) ПО (приложения, языки, ОС) сложнее, чем для однопроцессорных ЭВМ

(2) Ограниченность при наращивании (физ. размеры - близость к памяти, 64 процессора - максимально достигнутое).


^ 1.2 Достоинства распределенных систем

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

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


^ Почему создаются распределенные системы? В чем их преимущества перед централизованными ЭВМ?

1-ая причина - экономическая.

Закон Гроша (Herb Grosh)- быстродействие процессора пропорциональна квадрату его стоимости. С появлением микропроцессоров закон перестал действовать - за двойную цену можно получить тот же процессор с несколько большей частотой.

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

3-я причина - естественная распределенность (банк, поддержка совместной работы группы пользователей ).

^ 4-ая причина - надежность (выход из строя нескольких узлов незначительно снизит производительность).

5-я причина - наращиваемость производительности.


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


Почему нужно объединять PC в сети?

1. Необходимость разделять данные.

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

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

4. Гибкость использования различных ЭВМ, распределение нагрузки.

5. Упрощение постепенной модернизации посредством замены компъютеров.


Недостатки распределенных систем:

1. Проблемы ПО (приложения, языки , ОС).

2. Проблемы коммуникационной сети (потери информации, перегрузка, развитие и замена).

3. Секретность.


^ 1.3 Виды операционных систем (сетевые ОС, распределенные ОС, ОС мультипроцессоров).


Сетевые ОС - машины обладают высокой степенью автономности, общесистемных требований мало. Можно вести диалог с другой ЭВМ, вводить задания в ее очередь пакетных заданий, иметь доступ к удаленным файлам, хотя иерархия директорий может быть разной для разных клиентов. Пример - серверы файлов (многие WS могут не иметь дисков вообще).

Распределенные ОС - единый глобальный межпроцессный коммуникационный механизм, глобальная схема контроля доступа, одинаковое видение файловой системы. Вообще - иллюзия единой ЭВМ.

^ ОС мультипроцессоров - единая очередь процессов, ожидающих выполнения, одна файловая система.




Сетевая ОС

Распределенная ОС

ОС мульти
процессора

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

НЕТ

ДА

ДА

Одна и та же ОС выполняется на всех процессорах

НЕТ

ДА

ДА

Сколько копий ОС имеется в памяти

N

N

1

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

НЕТ

НЕТ

ДА

Имеется хорошо определенная семантика разделения файлов

Обычно НЕТ

ДА

ДА



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

(1) Прозрачность (для пользователя и программы).

Прозрачность расположения

Пользователь не должен знать, где расположены ресурсы

Прозрачность миграции

Ресурсы могут перемещаться без изменения их имен

Прозрачность размножения

Пользователь не должен знать,

сколько копий существует

Прозрачность конкуренции

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

Прозрачность параллелизма

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


(2) Гибкость (не все еще ясно - потребуется менять решения).

Использование монолитного ядра ОС или микроядра.

(3) Надежность.

Доступность, устойчивость к ошибкам (fault tolerance).

Секретность.

(4) Производительность.

Грануллированность. Мелкозернистый и крупнозернистый параллелизм (fine-grained parallelism, coarse-grained parallelism).

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

(5) Масштабируемость.

Плохие решения:

централизованные компоненты (один почтовый-сервер);

централизованные таблицы (один телефонный справочник);

централизованные алгоритмы (маршрутизатор на основе полной информации).

Только децентрализованные алгоритмы со следующими чертами:

ни одна машина не имеет полной информации о состоянии системы;

машины принимают решения на основе только локальной информации;

выход из строя одной машины не должен приводить к отказу алгоритма;

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


Литература


1. DISTRIBUTED OPERATING SYSTEMS. Andrew S. Tanenbaum, Prentice-Hall, Inc., 1995


2. ADVANCED CONCEPTS IN OPERATING SYSTEMS. Mukesh Singhal, Niranjan G. Shivaratri, McGraw-Hill, Inc., 1994


3. CENTRALIZED AND DISTRIBUTED OPERATING SYSTEMS. Gary J. Nutt, Prentice-Hall, Inc., 1992


4. David W. Walker, "The design of a standard message-passing interface for distributed memory concurrent computers", Parallel Computing, v.20, n 4, April 1994, 657-673. (www.mpi-forum.org)


5. A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam, “PVM 3 User’s Guide and Reference Manual”, Technical report, Oak Ridge National Laboratory ORNL/TM-12187 (1993).


6. Таненбаум Э., Стен М. ван. Распределенные системы. Принципы и парадигмы. –СПб.: Питер, 2003. (ISBN 5-272-00053-6, страниц: 877).


Вопрос:


Какие аппаратные механизмы необходимы для организации мультипрограммного режима? Как обеспечить мультипрограммный режим без этих механизмов? Как обеспечить, если отсутствует только один из этих механизмов?
Лекция 3
2 Операционные системы мультипроцессорных ЭВМ

Организация ОС:

главный-подчиненный (master-slave, выделение одного процессора для ОС упрощает ее, но этот процессор становится узким местом с точки зрения загруженности и надежности);

симметричная (наиболее эффективная и сложная).
^ 2.1 Процессы и нити
Процесс - это выполнение программы. Компоненты процесса - выполняющаяся программа, ее данные, ее ресурсы (например, память), и состояние выполнения.

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

таблицы страниц (или сегментов);

дескрипторы файлов;

заказы на ввод-вывод;

регистры;

и т.п.

Большой объем этой информации делает дорогими операции создания процессов, их переключение.

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

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

2.2. Взаимодействие процессов

Если приложение реализовано в виде множества процессов (или нитей), то эти процессы (нити) могут взаимодействовать двумя основными способами:

посредством разделения памяти (оперативной или внешней)

посредством передачи сообщений



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

Различают два вида синхронизации - взаимное исключение критических интервалов и координация процессов.

Критические секции. Недетерминизм, race condition (условия гонок).


Процесс p1 выполняет оператор I = I+J,

а процесс p2 - оператор I = I-K

машинные коды выглядят так:

Load R1,I Load R1,I

Load R2,J Load R2,K

Add R1,R2 Sub R1,R2

Store R1,I Store R1,I

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

Требуется взаимное исключение критических интервалов.

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

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

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

ни один процесс не должен бесконечно долго ждать разрешения на вход в критический интервал (если ни один процесс не будет находиться внутри критического интервала бесконечно долго);

не должно существовать никаких предположений о скоростях процессоров.


^ Взаимное исключение критических интервалов в однопроцессорной ЭВМ.

1. Блокировка внешних прерываний (может нарушаться управление внешними устройствами, возможны внутренние прерывания при работе с виртуальной памятью).

2. Блокировка переключения на другие процессы (MONO, MULTI).

^ Взаимное исключение критических интервалов в многопроцессорной ЭВМ.

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

^ Алгоритм Деккера (1968).

int turn;

boolean flag[2 ];


proc( int i )

{

while (TRUE)

{

<вычисления>;

enter_region( i );

<критический интервал>;

leave_region( i );

}

}


void enter_region( int i )

{

try: flag[ i ]=TRUE;

while (flag [( i+1 ) % 2])

{

if ( turn = = i ) continue;

flag[ i ] = FALSE;

while ( turn != i );

goto try;

}


}


void leave_region( int i )

{

turn = ( i +1 ) % 2;

flag[ i ] = FALSE;

}


turn = 0;

flag[ 0 ] = FALSE;

flag[ 1 ] = FALSE;

proc( 0 ) AND proc( 1 ) /* запустили 2 процесса */

^ Алгоритм Петерсона (1981)

int turn;

int flag[ 2 ];


void enter_region( int i )

{

int other; /* номер другого процесса */

other = 1 - i;

flag[ i ] = TRUE;

turn = i;

while (turn = = i && flag[ other ] = = TRUE) /* пустой оператор */;

}


void leave_region( int i )

{

flag[ i ] = FALSE;

}


^ Использование неделимой операции TEST_and_SET_LOCK.

Операция TSL(r,s): [r = s; s = 1]

Квадратные скобки - используются для спецификации неделимости операций.

enter_region:

tsl reg, flag

cmp reg, #0 /* сравниваем с нулем */

jnz enter_region /* если не нуль - цикл ожидания */

ret

leave_region:

mov flag, #0 /* присваиваем нуль*/

ret

^ Семафоры Дейкстры (1965).

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

Функция запроса семафора P(s):

[if (s == 0) <заблокировать текущий процесс>; else s = s-1;]

Замечание. Неделимость этой операции означает, что после разблокирования процесса он начнет ее выполнять заново.


Функция освобождения семафора V(s):

[if (s == 0) <разблокировать один из заблокированных процессов>;

s = s+1;]


Двоичные семафоры как частный случай общих (считающих).

Использование семафоров для взаимного исключения критических интервалов и для координации в задаче производитель-потребитель.

Задача производитель-потребитель (поставщик-потребитель, проблема ограниченного буфера).

semaphore s = 1;

semaphore full = 0;

semaphore empty = N;


producer() ¦ consumer()

{ ¦ {

¦

int item; ¦ int item;

while (TRUE) ¦ while (TRUE)

{ ¦ {

produce_item(&item); ¦

P(empty); ¦ P(full);

P(s); ¦ P(s);

enter_item(item); ¦ remove_item(&item);

V(s); ¦ V(s);

V(full); ¦ V(empty);

¦ consume_item(item);

} ¦ }

} ¦ }

¦

producer() AND consumer() /* запустили 2 процесса */

Реализация семафоров.

Мультипрограммный режим.

блокировка внешних прерываний;

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

переменная и очереди ожидающих процессов в ОС.



Для многопроцессорной ЭВМ первые два способа не годятся. Для реализации третьего способа достаточно команды TSL и возможности объявлять прерывание указанному процессору.

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

**********Лекция 4

Если произведенный объект используется многими, то семафоры не годятся.
События.
Это переменные, показывающие, что произошли определенные события.

Для объявления события служит оператор POST(имя переменной), для ожидания события - WAIT (имя переменной). Для чистки (присваивания нулевого значения) - оператор CLEAR(имя переменной).

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

Метод последовательной верхней релаксации (SOR) с использованием массива событий.

float A[ L1 ][ L2 ];

struct event s[ L1 ][ L2 ];

for ( i = 0; i < L1; i++)

for ( j = 0; j < L2; j++) { clear( s[ i ][ j ]) };

for ( j = 0; j < L2; j++) { post( s[ 0 ][ j ]) };

for ( i = 0; i < L1; i++) { post( s[ i ][ 0 ]) };

..............

..............

parfor ( i = 1; i < L1-1; i++)

parfor ( j = 1; j < L2-1; j++)

{ wait( s[ i-1 ][ j ]);

wait( s[ i ][ j-1 ]);

A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;

post( s[ i ][ j ]);

}


^ Обмен сообщениями (message passing)


Хоар (Xoare) 1978 год, "Взаимодействующие параллельные процессы". Цели - избавиться от проблем разделения памяти и предложить модель взаимодействия процессов для распределенных систем.

send (destination, &message, msize);

receive ([source], &message, msize);

Адресат - процесс. Отправитель - может не специфицироваться (любой).

С буферизацией (почтовые ящики) или нет (рандеву - Ада, Оккам).

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


Пример использования буферизуемых сообщений.

#define N 100 /* максимальное число сообщений */

/* в буфере*/

#define msize 4 /* размер сообщения*/

typedef int message[msize];


producer()

{

message m;

int item;


while (TRUE)

{

produce_item(&item);

receive(consumer, &m, msize); /* получает пустой */

/* "контейнер" */

build_message(&m, item); /* формирует сообщение */

send(consumer, &m, msize);

}

}


consumer()

{

message m;

int item, i;


for (i = 0; i < N; i ++)

send (producer, &m, msize); /* посылает все пустые *.

/* "контейнеры" */

while (TRUE)

{

receive(producer, &m, msize);

extract_item(&m, item);

send(producer, &m, msize); /* возвращает "контейнер" */

consume_item(item);

}

}


producer() AND consumer() /* запустили 2 процесса */


Механизмы семафоров и обмена сообщениями взаимозаменяемы семантически и на мультипроцессорах могут быть реализованы один через другой. Другие классические задачи взаимодействия процессов - проблема обедающих философов (Dijkstra) и "читатели-писатели".
^ 2.3 Планирование процессоров
Планирование процессоров очень сильно влияет на производительность мультипроцессорной системы. Можно выделить следующие главные причины деградации производительности:

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




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


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

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

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

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

Планирование с учетом "советов" программы (во время ее выполнения). В ОС Mach имеется два класса таких советов (hints) - указания (разной степени категоричности) о снятии текущего процесса с процессора, а также указания о том процессе, который должен быть выбран взамен текущего.


Вопросы:


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

Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на них, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора. Активное ожидание освобождения семафора не допускается.

Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы POST(имя переменной-события) и WAIT(имя переменной-события). Активное ожидание события не допускается. Оцените, во сколько раз нижеприведенный алгоритм метода последовательной верхней релаксации можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальных операторов можно пренебречь.

float A[ L1 ][ L2 ];

semaphore s[ L1 ][ L2 ]; /* массив двоичных семафоров с нулевым начальным значением */

for ( j = 0; j < L2; j++) { post( s[ 0 ][ j ]) }

parfor ( i = 1; i < L1-1; i++)

for ( j = 1; j < L2-1; j++)

{ wait( s[ i-1 ][ j ]);

A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;

post( s[ i ][ j ]);

}



Имеется механизм двоичных семафоров. Опираясь на него, реализуйте задачу читателей и писателей (алгоритмы предоставления прав доступа процессам-читателям и процессам-писателям):

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

Запросы на доступ должны удовлетворяться “справедливо” - в порядке их поступления (можно исходить из “справедливости“ удовлетворения запросов на двоичные семафоры).

Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.

Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.


При решении задач по теме 2 обратить внимание на следующее.

Нельзя модифицировать общие переменные вне КС.

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

Нельзя обращаться к семафорам и событиям обычными операторами – только посредством операций, которые определены над ними (P, V, POST, WAIT, CLEAR).

Нельзя освобождать свободный семафор и объявлять уже объявленное событие.

Определять начальные значения семафоров и событий, если они должны быть отличны от нуля (семафор занят, событие не объявлено).
^ Лекция 5 3 Коммуникации в распределенных системах
Все компьютеры в распределенной системе связаны между собой коммуникационной сетью. Коммуникационные сети подразделяются на широкомасштабные (Wide Area Networks, WANs) и локальные (Local Area Networks, LANs).

Широкомасштабные сети

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

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

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


^ Семиуровневая модель ISO

ISO OSI (International Standards Organizations»s Reference Model of Open Systems Interconnection) организует коммуникационные протоколы в виде семи уровней и специфицирует функции каждого уровня.

Локальные сети.

Особенности LAN:

географическая область охвата невелика (здание или несколько зданий);

высокая скорость передачи (10-100 Mbps);

малая вероятность ошибок передачи.

Свойственные многоуровневой модели ISO OSI накладные расходы являются причиной того, что в LAN применяются более простые протоколы.
Клиент-сервер
Можно избежать подтверждения получения сервером сообщения-запроса от клиента, если ответ сервера должен последовать скоро.
^ Удаленный вызов процедур
Send, receive - подход ввода/вывода

Более естественный подход, применяемый в централизованных ЭВМ - вызов процедур.

Birrell and Nelson (1984) (независимо и раньше - Илюшин А.И.,1978) предложили позволить вызывающей программе находиться на другой ЭВМ.


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

Время передачи сообщения между двумя узлами транспьютерной матрицы (характеристики аппаратуры - время старта передачи Ts, время передачи одного байта информации соседнему узлу Tb, процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми). За время Ts+ Tb транспьютер может передать 1 байт информации своим четырем соседям и принять от них 4 байта информации (по одному байту от каждого).

Конвейеризация и параллельное использование нескольких маршрутов – два метода ускорения передачи сообщений.
^ 3.1 Обмен сообщениями между прикладными процессами
SEND, RECEIVE (адресат/отправитель, [тэг,] адрес памяти, длина)

адресация - физический/логический номер процессора, уникальный идентификатор динамически создаваемого процесса, служба имен (сервер имен или широковещание - broadcasting).

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

Блокирующие операции send (до освобождения памяти с данными или до завершения фактической передачи) и неблокирующие.

Буферизуемые и небуферизуемые (rendezvous или с потерей информации при отсутствии receive).

Надежные и ненадежные.
^ MPI - Message-Passing Interface [4]
(Message Passing Interface Forum, May 5, 1994

http://www.mpi-forum.org)

(1) Цели:

Создать интерфейс прикладного программирования (не только для компиляторов или библиотек реализации систем);

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

Разрешить расширения для использования в гетерогенной среде;

Исходить из надежности коммуникаций (пользователь не должен бороться с коммуникационными сбоями - это дело коммуникационных подсистем нижнего уровня);

Определить интерфейс, который бы не слишком отличался от используемых в настоящее время, таких как PVM, Express, P4, и пр.;

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

**************************************************************


(2) Что включено в MPI ?

Коммуникации точка-точка;

Коллективные операции;

Группы процессов;

Коммуникационные контексты;

Простой способ создания процессов для модели SPMD (одна программа используется для обработки разных данных на разных процессорах);

Топология процессов.

**************************************************************

(3) Что не включено в MPI ?

Явные операции с разделяемой памятью и явная поддержка нитей (процессов с общей памятью);

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

Вспомогательные функции, такие как таймеры.

**************************************************************


(4) Некоторые понятия.

Коммуникационные операции могут быть:

неблокирущие - если возврат осуществляется до завершения операции;

блокируюшие - если возврат означает, что пользователь может использовать ресурсы (например, буфера), указанные в вызове;

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

(5) Группы, контексты, коммуникаторы.

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

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

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

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

Имеются предопределенные коммуникаторы (точнее, создаваемые при инициализации MPI-системы):

MPI_COMM_WORD - все процессы

MPI_COMM_SELF - один текущий процесс

**************************************************************

(6) Операции над группами (локальные, без обмена сообщениями).

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

Для поддержки связывания с серверами, имеются средства построения коммуникатора по некоторому имени, известному и серверу и клиентам.

(7) Точечные коммуникации.

Основные операции - send, receive

Операции могут быть блокирующими и неблокирующими.

В операции send задается:

адрес буфера в памяти;

количество посылаемых элементов;

тип данных каждого элемента;

номер процесса-адресата в его группе;

тег сообщения;

коммуникатор.

(последние 3 параметра - аналоги «почтового конверта»)



В операции receive задается:

адрес буфера в памяти;

количество посылаемых элементов;

тип данных каждого элемента;

номер процесса-адресата в его группе (либо «любой»);

тег сообщения (либо «любой»);

коммуникатор;

статус (источник и тег, необходимые в том случае, когда они неизвестны - при их задании с помощью шаблона «любой»).



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

Имеется четыре режима коммуникаций - стандартный, буферизуемый, синхронный и режим готовности.

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

В буферизуемом режиме последовательность выдачи операций send и receive произвольна, операция send завершается тогда, когда сообщение изъято из памяти и помещено в буфер. Если места в буфере нет - ошибка программы (но есть возможность определить свой буфер). Операция локальная.

В синхронном режиме последовательность выдачи операций произвольна, но операция send завершается только после выдачи и начала выполнения операции receive. Операция нелокальная.

В режиме готовности операция send может быть выдана только после выдачи соответствующей операции receive, иначе программа считается ошибочной и результат ее работы неопределен. Операция локальная.

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

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

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

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

Имеется составная операция send-receive, позволяющая избежать трудностей с порядком выдачи отдельных операций в обменивающихся между собой процессах. Для частного случая обмена данными одного типа и длины предлагается специальная операция (send-receive-replace), в которой для посылки и приема сообщения используется один буфер.
^ (8) Коллективные коммуникации.
Для обеспечения коллективных коммуникаций введены следующие функции:

барьер для всех членов группы (BARRIER);

передача сообщения всем членам группы от одного (BROADCAST);

сбор данных от всех членов группы для одного (GATHER);

рассылка данных всем членам группы от одного (SCATTER);

сбор данных от всех членов группы для всех (ALLGATHER);

рассылка данных всем членам группы от всех (ALLTOALL);

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



^ Схема перемещения данных между 4 процессами

Данные

Pr-0

A0













A0










Pr-1













BROADCAST

A0










Pr-2















A0










Pr-3

























A0













Pr-0

A0

A1

A2

A3

SCATTER

A0










Pr-1















A1










Pr-2













GATHER

A2










Pr-3















A3













Pr-0

A0

A1

A2

A3













A0










Pr-1

A0

A1

A2

A3

ALLGATHER

A1










Pr-2

A0

A1

A2

A3



A2










Pr-3

A0

A1

A2

A3













A3













Pr-0

A0

A1

A2

A3













A0

B0

C0

D0

Pr-1

B0

B1

B2

B3

ALLTOALL

A1

B1

C1

D1

Pr-2

C0

C1

C2

C3



A2

B2

C2

D2

Pr-3

D0

D1

D2

D3













A3

B3

C3

D3


Названия функций и параметры:

MPI_BARRIER(IN comm)

MPI_BCAST(IN/OUT buffer, IN cnt, IN type, IN root, IN comm)

MPI_GATHER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN root, IN comm)

MPI_SCATTER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN root, IN comm)

MPI_ALLGATHER(IN sendbuf, IN sendcnt, IN sendtype,

OUT recvbuf, IN recvcnt, IN recvtype, IN comm)

MPI_ALLTOALL(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN comm)


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


^ PVM (Parallel Virtual Machine).

Широко известная система PVM [5] была создана для объединения нескольких связанных сетью рабочих станций в единую виртуальную параллельную ЭВМ. Система представляет собой надстройку над операционн