JUN Jan Feb 15 2007 2009 2010 17 captures 28 Oct 04 - 15 Jan 09

Close Help

Введение

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

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

История ОС.

1940-е и 1950-е
"Персональные ЭВМ" - "пультовый режим" Библиотека программ ввода-вывода, служебная программа.

Середина 1950-х
Пакетная обработка. Однопрограммный и мультипрограммный режимы. Инструкция оператору -> паспорт задачи (простейший язык управления заданиями). Требования к аппаратуре:

• защита памяти;
• прерывания;
• привилегированный режим;
• таймер.

Середина 1960-х
Режим разделения времени. Терминалы, квантование, свопинг, страничная и сегментная организация.

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

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

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

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

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

1. Производительность
2. Надежность

Недостатки мультипроцессоров

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

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

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

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

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

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

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

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

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

1. Необходимость разделять данные.
2. Преимущество разделения дорогих периферийных устройств, уникальных информационных и программных ресурсов.
3. Достижение развитых коммуникаций между людьми. Электронная почта во многих случаях удобнее писем, телефонов и факсов.
4. Гибкость использования различных ЭВМ, распределение нагрузки.
5. Упрощение постепенной модернизации посредством замены компъютеров.

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

1. Проблемы ПО (приложения, языки, ОС).
2. Проблемы коммуникационной сети (потери информации, перегрузка,развитие и замена).
3. Секретность.

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

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

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

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

(2) Гибкость (не все еще ясно - потребуется менять решения).
Использование монолитного ядра ОС или микроядра.

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

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

(4) Производительность.
Грануллированность. Мелкозернистый и крупнозернистый параллелизм (fine-grained parallelism, coarse-grained parallelism). Устойчивость к ошибкам требует дополнительных накладных расходов.

(5) Масштабируемость.
Плохие решения:

• централизованные компоненты (один почтовый-сервер);
• централизованные таблицы (один телефонный справочник);
• централизованные алгоритмы (маршрутизатор на основе полной информации).

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

Операционные системы мультипроцессорных ЭВМ

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

2.1 Процессы и нити

• таблицы страниц (или сегментов);
• дескрипторы файлов;
• заказы на ввод-вывод;
• регистры;
• и т.п.

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

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

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

Процесс p1 выполняет оператор I = I+J, а процесс p2 - оператор I = I-K машинные коды выглядят так:

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

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

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

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 = ( turn +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()
{
  int item;
  while (TRUE)
  {
    produce_item(&item);
    P(empty);
    P(s);
    enter_item(item);
    V(s);
    V(full);
  }
}

consumer()
{
  int item;
  while (TRUE)
  {
    P(full);
    P(s);
    remove_item(&item);
    V(s);
    V(empty);
    consume_item(item);
  }
}

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

Реализация семафоров. Мультипрограммный режим.

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

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

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

События.
Это переменные, показывающие, что произошли определенные события. Для объявления события служит оператор 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 Планирование процессоров

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

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

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

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

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

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

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

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

3.1 Семиуровневая модель 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 байта информации (по одному байту от каждого). Конвейеризация и параллельное использование нескольких маршрутов.

Обмен сообщениями между прикладными процессами
SEND, RECEIVE (адресат/отправитель, [тэг], адрес памяти, длина)

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

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

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

Надежные и ненадежные.

3.2 MPI - Message-Passing Interface [4]

(1) Цели:

• Создать интерфейс прикладного программирования (не только для компиляторов или библиотек реализации систем);
• Обеспечить возможность эффективных коммуникаций (избежать копирования из памяти в память, позволить совмещение вычислений и коммуникаций или разгрузку на коммуникационный процессор там, где он есть);
• Разрешить расширения для использования в гетерогенной среде;
• Исходить из надежности коммуникаций (пользователь не должен бороться с коммуникационными сбоями - это дело коммуникационных подсистем нижнего уровня);
• Определить интерфейс, который бы не слишком отличался от используемых в настоящее время, таких как PVM, Express, P4, и пр.;
• Определить интерфейс, который мог бы быстро быть реализован на многих продаваемых платформах без серьезной переделки нижележащего коммуникационного и системного ПО.

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

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

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

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

(4) Некоторые понятия.
Коммуникационные операции могут быть:

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

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

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

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

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

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

• MPI_COMM_ALL - все процессы
• MPI_COMM_PEER - все, кроме главного процесса.

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

(7) Точечные коммуникации.
Основные операции - send, receive Операции могут быть блокирующими и неблокирующими.

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

• адрес буфера в памяти;
• количество посылаемых элементов;
• тип данных каждого элемента;
• номер процесса-адресата в его группе;
• тег сообщения;
• коммуникатор.

В операции 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       Pr-1         Pr-2         Pr-3	BROADCAST	A0       A0       A0       A0
Pr-0 A0 A1 A2 A3 Pr-1         Pr-2         Pr-3	SCATTER GATHER	A0       A1       A2       A3
Pr-0 A0 B0 C0 D0 Pr-1 A0 B0 C0 D0 Pr-2 A0 B0 C0 D0 Pr-3 A0 B0 C0 D0	ALLGATHER	A0       B0       C0       D0
Pr-0 A0 A1 A2 A3 Pr-1 B0 B1 B2 B3 Pr-2 C0 C1 C2 C3 Pr-3 D0 D1 D2 D3	ALLTOALL	A0 B0 C0 D0 A1 B1 C1 D1 A2 B2 C2 D2 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)

