Принципы параллельных вычислений

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

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

• Разделение глобальных ресурсов чревато опасностями. Например, если два процесса используют одну глобальную переменную и оба выполняют чтение и запись этой переменной, то критическим оказывается порядок чтения и записи этой переменной разными процессами. Пример такой проблемы приведен в следующем подразделе.
• Операционной системе трудно управлять распределением ресурсов оптимальным образом. Например, процесс А может затребовать и получить контроль над некоторым каналом ввода-вывода, после чего временно приостановить работу. Нежелательно, чтобы операционная система при этом блокировала канал и не давала другим процессам возможности использовать его — такая политика может привести к возникновению условий взаимоблокировки, описываемых в главе 6, "Взаимоблокировка и голодание".
• Становится очень трудно обнаружить программную ошибку, поскольку обычно результат работы программы перестает быть детерминированным и воспроизводимым (см., например, [LEBL87, CARR89]).

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

Простой пример

Рассмотрим следующую процедуру:

void echo()
{
chin = getchar();
chout = chin;
putchar(chout);
}

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

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

• Процесс Р1 вызывает процедуру echo и прерывается немедленно по выполнении функции getchar. В этот момент последний введенный символ х сохранен в переменной chin.
• Активируется процесс Р2, который вызывает процедуру echo. Эта процедура выполняется до конца; при этом считывается с клавиатуры и выводится на экран очередной символ у.
• Продолжается выполнение процесса Р1. Однако к этому моменту значение х в переменной chin перезаписано — теперь эта переменная содержит значение у, которое присваивается переменной chout и выводится на экран.

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

• Процесс Р1 вызывает процедуру echo и прерывается немедленно по выполнении функции getchar. В этот момент последний введенный символ х сохранен в переменной chin.
• Активируется процесс Р2, который вызывает процедуру echo. Однако, поскольку приостановленный процесс Р1 находится в процедуре echo, P2 блокируется от входа л данную процедуру. Следовательно, выполнение Р2 приостанавливается до тех пор, пока процедура echo не окажется свободной.
• В некоторый более поздний момент продолжается выполнение процесса Р1,который завершает выполнение процедуры echo, выводя на экран верный символ х.
• После того как Р1 покидает echo, блокировка Р2 удаляется и позже, при возобновлении работы процесса Р2, им успешно выполняется процедура echo.

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

• Одновременно выполняются процессы Р1 и Р2 — каждый на своем процессоре. Оба процесса вызывают процедуру echo.
• Происходят следующие события (события в одной строке происходят параллельно):

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

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

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

Участие операционной системы

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

• Операционная система должна быть способна отслеживать различные активные процессы. Это осуществляется при  помощи управляющих блоков процессов,  как описано в главе 4, "Потоки,  симметричная мультипроцессорная обработка и микроядра".
• Операционная система должна распределять и освобождать различные ресурсы для каждого активного процесса, в том числе следующие.

Процессорное время: это функция планирования, рассматриваемая в части 4, "Планирование".
Память: большинство операционных систем используют схему виртуальной памяти. Этот вопрос рассматривается в части 3, "Память".
Файлы: обсуждаются в главе 12, "Управление файлами".
Устройства: ввода-вывода: обсуждаются в главе 11, "Управление вводом-выводом и дисковое планирование".

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

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

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

Способы взаимодействия процессов можно классифицировать по степени осведомленности одного процесса о существовании другого. В табл. 5.1 перечислены три возможные степени осведомленности.
Процессы не осведомлены о наличии друг друга. Это независимые процессы, не предназначенные для совместной работы. Наилучшим примером такой ситуации может служить многозадачность множества независимых процессов. Это могут быть пакетные задания, интерактивные сессии или смесь тех и других. Хотя эти процессы и не работают совместно, операционная система должна решать вопросы конкурентного использования ресурсов. Например, два независимых приложения могут затребовать доступ к одному и тому же диску или к принтеру. Операционная система должна регулировать такие обращения.
Процессы косвенно осведомлены о наличии друг друга. Эти процессы необязательно должны быть осведомлены о наличии друг друга с точностью до идентификатора процесса, однако они разделяют доступ к некоторому объекту, например буферу ввода-вывода. Такие процессы демонстрируют сотрудничество при разделении общего объекта.
Процессы непосредственно осведомлены о наличии друг друга. Такие процессы способны общаться один с другим с использованием идентификаторов процессов, и изначально созданы для совместной работы. Эти процессы также демонстрируют сотрудничество при работе.
Условия работы процессов не всегда можно определить так ясно и четко, как указано в табл. 5.1; более того, некоторые процессы одновременно проявляют способность и к конкуренции, и к сотрудничеству. Тем не менее рассмотрим приведенный список и определим участие операционной системы в перечисленных в нем ситуациях.
Таблица 5.1. Взаимодействие процессов

Конкуренция процессов в борьбе за ресурсы

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

Между конкурирующими процессами не происходит никакого обмена информацией. Однако выполнение одного процесса может повлиять на поведение конкурирующего процесса. В частности, если два процесса желают получить доступ к одному ресурсу, то операционная система выделит этот ресурс одному из процессов, в то время как второй процесс вынужден будет ожидать завершения работы с ресурсом первого. Таким образом, скорость работы процесса, которому отказано в немедленном доступе к ресурсу, уменьшается. В предельном случае блокированный процесс может никогда не получить доступ к ресурсу и, следовательно, никогда не сможет успешно завершиться.
В случае конкуренции процессов мы сталкиваемся с тремя проблемами. Первая их них — необходимость взаимных исключений (mutual exclusion). Предположим, что два или большее количество процессов требуют доступ к одному неразделяемому ресурсу, такому, как принтер. При выполнении каждый процесс посылает команды в устройство ввода-вывода, получает информацию о его состоянии, посылает и/или получает данные. Мы будем говорить о таком ресурсе как о критическом ресурсе, а о части программы, которая его использует, — как о критическом разделе (critical section) программы. Крайне важно, чтобы в критическом разделе в любой момент времени могла находиться только одна программа. Мы не можем полагаться на то, что операционная система распознает ситуацию и выполнит это условие, поскольку полные требования к ресурсу могут оказаться не очевидными. Например, во время печати файла требуется, чтобы отдельный процесс имел полный контроль над принтером, иначе на бумаге можно получить чередование строк двух файлов.