PVM (Parallel Virtual Machine)

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

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

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

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

MPI-2 (1997 г.)

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

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

Обычно децентрализованные алгоритмы имеют следующие свойства:

1. Относящаяся к делу информация распределена среди ЭВМ.
2. Процессы принимают решение на основе только локальной информации.
3. Не должно быть единственной критической точки, выход из строя которой приводил бы к краху алгоритма.
4. Не существует общих часов или другого источника точного глобального времени.

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

4.1 Синхронизация времени

Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте.

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

Для синхронизации логических часов Lamport определил отношение "произошло до". Выражение a->b читается как "a произошло до b" и означает, что все процессы согласны, что сначала произошло событие "a", а затем "b". Это отношение может в двух случаях быть очевидным:

1. Если оба события произошли в одном процессе.
2. Если событие a есть операция SEND в одном процессе, а событие b - прием этого сообщения другим процессом.

Отношение -> является транзитивным.

Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения x->y и y->x являются неверными, а эти события называют одновременными.

Введем логическое время С таким образом, что если a->b, то C(a) < C(b)

Алгоритм:

1. Часы Ci увеличивают свое значение с каждым событием в процессе Pi: Ci=Ci+d (d > 0, обычно равно 1)
2. Если событие a есть посылка сообщения m процессом Pi, тогда в это сообщение вписывается временная метка tm=Ci(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом: Cj = max(Cj,tm+d)

Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2). Однако логических часов недостаточно для многих применений (системы управления в реальном времени).

Физические часы.
После изобретения в 17 веке механических часов время измерялось астрономически. Интервал между двумя последовательными достижениями солнцем наивысшей точки на небе называется солнечным днем. Солнечная секунда равняется 1/86400(24*3600) части солнечного дня.

В 1940-х годах было установлено, что период вращения земли не постоянен - земля замедляет вращение из-за приливов и атмосферы. Геологи считают, что 300 миллионов лет назад в году было 400 дней. Происходят и изменения длительности дня по другим причинам. Поэтому стали вычислять за длительный период среднюю солнечную секунду.

С изобретением в 1948 году атомных часов появилась возможность точно измерять время независимо от колебаний солнечного дня. В настоящее время 50 лабораторий в разных точках земли имеют часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI), исчисляемым с 1 июля 1958 года.

Отставание TAI от солнечного времени компенсируется становится добавлением секунды тогда, когда разница больше 800 мксек. Это скорректированное время, называеемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). При объявлении о добавлении секунды к UTC электрические компании меняют частоту с 60 Hz на 61 Hz (c 50 на 51) на период времени в 60 (50) секунд. Для обеспечения точного времени сигналы WWV передаются коротковолновым передатчиком (Fort Collins, Colorado) в начале каждой секунды UTC. Есть и другие службы времени.

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

4.2 Выбор координатора

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

Алгоритм "задиры"
Если процесс обнаружит, что координатор очень долго не отвечает, то инициирует выборы. Процесс P проводит выборы следующим образом:

1. P посылает сообщение "ВЫБОРЫ" всем процессам с большими чем у него номерами.
2. Если нет ни одного ответа, то P считается победителем и становится координатором.
3. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается.

В любой момент процесс может получить сообщение "ВЫБОРЫ" от одного из коллег с меньшим номером. В этом случае он посылает ответ "OK", чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением "КООРДИНАТОР".

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

Круговой алгоритм.
Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение "ВЫБОРЫ" со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на "КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется.

4.3 Взаимное исключение

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

Недостатки алгоритма - обычные недостатки централизованного алгоритма (крах координатора или его перегрузка сообщениями).

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

Проблемы:

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

Алгоритм древовидный маркерный (Raymond)
Все процессы представлены в виде сбалансированного двоичного дерева. Каждый процесс имеет очередь запросов от себя и соседних процессов (1-го, 2-х или 3-х) и указатель в направлении владельца маркера.

Вход в критическую секцию:
Если есть маркер, то процесс выполняет КС.
Если нет маркера, то процесс:

1. помещает свой запрос в очередь запросов
2. посылает сообщение "ЗАПРОС" в направлении владельца маркера и ждет сообщений.

Поведение процесса при приеме сообщений:
Процесс, не находящийся внутри КС должен реагировать на сообщения двух видов -"МАРКЕР" и "ЗАПРОС".

А) Пришло сообщение "МАРКЕР"

• М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможно себе);
• М2. Поменять значение указателя в сторону маркера;
• М3. Исключить запрос из очереди;
• М4. Если в очереди остались запросы, то послать сообщение "ЗАПРОС" в сторону маркера.

Б) Пришло сообщение "ЗАПРОС".

1. Поместить запрос в очередь
2. Если нет маркера, то послать сообщение "ЗАПРОС" в сторону маркера, иначе (если есть маркер) - перейти на пункт М1.

Выход из критической секции.
Если очередь запросов пуста, то при выходе ничего не делается, иначе - перейти к пункту М1.

Децентрализованный алгоритм на основе временных меток.
Алгоритм носит имя Ricart-Agrawala и является улучшением алгоритма, который предлжил Lamport.

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

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

Поведение процесса при приеме запроса:
Когда процесс получает сообщение-запрос, в зависимости от своего состояния по отношению к указанной критической секции он действует одним из следующих способов.

1. Если получатель не находится внутри критической секции и не запрашивал разрешение на вход в нее, то он посылает отправителю сообщение "OK".
2. Если получатель находится внутри критической секции, то он не отвечает, а запоминает запрос.
3. Если получатель выдал запрос на вхождение в эту секцию, но еще не вошел в нее, то он сравнивает временные метки своего запроса и чужого. Побеждает тот, чья метка меньше. Если чужой запрос победил, то процесс посылает сообщение "OK". Если у чужого запроса метка больше, то ответ не посылается, а чужой запрос запоминается.

Выход из критической секции:
После выхода из секции он посылает сообщение "OK" всем процессам, запросы от которых он запомнил, а затем стирает все запомненные запросы.

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

Алгоритм широковещательный маркерный (Suzuki-Kasami).
Маркер содержит:

• очередь запросов;
• массив LN[1...N] с номерами последних удовлетворенных запросов.

Вход в критическую секцию:

1. Если процесс Pk, запрашивающий критическую секцию, не имеет маркера, то он увеличивает порядковый номер своих запросов RNk[k] и посылает широковещательно сообщение "ЗАПРОС", содержащее номер процесса (k) и номер запроса (Sn=RNk[k]).
2. Процесс Pk выполняет критическую секцию, если имеет (или когда получит) маркер.

Поведение процесса при приеме запроса:

1. Когда процесс Pj получит сообщение-запрос от процесса Pk, он устанавливает RNj[k]=max(RNj[k],Sn). Если Pj имеет свободный маркер, то он его посылает Pk только в том случае, когда RNj[k]=LN[k]+1 (запрос не старый).