Осуществление взаимных исключений создает две дополнительные проблемы. Одна из них — взаимная блокировка (deadlock). Рассмотрим, например, два процесса — Р1 и Р2, и два ресурса — R1 и R2. Предположим, что каждому процессу для выполнения части своих функций требуется доступ к обоим ресурсам. Тогда возможно возникновение следующей ситуации: операционная система выделяет ресурс R1 процессу Р2, а ресурс R2 — процессу Р1. В результате каждый процесс ожидает получения одного из двух ресурсов; при этом ни один из них не освобождает уже имеющийся у него ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличия двух ресурсов. В результате процессы оказываются взаимно заблокированы.
Последняя проблема — голодание. Предположим, что у нас имеются три процесса (PI, P2, РЗ), каждому из которых периодически требуется доступ к ресурсу R. Представим ситуацию, в которой Р1 обладает ресурсом, а Р2 и РЗ приостановлены в ожидании освобождения ресурса. После выхода Р1 из критического раздела доступ к ресурсу будет получен одним из процессов Р2 и РЗ. Пусть операционная система предоставила доступ к ресурсу R процессу РЗ. Пока он работает с ресурсом, доступ к ресурсу вновь требуется процессу Р1. В результате по освобождении ресурса процессом РЗ может оказаться, что операционная система вновь предоставила доступ к ресурсу процессу Р1; тем временем процессу РЗ вновь требуется доступ к ресурсу R. Таким образом, теоретически возможна ситуация, в которой процесс Р2 никогда не получит доступа к требуемому ему ресурсу, несмотря на то что никакой взаимной блокировки в этом случае нет.
Управление конкуренцией неизбежно приводит к участию операционной системы в этом процессе, поскольку именно она распределяет ресурсы. Кроме того, процессам необходима возможность запрашивать взаимоисключение, такое, как блокировка ресурса перед его использованием. Любое решение этого вопроса требует поддержки операционной системы, например, такой, как обеспечение возможности блокировки. В листинге 5.1 показан абстрактный механизм взаимоисключений. Конструкция parbegin (Р1, Р2,..., Рn) означает приостановку выполнения основной программы, запуск параллельного выполнения процедур Р1,Р2,...,Рn и ожидание их завершения. По завершении всех запущенных процедур основная программа продолжает свою работу. В листинге 5.1 параллельно выполняются п процессов. Каждый процесс включает (1) критический раздел, работающий с некоторым ресурсом, идентификатором которого является целое число, и (2) остальную часть процедуры, в которой нет обращения к ресурсу. Для обеспечения взаимоисключения имеются две функции: entercritical и exitcritical. Каждая из них принимает в качестве аргумента имя ресурса, являющегося предметом конкуренции. Любой процесс, который пытается войти в критический раздел в то время, как в нем находится другой процесс, будет приостановлен.
Нам остается только рассмотреть механизм, обеспечивающий работу функций entercritical и exitcritical. Однако пока что мы отложим этот вопрос и приступим к рассмотрению других случаев взаимодействия процессов.

Листинг 5.1. Взаимные исключения

/* Программа взаимоисключений */
const int n = /* количество процессов */
void P(int i)
{
while
{
entercritical (i) ;
/*Критический раздел*/;
exitcritical(i);
/*Остальная часть процедуры*/;
}
}
void main ()
{
parbegin(P(Ri) ,P(R2) , . . . ,P(RJ ) ) ;
}

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

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

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

P1:
a =          a +       1;
b            =          b +       1;
P2:
b            =          2 *       b;
a =          2 *       a;

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

а = а + 1;
b = 2 * b;
b = b + 1;
a = 2 * a;

После выполнения этой последовательности действий условие а = b становится неверным. Например, если изначально а = b = 1, то по завершении вычислений а = 4 и b = 3. Проблема решается путем объявления критическим разделом каждой из последовательностей инструкций.

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

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

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

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

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

Требования к взаимным исключениям

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

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

Имеется ряд способов удовлетворения перечисленным условиям. Одним из них является передача ответственности за соответствие требованиям самому процессу, который должен выполняться параллельно. Таким образом, процесс, независимо от того, является ли он системной программой или приложением, должен координировать свои действия с другими процессами для работы взаимоисключений без поддержки со стороны языка программирования или операционной системы. Мы можем говорить о таком подходе как о программном. Хотя этот подход чреват большими накладными расходами и возможными ошибками, чрезвычайно полезно рассмотреть его для лучшего понимания сложностей, связанных с параллельными вычислениями. Этот вопрос будет рассмотрен в разделе 5.2. Другой подход, рассматриваемый в разделе 5.3, включает использование машинных команд специального назначения. Достоинство этого подхода заключается в снижении накладных расходов, но такой подход в общем случае проблему не решает. Еще один подход заключается в предоставлении определенного уровня поддержки со стороны операционной системы или языка программирования. Наиболее важные части такого подхода к решению проблемы взаимоисключений