Выход из критической секции процесса Pk:

1. Устанавливает LN[k] в маркере равным RNk[k].
2. Для каждого Pj, для которого RNk[j]=LN[j]+1, он добавляет его идентификатор в маркерную очередь запросов.
3. Если маркерная очередь запросов не пуста, то из нее удаляется первый элемент, а маркер посылается соответствующему процессу (запрос которого был первым в очереди).

Измерение производительности
Введем следующие три метрики.

1. MS/CS - количество операций приема сообщений, требуемое для одного прохождения критической секции.
2. TR - время ответа, время от появления запроса до получения разрешения на вход.
3. SD - синхронизационная задержка, время от выхода из критической секции одного процесса до входа в нее следующего процесса (другого!).

При оценке производительности интересны две ситуации:

• низкая загрузка (LL), при которой вероятность запроса входа в занятую критическую секцию очень мала;
• высокая загрузка (HL), при которой всегда есть запросы на вход в занятую секцию.

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

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

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

4.4 Координация процессов

1. Сообщения точка-точка (если известно, кто потребитель).
2. Если неизвестно, кто потребитель, то:
   • сообщения широковещательные;
   • сообщения в ответ на запрос.
3. Если неизвестно, кто потребляет и кто производит, то:
   • сообщения и запросы через координатора:
   • широковещательный запрос.

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

Высокая доступность.
Другая важная цель - обеспечение высокой доступности. Ошибки систем или осуществление операций копирования и сопровождения не должны приводить к недоступности файлов.

Понятие файлового сервиса и файлового сервера.

Файловый сервис - это то, что файловая система предоставляет своим клиентам, т.е. интерфейс с файловой системой.
Файловый сервер - это процесс, который реализует файловый сервис.

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

Так, как файловый сервер обычно является обычным пользовательским процессом, то в системе могут быть различные файловые серверы, предоставляющие различный сервис (например, UNIX файл сервис и MS-DOS файл сервис).

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

5.1.1 Интерфейс файлового сервера

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

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

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

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

5.1.2 Интерфейс сервера директорий

Определяет алфавит и синтаксис имен. Для спецификации типа информации в файле используется часть имени (расширение) либо явный атрибут.

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

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

Прозрачность именования.
Две формы прозрачности именования различают - прозрачность расположения (/server/d1/f1) и прозрачность миграции (когда изменение расположения файла не требует изменения имени).

Имеются три подхода к именованию:
 

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

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

5.1.3 Семантика разделения файлов

UNIX-семантика

Еще одна проблема - трудно сохранить семантику общего указателя файла (в UNIX он общий для открывшего файл процесса и его дочерних процессов) - для процессов на разных ЭВМ трудно иметь общий указатель.

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

5.2 Реализация распределенных файловых систем

5.2.1 Использование файлов

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

5.2.2 Структура системы

Второй вопрос - должны ли быть файловый сервер и сервер директорий отдельными серверами или быть объединенными в один сервер. Разделение позволяет иметь разные серверы директорий (UNIX, MS-DOS) и один файловый сервер. Объединение позволяет сократить коммуникационные издержки.

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

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

Последний важный вопрос - должны ли серверы хранить информацию о клиентах.

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

• устойчивость к ошибкам.
• не требуется операций ОТКРЫТЬ/ЗАКРЫТЬ.
• не требуется память для таблиц.
• нет ограничений на число открытых файлов.
• нет проблем при крахе клиента.

5.2.3 Кэширование

Во-первых, хранение файлов на дисках сервера. Нет проблемы когерентности, так как одна копия файла существует. Главная проблема - эффективность, поскольку для обмена с файлом требуется передача информации в обе стороны и обмен с диском.

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

Коммуникационные издержки остаются.

Избавиться от коммуникаций позволяет кэширование в машине клиента.

Кэширование на диске клиента может не дать преимуществ перед кэшированием в памяти сервера, а сложность повышается значительно.

Поэтому рассмотрим подробнее организацию кэширования в памяти клиента.

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

Когерентность кэшей.

Алгоритм с отложенной записью.
Через регулярные промежутки времени все модифицированные блоки пишутся в файл. Эффективность выше, но семантика непонятная пользователю (UNIX).

Алгоритм записи в файл при закрытии файла.
Реализует семантику сессий. Не намного хуже случая, когда два процесса на одной ЭВМ открывают файл, читают его, модифицируют в своей памяти и пишут назад в файл.

Алгоритм централизованного управления.
Можно выдержать семантику UNIX, но не эффективно, ненадежно, и плохо масштабируется.
 

5.2.4 Размножение

1. Повысить надежность.
2. Повысить доступность (крах одного сервера не вызывает недоступность размноженных файлов.
3. Распределить нагрузку на несколько серверов.
4. Явное размножение (непрозрачно). В ответ на открытие файла пользователю выдаются несколько двоичных имен, которые он должен использовать для явного дублирования операций с файлами.
5. “Ленивое” размножение. Одна копия создается на одном сервере, а затем он сам автоматически создает (в свободное время) дополнительные копии и обеспечивает их поддержание.
6. Симметричное размножение. Все операции одновременно вызываются в нескольких серверах и одновременно выполняются.

5.2.5 Пример: Sun Microsystem’s Network File System (NFS)

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

Клиент получает доступ к экспортированным директориям путем их монтирования. Если клиент не имеет дисков, то может монтировать директории в свою корневую директорию.

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

Многие клиенты монтируют требуемые удаленные директории автоматически при запуске (используя командную процедуру shell-интерпретатора ОС UNIX).

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

Второй протокол - для доступа к директориям и файлам. Клиенты посылают сообщения, чтобы манипулировать директориями, читать и писать файлы. Можно получить атрибуты файла. Поддерживается большинство системных вызовов ОС UNIX, исключая OPEN и CLOSE. Для получения дескриптора файла по его символическому имени используется операция LOOKUP, отличающаяся от открытия файла тем, что никаких внутренних таблиц не создается. Таким образом, серверы в NFS не имеют состояния (stateless). Поэтому для захвата файла используется специальный механизм.

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

Все ключи, используемые для контроля доступа, поддерживаются специальным сервисом (и серверами) - сетевым информационным сервисом (NIS). Храня пары (ключ, значение), сервис обеспечивает выдачу значения кода при правильном подтверждении ключей. Кроме того, он обеспечивает отображение имен машин на их сетевые адреса, и другие отображения. NIS-серверы используют схему главный -подчиненные для реализации размножения (“ленивое” размножение).

Задача уровня виртуальной файловой системы - поддерживать для каждого открытого файла строку в таблице (v-вершину), аналогичную i-вершине UNIX. Эта строка позволяет различать локальные файлы от удаленных. Для удаленных файлов вся необходимая информация хранится в специальной r-вершине в NFS-клиенте, на которую ссылается v-вершина. У сервера нет никаких таблиц.

Передачи информации между клиентом и сервером NFS производятся блоками размером 8К (для эффективности).

Два кэша - кэш данных и кэш атрибутов файлов (обращения к ним очень часты, разработчики NFS исходили из оценки 90%). Реализована семантика отложенной записи - предмет критики NFS.

Имеется также кэш подсказок для ускорения получения v-вершины по символическому имени. При использовании устаревшей подсказки NFS-клиент будет обращаться к NFS-серверу и корректировать свой кэш (пользователь об этом ничего не должен знать).

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

6.1 Достоинства DSM

1. В модели передачи сообщений программист обеспечивает доступ к разделяемым данным посредством явных операций посылки и приема сообщений. При этом приходится квантовать алгоритм, обеспечивать своевременную смену информации в буферах, преобразовывать индексы массивов. Все это сильно усложняет программирование и отладку. DSM скрывает от программиста пересылку данных и обеспечивает ему абстракцию разделяемой памяти, к использованию которой он уже привык на мультипроцессорах. Программирование и отладка с использованием DSM гораздо проще.
2. В модели передачи сообщений данные перемещаются между двумя различными адресными пространствами. Это делает очень трудным передачу сложных структур данных между процессами. Более того, передача данных по ссылке и передача структур данных, содержащих указатели, является в общем случае делом сложным и дорогостоящим. DSM же позволяет передавать данные по ссылке, что упрощает разработку распределенных приложений.
3. Объем суммарной физической памяти всех узлов может быть огромным. Эта огромная память становится доступна приложению без издержек, связанных в традиционных системах с дисковыми обменами. Это достоинство становится все весомее в связи с тем, что скорости процессоров растут быстрее скоростей памяти и в то же время появляются очень быстрые коммуникации.
4. DSM-системы могут наращиваться практически беспредельно в отличие от систем с разделяемой памятью, т.е. являются масштабируемыми.
5. Программы, написанные для мультипроцессоров с общей памятью, могут в принципе без каких-либо изменений выполняться на DSM-системах (по крайней мере, они могут быть легко перенесены на DSM-системы).По существу, DSM-системы преодолевают архитектурные ограничения мультипроцессоров и сокращают усилия, необходимые для написания программ для распределенных систем. Обычно они реализуются программно-аппаратными средствами, но в последние годы появилось несколько коммерческих MPP с DSM, реализованной аппаратно (Convex SPP, KSR1).

6.2 Алгоритмы реализации DSM

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

6.2.1 Алгоритм с центральным сервером

6.2.2 Миграционный алгоритм

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

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

6.2.3 Алгоритм размножения для чтения

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

6.2.4 Алгоритм полного размножения

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

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

6.3 Модели консистентности

6.3.1 Строгая консистентность

Все однопроцессорные системы обеспечивают строгую консистентность, но в распределенных многопроцессорных системах ситуация намного сложнее. Предположим, что переменная X расположена в памяти машины B, и процесс, который выполняется на машине A, пытается прочитать значение этой переменной в момент времени T1. Для этого машине B посылается запрос переменной X. Немного позже, в момент времени T2, процесс, выполняющийся на машине B, производит операцию записи нового значения в переменную X. Для обеспечения строгой консистентности операция чтения должна возвратить в машину А старое значение переменной вне зависимости от того, где расположена машина A и насколько близки между собой два момента времени T1 и T2. Однако, если T1-T2 равно 1 нсек, и машины расположены друг от друга на расстоянии 3-х метров, то сигнал о запросе значения переменной должен быть передан на машину B со скоростью в 10 раз превышающей скорость света, что невозможно.
 

P1: W(x)1	P1: W(x)1
--------------------------------> t	-----------------------------------> t
P2: R(x)1	P2: R(x)0 R(x)1
а)	б)

а) Строго консистентная память
б) Память без строгой консистентности
 

6.3.2 Последовательная консистентность

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

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

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

W(x)1 - запись значения 1 в переменную x;
R(x)0 - чтение значения 0 из переменной x. 

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

6.3.3 Причинная консистентность

<>Рассмотрим пример. Предположим, что процесс P1 модифицировал переменную x, затем процесс P2 прочитал x и модифицировал y. В этом случае модификация x и модификация y потенциально причинно зависимы, так как новое значение y могло зависеть от прочитанного значения переменной x. С другой стороны, если два процесса одновременно изменяют значения различных переменных, то между этими событиями нет причинной связи. Операции, которые причинно не зависят друг от друга называются параллельными.

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

Пример.

(а) Нарушение модели причинной консистентности
 

P1:	W(x)1
P2:		R(x)1	W(x)2
P3:				R(x)2	R(x)1
P4:				R(x)1	R(x)2

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

P1:	W(x)1			W(x)3
P2:		R(x)1	W(x)2
P3:		R(x)1			R(x)3	R(x)2
P4:		R(x)1			R(x)2	R(X)3

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

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

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

6.3.4 PRAM консистентность и процессорная консистентность

Пример допустимой последовательности событий в системе с PRAM консистентностью.
 

P1:	W(x)1
P2:		R(x)1	W(x)2
P3:				R(x)1	R(x)2
P4:				R(x)2	R(x)1

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

Процесс P1	Процесс P2
..........	..........
a = 1;	b = 1;
if (b==0) kill (P2);	if (a==0) kill (P1);
..........	..........

Оба процесса могут быть убиты, что невозможно при последовательной консистентности.
Модель процессорной консистентности отличается от модели PRAM консистентности тем, что в ней дополнительно требуется когерентность памяти: “Для каждой переменной x есть общее согласие относительно порядка, в котором процессоры модифицируют эту переменную, операции записи в разные переменные - параллельны”. Таким образом, к упорядочиванию записей каждого процессора добавляется упорядочивание записей в переменные или группы
 

6.3.5 Слабая консистентность

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

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

1. Доступ к синхронизационным переменным определяется моделью последовательной консистентности;
2. Доступ к синхронизационным переменным запрещен (задерживается), пока не выполнены все предыдущие операции записи;
3. Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущие обращения к синхронизационным переменным.

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

a) Пример допустимой последовательности событий.
 

P1:	W(x)1	W(x)2	S
P2:				R(x)1	R(x)2	S
P3:				R(x)2	R(x)1	S

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

P1:	W(x)1	W(x)2	S
P2:				S	R(x)1

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

6.3.6 Консистентность по выходу

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

(1) ACQUIRE - захват синхронизационной переменной, информирует систему о входе в критическую секцию;

(2) RELEASE - освобождение синхронизационной переменной, определяет завершение критической секции.

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

Пример допустимой последовательности событий для модели с консистентностью по выходу. (Acq(L) - захват синхронизационной переменной L; Rel(L) - освобождение синхронизационной переменной).
 

P1:	Acq(L)	W(x)1	W(x)2	Rel(L)
P2:					Acq(L)	R(x)2	Rel(L)
P3:								R(x)1

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

1. До выполнения обращения к общей переменной, должны быть полностью выполнены все предыдущие захваты синхронизационных переменных данным процессором.
2. Перед освобождением синхронизационной переменной должны быть закончены все операции чтения/записи, выполнявшиеся процессором прежде.
3. Реализация операций захвата и освобождения синхронизационной переменной должны удовлетворять требованиям процессорной консистентности (последовательная консистентность не требуется).

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

6.3.7 Консистентность по входу

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

• секция с монопольным доступом (для модификации переменных);
• секция с немонопольным доступом (для чтения переменных).

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

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

6.3.8 Сравнение моделей консистентности

(а) Модели консистентности, не использующие операции синхронизации.
 

Консистентность	Описание
Строгая	Упорядочение всех доступов к разделяемым данным по абсолютному времени
Последовательная	Все процессы видят все записи разделяемых данных в одном и том же порядке
Причинная	Все процессы видят все причинно-связанные записи данных в одном и том же порядке
Процессорная	PRAM-консистентность + когерентность памяти
PRAM	Все процессоры видят записи любого процессора в одном и том же порядке

(б) Модели консистентности с операциями синхронизации.
 

Консистентность	Описание
Слабая	Разделяемые данные можно считать консистентными только после выполнения синхронизации
По выходу	Разделяемые данные становятся консистентными после выхода из критической секции
По входу	Связанные с критической секцией разделяемые данные становятся консистентными при входе в нее

6.4 Протоколы когерентности

WRITE-UPDATE - организуется обновление копий у всех владельцов.

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

6.5 Конструкторские решения

6.5.1 Страничная DSM

К этому же типу DSM (не знающих заранее ничего о содержимом памяти) можно отнести и аппаратные реализации на базе кэшей (Convex SPP).
 

6.5.2 DSM на базе разделяемых переменных

Знание информации о режиме использования разделяемых переменных позволяет воспользоваться более эффективными протоколами когерентности.

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

s = 0;
izer = 0;
for (i = 1; i < L2-1; i++)
{
        r = A[i-1]*A[i+1];
        C[i] = r;
       s = s + r*r;
       if (A[i]==0) { izer = i};
}
A[izer] = 1;

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

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

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

s - редукционная переменная, используемая для суммирования;

izer - переменная, хранящая индекс последнего нулевого элемента массива А;

Приведения в консистентное состояние переменных A и r - не требуется.

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

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

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

Вне цикла приведение в консистентное состояние переменной A[izer] не требуется, поскольку на каждом процессоре выполняется один и тот же оператор, который присваивает одно и то же значение всем копиям переменной.
 

6.5.3 DSM на базе объектов

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